Of course, for this question to make sense, we need to make sure this ‘prime race’ won't suddenly run out of gas. We know there are infinitely many primes, but what about each type of prime?

It turns out that proving the first part of the proposition is nearly as easy as proving the Infinitude of Primes. But the second part seems to requires something equivalent to the idea of a square root of \(-1\) existing modulo some primes but not modulo others (recall Fact 16.1.2).

Now, from what we've seen it looks like the \(4k+3\) ones will always stay ahead. But that's not quite right. Here's one place where they fall behind.

There are other \(n\) for which we have such an ‘inversion’ as well, and it can be fun to look for them. The next such time is over six hundred thousand, for a little while; after that, you have to look at \(n\) over twelve million. Indeed, there is a theorem that there are infinitely many times where this will happen, and that the ‘wrong’ team will get ahead by at least a specified amount.

You may not be surprised to learn that this result is due to Littlewood, who was also one of the first contributors in studying the race between \(\pi\) and \(Li\). That his result is highly nontrivial is seen in the following interact.

Even though we can see the difference surge to become positive a few times, it seems hopeless to ever reach even the extremely slow \(\log(\log(\log(x)))\). But it does.

There are many races we can check out, and mathematicians have. (Indeed, this section is indebted to the excellent expository article [C.6.3], which has a host of recent references.) What is the pattern here, for modulus eight?

It turns out there are several types of theorems/conjectures one can make about such races. The key observation (which we will not explain here) is that the ‘slow’ teams are the residue classes \([a]\) such that \(nk+a\) can be a perfect square (see Exercise 22.4.2). In our cases, only \(4k+1\) and \(8k+1\), respectively, are possible perfect (odd) squares. See also Exercise 22.4.3.

Nonetheless, for any \(a,b\) coprime to each other and to \(n\), \begin{equation*}\lim_{x\to\infty}\frac{\text{Number of }p\equiv a\text{ (mod }n)\text{ less than }x}{\text{Number of }p\equiv b\text{ (mod }n)\text{ less than }x}=1 \end{equation*} so the teams can't get too far away from each other, at least not on a percentage basis. The more specific result that the numerator and denominator are both asymptotic to \(\frac{Li(x)}{\phi(n)}\) is often called the prime number theorem for arithmetic progressions, and it was also proved by Vallée-Poussin. (See the next section as well.)

With such a close connection to Chapter 21, at this point you won't be surprised to learn that, even though some teams are usually ahead, that just like with \(\pi\) and \(Li\), each team does get ahead in the race infinitely often. But if you “count right” (and assume some other technical but important hypotheses), the proportion of the time the ‘wrong’ teams are ahead in the race is very small. (See the [C.6.3] for more details.)