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

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}$.

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. Recall from the truncated explicit formula (Exercise 45(iv) of Notes 2) with (say) ${T := q^2}$ 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 one has the same formula with an additional term of ${x}$ on the right-hand side (as is easily deduced from Theorem 21 of Notes 2). 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 5 (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 6 (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 7 Use Theorem 6 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 8 (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 9 Use Theorem 6 and Theorem 8 to complete the proof of (3), and thus Linnik’s theorem.

Exercise 10 Use Theorem 8 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 8 is proven by similar methods to that of Theorem 6, 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 8 due to Bombieri that is along the lines of Theorem 6, 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 8. 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 11 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 12 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.

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.

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.

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.

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 »

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.]

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.)