Youness Lamzouri
email: lamzouri@mathstat.yorku.edu

ORDERINGS OF WEAKLY CORRELATED RANDOM VARIABLES, AND PRIME NUMBER RACES WITH MANY CONTESTANTS

We investigate the race between prime numbers in many residue classes modulo q, assuming the standard conjectures GRH and LI.

Among our results we exhibit, for the first time, n-way prime number races modulo q where the biases do not dissolve when n, q → ∞. We also study the leaders in the prime number race, obtaining asymptotic formulae for logarithmic densities when the number of competitors can be as large as a power of q, whereas previous methods could only allow a power of log q.

The proofs use harmonic analysis related to the Hardy-Littlewood circle method to control the average size of correlations in prime number races. They also use various probabilistic tools, including an exchangeable pairs version of Stein's method, normal comparison tools, and conditioning arguments. In the process we derive some general results about orderings of weakly correlated random variables, which may be of independent interest.

Introduction

In an 1853 letter to Fuss, Chebyshev noted that on a fine scale there seem to be more primes congruent to 3 than to 1 modulo 4. This observation led to the birth of comparative prime number theory, which investigates the discrepancies in the distribution of prime numbers. A central problem is the so-called "Shanks-Rényi prime number race" which is described by Knapowski and Turán [START_REF] Knapowski | Comparative prime-number theory[END_REF]: let q ≥ 3 and 2 ≤ n ≤ ϕ(q) be positive integers, (where the Euler function ϕ(q) denotes the number of residue classes mod q that are coprime to q), and denote by A n (q) the set of ordered n-tuples (a 1 , a 2 , . . . , a n ) of distinct residue classes that are coprime to q. For (a 1 , a 2 , . . . , a n ) ∈ A n (q) consider a game with n players called "a 1 " through to "a n ", where at time x, the player a j has a score of π(x; q, a j ) (where π(x; q, a) denotes the number of primes p ≤ x with p ≡ a mod q). Among the questions that Knapowski and Turán asked in [START_REF] Knapowski | Comparative prime-number theory[END_REF] are the following: Q1. Will each player take the lead for infinitely many integers x? Q2. Will all n! orderings of the players occur for infinitely many integers x?

It is generally believed that the answer to the stronger question Q2 (and thus to Q1) is yes for all q and all (a 1 , a 2 , . . . , a n ) ∈ A n (q). An old result of Littlewood [START_REF] Littlewood | Distribution des nombres premiers[END_REF] shows that this is indeed true when (q, a 1 , a 2 ) = (4, 1, 3) and (q, a 1 , a 2 ) = (3, 1, 2). Since then, this problem has been extensively studied by various authors, including Knapowski and Turán AJH is supported by a research fellowship at Jesus College, Cambridge; and, when this work was started, by a postdoctoral fellowship from the Centre de Recherches Mathématiques, Montréal. YL is partially supported by a Discovery Grant from the Natural Sciences and Engineering Research Council of Canada. [START_REF] Knapowski | Comparative prime-number theory[END_REF], Kaczorowski [START_REF] Kaczorowski | A contribution to the Shanks-Rényi race problem[END_REF][START_REF] Kaczorowski | Results on the distribution of primes[END_REF][START_REF] Kaczorowski | On the Shanks-Rényi race problem[END_REF], Feuerverger and Martin [START_REF] Feuerverger | Biases in the Shanks-Rényi prime number race[END_REF], Ford and Konyagin [START_REF] Ford | The prime number race and zeros of L-functions off the critical line[END_REF], Ford, Konyagin and Lamzouri [START_REF] Ford | The prime number race and zeros of Dirichlet L-functions off the critical line: Part III[END_REF], Fiorilli and Martin [START_REF] Fiorilli | Inequities in the Shanks-Rényi Prime Number Race: An asymptotic formula for the densities[END_REF], Fiorilli [START_REF] Fiorilli | Highly biased prime number races[END_REF], and Lamzouri [START_REF] Lamzouri | The Shanks-Rényi prime number race with many contestants[END_REF][START_REF] Lamzouri | Prime number races with three or more competitors[END_REF]. For a complete history as well as recent developments, see the expository papers of Granville and Martin [START_REF] Granville | Prime number races[END_REF], Ford and Konyagin [START_REF] Ford | Chebyshev's conjecture and the prime number race[END_REF], and Martin and Scarfy [START_REF] Martin | Comparative prime number theory: A survey[END_REF] (which includes a very comprehensive list of references).

Assuming the Generalized Riemann hypothesis GRH and the Linear Independence hypothesis LI (which is the assumption that the nonnegative imaginary parts of the nontrivial zeros of Dirichlet L-functions attached to primitive characters are linearly independent over Q), Rubinstein and Sarnak [START_REF] Rubinstein | Chebyshev's bias[END_REF] affirmatively answered questions Q1 and Q2. In fact, under these hypotheses, they established the stronger result that for any (a 1 , . . . , a n ) ∈ A n (q), the set of real numbers x ≥ 2 such that (1.1) π(x; q, a 1 ) > π(x; q, a 2 ) > • • • > π(x; q, a n ), has a positive logarithmic density, which we denote by δ(q; a 1 , . . . , a n ). (Recall that the logarithmic density of a subset S of R is defined as lim x→∞ 1 log x t∈S∩ [2,x] dt t ,

provided that this limit exists.) This density can be regarded as the "probability" that for each 1 ≤ j ≤ n, the player a j is at the j-th position in the prime race.

Among their results on question Q2, Rubinstein and Sarnak [START_REF] Rubinstein | Chebyshev's bias[END_REF] showed that for n fixed, (1.2) lim q→∞ max (a 1 ,...,an)∈An(q) δ(q; a 1 , . . . , a n ) -

1 n! = 0.
Feuerverger and Martin [START_REF] Feuerverger | Biases in the Shanks-Rényi prime number race[END_REF] raised the question of having a uniform version of this statement, in which the number of contestants n → ∞ as q → ∞. In response to this, Lamzouri [START_REF] Lamzouri | The Shanks-Rényi prime number race with many contestants[END_REF] established that for any integer n such that 2 ≤ n ≤ √ log q we have δ(q; a 1 , . . . ,

a n ) = 1 n! 1 + O n 2 log q ,
uniformly for all n-tuples (a 1 , . . . , a n ) ∈ A n (q). Feuerverger and Martin [START_REF] Feuerverger | Biases in the Shanks-Rényi prime number race[END_REF] also asked whether for n sufficiently large in terms of q the asymptotic formula δ(q; a 1 , . . . , a n ) ∼ 1/n! might become false. A few years ago, Ford and Lamzouri (unpublished) developed a heuristic argument which suggests that there should be a transition in the behaviour of the densities when n = (log q) 1+o (1) . More specifically, they formulated the following conjecture.

Conjecture 1.1 (Ford and Lamzouri). Let ε > 0 be small and q be sufficiently large.

(1) If 2 ≤ n ≤ (log q) 1-ε , then uniformly for all n-tuples (a 1 , . . . , a n ) ∈ A n (q) we have δ(q; a 1 , . . . , a n ) ∼ 1/n! as q → ∞. (2) If (log q) 1+ε ≤ n ≤ ϕ(q), then there exist n-tuples (a 1 , . . . , a n ), (b 1 , . . . , b n ) ∈ A n (q) for which n! • δ(q; a 1 , . . . , a n ) → 0 and n! • δ(q; b 1 , . . . , b n ) → ∞ as q → ∞.

Our first result establishes part (1) of this conjecture.

Theorem 1.2. Assume GRH and LI. Let 2 ≤ n ≤ log q/(log log q) 4 be a positive integer. Then, uniformly for all n-tuples (a 1 , . . . , a n ) ∈ A n (q) we have δ(q; a 1 , . . . , a n ) = 1 n! 1 + O n(log n) 4 log q .

To be clear, when we say that this estimate holds "uniformly for all n-tuples", we mean that it holds for all n, q and (a 1 , . . . , a n ) permitted in the statement, with an absolute implicit constant in the "big Oh" term. To be even more explicit, we mean that max (a 1 ,...,an)∈An(q) |n!δ(q; a 1 , . . . , a n ) -1| ≤ C n(log n) 4 log q , for all permitted n, q and for some absolute positive constant C. The same explanation applies to the statements of our subsequent theorems.

The second part of Conjecture 1.1 implies, in particular, that the asymptotic formula δ(q; a 1 , . . . , a n ) ∼ 1/n! need not hold for all n-tuples (a 1 , . . . , a n ) ∈ A n (q), if n lies in the range (log q) 1+ε ≤ n ≤ ϕ(q). We believe this to be true because we encounter various error terms in our arguments, from different sources, of size about 1/q. Thus we believe that when the target density 1/n! becomes much smaller than any negative power of q, which happens when n ≥ (log q) 1+ε , it is no longer reasonable to expect all of the δ(q; a 1 , . . . , a n ) to be close to 1/n!. Our next result shows that this is indeed the case in the smaller range ϕ(q) ε < n ≤ ϕ(q). Thus we are able to exhibit, for the first time, n-way prime number races for which the biases do not dissolve when q → ∞, confirming the prediction of Feuerverger and Martin [START_REF] Feuerverger | Biases in the Shanks-Rényi prime number race[END_REF].

Theorem 1.3. Assume GRH and LI. Let ε > 0 and let q be sufficiently large in terms of ε. For every integer ϕ(q) ε ≤ n ≤ ϕ(q) there exists an n-tuple (a 1 , . . . , a n ) ∈ A n (q) such that δ(q; a 1 , . . . , a n ) < 1 -c ε 1 n! , for some positive constant c ε which depends only on ε.

We next consider a stronger form of question Q1, concerning the leader in a prime number race with many contestants. By the work of Rubinstein and Sarnak, it follows that for any (a 1 , . . . , a n ) ∈ A n (q), the set of real numbers x ≥ 2 such that π(x; q, a 1 ) > max 2≤j≤n π(x; q, a j ), has a positive logarithmic density which we denote by δ 1 (q; a 1 , . . . , a n ). Kaczorowski [START_REF] Kaczorowski | A contribution to the Shanks-Rényi race problem[END_REF] has considered this leadership question (in the special case a 1 = 1), and obtained some positive lower density results assuming only GRH rather than LI. One can ask the following natural quantitative question: Q3. Will each of the players a 1 , . . . , a n have an "equal chance" 1/n of leading the race, when q → ∞?

It follows from Theorem 1.2 that the answer to this question is yes, if the number of contestants n lies in the range 2 ≤ n = o(log q/(log log q) 4 ). Using a different approach we extend this significantly, showing that n can be as large as a small power of q.

Theorem 1.4. Assume GRH and LI. Let 2 ≤ n ≤ ϕ(q) 1/32 be an integer. Then, uniformly for all n-tuples (a 1 , . . . , a n ) ∈ A n (q) we have 12/25 .

δ 1 (q; a 1 , . . . , a n ) = 1 n 1 + O n 4 ϕ(q) 1/8 + 1 (n log q)
The key ingredient in the proof of this theorem is the following probabilistic result, which may be of independent interest. It investigates the probability that a given random variable is the leader among weakly correlated Gaussian random variables.

Theorem 1.5. Suppose ε > 0 is sufficiently small, and n is sufficiently large. Let X 1 , ..., X n be mean zero, variance one, jointly normal random variables, and write r i,j := EX i X j , and suppose that |r i,j | ≤ ε whenever i = j. Then

|P(X 1 > max 2≤i≤n X i ) -1/n| n -100 + n -1.99 2≤i≤n |r 1,i | + n -2.99 2≤i<j≤n |r i,j |.
Note that the probability would be exactly 1/n if the X i were independent of one another, by symmetry.

We also consider a variant of question Q3 concerning the ordering of the first k contestants in a prime race with many competitors. To this end, for each integer 1 ≤ k ≤ n, we define δ k (q; a 1 , . . . , a n ) to be the logarithmic density of the set of real numbers x ≥ 2 such that π(x; q, a 1 ) > π(x; q, a 2 ) > • • • > π(x; q, a k ) > max k+1≤j≤n π(x; q, a j ).

Note that the cases k = n -1 and k = n both correspond to the full ordering (1.1), and hence δ n-1 (q; a 1 , . . . , a n ) = δ n (q; a 1 , . . . , a n ) = δ(q; a 1 , . . . , a n ).

It follows from Theorem 1.2 that in the range 1 ≤ k ≤ n -1 ≤ log q/(log log q) 4 , we have

δ k (q; a 1 , . . . , a n ) = (n -k)! n! 1 + O n(log n) 4 log q . Now (n-k)! n! = n -k(1+o(1))
as n → ∞, so the heuristic discussed following Theorem 1.2 leads us to expect that δ k (q; a 1 , . . . , a n ) ∼ (n-k)! n! even for very large n, provided roughly that k (log q)/ log n. We will show that the asymptotic does holds on almost this entire range of k, for all n such that (log n)/ log q → 0 as q → ∞. Moreover, unlike the case k = 1 (where Theorem 1.4 permits n to be a small fixed power of q), we show that the condition (log n)/ log q → 0 is necessary to guarantee an asymptotic for any k ≥ 2.

Theorem 1.6. Assume GRH and LI. Let 2 ≤ k ≤ n-2 be integers, and suppose (log q)/ log n is large enough and k(log k) 10 ≤ (log q)/ log n. Then, uniformly for all n-tuples (a 1 , . . . , a n ) ∈ A n (q) we have

δ k (q; a 1 , . . . , a n ) = (n -k)! n! 1 + O k(log k) 6 log n log q + 1 n log 1/10 q .
Theorem 1.7. Assume GRH and LI. Let ε > 0 and let q be sufficiently large in terms of ε. Let k ≥ 2 be fixed and let n be an integer in the range ϕ(q) ε ≤ n < ϕ(q) 1/41 . Then there exists an n-tuple (a 1 , . . . , a n ) ∈ A n (q) such that

δ k (q; a 1 , . . . , a n ) < 1 -c ε (n -k)! n! ,
for some positive constant c ε that depends only on ε.

Theorem 1.3 can be deduced from Theorem 1.7 as follows. Take k = 2, let ε > 0 be suitably small, and suppose first that ϕ(q) ε ≤ n < ϕ(q) 1/41 is an integer. Then it follows from Theorem 1.7 that there exists an n-tuple (a 1 , . . . , a n ) ∈ A n (q) such that

(1.3) δ 2 (q; a 1 , . . . , a n ) < 1 -c ε (n -2)!
n! for some positive constant c ε . Let S n-2 be the symmetric group on n -2 elements. Since the logarithmic density of the set of real numbers x ≥ 2 for which π(x; q, a) = π(x; q, b) is 0 (which follows from equation (2.3) below), we get

δ 2 (q; a 1 , . . . , a n ) = σ∈S n-2 δ(q; a 1 , a 2 , a σ(3) , . . . , a σ(n) ).
Thus by (1.3), there exists σ ∈ S n-2 for which

δ(q; a 1 , a 2 , a σ(3) , . . . , a σ(n) ) < 1 -c ε 1 n! ,
completing the proof of Theorem 1.3 provided n < ϕ(q) 1/41 . However, if n is larger then we can set m := ϕ(q) 1/41 -1, and note that by the previous discussion there exists an m-tuple (a 1 , . . . , a m ) ∈ A m (q) for which

δ(q; a 1 , . . . , a m ) < 1 -c 1 m! .
Then if we choose any other coprime residues a m+1 , ..., a n mod q, we have

δ(q; a 1 , . . . , a m ) = σ∈Sn: σ -1 (1)>σ -1 (2)>...>σ -1 (m) δ(q; a σ(1) , a σ(2) , . . . , a σ(n) ).
There are n!/m! terms in the sum, so it follows that for at least one permutation σ we must have δ(q; a σ(1) , a σ(2) , . . . , a σ(n) ) < (1 -c) 1 n! , as claimed.

Let us remark on the fact that all the results we have described and stated, from Rubinstein and Sarnak [START_REF] Rubinstein | Chebyshev's bias[END_REF] onwards, relate to limiting logarithmic densities such as δ(q; a 1 , . . . , a n ) and δ k (q; a 1 , . . . , a n ). It would be nice to have results where x varies at the same time as q, k and n, rather than being sent to infinity first. As can be seen in section 2, a key impediment to producing such results is that the formulation of the LI hypothesis is also rather qualitative and infinitary, stating that there are no linear relations amongst ordinates of zeros. To handle x in a quantitative manner, this hypothesis would need to be reworked as a more quantitative statement, that there are no approximate linear relations amongst ordinates of zeros up to a certain height (where the height and the notion of approximate relation would depend on x). It would certainly be interesting to try working out such an approach, but here we follow the simpler course of previous workers, and restrict attention to varying q, k and n when x has been sent to infinity.

Next we shall try to indicate the main ideas in the proofs of our theorems. The work of Rubinstein and Sarnak [START_REF] Rubinstein | Chebyshev's bias[END_REF] showing the existence of the logarithmic densities δ(q; a 1 , . . . , a n ) (assuming GRH and LI) in fact shows that (1.4) δ(q; a 1 , . . . , a n ) = P(X(q, a 1 ) > X(q, a 2 ) > ... > X(q, a n )),

where each X(q, a) is a sum of the same independent random variables twisted by certain arithmetic coefficients depending on q and a. Using a quantitative multivariate form of the central limit theorem (which we extract from Stein's method, replacing direct characteristic function calculations in the previous literature), one can replace the X(q, a) by jointly Gaussian random variables with the same means and covariances. Since the behaviour of Gaussians is entirely determined by those means and covariances, our task is then to obtain as much information as possible about them (on the number theory side), and deduce the best results we can on the ordering probabilities (on the probabilistic side). Theorem 1.2 uses a relatively naive probabilistic treatment, namely a direct estimation of the relevant multivariate Gaussian density. The improvement over the result of Lamzouri [START_REF] Lamzouri | The Shanks-Rényi prime number race with many contestants[END_REF] comes from substantially improved estimates for the average size of the covariances feeding into that density (they are typically small, so we are close to a standard multivariate Gaussian). These estimates rely on a harmonic analysis lemma related to the Hardy-Littlewood method, which we use to deduce that the differences a i -a j cannot too often be divisible by large divisors of q.

All of our other theorems exploit more sophisticated tools for comparing a multivariate Gaussian distribution with the standard multivariate Gaussian, such as the famous comparison lemmas of Slepian (see e.g. Piterbarg [START_REF] Piterbarg | Asymptotic Methods in the Theory of Gaussian Processes and Fields[END_REF]) and Li and Shao [START_REF] Li | A normal comparison inequality and its applications[END_REF]. However, none of these tools seem directly able to prove our theorems, because the probabilities of the events we are interested in are rather small and the bounds we have on the off-diagonal covariances are comparatively large. For example, in the case of Theorem 1.4 we need to show that δ 1 (q; a 1 , . . . , a n ) = P(X(q, a 1 ) > max

2≤j≤n X(q, a j )) = 1 n (1 + o(1)),
where potentially 1/n is as small as 1/ϕ(q) 1/32 = 1/q 1/32+o (1) , but where the largest offdiagonal covariances of the X(q, a) (when they are normalised to have variance 1) are 1/ log q. To address this problem, we observe that if Z 1 , Z 2 , ..., Z n are independent standard normal random variables, then with very high probability we have max 2≤j≤n (1) .

Z j = (2 -o(1)) log n, and P(Z 1 > (2 -o(1)) log n) = 1 n 1+o
In other words, most of the size 1/n of P(Z 1 > max 2≤j≤n Z j ) is determined just by the probability of Z 1 being large enough to possibly be the leader. This means that we can "factor out" most of the small size of our target probability 1/n by first conditioning on X(q, a 1 ) being roughly large enough to be in the lead, leaving a more achievable error bound to be obtained from comparison inequalities. Since the X(q, a i ) are not really independent of one another, this conditioning step itself requires some work and the use of Slepian's Lemma. Theorem 1.5 is a general probabilistic statement that we will prove using these methods.

Our result on the first k places in the race, Theorem 1.6, is proved by combining the direct density arguments of Theorem 1.2 with the conditioning arguments of Theorem 1.4. However, since the size of our target probability is now much smaller compared with n the latter part of the argument becomes more challenging, and in fact will be the hardest element of this paper. In particular, we need to prove a modified normal comparison lemma incorporating within it an application of Slepian's lemma, and when applying this we exploit the remarkable known fact that if the correlations of the random variables X(q, a) have positive sign, then they are very small.

Finally, the negative result Theorem 1.7 is proved by noting that in an event X(q, a 1 ) > X(q, a 2 ) > ... > X(q, a k ) > max k+1≤j≤n X(q, a j ), with very high probability the random variables X(q, a 1 ), ..., X(q, a k ) will have (normalised) size (2 -o(1)) log n, and so in the relevant probability integral there will be terms in the exponential of size log n. In particular, if there is a correlation between the random variables X(q, a i ) of size about 1/ log q, this will appear in the density in the exponential and will noticeably distort the multivariate normal probability if (log n)/ log q isn't small. So by choosing the tuple (a 1 , ..., a n ) so that there is a correlation of size 1/ log q, which is (the maximum) possible, we obtain an ordering probability that does not converge to uniformity.

We end by explaining the organisation of the rest of the paper. In section 2 we explicitly state the correspondence between logarithmic densities in prime races and orderings of suitable random variables. In section 3 we prove average estimates for the covariances of those random variables. Section 4 contains various probabilistic tools tailored to our needs, as well as the proof of Theorem 1.5 and the new probabilistic preparations for Theorem 1.6. Sections 5 and 6 are relatively short, and contain the deductions of Theorems 1.2 and 1.4. Finally, section 7 contains the somewhat difficult proof of Theorem 1.6, and section 8 has the proof of our negative result, Theorem 1.7.

We have tried to use notation that will not cause confusion between readers from a more number theoretic or a more probabilistic background, but two brief remarks might be in order. Firstly, we use Vinogradov's notation , which has the same meaning as the "big Oh" notation (thus x x/10, for example). In particular, does not mean "much less than". Secondly, if the implicit constant in a statement depends on some ambient parameter, we may adorn the notation with that parameter to reflect the dependence (e.g. we might write f (x) = O (x ), meaning that |f (x)| ≤ C( )x for some C( )).

Logarithmic densities of prime races and corresponding random variables

In order to investigate the distribution of prime numbers in arithmetic progressions, a standard tool in analytic number theory is to connect the prime counting functions π(x; q, a) to zeros of Dirichlet L-functions, via the so-called "explicit formulas". We shall briefly summarise some relevant aspects of this theory here, and the reader may consult Davenport's book [START_REF] Davenport | Multiplicative number theory. Revised and with a[END_REF] for many more details.

As usual, we denote by Λ the von Mangoldt function, defined by Λ(n) = log p if n = p k for some prime p and positive integer k, and Λ(n) = 0 otherwise. For a Dirichlet character χ (mod q) we define

ψ(x, χ) := n≤x χ(n)Λ(n).
Let χ 0 denote the principal character modulo q. For χ = χ 0 (mod q) we have the following classical explicit formula (see for example Eq. ( 7) of Chapter 19 of [START_REF] Davenport | Multiplicative number theory. Revised and with a[END_REF]):

(2.1) ψ(x, χ) = - |Im(ρχ)|≤T x ρχ ρ χ + O q x log 2 (xT ) T + log x ,
where ρ χ runs over the non-trivial zeros of the Dirichlet L-function L(s, χ). Now if a is a reduced residue modulo q, by the orthogonality of characters we deduce from (2.1) that

n≤x n≡a mod q Λ(n) = 1 ϕ(q) χ (mod q) χ(a)ψ(x, χ) = ψ(x, χ 0 ) ϕ(q) - 1 ϕ(q) χ =χ 0 χ (mod q) χ(a) |Im(ρχ)|≤T x ρχ ρ χ + O q x log 2 (xT ) T + log x .
If we assume the GRH, (which implies that ρ χ = 1/2 for all the terms in the sum over zeros), then a summation by parts argument leads to (see Eq (2.3) and (2.5) of [START_REF] Rubinstein | Chebyshev's bias[END_REF])

π(x; q, a) = π(x) ϕ(q) - C q (a) ϕ(q) √ x log x - √ x ϕ(q) log x χ =χ 0 χ (mod q) χ(a) |γχ|≤T x iγχ 1/2 + iγ χ +O q x log 2 (xT ) T log x + √ x log 2 x ,
where π(x) denotes the total number of primes less than x, and γ χ runs over the imaginary parts of the nontrivial zeros of L(s, χ), and C q (a) := -1 + |{b (mod q) : b 2 ≡ a (mod q)}|.

It is worth remarking here that the factor √ x in the second and third terms in the preceding display comes from different sources. In the second term (which is the origin of Chebyshev's bias for small q), √

x reflects the count of prime squares less than x, weighted by the von Mangoldt function. In the third term, √ x = x ρχ emerges from the sum over zeros as a consequence of GRH.

Thus, if we define E(x; q, a) := log x √ x (ϕ(q)π(x; q, a) -π(x)) , then we have

E(x; q, a) = -C q (a) - χ =χ 0 χ (mod q) χ(a) |γχ|≤T e iγχ log x 1/2 + iγ χ + O q √ x log 2 (xT ) T + 1 log x = -C q (a) -2Re χ =χ 0 χ (mod q) χ(a) 0<γχ≤T e iγχ log x 1/2 + iγ χ + O q √ x log 2 (xT ) T + 1 log x . (2.2)
Here the second equality follows because if ρ χ is a zero of L(s, χ), then its conjugate ρ χ is a zero of L(s, χ). The normalization of E(x; q, a) is such that, under our assumption of GRH, E(x; q, a) varies roughly boundedly as x varies.

If we assume LI then all of the positive values of γ χ are linearly independent over Q, and in particular are distinct. Let Γ = χ =χ 0 mod q {γ χ > 0}. Then assuming LI, it follows from Kronecker's Theorem that for any finite subset {γ 1 , . . . , γ N } ⊂ Γ, the set of values {(yγ 1 , . . . , yγ N ), y ∈ R} is uniformly distributed in U N , where U is the unit circle. Combining this fact with the explicit formula (2.2), Rubinstein and Sarnak [START_REF] Rubinstein | Chebyshev's bias[END_REF] proved (under GRH and LI) that if one looks at logarithmic densities, then E(x; q, a) has a limiting distribution as x → ∞. In fact they established a stronger result, which we shall now describe. Let a 1 , . . . , a n be distinct reduced residues modulo q, and define E q;a 1 ,...,an (x) := E(x; q, a 1 ), . . . , E(x; q, a n ) .

Then, notice that π(x; q, a 1 ) > π(x; q, a 2 ) > ... > π(x; q, a n ) ⇐⇒ E(x; q, a 1 ) > E(x; q, a 2 ) > ... > E(x; q, a n ).

Assuming GRH and LI, Rubinstein and Sarnak [START_REF] Rubinstein | Chebyshev's bias[END_REF] proved that for any Lebesgue measurable set S ⊂ R n whose boundary has measure zero, we have (2.3) δ q;a 1 ,...,an (S) := lim

X→∞ 1 log X x∈[2,X] Eq;a 1 ,...,an (x)∈S dx x = S dµ q;a 1 ,...,an
where µ q;a 1 ,...,an is a certain probability measure on R n .

Indeed, under the same assumptions they obtained the following formula for the Fourier transform of µ q;a 1 ,...,an :

(2.4) μq;a 1 ,...,an (ξ 1 , . . . ,

ξ n ) = exp i n j=1 C q (a j )ξ j χ =χ 0 χ (mod q) γχ>0 J 0   2| n j=1 χ(a j )ξ j | 1 4 + γ 2 χ   for (ξ 1 , . . . , ξ n ) ∈ R n , where J 0 (z) = ∞ m=0 (-1) m (z/2) 2m /(m!) 2
is the Bessel function of order 0. Since J 0 (z) is precisely the characteristic function of (the real part of) a random variable that is uniformly distributed on U, one can deduce from (2.4) that µ q;a 1 ,...,an is the probability measure corresponding to the random vector X(q, a 1 ), . . . , X(q, a n ) , where

X(q, a) := -C q (a) + χ =χ 0 χ (mod q) Re   2χ(a) γχ>0 U (γ χ ) 1 4 + γ 2 χ   ,
and {U (γ χ )} γχ∈Γ is a sequence of independent random variables uniformly distributed on U. Note that for (a, q) = 1 the function C q (a) takes only two values: C q (a) = -1 if a is a non-square modulo q, and C q (a) = C q (1) if a is a square modulo q. An elementary argument shows that C q (a) < d(q) q for any > 0, where d(q) = m|q 1 is the usual divisor function. Thus it will turn out that the shifts C q (a) can essentially be ignored when q → ∞.

Let Cov q;a 1 ,...,an be the covariance matrix of X(q, a 1 ), . . . , X(q, a n ) . Then a straightforward computation (see also Lemma 2.1 of [START_REF] Lamzouri | The Shanks-Rényi prime number race with many contestants[END_REF], for example) shows that Cov q;a 1 ,...,an (i, j) = Var(q) if i = j B q (a i , a j ) if i = j, where Var(q) := 2

χ =χ 0 χ (mod q) γχ>0 1 1 4 + γ 2 χ , and B q (a, b) := χ =χ 0 χ (mod q) γχ>0 χ b a + χ a b 1 4 + γ 2 χ .
We end this section by recording several basic estimates for the quantities Var(q) and B q (a, b) that will be useful in our subsequent work.

Lemma 2.1. Assume GRH. Then for any non-principal character χ (mod q), (2.5)

γχ>0 1 1 4 + γ 2 χ log q.
Moreover, we have

(2.6)
Var(q) ∼ ϕ(q) log q as q → ∞.

Proof. These estimates follow from Lemma 3.1 of [START_REF] Lamzouri | Prime number races with three or more competitors[END_REF], for example.

Lemma 2.2. Assume GRH. For all distinct reduced residues a, b mod q, we have

(2.7) B q (a.b) ϕ(q).
Moreover, if a, b are distinct residue classes such that 1 ≤ |a| < |b| ≤ q/2 and |b|/|a| is not a prime power, then we have

(2.8) B q (a, b) |b|(log q) 2 .
On the other hand we have

(2.9) B q (1, -1) = -(log 2)ϕ(q) + O (log q) 2 .
Finally, if a, b are distinct residue classes and B q (a, b) ≥ 0 then

(2.10) B q (a, b) log q.
Proof. The first bound (2.7) corresponds to Corollary 5.4 of [START_REF] Lamzouri | Prime number races with three or more competitors[END_REF]. The estimates (2.8) and (2.9) follow from Proposition 6.1 of [START_REF] Lamzouri | Prime number races with three or more competitors[END_REF]. The fact (2.10) that positive correlations are always very small is noted in Remark 5.1 of [START_REF] Lamzouri | Prime number races with three or more competitors[END_REF], for example.

3. An average result for the sums of the covariances B q (a i , a j ) 3.1. A double average. In view of Lemma 2.2, all of the non-diagonal covariances in our prime number race satisfy (when normalised by the variance Var(q))

|B q (a i , a j )| Var(q) 1 log q , i = j.
This bound is useful, but to obtain strong results we will need to exploit the fact that, if we are looking at many residue classes a 1 , ..., a n , the covariances will on average be much smaller. This was established in Theorem 5 of Lamzouri [START_REF] Lamzouri | Prime number races with three or more competitors[END_REF] when averaging over all pairs of distinct reduced residue classes, but we will need a strong result when averaging only over a subset, which requires quite different methods.

Correlation Estimate 1. Assume GRH. Let q be large and let r, s ≥ 1. For any collections a 1 , ..., a r and b 1 , ..., b s of distinct reduced residue classes modulo q, we have

1≤j≤r 1≤k≤s, b k =a j |B q (a j , b k )| Var(q) √ rs log 2 (2rs) log q .
In particular, we have

1≤k≤s, b k =a 1 |B q (a 1 , b k )| Var(q) √ s log 2 (2s) log q , and 1≤j,k≤r, j =k |B q (a j , a k )| Var(q)
r log 2 (2r) log q .

Note that this estimate saves roughly a factor of √ rs as compared with a trivial treatment using the pointwise bound

|Bq(a j ,b k )| Var(q)
1/ log q.

To prove Correlation Estimate 1 we shall need two lemmas. The first is the following, which will reduce the problem to upper bounding some easier sums. Lemma 3.1. Assume GRH. In the setting of Correlation Estimate 1, for any 1 ≤ j ≤ r we have

1≤k≤s, b k =a j |B q (a j , b k )| ϕ(q) log 2 (2s) + 1≤k≤s, b k =a j Λ(q/(q, a j -b k )) ϕ(q/(q, a j -b k )) ,
where Λ(n) denotes the von Mangoldt function.

Proof of Lemma 3.1. Let x = (q log q) 2 , and for simplicity of writing set a = a j . Then it follows from Proposition 5.1 of [START_REF] Lamzouri | The Shanks-Rényi prime number race with many contestants[END_REF] that

(3.1) 1≤k≤s, b k =a |B q (a, b k )| ϕ(q) 1 + 1≤k≤s, b k =a Λ q (q,a-b k ) ϕ q (q,a-b k ) + M 1 (q; a, b k ) + M 1 (q; b k , a) + M 2 (q; a, b k ) + M 2 (q; b k , a) + s log q,
where

M 1 (q; a, d) = n≤2x log x an≡d (mod q) Λ(n) n e -n/
x , and M 2 (q; a, d) = p ν q 1≤e≤2 log x ap e ≡d mod q/p ν log p p e+ν-1 (p -1) , and p ν q denotes that p ν is the largest power of p that divides q. Now it follows from Lemma 5.3 of [START_REF] Lamzouri | The Shanks-Rényi prime number race with many contestants[END_REF] that

M 1 (q; a, b k ) = Λ(n k ) n k + O log 2 q q ≤ log(n k ) n k + O log 2 q q ,
where n k is the least positive residue of b k a -1 modulo q. Since (log n)/n is a decreasing function for n ≥ 3, we deduce that

1≤k≤s, b k =a M 1 (q; a, b k ) 1≤k≤s, b k =a log(n k ) n k + s log 2 q q 1 + k≤s log k k + s log 2 q q log 2 (2s) + s log 2 q q .
A similar bound holds for

M 1 (q; b k , a). Next we bound the sum (M 2 (q; a, b k ) + M 2 (q; b k , a)). We have s k=1 M 2 (q; a, b k ) = p ν q e≤2 log x log p p e+ν-1 (p -1) 1≤k≤s ap e ≡b k mod q/p ν 1 ≤ p ν q e≤2 log x log p p e+ν-1 (p -1) min{p ν , s},
since the b k are distinct modulo q. Splitting the outer sum over the primes p dividing q into the cases p ≤ s and p > s, we find the above is A similar bound holds for s k=1 M 2 (q; b k , a). Putting everything together (and remembering that s ≤ q, so (s log 2 q)/q log 2 (2s)) completes the proof of Lemma 3.1.

To control the sum on the right hand side in Lemma 3.1 we shall deploy the following harmonic analysis lemma. This will be the really new aspect of our analysis of the covariances. Lemma 3.2 (Following pp 305-307 of Bourgain [START_REF] Bourgain | On Λ(p)-subsets of squares[END_REF], 1989). Let x be large and let

Q ≥ 1. Define G(θ) := q≤Q Λ(q) q q-1 a=0 1 ||θ-a/q||≤1/x ,
where || • || denotes distance to the nearest integer, and 1 denotes the indicator function.

Then if θ 1 , ..., θ R and φ 1 , ..., φ S are any real numbers that are 1/x-spaced (i.e. such that ||θ r 1 -θ r 2 || ≥ 1/x when r 1 = r 2 , and such that ||φ

s 1 -φ s 2 || ≥ 1/x when s 1 = s 2 ), we have 1≤r≤R, 1≤s≤S G(θ r -φ s ) √ RS log 2 (2QRS) + RSQ x .
Lemma 3.2 encodes the fact that rationals a/q are well spaced, so it is impossible for lots of the points θ r -φ s to be very close to lots of rationals. The proof uses additive characters, the problem being analytically nice because we are looking at pairwise differences, which corresponds to a convolution on the harmonic analysis side.

Proof of Lemma 3.2. Lemma 3.2 is inspired by a result in work of Bourgain [START_REF] Bourgain | On Λ(p)-subsets of squares[END_REF] (in a substantially different context), but differs in that it is concerned with two sets of points θ r and φ s rather than one, and it involves a weight Λ(q)/q rather than 1/q (where Λ(q) denotes the von Mangoldt function). It turns out that the former adaptation is easy, and the latter one simplifies and strengthens the argument, since all work with divisor functions becomes much easier. For the sake of completeness, we provide a fairly complete proof here.

Recall that we are given two sets θ 1 , ..., θ R and φ 1 , ..., φ S of 1/x-spaced real numbers. Corresponding to these, let I θ , I φ : R/Z → [0, 10] be bounded variation continuous functions on the real numbers mod 1, that satisfy

I θ (t) ≥ 1≤r≤R 1 ||t-θr||≤1/x and I φ (t) ≥ 1≤s≤S 1 ||t-(-φs)||≤1/x ,
(note the negative signs attached to the φ s here), and also

1 0 I θ (t)dt ≤ 1000R x , 1 0 I φ (t)dt ≤ 1000S x , supp( Îθ ), supp( Îφ ) ⊆ [-x, x],
where Îθ (k) := [START_REF] Montgomery | Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis[END_REF] for details about Beurling-Selberg functions). Then we see immediately that the convolution

(I θ * I φ )(t) := 1 0 I θ (u)I φ (t-u)du ≥ 1≤r≤R, 1≤s≤S 1 0 1 ||u-θr||≤ 1 x 1 ||t-u+φs||≤ 1 x du ≥ 1 x 1≤r≤R, 1≤s≤S 1 ||t-(θr-φs)||≤ 1 x .
Consequently, in Lemma 3.2 we have 1≤r≤R, 1≤s≤S

G(θ r -φ s ) = q≤Q Λ(q) q q-1 a=0 1≤r≤R, 1≤s≤S 1 ||(θr-φs)-a/q||≤ 1 x ≤ x q≤Q Λ(q) q q-1 a=0 (I θ * I φ )(a/q).
On writing (I θ * I φ )(a/q) in terms of its Fourier coefficients, and using that the geometric progression q-1 a=0 e 2πika/q vanishes unless q divides k (in which case the sum equals q), we find

q-1 a=0 (I θ * I φ )(a/q) = q-1 a=0 ∞ k=-∞ (I θ * I φ )(k)e 2πika/q = q ∞ k=-∞, q|k (I θ * I φ )(k).
Using also the fact that (

I θ * I φ )(k) = I θ (k) I φ (k), we conclude overall that 1≤r≤R, 1≤s≤S G(θ r -φ s ) ≤ x q≤Q Λ(q) ∞ k=-∞, q|k I θ (k) I φ (k) ≤ x ∞ k=-∞ q≤Q, q|k Λ(q)| I θ (k)|| I φ (k)|.
To finish, we define B := {-x ≤ k ≤ x : k = 0, q≤Q, q|k Λ(q) ≥ log 2 (2QRS)}, and note that since Îθ , Îφ are supposed to vanish outside the interval [-x, x], and since we always have q≤Q, q|k

Λ(q) ≤ q≤Q Λ(q) Q and also | I θ (k)| ≤ 1 0 I θ (t)dt ≤ 1000R x and | I φ (k)| ≤ 1000S
x , the right hand side above is

log 2 (2QRS)x -x≤k≤x | I θ (k)|| I φ (k)| + Qx| I θ (0)|| I φ (0)| + Qx k∈B | I θ (k)|| I φ (k)| log 2 (2QRS)x k | I θ (k)| 2 k | I φ (k)| 2 + RSQ x + RSQ x #B.
The second term above is acceptable for Lemma 3.2. By Parseval's Identity we have

k | I θ (k)| 2 k | I φ (k)| 2 1 0 I θ (t) 2 dt 1 0 I φ (t) 2 dt √ RS x ,
and so the first term above is also acceptable. Turning to the third term, since we always have q≤Q, q|k Λ(q) ≤ q|k Λ(q) = log |k| provided k = 0, there can be no elements of B having modulus smaller than exp{log 2 (2QRS)}. Moreover, if exp{log 2 (2QRS)} ≤ k ≤ x and q≤Q, q|k Λ(q) ≥ log 2 (2QRS) then in fact we must be able to write k = nm, where n is Q smooth (i.e. all the prime factors of n are at most Q)

and also n ≥ exp{log 2 (2QRS)}. Therefore, picking up a factor of 2 from counting positive and negative k, we have the upper bound

#B ≤ 2 exp{log 2 (2QRS)}≤n≤x, n is Q smooth m≤x/n 1 ≤ 2 exp{log 2 (2QRS)}≤n≤x, n is Q smooth x n .
And for any exp{log 2 (2QRS)} ≤ N ≤ x, standard upper bounds for the counting function of smooth numbers (see e.g. Theorem 7.6 of Montgomery and Vaughan [START_REF] Montgomery | Multiplicative Number Theory I: Classical Theory[END_REF]) imply that the dyadic sum

N ≤n≤2N, n is Q smooth 1 n ≤ 1 N N ≤n≤2N, n is Q smooth 1 (log 2Q) exp{- log N log 2Q log( log N log 2Q )} 1 (QRS) 10 log 2 N ,
say. So splitting up the full sum by taking N = 2 j exp{log 2 (2QRS)} for j ≥ 0, we obtain that #B x/(QRS) 10 . It follows that RSQ x #B 1/(QRS) 9 ≤ 1, which is certainly an acceptable contribution for Lemma 3.2.

Proof of Correlation Estimate 1. We may suppose without loss of generality that s ≥ r. In view of Lemma 3.1, and the fact that Var(q) ∼ ϕ(q) log q that is contained in Lemma 2.1, to prove Correlation Estimate 1 it will certainly suffice to prove that

1≤j≤r 1≤k≤s, b k =a j Λ(q/(q, a j -b k )) ϕ(q/(q, a j -b k )) √ rs log 2 (2rs).
Rewriting a little, the double sum is

≤ n|q Λ(n) ϕ(n) 1≤j≤r 1≤k≤s, b k =a j 1 a j ≡b k mod q/n n|q Λ(n) n 1≤j≤r 1≤k≤s, b k =a j 1 a j ≡b k mod q/n ,
where 1 denotes the indicator function, and where we used the fact that ϕ(n) n if n is a prime power (and so Λ(n) = 0). We also observe that we cannot have a j ≡ b k modulo q/n for two values n that are powers of different primes, since in that case we would have a j ≡ b k modulo q, which is false by assumption. Therefore the contribution to the sum from those n > rs is trivially

1≤j≤r 1≤k≤s, b k =a j log(2rs) rs ≤ log(2rs),
which is acceptable.

To bound the contribution to the sum from those n ≤ rs, we apply Lemma 3.2 with the choices Q = rs, x = max{q, (rs) 2 }, θ j := a j /q and φ k := b k /q for all j, k. Thus all the points θ j and φ k are indeed 1/x-spaced, and a j ≡ b k modulo q/n if and only if θ j -φ k = u/n for some integer u. We deduce that n≤rs,n|q

Λ(n) n 1≤j≤r 1≤k≤s, b k =a j 1 a j ≡b k mod q/n ≤ 1≤j≤r, 1≤k≤s n≤rs Λ(n) n n-1 u=0 1 ||(θ j -φ k )-u/n||≤1/x √ rs log 2 (2rs) + 1,
which is enough to prove Correlation Estimate 1.

3.2. Some matrix estimates involving the covariances. We will need some information about the determinant and inverse of a covariance matrix that is close to the identity matrix. Let M n ( ) denote the set of all n × n symmetric matrices whose diagonal entries are 1, and whose off-diagonal entries have absolute value at most .

Lemma 3.3. If ≤ 1/2n then for any A = (a j,k ) ∈ M n ( ) we have det(A) = 1 + O     1≤j,k≤n, j =k |a j,k |     .
In addition, if ≤ 1/2n then A is invertible, and if we let ãj,k denote the entries of the inverse matrix A -1 then we have

ãj,k =        1 + O 1≤l,m≤n, l =m |a l,m | if j = k, O |a j,k | + i =j,k |a j,i ||a i,k | + 2 1≤l,m≤n, l =m |a l,m | if j = k.
Lemma 3.3 extends Lemmas 4.1 and 4.2 of Lamzouri [START_REF] Lamzouri | The Shanks-Rényi prime number race with many contestants[END_REF], which would give roughly the same result if all the off-diagonal entries a j,k had size about , but are weaker if the a j,k are on average smaller (as will later be the case for us when we take of size about 1/ log q). Proof of Lemma 3.3. We have

det(A) = 1 + σ∈Sn, σ =1 sgn(σ)a 1,σ(1) ...a n,σ(n) ,
where S n denotes the symmetric group on n elements. We divide the sum according to the number t of points that are not fixed by a permutation σ. Thus the only term with t = 0 is the identity permutation, which we removed from the sum; there are no terms with t = 1; and the contribution from t = 2 has size at most

1≤j≤n 1≤k≤n, k =j |a j,k | 2 ≤ 1≤j,k≤n, j =k |a j,k |.
For any 3 ≤ t ≤ n, by averaging the total contribution is at most 1 t 1≤j≤n σ∈Sn,σ(j) =j, σ has t non-fixed points

|a j,σ(j) | t-1 = 1 t 1≤j,k≤n, j =k |a j,k | t-1
σ∈Sn,σ(j)=k, σ has t non-fixed points 1.

In the inner sum we have n-2 t-2 choices of points that are not fixed (in addition to j and k), and for any such choice there are at most (t -1)! ways to construct σ such that σ(j) = k. Thus the total contribution from any 3 ≤ t ≤ n is

≤ 1≤j,k≤n, j =k |a j,k | t-1 1 t n -2 t -2 (t -1)! ≤ 1≤j,k≤n, j =k |a j,k | ( n) t-2 ,
and our claim about det(A) follows on using the assumption ≤ 1/2n and summing over t.

In particular, we see that det(A) ≥ 1/2 for all A ∈ M n ( ), so A is invertible.

Next we need to prove the claims about ãj,k . If j = k then we have ãj,j = det(A j,j ) det(A) ,

where A j,j denotes the matrix A with the j-th row and column removed. In particular we have A j,j ∈ M n-1 ( ), and so the claim about ãj,j follows from our determinant results.

In the off-diagonal case we have

|ã j,k | = det(A k,j ) det(A) = O(| det(A k,j )|) = O   σ∈B k,j i =k |a i,σ(i) |   ,
where now B k,j denotes the set of all bijections from {1, 2, ..., n}\{k} to {1, 2, ..., n}\{j}. We again divide the sum according to the number t of points that are not fixed by σ, noting that since k = j the point j is necessarily always a non-fixed point, and the point k will always be the image of a non-fixed point. Thus there are no terms with t = 0, and the contribution from t = 1 is simply |a j,k |. When t = 2 the contribution is

i =j,k |a j,i ||a i,k |.
For any 3 ≤ t ≤ n -1, each σ must have at least t -2 non-fixed points that are different from j, and whose image is different from k, so by averaging the total contribution is at most

1 t -2 1≤i≤n, i =k,j σ∈B k,j ,σ(i) =i,j,k, σ has t non-fixed points |a i,σ(i) | t-1 = 1 t -2 i =k,j h =i,j,k |a i,h | t-1 σ∈B k,j ,σ(i)=h, σ has t non-fixed points 1.
In the inner sum we have n-4 t-3 choices of points that are not fixed (in addition to j, i and h), and for any such choice there are at most (t -1)! ways to construct σ such that σ(i) = h. Thus the total contribution from any 3

≤ t ≤ n -1 is ≤ 1≤i,h≤n, i =h |a i,h | t-1 1 t -2 n -4 t -3 (t -1)! ≤ 1≤i,h≤n, i =h |a i,h | 2 ( n) t-3 (t -1).
Proposition 1 follows on using the assumption ≤ 1/2n and summing over t.

Probabilistic tools and results

4.1. Passing to the Gaussian case. As described in section 2, the prime number race between residue classes a modulo q is associated with random variables of the general shape

W a := m i=1 (c i (a)V i ),
where (V i ) 1≤i≤m is a sequence of independent, mean zero, complex valued random variables (depending on q), and where c i (a) ∈ C are deterministic coefficients.

In order to access the tools associated with Gaussian random processes, we would like a multivariate normal approximation (i.e. multivariate central limit theorem) for the ndimensional random vector W = (W a j ) 1≤j≤n . This will allow us to replace the W a j by Gaussian random variables with the same means and covariances. We need an explicit bound for the error arising in the normal approximation, which in particular makes clear the dependence on n. There are not too many such results in the literature, and we will deduce a suitable result from the work of Reinert and Röllin [START_REF] Reinert | Multivariate Normal Approximation with Stein's Method of Exchangeable Pairs under a General Linearity Condition[END_REF].

Lemma 4.1 (Following Theorem 2.1 of Reinert and Röllin [START_REF] Reinert | Multivariate Normal Approximation with Stein's Method of Exchangeable Pairs under a General Linearity Condition[END_REF], 2009). Let the situation be as described above, let A be a finite set, and let Z = (Z a ) a∈A denote a multivariate normal random vector with the same mean vector and covariance matrix as W = (W a ) a∈A . Assume that E|V i | 4 ≤ K 4 /m 2 for all i, for some K ≥ 1.

Then for any three times differentiable function h : R #A → R we have

|Eh(W ) -Eh(Z)| |h| 2 K 2 m a,b∈A m i=1 |c i (a)| 2 |c i (b)| 2 + |h| 3 K 3 m 3/2 m i=1 a∈A |c i (a)| 3 ,
where

|h| 2 := sup a,b∈A || ∂ 2 ∂xa∂x b h|| ∞ and |h| 3 := sup a,b,c∈A || ∂ 3 ∂xa∂x b ∂xc h|| ∞ .
Reinert and Röllin's work develops a multivariate version of Stein's method of exchangeable pairs, and applies in far more general situations than above. In Appendix A we very briefly indicate how to deduce Lemma 4.1 from Theorem 2.1 of Reinert and Röllin [START_REF] Reinert | Multivariate Normal Approximation with Stein's Method of Exchangeable Pairs under a General Linearity Condition[END_REF] (this deduction being, by now, a fairly standard calculation).

For the special case of prime number races, we centre and normalize the random variables X(q, a j ) from Section 2 by setting

Y j := X(q, a j ) + C q (a j ) Var(q) = 1 Var(q) χ mod q, χ =χ 0   2χ(a j ) γχ>0 U (γ χ ) 1 4 + γ 2 χ   , 1 ≤ j ≤ n,
where the U (γ χ ) are independent random variables distributed uniformly on the unit circle.

Then Y 1 , . . . , Y n have mean zero and variance 1. Moreover, we have

EY i Y j = B q (a i , a j ) Var(q) 1 log q , i = j,
by (2.6) and (2.7). In this case, we obtain the following corollary.

Lemma 4.2. Let Z = (Z j ) 1≤j≤n denote a multivariate normal random vector whose components have mean zero, variance one, and correlations

EZ i Z j := EY i Y j = B q (a i , a j ) Var(q) .
Then for any three times differentiable function h : R n → R we have

|Eh(Y ) -Eh(Z)| n 2 |h| 2 + n 3 |h| 3 ϕ(q) .
Proof of Lemma 4.2. We apply Lemma 4.1 with the sum over 1 ≤ i ≤ m replaced by a sum over characters χ = χ 0 mod q (so m = ϕ(q) -1), and with c i (a j ) replaced by χ(a j ) and with V i replaced by

V χ := 2 Var(q) γχ>0 U (γ χ ) 1 4 + γ 2 χ .
The V χ are indeed independent, mean zero random variables. Moreover, observe that

EU (γ χ 1 )U (γ χ 2 )U (γ χ 3 )U (γ χ 4 ) vanishes unless {χ 1 , χ 2 } = {χ 3 , χ 4 }
, and in that case it is 1. Therefore we have

E|V χ | 4 1 Var(q) 2   γχ>0 1 1 4 + γ 2 χ   2 log 2 q Var(q) 2 1 ϕ(q) 2 ,
where the final inequalities follow from Lemma 2.1. So we have checked that Lemma 4.1 is applicable with K an absolute constant.

Using the facts that |c i (a j )| = |χ(a j )| ≤ 1 and #A = n and m = ϕ(q) -1, Lemma 4.2 now follows immediately from Lemma 4.1.

The above still isn't quite what we need, since we are interested in the probabilities of certain orderings of the Y j (or really of the X(q, a j )), and these correspond to the expectations of indicator functions that are not three times differentiable. So we need to approximate indicator functions by smooth functions h, with some control on the resulting error in the probabilities. There is a substantial literature that attempts to do this as efficiently as possible, but for us a simple approach will suffice. Lemma 4.3. Let Y = (Y j ) 1≤j≤n and Z = (Z j ) 1≤j≤n be as in Lemma 4.2. Let (S) be any subset of {1, ..., n} × {1, ..., n} not including any diagonal pairs (i, i), and let S be the subset of R n defined by

S := {(x 1 , . . . , x n ) ∈ R n : x i ≥ x j ∀(i, j) ∈ (S)}.
Finally, let δ > 0 be a small parameter. Then

|P(Y ∈ S) -P(Z ∈ S)| n 6 δ 3 ϕ(q) + n 2 δ.
Proof of Lemma 4.3. Let φ : R → R be a three times differentiable function such that

φ(x) =      1 if x ≥ δ ∈ [0, 1] if 0 < x < δ 0 if x ≤ 0,
and φ (d) (x) (1/δ) d for 1 ≤ d ≤ 3 (where φ (d) denotes the d-th derivative of φ). Note that such φ exists since the interval on which φ changes from 0 to 1 has length δ. Now, let h + δ , h - δ : R n → R be three times differentiable functions defined by

h - δ (x 1 , . . . , x n ) := (i,j)∈(S) φ(x i -x j ), h + δ (x 1 , . . . , x n ) := (i,j)∈(S) φ(x i -x j + δ).
By repeated application of the product rule we see

∂ 2 ∂x a ∂x b h - δ (x 1 , . . . , x n ) = (i,j),(k,l)∈(S), (i,j) =(k,l) (u,v)∈(S), (u,v) =(i,j),(k,l) φ(x u -x v ) ∂ ∂x a φ(x i -x j ) ∂ ∂x b φ(x k -x l ) + (i,j)∈(S) (u,v)∈(S), (u,v) =(i,j) φ(x u -x v ) ∂ 2 ∂x a ∂x b φ(x i -x j ).
Here each of the products has absolute value at most 1. The derivatives vanish unless a ∈ {i, j} and b ∈ {k, l}, so there are n 2 non-vanishing terms in the sums, and each term contributes 1/δ 2 because φ (d) (x)

(1/δ) d . We conclude from this calculation that |h - δ | 2 n 2 /δ 2 . An exactly similar argument shows that |h - δ | 3 n 3 /δ 3 , and the same for h + δ . Now observe that Eh - δ (Y ) ≤ P(Y ∈ S) ≤ Eh + δ (Y ). In addition, by Lemma 4.2 we have

|Eh - δ (Y ) -Eh - δ (Z)| n 6 δ 3 ϕ(q) and |Eh + δ (Y ) -Eh + δ (Z)| n 6
δ 3 ϕ(q) , so to prove Lemma 4.3 it will suffice to show that

|P(Z ∈ S) -Eh - δ (Z)| n 2 δ and |P(Z ∈ S) -Eh + δ (Z)| n 2 δ.
But this is fairly easy, because we have for example that

|P(Z ∈ S) -Eh - δ (Z)| ≤ P(|Z i -Z j | ≤ δ for some (i, j) ∈ (S)) ≤ (i,j)∈(S) P(|Z i -Z j | ≤ δ).
And each difference Z i -Z j is a normal random variable with mean zero and variance

E(Z i -Z j ) 2 = EZ 2 i + EZ 2 j -2EZ i Z j = 2 -2 B q (a i , a j ) Var(q) = 2 + O(1/ log q),
in view of (2.6) and (2.7) (and our assumption that if (i, j) ∈ (S) then i = j, and therefore a i = a j ). Such a normal random variable has probability O(δ) of lying in any δ-ball, and there are at most n 2 pairs in (S), so we have the required bound n 2 δ for the right hand side.

Finally, by making the optimal choice of δ in Lemma 4.3, and correcting for the small shifts C q (a j )/ Var(q) in the definition of Y j , we obtain the following result that we shall actually use.

Normal Approximation Result 1. Let X := X(q,a j ) √ Var(q) 1≤j≤n , and let Z = (Z j ) 1≤j≤n denote a multivariate normal random vector whose components have mean zero, variance one, and correlations EZ i Z j := Bq(a i ,a j ) Var(q) . Then for any set S as in Lemma 4.3, we have

|P(X ∈ S) -P(Z ∈ S)| n 3 ϕ(q) 1/8 .
Proof of Normal Approximation Result 1. Choosing δ = n/ϕ(q) 1/8 in Lemma 4.3 is optimal and leads to the bound

|P(Y ∈ S) -P(Z ∈ S)| n 3 ϕ(q) 1/8 . Since we have X = Y -( Cq(a j ) √ Var(q)
) 1≤j≤n , and as described in section 2 we always have C q (a j )/ Var(q) q / Var(q) 1/ϕ(q) 1/2-(which is much smaller than δ = n/ϕ(q) 1/8 ), then as well as the inequality Eh - δ (Y ) ≤ P(Y ∈ S) ≤ Eh + δ (Y ) in the proof of Lemma 4.3 we will actually have Eh - δ (Y ) ≤ P(X ∈ S) ≤ Eh + δ (Y ), provided the function φ there is chosen suitably (e.g. such that φ(x) = 0 if x ≤ δ/100, and φ(x) = 1 if x ≥ 99δ/100). So we will have the same bound for |P(X ∈ S) -P(Z ∈ S)|.

Normal comparison results.

In this subsection we record some celebrated results that let one compare probabilities for multivariate Gaussians with different covariance matrices.

Normal Comparison Result 1 (Slepian's Lemma, see e.g. Piterbarg [START_REF] Piterbarg | Asymptotic Methods in the Theory of Gaussian Processes and Fields[END_REF]). Let X = (X i ) 1≤i≤n and W = (W i ) 1≤i≤n be vectors of jointly normal, mean zero, variance one random variables. Suppose that EX i X j ≤ EW i W j for all pairs i, j. Then for any real numbers u 1 , ..., u n we have

P(X i ≤ u i ∀ 1 ≤ i ≤ n) ≤ P(W i ≤ u i ∀ 1 ≤ i ≤ n).
Slepian's Lemma says that decreasing the correlations of normal random variables makes them stochastically larger. It allows one to replace complicated correlations with simpler ones and it has the great advantage that it is never worse than trivial.

Using Slepian's Lemma we can prove the following useful bound.

Normal Comparison Result 2. Suppose that n ≥ 2 and that > 0 is sufficiently small. Let X 1 , ..., X n be mean zero, variance one, jointly normal random variables, and suppose that EX i X j ≤ whenever i = j. Then for any A ≥ 1 and any B > 0 we have

P( max 1≤i≤n X i ≤ A) exp -Θ n e -A 2 /2+O( A 2 +AB+B 2 ) A + B + e -B 2 / .
In particular, for any 100 ≤ δ ≤ 1/100 (say) we have

P( max 1≤i≤n X i ≤ (2 -δ) log n) e -Θ(n δ/20 / √ log n) + n -δ 2 /50 .
Proof of Normal Comparison Result 2. In view of Slepian's Lemma, the probability is at most as large as with the X i replaced by W i , where EW i W j = whenever i = j. However, it is well known that one can explicitly construct random variables with this covariance structure, by letting Z 0 , Z 1 , ..., Z n be independent standard normal random variables, and then taking

W i = √ Z 0 + √ 1 -Z i ∀ 1 ≤ i ≤ n.
So conditioning on the value of Z 0 , we deduce that

P( max 1≤i≤n X i ≤ A) ≤ P( max 1≤i≤n W i ≤ A) = 1 √ 2π ∞ -∞ Φ A + √ y √ 1 - n e -y 2 /2 dy,
where Φ denotes the standard normal cumulative distribution function.

Splitting the integral at y = B 2/ , we find it is

(4.1) ≤ Φ A + B √ 2 √ 1 - n + ∞ B √ 2/ e -y 2 /2 dy Φ A + B √ 2 √ 1 - n + e -B 2 / .
Moreover, for any z ≥ 1 we have

Φ(z) = 1 - 1 √ 2π ∞ z e -y 2 /2 dy ≤ 1 -Θ( e -z 2 /2 z ),
and so (since is small) we deduce

(4.2) Φ A + B √ 2 √ 1 - n ≤ 1 -Θ e -(1+2 )(A+B √ 2) 2 /2 A + B n ,
n e -(1+2 )(A+B √ 2) 2 /2 A + B n e -(1+2 )A 2 /2-2AB A + B n e -(1+δ/50)(1-δ/2) log n-(2/5)δ log n √ log n ≥ n δ/20 √ log n .
The above results only give one sided bounds on probabilities, whereas in our theorems we want to show probabilities are equal up to a small error. The following result can supply such estimates in some cases. [START_REF] Li | A normal comparison inequality and its applications[END_REF]). Let X = (X i ) 1≤i≤n and W = (W i ) 1≤i≤n be vectors of jointly normal, mean zero, variance one random variables. For each pair i, j define ρ i,j := max{|EX i X j |, |EW i W j |}. Then for any real numbers u 1 , ..., u n we have

Normal Comparison Result 3 (See Theorem 2.1 of Li and Shao

P(X i ≤ u i ∀ 1 ≤ i ≤ n) -P(W i ≤ u i ∀ 1 ≤ i ≤ n) ≤ 1 2π 1≤i<j≤n, EX i X j >EW i W j (arcsin(EX i X j ) -arcsin(EW i W j )) exp - (u 2 i + u 2 j ) 2(1 + ρ i,j )
.

Note that by swapping the roles of X and W one can obtain two sided bounds from this result.

A problem with Normal Comparison Result 3 is that the probabilities on the left may themselves be very small, and so the bound on the right may be worse than trivial. We know of no result that can overcome this difficulty in general, and a major issue in proving our theorems will be arranging things so that we only apply Normal Comparison Result 3 to probabilities that are fairly large, as discussed in the introduction.

4.3.

A result on leaders. In this subsection we shall establish Theorem 1.5. To this end, we shall first prove the following. Lemma 4.4. Let the situation be as in Theorem 1.5. Then for any x ≥ 1 we have

|P( max 2≤i≤n X i ≤ x|X 1 = x) -Φ(x) n-1 | xe -(x 2 /2)(1+O( )) 2≤i≤n |r 1,i | + e -x 2 (1+O( )) 2≤i<j≤n |r i,j |.
Proof of Lemma 4.4. Consider the transformed random variables

V i := X i -r 1,i X 1 1 -r 2 1,i , 2 ≤ i ≤ n.
It is easy to check that these are all standard normal random variables, and they satisfy

EV i X 1 = 0 ∀2 ≤ i ≤ n, EV i V j = r i,j -r 1,i r 1,j (1 -r 2 1,i )(1 -r 2 1,j ) = O(|r i,j |+|r 1,i ||r 1,j |) = O( ) ∀i = j.
In particular, since the V i are uncorrelated with X 1 they are independent from X 1 , and so we see

P( max 2≤i≤n X i ≤ x|X 1 = x) = P V i ≤ x(1 -r 1,i ) 1 -r 2 1,i ∀2 ≤ i ≤ n = P V i ≤ x 1 -r 1,i 1 + r 1,i ∀2 ≤ i ≤ n .
Next, using Normal Comparison Result 3 twice (with X and W swapped the second time) to compare the V i with independent standard normals we obtain

P V i ≤ x 1 -r 1,i 1 + r 1,i ∀2 ≤ i ≤ n - 2≤i≤n Φ x 1 -r 1,i 1 + r 1,i = O 2≤i<j≤n |EV i V j | exp(-x 2 ((1 -r 1,i )/(1 + r 1,i )) + ((1 -r 1,j )/(1 + r 1,j )) 2(1 + |EV i V j |) ) = O e -x 2 (1+O( )) 2≤i<j≤n (|r 1,i ||r 1,j | + |r i,j |) .
Notice here that the contribution from |r i,j | is acceptable for Lemma 4.4, and the contribution from |r 1,i ||r 1,j | may be rewritten as

e -x 2 /2(1+O( )) 2≤i≤n |r 1,i | 2 .
If this term is smaller than one then it is acceptable because it is smaller than the first error term in Lemma 4.4, and if it is bigger than one then so is the first error term in Lemma 4.4, so the lemma is trivially true.

To finish it will suffice to prove that

2≤i≤n Φ x 1 -r 1,i 1 + r 1,i -Φ(x) n-1 xe -(x 2 /2)(1+O( )) 2≤i≤n |r 1,i |.
But this follows simply because we have

Φ x 1 -r 1,i 1 + r 1,i -Φ(x) = 1 √ 2π x √ (1-r 1,i )/(1+r 1,i ) x e -y 2 /2 dy = O x|r 1,i |e -(x 2 /2)(1+O( ))
for each 2 ≤ i ≤ n, on noting that

1-r 1,i 1+r 1,i = 1 + O(|r 1,i |) = 1 + O( ) for all such i.
Proof of Theorem 1.5. Lemma 4.4 looks very close to Theorem 1.5, but it doesn't immediately yield the theorem because it is quite weak (possibly worse than trivial) unless x is fairly large. (As x becomes smaller we expect the probabilities on the left to become very small, whereas the bound on the right becomes larger.) Fortunately we can deal with the case of small x using Normal Comparison Result 2. Indeed, if we choose δ = 1/1000, say, then we clearly have

|P(X 1 > max 2≤i≤n X i )-P(X 1 > max 2≤i≤n X i , and X 1 > (2 -δ) log n)| ≤ P( max 2≤i≤n X i ≤ (2 -δ) log n),
and by Normal Comparison Result 2 the right hand side is

e -Θ(n 1/20000 / √ log n) + n -1/50000000 n -100 ,
since is assumed to be small enough. We would have the same bound if the X i were replaced by independent normals Xi , and in that case we have P( X1 > max 2≤i≤n Xi ) = 1/n by symmetry, so to prove Theorem 1.5 it will suffice to show that

|P(X 1 > max 2≤i≤n X i , and X 1 > (2 -δ) log n) -P( X1 > max 2≤i≤n Xi , and X1 > (2 -δ) log n)| n -1.99 2≤i≤n |r 1,i | + n -2.99 2≤i<j≤n |r i,j |.
But using Lemma 4.4 we have

P(X 1 > max 2≤i≤n X i , and X 1 > (2 -δ) log n) -P( X1 > max 2≤i≤n Xi , and X1 > (2 -δ) log n) = ∞ √ (2-δ) log n e -x 2 /2 √ 2π P( max 2≤i≤n X i ≤ x|X 1 = x)dx - ∞ √ (2-δ) log n e -x 2 /2 √ 2π Φ(x) n-1 dx = O n -(2-δ)(1+O( )) 2≤i≤n |r 1,i | + n -(3/2)(2-δ)(1+O( )) 2≤i<j≤n |r i,j | .
The Theorem follows on remembering that δ = 1/1000 and is sufficiently small.

4.4.

Preparation for the k-contestant theorems. In this subsection we shall develop two lemmas that will be required later for the proof of Theorem 1.6. We present these in a moderate amount of generality, and they might be of wider interest. We begin with a kind of hybrid normal comparison inequality.

Lemma 4.5. Let (W i ) i∈I be a finite collection of jointly standard normal random variables, let ≥ 1 > 0 be small, and suppose that

|EW i W j | ≤ ∀i = j, and EW i W j ≤ 1 ∀i = j.
Then if w ≥ 1, and w/2 ≤ w i ≤ 2w for all i ∈ I, we have

P(W i ≤ w i ∀i ∈ I) - i∈I Φ(w i ) i∈I Φ((1 + O( ))w i ) + e -Θ(( w) 2 /( 1 + 3 )) i,j∈I, i =j |EW i W j |e -(1/2+O( ))(w 2 i +w 2 j ) .
The key advantage of Lemma 4.5, as opposed to a result like Normal Comparison Result 3, is the presence of the bracketed prefactor on the right hand side, which can make the inequality much more powerful if i∈I Φ(w i ) is small. Notice also that if one has a stronger upper bound for EW i W j than an absolute value bound (i.e. if 1 is appreciably smaller than ), then the second term in the bracket is improved. This should not be too surprising, since Slepian's Lemma (Normal Comparison Result 1) implies that negative correlations make normal random variables stochastically smaller.

Proof of Lemma 4.5. If one looks inside the proofs of the usual normal comparison lemmas (see e.g. Li and Shao's paper [START_REF] Li | A normal comparison inequality and its applications[END_REF]), they yield that

|P(W i ≤ w i ∀i ∈ I) - i∈I Φ(w i )| i,j∈I, i =j P i,j |EW i W j |e -(w 2 i +w 2 j )/2(1+|EW i W j |) = i,j∈I, i =j P i,j |EW i W j |e -(1/2+O( ))(w 2 i +w 2 j )
,

where P i,j := sup 0≤h≤1 P(W (h) k ≤ w k ∀ k ∈ I|W (h) i = w i , W (h) j = w j ),
and the W (h) k are mean zero, variance one, jointly normal random variables with correlations

EW (h) k W (h) l = hEW k W l , k = l.
(Thus, in particular, when h = 1 the W (h) k are simply the W k , and when h = 0 the W (h) k are independent standard normal random variables.) We will show that

P(W k ≤ w k ∀ k ∈ I|W i = w i , W j = w j ) i∈I Φ((1 + O( ))w i ) + e -Θ(( w) 2 /( 1 + 3 ))
for any i = j. Exactly the same argument would yield the corresponding estimate for any 0 ≤ h ≤ 1 (uniformly over h), thus proving Lemma 4.5.

Indeed, if we define

V k := W k - (EW k W i -EW k W j EW i W j ) 1 -(EW i W j ) 2 W i - (EW k W j -EW k W i EW i W j ) 1 -(EW i W j ) 2 W j ∀k ∈ I\{i, j},
then one can check that EV k W i = EV k W j = 0, and so if k, l ∈ I\{i, j} then

EV k V l = EV k W l -0 -0 = EV k W l = EW k W l -EW k W i EW i W l -EW k W j EW j W l + O( 3 ).
In particular, it follows that EV 2 k = 1 + O( 2). One can also check that when k = l we have the upper bound

EV k V l ≤ 1 + 2 1 + O( 3 ) ≤ (C/2)( 1 + 3 ), for a suitable positive constant C, since EW k W l ≤ 1 and if -EW k W i EW i W l is
positive then one of the factors must be positive and one negative, so one has size at most 1 and the other has size at most . Now if we set Ṽk :

= V k √ EV 2 k , then P(W k ≤ w k ∀ k ∈ I|W i = w i , W j = w j ) is = P(V k ≤ w k - (EW k W i -EW k W j EW i W j ) 1 -(EW i W j ) 2 w i - (EW k W j -EW k W i EW i W j ) 1 -(EW i W j ) 2 w j ∀ k ∈ I\{i, j}) = P( Ṽk ≤ (1 + O( ))w k ∀ k ∈ I\{i, j}),
where the first equality uses the fact that V k is uncorrelated with, and therefore independent of, W i and W j (so we can remove the conditioning), and the second equality uses the fact that w i , w j w w k . Now the Ṽk are jointly standard normal random variables with off-diagonal correlations that are ≤ (1 + O( 2))EV k V l ≤ C( 1 + 3 ), so by Slepian's Lemma (Normal Comparison Result 1) the probability is at most as large as if all the off-diagonal correlations were equal to C( 1 + 3 ). Arguing as in the proof of Normal Comparison Result 2, it follows that

P( Ṽk ≤ (1 + O( ))w k ∀ k ∈ I\{i, j}) ≤ 1 √ 2π ∞ -∞ k∈I, k =i,j Φ (1 + O( ))w k + C( 1 + 3 )y 1 -C( 1 + 3 ) e -y 2 /2 dy,
and Lemma 4.5 follows on splitting the integral at y = w/ C( 1 + 3 ).

We finish this section by applying Lemma 4.5 to prove the following general estimate for

P(max k+1≤i≤n X i ≤ x k |X 1 = x 1 , ..., X k = x k ),
which is what we shall actually use later when proving Theorem 1.6.

Lemma 4.6. Let X 1 , ..., X n be mean zero, variance one, jointly normal random variables, and write r i,j := EX i X j . Let ≥ 1 , 2 > 0 be sufficiently small, and suppose that |r i,j | ≤ ∀i = j, and r i,j ≤ 1 ∀i = j. for any distinct k + 1 ≤ i, j ≤ n.

Let 1 ≤ k ≤ n -2
Then for any real numbers x 1 , ..., x k-1 ≥ x k ≥ 1 such that k i=1 x 2 i 1/ , we have

P( max k+1≤i≤n X i ≤ x k |X 1 = x 1 , ..., X k = x k ) - n i=k+1 Φ (w i ) e -(1+O( √ k))x 2 k n i=k+1 Φ ((1 + O( ))w i ) + e -Θ ( x k ) 2 /( 1 + 2 + 3 ) (4.3) ×   k+1≤i<j≤n |r i,j | + k l=1 n i=k+1 |r i,l | 2   ,
for certain numbers w i that satisfy

w i = (1 + O( 2 k))x k + O k l=1 x l |r i,l | = 1 + O √ k x k .
The reader may wish to compare Lemma 4.6 with Lemma 4.4. The first bracketed term on the right hand side of Lemma 4.6 will be crucial when we come to apply the lemma to prime number races with k large, since on the relevant range of x 1 , ..., x k it will turn out that n i=k+1 Φ (w i ) is rather small (in fact of size roughly e -Ck ).

Proof of Lemma 4.6. Note first that provided k ≤ 1/2, Lemma 3.3 implies that the covariance (sub-)matrix A := (r i,j ) 1≤i,j≤k is invertible. Let (r i,j ) 1≤i,j≤k := A -1 denote the inverse matrix, and for all k + 1 ≤ i ≤ n and all 1 ≤ l ≤ k set u i,l := k s=1 r l,s r i,s , and

V i := X i - k l=1 u i,l X l .
Then the random variables V i are zero mean, jointly normal random variables, and for any 1 ≤ t ≤ k they satisfy

EV i X t = r i,t - k l=1 u i,l r l,t = r i,t - 1≤l,s≤k r i,s rl,s r l,t = r i,t - 1≤s≤k r i,s 1 s=t = 0.
In other words, the random variables V i are uncorrelated with, and therefore independent from, all of X 1 , X 2 , . . . , X k . Let us also note that for any k + 1 ≤ i ≤ n and any 1 ≤ l ≤ k, using Lemma 3.3 to estimate the r l,s yields that (4.4)

u i,l = 1 + O 1≤t,u≤k, t =u |r t,u | r i,l + O     k s=1, s =l |r i,s |     |r l,s | + t =l,s |r l,t ||r s,t | + 2 1≤t,u≤k, t =u |r t,u |         ,
and using our assumptions that the off-diagonal covariances are bounded by , and that k is small, it follows in particular that (4.5)

|u i,l | |r i,l | + k s=1, s =l |r i,s | .
We also see that

(4.6) EV 2 i = EV i X i -0 = EV i X i = 1 + O k l=1 |u i,l | = 1 + O( 2 k).
In view of the above discussion, if we rewrite the event max k+1≤i≤n X i ≤ x k in terms of the V i so that we can remove the conditioning, we find

P( max k+1≤i≤n X i ≤ x k |X 1 = x 1 , ..., X k = x k ) = P V i ≤ x k - k l=1 x l u i,l ∀k + 1 ≤ i ≤ n = P (W i ≤ w i ∀k + 1 ≤ i ≤ n)
where

w i := 1 √ EV 2 i x k -k l=1 x l u i,l , and
W i := V i √ EV 2 i
are mean zero, variance one, jointly normal random variables. Proceeding to estimate the off-diagonal correlations, we note first that

EW i W j = (1 + O( 2 k))EV i V j = (1 + O( 2 k))EX i V j ,
and then from (4.4) we deduce that (4.7)

EW i W j = (1 + O( 2 k))r i,j -1 + O 2 k + 1≤t,u≤k, t =u |r t,u | k l=1 r i,l r j,l + O     k l=1 k s=1,s =l |r i,l ||r j,s | |r l,s | + k t=1,t =l,s |r l,t ||r s,t | + 2 1≤t,u≤k, t =u |r t,u |     .
Since |r i,j | ≤ and r i,j ≤ 1 when i = j, and since k is small, it follows in particular that whenever i = j we have |EW i W j | = O( ), and

EW i W j ≤ (1 + O( 2 k)) 1 + (1 + O( 2 k 2 ))k 1 + O( 2 ) = O( 1 + 2 ).
Finally, using that k l=1 x l ≤ k k l=1 x 2 l k/ (which follows from the Cauchy-Schwarz inequality) together with (4.5) we find

w i = (1 + O( 2 k))x k + O k l=1 x l |r i,l | + √ k k s=1 |r i,s | = 1 + O( 2 k) x k + O k l=1 x l |r i,l | .
Here the final equality follows because the x l are all ≥ 1 whereas k is small. We also have

k l=1 x l |r i,l | ≤ k l=1 x l √ k, and therefore w i = 1 + O √ k x k , and hence x k /2 ≤ w i ≤ 2x k for all k + 1 ≤ i ≤ n.
This all means that Lemma 4.5 is applicable, with 1 replaced by O( 1 + 2 ) and w replaced by x k . Lemma 4.6 follows from Lemma 4.5 on noting that

1/2 + O( ) (w 2 i + w 2 j ) = 1 + O( √ k) x 2
k , and using (4.7) to get

k+1≤i<j≤n |EW i W j | k+1≤i<j≤n |r i,j | + k l=1 |r i,l ||r j,l | + k l=1 k s=1,s =l |r i,l ||r j,s | k+1≤i<j≤n |r i,j | + k l=1 n i=k+1 |r i,l | 2 + k l=1 n i=k+1 |r i,l | 2 k+1≤i<j≤n |r i,j | + k l=1 n i=k+1 |r i,l | 2 .
Here the final line uses the Cauchy-Schwarz inequality in the form

k l=1 n i=k+1 |r i,l | 2 ≤ k k l=1 n i=k+1 |r i,l | 2 .
5. The full prime number race: Proof of Theorem 1.2

Suppose q is large, and let Z = (Z j ) 1≤j≤n denote a multivariate normal random vector whose components have mean zero, variance one, and correlations

r i,j = EZ i Z j = B q (a i , a j ) Var(q) .
Let S 1 , S 2 ⊆ {1, 2, . . . , n} be non-empty. Then Correlation Estimate 1 implies that (5.1)

∈S 1 ,s∈S 2 l =s |r ,s | |S 1 | • |S 2 | log 2 2|S 1 | • |S 2 | log q , and
1≤ ,s≤n, =s |r ,s | n log 2 (2n) log q .
Let C = (r i,j ) 1≤i,j≤n be the covariance matrix of Z 1 , . . . , Z n . In view of the pointwise bound |r i,j | 1/ log q (for i = j) from Lemma 2.2, we may apply Lemma 3.3 with 1/ log q provided that n is at most a certain constant times log q, and obtain that

(5.2) det(C) = 1 + O n(log n) 2 (log q) 2 ,
and

(5.3) r ,s =      1 + O n(log n) 2 (log q) 2 if = s O |r ,s | + 1≤j≤n j = ,s |r ,j ||r s,j | + n(log n) 2 (log q) 3 if = s,
where r i,j denote the entries of the inverse matrix C -1 . Now the key ingredient in the proof of Theorem 1.2 is the following proposition, which gives an approximation for the joint density function of Z 1 , . . . , Z n . Let f (x 1 , . . . , x n ) be this density, and define the Euclidean norm ||x|| := (x 2 1

+ • • • + x 2 n ) 1/2 .
Proposition 5.1. Let 2 ≤ n log q be an integer. For any x = (x 1 , . . . , x n ) ∈ R n , we have

f (x 1 , . . . , x n ) = 1 + O n(log n) 2 (log q) 2 × 1 (2π) n/2 exp - ||x|| 2 2 1 + O (log n) 4 log q + n(log n) 6 (log q) 2 + n 2 (log n) 2 (log q) 3 .
Proof. By definition and by (5.2) we have (5.4)

f (x 1 , . . . , x n ) = 1 (2π) n/2 det(C) exp - 1 2 x T C -1 x = 1 + O n(log n) 2 (log q) 2 1 (2π) n/2 exp - 1 2
x T C -1 x , and using (5.3) we obtain (5.5)

x T C -1 x = 1≤ ,s≤n x x s r ,s = ||x|| 2 1 + O n(log n) 2 (log q) 2 + 1≤ =s≤n
x x s r ,s , and also that (5.6)

1≤ =s≤n

x x s r ,s

1≤ =s≤n |x x s r ,s | + 1≤ =s≤n |x x s | 1≤j≤n j = ,s |r ,j ||r s,j | + n(log n) 2 (log q) 3 1≤ =s≤n |x x s |.
Now let J := 2 log n , and for each 1 ≤ j ≤ J -1 define S j to be the subset of {1, . . . , n} consisting of those for which ||x||/2 j < |x | ≤ ||x||/2 j-1 . Also let S J be the set of those for which |x | ≤ ||x||/2 J-1 . Then note that for all 1 ≤ j ≤ J we have Proof of Theorem 1.2. By Proposition 5.1, if 2 ≤ n ≤ log q/(log log q) 4 then

|S j | ≤ 2 2j , since |S J | ≤ n ≤ 2 2J and if j < J, then ||x|| 2 2 2j |S j | ≤ x 2 1 + • • • x 2 n = ||x|| 2 .
P(Z 1 > Z 2 > • • • > Z n ) = x 1 >•••>xn f (x 1 , . . . , x n )dx 1 • • • dx n = 1 + O n(log n) 2 (log q) 2 1 (2π) n/2 x 1 >•••>xn exp - ||x|| 2 2 1 + O (log n) 4 log q dx 1 • • • dx n = 1 + O n(log n) 2 (log q) 2 1 n! 1 √ 2π ∞ -∞ exp - t 2 2 1 + O (log n) 4 log q dt n = 1 + O n(log n) 4 log q 1 n! ,
since the integrand is symmetric in x 1 , . . . , x n . Combining this with Normal Approximation Result 1, we obtain

P(X(q, a 1 ) > X(q, a 2 ) > • • • > X(q, a n )) = 1 + O n(log n) 4 log q 1 n! + O n 3 ϕ(q) 1/8 .
If n ≤ log q/(log log q) 4 then 1/n! ≥ 1/n n = 1/q o(1) , so the second "big Oh" term may be absorbed into the first, and Theorem 1.2 follows.

6. The leader: Proof of Theorem 1.4

We may assume that q is sufficiently large, otherwise the theorem is trivial. Then we may assume that n ≥ log 0.1 q, say, otherwise the theorem follows from Theorem 1.2. Let Z = (Z j ) 1≤j≤n denote a multivariate normal random vector whose components have mean zero, variance one, and correlations r i,j = EZ i Z j = B q (a i , a j )/Var(q). In view of Theorem 1.5 and Correlation Estimate 1, and our assumption that n ≥ log 0.1 q,

|P(Z 1 > max 2≤i≤n Z i ) - 1 n | n -100 + n -1.99 2≤i≤n |r 1,i | + n -2.99 2≤i<j≤n |r i,j | n -100 +
√ n log 2 n n 1.99 log q + n log 2 n n 2.99 log q log 2 n n 1.49 log q = 1 n • log 2 n n 0.49 log q .

Theorem 1.4 follows by combining this estimate with Normal Approximation Result 1.

7.

Ordering the first k contestants: Proof of Theorem 1.6

Throughout this section we let Z 1 , ..., Z n denote mean zero, variance one, jointly normal random variables corresponding to a prime number race modulo q (i.e. with off-diagonal correlations r i,j = EZ i Z j = B q (a i , a j )/Var(q)), where q is large.

Our key tool in proving Theorem 1.6 will be the version of Lemma 4.6 that arises from specializing to the prime number race situation. We record this now, together with an estimate for the number of large values of the |r i,j | that we shall need when deducing it. Lemma 7.1. For any k + 1 ≤ i ≤ n and any j ≥ 1 we have

# 1 ≤ l ≤ k : |r i,l | ≥ 1 2 j log q 2 2j j 4 .
Proof. Let S j denote the set of 1 ≤ l ≤ k for which |r i,l | ≥ 1 2 j log q . Using Correlation Estimate 1, we have

l∈S j |r i,l | #S j log 2 (2#S j ) log q .
On the other hand, by definition of S j the left hand side is ≥ #S j 2 j log q , and so the lemma follows by rearranging. Lemma 7.2. Let k be a positive integer such that k/ log q is small enough, and suppose

n ≥ k + 2 is large. Let 1 ≤ A ≤ 2 √ log n be real. If x = (x 1 , ..., x k ) is such that x 1 , ..., x k-1 ≥ x k ≥ A and ||x|| ≤ 10
√ log q, then we have

P( max k+1≤i≤n Z i ≤ x k |Z 1 = x 1 , ..., Z k = x k ) = n i=k+1 Φ (w i ) + O e -A 2 1+O √ k/ log q n(log n) 4 log q n i=k+1
Φ ((1 + O(1/ log q))w i ) + e -Θ(A 2 (log q)/(log log q) 9 ) , for certain numbers w i that satisfy

w i = 1 + O k (log q) 2 x k + O k l=1
x l |r i,l | .

Proof. We want to apply Lemma 4.6, and Lemma 2.2 shows that we may do so with 1/ log q. We also have B q (a, b) ≤ C log q (when a = b) by (2.10), and therefore we may take 1 1/ϕ(q), which is very small. It is more difficult to determine a permissible value of 2 , but we may do so using Lemma 7.1 together with Correlation Estimate 1. Indeed, we can write k l=1 = a≤2 log k l∈Sa , where S a := {1 ≤ l ≤ k : 1 2 a log q < |r i,l | ≤ log 2 (2k) log q = log 8 (2k) log 3 q (log log q) 8 log 3 q .

By dividing up the sum over t according to the size of |r (log log q) 5 log 2 q .

Putting these estimates together with the standard bounds

k l=1 |r i,l | √ k log 2 (2k) log q and 1≤l,s≤k, l =s |r l,s | k log 2 (2k)
log q , (coming from Correlation Estimate 1), one checks that it is permissible to take 2 (log log q) 9 log 3 q , whereupon Lemma 4.6 implies that

P( max k+1≤i≤n Z i ≤ x k |Z 1 = x 1 , ..., Z k = x k ) - n i=k+1 Φ (w i ) e -1+O √ k/ log q x 2 k n i=k+1
Φ ( wi ) + e -Θ(A 2 (log q)/(log log q) 9 )

  k+1≤i<j≤n |r i,j | + k l=1 n i=k+1 |r i,l | 2   ,
where wi = (1 + O(1/ log q))w i .

Finally, the stated form of the result follows by using Correlation Estimate 1 again to show that the second bracket on the right hand side is n log 2 n log q + nk log 4 n log 2 q n log 4 n log q .

We have now collected all the necessary ingredients for the proof of Theorem 1.6.

Proof of Theorem 1.6. Let c > 0 be a small constant to be fixed later, and suppose first that cn/ log n < k ≤ n. Then our condition k log 10 k ≤ (log q)/ log n implies that n c (log q)/(log log q) 10 , in which case Theorem 1.2 is applicable and implies that

δ k (q; a 1 , . . . , a n ) = (n -k)! n! 1 + O n(log n) 4 log q = (n -k)! n! 1 + O k(log k) 4 log n log q .
This result is already acceptable for Theorem 1.6, so we may assume henceforth that we are in the other case where 2 ≤ k ≤ cn/ log n. We may also assume throughout that n ≥ log 0.1 q, because otherwise the result again follows from Theorem 1.2 regardless of the value of k.

Since we assume that q is large, we may assume in particular that n is large. First, it follows from Normal Approximation Result 1 together with the discussion in section 2 that

δ k (q; a 1 , . . . , a n ) -P(Z 1 > Z 2 > ... > Z k > max k+1≤i≤n Z i ) n 3 ϕ(q) 1/8 .
This error is completely negligible for Theorem 1.6, since we assume k log 10 k ≤ (log q)/ log n and (log q)/ log n is large.

Let 1 ≤ A ≤ 2 √ log n be a real parameter to be chosen later. Then we have

P(Z 1 > Z 2 > ... > Z k > max k+1≤i≤n Z i ) = P(Z 1 > ... > Z k > max k+1≤i≤n Z i , and Z k > A) + O P max k+1≤i≤n Z i ≤ A ,
and using Normal Comparison Result 2 with 1/ log q we get

P max k+1≤i≤n Z i ≤ A exp -Θ n e -A 2 /2+O(A 2 / log q+AB+B 2 ) A + B + e -Θ(B 2 log q) ,
for any B > 0. Simply choosing B = 1, and using that 1 ≤ A ≤ 2 √ log n ≤ 2 √ log q and that k log 10 k ≤ (log q)/ log n, we deduce (7.1)

P max k+1≤i≤n Z i ≤ A exp -Θ n e -A 2 /2+O(A) A + n -2k .
Ultimately we will choose A so this whole thing is n -2k

(n-k)! n!
1 n log 0.1 q , which will be an acceptable error term.

Next, we have (7.2)

P(Z 1 > Z 2 > ... > Z k > max k+1≤i≤n Z i , and Z k > A) = x 1 >...>x k >A f (x 1 , ..., x k ) • P max k+1≤i≤n Z i < x k Z 1 = x 1 , ..., Z k = x k dx 1 • • • dx k = x 1 >...>x k >A, ||x||≤3 √ k log n f (x 1 , ..., x k ) • P max k+1≤i≤n Z i < x k Z 1 = x 1 , ..., Z k = x k dx 1 • • • dx k + O(n -2k ),
where as before f denotes the joint density of Z 1 , ..., Z k , and where the second equality follows because by Proposition 5.1 (and the fact that k log q) we always have f (x 1 , ..., x k )

1 (2π) k/2 exp -||x|| 2 4
. Moreover, we note that when ||x|| ≤ 3 √ k log n, Proposition 5.1 implies

(7.3) f (x 1 , ..., x k ) = 1 + O k log 4 k log n log q 1 (2π) k/2 exp - ||x|| 2 2 .
Now let us note that Φ(y ± ) = 1 + O e -(y+O( )) 2 /2 Φ(y), for any y, > 0. In view of this, and the crude bound k l=1 x l |r i,l | (1/ log q) √ k k l=1 x 2 l k/ log q, the main term n i=k+1 Φ (w i ) in our Lemma 7.2 estimate for P max k+1≤i≤n Z

i < x k Z 1 = x 1 , ..., Z k = x k equals (7.4) n i=k+1 Φ (1 + O(1/ log q))x k + O k l=1 x l |r i,l | = n i=k+1 Φ 1 + O(1/ log q) x k n i=k+1, k l=1 x l |r i,l |≥ x k log q 1 + O e -1/2+O( √ k/ log q) x 2 k k l=1 x l |r i,l | = Φ 1 + O(1/ log q) x k n-k exp          O e -A 2 2 1+O √ k/ log q n i=k+1, k l=1 x l |r i,l |≥ x k log q k l=1 x l |r i,l |         
. Now for any given x 1 > x 2 > ... > x k > A satisfying ||x|| ≤ 3 √ k log n, and any non-empty subset S ⊆ {k + 1, k + 2, ..., n}, we can divide the sum k l=1 x l |r i,l | into O(log(2k)) pieces depending on the size of x l (on dyadic ranges), and apply Correlation Estimate 1 (similarly as in the proof of Proposition 5.1) to deduce that

i∈S k l=1 x l |r i,l | log(2k)||x|| #S log 2 (2k#S) log q (#S)k log n log 3 (2k#S) log q . But if S := {k + 1 ≤ i ≤ n : k l=1 x l |r i,l | ≥ x k log q } then the left hand side must also be ≥ #S x k log q #S 1
log q , so we deduce that #S k(log n) log 6 2k log n k(log n)(log log q) 6 . Substituting back this size estimate for S implies that

n i=k+1, k l=1 x l |r i,l |≥ x k log q k l=1 x l |r i,l | k(log n)(log log q) 6 log q .
Collecting the above estimates shows that

n i=k+1 Φ (w i ) = Φ ((1 + O(1/ log q))x k ) n-k exp O e -A 2 2 1+O √ k/ log q k(log n)(log log q) 6 log q ,
and clearly we have the same estimate for n i=k+1 Φ ((1 + O(1/ log q))w i ), which appears in the error term of Lemma 7.2.

At this point we choose A such that (7.5) e 0.51A 2 = n k log n .

Note that since we assume that 2 ≤ k ≤ cn/ log n, this choice of A will satisfy 1 ≤ A ≤ 2 √ log n provided c is fixed small enough. Notice also that if n ≥ log 2 q, then k log n log q ≤ √ n and so A √ log n. Substituting our choice of A back into (7.1) yields

(7.6) P max k+1≤i≤n Z i ≤ A exp -Θ e 0.01A 2 +O(A) A k log n + n -2k n -2k ,
provided c was chosen small so A is large enough. With this choice of A we also have

e -A 2 1+O √ k/ log q n(log n) 4 log q = e -A 2 0.49+O √ k/ log q k(log n) 5 log q k(log k) 4 log n log q ,
and similarly (distinguishing cases according as k ≥ √ n ≥ log 0.05 q or not) that e

-A 2 2 1+O √ k/ log q k(log n)(log log q) 6 log q k(log n)(log k) 6 log q 1.
Substituting into Lemma 7.2, and using our previous computations of n i=k+1 Φ (w i ) and our assumption that k (log q)/(log log q) 10 , yields that (7.7)

P( max k+1≤i≤n Z i ≤ x k |Z 1 = x 1 , ..., Z k = x k ) = Φ (1+O( 1 log q ))x k n-k 1 + O k log n log 6 k log q +O(n -2k ).
Now, in view of the estimates (7.3) and (7.7), the main term on the right hand side of (7.2) equals

x 1 >•••>x k >A, ||x||≤3 √ k log n 1 (2π) k/2 e -||x|| 2 /2 Φ ((1 + O(1/ log q))x k ) n-k dx 1 ...dx k = x 1 >•••>x k >A 1 (2π) k/2 e -||x|| 2 /2 Φ ((1 + O(1/ log q))x k ) n-k dx 1 ...dx k + O(n -2k ).
Thus Theorem 1.6 will certainly follow if we show that (7.8)

x 1 >•••>x k >A 1 (2π) k/2 e -||x|| 2 /2 Φ ((1 + O(1/ log q))x k ) n-k dx 1 ...dx k = 1 + O k log n log q (n -k)! n! .
We shall only prove an upper bound, since an exactly similar argument would give a matching lower bound. Indeed, for a certain absolute constant C > 0 the integral is

≤ x 1 >•••>x k >A 1 (2π) k/2 e -||x|| 2 /2 Φ ((1 + C/ log q)x k ) n-k dx 1 • • • dx k = x k >A e -x 2 k /2 √ 2π Φ ((1 + C/ log q)x k ) n-k 1 (k -1)! x>x k e -x 2 /2 √ 2π dx k-1 dx k ,
by symmetry of the integration variables x 1 , . . . , x k-1 . Making a substitution shows this is

= 1 + O 1 log q x k >(1+ C log q )A e -(1+O(1/ log q))x 2 k /2 √ 2π Φ (x k ) n-k × 1 (k -1)! x>(1+C/ log q) -1 x k e -x 2 /2 √ 2π dx k-1 dx k = 1 + O 1 log q x k >(1+ C log q )A e -x 2 k /2 √ 2π Φ (x k ) n-k • e O(kx 2 k / log q) (k -1)! x>x k e -x 2 /2 √ 2π dx k-1 dx k ,
and here the term e O(kx 2 k / log q) is e O(k log n/ log q) = 1 + O( k log n log q ) provided x k ≤ 3 √ log n, say. Moreover (and as seen before), the contribution to the integral from the complementary range

x k > 3 √ log n is n -2k , since in this case we have ||x|| ≥ 3 √ k log n. Hence, our integral equals 1 + O k log n log q x k >(1+ C log q )A e -x 2 k /2 √ 2π Φ (x k ) n-k • 1 (k -1)! x>x k e -x 2 /2 √ 2π dx k-1 dx k + O(n -2k ) = 1 + O k log n log q x 1 >•••>x k >(1+ C log q )A 1 (2π) k/2 e -||x|| 2 /2 Φ (x k ) n-k dx 1 • • • dx k + O(n -2k ) = 1 + O k log n log q • P Z1 > Z2 > ... > Zk > max k+1≤i≤n
Zi , and Zk > (1 +

C log q )A + O(n -2k )
where the Zi are independent standard normal random variables. Furthermore, the same argument leading to (7.6) shows that

P max k+1≤i≤n Zi < (1 + C log q )A n -2k .
Finally, the asymptotic (7.8) follows from combining the above estimates, and using that the probability P( Z1 > Z2 > ... > Zk > max k+1≤i≤n Zi ) equals (n -k)!/n! by symmetry of the random variables Z1 , Z2 , . . . , Zn .

8. Irregularities in the densities: Proof of Theorem 1.7

As in the previous section, given distinct reduced residues a 1 , . . . , a n mod q we let Z = (Z j ) 1≤j≤n be a multivariate normal random vector whose components have mean zero, variance one, and correlations r i,j = EZ i Z j := Bq(a i ,a j ) Var(q) . Also, we let 2 ≤ k ≤ n be a fixed positive integer and let f (x 1 , . . . , x k ) denote the density function of Z 1 , . . . , Z k . We denote by C = (r i,j ) 1≤i,j≤k the covariance matrix of Z 1 , . . . , Z k (which is certainly invertible provided q is large enough in terms of k), and let r i,j denote the entries of the inverse matrix C -1 .

The key ingredient in the proof of Theorem 1.7 is the following result.

Lemma 8.1. Let k ≥ 2 be fixed, and let q be large enough in terms of k. There exist distinct reduced residues a 1 , . . . , a k modulo q such that f (x 1 , x 2 , . . . , x k ) = 1 + O k 1 (log q) 2 1 (2π) k/2 exp -||x|| 2 2 -x 1 x 2 log 2 + o(1) log q + O k ||x|| 2 (log q) 2 ,

where the o(1) term tends to zero as q → ∞.

Proof. Let p 1 < p 2 be the smallest prime numbers such that (p 1 p 2 , q) = 1. Then one has p 1 < p 2 ≤ 2 log q in view of the fact that p≤z p = e z(1+o(1)) , which follows from the prime number theorem. Mimicking a construction used in Theorem 2 of Lamzouri [START_REF] Lamzouri | Prime number races with three or more competitors[END_REF], we let a 1 = 1, a 2 = -1 and a j = (p 1 p 2 ) j for 3 ≤ j ≤ k. (2 log q) 2k+1 ϕ(q) , for all i = j such that {i, j} = {1, 2}. Now, by (5.4) we have

f (x 1 , . . . , x k ) = 1 + O k 1 (log q) 2 1 (2π) k/2 exp - 1 2 x T C -1 x .
Recall that r i,i = 1 + O k (1/(log q) 2 ) by (5.3). Furthermore, by (5.3) and (8.2) we have r i,j k 1 (log q) 2 , for all i = j such that {i, j} = {1, 2}. This implies (8.3)

f (x 1 , . . . , x k ) = 1 + O k 1 (log q) 2 1 (2π) k/2 exp - ||x|| 2 2 -x 1 x 2 r 2,1 + r 1,2 2 + O k ||x|| 2 (log q) 2 .
Now, let A be the matrix obtained from C by removing the first row and the second column. Then arguing as in the proof of Lemma 3.3, we obtain

r 2,1 = - det(A) det(C) = -1 + O k 1 (log q) 2 det(A) = -1 + O k 1 (log q) 2 r 2,1 + O k (2 log q) 2k+1 ϕ(q) .
Thus by (8.1) we obtain r 2,1 = log 2+o (1) log q

, and a similar estimate holds for r 1,2 . Inserting these estimates in (8.3) completes the proof.

Proof of Theorem 1.7. By the same argument that was used in the Introduction to deduce Theorem 1.3 from Theorem 1.7, it will suffice to prove Theorem 1.7 in the case k = 2, since this implies the result for larger k. (Using Lemma 8.1 one could in fact prove the result directly for any fixed k, but this would be more complicated and require an unwanted additional assumption of the shape n < ϕ(q) c/k at the end.)

Let a 1 = 1 and a 2 = -1 be as in Lemma 8.1, and let a 3 , . . . , a n be distinct reduced residues modulo q that are different from a 1 , a 2 . As in the proof of Theorem 1.6, Normal Approximation Result 1 implies that δ 2 (q; a 1 , . . . , a n ) -P(Z 1 > Z 2 > max 3≤i≤n Z i ) n 3 ϕ(q) 1/8 . Next, we have

P(Z 1 > Z 2 > max 3≤i≤n Z i ) = P(Z 1 > Z 2 > max 3≤i≤n Z i ,
Z i < x 2 Z 1 = x 1 , Z 2 = x 2 dx 1 dx 2 + O n -4 .
Next, it follows from Lemma 7.2 that for all x = (x 1 , x 2 ) such that x 1 > x 2 > √ 1.99 log n and ||x|| < 3 for some positive constant c > 0, provided q is large enough.

Combining the above estimates, and using our assumption that n ≥ ϕ(q) , we deduce that the main term in (8.5) for some positive constant c . Furthermore, using an exactly similar argument as in the proof of (7.8), together with (8.4), we derive

x 1 >x 2 > √ 1.99 log n ||x||<3 √ 2 log n 1 2π e -||x|| 2 /2 Φ (1 + O(1/ log 2 q))x 2 n-2 dx 1 dx 2 = 1 + O log n log 2 q (n -2)! n! = 1 + O 1 log q (n -2)! n! .
Finally, the total contribution of the various error terms (notably the one from Normal Approximation Result 1 and the one from (8.6)) is n 3 ϕ(q) 1/8 + n -4 + 1 n 0.9 log q (n -2)! n! .

Recalling our assumption that ϕ(q) ≤ n < ϕ(q) 1/41 , we see the error is negligible compared with (n-2)! n! , which completes the proof.

Appendix A. Sketch proof of Lemma 4.1

In this appendix we very briefly indicate how to deduce Lemma 4.1 from Theorem 2.1 of Reinert and Röllin [START_REF] Reinert | Multivariate Normal Approximation with Stein's Method of Exchangeable Pairs under a General Linearity Condition[END_REF].

Indeed, the exchangeable pair construction and calculations used to deduce Central Limit Theorem 1, in an appendix of the preprint [START_REF] Harper | A note on the maximum of the Riemann zeta function, and log-correlated random variables[END_REF], transfer directly to this situation and imply that which is acceptable for Lemma 4.1. We also note that

E|V i | 3 ≤ K 3 m 3/2 + E|V i | 3 1 |V i |>K/ √ m ≤ K 3 m 3/2 + √ m K E|V i | 4 ≤ 2 K 3 m 3/2 ,
and therefore the second term above is

1 0

 1 I θ (t)e -2πitk dt and Îφ (k) (for k ∈ Z) denote the Fourier transforms of I θ , I φ . It is a standard fact that one can construct such functions I, as a sum of Beurling-Selberg type smooth functions that approximate 1 ||t-θr||≤1/x and 1 ||t-(-φs)||≤1/x , and each have integral at most 1000/x and Fourier transform supported in [-x, x] (see e.g. Chapter 1.2 of Montgomery's book

  from which the first bound claimed in Normal Comparison Result 2 follows. The second bound follows on taking A = (2 -δ) log n and B = δ (log n)/50 in (4.1) and (4.2), and noting then that

1 2 a- 1 1 2 b- 1

 1111 log q }, and write k s=1 = b≤2 log k s∈T b , where T b := {1 ≤ s ≤ k : 1 2 b log q < |r j,s | ≤ log q } (with suitable adjustments to the definitions of S 1 , S 2 log k , T 1 , T 2 log k to ensure that all indices l, s are included). Then Lemma 7.1 implies that #S a 2 2a a 4 and #T b 2 2b b 4 , and using Correlation Estimate 1 to bound all the sums of |r l,s | over l ∈ S a and s ∈ T b , we obtain that k l=1 k s=1,s =l |r i,l ||r j,s ||r l,s | log 2 (2k) log 4 (2k) log 2 q

Z i ≤ x 2 |Z 1 = x 1 , Z 2 = x 2 Φ (w i ) = n i=3 Φ ( 1 +

 21122i=31 1 + O(1/ log q))w i ) + n -4 ,wherew i = (1 + O(1/ log 2 q))x 2 + O(||x|| 2 s=1 |r i,s |).Then, similarly to (7.4) one getsn i=3 O(1/ log 2 q))x 2 1 + O ||x|| • e -1/2+O( 1 and the fact that x 2 > √ 1.99 log n. Moreover, in the same range for the x i we deduce from Lemma 8.1 thatf (x 1 , x 2 ) = 1 + O log n (log q) 2

1 ( 2 -x 1 x 2 log 2 +

 122 2π) 2/2 exp -||x|| 2 o(1) log q ≤ 1 -c log n log q 1 2π e -||x|| 2 /2

E|V i | 3 a∈A |c i (a)| 3 .

 33 a)| 2 |c i (b)| 2 E|V i | 4 + |h| 3 m i=1In Lemma 4.1 we assume the uniform fourth moment bound E|V i | 4 ≤ K 4 /m 2 , and so the first term is|h| 2 K 2 m a,b∈A m i=1 |c i (a)| 2 |c i (b)| 2 ,

|h| 3 K 3 m 3 3 ,

 33 as required for Lemma 4.1.

  be such that k is sufficiently small, and suppose further that

	k	k	k
		|r i,l ||r j,s | |r l,s | +	|r l,t ||r s,t | + 2	|r t,u |	≤ 2
	l=1	s=1,s =l	t=1,t =l,s	1≤t,u≤k,
				t =u

  |S i | log 2 (2|S i |))/ log q 2 i i 2 / log q.Finally, by the Cauchy-Schwarz inequality we have 1≤ =s≤n |x x s | ≤ n||x|| 2 , and hence the contribution of the third term in the right hand side of (5.6) is n 2 (log n) 2 ||x|| 2 /(log q) 3 . Collecting the above estimates completes the proof.

	Similarly we have
													2			2
	1≤ =s≤n	|x x s |	1≤j≤n	|r ,j ||r s,j | ≤	1≤j≤n	   1≤ ≤n,	|x ||r ,j |   	1≤j≤n	   1≤i≤J	||x|| 2 i	∈S i ,	|r ,j |   
			j = ,s					=j			=j
													n(log n) 6 (log q) 2 ||x|| 2 ,
	since (5.1) implies that	∈S i ,	|r ,j |	(
							=j
													Using (5.1) we deduce that
		1≤ =s≤n	|x x s r ,s | =	1≤i,j≤J ∈S i ,s∈S j	|x x s r ,s |	||x|| 2	1≤i,j≤J	1 2 i+j	∈S i ,s∈S j	|r ,s |
									=s				=s
													(log n) 4 log q	||x|| 2 .

  l,t |, one can similarly show that

	k t=1,t =l,s	|r l,t ||r s,t |	log(2k)	log 2 (2k) log q	log 2 (2k) log q

  and Z 2 > 1.99 log n) + O(P( max3≤i≤n Z i ≤ 1.99 log n)), ≤ 1.99 log n) e -n c 1 + n -c 2 log q n -4 ,for some positive constants c 1 , c 2 . Moreover, similarly to (7.2) we derive

	and using Normal Comparison Result 2 we obtain
	(8.4)	P( max
	=	x 1 >x 2 > √ ||x||<3 √ 1.99 log n 2 log n

3≤i≤n

Z i (8.5)

P(Z 1 > Z 2 > max 3≤i≤n Z i , and Z 2 > 1.99 log n) f (x 1 , x 2 ) • P max 3≤i≤n

  equals -||x|| 2 /2 Φ (1 + O(1/ log 2 q))x 2 n-2 dx 1 dx 2 ,

				n
	x 1 >x 2 > √ ||x||<3 √ 1.99 log n 2 log n	f (x 1 , x 2 ) •	i=3	Φ (w i ) dx 1 dx 2
	≤ (1 -c )	x 1 >x 2 > √ ||x||<3 √ 1.99 log n 2 log n	1 2π	e

Acknowledgments

We would like to thank Daniel Fiorilli for a helpful clarification of the discussion of one of our results, and the referee for their comments and corrections.