2021/11/18 by Josse van Dobben de Bruyn, de Bruyn, Josse van Dobben, Dion Gijswijt +1
Computer Science · Mathematics · #05D40 (Primary) #11B25 (Secondary) #Advanced Graph Theory Research #Analytic Number Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2111.09879
openalex publication_date 2021/11/18 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
Consider a system of m balanced linear equations in k variables with coefficients in \mathbbFq. 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 ⊆ \mathbbFqn of size at least β⋅ γn, the system has a solution (x1,…,xk) ∈ Sk with x1,…,xk 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 x1,…,xk are pairwise distinct, or even a solution where x1,…,xk 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 ⊆ \mathbbFqn of size at least β⋅ γn 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 ⊆ \mathbbFpn 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.