[math-fun] Asymptotics of Moebius function
Dear Math Fun, Does anyone know the asymptotics for this sequence? (I did a crude estimate, but I have no confidence in it.) Thanks! Neil %I A070548 %S A070548 1,1,1,1,1,2,2,2,2,3,3,3,3,4,5,5,5,5,5,5,6,7,7,7,7,8,8,8,8,8,8,8,9,10, %T A070548 11,11,11,12,13,13,13,13,13,13,13,14,14,14,14,14,15,15,15,15,16,16,17, %U A070548 18,18,18,18,19,19,19,20,20,20,20,21,21,21,21,21,22,22,22,23,23,23,23 %N A070548 a(n) = Card{ k in range 1<=k<=n such that Moebius(k)=1 }. %C A070548 Moebius(k)=1 iff k is the product of an even number of distinct primes (cf. A008683). See A057627 for Moebius(k)=0. %H A070548 N. J. A. Sloane, <a href="http://www.research.att.com/~njas/sequences/b070548.txt">Table of n, a(n) for n = 1..10000</a> %o A070548 (PARI) for(n=1,150,print1(sum(i=1,n,if(moebius(i)-1,0,1)),",")) %Y A070548 Cf. A008683. Equals A072613(n) + 1. %K A070548 easy,nonn %O A070548 1,6 %A A070548 Benoit Cloitre (benoit7848c(AT)orange.fr), May 02 2002
You want something better than N * 3/pi^2? --Rich ________________________________________ From: math-fun-bounces@mailman.xmission.com [math-fun-bounces@mailman.xmission.com] On Behalf Of N. J. A. Sloane [njas@research.att.com] Sent: Wednesday, September 10, 2008 2:36 PM To: math-fun@mailman.xmission.com Cc: njas@research.att.com Subject: [math-fun] Asymptotics of Moebius function Dear Math Fun, Does anyone know the asymptotics for this sequence? (I did a crude estimate, but I have no confidence in it.) Thanks! Neil %I A070548 %S A070548 1,1,1,1,1,2,2,2,2,3,3,3,3,4,5,5,5,5,5,5,6,7,7,7,7,8,8,8,8,8,8,8,9,10, %T A070548 11,11,11,12,13,13,13,13,13,13,13,14,14,14,14,14,15,15,15,15,16,16,17, %U A070548 18,18,18,18,19,19,19,20,20,20,20,21,21,21,21,21,22,22,22,23,23,23,23 %N A070548 a(n) = Card{ k in range 1<=k<=n such that Moebius(k)=1 }. %C A070548 Moebius(k)=1 iff k is the product of an even number of distinct primes (cf. A008683). See A057627 for Moebius(k)=0. %H A070548 N. J. A. Sloane, <a href="http://www.research.att.com/~njas/sequences/b070548.txt">Table of n, a(n) for n = 1..10000</a> %o A070548 (PARI) for(n=1,150,print1(sum(i=1,n,if(moebius(i)-1,0,1)),",")) %Y A070548 Cf. A008683. Equals A072613(n) + 1. %K A070548 easy,nonn %O A070548 1,6 %A A070548 Benoit Cloitre (benoit7848c(AT)orange.fr), May 02 2002 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Here's a stupid estimate from me: I think it's known that sum of mu(n)/n^2 is 6/pi^2, and sum of |mu(n)| / n^2 is 15/pi^2 -- I don't know how to prove either of those, though, so maybe I'm wrong. This suggests that of the squarefree numbers, the proportion where mu is 1 can be found by (|mu| + mu)/2 / |mu|, which would be (15+6)/30 = 21/30 = 7/10 if my arithmetic here makes any sense. Of course I'm ignoring all kinds of stuff here, like the weighting by n^2 ... Then, since 6/pi^2 of all numbers are squarefree, I'd be saying that 21 / (5pi^2) = about 42% of all numbers have mu = 1, about 18% -1, and the remaining 40% or so have mu = 0. ... OK, looks like I'm totally wrong. http://www.maa.org/editorial/mathgames/mathgames_11_03_03.html says that 3/pi^2 is the limiting density (well, actually it says 3/n^2 is the limiting density, but I'm guessing that it's a bad scan of an article that said pi), so +1 and -1 occur equally often. Then I'm surprised that sum of mu(n) / n^2 is so big, instead of being close to 0. What is wrong with my intuition here? Why wasn't my handwavy argument at least close? http://projecteuclid.org/DPubS?verb=Display&version=1.0&service=UI&handle=eu... doesn't give asymptotics but it does give the sum up to 10^16 being close-ish to 0. --Joshua On Wed, Sep 10, 2008 at 1:36 PM, N. J. A. Sloane <njas@research.att.com> wrote:
Dear Math Fun, Does anyone know the asymptotics for this sequence? (I did a crude estimate, but I have no confidence in it.) Thanks! Neil
%I A070548 %S A070548 1,1,1,1,1,2,2,2,2,3,3,3,3,4,5,5,5,5,5,5,6,7,7,7,7,8,8,8,8,8,8,8,9,10, %T A070548 11,11,11,12,13,13,13,13,13,13,13,14,14,14,14,14,15,15,15,15,16,16,17, %U A070548 18,18,18,18,19,19,19,20,20,20,20,21,21,21,21,21,22,22,22,23,23,23,23 %N A070548 a(n) = Card{ k in range 1<=k<=n such that Moebius(k)=1 }. %C A070548 Moebius(k)=1 iff k is the product of an even number of distinct primes (cf. A008683). See A057627 for Moebius(k)=0. %H A070548 N. J. A. Sloane, <a href="http://www.research.att.com/~njas/sequences/b070548.txt">Table of n, a(n) for n = 1..10000</a> %o A070548 (PARI) for(n=1,150,print1(sum(i=1,n,if(moebius(i)-1,0,1)),",")) %Y A070548 Cf. A008683. Equals A072613(n) + 1. %K A070548 easy,nonn %O A070548 1,6 %A A070548 Benoit Cloitre (benoit7848c(AT)orange.fr), May 02 2002
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Just for the fun of it, let's use Riemann's hypothesis. The proof that the proportion of squarefree numbers <= x is around 6/pi^2*x + O(sqrt(x)) is not too hard, if I remember correctly. Assuming the Riemann hypothesis to be true, we can use an equivalent formulation (which is given by formula (4) in http://mathworld.wolfram.com/MertensConjecture.html). This gives us that the desired quantity <= x is around 3/pi^2*x + O(x^(1/2 + e)). Stefan
participants (4)
-
Joshua Zucker -
N. J. A. Sloane -
Schroeppel, Richard -
Stefan Steinerberger