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

In everyday usage, we rely heavily on percentages to quantify probabilities and proportions: we might say that a prediction is ${50\%}$ accurate or ${80\%}$ accurate, that there is a ${2\%}$ chance of dying from some disease, and so forth. However, for those without extensive mathematical training, it can sometimes be difficult to assess whether a given percentage amounts to a “good” or “bad” outcome, because this depends very much on the context of how the percentage is used. For instance:

• (i) In a two-party election, an outcome of say ${51\%}$ to ${49\%}$ might be considered close, but ${55\%}$ to ${45\%}$ would probably be viewed as a convincing mandate, and ${60\%}$ to ${40\%}$ would likely be viewed as a landslide.
• (ii) Similarly, if one were to poll an upcoming election, a poll of ${51\%}$ to ${49\%}$ would be too close to call, ${55\%}$ to ${45\%}$ would be an extremely favorable result for the candidate, and ${60\%}$ to ${40\%}$ would mean that it would be a major upset if the candidate lost the election.
• (iii) On the other hand, a medical operation that only had a ${51\%}$, ${55\%}$, or ${60\%}$ chance of success would be viewed as being incredibly risky, especially if failure meant death or permanent injury to the patient. Even an operation that was ${90\%}$ or ${95\%}$ likely to be non-fatal (i.e., a ${10\%}$ or ${5\%}$ chance of death) would not be conducted lightly.
• (iv) A weather prediction of, say, ${30\%}$ chance of rain during a vacation trip might be sufficient cause to pack an umbrella, even though it is more likely than not that rain would not occur. On the other hand, if the prediction was for an ${80\%}$ chance of rain, and it ended up that the skies remained clear, this does not seriously damage the accuracy of the prediction – indeed, such an outcome would be expected in one out of every five such predictions.
• (v) Even extremely tiny percentages of toxic chemicals in everyday products can be considered unacceptable. For instance, EPA rules require action to be taken when the percentage of lead in drinking water exceeds ${0.0000015\%}$ (15 parts per billion). At the opposite extreme, recycling contamination rates as high as ${10\%}$ are often considered acceptable.

Because of all the very different ways in which percentages could be used, I think it may make sense to propose an alternate system of units to measure one class of probabilities, namely the probabilities of avoiding some highly undesirable outcome, such as death, accident or illness. The units I propose are that of “nines“, which are already commonly used to measure availability of some service or purity of a material, but can be equally used to measure the safety (i.e., lack of risk) of some activity. Informally, nines measure how many consecutive appearances of the digit ${9}$ are in the probability of successfully avoiding the negative outcome, thus

• ${90\%}$ success = one nine of safety
• ${99\%}$ success = two nines of safety
• ${99.9\%}$ success = three nines of safety
and so forth. Using the mathematical device of logarithms, one can also assign a fractional number of nines of safety to a general probability:

Definition 1 (Nines of safety) An activity (affecting one or more persons, over some given period of time) that has a probability ${p}$ of the “safe” outcome and probability ${1-p}$ of the “unsafe” outcome will have ${k}$ nines of safety against the unsafe outcome, where ${k}$ is defined by the formula

$\displaystyle k = -\log_{10}(1-p) \ \ \ \ \ (1)$

(where ${\log_{10}}$ is the logarithm to base ten), or equivalently

$\displaystyle p = 1 - 10^{-k}. \ \ \ \ \ (2)$

Remark 2 Because of the various uncertainties in measuring probabilities, as well as the inaccuracies in some of the assumptions and approximations we will be making later, we will not attempt to measure the number of nines of safety beyond the first decimal point; thus we will round to the nearest tenth of a nine of safety throughout this post.

Here is a conversion table between percentage rates of success (the safe outcome), failure (the unsafe outcome), and the number of nines of safety one has:

 Success rate ${p}$ Failure rate ${1-p}$ Number of nines ${k}$ ${0\%}$ ${100\%}$ ${0.0}$ ${50\%}$ ${50\%}$ ${0.3}$ ${75\%}$ ${25\%}$ ${0.6}$ ${80\%}$ ${20\%}$ ${0.7}$ ${90\%}$ ${10\%}$ ${1.0}$ ${95\%}$ ${5\%}$ ${1.3}$ ${97.5\%}$ ${2.5\%}$ ${1.6}$ ${98\%}$ ${2\%}$ ${1.7}$ ${99\%}$ ${1\%}$ ${2.0}$ ${99.5\%}$ ${0.5\%}$ ${2.3}$ ${99.75\%}$ ${0.25\%}$ ${2.6}$ ${99.8\%}$ ${0.2\%}$ ${2.7}$ ${99.9\%}$ ${0.1\%}$ ${3.0}$ ${99.95\%}$ ${0.05\%}$ ${3.3}$ ${99.975\%}$ ${0.025\%}$ ${3.6}$ ${99.98\%}$ ${0.02\%}$ ${3.7}$ ${99.99\%}$ ${0.01\%}$ ${4.0}$ ${100\%}$ ${0\%}$ infinite

Thus, if one has no nines of safety whatsoever, one is guaranteed to fail; but each nine of safety one has reduces the failure rate by a factor of ${10}$. In an ideal world, one would have infinitely many nines of safety against any risk, but in practice there are no ${100\%}$ guarantees against failure, and so one can only expect a finite amount of nines of safety in any given situation. Realistically, one should thus aim to have as many nines of safety as one can reasonably expect to have, but not to demand an infinite amount.

Remark 3 The number of nines of safety against a certain risk is not absolute; it will depend not only on the risk itself, but (a) the number of people exposed to the risk, and (b) the length of time one is exposed to the risk. Exposing more people or increasing the duration of exposure will reduce the number of nines, and conversely exposing fewer people or reducing the duration will increase the number of nines; see Proposition 7 below for a rough rule of thumb in this regard.

Remark 4 Nines of safety are a logarithmic scale of measurement, rather than a linear scale. Other familiar examples of logarithmic scales of measurement include the Richter scale of earthquake magnitude, the pH scale of acidity, the decibel scale of sound level, octaves in music, and the magnitude scale for stars.

Remark 5 One way to think about nines of safety is via the Swiss cheese model that was created recently to describe pandemic risk management. In this model, each nine of safety can be thought of as a slice of Swiss cheese, with holes occupying ${10\%}$ of that slice. Having ${k}$ nines of safety is then analogous to standing behind ${k}$ such slices of Swiss cheese. In order for a risk to actually impact you, it must pass through each of these ${k}$ slices. A fractional nine of safety corresponds to a fractional slice of Swiss cheese that covers the amount of space given by the above table. For instance, ${0.6}$ nines of safety corresponds to a fractional slice that covers about ${75\%}$ of the given area (leaving ${25\%}$ uncovered).

Now to give some real-world examples of nines of safety. Using data for deaths in the US in 2019 (without attempting to account for factors such as age and gender), a random US citizen will have had the following amount of safety from dying from some selected causes in that year:

 Cause of death Mortality rate per ${100,\! 000}$ (approx.) Nines of safety All causes ${870}$ ${2.0}$ Heart disease ${200}$ ${2.7}$ Cancer ${180}$ ${2.7}$ Accidents ${52}$ ${3.3}$ Drug overdose ${22}$ ${3.7}$ Influenza/Pneumonia ${15}$ ${3.8}$ Suicide ${14}$ ${3.8}$ Gun violence ${12}$ ${3.9}$ Car accident ${11}$ ${4.0}$ Murder ${5}$ ${4.3}$ Airplane crash ${0.14}$ ${5.9}$ Lightning strike ${0.006}$ ${7.2}$

The safety of air travel is particularly remarkable: a given hour of flying in general aviation has a fatality rate of ${0.00001}$, or about ${5}$ nines of safety, while for the major carriers the fatality rate drops down to ${0.0000005}$, or about ${7.3}$ nines of safety.

Of course, in 2020, COVID-19 deaths became significant. In this year in the US, the mortality rate for COVID-19 (as the underlying or contributing cause of death) was ${91.5}$ per ${100,\! 000}$, corresponding to ${3.0}$ nines of safety, which was less safe than all other causes of death except for heart disease and cancer. At this time of writing, data for all of 2021 is of course not yet available, but it seems likely that the safety level would be even lower for this year.

Some further illustrations of the concept of nines of safety:

• Each round of Russian roulette has a success rate of ${5/6}$, providing only ${0.8}$ nines of safety. Of course, the safety will decrease with each additional round: one has only ${0.5}$ nines of safety after two rounds, ${0.4}$ nines after three rounds, and so forth. (See also Proposition 7 below.)
• The ancient Roman punishment of decimation, by definition, provided exactly one nine of safety to each soldier being punished.
• Rolling a ${1}$ on a ${20}$-sided die is a risk that carries about ${1.3}$ nines of safety.
• Rolling a double one (“snake eyes“) from two six-sided dice carries about ${1.6}$ nines of safety.
• One has about ${2.6}$ nines of safety against the risk of someone randomly guessing your birthday on the first attempt.
• A null hypothesis has ${1.3}$ nines of safety against producing a ${p = 0.05}$ statistically significant result, and ${2.0}$ nines against producing a ${p=0.01}$ statistically significant result. (However, one has to be careful when reversing the conditional; a ${p=0.01}$ statistically significant result does not necessarily have ${2.0}$ nines of safety against the null hypothesis. In Bayesian statistics, the precise relationship between the two risks is given by Bayes’ theorem.)
• If a poker opponent is dealt a five-card hand, one has ${5.8}$ nines of safety against that opponent being dealt a royal flush, ${4.8}$ against a straight flush or higher, ${3.6}$ against four-of-a-kind or higher, ${2.8}$ against a full house or higher, ${2.4}$ against a flush or higher, ${2.1}$ against a straight or higher, ${1.5}$ against three-of-a-kind or higher, ${1.1}$ against two pairs or higher, and just ${0.3}$ against one pair or higher. (This data was converted from this Wikipedia table.)
• A ${k}$-digit PIN number (or a ${k}$-digit combination lock) carries ${k}$ nines of safety against each attempt to randomly guess the PIN. A length ${k}$ password that allows for numbers, upper and lower case letters, and punctuation carries about ${2k}$ nines of safety against a single guess. (For the reduction in safety caused by multiple guesses, see Proposition 7 below.)

Here is another way to think about nines of safety:

Proposition 6 (Nines of safety extend expected onset of risk) Suppose a certain risky activity has ${k}$ nines of safety. If one repeatedly indulges in this activity until the risk occurs, then the expected number of trials before the risk occurs is ${10^k}$.

Proof: The probability that the risk is activated after exactly ${n}$ trials is ${(1-10^{-k})^{n-1} 10^{-k}}$, which is a geometric distribution of parameter ${10^k}$. The claim then follows from the standard properties of that distribution. $\Box$

Thus, for instance, if one performs some risky activity daily, then the expected length of time before the risk occurs is given by the following table:

 Daily nines of safety Expected onset of risk ${0}$ One day ${0.8}$ One week ${1.5}$ One month ${2.6}$ One year ${2.9}$ Two years ${3.3}$ Five years ${3.6}$ Ten years ${3.9}$ Twenty years ${4.3}$ Fifty years ${4.6}$ A century

Or, if one wants to convert the yearly risks of dying from a specific cause into expected years before that cause of death would occur (assuming for sake of discussion that no other cause of death exists):

 Yearly nines of safety Expected onset of risk ${0}$ One year ${0.3}$ Two years ${0.7}$ Five years ${1}$ Ten years ${1.3}$ Twenty years ${1.7}$ Fifty years ${2.0}$ A century

These tables suggest a relationship between the amount of safety one would have in a short timeframe, such as a day, and a longer time frame, such as a year. Here is an approximate formalisation of that relationship:

Proposition 7 (Repeated exposure reduces nines of safety) If a risky activity with ${k}$ nines of safety is (independently) repeated ${m}$ times, then (assuming ${k}$ is large enough depending on ${m}$), the repeated activity will have approximately ${k - \log_{10} m}$ nines of safety. Conversely: if the repeated activity has ${k'}$ nines of safety, the individual activity will have approximately ${k' + \log_{10} m}$ nines of safety.

Proof: An activity with ${k}$ nines of safety will be safe with probability ${1-10^{-k}}$, hence safe with probability ${(1-10^{-k})^m}$ if repeated independently ${m}$ times. For ${k}$ large, we can approximate

$\displaystyle (1 - 10^{-k})^m \approx 1 - m 10^{-k} = 1 - 10^{-(k - \log_{10} m)}$

giving the former claim. The latter claim follows from inverting the former. $\Box$

Remark 8 The hypothesis of independence here is key. If there is a lot of correlation between the risks between different repetitions of the activity, then there can be much less reduction in safety caused by that repetition. As a simple example, suppose that ${90\%}$ of a workforce are trained to perform some task flawlessly no matter how many times they repeat the task, but the remaining ${10\%}$ are untrained and will always fail at that task. If one selects a random worker and asks them to perform the task, one has ${1.0}$ nines of safety against the task failing. If one took that same random worker and asked them to perform the task ${m}$ times, the above proposition might suggest that the number of nines of safety would drop to approximately ${1.0 - \log_{10} m}$; but in this case there is perfect correlation, and in fact the number of nines of safety remains steady at ${1.0}$ since it is the same ${10\%}$ of the workforce that would fail each time.

Because of this caveat, one should view the above proposition as only a crude first approximation that can be used as a simple rule of thumb, but should not be relied upon for more precise calculations.

One can repeat a risk either in time (extending the time of exposure to the risk, say from a day to a year), or in space (by exposing the risk to more people). The above proposition then gives an additive conversion law for nines of safety in either case. Here are some conversion tables for time:

 From/to Daily Weekly Monthly Yearly Daily 0 -0.8 -1.5 -2.6 Weekly +0.8 0 -0.6 -1.7 Monthly +1.5 +0.6 0 -1.1 Yearly +2.6 +1.7 +1.1 0

 From/to Yearly Per 5 yr Per decade Per century Yearly 0 -0.7 -1.0 -2.0 Per 5 yr +0.7 0 -0.3 -1.3 Per decade +1.0 + -0.3 0 -1.0 Per century +2.0 +1.3 +1.0 0

For instance, as mentioned before, the yearly amount of safety against cancer is about ${2.7}$. Using the above table (and making the somewhat unrealistic hypothesis of independence), we then predict the daily amount of safety against cancer to be about ${2.7 + 2.6 = 5.3}$ nines, the weekly amount to be about ${2.7 + 1.7 = 4.4}$ nines, and the amount of safety over five years to drop to about ${2.7 - 0.7 = 2.0}$ nines.

Now we turn to conversions in space. If one knows the level of safety against a certain risk for an individual, and then one (independently) exposes a group of such individuals to that risk, then the reduction in nines of safety when considering the possibility that at least one group member experiences this risk is given by the following table:

 Group Reduction in safety You (${1}$ person) ${0}$ You and your partner (${2}$ people) ${-0.3}$ You and your parents (${3}$ people) ${-0.5}$ You, your partner, and three children (${5}$ people) ${-0.7}$ An extended family of ${10}$ people ${-1.0}$ A class of ${30}$ people ${-1.5}$ A workplace of ${100}$ people ${-2.0}$ A school of ${1,\! 000}$ people ${-3.0}$ A university of ${10,\! 000}$ people ${-4.0}$ A town of ${100,\! 000}$ people ${-5.0}$ A city of ${1}$ million people ${-6.0}$ A state of ${10}$ million people ${-7.0}$ A country of ${100}$ million people ${-8.0}$ A continent of ${1}$ billion people ${-9.0}$ The entire planet ${-9.8}$

For instance, in a given year (and making the somewhat implausible assumption of independence), you might have ${2.7}$ nines of safety against cancer, but you and your partner collectively only have about ${2.7 - 0.3 = 2.4}$ nines of safety against this risk, your family of five might only have about ${2.7 - 0.7 = 2}$ nines of safety, and so forth. By the time one gets to a group of ${1,\! 000}$ people, it actually becomes very likely that at least one member of the group will die of cancer in that year. (Here the precise conversion table breaks down, because a negative number of nines such as ${2.7 - 3.0 = -0.3}$ is not possible, but one should interpret a prediction of a negative number of nines as an assertion that failure is very likely to happen. Also, in practice the reduction in safety is less than this rule predicts, due to correlations such as risk factors that are common to the group being considered that are incompatible with the assumption of independence.)

In the opposite direction, any reduction in exposure (either in time or space) to a risk will increase one’s safety level, as per the following table:

 Reduction in exposure Additional nines of safety ${\div 1}$ ${0}$ ${\div 2}$ ${+0.3}$ ${\div 3}$ ${+0.5}$ ${\div 5}$ ${+0.7}$ ${\div 10}$ ${+1.0}$ ${\div 100}$ ${+2.0}$

For instance, a five-fold reduction in exposure will reclaim about ${0.7}$ additional nines of safety.

Here is a slightly different way to view nines of safety:

Proposition 9 Suppose that a group of ${m}$ people are independently exposed to a given risk. If there are at most

$\displaystyle \log_{10} \frac{1}{1-2^{-1/m}}$

nines of individual safety against that risk, then there is at least a ${50\%}$ chance that one member of the group is affected by the risk.

Proof: If individually there are ${k}$ nines of safety, then the probability that all the members of the group avoid the risk is ${(1-10^{-k})^m}$. Since the inequality

$\displaystyle (1-10^{-k})^m \leq \frac{1}{2}$

is equivalent to

$\displaystyle k \leq \log_{10} \frac{1}{1-2^{-1/m}},$

the claim follows. $\Box$

Thus, for a group to collectively avoid a risk with at least a ${50\%}$ chance, one needs the following level of individual safety:

 Group Individual safety level required You (${1}$ person) ${0.3}$ You and your partner (${2}$ people) ${0.5}$ You and your parents (${3}$ people) ${0.7}$ You, your partner, and three children (${5}$ people) ${0.9}$ An extended family of ${10}$ people ${1.2}$ A class of ${30}$ people ${1.6}$ A workplace of ${100}$ people ${2.2}$ A school of ${1,\! 000}$ people ${3.2}$ A university of ${10,\! 000}$ people ${4.2}$ A town of ${100,\! 000}$ people ${5.2}$ A city of ${1}$ million people ${6.2}$ A state of ${10}$ million people ${7.2}$ A country of ${100}$ million people ${8.2}$ A continent of ${1}$ billion people ${9.2}$ The entire planet ${10.0}$

For large ${m}$, the level ${k}$ of nines of individual safety required to protect a group of size ${m}$ with probability at least ${50\%}$ is approximately ${\log_{10} \frac{m}{\ln 2} \approx (\log_{10} m) + 0.2}$.

Precautions that can work to prevent a certain risk from occurring will add additional nines of safety against that risk, even if the precaution is not ${100\%}$ effective. Here is the precise rule:

Proposition 10 (Precautions add nines of safety) Suppose an activity carries ${k}$ nines of safety against a certain risk, and a separate precaution can independently protect against that risk with ${l}$ nines of safety (that is to say, the probability that the protection is effective is ${1 - 10^{-l}}$). Then applying that precaution increases the number of nines in the activity from ${k}$ to ${k+l}$.

Proof: The probability that the precaution fails and the risk then occurs is ${10^{-l} \times 10^{-k} = 10^{-(k+l)}}$. The claim now follows from Definition 1. $\Box$

In particular, we can repurpose the table at the start of this post as a conversion chart for effectiveness of a precaution:

 Effectiveness Failure rate Additional nines provided ${0\%}$ ${100\%}$ ${+0.0}$ ${50\%}$ ${50\%}$ ${+0.3}$ ${75\%}$ ${25\%}$ ${+0.6}$ ${80\%}$ ${20\%}$ ${+0.7}$ ${90\%}$ ${10\%}$ ${+1.0}$ ${95\%}$ ${5\%}$ ${+1.3}$ ${97.5\%}$ ${2.5\%}$ ${+1.6}$ ${98\%}$ ${2\%}$ ${+1.7}$ ${99\%}$ ${1\%}$ ${+2.0}$ ${99.5\%}$ ${0.5\%}$ ${+2.3}$ ${99.75\%}$ ${0.25\%}$ ${+2.6}$ ${99.8\%}$ ${0.2\%}$ ${+2.7}$ ${99.9\%}$ ${0.1\%}$ ${+3.0}$ ${99.95\%}$ ${0.05\%}$ ${+3.3}$ ${99.975\%}$ ${0.025\%}$ ${+3.6}$ ${99.98\%}$ ${0.02\%}$ ${+3.7}$ ${99.99\%}$ ${0.01\%}$ ${+4.0}$ ${100\%}$ ${0\%}$ infinite

Thus for instance a precaution that is ${80\%}$ effective will add ${0.7}$ nines of safety, a precaution that is ${99.8\%}$ effective will add ${2.7}$ nines of safety, and so forth. The mRNA COVID vaccines by Pfizer and Moderna have somewhere between ${88\% - 96\%}$ effectiveness against symptomatic COVID illness, providing about ${0.9-1.4}$ nines of safety against that risk, and over ${95\%}$ effectiveness against severe illness, thus adding at least ${1.3}$ nines of safety in this regard.

A slight variant of the above rule can be stated using the concept of relative risk:

Proposition 11 (Relative risk and nines of safety) Suppose an activity carries ${k}$ nines of safety against a certain risk, and an action multiplies the chance of failure by some relative risk ${R}$. Then the action removes ${\log_{10} R}$ nines of safety (if ${R > 1}$) or adds ${-\log_{10} R}$ nines of safety (if ${R<1}$) to the original activity.

Proof: The additional action adjusts the probability of failure from ${10^{-k}}$ to ${R \times 10^{-k} = 10^{-(k - \log_{10} R)}}$. The claim now follows from Definition 1. $\Box$

Here is a conversion chart between relative risk and change in nines of safety:

 Relative risk Change in nines of safety ${0.01}$ ${+2.0}$ ${0.02}$ ${+1.7}$ ${0.05}$ ${+1.3}$ ${0.1}$ ${+1.0}$ ${0.2}$ ${+0.7}$ ${0.5}$ ${+0.3}$ ${1}$ ${0}$ ${2}$ ${-0.3}$ ${5}$ ${-0.7}$ ${10}$ ${-1.0}$ ${20}$ ${-1.3}$ ${50}$ ${-1.7}$ ${100}$ ${-2.0}$

Some examples:

• Smoking increases the fatality rate of lung cancer by a factor of about ${20}$, thus removing about ${1.3}$ nines of safety from this particular risk; it also increases the fatality rates of several other diseases, though not quite as dramatically an extent.
• Seatbelts reduce the fatality rate in car accidents by a factor of about two, adding about ${0.3}$ nines of safety. Airbags achieve a reduction of about ${30-50\%}$, adding about ${0.2-0.3}$ additional nines of safety.
• As far as transmission of COVID is concerned, it seems that constant use of face masks reduces transmission by a factor of about five (thus adding about ${0.7}$ nines of safety), and similarly for constant adherence to social distancing; whereas for instance a ${30\%}$ compliance with mask usage reduced transmission by about ${10\%}$ (adding only ${0.05}$ or so nines of safety).

The effect of combining multiple (independent) precautions together is cumulative; one can achieve quite a high level of safety by stacking together several precautions that individually have relatively low levels of effectiveness. Again, see the “swiss cheese model” referred to in Remark 5. For instance, if face masks add ${0.7}$ nines of safety against contracting COVID, social distancing adds another ${0.7}$ nines, and the vaccine provide another ${1.0}$ nine of safety, implementing all three mitigation methods would (assuming independence) add a net of ${2.4}$ nines of safety against contracting COVID.

In summary, when debating the value of a given risk mitigation measure, the correct question to ask is not quite “Is it certain to work” or “Can it fail?”, but rather “How many extra nines of safety does it add?”.

As one final comparison between nines of safety and other standard risk measures, we give the following proposition regarding large deviations from the mean.

Proposition 12 Let ${X}$ be a normally distributed random variable of standard deviation ${\sigma}$, and let ${\lambda > 0}$. Then the “one-sided risk” of ${X}$ exceeding its mean ${{\bf E} X}$ by at least ${\lambda \sigma}$ (i.e., ${X \geq {\bf E} X + \lambda \sigma}$) carries

$\displaystyle -\log_{10} \frac{1 - \mathrm{erf}(\lambda/\sqrt{2})}{2}$

nines of safety, the “two-sided risk” of ${X}$ deviating (in either direction) from its mean by at least ${\lambda \sigma}$ (i.e., ${|X-{\bf E} X| \geq \lambda \sigma}$) carries

$\displaystyle -\log_{10} (1 - \mathrm{erf}(\lambda/\sqrt{2}))$

nines of safety, where ${\mathrm{erf}}$ is the error function.

Proof: This is a routine calculation using the cumulative distribution function of the normal distribution. $\Box$

Here is a short table illustrating this proposition:

 Number ${\lambda}$ of deviations from the mean One-sided nines of safety Two-sided nines of safety ${0}$ ${0.3}$ ${0.0}$ ${1}$ ${0.8}$ ${0.5}$ ${2}$ ${1.6}$ ${1.3}$ ${3}$ ${2.9}$ ${2.6}$ ${4}$ ${4.5}$ ${4.2}$ ${5}$ ${6.5}$ ${6.2}$ ${6}$ ${9.0}$ ${8.7}$

Thus, for instance, the risk of a five sigma event (deviating by more than five standard deviations from the mean in either direction) should carry ${6.2}$ nines of safety assuming a normal distribution, and so one would ordinarily feel extremely safe against the possibility of such an event, unless one started doing hundreds of thousands of trials. (However, we caution that this conclusion relies heavily on the assumption that one has a normal distribution!)

See also this older essay I wrote on anonymity on the internet, using bits as a measure of anonymity in much the same way that nines are used here as a measure of safety.

Asgar Jamneshan and I have just uploaded to the arXiv our paper “Foundational aspects of uncountable measure theory: Gelfand duality, Riesz representation, canonical models, and canonical disintegration“. This paper arose from our longer-term project to systematically develop “uncountable” ergodic theory – ergodic theory in which the groups acting are not required to be countable, the probability spaces one acts on are not required to be standard Borel, or Polish, and the compact groups that arise in the structural theory (e.g., the theory of group extensions) are not required to be separable. One of the motivations of doing this is to allow ergodic theory results to be applied to ultraproducts of finite dynamical systems, which can then hopefully be transferred to establish combinatorial results with good uniformity properties. An instance of this is the uncountable Mackey-Zimmer theorem, discussed in this companion blog post.

In the course of this project, we ran into the obstacle that many foundational results, such as the Riesz representation theorem, often require one or more of these countability hypotheses when encountered in textbooks. Other technical issues also arise in the uncountable setting, such as the need to distinguish the Borel ${\sigma}$-algebra from the (two different types of) Baire ${\sigma}$-algebra. As such we needed to spend some time reviewing and synthesizing the known literature on some foundational results of “uncountable” measure theory, which led to this paper. As such, most of the results of this paper are already in the literature, either explicitly or implicitly, in one form or another (with perhaps the exception of the canonical disintegration, which we discuss below); we view the main contribution of this paper as presenting the results in a coherent and unified fashion. In particular we found that the language of category theory was invaluable in clarifying and organizing all the different results. In subsequent work we (and some other authors) will use the results in this paper for various applications in uncountable ergodic theory.

The foundational results covered in this paper can be divided into a number of subtopics (Gelfand duality, Baire ${\sigma}$-algebras and Riesz representation, canonical models, and canonical disintegration), which we discuss further below the fold.

Dimitri Shlyakhtenko and I have uploaded to the arXiv our paper Fractional free convolution powers. For me, this project (which we started during the 2018 IPAM program on quantitative linear algebra) was motivated by a desire to understand the behavior of the minor process applied to a large random Hermitian ${N \times N}$ matrix ${A_N}$, in which one takes the successive upper left ${n \times n}$ minors ${A_n}$ of ${A_N}$ and computes their eigenvalues ${\lambda_1(A_n) \leq \dots \leq \lambda_n(A_n)}$ in non-decreasing order. These eigenvalues are related to each other by the Cauchy interlacing inequalities

$\displaystyle \lambda_i(A_{n+1}) \leq \lambda_i(A_n) \leq \lambda_{i+1}(A_{n+1})$

for ${1 \leq i \leq n < N}$, and are often arranged in a triangular array known as a Gelfand-Tsetlin pattern, as discussed in these previous blog posts.

When ${N}$ is large and the matrix ${A_N}$ is a random matrix with empirical spectral distribution converging to some compactly supported probability measure ${\mu}$ on the real line, then under suitable hypotheses (e.g., unitary conjugation invariance of the random matrix ensemble ${A_N}$), a “concentration of measure” effect occurs, with the spectral distribution of the minors ${A_n}$ for ${n = \lfloor N/k\rfloor}$ for any fixed ${k \geq 1}$ converging to a specific measure ${k^{-1}_* \mu^{\boxplus k}}$ that depends only on ${\mu}$ and ${k}$. The reason for this notation is that there is a surprising description of this measure ${k^{-1}_* \mu^{\boxplus k}}$ when ${k}$ is a natural number, namely it is the free convolution ${\mu^{\boxplus k}}$ of ${k}$ copies of ${\mu}$, pushed forward by the dilation map ${x \mapsto k^{-1} x}$. For instance, if ${\mu}$ is the Wigner semicircular measure ${d\mu_{sc} = \frac{1}{\pi} (4-x^2)^{1/2}_+\ dx}$, then ${k^{-1}_* \mu_{sc}^{\boxplus k} = k^{-1/2}_* \mu_{sc}}$. At the random matrix level, this reflects the fact that the minor of a GUE matrix is again a GUE matrix (up to a renormalizing constant).

As first observed by Bercovici and Voiculescu and developed further by Nica and Speicher, among other authors, the notion of a free convolution power ${\mu^{\boxplus k}}$ of ${\mu}$ can be extended to non-integer ${k \geq 1}$, thus giving the notion of a “fractional free convolution power”. This notion can be defined in several different ways. One of them proceeds via the Cauchy transform

$\displaystyle G_\mu(z) := \int_{\bf R} \frac{d\mu(x)}{z-x}$

of the measure ${\mu}$, and ${\mu^{\boxplus k}}$ can be defined by solving the Burgers-type equation

$\displaystyle (k \partial_k + z \partial_z) G_{\mu^{\boxplus k}}(z) = \frac{\partial_z G_{\mu^{\boxplus k}}(z)}{G_{\mu^{\boxplus k}}(z)} \ \ \ \ \ (1)$

with initial condition ${G_{\mu^{\boxplus 1}} = G_\mu}$ (see this previous blog post for a derivation). This equation can be solved explicitly using the ${R}$-transform ${R_\mu}$ of ${\mu}$, defined by solving the equation

$\displaystyle \frac{1}{G_\mu(z)} + R_\mu(G_\mu(z)) = z$

for sufficiently large ${z}$, in which case one can show that

$\displaystyle R_{\mu^{\boxplus k}}(z) = k R_\mu(z).$

(In the case of the semicircular measure ${\mu_{sc}}$, the ${R}$-transform is simply the identity: ${R_{\mu_{sc}}(z)=z}$.)

Nica and Speicher also gave a free probability interpretation of the fractional free convolution power: if ${A}$ is a noncommutative random variable in a noncommutative probability space ${({\mathcal A},\tau)}$ with distribution ${\mu}$, and ${p}$ is a real projection operator free of ${A}$ with trace ${1/k}$, then the “minor” ${[pAp]}$ of ${A}$ (viewed as an element of a new noncommutative probability space ${({\mathcal A}_p, \tau_p)}$ whose elements are minors ${[pXp]}$, ${X \in {\mathcal A}}$ with trace ${\tau_p([pXp]) := k \tau(pXp)}$) has the law of ${k^{-1}_* \mu^{\boxplus k}}$ (we give a self-contained proof of this in an appendix to our paper). This suggests that the minor process (or fractional free convolution) can be studied within the framework of free probability theory.

One of the known facts about integer free convolution powers ${\mu^{\boxplus k}}$ is monotonicity of the free entropy

$\displaystyle \chi(\mu) = \int_{\bf R} \int_{\bf R} \log|s-t|\ d\mu(s) d\mu(t) + \frac{3}{4} + \frac{1}{2} \log 2\pi$

and free Fisher information

$\displaystyle \Phi(\mu) = \frac{2\pi^2}{3} \int_{\bf R} \left(\frac{d\mu}{dx}\right)^3\ dx$

which were introduced by Voiculescu as free probability analogues of the classical probability concepts of differential entropy and classical Fisher information. (Here we correct a small typo in the normalization constant of Fisher entropy as presented in Voiculescu’s paper.) Namely, it was shown by Shylakhtenko that the quantity ${\chi(k^{-1/2}_* \mu^{\boxplus k})}$ is monotone non-decreasing for integer ${k}$, and the Fisher information ${\Phi(k^{-1/2}_* \mu^{\boxplus k})}$ is monotone non-increasing for integer ${k}$. This is the free probability analogue of the corresponding monotonicities for differential entropy and classical Fisher information that was established by Artstein, Ball, Barthe, and Naor, answering a question of Shannon.

Our first main result is to extend the monotonicity results of Shylakhtenko to fractional ${k \geq 1}$. We give two proofs of this fact, one using free probability machinery, and a more self contained (but less motivated) proof using integration by parts and contour integration. The free probability proof relies on the concept of the free score ${J(X)}$ of a noncommutative random variable, which is the analogue of the classical score. The free score, also introduced by Voiculescu, can be defined by duality as measuring the perturbation with respect to semicircular noise, or more precisely

$\displaystyle \frac{d}{d\varepsilon} \tau( Z P( X + \varepsilon Z) )|_{\varepsilon=0} = \tau( J(X) P(X) )$

whenever ${P}$ is a polynomial and ${Z}$ is a semicircular element free of ${X}$. If ${X}$ has an absolutely continuous law ${\mu = f\ dx}$ for a sufficiently regular ${f}$, one can calculate ${J(X)}$ explicitly as ${J(X) = 2\pi Hf(X)}$, where ${Hf}$ is the Hilbert transform of ${f}$, and the Fisher information is given by the formula

$\displaystyle \Phi(X) = \tau( J(X)^2 ).$

One can also define a notion of relative free score ${J(X:B)}$ relative to some subalgebra ${B}$ of noncommutative random variables.

The free score interacts very well with the free minor process ${X \mapsto [pXp]}$, in particular by standard calculations one can establish the identity

$\displaystyle J( [pXp] : [pBp] ) = k {\bf E}( [p J(X:B) p] | [pXp], [pBp] )$

whenever ${X}$ is a noncommutative random variable, ${B}$ is an algebra of noncommutative random variables, and ${p}$ is a real projection of trace ${1/k}$ that is free of both ${X}$ and ${B}$. The monotonicity of free Fisher information then follows from an application of Pythagoras’s theorem (which implies in particular that conditional expectation operators are contractions on ${L^2}$). The monotonicity of free entropy then follows from an integral representation of free entropy as an integral of free Fisher information along the free Ornstein-Uhlenbeck process (or equivalently, free Fisher information is essentially the rate of change of free entropy with respect to perturbation by semicircular noise). The argument also shows when equality holds in the monotonicity inequalities; this occurs precisely when ${\mu}$ is a semicircular measure up to affine rescaling.

After an extensive amount of calculation of all the quantities that were implicit in the above free probability argument (in particular computing the various terms involved in the application of Pythagoras’ theorem), we were able to extract a self-contained proof of monotonicity that relied on differentiating the quantities in ${k}$ and using the differential equation (1). It turns out that if ${d\mu = f\ dx}$ for sufficiently regular ${f}$, then there is an identity

$\displaystyle \partial_k \Phi( k^{-1/2}_* \mu^{\boxplus k} ) = -\frac{1}{2\pi^2} \lim_{\varepsilon \rightarrow 0} \sum_{\alpha,\beta = \pm} f(x) f(y) K(x+i\alpha \varepsilon, y+i\beta \varepsilon)\ dx dy \ \ \ \ \ (2)$

where ${K}$ is the kernel

$\displaystyle K(z,w) := \frac{1}{G(z) G(w)} (\frac{G(z)-G(w)}{z-w} + G(z) G(w))^2$

and ${G(z) := G_\mu(z)}$. It is not difficult to show that ${K(z,\overline{w})}$ is a positive semi-definite kernel, which gives the required monotonicity. It would be interesting to obtain some more insightful interpretation of the kernel ${K}$ and the identity (2).

These monotonicity properties hint at the minor process ${A \mapsto [pAp]}$ being associated to some sort of “gradient flow” in the ${k}$ parameter. We were not able to formalize this intuition; indeed, it is not clear what a gradient flow on a varying noncommutative probability space ${({\mathcal A}_p, \tau_p)}$ even means. However, after substantial further calculation we were able to formally describe the minor process as the Euler-Lagrange equation for an intriguing Lagrangian functional that we conjecture to have a random matrix interpretation. We first work in “Lagrangian coordinates”, defining the quantity ${\lambda(s,y)}$ on the “Gelfand-Tsetlin pyramid”

$\displaystyle \Delta = \{ (s,y): 0 < s < 1; 0 < y < s \}$

by the formula

$\displaystyle \mu^{\boxplus 1/s}((-\infty,\lambda(s,y)/s])=y/s,$

which is well defined if the density of ${\mu}$ is sufficiently well behaved. The random matrix interpretation of ${\lambda(s,y)}$ is that it is the asymptotic location of the ${\lfloor yN\rfloor^{th}}$ eigenvalue of the ${\lfloor sN \rfloor \times \lfloor sN \rfloor}$ upper left minor of a random ${N \times N}$ matrix ${A_N}$ with asymptotic empirical spectral distribution ${\mu}$ and with unitarily invariant distribution, thus ${\lambda}$ is in some sense a continuum limit of Gelfand-Tsetlin patterns. Thus for instance the Cauchy interlacing laws in this asymptotic limit regime become

$\displaystyle 0 \leq \partial_s \lambda \leq \partial_y \lambda.$

After a lengthy calculation (involving extensive use of the chain rule and product rule), the equation (1) is equivalent to the Euler-Lagrange equation

$\displaystyle \partial_s L_{\lambda_s}(\partial_s \lambda, \partial_y \lambda) + \partial_y L_{\lambda_y}(\partial_s \lambda, \partial_y \lambda) = 0$

where ${L}$ is the Lagrangian density

$\displaystyle L(\lambda_s, \lambda_y) := \log \lambda_y + \log \sin( \pi \frac{\lambda_s}{\lambda_y} ).$

Thus the minor process is formally a critical point of the integral ${\int_\Delta L(\partial_s \lambda, \partial_y \lambda)\ ds dy}$. The quantity ${\partial_y \lambda}$ measures the mean eigenvalue spacing at some location of the Gelfand-Tsetlin pyramid, and the ratio ${\frac{\partial_s \lambda}{\partial_y \lambda}}$ measures mean eigenvalue drift in the minor process. This suggests that this Lagrangian density is some sort of measure of entropy of the asymptotic microscale point process emerging from the minor process at this spacing and drift. There is work of Metcalfe demonstrating that this point process is given by the Boutillier bead model, so we conjecture that this Lagrangian density ${L}$ somehow measures the entropy density of this process.

Asgar Jamneshan and I have just uploaded to the arXiv our paper “An uncountable Moore-Schmidt theorem“. This paper revisits a classical theorem of Moore and Schmidt in measurable cohomology of measure-preserving systems. To state the theorem, let ${X = (X,{\mathcal X},\mu)}$ be a probability space, and ${\mathrm{Aut}(X, {\mathcal X}, \mu)}$ be the group of measure-preserving automorphisms of this space, that is to say the invertible bimeasurable maps ${T: X \rightarrow X}$ that preserve the measure ${\mu}$: ${T_* \mu = \mu}$. To avoid some ambiguity later in this post when we introduce abstract analogues of measure theory, we will refer to measurable maps as concrete measurable maps, and measurable spaces as concrete measurable spaces. (One could also call ${X = (X,{\mathcal X}, \mu)}$ a concrete probability space, but we will not need to do so here as we will not be working explicitly with abstract probability spaces.)

Let ${\Gamma = (\Gamma,\cdot)}$ be a discrete group. A (concrete) measure-preserving action of ${\Gamma}$ on ${X}$ is a group homomorphism ${\gamma \mapsto T^\gamma}$ from ${\Gamma}$ to ${\mathrm{Aut}(X, {\mathcal X}, \mu)}$, thus ${T^1}$ is the identity map and ${T^{\gamma_1} \circ T^{\gamma_2} = T^{\gamma_1 \gamma_2}}$ for all ${\gamma_1,\gamma_2 \in \Gamma}$. A large portion of ergodic theory is concerned with the study of such measure-preserving actions, especially in the classical case when ${\Gamma}$ is the integers (with the additive group law).

Let ${K = (K,+)}$ be a compact Hausdorff abelian group, which we can endow with the Borel ${\sigma}$-algebra ${{\mathcal B}(K)}$. A (concrete measurable) ${K}$cocycle is a collection ${\rho = (\rho_\gamma)_{\gamma \in \Gamma}}$ of concrete measurable maps ${\rho_\gamma: X \rightarrow K}$ obeying the cocycle equation

$\displaystyle \rho_{\gamma_1 \gamma_2}(x) = \rho_{\gamma_1} \circ T^{\gamma_2}(x) + \rho_{\gamma_2}(x) \ \ \ \ \ (1)$

for ${\mu}$-almost every ${x \in X}$. (Here we are glossing over a measure-theoretic subtlety that we will return to later in this post – see if you can spot it before then!) Cocycles arise naturally in the theory of group extensions of dynamical systems; in particular (and ignoring the aforementioned subtlety), each cocycle induces a measure-preserving action ${\gamma \mapsto S^\gamma}$ on ${X \times K}$ (which we endow with the product of ${\mu}$ with Haar probability measure on ${K}$), defined by

$\displaystyle S^\gamma( x, k ) := (T^\gamma x, k + \rho_\gamma(x) ).$

This connection with group extensions was the original motivation for our study of measurable cohomology, but is not the focus of the current paper.

A special case of a ${K}$-valued cocycle is a (concrete measurable) ${K}$-valued coboundary, in which ${\rho_\gamma}$ for each ${\gamma \in \Gamma}$ takes the special form

$\displaystyle \rho_\gamma(x) = F \circ T^\gamma(x) - F(x)$

for ${\mu}$-almost every ${x \in X}$, where ${F: X \rightarrow K}$ is some measurable function; note that (ignoring the aforementioned subtlety), every function of this form is automatically a concrete measurable ${K}$-valued cocycle. One of the first basic questions in measurable cohomology is to try to characterize which ${K}$-valued cocycles are in fact ${K}$-valued coboundaries. This is a difficult question in general. However, there is a general result of Moore and Schmidt that at least allows one to reduce to the model case when ${K}$ is the unit circle ${\mathbf{T} = {\bf R}/{\bf Z}}$, by taking advantage of the Pontryagin dual group ${\hat K}$ of characters ${\hat k: K \rightarrow \mathbf{T}}$, that is to say the collection of continuous homomorphisms ${\hat k: k \mapsto \langle \hat k, k \rangle}$ to the unit circle. More precisely, we have

Theorem 1 (Countable Moore-Schmidt theorem) Let ${\Gamma}$ be a discrete group acting in a concrete measure-preserving fashion on a probability space ${X}$. Let ${K}$ be a compact Hausdorff abelian group. Assume the following additional hypotheses:

• (i) ${\Gamma}$ is at most countable.
• (ii) ${X}$ is a standard Borel space.
• (iii) ${K}$ is metrisable.

Then a ${K}$-valued concrete measurable cocycle ${\rho = (\rho_\gamma)_{\gamma \in \Gamma}}$ is a concrete coboundary if and only if for each character ${\hat k \in \hat K}$, the ${\mathbf{T}}$-valued cocycles ${\langle \hat k, \rho \rangle = ( \langle \hat k, \rho_\gamma \rangle )_{\gamma \in \Gamma}}$ are concrete coboundaries.

The hypotheses (i), (ii), (iii) are saying in some sense that the data ${\Gamma, X, K}$ are not too “large”; in all three cases they are saying in some sense that the data are only “countably complicated”. For instance, (iii) is equivalent to ${K}$ being second countable, and (ii) is equivalent to ${X}$ being modeled by a complete separable metric space. It is because of this restriction that we refer to this result as a “countable” Moore-Schmidt theorem. This theorem is a useful tool in several other applications, such as the Host-Kra structure theorem for ergodic systems; I hope to return to these subsequent applications in a future post.

Let us very briefly sketch the main ideas of the proof of Theorem 1. Ignore for now issues of measurability, and pretend that something that holds almost everywhere in fact holds everywhere. The hard direction is to show that if each ${\langle \hat k, \rho \rangle}$ is a coboundary, then so is ${\rho}$. By hypothesis, we then have an equation of the form

$\displaystyle \langle \hat k, \rho_\gamma(x) \rangle = \alpha_{\hat k} \circ T^\gamma(x) - \alpha_{\hat k}(x) \ \ \ \ \ (2)$

for all ${\hat k, \gamma, x}$ and some functions ${\alpha_{\hat k}: X \rightarrow {\mathbf T}}$, and our task is then to produce a function ${F: X \rightarrow K}$ for which

$\displaystyle \rho_\gamma(x) = F \circ T^\gamma(x) - F(x)$

for all ${\gamma,x}$.

Comparing the two equations, the task would be easy if we could find an ${F: X \rightarrow K}$ for which

$\displaystyle \langle \hat k, F(x) \rangle = \alpha_{\hat k}(x) \ \ \ \ \ (3)$

for all ${\hat k, x}$. However there is an obstruction to this: the left-hand side of (3) is additive in ${\hat k}$, so the right-hand side would have to be also in order to obtain such a representation. In other words, for this strategy to work, one would have to first establish the identity

$\displaystyle \alpha_{\hat k_1 + \hat k_2}(x) - \alpha_{\hat k_1}(x) - \alpha_{\hat k_2}(x) = 0 \ \ \ \ \ (4)$

for all ${\hat k_1, \hat k_2, x}$. On the other hand, the good news is that if we somehow manage to obtain the equation, then we can obtain a function ${F}$ obeying (3), thanks to Pontryagin duality, which gives a one-to-one correspondence between ${K}$ and the homomorphisms of the (discrete) group ${\hat K}$ to ${\mathbf{T}}$.

Now, it turns out that one cannot derive the equation (4) directly from the given information (2). However, the left-hand side of (2) is additive in ${\hat k}$, so the right-hand side must be also. Manipulating this fact, we eventually arrive at

$\displaystyle (\alpha_{\hat k_1 + \hat k_2} - \alpha_{\hat k_1} - \alpha_{\hat k_2}) \circ T^\gamma(x) = (\alpha_{\hat k_1 + \hat k_2} - \alpha_{\hat k_1} - \alpha_{\hat k_2})(x).$

In other words, we don’t get to show that the left-hand side of (4) vanishes, but we do at least get to show that it is ${\Gamma}$-invariant. Now let us assume for sake of argument that the action of ${\Gamma}$ is ergodic, which (ignoring issues about sets of measure zero) basically asserts that the only ${\Gamma}$-invariant functions are constant. So now we get a weaker version of (4), namely

$\displaystyle \alpha_{\hat k_1 + \hat k_2}(x) - \alpha_{\hat k_1}(x) - \alpha_{\hat k_2}(x) = c_{\hat k_1, \hat k_2} \ \ \ \ \ (5)$

for some constants ${c_{\hat k_1, \hat k_2} \in \mathbf{T}}$.

Now we need to eliminate the constants. This can be done by the following group-theoretic projection. Let ${L^0({\bf X} \rightarrow {\bf T})}$ denote the space of concrete measurable maps ${\alpha}$ from ${{\bf X}}$ to ${{\bf T}}$, up to almost everywhere equivalence; this is an abelian group where the various terms in (5) naturally live. Inside this group we have the subgroup ${{\bf T}}$ of constant functions (up to almost everywhere equivalence); this is where the right-hand side of (5) lives. Because ${{\bf T}}$ is a divisible group, there is an application of Zorn’s lemma (a good exercise for those who are not acquainted with these things) to show that there exists a retraction ${w: L^0({\bf X} \rightarrow {\bf T}) \rightarrow {\bf T}}$, that is to say a group homomorphism that is the identity on the subgroup ${{\bf T}}$. We can use this retraction, or more precisely the complement ${\alpha \mapsto \alpha - w(\alpha)}$, to eliminate the constant in (5). Indeed, if we set

$\displaystyle \tilde \alpha_{\hat k}(x) := \alpha_{\hat k}(x) - w(\alpha_{\hat k})$

then from (5) we see that

$\displaystyle \tilde \alpha_{\hat k_1 + \hat k_2}(x) - \tilde \alpha_{\hat k_1}(x) - \tilde \alpha_{\hat k_2}(x) = 0$

while from (2) one has

$\displaystyle \langle \hat k, \rho_\gamma(x) \rangle = \tilde \alpha_{\hat k} \circ T^\gamma(x) - \tilde \alpha_{\hat k}(x)$

and now the previous strategy works with ${\alpha_{\hat k}}$ replaced by ${\tilde \alpha_{\hat k}}$. This concludes the sketch of proof of Theorem 1.

In making the above argument rigorous, the hypotheses (i)-(iii) are used in several places. For instance, to reduce to the ergodic case one relies on the ergodic decomposition, which requires the hypothesis (ii). Also, most of the above equations only hold outside of a set of measure zero, and the hypothesis (i) and the hypothesis (iii) (which is equivalent to ${\hat K}$ being at most countable) to avoid the problem that an uncountable union of sets of measure zero could have positive measure (or fail to be measurable at all).

My co-author Asgar Jamneshan and I are working on a long-term project to extend many results in ergodic theory (such as the aforementioned Host-Kra structure theorem) to “uncountable” settings in which hypotheses analogous to (i)-(iii) are omitted; thus we wish to consider actions on uncountable groups, on spaces that are not standard Borel, and cocycles taking values in groups that are not metrisable. Such uncountable contexts naturally arise when trying to apply ergodic theory techniques to combinatorial problems (such as the inverse conjecture for the Gowers norms), as one often relies on the ultraproduct construction (or something similar) to generate an ergodic theory translation of these problems, and these constructions usually give “uncountable” objects rather than “countable” ones. (For instance, the ultraproduct of finite groups is a hyperfinite group, which is usually uncountable.). This paper marks the first step in this project by extending the Moore-Schmidt theorem to the uncountable setting.

If one simply drops the hypotheses (i)-(iii) and tries to prove the Moore-Schmidt theorem, several serious difficulties arise. We have already mentioned the loss of the ergodic decomposition and the possibility that one has to control an uncountable union of null sets. But there is in fact a more basic problem when one deletes (iii): the addition operation ${+: K \times K \rightarrow K}$, while still continuous, can fail to be measurable as a map from ${(K \times K, {\mathcal B}(K) \otimes {\mathcal B}(K))}$ to ${(K, {\mathcal B}(K))}$! Thus for instance the sum of two measurable functions ${F: X \rightarrow K}$ need not remain measurable, which makes even the very definition of a measurable cocycle or measurable coboundary problematic (or at least unnatural). This phenomenon is known as the Nedoma pathology. A standard example arises when ${K}$ is the uncountable torus ${{\mathbf T}^{{\bf R}}}$, endowed with the product topology. Crucially, the Borel ${\sigma}$-algebra ${{\mathcal B}(K)}$ generated by this uncountable product is not the product ${{\mathcal B}(\mathbf{T})^{\otimes {\bf R}}}$ of the factor Borel ${\sigma}$-algebras (the discrepancy ultimately arises from the fact that topologies permit uncountable unions, but ${\sigma}$-algebras do not); relating to this, the product ${\sigma}$-algebra ${{\mathcal B}(K) \otimes {\mathcal B}(K)}$ is not the same as the Borel ${\sigma}$-algebra ${{\mathcal B}(K \times K)}$, but is instead a strict sub-algebra. If the group operations on ${K}$ were measurable, then the diagonal set

$\displaystyle K^\Delta := \{ (k,k') \in K \times K: k = k' \} = \{ (k,k') \in K \times K: k - k' = 0 \}$

would be measurable in ${{\mathcal B}(K) \otimes {\mathcal B}(K)}$. But it is an easy exercise in manipulation of ${\sigma}$-algebras to show that if ${(X, {\mathcal X}), (Y, {\mathcal Y})}$ are any two measurable spaces and ${E \subset X \times Y}$ is measurable in ${{\mathcal X} \otimes {\mathcal Y}}$, then the fibres ${E_x := \{ y \in Y: (x,y) \in E \}}$ of ${E}$ are contained in some countably generated subalgebra of ${{\mathcal Y}}$. Thus if ${K^\Delta}$ were ${{\mathcal B}(K) \otimes {\mathcal B}(K)}$-measurable, then all the points of ${K}$ would lie in a single countably generated ${\sigma}$-algebra. But the cardinality of such an algebra is at most ${2^{\alpha_0}}$ while the cardinality of ${K}$ is ${2^{2^{\alpha_0}}}$, and Cantor’s theorem then gives a contradiction.

To resolve this problem, we give ${K}$ a coarser ${\sigma}$-algebra than the Borel ${\sigma}$-algebra, namely the Baire ${\sigma}$-algebra ${{\mathcal B}^\otimes(K)}$, thus coarsening the measurable space structure on ${K = (K,{\mathcal B}(K))}$ to a new measurable space ${K_\otimes := (K, {\mathcal B}^\otimes(K))}$. In the case of compact Hausdorff abelian groups, ${{\mathcal B}^{\otimes}(K)}$ can be defined as the ${\sigma}$-algebra generated by the characters ${\hat k: K \rightarrow {\mathbf T}}$; for more general compact abelian groups, one can define ${{\mathcal B}^{\otimes}(K)}$ as the ${\sigma}$-algebra generated by all continuous maps into metric spaces. This ${\sigma}$-algebra is equal to ${{\mathcal B}(K)}$ when ${K}$ is metrisable but can be smaller for other ${K}$. With this measurable structure, ${K_\otimes}$ becomes a measurable group; it seems that once one leaves the metrisable world that ${K_\otimes}$ is a superior (or at least equally good) space to work with than ${K}$ for analysis, as it avoids the Nedoma pathology. (For instance, from Plancherel’s theorem, we see that if ${m_K}$ is the Haar probability measure on ${K}$, then ${L^2(K,m_K) = L^2(K_\otimes,m_K)}$ (thus, every ${K}$-measurable set is equivalent modulo ${m_K}$-null sets to a ${K_\otimes}$-measurable set), so there is no damage to Plancherel caused by passing to the Baire ${\sigma}$-algebra.

Passing to the Baire ${\sigma}$-algebra ${K_\otimes}$ fixes the most severe problems with an uncountable Moore-Schmidt theorem, but one is still faced with an issue of having to potentially take an uncountable union of null sets. To avoid this sort of problem, we pass to the framework of abstract measure theory, in which we remove explicit mention of “points” and can easily delete all null sets at a very early stage of the formalism. In this setup, the category of concrete measurable spaces is replaced with the larger category of abstract measurable spaces, which we formally define as the opposite category of the category of ${\sigma}$-algebras (with Boolean algebra homomorphisms). Thus, we define an abstract measurable space to be an object of the form ${{\mathcal X}^{\mathrm{op}}}$, where ${{\mathcal X}}$ is an (abstract) ${\sigma}$-algebra and ${\mathrm{op}}$ is a formal placeholder symbol that signifies use of the opposite category, and an abstract measurable map ${T: {\mathcal X}^{\mathrm{op}} \rightarrow {\mathcal Y}^{\mathrm{op}}}$ is an object of the form ${(T^*)^{\mathrm{op}}}$, where ${T^*: {\mathcal Y} \rightarrow {\mathcal X}}$ is a Boolean algebra homomorphism and ${\mathrm{op}}$ is again used as a formal placeholder; we call ${T^*}$ the pullback map associated to ${T}$.  [UPDATE: It turns out that this definition of a measurable map led to technical issues.  In a forthcoming revision of the paper we also impose the requirement that the abstract measurable map be $\sigma$-complete (i.e., it respects countable joins).] The composition ${S \circ T: {\mathcal X}^{\mathrm{op}} \rightarrow {\mathcal Z}^{\mathrm{op}}}$ of two abstract measurable maps ${T: {\mathcal X}^{\mathrm{op}} \rightarrow {\mathcal Y}^{\mathrm{op}}}$, ${S: {\mathcal Y}^{\mathrm{op}} \rightarrow {\mathcal Z}^{\mathrm{op}}}$ is defined by the formula ${S \circ T := (T^* \circ S^*)^{\mathrm{op}}}$, or equivalently ${(S \circ T)^* = T^* \circ S^*}$.

Every concrete measurable space ${X = (X,{\mathcal X})}$ can be identified with an abstract counterpart ${{\mathcal X}^{op}}$, and similarly every concrete measurable map ${T: X \rightarrow Y}$ can be identified with an abstract counterpart ${(T^*)^{op}}$, where ${T^*: {\mathcal Y} \rightarrow {\mathcal X}}$ is the pullback map ${T^* E := T^{-1}(E)}$. Thus the category of concrete measurable spaces can be viewed as a subcategory of the category of abstract measurable spaces. The advantage of working in the abstract setting is that it gives us access to more spaces that could not be directly defined in the concrete setting. Most importantly for us, we have a new abstract space, the opposite measure algebra ${X_\mu}$ of ${X}$, defined as ${({\bf X}/{\bf N})^*}$ where ${{\bf N}}$ is the ideal of null sets in ${{\bf X}}$. Informally, ${X_\mu}$ is the space ${X}$ with all the null sets removed; there is a canonical abstract embedding map ${\iota: X_\mu \rightarrow X}$, which allows one to convert any concrete measurable map ${f: X \rightarrow Y}$ into an abstract one ${[f]: X_\mu \rightarrow Y}$. One can then define the notion of an abstract action, abstract cocycle, and abstract coboundary by replacing every occurrence of the category of concrete measurable spaces with their abstract counterparts, and replacing ${X}$ with the opposite measure algebra ${X_\mu}$; see the paper for details. Our main theorem is then

Theorem 2 (Uncountable Moore-Schmidt theorem) Let ${\Gamma}$ be a discrete group acting abstractly on a ${\sigma}$-finite measure space ${X}$. Let ${K}$ be a compact Hausdorff abelian group. Then a ${K_\otimes}$-valued abstract measurable cocycle ${\rho = (\rho_\gamma)_{\gamma \in \Gamma}}$ is an abstract coboundary if and only if for each character ${\hat k \in \hat K}$, the ${\mathbf{T}}$-valued cocycles ${\langle \hat k, \rho \rangle = ( \langle \hat k, \rho_\gamma \rangle )_{\gamma \in \Gamma}}$ are abstract coboundaries.

With the abstract formalism, the proof of the uncountable Moore-Schmidt theorem is almost identical to the countable one (in fact we were able to make some simplifications, such as avoiding the use of the ergodic decomposition). A key tool is what we call a “conditional Pontryagin duality” theorem, which asserts that if one has an abstract measurable map ${\alpha_{\hat k}: X_\mu \rightarrow {\bf T}}$ for each ${\hat k \in K}$ obeying the identity ${ \alpha_{\hat k_1 + \hat k_2} - \alpha_{\hat k_1} - \alpha_{\hat k_2} = 0}$ for all ${\hat k_1,\hat k_2 \in \hat K}$, then there is an abstract measurable map ${F: X_\mu \rightarrow K_\otimes}$ such that ${\alpha_{\hat k} = \langle \hat k, F \rangle}$ for all ${\hat k \in \hat K}$. This is derived from the usual Pontryagin duality and some other tools, most notably the completeness of the ${\sigma}$-algebra of ${X_\mu}$, and the Sikorski extension theorem.

We feel that it is natural to stay within the abstract measure theory formalism whenever dealing with uncountable situations. However, it is still an interesting question as to when one can guarantee that the abstract objects constructed in this formalism are representable by concrete analogues. The basic questions in this regard are:

• (i) Suppose one has an abstract measurable map ${f: X_\mu \rightarrow Y}$ into a concrete measurable space. Does there exist a representation of ${f}$ by a concrete measurable map ${\tilde f: X \rightarrow Y}$? Is it unique up to almost everywhere equivalence?
• (ii) Suppose one has a concrete cocycle that is an abstract coboundary. When can it be represented by a concrete coboundary?

For (i) the answer is somewhat interesting (as I learned after posing this MathOverflow question):

• If ${Y}$ does not separate points, or is not compact metrisable or Polish, there can be counterexamples to uniqueness. If ${Y}$ is not compact or Polish, there can be counterexamples to existence.
• If ${Y}$ is a compact metric space or a Polish space, then one always has existence and uniqueness.
• If ${Y}$ is a compact Hausdorff abelian group, one always has existence.
• If ${X}$ is a complete measure space, then one always has existence (from a theorem of Maharam).
• If ${X}$ is the unit interval with the Borel ${\sigma}$-algebra and Lebesgue measure, then one has existence for all compact Hausdorff ${Y}$ assuming the continuum hypothesis (from a theorem of von Neumann) but existence can fail under other extensions of ZFC (from a theorem of Shelah, using the method of forcing).
• For more general ${X}$, existence for all compact Hausdorff ${Y}$ is equivalent to the existence of a lifting from the ${\sigma}$-algebra ${\mathcal{X}/\mathcal{N}}$ to ${\mathcal{X}}$ (or, in the language of abstract measurable spaces, the existence of an abstract retraction from ${X}$ to ${X_\mu}$).
• It is a long-standing open question (posed for instance by Fremlin) whether it is relatively consistent with ZFC that existence holds whenever ${Y}$ is compact Hausdorff.

Our understanding of (ii) is much less complete:

• If ${K}$ is metrisable, the answer is “always” (which among other things establishes the countable Moore-Schmidt theorem as a corollary of the uncountable one).
• If ${\Gamma}$ is at most countable and ${X}$ is a complete measure space, then the answer is again “always”.

In view of the answers to (i), I would not be surprised if the full answer to (ii) was also sensitive to axioms of set theory. However, such set theoretic issues seem to be almost completely avoided if one sticks with the abstract formalism throughout; they only arise when trying to pass back and forth between the abstract and concrete categories.

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

Previous set of notes: Notes 3.
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.