NTIC Types of Primes

Section 22.3 Types of Primes

There are many types of primes we have encountered up to this point. For instance:

Germain (Subsection 11.6.4)
Mersenne (Subsection 12.1.3)
repunit (Exercise 6.6.1)

Notice that for many of these types, we don't know if there are finitely many or not! Are there any conjectures for how often certain types of primes might appear?

🔗

Subsection 22.3.1 Twin primes

🔗

Consider primes in an arithmetic progression

a x + b .

Can one say anything about the constants involved in these progressions? Since

b

is pretty arbitrary, we would focus on

a .

Here are some natural questions along these lines.

🔗

Question 22.3.1.

Consider the following for small values of $a .$

Find some primes that look like $2 x + b$ for some $b$ and several consecutive $x .$ How many $x$ in a row can you do?
How about for $3 x + b ?$
What about $4 x + b ?$
Are the primes you get in these cases ever consecutive?

🔗

Hopefully it's pretty clear that you can't do every possible combination of

b

and

a,

nor can every such progression go on indefinitely! Why?

🔗

Thinking about this and the Sieve of Eratosthenes led the French mathematician Alphonse de Polignac to the following.

🔗

Conjecture 22.3.2. Polignac's Conjecture.

Every even number is the difference between consecutive primes in infinitely many ways.

🔗

We have no proof of this. In fact, even the most basic case of Polignac's conjecture is one of the most celebrated open questions in number theory – celebrated enough that well-known comedian Stephen Colbert interviewed Fields medalist Tao about it.

🔗

Conjecture 22.3.3. Twin prime conjecture.

There are infinitely many consecutive odd prime numbers.

🔗

Definition 22.3.4.

Pairs of primes $p$ and $q$ such that $p + 2 = q$ are called twin primes.

🔗

There are lots of twin primes. The following cell computes twin prime pairs, numbered by which twin prime pair it is. The pair 17 and 19 is the fourth pair, for example.

xxxxxxxxxx
 
def twin_primes_upto(n):
    v = prime_range(n+1)
    L = []
    counter = 0
    for i in range(len(v)-1):
        if v[i+1]-v[i]==2:
            counter += 1
            L.append((v[i],v[i+1],counter))
    return L
​
twin_primes_upto(100)

🔗

We can use similar searching to try to see whether there are enough that there are infinitely many such pairs. Here are two sample graphics.

🔗
Figure 22.3.5. Estimating number of twin primes through $n = 10000$ and $n = 1000000$

🔗

You can see in the preceding graphic that it's certainly possible to approximate the twin prime counting function in a similar way to how we approximated the prime counting function

π .

There is a mysterious constant

C_{2}

I've used; it will be explained below.

🔗

Subsection 22.3.2 Heuristics for twin primes

🔗

To explain how to get to twin primes, there is a nice little rule of thumb; see e.g. [E.4.5] for what follows. Even though we definitely do not have a proof, we can still give you a good idea of how these ideas come about.

🔗

First, one might want to estimate how many primes there are up to a certain point to start. The problem is we should use a different idea than just looking at tables! What can we say that is a little smarter?

About half the numbers less than $n$ are not divisible by 2.
About 2/3 the numbers less than $n$ are not divisible by 3.
About 4/5 the numbers less than $n$ are not divisible by 5.
Etc. for each prime less than $\sqrt{n} \dots$

🔗

If we take this thinking to its logical extreme, you might even expect that

\prod_{p < \sqrt{x}} (1 - \frac{1}{p})

🔗

is a good approximation of the probability that a given number

x

is prime. Unfortunately, it isn't. In fact, this product turns out to be asymptotic to

2 e^{- γ} / \log (x)

(recall that

γ

from Definition 20.3.10).

🔗

Still, this kind of thinking is still helpful, and might help us make ideas for how many twin primes there are – especially if we keep in mind this isn't really a probability. After all, if

p > 2

is prime, then with one hundred percent probability the next number is not prime! And for

p

and

p + 2

to be both prime, they must also both be odd; so if

p

is odd, then

p + 2

is much more likely than a random number to be prime.

🔗

So we do the following analysis instead. (See Exercises 22.4.11 and 22.4.12.)

Although one would expect for 1/4 of all pairs separated by two to both be odd, $n + 2$ has the same parity as $n$ so we should expect 1/2 the pairs to both be odd.
The chances that $n$ and $n + 2$ are both not divisible by three is $1 / 3 .$
The chances that $n$ and $n + 2$ are both not divisible by five is $3 / 5 .$
And so forth.

🔗

So, having gotten a little more sophisticated, we might expect that

\frac{1}{2} \prod_{p < \sqrt{x}, p > 2} (1 - \frac{2}{p})

🔗

is a decent approximation of the probability that a given pair of consecutive odd numbers are both prime.

🔗

This doesn't look so recognizable yet, but we can do some algebra to turn this into something that looks better and has logarithms, just like in the prime number theorem. If we substitute

(1 - \frac{2}{p}) = (1 - \frac{1}{(p - 1)^{2}}) {(1 - \frac{1}{p})}^{2}

🔗

then the approximation of the number of twin primes less than

x

looks more like this:

\frac{1}{2} \prod_{p < \sqrt{x}, p > 2} (1 - \frac{1}{(p - 1)^{2}}) \prod_{p prime} {(1 - \frac{1}{p})}^{2}

🔗

Finally, if we now use the earlier suggestion about the right-hand side being more or less the square of the number of primes, we come up with a reasonable suggestion that looks more familiar.

\frac{1}{2} \prod_{p < \sqrt{x}, p > 2} (1 - \frac{1}{(p - 1)^{2}}) {(\frac{x}{\log (x)})}^{2}

🔗

Remark 22.3.6.

The constant part of this formula is finite, and known as the twin prime constant:

C_{2} = 2 \prod_{p > 2} (1 - {\frac{1}{p - 1}}^{2}) .

The graphs in Subsection 22.3.1 use this constant (which is built-in in Sage) as well as a logarithmic integral version of the preceding analysis.

There is some inconsistency in the literature about whether the 2 in front of the formula for $C_{2}$ is part of the twin prime constant or not.

🔗

This also leads to a conjecture of Hardy and Littlewood.

🔗

Conjecture 22.3.7.

The number of ways to write an even number $2 k$ as a sum of primes is also asymptotic to $\frac{1}{2} \prod_{p < \sqrt{x}, p > 2} (1 - \frac{1}{(p - 1)^{2}}) {(\frac{x}{\log (x)})}^{2} .$

🔗

This would provide a very overwhelming proof of the following old suggestion, going back to correspondence between Euler and Prussian/Russian mathematician Christian Goldbach.

🔗

Conjecture 22.3.8. Goldbach Conjecture.

Any even number can be written in at least one way as a sum of two primes.

🔗

In fact, there are two such conjectures, with the other one suggesting that any positive integer may be written as a sum of three primes. There is a proof claimed for the latter ‘weak’ conjecture, but it has not appeared in a peer-reviewed journal yet.

🔗

Historical remark 22.3.9. The Pentium bug.

Returning to the twin prime constant, computing it (as in the Sage cell below) led to a very interesting real-life application.

xxxxxxxxxx
 
2*twinprime.n()

Computing this constant to arbitrary precision led to the discovery of the infamous Pentium chip bug, where some floating-point calculations would be incorrect in high decimal places. This is a quite surprising ‘application’ of number theory! (It turns out manufacturers do use number-theoretic computations to stress-test their products. See also Historical remark 12.1.8.)

🔗

Historical remark 22.3.10. Twin prime status.

It is still unknown whether there are infinitely many twin prime pairs. In a 2013 result that shocked the mathematics world, (then) unknown mathematician Yitang Zhang proved that there exists some $N$ less than seventy million such that there are infinitely many pairs of primes separated by exactly $N .$ This was a huge improvement over previous results, and further work of an unusually collaborative nature have now reduced this bound to $N \leq 246,$ but the effort has not continued progress. A related result about polynomials was proved in 2019, but this doesn't seem to have led closer to a final resolution, either.

🔗

As we finish this subsection, we must mention another constant affiliated with twin primes. Although there may really be infinitely many pairs, the sum of their reciprocals

\sum_{p, p + 2 both prime} \frac{1}{p} + \frac{1}{p + 2}

🔗

is still a finite constant. At the very least means twin primes must be pretty rare. This (possibly infinite) sum is called Brun's constant.

🔗

Sage note 22.3.11. Sage can change.

Originally, this constant was included in Sage. However, as nearly every digit of the constant is conjectural, it was removed as a built-in.

xxxxxxxxxx
 
brun.n(digits=5)

Because Sage is open source, you can follow discussions about decisions and additions to Sage functionality on the Sage developer Trac or sometimes on the Github organization.

🔗

Subsection 22.3.3 Other types of primes

🔗

In the quest toward Polignac's Conjecture, researchers have dubbed primes (not necessarily consecutive) with spacing

N = 4

cousin primes and those

N = 6

apart sexy primes. In another result of similar vintage to Zhang's (and also collaborative like its refinement), we know (conditional upon the so-called “generalized Elliott-Halberstam conjecture”, which is closely related to our investigations in Subsection 22.2.2) that at least one of the classes of twin, cousin, or sexy primes is infinite ². This is a very special case of exploring something called prime constellations; see Exercise 22.4.13.

Go to the video of Tao's interview with Colbert, linked just before Conjecture 22.3.3, again to see Colbert's quite amusing reaction to this fact.

🔗

In addition, there are many other heuristics like the ones above. Here is a sampling of those we don't have space or expertise in this text to dig further into.

As one example, consider the chance that $n$ and $2 n + 1$ are both not divisible by a given prime $p .$ Probabilistically, this is basically the same chance as that $n$ and $n + 2$ are both not divisible by $p,$ so it turns out that Germain primes might also be distributed in the same fashion as twin primes.
Using similar ideas, one can get a heuristic that Mersenne primes are distributed as

$e^{γ} \log (\log (x)) / \log (2) .$

This is known as Wagstaff's conjecture.
Bizarrely, one can use the same idea to get a heuristic for factorial primes. These are primes of the form $n! \pm 1,$ like 5, 7, 23, and 719. It's conjectured that there are $e^{γ} \log (n)$ such primes less than $n .$
These rules of thumb even seem to apply to the so-called primorial primes – primes of the form $p # \pm 1,$ like 3, 5, 7, 29, 31, 211, etc. It's truly weird, yet also cool.

🔗

There is so much to explore! There is never a lack of questions for mathematicians to explore when it comes to prime numbers.