Movatterモバイル変換

[0]ホーム

Jump to content

Square-free integer

Edit links

From Wikipedia, the free encyclopedia

Number without repeated prime factors

10 is square-free, as its divisors greater than 1 are 2, 5, and 10, none of which is square (the first few squares being 1, 4, 9, and 16)

Square-free integers up to 120 remain after eliminating multiples of squares of primes up to √120

Inmathematics, asquare-free integer (orsquarefree integer) is aninteger that isdivisible by nosquare number other than 1. That is, itsprime factorization has exactly one factor for each prime that appears in it. For example,10 = 2 ⋅ 5 is square-free, but18 = 2 ⋅ 3 ⋅ 3 is not, because 18 is divisible by9 = 3². The smallest positive square-free numbers are

1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39, ... (sequenceA005117 in theOEIS)

Square-free factorization

[edit]

Every positive integer $n {\displaystyle n}$ can be factored in a unique way as $n=\prod _{i=1}^{k}q_{i}^{i},$ where the $q_{i}$ different from one are square-free integers that arepairwise coprime.This is called thesquare-free factorization ofn.

To construct the square-free factorization, let $n=\prod _{j=1}^{h}p_{j}^{e_{j}}$ be theprime factorization of $n {\displaystyle n}$ , where the $p_{j}$ are distinctprime numbers. Then the factors of the square-free factorization are defined as $q_{i}=\prod _{j:e_{j}=i}p_{j}.$

An integer is square-free if and only if $q_{i}=1$ for all $i>1$ . An integer greater than one is the $k {\displaystyle k}$ th power of another integer if and only if $k {\displaystyle k}$ is a divisor of all $i {\displaystyle i}$ such that $q_{i}\neq 1.$

The use of the square-free factorization of integers is limited by the fact that its computation is as difficult as the computation of the prime factorization. More precisely every knownalgorithm for computing a square-free factorization computes also the prime factorization. This is a notable difference with the case ofpolynomials for which the same definitions can be given, but, in this case, thesquare-free factorization is not only easier to compute than the complete factorization, but it is the first step of all standard factorization algorithms.

Square-free factors of integers

[edit]

Theradical of an integer is its largest square-free factor, that is $\textstyle \prod _{i=1}^{k}q_{i}$ with notation of the preceding section. An integer is square-freeif and only if it is equal to its radical.

Every positive integer $n {\displaystyle n}$ can be represented in a unique way as the product of apowerful number (that is an integer such that is divisible by the square of every prime factor) and a square-free integer, which arecoprime. In this factorization, the square-free factor is $q_{1},$ and the powerful number is $\textstyle \prod _{i=2}^{k}q_{i}^{i}.$

Thesquare-free part of $n {\displaystyle n}$ is $q_{1},$ which is the largest square-free divisor $k {\displaystyle k}$ of $n {\displaystyle n}$ that is coprime with $n/k$ . The square-free part of an integer may be smaller than the largest square-free divisor, which is $\textstyle \prod _{i=1}^{k}q_{i}.$

Any arbitrary positive integer $n {\displaystyle n}$ can be represented in a unique way as the product of asquare and a square-free integer: $n=m^{2}k$ In this factorization, $m {\displaystyle m}$ is the largest divisor of $n {\displaystyle n}$ such that $m^{2}$ is a divisor of $n {\displaystyle n}$ .

In summary, there are three square-free factors that are naturally associated to every integer: the square-free part, the above factor $k {\displaystyle k}$ , and the largest square-free factor. Each is a factor of the next one. All are easily deduced from theprime factorization or the square-free factorization: if $n=\prod _{i=1}^{h}p_{i}^{e_{i}}=\prod _{i=1}^{k}q_{i}^{i}$ are the prime factorization and the square-free factorization of $n {\displaystyle n}$ , where $p_{1},\ldots ,p_{h}$ are distinct prime numbers, then the square-free part is $\prod _{e_{i}=1}p_{i}=q_{1},$ The square-free factor such the quotient is a square is $\prod _{e_{i}{\text{ odd}}}p_{i}=\prod _{i{\text{ odd}}}q_{i},$ and the largest square-free factor is $\prod _{i=1}^{h}p_{i}=\prod _{i=1}^{k}q_{i}.$

For example, if $n=75600=2^{4}\cdot 3^{3}\cdot 5^{2}\cdot 7,$ one has $q_{1}=7,\;q_{2}=5,\;q_{3}=3,\;q_{4}=2.$ The square-free part is7, the square-free factor such that the quotient is a square is3 ⋅ 7 = 21, and the largest square-free factor is2 ⋅ 3 ⋅ 5 ⋅ 7 = 210.

No algorithm is known for computing any of these square-free factors which is faster than computing the complete prime factorization. In particular, there is no knownpolynomial-time algorithm for computing the square-free part of an integer, or even fordetermining whether an integer is square-free.^[1] In contrast, polynomial-time algorithms are known forprimality testing.^[2] This is a major difference between the arithmetic of the integers, and the arithmetic of theunivariate polynomials, as polynomial-time algorithms are known forsquare-free factorization of polynomials (in short, the largest square-free factor of a polynomial is its quotient by thegreatest common divisor of the polynomial and itsformal derivative).^[3]

Equivalent characterizations

[edit]

A positive integer $n {\displaystyle n}$ is square-free if and only if in theprime factorization of $n {\displaystyle n}$ , no prime factor occurs with an exponent larger than one. Another way of stating the same is that for every primefactor $p {\displaystyle p}$ of $n {\displaystyle n}$ , the prime $p {\displaystyle p}$ does not evenly divide $n/p$ . Also $n {\displaystyle n}$ is square-free if and only if in every factorization $n=ab$ , the factors $a {\displaystyle a}$ and $b {\displaystyle b}$ arecoprime. An immediate result of this definition is that all prime numbers are square-free.

A positive integer $n {\displaystyle n}$ is square-free if and only if allabelian groups oforder $n {\displaystyle n}$ areisomorphic, which is the case if and only if any such group iscyclic. This follows from the classification offinitely generated abelian groups.

A integer $n {\displaystyle n}$ is square-free if and only if thefactor ring $\mathbb {Z} /n\mathbb {Z}$ (seemodular arithmetic) is aproduct offields. This follows from theChinese remainder theorem and the fact that a ring of the form $\mathbb {Z} /k\mathbb {Z}$ is a field if and only if $k {\displaystyle k}$ is prime.

For every positive integer $n {\displaystyle n}$ , the set of all positive divisors of $n {\displaystyle n}$ becomes apartially ordered set if we usedivisibility as the order relation. This partially ordered set is always adistributive lattice. It is aBoolean algebra if and only if $n {\displaystyle n}$ is square-free.

A positive integer $n {\displaystyle n}$ is square-freeif and only if $\mu (n)\neq 0$ , where $\mu$ denotes theMöbius function.

Dirichlet series

[edit]

The absolute value of the Möbius function is theindicator function for the square-free integers – that is,|μ(n)| is equal to 1 ifn is square-free, and 0 if it is not. TheDirichlet series of this indicator function is

\sum _{n=1}^{\infty }{\frac {|\mu (n)|}{n^{s}}}={\frac {\zeta (s)}{\zeta (2s)}},

whereζ(s) is theRiemann zeta function. This follows from theEuler product

{\frac {\zeta (s)}{\zeta (2s)}}=\prod _{p}{\frac {(1-p^{-2s})}{(1-p^{-s})}}=\prod _{p}(1+p^{-s}),

where the products are taken over the prime numbers.

Distribution

[edit]

LetQ(x) denote the number of square-free integers between 1 andx (OEIS: A013928 shifting index by 1). For largen, 3/4 of the positive integers less thann are not divisible by 4, 8/9 of these numbers are not divisible by 9, and so on. Because these ratios satisfy themultiplicative property (this follows fromChinese remainder theorem), we obtain the approximation:

{\begin{aligned}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{aligned}}

This argument can be made rigorous for getting the estimate (usingbig O notation)

Q(x)={\frac {6x}{\pi ^{2}}}+O\left({\sqrt {x}}\right).

Sketch of a proof: the above characterization gives

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 ;

observing that the last summand is zero for $d>{\sqrt {x}}$ , it follows that

Q(x)=\sum _{d\leq {\sqrt {x}}}\mu (d)\left\lfloor {\frac {x}{d^{2}}}\right\rfloor

{\begin{aligned}{\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{aligned}}

By exploiting the largest known zero-free region of the Riemann zeta functionArnold Walfisz improved the approximation to^[4]

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

for some positive constantc.

Under theRiemann hypothesis, the error term can be reduced to^[5]

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

In 2015 the error term was further reduced (assuming also Riemann hypothesis) to^[6]

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

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

\lim _{x\to \infty }{\frac {Q(x)}{x}}={\frac {6}{\pi ^{2}}}\approx 0.6079

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

Likewise, ifQ(x,n) denotes the number ofn-free integers (e.g. 3-free integers being cube-free integers) between 1 andx, one can show^[7]

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

Since a multiple of 4 must have a square factor 4=2², it cannot occur that four consecutive integers are all square-free. On the other hand, there exist infinitely many integersn for which 4n +1, 4n +2, 4n +3 are all square-free. Otherwise, observing that 4n and at least one of 4n +1, 4n +2, 4n +3 among four could be non-square-free for sufficiently largen, half of all positive integers minus finitely many must be non-square-free and therefore

Q(x)\leq {\frac {x}{2}}+C

for some constantC,

contrary to the above asymptotic estimate for $Q(x)$ .

There exist sequences of consecutive non-square-free integers of arbitrary length. Indeed, for every tuple(p₁, ...,p_l) of distinct primes, theChinese remainder theorem guarantees the existence of ann that satisfies the simultaneous congruence

n\equiv -i{\pmod {p_{i}^{2}}}\qquad (i=1,2,\ldots ,l).

Eachn +i is then divisible byp²
_i.^[8] On the other hand, the above-mentioned estimate $Q(x)=6x/\pi ^{2}+O\left({\sqrt {x}}\right)$ implies that, for some constantc, there always exists a square-free integer betweenx and $x+c{\sqrt {x}}$ for positivex. Moreover, an elementary argument allows us to replace $x+c{\sqrt {x}}$ by $x+cx^{1/5}\log x.$ ^[9] Theabc conjecture would allow $x+x^{o(1)}$ .^[10]

Computation ofQ(x)

[edit]

The squarefree integers≤x can be identified and counted inÕ(x) time by using a modifiedSieve of Eratosthenes. If onlyQ(x) is desired, and not a list of the numbers that it counts, then (1) can be used to computeQ(x) inÕ(√x) time. The largest known value ofQ(x), forx = 10³⁶, was computed by Jakub Pawlewicz in 2011 using an algorithm that achievesÕ(x^2/5) time,^[11] and an algorithm takingÕ(x^1/3) time has been outlined but not implemented.^[12]^: §5.5

Table ofQ(x),⁠6/π²⁠x, andR(x)

[edit]

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

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

$x {\displaystyle x}$	$Q(x)$	${\frac {6}{\pi ^{2}}}x$	$R(x)$
10	7	6.1	0.9
10²	61	60.8	0.2
10³	608	607.9	0.1
10⁴	6,083	6,079.3	3.7
10⁵	60,794	60,792.7	1.3
10⁶	607,926	607,927.1	−1.3
10⁷	6,079,291	6,079,271.0	20.0
10⁸	60,792,694	60,792,710.2	−16.2
10⁹	607,927,124	607,927,101.9	22.1
10¹⁰	6,079,270,942	6,079,271,018.5	−76.5
10¹¹	60,792,710,280	60,792,710,185.4	94.6
10¹²	607,927,102,274	607,927,101,854.0	420.0
10¹³	6,079,271,018,294	6,079,271,018,540.3	−246.3
10¹⁴	60,792,710,185,947	60,792,710,185,402.7	544.3
10¹⁵	607,927,101,854,103	607,927,101,854,027.0	76.0

$R(x)$ changes its sign infinitely often as $x {\displaystyle x}$ tends to infinity.^[13]

The absolute value of $R(x)$ is astonishingly small compared with $x {\displaystyle x}$ .

Encoding as binary numbers

[edit]

If we represent a square-free number as the infinite product

\prod _{n=0}^{\infty }(p_{n+1})^{a_{n}},a_{n}\in \lbrace 0,1\rbrace ,{\text{ and }}p_{n}{\text{ is the }}n{\text{th prime}},

then we may take those $a_{n}$ and use them as bits in a binary number with the encoding

\sum _{n=0}^{\infty }{a_{n}}\cdot 2^{n}.

The square-free number 42 has factorization2 × 3 × 7, or as an infinite product2¹ · 3¹ · 5⁰ · 7¹ · 11⁰ · 13⁰ ··· Thus the number 42 may be encoded as the binary sequence...001011 or 11 decimal. (The binary digits are reversed from the ordering in the infinite product.)

Since the prime factorization of every number is unique, so also is every binary encoding of the square-free integers.

The converse is also true. Since every positive integer has a unique binary representation it is possible to reverse this encoding so that they may be decoded into a unique square-free integer.

Again, for example, if we begin with the number 42, this time as simply a positive integer, we have its binary representation101010. This decodes to2⁰ · 3¹ · 5⁰ · 7¹ · 11⁰ · 13¹ = 3 × 7 × 13 = 273.

Thus binary encoding of squarefree numbers describes abijection between the nonnegative integers and the set of positive squarefree integers.

(See sequencesA019565,A048672 andA064273 in theOEIS.)

Erdős squarefree conjecture

[edit]

Thecentral binomial coefficient

{2n \choose n}

is never squarefree forn > 4. This was proven in 1985 for all sufficiently large integers byAndrás Sárközy,^[14] and for all integers > 4 in 1996 byOlivier Ramaré andAndrew Granville.^[15]

Squarefree core

[edit]

Let us call "t-free" a positive integer that has not-th power in its divisors. In particular, the 2-free integers are the square-free integers.

Themultiplicative function $\mathrm {core} _{t}(n)$ maps every positive integern to the quotient ofn by its largest divisor that is at-th power. That is,

\mathrm {core} _{t}(p^{e})=p^{e{\bmod {t}}}.

The integer $\mathrm {core} _{t}(n)$ ist-free, and everyt-free integer is mapped to itself by the function $\mathrm {core} _{t}.$

TheDirichlet generating function of the sequence $\left(\mathrm {core} _{t}(n)\right)_{n\in \mathbb {N} }$ is

\sum _{n\geq 1}{\frac {\mathrm {core} _{t}(n)}{n^{s}}}={\frac {\zeta (ts)\zeta (s-1)}{\zeta (ts-t)}}

See alsoOEIS: A007913 (t=2),OEIS: A050985 (t=3) andOEIS: A053165 (t=4).

Notes

[edit]

^Adleman, Leonard M.; McCurley, Kevin S. (1994). "Open problems in number theoretic complexity, II". In Adleman, Leonard M.; Huang, Ming-Deh A. (eds.).Algorithmic Number Theory, First International Symposium, ANTS-I, Ithaca, NY, USA, May 6–9, 1994, Proceedings. Lecture Notes in Computer Science. Vol. 877. Springer. pp. 291–322.doi:10.1007/3-540-58691-1_70.ISBN 978-3-540-58691-3.
^Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (1 September 2004)."PRIMES is in P"(PDF).Annals of Mathematics.160 (2):781–793.doi:10.4007/annals.2004.160.781.ISSN 0003-486X.MR 2123939.Zbl 1071.11070.
^Richards, Chelsea (2009).Algorithms for factoring square-free polynomials over finite fields(PDF) (Master's thesis). Canada: Simon Fraser University.
^Walfisz, A. (1963).Weylsche Exponentialsummen in der neueren Zahlentheorie. Berlin:VEB Deutscher Verlag der Wissenschaften.
^Jia, Chao Hua. "The distribution of square-free numbers",Science in China Series A: Mathematics36:2 (1993), pp. 154–169. Cited in Pappalardi 2003,A Survey onk-freeness; also see Kaneenika Sinha, "Average orders of certain arithmetical functions Archived 14 February 2012 at theWayback Machine",Journal of the Ramanujan Mathematical Society21:3 (2006), pp. 267–277.
^Liu, H.-Q. (2016)."On the distribution of squarefree numbers".Journal of Number Theory.159:202–222.doi:10.1016/j.jnt.2015.07.013.
^Linfoot, E. H.; Evelyn, C. J. A. (1929)."On a Problem in the Additive Theory of Numbers".Mathematische Zeitschrift.30:443–448.doi:10.1007/BF01187781.S2CID 120604049.
^Parent, D. P. (1984).Exercises in Number Theory. Problem Books in Mathematics.Springer-Verlag New York.doi:10.1007/978-1-4757-5194-9.ISBN 978-1-4757-5194-9.
^Filaseta, Michael; Trifonov, Ognian (1992). "On gaps between squarefree numbers. II".Journal of the London Mathematical Society. Second Series.45 (2):215–221.doi:10.1112/jlms/s2-45.2.215.MR 1171549.
^Granville, Andrew (1998). "ABC allows us to count squarefrees".Int. Math. Res. Not.1998 (19):991–1009.doi:10.1155/S1073792898000592.{{cite journal}}: CS1 maint: unflagged free DOI (link)
^Pawlewicz, Jakub (2011). "Counting Square-Free Numbers".arXiv:1107.4890 [math.NT].
^Hirsch, Dean; Kessler, Ido; Mendlovic, Uri (2024)."Computingπ(N): An elementary approach inÕ(√N) time".Mathematics of Computation.arXiv:2212.09857.doi:10.1090/mcom/4039.ISSN 0025-5718.
^Minoru, Tanaka (1979)."Experiments concerning the distribution of squarefree numbers".Proceedings of the Japan Academy, Series A, Mathematical Sciences.55 (3).doi:10.3792/pjaa.55.101.S2CID 121862978.
^Sárközy, A. (1985)."On divisors of binomial coefficients. I".Journal of Number Theory.20 (1):70–80.doi:10.1016/0022-314X(85)90017-4.MR 0777971.
^Ramaré, Olivier; Granville, Andrew (1996). "Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients".Mathematika.43 (1):73–107.doi:10.1112/S0025579300011608.

References

[edit]

Shapiro, Harold N. (1983).Introduction to the theory of numbers.Oxford University Press Dover Publications.ISBN 978-0-486-46669-9.
Granville, Andrew; Ramaré, Olivier (1996). "Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients".Mathematika.43:73–107.CiteSeerX 10.1.1.55.8.doi:10.1112/S0025579300011608.MR 1401709.Zbl 0868.11009.
Guy, Richard K. (2004).Unsolved problems in number theory (3rd ed.).Springer-Verlag.ISBN 978-0-387-20860-2.Zbl 1058.11001.
"OEIS Wiki". Retrieved24 September 2021.

v t e Divisibility-based sets of integers
Overview	Integer factorization Divisor Unitary divisor Divisor function Prime factor Fundamental theorem of arithmetic
Factorization forms	Prime Composite Semiprime Pronic Sphenic Square-free Powerful Perfect power Achilles Smooth Regular Rough Unusual
Constrained divisor sums	Perfect Almost perfect Quasiperfect Multiply perfect Hemiperfect Hyperperfect Superperfect Unitary perfect Semiperfect Practical Descartes Erdős–Nicolas
With many divisors	Abundant Primitive abundant Highly abundant Superabundant Colossally abundant Highly composite Superior highly composite Weird
Aliquot sequence-related	Untouchable Amicable (Triple) Sociable Betrothed
Base-dependent	Equidigital Extravagant Frugal Harshad Polydivisible Smith
Other sets	Arithmetic Deficient Friendly Solitary Sublime Harmonic divisor Refactorable Superperfect