Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

#### General systems of linear forms: equidistribution and true complexity

Revision #1
Authors: Hamed Hatami, Pooya Hatami, Shachar Lovett
Accepted on: 7th May 2014 23:23
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