General systems of linear forms: equidistribution and true complexity

DOI10.1016/J.AIM.2016.01.019MaRDI QIDQ5965073zbMATH OpenOpenAlexFDO

Authors Hamed Hatami, Pooya Hatami, Shachar Lovett

Publication date 2 March 2016

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.7703

zbMATH Keywords

additive combinatoricshigher-order Fourier analysislinear patternsnonclassical polynomials

Mathematics Subject Classification ID

Arithmetic progressions (11B25) Arithmetic combinatorics; higher degree uniformity (11B30) Other character sums and Gauss sums (11T24)

Abstract: The densities of small linear structures (such as arithmetic progressions) in subsets of Abelian groups can be expressed as certain analytic averages involving linear forms. Higher-order Fourier analysis examines such averages by approximating the indicator function of a subset by a function of bounded number of polynomials. Then, to approximate the average, it suffices to know the joint distribution of the polynomials applied to the linear forms. We prove a near-equidistribution theorem that describes these distributions for the group $mathbb{F}_p^n$ when $p$ is a fixed prime. This fundamental fact is equivalent to a strong near-orthogonality statement regarding the higher-order characters, and was previously known only under various extra assumptions about the linear forms. As an application of our near-equidistribution theorem, we settle a conjecture of Gowers and Wolf on the true complexity of systems of linear forms for the group $mathbb{F}_p^n$.

Review text

The paper is a continuation of the authors' previous paper [\textit{A. Bhattacharyya} et al., in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC 2013. Palo Alto, CA, USA, June 1--4, 2013. New York, NY: ACM, 429--436 (2013; Zbl 1293.11016)]. The density of a linear system in subsets of Abelian groups is analysed by high-order Fourier analysis.NEWLINENEWLINEA complete characterization for a special type of distributions for arbitrary systems of linear forms is given.NEWLINENEWLINESome interesting applications are discussed, one of which -- an idea for a new theory of homogeneous non-classical polynomials.

Recommendations

• The true complexity of a system of linear equations
• Higher-order Fourier analysis of \(\mathbb F_p^n\) and the complexity of systems of linear forms
• Linear forms and higher-degree uniformity for functions on \(\mathbb F^n_p\)
• Linear forms and quadratic uniformity for functions on F^n_p
• Linear equations in primes and dynamics of nilmanifolds

Cites work

• A new proof of Szemerédi's theorem
• An arithmetic regularity lemma, an associated counting lemma, and applications
• An inverse theorem for the Gowers \(U^{s+1}[N]\)-norm
• An inverse theorem for the uniformity seminorms associated with the action of \(\mathbb F_p^\infty\)
• Decompositions, approximate structure, transference, and the Hahn-Banach theorem
• Every locally characterized affine-invariant property is testable
• Higher-order Fourier analysis of \(\mathbb F_p^n\) and the complexity of systems of linear forms
• scientific article; zbMATH DE number 5219603 (Why is no real title available?)
• Linear equations in primes
• Linear forms and higher-degree uniformity for functions on \(\mathbb F^n_p\)
• Low-degree tests at large distances
• Testing low complexity affine-invariant properties
• The distribution of polynomials over finite fields, with applications to the Gowers norms
• The inverse conjecture for the Gowers norm over finite fields in low characteristic
• The inverse conjecture for the Gowers norm over finite fields via the correspondence principle
• The true complexity of a system of linear equations

Cited in

(13)

• Induced arithmetic removal: complexity 1 patterns over finite fields
• Stability and exact Turán numbers for matroids
• A counting lemma for binary matroids and applications to extremal problems
• A refinement of Cauchy-Schwarz complexity
• On sets of linear forms of maximal complexity
• Convergence results for systems of linear forms on cyclic groups and periodic nilsequences
• Good bounds in certain systems of true complexity one
• Higher order Fourier analysis
• Testing Linear-Invariant Properties
• True complexity of polynomial progressions in finite fields
• The true complexity of a system of linear equations
• Higher-order Fourier analysis of \(\mathbb F_p^n\) and the complexity of systems of linear forms
• Induced arithmetic removal for partition-regular patterns of complexity 1

This page was built for publication: General systems of linear forms: equidistribution and true complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5965073)