1) Gauss' function*
r(n)*

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 :

*5=(+/-1)*^{2}+(+/-2)^{2}=(+/-2)^{2}+(+/-1)^{2}

therefore *r(5)=4+4=8*.

The properties of that function were mostly studied by Gauss and Jacobi.

The first demonstrated the result we want, and that has a nice
geometrical explenation.

If we consider a
disc of radius , that is which has
equation *x*^{2}+y^{2}=, we can see that the integer couples *(x,y)*
that satisfy *x*^{2}+y^{2}= 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 *D*_{n},
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 *D*_{n }shown above is therfore *r(1)+r(2)+...+r(n)*.

But *D*_{n} 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 *D*_{n}
:

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 *r*_{k}(n) the
number of decomposition of *n* as the sum of *k* squares.
This comes down to work not in *R*^{2} like we did for
two squares, but in *R*^{k}.

We even get

with*V*_{k}(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 :

with

2) Function *(n)* sums of dividors

Once again let's remind ourself that *(n)=*, that is the sum of positive integers that
divide n.

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 *y*_{p}
such that *xy*_{p}=p, *pn*.

So for the set of *pn*, we then have counted the
number of time each divisor *y*_{p} of *(p)* appear as well as the divisors of *x*.
Then, we sum the *y*_{p} 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*,
we get

*(1)+(2)+...+(n)=*

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

*(1)+(2)+...+(n)=n*^{2}+O(n.Ln(n))

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.Ln*^{2/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 *µ(p*_{1}p_{2}...p_{k})=(-1)^{k}
if *p*_{1}, p_{2}, ..., p_{k} are
distinct prime numbers (exemple *µ(2)=µ(7)=-1*, *µ(4)=µ(8)=0*,
*µ(6)=µ(10)=1*).

Lemmae

1) One of the first (quite amazing) property of this function is the
following:

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 :

*n=p*_{1}^{a1}p_{2}^{a2}...p_{k}^{ak}.
If we want to find the sum of the divisor of *n*,
this is the same as taking the sum of the primes *p*_{i},
then the couples of primes *p*_{i}p_{j} ,
then the triplets, etc.. therefore :

using the definition *µ(p*_{1}p_{2}...p_{k})=(-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 )

Demonstration:

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
gives us:

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

Prove :

Define *Q(x)* for real x the number
of integers *k* less than *x* and who don't have squared
factors.
Using the definition of Möbius' function, we can write for n
integers :

*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

*Q(n)=n+O(n*^{1/2})

The basis of it consit first of all to
place an integer *k* whose biggest squared factor is *d*^{2}
in a set *E*_{d}. We do this for all *kn*. For *E*_{1}, obviously, correspond to
the set of integers without squared factors.
And since there are no squared factors greater than *n*^{1/2}
in *n* (Again obviously!), *E*_{d}
is empty for *d>n*^{1/2}. Counting the numberf of
element of *E*_{d}:

It is fairly evident that *card(E*_{1})=Q(n).

For the others *E*_{d}, take *k=d*^{2}*k'
in *E*_{d}.

*k'n/d*^{2} 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 *E*_{i}. So in the end *card(E*_{d})=number
of *k'n/d*^{2} without any squared
factors, hence : *card(E*_{d})=Q(n/d^{2})

Since we have *n* non nul integers less than *n*
(!), and that they are all included in a *E*_{d}, we can
write :

Following this, if we aplly the famous
inversion formula of Möbius to *f(x)=Q(x*^{2}) with *n*^{1/2}=x

and so to *g(n)=n*^{2}, *g(x)=*[*x*^{2}]
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
function *(n)*

Recall : *(n)* the number of integers strictly less
than *n* and that are coprime with *n*
(don't have any common factors with *n*).

Lemmae:

1) A first lemma states that is multiplicative
for two integers *m*
and *n* that are coprime, i.e.

*(n.m)=(n).(m)*

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=p*_{1}^{a1}p_{2}^{a2}...p_{k}^{ak}
, *a*_{i} being an non nul integer, and calculate for *p*_{i}^{ai} :

Between* 1* and *p*_{i}^{ai} (not included),
there's *p*_{i}^{ai}-1 integers (!) and since the
only multiples of *p*_{i} are factors of *p*_{i}^{ai}
as *p*_{i} prime, those factors are :

*pi, 2pi, 3pi, ..., (p*_{i}^{ai}-1)p. So
there are *p*_{i}^{ai}-1.

So the number of integers that are coprime with *n* is :

*(p*_{i}^{ai})=p_{i}^{ai}-1-number
of divisors of n=p_{i}^{ai}-1-(p_{i}^{ai-1}-1)=p_{i}^{ai}(1-1/p)

And since the *p*_{i}^{ai}
are evidently coprime between them, we can work out *(n)* thanks to the multiplicity of :

For example, *500=2*^{2}5^{3}
so *(500)=500(1-1/2)(1-1/5)=200*.

3) Developing the following product, we get :

If we have *d=p*_{1}p_{2}...p_{k}, the *p*_{i}
being all disctint like in the sum, then *µ(d)=(-1)*^{k}
so .

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.

Cool...

Prove:

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 :

Phew...

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
dive in...

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

Great!.....