Entero libre de cuadrados

En matemáticas , un entero libre de cuadrados (o entero libre de cuadrados ) es un entero que no es divisible por ningún número cuadrado distinto de 1. Es decir, su factorización prima tiene exactamente un factor por cada primo que aparece en él. Por ejemplo, 10 = 2 ⋅ 5 es libre de cuadrados, pero 18 = 2 ⋅ 3 ⋅ 3 no lo es, porque 18 es divisible por 9 = 3 ² . Los números libres de cuadrados positivos más pequeños son

Cada entero positivo${\displaystyle n}$puede ser considerado de una manera única como $${\displaystyle n=\prod _{i=1}^{k}q_{i}^{i},}$$ donde el${\displaystyle q_{i}}$Los números distintos de 1 son enteros libres de cuadrados que son coprimos dos a dos . Esto se denomina factorización libre de cuadrados de n .

Para construir la factorización libre de cuadrados, sea $${\displaystyle n=\prod _{j=1}^{h}p_{j}^{e_{j}}}$$ sea ​​la factorización prima de${\displaystyle n}$, donde el${\displaystyle p_{j}}$son números primos distintos . Entonces, los factores de la factorización libre de cuadrados se definen como $${\displaystyle q_{i}=\prod _{j:e_{j}=i}p_{j}.}$$

Un número entero es libre de cuadrados si y solo si${\displaystyle q_{i}=1}$a pesar de${\displaystyle i>1}$. Un número entero mayor que uno es el${\displaystyle k}$la enésima potencia de otro número entero si y solo si${\displaystyle k}$es un divisor de todos${\displaystyle i}$de tal manera que${\displaystyle q_{i}\neq 1.}$

El uso de la factorización libre de cuadrados para números enteros se ve limitado por la dificultad de su cálculo, comparable a la de la factorización prima. Más precisamente, todo algoritmo conocido para calcular la factorización libre de cuadrados también calcula la factorización prima. Esta es una diferencia notable con respecto al caso de los polinomios , para los cuales se pueden dar las mismas definiciones; sin embargo, en este caso, la factorización libre de cuadrados no solo es más fácil de calcular que la factorización completa, sino que constituye el primer paso de todos los algoritmos de factorización estándar.

La parte libre de cuadrados de${\displaystyle n}$es el producto de todos los divisores primos de ${\displaystyle n}$cuyo exponente en la factorización de${\displaystyle n}$es impar. Cada entero positivo${\displaystyle n}$puede representarse de una manera única como el producto de un cuadrado lo más grande posible y un entero libre de cuadrados, ${\displaystyle n=m^{2}k,}$ dónde${\displaystyle k}$es la parte libre de cuadrados de${\displaystyle n}$y${\displaystyle m}$es el divisor más grande de${\displaystyle n}$de tal manera que${\displaystyle m^{2}}$es un divisor de${\displaystyle n}$.

Cada entero positivo${\displaystyle n}$puede representarse de una manera única como el producto de un número poderoso (es decir, un entero que es divisible por el cuadrado de cada factor primo) y un entero libre de cuadrados.${\displaystyle s}$. Este${\displaystyle s}$es el producto de los primos que dividen${\displaystyle n}$solo a la primera potencia, y el número poderoso es ${\displaystyle n/s.}$

El radical de un número entero${\displaystyle n}$es su factor libre de cuadrados más grande, es decir, el producto de todos los divisores primos de${\displaystyle n}$, lo cual es igual a${\displaystyle \textstyle \prod _ {i=1}^{k}q_ {i}}$en la notación de la sección anterior. El radical de un número entero puede ser menor que la parte libre de cuadrados; un número entero es libre de cuadrados si y solo si es igual a su radical.

En resumen, hay tres factores libres de cuadrados que están asociados naturalmente a cada número entero: el factor mencionado anteriormente.${\displaystyle s,}$la parte libre de cuadrados y el factor libre de cuadrados más grande. Cada uno es un factor del siguiente. Todos se deducen fácilmente de la factorización prima o de la factorización libre de cuadrados: si $${\displaystyle n=\prod _{i=1}^{h}p_{i}^{e_{i}}=\prod _{i=1}^{k}q_{i}^{i}}$$ son la factorización prima y la factorización libre de cuadrados de${\displaystyle n}$, dónde${\displaystyle p_{1},\ldots ,p_{h}}$son números primos distintos, entonces la parte libre de cuadrados es $${\displaystyle \prod _{e_{i}=1}p_{i}=q_{1},}$$ El factor libre de cuadrados tal que el cociente es un cuadrado es $${\displaystyle \prod _{e_{i}{\text{ impar}}}p_{i}=\prod _{i{\text{ impar}}}q_{i},}$$ y el factor libre de cuadrados más grande es $${\displaystyle \prod _{i=1}^{h}p_{i}=\prod _{i=1}^{k}q_{i}.}$$

Por ejemplo, si${\displaystyle n=75600=2^{4}\cdot 3^{3}\cdot 5^{2}\cdot 7,}$uno tiene${\displaystyle q_{1}=7,\;q_{2}=5,\;q_{3}=3,\;q_{4}=2.}$La parte libre de cuadrados es 7 , el factor libre de cuadrados tal que el cociente es un cuadrado es 3 ⋅ 7 = 21 , y el factor libre de cuadrados más grande es 2 ⋅ 3 ⋅ 5 ⋅ 7 = 210 .

No se conoce ningún algoritmo para calcular ninguno de estos factores libres de cuadrados que sea más rápido que calcular la factorización prima completa. En particular, no se conoce ningún algoritmo de tiempo polinomial para calcular la parte libre de cuadrados de un entero, ni siquiera para determinar si un entero es libre de cuadrados. ^{[ 1 ]} En cambio, se conocen algoritmos de tiempo polinomial para la prueba de primalidad . ^{[ 2 ]}

Un número entero positivo${\displaystyle n}$es libre de cuadrados si y solo si en la factorización prima de${\displaystyle n}$, ningún factor primo aparece con un exponente mayor que uno. Otra forma de decir lo mismo es que para cada factor primo${\displaystyle p}$de${\displaystyle n}$, el principal${\displaystyle p}$no divide de manera uniforme ${\displaystyle n/p}$. También${\displaystyle n}$es libre de cuadrados si y solo si en cada factorización${\displaystyle n=ab}$los factores${\displaystyle a}$y${\displaystyle b}$son coprimos . Una consecuencia inmediata de esta definición es que todos los números primos son libres de cuadrados.

Un número entero positivo${\displaystyle n}$es libre de cuadrados si y solo si todos los grupos abelianos de orden${\displaystyle n}$son isomorfos , lo cual es el caso si y solo si alguno de esos grupos es cíclico . Esto se deduce de la clasificación de los grupos abelianos finitamente generados .

Un número entero${\displaystyle n}$es libre de cuadrados si y solo si el anillo factor${\displaystyle \mathbb {Z} /n\mathbb {Z} }$(véase aritmética modular ) es un producto de cuerpos . Esto se deduce del teorema chino del resto y del hecho de que un anillo de la forma${\displaystyle \mathbb {Z} /k\mathbb {Z} }$es un campo si y solo si${\displaystyle k}$es primordial.

Para cada entero positivo${\displaystyle n}$, el conjunto de todos los divisores positivos de${\displaystyle n}$se convierte en un conjunto parcialmente ordenado si usamos la divisibilidad como relación de orden. Este conjunto parcialmente ordenado es siempre un retículo distributivo . Es un álgebra booleana si y solo si${\displaystyle n}$es libre de cuadrados.

Un número entero positivo${\displaystyle n}$es libre de cuadrados si y solo si${\displaystyle \mu (n)\neq 0}$, dónde${\displaystyle \mu }$denota la función de Möbius .

El valor absoluto de la función de Möbius es la función indicadora para los enteros libres de cuadrados ; es decir, | μ ( n ) | es igual a 1 si n es libre de cuadrados y 0 si no lo es. La serie de Dirichlet de esta función indicadora es

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

donde ζ ( s ) es la función zeta de Riemann . Esto se deduce del producto de Euler.

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

donde los productos se toman sobre los números primos.

Sea Q ( x ) el número de enteros libres de cuadrados entre 1 y x ( OEIS : A013928  , índice de desplazamiento de 1). Para valores grandes de n , 3/4 de los enteros positivos menores que n no son divisibles por 4, 8/9 de estos números no son divisibles por 9, y así sucesivamente. Debido a que estas razones satisfacen la propiedad multiplicativa (esto se deduce del teorema chino del resto ), obtenemos la aproximación:

${\displaystyle {\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}}}$

Este argumento puede hacerse riguroso para obtener la estimación (usando la notación O grande ).

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

Bosquejo de una demostración: la caracterización anterior da

${\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$ ;}

observando que el último sumando es cero para${\displaystyle d>{\sqrt {x}}}$De ello se deduce que

${\displaystyle {\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}}}$

Al explotar la región libre de ceros más grande conocida de la función zeta de Riemann, Arnold Walfisz mejoró la aproximación a ^{[ 3 ].}

${\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),}$

para alguna constante positiva c .

Bajo la hipótesis de Riemann , el término de error se puede reducir a ^{[ 4 ]}

${\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).}$

En 2015 el término de error se redujo aún más (asumiendo también la hipótesis de Riemann) a ^{[ 5 ].}

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

Por lo tanto, la densidad asintótica/natural de los números libres de cuadrados es

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

Por lo tanto, más de 3/5 de los números enteros no son cuadrados.

De igual modo, si Q ( x , n ) denota el número de enteros libres de n (por ejemplo, los enteros libres de 3 son enteros libres de cubos) entre 1 y x , se puede demostrar ^{[ 6 ]}

${\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).}$

Dado que un múltiplo de 4 debe tener un factor cuadrado 4 = 2² ^, no puede ocurrir que cuatro enteros consecutivos sean todos libres de cuadrados. Por otro lado, existen infinitos enteros n para los cuales 4ⁿ⁺¹ , 4ⁿ⁺² , 4ⁿ⁺³ son todos libres de cuadrados. De lo contrario, observando que 4ⁿ y al menos uno de 4ⁿ⁺¹ , 4ⁿ⁺² , 4ⁿ⁺³ entre cuatro podrían no ser libres de cuadrados para n suficientemente grande , la mitad de todos los enteros positivos menos un número finito deben no ser libres de cuadrados y, por lo tanto,

${\displaystyle Q(x)\leq {\frac {x}{2}}+C}$para alguna constante C ,

contrariamente a la estimación asintótica anterior para${\displaystyle Q(x)}$.

Existen secuencias de enteros consecutivos no libres de cuadrados de longitud arbitraria. De hecho, para cada tupla ₍ p1 , ..., pl ) de primos distintos, el teorema chino del resto garantiza la existencia de un n que satisface la congruencia simultánea _.

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

Cada n + i es entonces divisible por p ² _i . ^{[ 7 ]} Por otro lado, la estimación mencionada anteriormente${\displaystyle Q(x)=6x/\pi ^{2}+O\left({\sqrt {x}}\right)}$implica que, para alguna constante c , siempre existe un entero libre de cuadrados entre x y${\displaystyle x+c{\sqrt {x}}}$para x positivo . Además, un argumento elemental nos permite reemplazar${\displaystyle x+c{\sqrt {x}}}$por${\displaystyle x+cx^{1/5}\log x.}$^{[ 8 ]} Laconjeturaabcpermitiría${\displaystyle x+x^{o(1)}}$. ^{[ 9 ]}

Si representamos un número libre de cuadrados como el producto infinito

${\displaystyle \prod _{n=0}^{\infty }(p_{n+1})^{a_{n}},a_{n}\in \lbrace 0,1\rbrace ,{\text{ y }}p_{n}{\text{ es el }}n{\text{ésimo primo}},}$

entonces podemos tomar esos${\displaystyle a_{n}}$y utilizarlos como bits en un número binario con la codificación

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

El número 42, libre de cuadrados, tiene como factorización 2 × 3 × 7 , o como producto infinito 2 ¹ · 3 ¹ · 5 ⁰ · 7 ¹ · 11 ⁰ · 13 ⁰ ··· Por lo tanto, el número 42 puede codificarse como la secuencia binaria ...001011o decimal 11. (Los dígitos binarios están invertidos con respecto al orden del producto infinito).

Dado que la factorización prima de cada número es única, también lo es cada codificación binaria de los enteros libres de cuadrados.

Lo contrario también es cierto. Dado que cada entero positivo tiene una representación binaria única, es posible invertir esta codificación para poder decodificarlos en un entero único libre de cuadrados.

Nuevamente, por ejemplo, si comenzamos con el número 42, esta vez como un entero positivo, tenemos su representación binaria 101010. Esto se decodifica a 2 ⁰ · 3 ¹ · 5 ⁰ · 7 ¹ · 11 ⁰ · 13 ¹ = 3 × 7 × 13 = 273.

De este modo, la codificación binaria de los números libres de cuadrados describe una biyección entre los enteros no negativos y el conjunto de enteros libres de cuadrados positivos.

(Véanse las secuencias A019565 , A048672 y A064273 en el OEIS ).

El coeficiente binomial central

${\displaystyle {2n \choose n}}$

nunca es libre de cuadrados para n > 4. Esto fue demostrado en 1985 para todos los enteros suficientemente grandes por András Sárközy , ^{[ 13 ]} y para todos los enteros > 4 en 1996 por Olivier Ramaré y Andrew Granville . ^{[ 14 ]}

Llamaremos " t -libre" a un entero positivo que no tiene divisores de orden t . En particular, los enteros 2-libres son los enteros libres de cuadrados.

La función multiplicativa${\displaystyle \mathrm {core} _{t}(n)}$asigna a cada entero positivo n el cociente de n por su divisor más grande que sea una potencia t . Es decir,

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

El entero${\displaystyle \mathrm {core} _{t}(n)}$es t -libre, y cada entero t -libre se asigna a sí mismo mediante la función${\displaystyle \mathrm {core} _{t}.}$

La función generadora de Dirichlet de la secuencia ${\displaystyle \left(\mathrm {core} _{t}(n)\right)_{n\in \mathbb {N} }}$es

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

Véase también OEIS : A007913  ( t = 2), OEIS : A050985  ( t = 3) y OEIS : A053165  ( t = 4).

• Shapiro, Harold N. (1983). Introducción a la teoría de los números . Oxford University Press Dover Publications. ISBN 978-0-486-46669-9.
• Granville, Andrew; Ramaré, Olivier (1996). "Límites explícitos en sumas exponenciales y la escasez de coeficientes binomiales libres de cuadrados". Mathematika . 43 : 73–107 . CiteSeerX 10.1.1.55.8 . doi : 10.1112 /S0025579300011608 . MR 1401709. Zbl 0868.11009 .   
• Guy, Richard K. (2004). Problemas sin resolver en teoría de números (3.ª  ed.). Springer-Verlag . ISBN 978-0-387-20860-2. Zbl 1058.11001 . 
• "OEIS Wiki" . Consultado el 24 de septiembre de 2021 .