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

- Department of Mathematics, University of California, Los Angeles
- More about Terence Tao

- Einstein Institute of Mathematics, Hebrew University of Jerusalem
- More about Tamar Ziegler

### Editorial introduction

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)=am(y)xm+⋯+a1(y)x+a0(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 ai that are all polynomials of degree at most n, from which it follows that the functions ai 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 ‖.‖Uk k=1,2,… (actually, ‖.‖U1 is just a seminorm) that provide a useful measure of quasirandomness. For example, let A be a subset of Zn of density δ and let fA(x) to be 1−δ if x∈A and −δ if x∉A. Then if ‖fA‖Uk is small, it can be shown that a randomly chosen set of the form {x,x+d,…,x+kd} has a probability approximately δ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‖∞≤1 and ‖f‖Uk≥c, then there is a “polynomially structured phase function” ϕ of degree at most k−1 (an example of such a function is exp(2πip(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 Uk 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:Zn→Zn be an arbitrary function. If we partition Zn into roughly equal intervals A and B, we can define f(x,y) to be exp(2πih(x)) if (x,y)∈A×A∪B×B and exp(2πih(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 ‖.‖∗Uk. A function f has small Uk-dual norm if it has a small inner product with every function with small Uk-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 Uk 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 Uk-dual norm: the cross-sections of the function described in the previous paragraph have random parts, so they have very large Uk-dual norm and therefore do not give counterexamples.

Thus, a function with small Uk-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 d1 in the first variable and degree d2 in the second, then it has polynomial structure of degree at most d1+d2 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+a2,x+2a2)) 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 Us+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