Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR14-040 | 7th May 2014 23:23

General systems of linear forms: equidistribution and true complexity

RSS-Feed




Revision #1
Authors: Hamed Hatami, Pooya Hatami, Shachar Lovett
Accepted on: 7th May 2014 23:23
Downloads: 934
Keywords: 


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$.



Changes to previous version:

Some minor typos are fixed.


Paper:

TR14-040 | 30th March 2014 07:53

General systems of linear forms: equidistribution and true complexity





TR14-040
Authors: Hamed Hatami, Pooya Hatami, Shachar Lovett
Publication: 31st March 2014 14:41
Downloads: 3234
Keywords: 


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 $\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$.



ISSN 1433-8092 | Imprint