Mobius inversion and zeta function
Freakazoid
I was examining the passage where Riemann did the inversion
from J(x) to pi(x) to obtain the prime counting function.
Well, I really can't understand this. The Mobius inversion formula and
the situation he had to face with are quite different.
In fact, the theorem says that
G(x) = sum{ F(x/n), n < x}
F(x) = sum{ mu(n)G(x/n) n < x}
but the relation between J(x) and pi(x) is
J(x) = sum{ pi(x^(1/n)) * (1/n), n < x}
pi(x) = sum{ mu(n)/n * J(x^(1/n)), n < x}
and we can say n<x because we need just the terms that are different
to 0.
Now we've got different arguments for G(x): in fact the n is at the
exponent. I was thinking why the mobius formula should be still valid.
Thanks
Mariano Suárez-Alvarez
> Hi,
> I was examining the passage where Riemann did the inversion
> from J(x) to pi(x) to obtain the prime counting function.
> Well, I really can't understand this. The Mobius inversion formula and
> the situation he had to face with are quite different.
> In fact, the theorem says that
>
> G(x) = sum{ F(x/n), n < x}
> F(x) = sum{ mu(n)G(x/n) n < x}
The inversion formulas involve not sums for "n < x"
but sums for "n dividing x".
-- m
Freakazoid
Yes, I know that, but the Riemann sum is over all n, so I thought that
he used the generalized mobius inversion formula.
galathaea
actually the mobius inversion formula
is a general theorem on flows of arithmetical semigroups
mobius' original theorem was on the inversion of power series
there are several really good papers on this
but the one by benito, navas, and varona
"mobius inversion formulas for flows of arithmetic semigroups"
is the best summary i have seen
see http://www.unirioja.es/cu/jvarona/papers.html
i used it
for instance
to prove mobius inversion formulas for generalised polynomial rings
mobius inversion is very general
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
galathaea: prankster, fablist, magician, liar
Narcoleptic Insomniac
H. M. Edwards wrote an excellent text on the subject
called "Riemann's Zeta Function." The first chapter is
an analysis of Riemann's famous paper (of which a
translation is provided in the appendix); here is what
Edwards has to say on the matter in section 1.17 on
page 33-4:
---------------------------------------------------------
1.17 THE FORMULA FOR pi(x)
Of course Riemann's goal was to obtain a formula not for
J(x) but for the function pi(x), that is, for the number
of primes less than any given magitude x. Since the
number of prime squares less than x is obviously equal to
the number of primes less than x^(1/2), that is, equal to
pi(x^(1/2)), and since in the same way the number of
prime n'th powers p^n less than x is pi(x^(1/n)), it
follows that J and pi are related by the formula
(1) J(x) = pi(x) + 1/2 pi(x^(1/2)) + 1/3 pi(x^(1/3))
+ ... + 1/n pi(x^(1/n)) + ... .
The series in this formula is finite for any given x
because x^(1/n) < 2 for n sufficiently large, which
implies pi(x^(1/n)) = 0. Riemann inverts this
relationship by means of the Mobius inversion formula**
(see Section 10.9) to obtain
(2) pi(x) = J(x) - 1/2 J(x^(1/2)) - 1/3 J(x^(1/3))
- 1/5 J(x^(1/5)) + 1/6 J(x^(1/6))
+ ... + mu(n)/n J(x^(1/n)) + ... ,
where mu(n) is 0 if n is divisible by a prime square, 1
if n is a product of an even number of distinct primes,
and -1 if n is a product of an odd number of distinct
primes.
** Very simply this inversion is effected by performing
successively for each prime p = 2, 3, 5, 7, 11, ... the
operation of replacing the functions f(x) on each side of
the equation with the functions f(x) - (1/p) f(x^(1/p)).
This gives successively
J(x) - 1/2 J(x^(1/2)) = pi(x) + 1/3 pi(x^(1/3))
+ 1/5 pi(x^(1/5)) + ... ,
J(x) - 1/2 J(x^(1/2)) - 1/3 J(x^(1/3)) + 1/6 J(x^(1/6)) =
pi(x) + 1/5 pi(x^(1/5)) + 1/7 pi(x^(1/7)) + ... ,
etc., where at each step the sum on the left consists of
those terms of the right side of (2) for which the factor
n contains *only* the primes already covered and the sum
on the right consists of those terms on the right side of
(1) for which the factors of n contain *none* of the
primes already covered. Once p is sufficently large, the
latter are all zero except for pi(x).
---------------------------------------------------------
Hopefully Edward's explanation helps you see how the
inversion actually works ^_^
In any case, if you are interested in Riemann's famous
manuscript, the zeta function, and the Prime Number
Theorem, then I strongly suggest picking up a copy of
Edward's text.
Regards,
Kyle Czarnecki
Freakazoid
>
> Regards,
> Kyle Czarnecki
Oh, that's an excellent one. I already had a look at Edward's, but I
was asking to myself if the proof in the note at the bottom of the
page was mathematically valid or if it was an easy explanation of the
transform process.
As far as I can see from the text that galathaea pointed to me, the
inversion formula is valid because of some other forms.
Thanks to everyone.
Timothy Murphy
> actually the mobius inversion formula
> is a general theorem on flows of arithmetical semigroups
I think the most natural generalisation of Mobius inversion
is to distributive lattices
(as described eg in the book on Lattices by Birkhoff senior).
The set of positive integers, ordered by division,
forms a distributive lattice,
as do the subsets of a set.
Mariano Suárez-Alvarez
Distributivity of the poset is quite irrelevant.
-- m
Narcoleptic Insomniac
> > Hopefully Edward's explanation helps you see how the
> > inversion actually works ^_^
> >
> > In any case, if you are interested in Riemann's famous
> > manuscript, the zeta function, and the Prime Number
> > Theorem, then I strongly suggest picking up a copy of
> > Edward's text.
> >
> >
> http://www.amazon.com/Riemanns-Zeta-Function-Harold-Edwards/dp/048641...
> >
> > Regards,
> > Kyle Czarnecki
>
> Oh, that's an excellent one. I already had a look at
> Edward's, but I was asking to myself if the proof in the
> note at the bottom of the page was mathematically valid
> or if it was an easy explanation of the transform
> process.
It is definitely not a mathematical "proof" by any means,
but rather an "explanation" (I thought that was what you
were looking for).
> As far as I can see from the text that galathaea pointed
> to me, the inversion formula is valid because of some
> other forms.
>
> Thanks to everyone.
Yes, as galathaea and Timothy have pointed out, Mobius
inversions can be generalized from the integers to sets
with more structure.
If you're looking for a "proof" that deals with the
Mobius inversion formula for sequences and series, then
I might suggest "An Introduction to Analytic Number
Theory" by Tom Apostol
IIRC, there is a proof somewhere in chapter 2, but I may
be mistaken. The text also contains some material on the
Riemann zeta function and it's generalization to the
Dirichlet L-series.
Regards,
Kyle Czarnecki
Timothy Murphy
>> I think the most natural generalisation of Mobius inversion
>> is to distributive lattices
>> (as described eg in the book on Lattices by Birkhoff senior).
>>
>> The set of positive integers, ordered by division,
>> forms a distributive lattice,
>> as do the subsets of a set.
>
> Distributivity of the poset is quite irrelevant.
Yes, I'm not sure why I thought distributivity was relevant.
IIRC, Birkhoff in his classic book on lattice theory
defines the Mobius function in the section on distributive lattices.
But it several decades since I read that book
and my recollection may well be defective.
Maybe the Mobius function is particularly simple in that case?
Mariano Suárez-Alvarez
The distributive case is probably the most interesting one
from the point of view of combinatorics. The book by Stanley
[Enumerative Combinatorics] has lots of information on the subject
of Moebius inversion, specially in the distrbutive case,
and lots of connections to nice examples of enumeration.
-- m