The true complexity of a system of linear equations

Abstract

It is well-known that if a subset A of a finite Abelian group G satisfies a quasirandomness property called uniformity of degree k, then it contains roughly the expected number of arithmetic progressions of length k, that is, the number of progressions one would expect in a random subset of G of the same density as A. One is naturally led to ask which degree of uniformity is required of A in order to control the number of solutions to a general system of linear equations. Using so-called "quadratic Fourier analysis", we show that certain linear systems that were previously thought to require quadratic uniformity are in fact governed by linear uniformity. More generally, we conjecture a necessary and sufficient condition on a linear system L which guarantees that any subset A of F_p^n which is uniform of degree k contains the expected number of solutions to L.

30 pages

References in corpus (3)

• An inverse theorem for the Gowers U^3 norm
• Montreal Lecture Notes on Quadratic Fourier Analysis
• Linear Equations in Primes

Cited by in corpus (32)

• On Roth's theorem on progressions
• Linear forms and higher-degree uniformity for functions on ${\mathbb{F}}_p^n$
• On higher order Fourier analysis
• Concatenation theorems for anti-Gowers-uniform functions and Host-Kra characteristic factors
• Relational mechanics of shape and scale
• On polynomial configurations in fractal sets
• Linear forms and quadratic uniformity for functions on ${\mathbb{F}}_p^n$
• Gowers norms, regularization and limits of functions on abelian groups
• Linear forms and quadratic uniformity for functions on ${\mathbb{Z}}_N$
• On uniformity of $q$-multiplicative sequences
• The inverse conjecture for the Gowers norm over finite fields in low characteristic
• Quantitative bounds in the inverse theorem for the Gowers $U^{s+1}$-norms over cyclic groups
• Testing Linear-Invariant Non-Linear Properties
• Bootstrapping partition regularity of linear systems
• Polynomial patterns in the primes
• Finite configurations in sparse sets
• Sparse graph counting and Kelley-Meka bounds for binary systems
• True complexity of polynomial progressions in finite fields
• True complexity and iterated Cauchy--Schwarz
• Gowers norms control diophantine inequalities
• Higher-order Fourier analysis of ${\mathbb{F}}_p^n$ and the complexity of systems of linear forms
• On the asymptotic maximal density of a set avoiding solutions to linear equations modulo a prime
• Quasirandomness in additive groups and hypergraphs
• On a conjecture of Gowers and Wolf
• Stability and exact Turan numbers for matroids
• Correlation Testing for Affine Invariant Properties on ${\mathbb{F}}_p^n$ in the High Error Regime
• Induced arithmetic removal for partition-regular patterns of complexity 1
• Higher-order generalizations of stability and arithmetic regularity
• A non-flag arithmetic regularity lemma and counting lemma
• Local aspects of the Sidorenko property for linear equations
• Noise Correlation Bounds for Uniform Low Degree Functions
• Convergence results for systems of linear forms on cyclic groups, and periodic nilsequences