Tag Archive

You are currently browsing the tag archive for the ‘Tamar Ziegler’ 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.

Infinite partial sumsets in the primes

26 January, 2023 in math.NT, paper | Tags: Maynard sieve, prime tuples conjecture, Tamar Ziegler | by Terence Tao | 45 comments

Tamar Ziegler and I have just uploaded to the arXiv our paper “Infinite partial sumsets in the primes“. This is a short paper inspired by a recent result of Kra, Moreira, Richter, and Robertson (discussed for instance in this Quanta article from last December) showing that for any set ${A}$ of natural numbers of positive upper density, there exists a sequence ${b_1 < b_2 < b_3 < \dots}$ of natural numbers and a shift ${t}$ such that ${b_i + b_j + t \in A}$ for all ${i<j}$ this answers a question of Erdős). In view of the “transference principle“, it is then plausible to ask whether the same result holds if ${A}$ is replaced by the primes. We can show the following results:

Theorem 1

(i) If the Hardy-Littlewood prime tuples conjecture (or the weaker conjecture of Dickson) is true, then there exists an increasing sequence ${b_1 < b_2 < b_3 < \dots}$ of primes such that ${b_i + b_j + 1}$ is prime for all ${i < j}$ .
(ii) Unconditionally, there exist increasing sequences ${a_1 < a_2 < \dots}$ and ${b_1 < b_2 < \dots}$ of natural numbers such that ${a_i + b_j}$ is prime for all ${i<j}$ .
(iii) These conclusions fail if “prime” is replaced by “positive (relative) density subset of the primes” (even if the density is equal to 1).

We remark that it was shown by Balog that there (unconditionally) exist arbitrarily long but finite sequences ${b_1 < \dots < b_k}$ of primes such that ${b_i + b_j + 1}$ is prime for all ${i < j \leq k}$ . (This result can also be recovered from the later results of Ben Green, myself, and Tamar Ziegler.) Also, it had previously been shown by Granville that on the Hardy-Littlewood prime tuples conjecture, there existed increasing sequences ${a_1 < a_2 < \dots}$ and ${b_1 < b_2 < \dots}$ of natural numbers such that ${a_i+b_j}$ is prime for all ${i,j}$ .

The conclusion of (i) is stronger than that of (ii) (which is of course consistent with the former being conditional and the latter unconditional). The conclusion (ii) also implies the well-known theorem of Maynard that for any given ${k}$ , there exist infinitely many ${k}$ -tuples of primes of bounded diameter, and indeed our proof of (ii) uses the same “Maynard sieve” that powers the proof of that theorem (though we use a formulation of that sieve closer to that in this blog post of mine). Indeed, the failure of (iii) basically arises from the failure of Maynard’s theorem for dense subsets of primes, simply by removing those clusters of primes that are unusually closely spaced.

Our proof of (i) was initially inspired by the topological dynamics methods used by Kra, Moreira, Richter, and Robertson, but we managed to condense it to a purely elementary argument (taking up only half a page) that makes no reference to topological dynamics and builds up the sequence ${b_1 < b_2 < \dots}$ recursively by repeated application of the prime tuples conjecture.

The proof of (ii) takes up the majority of the paper. It is easiest to phrase the argument in terms of “prime-producing tuples” – tuples ${(h_1,\dots,h_k)}$ for which there are infinitely many ${n}$ with ${n+h_1,\dots,n+h_k}$ all prime. Maynard’s theorem is equivalent to the existence of arbitrarily long prime-producing tuples; our theorem is equivalent to the stronger assertion that there exist an infinite sequence ${h_1 < h_2 < \dots}$ such that every initial segment ${(h_1,\dots,h_k)}$ is prime-producing. The main new tool for achieving this is the following cute measure-theoretic lemma of Bergelson:

Lemma 2 (Bergelson intersectivity lemma) Let ${E_1,E_2,\dots}$ be subsets of a probability space ${(X,\mu)}$ of measure uniformly bounded away from zero, thus ${\inf_i \mu(E_i) > 0}$ . Then there exists a subsequence ${E_{i_1}, E_{i_2}, \dots}$ such that
$\displaystyle \mu(E_{i_1} \cap \dots \cap E_{i_k} ) > 0$
for all ${k}$ .

This lemma has a short proof, though not an entirely obvious one. Firstly, by deleting a null set from ${X}$ , one can assume that all finite intersections ${E_{i_1} \cap \dots \cap E_{i_k}}$ are either positive measure or empty. Secondly, a routine application of Fatou’s lemma shows that the maximal function ${\limsup_N \frac{1}{N} \sum_{i=1}^N 1_{E_i}}$ has a positive integral, hence must be positive at some point ${x_0}$ . Thus there is a subsequence ${E_{i_1}, E_{i_2}, \dots}$ whose finite intersections all contain ${x_0}$ , thus have positive measure as desired by the previous reduction.

It turns out that one cannot quite combine the standard Maynard sieve with the intersectivity lemma because the events ${E_i}$ that show up (which roughly correspond to the event that ${n + h_i}$ is prime for some random number ${n}$ (with a well-chosen probability distribution) and some shift ${h_i}$ ) have their probability going to zero, rather than being uniformly bounded from below. To get around this, we borrow an idea from a paper of Banks, Freiberg, and Maynard, and group the shifts ${h_i}$ into various clusters ${h_{i,1},\dots,h_{i,J_1}}$ , chosen in such a way that the probability that at least one of ${n+h_{i,1},\dots,n+h_{i,J_1}}$ is prime is bounded uniformly from below. One then applies the Bergelson intersectivity lemma to those events and uses many applications of the pigeonhole principle to conclude.

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.

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.

An inverse theorem for the continuous Gowers uniformity norm

22 July, 2015 in expository, math.CO, math.DS | Tags: Ben Green, Gowers uniformity norms, inverse conjecture, regularity lemma, Tamar Ziegler | by Terence Tao | 3 comments

A few years ago, Ben Green, Tamar Ziegler, and myself proved the following (rather technical-looking) inverse theorem for the Gowers norms:

Theorem 1 (Discrete 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}} \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.$

For the definitions of “filtered nilmanifold”, “degree”, “complexity”, and “polynomial sequence”, see the paper of Ben, Tammy, and myself. (I should caution the reader that this blog post will presume a fair amount of familiarity with this subfield of additive combinatorics.) This result has a number of applications, for instance to establishing asymptotics for linear equations in the primes, but this will not be the focus of discussion here.

The purpose of this post is to record the observation that this “discrete” inverse theorem, together with an equidistribution theorem for nilsequences that Ben and I worked out in a separate paper, implies a continuous version:

Theorem 2 (Continuous inverse theorem for Gowers norms) Let ${s \geq 1}$ be an integer, and let ${\delta>0}$ . Suppose that ${f: {\bf R} \rightarrow [-1,1]}$ is a measurable function supported on ${[0,1]}$ such that

$\displaystyle \int_{{\bf R}^{s+1}} \prod_{\omega \in \{0,1\}^{s+1}} f(t+\omega_1 h_1 + \dots + \omega_{s+1} h_{s+1})\ dt dh_1 \dots dh_{s+1} \geq \delta. \ \ \ \ \ (1)$

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

$\displaystyle \int_{\bf R} f(t) F(g(t) \Gamma)\ dt \gg_{s,\delta} 1.$

The interval ${[0,1]}$ can be easily replaced with any other fixed interval by a change of variables. A key point here is that the bounds are completely uniform in the choice of ${f}$ . Note though that the coefficients of ${g}$ can be arbitrarily large (and this is necessary, as can be seen just by considering functions of the form ${f(t) = \cos( \xi t)}$ for some arbitrarily large frequency ${\xi}$ ).

It is likely that one could prove Theorem 2 by carefully going through the proof of Theorem 1 and replacing all instances of ${{\bf Z}}$ with ${{\bf R}}$ (and making appropriate modifications to the argument to accommodate this). However, the proof of Theorem 1 is quite lengthy. Here, we shall proceed by the usual limiting process of viewing the continuous interval ${[0,1]}$ as a limit of the discrete interval ${\frac{1}{N} \cdot [N]}$ as ${N \rightarrow \infty}$ . However there will be some problems taking the limit due to a failure of compactness, and specifically with regards to the coefficients of the polynomial sequence ${g: {\bf N} \rightarrow G}$ produced by Theorem 1, after normalising these coefficients by ${N}$ . Fortunately, a factorisation theorem from a paper of Ben Green and myself resolves this problem by splitting ${g}$ into a “smooth” part which does enjoy good compactness properties, as well as “totally equidistributed” and “periodic” parts which can be eliminated using the measurability (and thus, approximate smoothness), of ${f}$ .

Read the rest of this entry »

Narrow progressions in the primes

4 September, 2014 in math.NT, paper | Tags: densification, Tamar Ziegler | by Terence Tao | 11 comments

Tamar Ziegler and I have just uploaded to the arXiv our paper “Narrow progressions in the primes“, submitted to the special issue “Analytic Number Theory” in honor of the 60th birthday of Helmut Maier. The results here are vaguely reminiscent of the recent progress on bounded gaps in the primes, but use different methods.

About a decade ago, Ben Green and I showed that the primes contained arbitrarily long arithmetic progressions: given any ${k}$ , one could find a progression ${n, n+r, \dots, n+(k-1)r}$ with ${r>0}$ consisting entirely of primes. In fact we showed the same statement was true if the primes were replaced by any subset of the primes of positive relative density.

A little while later, Tamar Ziegler and I obtained the following generalisation: given any ${k}$ and any polynomials ${P_1,\dots,P_k: {\bf Z} \rightarrow {\bf Z}}$ with ${P_1(0)=\dots=P_k(0)}$ , one could find a “polynomial progression” ${n+P_1(r),\dots,n+P_k(r)}$ with ${r>0}$ consisting entirely of primes. Furthermore, we could make this progression somewhat “narrow” by taking ${r = n^{o(1)}}$ (where ${o(1)}$ denotes a quantity that goes to zero as ${n}$ goes to infinity). Again, the same statement also applies if the primes were replaced by a subset of positive relative density. My previous result with Ben corresponds to the linear case ${P_i(r) = (i-1)r}$ .

In this paper we were able to make the progressions a bit narrower still: given any ${k}$ and any polynomials ${P_1,\dots,P_k: {\bf Z} \rightarrow {\bf Z}}$ with ${P_1(0)=\dots=P_k(0)}$ , one could find a “polynomial progression” ${n+P_1(r),\dots,n+P_k(r)}$ with ${r>0}$ consisting entirely of primes, and such that ${r \leq \log^L n}$ , where ${L}$ depends only on ${k}$ and ${P_1,\dots,P_k}$ (in fact it depends only on ${k}$ and the degrees of ${P_1,\dots,P_k}$ ). The result is still true if the primes are replaced by a subset of positive density ${\delta}$ , but unfortunately in our arguments we must then let ${L}$ depend on ${\delta}$ . However, in the linear case ${P_i(r) = (i-1)r}$ , we were able to make ${L}$ independent of ${\delta}$ (although it is still somewhat large, of the order of ${k 2^k}$ ).

The polylogarithmic factor is somewhat necessary: using an upper bound sieve, one can easily construct a subset of the primes of density, say, ${90\%}$ , whose arithmetic progressions ${n,n+r,\dots,n+(k-1)r}$ of length ${k}$ all obey the lower bound ${r \gg \log^{k-1} n}$ . On the other hand, the prime tuples conjecture predicts that if one works with the actual primes rather than dense subsets of the primes, then one should have infinitely many length ${k}$ arithmetic progressions of bounded width for any fixed ${k}$ . The ${k=2}$ case of this is precisely the celebrated theorem of Yitang Zhang that was the focus of the recently concluded Polymath8 project here. The higher ${k}$ case is conjecturally true, but appears to be out of reach of known methods. (Using the multidimensional Selberg sieve of Maynard, one can get ${m}$ primes inside an interval of length ${O( \exp(O(m)) )}$ , but this is such a sparse set of primes that one would not expect to find even a progression of length three within such an interval.)

The argument in the previous paper was unable to obtain a polylogarithmic bound on the width of the progressions, due to the reliance on a certain technical “correlation condition” on a certain Selberg sieve weight ${\nu}$ . This correlation condition required one to control arbitrarily long correlations of ${\nu}$ , which was not compatible with a bounded value of ${L}$ (particularly if one wanted to keep ${L}$ independent of ${\delta}$ ).

However, thanks to recent advances in this area by Conlon, Fox, and Zhao (who introduced a very nice “densification” technique), it is now possible (in principle, at least) to delete this correlation condition from the arguments. Conlon-Fox-Zhao did this for my original theorem with Ben; and in the current paper we apply the densification method to our previous argument to similarly remove the correlation condition. This method does not fully eliminate the need to control arbitrarily long correlations, but allows most of the factors in such a long correlation to be bounded, rather than merely controlled by an unbounded weight such as ${\nu}$ . This turns out to be significantly easier to control, although in the non-linear case we still unfortunately had to make ${L}$ large compared to ${\delta}$ due to a certain “clearing denominators” step arising from the complicated nature of the Gowers-type uniformity norms that we were using to control polynomial averages. We believe though that this an artefact of our method, and one should be able to prove our theorem with an ${L}$ that is uniform in ${\delta}$ .

Here is a simple instance of the densification trick in action. Suppose that one wishes to establish an estimate of the form

$\displaystyle {\bf E}_n {\bf E}_r f(n) g(n+r) h(n+r^2) = o(1) \ \ \ \ \ (1)$

for some real-valued functions ${f,g,h}$ which are bounded in magnitude by a weight function ${\nu}$ , but which are not expected to be bounded; this average will naturally arise when trying to locate the pattern ${(n,n+r,n+r^2)}$ in a set such as the primes. Here I will be vague as to exactly what range the parameters ${n,r}$ are being averaged over. Suppose that the factor ${g}$ (say) has enough uniformity that one can already show a smallness bound

$\displaystyle {\bf E}_n {\bf E}_r F(n) g(n+r) H(n+r^2) = o(1) \ \ \ \ \ (2)$

whenever ${F, H}$ are bounded functions. (One should think of ${F,H}$ as being like the indicator functions of “dense” sets, in contrast to ${f,h}$ which are like the normalised indicator functions of “sparse” sets). The bound (2) cannot be directly applied to control (1) because of the unbounded (or “sparse”) nature of ${f}$ and ${h}$ . However one can “densify” ${f}$ and ${h}$ as follows. Since ${f}$ is bounded in magnitude by ${\nu}$ , we can bound the left-hand side of (1) as

$\displaystyle {\bf E}_n \nu(n) | {\bf E}_r g(n+r) h(n+r^2) |.$

The weight function ${\nu}$ will be normalised so that ${{\bf E}_n \nu(n) = O(1)}$ , so by the Cauchy-Schwarz inequality it suffices to show that

$\displaystyle {\bf E}_n \nu(n) | {\bf E}_r g(n+r) h(n+r^2) |^2 = o(1).$

The left-hand side expands as

$\displaystyle {\bf E}_n {\bf E}_r {\bf E}_s \nu(n) g(n+r) h(n+r^2) g(n+s) h(n+s^2).$

Now, it turns out that after an enormous (but finite) number of applications of the Cauchy-Schwarz inequality to steadily eliminate the ${g,h}$ factors, as well as a certain “polynomial forms condition” hypothesis on ${\nu}$ , one can show that

$\displaystyle {\bf E}_n {\bf E}_r {\bf E}_s (\nu-1)(n) g(n+r) h(n+r^2) g(n+s) h(n+s^2) = o(1).$

(Because of the polynomial shifts, this requires a method known as “PET induction”, but let me skip over this point here.) In view of this estimate, we now just need to show that

$\displaystyle {\bf E}_n {\bf E}_r {\bf E}_s g(n+r) h(n+r^2) g(n+s) h(n+s^2) = o(1).$

Now we can reverse the previous steps. First, we collapse back to

$\displaystyle {\bf E}_n | {\bf E}_r g(n+r) h(n+r^2) |^2 = o(1).$

One can bound ${|{\bf E}_r g(n+r) h(n+r^2)|}$ by ${{\bf E}_r \nu(n+r) \nu(n+r^2)}$ , which can be shown to be “bounded on average” in a suitable sense (e.g. bounded ${L^4}$ norm) via the aforementioned polynomial forms condition. Because of this and the Hölder inequality, the above estimate is equivalent to

$\displaystyle {\bf E}_n | {\bf E}_r g(n+r) h(n+r^2) | = o(1).$

By setting ${F}$ to be the signum of ${{\bf E}_r g(n+r) h(n+r^2)}$ , this is equivalent to

$\displaystyle {\bf E}_n {\bf E}_r F(n) g(n+r) h(n+r^2) = o(1).$

This is halfway between (1) and (2); the sparsely supported function ${f}$ has been replaced by its “densification” ${F}$ , but we have not yet densified ${h}$ to ${H}$ . However, one can shift ${n}$ by ${r^2}$ and repeat the above arguments to achieve a similar densificiation of ${h}$ , at which point one has reduced (1) to (2).

A multi-dimensional Szemer\’edi theorem for the primes via a correspondence principle

13 June, 2013 in math.DS, math.NT, paper | Tags: constellations, correspondence principle, prime numbers, Szemeredi's theorem, Tamar Ziegler, transference principle | by Terence Tao | 1 comment

Tamar Ziegler and I have just uploaded to the arXiv our joint paper “A multi-dimensional Szemerédi theorem for the primes via a correspondence principle“. This paper is related to an earlier result of Ben Green and mine in which we established that the primes contain arbitrarily long arithmetic progressions. Actually, in that paper we proved a more general result:

Theorem 1 (Szemerédi’s theorem in the primes) Let ${A}$ be a subset of the primes ${{\mathcal P}}$ of positive relative density, thus ${\limsup_{N \rightarrow \infty} \frac{|A \cap [N]|}{|{\mathcal P} \cap [N]|} > 0}$ . Then ${A}$ contains arbitrarily long arithmetic progressions.

This result was based in part on an earlier paper of Green that handled the case of progressions of length three. With the primes replaced by the integers, this is of course the famous theorem of Szemerédi.

Szemerédi’s theorem has now been generalised in many different directions. One of these is the multidimensional Szemerédi theorem of Furstenberg and Katznelson, who used ergodic-theoretic techniques to show that any dense subset of ${{\bf Z}^d}$ necessarily contained infinitely many constellations of any prescribed shape. Our main result is to relativise that theorem to the primes as well:

Theorem 2 (Multidimensional Szemerédi theorem in the primes) Let ${d \geq 1}$ , and let ${A}$ be a subset of the ${d^{th}}$ Cartesian power ${{\mathcal P}^d}$ of the primes of positive relative density, thus

$\displaystyle \limsup_{N \rightarrow \infty} \frac{|A \cap [N]^d|}{|{\mathcal P}^d \cap [N]^d|} > 0.$

Then for any ${v_1,\ldots,v_k \in {\bf Z}^d}$ , ${A}$ contains infinitely many “constellations” of the form ${a+r v_1, \ldots, a + rv_k}$ with ${a \in {\bf Z}^k}$ and ${r}$ a positive integer.

In the case when ${A}$ is itself a Cartesian product of one-dimensional sets (in particular, if ${A}$ is all of ${{\mathcal P}^d}$ ), this result already follows from Theorem 1, but there does not seem to be a similarly easy argument to deduce the general case of Theorem 2 from previous results. Simultaneously with this paper, an independent proof of Theorem 2 using a somewhat different method has been established by Cook, Maygar, and Titichetrakun.

The result is reminiscent of an earlier result of mine on finding constellations in the Gaussian primes (or dense subsets thereof). That paper followed closely the arguments of my original paper with Ben Green, namely it first enclosed (a W-tricked version of) the primes or Gaussian primes (in a sieve theoretic-sense) by a slightly larger set (or more precisely, a weight function ${\nu}$ ) of almost primes or almost Gaussian primes, which one could then verify (using methods closely related to the sieve-theoretic methods in the ongoing Polymath8 project) to obey certain pseudorandomness conditions, known as the linear forms condition and the correlation condition. Very roughly speaking, these conditions assert statements of the following form: if ${n}$ is a randomly selected integer, then the events of ${n+h_1,\ldots,n+h_k}$ simultaneously being an almost prime (or almost Gaussian prime) are approximately independent for most choices of ${h_1,\ldots,h_k}$ . Once these conditions are satisfied, one can then run a transference argument (initially based on ergodic-theory methods, but nowadays there are simpler transference results based on the Hahn-Banach theorem, due to Gowers and Reingold-Trevisan-Tulsiani-Vadhan) to obtain relative Szemerédi-type theorems from their absolute counterparts.

However, when one tries to adapt these arguments to sets such as ${{\mathcal P}^2}$ , a new difficulty occurs: the natural analogue of the almost primes would be the Cartesian square ${{\mathcal A}^2}$ of the almost primes – pairs ${(n,m)}$ whose entries are both almost primes. (Actually, for technical reasons, one does not work directly with a set of almost primes, but would instead work with a weight function such as ${\nu(n) \nu(m)}$ that is concentrated on a set such as ${{\mathcal A}^2}$ , but let me ignore this distinction for now.) However, this set ${{\mathcal A}^2}$ does not enjoy as many pseudorandomness conditions as one would need for a direct application of the transference strategy to work. More specifically, given any fixed ${h, k}$ , and random ${(n,m)}$ , the four events

$\displaystyle (n,m) \in {\mathcal A}^2$

$\displaystyle (n+h,m) \in {\mathcal A}^2$

$\displaystyle (n,m+k) \in {\mathcal A}^2$

$\displaystyle (n+h,m+k) \in {\mathcal A}^2$

do not behave independently (as they would if ${{\mathcal A}^2}$ were replaced for instance by the Gaussian almost primes), because any three of these events imply the fourth. This blocks the transference strategy for constellations which contain some right-angles to them (e.g. constellations of the form ${(n,m), (n+r,m), (n,m+r)}$ ) as such constellations soon turn into rectangles such as the one above after applying Cauchy-Schwarz a few times. (But a few years ago, Cook and Magyar showed that if one restricted attention to constellations which were in general position in the sense that any coordinate hyperplane contained at most one element in the constellation, then this obstruction does not occur and one can establish Theorem 2 in this case through the transference argument.) It’s worth noting that very recently, Conlon, Fox, and Zhao have succeeded in removing of the pseudorandomness conditions (namely the correlation condition) from the transference principle, leaving only the linear forms condition as the remaining pseudorandomness condition to be verified, but unfortunately this does not completely solve the above problem because the linear forms condition also fails for ${{\mathcal A}^2}$ (or for weights concentrated on ${{\mathcal A}^2}$ ) when applied to rectangular patterns.

There are now two ways known to get around this problem and establish Theorem 2 in full generality. The approach of Cook, Magyar, and Titichetrakun proceeds by starting with one of the known proofs of the multidimensional Szemerédi theorem – namely, the proof that proceeds through hypergraph regularity and hypergraph removal – and attach pseudorandom weights directly within the proof itself, rather than trying to add the weights to the result of that proof through a transference argument. (A key technical issue is that weights have to be added to all the levels of the hypergraph – not just the vertices and top-order edges – in order to circumvent the failure of naive pseudorandomness.) As one has to modify the entire proof of the multidimensional Szemerédi theorem, rather than use that theorem as a black box, the Cook-Magyar-Titichetrakun argument is lengthier than ours; on the other hand, it is more general and does not rely on some difficult theorems about primes that are used in our paper.

In our approach, we continue to use the multidimensional Szemerédi theorem (or more precisely, the equivalent theorem of Furstenberg and Katznelson concerning multiple recurrence for commuting shifts) as a black box. The difference is that instead of using a transference principle to connect the relative multidimensional Szemerédi theorem we need to the multiple recurrence theorem, we instead proceed by a version of the Furstenberg correspondence principle, similar to the one that connects the absolute multidimensional Szemerédi theorem to the multiple recurrence theorem. I had discovered this approach many years ago in an unpublished note, but had abandoned it because it required an infinite number of linear forms conditions (in contrast to the transference technique, which only needed a finite number of linear forms conditions and (until the recent work of Conlon-Fox-Zhao) a correlation condition). The reason for this infinite number of conditions is that the correspondence principle has to build a probability measure on an entire ${\sigma}$ -algebra; for this, it is not enough to specify the measure ${\mu(A)}$ of a single set such as ${A}$ , but one also has to specify the measure ${\mu( T^{n_1} A \cap \ldots \cap T^{n_m} A)}$ of “cylinder sets” such as ${T^{n_1} A \cap \ldots \cap T^{n_m} A}$ where ${m}$ could be arbitrarily large. The larger ${m}$ gets, the more linear forms conditions one needs to keep the correspondence under control.

With the sieve weights ${\nu}$ we were using at the time, standard sieve theory methods could indeed provide a finite number of linear forms conditions, but not an infinite number, so my idea was abandoned. However, with my later work with Green and Ziegler on linear equations in primes (and related work on the Mobius-nilsequences conjecture and the inverse conjecture on the Gowers norm), Tamar and I realised that the primes themselves obey an infinite number of linear forms conditions, so one can basically use the primes (or a proxy for the primes, such as the von Mangoldt function ${\Lambda}$ ) as the enveloping sieve weight, rather than a classical sieve. Thus my old idea of using the Furstenberg correspondence principle to transfer Szemerédi-type theorems to the primes could actually be realised. In the one-dimensional case, this simply produces a much more complicated proof of Theorem 1 than the existing one; but it turns out that the argument works as well in higher dimensions and yields Theorem 2 relatively painlessly, except for the fact that it needs the results on linear equations in primes, the known proofs of which are extremely lengthy (and also require some of the transference machinery mentioned earlier). The problem of correlations in rectangles is avoided in the correspondence principle approach because one can compensate for such correlations by performing a suitable weighted limit to compute the measure ${\mu( T^{n_1} A \cap \ldots \cap T^{n_m} A)}$ of cylinder sets, with each ${m}$ requiring a different weighted correction. (This may be related to the Cook-Magyar-Titichetrakun strategy of weighting all of the facets of the hypergraph in order to recover pseudorandomness, although our contexts are rather different.)

Multiple recurrence and convergence results associated to F_p^omega-actions

21 May, 2013 in math.DS, paper | Tags: ergodic theory, finite fields, multiple convergence, multiple recurrence, polynomials, Tamar Ziegler, Vitaly Bergelson | by Terence Tao | 4 comments

Vitaly Bergelson, Tamar Ziegler, and I have just uploaded to the arXiv our joint paper “Multiple recurrence and convergence results associated to ${{\bf F}_{p}^{\omega}}$ -actions“. This paper is primarily concerned with limit formulae in the theory of multiple recurrence in ergodic theory. Perhaps the most basic formula of this type is the mean ergodic theorem, which (among other things) asserts that if ${(X,{\mathcal X}, \mu,T)}$ is a measure-preserving ${{\bf Z}}$ -system (which, in this post, means that ${(X,{\mathcal X}, \mu)}$ is a probability space and ${T: X \mapsto X}$ is measure-preserving and invertible, thus giving an action ${(T^n)_{n \in {\bf Z}}}$ of the integers), and ${f,g \in L^2(X,{\mathcal X}, \mu)}$ are functions, and ${X}$ is ergodic (which means that ${L^2(X,{\mathcal X}, \mu)}$ contains no ${T}$ -invariant functions other than the constants (up to almost everywhere equivalence, of course)), then the average

$\displaystyle \frac{1}{N} \sum_{n=1}^N \int_X f(x) g(T^n x)\ d\mu \ \ \ \ \ (1)$

converges as ${N \rightarrow \infty}$ to the expression

$\displaystyle (\int_X f(x)\ d\mu) (\int_X g(x)\ d\mu);$

see e.g. this previous blog post. Informally, one can interpret this limit formula as an equidistribution result: if ${x}$ is drawn at random from ${X}$ (using the probability measure ${\mu}$ ), and ${n}$ is drawn at random from ${\{1,\ldots,N\}}$ for some large ${N}$ , then the pair ${(x, T^n x)}$ becomes uniformly distributed in the product space ${X \times X}$ (using product measure ${\mu \times \mu}$ ) in the limit as ${N \rightarrow \infty}$ .

If we allow ${(X,\mu)}$ to be non-ergodic, then we still have a limit formula, but it is a bit more complicated. Let ${{\mathcal X}^T}$ be the ${T}$ -invariant measurable sets in ${{\mathcal X}}$ ; the ${{\bf Z}}$ -system ${(X, {\mathcal X}^T, \mu, T)}$ can then be viewed as a factor of the original system ${(X, {\mathcal X}, \mu, T)}$ , which is equivalent (in the sense of measure-preserving systems) to a trivial system ${(Z_0, {\mathcal Z}_0, \mu_{Z_0}, 1)}$ (known as the invariant factor) in which the shift is trivial. There is then a projection map ${\pi_0: X \rightarrow Z_0}$ to the invariant factor which is a factor map, and the average (1) converges in the limit to the expression

$\displaystyle \int_{Z_0} (\pi_0)_* f(z) (\pi_0)_* g(z)\ d\mu_{Z_0}(x), \ \ \ \ \ (2)$

where ${(\pi_0)_*: L^2(X,{\mathcal X},\mu) \rightarrow L^2(Z_0,{\mathcal Z}_0,\mu_{Z_0})}$ is the pushforward map associated to the map ${\pi_0: X \rightarrow Z_0}$ ; see e.g. this previous blog post. We can interpret this as an equidistribution result. If ${(x,T^n x)}$ is a pair as before, then we no longer expect complete equidistribution in ${X \times X}$ in the non-ergodic, because there are now non-trivial constraints relating ${x}$ with ${T^n x}$ ; indeed, for any ${T}$ -invariant function ${f: X \rightarrow {\bf C}}$ , we have the constraint ${f(x) = f(T^n x)}$ ; putting all these constraints together we see that ${\pi_0(x) = \pi_0(T^n x)}$ (for almost every ${x}$ , at least). The limit (2) can be viewed as an assertion that this constraint ${\pi_0(x) = \pi_0(T^n x)}$ are in some sense the “only” constraints between ${x}$ and ${T^n x}$ , and that the pair ${(x,T^n x)}$ is uniformly distributed relative to these constraints.

Limit formulae are known for multiple ergodic averages as well, although the statement becomes more complicated. For instance, consider the expression

$\displaystyle \frac{1}{N} \sum_{n=1}^N \int_X f(x) g(T^n x) h(T^{2n} x)\ d\mu \ \ \ \ \ (3)$

for three functions ${f,g,h \in L^\infty(X, {\mathcal X}, \mu)}$ ; this is analogous to the combinatorial task of counting length three progressions in various sets. For simplicity we assume the system ${(X,{\mathcal X},\mu,T)}$ to be ergodic. Naively one might expect this limit to then converge to

$\displaystyle (\int_X f\ d\mu) (\int_X g\ d\mu) (\int_X h\ d\mu)$

which would roughly speaking correspond to an assertion that the triplet ${(x,T^n x, T^{2n} x)}$ is asymptotically equidistributed in ${X \times X \times X}$ . However, even in the ergodic case there can be additional constraints on this triplet that cannot be seen at the level of the individual pairs ${(x,T^n x)}$ , ${(x, T^{2n} x)}$ . The key obstruction here is that of eigenfunctions of the shift ${T: X \rightarrow X}$ , that is to say non-trivial functions ${f: X \rightarrow S^1}$ that obey the eigenfunction equation ${Tf = \lambda f}$ almost everywhere for some constant (or ${T}$ -invariant) ${\lambda}$ . Each such eigenfunction generates a constraint

$\displaystyle f(x) \overline{f(T^n x)}^2 f(T^{2n} x) = 1 \ \ \ \ \ (4)$

tying together ${x}$ , ${T^n x}$ , and ${T^{2n} x}$ . However, it turns out that these are in some sense the only constraints on ${x,T^n x, T^{2n} x}$ that are relevant for the limit (3). More precisely, if one sets ${{\mathcal X}_1}$ to be the sub-algebra of ${{\mathcal X}}$ generated by the eigenfunctions of ${T}$ , then it turns out that the factor ${(X, {\mathcal X}_1, \mu, T)}$ is isomorphic to a shift system ${(Z_1, {\mathcal Z}_1, \mu_{Z_1}, x \mapsto x+\alpha)}$ known as the Kronecker factor, for some compact abelian group ${Z_1 = (Z_1,+)}$ and some (irrational) shift ${\alpha \in Z_1}$ ; the factor map ${\pi_1: X \rightarrow Z_1}$ pushes eigenfunctions forward to (affine) characters on ${Z_1}$ . It is then known that the limit of (3) is

$\displaystyle \int_\Sigma (\pi_1)_* f(x_0) (\pi_1)_* g(x_1) (\pi_1)_* h(x_2)\ d\mu_\Sigma$

where ${\Sigma \subset Z_1^3}$ is the closed subgroup

$\displaystyle \Sigma = \{ (x_1,x_2,x_3) \in Z_1^3: x_1-2x_2+x_3=0 \}$

and ${\mu_\Sigma}$ is the Haar probability measure on ${\Sigma}$ ; see this previous blog post. The equation ${x_1-2x_2+x_3=0}$ defining ${\Sigma}$ corresponds to the constraint (4) mentioned earlier. Among other things, this limit formula implies Roth’s theorem, which in the context of ergodic theory is the assertion that the limit (or at least the limit inferior) of (3) is positive when ${f=g=h}$ is non-negative and not identically vanishing.

If one considers a quadruple average

$\displaystyle \frac{1}{N} \sum_{n=1}^N \int_X f(x) g(T^n x) h(T^{2n} x) k(T^{3n} x)\ d\mu \ \ \ \ \ (5)$

(analogous to counting length four progressions) then the situation becomes more complicated still, even in the ergodic case. In addition to the (linear) eigenfunctions that already showed up in the computation of the triple average (3), a new type of constraint also arises from quadratic eigenfunctions ${f: X \rightarrow S^1}$ , which obey an eigenfunction equation ${Tf = \lambda f}$ in which ${\lambda}$ is no longer constant, but is now a linear eigenfunction. For such functions, ${f(T^n x)}$ behaves quadratically in ${n}$ , and one can compute the existence of a constraint

$\displaystyle f(x) \overline{f(T^n x)}^3 f(T^{2n} x)^3 \overline{f(T^{3n} x)} = 1 \ \ \ \ \ (6)$

between ${x}$ , ${T^n x}$ , ${T^{2n} x}$ , and ${T^{3n} x}$ that is not detected at the triple average level. As it turns out, this is not the only type of constraint relevant for (5); there is a more general class of constraint involving two-step nilsystems which we will not detail here, but see e.g. this previous blog post for more discussion. Nevertheless there is still a similar limit formula to previous examples, involving a special factor ${(Z_2, {\mathcal Z}_2, \mu_{Z_2}, S)}$ which turns out to be an inverse limit of two-step nilsystems; this limit theorem can be extracted from the structural theory in this paper of Host and Kra combined with a limit formula for nilsystems obtained by Lesigne, but will not be reproduced here. The pattern continues to higher averages (and higher step nilsystems); this was first done explicitly by Ziegler, and can also in principle be extracted from the structural theory of Host-Kra combined with nilsystem equidistribution results of Leibman. These sorts of limit formulae can lead to various recurrence results refining Roth’s theorem in various ways; see this paper of Bergelson, Host, and Kra for some examples of this.

The above discussion was concerned with ${{\bf Z}}$ -systems, but one can adapt much of the theory to measure-preserving ${G}$ -systems for other discrete countable abelian groups ${G}$ , in which one now has a family ${(T_g)_{g \in G}}$ of shifts indexed by ${G}$ rather than a single shift, obeying the compatibility relation ${T_{g+h}=T_g T_h}$ . The role of the intervals ${\{1,\ldots,N\}}$ in this more general setting is replaced by that of Folner sequences. For arbitrary countable abelian ${G}$ , the theory for double averages (1) and triple limits (3) is essentially identical to the ${{\bf Z}}$ -system case. But when one turns to quadruple and higher limits, the situation becomes more complicated (and, for arbitrary ${G}$ , still not fully understood). However one model case which is now well understood is the finite field case when ${G = {\bf F}_p^\omega = \bigcup_{n=1}^\infty {\bf F}_p^n}$ is an infinite-dimensional vector space over a finite field ${{\bf F}_p}$ (with the finite subspaces ${{\bf F}_p^n}$ then being a good choice for the Folner sequence). Here, the analogue of the structural theory of Host and Kra was worked out by Vitaly, Tamar, and myself in these previous papers (treating the high characteristic and low characteristic cases respectively). In the finite field setting, it turns out that nilsystems no longer appear, and one only needs to deal with linear, quadratic, and higher order eigenfunctions (known collectively as phase polynomials). It is then natural to look for a limit formula that asserts, roughly speaking, that if ${x}$ is drawn at random from a ${{\bf F}_p^\omega}$ -system and ${n}$ drawn randomly from a large subspace of ${{\bf F}_p^\omega}$ , then the only constraints between ${x, T^n x, \ldots, T^{(p-1)n} x}$ are those that arise from phase polynomials. The main theorem of this paper is to establish this limit formula (which, again, is a little complicated to state explicitly and will not be done here). In particular, we establish for the first time that the limit actually exists (a result which, for ${{\bf Z}}$ -systems, was one of the main results of this paper of Host and Kra).

As a consequence, we can recover finite field analogues of most of the results of Bergelson-Host-Kra, though interestingly some of the counterexamples demonstrating sharpness of their results for ${{\bf Z}}$ -systems (based on Behrend set constructions) do not seem to be present in the finite field setting (cf. this previous blog post on the cap set problem). In particular, we are able to largely settle the question of when one has a Khintchine-type theorem that asserts that for any measurable set ${A}$ in an ergodic ${{\bf F}_p^\omega}$ -system and any ${\epsilon>0}$ , one has

$\displaystyle \mu( T_{c_1 n} A \cap \ldots \cap T_{c_k n} A ) > \mu(A)^k - \epsilon$

for a syndetic set of ${n}$ , where ${c_1,\ldots,c_k \in {\bf F}_p}$ are distinct residue classes. It turns out that Khintchine-type theorems always hold for ${k=1,2,3}$ (and for ${k=1,2}$ ergodicity is not required), and for ${k=4}$ it holds whenever ${c_1,c_2,c_3,c_4}$ form a parallelogram, but not otherwise (though the counterexample here was such a painful computation that we ended up removing it from the paper, and may end up putting it online somewhere instead), and for larger ${k}$ we could show that the Khintchine property failed for generic choices of ${c_1,\ldots,c_k}$ , though the problem of determining exactly the tuples for which the Khintchine property failed looked to be rather messy and we did not completely settle it.

The Katai-Bourgain-Sarnak-Ziegler orthogonality criterion

21 November, 2011 in expository, math.NT | Tags: almost orthogonality, Jean Bourgain, Mobius function, Peter Sarnak, Tamar Ziegler | by Terence Tao | 14 comments

One of the basic problems in analytic number theory is to estimate sums of the form

$\displaystyle \sum_{p<x} f(p)$

as ${x \rightarrow \infty}$ , where ${p}$ ranges over primes and ${f}$ is some explicit function of interest (e.g. a linear phase function ${f(p) = e^{2\pi i \alpha p}}$ for some real number ${\alpha}$ ). This is essentially the same task as obtaining estimates on the sum

$\displaystyle \sum_{n<x} \Lambda(n) f(n)$

where ${\Lambda}$ is the von Mangoldt function. If ${f}$ is bounded, ${f(n)=O(1)}$ , then from the prime number theorem one has the trivial bound

$\displaystyle \sum_{n<x} \Lambda(n) f(n) = O(x)$

but often (when ${f}$ is somehow “oscillatory” in nature) one is seeking the refinement

$\displaystyle \sum_{n<x} \Lambda(n) f(n) = o(x) \ \ \ \ \ (1)$

or equivalently

$\displaystyle \sum_{p<x} f(p) = o(\frac{x}{\log x}). \ \ \ \ \ (2)$

Thanks to identities such as

$\displaystyle \Lambda(n) = \sum_{d|n} \mu(d) \log(\frac{n}{d}), \ \ \ \ \ (3)$

where ${\mu}$ is the Möbius function, refinements such as (1) are similar in spirit to estimates of the form

$\displaystyle \sum_{n<x} \mu(n) f(n) = o(x). \ \ \ \ \ (4)$

Unfortunately, the connection between (1) and (4) is not particularly tight; roughly speaking, one needs to improve the bounds in (4) (and variants thereof) by about two factors of ${\log x}$ before one can use identities such as (3) to recover (1). Still, one generally thinks of (1) and (4) as being “morally” equivalent, even if they are not formally equivalent.

When ${f}$ is oscillating in a sufficiently “irrational” way, then one standard way to proceed is the method of Type I and Type II sums, which uses truncated versions of divisor identities such as (3) to expand out either (1) or (4) into linear (Type I) or bilinear sums (Type II) with which one can exploit the oscillation of ${f}$ . For instance, Vaughan’s identity lets one rewrite the sum in (1) as the sum of the Type I sum

$\displaystyle \sum_{d \leq U} \mu(d) (\sum_{V/d \leq r \leq x/d} (\log r) f(rd)),$

the Type I sum

$\displaystyle -\sum_{d \leq UV} a(d) \sum_{V/d \leq r \leq x/d} f(rd),$

the Type II sum

$\displaystyle -\sum_{V \leq d \leq x/U} \sum_{U < m \leq x/V} \Lambda(d) b(m) f(dm),$

and the error term ${\sum_{d \leq V} \Lambda(n) f(n)}$ , whenever ${1 \leq U, V \leq x}$ are parameters, and ${a, b}$ are the sequences

$\displaystyle a(d) := \sum_{e \leq U, f \leq V: ef = d} \Lambda(d) \mu(e)$

and

$\displaystyle b(m) := \sum_{d|m: d \leq U} \mu(d).$

Similarly one can express (4) as the Type I sum

$\displaystyle -\sum_{d \leq UV} c(d) \sum_{UV/d \leq r \leq x/d} f(rd),$

the Type II sum

$\displaystyle - \sum_{V < d \leq x/U} \sum_{U < m \leq x/d} \mu(m) b(d) f(dm)$

and the error term ${\sum_{d \leq UV} \mu(n) f(N)}$ , whenever ${1 \leq U,V \leq x}$ with ${UV \leq x}$ , and ${c}$ is the sequence

$\displaystyle c(d) := \sum_{e \leq U, f \leq V: ef = d} \mu(d) \mu(e).$

After eliminating troublesome sequences such as ${a(), b(), c()}$ via Cauchy-Schwarz or the triangle inequality, one is then faced with the task of estimating Type I sums such as

$\displaystyle \sum_{r \leq y} f(rd)$

or Type II sums such as

$\displaystyle \sum_{r \leq y} f(rd) \overline{f(rd')}$

for various ${y, d, d' \geq 1}$ . Here, the trivial bound is ${O(y)}$ , but due to a number of logarithmic inefficiencies in the above method, one has to obtain bounds that are more like ${O( \frac{y}{\log^C y})}$ for some constant ${C}$ (e.g. ${C=5}$ ) in order to end up with an asymptotic such as (1) or (4).

However, in a recent paper of Bourgain, Sarnak, and Ziegler, it was observed that as long as one is only seeking the Mobius orthogonality (4) rather than the von Mangoldt orthogonality (1), one can avoid losing any logarithmic factors, and rely purely on qualitative equidistribution properties of ${f}$ . A special case of their orthogonality criterion (which actually dates back to an earlier paper of Katai, as was pointed out to me by Nikos Frantzikinakis) is as follows:

Proposition 1 (Orthogonality criterion) Let ${f: {\bf N} \rightarrow {\bf C}}$ be a bounded function such that

$\displaystyle \sum_{n \leq x} f(pn) \overline{f(qn)} = o(x) \ \ \ \ \ (5)$

for any distinct primes ${p, q}$ (where the decay rate of the error term ${o(x)}$ may depend on ${p}$ and ${q}$ ). Then

$\displaystyle \sum_{n \leq x} \mu(n) f(n) =o(x). \ \ \ \ \ (6)$

Actually, the Bourgain-Sarnak-Ziegler paper establishes a more quantitative version of this proposition, in which ${\mu}$ can be replaced by an arbitrary bounded multiplicative function, but we will content ourselves with the above weaker special case. (See also these notes of Harper, which uses the Katai argument to give a slightly weaker quantitative bound in the same spirit.) This criterion can be viewed as a multiplicative variant of the classical van der Corput lemma, which in our notation asserts that ${\sum_{n \leq x} f(n) = o(x)}$ if one has ${\sum_{n \leq x} f(n+h) \overline{f(n)} = o(x)}$ for each fixed non-zero ${h}$ .

As a sample application, Proposition 1 easily gives a proof of the asymptotic

$\displaystyle \sum_{n \leq x} \mu(n) e^{2\pi i \alpha n} = o(x)$

for any irrational ${\alpha}$ . (For rational ${\alpha}$ , this is a little trickier, as it is basically equivalent to the prime number theorem in arithmetic progressions.) The paper of Bourgain, Sarnak, and Ziegler also apply this criterion to nilsequences (obtaining a quick proof of a qualitative version of a result of Ben Green and myself, see these notes of Ziegler for details) and to horocycle flows (for which no Möbius orthogonality result was previously known).

Informally, the connection between (5) and (6) comes from the multiplicative nature of the Möbius function. If (6) failed, then ${\mu(n)}$ exhibits strong correlation with ${f(n)}$ ; by change of variables, we then expect ${\mu(pn)}$ to correlate with ${f(pn)}$ and ${\mu(pm)}$ to correlate with ${f(qn)}$ , for “typical” ${p,q}$ at least. On the other hand, since ${\mu}$ is multiplicative, ${\mu(pn)}$ exhibits strong correlation with ${\mu(qn)}$ . Putting all this together (and pretending correlation is transitive), this would give the claim (in the contrapositive). Of course, correlation is not quite transitive, but it turns out that one can use the Cauchy-Schwarz inequality as a substitute for transitivity of correlation in this case.

I will give a proof of Proposition 1 below the fold (which is not quite based on the argument in the above mentioned paper, but on a variant of that argument communicated to me by Tamar Ziegler, and also independently discovered by Adam Harper). The main idea is to exploit the following observation: if ${P}$ is a “large” but finite set of primes (in the sense that the sum ${A := \sum_{p \in P} \frac{1}{p}}$ is large), then for a typical large number ${n}$ (much larger than the elements of ${P}$ ), the number of primes in ${P}$ that divide ${n}$ is pretty close to ${A = \sum_{p \in P} \frac{1}{p}}$ :

$\displaystyle \sum_{p \in P: p|n} 1 \approx A. \ \ \ \ \ (7)$

A more precise formalisation of this heuristic is provided by the Turan-Kubilius inequality, which is proven by a simple application of the second moment method.

In particular, one can sum (7) against ${\mu(n) f(n)}$ and obtain an approximation

$\displaystyle \sum_{n \leq x} \mu(n) f(n) \approx \frac{1}{A} \sum_{p \in P} \sum_{n \leq x: p|n} \mu(n) f(n)$

that approximates a sum of ${\mu(n) f(n)}$ by a bunch of sparser sums of ${\mu(n) f(n)}$ . Since

$\displaystyle x = \frac{1}{A} \sum_{p \in P} \frac{x}{p},$

we see (heuristically, at least) that in order to establish (4), it would suffice to establish the sparser estimates

$\displaystyle \sum_{n \leq x: p|n} \mu(n) f(n) = o(\frac{x}{p})$

for all ${p \in P}$ (or at least for “most” ${p \in P}$ ).

Now we make the change of variables ${n = pm}$ . As the Möbius function is multiplicative, we usually have ${\mu(n) = \mu(p) \mu(m) = - \mu(m)}$ . (There is an exception when ${n}$ is divisible by ${p^2}$ , but this will be a rare event and we will be able to ignore it.) So it should suffice to show that

$\displaystyle \sum_{m \leq x/p} \mu(m) f(pm) = o( x/p )$

for most ${p \in P}$ . However, by the hypothesis (5), the sequences ${m \mapsto f(pm)}$ are asymptotically orthogonal as ${p}$ varies, and this claim will then follow from a Cauchy-Schwarz argument.

Read the rest of this entry »

The inverse conjecture for the Gowers norm over finite fields in low characteristic

11 January, 2011 in math.CO, paper | Tags: finite fields, inverse conjecture for the Gowers norm, polynomials, Tamar Ziegler | by Terence Tao | 3 comments

Tamar Ziegler and I have just uploaded to the arXiv our paper “The inverse conjecture for the Gowers norm over finite fields in low characteristic“, submitted to Annals of Combinatorics. This paper completes another case of the inverse conjecture for the Gowers norm, this time for vector spaces ${{\bf F}^n}$ over a fixed finite field ${{\bf F} = {\bf F}_p}$ of prime order; with Vitaly Bergelson, we had previously established this claim when the characteristic of the field was large, so the main new result here is the extension to the low characteristic case. (The case of a cyclic group ${{\bf Z}/N{\bf Z}}$ or interval ${[N]}$ was established by Ben Green and ourselves in another recent paper. For an arbitrary abelian (or nilpotent) group, a general but less explicit description of the obstructions to Gowers uniformity was recently obtained by Szegedy; the latter result recovers the high-characteristic case of our result (as was done in a subsequent paper of Szegedy), as well as our results with Green, but it is not immediately evident whether Szegedy’s description of the obstructions matches up with the one predicted by the inverse conjecture in low characteristic.)

The statement of the main theorem is as follows. Given a finite-dimensional vector space ${V = {\bf F}^n}$ and a function ${f: V \rightarrow {\bf C}}$ , and an integer ${s \geq 0}$ , one can define the Gowers uniformity norm ${\|f\|_{U^{s+1}(V)}}$ by the formula

$\displaystyle \|f\|_{U^{s+1}(V)} := \left( \mathop{\bf E}_{x,h_1,\ldots,h_{s+1} \in V} \Delta_{h_1} \ldots \Delta_{h_{s+1}} f(x) \right)^{1/2^{s+1}}$

where ${\Delta_h f(x) := f(x+h) \overline{f(x)}}$ . If ${f}$ is bounded in magnitude by ${1}$ , it is easy to see that ${\|f\|_{U^{s+1}(V)}}$ is bounded by ${1}$ also, with equality if and only if ${f(x) = e(P)}$ for some non-classical polynomial ${P: V \rightarrow {\bf R}/{\bf Z}}$ of degree at most ${s}$ , where ${e(x) := e^{2\pi ix}}$ , and a non-classical polynomial of degree at most ${s}$ is a function whose ${s+1^{th}}$ “derivatives” vanish in the sense that

$\displaystyle \partial_{h_1} \ldots \partial_{h_{s+1}} P(x) = 0$

for all ${x,h_1,\ldots,h_{s+1} \in V}$ , where ${\partial_h P(x) := P(x+h) - P(x)}$ . Our result generalises this to the case when the uniformity norm is not equal to ${1}$ , but is still bounded away from zero:

Theorem 1 (Inverse conjecture) Let ${f: V \rightarrow {\bf C}}$ be bounded by ${1}$ with ${\|f\|_{U^{s+1}(V)} \geq \delta > 0}$ for some ${s \geq 0}$ . Then there exists a non-classical polynomial ${P: V \rightarrow {\bf R}/{\bf Z}}$ of degree at most ${s}$ such that ${|\langle f, e(P) \rangle_{L^2(V)}| := |{\bf E}_{x \in V} f(x) e(-P(x))| \geq c(s,p, \delta) > 0}$ , where ${c(s,p, \delta)}$ is a positive quantity depending only on the indicated parameters.

This theorem is trivial for ${s=0}$ , and follows easily from Fourier analysis for ${s=1}$ . The case ${s=2}$ was done in odd characteristic by Ben Green and myself, and in even characteristic by Samorodnitsky. In two papers, one with Vitaly Bergelson, we established this theorem in the “high characteristic” case when the characteristic ${p}$ of ${{\bf F}}$ was greater than ${s}$ (in which case there is essentially no distinction between non-classical polynomials and their classical counterparts, as discussed previously on this blog). The need to deal with genuinely non-classical polynomials is the main new difficulty in this paper that was not dealt with in previous literature.

In our previous paper with Bergelson, a “weak” version of the above theorem was proven, in which the polynomial ${P}$ in the conclusion had bounded degree ${O_{s,p}(1)}$ , rather than being of degree at most ${s}$ . In the current paper, we use this weak inverse theorem to reduce the inverse conjecture to a statement purely about polynomials:

Theorem 2 (Inverse conjecture for polynomials) Let ${s \geq 0}$ , and let ${P: V \rightarrow {\bf C}}$ be a non-classical polynomial of degree at most ${s+1}$ such that ${\|e(P)\|_{U^{s+1}(V)} \geq \delta > 0}$ . Then ${P}$ has bounded rank in the sense that ${P}$ is a function of ${O_{s,p,\delta}(1)}$ polynomials of degree at most ${s}$ .

This type of inverse theorem was first introduced by Bogdanov and Viola. The deduction of Theorem 1 from Theorem 2 and the weak inverse Gowers conjecture is fairly standard, so the main difficulty is to show Theorem 2.

The quantity ${-\log_{|{\bf F}|} \|e(P)\|_{U^{s+1}(V)}^{1/2^{s+1}}}$ of a polynomial ${P}$ of degree at most ${s+1}$ was denoted the analytic rank of ${P}$ by Gowers and Wolf. They observed that the analytic rank of ${P}$ was closely related to the rank of ${P}$ , defined as the least number of degree ${s}$ polynomials needed to express ${P}$ . For instance, in the quadratic case ${s=1}$ the two ranks are identical (in odd characteristic, at least). For general ${s}$ , it was easy to see that bounded rank implied bounded analytic rank; Theorem 2 is the converse statement.

We tried a number of ways to show that bounded analytic rank implied bounded rank, in particular spending a lot of time on ergodic-theoretic approaches, but eventually we settled on a “brute force” approach that relies on classifying those polynomials of bounded analytic rank as precisely as possible. The argument splits up into establishing three separate facts:

(Classical case) If a classical polynomial has bounded analytic rank, then it has bounded rank.
(Multiplication by ${p}$ ) If a non-classical polynomial ${P}$ (of degree at most ${s+1}$ ) has bounded analytic rank, then ${pP}$ (which can be shown to have degree at most ${\max(s-p,0)}$ ) also has bounded analytic rank.
(Division by ${p}$ ) If ${Q}$ is a non-clsasical polynomial of degree ${\max(s-p,0)}$ of bounded rank, then there is a non-classical polynomial ${P}$ of degree at most ${s+1}$ of bounded rank such that ${pQ=P}$ .

The multiplication by ${p}$ and division by ${p}$ facts allow one to easily extend the classical case of the theorem to the non-classical case of the theorem, basically because classical polynomials are the kernel of the multiplication-by- ${p}$ homomorphism. Indeed, if ${P}$ is a non-classical polynomial of bounded analytic rank of the right degree, then the multiplication by ${p}$ claim tells us that ${pP}$ also has bounded analytic rank, which by an induction hypothesis implies that ${pP}$ has bounded rank. Applying the division by ${p}$ claim, we find a bounded rank polynomial ${P'}$ such that ${pP = pP'}$ , thus ${P}$ differs from ${P'}$ by a classical polynomial, which necessarily has bounded analytic rank, hence bounded rank by the classical claim, and the claim follows.

Of the three claims, the multiplication-by- ${p}$ claim is the easiest to prove using known results; after a bit of Fourier analysis, it turns out to follow more or less immediately from the multidimensional Szemerédi theorem over finite fields of Bergelson, Leibman, and McCutcheon (one can also use the density Hales-Jewett theorem here if one desires).

The next easiest claim is the classical case. Here, the idea is to analyse a degree ${s+1}$ classical polynomial ${P: V \rightarrow {\bf F}}$ via its derivative ${d^{s+1} P: V^{s+1} \rightarrow {\bf F}}$ , defined by the formula

$\displaystyle d^{s+1} P( h_1,\ldots,h_{s+1}) := \partial_{h_1} \ldots \partial_{h_{s+1}} P(x)$

for any ${x,h_1,\ldots,h_{s+1} \in V}$ (the RHS is independent of ${x}$ as ${P}$ has degree ${s+1}$ ). This is a multilinear form, and if ${P}$ has bounded analytic rank, this form is biased (in the sense that the mean of ${e(d^{s+1} P)}$ is large). Applying a general equidistribution theorem of Kaufman and Lovett (based on this earlier paper of Green and myself) this implies that ${d^{s+1} P}$ is a function of a bounded number of multilinear forms of lower degree. Using some “regularity lemma” theory to clean up these forms so that they have good equidistribution properties, it is possible to understand exactly how the original multilinear form ${d^{s+1} P}$ depends on these lower degree forms; indeed, the description one eventually obtains is so explicit that one can write down by inspection another bounded rank polynomial ${Q}$ such that ${d^{s+1} P}$ is equal to ${d^{s+1} Q}$ . Thus ${P}$ differs from the bounded rank polynomial ${Q}$ by a lower degree error, which is automatically of bounded rank also, and the claim follows.

The trickiest thing to establish is the division by ${p}$ claim. The polynomial ${Q}$ is some function ${F(R_1,\ldots,R_m)}$ of lower degree polynomials ${R_1,\ldots,R_m}$ . Ideally, one would like to find a function ${F'(R_1,\ldots,R_m)}$ of the same polynomials with ${pF' = F}$ , such that ${F'(R_1,\ldots,R_m)}$ has the correct degree; however, we have counterexamples that show that this is not always possible. (These counterexamples are the main obstruction to making the ergodic theory approach work: in ergodic theory, one is only allowed to work with “measurable” functions, which are roughly analogous in this context to functions of the indicated polynomials ${Q, R_1,\ldots,R_m}$ and their shifts.) To get around this we have to first apply a regularity lemma to place ${R_1,\ldots,R_m}$ in a suitably equidistributed form (although the fact that ${R_1,\ldots,R_m}$ may be non-classical leads to a rather messy and technical description of this equidistribution), and then we have to extend each ${R_j}$ to a higher degree polynomial ${R'_j}$ with ${pR'_j = R_j}$ . There is a crucial “exact roots” property of polynomials that allows one to do this, with ${R'_j}$ having degree exactly ${p-1}$ higher than ${R_j}$ . It turns out that it is possible to find a function ${P = F'(R'_1,\ldots,R'_m)}$ of these extended polynomials that have the right degree and which solves the required equation ${pP=Q}$ ; this is established by classifying completely all functions of the equidistributed polynomials ${R_1,\ldots,R_m}$ or ${R'_1,\ldots,R'_m}$ that are of a given degree.

	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”

Infinite partial sumsets in the primes

Higher uniformity of bounded multiplicative functions in short intervals on average

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

An inverse theorem for the continuous Gowers uniformity norm

Narrow progressions in the primes

A multi-dimensional Szemer\’edi theorem for the primes via a correspondence principle

Multiple recurrence and convergence results associated to F_p^omega-actions

The Katai-Bourgain-Sarnak-Ziegler orthogonality criterion

The inverse conjecture for the Gowers norm over finite fields in low characteristic

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

For commenters