A Formula for Primes in Arithmetic Progressions

start x axis at (from 0 to 400)

length of x axis (from 10 to 200)

pairs of zeros (from 0 to 100)

always show estimate using no L zeros

display

q,a

(x) values in a tooltip

primes in the progression

3n + 1

3n + 2

4n + 1

4n + 3

10n + 1

10n + 3

10n + 7

10n + 9

Let

and

be integers with

q>0

. If

and

are relatively prime, then the arithmetic progression

qn+a

where

n=0,1,2,3,…

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

q,a

(x)

The graph of

q,a

(x)

is an irregular step function that jumps by 1 for every

such that

x=qn+a

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.

Details

Snapshot 1: primes of the form

3n+1

; the graphs of the step function

3,1

(x)

and the formula using no

zeros

Snapshot 2: the graphs of

3,1

(x)

and the formula using 50 pairs of

zeros

Snapshot 3: primes of the form

10n+1

; the graphs of

10,1

(x)

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

q>0

, and with

and

relatively prime. Dirichlet's theorem (see [3]) says that the arithmetic progression

qn+a

is prime for infinitely many values of

. For example, when

q=10

and

a=1

, the progression

10n+1

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

π(x)

. Likewise, the number of primes in the progression

qn+a

that are less than or equal to

is usually denoted by

q,a

(x)

. We will also use Euler's phi (or "totient") function,

ϕ(q)

, 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

q,a

(x)

(1)

q,a

(x)=

π(x)

ϕ(q)

+e(x,q,a)

ϕ(q)log(x)

where

(2)

e(x,q,a)=-c(q,a)-

∑

χ≠

χ(a)

e(x,χ)

(3)

e(x,χ)=

∑

k=1



1/2+

and

(4)

c(q,a)=-1+numberofsquarerootsthatahas,(modq)

In equation (1), the largest term is

π(x)/ϕ(q)

. 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

c(q,a)=-1

. Otherwise,

must have at least two square roots mod

; this makes

c(q,a)≥1

When equation (1) is graphed, we must account for the fact that, for example, neither of the two progressions mod 3 (

3n+1

and

3n+2

) 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

10n+1

10n+3

10n+7

, and

10n+9

, we subtract 1/4, 0, 3/4, and 1, respectively.

Discussion:

Each of the

ϕ(q)

values of

that have no factor in common with

gives rise to an arithmetic progression

qn+a

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

π(x)

primes less than or equal to

, so each of the

ϕ(q)

progressions has, as

approaches infinity, about

π(x)/ϕ(q)

primes. This explains the first term on the right side of equation (1).

For example, for

= 10, each of the

ϕ(10)

= 4 progressions

10n+1

10n+3

10n+7

, and

10n+9

has about

π(x)/4

primes, for large

Notice that equation (1) uses

π(x)

. It might seem like cheating to call something a "formula for primes" when that formula contains

π(x)

. However,

π(x)

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

ϕ(q)

progressions

qn+a

will have the same proportion of primes (namely,

1/ϕ(q)

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

q=3

. The progressions

3n+1

and

3n+2

each contain infinitely many primes. The first two primes in these progressions are 2 and 5, both of which belong to the progression

3n+2

. The next prime is 7, in the progression

3n+1

. So, these progressions start out with

3n+2

having more primes than

3n+1

. Using the

q,a

(x)

notation, it has been shown that, at least up to

x=10

3,2

(x)>

3,1

(x)

. But here is the amazing part:

3,2

(x)>

3,1

(x)

for every

less than 608,981,813,029! At

= 608,981,813,029,

3,1

(x)

finally exceeds

3,2

(x)

! In fact,

3,1

(608981813029)=11669295396

and

3,2

(608981813029)=11669295395

With the two progressions mod 4, namely,

4n+1

and

4n+3

, something similar happens:

4,3

(x)>

4,1

(x)

for every

< 26,861. Then, at

= 26,861,

4,1

(x)

finally becomes greater than

4,3

(x)

For

q=10

: 3 is prime, so

10n+3

starts out in the lead over the other three progressions

10n+1

10n+7

, and

10n+9

10,7

(x)

first takes the lead over the other three progressions at

x=157

10,9

(x)

first takes the lead at

= 72,269. Finally,

10,1

(x)

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,

a=2

has no square roots mod 3), then

c(q,a)=-1

. If

has, say, two square roots mod

(for example,

a=1

has two square roots mod 3), then

c(q,a)=1

. But if

c(q,a)=-1

, then, by equation (2),

e(x,q,a)

is larger (by 2) than it would be if

c(q,a)=1

, all other things being equal. This, in turn, makes

q,a

(x)

larger when

c(q,a)=-1

than it would be if

c(q,a)=1

What this means is that, for values of

that have no square roots mod

, the arithmetic progression

qn+a

tends to have a few more primes up to a given

than other progressions

qn+b

where

does have square roots mod

. (Of course,

qn+a

will not have enough primes to affect the proportion, which, as

approaches infinity, is

π(x)

ϕ(q)

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 Character on Wikipedia.

External Links

Dirichlet L-Functions and Their Zeros

Dirichlet L-Functions near the Critical Line

Dirichlet L-Series (Wolfram MathWorld)

How the Zeros of the Zeta Function Predict the Distribution of Primes

Root (Wolfram MathWorld)

Table of Dirichlet Characters

Permanent Citation

Robert Baillie

"A Formula for Primes in Arithmetic Progressions" from the Wolfram Demonstrations Project http://demonstrations.wolfram.com/AFormulaForPrimesInArithmeticProgressions/
Published: March 7, 2011