Section22.1Prime Races

One of Chebyshev's more interesting observations was that our familiar categories of primes – the classes \(4k+1\) and \(4k+3\) – don't always seem to have the same size. Try making a table of how many primes of each type there are up to \(n=10\), \(n=20\), and \(n=50\) by hand before moving on.

We can, as always, use computational power to try to see more.

Do you detect the bias Chebyshev did? Do you think it will persist?

Subsection22.1.1Infinitude of types of primes

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?

  • There are infinitely many primes congruent to 3 modulo 4.
  • There are infinitely many primes congruent to 1 modulo 4.
It turns out that proving the first proposition is nearly as easy as proving the infinitude of primes, while the second one seems to requires something equivalent to the idea of a square root of \(-1\) existing modulo some primes but not modulo others.

Subsection22.1.2Back to bias

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

There are other places as well, and it can be fun to look for them. The next such place is over six hundred thousand, for a little while; after that, over twelve million.

Indeed, there is a theorem that there are infinitely many places where this will happen.

That this fact 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 \(\ln(\ln(\ln(x)))\). But it does.

Subsection22.1.3Other prime races

We can check out other races, too. What is the pattern here?

It turns out there are several types of theorems/conjectures one can make about such races. The key is to recognize that the 'slow' ones are the residue classes \([a]\) such that \(4n+a\) can be a perfect square; in our case, only \(4k+1\) and \(8k+1\) are possible perfect (odd) squares.

  • The residue classes with perfect squares do get ahead in the race infinitely often.
  • But if you “count right” (and assume something else technical but important), the proportion of the time they are ahead in the race is very small.
  • Nonetheless, \[\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\; \text{ for any }a,b\text{ coprime to each other and to }n\; ,\] so they can't get too far away from each other.
Note that Littlewood is also responsible for some of the first results in the prime races.