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

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.

25 comments

Comments feed for this article

25 July, 2021 at 6:04 pm

Freddie Manners

Is it possible to state precisely, in terms of this $U^{1^+}$ norm, what “true complexity” bound would suffice to generalize results of Peluse and Prendiville to general polynomial patterns of true complexity $0^+$ ? They make some statements in their papers but I have not fully translated between those and these more concise $U^{1+}$ statements.

There seemed to be some subtlety about whether you have $U^{1^+}$ control in one position or all positions, which determines whether you can get $\log^c$ or $\log \log^c$ , but I could be wrong about that.

25 July, 2021 at 8:11 pm

Terence Tao

I think in the notation of this blog post, the two papers of Peluse and Prendiville show bounds of the form

$\displaystyle \Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}, \mathrm{n}+\mathrm{r}^2}(f,g,h) \ll \min( \| f \|_{U^{1^+}_{\sqrt{N}}[N]}, \| g \|_{U^{1^+}_{\sqrt{N}}[N]}, \| h \|_{U^{1^+}[N]})^c$

for $1$ -bounded $f,g,h$ , where the subscript here denotes a local version of the $U^{1^+}$ norm,

$\displaystyle \|f\|_{U^{1^+}_{\sqrt{N}}[N]} = {\bf E}_{n_0 \in [N]} \sup_{P} |{\bf E}_{n \in [n_0,n_0+\sqrt{N}]} f 1_P(n)|.$

This localisation is necessary because of the scenario in which $f,g$ are locally constant at scale $\sqrt{N}$ at which point the form $\Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}, \mathrm{n}+\mathrm{r}^2}(f,g,h)$ basically collapses to $\Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}^2}(fg,h)$ and one can no longer exploit any further uniformity of the individual functions $f,g$ .

I have heard from Sarah that analogous results are now known for any average involving polynomials of distinct degree, but this work might not be publicly available yet. I’m not sure what the situation is for the polynomial patterns that are suspected to be of complexity $0^+$ but do not have distinct degrees.

25 July, 2021 at 10:53 pm

Frederick Manners

I see, thanks — that’s what’s meant above about the first two indices being different and having at best local norm control.

I think my confusion was more about the stage of the argument where you take certain $U^{1^+}$ -control statements as a black box, and try to deduce the corresponding instance of the polynomial Szemerédi theorem for these configurations, with as good a bound as possible.

For illustration take $\Lambda^{n,n+r,n+r^2,n+r^3}$ . Reading a bit more of the relevant papers, I think the following are true statements in your language above:–

1. the bound

$\displaystyle \lvert \Lambda^{n,n+r,n+r^2,n+r^3}(f_0,f_1,f_2,f_3) \rvert \ll \|f_1\|_{U^{1^+}_{N^{1/3}}}^c$

is known, by [Peluse, “Bounds for sets with no polynomial progressions”], and as a black box this inequality enough to deduce polynomial Szemerédi for $(n,n+r,n+r^2,n+r^3)$ for densities $\log \log^c$ (by vanilla density increment);

2. the comments in [“A polylogarithmic bound in the non-linear Roth theorem”, Section 7] seem to suggest that if we knew

$\displaystyle \lvert \Lambda^{n,n+r,n+r^2,n+r^3}(f_0,f_1,f_2,f_3) \rvert \ll \min \left( \|f_0\|_{U^{1^+}_{N^{1/3}}}, \|f_1\|_{U^{1^+}_{N^{1/3}}}, \|f_2\|_{U^{1^+}_{N^{2/3}}}, \|f_3\|_{U^{1^+}} \right)^c$

then we could feed that into the more powerful “multiplicative gain” density increment machine, essentially as a black box, to get a $\log^c$ bound (not currently known in the published literature).

I’m not 100% sure this summary is accurate; hopefully I can be corrected if not.

It is a little surprising in this picture (if correct) that you could get control over one $f_i$ but not the others, so either I’ve misunderstood, or it is a (plausible) quirk of the proofs that the lowest-degree polynomial is somehow special. I guess it seems this issue has been resolved in unpublished work and the better bound is now known.

26 July, 2021 at 6:47 am

Terence Tao

One probably needs to talk to Sarah or Sean for the most up to date status of this problem, but it is certainly easier to use the global $U^{1^+}$ norm for density increment purposes with polylogarithmic bounds than the local one if it is available to control the multilinear form, and in the case of say $n,n+r,n+r^2,n+r^3$ it is only the fourth function $f_3$ that has any hope of being controlled by the global norm, for the geometric reason that $n+r^3$ is the only element of this quadruple that is very well separated (distance $\sim N$ ) from the rest of the quadruple for typical values of $r$ . But it seems with Sarah and Sean’s approach that $f_3$ is the hardest function to get their estimates for; they initially only get to control the form in terms of $f_0,f_1$ and then struggle to move up to $f_2$ and then to $f_3$ . But once they get control by the global norm of $f_3$ I would imagine that their multiplicative-gain density increment approach would work, at least for the first increment, though for subsequent increments one may need to keep careful track of how the coefficients of the (renormalised) polynomials are growing.

27 July, 2021 at 4:10 am

Sean Prendiville

Personally, I am confident that the argument sketched in §7.1 of https://arxiv.org/abs/2003.04122 should yield control of all functions (and hence poly-logarithmic bounds) for distinct-degree progressions.

In order to implement the strategy sketched, it seems like one cannot use Sarah’s very general results (https://arxiv.org/abs/1909.00309) as a black box, and must re-run her arguments with mildly more general hypotheses (although we did not think too hard about bootstrapping her results to give the more general statements required). I could be entirely mistaken, but the obstructions appear to be only technical (albeit lengthy). Sarah or others may have since thought more about this.

25 July, 2021 at 7:00 pm

Vivian

Thank you, Professor Tao

Sent from my iPhone

26 July, 2021 at 6:17 am

Mark

Can you explain how does

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

implies

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

26 July, 2021 at 6:48 am

Terence Tao

This follows from $L^1$ estimates on $|1_I - 1_I * \psi_\delta|$ and the triangle inequality (the errors picked up are of size $O(\delta)$ and can be absorbed into the right-hand side by letting $\delta$ be a sufficiently small multiple of $\eta$ ). The $L^1$ estimate follows in turn from the decay and unit mass properties of $\psi_\delta$ .

26 July, 2021 at 7:06 am

Lillian

Could you please give a brief explanation for the inequality

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

It looks plausible, but I can’t quite convince myself it is correct. For example, I don’t really see where does $+\delta$ on the RHS come from?

[Fixed some typos and added further explanation -T.]

26 July, 2021 at 9:05 am

yasmin

Dear Prof Tao,
I have two questions:
“The Fourier transform of {1_I * \psi_\delta} is bounded and supported on {[-1/\delta,1/\delta]}”
– What is the normalisation here? Isn’t $(1_I * \psi_\delta)^\hat (0) = (1_I)\hat (0) (\psi_\delta)^ (0) = |I| \sim N$ which is unbounded?

“{\alpha = \frac{a}{q} + O(1/\eta)}”
– Isn’t the O-term here larger than the main term (a/q)?

[Fixed some typos and added further explanation -T.]

26 July, 2021 at 9:46 am

John Griesmer

It may be worth mentioning that the true complexity of $(n, n+r, n+r^2)$ for ergodic averages was determined by Furstenberg and Weiss [FW96], and for polynomial expressions of the form $(n, n+p(r), n+q(r), n + s(r))$ by Frantzikinakis (arxiv:0606567).

27 July, 2021 at 2:07 pm

Anonymous

Could you post your last Friday’s lecture slides on HIM website? You skipped many slides, and would be helpful for students who are new to the subject.

[Slides are now posted – T.]

28 July, 2021 at 5:59 am

Ryan Norris

When you do the Fourier expansion of psi(h/delta N) (I assume you are thinking of it as function in integer variable h) to obtain coefficient beta, don’t you need an L^1 upper bound of quality O(1) for its Fourier transform to get the desired conclusion? It’s support is [0,1], but the largest value (coming from zeroth coefficient) is delta*N, which doesn’t seem to be good enough. Or did I mess up the normalisation somewhere?

[Because of the rapid decay of the Fourier transform of $\psi$ , the Fourier transform of $\psi(h/\delta N)$ is effectively localised to an interval of length $O(1/\delta N)$ . -T]

28 July, 2021 at 1:03 pm

Lior Silberman

Trivial typo, but in the definition of the multilinear form in the displayed equation after (1), the $f$ on the RHS should be an $f_j$ .

[Corrected, thanks – T.]

28 July, 2021 at 7:13 pm

Will Sawin

For which class of forms does it make sense to define the complexity? I think Gowers and Wolf defined it only for multilinear forms arising from systems of linear equations, which wouldn’t include the Peluse-Prendiville example (or other examples arising in the work of Peluse and Peluse-Prendiville).

I am worried about the following phenomenon: Suppose we have a multilinear form which is controlled very nicely by a norm which is easy to work with, but happens to not be a Gowers norm. Should we really then say it has complexity infinity?

I was also a bit concerned with whether, if we prove a multilinear form is controlled by a simple norm using a complicated inductive process that passes through the first 10 Gowers norm, it is reasonable to say the problem is complexity 0 just because the final statement doesn’t involve any Gowers norms, but I can’t really complain because a version of this occurs already in the paper of Gowers and Wolf.

I guess one would like to have a heuristic conjecture along the lines of “If this multilinear form is controlled by any nice norm, then it is controlled by some Gowers norm”. Is it reasonable to believe this for translation-invariant multilinear forms, say, which would include the progressions and Peluse-Prendiville examples?

28 July, 2021 at 9:39 pm

Freddie Manners

“I guess one would like to have a heuristic conjecture along the lines of “If this multilinear form is controlled by any nice norm, then it is controlled by some Gowers norm”.”

It is almost certainly hard to formulate such a conjecture correctly, but I think it should be true-ish in some settings once you eliminate ways in which it is not true.

For instance, I think the case of polynomial multilinear averages over finite fields should be fairly solid. That is, given polynomials $P_i : \mathbb{F}_p^d \to \mathbb{F}_p$ , averages

$\displaystyle E_{v_1,\dots,v_d \in F_p^{n}} f_1(P_1(v_1,\dots,v_d)) \dots f_k(P_k(v_1,\dots,v_d))$

should be controlled by a norm $U^{s+1}$ for some “complexity” s depending on the polynomials, such that if it is controlled by any other norm, that norm control is, in some very vague sense, a weaker statement than $U^{s+1}$ control.

(In “vague” I include things such as UAP norms or generalized-convolution-cut-norms, which are loosely but not actually equivalent to Gowers norms.)

The point is that you can consider which 1-bounded functions in your norm have $\|f\| = 1$ . For Gowers norms, these will be phase polynomials $f(x) = \exp(2 \pi i P(x))$ for $P$ a polynomial of degree $s$ . Because there is no such thing as a polynomial of degree 1.5, and because extremal functions of polynomial multilinear averages are also basically phase polynomials, and for other reasons, I’m willing to guess that the Gowers norm hierarchy is the full story, as per your heuristic conjecture.

Certainly one case where things get more complicated is when you allow “functions in more than one variable”. For example, consider the multilinear average

$\displaystyle E_{x,y,z,w \in \mathbb{F}_p^n} A(x,y) B(x,z) C(w,y) D(w,z).$

(Feel free to disguise this in terms of multilinear forms by adding spurious plus signs.)

This is controlled by the Schatten-4 norm, or basically any other spectral norm, but the Schatten-4 norm is of interest because it “looks like” a Gowers norm. However, it is certainly meaningful to say that this has true complexity infinity because it fails to be controlled by any true Gowers norm on $\displaystyle \mathbb{F}_p^{2n}$ . But Schatten-4 control is clearly better than nothing. Maybe this realizes your concern.

In general you will have a raft of different possible norm controls, often incomparable, based on what their 100% functions look like (e.g., things like “all at most quadratic functions $\displaystyle F(x,y,z)$ ” and “all at most trilinear functions $\displaystyle F(x,y,z)$ ” can all be assigned norms). But they should still be *coarsely* classified by degree: in other words, such norms should always fit between two consecutive Gowers norms, or fall off one end of the list. I think that coarse measure is what should be understood by complexity in this generality, while understanding that it is not the full story.

For polynomial forms in one variable over the integers, you certainly need to include “local” Gowers norms, where certain parameters are constrained to have local sizes, as Terry points out above. I don’t know how fine the hierarchy of such local norms is: it seems plausible that you can mimic the difficulties arising for functions in several variables by using different scales as if they were different variables, but I have not thought hard about this.

Not sure if that answers any of your questions satisfactorily.

31 July, 2021 at 10:28 am

Terence Tao

I agree with basically everything Freddie said. In general one would expect the notion of complexity to take values in some weird partially ordered set, where some norms control others but there is no obvious reason why there should be a total ordering. But in the case of one-dimensional averages at a given spatial scale there does seem to be this remarkable phenomenon that there is this one-dimensional hierarchy of Gowers norms $U^{s+1}$ that control everything (after belatedly adding this final norm $U^{1+}$ to the hierarchy). For instance, the “ $u^3$ norm” that comes from taking the maximal inner product of $f$ against a globally quadratic phase (as opposed to a locally quadratic phase) is intermediate in strength between the $U^2$ and $U^3$ norms (as depicted on the diagram in the blog post, where it is labeled $\mathrm{quad.}^*$ ), but does not seem to be associated as the true complexity of any polynomial average, as far as I know; any average that is sensitive to globally quadratic phases is automatically also sensitive to locally quadratic phases (or degree 2 nilsequences, or bracket quadratic phases) and thus is really controlled by $U^3$ rather than $u^3$ . As such the $u^3$ norm plays only a very minor role in additive combinatorics.

It reminds me a bit of the phenomenon in reverse mathematics, where one would a priori expect a hugely complicated partially ordered set of theories of arithmetic where various theorems in analysis (Bolzano-Weierstrass, Heine-Borel, etc.) naturally live, but instead one ends up with a “big five” of arithmetic theories ( $RCA_0$ , $WKL_0$ , etc.) which are basically the “complexity” for the vast majority of such theorems.

The situation is currently understood the best in the ergodic theory setting, where the analogue of the notion of complexity is known as the “characteristic factor” – the maximal factor $Z$ of a given system $X$ in which all functions $f \in L^\infty(X)$ orthogonal to $L^2(Z)$ (or equivalently, all functions $f \in L^\infty(X)$ with vanishing conditional expectation ${\bf E}(f|Z)$ are negligible for a given ergodic average. For any given multiple polynomial average we now know that the characteristic factor is always one of the Host-Kra factors $Z^s(X)$ , or the profinite factor $Z^{0+}(X)$ (modulo some minor technicalities at small primes where there is “ramification”), though the proof proceeds by first controlling things by some Host-Kra seminorm $\| \|_{U^{s+1}}$ (the analogue of the Gowers norm in the ergodic setting) of enormous degree and then whittling down the degree. Perhaps as the degree-lowering theory matures we will have a better understanding of where true complexity actually comes from and why the Gowers uniformity hierarchy is pretty much all that shows up, but the phenomenon still only partially understood at present.

As discussed in other comments, the situation seems to be markedly different in the setting of polynomial averages over finite fields, where there are many more algebraic obstructions in play.

31 July, 2021 at 11:04 am

John Griesmer

There are polynomial averages whose characteristic factor is strictly between $Z^{1}$ and $Z^{2}$ (and therefore is not one of the $Z^s$ or $Z^{0+}$ ): Theorem B of Frantzikinakis’s three polynomials paper shows that the characteristic factor for $\frac{1}{N}\sum_{n=1}^N f\circ T^n\cdot f\circ T^{2n}\cdot f\circ T^{n^2}$ is the maximal 2 step affine factor of $X$ , which is (often) strictly between $Z^1(X)$ and $Z^2(X)$ .

31 July, 2021 at 12:17 pm

Terence Tao

Huh, I was not aware of this very interesting example! On the algebraic side it seems to boil down to the identity

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

for real $\alpha$ which shows that globally quadratic phases are non-negligible for this average, but there isn’t an analogous identity (or near-identity) for locally quadratic functions. So perhaps on the combinatorial side the average $\Lambda^{n,n+r, n+2r, n+r^2}$ is in fact controlled by the $u^3$ norm and not just the $U^3$ norm (and not by the $U^2$ norm), which would be the first example of a “complexity 1.5 pattern” that I am aware of. I stand corrected!

EDIT: a concrete conjecture in this regard would be that

$\displaystyle \Lambda^{n,n+r,n+2r,n+r^2}(f,g,h,k) \ll \min( \|f\|_{u^3_{\sqrt{N}}}, \|g\|_{u^3_{\sqrt{N}}}, \|h\|_{u^3_{\sqrt{N}}}, \|k\|_{U^2} )^c$

for some $c>0$ and all $1$ -bounded $f,g,h,k$ , with the obvious definitions for the local norm $u^3_{\sqrt{N}}$ . There does seem to some chance that the degree lowering machinery could stretch to cover this case without needing to touch the inverse $U^3$ theorem which currently does not enjoy polynoimal bounds.

3 August, 2021 at 4:44 pm

Will Sawin

If we look at the average $\Lambda^{n-r, n, n+r, n+r^2, n+r^4}$ then the identity $(n-r)^3 - 2 n^3 + 3 n^2 -3n + (n+r)^3 - 3 (n+r^2)^2 + 3 (n+r^4) = 0$ appears, showing that a cubic phase in any of the first three variables is not negligible.

Are locally quadratic phases non-negligible for these functions? I don’t see why they would be, since they don’t have any special structure when polynomials are multiplied and thus they should only see the three linearly dependent terms $n-r, n ,n+r$ , where we know only additive phases contribute.

So maybe the norm relevant for this example is strictly incomparable with the $U^3$ norm?

28 July, 2021 at 10:25 pm

Freddie Manners

Actually I guess parts of this are not as mysterious as I’m trying to make it. You are essentially asking for a converse to Gowers–Wolf: for (say) a system of linear forms of complexity $s$ at index $1$ , show that for all $\varepsilon>0$ there exists $\delta>0$ such that if $\|f\|_{U^{s+1}} > \varepsilon$ then there exist 1-bounded functions $g_2,\dots,g_k$ such that

$\displaystyle |\Lambda_{\Phi}(f, g_2,\dots,g_k)| > \delta.$

The point is that $\Lambda_{\Phi}$ is vacuously and optimally controlled by the “ $\Phi$ cut-norm”, namely the supremum of the left-hand side over all 1-bounded functions $g_i$ . Gowers–Wolf asserts that this cut-norm is bounded above (in a very weak sense) by $U^{s+1}$ for a suitably chosen $s$ ; this would imply the two norms are equivalent (in a very weak sense).

For systems of linear forms, or polynomial forms over finite fields, I would be fairly confident this is true, but am also confident it is not known. For polynomial forms over the integers, I have no idea what to expect.

29 July, 2021 at 5:44 am

Will Sawin

I think this is not true as you state for polynomial forms over finite fields.

For one, we could have $P_i (v_1,v_2) = v_i v_2^{i-1}$ in which case we need to use the multiplicative group Gowers norm and not the additive group Gowers norm. Probably one can even get elliptic Gowers norms to show up as well.

You could say “well, those are all really different types of Gowers norms even if they’re not literally part of the same sequence of norms” but then you could have each $P_i$ of the form $Q_i^3 - Q_i$ for other polynomials $Q_i$ and then you would need to know about the average value of your $f_i$ s against the number of ways of representing them as $x^3 - x$ , which is not periodic additively or multiplicatively.

There’s a lot of norms you could potentially need to get the full picture.

29 July, 2021 at 6:53 am

Freddie Manners

Of course you are right — I had not considered things like geometric progressions or even more badly-behaved examples. Was the point in your original post that adding “translation-invariant” is a good way to kill these off and fall back into the safe ergodic-theoretic world I probably imagined I lived in?

I think a number of my comments above could wind up being technically correct as stated if I simply bundle all these examples in as “infinite complexity”, but I guess that’s exactly the thing you objected to in the first place.

I think it is a consistent if unambitious world-view to say that “complexity” really means “degree complexity”, and has to do with cases whether the 100% solutions are necessarily phase polynomials of bounded degree; and if not, the “degree complexity” is infinite and you are on your own.

Certainly given your examples, I don’t know how to tell whether a system of polynomial forms has finite degree complexity just by looking at it, and that seems like a very natural question I would like to know the answer to.

29 July, 2021 at 8:14 am

Will Sawin

I’m not sure if translation-invariant is a good way to kill off all of these, though I suspect it might be. I asked because I thought someone else might know.

For systems of polynomial forms, or, slightly differently, systems of polynomial equations, I a while ago had an idea (inspired by some stuff Jacob Tsimerman told me) of using Galois theory to classify what kind of norms you should need for a given system, based on the theory that the worst-behaved functions for a given system of forms should be characteristic functions of sets of points with a fixed splitting behavior in a Galois cover of the line. But even proving the purely Galois-theoretic statements needed for this idea to make sense proved tricky, let alone making it actually interface with the combinatorics.

29 August, 2022 at 5:03 pm

Quân Nguyễn

Dear prof Tao,
I’ve attempted to prove but don’t know if the following identity is actually true:

$\displaystyle \|f\|_{U^k([N])} \asymp (N \int_{\mathbf R \setminus \mathbf Z} |\mathop{\bf E}_{n \in [N]} f(n) e(-\alpha n)|^{2^k}\ d\alpha)^{2^{-k}}$

[This is only true for $k=2$ – T.]

	Yingyuan Li on Analysis II
	Anonymous on Analysis II
	Anonymous on Analysis II
	Yingyuan Li on Analysis II
	Yingyuan Li on Analysis II
	Yingyuan Li on Analysis II
	Yingyuan Li on Analysis II
	Jamie on On writing
	Anonymous on On writing
	Terence Tao on PCAST Working Group on Generat…
	Yingyuan Li on Analysis II
	Sam on 245A, Notes 5: Differentiation…
	Johan Aspegren on PCAST Working Group on Generat…
	Sam on 245A, Notes 5: Differentiation…
	wbshu on 247B, Notes 1: Restriction…

The Gowers uniformity norm of order 1+

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

25 comments

Leave a Reply Cancel reply

For commenters

The Gowers uniformity norm of order 1+

Share this:

Like this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

25 comments

Leave a Reply Cancel reply

For commenters