ECCC-Report TR10-181https://eccc.weizmann.ac.il/report/2010/181Comments and Revisions published for TR10-181en-usWed, 24 Nov 2010 23:21:46 +0200
Paper TR10-181
| Higher-order Fourier analysis of $\mathbb{F}_p^n$ and the complexity of systems of linear forms |
Hamed Hatami,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2010/181In 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$.Wed, 24 Nov 2010 23:21:46 +0200https://eccc.weizmann.ac.il/report/2010/181