|
|
| View previous topic :: View next topic |
| Author |
Message |
Freakazoid
Guest
|
 Posted: Fri Jul 04, 2008 8:26 pm Post subject: Mobius inversion and zeta function |
 |
|
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}
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 |
|
| Back to top |
|
 |
| |
Ads |
Advertising
Sponsor
|
|
Mariano Suárez-Alvarez
Guest
|
| Posted: Fri Jul 04, 2008 8:42 pm Post subject: Re: Mobius inversion and zeta function |
|
|
Freakazoid wrote:
| Quote: |
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 |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
Freakazoid
Guest
|
| Posted: Fri Jul 04, 2008 9:20 pm Post subject: Re: Mobius inversion and zeta function |
|
|
On 4 Lug, 20:42, Mariano Suárez-Alvarez
<mariano.suarezalva...@gmail.com> wrote:
| Quote: |
Freakazoid wrote:
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
|
Yes, I know that, but the Riemann sum is over all n, so I thought that
he used the generalized mobius inversion formula. |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
galathaea
Guest
|
| Posted: Sat Jul 05, 2008 3:35 am Post subject: Re: Mobius inversion and zeta function |
|
|
On Jul 4, 1:26 pm, Freakazoid <douglas.dex...@gmail.com> wrote:
| Quote: |
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}
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.
|
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 |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
Narcoleptic Insomniac
Guest
|
| Posted: Sat Jul 05, 2008 5:06 am Post subject: Re: Mobius inversion and zeta function |
|
|
On Jul 4, 2008 3:26 PM CT, Freakazoid wrote:
| Quote: |
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}
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
|
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.
http://www.amazon.com/Riemanns-Zeta-Function-Harold-Edwards/dp/0486417409/ref=sr_1_2?ie=UTF8&s=books&qid=1215234144&sr=8-2
Regards,
Kyle Czarnecki |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
Freakazoid
Guest
|
| Posted: Sat Jul 05, 2008 8:53 am Post subject: Re: Mobius inversion and zeta function |
|
|
On 5 Lug, 05:06, Narcoleptic Insomniac
<i_have_narcoleptic_insom...@yahoo.com> wrote:
| Quote: |
On Jul 4, 2008 3:26 PM CT, Freakazoid wrote:
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}
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
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.
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.
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. |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
Mariano Suárez-Alvarez
Guest
|
| Posted: Mon Jul 07, 2008 2:23 am Post subject: Re: Mobius inversion and zeta function |
|
|
On Jul 5, 8:50 pm, Timothy Murphy <gayle...@eircom.net> wrote:
| Quote: |
Mariano Suárez-Alvarez wrote:
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?
|
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 |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
