Tag Archive

You are currently browsing the tag archive for the ‘arithmetic progressions’ tag.

The Gowers uniformity norm of order 1+

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$\displaystyle + \delta$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

New bounds for Szemerédi’s theorem, III: A polylogarithmic bound for r_4(N)

5 May, 2017 in math.CO, paper | Tags: arithmetic progressions, Ben Green, Gowers uniformity norm, Szemeredi's theorem | by Terence Tao | 18 comments

Ben Green and I have (finally!) uploaded to the arXiv our paper “New bounds for Szemerédi’s theorem, III: A polylogarithmic bound for ${r_4(N)}$ “, submitted to Mathematika. This is the sequel to two previous papers (and an erratum to the former paper), concerning quantitative versions of Szemerédi’s theorem in the case of length four progressions. This sequel has been delayed for over a decade for a number of reasons, but we have finally managed to write the arguments up to our satisfaction and submit it (to a special issue of Mathematika honouring the work of Klaus Roth).

For any natural number ${N}$ , define ${r_4(N)}$ to be the largest cardinality of a subset ${A}$ of ${[N] = \{1,\dots,N\}}$ which does not contain any non-trivial arithmetic progressions ${a, a+r, a+2r, a+3r}$ of length four (where “non-trivial” means that ${r}$ is non-zero). Trivially we have ${r_4(N) \leq N}$ . In 1969, Szemerédi showed that ${r_4(N) = o(N)}$ . However, the decay rate that could be theoretically extracted from this argument (and from several subsequent proofs of this bound, including one by Roth) were quite poor. The first significant quantitative bound on this quantity was by Gowers, who showed that ${r_4(N) \ll N (\log \log N)^{-c}}$ for some absolute constant ${c>0}$ . In the second paper in the above-mentioned series, we managed to improve this bound to ${r_4(N) \ll N \exp( - c \sqrt{\log \log N})}$ . In this paper, we improve the bound further to ${r_4(N) \ll N (\log N)^{-c}}$ , which seems to be the limit of the methods. (We remark that if we could take ${c}$ to be larger than one, this would imply the length four case of a well known conjecture of Erdös that any set of natural numbers whose sum of reciprocals diverges would contain arbitrarily long arithmetic progressions. Thanks to the work of Sanders and of Bloom, the corresponding case of the conjecture for length three conjectures is nearly settled, as it is known that for the analogous bound on ${r_3(N)}$ one can take any ${c}$ less than one.)

Most of the previous work on bounding ${r_4(N)}$ relied in some form or another on the density increment argument introduced by Roth back in 1953; roughly speaking, the idea is to show that if a dense subset ${A}$ of ${[N]}$ fails to contain arithmetic progressions of length four, one seeks to then locate a long subprogression of ${[N]}$ in which ${A}$ has increased density. This was the basic method for instance underlying our previous bound ${r_4(N) \ll N \exp( - c \sqrt{\log \log N})}$ , as well as a finite field analogue of the bound ${r_4(N) \ll N (\log N)^{-c}}$ ; however we encountered significant technical difficulties for several years in extending this argument to obtain the result of the current paper. Our method is instead based on “energy increment arguments”, and more specifically on establishing quantitative version of a Khintchine-type recurrence theorem, similar to the qualitative recurrence theorems established (in the ergodic theory context) by Bergelson-Host-Kra, and (in the current combinatorial context) by Ben Green and myself.

One way to phrase the latter recurrence theorem is as follows. Suppose that ${A \subset [N]}$ has density ${\delta}$ . Then one would expect a “randomly” selected arithmetic progression ${{\bf a}, {\bf a}+{\bf r}, {\bf a}+2{\bf r}, {\bf a}+3{\bf r}}$ in ${[N]}$ (using the convention that random variables will be in boldface) to be contained in ${A}$ with probability about ${\delta^4}$ . This is not true in general, however it was shown by Ben and myself that for any ${\eta>0}$ , there was a set of shifts ${r \in [-N,N]}$ of cardinality ${\gg_{\delta,\eta} N}$ , such that for any such ${r}$ one had

$\displaystyle {\bf P}( {\bf a}, {\bf a}+r, {\bf a}+2r, {\bf a}+3r \in A ) \geq \delta^4 - \eta$

if ${{\bf a}}$ was chosen uniformly at random from ${[N]}$ . This easily implies that ${r_4(N) = o(N)}$ , but does not give a particularly good bound on the decay rate, because the implied constant in the cardinality lower bound ${\gg_{\delta,\eta} N}$ is quite poor (in fact of tower-exponential type, due to the use of regularity lemmas!), and so one has to take ${N}$ to be extremely large compared to ${\delta,\eta}$ to avoid the possibility that the set of shifts in the above theorem consists only of the trivial shift ${r=0}$ .

We do not know how to improve the lower bound on the set of shifts to the point where it can give bounds that are competitive with those in this paper. However, we can obtain better quantitative results if we permit ourselves to couple together the two parameters ${{\bf a}}$ and ${{\bf r}}$ of the length four progression. Namely, with ${A}$ , ${\delta}$ , ${\eta}$ as above, we are able to show that there exist random variables ${{\bf a}, {\bf r}}$ , not necessarily independent, such that

$\displaystyle {\bf P}( {\bf a}, {\bf a}+{\bf r}, {\bf a}+2{\bf r}, {\bf a}+3{\bf r} \in A ) \geq \delta^4 - \eta \ \ \ \ \ (1)$

and such that we have the non-degeneracy bound

$\displaystyle {\bf P}( {\bf r} = 0 ) \ll \exp( \eta^{-O(1)} ) / N.$

This then easily implies the main theorem.

The energy increment method is then deployed to locate a good pair ${({\bf a}, {\bf r})}$ of random variables that will obey the above bounds. One can get some intuition on how to proceed here by considering some model cases. Firstly one can consider a “globally quadratically structured” case in which the indicator function ${1_A}$ “behaves like” a globally quadratic function such as ${F( \alpha n^2 )}$ , for some irrational ${\alpha}$ and some smooth periodic function ${F: {\bf R}/{\bf Z} \rightarrow {\bf R}}$ of mean ${\delta}$ . If one then takes ${{\bf a}, {\bf r}}$ to be uniformly distributed in ${[N]}$ and ${[-\varepsilon N, \varepsilon N]}$ respectively for some small ${\varepsilon>0}$ , with no coupling between the two variables, then the left-hand side of (1) is approximately of the form

$\displaystyle \int_{(x,y,z,w) \in ({\bf R}/{\bf Z})^4: x-3y+3z-w = 0} F(x) F(y) F(z) F(w) \ \ \ \ \ (2)$

where the integral is with respect to the probability Haar measure, and the constraint ${x-3y+3z-w=0}$ ultimately arises from the algebraic constraint

$\displaystyle \alpha {\bf a}^2 - 3 \alpha ({\bf a}+{\bf r})^2 + 3 \alpha ({\bf a}+2{\bf r})^2 - \alpha ({\bf a}+3{\bf r})^2 = 0.$

However, an application of the Cauchy-Schwarz inequality and Fubini’s theorem shows that the integral in (2) is at least ${(\int_{{\bf R}/{\bf Z}} F)^4}$ , which (morally at least) gives (1) in this case.

Due to the nature of the energy increment argument, it also becomes necessary to consider “locally quadratically structured” cases, in which ${[N]}$ is partitioned into some number of structured pieces ${B_c}$ (think of these as arithmetic progressions, or as “Bohr sets), and on each piece ${B_c}$ , ${1_A}$ behaves like a locally quadratic function such as ${F_c( \alpha_c n^2 )}$ , where ${\alpha_c}$ now varies with ${c}$ , and the mean of ${F_c}$ will be approximately ${\delta}$ on the average after averaging in ${c}$ (weighted by the size of the pieces ${B_c}$ ). Now one should select ${{\bf a}}$ and ${{\bf r}}$ in the following coupled manner: first one chooses ${{\bf a}}$ uniformly from ${[N]}$ , then one defines ${{\bf c}}$ to be the label ${c}$ such that ${{\bf a} \in B_c}$ , and then selects ${{\bf r}}$ uniformly from a set ${B_{c,\varepsilon}}$ which is related to ${B_c}$ in much the same way that ${[-\varepsilon N, \varepsilon N]}$ is related to ${[N]}$ . If one does this correctly, the analogue of (2) becomes

$\displaystyle {\bf E} \int_{(x,y,z,w) \in ({\bf R}/{\bf Z})^4: x-3y+3z-w = 0} F_{\mathbf c}(x) F_{\mathbf c}(y) F_{\mathbf c}(z) F_{\mathbf c}(w),$

and one can again use Cauchy-Schwarz and Fubini’s theorem to conclude.

The general case proceeds, very roughly, by an iterative argument. At each stage of the iteration, one has some sort of quadratic model of ${1_A}$ which involves a decomposition of ${[N]}$ into structured pieces ${B_c}$ , and a quadratic approximation to ${1_A}$ on each piece. If this approximation is accurate enough (or more precisely, if a certain (averaged) local Gowers uniformity norm ${U^3}$ of the error is small enough) to model the count in (1) (for random variables ${{\bf a}, {\bf r}}$ determined by the above partition of ${[N]}$ into pieces ${B_c}$ ), and if the frequencies (such as ${\alpha_c}$ ) involved in the quadratic approximation are “high rank” or “linearly independent over the rationals” in a suitably quantitative sense, then some version of the above arguments can be made to work. If there are some unwanted linear dependencies in the frequencies, we can do some linear algebra to eliminate one of the frequencies (using some geometry of numbers to keep the quantitative bounds under control) and continue the iteration. If instead the approximation is too inaccurate, then the error will be large in a certain averaged local Gowers uniformity norm ${U^3}$ . A significant fraction of the paper is then devoted to establishing a quantitative inverse theorem for that norm that concludes (with good bounds) that the error must then locally correlate with locally quadratic phases, which can be used to refine the quadratic approximation to ${1_A}$ in a manner that significantly increases its “energy” (basically an ${L^2}$ norm). Such energy increments cannot continue indefinitely, and when they terminate we obtain the desired claim.

There are existing inverse theorems for ${U^3}$ type norms in the literature, going back to the pioneering work of Gowers mentioned previously, and relying on arithmetic combinatorics tools such as Freiman’s theorem and the Balog-Szemerédi-Gowers lemma, which are good for analysing the “ ${1\%}$ -structured homomorphisms” that arise in Gowers’ argument. However, when we applied these methods to the local Gowers norms we obtained inferior quantitative results that were not strong enough for our application. Instead, we use arguments from a different paper of Gowers in which he tackled Szemerédi’s theorem for arbitrary length progressions. This method produces “ ${99\%}$ -structured homomorphisms” associated to any function with large Gowers uniformity norm; however the catch is that such homomorphisms are initially supported only on a sparse unstructured set, rather than a structured set such as a Bohr set. To proceed further, one first has to locate inside the sparse unstructured set a sparse pseudorandom subset of a Bohr set, and then use “error-correction” type methods (such as “majority-vote” based algorithms) to locally upgrade this ${99\%}$ -structured homomorphism on pseudorandom subsets of Bohr sets to a ${100\%}$ -structured homomorphism on the entirety of a Bohr set. It is then possible to use some “approximate cohomology” tools to “integrate” these homomorphisms (and discern a key “local symmetry” property of these homomorphisms) to locate the desired local quadratic structure (in much the same fashion that a ${1}$ -form on ${{\bf R}^n}$ that varies linearly with the coordinates can be integrated to be the derivative of a quadratic function if we know that the ${1}$ -form is closed). These portions of the paper are unfortunately rather technical, but broadly follow the methods already used in previous literature.

A remark on the lonely runner conjecture

13 May, 2015 in expository, math.CA, question | Tags: arithmetic progressions, lonely runner conjecture | by Terence Tao | 58 comments

The lonely runner conjecture is the following open problem:

Conjecture 1 Suppose one has ${n \geq 1}$ runners on the unit circle ${{\bf R}/{\bf Z}}$ , all starting at the origin and moving at different speeds. Then for each runner, there is at least one time ${t}$ for which that runner is “lonely” in the sense that it is separated by a distance at least ${1/n}$ from all other runners.

One can normalise the speed of the lonely runner to be zero, at which point the conjecture can be reformulated (after replacing ${n}$ by ${n+1}$ ) as follows:

Conjecture 2 Let ${v_1,\dots,v_n}$ be non-zero real numbers for some ${n \geq 1}$ . Then there exists a real number ${t}$ such that the numbers ${tv_1,\dots,tv_n}$ are all a distance at least ${\frac{1}{n+1}}$ from the integers, thus ${\|tv_1\|_{{\bf R}/{\bf Z}},\dots,\|tv_n\|_{{\bf R}/{\bf Z}} \geq \frac{1}{n+1}}$ where ${\|x\|_{{\bf R}/{\bf Z}}}$ denotes the distance of ${x}$ to the nearest integer.

This conjecture has been proven for ${n \leq 7}$ , but remains open for larger ${n}$ . The bound ${\frac{1}{n+1}}$ is optimal, as can be seen by looking at the case ${v_i=i}$ and applying the Dirichlet approximation theorem. Note that for each non-zero ${v}$ , the set ${\{ t \in {\bf R}: \|vt\|_{{\bf R}/{\bf Z}} \leq r \}}$ has (Banach) density ${2r}$ for any ${0 < r < 1/2}$ , and from this and the union bound we can easily find ${t \in {\bf R}}$ for which

$\displaystyle \|tv_1\|_{{\bf R}/{\bf Z}},\dots,\|tv_n\|_{{\bf R}/{\bf Z}} \geq \frac{1}{2n}-\varepsilon$

for any ${\varepsilon>0}$ , but it has proven to be quite challenging to remove the factor of ${2}$ to increase ${\frac{1}{2n}}$ to ${\frac{1}{n+1}}$ . (As far as I know, even improving ${\frac{1}{2n}}$ to ${\frac{1+c}{2n}}$ for some absolute constant ${c>0}$ and sufficiently large ${n}$ remains open.)

The speeds ${v_1,\dots,v_n}$ in the above conjecture are arbitrary non-zero reals, but it has been known for some time that one can reduce without loss of generality to the case when the ${v_1,\dots,v_n}$ are rationals, or equivalently (by scaling) to the case where they are integers; see e.g. Section 4 of this paper of Bohman, Holzman, and Kleitman.

In this post I would like to remark on a slight refinement of this reduction, in which the speeds ${v_1,\dots,v_n}$ are integers of bounded size, where the bound depends on ${n}$ . More precisely:

Proposition 3 In order to prove the lonely runner conjecture, it suffices to do so under the additional assumption that the ${v_1,\dots,v_n}$ are integers of size at most ${n^{Cn^2}}$ , where ${C}$ is an (explicitly computable) absolute constant. (More precisely: if this restricted version of the lonely runner conjecture is true for all ${n \leq n_0}$ , then the original version of the conjecture is also true for all ${n \leq n_0}$ .)

In principle, this proposition allows one to verify the lonely runner conjecture for a given ${n}$ in finite time; however the number of cases to check with this proposition grows faster than exponentially in ${n}$ , and so this is unfortunately not a feasible approach to verifying the lonely runner conjecture for more values of ${n}$ than currently known.

One of the key tools needed to prove this proposition is the following additive combinatorics result. Recall that a generalised arithmetic progression (or ${GAP}$ ) in the reals ${{\bf R}}$ is a set of the form

$\displaystyle P = \{ n_1 v_1 + \dots + n_d v_d: n_1,\dots,n_d \in {\bf Z}; |n_1| \leq N_1, \dots, |n_d| \leq N_d \}$

for some ${v_1,\dots,v_d \in {\bf R}}$ and ${N_1,\dots,N_d > 0}$ ; the quantity ${d}$ is called the rank of the progression. If ${t>0}$ , the progression ${P}$ is said to be ${t}$ -proper if the sums ${n_1 v_1 + \dots + n_d v_d}$ with ${|n_i| \leq t N_i}$ for ${i=1,\dots,d}$ are all distinct. We have

Lemma 4 (Progressions lie inside proper progressions) Let ${P}$ be a GAP of rank ${d}$ in the reals, and let ${t \geq 1}$ . Then ${P}$ is contained in a ${t}$ -proper GAP ${Q}$ of rank at most ${d}$ , with

$\displaystyle |Q| \leq (2t)^d d^{6d^2} \prod_{i=1}^d (2N_i+1).$

Proof: See Theorem 2.1 of this paper of Bilu. (Very similar results can also be found in Theorem 3.40 of my book with Van Vu, or Theorem 1.10 of this paper of mine with Van Vu.) $\Box$

Now let ${n \geq 1}$ , and assume inductively that the lonely runner conjecture has been proven for all smaller values of ${n}$ , as well as for the current value of ${n}$ in the case that ${v_1,\dots,v_n}$ are integers of size at most ${n^{Cn^2}}$ for some sufficiently large ${C}$ . We will show that the lonely runner conjecture holds in general for this choice of ${n}$ .

let ${v_1,\dots,v_n}$ be non-zero real numbers. Let ${C_0}$ be a large absolute constant to be chosen later. From the above lemma applied to the GAP ${\{ n_1 v_1 + \dots + n_d v_d: n_1,\dots,n_d \in \{-1,0,1\}\}}$ , one can find a ${n^{C_0n}}$ -proper GAP ${Q}$ of rank at most ${n}$ containing ${\{v_1,\dots,v_n\}}$ such that

$\displaystyle |Q| \leq (6n^{C_0 n})^n n^{6n^2};$

in particular ${|Q| \leq n^{Cn^2}}$ if ${C}$ is large enough depending on ${C_0}$ .

We write

$\displaystyle Q = \{ n_1 w_1 + \dots + n_d w_d: n_1,\dots,n_d \in {\bf Z}; |n_1| \leq N_1,\dots,|n_d| \leq N_d \}$

for some ${d \leq n}$ , ${w_1,\dots,w_d}$ , and ${N_1,\dots,N_d \geq 0}$ . We thus have ${v_i = \phi(a_i)}$ for ${i=1,\dots,n}$ , where ${\phi: {\bf R}^d \rightarrow {\bf R}}$ is the linear map ${\phi(n_1,\dots,n_d) := n_1 w_1 + \dots + n_d w_d}$ and ${a_1,\dots,a_n \in {\bf Z}^d}$ are non-zero and lie in the box ${\{ (n_1,\dots,n_d) \in {\bf R}^d: |n_1| \leq N_1,\dots,|n_d| \leq N_d \}}$ .

We now need an elementary lemma that allows us to create a “collision” between two of the ${a_1,\dots,a_n}$ via a linear projection, without making any of the ${a_i}$ collide with the origin:

Lemma 5 Let ${a_1,\dots,a_n \in {\bf R}^d}$ be non-zero vectors that are not all collinear with the origin. Then, after replacing one or more of the ${a_i}$ with their negatives ${-a_i}$ if necessary, there exists a pair ${a_i,a_j}$ such that ${a_i-a_j \neq 0}$ , and such that none of the ${a_1,\dots,a_n}$ is a scalar multiple of ${a_i-a_j}$ .

Proof: We may assume that ${d \geq 2}$ , since the ${d \leq 1}$ case is vacuous. Applying a generic linear projection to ${{\bf R}^2}$ (which does not affect collinearity, or the property that a given ${a_k}$ is a scalar multiple of ${a_i-a_j}$ ), we may then reduce to the case ${d=2}$ .

By a rotation and relabeling, we may assume that ${a_1}$ lies on the negative ${x}$ -axis; by flipping signs as necessary we may then assume that all of the ${a_2,\dots,a_n}$ lie in the closed right half-plane. As the ${a_i}$ are not all collinear with the origin, one of the ${a_i}$ lies off of the ${x}$ -axis, by relabeling, we may assume that ${a_2}$ lies off of the ${x}$ axis and makes a minimal angle with the ${x}$ -axis. Then the angle of ${a_2-a_1}$ with the ${x}$ -axis is non-zero but smaller than any non-zero angle that any of the ${a_i}$ make with this axis, and so none of the ${a_i}$ are a scalar multiple of ${a_2-a_1}$ , and the claim follows. $\Box$

We now return to the proof of the proposition. If the ${a_1,\dots,a_n}$ are all collinear with the origin, then ${\phi(a_1),\dots,\phi(a_n)}$ lie in a one-dimensional arithmetic progression ${\{ mv: |m| \leq |Q| \}}$ , and then by rescaling we may take the ${v_1,\dots,v_n}$ to be integers of magnitude at most ${|Q| \leq n^{Cn}}$ , at which point we are done by hypothesis. Thus, we may assume that the ${a_1,\dots,a_n}$ are not all collinear with the origin, and so by the above lemma and relabeling we may assume that ${a_n-a_1}$ is non-zero, and that none of the ${a_i}$ are scalar multiples of ${a_n-a_1}$ .

We write

$\displaystyle a_n-a_1 = (c_1,\dots,c_d) \ \ \ \ \ (1)$

with ${|c_i| \leq 2 N_i}$ for ${i=1,\dots,d}$ ; by relabeling we may assume without loss of generality that ${c_d}$ is non-zero, and furthermore that

$\displaystyle \frac{|c_i|}{N_i} \leq \frac{|c_d|}{N_d}$

for ${i=1,\dots,d}$ . We can also factor

$\displaystyle (c_1,\dots,c_d) = q (c'_1,\dots,c'_d) \ \ \ \ \ (2)$

where ${q}$ is a natural number and ${c'_1,\dots,c'_d}$ have no common factor.

We now define a variant ${\tilde \phi: {\bf R}^d \rightarrow {\bf R}}$ of ${\phi: {\bf R}^d \rightarrow {\bf R}}$ by the map

$\displaystyle \tilde \phi(n_1,\dots,n_d) := n_1 \tilde w_1 + \dots + n_{d-1} \tilde w_{d-1} - \frac{n_d}{c_d} (c_1 \tilde w_1 + \dots + c_{d-1} \tilde w_{d-1}),$

where the ${\tilde w_1,\dots,\tilde w_{d-1}}$ are real numbers that are linearly independent over ${{\bf Q}}$ , whose precise value will not be of importance in our argument. This is a linear map with the property that ${\tilde \phi(a_n-a_1)=0}$ , so that ${\tilde \phi(a_1),\dots,\tilde \phi(a_n)}$ consists of at most ${n-1}$ distinct real numbers, which are non-zero since none of the ${a_i}$ are scalar multiples of ${a_n-a_1}$ , and the ${\tilde w_i}$ are linearly independent over ${{\bf Q}}$ . As we are assuming inductively that the lonely runner conjecture holds for ${n-1}$ , we conclude (after deleting duplicates) that there exists at least one real number ${\tilde t}$ such that

$\displaystyle \| \tilde t \tilde \phi(a_1) \|_{{\bf R}/{\bf Z}}, \dots, \| \tilde t \tilde \phi(a_n) \|_{{\bf R}/{\bf Z}} \geq \frac{1}{n}.$

We would like to “approximate” ${\phi}$ by ${\tilde \phi}$ to then conclude that there is at least one real number ${t}$ such that

$\displaystyle \| t \phi(a_1) \|_{{\bf R}/{\bf Z}}, \dots, \| t \phi(a_n) \|_{{\bf R}/{\bf Z}} \geq \frac{1}{n+1}.$

It turns out that we can do this by a Fourier-analytic argument taking advantage of the ${n^{C_0 n}}$ -proper nature of ${Q}$ . Firstly, we see from the Dirichlet approximation theorem that one has

$\displaystyle \| \tilde t \tilde \phi(a_1) \|_{{\bf R}/{\bf Z}}, \dots, \| \tilde t \tilde \phi(a_n) \|_{{\bf R}/{\bf Z}} \leq \frac{1}{10 n^2}$

for a set ${\tilde t}$ of reals of (Banach) density ${\gg n^{-O(n)}}$ . Thus, by the triangle inequality, we have

$\displaystyle \| \tilde t \tilde \phi(a_1) \|_{{\bf R}/{\bf Z}}, \dots, \| \tilde t \tilde \phi(a_n) \|_{{\bf R}/{\bf Z}} \geq \frac{1}{n} - \frac{1}{10n^2}$

for a set ${\tilde t}$ of reals of density ${\gg n^{-O(n)}}$ .

Applying a smooth Fourier multiplier of Littlewood-Paley type, one can find a trigonometric polynomial

$\displaystyle \eta(x) = \sum_{m: |m| \leq n^{C_0 n/10}} b_m e^{2\pi i mx}$

which takes values in ${[0,1]}$ , is ${\gg 1}$ for ${\|x\|_{{\bf R}/{\bf Z}} \geq \frac{1}{n} - \frac{1}{10n^2}}$ , and is no larger than ${O( n^{-100 C_0n} )}$ for ${\|x\|_{{\bf R}/{\bf Z}} \leq \frac{1}{n+1}}$ . We then have

$\displaystyle \mathop{\bf E}_t \prod_{j=1}^n \eta( t \tilde \phi(a_j) ) \gg n^{-O(n)}$

where ${\mathop{\bf E}_t f(t)}$ denotes the mean value of a quasiperiodic function ${f}$ on the reals ${{\bf R}}$ . We expand the left-hand side out as

$\displaystyle \sum_{m_1,\dots,m_n: m_1 \tilde \phi(a_1) + \dots + m_n \tilde \phi(a_n) = 0} b_{m_1} \dots b_{m_n}.$

From the genericity of ${\tilde w_1,\dots,\tilde w_n}$ , we see that the constraint

$\displaystyle m_1 \tilde \phi(a_1) + \dots + m_n \tilde \phi(a_n) = 0$

occurs if and only if ${m_1 a_1 + \dots + m_n a_n}$ is a scalar multiple of ${a_n-a_1}$ , or equivalently (by (1), (2)) an integer multiple of ${(c'_1,\dots,c'_d)}$ . Thus

$\displaystyle \sum_{m_1,\dots,m_n: m_1 a_1 + \dots + m_n a_n \in {\bf Z} (c'_1,\dots,c'_d)} b_{m_1} \dots b_{m_n} \gg n^{-O(n)}. \ \ \ \ \ (3)$

Next, we consider the average

$\displaystyle \mathop{\bf E}_t \varphi( t \xi ) \prod_{j=1}^n \eta( t v_j ) \ \ \ \ \ (4)$

where

$\displaystyle \xi := c'_1 w_1 + \dots + c'_d w_d. \ \ \ \ \ (5)$

and ${\varphi}$ is the Dirichlet series

$\displaystyle \varphi(x) := \sum_{m: |m| \leq n^{C_0 n/2}} e^{2\pi i mx}.$

By Fourier expansion and writing ${v_j = \phi(a_j)}$ , we may write (4) as

$\displaystyle \sum_{m,m_1,\dots,m_n: |m| \leq n^{C_0n/2}; m_1 \phi(a_1) + \dots + m_n \phi(a_n) = m \xi} b_{m_1} \dots b_{m_n}.$

The support of the ${b_{m_i}}$ implies that ${|m_i| \leq n^{C_0n/10}}$ . Because of the ${n^{C_0 n}}$ -properness of ${Q}$ , we see (for ${n}$ large enough) that the equation

$\displaystyle m_1 \phi(a_1) + \dots + m_n \phi(a_n) = m \xi \ \ \ \ \ (6)$

implies that

$\displaystyle m_1 a_1 + \dots + m_n a_n \in {\bf Z} (c'_1,\dots,c'_d) \ \ \ \ \ (7)$

and conversely that (7) implies that (6) holds for some ${m}$ with ${|m| \leq n^{C_0 n/2}}$ . From (3) we thus have

$\displaystyle \mathop{\bf E}_t \varphi( t \xi ) \prod_{j=1}^n \eta( t v_j ) \gg n^{-O(1)}.$

In particular, there exists a ${t}$ such that

$\displaystyle \varphi( t \xi ) \prod_{j=1}^n \eta( t v_j ) \gg n^{-O(1)}.$

Since ${\varphi}$ is bounded in magnitude by ${n^{C_0n/2}}$ , and ${\eta}$ is bounded by ${1}$ , we thus have

$\displaystyle \eta(t v_j) \gg n^{-C_0 n/2 - O(1)}$

for each ${1 \leq j \leq n}$ , which by the size properties of ${\eta}$ implies that ${\|tv_j\|_{{\bf R}/{\bf Z}} \geq \frac{1}{n+1}}$ for all ${1 \leq j \leq n}$ , giving the lonely runner conjecture for ${n}$ .

254A, Notes 7: Linnik’s theorem on primes in arithmetic progressions

22 February, 2015 in 254A - analytic prime number theory, math.NT | Tags: arithmetic progressions, Deuring-Heilbronn repulsion, prime number theorem | by Terence Tao | 12 comments

In the previous set of notes, we saw how zero-density theorems for the Riemann zeta function, when combined with the zero-free region of Vinogradov and Korobov, could be used to obtain prime number theorems in short intervals. It turns out that a more sophisticated version of this type of argument also works to obtain prime number theorems in arithmetic progressions, in particular establishing the celebrated theorem of Linnik:

Theorem 1 (Linnik’s theorem) Let ${a\ (q)}$ be a primitive residue class. Then ${a\ (q)}$ contains a prime ${p}$ with ${p \ll q^{O(1)}}$ .

In fact it is known that one can find a prime ${p}$ with ${p \ll q^{5}}$ , a result of Xylouris. For sake of comparison, recall from Exercise 65 of Notes 2 that the Siegel-Walfisz theorem gives this theorem with a bound of ${p \ll \exp( q^{o(1)} )}$ , and from Exercise 48 of Notes 2 one can obtain a bound of the form ${p \ll \phi(q)^2 \log^2 q}$ if one assumes the generalised Riemann hypothesis. The probabilistic random models from Supplement 4 suggest that one should in fact be able to take ${p \ll q^{1+o(1)}}$ .

We will not aim to obtain the optimal exponents for Linnik’s theorem here, and follow the treatment in Chapter 18 of Iwaniec and Kowalski. We will in fact establish the following more quantitative result (a special case of a more powerful theorem of Gallagher), which splits into two cases, depending on whether there is an exceptional zero or not:

Theorem 2 (Quantitative Linnik theorem) Let ${a\ (q)}$ be a primitive residue class for some ${q \geq 2}$ . For any ${x > 1}$ , let ${\psi(x;q,a)}$ denote the quantity

$\displaystyle \psi(x;q,a) := \sum_{n \leq x: n=a\ (q)} \Lambda(n).$

Assume that ${x \geq q^C}$ for some sufficiently large ${C}$ .

(i) (No exceptional zero) If all the real zeroes ${\beta}$ of ${L}$ -functions ${L(\cdot,\chi)}$ of real characters ${\chi}$ of modulus ${q}$ are such that ${1-\beta \gg \frac{1}{\log q}}$ , then
$\displaystyle \psi(x;q,a) = \frac{x}{\phi(q)} ( 1 + O( \exp( - c \frac{\log x}{\log q} ) ) + O( \frac{\log^2 q}{q} ) )$

for all ${x \geq 1}$ and some absolute constant ${c>0}$ .

(ii) (Exceptional zero) If there is a zero ${\beta}$ of an ${L}$ -function ${L(\cdot,\chi_1)}$ of a real character ${\chi_1}$ of modulus ${q}$ with ${\beta = 1 - \frac{\varepsilon}{\log q}}$ for some sufficiently small ${\varepsilon>0}$ , then
$\displaystyle \psi(x;q,a) = \frac{x}{\phi(q)} ( 1 - \chi_1(a) \frac{x^{\beta-1}}{\beta} \ \ \ \ \ (1)$

$\displaystyle + O( \exp( - c \frac{\log x}{\log q} \log \frac{1}{\varepsilon} ) )$

$\displaystyle + O( \frac{\log^2 q}{q} ) )$

for all ${x \geq 1}$ and some absolute constant ${c>0}$ .

The implied constants here are effective.

Note from the Landau-Page theorem (Exercise 54 from Notes 2) that at most one exceptional zero exists (if ${\varepsilon}$ is small enough). A key point here is that the error term ${O( \exp( - c \frac{\log x}{\log q} \log \frac{1}{\varepsilon} ) )}$ in the exceptional zero case is an improvement over the error term when no exceptional zero is present; this compensates for the potential reduction in the main term coming from the ${\chi_1(a) \frac{x^{\beta-1}}{\beta}}$ term. The splitting into cases depending on whether an exceptional zero exists or not turns out to be an essential technique in many advanced results in analytic number theory (though presumably such a splitting will one day become unnecessary, once the possibility of exceptional zeroes are finally eliminated for good).

Exercise 3 Assuming Theorem 2, and assuming ${x \geq q^C}$ for some sufficiently large absolute constant ${C}$ , establish the lower bound

$\displaystyle \psi(x;a,q) \gg \frac{x}{\phi(q)}$

when there is no exceptional zero, and

$\displaystyle \psi(x;a,q) \gg \varepsilon \frac{x}{\phi(q)}$

when there is an exceptional zero ${\beta = 1 - \frac{\varepsilon}{\log q}}$ . Conclude that Theorem 2 implies Theorem 1, regardless of whether an exceptional zero exists or not.

Remark 4 The Brun-Titchmarsh theorem (Exercise 33 from Notes 4), in the sharp form of Montgomery and Vaughan, gives that

$\displaystyle \pi(x; q, a) \leq 2 \frac{x}{\phi(q) \log (x/q)}$

for any primitive residue class ${a\ (q)}$ and any ${x \geq q}$ . This is (barely) consistent with the estimate (1). Any lowering of the coefficient ${2}$ in the Brun-Titchmarsh inequality (with reasonable error terms), in the regime when ${x}$ is a large power of ${q}$ , would then lead to at least some elimination of the exceptional zero case. However, this has not led to any progress on the Landau-Siegel zero problem (and may well be just a reformulation of that problem). (When ${x}$ is a relatively small power of ${q}$ , some improvements to Brun-Titchmarsh are possible that are not in contradiction with the presence of an exceptional zero; see this paper of Maynard for more discussion.)

Theorem 2 is deduced in turn from facts about the distribution of zeroes of ${L}$ -functions. We first need a version of the truncated explicit formula that does not lose unnecessary logarithms:

Exercise 5 (Log-free truncated explicit formula) With the hypotheses as above, show that

$\displaystyle \sum_{n \leq x} \Lambda(n) \chi(n) = - \sum_{\hbox{Re}(\rho) > 3/4; |\hbox{Im}(\rho)| \leq q^2; L(\rho,\chi)=0} \frac{x^\rho}{\rho} + O( \frac{x}{q^2} \log^2 q)$

for any non-principal character ${\chi}$ of modulus ${q}$ , where we assume ${x \geq q^C}$ for some large ${C}$ ; for the principal character establish the same formula with an additional term of ${x}$ on the right-hand side. (Hint: this is almost immediate from Exercise 45(iv) and Theorem 21 ofNotes 2) with (say) ${T := q^2}$ , except that there is a factor of ${\log^2 x}$ in the error term instead of ${\log^2 q}$ when ${x}$ is extremely large compared to ${q}$ . However, a closer inspection of the proof (particularly with regards to the truncated Perron formula in Proposition 12 of Notes 2) shows that the ${\log^2 x}$ factor can be replaced fairly easily by ${\log x \log q}$ . To get rid of the final factor of ${\log x}$ , note that the proof of Proposition 12 used the rather crude bound ${\Lambda(n) = O(\log n)}$ . If one replaces this crude bound by more sophisticated tools such as the Brun-Titchmarsh inequality, one will be able to remove the factor of ${\log x}$ .

Using the Fourier inversion formula

$\displaystyle 1_{n = a\ (q)} = \frac{1}{\phi(q)} \sum_{\chi\ (q)} \overline{\chi(a)} \chi(n)$

(see Theorem 69 of Notes 1), we thus have

$\displaystyle \psi(x;a,q) = \frac{x}{\phi(q)} ( 1 - \sum_{\chi\ (q)} \overline{\chi(a)} \sum_{\hbox{Re}(\rho) > 3/4; |\hbox{Im}(\rho)| \leq q^2; L(\rho,\chi)=0} \frac{x^{\rho-1}}{\rho}$

$\displaystyle + O( \frac{\log^2 q}{q} ) )$

and so it suffices by the triangle inequality (bounding ${1/\rho}$ very crudely by ${O(1)}$ , as the contribution of the low-lying zeroes already turns out to be quite dominant) to show that

$\displaystyle \sum_{\chi\ (q)} \sum_{\sigma > 3/4; |t| \leq q^2; L(\sigma+it,\chi)=0} x^{\sigma-1} \ll \exp( - c \frac{\log x}{\log q} ) \ \ \ \ \ (2)$

when no exceptional zero is present, and

$\displaystyle \sum_{\chi\ (q)} \sum_{\sigma > 3/4; |t| \leq q^2; L(\sigma+it,\chi)=0; \sigma+it \neq \beta} x^{\sigma-1} \ll \exp( - c \frac{\log x}{\log q} \log \frac{1}{\varepsilon} ) \ \ \ \ \ (3)$

when an exceptional zero is present.

To handle the former case (2), one uses two facts about zeroes. The first is the classical zero-free region (Proposition 51 from Notes 2), which we reproduce in our context here:

Proposition 6 (Classical zero-free region) Let ${q, T \geq 2}$ . Apart from a potential exceptional zero ${\beta}$ , all zeroes ${\sigma+it}$ of ${L}$ -functions ${L(\cdot,\chi)}$ with ${\chi}$ of modulus ${q}$ and ${|t| \leq T}$ are such that

$\displaystyle \sigma \leq 1 - \frac{c}{\log qT}$

for some absolute constant ${c>0}$ .

Using this zero-free region, we have

$\displaystyle x^{\sigma-1} \ll \log x \int_{1/2}^{1-c/\log q} 1_{\alpha < \sigma} x^{\alpha-1}\ d\alpha$

whenever ${\sigma}$ contributes to the sum in (2), and so the left-hand side of (2) is bounded by

$\displaystyle \ll \log x \int_{1/2}^{1 - c/\log q} N( \alpha, q, q^2 ) x^{\alpha-1}\ d\alpha$

where we recall that ${N(\alpha,q,T)}$ is the number of zeroes ${\sigma+it}$ of any ${L}$ -function of a character ${\chi}$ of modulus ${q}$ with ${\sigma \geq \alpha}$ and ${0 \leq t \leq T}$ (here we use conjugation symmetry to make ${t}$ non-negative, accepting a multiplicative factor of two).

In Exercise 25 of Notes 6, the grand density estimate

$\displaystyle N(\alpha,q,T) \ll (qT)^{4(1-\alpha)} \log^{O(1)}(qT) \ \ \ \ \ (4)$

is proven. If one inserts this bound into the above expression, one obtains a bound for (2) which is of the form

$\displaystyle \ll (\log^{O(1)} q) \exp( - c \frac{\log x}{\log q} ).$

Unfortunately this is off from what we need by a factor of ${\log^{O(1)} q}$ (and would lead to a weak form of Linnik’s theorem in which ${p}$ was bounded by ${O( \exp( \log^{O(1)} q ) )}$ rather than by ${q^{O(1)}}$ ). In the analogous problem for prime number theorems in short intervals, we could use the Vinogradov-Korobov zero-free region to compensate for this loss, but that region does not help here for the contribution of the low-lying zeroes with ${t = O(1)}$ , which as mentioned before give the dominant contribution. Fortunately, it is possible to remove this logarithmic loss from the zero-density side of things:

Theorem 7 (Log-free grand density estimate) For any ${q, T > 1}$ and ${1/2 \leq \alpha \leq 1}$ , one has

$\displaystyle N(\alpha,q,T) \ll (qT)^{O(1-\alpha)}.$

The implied constants are effective.

We prove this estimate below the fold. The proof follows the methods of the previous section, but one inserts various sieve weights to restrict sums over natural numbers to essentially become sums over “almost primes”, as this turns out to remove the logarithmic losses. (More generally, the trick of restricting to almost primes by inserting suitable sieve weights is quite useful for avoiding any unnecessary losses of logarithmic factors in analytic number theory estimates.)

Exercise 8 Use Theorem 7 to complete the proof of (2).

Now we turn to the case when there is an exceptional zero (3). The argument used to prove (2) applies here also, but does not gain the factor of ${\log \frac{1}{\varepsilon}}$ in the exponent. To achieve this, we need an additional tool, a version of the Deuring-Heilbronn repulsion phenomenon due to Linnik:

Theorem 9 (Deuring-Heilbronn repulsion phenomenon) Suppose ${q \geq 2}$ is such that there is an exceptional zero ${\beta = 1 - \frac{\varepsilon}{\log q}}$ with ${\varepsilon}$ small. Then all other zeroes ${\sigma+it}$ of ${L}$ -functions of modulus ${q}$ are such that

$\displaystyle \sigma \leq 1 - c \frac{\log \frac{1}{\varepsilon}}{\log(q(2+|t|))}.$

In other words, the exceptional zero enlarges the classical zero-free region by a factor of ${\log \frac{1}{\varepsilon}}$ . The implied constants are effective.

Exercise 10 Use Theorem 7 and Theorem 9 to complete the proof of (3), and thus Linnik’s theorem.

Exercise 11 Use Theorem 9 to give an alternate proof of (Tatuzawa’s version of) Siegel’s theorem (Theorem 62 of Notes 2). (Hint: if two characters have different moduli, then they can be made to have the same modulus by multiplying by suitable principal characters.)

Theorem 9 is proven by similar methods to that of Theorem 7, the basic idea being to insert a further weight of ${1 * \chi_1}$ (in addition to the sieve weights), the point being that the exceptional zero causes this weight to be quite small on the average. There is a strengthening of Theorem 9 due to Bombieri that is along the lines of Theorem 7, obtaining the improvement

$\displaystyle N'(\alpha,q,T) \ll \varepsilon (1 + \frac{\log T}{\log q}) (qT)^{O(1-\alpha)} \ \ \ \ \ (5)$

with effective implied constants for any ${1/2 \leq \alpha \leq 1}$ and ${T \geq 1}$ in the presence of an exceptional zero, where the prime in ${N'(\alpha,q,T)}$ means that the exceptional zero ${\beta}$ is omitted (thus ${N'(\alpha,q,T) = N(\alpha,q,T)-1}$ if ${\alpha \leq \beta}$ ). Note that the upper bound on ${N'(\alpha,q,T)}$ falls below one when ${\alpha > 1 - c \frac{\log \frac{1}{\varepsilon}}{\log(qT)}}$ for a sufficiently small ${c>0}$ , thus recovering Theorem 9. Bombieri’s theorem can be established by the methods in this set of notes, and will be given as an exercise to the reader.

Remark 12 There are a number of alternate ways to derive the results in this set of notes, for instance using the Turan power sums method which is based on studying derivatives such as

$\displaystyle \frac{L'}{L}(s,\chi)^{(k)} = (-1)^k \sum_n \frac{\Lambda(n) \chi(n) \log^k n}{n^s}$

$\displaystyle \approx (-1)^{k+1} k! \sum_\rho \frac{1}{(s-\rho)^{k+1}}$

for ${\hbox{Re}(s)>1}$ and large ${k}$ , and performing various sorts of averaging in ${k}$ to attenuate the contribution of many of the zeroes ${\rho}$ . We will not develop this method here, but see for instance Chapter 9 of Montgomery’s book. See the text of Friedlander and Iwaniec for yet another approach based primarily on sieve-theoretic ideas.

Remark 13 When one optimises all the exponents, it turns out that the exponent in Linnik’s theorem is extremely good in the presence of an exceptional zero – indeed Friedlander and Iwaniec showed can even get a bound of the form ${p \ll q^{2-c}}$ for some ${c>0}$ , which is even stronger than one can obtain from GRH! There are other places in which exceptional zeroes can be used to obtain results stronger than what one can obtain even on the Riemann hypothesis; for instance, Heath-Brown used the hypothesis of an infinite sequence of Siegel zeroes to obtain the twin prime conejcture.

Read the rest of this entry »

Large gaps between consecutive prime numbers

21 August, 2014 in math.NT, paper | Tags: arithmetic progressions, prime gaps | by Terence Tao | 44 comments

Kevin Ford, Ben Green, Sergei Konyagin, and myself have just posted to the arXiv our preprint “Large gaps between consecutive prime numbers“. This paper concerns the “opposite” problem to that considered by the recently concluded Polymath8 project, which was concerned with very small values of the prime gap ${p_{n+1}-p_n}$ . Here, we wish to consider the largest prime gap ${G(X) = p_{n+1}-p_n}$ that one can find in the interval ${[X] = \{1,\dots,X\}}$ as ${X}$ goes to infinity.

Finding lower bounds on ${G(X)}$ is more or less equivalent to locating long strings of consecutive composite numbers that are not too large compared to the length of the string. A classic (and quite well known) construction here starts with the observation that for any natural number ${n}$ , the consecutive numbers ${n!+2, n!+3,\dots,n!+n}$ are all composite, because each ${n!+i}$ , ${i=2,\dots,n}$ is divisible by some prime ${p \leq n}$ , while being strictly larger than that prime ${p}$ . From this and Stirling’s formula, it is not difficult to obtain the bound

$\displaystyle G(X) \gg \frac{\log X}{\log\log X}. \ \ \ \ \ (1)$

A more efficient bound comes from the prime number theorem: there are only ${(1+o(1)) \frac{X}{\log X}}$ primes up to ${X}$ , so just from the pigeonhole principle one can locate a string of consecutive composite numbers up to ${X}$ of length at least ${(1-o(1)) \log X}$ , thus

$\displaystyle G(X) \gtrsim \log X \ \ \ \ \ (2)$

where we use ${X \gtrsim Y}$ or ${Y \lesssim X}$ as shorthand for ${X \geq (1-o(1)) Y}$ or ${Y \leq (1+o(1)) X}$ .

What about upper bounds? The Cramér random model predicts that the primes up to ${X}$ are distributed like a random subset ${\{1,\dots,X\}}$ of density ${1/\log X}$ . Using this model, Cramér arrived at the conjecture

$\displaystyle G(X) \ll \log^2 X.$

In fact, if one makes the extremely optimistic assumption that the random model perfectly describes the behaviour of the primes, one would arrive at the even more precise prediction

$\displaystyle G(X) \sim \log^2 X.$

However, it is no longer widely believed that this optimistic version of the conjecture is true, due to some additional irregularities in the primes coming from the basic fact that large primes cannot be divisible by very small primes. Using the Maier matrix method to capture some of this irregularity, Granville was led to the conjecture that

$\displaystyle G(X) \gtrsim 2e^{-\gamma} \log^2 X$

(note that ${2e^{-\gamma} = 1.1229\dots}$ is slightly larger than ${1}$ ). For comparison, the known upper bounds on ${G(X)}$ are quite weak; unconditionally one has ${G(X) \ll X^{0.525}}$ by the work of Baker, Harman, and Pintz, and even on the Riemann hypothesis one only gets down to ${G(X) \ll X^{1/2} \log X}$ , as shown by Cramér (a slight improvement is also possible if one additionally assumes the pair correlation conjecture; see this article of Heath-Brown and the references therein).

This conjecture remains out of reach of current methods. In 1931, Westzynthius managed to improve the bound (2) slightly to

$\displaystyle G(X) \gg \frac{\log\log\log X}{\log\log\log\log X} \log X ,$

which Erdös in 1935 improved to

$\displaystyle G(X) \gg \frac{\log\log X}{(\log\log\log X)^2} \log X$

and Rankin in 1938 improved slightly further to

$\displaystyle G(X) \gtrsim c \frac{(\log\log X) \log\log\log\log X}{(\log\log\log X)^2} \log X \ \ \ \ \ (3)$

with ${c=1/3}$ . Remarkably, this rather strange bound then proved extremely difficult to advance further on; until recently, the only improvements were to the constant ${c}$ , which was raised to ${c=\frac{1}{2} e^\gamma}$ in 1963 by Schönhage, to ${c= e^\gamma}$ in 1963 by Rankin, to ${c = 1.31256 e^\gamma}$ by Maier and Pomerance, and finally to ${c = 2e^\gamma}$ in 1997 by Pintz.

Erdös listed the problem of making ${c}$ arbitrarily large one of his favourite open problems, even offering (“somewhat rashly”, in his words) a cash prize for the solution. Our main result answers this question in the affirmative:

Theorem 1 The bound (3) holds for arbitrarily large ${c>0}$ .

In principle, we thus have a bound of the form

$\displaystyle G(X) \geq f(X) \frac{(\log\log X) \log\log\log\log X}{(\log\log\log X)^2} \log X$

for some ${f(X)}$ that grows to infinity. Unfortunately, due to various sources of ineffectivity in our methods, we cannot provide any explicit rate of growth on ${f(X)}$ at all.

We decided to announce this result the old-fashioned way, as part of a research lecture; more precisely, Ben Green announced the result in his ICM lecture this Tuesday. (The ICM staff have very efficiently put up video of his talks (and most of the other plenary and prize talks) online; Ben’s talk is here, with the announcement beginning at about 0:48. Note a slight typo in his slides, in that the exponent of ${\log\log\log X}$ in the denominator is ${3}$ instead of ${2}$ .) Ben’s lecture slides may be found here.

By coincidence, an independent proof of this theorem has also been obtained very recently by James Maynard.

I discuss our proof method below the fold.

Read the rest of this entry »

New bounds for Szemeredi’s theorem, Ia: Progressions of length 4 in finite field geometries revisited

8 May, 2012 in math.CO, paper | Tags: arithmetic progressions, Ben Green, finite fields, Szemeredi's theorem | by Terence Tao | 7 comments

Ben Green and I have just uploaded to the arXiv our paper “New bounds for Szemeredi’s theorem, Ia: Progressions of length 4 in finite field geometries revisited“, submitted to Proc. Lond. Math. Soc.. This is both an erratum to, and a replacement for, our previous paper “New bounds for Szemeredi’s theorem. I. Progressions of length 4 in finite field geometries“. The main objective in both papers is to bound the quantity ${r_4(F^n)}$ for a vector space ${F^n}$ over a finite field ${F}$ of characteristic greater than ${4}$ , where ${r_4(F^n)}$ is defined as the cardinality of the largest subset of ${F^n}$ that does not contain an arithmetic progression of length ${4}$ . In our earlier paper, we gave two arguments that bounded ${r_4(F^n)}$ in the regime when the field ${F}$ was fixed and ${n}$ was large. The first “cheap” argument gave the bound

$\displaystyle r_4(F^n) \ll |F|^n \exp( - c \sqrt{\log n} )$

and the more complicated “expensive” argument gave the improvement

$\displaystyle r_4(F^n) \ll |F|^n n^{-c} \ \ \ \ \ (1)$

for some constant ${c>0}$ depending only on ${F}$ .

Unfortunately, while the cheap argument is correct, we discovered a subtle but serious gap in our expensive argument in the original paper. Roughly speaking, the strategy in that argument is to employ the density increment method: one begins with a large subset ${A}$ of ${F^n}$ that has no arithmetic progressions of length ${4}$ , and seeks to locate a subspace on which ${A}$ has a significantly increased density. Then, by using a “Koopman-von Neumann theorem”, ultimately based on an iteration of the inverse ${U^3}$ theorem of Ben and myself (and also independently by Samorodnitsky), one approximates ${A}$ by a “quadratically structured” function ${f}$ , which is (locally) a combination of a bounded number of quadratic phase functions, which one can prepare to be in a certain “locally equidistributed” or “locally high rank” form. (It is this reduction to the high rank case that distinguishes the “expensive” argument from the “cheap” one.) Because ${A}$ has no progressions of length ${4}$ , the count of progressions of length ${4}$ weighted by ${f}$ will also be small; by combining this with the theory of equidistribution of quadratic phase functions, one can then conclude that there will be a subspace on which ${f}$ has increased density.

The error in the paper was to conclude from this that the original function ${1_A}$ also had increased density on the same subspace; it turns out that the manner in which ${f}$ approximates ${1_A}$ is not strong enough to deduce this latter conclusion from the former. (One can strengthen the nature of approximation until one restores such a conclusion, but only at the price of deteriorating the quantitative bounds on ${r_4(F^n)}$ one gets at the end of the day to be worse than the cheap argument.)

After trying unsuccessfully to repair this error, we eventually found an alternate argument, based on earlier papers of ourselves and of Bergelson-Host-Kra, that avoided the density increment method entirely and ended up giving a simpler proof of a stronger result than (1), and also gives the explicit value of ${c = 2^{-22}}$ for the exponent ${c}$ in (1). In fact, it gives the following stronger result:

Theorem 1 Let ${A}$ be a subset of ${F^n}$ of density at least ${\alpha}$ , and let ${\epsilon>0}$ . Then there is a subspace ${W}$ of ${F^n}$ of codimension ${O( \epsilon^{-2^{20}})}$ such that the number of (possibly degenerate) progressions ${a, a+r, a+2r, a+3r}$ in ${A \cap W}$ is at least ${(\alpha^4-\epsilon)|W|^2}$ .

The bound (1) is an easy consequence of this theorem after choosing ${\epsilon := \alpha^4/2}$ and removing the degenerate progressions from the conclusion of the theorem.

The main new idea is to work with a local Koopman-von Neumann theorem rather than a global one, trading a relatively weak global approximation to ${1_A}$ with a significantly stronger local approximation to ${1_A}$ on a subspace ${W}$ . This is somewhat analogous to how sometimes in graph theory it is more efficient (from the point of view of quantative estimates) to work with a local version of the Szemerédi regularity lemma which gives just a single regular pair of cells, rather than attempting to regularise almost all of the cells. This local approach is well adapted to the inverse ${U^3}$ theorem we use (which also has this local aspect), and also makes the reduction to the high rank case much cleaner. At the end of the day, one ends up with a fairly large subspace ${W}$ on which ${A}$ is quite dense (of density ${\alpha-O(\epsilon)}$ ) and which can be well approximated by a “pure quadratic” object, namely a function of a small number of quadratic phases obeying a high rank condition. One can then exploit a special positivity property of the count of length four progressions weighted by pure quadratic objects, essentially due to Bergelson-Host-Kra, which then gives the required lower bound.

254B, Lecture Notes 7: The transference principle, and linear equations in primes

5 June, 2010 in 254B - Higher order Fourier analysis, math.CO, math.NT | Tags: arithmetic progressions, Green-Tao theorem, prime numbers, pseudorandomness, Selberg sieve, transference principle | by Terence Tao | 4 comments

In this, the final lecture notes of this course, we discuss one of the motivating applications of the theory developed thus far, namely to count solutions to linear equations in primes ${{\mathcal P} = \{2,3,5,7,\ldots\}}$ (or in dense subsets ${A}$ of primes ${{\mathcal P}}$ ). Unfortunately, the most famous linear equations in primes: the twin prime equation ${p_2 - p_1 = 2}$ and the even Goldbach equation ${p_1+p_2=N}$ – remain out of reach of this technology (because the relevant affine linear forms involved are commensurate, and thus have infinite complexity with respect to the Gowers norms), but most other systems of equations, in particular that of arithmetic progressions ${p_i = n+ir}$ for ${i=0,\ldots,k-1}$ (or equivalently, ${p_i + p_{i+2} = 2p_{i+1}}$ for ${i=0,\ldots,k-2}$ ) , as well as the odd Goldbach equation ${p_1+p_2+p_3=N}$ , are tractable.

To illustrate the main ideas, we will focus on the following result of Green:

Theorem 1 (Roth’s theorem in the primes) Let ${A \subset {\mathcal P}}$ be a subset of primes whose upper density ${\limsup_{N \rightarrow \infty} |A \cap [N]|/|{\mathcal P} \cap [N]|}$ is positive. Then ${A}$ contains infinitely many arithmetic progressions of length three.

This should be compared with Roth’s theorem in the integers (Notes 2), which is the same statement but with the primes ${{\mathcal P}}$ replaced by the integers ${{\bf Z}}$ (or natural numbers ${{\bf N}}$ ). Indeed, Roth’s theorem for the primes is proven by transferring Roth’s theorem for the integers to the prime setting; the latter theorem is used as a “black box”. The key difficulty here in performing this transference is that the primes have zero density inside the integers; indeed, from the prime number theorem we have ${|{\mathcal P} \cap [N]| = (1+o(1)) \frac{N}{\log N} = o(N)}$ .

There are a number of generalisations of this transference technique. In a paper of Green and myself, we extended the above theorem to progressions of longer length (thus transferring Szemerédi’s theorem to the primes). In a series of papers (culminating in a paper to appear shortly) of Green, myself, and also Ziegler, related methods are also used to obtain an asymptotic for the number of solutions in the primes to any system of linear equations of bounded complexity. This latter result uses the full power of higher order Fourier analysis, in particular relying heavily on the inverse conjecture for the Gowers norms; in contrast, Roth’s theorem and Szemerédi’s theorem in the primes are “softer” results that do not need this conjecture.

To transfer results from the integers to the primes, there are three basic steps:

A general transference principle, that transfers certain types of additive combinatorial results from dense subsets of the integers to dense subsets of a suitably “pseudorandom set” of integers (or more precisely, to the integers weighted by a suitably “pseudorandom measure”);
An application of sieve theory to show that the primes (or more precisely, an affine modification of the primes) lie inside a suitably pseudorandom set of integers (or more precisely, have significant mass with respect to a suitably pseudorandom measure).
If one is seeking asymptotics for patterns in the primes, and not simply lower bounds, one also needs to control correlations between the primes (or proxies for the primes, such as the Möbius function) with various objects that arise from higher order Fourier analysis, such as nilsequences.

The former step can be accomplished in a number of ways. For progressions of length three (and more generally, for controlling linear patterns of complexity at most one), transference can be accomplished by Fourier-analytic methods. For more complicated patterns, one can use techniques inspired by ergodic theory; more recently, simplified and more efficient methods based on duality (the Hahn-Banach theorem) have also been used. No number theory is used in this step. (In the case of transference to genuinely random sets, rather than pseudorandom sets, similar ideas appeared earlier in the graph theory setting, see this paper of Kohayakawa, Luczak, and Rodl.

The second step is accomplished by fairly standard sieve theory methods (e.g. the Selberg sieve, or the slight variants of this sieve used by Goldston and Yildirim). Remarkably, very little of the formidable apparatus of modern analytic number theory is needed for this step; for instance, the only fact about the Riemann zeta function that is truly needed is that it has a simple pole at ${s=1}$ , and no knowledge of L-functions is needed.

The third step does draw more significantly on analytic number theory techniques and results (most notably, the method of Vinogradov to compute oscillatory sums over the primes, and also the Siegel-Walfisz theorem that gives a good error term on the prime number theorem in arithemtic progressions). As these techniques are somewhat orthogonal to the main topic of this course, we shall only touch briefly on this aspect of the transference strategy.

Read the rest of this entry »

Marker lectures II, “Linear equations in primes”

18 November, 2008 in math.CO, math.DS, math.NT, talk, travel | Tags: arithmetic progressions, Ben Green, Gowers norms, linear equations, Marker lecture, prime numbers | by Terence Tao | 6 comments

This week I am at Penn State University, giving this year’s Marker lectures. My chosen theme for my four lectures here is “recent developments in additive prime number theory”. My first lecture, “Long arithmetic progressions in primes”, is similar to my AMS lecture on the same topic and so I am not reposting it here. The second lecture, the notes for which begin after the fold, is on “Linear equations in primes”. These two lectures focus primarily on work of myself and Ben Green. The third and fourth lectures, entitled “Small gaps between primes” and “Sieving for almost primes and expander graphs”, will instead be focused on the work of Goldston-Yildirim-Pintz and Bourgain-Gamburd-Sarnak respectively.
Read the rest of this entry »

AMS lecture: Structure and randomness in the prime numbers

7 January, 2008 in math.NT, talk | Tags: American Mathematical Society, arithmetic progressions, Endre Szemeredi, Green-Tao theorem, prime numbers, Steele prize | by Terence Tao | 18 comments

This week I am in San Diego for the annual joint mathematics meeting of the American Mathematical Society and the Mathematical Association of America. I am giving two talks here. One is a lecture (for the AMS “Current Events” Bulletin) on recent developments (by Martel-Merle, Merle-Raphael, and others) on stability of solitons; I will post on that lecture at some point in the near future, once the survey paper associated to that lecture is finalised.
The other, which I am presenting here, is an address on “structure and randomness in the prime numbers“. Of course, I’ve talked about this general topic many times before, (e.g. at my Simons lecture at MIT, my Milliman lecture at U. Washington, and my Science Research Colloquium at UCLA), and I have given similar talks to the one here – which focuses on my original 2004 paper with Ben Green on long arithmetic progressions in the primes – about a dozen or so times. As such, this particular talk has probably run its course, and so I am “retiring” it by posting it here.

p.s. At this meeting, Endre Szemerédi was awarded the 2008 Steele prize for a seminal contribution to research, for his landmark paper establishing what is now known as Szemerédi’s theorem, which underlies the result I discuss in this talk. This prize is richly deserved – congratulations Endre! [The AMS and MAA also awarded prizes to several dozen other mathematicians, including many mentioned previously on this blog; rather than list them all here, let me just point you to their prize booklet.]

Read the rest of this entry »

Simons Lecture I: Structure and randomness in Fourier analysis and number theory

5 April, 2007 in math.CA, math.NT, talk, travel | Tags: arithmetic progressions, Fourier analysis, randomness, sieve theory, Simons lecture, structure | by Terence Tao | 44 comments

This week I am in Boston, giving this year’s Simons lectures at MIT together with David Donoho. (These lectures, incidentally, are endowed by Jim Simons, who was mentioned in some earlier discussion here.) While preparing these lectures, it occurred to me that I may as well post my lecture notes on this blog, since this medium is essentially just an asynchronous version of a traditional lecture series, and the hypertext capability is in some ways more convenient and informal than, say, $\LaTeX$ slides.

I am giving three lectures, each expounding on some aspects of the theme “the dichotomy between structure and randomness”, which I also spoke about (and wrote about) for the ICM last August. This theme seems to pervade many of the areas of mathematics that I work in, and my lectures aim to explore how this theme manifests itself in several of these. In this, the first lecture, I describe the dichotomy as it appears in Fourier analysis and in number theory. (In the second, I discuss the dichotomy in ergodic theory and graph theory, while in the third, I discuss PDE.)

Read the rest of this entry »

	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

The Gowers uniformity norm of order 1+

New bounds for Szemerédi’s theorem, III: A polylogarithmic bound for r_4(N)

A remark on the lonely runner conjecture

254A, Notes 7: Linnik’s theorem on primes in arithmetic progressions

Large gaps between consecutive prime numbers

New bounds for Szemeredi’s theorem, Ia: Progressions of length 4 in finite field geometries revisited

254B, Lecture Notes 7: The transference principle, and linear equations in primes

Marker lectures II, “Linear equations in primes”

AMS lecture: Structure and randomness in the prime numbers

Simons Lecture I: Structure and randomness in Fourier analysis and number theory

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

For commenters