Landau-Mignotte con destino

Atado a los coeficientes de un polinomio factorial

En álgebra , un límite de Landau-Mignotte (a veces sólo denominado límite de Mignotte ^[1] ) pertenece a una familia de desigualdades relativas a un polinomio entero univariado f ( x ) y uno de sus factores h ( x ). Una versión básica establece que los coeficientes de h ( x ) están acotados independientemente de h ( x ) por una expresión exponencial que involucra solo el grado y los coeficientes de f ( x ), es decir, solo depende de f ( x ).

Tiene aplicaciones en álgebra informática donde estos límites pueden dar estimaciones a priori sobre el tiempo de ejecución y la complejidad de los algoritmos . ^[2]

Versión básica

Para tal que divide denota por resp. la suma de los valores absolutos de los coeficientes de resp. y sea el grado de , entonces ${\displaystyle f(x),h(x)\in \mathbb {Z} [x]}$ ${\displaystyle h(x)}$ ${\displaystyle f(x)}$ ${\displaystyle \|h\|_{1}}$ ${\displaystyle \|f\|_{1}}$ ${\displaystyle h(x)}$ ${\displaystyle f(x)}$ ${\displaystyle n}$ ${\displaystyle f(x)}$

${\displaystyle \|h\|_{1}\leq 2^{n}\|f\|_{1}}$

Notación

${\displaystyle f,g,h\in \mathbb {C} [x]}$serán polinomios complejos univariados que luego se restringirán a polinomios enteros , es decir, en . Explícitamente ${\displaystyle \mathbb {Z} [x]}$

${\displaystyle f=\sum \limits _{i=0}^{n}f_{i}x^{i},\ \ \ g=\sum \limits _{i=0}^{m}g_{i}x^{i},\ \ \ h=\sum \limits _{i=0}^{k}h_{i}x^{i}.}$

${\displaystyle n,m,k}$son los grados , los coeficientes principales son . ${\displaystyle f_{n},g_{m},h_{k}}$

Definir normas considerando los coeficientes como vectores, explícitamente

${\displaystyle \|f\|_{\infty }=\max _{0\leq i\leq n}|f_{i}|,\ \ \ \|f\|_{2}=\left(\sum \limits _{i=0}^{n}|f_{i}|^{2}\right)^{1/2},\ \ \ \|f\|_{1}=\sum \limits _{i=0}^{n}|f_{i}|.}$

Por el teorema fundamental del álgebra tiene raíces (con multiplicidad ). Establezca la medida de Mahler de como ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle z_{1},z_{2},\ldots ,z_{n}}$ ${\displaystyle f}$

${\displaystyle M(f)=|f_{n}|\prod \limits _{i=1}^{n}\max\{1,|z_{i}|\}.}$

De manera similar defina , , etc. ${\displaystyle \|g\|_{2}}$ ${\displaystyle M(h)}$

La desigualdad de Landau y otras propiedades básicas

Landau demostró ^[3] en 1905 una desigualdad clave que vinculaba la medida de Mahler de un polinomio con su norma euclidiana .

${\displaystyle M(f)\leq \|f\|_{2}}$

En general las normas obedecen a las siguientes desigualdades

${\displaystyle \|f\|_{\infty }\leq \|f\|_{2}\leq \|f\|_{1}\leq {\sqrt {n+1}}\|f\|_{2}\leq (n+1)\|f\|_{\infty }.}$

La medida de Mahler satisface lo que implica para polinomios enteros no triviales . Véase también la conjetura de Lehmer . ${\displaystyle M(f)\geq |f_{n}|}$ ${\displaystyle M(f)\geq 1}$

La medida de Mahler es multiplicativa, es decir, si entonces ${\displaystyle f=gh}$

${\displaystyle M(f)=M(g)M(h).}$

Mignotte está atado

Mignotte utilizó la desigualdad de Landau en 1974 para demostrar una versión básica ^[4] de los siguientes límites ^{[2] : 164 y siguientes} en la notación presentada anteriormente.

Para polinomios complejos en , si se divide , entonces ${\displaystyle \mathbb {C} [x]}$ ${\displaystyle h}$ ${\displaystyle f}$

${\displaystyle \|h\|_{1}\leq 2^{k}M(h)\leq 2^{k}{\frac {|h_{k}|}{|f_{n}|}}\|f\|_{2}\leq 2^{n}{\frac {|h_{k}|}{|f_{n}|}}\|f\|_{2}}$

y los coeficientes individuales obedecen a las desigualdades.

${\displaystyle |h_{i}|\leq {\binom {k}{i}}M(h)\leq {\binom {k}{i}}{\frac {|h_{k}|}{|f_{n}|}}\|f\|_{2}\leq {\binom {n}{i}}{\frac {|h_{k}|}{|f_{n}|}}\|f\|_{2}}$

Si además y son polinomios enteros en entonces y si además es mónico, entonces par . En estos casos se puede simplificar omitiendo la fracción. Incluyendo productos en el análisis tenemos el siguiente teorema. ${\displaystyle f}$ ${\displaystyle h}$ ${\displaystyle \mathbb {Z} [x]}$ ${\displaystyle 0<{\frac {|h_{k}|}{|f_{n}|}}\leq 1}$ ${\displaystyle f}$ ${\displaystyle {\frac {|h_{k}|}{|f_{n}|}}=1}$

Deja tal que divide entonces. ${\displaystyle f,g,h\in \mathbb {Z} [x]}$ ${\displaystyle gh}$ ${\displaystyle f}$

${\displaystyle \|g\|_{\infty }\|h\|_{\infty }\leq \|g\|_{2}\|h\|_{2}\leq \|g\|_{1}\|h\|_{1}\leq 2^{m+k}\|f\|_{2}\leq 2^{n}{\sqrt {n+1}}\|f\|_{\infty },}$

${\displaystyle \|h\|_{\infty }\leq \|h\|_{2}\leq \|h\|_{1}\leq 2^{k}\|f\|_{2}\leq 2^{n}\|f\|_{2}\leq 2^{n}\|f\|_{1},}$

${\displaystyle \|h\|_{\infty }\leq \|h\|_{2}\leq \|h\|_{1}\leq 2^{k}\|f\|_{2}\leq 2^{k}{\sqrt {n+1}}\|f\|_{\infty }\leq 2^{n}{\sqrt {n+1}}\|f\|_{\infty },}$

${\displaystyle |h_{i}|\leq {\binom {k}{i}}M(h)\leq {\binom {k}{i}}\|f\|_{2}\leq {\binom {n}{i}}\|f\|_{2},}$

${\displaystyle \|h\|_{\infty }\leq {\binom {k}{\lfloor k/2\rfloor }}\|f\|_{2}\leq {\binom {n}{\lfloor n/2\rfloor }}\|f\|_{2}\leq {\binom {n}{\lfloor n/2\rfloor }}\|f\|_{1}.}$

Usando la fórmula de Stirling aplicada a coeficientes binomiales obtenemos asintóticamente una ligera mejora al usar coeficientes binomiales

${\displaystyle \|h\|_{\infty }\leq {\binom {n}{\lfloor n/2\rfloor }}\|f\|_{2}\approx 2^{n}{\sqrt {\frac {2}{\pi n}}}\|f\|_{2}.}$

De los límites de los coeficientes individuales se puede deducir el siguiente límite relacionado.

Si es reducible , entonces tiene un factor de grado no trivial tal que ${\displaystyle f\in \mathbb {Z} [x]}$ ${\displaystyle h}$ ${\displaystyle k\leq \lfloor n/2\rfloor }$

${\displaystyle \|h\|_{\infty }\leq {\binom {\lfloor n/2\rfloor }{\lfloor n/4\rfloor }}\|f\|_{2}\leq {\binom {\lfloor n/2\rfloor }{\lfloor n/4\rfloor }}\|f\|_{1}.}$

Combinando esto con la fórmula de Stirling para reemplazar los coeficientes binomiales se obtienen versiones más explícitas.

Si bien los límites superiores que son independientes y solo dependen de son de gran interés teórico y atractivo estético, en la aplicación práctica generalmente se tiene información sobre el grado de . Esta es la razón por la que los límites más definidos de los que además dependen suelen ser más relevantes. ${\displaystyle h}$ ${\displaystyle f}$ ${\displaystyle k}$ ${\displaystyle h}$ ${\displaystyle k}$

Nitidez de los límites

Polinomios ciclotómicos

Para los polinomios ciclotómicos es un divisor irreducible de grado , función totiente de Euler . En este caso y es costumbre denotar . Un resultado de los estados de Vaugn ^[5] para una infinidad de números enteros positivos ${\displaystyle f=x^{n}-1}$ ${\displaystyle h=\Phi _{n}(x)}$ ${\displaystyle k=\varphi (n)}$ ${\displaystyle \|f\|_{2}={\sqrt {2}}}$ ${\displaystyle \|h\|_{\infty }=A(n)}$ ${\displaystyle n}$

${\displaystyle \|h\|_{\infty }=A(n)>e^{\left(n^{(\log 2)/(\log \log n)}\right)},}$

un superpolinomio ligado en el grado . ${\displaystyle n}$

Comparando con el límite de Mignotte y usando la fórmula de Stirling , así como los límites de la función totiente de Euler, obtenemos una cantidad infinita ${\displaystyle n}$

${\displaystyle e^{\left(n^{(\log 2)/(\log \log n)}\right)}<\|h\|_{\infty }\leq {\binom {k}{\lfloor k/2\rfloor }}\|f\|_{2}={\binom {\varphi (n)}{\lfloor \varphi (n)/2\rfloor }}{\sqrt {2}}\approx 2^{\varphi (n)}{\sqrt {\frac {2}{\pi \varphi (n)}}}{\sqrt {2}}\geq 2^{e^{-\gamma }n/(\log \log n)}{\frac {2}{\sqrt {\pi e^{-\gamma }n/(\log \log n)}}}.}$

Esto deja una brecha entre el límite superior de Mignotte y lo que se sabe que se logra mediante polinomios ciclotómicos. Los polinomios ciclotómicos no pueden cerrar esta brecha por un resultado de Bateman que establece ^[6] para cada para todos los enteros positivos suficientemente grandes que tenemos ${\displaystyle \varepsilon >0}$ ${\displaystyle n}$

${\displaystyle \|h\|_{\infty }=A(n)<e^{\left(n^{(\log 2+\varepsilon )/(\log \log n)}\right)}.}$

También tenga en cuenta que a pesar del crecimiento superpolinomial del límite inferior de Vaugn, en la práctica, al observar ejemplos de polinomios ciclotómicos, los coeficientes de son mucho más pequeños que el límite de Mignotte. ${\displaystyle h=\Phi _{n}(x)}$

Una familia de polinomios con crecimiento exponencial en los coeficientes de sus factores.

Abbot da el siguiente ejemplo ^[7] relacionado con polinomios ciclotómicos. Colocar

${\displaystyle H(x)=(x+1)(x^{2}+x+1)=x^{3}+2x^{2}+2x+1,\ \ \ F(x)=H(x)\cdot H(-x)=-x^{6}+1}$

y considerar para números enteros positivos ${\displaystyle j}$

${\displaystyle h=h_{j}=H(x)^{j},\ \ \ f=f_{j}=F(x)^{j}.}$

Tenga en cuenta que los grados son resp. . Abbot muestra que asintóticamente para grandes tenemos ${\displaystyle k=3j}$ ${\displaystyle n=6j}$ ${\displaystyle j}$

${\displaystyle \|h_{j}\|_{\infty }\geq 6^{j}{\frac {1}{3j+1}},\ \ \ \|f_{j}\|_{\infty }\approx 2^{j}{\sqrt {\frac {2}{\pi j}}}.}$

Usando el límite de Mignotte en la versión que comparamos ${\displaystyle \|h\|_{\infty }\leq 2^{k}{\sqrt {n+1}}\|f\|_{\infty }}$

${\displaystyle 3^{n/6}{\sqrt {\frac {\pi }{3n}}}\approx {\frac {6^{j}{\frac {1}{3j+1}}}{2^{j}{\sqrt {\frac {2}{\pi j}}}}}\lesssim {\frac {\|h\|_{\infty }}{\|f\|_{\infty }}}\leq 2^{k}{\sqrt {n+1}}=2^{n/2}{\sqrt {n+1}}}$

Ignorar los términos raíz conduce a

${\displaystyle 1.2009^{n}\approx {\sqrt[{6}]{3}}^{n}\lesssim {\frac {\|h\|_{\infty }}{\|f\|_{\infty }}}\lesssim {\sqrt {2}}^{n}\approx 1.4142^{n}.}$

Abbot afirma que ^{[7] : 24}

Una búsqueda exhaustiva en grados bajos sugiere que esta familia de factorizaciones es cercana a la extrema.

Si bien todavía existe una brecha exponencial entre el ejemplo y el límite de Mignotte, el ejemplo muestra que el crecimiento exponencial es el orden correcto para dicho límite general.

Tenga en cuenta que Abbot también compara la cota de Mignotte con otros tipos de cotas y da ejemplos en los que la cota de Mignotte es mejor y ejemplos en los que otras cotas son mejores ^{[7] : 7ff} .

Tenga en cuenta también que, si bien los polinomios ciclotómicos de la sección anterior son factores irreducibles, los factores tienen muchos factores en sí mismos. Abad especula ^{[7] : 32} ${\displaystyle h=\Phi _{n}(x)}$ ${\displaystyle h=h_{j}=H(x)^{j}=(x+1)^{j}(x^{2}+x+1)^{j}}$

Los ejemplos [...] obligan a cualquier “límite de factor único irreducible” ideal a crecer con grado, aunque la tasa de crecimiento parece ser mucho más lenta que para los límites de factor único válidos para cualquier factorización (adecuadamente escalada) en . Esto sugiere que una cota de factor único ideal podría ser mucho más pequeña que las conocidas actualmente. ${\displaystyle \mathbb {C} [x]}$

Generalizaciones

Por lo general, los límites de Mignotte sólo se establecen para polinomios complejos o enteros. Son igualmente válidos para cualquier subanillo , en particular cuando se consideran sólo polinomios mónicos para los cuales . ${\displaystyle R\subset \mathbb {C} }$ ${\displaystyle {\frac {|h_{k}|}{|f_{n}|}}=1}$

Cualquier campo numérico abstracto y su anillo de números enteros se puede considerar un subanillo de , sin embargo, puede haber múltiples incrustaciones que no sean equivalentes con respecto a los valores absolutos. Los límites de Mignotte son lo suficientemente abstractos y generales como para ser independientes de la incorporación elegida. Esto puede tomarse como un indicio de que, en principio, no son lo más ajustados posible, como se puede ver en los límites en competencia que a veces son mejores ^{[7] : 7ss} . ${\displaystyle \mathbb {C} }$

Aplicaciones

En álgebra informática, cuando se realizan cálculos efectivos con polinomios enteros, a menudo se aplica la siguiente estrategia. Se reduce un módulo polinomial a un número primo adecuado ${\displaystyle f}$ ${\displaystyle p}$ para obtener , se resuelve un problema relacionado en lugar de cuál suele ser más simple y finalmente se utiliza el levantamiento de Hensel para transferir el resultado de regreso a . ${\displaystyle f_{p}}$ ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle f_{p}}$ ${\displaystyle f}$

El levantamiento de Hensel es un proceso iterativo y, en general, no está claro cuándo detenerlo. Los límites de Landau-Mignotte pueden proporcionar información adicional a priori que permite dar límites explícitos sobre la frecuencia con la que se debe iterar el levantamiento de Hensel para recuperar la solución para a partir de una solución para . ${\displaystyle f}$ ${\displaystyle f_{p}}$

En particular, esto se puede aplicar para factorizar polinomios enteros ^[1] o para calcular el mcd de polinomios enteros ^{[2] : 166} . Aunque eficaz , este enfoque puede no ser el más eficiente , como puede verse en el caso del factoring .

Ver también

• La separación de Mignotte está ligada

Referencias

1. Bhatt, Bhuvanesh. "Landau-Mignotte con destino". MathWorld: un recurso web Wolfram, creado por Eric W. Weisstein . Wolfram Research Inc. Consultado el 6 de mayo de 2023 .
2. von zur Gathen, Joaquín; Gerhard, Jürgen (2013). Álgebra informática moderna. Cambridge Reino Unido: Cambridge University Press. ISBN 9781139856065.
3. Landau, Edmund (1905). "Sur quelques théorèmes de M. Petrovitch relatifs aux zéros des fonctions analytiques". Boletín de la Société Mathématique de France . 33 : 251–261. doi : 10.24033/BSMF.760 .
4. Mignotte, Mauricio (1974). "Una desigualdad sobre factores de polinomios". Matemáticas de la Computación . 28 (128): 1153-1157. doi : 10.2307/2005373 . JSTOR  2005373.
5. Vaughan, RC (1975). "Límites de los coeficientes de polinomios ciclotómicos". Matemáticas de Michigan. J.​ 21 (4): 289–295. doi : 10.1307/mmj/1029001352 .
6. Bateman, Paul T. (1981). "Sobre el tamaño de los coeficientes del polinomio ciclotómico". Séminaire de Théorie des Nombres de Bordeaux : 1–17. JSTOR  44165422.
7. , John (2013). "Límites de factores en Z [x]". Revista de Computación Simbólica . 50 : 532–563. arXiv : 0904.3057 . doi : 10.1016/j.jsc.2012.09.004. S2CID  15176498.