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 sin cuadrados hasta 120 quedan después de eliminar múltiplos de cuadrados de números 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 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 no tiene cuadrados, pero 18 = 2 ⋅ 3 ⋅ 3 no lo es, porque 18 es divisible por 9 = 3 ² . Los números positivos libres de cuadrados 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 sin cuadrados

Cada número entero positivo se puede factorizar de una manera única como ${\displaystyle n}$

$${\displaystyle n=\prod _{i=1}^{k}q_{i}^{i},}$$

coprimos por paresfactorización libre de cuadradosn ${\displaystyle q_{i}}$

Para construir la factorización libre de cuadrados, sea

$${\displaystyle n=\prod _{j=1}^{h}p_{j}^{e_{j}}}$$

factorización primanúmeros primos ${\displaystyle n}$ ${\displaystyle p_{j}}$

$${\displaystyle q_{i}=\prod _{j:e_{j}=i}p_{j}.}$$

Un número entero no tiene cuadrados si y sólo si para todos . Un número entero mayor que uno es la enésima potencia de otro número entero si y sólo si es divisor de todos los 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 de números enteros sin cuadrados 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 cuales 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 todo estándar. Algoritmos de factorización.

Factores libres de cuadrados de números enteros

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

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

La parte libre de cuadrados de es cuál es el divisor libre de cuadrados más grande de que es coprimo con . La parte libre de cuadrados de un número entero puede ser menor que el divisor libre de cuadrados más grande, 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 sin cuadrados: ${\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 están naturalmente asociados a todo número 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. Todo se deduce fácilmente de la factorización prima o de la factorización libre de cuadrados: si ${\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 cualquiera 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 número entero, o incluso para determinar si un número entero está libre de cuadrados. ^[1] Por el contrario, los algoritmos de tiempo polinomial son conocidos por las pruebas de primalidad . ^[2] Esta es una diferencia importante entre la aritmética de los números enteros y la aritmética de los polinomios univariados , ya que los algoritmos de tiempo polinomial son conocidos por la factorización de polinomios sin cuadrados (en resumen, el factor libre de cuadrados más grande de un polinomio). es su cociente entre el máximo común divisor del polinomio y su derivada formal ). ^[3]

Caracterizaciones equivalentes

Un entero positivo no tiene cuadrados si y sólo si en la factorización prima de , no aparece ningún factor primo con un exponente mayor que uno. Otra forma de decir lo mismo es que para cada factor primo de , el primo no se divide uniformemente  . También es libre de cuadrados si y sólo si en cada factorización , los factores y son coprimos . Un resultado inmediato de esta definición es que todos los números primos no tienen 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 sólo si todos los grupos abelianos de orden son isomorfos , que es el caso si y sólo si cualquiera de dichos grupos es cíclico . Esto se desprende de la clasificación de grupos abelianos generados finitamente . ${\displaystyle n}$ ${\displaystyle n}$

Un número entero no tiene cuadrados si y sólo si el anillo de factores (ver aritmética modular ) es un producto de campos . Esto se desprende del teorema chino del resto y del hecho de que un anillo de la forma es un campo si y sólo 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 usamos la divisibilidad como relación de orden. Este conjunto parcialmente ordenado es siempre una red distributiva . Es un álgebra booleana si y sólo si no tiene cuadrados. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

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

Serie Dirichlet

El valor absoluto de la función de Möbius es la función indicadora para los números enteros sin cuadrados, es decir, | μ ( norte ) | es igual a 1 si n no tiene 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 desprende 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 índice desplazado en 1). Para n grande , 3/4 de los números 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 desprende 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 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 cero 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 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 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 tienen cuadrados.

Del mismo modo, si Q ( x , n ) denota el número de n enteros libres (por ejemplo, 3 enteros libres son enteros libres de cubos) 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).}$

Dado que un múltiplo de 4 debe tener un factor cuadrado 4=2 ² , no puede ocurrir que cuatro números enteros consecutivos estén libres de cuadrados. Por otro lado, existen infinitos números 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ían no estar libres de cuadrados para n suficientemente grande , la mitad de todos los números enteros positivos menos un número finito deben ser no -libre de cuadrados y por lo tanto

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

contrario 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, 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 otro lado, la estimación antes mencionada 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 sustituir 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 de Q ( x ),.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/π 2x y R ( x )

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 de signo infinitamente veces cuando 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}},}$

entonces 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 sin cuadrados 42 tiene factorización 2 × 3 × 7 , o como un producto infinito 2 ¹ · 3 ¹ · 5 ⁰ · 7 ¹ · 11 ⁰ · 13 ⁰ ··· Por lo tanto, el número 42 puede codificarse como la secuencia binaria ...001011o 11 decimales. (Los dígitos binarios están invertidos del orden en el producto infinito).

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

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

Nuevamente, por ejemplo, si comenzamos con el número 42, esta vez simplemente como un entero positivo, tenemos su representación binaria 101010. Esto se decodifica a 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 enteros no negativos y el conjunto de enteros positivos libres de cuadrados.

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

Conjetura libre de cuadrados de Erdős

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 libre de cuadrados

Llamemos " t -libre" a un entero positivo que no tiene t -ésima potencia en sus divisores. En particular, los números enteros libres de 2 son los números 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 t -ésima potencia. Eso es, ${\displaystyle \mathrm {core} _{t}(n)}$

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

El número 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 de la teoría 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, Nueva York, EE. UU., 6 al 9 de mayo de 1994, Actas . Apuntes de conferencias sobre informática. vol. 877. Saltador. 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 libres de cuadrados sobre campos 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". Revista de teoría de números . 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. Padre, DP (1984). Ejercicios de teoría de números. Libros de problemas en 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 espacios entre números libres de cuadrados. II". Revista de la Sociedad Matemática de Londres . Segunda Serie. 45 (2): 215–221. doi :10.1112/jlms/s2-45.2.215. SEÑOR  1171549.
10. Andrés, Granville (1998). "ABC nos permite contar cuadrados libres". En t. Matemáticas. Res. No . 1998 (19): 991–1009. doi : 10.1155/S1073792898000592 .
11. Minoru, Tanaka (1979). "Experimentos sobre la distribución de números libres de cuadrados". Actas de la Academia de Japón, Serie A, Ciencias Matemáticas . 55 (3). doi : 10.3792/pjaa.55.101 . S2CID  121862978.
12. Sarkö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 . SEÑOR  0777971.
13. Ramaré, Olivier; Granville, Andrés (1996). "Límites explícitos de sumas exponenciales y la escasez de coeficientes binomiales libres de cuadrados". Matemática . 43 (1): 73-107. doi :10.1112/S0025579300011608.

Referencias

• Shapiro, Harold N. (1983). Introducción a la teoría de los números . Publicaciones de Dover de Oxford University Press . ISBN 978-0-486-46669-9.
• Granville, Andrés; Ramaré, Olivier (1996). "Límites explícitos de sumas exponenciales y la escasez de coeficientes binomiales libres de cuadrados". Matemática . 43 : 73-107. CiteSeerX  10.1.1.55.8 . doi :10.1112/S0025579300011608. SEÑOR  1401709. Zbl  0868.11009.
• Chico, 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.
• "Wiki de OEIS" . Consultado el 24 de septiembre de 2021 .