Número entero sin cuadrados

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

Todo entero positivo se puede factorizar de una forma única, como donde los números enteros distintos de uno son números enteros libres de cuadrados que son coprimos por pares . Esto se denomina factorización libre de cuadrados de n .${\estilo de visualización n}$$${\displaystyle n=\prod_{i=1}^{k}q_{i}^{i},}$$$estilo de visualización 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}}}$$${\estilo de visualización n}$$estilo de visualización 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$estilo de visualización q_{i}=1$${\displaystyle i>1}$${\estilo de visualización k}$${\estilo de visualización k}$${\estilo de visualización 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.

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${\estilo de visualización 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${\estilo de visualización n}$${\displaystyle q_{1},}$${\estilo de visualización k}$${\estilo de visualización n}$${\estilo de visualización 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 .${\estilo de visualización n}$$$Estilo de visualización n=m^{2}k$$${\estilo de visualización m}$${\estilo de visualización n}$${\estilo de visualización m^{2}}$${\estilo de visualización 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 ${\estilo de visualización k}$$${\displaystyle n=\prod_{i=1}^{h}p_{i}^{e_{i}}=\prod_{i=1}^{k}q_{i}^{i}}$$${\estilo de visualización n}$${\displaystyle p_{1},\ldots ,p_{h}}$$${\displaystyle \prod_{e_{i}=1}p_{i}=q_{1},}$$$${\displaystyle \prod _{e_{i}{\text{ impar}}}p_{i}=\prod _{i{\text{ impar}}}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]

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.${\estilo de visualización n}$${\estilo de visualización n}$ ${\estilo de visualización p}$${\estilo de visualización n}$${\estilo de visualización p}$${\estilo de visualización n/p}$${\estilo de visualización n}$${\estilo de visualización n=ab}$${\estilo de visualización a}$${\estilo de visualización 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 .${\estilo de visualización n}$ ${\estilo de visualización 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.${\estilo de visualización n}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$${\displaystyle \mathbb {Z} /k\mathbb {Z} }$${\estilo de visualización 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.${\estilo de visualización n}$${\estilo de visualización n}$${\estilo de visualización n}$

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

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.

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)=\suma _{n\leq x}\suma _{d^{2}\mid n}\mu (d)=\suma _{d\leq x}\mu (d)\suma _{n\leq x,d^{2}\mid n}1=\suma _{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)}}$

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 x}$	${\displaystyle Q(x)}$	${\displaystyle {\frac {6}{\pi ^{2}}}x}$	${\displaystyle R(x)}$
10	7	6.1	0.9
10 2	61	60.8	0,2
10 3	608	607.9	0,1
10 4	6.083	6.079,3	3.7
10 5	60.794	60.792,7	1.3
10 6	607.926	607.927,1	- 1.3
10 7	6.079.291	6.079.271,0	20.0
10 8	60.792.694	60.792.710,2	- 16.2
10 9	607.927.124	607.927.101,9	22.1
10 10	6.079.270.942	6.079.271.018,5	- 76,5
10 11	60.792.710.280	60.792.710.185,4	94.6
10 12	607.927.102.274	607.927.101.854,0	420.0
10 13	6.079.271.018.294	6.079.271.018.540,3	- 246,3
10 14	60.792.710.185.947	60.792.710.185.402,7	544.3
10 15	607.927.101.854.103	607.927.101.854.027,0	76.0

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

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

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]

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

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