Quantitative bounds for the $U^4$-inverse theorem over low characteristic finite fields

Quantitative bounds for the $U^4$-inverse theorem over low characteristic finite fields, Discrete Analysis 2022:14, 17 pp.

Let $G$ be a finite Abelian group and let $f$ be a complex-valued function defined on $G$. For each $a\in G$ let $\partial_af$ be the function given by the formula
$$\partial_af(x) = f(x)\overline{f(x-a)}.$$
Then for every integer $k\geq 2$ we can define a norm $\|.\|_{U^k}$ on $\mathbb C^G$ by the formula
$$\|f\|_{U^k}^{2^k}=\mathbb E_{x,a_1,\dots,a_k}\partial_{a_1}\dots\partial_{a_k}f(x),$$
where $x,a_1,\dots,a_k$ are chosen uniformly and independently from $G$. It is not immediately obvious that this is a norm, but it can be shown to be with the help of multiple applications of the Cauchy-Schwarz inequality. (When $k=1$ the formula is still meaningful, but it simplifies to $|\mathbb E_xf(x)|$, which is not a norm but a seminorm, since it can equal zero for non-zero functions $f$.)

The $U^k$ norms play an important role in additive combinatorics because they lead to a useful definition of quasirandomness for subsets of finite Abelian groups. For example, let $k$ be a positive integer, let $G$ be a finite Abelian group such that $|G|$ has no non-trivial factors less than $k$, let $A\subset G$ be a subset of density $\alpha$, and for each $x\in G$, let $f(x)=A(x)-\alpha$, where $A(x)=1$ if $x\in A$ and 0 otherwise. Then for every $\epsilon>0$ there exists $c=c(\epsilon,k)>0$ such that if $\|f\|_{U^k}\leq\epsilon$, then
$$|\mathbb E_{x,d}A(x)A(x+d)\dots A(x+(k-1)d)-\alpha^k|\leq\epsilon.$$
If $A$ is a random subset of $G$ of density $\alpha$, then the expectation of $\mathbb E_{x,d}A(x)A(x+d)\dots A(x+(k-1)d)$ is very close to $\alpha^k$ (the only reason we do not have equality is that when $d=0$ the events $x+jd\in A$ are not independent), so the inequality above tells us that the number of arithmetic progressions in $A$ of length $k$ is roughly what it would be in a random set of the same density.

This fact focuses attention on what one can say about a function $f$ if it takes values in $[-1,1]$ but does not have a small $U^k$ norm. When $k=2$, a straightforward argument shows that $f$ must have a large Fourier coefficient, or equivalently that there is some character $\chi:G\to\mathbb C$ such that $\langle f,\chi\rangle$ is large in absolute value. However, when $k>2$, the question becomes surprisingly difficult.

When $G=\mathbb F_p^n$ for a prime $p$, and when $p\geq k$, a result of Bergelson, Tao and Ziegler shows that $f$ correlates with a polynomial phase function of degree at most $k-1$. That is, if $f:\mathbb F_p^n\to\mathbb C$ is a function with $|f(x)|\leq 1$ for every $x$, and if $\|f\|_{U^k}\geq c>0$, then there is a polynomial $P$ in $n$ variables of total degree at most $k-1$ such that $|\mathbb E_xf(x)e^{-2\pi iP(x)/p}|\geq c'$, where $c'$ is a positive constant that depends on $c$ only.

This result, known as an inverse theorem for the $U^k$ norm, was proved using infinitary methods, and therefore did not give an explicit dependence of $c'$ on $c$. Such a dependence was known when $k=3$, thanks to an earlier result of Green and Tao, and was obtained for general $k$ by Gowers and Miličevič (though the bound they obtained is unlikely to be optimal).

Another direction in which the result was strengthened was to remove the condition that $p\geq k$. It had been discovered by Green and Tao, and independently by Lovett, Meshulam, and Samorodnitsky, that the conclusion of the theorem was no longer true in general, and that it was necessary to introduce “non-classical polynomial phase functions” to obtain a correct statement. Tao and Ziegler followed up on the result described above with an inverse theorem in low characteristic, showing that a function with large $U^k$ norm must correlate with a non-classical polynomial phase function.

However, it remains open to combine these two directions and prove a quantitative inverse theorem in the low-characteristic case. That is the problem addressed in this paper, which proves such a result when $k=4$ and sets out a clear programme for doing so for general $k$. The proof uses several elements of the proof of Gowers and Miličevič but departs from it at a point where the latter uses a polarization identity that requires dividing by $(k-1)!$.

An example of a non-classical polynomial can be constructed as follows. Consider first the map $\phi:\mathbb F_2\to\mathbb Z/4\mathbb Z$ that sends 0 to 0 and 1 to 1. One can check that $\phi(x)-\phi(x-a)=-a$ if $x=0$ and $a$ if $x=1$, and that $\phi(x)-\phi(x-a)-\phi(x-b)+\phi(x-a-b)=-2$ if $x=0, a=b=1$, $2$ if $x=a=b=1$, and 0 otherwise. Since $-2=2$ in $\mathbb Z/4\mathbb Z$, it follows that $\phi(x)-\phi(x-a)-\phi(x-b)+\phi(x-a-b)$ does not depend on $x$. From this it follows that if we set $g(x)$ to be $i^{\phi(x)}$, then for every $a,b,c,x\in\mathbb F_2$ we have that $\partial_a\partial_b\partial_cg(x)=1$.

If we now define a function $f:\mathbb F_2^n\to\mathbb C$ by $f(x)=\prod_jg(x_j)$, then $\partial_a\partial_b\partial_cf(x)=1$ for every $x,a,b,c\in\mathbb F_2^n$, so $\|f\|_{U^3}=1$. However, $f$ is not of the form $(-1)^P$ for a quadratic function $P:\mathbb F_2^n\to\mathbb F_2$. As it happens, Samorodnitsky has proved a quantitative $U^3$ inverse theorem for functions defined on $\mathbb F_2^n$ that does not require non-classical polynomials, but in general they are needed. Thus, the result of this paper is the first quantitative inverse theorem for a case where non-classical polynomials necessarily appear.