Re: [math-fun] mu question
Letting mu be the Moebius function, and nu be the Mertens function defined as
nu(n) = SUM(k = 1..n, mu(k))
Then I notice
[1] SUM(k = 1..n, mu(k)*[n/k]) = 1
[2] SUM(k = 1..n, nu([n/k])) = 1
where [x] is the floor of x. I wondered if there was any simple relationship linking [1] and [2], or perhaps some relationship to the
Sure, write the second sum as a double sum, using the definition of nu(-) , and then switch the order of summation.
Moebius transform
a(n) = SUM(d|n; b(d)) <=> b(n) = SUM(d|n; mu(n/d)*a(d)).
On 2/18/12, Michael Reid <reid@gauss.math.ucf.edu> wrote:
Letting mu be the Moebius function, and nu be the Mertens function defined as
nu(n) = SUM(k = 1..n, mu(k))
Then I notice
[1] SUM(k = 1..n, mu(k)*[n/k]) = 1
[2] SUM(k = 1..n, nu([n/k])) = 1
where [x] is the floor of x. I wondered if there was any simple relationship linking [1] and [2], or perhaps some relationship to the
Sure, write the second sum as a double sum, using the definition of nu(-) , and then switch the order of summation.
Moebius transform
a(n) = SUM(d|n; b(d)) <=> b(n) = SUM(d|n; mu(n/d)*a(d)).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Fred: Did you add anything here? Asking only because I have come to expect gems whenever you chime in. On 2/18/2012 4:33 PM, Fred lunnon wrote:
On 2/18/12, Michael Reid<reid@gauss.math.ucf.edu> wrote:
Letting mu be the Moebius function, and nu be the Mertens function defined as
nu(n) = SUM(k = 1..n, mu(k))
Then I notice
[1] SUM(k = 1..n, mu(k)*[n/k]) = 1
[2] SUM(k = 1..n, nu([n/k])) = 1
where [x] is the floor of x. I wondered if there was any simple relationship linking [1] and [2], or perhaps some relationship to the Sure, write the second sum as a double sum, using the definition of nu(-) , and then switch the order of summation.
Moebius transform
a(n) = SUM(d|n; b(d))<=> b(n) = SUM(d|n; mu(n/d)*a(d)).
General apologies to everybody --- the "Send" and "Back to Inbox" buttons are a bit too close for comfort on my mailer window, so I occasionally hit the wrong one. Apparently several people have met their partners on dating sites as a result of similar confusion --- can't see that happening to me here, though! WFL On 2/18/12, David Wilson <davidwwilson@comcast.net> wrote:
Fred:
Did you add anything here? Asking only because I have come to expect gems whenever you chime in.
On 2/18/2012 4:33 PM, Fred lunnon wrote:
On 2/18/12, Michael Reid<reid@gauss.math.ucf.edu> wrote:
Letting mu be the Moebius function, and nu be the Mertens function defined as
nu(n) = SUM(k = 1..n, mu(k))
Then I notice
[1] SUM(k = 1..n, mu(k)*[n/k]) = 1
[2] SUM(k = 1..n, nu([n/k])) = 1
where [x] is the floor of x. I wondered if there was any simple relationship linking [1] and [2], or perhaps some relationship to the Sure, write the second sum as a double sum, using the definition of nu(-) , and then switch the order of summation.
Moebius transform
a(n) = SUM(d|n; b(d))<=> b(n) = SUM(d|n; mu(n/d)*a(d)).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
So starting with x = SUM(k = 1..n; nu([n/k])) the definition of nu gives x = SUM(k = 1..n; SUM(j = 1..[n/k]; mu(j))) I couldn't see how to change the summation order, until I drew a picture, which showed me that {(j,k) : j <= [n/k]} = {(j,k) : k <= [n/j]} which is to say, the summation domain is symmetric with respect to j and k. So we can switch j and k, getting x = SUM(j = 1..n; SUM(k = 1..[n/j]; mu(j))) and evaluating the inner sum gives x = SUM(j = 1..n; mu(j) * [n/j]) which shows that the left sides of [1] and [2] are equal. The fact that the right sides of [1] and [2] are 1 would follow from a different partitioning of the summation domain, to wit {(j,k) : j <= [n/k]} = {(j,k) : j*k <= n} The we can reform x = SUM(k = 1..n; SUM(j = 1..[n/k]; mu(j))) to x = SUM(v = 1..n; SUM(jk = v; mu(j))) By a property of mu x = SUM(v = 1..n; 1 if v = 1, 0 otherwise) which simplifies to x = 1. Now that I understand it, I must believe that this sort of sum reordering is a standard trick in an analyst's bag thereof. I found [2] by accident, but seeing that it is a shallow consequence of known facts about the Moebius function, I would think someone must have noted it somewhere, though I don't find it in any of the publicly available web expositions of Merten's function. But it is a cute trick. For example, with harmonic function H(n) it gives SUM(k = 1..n; H(n)) = SUM(k = 1..n; [n/j]/j) On 2/18/2012 2:06 PM, Michael Reid wrote:
Letting mu be the Moebius function, and nu be the Mertens function defined as
nu(n) = SUM(k = 1..n, mu(k))
Then I notice
[1] SUM(k = 1..n, mu(k)*[n/k]) = 1
[2] SUM(k = 1..n, nu([n/k])) = 1
where [x] is the floor of x. I wondered if there was any simple relationship linking [1] and [2], or perhaps some relationship to the Sure, write the second sum as a double sum, using the definition of nu(-) , and then switch the order of summation.
Moebius transform
a(n) = SUM(d|n; b(d))<=> b(n) = SUM(d|n; mu(n/d)*a(d)).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
* David Wilson <davidwwilson@comcast.net> [Feb 19. 2012 07:28]:
[...]
Just because I stumbled on this one yesterday: Peter H. van der Kamp: On the Fourier transform of the greatest common divisor http://arxiv.org/abs/1201.3139
participants (4)
-
David Wilson -
Fred lunnon -
Joerg Arndt -
Michael Reid