Complexity of Linear Equations and Infinite Gadgets

Abstract

We investigate the descriptive set-theoretic complexity of the solvability of a Borel family of linear equations over a finite field. Answering a question of Thornton, we show that this problem is already hard, namely $\hat{I}{\pounds }_2^1$-complete. This implies that the split between easy and hard problems is at a different place in the Borel setting than in the case of the CSP Dichotomy.