Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-181 | 21st November 2010 04:57

Higher-order Fourier analysis of $\mathbb{F}_p^n$ and the complexity of systems of linear forms


Authors: Hamed Hatami, Shachar Lovett
Publication: 24th November 2010 23:21
Downloads: 2847


In this article we are interested in the density of small linear structures (e.g. arithmetic progressions) in subsets $A$ of the group $\mathbb{F}_p^n$. It is possible to express these densities as certain analytic averages involving $1_A$, the indicator function of $A$. In the higher-order Fourier analytic approach, the function $1_A$ is decomposed as a sum $f_1+f_2$ where $f_1$ is structured in the sense that it has a simple higher-order Fourier expansion, and $f_2$ is pseudorandom in the sense that the $k$th Gowers uniformity norm of $f_2$, denoted by $\|f_2\|_{U^k}$, is small for a proper value of $k$.

For a given linear structure, we find the smallest degree of uniformity $k$ such that assuming that $\|f_2\|_{U^k}$ is sufficiently small, it is possible to discard $f_2$ and replace $1_A$ with $f_1$, affecting the corresponding analytic average only negligibly. Previously, Gowers and Wolf solved this problem for the case where $f_1$ is a constant function. Furthermore, our main result solves Problem 7.6 in [W.T. Gowers and J.Wolf, Linear forms and higher-degree uniformity for functions on $\mathbb{F}_p^n$, Geom. Funct. Anal., to appear] regarding the analytic averages that involve more than one subset of $\mathbb{F}_p^n$.

ISSN 1433-8092 | Imprint