On the size of subsets of Fⁿ_q avoiding solutions to linear systems with repeated columns

Abstract

Consider a system of m balanced linear equations in k variables with coefficients in F_q. If k ⩾ 2m + 1, then a routine application of the slice rank method shows that there are constants β, γ ⩾ 1 with γ < q such that, for every subset S ⊆ Fⁿq of size at least β · γⁿ, the system has a solution (x₁, …, x_k) ∈ S^k with x₁, …, x_k not all equal. Building on a series of papers by Mimura and Tokushige and on a paper by Sauermann, this paper investigates the problem of finding a solution of higher non-degeneracy; that is, a solution where x₁, …, x_k are pairwise distinct, or even a solution where x₁, …, x_k do not satisfy any balanced linear equation that is not a linear combination of the equations in the system. In this paper, we focus on linear systems with repeated columns. For a large class of systems of this type, we prove that there are constants β, γ ⩾ 1 with γ < q such that every subset S ⊆ Fⁿq of size at least β · γⁿ contains a solution that is non-degenerate (in one of the two senses described above). This class is disjoint from the class covered by Sauermann’s result, and captures the systems studied by Mimura and Tokushige into a single proof. Moreover, a special case of our results shows that, if S ⊆ Fⁿp is a subset such that S − S does not contain a non-trivial k-term arithmetic progression (with p prime and 3 ⩽ k ⩽ p), then S must have exponentially small density.