A Formula for Primes in Arithmetic Progressions

Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
Let and
be integers with
. If
and
are relatively prime, then the arithmetic progression
where
contains an infinite number of primes. The number of such primes that are less than or equal to
is a function of
usually denoted by
.
Contributed by: Robert Baillie (March 2011)
Open content licensed under CC BY-NC-SA
Snapshots
Details
Snapshot 1: primes of the form ; the graphs of the step function
and the formula using no
zeros
Snapshot 2: the graphs of and the formula using 50 pairs of
zeros
Snapshot 3: primes of the form ; the graphs of
and the formula using 50 pairs of
zeros; the step function jumps up at primes 11, 31, 41, 61, 71, …
Let and
be integers with
, and with
and
relatively prime. Dirichlet's theorem (see [3]) says that the arithmetic progression
is prime for infinitely many values of
. For example, when
and
, the progression
has infinitely many primes, the first five of which are 11, 31, 41, 61, and 71.
The standard notation for the number of primes less than or equal to is
. Likewise, the number of primes in the progression
that are less than or equal to
is usually denoted by
. We will also use Euler's phi (or "totient") function,
, which is the number of integers between 1 and
relatively prime to
.
Technical Details:
These equations come from equations (6)–(8) in reference [1]. There is a lot of terminology here. For an introduction to characters and Dirichlet -functions, see reference [3].
You use the slider to specify , the number of pairs of complex zeros of Dirichlet
-functions to include in the sums. This Demonstration then applies the following formulas to compute
:
(1) ,
where
(2) ,
(3) ,
and
(4)
In equation (1), the largest term is . The other term on the right depends on zeros of
-functions.
In equation (2), the asterisk denotes the complex conjugate, and we sum over all characters (mod
) except the "principal" character,
.
In equation (3), for the character (mod
), we sum over
complex zeros of the corresponding Dirichlet
-function. The sum extends over the
zeros having the smallest positive imaginary part, and the
zeros having the least-negative imaginary part. (These pairs of zeros are not necessarily conjugates of each other.)
denotes the imaginary part of the
zero. For speed, this Demonstration uses precomputed zeros of
-functions mod 3, 4, and 10.
In equation (4), if has no square roots mod
(that is,
is a quadratic nonresidue mod
), then
. Otherwise,
must have at least two square roots mod
; this makes
.
When equation (1) is graphed, we must account for the fact that, for example, neither of the two progressions mod 3 ( and
) include the prime 3. We do this by subtracting 1/2 from each value obtained in equation (1). The same adjustment is made for mod 4, whose progressions omit the prime 2. The mod 10 progressions omit two primes (namely, 2 and 5), so for
,
,
, and
, we subtract 1/4, 0, 3/4, and 1, respectively.
Discussion:
Each of the values of
that have no factor in common with
gives rise to an arithmetic progression
that contains infinitely many primes. As
approaches infinity, each of these progressions will have the same proportion of primes less than or equal to
. There are
primes less than or equal to
, so each of the
progressions has, as
approaches infinity, about
primes. This explains the first term on the right side of equation (1).
For example, for = 10, each of the
= 4 progressions
,
,
, and
has about
primes, for large
.
Notice that equation (1) uses . It might seem like cheating to call something a "formula for primes" when that formula contains
. However,
can itself be computed by using a sum of terms that involve zeros of the Riemann zeta function. The Demonstration "How the Zeros of the Zeta Function Predict the Distribution of Primes" shows how to do that.
Prime Number Races:
As approaches infinity, each of the
progressions
will have the same proportion of primes (namely,
). However, this does not mean that the progressions have the same number of primes up to any given
. Perhaps the most dramatic example of this happens with
. The progressions
and
each contain infinitely many primes. The first two primes in these progressions are 2 and 5, both of which belong to the progression
. The next prime is 7, in the progression
. So, these progressions start out with
having more primes than
. Using the
notation, it has been shown that, at least up to
,
. But here is the amazing part:
for every
less than 608,981,813,029! At
= 608,981,813,029,
finally exceeds
! In fact,
and
.
With the two progressions mod 4, namely, and
, something similar happens:
for every
< 26,861. Then, at
= 26,861,
finally becomes greater than
.
For : 3 is prime, so
starts out in the lead over the other three progressions
,
, and
.
first takes the lead over the other three progressions at
.
first takes the lead at
= 72,269. Finally,
first takes the lead over the other three progressions at
= 45,845,791.
Because each progression mod has the same proportion of primes, one might expect that the lead would have switched back and forth much more often, as if one were flipping a coin and tallying heads versus tails. It is surprising that one progression so consistently maintains the lead over the others.
For a given , why do some progressions have more primes than others? The key is equation (4) above. If
has no square roots mod
(for example,
has no square roots mod 3), then
. If
has, say, two square roots mod
(for example,
has two square roots mod 3), then
. But if
, then, by equation (2),
is larger (by 2) than it would be if
, all other things being equal. This, in turn, makes
larger when
than it would be if
.
What this means is that, for values of that have no square roots mod
, the arithmetic progression
tends to have a few more primes up to a given
than other progressions
where
does have square roots mod
. (Of course,
will not have enough primes to affect the proportion, which, as
approaches infinity, is
for every progression mod
.) Finally, it is worth noting that in 1914, Littlewood proved (see reference [2]) that, for both mod 3 and mod 4, the lead switches back and forth infinitely many times.
There are many articles about these "prime number races"; for example, [2] is a readable introduction to the subject.
References:
[1] G. Martin, "Asymmetries in the Shanks-Renyi Prime Number Race," arXiv, 2000.
[2] A. Granville and G. Martin, "Prime Number Races," American Mathematical Monthly, 113(1), 2006 pp. 1–33.
[3] W. J. LeVeque, Topics in Number Theory, vol. 2, Reading, MA: Addison–Wesley, 1961 pp. 81–124.
[4] Dirichlet Characteron Wikipedia.
Permanent Citation