15
$\begingroup$

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 < q_n < (\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| < f(n)$$ for sublinear $f$ would be preferable (and should be possible; squarefree numbers are fairly well-behaved).

I'm sure this is in some standard reference but I haven't found it. Ideas?


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.

$\endgroup$
  • $\begingroup$ How big an n will you need? If n has 20 or fewer digits you can probably preprocess most of what you need and store it in a not very large table.. If you need n up to 100 digits, how sublinear/approximate do you want? Gerhard "Ask Me About System Design" Paseman, 2011.06.01 $\endgroup$ – Gerhard Paseman Jun 2 '11 at 3:15
  • $\begingroup$ @Gerhard Paseman: 40 to 50 digits should suffice. $\endgroup$ – Charles Jun 2 '11 at 15:03
17
$\begingroup$

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)| < 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} < 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.

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 < q_n < \zeta(2)n + 5\sqrt n $$ for $n\ge144$ (that is, for all squarefree numbers exceeding 230).

| cite | improve this answer | |
$\endgroup$
10
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I know of the $\ll\sqrt x$ asymptotic, but not of Jia's paper. Thanks! $\endgroup$ – Charles Jun 2 '11 at 14:49
10
$\begingroup$

Result

$$ \zeta(2)n - 0.058377\sqrt n < q_n < \zeta(2)n + 0.058377\sqrt n $$ for all $n\ge268293.$ For smaller values of $n$ you can use $$ \zeta(2)n - 36 < q_n < \zeta(2)n + 33 $$ which actually holds for $1 \le n \le 696017.$

Here's a chart of the residuals below 268293. Yellow and gray are the upper and lower bounds for this range (-36 to +33) and hence never cross 0. Red and blue and the upper and lower bounds for larger numbers ($\pm\,0.058377\sqrt n$) which cross 0 several times. There are tick marks on the x-axis every 25,000.

Residual chart

Proof

Let $$ Q(x):=\sum_{n\le x}\mu(n)^2 $$ be the number of squarefree numbers up to $x.$ Cohen, Dress, & El Marraki [2] (improving on Cohen & Dress 1) prove that $$ \left|Q(x)-\frac{x}{\zeta(2)}\right| < 0.02767\sqrt x $$ for $x\ge438653.$ So $$ \left|Q(\zeta(2)x)-\frac{\zeta(2)x}{\zeta(2)}\right| < 0.02767\sqrt{\zeta(2)x} < 0.0354882\sqrt x $$ for $x\ge266079.$ We want $Q(x) \ge n$ so we need a slightly larger argument. Choosing $\zeta(2)n + k\sqrt n$ (where $k$ is to be chosen later) we get $$ Q\left(\zeta(2)n + k\sqrt n\right) > n + \sqrt n\left(\frac{k}{\zeta(2)} - 0.02767\sqrt{\zeta(2) + k/\sqrt n}\right) $$ and so the goal is to choose a small $k$ such that $$ \frac{k}{\zeta(2)} \ge 0.02767\sqrt{\zeta(2) + k/\sqrt N} $$ for all $N\ge n$, which happens just when $$ k \ge \frac{c}{2\sqrt n}\left(c\zeta(2)^2+\zeta(2)^2\sqrt{4n/\zeta(2)+c^2}\right) $$ (with $c=0.02767$ for brevity). Choosing $n=10^6$ shows that $k=0.058377$ is admissible; substituting this value gives $$ Q\left(\zeta(2)n + 0.058377\sqrt n\right) > n + \sqrt n\left(\frac{0.058377}{\zeta(2)} - 0.02767\sqrt{\zeta(2) + 0.058377/\sqrt n}\right) > n $$ as desired. Checking up to that bound reveals that this works for all $n\ge268293.$ Similar calculations in the other direction complete the proof; in that direction only $n\ge217502$ is needed.


1 H. Cohen and F. Dress, Estimations numériques du reste de la fonction sommatoire relative aux entiers sans facteur carré, Colloque de théorie analytique des nombres "Jean Coquet": proceedings journées SMF-CNRS, CIRM, Marseille (Septembre 1985), pp. 73–76.

[2] Henri Cohen, Francois Dress, and Mohamed El Marraki, Explicit estimates for summatory functions linked to the Möbius μ-function, Functiones et Approximatio Commentarii Mathematici 37 (2007), part 1, pp. 51–63.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ It is quite nice to see such explicit formulae. Can you say when (for small values of n) the endpoints are achieved (e.g. when q_n is 35 below the expected value)? Gerhard "Likes Studying Explicit Number Theory" Paseman, 2018.01.18. $\endgroup$ – Gerhard Paseman Jan 18 '18 at 15:30
  • 1
    $\begingroup$ @GerhardPaseman I added a chart. The residuals are below -35 for some values in the range $q_{213211}=350683$ to $q_{213474}=351115$ and above 32 for some values in the range $q_{264872}=435729$ to $q_{265996}=437578.$ $\endgroup$ – Charles Feb 15 '18 at 21:11
5
$\begingroup$

The "Handbook of Number Theory" by Sandor, Mitrinovic and Crstici, page 201 gives $Q(x)\ge 53x/88$, where $Q(x)$ is the number of square free positive integers less than or equal to $x$. This implies $q_n\le 88n/53$. They cite "The Schnirelmann Density of the Squarefree Integers", K. Rogers, Proc. Am. Math. Soc. 15, 1964

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.