wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Sum over the rationals
        
(Message started by: Pietro K.C. on Jun 7th, 2004, 9:28am)
Title: Sum over the rationals
Post by Pietro K.C. on Jun 7th, 2004, 9:28am
I got this one from American Mathematical Monthly, section 'Problems and Solutions'. I think it was the latest issue (as of June 4th).

For x [in] [bbq], let a / b be the representation of x in its lowest terms, i.e.

x = a / b  and gcd(a,b) = 1.

Define f : [bbq] [to] [bbz] by f(x) = ab. Show that

  [sum]  (f(x))-2  =  5/2.
x [in] [bbq]+
Title: Re: Sum over the rationals
Post by Aryabhatta on Jun 7th, 2004, 7:03pm

on 06/07/04 at 09:28:28, Pietro K.C. wrote:
I got this one from American Mathematical Monthly, section 'Problems and Solutions'. I think it was the latest issue (as of June 4th).

For x [in] [bbq], let a / b be the representation of x in its lowest terms, i.e.

x = a / b  and gcd(a,b) = 1.

Define f : [bbq] [to] [bbz] by f(x) = ab. Show that

  [sum]  (f(x))-2  =  5/2.
x [in] [bbq]+



The value of this is [zeta][sup2](2)/[zeta](4) = 90/36 = 5/2
([zeta] is the riemann zeta function)
We use the fact that [sum]d [mu](d) d-n = 1/[zeta](n), [forall] n > 1, where [mu] is the moebius function.

The given sum = [sum]kk-2 [sum] {(n,k) = 1} n-2, k and n range from 1 to [infty]
For a given k, the inner sigma can be written as (using a standard theorem in number theory)

[sum] d|k [mu](d) [sum] m (md)-2  which is equal to

[sum] d|k [mu](d)d-2[sum] m m-2 =

[zeta](2)[sum] d|k [mu](d)d-2

so the total sum =

[zeta](2)([sum]kk-2[sum] d|k [mu](d)d-2)

Now,
[sum]kk-2[sum] d|k [mu](d)d-2 = [sum]k[sum] d|k [mu](d)d-2 k-2 =

[sum]d [sum]m[mu](d)d-2(md)-2 = [sum]d[mu](d)d-4[sum]mm-2 = [sum]d[zeta](2)[mu](d)d-4 = [zeta](2)/[zeta](4)

So the total sum = [zeta][sup2](2)/[zeta](4)

Also, in general, for the f which was defined in the problem,

  [sum]  (f(x))-t = [zeta][sup2](t)/[zeta](2t) where t > 1.
x [in] [bbq]+

Thanks for posting this,  I have just started to learn about the moebius function and this turned out to be a good exercise!   :D
Title: Re: Sum over the rationals
Post by Pietro K.C. on Jun 8th, 2004, 4:49pm
Well, you sure do know a lot of number theory for someone who's just starting to learn about the Möbius function! :)

I don't know how it is abroad, but here in Brazil the Möbius function is introduced in the very first semester on number theory, long before zeta functions or even infinite sums!

I have two follow-ups now:

1. Let S(t) be the sum of my first post, but with the 2 replaced by t in the exponent. Find all integers t such that S(t) is rational.

2. Demonstrate the formula for 1 / [zeta](n) used by Aryabhatta. Generalize. (Intentionally open-ended, though I have a generalization myself.)

Note: I didn't know that formula for 1 / [zeta](n). Pretty!
Title: Re: Sum over the rationals
Post by Barukh on Jun 9th, 2004, 5:37am

on 06/08/04 at 16:49:16, Pietro K.C. wrote:
Well, you sure do know a lot of number theory for someone who's just starting to learn about the Möbius function! :)

I don't know how it is abroad, but here in Brazil the Möbius function is introduced in the very first semester on number theory, long before zeta functions or even infinite sums!

For somebody who hasn’t learned about Möbius function at any semester in the University (like myself), this thread is an excellent sourse of new treasures.

So, I would like to comment on some “well-known” results that were new for me. Let me begin with the definition of the Möbius function [mu]: [bbn] [to] (-1,0,1):

[mu](1) = 1; [mu](d) = (-1)r, if d is square-free and has r distinct prime factors; [mu](d) = 0, if d is not square-free.



on 06/07/04 at 19:03:02, Aryabhatta wrote:
For a given k …(using a standard theorem in number theory)

[sum] {(n,k) = 1} n-2 = [sum] d|k [mu](d) [sum] m (md)-2

(Sorry, Aryabhatta, I changed your post). How do we show this? Use Inclusion-Exclusion Principle to find all the integers co-prime with k, that has r distinct prime factors p1, …, pn:

[bbn] = { [mu](1)m }
-p1[bbn] = { [mu](p1) p1m }
…
-pn[bbn] = { [mu](pn) pnm }
+p1p2[bbn] = { [mu](p1p2) p1 p2m }
…
(-1)rp1…pn[bbn]  = { [mu](p1… pn) p1… pnm }
[smiley=blacksquare.gif]

I also encountered the following interesting identity involving Möbius function: [sum]d|n [mu](d) = 0 for n > 1. Can you see why?

Excellent stuff, Pietro and Aryabhatta!  :D Will look at the follow-ups.

P.S. I hope I wasn’t too annoying…
Title: Re: Sum over the rationals
Post by Barukh on Jun 10th, 2004, 2:28am

on 06/08/04 at 16:49:16, Pietro K.C. wrote:
1. Let S(t) be the sum of my first post, but with the 2 replaced by t in the exponent. Find all integers t such that S(t) is rational.

All even integers satsify - using Aryabhatta’s generalization and the fact that [zeta](t) = [pi]t times rational number for even t.

Can’t say about odd integers, though… ;)


Quote:
2. Demonstrate the formula for 1 / [zeta](n) used by Aryabhatta

Let M(n) = [sum]k[mu](k)k-n, [zeta](n) =  [sum]kk-n. We have: M(n)[zeta](n) = [sum]kk-n[sum]d|k[mu](d). But the last inner sum equals 1 for k = 1, 0 otherwise (see my previous post).

Therefore, M(n)[zeta](n) = 1.
Title: Re: Sum over the rationals
Post by Aryabhatta on Jun 11th, 2004, 1:19pm

on 06/09/04 at 05:37:13, Barukh wrote:
I also encountered the following interesting identity involving Möbius function: [sum]d|n [mu](d) = 0 for n > 1. Can you see why?

P.S. I hope I wasn’t too annoying…


No. You are not annoying ;D

The theorem which was used is this:
Given k,
[sum](n,k) = 1 f(n) = [sum]d|k[mu](d)[sum]m f(md)

The proof of this uses the fact that [sum]d|t [mu](d) = 0 for  t > 1 and 1 for t =1. -(*)

Basically we rewrite  [sum](n,k) = 1 f(n)  as [sum]n f(n)g(n,k) where g(n,k) is 1 if (n,k) = 1 and 0 otherwise .  From (*) we see that g(n,k) = [sum]d|(n,k)[mu](d)

I will leave it to you from here.

I knew the identity
[zeta](s)[sum]n[mu](n)n-s = 1 because i read it online somewhere (some course webpage) that this was the motivation for defining [mu].
Title: Re: Sum over the rationals
Post by Barukh on Jun 14th, 2004, 6:04am
Here’s another solution of the original problem.

[smiley=blacksquare.gif]
It’s clear that every natural number is a value of f(x), so I write the given sum S = [sum]ng(n)n-2, where g(n) is the number of times n appears in the sum. But g(n) is just a number of ways to write n as a product of two co-prime numbers, so g(n) = 2[omega](n), where [omega](n)  is number of distinct prime factors of n; and g(1) = 0.

The next step is not obvious, but once written, it’s not difficult to get convinced:

S = [sum]n2[omega](n)n-2 = [prod] p(1+ 2p-2 + 2p-4 + 2p-6...),

where the product is taken over all prime numbers, and for every p, the sum is infinite. This formula follows from the Fundamental Theorem of Arithmetic (FTA): every natural number n may be written uniquely as a product of powers of [omega](n) prime factors.

Now, we have:

1+ 2p-2 + 2p-4 + 2p-6... = (1 + p-2) (1+ p-2 + p-4 + p-6...) = (1+ p-2)/(1- p-2) = (1- p-4)/(1- p-2)2,

so
S = [prod](1- p-4) / [prod](1- p-2)2 = ([sum]n-2)2 / ([sum]n-4) = [zeta]2(2)/[zeta](4).

This uses the identity (known already to Euler) [sum]n-s = [prod](1- p-s)-1, which is yet another consequence of FTA.
[smiley=blacksquare.gif]
Title: Re: Sum over the rationals
Post by Aryabhatta on Jun 17th, 2004, 7:07am

on 06/14/04 at 06:04:21, Barukh wrote:
Here’s another solution of the original problem.

S = [sum]n2[omega](n)n-2 = [prod] p(1+ 2p-2 + 2p-4 + 2p-6...),

where the product is taken over all prime numbers, and for every p, the sum is infinite.


Nice!  :D


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board