1) Gauss' function
So, let's remind ourself that r(n) is the number of way to
decompose n into 2 squares, combinations included. That is we
also include in this number the trivail combinations with
multiplication by -1 or the order of the squares.
For example, taking 5, we get :
The properties of that function were mostly studied by Gauss and Jacobi.
The first demonstrated the result we want, and that has a nice
If we consider a
disc of radius , that is which has
equation x2+y2=, we can see that the integer couples (x,y)
that satisfy x2+y2= where pn are within the
disk as shown in the figure on the right (they are on the edge of the
circle radius whuch is smaller
that the one of radius , they are the dots
inside the circle). Draw for each of thoses dots in the disk a square
which the lower left corner is that point.
We then get a funny figure, which we'll call the domain Dn,
where the area is the number of squares (of sides and so area 1)
which it contains.
But r(p) for pn counts the
number of dots that are on the circle of radius hence all the dots inside the disc is counted
in a r(p) for pn. Therefore, the number of
points and associated squares is r(1)+r(2)+...+r(n).
The area of the domaine Dn shown above is therfore r(1)+r(2)+...+r(n).
But Dn is included in a circle of radius , that is the radius of the first circle +
the diagonal of square 1 unit length (Look at the figure, the only
thing of the domain that is not in the circle is never greater than the
diagonal of a square, as marked)
Similarly, this domain can contain a circle of radius . Those disk have an area of so in the end we have sandwitch the area of Dn
There we go !
We do get
Instead of considering O(), we could find
for what minimal power of n (call it a) the result is still
valid, in other terms, what is the speed of convergence.
As Autour du nombre Pi by Eymard/Lafon remind us, it's has been
a reasearch issues for the last one and a half century.
It has recently been found that a1/2. Hardy and
Landeau proved seperatly that a1/4. The
conjucture is that a=1/4 but it has yet to be proved. The best
know coefficient for the moment is a22/73 and was
found by Huxley (1993).
In the same style, we can generalise rk(n) the
number of decomposition of n as the sum of k squares.
This comes down to work not in R2 like we did for
two squares, but in Rk.
We even get
withVk(R) being the volume of a sphere of
radius R in dimension k.
But from the attic, we know this is
equivelant to :
for dimension m.
Therefore we can conclude that :
2) Function (n) sums of dividors
Once again let's remind ourself that (n)=, that is the sum of positive integers that
A few example, just to make it clear !
(1)=1, (2)=1+2=3, (6)=1+2+3+6=12, (12)=1+2+3+4+6+12=28
This function is multiplicative for any to integers that are coprime.
Let's plunge in straight away in the deep
end and do a bit of counting.
(1)+(2)+...+(n) contains the dividors of each naturals n counted a certain number of time, and we add them all up.
We are going to find out this "certain number of time" for each divisor.
We start by fixing an x
between 1 and n, first we look for the yp
such that xyp=p, pn.
So for the set of pn, we then have counted the
number of time each divisor yp of (p) appear as well as the divisors of x.
Then, we sum the yp on all the x, and we
will obtain the wanted value of (1)+(2)+...+(n).
Consider the line xy=n
in the plane as shown on the right.
Fixing x is the same as counting the y such that xyD.
Thefore using the notation [a] to be the integer part of a,
but we know that by taking the
greatest value of each term so
We also know that gamma, Euler's constant is
so and finnaly
Great, two down and two more to go....
As with 1), intense research are still being done on the best possible
remainder, and for the moment A. Walfisz has the prize with O(n.Ln2/3(n))
found in 1963.
3) Möbius's function µ(n)
Let µ(1)=1 ; µ(n)=0 if n
contains at least one squared factor>1 and µ(p1p2...pk)=(-1)k
if p1, p2, ..., pk are
distinct prime numbers (exemple µ(2)=µ(7)=-1, µ(4)=µ(8)=0,
1) One of the first (quite amazing) property of this function is the
Proving this is fairly simple, the result
is obvious by definition for n=1. Taking now an un n>1
and show that the sum is nul.
The integer n is as always the product of prime factors hence
we can write it :
If we want to find the sum of the divisor of n,
this is the same as taking the sum of the primes pi,
then the couples of primes pipj ,
then the triplets, etc.. therefore :
using the definition µ(p1p2...pk)=(-1)k
and then we count the number of couples, triplest that can exists in
the sum (hence the combinations) and finnaly, we can see Newton's binomial formula.
2) µ is a multiplicative
function, and provide a strong results that make it possible to inverse
certain formulae :
(We do get )
Ok, so this is all good, but now for the demonstration that we want :
Proving that :
We will need a small lemma, that we'll call Dirichlet's Lemma :
Let f(s) and g(s) the series said to be Dirichlet to be
defined as :
. Multiplying those two series
Now using this Dirichlet multiplication we can calculate:
with so finnaly
whith the result
This is not all, if we go further, as
mentioned above, by considering Q the set of intergers nN* who don't have any square factors in it's
decomposition (that is such that µ(n)=1) we obtain the lovely following formula:
The prove in itself is not very difficult
but it needs a rather long generalistion of certain results, and for
the moment, I don't want this page to turn into a monster... Though I
can't resist the pleasure of being able to show a small result which I
find even more impressive:
The probability that an
integer is without any squared factors is
Define Q(x) for real x the number
of integers k less than x and who don't have squared
Using the definition of Möbius' function, we can write for n
Q(n)=. To prove the
theorem, we just need to look at the proportion of Q(n)
compared to n, that is to show that
The basis of it consit first of all to
place an integer k whose biggest squared factor is d2
in a set Ed. We do this for all kn. For E1, obviously, correspond to
the set of integers without squared factors.
And since there are no squared factors greater than n1/2
in n (Again obviously!), Ed
is empty for d>n1/2. Counting the numberf of
element of Ed:
It is fairly evident that card(E1)=Q(n).
For the others Ed, take k=d2*k'
k'n/d2 since kn.
Furthermore, k' does not have any squared factors
because if it had one (call it a for example), a.d will
also be a squared factor of k and since a.d>d, k
would belong to another Ei. So in the end card(Ed)=number
of k'n/d2 without any squared
factors, hence : card(Ed)=Q(n/d2)
Since we have n non nul integers less than n
(!), and that they are all included in a Ed, we can
Following this, if we aplly the famous
inversion formula of Möbius to f(x)=Q(x2) with n1/2=x
and so to g(n)=n2, g(x)=[x2]
for real x.
This formula allows the following calculation, with (it seems to
me....) quite obvious steps :
Finnally, for O(sum), the result comes from :
4) Euler's Indicator
Recall : (n) the number of integers strictly less
than n and that are coprime with n
(don't have any common factors with n).
1) A first lemma states that is multiplicative
for two integers m
and n that are coprime, i.e.
It is true, if we try to evaluate (n), we start from the definition :
according to Bézout's theorem, k and n are
coprime if and only if there exists integers u and v
such that u.k+v.n=1 so this is equivalent to k
inversible modulo n.
Therefor (n) is the cardinal of the
inversibles groups of Z/nZ. Since m and n are
coprime, according to the famous chinesse lemma, there exists an
isomorphism between Z/mnZ and Z/nZ*Z/mZ so the
inversibles groups of those two rings have the same cardinality and (n.m)=(n).(m).
(phew, this brings back some painful memories of algebra!)
2) Now, if we want to evaluate for all n,
let's start by decompose this poor integer: n=p1a1p2a2...pkak
, ai being an non nul integer, and calculate for piai :
Between 1 and piai (not included),
there's piai-1 integers (!) and since the
only multiples of pi are factors of piai
as pi prime, those factors are :
pi, 2pi, 3pi, ..., (piai-1)p. So
there are piai-1.
So the number of integers that are coprime with n is :
of divisors of n=piai-1-(piai-1-1)=piai(1-1/p)
And since the piai
are evidently coprime between them, we can work out (n) thanks to the multiplicity of :
For example, 500=2253
3) Developing the following product, we get :
If we have d=p1p2...pk, the pi
being all disctint like in the sum, then µ(d)=(-1)k
Therefore, in all cases, we can write :
because if d has a prime factor squared, the Möbius'
function applied to d is nul by definition.
Ok, now we need to show that then ...
We suspected for quite a while, that the previous lemma using
Möbius' function was going to be very useful!
Let's plunge straight in the calculation :
Here again, numerous research end it up with a new masterpiece by
Walfisz (1963) who found the best remainder known today, O(n(Ln(n))2/3(Ln(Ln(n)))4/3).
To prove the second fomula, we are going to use Dirichlet's
multiplication and the result demonstrated above:
There we go! It wasn't that hard, was it ? But we just simply need to
This last formula allow us for example to find :
One last consequence of this result
is the famous theorem of Cesàro !
It's unbelievable to find it here, but the definition of Euler's Indicator function was hinting at it.
Truly, count the number of integers couple (p,q) included
between 1 and n. If p=1, q can take the value 1 to n,
hence n values. If p=2, q can take the value
2 to n
(since (2,1) was already counted previously under the form (1,2)
when p=1) hence n-1 value, and so on until p=n.
So there are 1+2+3+...+n=n(n+1)/2 couples (p,q).
The number of integers coprime with fixed p is simply the value
of the function(p) by definition. So up to n, the number
of integers couple (p,q)
that are coprime is (1)+(2)+(3)+...+(n).
So the probability that two positive integers are coprime is equal to
the limit of the sum proportion of the (k) (favorables cases) on the number n(n+1)/2
of coup;es (p,q) (total cases) i.e. :