Bounds on squarefree numbers - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T10:15:23Z http://mathoverflow.net/feeds/question/66701 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/66701/bounds-on-squarefree-numbers Bounds on squarefree numbers Charles 2011-06-02T01:43:23Z 2011-06-02T07:08:51Z <p>Let $q_1,q_2,\ldots$ denote the squarefree integers 1, 2, 3, 5, .... What effective bounds are known for $q_n$? Clearly $$q_n\sim\zeta(2)n$$ but I need hard inequalities. Of course from the above there exist $\varepsilon,N$ with $$(\zeta(2)-\varepsilon)n &lt; q_n &lt; (\zeta(2)+\varepsilon)n$$ for all $n>N,$ but I do not have proven values for $\varepsilon,N$. Of course $$|q_n-\zeta(2)n| &lt; f(n)$$ for sublinear $f$ would be preferable (and should be possible; squarefree numbers are fairly well-behaved).</p> <p>I'm sure this is in some standard reference but I haven't found it. Ideas?</p> <hr> <p>For those interested, my actual goal is to find a reasonable bound for the powerful (2-full) numbers for computational purposes. Their asymptotic growth is tightly constrained but for numerical computations I would prefer worst-case bounds that I can trust rather than a heuristic that says the error probably won't be much more than, say, 10 times the O-term.</p> http://mathoverflow.net/questions/66701/bounds-on-squarefree-numbers/66707#66707 Answer by Mark Lewko for Bounds on squarefree numbers Mark Lewko 2011-06-02T05:17:41Z 2011-06-02T05:17:41Z <p>Let $Q(x)$ denote the number of square-free numbers less than $x$ than $Q(x) = x/\zeta(2) + E(x)$. An elementary argument gives that $E(x) \ll x^{1/2}$. This can be found in Hardy and Wright's Introduction to the Theory of Numbers (it is Theorem 333 in my copy). One should be able to easily work out explicit constants in that argument if that is what you need. The truth is that the error term is probably much smaller. There have been a number of improvements assuming Riemann hypothesis. I believe the current such record is $E(x) \ll_{\epsilon} x^{17/54+\epsilon}$ (see: Jia, Chao Hua. "The distribution of square-free numbers", Science in China Series A: Mathematics 36:2 (1993), pp. 154–169). </p> http://mathoverflow.net/questions/66701/bounds-on-squarefree-numbers/66711#66711 Answer by SJR for Bounds on squarefree numbers SJR 2011-06-02T06:34:33Z 2011-06-02T06:34:33Z <p>The "Handbook of Number Theory" by Sandor, Mitrinovic and Crstici, page 201 gives <code>$Q(x)\ge 53x/88$</code>, where <code>$Q(x)$</code> is the number of square free positive integers less than or equal to $x$. This implies <code>$q_n\le 88n/53$</code>. They cite "The Schnirelmann Density of the Squarefree Integers", K. Rogers, Proc. Am. Math. Soc. 15, 1964</p> http://mathoverflow.net/questions/66701/bounds-on-squarefree-numbers/66712#66712 Answer by Greg Martin for Bounds on squarefree numbers Greg Martin 2011-06-02T07:08:51Z 2011-06-02T07:08:51Z <p>Expanding upon the first part of Mark Lewko's answer: if $Q(x) = x/\zeta(2) + E(x)$, then we can quickly show that $|E(x)| &lt; 2(\sqrt x + 1)$ for $x\ge4$. Start from the fact that $\sum_{d^2\mid n} \mu(d)$ equals 1 if $n$ is squarefree and 0 otherwise. Then $$Q(x) = \sum_{n\le x} \sum_{d^2\mid n} \mu(d) = \sum_{d\le\sqrt x} \mu(d) \sum_{n\le x,~d^2\mid n} 1 = \sum_{d\le\sqrt x} \mu(d) \Big\lfloor \frac x{d^2} \Big\rfloor.$$ Since $|y-\lfloor y\rfloor| \le 1$, $$\bigg|Q(x) - x \sum_{d\le\sqrt x} \frac{\mu(d)}{d^2} \bigg| \le \sum_{d\le\sqrt x} |\mu(d)| \le \sqrt x.$$ Also, $\sum_{d=1}^\infty \mu(d)/d^2 = 1/\zeta(2)$, and so $$\bigg| \frac x{\zeta(2)} - x \sum_{d\le\sqrt x} \frac{\mu(d)}{d^2} \bigg| \le x \sum_{d>\sqrt x} \frac{|\mu(d)|}{d^2} &lt; x \int_{\sqrt x-1}^\infty \frac{dt}{t^2} = \frac x{\sqrt x-1} \le \sqrt x + 2$$ since $x\ge4$. Combining these two inequalities gives $|Q(x) - x/\zeta(2)| \le 2\sqrt x + 2$ as claimed.</p> <p>Applying this with $x=q_n$ (for some $n>3$) gives $|n-q_n/\zeta(2)| = |Q(q_n)-q_n/\zeta(2)| \le 2\sqrt{q_n}+2$, or $$q_n - 2\zeta(2)\sqrt{q_n} - 2\zeta(2) \le \zeta(2)n \le q_n + 2\zeta(2)\sqrt{q_n} + 2\zeta(2).$$ From this various inequalities can be derived: for example, $$\zeta(2)n - 5\sqrt n &lt; q_n &lt; \zeta(2)n + 5\sqrt n$$ for $n\ge144$ (that is, for all squarefree numbers exceeding 230).</p>