NTIC Prime Races

Section 22.1 Prime Races

One of Chebyshev's more interesting observations was that our familiar categories of primes – the classes

4 k + 1

and

4 k + 3

– don't always seem to have the ‘same size’. Before moving on, try solving the next question by hand.

🔗

Question 22.1.1.

How many primes of each type there are up to $n = 10,$ $n = 20,$ and $n = 50 ?$ Try making a table.

🔗

You can try it by hand, or we can, as always, use computational power below to try to see more. (We saw this computation in a different context way back in Section 7.6.)

xxxxxxxxxx
 
import itertools
​
@interact
def _(n=7):
    L = itertools.zip_longest([p for p in prime_range(n+1) if p%4==1],[p for p in prime_range(n+1) if p%4==3])
    L = [['',l[1]] if l[0] is None else l for l in L]
    T = [[r'$p\equiv 1\text{ (mod }4)$',r'$p\equiv 3\text{ (mod }4)$']]
    pretty_print(html(table(T+L,header_row=True, frame=True)))

xxxxxxxxxx
 
@interact
def _(k=100):
    p1 = 0
    p3 = 0
    for i in prime_range(k):
        if i%4==1:
            p1 += 1
        if i%4==3:
            p3 += 1
    pretty_print(html("Up to $k=%s$, there are"%k))
    pretty_print(html(r"%s primes $p\equiv 1\text{ (mod }4)$ and "%p1))
    pretty_print(html(r"%s primes $p\equiv 3\text{ (mod }4)$."%p3))

🔗

Question 22.1.2.

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

🔗

Subsection 22.1.1 Infinitude 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?

🔗

Fact 22.1.3.

There are infinitely many primes congruent to 3 modulo 4 and there are infinitely many primes congruent to 1 modulo 4.

🔗

Proof.

See the following two Propositions 22.1.4 and 22.1.5.

🔗

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). These proofs are standard; we follow the notation in [E.2.1].

🔗

Proposition 22.1.4. Infinitude of primes 3 (mod 4).

There is no largest prime congruent to 3 modulo 4.

🔗

Proof.

We'll prove this by contradiction. Suppose $p_1,p_2,\ldots,p_k$ is the (finite) set of all primes congruent to 3 modulo 4.

Form the product of all these primes, together with four; then subtract one to let

\begin{equation*} m = 4p_1 p_2\cdots p_k - 1\text{.} \end{equation*}

What are the prime divisors of this number?

Clearly none of the $p_i$ can be a prime divisor, since $m$ is congruent to $-1$ modulo all the $p_i\text{.}$
Since $m$ is not even, it is also not divisible by a power of 2.
If $m$ were a product only of primes congruent to 1 modulo 4, then it would have to be 1 modulo 4 itself (since any product of $1$s is 1).
That is false, so there must be a prime congruent to 3 modulo 4 which divides it, which cannot be on the original list of $p_i\text{.}$

This contradicts our assumption of having the full set of such primes, so that assumption must have been wrong.

🔗

Proposition 22.1.5. Infinitude of primes 1 mod 4.

There is no largest prime congruent to 1 modulo 4.

🔗

Proof.

As usual, suppose there are finitely many primes $p_i$ which are congruent to 1 modulo 4. Let's form the modified product

\begin{equation*} m=(2p_1 p_2\ldots p_k)^2+1\text{.} \end{equation*}

What are its prime divisors?

For the same reasons as in the proof of Proposition 22.1.4, it is clear that $m$ is odd and that it is also not divisible by any of the $p_i\text{.}$ Initially, one might assume one could also modify that argument to show that at least one of the primes $p$ which divides $m$ is not 3 modulo 4.

Unfortunately, as $3^2$ is congruent to 1 modulo 4, this argument fails. However, we can use an indirect argument.

For any prime divisor $p$ of $m$ and for $x=2p_1 p_2\ldots p_k\text{,}$ we have $m=x^2+1\equiv 0\text{ (mod }p)\text{.}$ So $-1$ is a quadratic residue modulo $p\text{,}$ by definition of quadratic residues! Because of Fact 13.3.2, this can only happen if $p\equiv 1$ (mod $4$). (Compare with Theorem 13.5.5, where even powers of primes of the form $4k+3$ were allowed; here, they are completely prohibited.)

Since this $p$ wouldn't be one of the $p_i\text{,}$ its existence contradicts the assumption that we already had all such primes.

🔗

Subsection 22.1.2 Back to bias

🔗

Now that we know we will always have primes of both kinds, let's return to the prime race. From what we've seen previously, it looks like the

4 k + 3

-type primes will always stay ahead. But that's not quite right. The next Sage cell computes one place where they fall behind.

xxxxxxxxxx
 
def prime_race_up_to_n(n):
    p1 = 0
    p3 = 0
    for i in prime_range(n):
        if i%4==1:
            p1 += 1
        if i%4==3:
            p3 += 1
    pretty_print(html(r"Up to $n=%s$, there are:<ul><li>%s primes $p\equiv 1\text{ (mod }4)$</li><li>%s primes $p\equiv 3\text{ (mod }4)$.</li></ul>"%(n,p1,p3)))
​
@interact
def _(n=[26860,26862,26864,26880]):
    prime_race_up_to_n(n)

🔗

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.

🔗

Fact 22.1.6.

No matter how far out you go, there exists an $n$ where the $4 k + 1$ team is ahead at $n$ by

\frac{1}{2} \frac{\sqrt{n}}{\log (n)} \log (\log (\log (n))) .

🔗

You may not be surprised to learn that this result is also due to Littlewood, the early contributor in studying the race between

π

and

L i

back in Fact 21.2.6. That his result is highly nontrivial is seen in the following graphic, which plots the difference between the ‘teams’ up to the first place the

4 k + 1

type is ahead.

Difference in prime teams up through $n=26862$ — 🔗
Figure 22.1.7. Difference in prime teams up through $n = 26862$

🔗

Try the interactive version to see what happens beyond that.

xxxxxxxxxx
 
@interact
def _(n=26862):
    L = []
    p1 = 0
    p3 = 0
    for i in prime_range(n):
        if i%4==1:
            p1 += 1
            L.append([i,p1-p3])
        if i%4==3:
            p3 += 1
            L.append([i,p1-p3])
    P = plot(1/2*sqrt(x)/log(x)*log(log(log(x))), (x,10,n+10))
    P += plot_step_function(L)
    show(P)

🔗

Even though we can see the difference surge to become positive a few times, it seems hopeless for the

4 k + 1

team to ever get ahead by as much as the extremely slowly growing

\log (\log (\log (x))) .

But it does.

🔗

Subsection 22.1.3 Other prime races

🔗

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

🔗
Figure 22.1.8. Difference in prime teams modulo eight

🔗

It might be a little tough to see, so feel free to use the interactive version below if you are online.

xxxxxxxxxx
 
@interact
def _(n=100):
    p1,p3,p5,p7=0,0,0,0
    L1 = []
    L3 = []
    L5 = []
    L7 = []
    for i in prime_range(n):
        if i%8==1:
            p1 += 1
            L1.append([i,p1])
        elif i%8==3:
            p3 += 1
            L3.append([i,p3])
        elif i%8==5:
            p5 += 1
            L5.append([i,p5])
        elif i%8==7:
            p7 += 1
            L7.append([i,p7])
    L1.append([n,p1])
    L3.append([n,p3])
    L5.append([n,p5])
    L7.append([n,p7])
    P = Graphics()
    P += plot_step_function(L1,color='red',legend_label='1 (mod 8)')
    P += plot_step_function(L3,color='green',legend_label='3 (mod 8)')
    P += plot_step_function(L5,color='blue',legend_label='5 (mod 8)')
    P += plot_step_function(L7,color='orange',legend_label='7 (mod 8)')
    show(P,xmin=max(0,n-1000),ymin=max(0,L1[-1][1]-100))

🔗

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

n k + a

can be a perfect square (see Exercise 22.4.2). In the two examples we showed graphically, only

4 k + 1

and

8 k + 1,

respectively, are possible perfect (odd) squares, and they are the ‘slow’ teams. See also Exercise 22.4.3.

🔗

Nonetheless, for any

a, b

coprime to each other and to

n,

lim_{x \to \infty} \frac{Number of p \equiv a (mod n) less than x}{Number of p \equiv b (mod n) less than x} = 1

🔗

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{L i (x)}{ϕ (n)}

is often called the prime number theorem for arithmetic progressions, and it was also proved by Vallée-Poussin. (See also Subsection 22.2.1.)

🔗

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

π

and

L i,

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 article [E.7.3] for more details.)