Unchecked

Square-free integer

From Wikipedia
Jump to navigation Jump to search

In mathematics, a square-free integer (or squarefree integer) is an integer that is divisible by no square number other than 1. That is, its prime factorization has exactly one factor for each prime that appears in it. For example, 10 = 2 ⋅ 5 is square-free, but 18 = 2 ⋅ 3 ⋅ 3 is not, because 18 is divisible by 9 = 32. The smallest positive square-free numbers are Template:Bi

File:Composite number Cuisenaire rods 10.svg
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)
File:Squarefree numbers sieve.svg
Square-free integers up to 120 remain after eliminating multiples of squares of primes up to √120

Square-free factorization

[edit]

Every positive integer   can be factored in a unique way as Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n=\prod _{i=1}^{k}q_{i}^{i},} where the   different from 1 are square-free integers that are pairwise coprime. This is called the square-free factorization of n.

To construct the square-free factorization, let Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n=\prod _{j=1}^{h}p_{j}^{e_{j}}} be the prime factorization of  , where the   are distinct prime numbers. Then the factors of the square-free factorization are defined as  

An integer is square-free if and only if   for all  . An integer greater than one is the  th power of another integer if and only if   is a divisor of all   such that Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 known algorithm for computing a square-free factorization computes also the prime factorization. This is a notable difference with the case of polynomials for which the same definitions can be given, but, in this case, the square-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]

The square-free part of   is the product of all prime divisors of   whose exponent in the factorization of   is odd. Each positive integer   can be represented in a unique way as the product of a largest possible square and a square-free integer, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=m^2 k,} where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} is the square-free part of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} is the largest divisor of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m^2} is a divisor of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} .

Every positive integer Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} can be represented in a unique way as the product of a powerful number (that is an integer that is divisible by the square of every prime factor) and a square-free integer Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} . This Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} is the product of the primes that divide Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} only to the first power, and the powerful number is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n/s.}

The radical of an integer Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is its largest square-free factor, that is, the product of all prime divisors of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , which equals Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle \prod_{i=1}^k q_i} in the notation of the preceding section. The radical of an integer may be smaller than the square-free part; an integer is square-free if and only if it is equal to its radical.

In summary, there are three square-free factors that are naturally associated to every integer: the above factor Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s,} the square-free part, and the largest square-free factor. Each is a factor of the next one. All are easily deduced from the prime factorization or the square-free factorization: if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_1, \ldots, p_h} are distinct prime numbers, then the square-free part is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \prod_{e_i=1} p_i =q_1,} The square-free factor such the quotient is a square is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \prod_{e_i \text{ odd}} p_i=\prod_{i \text{ odd}} q_i,} and the largest square-free factor is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \prod_{i=1}^h p_i=\prod_{i=1}^k q_i.}

For example, if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=75600=2^4\cdot 3^3\cdot 5^2\cdot 7,} one has Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_1=7,\; q_2=5,\;q_3=3,\;q_4=2.} The square-free part is 7, the square-free factor such that the quotient is a square is 3 ⋅ 7 = 21, and the largest square-free factor is 2 ⋅ 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 known polynomial-time algorithm for computing the square-free part of an integer, or even for determining whether an integer is square-free.[1] In contrast, polynomial-time algorithms are known for primality testing.[2]

Equivalent characterizations

[edit]

A positive integer Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is square-free if and only if in the prime factorization of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , no prime factor occurs with an exponent larger than one. Another way of stating the same is that for every prime factor Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , the prime Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} does not evenly divide Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n/p} . Also Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is square-free if and only if in every factorization Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=ab} , the factors Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} are coprime. An immediate result of this definition is that all prime numbers are square-free.

A positive integer Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is square-free if and only if all abelian groups of order Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} are isomorphic, which is the case if and only if any such group is cyclic. This follows from the classification of finitely generated abelian groups.

A integer Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is square-free if and only if the factor ring Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}/n\mathbb{Z}} (see modular arithmetic) is a product of fields. This follows from the Chinese remainder theorem and the fact that a ring of the form Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}/k\mathbb{Z}} is a field if and only if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} is prime.

For every positive integer Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , the set of all positive divisors of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} becomes a partially ordered set if we use divisibility as the order relation. This partially ordered set is always a distributive lattice. It is a Boolean algebra if and only if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is square-free.

A positive integer Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is square-free if and only if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu(n)\ne 0} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu} denotes the Möbius function.

Dirichlet series

[edit]

The absolute value of the Möbius function is the indicator function for the square-free integers – that is, Template:Mabs is equal to 1 if n is square-free, and 0 if it is not. The Dirichlet series of this indicator function is

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{n=1}^{\infty}\frac{|\mu(n)|}{n^{s}} = \frac{\zeta(s)}{\zeta(2s)},}

where ζ(s) is the Riemann zeta function. This follows from the Euler product

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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]

Let Q(x) denote the number of square-free integers between 1 and x (Template:OEIS2C 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 property (this follows from Chinese remainder theorem), we obtain the approximation:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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}}

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q(x) = \frac{6x}{\pi^2} + O\left(\sqrt{x}\right).}

Sketch of a proof: the above characterization gives

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d>\sqrt{x}} , it follows that

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q(x) = \sum_{d\leq\sqrt{x}} \mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor}

 

 

 

 

(1)

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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}}

By exploiting the largest known zero-free region of the Riemann zeta function Arnold Walfisz improved the approximation to[3]

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 constant c.

Under the Riemann hypothesis, the error term can be reduced to[4]

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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[5]

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q(x) = \frac{6}{\pi^2}x + O\left(x^{11/35+\varepsilon}\right).}

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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, 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[6]

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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=22, it cannot occur that four consecutive integers are all square-free. On the other hand, there exist infinitely many integers n 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 large n, half of all positive integers minus finitely many must be non-square-free and therefore

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q(x) \leq \frac{x}{2}+C} for some constant C,

contrary to the above asymptotic estimate for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q(x)} .

There exist sequences of consecutive non-square-free integers of arbitrary length. Indeed, for every tuple (p1, ..., pl) of distinct primes, the Chinese remainder theorem guarantees the existence of an n that satisfies the simultaneous congruence

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\equiv -i\pmod{p_i^2} \qquad (i=1, 2, \ldots, l).}

Each n + i is then divisible by p2
i.[7] On the other hand, the above-mentioned estimate Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q(x) = 6x/\pi^2 + O\left(\sqrt{x}\right)} implies that, for some constant c, there always exists a square-free integer between x and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x+c\sqrt{x}} for positive x. Moreover, an elementary argument allows us to replace Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x+c\sqrt{x}} by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x+cx^{1/5}\log x.} [8] The abc conjecture would allow Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x+x^{o(1)}} .[9]

Computation of Q(x)

[edit]

The squarefree integers ≤ x can be identified and counted in Õ(x) time by using a modified Sieve of Eratosthenes. If only Q(x) is desired, and not a list of the numbers that it counts, then (1) can be used to compute Q(x) in Õ(√x) time. The largest known value of Q(x), for x = 1036, was computed by Jakub Pawlewicz in 2011 using an algorithm that achieves Õ(x2/5) time,[10] and an algorithm taking Õ(x1/3) time has been outlined but not implemented.[11]: §5.5 

Table of Q(x), 6/π2x, and R(x)

[edit]

The table shows how Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q(x)} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{6}{\pi^2}x} (with the latter rounded to one decimal place) compare at powers of 10.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R(x) = Q(x) -\frac{6}{\pi^2}x } , also denoted as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta(x) } .

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x } Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q(x) } Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{6}{\pi^2}x} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R(x)}
10 7 6.1 0.9
102 61 60.8 0.2
103 608 607.9 0.1
104 6,083 6,079.3 3.7
105 60,794 60,792.7 1.3
106 607,926 607,927.1 −1.3
107 6,079,291 6,079,271.0 20.0
108 60,792,694 60,792,710.2 −16.2
109 607,927,124 607,927,101.9 22.1
1010 6,079,270,942 6,079,271,018.5 −76.5
1011 60,792,710,280 60,792,710,185.4 94.6
1012 607,927,102,274 607,927,101,854.0 420.0
1013 6,079,271,018,294 6,079,271,018,540.3 −246.3
1014 60,792,710,185,947 60,792,710,185,402.7 544.3
1015 607,927,101,854,103 607,927,101,854,027.0 76.0

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R(x) } changes its sign infinitely often as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x } tends to infinity.[12]

The absolute value of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R(x) } is astonishingly small compared with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x } .

Encoding as binary numbers

[edit]

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_n} and use them as bits in a binary number with the encoding

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{n=0}^\infty {a_n}\cdot 2^n .}

The square-free number 42 has factorization 2 × 3 × 7, or as an infinite product 21 · 31 · 50 · 71 · 110 · 130 ··· 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 representation 101010. This decodes to 20 · 31 · 50 · 71 · 110 · 131 = 3 × 7 × 13 = 273.

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

(See sequences A019565, A048672 and A064273 in the OEIS.)

Erdős squarefree conjecture

[edit]

The central binomial coefficient

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {2n \choose n}}

is never squarefree for n > 4. This was proven in 1985 for all sufficiently large integers by András Sárközy,[13] and for all integers > 4 in 1996 by Olivier Ramaré and Andrew Granville.[14]

Squarefree core

[edit]

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

The multiplicative function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{core}_t(n)} maps every positive integer n to the quotient of n by its largest divisor that is a t-th power. That is,

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{core}_t(p^e) = p^{e\bmod t}.}

The integer Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{core}_t(n)} is t-free, and every t-free integer is mapped to itself by the function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{core}_t.}

The Dirichlet generating function of the sequence Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\mathrm{core}_t(n) \right)_{n\in \N}} is

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{n\ge 1}\frac{\mathrm{core}_t(n)}{n^s} = \frac{\zeta(ts)\zeta(s-1)}{\zeta(ts-t)}} .

See also Template:OEIS2C (t=2), Template:OEIS2C (t=3) and Template:OEIS2C (t=4).

Notes

[edit]
  1. ↑ 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. 877. Springer. pp. 291–322. doi:10.1007/3-540-58691-1_70. ISBN 978-3-540-58691-3.
  2. ↑ 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.
  3. ↑ Walfisz, A. (1963). Weylsche Exponentialsummen in der neueren Zahlentheorie. Berlin: VEB Deutscher Verlag der Wissenschaften.
  4. ↑ 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, A Survey on k-freeness; also see Kaneenika Sinha, "Average orders of certain arithmetical functions Archived 14 February 2012 at the Wayback Machine", Journal of the Ramanujan Mathematical Society 21:3 (2006), pp. 267–277.
  5. ↑ 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.
  6. ↑ 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.
  7. ↑ 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.
  8. ↑ 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.
  9. ↑ Granville, Andrew (1998). "ABC allows us to count squarefrees". Int. Math. Res. Not. 1998 (19): 991–1009. doi:10.1155/S1073792898000592.
  10. ↑ Pawlewicz, Jakub (2011). "Counting Square-Free Numbers". arXiv:1107.4890 [math.NT].
  11. ↑ 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.
  12. ↑ 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.
  13. ↑ 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.
  14. ↑ 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]

Template:Divisor classes

Retrieved from "https://wiki.tachyony.co.uk/w/index.php?title=Square-free_integer"