Tag Archive

You are currently browsing the tag archive for the ‘Gowers uniformity norms’ tag.

Erratum for “An inverse theorem for the Gowers U^{s+1}[N]-norm”

25 April, 2024 in math.CO, update | Tags: Ben Green, erratum, Gowers uniformity norms, Tamar Ziegler | by Terence Tao | 10 comments

The purpose of this post is to report an erratum to the 2012 paper “An inverse theorem for the Gowers ${U^{s+1}[N]}$ -norm” of Ben Green, myself, and Tamar Ziegler (previously discussed in this blog post). The main results of this paper have been superseded with stronger quantitative results, first in work of Manners (using somewhat different methods), and more recently in a remarkable paper of Leng, Sah, and Sawhney which combined the methods of our paper with several new innovations to obtain quite strong bounds (of quasipolynomial type); see also an alternate proof of our main results (again by quite different methods) by Candela and Szegedy. In the course of their work, they discovered some fixable but nontrivial errors in our paper. These (rather technical) issues were already implicitly corrected in this followup work which supersedes our own paper, but for the sake of completeness we are also providing a formal erratum for our original paper, which can be found here. We thank Leng, Sah, and Sawhney for bringing these issues to our attention.

Excluding some minor (mostly typographical) issues which we also have reported in this erratum, the main issues stemmed from a conflation of two notions of a degree ${s}$ filtration

$\displaystyle G = G_0 \geq G_1 \geq \dots \geq G_s \geq G_{s+1} = \{1\}$

of a group ${G}$ , which is a nested sequence of subgroups that obey the relation ${[G_i,G_j] \leq G_{i+j}}$ for all ${i,j}$ . The weaker notion (sometimes known as a prefiltration) permits the group ${G_1}$ to be strictly smaller than ${G_0}$ , while the stronger notion requires ${G_0}$ and ${G_1}$ to equal. In practice, one can often move between the two concepts, as ${G_1}$ is always normal in ${G_0}$ , and a prefiltration behaves like a filtration on every coset of ${G_1}$ (after applying a translation and perhaps also a conjugation). However, we did not clarify this issue sufficiently in the paper, and there are some places in the text where results that were only proven for filtrations were applied for prefiltrations. The erratum fixes this issues, mostly by clarifying that we work with filtrations throughout (which requires some decomposition into cosets in places where prefiltrations are generated). Similar adjustments need to be made for multidegree filtrations and degree-rank filtrations, which we also use heavily on our paper.

In most cases, fixing this issue only required minor changes to the text, but there is one place (Section 8) where there was a non-trivial problem: we used the claim that the final group ${G_s}$ was a central group, which is true for filtrations, but not necessarily for prefiltrations. This fact (or more precisely, a multidegree variant of it) was used to claim a factorization for a certain product of nilcharacters, which is in fact not true as stated. In the erratum, a substitute factorization for a slightly different product of nilcharacters is provided, which is still sufficient to conclude the main result of this part of the paper (namely, a statistical linearization of a certain family of nilcharacters in the shift parameter ${h}$ ).

Again, we stress that these issues do not impact the paper of Leng, Sah, and Sawhney, as they adapted the methods in our paper in a fashion that avoids these errors.

A Host–Kra F^omega_2-system of order 5 that is not Abramov of order 5, and non-measurability of the inverse theorem for the U^6(F^n_2) norm; The structure of totally disconnected Host–Kra–Ziegler factors, and the inverse theorem for the U^k Gowers uniformity norms on finite abelian groups of bounded torsion

10 March, 2023 in math.CO, math.DS, paper | Tags: Asgar Jamneshan, Gowers uniformity norms, Gowers-Host-Kra seminorms, inverse conjecture for the Gowers norm, Or Shalom | by Terence Tao | 3 comments

Asgar Jamneshan, Or Shalom, and myself have just uploaded to the arXiv our preprints “A Host–Kra ${{\bf F}^\omega_2}$ -system of order 5 that is not Abramov of order 5, and non-measurability of the inverse theorem for the ${U^6({\bf F}^n_2)}$ norm” and “The structure of totally disconnected Host–Kra–Ziegler factors, and the inverse theorem for the ${U^k}$ Gowers uniformity norms on finite abelian groups of bounded torsion“. These two papers are both concerned with advancing the inverse theory for the Gowers norms and Gowers-Host-Kra seminorms; the first paper provides a counterexample in this theory (in particular disproving a conjecture of Bergelson, Ziegler and myself), and the second paper gives new positive results in the case when the underlying group is bounded torsion, or the ergodic system is totally disconnected. I discuss the two papers more below the fold.

Read the rest of this entry »

Notes on inverse theorem entropy

27 May, 2022 in expository, math.CO, math.PR | Tags: entropy, Gowers uniformity norms, random sampling | by Terence Tao | 7 comments

Let ${G}$ be a finite set of order ${N}$ ; in applications ${G}$ will be typically something like a finite abelian group, such as the cyclic group ${{\bf Z}/N{\bf Z}}$ . Let us define a ${1}$ -bounded function to be a function ${f: G \rightarrow {\bf C}}$ such that ${|f(n)| \leq 1}$ for all ${n \in G}$ . There are many seminorms ${\| \|}$ of interest that one places on functions ${f: G \rightarrow {\bf C}}$ that are bounded by ${1}$ on ${1}$ -bounded functions, such as the Gowers uniformity seminorms ${\| \|_k}$ for ${k \geq 1}$ (which are genuine norms for ${k \geq 2}$ ). All seminorms in this post will be implicitly assumed to obey this property.

In additive combinatorics, a significant role is played by inverse theorems, which abstractly take the following form for certain choices of seminorm ${\| \|}$ , some parameters ${\eta, \varepsilon>0}$ , and some class ${{\mathcal F}}$ of ${1}$ -bounded functions:

Theorem 1 (Inverse theorem template) If ${f}$ is a ${1}$ -bounded function with ${\|f\| \geq \eta}$ , then there exists ${F \in {\mathcal F}}$ such that ${|\langle f, F \rangle| \geq \varepsilon}$ , where ${\langle,\rangle}$ denotes the usual inner product
$\displaystyle \langle f, F \rangle := {\bf E}_{n \in G} f(n) \overline{F(n)}.$

Informally, one should think of ${\eta}$ as being somewhat small but fixed independently of ${N}$ , ${\varepsilon}$ as being somewhat smaller but depending only on ${\eta}$ (and on the seminorm), and ${{\mathcal F}}$ as representing the “structured functions” for these choices of parameters. There is some flexibility in exactly how to choose the class ${{\mathcal F}}$ of structured functions, but intuitively an inverse theorem should become more powerful when this class is small. Accordingly, let us define the ${(\eta,\varepsilon)}$ -entropy of the seminorm ${\| \|}$ to be the least cardinality of ${{\mathcal F}}$ for which such an inverse theorem holds. Seminorms with low entropy are ones for which inverse theorems can be expected to be a useful tool. This concept arose in some discussions I had with Ben Green many years ago, but never appeared in print, so I decided to record some observations we had on this concept here on this blog.

Lebesgue norms ${\| f\|_{L^p} := ({\bf E}_{n \in G} |f(n)|^p)^{1/p}}$ for ${1 < p < \infty}$ have exponentially large entropy (and so inverse theorems are not expected to be useful in this case):

Proposition 2 ( ${L^p}$ norm has exponentially large inverse entropy) Let ${1 < p < \infty}$ and ${0 < \eta < 1}$ . Then the ${(\eta,\eta^p/4)}$ -entropy of ${\| \|_{L^p}}$ is at most ${(1+8/\eta^p)^N}$ . Conversely, for any ${\varepsilon>0}$ , the ${(\eta,\varepsilon)}$ -entropy of ${\| \|_{L^p}}$ is at least ${\exp( c \varepsilon^2 N)}$ for some absolute constant ${c>0}$ .

Proof: If ${f}$ is ${1}$ -bounded with ${\|f\|_{L^p} \geq \eta}$ , then we have

$\displaystyle |\langle f, |f|^{p-2} f \rangle| \geq \eta^p$

and hence by the triangle inequality we have

$\displaystyle |\langle f, F \rangle| \geq \eta^p/2$

where ${F}$ is either the real or imaginary part of ${|f|^{p-2} f}$ , which takes values in ${[-1,1]}$ . If we let ${\tilde F}$ be ${F}$ rounded to the nearest multiple of ${\eta^p/4}$ , then by the triangle inequality again we have

$\displaystyle |\langle f, \tilde F \rangle| \geq \eta^p/4.$

There are only at most ${1+8/\eta^p}$ possible values for each value ${\tilde F(n)}$ of ${\tilde F}$ , and hence at most ${(1+8/\eta^p)^N}$ possible choices for ${\tilde F}$ . This gives the first claim.

Now suppose that there is an ${(\eta,\varepsilon)}$ -inverse theorem for some ${{\mathcal F}}$ of cardinality ${M}$ . If we let ${f}$ be a random sign function (so the ${f(n)}$ are independent random variables taking values in ${-1,+1}$ with equal probability), then there is a random ${F \in {\mathcal F}}$ such that

$\displaystyle |\langle f, F \rangle| \geq \varepsilon$

and hence by the pigeonhole principle there is a deterministic ${F \in {\mathcal F}}$ such that

$\displaystyle {\bf P}( |\langle f, F \rangle| \geq \varepsilon ) \geq 1/M.$

On the other hand, from the Hoeffding inequality one has

$\displaystyle {\bf P}( |\langle f, F \rangle| \geq \varepsilon ) \ll \exp( - c \varepsilon^2 N )$

for some absolute constant ${c}$ , hence

$\displaystyle M \geq \exp( c \varepsilon^2 N )$

as claimed. $\Box$

Most seminorms of interest in additive combinatorics, such as the Gowers uniformity norms, are bounded by some finite ${L^p}$ norm thanks to Hölder’s inequality, so from the above proposition and the obvious monotonicity properties of entropy, we conclude that all Gowers norms on finite abelian groups ${G}$ have at most exponential inverse theorem entropy. But we can do significantly better than this:

For the ${U^1}$ seminorm ${\|f\|_{U^1(G)} := |{\bf E}_{n \in G} f(n)|}$ , one can simply take ${{\mathcal F} = \{1\}}$ to consist of the constant function ${1}$ , and the ${(\eta,\eta)}$ -entropy is clearly equal to ${1}$ for any ${0 < \eta < 1}$ .
For the ${U^2}$ norm, the standard Fourier-analytic inverse theorem asserts that if ${\|f\|_{U^2(G)} \geq \eta}$ then ${|\langle f, e(\xi \cdot) \rangle| \geq \eta^2}$ for some Fourier character ${\xi \in \hat G}$ . Thus the ${(\eta,\eta^2)}$ -entropy is at most ${N}$ .
For the ${U^k({\bf Z}/N{\bf Z})}$ norm on cyclic groups for ${k > 2}$ , the inverse theorem proved by Green, Ziegler, and myself gives an ${(\eta,\varepsilon)}$ -inverse theorem for some ${\varepsilon \gg_{k,\eta} 1}$ and ${{\mathcal F}}$ consisting of nilsequences ${n \mapsto F(g(n) \Gamma)}$ for some filtered nilmanifold ${G/\Gamma}$ of degree ${k-1}$ in a finite collection of cardinality ${O_{\eta,k}(1)}$ , some polynomial sequence ${g: {\bf Z} \rightarrow G}$ (which was subsequently observed by Candela-Sisask (see also Manners) that one can choose to be ${N}$ -periodic), and some Lipschitz function ${F: G/\Gamma \rightarrow {\bf C}}$ of Lipschitz norm ${O_{\eta,k}(1)}$ . By the Arzela-Ascoli theorem, the number of possible ${F}$ (up to uniform errors of size at most ${\varepsilon/2}$ , say) is ${O_{\eta,k}(1)}$ . By standard arguments one can also ensure that the coefficients of the polynomial ${g}$ are ${O_{\eta,k}(1)}$ , and then by periodicity there are only ${O(N^{O_{\eta,k}(1)}}$ such polynomials. As a consequence, the ${(\eta,\varepsilon)}$ -entropy is of polynomial size ${O_{\eta,k}( N^{O_{\eta,k}(1)} )}$ (a fact that seems to have first been implicitly observed in Lemma 6.2 of this paper of Frantzikinakis; thanks to Ben Green for this reference). One can obtain more precise dependence on ${\eta,k}$ using the quantitative version of this inverse theorem due to Manners; back of the envelope calculations using Section 5 of that paper suggest to me that one can take ${\varepsilon = \eta^{O_k(1)}}$ to be polynomial in ${\eta}$ and the entropy to be of the order ${O_k( N^{\exp(\exp(\eta^{-O_k(1)}))} )}$ , or alternatively one can reduce the entropy to ${O_k( \exp(\exp(\eta^{-O_k(1)})) N^{\eta^{-O_k(1)}})}$ at the cost of degrading ${\varepsilon}$ to ${1/\exp\exp( O(\eta^{-O(1)}))}$ .
If one replaces the cyclic group ${{\bf Z}/N{\bf Z}}$ by a vector space ${{\bf F}_p^n}$ over some fixed finite field ${{\bf F}_p}$ of prime order (so that ${N=p^n}$ ), then the inverse theorem of Ziegler and myself (available in both high and low characteristic) allows one to obtain an ${(\eta,\varepsilon)}$ -inverse theorem for some ${\varepsilon \gg_{k,\eta} 1}$ and ${{\mathcal F}}$ the collection of non-classical degree ${k-1}$ polynomial phases from ${{\bf F}_p^n}$ to ${S^1}$ , which one can normalize to equal ${1}$ at the origin, and then by the classification of such polynomials one can calculate that the ${(\eta,\varepsilon)}$ entropy is of quasipolynomial size ${\exp( O_{p,k}(n^{k-1}) ) = \exp( O_{p,k}( \log^{k-1} N ) )}$ in ${N}$ . By using the recent work of Gowers and Milicevic, one can make the dependence on ${p,k}$ here more precise, but we will not perform these calcualtions here.
For the ${U^3(G)}$ norm on an arbitrary finite abelian group, the recent inverse theorem of Jamneshan and myself gives (after some calculations) a bound of the polynomial form ${O( q^{O(n^2)} N^{\exp(\eta^{-O(1)})})}$ on the ${(\eta,\varepsilon)}$ -entropy for some ${\varepsilon \gg \eta^{O(1)}}$ , which one can improve slightly to ${O( q^{O(n^2)} N^{\eta^{-O(1)}})}$ if one degrades ${\varepsilon}$ to ${1/\exp(\eta^{-O(1)})}$ , where ${q}$ is the maximal order of an element of ${G}$ , and ${n}$ is the rank (the number of elements needed to generate ${G}$ ). This bound is polynomial in ${N}$ in the cyclic group case and quasipolynomial in general.

For general finite abelian groups ${G}$ , we do not yet have an inverse theorem of comparable power to the ones mentioned above that give polynomial or quasipolynomial upper bounds on the entropy. However, there is a cheap argument that at least gives some subexponential bounds:

Proposition 3 (Cheap subexponential bound) Let ${k \geq 2}$ and ${0 < \eta < 1/2}$ , and suppose that ${G}$ is a finite abelian group of order ${N \geq \eta^{-C_k}}$ for some sufficiently large ${C_k}$ . Then the ${(\eta,c_k \eta^{O_k(1)})}$ -complexity of ${\| \|_{U^k(G)}}$ is at most ${O( \exp( \eta^{-O_k(1)} N^{1 - \frac{k+1}{2^k-1}} ))}$ .

Proof: (Sketch) We use a standard random sampling argument, of the type used for instance by Croot-Sisask or Briet-Gopi (thanks to Ben Green for this latter reference). We can assume that ${N \geq \eta^{-C_k}}$ for some sufficiently large ${C_k>0}$ , since otherwise the claim follows from Proposition 2.

Let ${A}$ be a random subset of ${{\bf Z}/N{\bf Z}}$ with the events ${n \in A}$ being iid with probability ${0 < p < 1}$ to be chosen later, conditioned to the event ${|A| \leq 2pN}$ . Let ${f}$ be a ${1}$ -bounded function. By a standard second moment calculation, we see that with probability at least ${1/2}$ , we have

$\displaystyle \|f\|_{U^k(G)}^{2^k} = {\bf E}_{n, h_1,\dots,h_k \in G} f(n) \prod_{\omega \in \{0,1\}^k \backslash \{0\}} {\mathcal C}^{|\omega|} \frac{1}{p} 1_A f(n + \omega \cdot h)$

$\displaystyle + O((\frac{1}{N^{k+1} p^{2^k-1}})^{1/2}).$

Thus, by the triangle inequality, if we choose ${p := C \eta^{-2^{k+1}/(2^k-1)} / N^{\frac{k+1}{2^k-1}}}$ for some sufficiently large ${C = C_k > 0}$ , then for any ${1}$ -bounded ${f}$ with ${\|f\|_{U^k(G)} \geq \eta/2}$ , one has with probability at least ${1/2}$ that

$\displaystyle |{\bf E}_{n, h_1,\dots,h_k \i2^n G} f(n) \prod_{\omega \in \{0,1\}^k \backslash \{0\}} {\mathcal C}^{|\omega|} \frac{1}{p} 1_A f(n + \omega \cdot h)|$

$\displaystyle \geq \eta^{2^k}/2^{2^k+1}.$

We can write the left-hand side as ${|\langle f, F \rangle|}$ where ${F}$ is the randomly sampled dual function

$\displaystyle F(n) := {\bf E}_{n, h_1,\dots,h_k \in G} f(n) \prod_{\omega \in \{0,1\}^k \backslash \{0\}} {\mathcal C}^{|\omega|+1} \frac{1}{p} 1_A f(n + \omega \cdot h).$

Unfortunately, ${F}$ is not ${1}$ -bounded in general, but we have

$\displaystyle \|F\|_{L^2(G)}^2 \leq {\bf E}_{n, h_1,\dots,h_k ,h'_1,\dots,h'_k \in G}$

$\displaystyle \prod_{\omega \in \{0,1\}^k \backslash \{0\}} \frac{1}{p} 1_A(n + \omega \cdot h) \frac{1}{p} 1_A(n + \omega \cdot h')$

and the right-hand side can be shown to be ${1+o(1)}$ on the average, so we can condition on the event that the right-hand side is ${O(1)}$ without significant loss in falure probability.

If we then let ${\tilde f_A}$ be ${1_A f}$ rounded to the nearest Gaussian integer multiple of ${\eta^{2^k}/2^{2^{10k}}}$ in the unit disk, one has from the triangle inequality that

$\displaystyle |\langle f, \tilde F \rangle| \geq \eta^{2^k}/2^{2^k+2}$

where ${\tilde F}$ is the discretised randomly sampled dual function

$\displaystyle \tilde F(n) := {\bf E}_{n, h_1,\dots,h_k \in G} f(n) \prod_{\omega \in \{0,1\}^k \backslash \{0\}} {\mathcal C}^{|\omega|+1} \frac{1}{p} \tilde f_A(n + \omega \cdot h).$

For any given ${A}$ , there are at most ${2np}$ places ${n}$ where ${\tilde f_A(n)}$ can be non-zero, and in those places there are ${O_k( \eta^{-2^{k}})}$ possible values for ${\tilde f_A(n)}$ . Thus, if we let ${{\mathcal F}_A}$ be the collection of all possible ${\tilde f_A}$ associated to a given ${A}$ , the cardinality of this set is ${O( \exp( \eta^{-O_k(1)} N^{1 - \frac{k+1}{2^k-1}} ) )}$ , and for any ${f}$ with ${\|f\|_{U^k(G)} \geq \eta/2}$ , we have

$\displaystyle \sup_{\tilde F \in {\mathcal F}_A} |\langle f, \tilde F \rangle| \geq \eta^{2^k}/2^{k+2}$

with probability at least ${1/2}$ .

Now we remove the failure probability by independent resampling. By rounding to the nearest Gaussian integer multiple of ${c_k \eta^{2^k}}$ in the unit disk for a sufficiently small ${c_k>0}$ , one can find a family ${{\mathcal G}}$ of cardinality ${O( \eta^{-O_k(N)})}$ consisting of ${1}$ -bounded functions ${\tilde f}$ of ${U^k(G)}$ norm at least ${\eta/2}$ such that for every ${1}$ -bounded ${f}$ with ${\|f\|_{U^k(G)} \geq \eta}$ there exists ${\tilde f \in {\mathcal G}}$ such that

$\displaystyle \|f-\tilde f\|_{L^\infty(G)} \leq \eta^{2^k}/2^{k+3}.$

Now, let ${A_1,\dots,A_M}$ be independent samples of ${A}$ for some ${M}$ to be chosen later. By the preceding discussion, we see that with probability at least ${1 - 2^{-M}}$ , we have

$\displaystyle \sup_{\tilde F \in \bigcup_{j=1}^M {\mathcal F}_{A_j}} |\langle \tilde f, \tilde F \rangle| \geq \eta^{2^k}/2^{k+2}$

for any given ${\tilde f \in {\mathcal G}}$ , so by the union bound, if we choose ${M = \lfloor C N \log \frac{1}{\eta} \rfloor}$ for a large enough ${C = C_k}$ , we can find ${A_1,\dots,A_M}$ such that

$\displaystyle \sup_{\tilde F \in \bigcup_{j=1}^M {\mathcal F}_{A_j}} |\langle \tilde f, \tilde F \rangle| \geq \eta^{2^k}/2^{k+2}$

for all ${\tilde f \in {\mathcal G}}$ , and hence y the triangle inequality

$\displaystyle \sup_{\tilde F \in \bigcup_{j=1}^M {\mathcal F}_{A_j}} |\langle f, \tilde F \rangle| \geq \eta^{2^k}/2^{k+3}.$

Taking ${{\mathcal F}}$ to be the union of the ${{\mathcal F}_{A_j}}$ (applying some truncation and rescaling to these ${L^2}$ -bounded functions to make them ${L^\infty}$ -bounded, and then ${1}$ -bounded), we obtain the claim. $\Box$

One way to obtain lower bounds on the inverse theorem entropy is to produce a collection of almost orthogonal functions with large norm. More precisely:

Proposition 4 Let ${\| \|}$ be a seminorm, let ${0 < \varepsilon \leq \eta < 1}$ , and suppose that one has a collection ${f_1,\dots,f_M}$ of ${1}$ -bounded functions such that for all ${i=1,\dots,M}$ , ${\|f_i\| \geq \eta}$ one has ${|\langle f_i, f_j \rangle| \leq \varepsilon^2/2}$ for all but at most ${L}$ choices of ${j \in \{1,\dots,M\}}$ for all distinct ${i,j \in \{1,\dots,M\}}$ . Then the ${(\eta, \varepsilon)}$ -entropy of ${\| \|}$ is at least ${\varepsilon^2 M / 2L}$ .

Proof: Suppose we have an ${(\eta,\varepsilon)}$ -inverse theorem with some family ${{\mathcal F}}$ . Then for each ${i=1,\dots,M}$ there is ${F_i \in {\mathcal F}}$ such that ${|\langle f_i, F_i \rangle| \geq \varepsilon}$ . By the pigeonhole principle, there is thus ${F \in {\mathcal F}}$ such that ${|\langle f_i, F \rangle| \geq \varepsilon}$ for all ${i}$ in a subset ${I}$ of ${\{1,\dots,M\}}$ of cardinality at least ${M/|{\mathcal F}|}$ :

$\displaystyle |I| \geq M / |{\mathcal F}|.$

We can sum this to obtain

$\displaystyle |\sum_{i \in I} c_i \langle f_i, F \rangle| \geq |I| \varepsilon$

for some complex numbers ${c_i}$ of unit magnitude. By Cauchy-Schwarz, this implies

$\displaystyle \| \sum_{i \in I} c_i f_i \|_{L^2(G)}^2 \geq |I|^2 \varepsilon^2$

and hence by the triangle inequality

$\displaystyle \sum_{i,j \in I} |\langle f_i, f_j \rangle| \geq |I|^2 \varepsilon^2.$

On the other hand, by hypothesis we can bound the left-hand side by ${|I| (L + \varepsilon^2 |I|/2)}$ . Rearranging, we conclude that

$\displaystyle |I| \leq 2 L / \varepsilon^2$

and hence

$\displaystyle |{\mathcal F}| \geq \varepsilon^2 M / 2L$

giving the claim. $\Box$

Thus for instance:

For the ${U^2(G)}$ norm, one can take ${f_1,\dots,f_M}$ to be the family of linear exponential phases ${n \mapsto e(\xi \cdot n)}$ with ${M = N}$ and ${L=1}$ , and obtain a linear lower bound of ${\varepsilon^2 N/2}$ for the ${(\eta,\varepsilon)}$ -entropy, thus matching the upper bound of ${N}$ up to constants when ${\varepsilon}$ is fixed.
For the ${U^k({\bf Z}/N{\bf Z})}$ norm, a similar calculation using polynomial phases of degree ${k-1}$ , combined with the Weyl sum estimates, gives a lower bound of ${\gg_{k,\varepsilon} N^{k-1}}$ for the ${(\eta,\varepsilon)}$ -entropy for any fixed ${\eta,\varepsilon}$ ; by considering nilsequences as well, together with nilsequence equidistribution theory, one can replace the exponent ${k-1}$ here by some quantity that goes to infinity as ${\eta \rightarrow 0}$ , though I have not attempted to calculate the exact rate.
For the ${U^k({\bf F}_p^n)}$ norm, another similar calculation using polynomial phases of degree ${k-1}$ should give a lower bound of ${\gg_{p,k,\eta,\varepsilon} \exp( c_{p,k,\eta,\varepsilon} n^{k-1} )}$ for the ${(\eta,\varepsilon)}$ -entropy, though I have not fully performed the calculation.

We close with one final example. Suppose ${G}$ is a product ${G = A \times B}$ of two sets ${A,B}$ of cardinality ${\asymp \sqrt{N}}$ , and we consider the Gowers box norm

$\displaystyle \|f\|_{\Box^2(G)}^4 := {\bf E}_{a,a' \in A; b,b' \in B} f(a,b) \overline{f}(a,b') \overline{f}(a',b) f(a,b).$

One possible choice of class ${{\mathcal F}}$ here are the indicators ${1_{U \times V}}$ of “rectangles” ${U \times V}$ with ${U \subset A}$ , ${V \subset B}$ (cf. this previous blog post on cut norms). By standard calculations, one can use this class to show that the ${(\eta, \eta^4/10)}$ -entropy of ${\| \|_{\Box^2(G)}}$ is ${O( \exp( O(\sqrt{N}) )}$ , and a variant of the proof of the second part of Proposition 2 shows that this is the correct order of growth in ${N}$ . In contrast, a modification of Proposition 3 only gives an upper bound of the form ${O( \exp( O( N^{2/3} ) ) )}$ (the bottleneck is ensuring that the randomly sampled dual functions stay bounded in ${L^2}$ ), which shows that while this cheap bound is not optimal, it can still broadly give the correct “type” of bound (specifically, intermediate growth between polynomial and exponential).

The Gowers uniformity norm of order 1+

25 July, 2021 in expository, math.CA, math.CO, math.DS | Tags: arithmetic progressions, Gowers uniformity norms, polynomial recurrence, randomness | by Terence Tao | 25 comments

In the modern theory of higher order Fourier analysis, a key role are played by the Gowers uniformity norms ${\| \|_{U^k}}$ for ${k=1,2,\dots}$ . For finitely supported functions ${f: {\bf Z} \rightarrow {\bf C}}$ , one can define the (non-normalised) Gowers norm ${\|f\|_{\tilde U^k({\bf Z})}}$ by the formula

$\displaystyle \|f\|_{\tilde U^k({\bf Z})}^{2^k} := \sum_{n,h_1,\dots,h_k \in {\bf Z}} \prod_{\omega_1,\dots,\omega_k \in \{0,1\}} {\mathcal C}^{\omega_1+\dots+\omega_k} f(x+\omega_1 h_1 + \dots + \omega_k h_k)$

where ${{\mathcal C}}$ denotes complex conjugation, and then on any discrete interval ${[N] = \{1,\dots,N\}}$ and any function ${f: [N] \rightarrow {\bf C}}$ we can then define the (normalised) Gowers norm

$\displaystyle \|f\|_{U^k([N])} := \| f 1_{[N]} \|_{\tilde U^k({\bf Z})} / \|1_{[N]} \|_{\tilde U^k({\bf Z})}$

where ${f 1_{[N]}: {\bf Z} \rightarrow {\bf C}}$ is the extension of ${f}$ by zero to all of ${{\bf Z}}$ . Thus for instance

$\displaystyle \|f\|_{U^1([N])} = |\mathop{\bf E}_{n \in [N]} f(n)|$

(which technically makes ${\| \|_{U^1([N])}}$ a seminorm rather than a norm), and one can calculate

$\displaystyle \|f\|_{U^2([N])} \asymp (N \int_0^1 |\mathop{\bf E}_{n \in [N]} f(n) e(-\alpha n)|^4\ d\alpha)^{1/4} \ \ \ \ \ (1)$

where ${e(\theta) := e^{2\pi i \alpha}}$ , and we use the averaging notation ${\mathop{\bf E}_{n \in A} f(n) = \frac{1}{|A|} \sum_{n \in A} f(n)}$ .

The significance of the Gowers norms is that they control other multilinear forms that show up in additive combinatorics. Given any polynomials ${P_1,\dots,P_m: {\bf Z}^d \rightarrow {\bf Z}}$ and functions ${f_1,\dots,f_m: [N] \rightarrow {\bf C}}$ , we define the multilinear form

$\displaystyle \Lambda^{P_1,\dots,P_m}(f_1,\dots,f_m) := \sum_{n \in {\bf Z}^d} \prod_{j=1}^m f_j 1_{[N]}(P_j(n)) / \sum_{n \in {\bf Z}^d} \prod_{j=1}^m 1_{[N]}(P_j(n))$

(assuming that the denominator is finite and non-zero). Thus for instance

$\displaystyle \Lambda^{\mathrm{n}}(f) = \mathop{\bf E}_{n \in [N]} f(n)$

$\displaystyle \Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}}(f,g) = (\mathop{\bf E}_{n \in [N]} f(n)) (\mathop{\bf E}_{n \in [N]} g(n))$

$\displaystyle \Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}, \mathrm{n}+2\mathrm{r}}(f,g,h) \asymp \mathop{\bf E}_{n \in [N]} \mathop{\bf E}_{r \in [-N,N]} f(n) g(n+r) h(n+2r)$

$\displaystyle \Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}, \mathrm{n}+\mathrm{r}^2}(f,g,h) \asymp \mathop{\bf E}_{n \in [N]} \mathop{\bf E}_{r \in [-N^{1/2},N^{1/2}]} f(n) g(n+r) h(n+r^2)$

where we view ${\mathrm{n}, \mathrm{r}}$ as formal (indeterminate) variables, and ${f,g,h: [N] \rightarrow {\bf C}}$ are understood to be extended by zero to all of ${{\bf Z}}$ . These forms are used to count patterns in various sets; for instance, the quantity ${\Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}, \mathrm{n}+2\mathrm{r}}(1_A,1_A,1_A)}$ is closely related to the number of length three arithmetic progressions contained in ${A}$ . Let us informally say that a form ${\Lambda^{P_1,\dots,P_m}(f_1,\dots,f_m)}$ is controlled by the ${U^k[N]}$ norm if the form is small whenever ${f_1,\dots,f_m: [N] \rightarrow {\bf C}}$ are ${1}$ -bounded functions with at least one of the ${f_j}$ small in ${U^k[N]}$ norm. This definition was made more precise by Gowers and Wolf, who then defined the true complexity of a form ${\Lambda^{P_1,\dots,P_m}}$ to be the least ${s}$ such that ${\Lambda^{P_1,\dots,P_m}}$ is controlled by the ${U^{s+1}[N]}$ norm. For instance,

${\Lambda^{\mathrm{n}}}$ and ${\Lambda^{\mathrm{n}, \mathrm{n} + \mathrm{r}}}$ have true complexity ${0}$ ;
${\Lambda^{\mathrm{n}, \mathrm{n} + \mathrm{r}, \mathrm{n} + \mathrm{2r}}}$ has true complexity ${1}$ ;
${\Lambda^{\mathrm{n}, \mathrm{n} + \mathrm{r}, \mathrm{n} + \mathrm{2r}, \mathrm{n} + \mathrm{3r}}}$ has true complexity ${2}$ ;
The form ${\Lambda^{\mathrm{n}, \mathrm{n}+2}}$ (which among other things could be used to count twin primes) has infinite true complexity (which is quite unfortunate for applications).

Roughly speaking, patterns of complexity ${1}$ or less are amenable to being studied by classical Fourier analytic tools (the Hardy-Littlewood circle method); patterns of higher complexity can be handled (in principle, at least) by the methods of higher order Fourier analysis; and patterns of infinite complexity are out of range of both methods and are generally quite difficult to study. See these recent slides of myself (or this video of the lecture) for some further discussion.

Gowers and Wolf formulated a conjecture on what this complexity should be, at least for linear polynomials ${P_1,\dots,P_m}$ ; Ben Green and I thought we had resolved this conjecture back in 2010, though it turned out there was a subtle gap in our arguments and we were only able to resolve the conjecture in a partial range of cases. However, the full conjecture was recently resolved by Daniel Altman.

The ${U^1}$ (semi-)norm is so weak that it barely controls any averages at all. For instance the average

$\displaystyle \Lambda^{2\mathrm{n}}(f) = \mathop{\bf E}_{n \in [N], \hbox{ even}} f(n)$

is not controlled by the ${U^1[N]}$ semi-norm: it is perfectly possible for a ${1}$ -bounded function ${f: [N] \rightarrow {\bf C}}$ to even have vanishing ${U^1([N])}$ norm but have large value of ${\Lambda^{2\mathrm{n}}(f)}$ (consider for instance the parity function ${f(n) := (-1)^n}$ ).

Because of this, I propose inserting an additional norm in the Gowers uniformity norm hierarchy between the ${U^1}$ and ${U^2}$ norms, which I will call the ${U^{1^+}}$ (or “profinite ${U^1}$ “) norm:

$\displaystyle \| f\|_{U^{1^+}[N]} := \frac{1}{N} \sup_P |\sum_{n \in P} f(n)| = \sup_P | \mathop{\bf E}_{n \in [N]} f 1_P(n)|$

where ${P}$ ranges over all arithmetic progressions in ${[N]}$ . This can easily be seen to be a norm on functions ${f: [N] \rightarrow {\bf C}}$ that controls the ${U^1[N]}$ norm. It is also basically controlled by the ${U^2[N]}$ norm for ${1}$ -bounded functions ${f}$ ; indeed, if ${P}$ is an arithmetic progression in ${[N]}$ of some spacing ${q \geq 1}$ , then we can write ${P}$ as the intersection of an interval ${I}$ with a residue class modulo ${q}$ , and from Fourier expansion we have

$\displaystyle \mathop{\bf E}_{n \in [N]} f 1_P(n) \ll \sup_\alpha |\mathop{\bf E}_{n \in [N]} f 1_I(n) e(\alpha n)|.$

If we let ${\psi}$ be a standard bump function supported on ${[-1,1]}$ with total mass and ${\delta>0}$ is a parameter then

$\displaystyle \mathop{\bf E}_{n \in [N]} f 1_I(n) e(\alpha n)$

$\displaystyle \ll |\mathop{\bf E}_{n \in [-N,2N]; h, k \in [-N,N]} \frac{1}{\delta} \psi(\frac{h}{\delta N})$

$\displaystyle 1_I(n+h+k) f(n+h+k) e(\alpha(n+h+k))|$

$\displaystyle \ll |\mathop{\bf E}_{n \in [-N,2N]; h, k \in [-N,N]} \frac{1}{\delta} \psi(\frac{h}{\delta N}) 1_I(n+k) f(n+h+k) e(\alpha(n+h+k))|$

$\displaystyle + \delta$

(extending ${f}$ by zero outside of ${[N]}$ ), as can be seen by using the triangle inequality and the estimate

$\displaystyle \mathop{\bf E}_{h \in [-N,N]} \frac{1}{\delta} \psi(\frac{h}{\delta N}) 1_I(n+h+k) - \mathop{\bf E}_{h \in [-N,N]} \frac{1}{\delta} \psi(\frac{h}{\delta N}) 1_I(n+k)$

$\displaystyle \ll (1 + \mathrm{dist}(n+k, I) / \delta N)^{-2}.$

After some Fourier expansion of ${\delta \psi(\frac{h}{\delta N})}$ we now have

$\displaystyle \mathop{\bf E}_{n \in [N]} f 1_P(n) \ll \frac{1}{\delta} \sup_{\alpha,\beta} |\mathop{\bf E}_{n \in [N]; h, k \in [-N,N]} e(\beta h + \alpha (n+h+k))$

$\displaystyle 1_P(n+k) f(n+h+k)| + \delta.$

Writing ${\alpha h + \alpha(n+h+k)}$ as a linear combination of ${n, n+h, n+k}$ and using the Gowers–Cauchy–Schwarz inequality, we conclude

$\displaystyle \mathop{\bf E}_{n \in [N]} f 1_P(n) \ll \frac{1}{\delta} \|f\|_{U^2([N])} + \delta$

hence on optimising in ${\delta}$ we have

$\displaystyle \| f\|_{U^{1^+}[N]} \ll \|f\|_{U^2[N]}^{1/2}.$

Forms which are controlled by the ${U^{1^+}}$ norm (but not ${U^1}$ ) would then have their true complexity adjusted to ${0^+}$ with this insertion.

The ${U^{1^+}}$ norm recently appeared implicitly in work of Peluse and Prendiville, who showed that the form ${\Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}, \mathrm{n}+\mathrm{r}^2}(f,g,h)}$ had true complexity ${0^+}$ in this notation (with polynomially strong bounds). [Actually, strictly speaking this control was only shown for the third function ${h}$ ; for the first two functions ${f,g}$ one needs to localize the ${U^{1^+}}$ norm to intervals of length ${\sim \sqrt{N}}$ . But I will ignore this technical point to keep the exposition simple.] The weaker claim that ${\Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}^2}(f,g)}$ has true complexity ${0^+}$ is substantially easier to prove (one can apply the circle method together with Gauss sum estimates).

The well known inverse theorem for the ${U^2}$ norm tells us that if a ${1}$ -bounded function ${f}$ has ${U^2[N]}$ norm at least ${\eta}$ for some ${0 < \eta < 1}$ , then there is a Fourier phase ${n \mapsto e(\alpha n)}$ such that

$\displaystyle |\mathop{\bf E}_{n \in [N]} f(n) e(-\alpha n)| \gg \eta^2;$

this follows easily from (1) and Plancherel’s theorem. Conversely, from the Gowers–Cauchy–Schwarz inequality one has

$\displaystyle |\mathop{\bf E}_{n \in [N]} f(n) e(-\alpha n)| \ll \|f\|_{U^2[N]}.$

For ${U^1[N]}$ one has a trivial inverse theorem; by definition, the ${U^1[N]}$ norm of ${f}$ is at least ${\eta}$ if and only if

$\displaystyle |\mathop{\bf E}_{n \in [N]} f(n)| \geq \eta.$

Thus the frequency ${\alpha}$ appearing in the ${U^2}$ inverse theorem can be taken to be zero when working instead with the ${U^1}$ norm.

For ${U^{1^+}}$ one has the intermediate situation in which the frequency ${\alpha}$ is not taken to be zero, but is instead major arc. Indeed, suppose that ${f}$ is ${1}$ -bounded with ${\|f\|_{U^{1^+}[N]} \geq \eta}$ , thus

$\displaystyle |\mathop{\bf E}_{n \in [N]} 1_P(n) f(n)| \geq \eta$

for some progression ${P}$ . This forces the spacing ${q}$ of this progression to be ${\ll 1/\eta}$ . We write the above inequality as

$\displaystyle |\mathop{\bf E}_{n \in [N]} 1_{n=b\ (q)} 1_I(n) f(n)| \geq \eta$

for some residue class ${b\ (q)}$ and some interval ${I}$ . By Fourier expansion and the triangle inequality we then have

$\displaystyle |\mathop{\bf E}_{n \in [N]} e(-an/q) 1_I(n) f(n)| \geq \eta$

for some integer ${a}$ . Convolving ${1_I}$ by ${\psi_\delta: n \mapsto \frac{1}{N\delta} \psi(\frac{n}{N\delta})}$ for ${\delta}$ a small multiple of ${\eta}$ and ${\psi}$ a Schwartz function of unit mass with Fourier transform supported on ${[-1,1]}$ , we have

$\displaystyle |\mathop{\bf E}_{n \in [N]} e(-an/q) (1_I * \psi_\delta)(n) f(n)| \gg \eta.$

The Fourier transform ${\xi \mapsto \sum_n 1_I * \psi_\delta(n) e(- \xi n)}$ of ${1_I * \psi_\delta}$ is bounded by ${O(N)}$ and supported on ${[-\frac{1}{\delta N},\frac{1}{\delta N}]}$ , thus by Fourier expansion and the triangle inequality we have

$\displaystyle |\mathop{\bf E}_{n \in [N]} e(-an/q) e(-\xi n) f(n)| \gg \eta^2$

for some ${\xi \in [-\frac{1}{\delta N},\frac{1}{\delta N}]}$ , so in particular ${\xi = O(\frac{1}{\eta N})}$ . Thus we have

$\displaystyle |\mathop{\bf E}_{n \in [N]} f(n) e(-\alpha n)| \gg \eta^2 \ \ \ \ \ (2)$

for some ${\alpha}$ of the major arc form ${\alpha = \frac{a}{q} + O(1/\eta)}$ with ${1 \leq q \leq 1/\eta}$ . Conversely, for ${\alpha}$ of this form, some routine summation by parts gives the bound

$\displaystyle |\mathop{\bf E}_{n \in [N]} f(n) e(-\alpha n)| \ll \frac{q}{\eta} \|f\|_{U^{1^+}[N]} \ll \frac{1}{\eta^2} \|f\|_{U^{1^+}[N]}$

so if (2) holds for a ${1}$ -bounded ${f}$ then one must have ${\|f\|_{U^{1^+}[N]} \gg \eta^4}$ .

Here is a diagram showing some of the control relationships between various Gowers norms, multilinear forms, and duals of classes ${{\mathcal F}}$ of functions (where each class of functions ${{\mathcal F}}$ induces a dual norm ${\| f \|_{{\mathcal F}^*} := \sup_{\phi \in {\mathcal F}} \mathop{\bf E}_{n \in[N]} f(n) \overline{\phi(n)}}$ :

Here I have included the three classes of functions that one can choose from for the ${U^3}$ inverse theorem, namely degree two nilsequences, bracket quadratic phases, and local quadratic phases, as well as the more narrow class of globally quadratic phases.

The Gowers norms have counterparts for measure-preserving systems ${(X,T,\mu)}$ , known as Host-Kra seminorms. The ${U^1(X)}$ norm can be defined for ${f \in L^\infty(X)}$ as

$\displaystyle \|f\|_{U^1(X)} := \lim_{N \rightarrow \infty} \int_X |\mathop{\bf E}_{n \in [N]} T^n f|\ d\mu$

and the ${U^2}$ norm can be defined as

$\displaystyle \|f\|_{U^2(X)}^4 := \lim_{N \rightarrow \infty} \mathop{\bf E}_{n \in [N]} \| T^n f \overline{f} \|_{U^1(X)}^2.$

The ${U^1(X)}$ seminorm is orthogonal to the invariant factor ${Z^0(X)}$ (generated by the (almost everywhere) invariant measurable subsets of ${X}$ ) in the sense that a function ${f \in L^\infty(X)}$ has vanishing ${U^1(X)}$ seminorm if and only if it is orthogonal to all ${Z^0(X)}$ -measurable (bounded) functions. Similarly, the ${U^2(X)}$ norm is orthogonal to the Kronecker factor ${Z^1(X)}$ , generated by the eigenfunctions of ${X}$ (that is to say, those ${f}$ obeying an identity ${Tf = \lambda f}$ for some ${T}$ -invariant ${\lambda}$ ); for ergodic systems, it is the largest factor isomorphic to rotation on a compact abelian group. In analogy to the Gowers ${U^{1^+}[N]}$ norm, one can then define the Host-Kra ${U^{1^+}(X)}$ seminorm by

$\displaystyle \|f\|_{U^{1^+}(X)} := \sup_{q \geq 1} \frac{1}{q} \lim_{N \rightarrow \infty} \int_X |\mathop{\bf E}_{n \in [N]} T^{qn} f|\ d\mu;$

it is orthogonal to the profinite factor ${Z^{0^+}(X)}$ , generated by the periodic sets of ${X}$ (or equivalently, by those eigenfunctions whose eigenvalue is a root of unity); for ergodic systems, it is the largest factor isomorphic to rotation on a profinite abelian group.

Quantitative bounds for Gowers uniformity of the Mobius and von Mangoldt functions

5 July, 2021 in math.NT, paper | Tags: Gowers uniformity norms, Joni Teravainen, Mobius function, von Mangoldt function | by Terence Tao | 24 comments

Joni Teräväinen and myself have just uploaded to the arXiv our preprint “Quantitative bounds for Gowers uniformity of the Möbius and von Mangoldt functions“. This paper makes quantitative the Gowers uniformity estimates on the Möbius function ${\mu}$ and the von Mangoldt function ${\Lambda}$ .

To discuss the results we first discuss the situation of the Möbius function, which is technically simpler in some (though not all) ways. We assume familiarity with Gowers norms and standard notations around these norms, such as the averaging notation ${\mathop{\bf E}_{n \in [N]}}$ and the exponential notation ${e(\theta) = e^{2\pi i \theta}}$ . The prime number theorem in qualitative form asserts that

$\displaystyle \mathop{\bf E}_{n \in [N]} \mu(n) = o(1)$

as ${N \rightarrow \infty}$ . With Vinogradov-Korobov error term, the prime number theorem is strengthened to

$\displaystyle \mathop{\bf E}_{n \in [N]} \mu(n) \ll \exp( - c \log^{3/5} N (\log \log N)^{-1/5} );$

we refer to such decay bounds (With ${\exp(-c\log^c N)}$ type factors) as pseudopolynomial decay. Equivalently, we obtain pseudopolynomial decay of Gowers ${U^1}$ seminorm of ${\mu}$ :

$\displaystyle \| \mu \|_{U^1([N])} \ll \exp( - c \log^{3/5} N (\log \log N)^{-1/5} ).$

As is well known, the Riemann hypothesis would be equivalent to an upgrade of this estimate to polynomial decay of the form

$\displaystyle \| \mu \|_{U^1([N])} \ll_\varepsilon N^{-1/2+\varepsilon}$

for any ${\varepsilon>0}$ .

Once one restricts to arithmetic progressions, the situation gets worse: the Siegel-Walfisz theorem gives the bound

$\displaystyle \| \mu 1_{a \hbox{ mod } q}\|_{U^1([N])} \ll_A \log^{-A} N \ \ \ \ \ (1)$

for any residue class ${a \hbox{ mod } q}$ and any ${A>0}$ , but with the catch that the implied constant is ineffective in ${A}$ . This ineffectivity cannot be removed without further progress on the notorious Siegel zero problem.

In 1937, Davenport was able to show the discorrelation estimate

$\displaystyle \mathop{\bf E}_{n \in [N]} \mu(n) e(-\alpha n) \ll_A \log^{-A} N$

for any ${A>0}$ uniformly in ${\alpha \in {\bf R}}$ , which leads (by standard Fourier arguments) to the Fourier uniformity estimate

$\displaystyle \| \mu \|_{U^2([N])} \ll_A \log^{-A} N.$

Again, the implied constant is ineffective. If one insists on effective constants, the best bound currently available is

$\displaystyle \| \mu \|_{U^2([N])} \ll \log^{-c} N \ \ \ \ \ (2)$

for some small effective constant ${c>0}$ .

For the situation with the ${U^3}$ norm the previously known results were much weaker. Ben Green and I showed that

$\displaystyle \mathop{\bf E}_{n \in [N]} \mu(n) \overline{F}(g(n) \Gamma) \ll_{A,F,G/\Gamma} \log^{-A} N \ \ \ \ \ (3)$

uniformly for any ${A>0}$ , any degree two (filtered) nilmanifold ${G/\Gamma}$ , any polynomial sequence ${g: {\bf Z} \rightarrow G}$ , and any Lipschitz function ${F}$ ; again, the implied constants are ineffective. On the other hand, in a separate paper of Ben Green and myself, we established the following inverse theorem: if for instance we knew that

$\displaystyle \| \mu \|_{U^3([N])} \geq \delta$

for some ${0 < \delta < 1/2}$ , then there exists a degree two nilmanifold ${G/\Gamma}$ of dimension ${O( \delta^{-O(1)} )}$ , complexity ${O( \delta^{-O(1)} )}$ , a polynomial sequence ${g: {\bf Z} \rightarrow G}$ , and Lipschitz function ${F}$ of Lipschitz constant ${O(\delta^{-O(1)})}$ such that

$\displaystyle \mathop{\bf E}_{n \in [N]} \mu(n) \overline{F}(g(n) \Gamma) \gg \exp(-\delta^{-O(1)}).$

Putting the two assertions together and comparing all the dependencies on parameters, one can establish the qualitative decay bound

$\displaystyle \| \mu \|_{U^3([N])} = o(1).$

However the decay rate ${o(1)}$ produced by this argument is completely ineffective: obtaining a bound on when this ${o(1)}$ quantity dips below a given threshold ${\delta}$ depends on the implied constant in (3) for some ${G/\Gamma}$ whose dimension depends on ${\delta}$ , and the dependence on ${\delta}$ obtained in this fashion is ineffective in the face of a Siegel zero.

For higher norms ${U^k, k \geq 3}$ , the situation is even worse, because the quantitative inverse theory for these norms is poorer, and indeed it was only with the recent work of Manners that any such bound is available at all (at least for ${k>4}$ ). Basically, Manners establishes if

$\displaystyle \| \mu \|_{U^k([N])} \geq \delta$

then there exists a degree ${k-1}$ nilmanifold ${G/\Gamma}$ of dimension ${O( \delta^{-O(1)} )}$ , complexity ${O( \exp\exp(\delta^{-O(1)}) )}$ , a polynomial sequence ${g: {\bf Z} \rightarrow G}$ , and Lipschitz function ${F}$ of Lipschitz constant ${O(\exp\exp(\delta^{-O(1)}))}$ such that

$\displaystyle \mathop{\bf E}_{n \in [N]} \mu(n) \overline{F}(g(n) \Gamma) \gg \exp\exp(-\delta^{-O(1)}).$

(We allow all implied constants to depend on ${k}$ .) Meanwhile, the bound (3) was extended to arbitrary nilmanifolds by Ben and myself. Again, the two results when concatenated give the qualitative decay

$\displaystyle \| \mu \|_{U^k([N])} = o(1)$

but the decay rate is completely ineffective.

Our first result gives an effective decay bound:

Theorem 1 For any ${k \geq 2}$ , we have ${\| \mu \|_{U^k([N])} \ll (\log\log N)^{-c_k}}$ for some ${c_k>0}$ . The implied constants are effective.

This is off by a logarithm from the best effective bound (2) in the ${k=2}$ case. In the ${k=3}$ case there is some hope to remove this logarithm based on the improved quantitative inverse theory currently available in this case, but there is a technical obstruction to doing so which we will discuss later in this post. For ${k>3}$ the above bound is the best one could hope to achieve purely using the quantitative inverse theory of Manners.

We have analogues of all the above results for the von Mangoldt function ${\Lambda}$ . Here a complication arises that ${\Lambda}$ does not have mean close to zero, and one has to subtract off some suitable approximant ${\Lambda^\sharp}$ to ${\Lambda}$ before one would expect good Gowers norms bounds. For the prime number theorem one can just use the approximant ${1}$ , giving

$\displaystyle \| \Lambda - 1 \|_{U^1([N])} \ll \exp( - c \log^{3/5} N (\log \log N)^{-1/5} )$

but even for the prime number theorem in arithmetic progressions one needs a more accurate approximant. In our paper it is convenient to use the “Cramér approximant”

$\displaystyle \Lambda_{\hbox{Cram\'er}}(n) := \frac{W}{\phi(W)} 1_{(n,W)=1}$

where

$\displaystyle W := \prod_{p<Q} p$

and ${Q}$ is the quasipolynomial quantity

$\displaystyle Q = \exp(\log^{1/10} N). \ \ \ \ \ (4)$

Then one can show from the Siegel-Walfisz theorem and standard bilinear sum methods that

$\displaystyle \mathop{\bf E}_{n \in [N]} (\Lambda - \Lambda_{\hbox{Cram\'er}}(n)) e(-\alpha n) \ll_A \log^{-A} N$

and

$\displaystyle \| \Lambda - \Lambda_{\hbox{Cram\'er}}\|_{U^2([N])} \ll_A \log^{-A} N$

for all ${A>0}$ and ${\alpha \in {\bf R}}$ (with an ineffective dependence on ${A}$ ), again regaining effectivity if ${A}$ is replaced by a sufficiently small constant ${c>0}$ . All the previously stated discorrelation and Gowers uniformity results for ${\mu}$ then have analogues for ${\Lambda}$ , and our main result is similarly analogous:

Theorem 2 For any ${k \geq 2}$ , we have ${\| \Lambda - \Lambda_{\hbox{Cram\'er}} \|_{U^k([N])} \ll (\log\log N)^{-c_k}}$ for some ${c_k>0}$ . The implied constants are effective.

By standard methods, this result also gives quantitative asymptotics for counting solutions to various systems of linear equations in primes, with error terms that gain a factor of ${O((\log\log N)^{-c})}$ with respect to the main term.

We now discuss the methods of proof, focusing first on the case of the Möbius function. Suppose first that there is no “Siegel zero”, by which we mean a quadratic character ${\chi}$ of some conductor ${q \leq Q}$ with a zero ${L(\beta,\chi)}$ with ${1 - \beta \leq \frac{c}{\log Q}}$ for some small absolute constant ${c>0}$ . In this case the Siegel-Walfisz bound (1) improves to a quasipolynomial bound

$\displaystyle \| \mu 1_{a \hbox{ mod } q}\|_{U^1([N])} \ll \exp(-\log^c N). \ \ \ \ \ (5)$

To establish Theorem 1 in this case, it suffices by Manners’ inverse theorem to establish the polylogarithmic bound

$\displaystyle \mathop{\bf E}_{n \in [N]} \mu(n) \overline{F}(g(n) \Gamma) \ll \exp(-\log^c N) \ \ \ \ \ (6)$

for all degree ${k-1}$ nilmanifolds ${G/\Gamma}$ of dimension ${O((\log\log N)^c)}$ and complexity ${O( \exp(\log^c N))}$ , all polynomial sequences ${g}$ , and all Lipschitz functions ${F}$ of norm ${O( \exp(\log^c N))}$ . If the nilmanifold ${G/\Gamma}$ had bounded dimension, then one could repeat the arguments of Ben and myself more or less verbatim to establish this claim from (5), which relied on the quantitative equidistribution theory on nilmanifolds developed in a separate paper of Ben and myself. Unfortunately, in the latter paper the dependence of the quantitative bounds on the dimension ${d}$ was not explicitly given. In an appendix to the current paper, we go through that paper to account for this dependence, showing that all exponents depend at most doubly exponentially in the dimension ${d}$ , which is barely sufficient to handle the dimension of ${O((\log\log N)^c)}$ that arises here.

Now suppose we have a Siegel zero ${L(\beta,\chi)}$ . In this case the bound (5) will not hold in general, and hence also (6) will not hold either. Here, the usual way out (while still maintaining effective estimates) is to approximate ${\mu}$ not by ${0}$ , but rather by a more complicated approximant ${\mu_{\hbox{Siegel}}}$ that takes the Siegel zero into account, and in particular is such that one has the (effective) pseudopolynomial bound

$\displaystyle \| (\mu - \mu_{\hbox{Siegel}}) 1_{a \hbox{ mod } q}\|_{U^1([N])} \ll \exp(-\log^c N) \ \ \ \ \ (7)$

for all residue classes ${a \hbox{ mod } q}$ . The Siegel approximant to ${\mu}$ is actually a little bit complicated, and to our knowledge the first appearance of this sort of approximant only appears as late as this 2010 paper of Germán and Katai. Our version of this approximant is defined as the multiplicative function such that

$\displaystyle \mu_{\hbox{Siegel}}(p^j) = \mu(p^j)$

when ${p < Q}$ , and

$\displaystyle \mu_{\hbox{Siegel}}(n) = \alpha n^{\beta-1} \chi(n)$

when ${n}$ is coprime to all primes ${p<Q}$ , and ${\alpha}$ is a normalising constant given by the formula

$\displaystyle \alpha := \frac{1}{L'(\beta,\chi)} \prod_{p<Q} (1-\frac{1}{p})^{-1} (1 - \frac{\chi(p)}{p^\beta})^{-1}$

(this constant ends up being of size ${O(1)}$ and plays only a minor role in the analysis). This is a rather complicated formula, but it seems to be virtually the only choice of approximant that allows for bounds such as (7) to hold. (This is the one aspect of the problem where the von Mangoldt theory is simpler than the Möbius theory, as in the former one only needs to work with very rough numbers for which one does not need to make any special accommodations for the behavior at small primes when introducing the Siegel correction term.) With this starting point it is then possible to repeat the analysis of my previous papers with Ben and obtain the pseudopolynomial discorrelation bound

$\displaystyle \mathop{\bf E}_{n \in [N]} (\mu - \mu_{\hbox{Siegel}})(n) \overline{F}(g(n) \Gamma) \ll \exp(-\log^c N)$

for ${F(g(n)\Gamma)}$ as before, which when combined with Manners’ inverse theorem gives the doubly logarithmic bound

$\displaystyle \| \mu - \mu_{\hbox{Siegel}} \|_{U^k([N])} \ll (\log\log N)^{-c_k}.$

Meanwhile, a direct sieve-theoretic computation ends up giving the singly logarithmic bound

$\displaystyle \| \mu_{\hbox{Siegel}} \|_{U^k([N])} \ll \log^{-c_k} N$

(indeed, there is a good chance that one could improve the bounds even further, though it is not helpful for this current argument to do so). Theorem 1 then follows from the triangle inequality for the Gowers norm. It is interesting that the Siegel approximant ${\mu_{\hbox{Siegel}}}$ seems to play a rather essential component in the proof, even if it is absent in the final statement. We note that this approximant seems to be a useful tool to explore the “illusory world” of the Siegel zero further; see for instance the recent paper of Chinis for some work in this direction.

For the analogous problem with the von Mangoldt function (assuming a Siegel zero for sake of discussion), the approximant ${\Lambda_{\hbox{Siegel}}}$ is simpler; we ended up using

$\displaystyle \Lambda_{\hbox{Siegel}}(n) = \Lambda_{\hbox{Cram\'er}}(n) (1 - n^{\beta-1} \chi(n))$

which allows one to state the standard prime number theorem in arithmetic progressions with classical error term and Siegel zero term compactly as

$\displaystyle \| (\Lambda - \Lambda_{\hbox{Siegel}}) 1_{a \hbox{ mod } q}\|_{U^1([N])} \ll \exp(-\log^c N).$

Routine modifications of previous arguments also give

$\displaystyle \mathop{\bf E}_{n \in [N]} (\Lambda - \Lambda_{\hbox{Siegel}})(n) \overline{F}(g(n) \Gamma) \ll \exp(-\log^c N) \ \ \ \ \ (8)$

and

$\displaystyle \| \Lambda_{\hbox{Siegel}} \|_{U^k([N])} \ll \log^{-c_k} N.$

The one tricky new step is getting from the discorrelation estimate (8) to the Gowers uniformity estimate

$\displaystyle \| \Lambda - \Lambda_{\hbox{Siegel}} \|_{U^k([N])} \ll (\log\log N)^{-c_k}.$

One cannot directly apply Manners’ inverse theorem here because ${\Lambda}$ and ${\Lambda_{\hbox{Siegel}}}$ are unbounded. There is a standard tool for getting around this issue, now known as the dense model theorem, which is the standard engine powering the transference principle from theorems about bounded functions to theorems about certain types of unbounded functions. However the quantitative versions of the dense model theorem in the literature are expensive and would basically weaken the doubly logarithmic gain here to a triply logarithmic one. Instead, we bypass the dense model theorem and directly transfer the inverse theorem for bounded functions to an inverse theorem for unbounded functions by using the densification approach to transference introduced by Conlon, Fox, and Zhao. This technique turns out to be quantitatively quite efficient (the dependencies of the main parameters in the transference are polynomial in nature), and also has the technical advantage of avoiding the somewhat tricky “correlation condition” present in early transference results which are also not beneficial for quantitative bounds.

In principle, the above results can be improved for ${k=3}$ due to the stronger quantitative inverse theorems in the ${U^3}$ setting. However, there is a bottleneck that prevents us from achieving this, namely that the equidistribution theory of two-step nilmanifolds has exponents which are exponential in the dimension rather than polynomial in the dimension, and as a consequence we were unable to improve upon the doubly logarithmic results. Specifically, if one is given a sequence of bracket quadratics such as ${\lfloor \alpha_1 n \rfloor \beta_1 n, \dots, \lfloor \alpha_d n \rfloor \beta_d n}$ that fails to be ${\delta}$ -equidistributed, one would need to establish a nontrivial linear relationship modulo 1 between the ${\alpha_1,\beta_1,\dots,\alpha_d,\beta_d}$ (up to errors of ${O(1/N)}$ ), where the coefficients are of size ${O(\delta^{-d^{O(1)}})}$ ; current methods only give coefficient bounds of the form ${O(\delta^{-\exp(d^{O(1)})})}$ . An old result of Schmidt demonstrates proof of concept that these sorts of polynomial dependencies on exponents is possible in principle, but actually implementing Schmidt’s methods here seems to be a quite non-trivial task. There is also another possible route to removing a logarithm, which is to strengthen the inverse ${U^3}$ theorem to make the dimension of the nilmanifold logarithmic in the uniformity parameter ${\delta}$ rather than polynomial. Again, the Freiman-Bilu theorem (see for instance this paper of Ben and myself) demonstrates proof of concept that such an improvement in dimension is possible, but some work would be needed to implement it.

A correction to “An arithmetic regularity lemma, an associated counting lemma, and applications”

26 November, 2020 in math.CO, update | Tags: arithmetic regularity lemma, Ben Green, counting lemma, Daniel Altman, Gowers uniformity norms | by Terence Tao | 5 comments

Ben Green and I have updated our paper “An arithmetic regularity lemma, an associated counting lemma, and applications” to account for a somewhat serious issue with the paper that was pointed out to us recently by Daniel Altman. This paper contains two core theorems:

An “arithmetic regularity lemma” that, roughly speaking, decomposes an arbitrary bounded sequence ${f(n)}$ on an interval ${\{1,\dots,N\}}$ as an “irrational nilsequence” ${F(g(n) \Gamma)}$ of controlled complexity, plus some “negligible” errors (where one uses the Gowers uniformity norm as the main norm to control the neglibility of the error); and
An “arithmetic counting lemma” that gives an asymptotic formula for counting various averages ${{\mathbb E}_{{\bf n} \in {\bf Z}^d \cap P} f(\psi_1({\bf n})) \dots f(\psi_t({\bf n}))}$ for various affine-linear forms ${\psi_1,\dots,\psi_t}$ when the functions ${f}$ are given by irrational nilsequences.

The combination of the two theorems is then used to address various questions in additive combinatorics.

There are no direct issues with the arithmetic regularity lemma. However, it turns out that the arithmetic counting lemma is only true if one imposes an additional property (which we call the “flag property”) on the affine-linear forms ${\psi_1,\dots,\psi_t}$ . Without this property, there does not appear to be a clean asymptotic formula for these averages if the only hypothesis one places on the underlying nilsequences is irrationality. Thus when trying to understand the asymptotics of averages involving linear forms that do not obey the flag property, the paradigm of understanding these averages via a combination of the regularity lemma and a counting lemma seems to require some significant revision (in particular, one would probably have to replace the existing regularity lemma with some variant, despite the fact that the lemma is still technically true in this setting). Fortunately, for most applications studied to date (including the important subclass of translation-invariant affine forms), the flag property holds; however our claim in the paper to have resolved a conjecture of Gowers and Wolf on the true complexity of systems of affine forms must now be narrowed, as our methods only verify this conjecture under the assumption of the flag property.

In a bit more detail: the asymptotic formula for our counting lemma involved some finite-dimensional vector spaces ${\Psi^{[i]}}$ for various natural numbers ${i}$ , defined as the linear span of the vectors ${(\psi^i_1({\bf n}), \dots, \psi^i_t({\bf n}))}$ as ${{\bf n}}$ ranges over the parameter space ${{\bf Z}^d}$ . Roughly speaking, these spaces encode some constraints one would expect to see amongst the forms ${\psi^i_1({\bf n}), \dots, \psi^i_t({\bf n})}$ . For instance, in the case of length four arithmetic progressions when ${d=2}$ , ${{\bf n} = (n,r)}$ , and

$\displaystyle \psi_i({\bf n}) = n + (i-1)r$

for ${i=1,2,3,4}$ , then ${\Psi^{[1]}}$ is spanned by the vectors ${(1,1,1,1)}$ and ${(1,2,3,4)}$ and can thus be described as the two-dimensional linear space

$\displaystyle \Psi^{[1]} = \{ (a,b,c,d): a-2b+c = b-2c+d = 0\} \ \ \ \ \ (1)$

while ${\Psi^{[2]}}$ is spanned by the vectors ${(1,1,1,1)}$ , ${(1,2,3,4)}$ , ${(1^2,2^2,3^2,4^2)}$ and can be described as the hyperplane

$\displaystyle \Psi^{[2]} = \{ (a,b,c,d): a-3b+3c-d = 0 \}. \ \ \ \ \ (2)$

As a special case of the counting lemma, we can check that if ${f}$ takes the form ${f(n) = F( \alpha n, \beta n^2 + \gamma n)}$ for some irrational ${\alpha,\beta \in {\bf R}/{\bf Z}}$ , some arbitrary ${\gamma \in {\bf R}/{\bf Z}}$ , and some smooth ${F: {\bf R}/{\bf Z} \times {\bf R}/{\bf Z} \rightarrow {\bf C}}$ , then the limiting value of the average

$\displaystyle {\bf E}_{n, r \in [N]} f(n) f(n+r) f(n+2r) f(n+3r)$

as ${N \rightarrow \infty}$ is equal to

$\displaystyle \int_{a_1,b_1,c_1,d_1 \in {\bf R}/{\bf Z}: a_1-2b_1+c_1=b_1-2c_1+d_1=0} \int_{a_2,b_2,c_2,d_2 \in {\bf R}/{\bf Z}: a_2-3b_2+3c_2-d_2=0}$

$\displaystyle F(a_1,a_2) F(b_1,b_2) F(c_1,c_2) F(d_1,d_2)$

which reflects the constraints

$\displaystyle \alpha n - 2 \alpha(n+r) + \alpha(n+2r) = \alpha(n+r) - 2\alpha(n+2r)+\alpha(n+3r)=0$

and

$\displaystyle (\beta n^2 + \gamma n) - 3 (\beta(n+r)^2+\gamma(n+r))$

$\displaystyle + 3 (\beta(n+2r)^2 +\gamma(n+2r)) - (\beta(n+3r)^2+\gamma(n+3r))=0.$

These constraints follow from the descriptions (1), (2), using the containment ${\Psi^{[1]} \subset \Psi^{[2]}}$ to dispense with the lower order term ${\gamma n}$ (which then plays no further role in the analysis).

The arguments in our paper turn out to be perfectly correct under the assumption of the “flag property” that ${\Psi^{[i]} \subset \Psi^{[i+1]}}$ for all ${i}$ . The problem is that the flag property turns out to not always hold. A counterexample, provided by Daniel Altman, involves the four linear forms

$\displaystyle \psi_1(n,r) = r; \psi_2(n,r) = 2n+2r; \psi_3(n,r) = n+3r; \psi_4(n,r) = n.$

Here it turns out that

$\displaystyle \Psi^{[1]} = \{ (a,b,c,d): d-c=3a; b-2a=2d\}$

and

$\displaystyle \Psi^{[2]} = \{ (a,b,c,d): 24a+3b-4c-8d=0 \}$

and ${\Psi^{[1]}}$ is no longer contained in ${\Psi^{[2]}}$ . The analogue of the asymptotic formula given previously for ${f(n) = F( \alpha n, \beta n^2 + \gamma n)}$ is then valid when ${\gamma}$ vanishes, but not when ${\gamma}$ is non-zero, because the identity

$\displaystyle 24 (\beta \psi_1(n,r)^2 + \gamma \psi_1(n,r)) + 3 (\beta \psi_2(n,r)^2 + \gamma \psi_2(n,r))$

$\displaystyle - 4 (\beta \psi_3(n,r)^2 + \gamma \psi_3(n,r)) - 8 (\beta \psi_4(n,r)^2 + \gamma \psi_4(n,r)) = 0$

holds in the former case but not the latter. Thus the output of any purported arithmetic regularity lemma in this case is now sensitive to the lower order terms of the nilsequence and cannot be described in a uniform fashion for all “irrational” sequences. There should still be some sort of formula for the asymptotics from the general equidistribution theory of nilsequences, but it could be considerably more complicated than what is presented in this paper.

Fortunately, the flag property does hold in several key cases, most notably the translation invariant case when ${\Psi^{[1]}}$ contains ${(1,\dots,1)}$ , as well as “complexity one” cases. Nevertheless non-flag property systems of affine forms do exist, thus limiting the range of applicability of the techniques in this paper. In particular, the conjecture of Gowers and Wolf (Theorem 1.13 in the paper) is now open again in the non-flag property case.

Higher uniformity of bounded multiplicative functions in short intervals on average

30 July, 2020 in math.NT, paper | Tags: Gowers uniformity norms, Joni Teravainen, Kaisa Matomaki, Liouville function, Maksym Radziwill, nilsequences, sign patterns, Tamar Ziegler | by Terence Tao | 7 comments

Kaisa Matomäki, Maksym Radziwill, Joni Teräväinen, Tamar Ziegler and I have uploaded to the arXiv our paper Higher uniformity of bounded multiplicative functions in short intervals on average. This paper (which originated from a working group at an AIM workshop on Sarnak’s conjecture) focuses on the local Fourier uniformity conjecture for bounded multiplicative functions such as the Liouville function ${\lambda}$ . One form of this conjecture is the assertion that

$\displaystyle \int_0^X \| \lambda \|_{U^k([x,x+H])}\ dx = o(X) \ \ \ \ \ (1)$

as ${X \rightarrow \infty}$ for any fixed ${k \geq 0}$ and any ${H = H(X) \leq X}$ that goes to infinity as ${X \rightarrow \infty}$ , where ${U^k([x,x+H])}$ is the (normalized) Gowers uniformity norm. Among other things this conjecture implies (logarithmically averaged version of) the Chowla and Sarnak conjectures for the Liouville function (or the Möbius function), see this previous blog post.

The conjecture gets more difficult as ${k}$ increases, and also becomes more difficult the more slowly ${H}$ grows with ${X}$ . The ${k=0}$ conjecture is equivalent to the assertion

$\displaystyle \int_0^X |\sum_{x \leq n \leq x+H} \lambda(n)| \ dx = o(HX)$

which was proven (for arbitrarily slowly growing ${H}$ ) in a landmark paper of Matomäki and Radziwill, discussed for instance in this blog post.

For ${k=1}$ , the conjecture is equivalent to the assertion

$\displaystyle \int_0^X \sup_\alpha |\sum_{x \leq n \leq x+H} \lambda(n) e(-\alpha n)| \ dx = o(HX). \ \ \ \ \ (2)$

This remains open for sufficiently slowly growing ${H}$ (and it would be a major breakthrough in particular if one could obtain this bound for ${H}$ as small as ${\log^\varepsilon X}$ for any fixed ${\varepsilon>0}$ , particularly if applicable to more general bounded multiplicative functions than ${\lambda}$ , as this would have new implications for a generalization of the Chowla conjecture known as the Elliott conjecture). Recently, Kaisa, Maks and myself were able to establish this conjecture in the range ${H \geq X^\varepsilon}$ (in fact we have since worked out in the current paper that we can get ${H}$ as small as ${\exp(\log^{5/8+\varepsilon} X)}$ ). In our current paper we establish Fourier uniformity conjecture for higher ${k}$ for the same range of ${H}$ . This in particular implies local orthogonality to polynomial phases,

$\displaystyle \int_0^X \sup_{P \in \mathrm{Poly}_{\leq k-1}({\bf R} \rightarrow {\bf R})} |\sum_{x \leq n \leq x+H} \lambda(n) e(-P(n))| \ dx = o(HX) \ \ \ \ \ (3)$

where ${\mathrm{Poly}_{\leq k-1}({\bf R} \rightarrow {\bf R})}$ denotes the polynomials of degree at most ${k-1}$ , but the full conjecture is a bit stronger than this, establishing the more general statement

$\displaystyle \int_0^X \sup_{g \in \mathrm{Poly}({\bf R} \rightarrow G)} |\sum_{x \leq n \leq x+H} \lambda(n) \overline{F}(g(n) \Gamma)| \ dx = o(HX) \ \ \ \ \ (4)$

for any degree ${k}$ filtered nilmanifold ${G/\Gamma}$ and Lipschitz function ${F: G/\Gamma \rightarrow {\bf C}}$ , where ${g}$ now ranges over polynomial maps from ${{\bf R}}$ to ${G}$ . The method of proof follows the same general strategy as in the previous paper with Kaisa and Maks. (The equivalence of (4) and (1) follows from the inverse conjecture for the Gowers norms, proven in this paper.) We quickly sketch first the proof of (3), using very informal language to avoid many technicalities regarding the precise quantitative form of various estimates. If the estimate (3) fails, then we have the correlation estimate

$\displaystyle |\sum_{x \leq n \leq x+H} \lambda(n) e(-P_x(n))| \gg H$

for many ${x \sim X}$ and some polynomial ${P_x}$ depending on ${x}$ . The difficulty here is to understand how ${P_x}$ can depend on ${x}$ . We write the above correlation estimate more suggestively as

$\displaystyle \lambda(n) \sim_{[x,x+H]} e(P_x(n)).$

Because of the multiplicativity ${\lambda(np) = -\lambda(p)}$ at small primes ${p}$ , one expects to have a relation of the form

$\displaystyle e(P_{x'}(p'n)) \sim_{[x/p,x/p+H/p]} e(P_x(pn)) \ \ \ \ \ (5)$

for many ${x,x'}$ for which ${x/p \approx x'/p'}$ for some small primes ${p,p'}$ . (This can be formalised using an inequality of Elliott related to the Turan-Kubilius theorem.) This gives a relationship between ${P_x}$ and ${P_{x'}}$ for “edges” ${x,x'}$ in a rather sparse “graph” connecting the elements of say ${[X/2,X]}$ . Using some graph theory one can locate some non-trivial “cycles” in this graph that eventually lead (in conjunction to a certain technical but important “Chinese remainder theorem” step to modify the ${P_x}$ to eliminate a rather serious “aliasing” issue that was already discussed in this previous post) to obtain functional equations of the form

$\displaystyle P_x(a_x \cdot) \approx P_x(b_x \cdot)$

for some large and close (but not identical) integers ${a_x,b_x}$ , where ${\approx}$ should be viewed as a first approximation (ignoring a certain “profinite” or “major arc” term for simplicity) as “differing by a slowly varying polynomial” and the polynomials ${P_x}$ should now be viewed as taking values on the reals rather than the integers. This functional equation can be solved to obtain a relation of the form

$\displaystyle P_x(t) \approx T_x \log t$

for some real number ${T_x}$ of polynomial size, and with further analysis of the relation (5) one can make ${T_x}$ basically independent of ${x}$ . This simplifies (3) to something like

$\displaystyle \int_0^X \sup_{P \in \mathrm{Poly}_{\leq k-1}({\bf R} \rightarrow {\bf R})} |\sum_{x \leq n \leq x+H} \lambda(n) n^{-iT}| \ dx = o(HX)$

and this is now of a form that can be treated by the theorem of Matomäki and Radziwill (because ${n \mapsto \lambda(n) n^{-iT}}$ is a bounded multiplicative function). (Actually because of the profinite term mentioned previously, one also has to insert a Dirichlet character of bounded conductor into this latter conclusion, but we will ignore this technicality.)

Now we apply the same strategy to (4). For abelian ${G}$ the claim follows easily from (3), so we focus on the non-abelian case. One now has a polynomial sequence ${g_x \in \mathrm{Poly}({\bf R} \rightarrow G)}$ attached to many ${x \sim X}$ , and after a somewhat complicated adaptation of the above arguments one again ends up with an approximate functional equation

$\displaystyle g_x(a_x \cdot) \Gamma \approx g_x(b_x \cdot) \Gamma \ \ \ \ \ (6)$

where the relation ${\approx}$ is rather technical and will not be detailed here. A new difficulty arises in that there are some unwanted solutions to this equation, such as

$\displaystyle g_x(t) = \gamma^{\frac{\log(a_x t)}{\log(a_x/b_x)}}$

for some ${\gamma \in \Gamma}$ , which do not necessarily lead to multiplicative characters like ${n^{-iT}}$ as in the polynomial case, but instead to some unfriendly looking “generalized multiplicative characters” (think of ${e(\lfloor \alpha \log n \rfloor \beta \log n)}$ as a rough caricature). To avoid this problem, we rework the graph theory portion of the argument to produce not just one functional equation of the form (6)for each ${x}$ , but many, leading to dilation invariances

$\displaystyle g_x((1+\theta) t) \Gamma \approx g_x(t) \Gamma$

for a “dense” set of ${\theta}$ . From a certain amount of Lie algebra theory (ultimately arising from an understanding of the behaviour of the exponential map on nilpotent matrices, and exploiting the hypothesis that ${G}$ is non-abelian) one can conclude that (after some initial preparations to avoid degenerate cases) ${g_x(t)}$ must behave like ${\gamma_x^{\log t}}$ for some central element ${\gamma_x}$ of ${G}$ . This eventually brings one back to the multiplicative characters ${n^{-iT}}$ that arose in the polynomial case, and the arguments now proceed as before.

We give two applications of this higher order Fourier uniformity. One regards the growth of the number

$\displaystyle s(k) := |\{ (\lambda(n+1),\dots,\lambda(n+k)): n \in {\bf N} \}|$

of length ${k}$ sign patterns in the Liouville function. The Chowla conjecture implies that ${s(k) = 2^k}$ , but even the weaker conjecture of Sarnak that ${s(k) \gg (1+\varepsilon)^k}$ for some ${\varepsilon>0}$ remains open. Until recently, the best asymptotic lower bound on ${s(k)}$ was ${s(k) \gg k^2}$ , due to McNamara; with our result, we can now show ${s(k) \gg_A k^A}$ for any ${A}$ (in fact we can get ${s(k) \gg_\varepsilon \exp(\log^{8/5-\varepsilon} k)}$ for any ${\varepsilon>0}$ ). The idea is to repeat the now-standard argument to exploit multiplicativity at small primes to deduce Chowla-type conjectures from Fourier uniformity conjectures, noting that the Chowla conjecture would give all the sign patterns one could hope for. The usual argument here uses the “entropy decrement argument” to eliminate a certain error term (involving the large but mean zero factor ${p 1_{p|n}-1}$ ). However the observation is that if there are extremely few sign patterns of length ${k}$ , then the entropy decrement argument is unnecessary (there isn’t much entropy to begin with), and a more low-tech moment method argument (similar to the derivation of Chowla’s conjecture from Sarnak’s conjecture, as discussed for instance in this post) gives enough of Chowla’s conjecture to produce plenty of length ${k}$ sign patterns. If there are not extremely few sign patterns of length ${k}$ then we are done anyway. One quirk of this argument is that the sign patterns it produces may only appear exactly once; in contrast with preceding arguments, we were not able to produce a large number of sign patterns that each occur infinitely often.

The second application is to obtain cancellation for various polynomial averages involving the Liouville function ${\lambda}$ or von Mangoldt function ${\Lambda}$ , such as

$\displaystyle {\bf E}_{n \leq X} {\bf E}_{m \leq X^{1/d}} \lambda(n+P_1(m)) \lambda(n+P_2(m)) \dots \lambda(n+P_k(m))$

$\displaystyle {\bf E}_{n \leq X} {\bf E}_{m \leq X^{1/d}} \lambda(n+P_1(m)) \Lambda(n+P_2(m)) \dots \Lambda(n+P_k(m))$

where ${P_1,\dots,P_k}$ are polynomials of degree at most ${d}$ , no two of which differ by a constant (the latter is essential to avoid having to establish the Chowla or Hardy-Littlewood conjectures, which of course remain open). Results of this type were previously obtained by Tamar Ziegler and myself in the “true complexity zero” case when the polynomials ${P}$ had distinct degrees, in which one could use the ${k=0}$ theory of Matomäki and Radziwill; now that higher ${k}$ is available at the scale ${H=X^{1/d}}$ we can now remove this restriction.

Cut norms and degree lowering

8 March, 2020 in expository, math.CO | Tags: cut norm, Gowers uniformity norms, Roth's theorem | by Terence Tao | 15 comments

In the modern theory of additive combinatorics, a large role is played by the Gowers uniformity norms ${\|f\|_{U^k(G)}}$ , where ${k \geq 1}$ , ${G = (G,+)}$ is a finite abelian group, and ${f: G \rightarrow {\bf C}}$ is a function (one can also consider these norms in finite approximate groups such as ${[N] = \{1,\dots,N\}}$ instead of finite groups, but we will focus on the group case here for simplicity). These norms can be defined by the formula

$\displaystyle \|f\|_{U^k(G)} := (\mathop{\bf E}_{x,h_1,\dots,h_k \in G} \Delta_{h_1} \dots \Delta_{h_k} f(x))^{1/2^k}$

where we use the averaging notation

$\displaystyle \mathop{\bf E}_{x \in A} f(x) := \frac{1}{|A|} \sum_{x \in A} f(x)$

for any non-empty finite set ${A}$ (with ${|A|}$ denoting the cardinality of ${A}$ ), and ${\Delta_h}$ is the multiplicative discrete derivative operator

$\displaystyle \Delta_h f(x) := f(x+h) \overline{f(x)}.$

One reason why these norms play an important role is that they control various multilinear averages. We give two sample examples here:

Proposition 1 Let ${G = {\bf Z}/N{\bf Z}}$ .

(i) If ${a_1,\dots,a_k}$ are distinct elements of ${G}$ for some ${k \geq 2}$ , and ${f_1,\dots,f_k: G \rightarrow {\bf C}}$ are ${1}$ -bounded functions (thus ${|f_j(x)| \leq 1}$ for all ${j=1,\dots,k}$ and ${x \in G}$ ), then
$\displaystyle \mathop{\bf E}_{x, h \in G} f_1(x+a_1 h) \dots f_k(x+a_k h) \leq \|f_i\|_{U^{k-1}(G)} \ \ \ \ \ (1)$

for any ${i=1,\dots,k}$ .

(ii) If ${f_1,f_2,f_3: G \rightarrow {\bf C}}$ are ${1}$ -bounded, then one has
$\displaystyle \mathop{\bf E}_{x, h \in G} f_1(x) f_2(x+h) f_3(x+h^2) \ll \|f_3\|_{U^4(G)} + N^{-1/4}.$

We establish these claims a little later in this post.

In some more recent literature (e.g., this paper of Conlon, Fox, and Zhao), the role of Gowers norms have been replaced by (generalisations) of the cut norm, a concept originating from graph theory. In this blog post, it will be convenient to define these cut norms in the language of probability theory (using boldface to denote random variables).

Definition 2 (Cut norm) Let ${{\bf X}_1,\dots,{\bf X}_k, {\bf Y}_1,\dots,{\bf Y}_l}$ be independent random variables with ${k,l \geq 0}$ ; to avoid minor technicalities we assume that these random variables are discrete and take values in a finite set. Given a random variable ${{\bf F} = F( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )}$ of these independent random variables, we define the cut norm

$\displaystyle \| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )} := \sup | \mathop{\bf E} {\bf F} {\bf B}_1 \dots {\bf B}_k |$

where the supremum ranges over all choices ${{\bf B}_1,\dots,{\bf B}_k}$ of random variables ${{\bf B}_i = B_i( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )}$ that are ${1}$ -bounded (thus ${|{\bf B}_i| \leq 1}$ surely), and such that ${{\bf B}_i}$ does not depend on ${{\bf X}_i}$ .

If ${l=0}$ , we abbreviate ${\| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )}}$ as ${\| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k )}}$ .

Strictly speaking, the cut norm is only a cut semi-norm when ${k=0,1}$ , but we will abuse notation by referring to it as a norm nevertheless.

Example 3 If ${G = (V_1,V_2,E)}$ is a bipartite graph, and ${\mathbf{v_1}}$ , ${\mathbf{v_2}}$ are independent random variables chosen uniformly from ${V_1,V_2}$ respectively, then

$\displaystyle \| 1_E(\mathbf{v_1},\mathbf{v_2}) \|_{\mathrm{CUT}(\mathbf{v_1}, \mathbf{v_2})}$

$\displaystyle = \sup_{\|f\|_\infty, \|g\|_\infty \leq 1} |\mathop{\bf E}_{v_1 \in V_1, v_2 \in V_2} 1_E(v_1,v_2) f(v_1) g(v_2)|$

where the supremum ranges over all ${1}$ -bounded functions ${f: V_1 \rightarrow [-1,1]}$ , ${g: V_2 \rightarrow [-1,1]}$ . The right hand side is essentially the cut norm of the graph ${G}$ , as defined for instance by Frieze and Kannan.

The cut norm is basically an expectation when ${k=0,1}$ :

Example 4 If ${k=0}$ , we see from definition that

$\displaystyle \| {\bf F} \|_{\mathrm{CUT}( ; {\bf Y}_1,\dots,{\bf Y}_l )} =| \mathop{\bf E} {\bf F} |.$

If ${k=1}$ , one easily checks that

$\displaystyle \| {\bf F} \|_{\mathrm{CUT}( {\bf X}; {\bf Y}_1,\dots,{\bf Y}_l )} = \mathop{\bf E} | \mathop{\bf E}_{\bf X} {\bf F} |,$

where ${\mathop{\bf E}_{\bf X} {\bf F} = \mathop{\bf E}( {\bf F} | {\bf Y}_1,\dots,{\bf Y}_l )}$ is the conditional expectation of ${{\bf F}}$ to the ${\sigma}$ -algebra generated by all the variables other than ${{\bf X}}$ , i.e., the ${\sigma}$ -algebra generated by ${{\bf Y}_1,\dots,{\bf Y}_l}$ . In particular, if ${{\bf X}, {\bf Y}_1,\dots,{\bf Y}_l}$ are independent random variables drawn uniformly from ${X,Y_1,\dots,Y_l}$ respectively, then

$\displaystyle \| F( {\bf X}; {\bf Y}_1,\dots, {\bf Y}_l) \|_{\mathrm{CUT}( {\bf X}; {\bf Y}_1,\dots,{\bf Y}_l )}$

$\displaystyle = \mathop{\bf E}_{y_1 \in Y_1,\dots, y_l \in Y_l} |\mathop{\bf E}_{x \in X} F(x; y_1,\dots,y_l)|.$

Here are some basic properties of the cut norm:

Lemma 5 (Basic properties of cut norm) Let ${{\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l}$ be independent discrete random variables, and ${{\bf F} = F({\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l)}$ a function of these variables.

(i) (Permutation invariance) The cut norm ${\| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )}}$ is invariant with respect to permutations of the ${{\bf X}_1,\dots,{\bf X}_k}$ , or permutations of the ${{\bf Y}_1,\dots,{\bf Y}_l}$ .

(ii) (Conditioning) One has
$\displaystyle \| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )} = \mathop{\bf E} \| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k )}$

where on the right-hand side we view, for each realisation ${y_1,\dots,y_l}$ of ${{\bf Y}_1,\dots,{\bf Y}_l}$ , ${{\bf F}}$ as a function ${F( {\bf X}_1,\dots,{\bf X}_k; y_1,\dots,y_l)}$ of the random variables ${{\bf X}_1,\dots, {\bf X}_k}$ alone, thus the right-hand side may be expanded as

$\displaystyle \sum_{y_1,\dots,y_l} \| F( {\bf X}_1,\dots,{\bf X}_k; y_1,\dots,y_l) \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k )}$

$\displaystyle \times \mathop{\bf P}( Y_1=y_1,\dots,Y_l=y_l).$

(iii) (Monotonicity) If ${k \geq 1}$ , we have
$\displaystyle \| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )} \geq \| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_{k-1}; {\bf X}_k, {\bf Y}_1,\dots,{\bf Y}_l )}.$

(iv) (Multiplicative invariances) If ${{\bf B} = B({\bf X}_1,\dots,{\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l)}$ is a ${1}$ -bounded function that does not depend on one of the ${{\bf X}_i}$ , then
$\displaystyle \| {\bf B} {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )} \leq \| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )}.$

In particular, if we additionally assume ${|{\bf B}|=1}$ , then

$\displaystyle \| {\bf B} {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )} = \| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )}.$

(v) (Cauchy-Schwarz) If ${k \geq 1}$ , one has
$\displaystyle \| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )} \leq \| \Box_{{\bf X}_1, {\bf X}'_1} {\bf F} \|_{\mathrm{CUT}( {\bf X}_2, \dots, {\bf X}_k; {\bf X}_1, {\bf X}'_1, {\bf Y}_1,\dots,{\bf Y}_l )}^{1/2}$

where ${{\bf X}'_1}$ is a copy of ${{\bf X}_1}$ that is independent of ${{\bf X}_1,\dots,{\bf X}_k,{\bf Y}_1,\dots,{\bf Y}_l}$ and ${\Box_{{\bf X}_1, {\bf X}'_1} {\bf F}}$ is the random variable

$\displaystyle \Box_{{\bf X}_1, {\bf X}'_1} {\bf F} := F( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )$

$\displaystyle \times \overline{F}( {\bf X}'_1, {\bf X}_2, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l ).$

(vi) (Averaging) If ${k \geq 1}$ and ${{\bf F} = \mathop{\bf E}_{\bf Z} {\bf F}_{\bf Z}}$ , where ${{\bf Z}}$ is another random variable independent of ${{\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l}$ , and ${{\bf F}_{\bf Z} = F_{\bf Z}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )}$ is a random variable depending on both ${{\bf Z}}$ and ${{\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l}$ , then
$\displaystyle \| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )} \leq \| {\bf F}_{\bf Z} \|_{\mathrm{CUT}( ({\bf X}_1, {\bf Z}), {\bf X}_2, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )}$

Proof: The claims (i), (ii) are clear from expanding out all the definitions. The claim (iii) also easily follows from the definitions (the left-hand side involves a supremum over a more general class of multipliers ${{\bf B}_1,\dots,{\bf B}_{k}}$ , while the right-hand side omits the ${{\bf B}_k}$ multiplier), as does (iv) (the multiplier ${{\bf B}}$ can be absorbed into one of the multipliers in the definition of the cut norm). The claim (vi) follows by expanding out the definitions, and observing that all of the terms in the supremum appearing in the left-hand side also appear as terms in the supremum on the right-hand side. It remains to prove (v). By definition, the left-hand side is the supremum over all quantities of the form

$\displaystyle |{\bf E} {\bf F} {\bf B}_1 \dots {\bf B}_k|$

where the ${{\bf B}_i}$ are ${1}$ -bounded functions of ${{\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l}$ that do not depend on ${{\bf X}_i}$ . We average out in the ${{\bf X}_1}$ direction (that is, we condition out the variables ${{\bf X}_2, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l}$ ), and pull out the factor ${{\bf B}_1}$ (which does not depend on ${{\bf X}_1}$ ), to write this as

$\displaystyle |{\bf E} {\bf B}_1 {\bf E}_{{\bf X}_1}( {\bf F} {\bf B}_2 \dots {\bf B}_k )|,$

which by Cauchy-Schwarz is bounded by

$\displaystyle ( |{\bf E} |{\bf E}_{{\bf X}_1}( {\bf F} {\bf B}_2 \dots {\bf B}_k )|^2)^{1/2},$

which can be expanded using the copy ${{\bf X}_1}$ as

$\displaystyle |{\bf E} \Box_{{\bf X}_1,{\bf X}'_1} ({\bf F} {\bf B}_2 \dots {\bf B}_k) |^{1/2}.$

Expanding

$\displaystyle \Box_{{\bf X}_1,{\bf X}'_1} ({\bf F} {\bf B}_2 \dots {\bf B}_k) = (\Box_{{\bf X}_1,{\bf X}'_1} {\bf F}) (\Box_{{\bf X}_1,{\bf X}'_1} {\bf B}_2) \dots (\Box_{{\bf X}_1,{\bf X}'_1} {\bf B}_k)$

and noting that each ${\Box_{{\bf X}_1,{\bf X}'_1} {\bf B}_i}$ is ${1}$ -bounded and independent of ${{\bf X}_i}$ for ${i=2,\dots,k}$ , we obtain the claim. $\Box$

Now we can relate the cut norm to Gowers uniformity norms:

Lemma 6 Let ${G}$ be a finite abelian group, let ${{\bf x}, {\bf h}_1,\dots,{\bf h}_k}$ be independent random variables uniformly drawn from ${G}$ for some ${k \geq 0}$ , and let ${f: G \rightarrow {\bf C}}$ . Then

$\displaystyle \| f({\bf x} + {\bf h}_1 + \dots + {\bf h}_k) \|_{\mathrm{CUT}( {\bf h}_1,\dots,{\bf h}_k, {\bf x} )} \leq \|f\|_{U^{k+1}(G)} \ \ \ \ \ (2)$

and similarly (if ${k \geq 1}$ )

$\displaystyle \| f({\bf x} + {\bf h}_1 + \dots + {\bf h}_k) \|_{\mathrm{CUT}( {\bf h}_1,\dots,{\bf h}_k; {\bf x} )} \leq \|f\|_{U^{k}(G)} \ \ \ \ \ (3)$

If ${f}$ is additionally assumed to be ${1}$ -bounded, we have the converse inequalities

$\displaystyle \|f\|_{U^{k+1}(G)}^{2^{k+1}} \leq \| f({\bf x} + {\bf h}_1 + \dots + {\bf h}_k) \|_{\mathrm{CUT}( {\bf h}_1,\dots,{\bf h}_k, {\bf x} )} \ \ \ \ \ (4)$

and (if ${k \geq 1}$ )

$\displaystyle \|f\|_{U^{k}(G)}^{2^{k}} \leq \| f({\bf x} + {\bf h}_1 + \dots + {\bf h}_k) \|_{\mathrm{CUT}( {\bf h}_1,\dots,{\bf h}_k; {\bf x} )}. \ \ \ \ \ (5)$

Proof: Applying Lemma 5(v) ${k}$ times, we can bound

$\displaystyle \| f({\bf x} + {\bf h}_1 + \dots + {\bf h}_k) \|_{\mathrm{CUT}( {\bf h_1},\dots,{\bf h_k}, {\bf x} )}$

$\displaystyle \| \Box_{{\bf h}_k,{\bf h}'_k} \dots \Box_{{\bf h}_1,{\bf h}'_1} (f({\bf x} + {\bf h}_1 + \dots + {\bf h}_k)) \|_{\mathrm{CUT}( {\bf x}; {\bf h}_1, {\bf h}'_1, \dots, {\bf h}_k, {\bf h}'_k )}^{1/2^k} \ \ \ \ \ (6)$

where ${{\bf h}'_1,\dots,{\bf h}'_k}$ are independent copies of ${{\bf h}_1,\dots,{\bf h}_k}$ that are also independent of ${{\bf x}}$ . The expression inside the norm can also be written as

$\displaystyle \Delta_{{\bf h}_k - {\bf h}'_k} \dots \Delta_{{\bf h}_1 - {\bf h}'_1} f({\bf x} + {\bf h}'_1 + \dots + {\bf h}'_k)$

so by Example 4 one can write (6) as

$\displaystyle |\mathop{\bf E}_{h_1,\dots,h_k,h'_1,\dots,h'_k \in G} |\mathop{\bf E}_{x \in G} \Delta_{h_k - h'_k} \dots \Delta_{h_1 - h'_1} f(x+h'_1+\dots+h'_k)||^{1/2^k}$

which after some change of variables simplifies to

$\displaystyle |\mathop{\bf E}_{h_1,\dots,h_k \in G} |\mathop{\bf E}_{x \in G} \Delta_{h_k} \dots \Delta_{h_1} f(x)||^{1/2^k}$

which by Cauchy-Schwarz is bounded by

$\displaystyle |\mathop{\bf E}_{h_1,\dots,h_k \in G} |\mathop{\bf E}_{x \in G} \Delta_{h_k} \dots \Delta_{h_1} f(x)|^2|^{1/2^{k+1}}$

which one can rearrange as

$\displaystyle |\mathop{\bf E}_{h_1,\dots,h_k,h_{k+1},x \in G} \Delta_{h_{k+1}} \Delta_{h_k} \dots \Delta_{h_1} f(x)|^{1/2^{k+1}}$

giving (2). A similar argument bounds

$\displaystyle \| f({\bf x} + {\bf h}_1 + \dots + {\bf h}_k) \|_{\mathrm{CUT}( {\bf h_1},\dots,{\bf h_k}; {\bf x} )}$

$\displaystyle |\mathop{\bf E}_{h_1,\dots,h_k \in G} \mathop{\bf E}_{x \in G} \Delta_{h_k} \dots \Delta_{h_1} f(x)|^{1/2^k}$

which gives (3).

For (4), we can reverse the above steps and expand ${\|f\|_{U^{k+1}(G)}^{2^{k+1}}}$ as

$\displaystyle \mathop{\bf E}_{h_1,\dots,h_k \in G} |\mathop{\bf E}_{x \in G} \Delta_{h_k} \dots \Delta_{h_1} f(x)|^2$

which we can write as

$\displaystyle |\mathop{\bf E}_{h_1,\dots,h_k \in G} b(h_1,\dots,h_k) \mathop{\bf E}_{x \in G} \Delta_{h_k} \dots \Delta_{h_1} f(x)|$

for some ${1}$ -bounded function ${b}$ . This can in turn be expanded as

$\displaystyle |\mathop{\bf E}_{h_1,\dots,h_k,x \in G} f(x+h_1+\dots+h_k) b(h_1,\dots,h_k) \prod_{i=1}^k b_i(x,h_1,\dots,h_k)|$

for some ${1}$ -bounded functions ${b_i}$ that do not depend on ${h_i}$ . By Example 4, this can be written as

$\displaystyle \| f({\bf x} + {\bf h_1}+\dots+{\bf h}_k) b({\bf h}_1,\dots,{\bf h}_k) \prod_{i=1}^k b_i(x,h_1,\dots,h_k) \|_{\mathrm{CUT}(; {\bf h}_1,\dots,{\bf h}_k, {\bf x})}$

which by several applications of Theorem 5(iii) and then Theorem 5(iv) can be bounded by

$\displaystyle \| f({\bf x} + {\bf h_1}+\dots+{\bf h}_k) \|_{\mathrm{CUT}( {\bf h}_1,\dots,{\bf h}_k, {\bf x})},$

giving (4). A similar argument gives (5). $\Box$

Now we can prove Proposition 1. We begin with part (i). By permutation we may assume ${i=k}$ , then by translation we may assume ${a_k=0}$ . Replacing ${x}$ by ${x+h_1+\dots+h_{k-1}}$ and ${h}$ by ${h - a_1^{-1} h_1 - \dots - a_{k-1}^{-1} h_{k-1}}$ , we can write the left-hand side of (1) as

$\displaystyle \mathop{\bf E}_{x,h,h_1,\dots,h_{k-1} \in G} f_k(x+h_1+\dots+h_{k-1}) \prod_{i=1}^{k-1} b_i(x,h,h_1,\dots,h_{k-1})$

where

$\displaystyle b_i(x,h,h_1,\dots,h_{k-1})$

$\displaystyle := f_i( x + h_1+\dots+h_{k-1}+ a_i(h - a_1^{-1} h_1 - \dots - a_k^{-1} h_{k-1}))$

is a ${1}$ -bounded function that does not depend on ${h_i}$ . Taking ${{\bf x}, {\bf h}, {\bf h}_1,\dots,{\bf h}_k}$ to be independent random variables drawn uniformly from ${G}$ , the left-hand side of (1) can then be written as

$\displaystyle \mathop{\bf E} f_k({\bf x}+{\bf h}_1+\dots+{\bf h}_{k-1}) \prod_{i=1}^{k-1} b_i({\bf x},{\bf h},{\bf h}_1,\dots,{\bf h}_{k-1})$

which by Example 4 is bounded in magnitude by

$\displaystyle \| f_k({\bf x}+{\bf h}_1+\dots+{\bf h}_{k-1}) \prod_{i=1}^{k-1} b_i({\bf x},{\bf h},{\bf h}_1,\dots,{\bf h}_{k-1}) \|_{\mathrm{CUT}(; {\bf h}_1,\dots,{\bf h}_{k-1}, {\bf x}, {\bf h})}.$

After many applications of Lemma 5(iii), (iv), this is bounded by

$\displaystyle \| f_k({\bf x}+{\bf h_1}+\dots+{\bf h_{k-1}}) \|_{\mathrm{CUT}({\bf h}_1,\dots,{\bf h}_{k-1}; {\bf x}, {\bf h})}$

By Lemma 5(ii) we may drop the ${{\bf h}}$ variable, and then the claim follows from Lemma 6.

For part (ii), we replace ${x}$ by ${x+a-h^2}$ and ${h}$ by ${h-a+b}$ to write the left-hand side as

$\displaystyle \mathop{\bf E}_{x, a,b,h \in G} f_1(x+a-h^2) f_2(x+h+b-h^2) f_3(x+a+(h-a+b)^2-h^2);$

the point here is that the first factor does not involve ${b}$ , the second factor does not involve ${a}$ , and the third factor has no quadratic terms in ${h}$ . Letting ${{\bf x}, {\bf a}, {\bf b}, {\bf h}}$ be independent variables drawn uniformly from ${G}$ , we can use Example 4 to bound this in magnitude by

$\displaystyle \| f_1({\bf x}+{\bf a}-{\bf h}^2) f_2({\bf x}+{\bf h}+{\bf b}-{\bf h}^2)$

$\displaystyle f_3( {\bf x}+{\bf a}+({\bf h}-{\bf a}+{\bf b})^2-{\bf h}^2 ) \|_{\mathrm{CUT}(; {\bf x}, {\bf a}, {\bf b}, {\bf h})}$

which by Lemma 5(i),(iii),(iv) is bounded by

$\displaystyle \| f_3( {\bf x}+{\bf a}+({\bf h}-{\bf a}+{\bf b})^2 - {\bf h}^2 ) \|_{\mathrm{CUT}({\bf a}, {\bf b}; {\bf x}, {\bf h})}$

and then by Lemma 5(v) we may bound this by

$\displaystyle \| \Box_{{\bf a}, {\bf a}'} \Box_{{\bf b}, {\bf b}'} f_3( {\bf x}+{\bf a}+({\bf h}-{\bf a}+{\bf b})^2 - {\bf h}^2 ) \|_{\mathrm{CUT}(;{\bf a}, {\bf a}', {\bf b}, {\bf b}', {\bf x}, {\bf h})}^{1/4}$

which by Example 4 is

$\displaystyle |\mathop{\bf E} \Box_{{\bf a}, {\bf a}'} \Box_{{\bf b}, {\bf b}'} f_3( {\bf x}+{\bf a}+({\bf h}-{\bf a}+{\bf b})^2 - {\bf h}^2 )|^{1/4}$

Now the expression inside the expectation is the product of four factors, each of which is ${f_3}$ or ${\overline{f}_3}$ applied to an affine form ${{\bf x} + {\bf c} + {\bf a} {\bf h}}$ where ${{\bf c}}$ depends on ${{\bf a}, {\bf a}', {\bf b}, {\bf b}'}$ and ${{\bf a}}$ is one of ${2({\bf b}-{\bf a})}$ , ${2({\bf b}'-{\bf a})}$ , ${2({\bf b}-{\bf a}')}$ , ${2({\bf b}'-{\bf a}')}$ . With probability ${1-O(1/N)}$ , the four different values of ${{\bf a}}$ are distinct, and then by part (i) we have

$\displaystyle |\mathop{\bf E}(\Box_{{\bf a}, {\bf a}'} \Box_{{\bf b}, {\bf b}'} f_3( {\bf x}+{\bf a}+({\bf h}-{\bf a}+{\bf b})^2 - {\bf h}^2 )|{\bf a}, {\bf a}', {\bf b}, {\bf b}')| \leq \|f_3\|_{U^4({\bf Z}/N{\bf Z})}.$

When they are not distinct, we can instead bound this quantity by ${1}$ . Taking expectations in ${{\bf a}, {\bf a}', {\bf b}, {\bf b}'}$ , we obtain the claim. $\Box$

The analogue of the inverse ${U^2}$ theorem for cut norms is the following claim (which I learned from Ben Green):

Lemma 7 ( ${U^2}$ -type inverse theorem) Let ${\mathbf{x}, \mathbf{h}}$ be independent random variables drawn from a finite abelian group ${G}$ , and let ${f: G \rightarrow {\bf C}}$ be ${1}$ -bounded. Then we have

$\displaystyle \| f(\mathbf{x} + \mathbf{h}) \|_{\mathrm{CUT}(\mathbf{x}, \mathbf{h})} = \sup_{\xi \in\hat G} \| f(\mathbf{x}) e(\xi \cdot \mathbf{x}) \|_{\mathrm{CUT}(\mathbf{x})}$

where ${\hat G}$ is the group of homomorphisms ${\xi: x \mapsto \xi \cdot x}$ is a homomorphism from ${G}$ to ${{\bf R}/{\bf Z}}$ , and ${e(\theta) := e^{2\pi i \theta}}$ .

Proof: Suppose first that ${\| f(\mathbf{x} + \mathbf{h}) \|_{\mathrm{CUT}(\mathbf{x}, \mathbf{h})} > \delta}$ for some ${\delta}$ , then by definition

$\displaystyle |\mathop{\bf E}_{x,h \in G} f(x+h) a(x) b(h)| > \delta$

for some ${1}$ -bounded ${a,b: G \rightarrow {\bf C}}$ . By Fourier expansion, the left-hand side is also

$\displaystyle \sum_{\xi \in \hat G} \hat f(-\xi) \hat a(\xi) \hat b(\xi)$

where ${\hat f(\xi) := \mathop{\bf E}_{x \in G} f(x) e(-\xi \cdot x)}$ . From Plancherel’s theorem we have

$\displaystyle \sum_{\xi \in \hat G} |\hat a(\xi)|^2, \sum_{\xi \in \hat G} |\hat b(\xi)|^2 \leq 1$

hence by Hölder’s inequality one has ${|\hat f(-\xi)| > \delta}$ for some ${\xi \in \hat G}$ , and hence

$\displaystyle \sup_{\xi \in\hat G} \| f(\mathbf{x}) e(\xi \cdot \mathbf{x}) \|_{\mathrm{CUT}(\mathbf{x})} > \delta. \ \ \ \ \ (7)$

Conversely, suppose (7) holds. Then there is ${\xi \in \hat G}$ such that

$\displaystyle \| f(\mathbf{x}) e(\xi \cdot \mathbf{x}) \|_{\mathrm{CUT}(\mathbf{x})} > \delta$

which on substitution and Example 4 implies

$\displaystyle \| f(\mathbf{x}+\mathbf{h}) e(\xi \cdot (\mathbf{x}+\mathbf{h})) \|_{\mathrm{CUT}(;\mathbf{x}, \mathbf{h})} > \delta.$

The term ${e(\xi \cdot (\mathbf{x}+\mathbf{h}))}$ splits into the product of a factor ${e(\xi \cdot \mathbf{x})}$ not depending on ${\mathbf{h}}$ , and a factor ${e(\xi \cdot \mathbf{h})}$ not depending on ${\mathbf{x}}$ . Applying Lemma 5(iii), (iv) we conclude that

$\displaystyle \| f(\mathbf{x}+\mathbf{h}) \|_{\mathrm{CUT}(\mathbf{x}, \mathbf{h})} > \delta.$

The claim follows. $\Box$

The higher order inverse theorems are much less trivial (and the optimal quantitative bounds are not currently known). However, there is a useful degree lowering argument, due to Peluse and Prendiville, that can allow one to lower the order of a uniformity norm in some cases. We give a simple version of this argument here:

Lemma 8 (Degree lowering argument, special case) Let ${G}$ be a finite abelian group, let ${Y}$ be a non-empty finite set, and let ${f: G \rightarrow {\bf C}}$ be a function of the form ${f(x) := \mathop{\bf E}_{y \in Y} F_y(x)}$ for some ${1}$ -bounded functions ${F_y: G \rightarrow {\bf C}}$ indexed by ${y \in Y}$ . Suppose that

$\displaystyle \|f\|_{U^k(G)} \geq \delta$

for some ${k \geq 2}$ and ${0 < \delta \leq 1}$ . Then one of the following claims hold (with implied constants allowed to depend on ${k}$ ):

(i) (Degree lowering) one has ${\|f\|_{U^{k-1}(G)} \gg \delta^{O(1)}}$ .

(ii) (Non-zero frequency) There exist ${h_1,\dots,h_{k-2} \in G}$ and non-zero ${\xi \in \hat G}$ such that
$\displaystyle |\mathop{\bf E}_{x \in G, y \in Y} \Delta_{h_1} \dots \Delta_{h_{k-2}} F_y(x) e( \xi \cdot x )| \gg \delta^{O(1)}.$

There are more sophisticated versions of this argument in which the frequency ${\xi}$ is “minor arc” rather than “zero frequency”, and then the Gowers norms are localised to suitable large arithmetic progressions; this is implicit in the above-mentioned paper of Peluse and Prendiville.

Proof: One can write

$\displaystyle \|f\|_{U^k(G)}^{2^k} = \mathop{\bf E}_{h_1,\dots,h_{k-2} \in G} \|\Delta_{h_1} \dots \Delta_{h_{k-2}} f \|_{U^2(G)}^4$

and hence we conclude that

$\displaystyle \|\Delta_{h_1} \dots \Delta_{h_{k-2}} f \|_{U^2(G)} \gg \delta^{O(1)}$

for a set ${\Sigma}$ of tuples ${(h_1,\dots,h_{k-2}) \in G^{k-2}}$ of density ${h_1,\dots,h_{k-2}}$ . Applying Lemma 6 and Lemma 7, we see that for each such tuple, there exists ${\phi(h_1,\dots,h_{k-2}) \in \hat G}$ such that

$\displaystyle \| \Delta_{h_1} \dots \Delta_{h_{k-2}} f({\bf x}) e( \phi(h_1,\dots,h_{k-2}) \cdot {\bf x} ) \|_{\mathrm{CUT}({\bf x})} \gg \delta^{O(1)}, \ \ \ \ \ (8)$

where ${{\bf x}}$ is drawn uniformly from ${G}$ .

Let us adopt the convention that ${e( \phi( _1,\dots,h_{k-2}) \cdot {\bf x} ) }$ vanishes for ${(h_1,\dots,h_{k-2})}$ not in ${\Sigma}$ , then from Lemma 5(ii) we have

$\displaystyle \| \Delta_{{\bf h}_1} \dots \Delta_{{\bf h}_{k-2}} f({\bf x}) e( \phi({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot {\bf x} ) \|_{\mathrm{CUT}({\bf x}; {\bf h}_1,\dots, {\bf h}_{k-2})} \gg \delta^{O(1)},$

where ${{\bf h}_1,\dots,{\bf h}_{k-2}}$ are independent random variables drawn uniformly from ${G}$ and also independent of ${{\bf x}}$ . By repeated application of Lemma 5(iii) we then have

$\displaystyle \| \Delta_{{\bf h}_1} \dots \Delta_{{\bf h}_{k-2}} f({\bf x}) e( \phi({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot {\bf x} ) \|_{\mathrm{CUT}({\bf x},{\bf h}_1,\dots, {\bf h}_{k-2})} \gg \delta^{O(1)}.$

Expanding out ${\Delta_{h_1} \dots \Delta_{h_{k-2}} f({\bf x})}$ and using Lemma 5(iv) repeatedly we conclude that

$\displaystyle \| f({\bf x} + {\bf h}_1 + \dots + {\bf h}_{k-2}) e( \phi({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot {\bf x} ) \|_{\mathrm{CUT}({\bf x},{\bf h}_1,\dots, {\bf h}_{k-2})} \gg \delta^{O(1)}.$

From definition of ${f}$ we then have

$\displaystyle \| {\bf E}_{y \in Y} F_y({\bf x} + {\bf h}_1 + \dots + {\bf h}_{k-2}) e( \phi({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot {\bf x} ) \|_{\mathrm{CUT}({\bf x},{\bf h}_1,\dots, {\bf h}_{k-2})}$

$\displaystyle \gg \delta^{O(1)}.$

By Lemma 5(vi), we see that the left-hand side is less than

$\displaystyle \| F_{\bf y}({\bf x} + {\bf h}_1 + \dots + {\bf h}_{k-2}) e( \phi({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot {\bf x} ) \|_{\mathrm{CUT}(({\bf x}, {\bf y}),{\bf h}_1,\dots, {\bf h}_{k-2})},$

where ${{\bf y}}$ is drawn uniformly from ${Y}$ , independently of ${{\bf x}, {\bf h}_1,\dots,{\bf h}_{k-2}}$ . By repeated application of Lemma 5(i), (v) repeatedly, we conclude that

$\displaystyle \| \Box_{{\bf h}_1, {\bf h}'_1} \dots \Box_{{\bf h}_{k-2}, {\bf h}'_{k-2}} (F_{\bf y}({\bf x} + {\bf h}_1 + \dots + {\bf h}_{k-2}) e( \phi({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot {\bf x} )) \|_{\mathrm{CUT}(({\bf x},{\bf y}); {\bf h}_1,{\bf h}'_1,\dots, {\bf h}_{k-2}, {\bf h}'_{k-2})} \gg \delta^{O(1)},$

where ${{\bf h}'_1,\dots,{\bf h}'_{k-2}}$ are independent copies of ${{\bf h}_1,\dots,{\bf h}_{k-2}}$ that are also independent of ${{\bf x}}$ , ${{\bf y}}$ . By Lemma 5(ii) and Example 4 we conclude that

$\displaystyle |\mathop{\bf E}( \Box_{{\bf h}_1, {\bf h}'_1} \dots \Box_{{\bf h}_{k-2}, {\bf h}'_{k-2}} (F_{\bf y}({\bf x} + {\bf h}_1 + \dots + {\bf h}_{k-2}) e( \phi({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot {\bf x} )) | {\bf h}_1,{\bf h}'_1,\dots, {\bf h}_{k-2}, {\bf h}'_{k-2}) )| \gg \delta^{O(1)} \ \ \ \ \ (9)$

with probability ${\gg \delta^{O(1)}}$ .

The left-hand side can be rewritten as

$\displaystyle |\mathop{\bf E}_{x \in G, y \in Y} \Delta_{{\bf h}_1 - {\bf h}'_1} \dots \Delta_{{\bf h}_{k-2} - {\bf h}'_{k-2}} F_y( x + {\bf h}'_1 + \dots + {\bf h}'_{k-2})$

$\displaystyle e( \delta_{{\bf h}_1, {\bf h}'_1} \dots \delta_{{\bf h}_{k-2}, {\bf h}'_{k-2}} \phi({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot x )|$

where ${\delta_{{\bf h}_1, {\bf h}'_1}}$ is the additive version of ${\Box_{{\bf h}_1, {\bf h}'_1}}$ , thus

$\displaystyle \delta_{{\bf h}_1, {\bf h}'_1} \phi({\bf h}_1,\dots,{\bf h}_{k-2}) := \phi({\bf h}_1,\dots,{\bf h}_{k-2}) - \phi({\bf h}'_1,\dots,{\bf h}_{k-2}).$

Translating ${x}$ , we can simplify this a little to

$\displaystyle |\mathop{\bf E}_{x \in G, y \in Y} \Delta_{{\bf h}_1 - {\bf h}'_1} \dots \Delta_{{\bf h}_k - {\bf h}'_k} F_y( x ) e( \delta_{{\bf h}_1, {\bf h}'_1} \dots \delta_{{\bf h}_{k-2}, {\bf h}'_{k-2}} \phi({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot x )|$

If the frequency ${\delta_{{\bf h}_1, {\bf h}'_1} \dots \delta_{{\bf h}_{k-2}, {\bf h}'_{k-2}} \phi({\bf h}_1,\dots,{\bf h}_{k-2})}$ is ever non-vanishing in the event (9) then conclusion (ii) applies. We conclude that

$\displaystyle \delta_{{\bf h}_1, {\bf h}'_1} \dots \delta_{{\bf h}_{k-2}, {\bf h}'_{k-2}} \phi({\bf h}_1,\dots,{\bf h}_{k-2}) = 0$

with probability ${\gg \delta^{O(1)}}$ . In particular, by the pigeonhole principle, there exist ${h'_1,\dots,h'_{k-2} \in G}$ such that

$\displaystyle \delta_{{\bf h}_1, h'_1} \dots \delta_{{\bf h}_{k-2}, h'_{k-2}} \phi({\bf h}_1,\dots,{\bf h}_{k-2}) = 0$

with probability ${\gg \delta^{O(1)}}$ . Expanding this out, we obtain a representation of the form

$\displaystyle \phi({\bf h}_1,\dots,{\bf h}_{k-2}) = \sum_{i=1}^{k-2} \phi_i({\bf h}_1,\dots,{\bf h}_{k-2})$

holding with probability ${\gg \delta^{O(1)}}$ , where the ${\phi_i: G^{k-2} \rightarrow {\bf R}/{\bf Z}}$ are functions that do not depend on the ${i^{th}}$ coordinate. From (8) we conclude that

$\displaystyle \| \Delta_{h_1} \dots \Delta_{h_{k-2}} f({\bf x}) e( \sum_{i=1}^{k-2} \phi_i(h_1,\dots,h_{k-2}) \cdot {\bf x} ) \|_{\mathrm{CUT}({\bf x})} \gg \delta^{O(1)}$

for ${\gg \delta^{O(1)}}$ of the tuples ${(h_1,\dots,h_{k-2}) \in G^{k-2}}$ . Thus by Lemma 5(ii)

$\displaystyle \| \Delta_{{\bf h}_1} \dots \Delta_{{\bf h}_{k-2}} f({\bf x}) e( \sum_{i=1}^{k-2} \phi_i({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot {\bf x} ) \|_{\mathrm{CUT}({\bf x}; {\bf h}_1,\dots,{\bf h}_{k-2})} \gg \delta^{O(1)}.$

By repeated application of Lemma 5(iii) we then have

$\displaystyle \| \Delta_{{\bf h}_1} \dots \Delta_{{\bf h}_{k-2}} f({\bf x}) e( \sum_{i=1}^{k-2} \phi_i({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot {\bf x} ) \|_{\mathrm{CUT}({\bf x}, {\bf h}_1,\dots,{\bf h}_{k-2})} \gg \delta^{O(1)}$

and then by repeated application of Lemma 5(iv)

$\displaystyle \| f({\bf x} + {\bf h}_1 + \dots + {\bf h}_{k-2}) \|_{\mathrm{CUT}({\bf x}, {\bf h}_1,\dots,{\bf h}_{k-2})} \gg \delta^{O(1)}$

and then the conclusion (i) follows from Lemma 6. $\Box$

As an application of degree lowering, we give an inverse theorem for the average in Proposition 1(ii), first established by Bourgain-Chang and later reproved by Peluse (by different methods from those given here):

Proposition 9 Let ${G = {\bf Z}/N{\bf Z}}$ be a cyclic group of prime order. Suppose that one has ${1}$ -bounded functions ${f_1,f_2,f_3: G \rightarrow {\bf C}}$ such that

$\displaystyle |\mathop{\bf E}_{x, h \in G} f_1(x) f_2(x+h) f_3(x+h^2)| \geq \delta \ \ \ \ \ (10)$

for some ${\delta > 0}$ . Then either ${N \ll \delta^{-O(1)}}$ , or one has

$\displaystyle |\mathop{\bf E}_{x \in G} f_1(x)|, |\mathop{\bf E}_{x \in G} f_2(x)| \gg \delta^{O(1)}.$

We remark that a modification of the arguments below also give ${|\mathop{\bf E}_{x \in G} f_3(x)| \gg \delta^{O(1)}}$ .

Proof: The left-hand side of (10) can be written as

$\displaystyle |\mathop{\bf E}_{x \in G} F(x) f_3(x)|$

where ${F}$ is the dual function

$\displaystyle F(x) := \mathop{\bf E}_{h \in G} f_1(x-h^2) f_2(x-h^2+h).$

By Cauchy-Schwarz one thus has

$\displaystyle |\mathop{\bf E}_{x \in G} F(x) \overline{F}(x)| \geq \delta^2$

and hence by Proposition 1, we either have ${N \ll \delta^{-O(1)}}$ (in which case we are done) or

$\displaystyle \|F\|_{U^4(G)} \gg \delta^2.$

Writing ${F = \mathop{\bf E}_{h \in G} F_h}$ with ${F_h(x) := f_1(x-h^2) f_2(x-h^2+h)}$ , we conclude that either ${\|F\|_{U^3(G)} \gg \delta^{O(1)}}$ , or that

$\displaystyle |\mathop{\bf E}_{x,h \in G} \Delta_{h_1} \Delta_{h_2} F_h(x) e(\xi x / N )| \gg \delta^{O(1)}$

for some ${h_1,h_2 \in G}$ and non-zero ${\xi \in G}$ . The left-hand side can be rewritten as

$\displaystyle |\mathop{\bf E}_{x,h \in G} g_1(x-h^2) g_2(x-h^2+h) e(\xi x/N)|$

where ${g_1 = \Delta_{h_1} \Delta_{h_2} f_1}$ and ${g_2 = \Delta_{h_1} \Delta_{h_2} f_2}$ . We can rewrite this in turn as

$\displaystyle |\mathop{\bf E}_{x,y \in G} g_1(x) g_2(y) e(\xi (x + (y-x)^2) / N)|$

which is bounded by

$\displaystyle \| e(\xi({\bf x} + ({\bf y}-{\bf x})^2)/N) \|_{\mathrm{CUT}({\bf x}, {\bf y})}$

where ${{\bf x}, {\bf y}}$ are independent random variables drawn uniformly from ${G}$ . Applying Lemma 5(v), we conclude that

$\displaystyle \| \Box_{{\bf y}, {\bf y}'} e(\xi({\bf x} + ({\bf y}-{\bf x})^2)/N) \|_{\mathrm{CUT}({\bf x}; {\bf y}, {\bf y}')} \gg \delta^{O(1)}.$

However, a routine Gauss sum calculation reveals that the left-hand side is ${O(N^{-c})}$ for some absolute constant ${c>0}$ because ${\xi}$ is non-zero, so that ${N \ll \delta^{-O(1)}}$ . The only remaining case to consider is when

$\displaystyle \|F\|_{U^3(G)} \gg \delta^{O(1)}.$

Repeating the above arguments we then conclude that

$\displaystyle \|F\|_{U^2(G)} \gg \delta^{O(1)},$

and then

$\displaystyle \|F\|_{U^1(G)} \gg \delta^{O(1)}.$

The left-hand side can be computed to equal ${|\mathop{\bf E}_{x \in G} f_1(x)| |\mathop{\bf E}_{x \in G} f_2(x)|}$ , and the claim follows. $\Box$

This argument was given for the cyclic group setting, but the argument can also be applied to the integers (see Peluse-Prendiville) and can also be used to establish an analogue over the reals (that was first obtained by Bourgain).

Concatenation theorems for anti-Gowers-uniform functions and Host-Kra characteristic factors; polynomial patterns in primes

27 March, 2016 in math.CO, math.DS, math.NT, paper | Tags: characteristic factor, concatenation theorems, Gowers uniformity norms, polynomial recurrence, Tamar Ziegler | by Terence Tao | 22 comments

Tamar Ziegler and I have just uploaded to the arXiv two related papers: “Concatenation theorems for anti-Gowers-uniform functions and Host-Kra characteoristic factors” and “polynomial patterns in primes“, with the former developing a “quantitative Bessel inequality” for local Gowers norms that is crucial in the latter.

We use the term “concatenation theorem” to denote results in which structural control of a function in two or more “directions” can be “concatenated” into structural control in a joint direction. A trivial example of such a concatenation theorem is the following: if a function ${f: {\bf Z} \times {\bf Z} \rightarrow {\bf R}}$ is constant in the first variable (thus ${x \mapsto f(x,y)}$ is constant for each ${y}$ ), and also constant in the second variable (thus ${y \mapsto f(x,y)}$ is constant for each ${x}$ ), then it is constant in the joint variable ${(x,y)}$ . A slightly less trivial example: if a function ${f: {\bf Z} \times {\bf Z} \rightarrow {\bf R}}$ is affine-linear in the first variable (thus, for each ${y}$ , there exist ${\alpha(y), \beta(y)}$ such that ${f(x,y) = \alpha(y) x + \beta(y)}$ for all ${x}$ ) and affine-linear in the second variable (thus, for each ${x}$ , there exist ${\gamma(x), \delta(x)}$ such that ${f(x,y) = \gamma(x)y + \delta(x)}$ for all ${y}$ ) then ${f}$ is a quadratic polynomial in ${x,y}$ ; in fact it must take the form

$\displaystyle f(x,y) = \epsilon xy + \zeta x + \eta y + \theta \ \ \ \ \ (1)$

for some real numbers ${\epsilon, \zeta, \eta, \theta}$ . (This can be seen for instance by using the affine linearity in ${y}$ to show that the coefficients ${\alpha(y), \beta(y)}$ are also affine linear.)

The same phenomenon extends to higher degree polynomials. Given a function ${f: G \rightarrow K}$ from one additive group ${G}$ to another, we say that ${f}$ is of degree less than ${d}$ along a subgroup ${H}$ of ${G}$ if all the ${d}$ -fold iterated differences of ${f}$ along directions in ${H}$ vanish, that is to say

$\displaystyle \partial_{h_1} \dots \partial_{h_d} f(x) = 0$

for all ${x \in G}$ and ${h_1,\dots,h_d \in H}$ , where ${\partial_h}$ is the difference operator

$\displaystyle \partial_h f(x) := f(x+h) - f(x).$

(We adopt the convention that the only ${f}$ of degree less than ${0}$ is the zero function.)

We then have the following simple proposition:

Proposition 1 (Concatenation of polynomiality) Let ${f: G \rightarrow K}$ be of degree less than ${d_1}$ along one subgroup ${H_1}$ of ${G}$ , and of degree less than ${d_2}$ along another subgroup ${H_2}$ of ${G}$ , for some ${d_1,d_2 \geq 1}$ . Then ${f}$ is of degree less than ${d_1+d_2-1}$ along the subgroup ${H_1+H_2}$ of ${G}$ .

Note the previous example was basically the case when ${G = {\bf Z} \times {\bf Z}}$ , ${H_1 = {\bf Z} \times \{0\}}$ , ${H_2 = \{0\} \times {\bf Z}}$ , ${K = {\bf R}}$ , and ${d_1=d_2=2}$ .

Proof: The claim is trivial for ${d_1=1}$ or ${d_2=1}$ (in which ${f}$ is constant along ${H_1}$ or ${H_2}$ respectively), so suppose inductively ${d_1,d_2 \geq 2}$ and the claim has already been proven for smaller values of ${d_1-1}$ .

We take a derivative in a direction ${h_1 \in H_1}$ along ${h_1}$ to obtain

$\displaystyle T^{-h_1} f = f + \partial_{h_1} f$

where ${T^{-h_1} f(x) = f(x+h_1)}$ is the shift of ${f}$ by ${-h_1}$ . Then we take a further shift by a direction ${h_2 \in H_2}$ to obtain

$\displaystyle T^{-h_1-h_2} f = T^{-h_2} f + T^{-h_2} \partial_{h_1} f = f + \partial_{h_2} f + T^{-h_2} \partial_{h_1} f$

leading to the cocycle equation

$\displaystyle \partial_{h_1+h_2} f = \partial_{h_2} f + T^{-h_2} \partial_{h_1} f.$

Since ${f}$ has degree less than ${d_1}$ along ${H_1}$ and degree less than ${d_2}$ along ${H_2}$ , ${\partial_{h_1} f}$ has degree less than ${d_1-1}$ along ${H_1}$ and less than ${d_2}$ along ${H_2}$ , so is degree less than ${d_1+d_2-2}$ along ${H_1+H_2}$ by induction hypothesis. Similarly ${\partial_{h_2} f}$ is also of degree less than ${d_1+d_2-2}$ along ${H_1+H_2}$ . Combining this with the cocycle equation we see that ${\partial_{h_1+h_2}f}$ is of degree less than ${d_1+d_2-2}$ along ${H_1+H_2}$ for any ${h_1+h_2 \in H_1+H_2}$ , and hence ${f}$ is of degree less than ${d_1+d_2-1}$ along ${H_1+H_2}$ , as required. $\Box$

While this proposition is simple, it already illustrates some basic principles regarding how one would go about proving a concatenation theorem:

(i) One should perform induction on the degrees ${d_1,d_2}$ involved, and take advantage of the recursive nature of degree (in this case, the fact that a function is of less than degree ${d}$ along some subgroup ${H}$ of directions iff all of its first derivatives along ${H}$ are of degree less than ${d-1}$ ).
(ii) Structure is preserved by operations such as addition, shifting, and taking derivatives. In particular, if a function ${f}$ is of degree less than ${d}$ along some subgroup ${H}$ , then any derivative ${\partial_k f}$ of ${f}$ is also of degree less than ${d}$ along ${H}$ , even if ${k}$ does not belong to ${H}$ .

Here is another simple example of a concatenation theorem. Suppose an at most countable additive group ${G}$ acts by measure-preserving shifts ${T: g \mapsto T^g}$ on some probability space ${(X, {\mathcal X}, \mu)}$ ; we call the pair ${(X,T)}$ (or more precisely ${(X, {\mathcal X}, \mu, T)}$ ) a ${G}$ -system. We say that a function ${f \in L^\infty(X)}$ is a generalised eigenfunction of degree less than ${d}$ along some subgroup ${H}$ of ${G}$ and some ${d \geq 1}$ if one has

$\displaystyle T^h f = \lambda_h f$

almost everywhere for all ${h \in H}$ , and some functions ${\lambda_h \in L^\infty(X)}$ of degree less than ${d-1}$ along ${H}$ , with the convention that a function has degree less than ${0}$ if and only if it is equal to ${1}$ . Thus for instance, a function ${f}$ is an generalised eigenfunction of degree less than ${1}$ along ${H}$ if it is constant on almost every ${H}$ -ergodic component of ${G}$ , and is a generalised function of degree less than ${2}$ along ${H}$ if it is an eigenfunction of the shift action on almost every ${H}$ -ergodic component of ${G}$ . A basic example of a higher order eigenfunction is the function ${f(x,y) := e^{2\pi i y}}$ on the skew shift ${({\bf R}/{\bf Z})^2}$ with ${{\bf Z}}$ action given by the generator ${T(x,y) := (x+\alpha,y+x)}$ for some irrational ${\alpha}$ . One can check that ${T^h f = \lambda_h f}$ for every integer ${h}$ , where ${\lambda_h: x \mapsto e^{2\pi i \binom{h}{2} \alpha} e^{2\pi i h x}}$ is a generalised eigenfunction of degree less than ${2}$ along ${{\bf Z}}$ , so ${f}$ is of degree less than ${3}$ along ${{\bf Z}}$ .

We then have

Proposition 2 (Concatenation of higher order eigenfunctions) Let ${(X,T)}$ be a ${G}$ -system, and let ${f \in L^\infty(X)}$ be a generalised eigenfunction of degree less than ${d_1}$ along one subgroup ${H_1}$ of ${G}$ , and a generalised eigenfunction of degree less than ${d_2}$ along another subgroup ${H_2}$ of ${G}$ , for some ${d_1,d_2 \geq 1}$ . Then ${f}$ is a generalised eigenfunction of degree less than ${d_1+d_2-1}$ along the subgroup ${H_1+H_2}$ of ${G}$ .

The argument is almost identical to that of the previous proposition and is left as an exercise to the reader. The key point is the point (ii) identified earlier: the space of generalised eigenfunctions of degree less than ${d}$ along ${H}$ is preserved by multiplication and shifts, as well as the operation of “taking derivatives” ${f \mapsto \lambda_k}$ even along directions ${k}$ that do not lie in ${H}$ . (To prove this latter claim, one should restrict to the region where ${f}$ is non-zero, and then divide ${T^k f}$ by ${f}$ to locate ${\lambda_k}$ .)

A typical example of this proposition in action is as follows: consider the ${{\bf Z}^2}$ -system given by the ${3}$ -torus ${({\bf R}/{\bf Z})^3}$ with generating shifts

$\displaystyle T^{(1,0)}(x,y,z) := (x+\alpha,y,z+y)$

$\displaystyle T^{(0,1)}(x,y,z) := (x,y+\alpha,z+x)$

for some irrational ${\alpha}$ , which can be checked to give a ${{\bf Z}^2}$ action

$\displaystyle T^{(n,m)}(x,y,z) := (x+n\alpha, y+m\alpha, z+ny+mx+nm\alpha).$

The function ${f(x,y,z) := e^{2\pi i z}}$ can then be checked to be a generalised eigenfunction of degree less than ${2}$ along ${{\bf Z} \times \{0\}}$ , and also less than ${2}$ along ${\{0\} \times {\bf Z}}$ , and less than ${3}$ along ${{\bf Z}^2}$ . One can view this example as the dynamical systems translation of the example (1) (see this previous post for some more discussion of this sort of correspondence).

The main results of our concatenation paper are analogues of these propositions concerning a more complicated notion of “polynomial-like” structure that are of importance in additive combinatorics and in ergodic theory. On the ergodic theory side, the notion of structure is captured by the Host-Kra characteristic factors ${Z^{<d}_H(X)}$ of a ${G}$ -system ${X}$ along a subgroup ${H}$ . These factors can be defined in a number of ways. One is by duality, using the Gowers-Host-Kra uniformity seminorms (defined for instance here) ${\| \|_{U^d_H(X)}}$ . Namely, ${Z^{<d}_H(X)}$ is the factor of ${X}$ defined up to equivalence by the requirement that

$\displaystyle \|f\|_{U^d_H(X)} = 0 \iff {\bf E}(f | Z^{<d}_H(X) ) = 0.$

An equivalent definition is in terms of the dual functions ${{\mathcal D}^d_H(f)}$ of ${f}$ along ${H}$ , which can be defined recursively by setting ${{\mathcal D}^0_H(f) = 1}$ and

$\displaystyle {\mathcal D}^d_H(f) = {\bf E}_h T^h f {\mathcal D}^{d-1}( f \overline{T^h f} )$

where ${{\bf E}_h}$ denotes the ergodic average along a Følner sequence in ${G}$ (in fact one can also define these concepts in non-amenable abelian settings as per this previous post). The factor ${Z^{<d}_H(X)}$ can then be alternately defined as the factor generated by the dual functions ${{\mathcal D}^d_H(f)}$ for ${f \in L^\infty(X)}$ .

In the case when ${G=H={\bf Z}}$ and ${X}$ is ${G}$ -ergodic, a deep theorem of Host and Kra shows that the factor ${Z^{<d}_H(X)}$ is equivalent to the inverse limit of nilsystems of step less than ${d}$ . A similar statement holds with ${{\bf Z}}$ replaced by any finitely generated group by Griesmer, while the case of an infinite vector space over a finite field was treated in this paper of Bergelson, Ziegler, and myself. The situation is more subtle when ${X}$ is not ${G}$ -ergodic, or when ${X}$ is ${G}$ -ergodic but ${H}$ is a proper subgroup of ${G}$ acting non-ergodically, when one has to start considering measurable families of directional nilsystems; see for instance this paper of Austin for some of the subtleties involved (for instance, higher order group cohomology begins to become relevant!).

One of our main theorems is then

Proposition 3 (Concatenation of characteristic factors) Let ${(X,T)}$ be a ${G}$ -system, and let ${f}$ be measurable with respect to the factor ${Z^{<d_1}_{H_1}(X)}$ and with respect to the factor ${Z^{<d_2}_{H_2}(X)}$ for some ${d_1,d_2 \geq 1}$ and some subgroups ${H_1,H_2}$ of ${G}$ . Then ${f}$ is also measurable with respect to the factor ${Z^{<d_1+d_2-1}_{H_1+H_2}(X)}$ .

We give two proofs of this proposition in the paper; an ergodic-theoretic proof using the Host-Kra theory of “cocycles of type ${<d}$ (along a subgroup ${H}$ )”, which can be used to inductively describe the factors ${Z^{<d}_H}$ , and a combinatorial proof based on a combinatorial analogue of this proposition which is harder to state (but which roughly speaking asserts that a function which is nearly orthogonal to all bounded functions of small ${U^{d_1}_{H_1}}$ norm, and also to all bounded functions of small ${U^{d_2}_{H_2}}$ norm, is also nearly orthogonal to alll bounded functions of small ${U^{d_1+d_2-1}_{H_1+H_2}}$ norm). The combinatorial proof parallels the proof of Proposition 2. A key point is that dual functions ${F := {\mathcal D}^d_H(f)}$ obey a property analogous to being a generalised eigenfunction, namely that

$\displaystyle T^h F = {\bf E}_k \lambda_{h,k} F_k$

where ${F_k := T^k F}$ and ${\lambda_{h,k} := {\mathcal D}^{d-1}( T^h f \overline{T^k f} )}$ is a “structured function of order ${d-1}$ ” along ${H}$ . (In the language of this previous paper of mine, this is an assertion that dual functions are uniformly almost periodic of order ${d}$ .) Again, the point (ii) above is crucial, and in particular it is key that any structure that ${F}$ has is inherited by the associated functions ${\lambda_{h,k}}$ and ${F_k}$ . This sort of inheritance is quite easy to accomplish in the ergodic setting, as there is a ready-made language of factors to encapsulate the concept of structure, and the shift-invariance and ${\sigma}$ -algebra properties of factors make it easy to show that just about any “natural” operation one performs on a function measurable with respect to a given factor, returns a function that is still measurable in that factor. In the finitary combinatorial setting, though, encoding the fact (ii) becomes a remarkably complicated notational nightmare, requiring a huge amount of “epsilon management” and “second-order epsilon management” (in which one manages not only scalar epsilons, but also function-valued epsilons that depend on other parameters). In order to avoid all this we were forced to utilise a nonstandard analysis framework for the combinatorial theorems, which made the arguments greatly resemble the ergodic arguments in many respects (though the two settings are still not equivalent, see this previous blog post for some comparisons between the two settings). Unfortunately the arguments are still rather complicated.

For combinatorial applications, dual formulations of the concatenation theorem are more useful. A direct dualisation of the theorem yields the following decomposition theorem: a bounded function which is small in ${U^{d_1+d_2-1}_{H_1+H_2}}$ norm can be split into a component that is small in ${U^{d_1}_{H_1}}$ norm, and a component that is small in ${U^{d_2}_{H_2}}$ norm. (One may wish to understand this type of result by first proving the following baby version: any function that has mean zero on every coset of ${H_1+H_2}$ , can be decomposed as the sum of a function that has mean zero on every ${H_1}$ coset, and a function that has mean zero on every ${H_2}$ coset. This is dual to the assertion that a function that is constant on every ${H_1}$ coset and constant on every ${H_2}$ coset, is constant on every ${H_1+H_2}$ coset.) Combining this with some standard “almost orthogonality” arguments (i.e. Cauchy-Schwarz) give the following Bessel-type inequality: if one has a lot of subgroups ${H_1,\dots,H_k}$ and a bounded function is small in ${U^{2d-1}_{H_i+H_j}}$ norm for most ${i,j}$ , then it is also small in ${U^d_{H_i}}$ norm for most ${i}$ . (Here is a baby version one may wish to warm up on: if a function ${f}$ has small mean on ${({\bf Z}/p{\bf Z})^2}$ for some large prime ${p}$ , then it has small mean on most of the cosets of most of the one-dimensional subgroups of ${({\bf Z}/p{\bf Z})^2}$ .)

There is also a generalisation of the above Bessel inequality (as well as several of the other results mentioned above) in which the subgroups ${H_i}$ are replaced by more general coset progressions ${H_i+P_i}$ (of bounded rank), so that one has a Bessel inequailty controlling “local” Gowers uniformity norms such as ${U^d_{P_i}}$ by “global” Gowers uniformity norms such as ${U^{2d-1}_{P_i+P_j}}$ . This turns out to be particularly useful when attempting to compute polynomial averages such as

$\displaystyle \sum_{n \leq N} \sum_{r \leq \sqrt{N}} f(n) g(n+r^2) h(n+2r^2) \ \ \ \ \ (2)$

for various functions ${f,g,h}$ . After repeated use of the van der Corput lemma, one can control such averages by expressions such as

$\displaystyle \sum_{n \leq N} \sum_{h,m,k \leq \sqrt{N}} f(n) f(n+mh) f(n+mk) f(n+m(h+k))$

(actually one ends up with more complicated expressions than this, but let’s use this example for sake of discussion). This can be viewed as an average of various ${U^2}$ Gowers uniformity norms of ${f}$ along arithmetic progressions of the form ${\{ mh: h \leq \sqrt{N}\}}$ for various ${m \leq \sqrt{N}}$ . Using the above Bessel inequality, this can be controlled in turn by an average of various ${U^3}$ Gowers uniformity norms along rank two generalised arithmetic progressions of the form ${\{ m_1 h_1 + m_2 h_2: h_1,h_2 \le \sqrt{N}\}}$ for various ${m_1,m_2 \leq \sqrt{N}}$ . But for generic ${m_1,m_2}$ , this rank two progression is close in a certain technical sense to the “global” interval ${\{ n: n \leq N \}}$ (this is ultimately due to the basic fact that two randomly chosen large integers are likely to be coprime, or at least have a small gcd). As a consequence, one can use the concatenation theorems from our first paper to control expressions such as (2) in terms of global Gowers uniformity norms. This is important in number theoretic applications, when one is interested in computing sums such as

$\displaystyle \sum_{n \leq N} \sum_{r \leq \sqrt{N}} \mu(n) \mu(n+r^2) \mu(n+2r^2)$

$\displaystyle \sum_{n \leq N} \sum_{r \leq \sqrt{N}} \Lambda(n) \Lambda(n+r^2) \Lambda(n+2r^2)$

where ${\mu}$ and ${\Lambda}$ are the Möbius and von Mangoldt functions respectively. This is because we are able to control global Gowers uniformity norms of such functions (thanks to results such as the proof of the inverse conjecture for the Gowers norms, the orthogonality of the Möbius function with nilsequences, and asymptotics for linear equations in primes), but much less control is currently available for local Gowers uniformity norms, even with the assistance of the generalised Riemann hypothesis (see this previous blog post for some further discussion).

By combining these tools and strategies with the “transference principle” approach from our previous paper (as improved using the recent “densification” technique of Conlon, Fox, and Zhao, discussed in this previous post), we are able in particular to establish the following result:

Theorem 4 (Polynomial patterns in the primes) Let ${P_1,\dots,P_k: {\bf Z} \rightarrow {\bf Z}}$ be polynomials of degree at most ${d}$ , whose degree ${d}$ coefficients are all distinct, for some ${d \geq 1}$ . Suppose that ${P_1,\dots,P_k}$ is admissible in the sense that for every prime ${p}$ , there are ${n,r}$ such that ${n+P_1(r),\dots,n+P_k(r)}$ are all coprime to ${p}$ . Then there exist infinitely many pairs ${n,r}$ of natural numbers such that ${n+P_1(r),\dots,n+P_k(r)}$ are prime.

Furthermore, we obtain an asymptotic for the number of such pairs ${n,r}$ in the range ${n \leq N}$ , ${r \leq N^{1/d}}$ (actually for minor technical reasons we reduce the range of ${r}$ to be very slightly less than ${N^{1/d}}$ ). In fact one could in principle obtain asymptotics for smaller values of ${r}$ , and relax the requirement that the degree ${d}$ coefficients be distinct with the requirement that no two of the ${P_i}$ differ by a constant, provided one had good enough local uniformity results for the Möbius or von Mangoldt functions. For instance, we can obtain an asymptotic for triplets of the form ${n, n+r,n+r^d}$ unconditionally for ${d \leq 5}$ , and conditionally on GRH for all ${d}$ , using known results on primes in short intervals on average.

The ${d=1}$ case of this theorem was obtained in a previous paper of myself and Ben Green (using the aforementioned conjectures on the Gowers uniformity norm and the orthogonality of the Möbius function with nilsequences, both of which are now proven). For higher ${d}$ , an older result of Tamar and myself was able to tackle the case when ${P_1(0)=\dots=P_k(0)=0}$ (though our results there only give lower bounds on the number of pairs ${(n,r)}$ , and no asymptotics). Both of these results generalise my older theorem with Ben Green on the primes containing arbitrarily long arithmetic progressions. The theorem also extends to multidimensional polynomials, in which case there are some additional previous results; see the paper for more details. We also get a technical refinement of our previous result on narrow polynomial progressions in (dense subsets of) the primes by making the progressions just a little bit narrower in the case of the density of the set one is using is small.

Deducing the inverse theorem for the multidimensional Gowers norms from the one-dimensional version

24 July, 2015 in expository, math.CO | Tags: Ben Green, Freiman isomorphism, Gowers uniformity norms, Nikos Frantzikinakis | by Terence Tao | 1 comment

This week I have been at a Banff workshop “Combinatorics meets Ergodic theory“, focused on the combinatorics surrounding Szemerédi’s theorem and the Gowers uniformity norms on one hand, and the ergodic theory surrounding Furstenberg’s multiple recurrence theorem and the Host-Kra structure theory on the other. This was quite a fruitful workshop, and directly inspired the various posts this week on this blog. Incidentally, BIRS being as efficient as it is, videos for this week’s talks are already online.

As mentioned in the previous two posts, Ben Green, Tamar Ziegler, and myself proved the following inverse theorem for the Gowers norms:

Theorem 1 (Inverse theorem for Gowers norms) Let ${N \geq 1}$ and ${s \geq 1}$ be integers, and let ${\delta > 0}$ . Suppose that ${f: {\bf Z} \rightarrow [-1,1]}$ is a function supported on ${[N] := \{1,\dots,N\}}$ such that

$\displaystyle \frac{1}{N^{s+2}} \sum_{n,h_1,\dots,h_{s+1} \in {\bf Z}} \prod_{\omega \in \{0,1\}^{s+1}} f(n+\omega_1 h_1 + \dots + \omega_{s+1} h_{s+1}) \geq \delta.$

Then there exists a filtered nilmanifold ${G/\Gamma}$ of degree ${\leq s}$ and complexity ${O_{s,\delta}(1)}$ , a polynomial sequence ${g: {\bf Z} \rightarrow G}$ , and a Lipschitz function ${F: G/\Gamma \rightarrow {\bf R}}$ of Lipschitz constant ${O_{s,\delta}(1)}$ such that

$\displaystyle \frac{1}{N} \sum_n f(n) F(g(n) \Gamma) \gg_{s,\delta} 1.$

There is a higher dimensional generalisation, which first appeared explicitly (in a more general form) in this preprint of Szegedy (which used a slightly different argument than the one of Ben, Tammy, and myself; see also this previous preprint of Szegedy with related results):

Theorem 2 (Inverse theorem for multidimensional Gowers norms) Let ${N \geq 1}$ and ${s,d \geq 1}$ be integers, and let ${\delta > 0}$ . Suppose that ${f: {\bf Z}^d \rightarrow [-1,1]}$ is a function supported on ${[N]^d}$ such that

$\displaystyle \frac{1}{N^{d(s+2)}} \sum_{n,h_1,\dots,h_{s+1} \in {\bf Z}^d} \prod_{\omega \in \{0,1\}^{s+1}} f(n+\omega_1 h_1 + \dots + \omega_{s+1} h_{s+1}) \geq \delta. \ \ \ \ \ (1)$

Then there exists a filtered nilmanifold ${G/\Gamma}$ of degree ${\leq s}$ and complexity ${O_{s,\delta,d}(1)}$ , a polynomial sequence ${g: {\bf Z}^d \rightarrow G}$ , and a Lipschitz function ${F: G/\Gamma \rightarrow {\bf R}}$ of Lipschitz constant ${O_{s,\delta,d}(1)}$ such that

$\displaystyle \frac{1}{N^d} \sum_{n \in {\bf Z}^d} f(n) F(g(n) \Gamma) \gg_{s,\delta,d} 1.$

The ${d=2}$ case of this theorem was recently used by Wenbo Sun. One can replace the polynomial sequence with a linear sequence if desired by using a lifting trick (essentially due to Furstenberg, but which appears explicitly in Appendix C of my paper with Ben and Tammy).

In this post I would like to record a very neat and simple observation of Ben Green and Nikos Frantzikinakis, that uses the tool of Freiman isomorphisms to derive Theorem 2 as a corollary of the one-dimensional theorem. Namely, consider the linear map ${\phi: {\bf Z}^d \rightarrow {\bf Z}}$ defined by

$\displaystyle \phi( n_1,\dots,n_d ) := \sum_{i=1}^d (10 N)^{i-1} n_i,$

that is to say ${\phi}$ is the digit string base ${10N}$ that has digits ${n_d \dots n_1}$ . This map is a linear map from ${[N]^d}$ to a subset of ${[d 10^d N^d]}$ of density ${1/(d10^d)}$ . Furthermore it has the following “Freiman isomorphism” property: if ${n, h_1,\dots,h_{s+1}}$ lie in ${{\bf Z}}$ with ${n + \omega_1 h_1 + \dots + \omega_{s+1} h_{s+1}}$ in the image set ${\phi( [N]^d )}$ of ${[N]^d}$ for all ${\omega}$ , then there exist (unique) lifts ${\tilde n \in {\bf Z}^d, \tilde h_1,\dots,\tilde h_{s+1} \in {\bf Z}}$ such that

$\displaystyle \tilde n + \omega_1 \tilde h_1 + \dots + \omega_{s+1} \tilde h_{s+1} \in [N]^d$

and

$\displaystyle \phi( \tilde n + \omega_1 \tilde h_1 + \dots + \omega_{s+1} \tilde h_{s+1} ) = n + \omega_1 h_1 + \dots + \omega_{s+1} h_{s+1}$

for all ${\omega}$ . Indeed, the injectivity of ${\phi}$ on ${[N]^d}$ uniquely determines the sum ${\tilde n + \omega_1 \tilde h_1 + \dots + \omega_{s+1} \tilde h_{s+1}}$ for each ${\omega}$ , and one can use base ${10N}$ arithmetic to verify that the alternating sum of these sums on any ${2}$ -facet of the cube ${\{0,1\}^{s+1}}$ vanishes, which gives the claim. (In the language of additive combinatorics, the point is that ${\phi}$ is a Freiman isomorphism of order (say) ${8}$ on ${[N]^d}$ .)

Now let ${\tilde f: {\bf Z} \rightarrow [-1,1]}$ be the function defined by setting ${\tilde f( \phi(n) ) := f(n)}$ whenever ${n \in [N]^d}$ , with ${\tilde f}$ vanishing outside of ${\phi([N]^d)}$ . If ${f}$ obeys (1), then from the above Freiman isomorphism property we have

$\displaystyle \frac{1}{N^{d(s+2)}} \sum_{n, h_1,\dots,h_{s+1} \in {\bf Z}} \prod_{\omega \in \{0,1\}^{s+1}} \tilde f(n+\omega_1 h_1 + \dots + \omega_{s+1} h_{s+1}) \geq \delta.$

Applying the one-dimensional inverse theorem (Theorem 1), with ${\delta}$ reduced by a factor of ${d 10^d}$ and ${N}$ replaced by ${d 10^d N^d}$ , this implies the existence of a filtered nilmanifold ${G/\Gamma}$ of degree ${\leq s}$ and complexity ${O_{s,\delta,d}(1)}$ , a polynomial sequence ${g: {\bf Z} \rightarrow G}$ , and a Lipschitz function ${F: G/\Gamma \rightarrow {\bf R}}$ of Lipschitz constant ${O_{s,\delta,d}(1)}$ such that

$\displaystyle \frac{1}{N^{d(s+2)}} \sum_{n \in {\bf Z}} \tilde f(n) F(g(n) \Gamma) \gg_{s,\delta,d} 1$

which by the Freiman isomorphism property again implies that

$\displaystyle \frac{1}{N^{d(s+2)}} \sum_{n \in {\bf Z}^d} f(n) F(g(\phi(n)) \Gamma) \gg_{s,\delta,d} 1.$

But the map ${n \mapsto g(\phi(n))}$ is clearly a polynomial map from ${{\bf Z}^d}$ to ${G}$ (the composition of two polynomial maps is polynomial, see e.g. Appendix B of my paper with Ben and Tammy), and the claim follows.

Remark 3 This trick appears to be largely restricted to the case of boundedly generated groups such as ${{\bf Z}^d}$ ; I do not see any easy way to deduce an inverse theorem for, say, ${\bigcup_{n=1}^\infty {\mathbb F}_p^n}$ from the ${{\bf Z}}$ -inverse theorem by this method.

Remark 4 By combining this argument with the one in the previous post, one can obtain a weak ergodic inverse theorem for ${{\bf Z}^d}$ -actions. Interestingly, the Freiman isomorphism argument appears to be difficult to implement directly in the ergodic category; in particular, there does not appear to be an obvious direct way to derive the Host-Kra inverse theorem for ${{\bf Z}^d}$ actions (a result first obtained in the PhD thesis of Griesmer) from the counterpart for ${{\bf Z}}$ actions.

	Jianfeng Li on An introduction to measure…
	Jianfeng Li on An introduction to measure…
	Jianfeng Li on An introduction to measure…
	Jianfeng Li on An introduction to measure…
	Anonymous on 275A, Notes 3: The weak and st…
	Anonymous on 275A, Notes 3: The weak and st…
	Anonymous on Dense sets of natural numbers…
	Anonymous on Dense sets of natural numbers…
	Anonymous on 275A, Notes 3: The weak and st…
	Anonymous on Dense sets of natural numbers…
	Fabrice Imparato on Dense sets of natural numbers…
	Anonymous on A computation-outsourced discu…
	Anonymous on Dense sets of natural numbers…
	Anonymous on 245A, Notes 3: Integration on…
	Samuel German on Analysis I

Tag Archive

Erratum for “An inverse theorem for the Gowers U^{s+1}[N]-norm”

Notes on inverse theorem entropy

The Gowers uniformity norm of order 1+

Quantitative bounds for Gowers uniformity of the Mobius and von Mangoldt functions

A correction to “An arithmetic regularity lemma, an associated counting lemma, and applications”

Higher uniformity of bounded multiplicative functions in short intervals on average

Cut norms and degree lowering

Concatenation theorems for anti-Gowers-uniform functions and Host-Kra characteristic factors; polynomial patterns in primes

Deducing the inverse theorem for the multidimensional Gowers norms from the one-dimensional version

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

For commenters