Wolfram Demonstrations Project

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

The graph of

is an irregular step function that jumps by 1 for every

such that

is prime.

This Demonstration illustrates the remarkable fact that we can replicate the jumps of this step function by using a sum that involves zeros of Dirichlet

-functions. This means that those zeros somehow carry information about which numbers in the progression are prime.

Contributed by: Robert Baillie

Slider Zoom

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

. 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:

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.