Concatenation theorems for anti-Gowers-uniform functions and Host-Kra characteristic factors

Concatenation theorems for anti-Gowers-uniform functions and Host-Kra characteristic factors, Discrete Analysis 2016:13, 61 pp.

It is a straightforward exercise to show that if $f$ is a function of two integer variables, and $f(x,y)$ is a polynomial of degree $m$ in $x$ when $y$ is fixed and degree $n$ in $y$ when $x$ is fixed, then $f$ is a polynomial of degree at most $m+n$ in $x$ and $y$. Indeed, the first assumption tells us that $f$ has a formula of the form $f(x,y)=a_m(y)x^m+\dots+a_1(y)x+a_0(y)$. If we now apply the second assumption for $m+1$ different values of $x$, we obtain $m+1$ independent linear combinations of the functions $a_i$ that are all polynomials of degree at most $n$, from which it follows that the functions $a_i$ are themselves polynomials of degree at most $n$.

One of the main results of this paper is a similar fact for a weaker notion of polynomial structure that is of central importance in additive combinatorics, based on the so-called uniformity norms. These are a sequence of norms $\|.\|_{U^k}$ $k=1,2,\dots$ (actually, $\|.\|_{U^1}$ is just a seminorm) that provide a useful measure of quasirandomness. For example, let $A$ be a subset of $\mathbb Z_n$ of density $\delta$ and let $f_A(x)$ to be $1-\delta$ if $x\in A$ and $-\delta$ if $x\notin A$. Then if $\|f_A\|_{U^k}$ is small, it can be shown that a randomly chosen set of the form $\{x,x+d,\dots,x+kd\}$ has a probability approximately $\delta^{k+1}$ of being a subset of $A$, showing that in a certain sense $A$ “seems random to arithmetic progressions of length at most $k+1$”. A fundamental and very difficult result due to the authors of the present paper together with Ben Green [1] shows that if $\|f\|_\infty\leq 1$ and $\|f\|_{U^k}\geq c$, then there is a “polynomially structured phase function” $\phi$ of degree at most $k-1$ (an example of such a function is $\exp(2\pi i p(x)/n)$, where $p$ is a polynomial of degree $k-1$ with integer coefficients, but for the theorem to be true one has to generalize in a non-obvious way to a much wider class of examples) that correlates well with $f$. Thus, in a certain sense a function with a large $U^k$ norm exhibits polynomial structure of degree $k-1$.

This notion of polynomial structure is too weak for a theorem of the kind proved by the authors, as a simple example shows. Let $h:\mathbb Z_n\to\mathbb Z_n$ be an arbitrary function. If we partition $\mathbb Z_n$ into roughly equal intervals $A$ and $B$, we can define $f(x,y)$ to be $\exp(2\pi ih(x))$ if $(x,y)\in A\times A\cup B\times B$ and $\exp(2\pi i h(y))$ otherwise. Then for each fixed $x$ the function $f$ is constant on $A$ or $B$ as $x$ varies, and for each fixed $y$ it is constant on $A$ or $B$ as $x$ varies. But $h$ could be a random function, so there is no hope of any joint structure.

However, the picture changes if we look at the dual norms $\|.\|_{U^k}^*$. A function $f$ has small $U^k$-dual norm if it has a small inner product with every function with small $U^k$-norm. Intuitively, what this says is that $f$ does not have any part that fail to be polynomially structured (since if it did, then we could create a function $g$ with small $U^k$ norm, based on the unstructured part of $f$, and it would have large inner product with $f$. It is reasonable to hope for a concatenation theorem for functions with small $U^k$-dual norm: the cross-sections of the function described in the previous paragraph have random parts, so they have very large $U^k$-dual norm and therefore do not give counterexamples.

Thus, a function with small $U^k$-dual norm can be thought of as having polynomial structure of degree at most $k-1$ “everywhere”. This is still a weakish notion of polynomial structure, but with the help of the inverse theorem, one can translate it into a more explicit description of the functions. However, the authors do not use the inverse theorem to prove their results, which roughly speaking state that if a function of two variables has polynomial structure of this kind of degree $d_1$ in the first variable and degree $d_2$ in the second, then it has polynomial structure of degree at most $d_1+d_2$ in the two variables together.

The actual statements are more complicated, and are motivated by applications. In particular, in a companion paper [2] the authors use the results of this paper to obtain asymptotics for the number of polynomial configurations of various kinds (for example, $(x,x+a^2,x+2a^2)$) in the primes.

A more detailed discussion of these results (but not as detailed as the paper itself) can be found in this blog post of Terence Tao. See also the video below.

[1] B. J. Green, T. Tao and T. Ziegler, An inverse theorem for the Gowers $U^{s+1}[N]$-norm, Ann. of Math. (2) 176 (2012), no. 2, 1231–1372. arXiv:1009.3998

[2] T. Tao and T. Ziegler, Polynomial patterns in the primes, arXiv:1603.07817