Editing Square-free integer (section)

==Distribution==
Let ''Q''(''x'') denote the number of square-free integers between 1 and ''x'' ({{OEIS2C|A013928}} shifting index by 1). For large ''n'', 3/4 of the positive integers less than ''n'' are not divisible by 4, 8/9 of these numbers are not divisible by 9, and so on. Because these ratios satisfy the [[multiplicative function|multiplicative property]] (this follows from [[Chinese remainder theorem]]), we obtain the approximation:

:<math>\begin{align}Q(x) &\approx x\prod_{p\ \text{prime}} \left(1-\frac{1}{p^2}\right) = x\prod_{p\ \text{prime}} \frac{1}{(1-\frac{1}{p^2})^{-1}}\\
&=x\prod_{p\ \text{prime}} \frac{1}{1+\frac{1}{p^2}+\frac{1}{p^4}+\cdots} = \frac{x}{\sum_{k=1}^\infty \frac{1}{k^2}} = \frac{x}{\zeta(2)} = \frac{6x}{\pi^2}.\end{align}</math>

This argument can be made rigorous for getting the estimate (using [[big O notation]])

:<math>Q(x) =  \frac{6x}{\pi^2} + O\left(\sqrt{x}\right).</math>

''Sketch of a proof:'' the above characterization gives
:<math>Q(x)=\sum_{n\leq x} \sum_{d^2\mid n} \mu(d)=\sum_{d\leq x} \mu(d)\sum_{n\leq x, d^2\mid n}1=\sum_{d\leq x} \mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor;</math>
observing that the last summand is zero for <math>d>\sqrt{x}</math>, it follows that

{{NumBlk|:|<math>Q(x) = \sum_{d\leq\sqrt{x}} \mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor</math>|{{EquationRef|1}}}}

:<math>\begin{align} \phantom{Q(x)} &= \sum_{d\leq\sqrt{x}} \frac{x\mu(d)}{d^2}+O\left(\sum_{d\leq\sqrt{x}} 1\right)
=x\sum_{d\leq\sqrt{x}} \frac{\mu(d)}{d^2}+O(\sqrt{x})\\
&=x\sum_{d} \frac{\mu(d)}{d^2}+O\left(x\sum_{d>\sqrt{x}}\frac{1}{d^2}+\sqrt{x}\right)
=\frac{x}{\zeta(2)}+O(\sqrt{x}).
\end{align}</math>

By exploiting the largest known zero-free region of the Riemann zeta function [[Arnold Walfisz]] improved the approximation to<ref>{{cite book |last1=Walfisz |first1=A. |title=Weylsche Exponentialsummen in der neueren Zahlentheorie |date=1963 |publisher=[[VEB Deutscher Verlag der Wissenschaften]] |location=Berlin}}</ref>
:<math>Q(x) = \frac{6x}{\pi^2} + O\left(x^{1/2}\exp\left(-c\frac{(\log x)^{3/5}}{(\log\log x)^{1/5}}\right)\right),</math>
for some positive constant {{math|''c''}}.

Under the [[Riemann hypothesis]], the error term can be reduced to<ref>Jia, Chao Hua. "The distribution of square-free numbers", ''Science in China Series A: Mathematics'' '''36''':2 (1993), pp. 154–169. Cited in Pappalardi 2003, [http://www.mat.uniroma3.it/users/pappa/papers/allahabad2003.pdf A Survey on ''k''-freeness]; also see Kaneenika Sinha, "[http://www.math.ualberta.ca/~kansinha/maxnrevfinal.pdf Average orders of certain arithmetical functions]", ''Journal of the Ramanujan Mathematical Society'' '''21''':3 (2006), pp. 267–277.</ref>
:<math>Q(x) = \frac{x}{\zeta(2)} + O\left(x^{17/54+\varepsilon}\right) = \frac{6}{\pi^2}x + O\left(x^{17/54+\varepsilon}\right).</math>

In 2015 the error term was further reduced (assuming also Riemann hypothesis) to<ref>{{cite journal |last1=Liu |first1=H.-Q. |title=On the distribution of squarefree numbers |journal=Journal of Number Theory |date=2016 |volume=159 |pages=202–222|doi=10.1016/j.jnt.2015.07.013 |doi-access=free }}</ref>

:<math>Q(x) =  \frac{6}{\pi^2}x + O\left(x^{11/35+\varepsilon}\right).</math>

The asymptotic/[[natural density]] of square-free numbers is therefore

:<math>\lim_{x\to\infty} \frac{Q(x)}{x} = \frac{6}{\pi^2}\approx 0.6079</math>

Therefore over 3/5 of the integers are square-free.

Likewise, if ''Q''(''x'',''n'') denotes the number of ''n''-free integers (e.g. 3-free integers being cube-free integers) between 1 and ''x'', one can show<ref>{{cite journal | first1 = E. H. | last1 = Linfoot | author-link1 = Edward Linfoot | first2 = C. J. A. | last2 = Evelyn | title = On a Problem in the Additive Theory of Numbers | journal = Mathematische Zeitschrift | date = 1929 | volume = 30 | pages = 443–448 | doi = 10.1007/BF01187781 | s2cid = 120604049 | url = https://gdz.sub.uni-goettingen.de/id/PPN266833020_0030?tify={%22pages%22:[437],%22view%22:%22info%22} }}</ref>
:<math>Q(x,n) = \frac{x}{\sum_{k=1}^\infty \frac{1}{k^n}} + O\left(\sqrt[n]{x}\right) = \frac{x}{\zeta(n)} + O\left(\sqrt[n]{x}\right).</math>

Since a multiple of 4 must have a square factor 4=2<sup>2</sup>, it cannot occur that four consecutive integers are all square-free. On the other hand, there exist infinitely many integers ''n'' for which 4''n'' +1, 4''n'' +2, 4''n'' +3 are all square-free. Otherwise, observing that 4''n'' and at least one of 4''n'' +1, 4''n'' +2, 4''n'' +3 among four could be non-square-free for sufficiently large ''n'', half of all positive integers minus finitely many must be non-square-free and therefore
:<math>Q(x) \leq \frac{x}{2}+C</math> for some constant ''C'',
contrary to the above asymptotic estimate for <math>Q(x)</math>.

There exist sequences of consecutive non-square-free integers of arbitrary length.  Indeed, for every tuple {{math|1=(''p''<sub>1</sub>, ..., ''p''<sub>''l''</sub>)}} of distinct primes, the [[Chinese remainder theorem]] guarantees the existence of an {{mvar|n}} that satisfies the simultaneous congruence
:<math>n\equiv -i\pmod{p_i^2} \qquad (i=1, 2, \ldots, l).</math>
Each {{math|1=''n'' + ''i''}} is then divisible by {{math|1=''p''{{su|b=''i''|p=2}}}}.<ref>{{cite book | last1= Parent | first1=D. P. |title=Exercises in Number Theory | publisher=[[Springer-Verlag]] New York | isbn=978-1-4757-5194-9 | url=https://www.springer.com/book/9780387960630 | doi=10.1007/978-1-4757-5194-9 | year=1984| series=Problem Books in Mathematics }}</ref> On the other hand, the above-mentioned estimate <math>Q(x) = 6x/\pi^2 + O\left(\sqrt{x}\right)</math> implies that, for some constant ''c'', there always exists a square-free integer between ''x'' and <math>x+c\sqrt{x}</math> for positive ''x''. Moreover, an elementary argument allows us to replace <math>x+c\sqrt{x}</math> by <math>x+cx^{1/5}\log x.</math><ref>{{cite journal
 | last1 = Filaseta | first1 = Michael
 | last2 = Trifonov | first2 = Ognian
 | doi = 10.1112/jlms/s2-45.2.215
 | issue = 2
 | journal = Journal of the London Mathematical Society
 | mr = 1171549
 | pages = 215–221
 | series = Second Series
 | title = On gaps between squarefree numbers. II
 | volume = 45
 | year = 1992}}</ref> The [[abc conjecture|''abc'' conjecture]] would allow <math>x+x^{o(1)}</math>.<ref>{{cite journal |last1=Granville |first1=Andrew |author-link=Andrew Granville |year=1998 |title=ABC allows us to count squarefrees |journal=Int. Math. Res. Not. |volume=1998 |issue=19 |pages=991–1009 |doi=10.1155/S1073792898000592 |doi-access=<!-- not free-->}}</ref>

=== Computation of {{Math|''Q''(''x'')}} ===
The squarefree integers {{Math|&leq; ''x''}} can be identified and counted in {{Math|[[big O notation|''Õ'']](''x'')}} time by using a modified [[Sieve of Eratosthenes]].  If only {{Math|''Q''(''x'')}} is desired, and not a list of the numbers that it counts, then ({{EquationNote|1}}) can be used to compute {{Math|''Q''(''x'')}} in {{Math|''Õ''({{radical|''x''}})}} time.  The largest known value of {{Math|''Q''(''x'')}}, for {{Math|1=''x'' = 10<sup>36</sup>}}, was computed by Jakub Pawlewicz in 2011 using an algorithm that achieves {{Math|''Õ''(''x''<sup>2/5</sup>)}} time,<ref>{{cite arXiv |eprint=1107.4890 |last1=Pawlewicz |first1=Jakub |title=Counting Square-Free Numbers |date=2011 |class=math.NT }}</ref> and an algorithm taking {{Math|''Õ''(''x''<sup>1/3</sup>)}} time has been outlined but not implemented.{{r|HirschKesslerMendlovic2024|at=&sect;5.5}}

===Table of ''Q''(''x''), {{Sfrac|6|π<sup>2</sup>}}''x'', and ''R''(''x'')   ===

The table shows how  <math> Q(x)</math> and <math>\frac{6}{\pi^2}x</math>  (with the latter rounded to one decimal place) compare at powers of 10.

<math> R(x) = Q(x) -\frac{6}{\pi^2}x </math> , also denoted as <math> \Delta(x) </math>.

:{| class="wikitable" style="text-align: right"
! <math> x </math>
! <math> Q(x) </math>
! <math>  \frac{6}{\pi^2}x</math>
!<math> R(x)</math>
|-
| 10
| 7
| 6.1
| 0.9
|-
| 10<sup>2</sup>
| 61
| 60.8
| 0.2
|-
| 10<sup>3</sup>
| 608
| 607.9
| 0.1
|-
| 10<sup>4</sup>
| 6,083
| 6,079.3
| 3.7
|-
| 10<sup>5</sup>
| 60,794
| 60,792.7
| 1.3
|-
| 10<sup>6</sup>
| 607,926
| 607,927.1
| {{font color|red|−1.3}}
|-
| 10<sup>7</sup>
| 6,079,291
| 6,079,271.0
| 20.0
|-
| 10<sup>8</sup>
| 60,792,694
| 60,792,710.2
| {{font color|red|−16.2}}
|-
| 10<sup>9</sup>
| 607,927,124
| 607,927,101.9
| 22.1
|-
| 10<sup>10</sup>
| 6,079,270,942
|  6,079,271,018.5
| {{font color|red|−76.5}}
|-
| 10<sup>11</sup>
| 60,792,710,280
| 60,792,710,185.4
| 94.6
|-
| 10<sup>12</sup>
| 607,927,102,274
|  607,927,101,854.0
| 420.0
|-
| 10<sup>13</sup>
| 6,079,271,018,294
| 6,079,271,018,540.3
| {{font color|red|−246.3}}
|-
| 10<sup>14</sup>
| 60,792,710,185,947
| 60,792,710,185,402.7
| 544.3
|-
| 10<sup>15</sup>
| 607,927,101,854,103
| 607,927,101,854,027.0
| 76.0
|-
|}
<math> R(x) </math> changes its sign infinitely often as <math> x </math> tends to infinity.<ref>{{cite journal |last1=Minoru |first1=Tanaka |title=Experiments concerning the distribution of squarefree numbers |journal=Proceedings of the Japan Academy, Series A, Mathematical Sciences |year=1979 |volume=55 |issue=3 |doi=10.3792/pjaa.55.101 |s2cid=121862978 |url=https://projecteuclid.org/euclid.pja/1195517398|doi-access=free }}</ref>

The absolute value of <math> R(x) </math> is astonishingly small compared with <math> x </math>.