If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
1 Introduction
``Le plus court chemin entre deux vérités dans le domaine réel passe
par le domaine complexe.'' (Jacques Hadamard)
``The shortest path between two truths in the real domain passes
through the complex domain.'' (Jack Hadamard)
The above quote captures the depth analysis can bring when one is
confronted by number theoretic questions. The oldest and most fundamental
of such questions is the study of prime numbers. The first question
to be answered is: Are there an infinite number of primes?
This can be answered by a number of simple proofs
(several other proofs are given in [7]):

Euclid: Assume there are a finite number of primes
p_{1},...,p_{n}, then
p_{1} p_{2} ··· p_{n}+1 is not divisible by any of the p_{i}'s,
so any of its prime divisors yields a new prime number (Euclid
only considered the case n=3).
 Pólya: The Fermat numbers F_{n}=2^{2}^{n}+1 are pairwise
relatively prime, so the set of their prime divisors must be infinite.
 Erdös: Fix x and consider the primes p_{1},...,p_{n}£ x.
Since every integer is the product of a perfect square and a
squarefree number, one can write every integer m£ x as
m=p_{1}^{e}_{1} ··· p_{n}^{e}_{n} Q^{2},
where e_{i} Î {0,1} and Q^{2}£ x.
There are 2^{n} choices for the e_{i} and (x)^{1/2} choices for Q,
so it follows that n ³ln(x)/2ln(2).
 Euler: One has the formal identity
which in fact
holds for Â(s) > 1. As s® 1, the left hand side
of (1) tends
to ¥ since the harmonic series diverges, so there must
be an infinite number of factors on the right.
This proof can be modified by noting that
z(2) = p^{2}/6, where z(s) = å 1/n^{s}.
If there were only a finite number of primes,
then (1)
would imply
that p^{2} is rational, proved false by Legendre in 1797,
see also [6].
A stronger version of this is due to Mertens: The finite version
of (1) gives
and taking logs will give
and so there are an infinite number of primes.
Which of these is the ``best'' proof? One argument would say that it
is the one which allows the best generalisation. For example,
Euclid's proof easily shows that there are an infinite number of
primes of the form 4k+3 (consider 4 p_{1}··· p_{n} 3),
but seems to fall flat when trying to prove
that the same holds for primes of the form 4k+1 (one has to consider
4 (p_{1}··· p_{n})^{2}+1). In general, one wants to
demonstrate Dirichlet's assertion (that he proved in 1837,
in [3]) ``there are an infinite number of primes of the form
ak+b, where a and b are relatively prime.'' It turns out that
the proof of this deep fact uses a generalisation of Euler's
method, i.e., equation (2):


=¥ Û there are an
infinite number of primes in ak+q.

2 Le théorème de Dirichlet
Soit c un caractère multiplicatif
modulo q, c'estàdire une fonction à valeurs complexes
c(n) vérifiant
c(mn)=c(m)c(n), c(1)=1
et c(0)=0 (ce qui implique que
si c(n)¹ 0,
alors c'est une racine de l'unité et a donc norme 1). Un exemple est
le symbole de Legendre (ou de Jacobi si q n'est pas premier)
c(n):= 
æ ç ç è 

ö ÷ ÷ ø 
= 
ì í î 
0 
if q  n, 
1 
if x^{2} º nmod q for some
x, 
1 
otherwise. 


En fait, pour tout q puissance d'un nombre premier impair, il y
a exactement f(q)
caractères multiplicatifs modulo q, tous donnés par c(n):=e^{2 ik p n(n) /f(q)} for 0£ k £ f(q)1
and where n(n) is such that nº g^{n(n)}mod q for any generator
of the group of invertible elements of Z/qZ. When q is a power of 2, the definition is little more cumbersome (linked to
the ``factorisation'' n º (1)^{n}_{1}^{(n)} 5^{n}_{2}^{(n)} mod q),
and for general q, it is the product of characters of the factors of q.
The importance of characters is seen by the following
orthogonality relation:





c(n) = 
ì í î 
1 
whenever nº a mod q, 
0 
otherwise, 


(3) 
where the sum is over all the characters (the two real ones and the
other complex characters).
The orthogonality relation allows one to pick out an arithmetic progression.
For his proof, Dirichlet introduced what are nowadays called Dirichlet
Lfunctions, defined by
Taking logarithm leads to ln L(s,c)=å_{p}
ln(1c(p)p^{s}), thus one has



ln L(s,c)= 





ln(1c(p)p^{s}) 
and a simple application of
relation (3) gives




ln 
L(s,c)= 




= 

p^{s} +O(1), s® 1^{+}.
(4) 
Then, by splitting the sum in real and complex characters, one gets


p^{1}= 


æ ç ç ç ç ç è 


+ 

+ 


ö ÷ ÷ ÷ ÷ ÷ ø 

ln L(1,c) + O(1).
(5) 
c_{0} is called the
principal character and equals 1 whenever
n¬ º0 mod q and 0 otherwise.
The first sum (over c_{0}) is +¥, as
L(s,c_{0})=z(s)Õ_{pq} (1p^{s}).
This infinite term should imply that there are an
infinite number of primes in the arithmetic progression. The only problem
is that one of the other terms could cancel this one by being
¥ at s = 1. The Abel summation criterion shows that L(1, c) is
finite. One therefore has to show that L(1, c)¹ 0.
This is definitely true for complex characters since otherwise,
by setting a=1 and taking the
exponential in (4), one has
Õ_{c}L(1, c)>1 which is incompatible with a zero of
order at least 2 (coming from L(1, c)=0 and L(1,c)=0) versus
a single pole in s=1. Hence the last sum in relation (5) is bounded.
The real problem is then to bound the middle sum
in relation (5),
that is to say to show that L(1,(· / q))¹ 0.
Dirichlet proved this result by a very ingenious method: He evaluated
this number in closed form! This is now known as
Dirichlet's class number formula:
0¹ L 
( 
1,(· / q) 
) 
= 
ì ï ï í ï ï î 

when qº 1mod 4 

when q º 3mod 4 


where h is
the class number of Q(((1)^{(q+1)/2}q)^{1/2}) and
e its fundamental unit and w the number
of roots of unity in this field (see the canonical reference [2]).
Since each of these quantities counts
something, they are positive, the result now follows:
Simpler proofs using only complex analysis are also possible.
The idea is to use Landau's theorem that a Dirichlet series with positive
terms has a pole at its abscissa of convergence and apply
it to Õ_{c} L(s, c) which has just
been shown to have positive coefficients.
3 Prime Number Theorem
The distribution of primes is quite irregular, so it is easier to
study their statistical behaviour. In this direction, let p(x) be
the number of primes £ x. Gauss conjectured that p(x)~
ò_{2}^{x} dt/ln t =:Li(x). This assertion simply says: ``the
probability that n is prime is about 1/ln n.'' This result was
finally proved by Hadamard and La Vallée Poussin in 1896. Both of
them
used fundamental ideas of Riemann who was the first to introduce
complex analysis in the study of the distribution of prime numbers.
Using Perron's formula, namely
and using residues,
Riemann essentially found what is perhaps the most important
formula in analytic number theory (the von Mangoldt explicit
formula):


ln(p)
=
x 

 



=
xln 
(2p) 



 

ln(1x^{2}),
(6) 
where sum on the right is over the zeroes of the Riemann z
function. These zeroes can be split up into two types: The trivial zeroes at 2, 4, 6, ..., and
the zeroes with 0 £ Â £ 1 (the right hand side of (6) reflects this dichotomy). This formula has many interesting
properties and reflects the following principles of analytic
number theory:
 Primes should always be counted with weight ln(p);
 Primes and prime powers should be counted together;
 There are much less prime powers than primes;
 The zeroes of the z function are the
``fundamental frequencies'' of the primes, and in this sense are
dual to the primes.
Following Chebyshev, one defines q(x) = å_{p £ x} ln(p)
and y(x) = å_{p}^{n}_{ £ x} ln(p) = å_{n £ x} L(n) ,
where L(n) = ln(p) when n=p^{m}, and zero otherwise.
A fairly straightforward partial summation shows that the prime
number theorem is equivalent to y(x) ~ x (note that trivially,
y(x) = q(x) + O((x)^{1/2})), and that more generally,
y(x) = x + R(x) ÜÞ p(x) ~ Li(x)
+ O(R(x)/ln(x)).
One can then see from the explicit formula (6) that the prime
number theorem would follow if one can bound
Â r < 1, since each error term would then be of order < x.
The prime number theorem would then be equivalent to showing that
z(1 + it) ¹ 0 for t¹ 0. In fact, this is an equivalence
(as was later shown by Wiener)
and Hadamard and La Vallée Poussin were able to prove that
z(1 + it) ¹ 0 using some ingenious trigonometric identities.
We will give a proof due to Mertens, in 1898.
Set r=1+it, then z(r)=0 Þ Â ln z(s+it)®
¥ when s® 1 (we restrict to Â(s)>1).
But, by the Euler identity, one has
ln z(s)=å_{p} å_{m³ 1} m^{1} p^{ms}
exp(itmln(p)) and so
Â ln 
z(s)= 



m^{1} p 

cos(tmln(p)). 
Mertens' trick consists in noticing that 2(1+cos b)^{2}=3 +4 cos
b + cos 2b ³ 0, thus
3 lnz(s)+4Âlnz(s+it)+Âlnz(s+2it)³ 0,
hence z^{3}(s) z^{4}(s+it) z(s+2it) ³ 1.
But, as s® 1, one has z(s)~ (s1)^{1}
and z(s+it)~ A (s1) for a some constant A (by analyticity). So one
should have z(s+2it)® ¥,
this contradicts the fact that z(1+2it) is bounded (by the Abel summation criterion).
In conclusion, the z function has no zero with Â(r)=1, the
PNT is proved.
Note that by mixing his proof of the PNT
and the proof of Dirichlet's theorem, La Vallée Poussin proved also
that there is asymptotically
p(x)/f(q) primes of the shape a+q n less than x.
An elementary (i.e. without complex analysis) proof of the PNT was
subsequently found by Erdös and Selberg in 1949 (see [4]
and [9]).
4 Chebyshev's Bias
All numerical evidence shows that p(x)<Li(x) and it was long
believed that this would be true for all x. Similarly, Chebyshev
noted that the number of primes of the form 4k+3 seemed to be more
abundant than the primes of the form 4k+1, more precisely, let
p_{q,a}(x) = {p £ x: pº amod q} then
p_{4, 3}(x) ³ p_{4, 1}(x).
In fact, Littlewood proved in 1914 that p(x)  Li(x) changes sign
infinitely often and the same is true for p_{4, 3}(x)  p_{4,
1}(x). In 1957 Leech showed that p_{4, 1} (x) > p_{4,3}(x)
is first true for x= 26861. That the similar inequality
p_{3, 1} (x) > p_{3,2}(x) is first true for x=608981813029
was shown by Bays and Hudson in 1978. No example of p(x) > Li(x)
is known. Skewes first gave an upper bound e^{e}^{e}^{5} which
was later reduced by ShermanLehman and then te Riele [10] who
gave an upper bound of 10^{370}.
This behaviour can easily be explained using explicit formulas.
In the case of p(x), the point is the following: The explicit
formula (6) expresses y(x) as a sum of powers x^{r}.
Assuming the Riemann Hypothesis, one can write this as
y(x) =
x  x^{1/2} 
æ ç ç è 




ö ÷ ÷ ø 
+o(x^{1/2}).

One can now see the reason for the bias: The function y(x)
does not count primes but prime powers so what one really wants
is the behaviour of q(x) which is given by
q(x) = y(x)  q((x)^{1/2}) +O(x^{1/3}),
so that
q(x) = x  x^{1/2} 
æ ç ç è 
1+ 



ö ÷ ÷ ø 
+o(x^{1/2}).

The function
is a very slowly oscillating trigonometric series which should
be zero on average, so the extra term biases q(x) to be
smaller than x on average. A simple description is that
Li(x) counts the number of prime powers £ x, so the
number of primes should be slightly less since the number
of prime squares is of the same order as the error term.
There is a similar explanation for the bias in arithmetic progressions.
There is an explicit formula

c(n) ln(p)
=
 x^{1/2} 
æ ç ç ç è 




ö ÷ ÷ ÷ ø 
+ o(x^{1/2}),

where the Generalised Riemann Hypothesis has been assumed
(there is no x term since L(1, c) is no longer a pole if
c ¹ c_{0}). As before one has
but one really wants to look at
q_{q,a} (x) =


ln 
(p)
=
y_{q, a} (x) 


ln(p) + O(x^{1/3})
=
y_{q, a}(x)  c_{q, a} x^{1/2} + O(x^{1/3}),

where c_{q, a} is the number of solutions of
y^{2} º amod q. In particular, the same
argument shows that there will always be fewer primes in the
progression qn + a when a is a residue than when a is a
nonresidue. Simply put, the ``balanced'' count is the set of
prime powers º amod q so there are fewer
primes º amod q when a is quadratic residue
since the number of prime squares congruent to a is of the same
order as the error term in the analytic formulas.
In 1994, Rubinstein and Sarnak [8] were able to make
Chebyshev's bias precise. Assuming GRH (if this is false, then there
is no bias) and also the Grand Simplicity Hypothesis (GSH:
All the ordinates of zeroes of Lfunction are linearly
independent over Q), then



® .00000026,




å 
p_{4,3}(n) > p_{4,1}(n) 
n £ x 


® .9959.

References
 [1]

Daboussi (Hédi). 
Sur le théorème des nombres premiers. Comptes Rendus des
Séances de l'Académie des Sciences. Série I. Mathématique, vol. 298,
n°8, 1984, pp. 161164.
 [2]

Davenport (Harold). 
Multiplicative Number Theory. 
SpringerVerlag, New York, 1980, second edition,
xiii+177p. Revised by Hugh L. Montgomery.
 [3]

Dirichlet (L.). 
Beweis des Satzes, das jede unbegrenzte arithmetische
Progression... Abh. König. Preuss. Akad., vol. 34,
1837, pp. 4581.
 [4]

Erdös (P.). 
On a New Method in Elementary Number Theory which leads to
an Elementary Proof of the Prime Number Theorem. Proceedings
of the National Academy of Sciences. U.S.A., vol. 35, 1949,
pp. 374384.
 [5]

Friedlander (John) and Iwaniec (Henryk). 
Using a ParitySensitive Sieve to Count Prime Values of a
Polynomial. Proceedings of the National Academy of Sciences. U.S.A.,
vol. 94, n°4, 1997, pp. 10541058.
 [6]

Niven (Ivan). 
A Simple Proof that p is Irrational. Bulletin of the
American Mathematical Society, vol. 53, 1947, p. 509.
 [7]

Ribenboim (Paulo). 
The New Book of Prime Number Records. 
SpringerVerlag, New York, 1996, xxiv+541p.
 [8]

Rubinstein (Michael) and Sarnak (Peter). 
Chebyshev's Bias. Experimental Mathematics, vol. 3, n°3,
1994, pp. 173197.
 [9]

Selberg (Atle). 
An Elementary Proof of the PrimeNumber Theorem. Annals of Mathematics (2), vol. 50, 1949, pp. 305313.
 [10]

te Riele (Herman J. J.). 
On the Sign of the Difference p(x)Li(x). Mathematics of Computation, vol. 48, n°177, 1987,
pp. 323328.
 [11]

Tenenbaum (Gérald) and Mendès France (Michel). 
Les nombres premiers. 
Presses Universitaires de France, Paris, 1997, 128p.