You are currently browsing the category archive for the ‘math.PR’ category.

I’ve just uploaded to the arXiv my paper “Almost all Collatz orbits attain almost bounded values“, submitted to the proceedings of the Forum of Mathematics, Pi. In this paper I returned to the topic of the notorious Collatz conjecture (also known as the ${3x+1}$ conjecture), which I previously discussed in this blog post. This conjecture can be phrased as follows. Let ${{\bf N}+1 = \{1,2,\dots\}}$ denote the positive integers (with ${{\bf N} =\{0,1,2,\dots\}}$ the natural numbers), and let ${\mathrm{Col}: {\bf N}+1 \rightarrow {\bf N}+1}$ be the map defined by setting ${\mathrm{Col}(N)}$ equal to ${3N+1}$ when ${N}$ is odd and ${N/2}$ when ${N}$ is even. Let ${\mathrm{Col}_{\min}(N) := \inf_{n \in {\bf N}} \mathrm{Col}^n(N)}$ be the minimal element of the Collatz orbit ${N, \mathrm{Col}(N), \mathrm{Col}^2(N),\dots}$. Then we have

Conjecture 1 (Collatz conjecture) One has ${\mathrm{Col}_{\min}(N)=1}$ for all ${N \in {\bf N}+1}$.

Establishing the conjecture for all ${N}$ remains out of reach of current techniques (for instance, as discussed in the previous blog post, it is basically at least as difficult as Baker’s theorem, all known proofs of which are quite difficult). However, the situation is more promising if one is willing to settle for results which only hold for “most” ${N}$ in some sense. For instance, it is a result of Krasikov and Lagarias that

$\displaystyle \{ N \leq x: \mathrm{Col}_{\min}(N) = 1 \} \gg x^{0.84}$

for all sufficiently large ${x}$. In another direction, it was shown by Terras that for almost all ${N}$ (in the sense of natural density), one has ${\mathrm{Col}_{\min}(N) < N}$. This was then improved by Allouche to ${\mathrm{Col}_{\min}(N) < N^\theta}$ for almost all ${N}$ and any fixed ${\theta > 0.869}$, and extended later by Korec to cover all ${\theta > \frac{\log 3}{\log 4} \approx 0.7924}$. In this paper we obtain the following further improvement (at the cost of weakening natural density to logarithmic density):

Theorem 2 Let ${f: {\bf N}+1 \rightarrow {\bf R}}$ be any function with ${\lim_{N \rightarrow \infty} f(N) = +\infty}$. Then we have ${\mathrm{Col}_{\min}(N) < f(N)}$ for almost all ${N}$ (in the sense of logarithmic density).

Thus for instance one has ${\mathrm{Col}_{\min}(N) < \log\log\log\log N}$ for almost all ${N}$ (in the sense of logarithmic density).

The difficulty here is one usually only expects to establish “local-in-time” results that control the evolution ${\mathrm{Col}^n(N)}$ for times ${n}$ that only get as large as a small multiple ${c \log N}$ of ${\log N}$; the aforementioned results of Terras, Allouche, and Korec, for instance, are of this time. However, to get ${\mathrm{Col}^n(N)}$ all the way down to ${f(N)}$ one needs something more like an “(almost) global-in-time” result, where the evolution remains under control for so long that the orbit has nearly reached the bounded state ${N=O(1)}$.

However, as observed by Bourgain in the context of nonlinear Schrödinger equations, one can iterate “almost sure local wellposedness” type results (which give local control for almost all initial data from a given distribution) into “almost sure (almost) global wellposedness” type results if one is fortunate enough to draw one’s data from an invariant measure for the dynamics. To illustrate the idea, let us take Korec’s aforementioned result that if ${\theta > \frac{\log 3}{\log 4}}$ one picks at random an integer ${N}$ from a large interval ${[1,x]}$, then in most cases, the orbit of ${N}$ will eventually move into the interval ${[1,x^{\theta}]}$. Similarly, if one picks an integer ${M}$ at random from ${[1,x^\theta]}$, then in most cases, the orbit of ${M}$ will eventually move into ${[1,x^{\theta^2}]}$. It is then tempting to concatenate the two statements and conclude that for most ${N}$ in ${[1,x]}$, the orbit will eventually move ${[1,x^{\theta^2}]}$. Unfortunately, this argument does not quite work, because by the time the orbit from a randomly drawn ${N \in [1,x]}$ reaches ${[1,x^\theta]}$, the distribution of the final value is unlikely to be close to being uniformly distributed on ${[1,x^\theta]}$, and in particular could potentially concentrate almost entirely in the exceptional set of ${M \in [1,x^\theta]}$ that do not make it into ${[1,x^{\theta^2}]}$. The point here is the uniform measure on ${[1,x]}$ is not transported by Collatz dynamics to anything resembling the uniform measure on ${[1,x^\theta]}$.

So, one now needs to locate a measure which has better invariance properties under the Collatz dynamics. It turns out to be technically convenient to work with a standard acceleration of the Collatz map known as the Syracuse map ${\mathrm{Syr}: 2{\bf N}+1 \rightarrow 2{\bf N}+1}$, defined on the odd numbers ${2{\bf N}+1 = \{1,3,5,\dots\}}$ by setting ${\mathrm{Syr}(N) = (3N+1)/2^a}$, where ${2^a}$ is the largest power of ${2}$ that divides ${3N+1}$. (The advantage of using the Syracuse map over the Collatz map is that it performs precisely one multiplication of ${3}$ at each iteration step, which makes the map better behaved when performing “${3}$-adic” analysis.)

When viewed ${3}$-adically, we soon see that iterations of the Syracuse map become somewhat irregular. Most obviously, ${\mathrm{Syr}(N)}$ is never divisible by ${3}$. A little less obviously, ${\mathrm{Syr}(N)}$ is twice as likely to equal ${2}$ mod ${3}$ as it is to equal ${1}$ mod ${3}$. This is because for a randomly chosen odd ${\mathbf{N}}$, the number of times ${\mathbf{a}}$ that ${2}$ divides ${3\mathbf{N}+1}$ can be seen to have a geometric distribution of mean ${2}$ – it equals any given value ${a \in{\bf N}+1}$ with probability ${2^{-a}}$. Such a geometric random variable is twice as likely to be odd as to be even, which is what gives the above irregularity. There are similar irregularities modulo higher powers of ${3}$. For instance, one can compute that for large random odd ${\mathbf{N}}$, ${\mathrm{Syr}^2(\mathbf{N}) \hbox{ mod } 9}$ will take the residue classes ${0,1,2,3,4,5,6,7,8 \hbox{ mod } 9}$ with probabilities

$\displaystyle 0, \frac{8}{63}, \frac{16}{63}, 0, \frac{11}{63}, \frac{4}{63}, 0, \frac{2}{63}, \frac{22}{63}$

respectively. More generally, for any ${n}$, ${\mathrm{Syr}^n(N) \hbox{ mod } 3^n}$ will be distributed according to the law of a random variable ${\mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$ on ${{\bf Z}/3^n{\bf Z}}$ that we call a Syracuse random variable, and can be described explicitly as

$\displaystyle \mathbf{Syrac}({\bf Z}/3^n{\bf Z}) = 2^{-\mathbf{a}_1} + 3^1 2^{-\mathbf{a}_1-\mathbf{a}_2} + \dots + 3^{n-1} 2^{-\mathbf{a}_1-\dots-\mathbf{a}_n} \hbox{ mod } 3^n, \ \ \ \ \ (1)$

where ${\mathbf{a}_1,\dots,\mathbf{a}_n}$ are iid copies of a geometric random variable of mean ${2}$.

In view of this, any proposed “invariant” (or approximately invariant) measure (or family of measures) for the Syracuse dynamics should take this ${3}$-adic irregularity of distribution into account. It turns out that one can use the Syracuse random variables ${\mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$ to construct such a measure, but only if these random variables stabilise in the limit ${n \rightarrow \infty}$ in a certain total variation sense. More precisely, in the paper we establish the estimate

$\displaystyle \sum_{Y \in {\bf Z}/3^n{\bf Z}} | \mathbb{P}( \mathbf{Syrac}({\bf Z}/3^n{\bf Z})=Y) - 3^{m-n} \mathbb{P}( \mathbf{Syrac}({\bf Z}/3^m{\bf Z})=Y \hbox{ mod } 3^m)| \ \ \ \ \ (2)$

$\displaystyle \ll_A m^{-A}$

for any ${1 \leq m \leq n}$ and any ${A > 0}$. This type of stabilisation is plausible from entropy heuristics – the tuple ${(\mathbf{a}_1,\dots,\mathbf{a}_n)}$ of geometric random variables that generates ${\mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$ has Shannon entropy ${n \log 4}$, which is significantly larger than the total entropy ${n \log 3}$ of the uniform distribution on ${{\bf Z}/3^n{\bf Z}}$, so we expect a lot of “mixing” and “collision” to occur when converting the tuple ${(\mathbf{a}_1,\dots,\mathbf{a}_n)}$ to ${\mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$; these heuristics can be supported by numerics (which I was able to work out up to about ${n=10}$ before running into memory and CPU issues), but it turns out to be surprisingly delicate to make this precise.

A first hint of how to proceed comes from the elementary number theory observation (easily proven by induction) that the rational numbers

$\displaystyle 2^{-a_1} + 3^1 2^{-a_1-a_2} + \dots + 3^{n-1} 2^{-a_1-\dots-a_n}$

are all distinct as ${(a_1,\dots,a_n)}$ vary over tuples in ${({\bf N}+1)^n}$. Unfortunately, the process of reducing mod ${3^n}$ creates a lot of collisions (as must happen from the pigeonhole principle); however, by a simple “Lefschetz principle” type argument one can at least show that the reductions

$\displaystyle 2^{-a_1} + 3^1 2^{-a_1-a_2} + \dots + 3^{m-1} 2^{-a_1-\dots-a_m} \hbox{ mod } 3^n \ \ \ \ \ (3)$

are mostly distinct for “typical” ${a_1,\dots,a_m}$ (as drawn using the geometric distribution) as long as ${m}$ is a bit smaller than ${\frac{\log 3}{\log 4} n}$ (basically because the rational number appearing in (3) then typically takes a form like ${M/2^{2m}}$ with ${M}$ an integer between ${0}$ and ${3^n}$). This analysis of the component (3) of (1) is already enough to get quite a bit of spreading on ${ \mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$ (roughly speaking, when the argument is optimised, it shows that this random variable cannot concentrate in any subset of ${{\bf Z}/3^n{\bf Z}}$ of density less than ${n^{-C}}$ for some large absolute constant ${C>0}$). To get from this to a stabilisation property (2) we have to exploit the mixing effects of the remaining portion of (1) that does not come from (3). After some standard Fourier-analytic manipulations, matters then boil down to obtaining non-trivial decay of the characteristic function of ${\mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$, and more precisely in showing that

$\displaystyle \mathbb{E} e^{-2\pi i \xi \mathbf{Syrac}({\bf Z}/3^n{\bf Z}) / 3^n} \ll_A n^{-A} \ \ \ \ \ (4)$

for any ${A > 0}$ and any ${\xi \in {\bf Z}/3^n{\bf Z}}$ that is not divisible by ${3}$.

If the random variable (1) was the sum of independent terms, one could express this characteristic function as something like a Riesz product, which would be straightforward to estimate well. Unfortunately, the terms in (1) are loosely coupled together, and so the characteristic factor does not immediately factor into a Riesz product. However, if one groups adjacent terms in (1) together, one can rewrite it (assuming ${n}$ is even for sake of discussion) as

$\displaystyle (2^{\mathbf{a}_2} + 3) 2^{-\mathbf{b}_1} + (2^{\mathbf{a}_4}+3) 3^2 2^{-\mathbf{b}_1-\mathbf{b}_2} + \dots$

$\displaystyle + (2^{\mathbf{a}_n}+3) 3^{n-2} 2^{-\mathbf{b}_1-\dots-\mathbf{b}_{n/2}} \hbox{ mod } 3^n$

where ${\mathbf{b}_j := \mathbf{a}_{2j-1} + \mathbf{a}_{2j}}$. The point here is that after conditioning on the ${\mathbf{b}_1,\dots,\mathbf{b}_{n/2}}$ to be fixed, the random variables ${\mathbf{a}_2, \mathbf{a}_4,\dots,\mathbf{a}_n}$ remain independent (though the distribution of each ${\mathbf{a}_{2j}}$ depends on the value that we conditioned ${\mathbf{b}_j}$ to), and so the above expression is a conditional sum of independent random variables. This lets one express the characeteristic function of (1) as an averaged Riesz product. One can use this to establish the bound (4) as long as one can show that the expression

$\displaystyle \frac{\xi 3^{2j-2} (2^{-\mathbf{b}_1-\dots-\mathbf{b}_j+1} \mod 3^n)}{3^n}$

is not close to an integer for a moderately large number (${\gg A \log n}$, to be precise) of indices ${j = 1,\dots,n/2}$. (Actually, for technical reasons we have to also restrict to those ${j}$ for which ${\mathbf{b}_j=3}$, but let us ignore this detail here.) To put it another way, if we let ${B}$ denote the set of pairs ${(j,l)}$ for which

$\displaystyle \frac{\xi 3^{2j-2} (2^{-l+1} \mod 3^n)}{3^n} \in [-\varepsilon,\varepsilon] + {\bf Z},$

we have to show that (with overwhelming probability) the random walk

$\displaystyle (1,\mathbf{b}_1), (2, \mathbf{b}_1 + \mathbf{b}_2), \dots, (n/2, \mathbf{b}_1+\dots+\mathbf{b}_{n/2})$

(which we view as a two-dimensional renewal process) contains at least a few points lying outside of ${B}$.

A little bit of elementary number theory and combinatorics allows one to describe the set ${B}$ as the union of “triangles” with a certain non-zero separation between them. If the triangles were all fairly small, then one expects the renewal process to visit at least one point outside of ${B}$ after passing through any given such triangle, and it then becomes relatively easy to then show that the renewal process usually has the required number of points outside of ${B}$. The most difficult case is when the renewal process passes through a particularly large triangle in ${B}$. However, it turns out that large triangles enjoy particularly good separation properties, and in particular afer passing through a large triangle one is likely to only encounter nothing but small triangles for a while. After making these heuristics more precise, one is finally able to get enough points on the renewal process outside of ${B}$ that one can finish the proof of (4), and thus Theorem 2.

William Banks, Kevin Ford, and I have just uploaded to the arXiv our paper “Large prime gaps and probabilistic models“. In this paper we introduce a random model to help understand the connection between two well known conjectures regarding the primes ${{\mathcal P} := \{2,3,5,\dots\}}$, the Cramér conjecture and the Hardy-Littlewood conjecture:

Conjecture 1 (Cramér conjecture) If ${x}$ is a large number, then the largest prime gap ${G_{\mathcal P}(x) := \sup_{p_n, p_{n+1} \leq x} p_{n+1}-p_n}$ in ${[1,x]}$ is of size ${\asymp \log^2 x}$. (Granville refines this conjecture to ${\gtrsim \xi \log^2 x}$, where ${\xi := 2e^{-\gamma} = 1.1229\dots}$. Here we use the asymptotic notation ${X \gtrsim Y}$ for ${X \geq (1-o(1)) Y}$, ${X \sim Y}$ for ${X \gtrsim Y \gtrsim X}$, ${X \gg Y}$ for ${X \geq C^{-1} Y}$, and ${X \asymp Y}$ for ${X \gg Y \gg X}$.)

Conjecture 2 (Hardy-Littlewood conjecture) If ${\mathcal{H} := \{h_1,\dots,h_k\}}$ are fixed distinct integers, then the number of numbers ${n \in [1,x]}$ with ${n+h_1,\dots,n+h_k}$ all prime is ${({\mathfrak S}(\mathcal{H}) +o(1)) \int_2^x \frac{dt}{\log^k t}}$ as ${x \rightarrow \infty}$, where the singular series ${{\mathfrak S}(\mathcal{H})}$ is defined by the formula

$\displaystyle {\mathfrak S}(\mathcal{H}) := \prod_p \left( 1 - \frac{|{\mathcal H} \hbox{ mod } p|}{p}\right) (1-\frac{1}{p})^{-k}.$

(One can view these conjectures as modern versions of two of the classical Landau problems, namely Legendre’s conjecture and the twin prime conjecture respectively.)

A well known connection between the Hardy-Littlewood conjecture and prime gaps was made by Gallagher. Among other things, Gallagher showed that if the Hardy-Littlewood conjecture was true, then the prime gaps ${p_{n+1}-p_n}$ with ${n \leq x}$ were asymptotically distributed according to an exponential distribution of mean ${\log x}$, in the sense that

$\displaystyle | \{ n: p_n \leq x, p_{n+1}-p_n \geq \lambda \log x \}| = (e^{-\lambda}+o(1)) \frac{x}{\log x} \ \ \ \ \ (1)$

as ${x \rightarrow \infty}$ for any fixed ${\lambda \geq 0}$. Roughly speaking, the way this is established is by using the Hardy-Littlewood conjecture to control the mean values of ${\binom{|{\mathcal P} \cap (p_n, p_n + \lambda \log x)|}{k}}$ for fixed ${k,\lambda}$, where ${p_n}$ ranges over the primes in ${[1,x]}$. The relevance of these quantities arises from the Bonferroni inequalities (or “Brun pure sieve“), which can be formulated as the assertion that

$\displaystyle 1_{N=0} \leq \sum_{k=0}^K (-1)^k \binom{N}{k}$

when ${K}$ is even and

$\displaystyle 1_{N=0} \geq \sum_{k=0}^K (-1)^k \binom{N}{k}$

when ${K}$ is odd, for any natural number ${N}$; setting ${N := |{\mathcal P} \cap (p_n, p_n + \lambda \log x)|}$ and taking means, one then gets upper and lower bounds for the probability that the interval ${(p_n, p_n + \lambda \log x)}$ is free of primes. The most difficult step is to control the mean values of the singular series ${{\mathfrak S}(\mathcal{H})}$ as ${{\mathcal H}}$ ranges over ${k}$-tuples in a fixed interval such as ${[0, \lambda \log x]}$.

Heuristically, if one extrapolates the asymptotic (1) to the regime ${\lambda \asymp \log x}$, one is then led to Cramér’s conjecture, since the right-hand side of (1) falls below ${1}$ when ${\lambda}$ is significantly larger than ${\log x}$. However, this is not a rigorous derivation of Cramér’s conjecture from the Hardy-Littlewood conjecture, since Gallagher’s computations only establish (1) for fixed choices of ${\lambda}$, which is only enough to establish the far weaker bound ${G_{\mathcal P}(x) / \log x \rightarrow \infty}$, which was already known (see this previous paper for a discussion of the best known unconditional lower bounds on ${G_{\mathcal P}(x)}$). An inspection of the argument shows that if one wished to extend (1) to parameter choices ${\lambda}$ that were allowed to grow with ${x}$, then one would need as input a stronger version of the Hardy-Littlewood conjecture in which the length ${k}$ of the tuple ${{\mathcal H} = (h_1,\dots,h_k)}$, as well as the magnitudes of the shifts ${h_1,\dots,h_k}$, were also allowed to grow with ${x}$. Our initial objective in this project was then to quantify exactly what strengthening of the Hardy-Littlewood conjecture would be needed to rigorously imply Cramer’s conjecture. The precise results are technical, but roughly we show results of the following form:

Theorem 3 (Large gaps from Hardy-Littlewood, rough statement)

• If the Hardy-Littlewood conjecture is uniformly true for ${k}$-tuples of length ${k \ll \frac{\log x}{\log\log x}}$, and with shifts ${h_1,\dots,h_k}$ of size ${O( \log^2 x )}$, with a power savings in the error term, then ${G_{\mathcal P}(x) \gg \frac{\log^2 x}{\log\log x}}$.
• If the Hardy-Littlewood conjecture is “true on average” for ${k}$-tuples of length ${k \ll \frac{y}{\log x}}$ and shifts ${h_1,\dots,h_k}$ of size ${y}$ for all ${\log x \leq y \leq \log^2 x \log\log x}$, with a power savings in the error term, then ${G_{\mathcal P}(x) \gg \log^2 x}$.

In particular, we can recover Cramer’s conjecture given a sufficiently powerful version of the Hardy-Littlewood conjecture “on the average”.

Our proof of this theorem proceeds more or less along the same lines as Gallagher’s calculation, but now with ${k}$ allowed to grow slowly with ${x}$. Again, the main difficulty is to accurately estimate average values of the singular series ${{\mathfrak S}({\mathfrak H})}$. Here we found it useful to switch to a probabilistic interpretation of this series. For technical reasons it is convenient to work with a truncated, unnormalised version

$\displaystyle V_{\mathcal H}(z) := \prod_{p \leq z} \left( 1 - \frac{|{\mathcal H} \hbox{ mod } p|}{p} \right)$

of the singular series, for a suitable cutoff ${z}$; it turns out that when studying prime tuples of size ${t}$, the most convenient cutoff ${z(t)}$ is the “Pólya magic cutoff“, defined as the largest prime for which

$\displaystyle \prod_{p \leq z(t)}(1-\frac{1}{p}) \geq \frac{1}{\log t} \ \ \ \ \ (2)$

(this is well defined for ${t \geq e^2}$); by Mertens’ theorem, we have ${z(t) \sim t^{1/e^\gamma}}$. One can interpret ${V_{\mathcal Z}(z)}$ probabilistically as

$\displaystyle V_{\mathcal Z}(z) = \mathbf{P}( {\mathcal H} \subset \mathcal{S}_z )$

where ${\mathcal{S}_z \subset {\bf Z}}$ is the randomly sifted set of integers formed by removing one residue class ${a_p \hbox{ mod } p}$ uniformly at random for each prime ${p \leq z}$. The Hardy-Littlewood conjecture can be viewed as an assertion that the primes ${{\mathcal P}}$ behave in some approximate statistical sense like the random sifted set ${\mathcal{S}_z}$, and one can prove the above theorem by using the Bonferroni inequalities both for the primes ${{\mathcal P}}$ and for the random sifted set, and comparing the two (using an even ${K}$ for the sifted set and an odd ${K}$ for the primes in order to be able to combine the two together to get a useful bound).

The proof of Theorem 3 ended up not using any properties of the set of primes ${{\mathcal P}}$ other than that this set obeyed some form of the Hardy-Littlewood conjectures; the theorem remains true (with suitable notational changes) if this set were replaced by any other set. In order to convince ourselves that our theorem was not vacuous due to our version of the Hardy-Littlewood conjecture being too strong to be true, we then started exploring the question of coming up with random models of ${{\mathcal P}}$ which obeyed various versions of the Hardy-Littlewood and Cramér conjectures.

This line of inquiry was started by Cramér, who introduced what we now call the Cramér random model ${{\mathcal C}}$ of the primes, in which each natural number ${n \geq 3}$ is selected for membership in ${{\mathcal C}}$ with an independent probability of ${1/\log n}$. This model matches the primes well in some respects; for instance, it almost surely obeys the “Riemann hypothesis”

$\displaystyle | {\mathcal C} \cap [1,x] | = \int_2^x \frac{dt}{\log t} + O( x^{1/2+o(1)})$

and Cramér also showed that the largest gap ${G_{\mathcal C}(x)}$ was almost surely ${\sim \log^2 x}$. On the other hand, it does not obey the Hardy-Littlewood conjecture; more precisely, it obeys a simplified variant of that conjecture in which the singular series ${{\mathfrak S}({\mathcal H})}$ is absent.

Granville proposed a refinement ${{\mathcal G}}$ to Cramér’s random model ${{\mathcal C}}$ in which one first sieves out (in each dyadic interval ${[x,2x]}$) all residue classes ${0 \hbox{ mod } p}$ for ${p \leq A}$ for a certain threshold ${A = \log^{1-o(1)} x = o(\log x)}$, and then places each surviving natural number ${n}$ in ${{\mathcal G}}$ with an independent probability ${\frac{1}{\log n} \prod_{p \leq A} (1-\frac{1}{p})^{-1}}$. One can verify that this model obeys the Hardy-Littlewood conjectures, and Granville showed that the largest gap ${G_{\mathcal G}(x)}$ in this model was almost surely ${\gtrsim \xi \log^2 x}$, leading to his conjecture that this bound also was true for the primes. (Interestingly, this conjecture is not yet borne out by numerics; calculations of prime gaps up to ${10^{18}}$, for instance, have shown that ${G_{\mathcal P}(x)}$ never exceeds ${0.9206 \log^2 x}$ in this range. This is not necessarily a conflict, however; Granville’s analysis relies on inspecting gaps in an extremely sparse region of natural numbers that are more devoid of primes than average, and this region is not well explored by existing numerics. See this previous blog post for more discussion of Granville’s argument.)

However, Granville’s model does not produce a power savings in the error term of the Hardy-Littlewood conjectures, mostly due to the need to truncate the singular series at the logarithmic cutoff ${A}$. After some experimentation, we were able to produce a tractable random model ${{\mathcal R}}$ for the primes which obeyed the Hardy-Littlewood conjectures with power savings, and which reproduced Granville’s gap prediction of ${\gtrsim \xi \log^2 x}$ (we also get an upper bound of ${\lesssim \xi \log^2 x \frac{\log\log x}{2 \log\log\log x}}$ for both models, though we expect the lower bound to be closer to the truth); to us, this strengthens the case for Granville’s version of Cramér’s conjecture. The model can be described as follows. We select one residue class ${a_p \hbox{ mod } p}$ uniformly at random for each prime ${p}$, and as before we let ${S_z}$ be the sifted set of integers formed by deleting the residue classes ${a_p \hbox{ mod } p}$ with ${p \leq z}$. We then set

$\displaystyle {\mathcal R} := \{ n \geq e^2: n \in S_{z(t)}\}$

with ${z(t)}$ Pólya’s magic cutoff (this is the cutoff that gives ${{\mathcal R}}$ a density consistent with the prime number theorem or the Riemann hypothesis). As stated above, we are able to show that almost surely one has

$\displaystyle \xi \log^2 x \lesssim {\mathcal G}_{\mathcal R}(x) \lesssim \xi \log^2 x \frac{\log\log x}{2 \log\log\log x} \ \ \ \ \ (3)$

and that the Hardy-Littlewood conjectures hold with power savings for ${k}$ up to ${\log^c x}$ for any fixed ${c < 1}$ and for shifts ${h_1,\dots,h_k}$ of size ${O(\log^c x)}$. This is unfortunately a tiny bit weaker than what Theorem 3 requires (which more or less corresponds to the endpoint ${c=1}$), although there is a variant of Theorem 3 that can use this input to produce a lower bound on gaps in the model ${{\mathcal R}}$ (but it is weaker than the one in (3)). In fact we prove a more precise almost sure asymptotic formula for ${{\mathcal G}_{\mathcal R}(x) }$ that involves the optimal bounds for the linear sieve (or interval sieve), in which one deletes one residue class modulo ${p}$ from an interval ${[0,y]}$ for all primes ${p}$ up to a given threshold. The lower bound in (3) relates to the case of deleting the ${0 \hbox{ mod } p}$ residue classes from ${[0,y]}$; the upper bound comes from the delicate analysis of the linear sieve by Iwaniec. Improving on either of the two bounds looks to be quite a difficult problem.

The probabilistic analysis of ${{\mathcal R}}$ is somewhat more complicated than of ${{\mathcal C}}$ or ${{\mathcal G}}$ as there is now non-trivial coupling between the events ${n \in {\mathcal R}}$ as ${n}$ varies, although moment methods such as the second moment method are still viable and allow one to verify the Hardy-Littlewood conjectures by a lengthy but fairly straightforward calculation. To analyse large gaps, one has to understand the statistical behaviour of a random linear sieve in which one starts with an interval ${[0,y]}$ and randomly deletes a residue class ${a_p \hbox{ mod } p}$ for each prime ${p}$ up to a given threshold. For very small ${p}$ this is handled by the deterministic theory of the linear sieve as discussed above. For medium sized ${p}$, it turns out that there is good concentration of measure thanks to tools such as Bennett’s inequality or Azuma’s inequality, as one can view the sieving process as a martingale or (approximately) as a sum of independent random variables. For larger primes ${p}$, in which only a small number of survivors are expected to be sieved out by each residue class, a direct combinatorial calculation of all possible outcomes (involving the random graph that connects interval elements ${n \in [0,y]}$ to primes ${p}$ if ${n}$ falls in the random residue class ${a_p \hbox{ mod } p}$) turns out to give the best results.

In a recent post I discussed how the Riemann zeta function ${\zeta}$ can be locally approximated by a polynomial, in the sense that for randomly chosen ${t \in [T,2T]}$ one has an approximation

$\displaystyle \zeta(\frac{1}{2} + it - \frac{2\pi i z}{\log T}) \approx P_t( e^{2\pi i z/N} ) \ \ \ \ \ (1)$

where ${N}$ grows slowly with ${T}$, and ${P_t}$ is a polynomial of degree ${N}$. Assuming the Riemann hypothesis (as we will throughout this post), the zeroes of ${P_t}$ should all lie on the unit circle, and one should then be able to write ${P_t}$ as a scalar multiple of the characteristic polynomial of (the inverse of) a unitary matrix ${U = U_t \in U(N)}$, which we normalise as

$\displaystyle P_t(Z) = \exp(A_t) \mathrm{det}(1 - ZU). \ \ \ \ \ (2)$

Here ${A_t}$ is some quantity depending on ${t}$. We view ${U}$ as a random element of ${U(N)}$; in the limit ${T \rightarrow \infty}$, the GUE hypothesis is equivalent to ${U}$ becoming equidistributed with respect to Haar measure on ${U(N)}$ (also known as the Circular Unitary Ensemble, CUE; it is to the unit circle what the Gaussian Unitary Ensemble (GUE) is on the real line). One can also view ${U}$ as analogous to the “geometric Frobenius” operator in the function field setting, though unfortunately it is difficult at present to make this analogy any more precise (due, among other things, to the lack of a sufficiently satisfactory theory of the “field of one element“).

Taking logarithmic derivatives of (2), we have

$\displaystyle -\frac{P'_t(Z)}{P_t(Z)} = \mathrm{tr}( U (1-ZU)^{-1} ) = \sum_{j=1}^\infty Z^{j-1} \mathrm{tr} U^j \ \ \ \ \ (3)$

and hence on taking logarithmic derivatives of (1) in the ${z}$ variable we (heuristically) have

$\displaystyle -\frac{2\pi i}{\log T} \frac{\zeta'}{\zeta}( \frac{1}{2} + it - \frac{2\pi i z}{\log T}) \approx \frac{2\pi i}{N} \sum_{j=1}^\infty e^{2\pi i jz/N} \mathrm{tr} U^j.$

Morally speaking, we have

$\displaystyle - \frac{\zeta'}{\zeta}( \frac{1}{2} + it - \frac{2\pi i z}{\log T}) = \sum_{n=1}^\infty \frac{\Lambda(n)}{n^{1/2+it}} e^{2\pi i z (\log n/\log T)}$

so on comparing coefficients we expect to interpret the moments ${\mathrm{tr} U^j}$ of ${U}$ as a finite Dirichlet series:

$\displaystyle \mathrm{tr} U^j \approx \frac{N}{\log T} \sum_{T^{(j-1)/N} < n \leq T^{j/N}} \frac{\Lambda(n)}{n^{1/2+it}}. \ \ \ \ \ (4)$

To understand the distribution of ${U}$ in the unitary group ${U(N)}$, it suffices to understand the distribution of the moments

$\displaystyle {\bf E}_t \prod_{j=1}^k (\mathrm{tr} U^j)^{a_j} (\overline{\mathrm{tr} U^j})^{b_j} \ \ \ \ \ (5)$

where ${{\bf E}_t}$ denotes averaging over ${t \in [T,2T]}$, and ${k, a_1,\dots,a_k, b_1,\dots,b_k \geq 0}$. The GUE hypothesis asserts that in the limit ${T \rightarrow \infty}$, these moments converge to their CUE counterparts

$\displaystyle {\bf E}_{\mathrm{CUE}} \prod_{j=1}^k (\mathrm{tr} U^j)^{a_j} (\overline{\mathrm{tr} U^j})^{b_j} \ \ \ \ \ (6)$

where ${U}$ is now drawn uniformly in ${U(n)}$ with respect to the CUE ensemble, and ${{\bf E}_{\mathrm{CUE}}}$ denotes expectation with respect to that measure.

The moment (6) vanishes unless one has the homogeneity condition

$\displaystyle \sum_{j=1}^k j a_j = \sum_{j=1}^k j b_j. \ \ \ \ \ (7)$

This follows from the fact that for any phase ${\theta \in {\bf R}}$, ${e(\theta) U}$ has the same distribution as ${U}$, where we use the number theory notation ${e(\theta) := e^{2\pi i\theta}}$.

In the case when the degree ${\sum_{j=1}^k j a_j}$ is low, we can use representation theory to establish the following simple formula for the moment (6), as evaluated by Diaconis and Shahshahani:

Proposition 1 (Low moments in CUE model) If

$\displaystyle \sum_{j=1}^k j a_j \leq N, \ \ \ \ \ (8)$

then the moment (6) vanishes unless ${a_j=b_j}$ for all ${j}$, in which case it is equal to

$\displaystyle \prod_{j=1}^k j^{a_j} a_j!. \ \ \ \ \ (9)$

Another way of viewing this proposition is that for ${U}$ distributed according to CUE, the random variables ${\mathrm{tr} U^j}$ are distributed like independent complex random variables of mean zero and variance ${j}$, as long as one only considers moments obeying (8). This identity definitely breaks down for larger values of ${a_j}$, so one only obtains central limit theorems in certain limiting regimes, notably when one only considers a fixed number of ${j}$‘s and lets ${N}$ go to infinity. (The paper of Diaconis and Shahshahani writes ${\sum_{j=1}^k a_j + b_j}$ in place of ${\sum_{j=1}^k j a_j}$, but I believe this to be a typo.)

Proof: Let ${D}$ be the left-hand side of (8). We may assume that (7) holds since we are done otherwise, hence

$\displaystyle D = \sum_{j=1}^k j a_j = \sum_{j=1}^k j b_j.$

Our starting point is Schur-Weyl duality. Namely, we consider the ${n^D}$-dimensional complex vector space

$\displaystyle ({\bf C}^n)^{\otimes D} = {\bf C}^n \otimes \dots \otimes {\bf C}^n.$

This space has an action of the product group ${S_D \times GL_n({\bf C})}$: the symmetric group ${S_D}$ acts by permutation on the ${D}$ tensor factors, while the general linear group ${GL_n({\bf C})}$ acts diagonally on the ${{\bf C}^n}$ factors, and the two actions commute with each other. Schur-Weyl duality gives a decomposition

$\displaystyle ({\bf C}^n)^{\otimes D} \equiv \bigoplus_\lambda V^\lambda_{S_D} \otimes V^\lambda_{GL_n({\bf C})} \ \ \ \ \ (10)$

where ${\lambda}$ ranges over Young tableaux of size ${D}$ with at most ${n}$ rows, ${V^\lambda_{S_D}}$ is the ${S_D}$-irreducible unitary representation corresponding to ${\lambda}$ (which can be constructed for instance using Specht modules), and ${V^\lambda_{GL_n({\bf C})}}$ is the ${GL_n({\bf C})}$-irreducible polynomial representation corresponding with highest weight ${\lambda}$.

Let ${\pi \in S_D}$ be a permutation consisting of ${a_j}$ cycles of length ${j}$ (this is uniquely determined up to conjugation), and let ${g \in GL_n({\bf C})}$. The pair ${(\pi,g)}$ then acts on ${({\bf C}^n)^{\otimes D}}$, with the action on basis elements ${e_{i_1} \otimes \dots \otimes e_{i_D}}$ given by

$\displaystyle g e_{\pi(i_1)} \otimes \dots \otimes g_{\pi(i_D)}.$

The trace of this action can then be computed as

$\displaystyle \sum_{i_1,\dots,i_D \in \{1,\dots,n\}} g_{\pi(i_1),i_1} \dots g_{\pi(i_D),i_D}$

where ${g_{i,j}}$ is the ${ij}$ matrix coefficient of ${g}$. Breaking up into cycles and summing, this is just

$\displaystyle \prod_{j=1}^k \mathrm{tr}(g^j)^{a_j}.$

But we can also compute this trace using the Schur-Weyl decomposition (10), yielding the identity

$\displaystyle \prod_{j=1}^k \mathrm{tr}(g^j)^{a_j} = \sum_\lambda \chi_\lambda(\pi) s_\lambda(g) \ \ \ \ \ (11)$

where ${\chi_\lambda: S_D \rightarrow {\bf C}}$ is the character on ${S_D}$ associated to ${V^\lambda_{S_D}}$, and ${s_\lambda: GL_n({\bf C}) \rightarrow {\bf C}}$ is the character on ${GL_n({\bf C})}$ associated to ${V^\lambda_{GL_n({\bf C})}}$. As is well known, ${s_\lambda(g)}$ is just the Schur polynomial of weight ${\lambda}$ applied to the (algebraic, generalised) eigenvalues of ${g}$. We can specialise to unitary matrices to conclude that

$\displaystyle \prod_{j=1}^k \mathrm{tr}(U^j)^{a_j} = \sum_\lambda \chi_\lambda(\pi) s_\lambda(U)$

and similarly

$\displaystyle \prod_{j=1}^k \mathrm{tr}(U^j)^{b_j} = \sum_\lambda \chi_\lambda(\pi') s_\lambda(U)$

where ${\pi' \in S_D}$ consists of ${b_j}$ cycles of length ${j}$ for each ${j=1,\dots,k}$. On the other hand, the characters ${s_\lambda}$ are an orthonormal system on ${L^2(U(N))}$ with the CUE measure. Thus we can write the expectation (6) as

$\displaystyle \sum_\lambda \chi_\lambda(\pi) \overline{\chi_\lambda(\pi')}. \ \ \ \ \ (12)$

Now recall that ${\lambda}$ ranges over all the Young tableaux of size ${D}$ with at most ${N}$ rows. But by (8) we have ${D \leq N}$, and so the condition of having ${N}$ rows is redundant. Hence ${\lambda}$ now ranges over all Young tableaux of size ${D}$, which as is well known enumerates all the irreducible representations of ${S_D}$. One can then use the standard orthogonality properties of characters to show that the sum (12) vanishes if ${\pi}$, ${\pi'}$ are not conjugate, and is equal to ${D!}$ divided by the size of the conjugacy class of ${\pi}$ (or equivalently, by the size of the centraliser of ${\pi}$) otherwise. But the latter expression is easily computed to be ${\prod_{j=1}^k j^{a_j} a_j!}$, giving the claim. $\Box$

Example 2 We illustrate the identity (11) when ${D=3}$, ${n \geq 3}$. The Schur polynomials are given as

$\displaystyle s_{3}(g) = \sum_i \lambda_i^3 + \sum_{i

$\displaystyle s_{2,1}(g) = \sum_{i < j} \lambda_i^2 \lambda_j + \sum_{i < j,k} \lambda_i \lambda_j \lambda_k$

$\displaystyle s_{1,1,1}(g) = \sum_{i

where ${\lambda_1,\dots,\lambda_n}$ are the (generalised) eigenvalues of ${g}$, and the formula (11) in this case becomes

$\displaystyle \mathrm{tr}(g^3) = s_{3}(g) - s_{2,1}(g) + s_{1,1,1}(g)$

$\displaystyle \mathrm{tr}(g^2) \mathrm{tr}(g) = s_{3}(g) - s_{1,1,1}(g)$

$\displaystyle \mathrm{tr}(g)^3 = s_{3}(g) + 2 s_{2,1}(g) + s_{1,1,1}(g).$

The functions ${s_{1,1,1}, s_{2,1}, s_3}$ are orthonormal on ${U(n)}$, so the three functions ${\mathrm{tr}(g^3), \mathrm{tr}(g^2) \mathrm{tr}(g), \mathrm{tr}(g)^3}$ are also, and their ${L^2}$ norms are ${\sqrt{3}}$, ${\sqrt{2}}$, and ${\sqrt{6}}$ respectively, reflecting the size in ${S_3}$ of the centralisers of the permutations ${(123)}$, ${(12)}$, and ${\mathrm{id}}$ respectively. If ${n}$ is instead set to say ${2}$, then the ${s_{1,1,1}}$ terms now disappear (the Young tableau here has too many rows), and the three quantities here now have some non-trivial covariance.

Example 3 Consider the moment ${{\bf E}_{\mathrm{CUE}} |\mathrm{tr} U^j|^2}$. For ${j \leq N}$, the above proposition shows us that this moment is equal to ${D}$. What happens for ${j>N}$? The formula (12) computes this moment as

$\displaystyle \sum_\lambda |\chi_\lambda(\pi)|^2$

where ${\pi}$ is a cycle of length ${j}$ in ${S_j}$, and ${\lambda}$ ranges over all Young tableaux with size ${j}$ and at most ${N}$ rows. The Murnaghan-Nakayama rule tells us that ${\chi_\lambda(\pi)}$ vanishes unless ${\lambda}$ is a hook (all but one of the non-zero rows consisting of just a single box; this also can be interpreted as an exterior power representation on the space ${{\bf C}^j_{\sum=0}}$ of vectors in ${{\bf C}^j}$ whose coordinates sum to zero), in which case it is equal to ${\pm 1}$ (depending on the parity of the number of non-zero rows). As such we see that this moment is equal to ${N}$. Thus in general we have

$\displaystyle {\bf E}_{\mathrm{CUE}} |\mathrm{tr} U^j|^2 = \min(j,N). \ \ \ \ \ (13)$

Now we discuss what is known for the analogous moments (5). Here we shall be rather non-rigorous, in particular ignoring an annoying “Archimedean” issue that the product of the ranges ${T^{(j-1)/N} < n \leq T^{j/N}}$ and ${T^{(k-1)/N} < n \leq T^{k/N}}$ is not quite the range ${T^{(j+k-1)/N} < n \leq T^{j+k/N}}$ but instead leaks into the adjacent range ${T^{(j+k-2)/N} < n \leq T^{j+k-1/N}}$. This issue can be addressed by working in a “weak" sense in which parameters such as ${j,k}$ are averaged over fairly long scales, or by passing to a function field analogue of these questions, but we shall simply ignore the issue completely and work at a heuristic level only. For similar reasons we will ignore some technical issues arising from the sharp cutoff of ${t}$ to the range ${[T,2T]}$ (it would be slightly better technically to use a smooth cutoff).

One can morally expand out (5) using (4) as

$\displaystyle (\frac{N}{\log T})^{J+K} \sum_{n_1,\dots,n_J,m_1,\dots,m_K} \frac{\Lambda(n_1) \dots \Lambda(n_J) \Lambda(m_1) \dots \Lambda(m_K)}{n_1^{1/2} \dots n_J^{1/2} m_1^{1/2} \dots m_K^{1/2}} \times \ \ \ \ \ (14)$

$\displaystyle \times {\bf E}_t (m_1 \dots m_K / n_1 \dots n_J)^{it}$

where ${J := \sum_{j=1}^k a_j}$, ${K := \sum_{j=1}^k b_j}$, and the integers ${n_i,m_i}$ are in the ranges

$\displaystyle T^{(j-1)/N} < n_{a_1 + \dots + a_{j-1} + i} \leq T^{j/N}$

for ${j=1,\dots,k}$ and ${1 \leq i \leq a_j}$, and

$\displaystyle T^{(j-1)/N} < m_{b_1 + \dots + b_{j-1} + i} \leq T^{j/N}$

for ${j=1,\dots,k}$ and ${1 \leq i \leq b_j}$. Morally, the expectation here is negligible unless

$\displaystyle m_1 \dots m_K = (1 + O(1/T)) n_1 \dots n_J \ \ \ \ \ (15)$

in which case the expecation is oscillates with magnitude one. In particular, if (7) fails (with some room to spare) then the moment (5) should be negligible, which is consistent with the analogous behaviour for the moments (6). Now suppose that (8) holds (with some room to spare). Then ${n_1 \dots n_J}$ is significantly less than ${T}$, so the ${O(1/T)}$ multiplicative error in (15) becomes an additive error of ${o(1)}$. On the other hand, because of the fundamental integrality gap – that the integers are always separated from each other by a distance of at least ${1}$ – this forces the integers ${m_1 \dots m_K}$, ${n_1 \dots n_J}$ to in fact be equal:

$\displaystyle m_1 \dots m_K = n_1 \dots n_J. \ \ \ \ \ (16)$

The von Mangoldt factors ${\Lambda(n_1) \dots \Lambda(n_J) \Lambda(m_1) \dots \Lambda(m_K)}$ effectively restrict ${n_1,\dots,n_J,m_1,\dots,m_K}$ to be prime (the effect of prime powers is negligible). By the fundamental theorem of arithmetic, the constraint (16) then forces ${J=K}$, and ${n_1,\dots,n_J}$ to be a permutation of ${m_1,\dots,m_K}$, which then forces ${a_j = b_j}$ for all ${j=1,\dots,k}$._ For a given ${n_1,\dots,n_J}$, the number of possible ${m_1 \dots m_K}$ is then ${\prod_{j=1}^k a_j!}$, and the expectation in (14) is equal to ${1}$. Thus this expectation is morally

$\displaystyle (\frac{N}{\log T})^{J+K} \sum_{n_1,\dots,n_J} \frac{\Lambda^2(n_1) \dots \Lambda^2(n_J) }{n_1 \dots n_J} \prod_{j=1}^k a_j!$

and using Mertens’ theorem this soon simplifies asymptotically to the same quantity in Proposition 1. Thus we see that (morally at least) the moments (5) associated to the zeta function asymptotically match the moments (6) coming from the CUE model in the low degree case (8), thus lending support to the GUE hypothesis. (These observations are basically due to Rudnick and Sarnak, with the degree ${1}$ case of pair correlations due to Montgomery, and the degree ${2}$ case due to Hejhal.)

With some rare exceptions (such as those estimates coming from “Kloostermania”), the moment estimates of Rudnick and Sarnak basically represent the state of the art for what is known for the moments (5). For instance, Montgomery’s pair correlation conjecture, in our language, is basically the analogue of (13) for ${{\mathbf E}_t}$, thus

$\displaystyle {\bf E}_{t} |\mathrm{tr} U^j|^2 \approx \min(j,N) \ \ \ \ \ (17)$

for all ${j \geq 0}$. Montgomery showed this for (essentially) the range ${j \leq N}$ (as remarked above, this is a special case of the Rudnick-Sarnak result), but no further cases of this conjecture are known.

These estimates can be used to give some non-trivial information on the largest and smallest spacings between zeroes of the zeta function, which in our notation corresponds to spacing between eigenvalues of ${U}$. One such method used today for this is due to Montgomery and Odlyzko and was greatly simplified by Conrey, Ghosh, and Gonek. The basic idea, translated to our random matrix notation, is as follows. Suppose ${Q_t(Z)}$ is some random polynomial depending on ${t}$ of degree at most ${N}$. Let ${\lambda_1,\dots,\lambda_n}$ denote the eigenvalues of ${U}$, and let ${c > 0}$ be a parameter. Observe from the pigeonhole principle that if the quantity

$\displaystyle \sum_{j=1}^n \int_0^{c/N} |Q_t( e(\theta) \lambda_j )|^2\ d\theta \ \ \ \ \ (18)$

exceeds the quantity

$\displaystyle \int_{0}^{2\pi} |Q_t(e(\theta))|^2\ d\theta, \ \ \ \ \ (19)$

then the arcs ${\{ e(\theta) \lambda_j: 0 \leq \theta \leq c \}}$ cannot all be disjoint, and hence there exists a pair of eigenvalues making an angle of less than ${c/N}$ (${c}$ times the mean angle separation). Similarly, if the quantity (18) falls below that of (19), then these arcs cannot cover the unit circle, and hence there exists a pair of eigenvalues making an angle of greater than ${c}$ times the mean angle separation. By judiciously choosing the coefficients of ${Q_t}$ as functions of the moments ${\mathrm{tr}(U^j)}$, one can ensure that both quantities (18), (19) can be computed by the Rudnick-Sarnak estimates (or estimates of equivalent strength); indeed, from the residue theorem one can write (18) as

$\displaystyle \frac{1}{2\pi i} \int_0^{c/N} (\int_{|z| = 1+\varepsilon} - \int_{|z|=1-\varepsilon}) Q_t( e(\theta) z ) \overline{Q_t}( \frac{1}{e(\theta) z} ) \frac{P'_t(z)}{P_t(z)}\ dz$

for sufficiently small ${\varepsilon>0}$, and this can be computed (in principle, at least) using (3) if the coefficients of ${Q_t}$ are in an appropriate form. Using this sort of technology (translated back to the Riemann zeta function setting), one can show that gaps between consecutive zeroes of zeta are less than ${\mu}$ times the mean spacing and greater than ${\lambda}$ times the mean spacing infinitely often for certain ${0 < \mu < 1 < \lambda}$; the current records are ${\mu = 0.50412}$ (due to Goldston and Turnage-Butterbaugh) and ${\lambda = 3.18}$ (due to Bui and Milinovich, who input some additional estimates beyond the Rudnick-Sarnak set, namely the twisted fourth moment estimates of Bettin, Bui, Li, and Radziwill, and using a technique based on Hall’s method rather than the Montgomery-Odlyzko method).

It would be of great interest if one could push the upper bound ${\mu}$ for the smallest gap below ${1/2}$. The reason for this is that this would then exclude the Alternative Hypothesis that the spacing between zeroes are asymptotically always (or almost always) a non-zero half-integer multiple of the mean spacing, or in our language that the gaps between the phases ${\theta}$ of the eigenvalues ${e^{2\pi i\theta}}$ of ${U}$ are nasymptotically always non-zero integer multiples of ${1/2N}$. The significance of this hypothesis is that it is implied by the existence of a Siegel zero (of conductor a small power of ${T}$); see this paper of Conrey and Iwaniec. (In our language, what is going on is that if there is a Siegel zero in which ${L(1,\chi)}$ is very close to zero, then ${1*\chi}$ behaves like the Kronecker delta, and hence (by the Riemann-Siegel formula) the combined ${L}$-function ${\zeta(s) L(s,\chi)}$ will have a polynomial approximation which in our language looks like a scalar multiple of ${1 + e(\theta) Z^{2N+M}}$, where ${q \approx T^{M/N}}$ and ${\theta}$ is a phase. The zeroes of this approximation lie on a coset of the ${(2N+M)^{th}}$ roots of unity; the polynomial ${P}$ is a factor of this approximation and hence will also lie in this coset, implying in particular that all eigenvalue spacings are multiples of ${1/(2N+M)}$. Taking ${M = o(N)}$ then gives the claim.)

Unfortunately, the known methods do not seem to break this barrier without some significant new input; already the original paper of Montgomery and Odlyzko observed this limitation for their particular technique (and in fact fall very slightly short, as observed in unpublished work of Goldston and of Milinovich). In this post I would like to record another way to see this, by providing an “alternative” probability distribution to the CUE distribution (which one might dub the Alternative Circular Unitary Ensemble (ACUE) which is indistinguishable in low moments in the sense that the expectation ${{\bf E}_{ACUE}}$ for this model also obeys Proposition 1, but for which the phase spacings are always a multiple of ${1/2N}$. This shows that if one is to rule out the Alternative Hypothesis (and thus in particular rule out Siegel zeroes), one needs to input some additional moment information beyond Proposition 1. It would be interesting to see if any of the other known moment estimates that go beyond this proposition are consistent with this alternative distribution. (UPDATE: it looks like they are, see Remark 7 below.)

To describe this alternative distribution, let us first recall the Weyl description of the CUE measure on the unitary group ${U(n)}$ in terms of the distribution of the phases ${\theta_1,\dots,\theta_N \in {\bf R}/{\bf Z}}$ of the eigenvalues, randomly permuted in any order. This distribution is given by the probability measure

$\displaystyle \frac{1}{N!} |V(\theta)|^2\ d\theta_1 \dots d\theta_N; \ \ \ \ \ (20)$

where

$\displaystyle V(\theta) := \prod_{1 \leq i

is the Vandermonde determinant; see for instance this previous blog post for the derivation of a very similar formula for the GUE distribution, which can be adapted to CUE without much difficulty. To see that this is a probability measure, first observe the Vandermonde determinant identity

$\displaystyle V(\theta) = \sum_{\pi \in S_N} \mathrm{sgn}(\pi) e(\theta \cdot \pi(\rho))$

where ${\theta := (\theta_1,\dots,\theta_N)}$, ${\cdot}$ denotes the dot product, and ${\rho := (1,2,\dots,N)}$ is the “long word”, which implies that (20) is a trigonometric series with constant term ${1}$; it is also clearly non-negative, so it is a probability measure. One can thus generate a random CUE matrix by first drawing ${(\theta_1,\dots,\theta_n) \in ({\bf R}/{\bf Z})^N}$ using the probability measure (20), and then generating ${U}$ to be a random unitary matrix with eigenvalues ${e(\theta_1),\dots,e(\theta_N)}$.

For the alternative distribution, we first draw ${(\theta_1,\dots,\theta_N)}$ on the discrete torus ${(\frac{1}{2N}{\bf Z}/{\bf Z})^N}$ (thus each ${\theta_j}$ is a ${2N^{th}}$ root of unity) with probability density function

$\displaystyle \frac{1}{(2N)^N} \frac{1}{N!} |V(\theta)|^2 \ \ \ \ \ (21)$

shift by a phase ${\alpha \in {\bf R}/{\bf Z}}$ drawn uniformly at random, and then select ${U}$ to be a random unitary matrix with eigenvalues ${e^{i(\theta_1+\alpha)}, \dots, e^{i(\theta_N+\alpha)}}$. Let us first verify that (21) is a probability density function. Clearly it is non-negative. It is the linear combination of exponentials of the form ${e(\theta \cdot (\pi(\rho)-\pi'(\rho))}$ for ${\pi,\pi' \in S_N}$. The diagonal contribution ${\pi=\pi'}$ gives the constant function ${\frac{1}{(2N)^N}}$, which has total mass one. All of the other exponentials have a frequency ${\pi(\rho)-\pi'(\rho)}$ that is not a multiple of ${2N}$, and hence will have mean zero on ${(\frac{1}{2N}{\bf Z}/{\bf Z})^N}$. The claim follows.

From construction it is clear that the matrix ${U}$ drawn from this alternative distribution will have all eigenvalue phase spacings be a non-zero multiple of ${1/2N}$. Now we verify that the alternative distribution also obeys Proposition 1. The alternative distribution remains invariant under rotation by phases, so the claim is again clear when (8) fails. Inspecting the proof of that proposition, we see that it suffices to show that the Schur polynomials ${s_\lambda}$ with ${\lambda}$ of size at most ${N}$ and of equal size remain orthonormal with respect to the alternative measure. That is to say,

$\displaystyle \int_{U(N)} s_\lambda(U) \overline{s_{\lambda'}(U)}\ d\mu_{\mathrm{CUE}}(U) = \int_{U(N)} s_\lambda(U) \overline{s_{\lambda'}(U)}\ d\mu_{\mathrm{ACUE}}(U)$

when ${\lambda,\lambda'}$ have size equal to each other and at most ${N}$. In this case the phase ${\alpha}$ in the definition of ${U}$ is irrelevant. In terms of eigenvalue measures, we are then reduced to showing that

$\displaystyle \int_{({\bf R}/{\bf Z})^N} s_\lambda(\theta) \overline{s_{\lambda'}(\theta)} |V(\theta)|^2\ d\theta = \frac{1}{(2N)^N} \sum_{\theta \in (\frac{1}{2N}{\bf Z}/{\bf Z})^N} s_\lambda(\theta) \overline{s_{\lambda'}(\theta)} |V(\theta)|^2.$

By Fourier decomposition, it then suffices to show that the trigonometric polynomial ${s_\lambda(\theta) \overline{s_{\lambda'}(\theta)} |V(\theta)|^2}$ does not contain any components of the form ${e( \theta \cdot 2N k)}$ for some non-zero lattice vector ${k \in {\bf Z}^N}$. But we have already observed that ${|V(\theta)|^2}$ is a linear combination of plane waves of the form ${e(\theta \cdot (\pi(\rho)-\pi'(\rho))}$ for ${\pi,\pi' \in S_N}$. Also, as is well known, ${s_\lambda(\theta)}$ is a linear combination of plane waves ${e( \theta \cdot \kappa )}$ where ${\kappa}$ is majorised by ${\lambda}$, and similarly ${s_{\lambda'}(\theta)}$ is a linear combination of plane waves ${e( \theta \cdot \kappa' )}$ where ${\kappa'}$ is majorised by ${\lambda'}$. So the product ${s_\lambda(\theta) \overline{s_{\lambda'}(\theta)} |V(\theta)|^2}$ is a linear combination of plane waves of the form ${e(\theta \cdot (\kappa - \kappa' + \pi(\rho) - \pi'(\rho)))}$. But every coefficient of the vector ${\kappa - \kappa' + \pi(\rho) - \pi'(\rho)}$ lies between ${1-2N}$ and ${2N-1}$, and so cannot be of the form ${2Nk}$ for any non-zero lattice vector ${k}$, giving the claim.

Example 4 If ${N=2}$, then the distribution (21) assigns a probability of ${\frac{1}{4^2 2!} 2}$ to any pair ${(\theta_1,\theta_2) \in (\frac{1}{4} {\bf Z}/{\bf Z})^2}$ that is a permuted rotation of ${(0,\frac{1}{4})}$, and a probability of ${\frac{1}{4^2 2!} 4}$ to any pair that is a permuted rotation of ${(0,\frac{1}{2})}$. Thus, a matrix ${U}$ drawn from the alternative distribution will be conjugate to a phase rotation of ${\mathrm{diag}(1, i)}$ with probability ${1/2}$, and to ${\mathrm{diag}(1,-1)}$ with probability ${1/2}$.

A similar computation when ${N=3}$ gives ${U}$ conjugate to a phase rotation of ${\mathrm{diag}(1, e(1/6), e(1/3))}$ with probability ${1/12}$, to a phase rotation of ${\mathrm{diag}( 1, e(1/6), -1)}$ or its adjoint with probability of ${1/3}$ each, and a phase rotation of ${\mathrm{diag}(1, e(1/3), e(2/3))}$ with probability ${1/4}$.

Remark 5 For large ${N}$ it does not seem that this specific alternative distribution is the only distribution consistent with Proposition 1 and which has all phase spacings a non-zero multiple of ${1/2N}$; in particular, it may not be the only distribution consistent with a Siegel zero. Still, it is a very explicit distribution that might serve as a test case for the limitations of various arguments for controlling quantities such as the largest or smallest spacing between zeroes of zeta. The ACUE is in some sense the distribution that maximally resembles CUE (in the sense that it has the greatest number of Fourier coefficients agreeing) while still also being consistent with the Alternative Hypothesis, and so should be the most difficult enemy to eliminate if one wishes to disprove that hypothesis.

In some cases, even just a tiny improvement in known results would be able to exclude the alternative hypothesis. For instance, if the alternative hypothesis held, then ${|\mathrm{tr}(U^j)|}$ is periodic in ${j}$ with period ${2N}$, so from Proposition 1 for the alternative distribution one has

$\displaystyle {\bf E}_{\mathrm{ACUE}} |\mathrm{tr} U^j|^2 = \min_{k \in {\bf Z}} |j-2Nk|$

which differs from (13) for any ${|j| > N}$. (This fact was implicitly observed recently by Baluyot, in the original context of the zeta function.) Thus a verification of the pair correlation conjecture (17) for even a single ${j}$ with ${|j| > N}$ would rule out the alternative hypothesis. Unfortunately, such a verification appears to be on comparable difficulty with (an averaged version of) the Hardy-Littlewood conjecture, with power saving error term. (This is consistent with the fact that Siegel zeroes can cause distortions in the Hardy-Littlewood conjecture, as (implicitly) discussed in this previous blog post.)

Remark 6 One can view the CUE as normalised Lebesgue measure on ${U(N)}$ (viewed as a smooth submanifold of ${{\bf C}^{N^2}}$). One can similarly view ACUE as normalised Lebesgue measure on the (disconnected) smooth submanifold of ${U(N)}$ consisting of those unitary matrices whose phase spacings are non-zero integer multiples of ${1/2N}$; informally, ACUE is CUE restricted to this lower dimensional submanifold. As is well known, the phases of CUE eigenvalues form a determinantal point process with kernel ${K(\theta,\theta') = \frac{1}{N} \sum_{j=0}^{N-1} e(j(\theta - \theta'))}$ (or one can equivalently take ${K(\theta,\theta') = \frac{\sin(\pi N (\theta-\theta'))}{N\sin(\pi(\theta-\theta'))}}$; in a similar spirit, the phases of ACUE eigenvalues, once they are rotated to be ${2N^{th}}$ roots of unity, become a discrete determinantal point process on those roots of unity with exactly the same kernel (except for a normalising factor of ${\frac{1}{2}}$). In particular, the ${k}$-point correlation functions of ACUE (after this rotation) are precisely the restriction of the ${k}$-point correlation functions of CUE after normalisation, that is to say they are proportional to ${\mathrm{det}( K( \theta_i,\theta_j) )_{1 \leq i,j \leq k}}$.

Remark 7 One family of estimates that go beyond the Rudnick-Sarnak family of estimates are twisted moment estimates for the zeta function, such as ones that give asymptotics for

$\displaystyle \int_T^{2T} |\zeta(\frac{1}{2}+it)|^{2k} |Q(\frac{1}{2}+it)|^2\ dt$

for some small even exponent ${2k}$ (almost always ${2}$ or ${4}$) and some short Dirichlet polynomial ${Q}$; see for instance this paper of Bettin, Bui, Li, and Radziwill for some examples of such estimates. The analogous unitary matrix average would be something like

$\displaystyle {\bf E}_t |P_t(1)|^{2k} |Q_t(1)|^2$

where ${Q_t}$ is now some random medium degree polynomial that depends on the unitary matrix ${U}$ associated to ${P_t}$ (and in applications will typically also contain some negative power of ${\exp(A_t)}$ to cancel the corresponding powers of ${\exp(A_t)}$ in ${|P_t(1)|^{2k}}$). Unfortunately such averages generally are unable to distinguish the CUE from the ACUE. For instance, if all the coefficients of ${Q}$ involve products of traces ${\mathrm{tr}(U^k)}$ of total order less than ${N-k}$, then in terms of the eigenvalue phases ${\theta}$, ${|Q(1)|^2}$ is a linear combination of plane waves ${e(\theta \cdot \xi)}$ where the frequencies ${\xi}$ have coefficients of magnitude less than ${N-k}$. On the other hand, as each coefficient of ${P_t}$ is an elementary symmetric function of the eigenvalues, ${P_t(1)}$ is a linear combination of plane waves ${e(\theta \cdot \xi)}$ where the frequencies ${\xi}$ have coefficients of magnitude at most ${1}$. Thus ${|P_t(1)|^{2k} |Q_t(1)|^2}$ is a linear combination of plane waves where the frequencies ${\xi}$ have coefficients of magnitude less than ${N}$, and thus is orthogonal to the difference between the CUE and ACUE measures on the phase torus ${({\bf R}/{\bf Z})^n}$ by the previous arguments. In other words, ${|P_t(1)|^{2k} |Q_t(1)|^2}$ has the same expectation with respect to ACUE as it does with respect to CUE. Thus one can only start distinguishing CUE from ACUE if the mollifier ${Q_t}$ has degree close to or exceeding ${N}$, which corresponds to Dirichlet polynomials ${Q}$ of length close to or exceeding ${T}$, which is far beyond current technology for such moment estimates.

Remark 8 The GUE hypothesis for the zeta function asserts that the average

$\displaystyle \lim_{T \rightarrow \infty} \frac{1}{T} \int_T^{2T} \sum_{\gamma_1,\dots,\gamma_n \hbox{ distinct}} \eta( \frac{\log T}{2\pi}(\gamma_1-t),\dots, \frac{\log T}{2\pi}(\gamma_k-t))\ dt \ \ \ \ \ (22)$

is equal to

$\displaystyle \int_{{\bf R}^n} \eta(x) \det(K(x_i-x_j))_{1 \leq i,j \leq k}\ dx_1 \dots dx_k \ \ \ \ \ (23)$

for any ${k \geq 1}$ and any test function ${\eta: {\bf R}^k \rightarrow {\bf C}}$, where ${K(x) := \frac{\sin \pi x}{\pi x}}$ is the Dyson sine kernel and ${\gamma_i}$ are the ordinates of zeroes of the zeta function. This corresponds to the CUE distribution for ${U}$. The ACUE distribution then corresponds to an “alternative gaussian unitary ensemble (AGUE)” hypothesis, in which the average (22) is instead predicted to equal a Riemann sum version of the integral (23):

$\displaystyle \int_0^1 2^{-k} \sum_{x_1,\dots,x_k \in \frac{1}{2} {\bf Z} + \theta} \eta(x) \det(K(x_i-x_j))_{1 \leq i,j \leq k}\ d\theta.$

This is a stronger version of the alternative hypothesis that the spacing between adjacent zeroes is almost always approximately a half-integer multiple of the mean spacing. I do not know of any known moment estimates for Dirichlet series that is able to eliminate this AGUE hypothesis (even assuming GRH). (UPDATE: These facts have also been independently observed in forthcoming work of Lagarias and Rodgers.)

Important note: As this is not a course in probability, we will try to avoid developing the general theory of stochastic calculus (which includes such concepts as filtrations, martingales, and Ito calculus). This will unfortunately limit what we can actually prove rigorously, and so at some places the arguments will be somewhat informal in nature. A rigorous treatment of many of the topics here can be found for instance in Lawler’s Conformally Invariant Processes in the Plane, from which much of the material here is drawn.

In these notes, random variables will be denoted in boldface.

Definition 1 A real random variable ${\mathbf{X}}$ is said to be normally distributed with mean ${x_0 \in {\bf R}}$ and variance ${\sigma^2 > 0}$ if one has

$\displaystyle \mathop{\bf E} F(\mathbf{X}) = \frac{1}{\sqrt{2\pi} \sigma} \int_{\bf R} e^{-(x-x_0)^2/2\sigma^2} F(x)\ dx$

for all test functions ${F \in C_c({\bf R})}$. Similarly, a complex random variable ${\mathbf{Z}}$ is said to be normally distributed with mean ${z_0 \in {\bf R}}$ and variance ${\sigma^2>0}$ if one has

$\displaystyle \mathop{\bf E} F(\mathbf{Z}) = \frac{1}{\pi \sigma^2} \int_{\bf C} e^{-|z-x_0|^2/\sigma^2} F(z)\ dx dy$

for all test functions ${F \in C_c({\bf C})}$, where ${dx dy}$ is the area element on ${{\bf C}}$.

A real Brownian motion with base point ${x_0 \in {\bf R}}$ is a random, almost surely continuous function ${\mathbf{B}^{x_0}: [0,+\infty) \rightarrow {\bf R}}$ (using the locally uniform topology on continuous functions) with the property that (almost surely) ${\mathbf{B}^{x_0}(0) = x_0}$, and for any sequence of times ${0 \leq t_0 < t_1 < t_2 < \dots < t_n}$, the increments ${\mathbf{B}^{x_0}(t_i) - \mathbf{B}^{x_0}(t_{i-1})}$ for ${i=1,\dots,n}$ are independent real random variables that are normally distributed with mean zero and variance ${t_i - t_{i-1}}$. Similarly, a complex Brownian motion with base point ${z_0 \in {\bf R}}$ is a random, almost surely continuous function ${\mathbf{B}^{z_0}: [0,+\infty) \rightarrow {\bf R}}$ with the property that ${\mathbf{B}^{z_0}(0) = z_0}$ and for any sequence of times ${0 \leq t_0 < t_1 < t_2 < \dots < t_n}$, the increments ${\mathbf{B}^{z_0}(t_i) - \mathbf{B}^{z_0}(t_{i-1})}$ for ${i=1,\dots,n}$ are independent complex random variables that are normally distributed with mean zero and variance ${t_i - t_{i-1}}$.

Remark 2 Thanks to the central limit theorem, the hypothesis that the increments ${\mathbf{B}^{x_0}(t_i) - \mathbf{B}^{x_0}(t_{i-1})}$ be normally distributed can be dropped from the definition of a Brownian motion, so long as one retains the independence and the normalisation of the mean and variance (technically one also needs some uniform integrability on the increments beyond the second moment, but we will not detail this here). A similar statement is also true for the complex Brownian motion (where now we need to normalise the variances and covariances of the real and imaginary parts of the increments).

Real and complex Brownian motions exist from any base point ${x_0}$ or ${z_0}$; see e.g. this previous blog post for a construction. We have the following simple invariances:

Exercise 3

• (i) (Translation invariance) If ${\mathbf{B}^{x_0}}$ is a real Brownian motion with base point ${x_0 \in {\bf R}}$, and ${h \in {\bf R}}$, show that ${\mathbf{B}^{x_0}+h}$ is a real Brownian motion with base point ${x_0+h}$. Similarly, if ${\mathbf{B}^{z_0}}$ is a complex Brownian motion with base point ${z_0 \in {\bf R}}$, and ${h \in {\bf C}}$, show that ${\mathbf{B}^{z_0}+c}$ is a complex Brownian motion with base point ${z_0+h}$.
• (ii) (Dilation invariance) If ${\mathbf{B}^{0}}$ is a real Brownian motion with base point ${0}$, and ${\lambda \in {\bf R}}$ is non-zero, show that ${t \mapsto \lambda \mathbf{B}^0(t / |\lambda|^{1/2})}$ is also a real Brownian motion with base point ${0}$. Similarly, if ${\mathbf{B}^0}$ is a complex Brownian motion with base point ${0}$, and ${\lambda \in {\bf C}}$ is non-zero, show that ${t \mapsto \lambda \mathbf{B}^0(t / |\lambda|^{1/2})}$ is also a complex Brownian motion with base point ${0}$.
• (iii) (Real and imaginary parts) If ${\mathbf{B}^0}$ is a complex Brownian motion with base point ${0}$, show that ${\sqrt{2} \mathrm{Re} \mathbf{B}^0}$ and ${\sqrt{2} \mathrm{Im} \mathbf{B}^0}$ are independent real Brownian motions with base point ${0}$. Conversely, if ${\mathbf{B}^0_1, \mathbf{B}^0_2}$ are independent real Brownian motions of base point ${0}$, show that ${\frac{1}{\sqrt{2}} (\mathbf{B}^0_1 + i \mathbf{B}^0_2)}$ is a complex Brownian motion with base point ${0}$.

The next lemma is a special case of the optional stopping theorem.

Lemma 4 (Optional stopping identities)

• (i) (Real case) Let ${\mathbf{B}^{x_0}}$ be a real Brownian motion with base point ${x_0 \in {\bf R}}$. Let ${\mathbf{t}}$ be a bounded stopping time – a bounded random variable with the property that for any time ${t \geq 0}$, the event that ${\mathbf{t} \leq t}$ is determined by the values of the trajectory ${\mathbf{B}^{x_0}}$ for times up to ${t}$ (or more precisely, this event is measurable with respect to the ${\sigma}$ algebra generated by this proprtion of the trajectory). Then

$\displaystyle \mathop{\bf E} \mathbf{B}^{x_0}(\mathbf{t}) = x_0$

and

$\displaystyle \mathop{\bf E} (\mathbf{B}^{x_0}(\mathbf{t})-x_0)^2 - \mathbf{t} = 0$

and

$\displaystyle \mathop{\bf E} (\mathbf{B}^{x_0}(\mathbf{t})-x_0)^4 = O( \mathop{\bf E} \mathbf{t}^2 ).$

• (ii) (Complex case) Let ${\mathbf{B}^{z_0}}$ be a real Brownian motion with base point ${z_0 \in {\bf R}}$. Let ${\mathbf{t}}$ be a bounded stopping time – a bounded random variable with the property that for any time ${t \geq 0}$, the event that ${\mathbf{t} \leq t}$ is determined by the values of the trajectory ${\mathbf{B}^{x_0}}$ for times up to ${t}$. Then

$\displaystyle \mathop{\bf E} \mathbf{B}^{z_0}(\mathbf{t}) = z_0$

$\displaystyle \mathop{\bf E} (\mathrm{Re}(\mathbf{B}^{z_0}(\mathbf{t})-z_0))^2 - \frac{1}{2} \mathbf{t} = 0$

$\displaystyle \mathop{\bf E} (\mathrm{Im}(\mathbf{B}^{z_0}(\mathbf{t})-z_0))^2 - \frac{1}{2} \mathbf{t} = 0$

$\displaystyle \mathop{\bf E} \mathrm{Re}(\mathbf{B}^{z_0}(\mathbf{t})-z_0) \mathrm{Im}(\mathbf{B}^{z_0}(\mathbf{t})-z_0) = 0$

$\displaystyle \mathop{\bf E} |\mathbf{B}^{x_0}(\mathbf{t})-z_0|^4 = O( \mathop{\bf E} \mathbf{t}^2 ).$

Proof: (Slightly informal) We just prove (i) and leave (ii) as an exercise. By translation invariance we can take ${x_0=0}$. Let ${T}$ be an upper bound for ${\mathbf{t}}$. Since ${\mathbf{B}^0(T)}$ is a real normally distributed variable with mean zero and variance ${T}$, we have

$\displaystyle \mathop{\bf E} \mathbf{B}^0( T ) = 0$

and

$\displaystyle \mathop{\bf E} \mathbf{B}^0( T )^2 = T$

and

$\displaystyle \mathop{\bf E} \mathbf{B}^0( T )^4 = 3T^2.$

By the law of total expectation, we thus have

$\displaystyle \mathop{\bf E} \mathop{\bf E}(\mathbf{B}^0( T ) | \mathbf{t}, \mathbf{B}^{z_0}(\mathbf{t}) ) = 0$

and

$\displaystyle \mathop{\bf E} \mathop{\bf E}((\mathbf{B}^0( T ))^2 | \mathbf{t}, \mathbf{B}^{z_0}(\mathbf{t}) ) = T$

and

$\displaystyle \mathop{\bf E} \mathop{\bf E}((\mathbf{B}^0( T ))^4 | \mathbf{t}, \mathbf{B}^{z_0}(\mathbf{t}) ) = 3T^2$

where the inner conditional expectations are with respect to the event that ${\mathbf{t}, \mathbf{B}^{0}(\mathbf{t})}$ attains a particular point in ${S}$. However, from the independent increment nature of Brownian motion, once one conditions ${(\mathbf{t}, \mathbf{B}^{0}(\mathbf{t}))}$ to a fixed point ${(t, x)}$, the random variable ${\mathbf{B}^0(T)}$ becomes a real normally distributed variable with mean ${x}$ and variance ${T-t}$. Thus we have

$\displaystyle \mathop{\bf E}(\mathbf{B}^0( T ) | \mathbf{t}, \mathbf{B}^{z_0}(\mathbf{t}) ) = \mathbf{B}^{z_0}(\mathbf{t})$

and

$\displaystyle \mathop{\bf E}( (\mathbf{B}^0( T ))^2 | \mathbf{t}, \mathbf{B}^{z_0}(\mathbf{t}) ) = \mathbf{B}^{z_0}(\mathbf{t})^2 + T - \mathbf{t}$

and

$\displaystyle \mathop{\bf E}( (\mathbf{B}^0( T ))^4 | \mathbf{t}, \mathbf{B}^{z_0}(\mathbf{t}) ) = \mathbf{B}^{z_0}(\mathbf{t})^4 + 6(T - \mathbf{t}) \mathbf{B}^{z_0}(\mathbf{t})^2 + 3(T - \mathbf{t})^2$

which give the first two claims, and (after some algebra) the identity

$\displaystyle \mathop{\bf E} \mathbf{B}^{z_0}(\mathbf{t})^4 - 6 \mathbf{t} \mathbf{B}^{z_0}(\mathbf{t})^2 + 3 \mathbf{t}^2 = 0$

which then also gives the third claim. $\Box$

Exercise 5 Prove the second part of Lemma 4.

In this post we assume the Riemann hypothesis and the simplicity of zeroes, thus the zeroes of ${\zeta}$ in the critical strip take the form ${\frac{1}{2} \pm i \gamma_j}$ for some real number ordinates ${0 < \gamma_1 < \gamma_2 < \dots}$. From the Riemann-von Mangoldt formula, one has the asymptotic

$\displaystyle \gamma_n = (1+o(1)) \frac{2\pi}{\log n} n$

as ${n \rightarrow \infty}$; in particular, the spacing ${\gamma_{n+1} - \gamma_n}$ should behave like ${\frac{2\pi}{\log n}}$ on the average. However, it can happen that some gaps are unusually small compared to other nearby gaps. For the sake of concreteness, let us define a Lehmer pair to be a pair of adjacent ordinates ${\gamma_n, \gamma_{n+1}}$ such that

$\displaystyle \frac{1}{(\gamma_{n+1} - \gamma_n)^2} \geq 1.3 \sum_{m \neq n,n+1} \frac{1}{(\gamma_m - \gamma_n)^2} + \frac{1}{(\gamma_m - \gamma_{n+1})^2}. \ \ \ \ \ (1)$

The specific value of constant ${1.3}$ is not particularly important here; anything larger than ${\frac{5}{4}}$ would suffice. An example of such a pair would be the classical pair

$\displaystyle \gamma_{6709} = 7005.062866\dots$

$\displaystyle \gamma_{6710} = 7005.100564\dots$

discovered by Lehmer. It follows easily from the main results of Csordas, Smith, and Varga that if an infinite number of Lehmer pairs (in the above sense) existed, then the de Bruijn-Newman constant ${\Lambda}$ is non-negative. This implication is now redundant in view of the unconditional results of this recent paper of Rodgers and myself; however, the question of whether an infinite number of Lehmer pairs exist remain open.

In this post, I sketch an argument that Brad and I came up with (as initially suggested by Odlyzko) the GUE hypothesis implies the existence of infinitely many Lehmer pairs. We argue probabilistically: pick a sufficiently large number ${T}$, pick ${n}$ at random from ${T \log T}$ to ${2 T \log T}$ (so that the average gap size is close to ${\frac{2\pi}{\log T}}$), and prove that the Lehmer pair condition (1) occurs with positive probability.

Introduce the renormalised ordinates ${x_n := \frac{\log T}{2\pi} \gamma_n}$ for ${T \log T \leq n \leq 2 T \log T}$, and let ${\varepsilon > 0}$ be a small absolute constant (independent of ${T}$). It will then suffice to show that

$\displaystyle \frac{1}{(x_{n+1} - x_n)^2} \geq$

$\displaystyle 1.3 \sum_{m \in [T \log T, 2T \log T]: m \neq n,n+1} \frac{1}{(x_m - x_n)^2} + \frac{1}{(x_m - x_{n+1})^2}$

$\displaystyle + \frac{1}{6\varepsilon^2}$

(say) with probability ${\gg \varepsilon^4 - o(1)}$, since the contribution of those ${m}$ outside of ${[T \log T, 2T \log T]}$ can be absorbed by the ${\frac{1}{\varepsilon^2}}$ factor with probability ${o(1)}$.

As one consequence of the GUE hypothesis, we have ${x_{n+1} - x_n \leq \varepsilon^2}$ with probability ${O(\varepsilon^6)}$. Thus, if ${E := \{ m \in [T \log T, 2T \log T]: x_{m+1} - x_m \leq \varepsilon^2 \}}$, then ${E}$ has density ${O( \varepsilon^6 )}$. Applying the Hardy-Littlewood maximal inequality, we see that with probability ${O(\varepsilon^6)}$, we have

$\displaystyle \sup_{h \geq 1} | \# E \cap [n+h, n-h] | \leq \frac{1}{10}$

which implies in particular that

$\displaystyle |x_m - x_n|, |x_{m} - x_{n+1}| \gg \varepsilon^2 |m-n|$

for all ${m \in [T \log T, 2 T \log T] \backslash \{ n, n+1\}}$. This implies in particular that

$\displaystyle \sum_{m \in [T \log T, 2T \log T]: |m-n| \geq \varepsilon^{-3}} \frac{1}{(x_m - x_n)^2} + \frac{1}{(x_m - x_{n+1})^2} \ll \varepsilon^{-1}$

and so it will suffice to show that

$\displaystyle \frac{1}{(x_{n+1} - x_n)^2}$

$\displaystyle \geq 1.3 \sum_{m \in [T \log T, 2T \log T]: m \neq n,n+1; |m-n| < \varepsilon^{-3}} \frac{1}{(x_m - x_n)^2} + \frac{1}{(x_m - x_{n+1})^2} + \frac{1}{5\varepsilon^2}$

(say) with probability ${\gg \varepsilon^4 - o(1)}$.

By the GUE hypothesis (and the fact that ${\varepsilon}$ is independent of ${T}$), it suffices to show that a Dyson sine process ${(x_n)_{n \in {\bf Z}}}$, normalised so that ${x_0}$ is the first positive point in the process, obeys the inequality

$\displaystyle \frac{1}{(x_{1} - x_0)^2} \geq 1.3 \sum_{|m| < \varepsilon^{-3}: m \neq 0,1} \frac{1}{(x_m - x_0)^2} + \frac{1}{(x_m - x_1)^2} \ \ \ \ \ (2)$

with probability ${\gg \varepsilon^4}$. However, if we let ${A > 0}$ be a moderately large constant (and assume ${\varepsilon}$ small depending on ${A}$), one can show using ${k}$-point correlation functions for the Dyson sine process (and the fact that the Dyson kernel ${K(x,y) = \sin(\pi(x-y))/\pi(x-y)}$ equals ${1}$ to second order at the origin) that

$\displaystyle {\bf E} N_{[-\varepsilon,0]} N_{[0,\varepsilon]} \gg \varepsilon^4$

$\displaystyle {\bf E} N_{[-\varepsilon,0]} \binom{N_{[0,\varepsilon]}}{2} \ll \varepsilon^7$

$\displaystyle {\bf E} \binom{N_{[-\varepsilon,0]}}{2} N_{[0,\varepsilon]} \ll \varepsilon^7$

$\displaystyle {\bf E} N_{[-\varepsilon,0]} N_{[0,\varepsilon]} N_{[\varepsilon,A^{-1}]} \ll A^{-3} \varepsilon^4$

$\displaystyle {\bf E} N_{[-\varepsilon,0]} N_{[0,\varepsilon]} N_{[-A^{-1}, -\varepsilon]} \ll A^{-3} \varepsilon^4$

$\displaystyle {\bf E} N_{[-\varepsilon,0]} N_{[0,\varepsilon]} N_{[-k, k]}^2 \ll k^2 \varepsilon^4 \ \ \ \ \ (3)$

for any natural number ${k}$, where ${N_{I}}$ denotes the number of elements of the process in ${I}$. For instance, the expression ${{\bf E} N_{[-\varepsilon,0]} \binom{N_{[0,\varepsilon]}}{2} }$ can be written in terms of the three-point correlation function ${\rho_3(x_1,x_2,x_3) = \mathrm{det}(K(x_i,x_j))_{1 \leq i,j \leq 3}}$ as

$\displaystyle \int_{-\varepsilon \leq x_1 \leq 0 \leq x_2 \leq x_3 \leq \varepsilon} \rho_3( x_1, x_2, x_3 )\ dx_1 dx_2 dx_3$

which can easily be estimated to be ${O(\varepsilon^7)}$ (since ${\rho_3 = O(\varepsilon^4)}$ in this region), and similarly for the other estimates claimed above.

Since for natural numbers ${a,b}$, the quantity ${ab - 2 a \binom{b}{2} - 2 b \binom{a}{2} = ab (5-2a-2b)}$ is only positive when ${a=b=1}$, we see from the first three estimates that the event ${E}$ that ${N_{[-\varepsilon,0]} = N_{[0,\varepsilon]} = 1}$ occurs with probability ${\gg \varepsilon^4}$. In particular, by Markov’s inequality we have the conditional probabilities

$\displaystyle {\bf P} ( N_{[\varepsilon,A^{-1}]} \geq 1 | E ) \ll A^{-3}$

$\displaystyle {\bf P} ( N_{[-A^{-1}, -\varepsilon]} \geq 1 | E ) \ll A^{-3}$

$\displaystyle {\bf P} ( N_{[-k, k]} \geq A k^{5/3} | E ) \ll A^{-4} k^{-4/3}$

and thus, if ${A}$ is large enough, and ${\varepsilon}$ small enough, it will be true with probability ${\gg \varepsilon^4}$ that

$\displaystyle N_{[-\varepsilon,0]}, N_{[0,\varepsilon]} = 1$

and

$\displaystyle N_{[A^{-1}, \varepsilon]} = N_{[\varepsilon, A^{-1}]} = 0$

and simultaneously that

$\displaystyle N_{[-k,k]} \leq A k^{5/3}$

for all natural numbers ${k}$. This implies in particular that

$\displaystyle x_1 - x_0 \leq 2\varepsilon$

and

$\displaystyle |x_m - x_0|, |x_m - x_1| \gg_A |m|^{3/5}$

for all ${m \neq 0,1}$, which gives (2) for ${\varepsilon}$ small enough.

Remark 1 The above argument needed the GUE hypothesis for correlations up to fourth order (in order to establish (3)). It might be possible to reduce the number of correlations needed, but I do not see how to obtain the claim just using pair correlations only.

Let ${\lambda: {\bf N} \rightarrow \{-1,1\}}$ be the Liouville function, thus ${\lambda(n)}$ is defined to equal ${+1}$ when ${n}$ is the product of an even number of primes, and ${-1}$ when ${n}$ is the product of an odd number of primes. The Chowla conjecture asserts that ${\lambda}$ has the statistics of a random sign pattern, in the sense that

$\displaystyle \lim_{N \rightarrow \infty} \mathbb{E}_{n \leq N} \lambda(n+h_1) \dots \lambda(n+h_k) = 0 \ \ \ \ \ (1)$

for all ${k \geq 1}$ and all distinct natural numbers ${h_1,\dots,h_k}$, where we use the averaging notation

$\displaystyle \mathbb{E}_{n \leq N} f(n) := \frac{1}{N} \sum_{n \leq N} f(n).$

For ${k=1}$, this conjecture is equivalent to the prime number theorem (as discussed in this previous blog post), but the conjecture remains open for any ${k \geq 2}$.

In recent years, it has been realised that one can make more progress on this conjecture if one works instead with the logarithmically averaged version

$\displaystyle \lim_{N \rightarrow \infty} \mathbb{E}_{n \leq N}^{\log} \lambda(n+h_1) \dots \lambda(n+h_k) = 0 \ \ \ \ \ (2)$

of the conjecture, where we use the logarithmic averaging notation

$\displaystyle \mathbb{E}_{n \leq N}^{\log} f(n) := \frac{\sum_{n \leq N} \frac{f(n)}{n}}{\sum_{n \leq N} \frac{1}{n}}.$

Using the summation by parts (or telescoping series) identity

$\displaystyle \sum_{n \leq N} \frac{f(n)}{n} = \sum_{M < N} \frac{1}{M(M+1)} (\sum_{n \leq M} f(n)) + \frac{1}{N} \sum_{n \leq N} f(n) \ \ \ \ \ (3)$

it is not difficult to show that the Chowla conjecture (1) for a given ${k,h_1,\dots,h_k}$ implies the logarithmically averaged conjecture (2). However, the converse implication is not at all clear. For instance, for ${k=1}$, we have already mentioned that the Chowla conjecture

$\displaystyle \lim_{N \rightarrow \infty} \mathbb{E}_{n \leq N} \lambda(n) = 0$

is equivalent to the prime number theorem; but the logarithmically averaged analogue

$\displaystyle \lim_{N \rightarrow \infty} \mathbb{E}^{\log}_{n \leq N} \lambda(n) = 0$

is significantly easier to show (a proof with the Liouville function ${\lambda}$ replaced by the closely related Möbius function ${\mu}$ is given in this previous blog post). And indeed, significantly more is now known for the logarithmically averaged Chowla conjecture; in this paper of mine I had proven (2) for ${k=2}$, and in this recent paper with Joni Teravainen, we proved the conjecture for all odd ${k}$ (with a different proof also given here).

In view of this emerging consensus that the logarithmically averaged Chowla conjecture was easier than the ordinary Chowla conjecture, it was thus somewhat of a surprise for me to read a recent paper of Gomilko, Kwietniak, and Lemanczyk who (among other things) established the following statement:

Theorem 1 Assume that the logarithmically averaged Chowla conjecture (2) is true for all ${k}$. Then there exists a sequence ${N_i}$ going to infinity such that the Chowla conjecture (1) is true for all ${k}$ along that sequence, that is to say

$\displaystyle \lim_{N_i \rightarrow \infty} \mathbb{E}_{n \leq N_i} \lambda(n+h_1) \dots \lambda(n+h_k) = 0$

for all ${k}$ and all distinct ${h_1,\dots,h_k}$.

This implication does not use any special properties of the Liouville function (other than that they are bounded), and in fact proceeds by ergodic theoretic methods, focusing in particular on the ergodic decomposition of invariant measures of a shift into ergodic measures. Ergodic methods have proven remarkably fruitful in understanding these sorts of number theoretic and combinatorial problems, as could already be seen by the ergodic theoretic proof of Szemerédi’s theorem by Furstenberg, and more recently by the work of Frantzikinakis and Host on Sarnak’s conjecture. (My first paper with Teravainen also uses ergodic theory tools.) Indeed, many other results in the subject were first discovered using ergodic theory methods.

On the other hand, many results in this subject that were first proven ergodic theoretically have since been reproven by more combinatorial means; my second paper with Teravainen is an instance of this. As it turns out, one can also prove Theorem 1 by a standard combinatorial (or probabilistic) technique known as the second moment method. In fact, one can prove slightly more:

Theorem 2 Let ${k}$ be a natural number. Assume that the logarithmically averaged Chowla conjecture (2) is true for ${2k}$. Then there exists a set ${{\mathcal N}}$ of natural numbers of logarithmic density ${1}$ (that is, ${\lim_{N \rightarrow \infty} \mathbb{E}_{n \leq N}^{\log} 1_{n \in {\mathcal N}} = 1}$) such that

$\displaystyle \lim_{N \rightarrow \infty: N \in {\mathcal N}} \mathbb{E}_{n \leq N} \lambda(n+h_1) \dots \lambda(n+h_k) = 0$

for any distinct ${h_1,\dots,h_k}$.

It is not difficult to deduce Theorem 1 from Theorem 2 using a diagonalisation argument. Unfortunately, the known cases of the logarithmically averaged Chowla conjecture (${k=2}$ and odd ${k}$) are currently insufficient to use Theorem 2 for any purpose other than to reprove what is already known to be true from the prime number theorem. (Indeed, the even cases of Chowla, in either logarithmically averaged or non-logarithmically averaged forms, seem to be far more powerful than the odd cases; see Remark 1.7 of this paper of myself and Teravainen for a related observation in this direction.)

We now sketch the proof of Theorem 2. For any distinct ${h_1,\dots,h_k}$, we take a large number ${H}$ and consider the limiting the second moment

$\displaystyle \limsup_{N \rightarrow \infty} \mathop{\bf E}_{n \leq N}^{\log} |\mathop{\bf E}_{m \leq H} \lambda(n+m+h_1) \dots \lambda(n+m+h_k)|^2.$

We can expand this as

$\displaystyle \limsup_{N \rightarrow \infty} \mathop{\bf E}_{m,m' \leq H} \mathop{\bf E}_{n \leq N}^{\log} \lambda(n+m+h_1) \dots \lambda(n+m+h_k)$

$\displaystyle \lambda(n+m'+h_1) \dots \lambda(n+m'+h_k).$

If all the ${m+h_1,\dots,m+h_k,m'+h_1,\dots,m'+h_k}$ are distinct, the hypothesis (2) tells us that the inner averages goes to zero as ${N \rightarrow \infty}$. The remaining averages are ${O(1)}$, and there are ${O( k^2 )}$ of these averages. We conclude that

$\displaystyle \limsup_{N \rightarrow \infty} \mathop{\bf E}_{n \leq N}^{\log} |\mathop{\bf E}_{m \leq H} \lambda(n+m+h_1) \dots \lambda(n+m+h_k)|^2 \ll k^2 / H.$

By Markov’s inequality (and (3)), we conclude that for any fixed ${h_1,\dots,h_k, H}$, there exists a set ${{\mathcal N}_{h_1,\dots,h_k,H}}$ of upper logarithmic density at least ${1-k/H^{1/2}}$, thus

$\displaystyle \limsup_{N \rightarrow \infty} \mathbb{E}_{n \leq N}^{\log} 1_{n \in {\mathcal N}_{h_1,\dots,h_k,H}} \geq 1 - k/H^{1/2}$

such that

$\displaystyle \mathop{\bf E}_{n \leq N} |\mathop{\bf E}_{m \leq H} \lambda(n+m+h_1) \dots \lambda(n+m+h_k)|^2 \ll k / H^{1/2}.$

By deleting at most finitely many elements, we may assume that ${{\mathcal N}_{h_1,\dots,h_k,H}}$ consists only of elements of size at least ${H^2}$ (say).

For any ${H_0}$, if we let ${{\mathcal N}_{h_1,\dots,h_k, \geq H_0}}$ be the union of ${{\mathcal N}_{h_1,\dots,h_k, H}}$ for ${H \geq H_0}$, then ${{\mathcal N}_{h_1,\dots,h_k, \geq H_0}}$ has logarithmic density ${1}$. By a diagonalisation argument (using the fact that the set of tuples ${(h_1,\dots,h_k)}$ is countable), we can then find a set ${{\mathcal N}}$ of natural numbers of logarithmic density ${1}$, such that for every ${h_1,\dots,h_k,H_0}$, every sufficiently large element of ${{\mathcal N}}$ lies in ${{\mathcal N}_{h_1,\dots,h_k,\geq H_0}}$. Thus for every sufficiently large ${N}$ in ${{\mathcal N}}$, one has

$\displaystyle \mathop{\bf E}_{n \leq N} |\mathop{\bf E}_{m \leq H} \lambda(n+m+h_1) \dots \lambda(n+m+h_k)|^2 \ll k / H^{1/2}.$

for some ${H \geq H_0}$ with ${N \geq H^2}$. By Cauchy-Schwarz, this implies that

$\displaystyle \mathop{\bf E}_{n \leq N} \mathop{\bf E}_{m \leq H} \lambda(n+m+h_1) \dots \lambda(n+m+h_k) \ll k^{1/2} / H^{1/4};$

interchanging the sums and using ${N \geq H^2}$ and ${H \geq H_0}$, this implies that

$\displaystyle \mathop{\bf E}_{n \leq N} \lambda(n+h_1) \dots \lambda(n+h_k) \ll k^{1/2} / H^{1/4} \leq k^{1/2} / H_0^{1/4}.$

We conclude on taking ${H_0}$ to infinity that

$\displaystyle \lim_{N \rightarrow \infty; N \in {\mathcal N}} \mathop{\bf E}_{n \leq N} \lambda(n+h_1) \dots \lambda(n+h_k) = 0$

as required.

Suppose we have an ${n \times n}$ matrix ${M}$ that is expressed in block-matrix form as

$\displaystyle M = \begin{pmatrix} A & B \\ C & D \end{pmatrix}$

where ${A}$ is an ${(n-k) \times (n-k)}$ matrix, ${B}$ is an ${(n-k) \times k}$ matrix, ${C}$ is an ${k \times (n-k)}$ matrix, and ${D}$ is a ${k \times k}$ matrix for some ${1 < k < n}$. If ${A}$ is invertible, we can use the technique of Schur complementation to express the inverse of ${M}$ (if it exists) in terms of the inverse of ${A}$, and the other components ${B,C,D}$ of course. Indeed, to solve the equation

$\displaystyle M \begin{pmatrix} x & y \end{pmatrix} = \begin{pmatrix} a & b \end{pmatrix},$

where ${x, a}$ are ${(n-k) \times 1}$ column vectors and ${y,b}$ are ${k \times 1}$ column vectors, we can expand this out as a system

$\displaystyle Ax + By = a$

$\displaystyle Cx + Dy = b.$

Using the invertibility of ${A}$, we can write the first equation as

$\displaystyle x = A^{-1} a - A^{-1} B y \ \ \ \ \ (1)$

and substituting this into the second equation yields

$\displaystyle (D - C A^{-1} B) y = b - C A^{-1} a$

and thus (assuming that ${D - CA^{-1} B}$ is invertible)

$\displaystyle y = - (D - CA^{-1} B)^{-1} CA^{-1} a + (D - CA^{-1} B)^{-1} b$

and then inserting this back into (1) gives

$\displaystyle x = (A^{-1} + A^{-1} B (D - CA^{-1} B)^{-1} C A^{-1}) a - A^{-1} B (D - CA^{-1} B)^{-1} b.$

Comparing this with

$\displaystyle \begin{pmatrix} x & y \end{pmatrix} = M^{-1} \begin{pmatrix} a & b \end{pmatrix},$

we have managed to express the inverse of ${M}$ as

$\displaystyle M^{-1} =$

$\displaystyle \begin{pmatrix} A^{-1} + A^{-1} B (D - CA^{-1} B)^{-1} C A^{-1} & - A^{-1} B (D - CA^{-1} B)^{-1} \\ - (D - CA^{-1} B)^{-1} CA^{-1} & (D - CA^{-1} B)^{-1} \end{pmatrix}. \ \ \ \ \ (2)$

One can consider the inverse problem: given the inverse ${M^{-1}}$ of ${M}$, does one have a nice formula for the inverse ${A^{-1}}$ of the minor ${A}$? Trying to recover this directly from (2) looks somewhat messy. However, one can proceed as follows. Let ${U}$ denote the ${n \times k}$ matrix

$\displaystyle U := \begin{pmatrix} 0 \\ I_k \end{pmatrix}$

(with ${I_k}$ the ${k \times k}$ identity matrix), and let ${V}$ be its transpose:

$\displaystyle V := \begin{pmatrix} 0 & I_k \end{pmatrix}.$

Then for any scalar ${t}$ (which we identify with ${t}$ times the identity matrix), one has

$\displaystyle M + UtV = \begin{pmatrix} A & B \\ C & D+t \end{pmatrix},$

and hence by (2)

$\displaystyle (M+UtV)^{-1} =$

$\displaystyle \begin{pmatrix} A^{-1} + A^{-1} B (D + t - CA^{-1} B)^{-1} C A^{-1} & - A^{-1} B (D + t- CA^{-1} B)^{-1} \\ - (D + t - CA^{-1} B)^{-1} CA^{-1} & (D + t - CA^{-1} B)^{-1} \end{pmatrix}.$

noting that the inverses here will exist for ${t}$ large enough. Taking limits as ${t \rightarrow \infty}$, we conclude that

$\displaystyle \lim_{t \rightarrow \infty} (M+UtV)^{-1} = \begin{pmatrix} A^{-1} & 0 \\ 0 & 0 \end{pmatrix}.$

On the other hand, by the Woodbury matrix identity (discussed in this previous blog post), we have

$\displaystyle (M+UtV)^{-1} = M^{-1} - M^{-1} U (t^{-1} + V M^{-1} U)^{-1} V M^{-1}$

and hence on taking limits and comparing with the preceding identity, one has

$\displaystyle \begin{pmatrix} A^{-1} & 0 \\ 0 & 0 \end{pmatrix} = M^{-1} - M^{-1} U (V M^{-1} U)^{-1} V M^{-1}.$

This achieves the aim of expressing the inverse ${A^{-1}}$ of the minor in terms of the inverse of the full matrix. Taking traces and rearranging, we conclude in particular that

$\displaystyle \mathrm{tr} A^{-1} = \mathrm{tr} M^{-1} - \mathrm{tr} (V M^{-2} U) (V M^{-1} U)^{-1}. \ \ \ \ \ (3)$

In the ${k=1}$ case, this can be simplified to

$\displaystyle \mathrm{tr} A^{-1} = \mathrm{tr} M^{-1} - \frac{e_n^T M^{-2} e_n}{e_n^T M^{-1} e_n} \ \ \ \ \ (4)$

where ${e_n}$ is the ${n^{th}}$ basis column vector.

We can apply this identity to understand how the spectrum of an ${n \times n}$ random matrix ${M}$ relates to that of its top left ${n-1 \times n-1}$ minor ${A}$. Subtracting any complex multiple ${z}$ of the identity from ${M}$ (and hence from ${A}$), we can relate the Stieltjes transform ${s_M(z) := \frac{1}{n} \mathrm{tr}(M-z)^{-1}}$ of ${M}$ with the Stieltjes transform ${s_A(z) := \frac{1}{n-1} \mathrm{tr}(A-z)^{-1}}$ of ${A}$:

$\displaystyle s_A(z) = \frac{n}{n-1} s_M(z) - \frac{1}{n-1} \frac{e_n^T (M-z)^{-2} e_n}{e_n^T (M-z)^{-1} e_n} \ \ \ \ \ (5)$

At this point we begin to proceed informally. Assume for sake of argument that the random matrix ${M}$ is Hermitian, with distribution that is invariant under conjugation by the unitary group ${U(n)}$; for instance, ${M}$ could be drawn from the Gaussian Unitary Ensemble (GUE), or alternatively ${M}$ could be of the form ${M = U D U^*}$ for some real diagonal matrix ${D}$ and ${U}$ a unitary matrix drawn randomly from ${U(n)}$ using Haar measure. To fix normalisations we will assume that the eigenvalues of ${M}$ are typically of size ${O(1)}$. Then ${A}$ is also Hermitian and ${U(n)}$-invariant. Furthermore, the law of ${e_n^T (M-z)^{-1} e_n}$ will be the same as the law of ${u^* (M-z)^{-1} u}$, where ${u}$ is now drawn uniformly from the unit sphere (independently of ${M}$). Diagonalising ${M}$ into eigenvalues ${\lambda_j}$ and eigenvectors ${v_j}$, we have

$\displaystyle u^* (M-z)^{-1} u = \sum_{j=1}^n \frac{|u^* v_j|^2}{\lambda_j - z}.$

One can think of ${u}$ as a random (complex) Gaussian vector, divided by the magnitude of that vector (which, by the Chernoff inequality, will concentrate to ${\sqrt{n}}$). Thus the coefficients ${u^* v_j}$ with respect to the orthonormal basis ${v_1,\dots,v_j}$ can be thought of as independent (complex) Gaussian vectors, divided by that magnitude. Using this and the Chernoff inequality again, we see (for ${z}$ distance ${\sim 1}$ away from the real axis at least) that one has the concentration of measure

$\displaystyle u^* (M-z)^{-1} u \approx \frac{1}{n} \sum_{j=1}^n \frac{1}{\lambda_j - z}$

and thus

$\displaystyle e_n^T (M-z)^{-1} e_n \approx \frac{1}{n} \mathrm{tr} (M-z)^{-1} = s_M(z)$

(that is to say, the diagonal entries of ${(M-z)^{-1}}$ are roughly constant). Similarly we have

$\displaystyle e_n^T (M-z)^{-2} e_n \approx \frac{1}{n} \mathrm{tr} (M-z)^{-2} = \frac{d}{dz} s_M(z).$

Inserting this into (5) and discarding terms of size ${O(1/n^2)}$, we thus conclude the approximate relationship

$\displaystyle s_A(z) \approx s_M(z) + \frac{1}{n} ( s_M(z) - s_M(z)^{-1} \frac{d}{dz} s_M(z) ).$

This can be viewed as a difference equation for the Stieltjes transform of top left minors of ${M}$. Iterating this equation, and formally replacing the difference equation by a differential equation in the large ${n}$ limit, we see that when ${n}$ is large and ${k \approx e^{-t} n}$ for some ${t \geq 0}$, one expects the top left ${k \times k}$ minor ${A_k}$ of ${M}$ to have Stieltjes transform

$\displaystyle s_{A_k}(z) \approx s( t, z ) \ \ \ \ \ (6)$

where ${s(t,z)}$ solves the Burgers-type equation

$\displaystyle \partial_t s(t,z) = s(t,z) - s(t,z)^{-1} \frac{d}{dz} s(t,z) \ \ \ \ \ (7)$

with initial data ${s(0,z) = s_M(z)}$.

Example 1 If ${M}$ is a constant multiple ${M = cI_n}$ of the identity, then ${s_M(z) = \frac{1}{c-z}}$. One checks that ${s(t,z) = \frac{1}{c-z}}$ is a steady state solution to (7), which is unsurprising given that all minors of ${M}$ are also ${c}$ times the identity.

Example 2 If ${M}$ is GUE normalised so that each entry has variance ${\sigma^2/n}$, then by the semi-circular law (see previous notes) one has ${s_M(z) \approx \frac{-z + \sqrt{z^2-4\sigma^2}}{2\sigma^2} = -\frac{2}{z + \sqrt{z^2-4\sigma^2}}}$ (using an appropriate branch of the square root). One can then verify the self-similar solution

$\displaystyle s(t,z) = \frac{-z + \sqrt{z^2 - 4\sigma^2 e^{-t}}}{2\sigma^2 e^{-t}} = -\frac{2}{z + \sqrt{z^2 - 4\sigma^2 e^{-t}}}$

to (7), which is consistent with the fact that a top ${k \times k}$ minor of ${M}$ also has the law of GUE, with each entry having variance ${\sigma^2 / n \approx \sigma^2 e^{-t} / k}$ when ${k \approx e^{-t} n}$.

One can justify the approximation (6) given a sufficiently good well-posedness theory for the equation (7). We will not do so here, but will note that (as with the classical inviscid Burgers equation) the equation can be solved exactly (formally, at least) by the method of characteristics. For any initial position ${z_0}$, we consider the characteristic flow ${t \mapsto z(t)}$ formed by solving the ODE

$\displaystyle \frac{d}{dt} z(t) = s(t,z(t))^{-1} \ \ \ \ \ (8)$

with initial data ${z(0) = z_0}$, ignoring for this discussion the problems of existence and uniqueness. Then from the chain rule, the equation (7) implies that

$\displaystyle \frac{d}{dt} s( t, z(t) ) = s(t,z(t))$

and thus ${s(t,z(t)) = e^t s(0,z_0)}$. Inserting this back into (8) we see that

$\displaystyle z(t) = z_0 + s(0,z_0)^{-1} (1-e^{-t})$

and thus (7) may be solved implicitly via the equation

$\displaystyle s(t, z_0 + s(0,z_0)^{-1} (1-e^{-t}) ) = e^t s(0, z_0) \ \ \ \ \ (9)$

for all ${t}$ and ${z_0}$.

Remark 3 In practice, the equation (9) may stop working when ${z_0 + s(0,z_0)^{-1} (1-e^{-t})}$ crosses the real axis, as (7) does not necessarily hold in this region. It is a cute exercise (ultimately coming from the Cauchy-Schwarz inequality) to show that this crossing always happens, for instance if ${z_0}$ has positive imaginary part then ${z_0 + s(0,z_0)^{-1}}$ necessarily has negative or zero imaginary part.

Example 4 Suppose we have ${s(0,z) = \frac{1}{c-z}}$ as in Example 1. Then (9) becomes

$\displaystyle s( t, z_0 + (c-z_0) (1-e^{-t}) ) = \frac{e^t}{c-z_0}$

for any ${t,z_0}$, which after making the change of variables ${z = z_0 + (c-z_0) (1-e^{-t}) = c - e^{-t} (c - z_0)}$ becomes

$\displaystyle s(t, z ) = \frac{1}{c-z}$

as in Example 1.

Example 5 Suppose we have

$\displaystyle s(0,z) = \frac{-z + \sqrt{z^2-4\sigma^2}}{2\sigma^2} = -\frac{2}{z + \sqrt{z^2-4\sigma^2}}.$

as in Example 2. Then (9) becomes

$\displaystyle s(t, z_0 - \frac{z_0 + \sqrt{z_0^2-4\sigma^2}}{2} (1-e^{-t}) ) = e^t \frac{-z_0 + \sqrt{z_0^2-4\sigma^2}}{2\sigma^2}.$

If we write

$\displaystyle z := z_0 - \frac{z_0 + \sqrt{z_0^2-4\sigma^2}}{2} (1-e^{-t})$

$\displaystyle = \frac{(1+e^{-t}) z_0 - (1-e^{-t}) \sqrt{z_0^2-4\sigma^2}}{2}$

one can calculate that

$\displaystyle z^2 - 4 \sigma^2 e^{-t} = (\frac{(1-e^{-t}) z_0 - (1+e^{-t}) \sqrt{z_0^2-4\sigma^2}}{2})^2$

and hence

$\displaystyle \frac{-z + \sqrt{z^2 - 4\sigma^2 e^{-t}}}{2\sigma^2 e^{-t}} = e^t \frac{-z_0 + \sqrt{z_0^2-4\sigma^2}}{2\sigma^2}$

which gives

$\displaystyle s(t,z) = \frac{-z + \sqrt{z^2 - 4\sigma^2 e^{-t}}}{2\sigma^2 e^{-t}}. \ \ \ \ \ (10)$

One can recover the spectral measure ${\mu}$ from the Stieltjes transform ${s(z)}$ as the weak limit of ${x \mapsto \frac{1}{\pi} \mathrm{Im} s(x+i\varepsilon)}$ as ${\varepsilon \rightarrow 0}$; we write this informally as

$\displaystyle d\mu(x) = \frac{1}{\pi} \mathrm{Im} s(x+i0^+)\ dx.$

In this informal notation, we have for instance that

$\displaystyle \delta_c(x) = \frac{1}{\pi} \mathrm{Im} \frac{1}{c-x-i0^+}\ dx$

which can be interpreted as the fact that the Cauchy distributions ${\frac{1}{\pi} \frac{\varepsilon}{(c-x)^2+\varepsilon^2}}$ converge weakly to the Dirac mass at ${c}$ as ${\varepsilon \rightarrow 0}$. Similarly, the spectral measure associated to (10) is the semicircular measure ${\frac{1}{2\pi \sigma^2 e^{-t}} (4 \sigma^2 e^{-t}-x^2)_+^{1/2}}$.

If we let ${\mu_t}$ be the spectral measure associated to ${s(t,\cdot)}$, then the curve ${e^{-t} \mapsto \mu_t}$ from ${(0,1]}$ to the space of measures is the high-dimensional limit ${n \rightarrow \infty}$ of a Gelfand-Tsetlin pattern (discussed in this previous post), if the pattern is randomly generated amongst all matrices ${M}$ with spectrum asymptotic to ${\mu_0}$ as ${n \rightarrow \infty}$. For instance, if ${\mu_0 = \delta_c}$, then the curve is ${\alpha \mapsto \delta_c}$, corresponding to a pattern that is entirely filled with ${c}$‘s. If instead ${\mu_0 = \frac{1}{2\pi \sigma^2} (4\sigma^2-x^2)_+^{1/2}}$ is a semicircular distribution, then the pattern is

$\displaystyle \alpha \mapsto \frac{1}{2\pi \sigma^2 \alpha} (4\sigma^2 \alpha -x^2)_+^{1/2},$

thus at height ${\alpha}$ from the top, the pattern is semicircular on the interval ${[-2\sigma \sqrt{\alpha}, 2\sigma \sqrt{\alpha}]}$. The interlacing property of Gelfand-Tsetlin patterns translates to the claim that ${\alpha \mu_\alpha(-\infty,\lambda)}$ (resp. ${\alpha \mu_\alpha(\lambda,\infty)}$) is non-decreasing (resp. non-increasing) in ${\alpha}$ for any fixed ${\lambda}$. In principle one should be able to establish these monotonicity claims directly from the PDE (7) or from the implicit solution (9), but it was not clear to me how to do so.

An interesting example of such a limiting Gelfand-Tsetlin pattern occurs when ${\mu_0 = \frac{1}{2} \delta_{-1} + \frac{1}{2} \delta_1}$, which corresponds to ${M}$ being ${2P-I}$, where ${P}$ is an orthogonal projection to a random ${n/2}$-dimensional subspace of ${{\bf C}^n}$. Here we have

$\displaystyle s(0,z) = \frac{1}{2} \frac{1}{-1-z} + \frac{1}{2} \frac{1}{1-z} = \frac{z}{1-z^2}$

and so (9) in this case becomes

$\displaystyle s(t, z_0 + \frac{1-z_0^2}{z_0} (1-e^{-t}) ) = \frac{e^t z_0}{1-z_0^2}$

A tedious calculation then gives the solution

$\displaystyle s(t,z) = \frac{(2e^{-t}-1)z + \sqrt{z^2 - 4e^{-t}(1-e^{-t})}}{2e^{-t}(1-z^2)}. \ \ \ \ \ (11)$

For ${\alpha = e^{-t} > 1/2}$, there are simple poles at ${z=-1,+1}$, and the associated measure is

$\displaystyle \mu_\alpha = \frac{2\alpha-1}{2\alpha} \delta_{-1} + \frac{2\alpha-1}{2\alpha} \delta_1 + \frac{1}{2\pi \alpha(1-x^2)} (4\alpha(1-\alpha)-x^2)_+^{1/2}\ dx.$

This reflects the interlacing property, which forces ${\frac{2\alpha-1}{2\alpha} \alpha n}$ of the ${\alpha n}$ eigenvalues of the ${\alpha n \times \alpha n}$ minor to be equal to ${-1}$ (resp. ${+1}$). For ${\alpha = e^{-t} \leq 1/2}$, the poles disappear and one just has

$\displaystyle \mu_\alpha = \frac{1}{2\pi \alpha(1-x^2)} (4\alpha(1-\alpha)-x^2)_+^{1/2}\ dx.$

For ${\alpha=1/2}$, one has an inverse semicircle distribution

$\displaystyle \mu_{1/2} = \frac{1}{\pi} (1-x^2)_+^{-1/2}.$

There is presumably a direct geometric explanation of this fact (basically describing the singular values of the product of two random orthogonal projections to half-dimensional subspaces of ${{\bf C}^n}$), but I do not know of one off-hand.

The evolution of ${s(t,z)}$ can also be understood using the ${R}$-transform and ${S}$-transform from free probability. Formally, letlet ${z(t,s)}$ be the inverse of ${s(t,z)}$, thus

$\displaystyle s(t,z(t,s)) = s$

for all ${t,s}$, and then define the ${R}$-transform

$\displaystyle R(t,s) := z(t,-s) - \frac{1}{s}.$

The equation (9) may be rewritten as

$\displaystyle z( t, e^t s ) = z(0,s) + s^{-1} (1-e^{-t})$

and hence

$\displaystyle R(t, -e^t s) = R(0, -s)$

or equivalently

$\displaystyle R(t,s) = R(0, e^{-t} s). \ \ \ \ \ (12)$

See these previous notes for a discussion of free probability topics such as the ${R}$-transform.

Example 6 If ${s(t,z) = \frac{1}{c-z}}$ then the ${R}$ transform is ${R(t,s) = c}$.

Example 7 If ${s(t,z)}$ is given by (10), then the ${R}$ transform is

$\displaystyle R(t,s) = \sigma^2 e^{-t} s.$

Example 8 If ${s(t,z)}$ is given by (11), then the ${R}$ transform is

$\displaystyle R(t,s) = \frac{-1 + \sqrt{1 + 4 s^2 e^{-2t}}}{2 s e^{-t}}.$

This simple relationship (12) is essentially due to Nica and Speicher (thanks to Dima Shylakhtenko for this reference). It has the remarkable consequence that when ${\alpha = 1/m}$ is the reciprocal of a natural number ${m}$, then ${\mu_{1/m}}$ is the free arithmetic mean of ${m}$ copies of ${\mu}$, that is to say ${\mu_{1/m}}$ is the free convolution ${\mu \boxplus \dots \boxplus \mu}$ of ${m}$ copies of ${\mu}$, pushed forward by the map ${\lambda \rightarrow \lambda/m}$. In terms of random matrices, this is asserting that the top ${n/m \times n/m}$ minor of a random matrix ${M}$ has spectral measure approximately equal to that of an arithmetic mean ${\frac{1}{m} (M_1 + \dots + M_m)}$ of ${m}$ independent copies of ${M}$, so that the process of taking top left minors is in some sense a continuous analogue of the process of taking freely independent arithmetic means. There ought to be a geometric proof of this assertion, but I do not know of one. In the limit ${m \rightarrow \infty}$ (or ${\alpha \rightarrow 0}$), the ${R}$-transform becomes linear and the spectral measure becomes semicircular, which is of course consistent with the free central limit theorem.

In a similar vein, if one defines the function

$\displaystyle \omega(t,z) := \alpha \int_{\bf R} \frac{zx}{1-zx}\ d\mu_\alpha(x) = e^{-t} (- 1 - z^{-1} s(t, z^{-1}))$

and inverts it to obtain a function ${z(t,\omega)}$ with

$\displaystyle \omega(t, z(t,\omega)) = \omega$

for all ${t, \omega}$, then the ${S}$-transform ${S(t,\omega)}$ is defined by

$\displaystyle S(t,\omega) := \frac{1+\omega}{\omega} z(t,\omega).$

Writing

$\displaystyle s(t,z) = - z^{-1} ( 1 + e^t \omega(t, z^{-1}) )$

for any ${t}$, ${z}$, we have

$\displaystyle z_0 + s(0,z_0)^{-1} (1-e^{-t}) = z_0 \frac{\omega(0,z_0^{-1})+e^{-t}}{\omega(0,z_0^{-1})+1}$

and so (9) becomes

$\displaystyle - z_0^{-1} \frac{\omega(0,z_0^{-1})+1}{\omega(0,z_0^{-1})+e^{-t}} (1 + e^{t} \omega(t, z_0^{-1} \frac{\omega(0,z_0^{-1})+1}{\omega(0,z_0^{-1})+e^{-t}}))$

$\displaystyle = - e^t z_0^{-1} (1 + \omega(0, z_0^{-1}))$

which simplifies to

$\displaystyle \omega(t, z_0^{-1} \frac{\omega(0,z_0^{-1})+1}{\omega(0,z_0^{-1})+e^{-t}})) = \omega(0, z_0^{-1});$

replacing ${z_0}$ by ${z(0,\omega)^{-1}}$ we obtain

$\displaystyle \omega(t, z(0,\omega) \frac{\omega+1}{\omega+e^{-t}}) = \omega$

and thus

$\displaystyle z(0,\omega)\frac{\omega+1}{\omega+e^{-t}} = z(t, \omega)$

and hence

$\displaystyle S(0, \omega) = \frac{\omega+e^{-t}}{\omega+1} S(t, \omega).$

One can compute ${\frac{\omega+e^{-t}}{\omega+1}}$ to be the ${S}$-transform of the measure ${(1-\alpha) \delta_0 + \alpha \delta_1}$; from the link between ${S}$-transforms and free products (see e.g. these notes of Guionnet), we conclude that ${(1-\alpha)\delta_0 + \alpha \mu_\alpha}$ is the free product of ${\mu_1}$ and ${(1-\alpha) \delta_0 + \alpha \delta_1}$. This is consistent with the random matrix theory interpretation, since ${(1-\alpha)\delta_0 + \alpha \mu_\alpha}$ is also the spectral measure of ${PMP}$, where ${P}$ is the orthogonal projection to the span of the first ${\alpha n}$ basis elements, so in particular ${P}$ has spectral measure ${(1-\alpha) \delta_0 + \alpha \delta_1}$. If ${M}$ is unitarily invariant then (by a fundamental result of Voiculescu) it is asymptotically freely independent of ${P}$, so the spectral measure of ${PMP = P^{1/2} M P^{1/2}}$ is asymptotically the free product of that of ${M}$ and of ${P}$.

In July I will be spending a week at Park City, being one of the mini-course lecturers in the Graduate Summer School component of the Park City Summer Session on random matrices.  I have chosen to give some lectures on least singular values of random matrices, the circular law, and the Lindeberg exchange method in random matrix theory; this is a slightly different set of topics than I had initially advertised (which was instead about the Lindeberg exchange method and the local relaxation flow method), but after consulting with the other mini-course lecturers I felt that this would be a more complementary set of topics.  I have uploaded an draft of my lecture notes (some portion of which is derived from my monograph on the subject); as always, comments and corrections are welcome.

[Update, June 23: notes revised and reformatted to PCMI format. -T.]

[Update, Mar 19 2018: further revision. -T.]

This is a postscript to the previous blog post which was concerned with obtaining heuristic asymptotic predictions for the correlation

$\displaystyle \sum_{n \leq x} \tau(n) \tau(n+h), \ \ \ \ \ (1)$

for the divisor function ${\tau(n) := \sum_{d|n} 1}$, in particular recovering the calculation of Ingham that obtained the asymptotic

$\displaystyle \sum_{n \leq x} \tau(n) \tau(n+h) \sim \frac{6}{\pi^2} \sigma_{-1}(h) x \log^2 x \ \ \ \ \ (2)$

when ${h}$ was fixed and non-zero and ${x}$ went to infinity. It is natural to consider the more general correlations

$\displaystyle \sum_{n \leq x} \tau_k(n) \tau_l(n+h)$

for fixed ${k,l \geq 1}$ and non-zero ${h}$, where

$\displaystyle \tau_k(n) := \sum_{d_1 \dots d_k = n} 1$

is the order ${k}$ divisor function. The sum (1) then corresponds to the case ${k=l=2}$. For ${l=1}$, ${\tau_1(n) = 1}$, and a routine application of the Dirichlet hyperbola method (or Perron’s formula) gives the asymptotic

$\displaystyle \sum_{n \leq x} \tau_k(n) \sim \frac{\log^{k-1} x}{(k-1)!} x,$

or more accurately

$\displaystyle \sum_{n \leq x} \tau_k(n) \sim P_k(\log x) x$

where ${P_k(t)}$ is a certain explicit polynomial of degree ${k-1}$ with leading coefficient ${\frac{1}{(k-1)!}}$; see e.g. Exercise 31 of this previous post for a discussion of the ${k=3}$ case (which is already typical). Similarly if ${k=1}$. For more general ${k,l \geq 1}$, there is a conjecture of Conrey and Gonek which predicts that

$\displaystyle \sum_{n \leq x} \tau_k(n) \tau_l(n+h) \sim P_{k,l,h}(\log x) x$

for some polynomial ${P_{k,l,h}(t)}$ of degree ${k+l-2}$ which is explicit but whose form is rather complicated (one has to compute residues of a various complicated products of zeta functions and local factors). This conjecture has been verified when ${k \leq 2}$ or ${l \leq 2}$, by the work of Linnik, Motohashi, Fouvry-Tenenbaum, and others, but all the remaining cases when ${k,l \geq 3}$ are currently open.

In principle, the calculations of the previous post should recover the predictions of Conrey and Gonek. In this post I would like to record this for the top order term:

Conjecture 1 If ${k,l \geq 2}$ and ${h \neq 0}$ are fixed, then

$\displaystyle \sum_{n \leq x} \tau_k(n) \tau_l(n+h) \sim \frac{\log^{k-1} x}{(k-1)!} \frac{\log^{l-1} x}{(l-1)!} x \prod_p {\mathfrak S}_{k,l,p}(h)$

as ${x \rightarrow \infty}$, where the product is over all primes ${p}$, and the local factors ${{\mathfrak S}_{k,l,p}(h)}$ are given by the formula

$\displaystyle {\mathfrak S}_{k,l,p}(h) := (\frac{p-1}{p})^{k+l-2} \sum_{j \geq 0: p^j|h} \frac{1}{p^j} P_{k,l,p}(j) \ \ \ \ \ (3)$

where ${P_{k,l,p}}$ is the degree ${k+l-4}$ polynomial

$\displaystyle P_{k,l,p}(j) := \sum_{k'=2}^k \sum_{l'=2}^l \binom{k-k'+j-1}{k-k'} \binom{l-l'+j-1}{l-l'} \alpha_{k',l',p}$

where

$\displaystyle \alpha_{k',l',p} := (\frac{p}{p-1})^{k'-1} + (\frac{p}{p-1})^{l'-1} - 1$

and one adopts the conventions that ${\binom{-1}{0} = 1}$ and ${\binom{m-1}{m} = 0}$ for ${m \geq 1}$.

For instance, if ${k=l=2}$ then

$\displaystyle P_{2,2,p}(h) = \frac{p}{p-1} + \frac{p}{p-1} - 1 = \frac{p+1}{p-1}$

and hence

$\displaystyle {\mathfrak S}_{2,2,p}(h) = (1 - \frac{1}{p^2}) \sum_{j \geq 0: p^j|h} \frac{1}{p^j}$

and the above conjecture recovers the Ingham formula (2). For ${k=2, l=3}$, we have

$\displaystyle P_{2,3,p}(h) =$

$\displaystyle (\frac{p}{p-1} + (\frac{p}{p-1})^2 - 1) + (\frac{p}{p-1} + \frac{p}{p-1} - 1) j$

$\displaystyle = \frac{p^2+p-1}{(p-1)^2} + \frac{p+1}{p-1} j$

and so we predict

$\displaystyle \sum_{n \leq x} \tau(n) \tau_3(n+h) \sim \frac{x \log^3 x}{2} \prod_p {\mathfrak S}_{2,3,p}(h)$

where

$\displaystyle {\mathfrak S}_{2,3,p}(h) = \sum_{j \geq 0: p^j|h} \frac{\frac{p^3 - 2p + 1}{p^3} + \frac{(p+1)(p-1)^2}{p^3} j}{p^j}.$

Similarly, if ${k=l=3}$ we have

$\displaystyle P_{3,3,p}(h) = ((\frac{p}{p-1})^2 + (\frac{p}{p-1})^2 - 1) + 2 (\frac{p}{p-1} + (\frac{p}{p-1})^2 - 1) j$

$\displaystyle + (\frac{p}{p-1} + \frac{p}{p-1} - 1) j^2$

$\displaystyle = \frac{p^2+2p-1}{(p-1)^2} + 2 \frac{p^2+p-1}{(p-1)^2} j + \frac{p+1}{p-1} j^2$

and so we predict

$\displaystyle \sum_{n \leq x} \tau_3(n) \tau_3(n+h) \sim \frac{x \log^4 x}{4} \prod_p {\mathfrak S}_{3,3,p}(h)$

where

$\displaystyle {\mathfrak S}_{3,3,p}(h) = \sum_{j \geq 0: p^j|h} \frac{\frac{p^4 - 4p^2 + 4p - 1}{p^4} + 2 \frac{(p^2+p-1)(p-1)^2}{p^4} j + \frac{(p+1)(p-1)^3}{p^4} j^2}{p^j}.$

and so forth.

As in the previous blog, the idea is to factorise

$\displaystyle \tau_k(n) = \prod_p \tau_{k,p}(n)$

where the local factors ${\tau_{k,p}(n)}$ are given by

$\displaystyle \tau_{k,p}(n) := \sum_{j_1,\dots,j_k \geq 0: p^{j_1+\dots+j_k} || n} 1$

(where ${p^j || n}$ means that ${p}$ divides ${n}$ precisely ${j}$ times), or in terms of the valuation ${v_p(n)}$ of ${n}$ at ${p}$,

$\displaystyle \tau_{k,p}(n) = \binom{k-1+v_p(n)}{k-1}. \ \ \ \ \ (4)$

We then have the following exact local asymptotics:

Proposition 2 (Local correlations) Let ${{\bf n}}$ be a profinite integer chosen uniformly at random, let ${h}$ be a profinite integer, and let ${k,l \geq 2}$. Then

$\displaystyle {\bf E} \tau_{k,p}({\bf n}) = (\frac{p}{p-1})^{k-1} \ \ \ \ \ (5)$

and

$\displaystyle {\bf E} \tau_{k,p}({\bf n}) \tau_{l,p}({\bf n}+h) = (\frac{p}{p-1})^{k+l-2} {\mathfrak S}_{k,l,p}(h). \ \ \ \ \ (6)$

(For profinite integers it is possible that ${v_p({\bf n})}$ and hence ${\tau_{k,p}({\bf n})}$ are infinite, but this is a probability zero event and so can be ignored.)

Conjecture 1 can then be heuristically justified from the local calculations (2) by various pseudorandomness heuristics, as discussed in the previous post.

I’ll give a short proof of the above proposition below, basically using the recursive methods of the previous post. This short proof actually took be quite a while to find; I spent several hours and a fair bit of scratch paper working out the cases ${k,l = 2,3}$ laboriously by hand (with some assistance and cross-checking from Maple). Here is an unorganised sample of some of this scratch, just to show how the sausage is actually made:

It was only after expending all this effort that I realised that it would be much more efficient to compute the correlations for all values of ${k,l}$ simultaneously by using generating functions. After performing this computation, it then became apparent that there would be a direct combinatorial proof of (6) that was shorter than even the generating function proof. (I will not supply the full generating function calculations here, but will at least show them for the easier correlation (5).)

I am confident that Conjecture 1 is consistent with the explicit asymptotic in the Conrey-Gonek conjecture, but have not yet rigorously established that the leading order term in the latter is indeed identical to the expression provided above.

Let ${\tau(n) := \sum_{d|n} 1}$ be the divisor function. A classical application of the Dirichlet hyperbola method gives the asymptotic

$\displaystyle \sum_{n \leq x} \tau(n) \sim x \log x$

where ${X \sim Y}$ denotes the estimate ${X = (1+o(1))Y}$ as ${x \rightarrow \infty}$. Much better error estimates are possible here, but we will not focus on the lower order terms in this discussion. For somewhat idiosyncratic reasons I will interpret this estimate (and the other analytic number theory estimates discussed here) through the probabilistic lens. Namely, if ${{\bf n} = {\bf n}_x}$ is a random number selected uniformly between ${1}$ and ${x}$, then the above estimate can be written as

$\displaystyle {\bf E} \tau( {\bf n} ) \sim \log x, \ \ \ \ \ (1)$

that is to say the random variable ${\tau({\bf n})}$ has mean approximately ${\log x}$. (But, somewhat paradoxically, this is not the median or mode behaviour of this random variable, which instead concentrates near ${\log^{\log 2} x}$, basically thanks to the Hardy-Ramanujan theorem.)

Now we turn to the pair correlations ${\sum_{n \leq x} \tau(n) \tau(n+h)}$ for a fixed positive integer ${h}$. There is a classical computation of Ingham that shows that

$\displaystyle \sum_{n \leq x} \tau(n) \tau(n+h) \sim \frac{6}{\pi^2} \sigma_{-1}(h) x \log^2 x, \ \ \ \ \ (2)$

where

$\displaystyle \sigma_{-1}(h) := \sum_{d|h} \frac{1}{d}.$

The error term in (2) has been refined by many subsequent authors, as has the uniformity of the estimates in the ${h}$ aspect, as these topics are related to other questions in analytic number theory, such as fourth moment estimates for the Riemann zeta function; but we will not consider these more subtle features of the estimate here. However, we will look at the next term in the asymptotic expansion for (2) below the fold.

Using our probabilistic lens, the estimate (2) can be written as

$\displaystyle {\bf E} \tau( {\bf n} ) \tau( {\bf n} + h ) \sim \frac{6}{\pi^2} \sigma_{-1}(h) \log^2 x. \ \ \ \ \ (3)$

From (1) (and the asymptotic negligibility of the shift by ${h}$) we see that the random variables ${\tau({\bf n})}$ and ${\tau({\bf n}+h)}$ both have a mean of ${\sim \log x}$, so the additional factor of ${\frac{6}{\pi^2} \sigma_{-1}(h)}$ represents some arithmetic coupling between the two random variables.

Ingham’s formula can be established in a number of ways. Firstly, one can expand out ${\tau(n) = \sum_{d|n} 1}$ and use the hyperbola method (splitting into the cases ${d \leq \sqrt{x}}$ and ${n/d \leq \sqrt{x}}$ and removing the overlap). If one does so, one soon arrives at the task of having to estimate sums of the form

$\displaystyle \sum_{n \leq x: d|n} \tau(n+h)$

for various ${d \leq \sqrt{x}}$. For ${d}$ much less than ${\sqrt{x}}$ this can be achieved using a further application of the hyperbola method, but for ${d}$ comparable to ${\sqrt{x}}$ things get a bit more complicated, necessitating the use of non-trivial estimates on Kloosterman sums in order to obtain satisfactory control on error terms. A more modern approach proceeds using automorphic form methods, as discussed in this previous post. A third approach, which unfortunately is only heuristic at the current level of technology, is to apply the Hardy-Littlewood circle method (discussed in this previous post) to express (2) in terms of exponential sums ${\sum_{n \leq x} \tau(n) e(\alpha n)}$ for various frequencies ${\alpha}$. The contribution of “major arc” ${\alpha}$ can be computed after a moderately lengthy calculation which yields the right-hand side of (2) (as well as the correct lower order terms that are currently being suppressed), but there does not appear to be an easy way to show directly that the “minor arc” contributions are of lower order, although the methods discussed previously do indirectly show that this is ultimately the case.

Each of the methods outlined above requires a fair amount of calculation, and it is not obvious while performing them that the factor ${\frac{6}{\pi^2} \sigma_{-1}(h)}$ will emerge at the end. One can at least explain the ${\frac{6}{\pi^2}}$ as a normalisation constant needed to balance the ${\sigma_{-1}(h)}$ factor (at a heuristic level, at least). To see this through our probabilistic lens, introduce an independent copy ${{\bf n}'}$ of ${{\bf n}}$, then

$\displaystyle {\bf E} \tau( {\bf n} ) \tau( {\bf n}' ) = ({\bf E} \tau ({\bf n}))^2 \sim \log^2 x; \ \ \ \ \ (4)$

using symmetry to order ${{\bf n}' > {\bf n}}$ (discarding the diagonal case ${{\bf n} = {\bf n}'}$) and making the change of variables ${{\bf n}' = {\bf n}+h}$, we see that (4) is heuristically consistent with (3) as long as the asymptotic mean of ${\frac{6}{\pi^2} \sigma_{-1}(h)}$ in ${h}$ is equal to ${1}$. (This argument is not rigorous because there was an implicit interchange of limits present, but still gives a good heuristic “sanity check” of Ingham’s formula.) Indeed, if ${{\bf E}_h}$ denotes the asymptotic mean in ${h}$, then we have (heuristically at least)

$\displaystyle {\bf E}_h \sigma_{-1}(h) = \sum_d {\bf E}_h \frac{1}{d} 1_{d|h}$

$\displaystyle = \sum_d \frac{1}{d^2}$

$\displaystyle = \frac{\pi^2}{6}$

and we obtain the desired consistency after multiplying by ${\frac{6}{\pi^2}}$.

This still however does not explain the presence of the ${\sigma_{-1}(h)}$ factor. Intuitively it is reasonable that if ${h}$ has many prime factors, and ${{\bf n}}$ has a lot of factors, then ${{\bf n}+h}$ will have slightly more factors than average, because any common factor to ${h}$ and ${{\bf n}}$ will automatically be acquired by ${{\bf n}+h}$. But how to quantify this effect?

One heuristic way to proceed is through analysis of local factors. Observe from the fundamental theorem of arithmetic that we can factor

$\displaystyle \tau(n) = \prod_p \tau_p(n)$

where the product is over all primes ${p}$, and ${\tau_p(n) := \sum_{p^j|n} 1}$ is the local version of ${\tau(n)}$ at ${p}$ (which in this case, is just one plus the ${p}$valuation ${v_p(n)}$ of ${n}$: ${\tau_p = 1 + v_p}$). Note that all but finitely many of the terms in this product will equal ${1}$, so the infinite product is well-defined. In a similar fashion, we can factor

$\displaystyle \sigma_{-1}(h) = \prod_p \sigma_{-1,p}(h)$

where

$\displaystyle \sigma_{-1,p}(h) := \sum_{p^j|h} \frac{1}{p^j}$

(or in terms of valuations, ${\sigma_{-1,p}(h) = (1 - p^{-v_p(h)-1})/(1-p^{-1})}$). Heuristically, the Chinese remainder theorem suggests that the various factors ${\tau_p({\bf n})}$ behave like independent random variables, and so the correlation between ${\tau({\bf n})}$ and ${\tau({\bf n}+h)}$ should approximately decouple into the product of correlations between the local factors ${\tau_p({\bf n})}$ and ${\tau_p({\bf n}+h)}$. And indeed we do have the following local version of Ingham’s asymptotics:

Proposition 1 (Local Ingham asymptotics) For fixed ${p}$ and integer ${h}$, we have

$\displaystyle {\bf E} \tau_p({\bf n}) \sim \frac{p}{p-1}$

and

$\displaystyle {\bf E} \tau_p({\bf n}) \tau_p({\bf n}+h) \sim (1-\frac{1}{p^2}) \sigma_{-1,p}(h) (\frac{p}{p-1})^2$

$\displaystyle = \frac{p+1}{p-1} \sigma_{-1,p}(h)$

From the Euler formula

$\displaystyle \prod_p (1-\frac{1}{p^2}) = \frac{1}{\zeta(2)} = \frac{6}{\pi^2}$

we see that

$\displaystyle \frac{6}{\pi^2} \sigma_{-1}(h) = \prod_p (1-\frac{1}{p^2}) \sigma_{-1,p}(h)$

and so one can “explain” the arithmetic factor ${\frac{6}{\pi^2} \sigma_{-1}(h)}$ in Ingham’s asymptotic as the product of the arithmetic factors ${(1-\frac{1}{p^2}) \sigma_{-1,p}(h)}$ in the (much easier) local Ingham asymptotics. Unfortunately we have the usual “local-global” problem in that we do not know how to rigorously derive the global asymptotic from the local ones; this problem is essentially the same issue as the problem of controlling the minor arc contributions in the circle method, but phrased in “physical space” language rather than “frequency space”.

Remark 2 The relation between the local means ${\sim \frac{p}{p-1}}$ and the global mean ${\sim \log^2 x}$ can also be seen heuristically through the application

$\displaystyle \prod_{p \leq x^{1/e^\gamma}} \frac{p}{p-1} \sim \log x$

of Mertens’ theorem, where ${1/e^\gamma}$ is Pólya’s magic exponent, which serves as a useful heuristic limiting threshold in situations where the product of local factors is divergent.

Let us now prove this proposition. One could brute-force the computations by observing that for any fixed ${j}$, the valuation ${v_p({\bf n})}$ is equal to ${j}$ with probability ${\sim \frac{p-1}{p} \frac{1}{p^j}}$, and with a little more effort one can also compute the joint distribution of ${v_p({\bf n})}$ and ${v_p({\bf n}+h)}$, at which point the proposition reduces to the calculation of various variants of the geometric series. I however find it cleaner to proceed in a more recursive fashion (similar to how one can prove the geometric series formula by induction); this will also make visible the vague intuition mentioned previously about how common factors of ${{\bf n}}$ and ${h}$ force ${{\bf n}+h}$ to have a factor also.

It is first convenient to get rid of error terms by observing that in the limit ${x \rightarrow \infty}$, the random variable ${{\bf n} = {\bf n}_x}$ converges vaguely to a uniform random variable ${{\bf n}_\infty}$ on the profinite integers ${\hat {\bf Z}}$, or more precisely that the pair ${(v_p({\bf n}_x), v_p({\bf n}_x+h))}$ converges vaguely to ${(v_p({\bf n}_\infty), v_p({\bf n}_\infty+h))}$. Because of this (and because of the easily verified uniform integrability properties of ${\tau_p({\bf n})}$ and their powers), it suffices to establish the exact formulae

$\displaystyle {\bf E} \tau_p({\bf n}_\infty) = \frac{p}{p-1} \ \ \ \ \ (5)$

and

$\displaystyle {\bf E} \tau_p({\bf n}_\infty) \tau_p({\bf n}_\infty+h) = (1-\frac{1}{p^2}) \sigma_{-1,p}(h) (\frac{p}{p-1})^2 = \frac{p+1}{p-1} \sigma_{-1,p}(h) \ \ \ \ \ (6)$

in the profinite setting (this setting will make it easier to set up the recursion).

We begin with (5). Observe that ${{\bf n}_\infty}$ is coprime to ${p}$ with probability ${\frac{p-1}{p}}$, in which case ${\tau_p({\bf n}_\infty)}$ is equal to ${1}$. Conditioning to the complementary probability ${\frac{1}{p}}$ event that ${{\bf n}_\infty}$ is divisible by ${p}$, we can factor ${{\bf n}_\infty = p {\bf n}'_\infty}$ where ${{\bf n}'_\infty}$ is also uniformly distributed over the profinite integers, in which event we have ${\tau_p( {\bf n}_\infty ) = 1 + \tau_p( {\bf n}'_\infty )}$. We arrive at the identity

$\displaystyle {\bf E} \tau_p({\bf n}_\infty) = \frac{p-1}{p} + \frac{1}{p} ( 1 + {\bf E} \tau_p( {\bf n}'_\infty ) ).$

As ${{\bf n}_\infty}$ and ${{\bf n}'_\infty}$ have the same distribution, the quantities ${{\bf E} \tau_p({\bf n}_\infty)}$ and ${{\bf E} \tau_p({\bf n}'_\infty)}$ are equal, and (5) follows by a brief amount of high-school algebra.

We use a similar method to treat (6). First treat the case when ${h}$ is coprime to ${p}$. Then we see that with probability ${\frac{p-2}{p}}$, ${{\bf n}_\infty}$ and ${{\bf n}_\infty+h}$ are simultaneously coprime to ${p}$, in which case ${\tau_p({\bf n}_\infty) = \tau_p({\bf n}_\infty+h) = 1}$. Furthermore, with probability ${\frac{1}{p}}$, ${{\bf n}_\infty}$ is divisible by ${p}$ and ${{\bf n}_\infty+h}$ is not; in which case we can write ${{\bf n} = p {\bf n}'}$ as before, with ${\tau_p({\bf n}_\infty) = 1 + \tau_p({\bf n}'_\infty)}$ and ${\tau_p({\bf n}_\infty+h)=1}$. Finally, in the remaining event with probability ${\frac{1}{p}}$, ${{\bf n}+h}$ is divisible by ${p}$ and ${{\bf n}}$ is not; we can then write ${{\bf n}_\infty+h = p {\bf n}'_\infty}$, so that ${\tau_p({\bf n}_\infty+h) = 1 + \tau_p({\bf n}'_\infty)}$ and ${\tau_p({\bf n}_\infty) = 1}$. Putting all this together, we obtain

$\displaystyle {\bf E} \tau_p({\bf n}_\infty) \tau_p({\bf n}_\infty+h) = \frac{p-2}{p} + 2 \frac{1}{p} (1 + {\bf E} \tau_p({\bf n}'_\infty))$

and the claim (6) in this case follows from (5) and a brief computation (noting that ${\sigma_{-1,p}(h)=1}$ in this case).

Now suppose that ${h}$ is divisible by ${p}$, thus ${h=ph'}$ for some integer ${h'}$. Then with probability ${\frac{p-1}{p}}$, ${{\bf n}_\infty}$ and ${{\bf n}_\infty+h}$ are simultaneously coprime to ${p}$, in which case ${\tau_p({\bf n}_\infty) = \tau_p({\bf n}_\infty+h) = 1}$. In the remaining ${\frac{1}{p}}$ event, we can write ${{\bf n}_\infty = p {\bf n}'_\infty}$, and then ${\tau_p({\bf n}_\infty) = 1 + \tau_p({\bf n}'_\infty)}$ and ${\tau_p({\bf n}_\infty+h) = 1 + \tau_p({\bf n}'_\infty+h')}$. Putting all this together we have

$\displaystyle {\bf E} \tau_p({\bf n}_\infty) \tau_p({\bf n}_\infty+h) = \frac{p-1}{p} + \frac{1}{p} {\bf E} (1+\tau_p({\bf n}'_\infty)(1+\tau_p({\bf n}'_\infty+h)$

which by (5) (and replacing ${{\bf n}'_\infty}$ by ${{\bf n}_\infty}$) leads to the recursive relation

$\displaystyle {\bf E} \tau_p({\bf n}_\infty) \tau_p({\bf n}_\infty+h) = \frac{p+1}{p-1} + \frac{1}{p} {\bf E} \tau_p({\bf n}_\infty) \tau_p({\bf n}_\infty+h)$

and (6) then follows by induction on the number of powers of ${p}$.

The estimate (2) of Ingham was refined by Estermann, who obtained the more accurate expansion

$\displaystyle \sum_{n \leq x} \tau(n) \tau(n+h) = \frac{6}{\pi^2} \sigma_{-1}(h) x \log^2 x + a_1(h) x \log x + a_2(h) x \ \ \ \ \ (7)$

$\displaystyle + O( x^{11/12+o(1)} )$

for certain complicated but explicit coefficients ${a_1(h), a_2(h)}$. For instance, ${a_1(h)}$ is given by the formula

$\displaystyle a_1(h) = (\frac{12}{\pi^2} (2\gamma-1) + 4 a') \sigma_{-1}(h) - \frac{24}{\pi^2} \sigma'_{-1}(h)$

where ${\gamma}$ is the Euler-Mascheroni constant,

$\displaystyle a' := - \sum_{r=1}^\infty \frac{\mu(r)}{r^2} \log r, \ \ \ \ \ (8)$

and

$\displaystyle \sigma'_{-1}(h) := \sum_{d|h} \frac{\log d}{d}.$

The formula for ${a_2(h)}$ is similar but even more complicated. The error term ${O( x^{11/12+o(1)})}$ was improved by Heath-Brown to ${O( x^{5/6+o(1)})}$; it is conjectured (for instance by Conrey and Gonek) that one in fact has square root cancellation ${O( x^{1/2+o(1)})}$ here, but this is well out of reach of current methods.

These lower order terms are traditionally computed either from a Dirichlet series approach (using Perron’s formula) or a circle method approach. It turns out that a refinement of the above heuristics can also predict these lower order terms, thus keeping the calculation purely in physical space as opposed to the “multiplicative frequency space” of the Dirichlet series approach, or the “additive frequency space” of the circle method, although the computations are arguably as messy as the latter computations for the purposes of working out the lower order terms. We illustrate this just for the ${a_1(h) x \log x}$ term below the fold.