Elementary proof of lower bound for number of squarfree naturals not exceeding $n$

50 Views Asked by At

Denote with $Q(N)$ the number of squarefree naturals not exceeding $N$. I want to prove, using elementary arguments (without Mobius function), that for $N \ge 7$: $$Q(N) \ge \frac{N}{2}$$

Now, we know that a squarefree number $k$ can be written like $k = p_1p_2\ldots p_l$ where $p_1$ to $p_l$ are all distinct primes. This might help us carry out the inductive step but i don't how to approach it.

Can someone give a hint, please?

1

There are 1 best solutions below

0
On BEST ANSWER

Following Daniel Fischer's gentle nudge, I rewrite the (previously completely wrong) answer (because I cannot delete an accepted answer)

Let's count the numbers up to $N$ that are not squarefree. Any such number is divisible by $p^2$ for at least one prime $p$. This way, each prime $p$ makes at most $\lfloor \frac N{p^2}\rfloor$ of the integers up to $N$ non-squarefree. We conclude that $$ Q(N)\ge N-\sum_{p}\left\lfloor \frac N{p^2}\right\rfloor>N-N\cdot\sum_p\frac1{p^2}.$$ (This is somewhat wasteful as we doubly subtract many numbers, for example all multiples of $36$).

Hence it suffices to show that $\sum_p\frac1{p^2}<\frac12$.

Note that for $m>3$ $$ \begin{align}\sum_{k=0}^\infty\frac1{(6k+m)^2}&<\sum_{k=0}^\infty\frac1{(6k+m)^2-9}\\&=\frac16\sum_{k=0}^\infty\left(\frac1{6k+m-3}-\frac1{6k+m+3}\right)\\&=\frac16\cdot\frac1{m-3}\end{align}$$ by telescoping. Because all primes $>3$ are of the form $6k\pm1$, we get the bound$$ \begin{align}\sum_{p\text{ prime}}\frac1{p^2}&<\frac14+\frac19+\sum_{k=0}^\infty\frac1{(6k+5)^2}+\sum_{k=0}^\infty\frac1{(6k+7)^2}\\&<\frac 14+\frac 19+\frac1{12}+\frac1{24}\\ &=\frac{35}{72}\\ &<\frac12, \end{align}$$ as desired. (Remark: the actual value of the series is $\approx 0.45225$)