Número entero sin cuadrados

Número sin factores primos repetidos

10 no tiene cuadrados, ya que sus divisores mayores que 1 son 2, 5 y 10, ninguno de los cuales es cuadrado (los primeros cuadrados son 1, 4, 9 y 16).

Los números enteros libres de cuadrados hasta 120 permanecen después de eliminar los múltiplos de los cuadrados de los primos hasta √120

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

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, ... (secuencia A005117 en la OEIS )

Factorización libre de cuadrados

Todo entero positivo se puede factorizar de una forma única, como donde los números enteros diferentes de uno son números enteros libres de cuadrados que son coprimos por pares . Esto se llama factorización libre de cuadrados de n . ${\displaystyle n}$ $${\displaystyle n=\prod _{i=1}^{k}q_{i}^{i},}$$ ${\displaystyle q_{i}}$

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

Un entero es libre de cuadrados si y solo si para todo . Un entero mayor que uno es la potencia de otro entero si y solo si es divisor de todos tales que ${\displaystyle q_{i}=1}$ ${\displaystyle i>1}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle i}$ ${\displaystyle q_{i}\neq 1.}$

El uso de la factorización libre de cuadrados de números enteros está limitado por el hecho de que su cálculo es tan difícil como el cálculo de la factorización prima. Más precisamente, todos los algoritmos conocidos para calcular una factorización libre de cuadrados calculan también la factorización prima. Esta es una diferencia notable con el caso de los polinomios para los que se pueden dar las mismas definiciones, pero, en este caso, la factorización libre de cuadrados no sólo es más fácil de calcular que la factorización completa, sino que es el primer paso de todos los algoritmos de factorización estándar.

Factores de números enteros libres de cuadrados

El radical de un número entero es su mayor factor libre de cuadrados, es decir, con la notación del apartado anterior. Un número entero es libre de cuadrados si y solo si es igual a su radical. ${\displaystyle \textstyle \prod _{i=1}^{k}q_{i}}$

Todo entero positivo puede representarse de forma única como el producto de un número primo (es decir, un número entero divisible por el cuadrado de cada factor primo) y un entero libre de cuadrados, que son coprimos . En esta factorización, el factor libre de cuadrados es y el número primo es ${\displaystyle n}$ ${\displaystyle q_{1},}$ ${\displaystyle \textstyle \prod _{i=2}^{k}q_{i}^{i}.}$

La parte libre al cuadrado de es que es el mayor divisor libre al cuadrado de que es coprimo con . La parte libre al cuadrado de un entero puede ser menor que el mayor divisor libre al cuadrado, que es ${\displaystyle n}$ ${\displaystyle q_{1},}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n/k}$ ${\displaystyle \textstyle \prod _{i=1}^{k}q_{i}.}$

Cualquier número entero positivo arbitrario se puede representar de forma única como el producto de un cuadrado y un entero libre de cuadrados: En esta factorización, es el mayor divisor de tal que es divisor de . ${\displaystyle n}$ $${\displaystyle n=m^{2}k}$$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m^{2}}$ ${\displaystyle n}$

En resumen, hay tres factores libres de cuadrados que se asocian naturalmente a cada entero: la parte libre de cuadrados, el factor anterior 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 la factorización libre de cuadrados: si son la factorización prima y la factorización libre de cuadrados de , donde son números primos distintos, entonces la parte libre de cuadrados es El factor libre de cuadrados tal que el cociente es un cuadrado es y el factor libre de cuadrados más grande es ${\displaystyle k}$ $${\displaystyle n=\prod _{i=1}^{h}p_{i}^{e_{i}}=\prod _{i=1}^{k}q_{i}^{i}}$$ ${\displaystyle n}$ ${\displaystyle p_{1},\ldots ,p_{h}}$ $${\displaystyle \prod _{e_{i}=1}p_{i}=q_{1},}$$ $${\displaystyle \prod _{e_{i}{\text{ odd}}}p_{i}=\prod _{i{\text{ odd}}}q_{i},}$$ $${\displaystyle \prod _{i=1}^{h}p_{i}=\prod _{i=1}^{k}q_{i}.}$$

Por ejemplo, si uno tiene 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 . ${\displaystyle n=75600=2^{4}\cdot 3^{3}\cdot 5^{2}\cdot 7,}$ ${\displaystyle q_{1}=7,\;q_{2}=5,\;q_{3}=3,\;q_{4}=2.}$

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 en tiempo polinomial para calcular la parte libre de cuadrados de un entero, o incluso para determinar si un entero es libre de cuadrados. ^[1] En contraste, los algoritmos en tiempo polinomial son conocidos para la prueba de primalidad . ^[2] Esta es una diferencia importante entre la aritmética de los enteros y la aritmética de los polinomios univariados , ya que los algoritmos en tiempo polinomial son conocidos para la factorización libre de cuadrados de polinomios (en resumen, el factor libre de cuadrados más grande de un polinomio es su cociente por el máximo común divisor del polinomio y su derivada formal ). ^[3]

Caracterizaciones equivalentes

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

Un entero positivo es libre de cuadrados si y solo si todos los grupos abelianos de orden son isomorfos , lo que sucede si y solo si cualquiera de dichos grupos es cíclico . Esto se desprende de la clasificación de los grupos abelianos finitamente generados . ${\displaystyle n}$ ${\displaystyle n}$

Un entero es libre de cuadrados si y solo si el anillo de factores (ver 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 es un cuerpo si y solo si es primo. ${\displaystyle n}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle \mathbb {Z} /k\mathbb {Z} }$ ${\displaystyle k}$

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

Un entero positivo no tiene cuadrados si y solo si , donde denota la función de Möbius . ${\displaystyle n}$ ${\displaystyle \mu (n)\neq 0}$ ${\displaystyle \mu }$

Serie de Dirichlet

El valor absoluto de la función de Möbius es la función indicadora de los números enteros sin cuadrados, es decir, | μ ( n ) | es igual a 1 si n es sin 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.

Distribución

Sea Q ( x ) el número de enteros sin cuadrados entre 1 y x ( OEIS : A013928 desplazando el índice por 1). Para n grande , 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. Como estas razones satisfacen la propiedad multiplicativa (esto se desprende del teorema del resto chino ), 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 se puede hacer riguroso para obtener la estimación (usando la notación O grande )

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

Esbozo de una prueba: 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 , resulta que ${\displaystyle d>{\sqrt {x}}}$

${\displaystyle {\begin{aligned}Q(x)&=\sum _{d\leq {\sqrt {x}}}\mu (d)\left\lfloor {\frac {x}{d^{2}}}\right\rfloor =\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 ^[4]

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

Según la hipótesis de Riemann , el término de error se puede reducir a ^[5]

${\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 ^[6]

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

Por lo tanto, la densidad asintótica/ natural de 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 tienen cuadrados.

De la misma manera, si Q ( x , n ) denota el número de enteros n -libres (por ejemplo, los enteros 3-libres son enteros libres de cubo) entre 1 y x , se puede demostrar ^[7]

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

Como 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 otra parte, existen infinitos enteros n para los cuales 4 n +1, 4 n +2, 4 n +3 son todos libres de cuadrados. De lo contrario, observando que 4 n y al menos uno de 4 n +1, 4 n +2, 4 n +3 entre cuatro podría ser no libre de cuadrados para n suficientemente grande , la mitad de todos los enteros positivos menos un número finito debe ser no libre 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 números enteros consecutivos no libres de cuadrados de longitud arbitraria. De hecho, si n satisface una congruencia simultánea

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

para primos distintos , entonces cada uno es divisible por p _i ² . ^[8] Por otra parte, la estimación mencionada anteriormente implica que, para alguna constante c , siempre existe un entero libre de cuadrados entre x y para x positivo . Además, un argumento elemental nos permite reemplazar por ^[9] La conjetura ABC permitiría . ^[10] ${\displaystyle p_{1},p_{2},\ldots ,p_{l}}$ ${\displaystyle n+i}$ ${\displaystyle Q(x)=6x/\pi ^{2}+O\left({\sqrt {x}}\right)}$ ${\displaystyle x+c{\sqrt {x}}}$ ${\displaystyle x+c{\sqrt {x}}}$ ${\displaystyle x+cx^{1/5}\log x.}$ ${\displaystyle x+x^{o(1)}}$

Tabla deQ(incógnita),.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠6/π2​⁠incógnita, yR(incógnita)

La tabla muestra cómo y (con este último redondeado a un decimal) se comparan en potencias de 10. ${\displaystyle Q(x)}$ ${\displaystyle {\frac {6}{\pi ^{2}}}x}$

${\displaystyle R(x)=Q(x)-{\frac {6}{\pi ^{2}}}x}$, también denotado como . ${\displaystyle \Delta (x)}$

${\displaystyle R(x)}$cambia su signo infinitamente a menudo porque tiende al infinito. ^[11] ${\displaystyle x}$

El valor absoluto de es sorprendentemente pequeño comparado con . ${\displaystyle R(x)}$ ${\displaystyle x}$

Codificación como números binarios

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{ and }}p_{n}{\text{ is the }}n{\text{th prime}},}$

Luego podemos tomarlos y usarlos como bits en un número binario con la codificación ${\displaystyle a_{n}}$

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

El número libre de cuadrados 42 tiene 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 se invierten respecto del orden en el producto infinito).

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

Lo inverso también es cierto. Como cada número entero positivo tiene una representación binaria única, es posible invertir esta codificación para que se puedan decodificar en un único número entero sin cuadrados.

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

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

(Ver secuencias A019565, A048672 y A064273 en la OEIS .)

Conjetura de Erdős de cuadrados libres

El coeficiente binomial central

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

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

Núcleo cuadrado libre

Llamemos " t -libre" a un entero positivo que no tiene en sus divisores la potencia t -ésima. En particular, los enteros 2-libres son los enteros libres de cuadrados.

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

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

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

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

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

Notas

1. Adleman, Leonard M.; McCurley, Kevin S. (1994). "Problemas abiertos en complejidad teórica de números, II". En Adleman, Leonard M.; Huang, Ming-Deh A. (eds.). Teoría algorítmica de números, Primer simposio internacional, ANTS-I, Ithaca, NY, EE. UU., 6-9 de mayo de 1994, Actas . Apuntes de clase en informática. Vol. 877. Springer. págs. 291-322. doi :10.1007/3-540-58691-1_70. ISBN. 978-3-540-58691-3.
2. Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (1 de septiembre de 2004). "PRIMES está en P" (PDF) . Anales de Matemáticas . 160 (2): 781–793. doi : 10.4007/anales.2004.160.781 . ISSN  0003-486X. SEÑOR  2123939. Zbl  1071.11070.
3. Richards, Chelsea (2009). Algoritmos para factorizar polinomios sin cuadrados sobre cuerpos finitos (PDF) (Tesis de maestría). Canadá: Universidad Simon Fraser.
4. Walfisz, A. (1963). Weylsche Exponentialsummen in der neueren Zahlentheorie . Berlín: VEB Deutscher Verlag der Wissenschaften .
5. Jia, Chao Hua. "La distribución de números sin cuadrados", Science in China Series A: Mathematics 36 :2 (1993), págs. Citado en Pappalardi 2003, A Survey on k-freeness; Véase también Kaneenika Sinha, "Average Orders of ciertas funciones aritméticas", Journal of the Ramanujan Mathematical Society 21 :3 (2006), págs.
6. Liu, H.-Q. (2016). "Sobre la distribución de números libres de cuadrados". Journal of Number Theory . 159 : 202–222. doi : 10.1016/j.jnt.2015.07.013 .
7. Linfoot, EH ; Evelyn, CJA (1929). "Sobre un problema de la teoría aditiva de números". Mathematische Zeitschrift . 30 : 443–448. doi :10.1007/BF01187781. S2CID  120604049.
8. Parent, DP (1984). Ejercicios de teoría de números. Libros de problemas de matemáticas. Springer-Verlag, Nueva York. doi :10.1007/978-1-4757-5194-9. ISBN 978-1-4757-5194-9.
9. Filaseta, Michael; Trifonov, Ognian (1992). "Sobre los huecos entre números sin cuadrados. II". Revista de la Sociedad Matemática de Londres . Segunda serie. 45 (2): 215–221. doi :10.1112/jlms/s2-45.2.215. MR  1171549.
10. Andrew, Granville (1998). "ABC nos permite contar cuadrados libres". Int. Math. Res. Not . 1998 (19): 991–1009. doi : 10.1155/S1073792898000592 .
11. Minoru, Tanaka (1979). "Experimentos relacionados con la distribución de números libres de cuadrados". Actas de la Academia Japonesa, Serie A, Ciencias Matemáticas . 55 (3). doi : 10.3792/pjaa.55.101 . S2CID  121862978.
12. Sárközy, A. (1985). "Sobre divisores de coeficientes binomiales. I". Revista de teoría de números . 20 (1): 70–80. doi : 10.1016/0022-314X(85)90017-4 . MR  0777971.
13. Ramaré, Olivier; Granville, Andrew (1996). "Límites explícitos en sumas exponenciales y la escasez de coeficientes binomiales sin cuadrados". Mathematika . 43 (1): 73–107. doi :10.1112/S0025579300011608.

Referencias

• Shapiro, Harold N. (1983). Introducción a la teoría de 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 sin 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 no resueltos 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 .