🔢 mathematics

Algorithmic aspects of Newman polynomials and their divisors

Este artículo investiga qué polinomios enteros dividen a los polinomios de Newman mediante el análisis de ejemplos conocidos de baja medida de Mahler, la identificación de polinomios específicos que no dividen a ninguno (mejorando así la cota superior para una posible constante universal $\sigma$ ) y la determinación de la máxima potencia del polinomio de Lehmer que puede dividir a un polinomio de Newman dentro de límites de grado específicos.

Autores originales: Musbahu Idris, Jean-Marc Sac-Épée

Publicado 2026-04-29

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Musbahu Idris, Jean-Marc Sac-Épée

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que eres un maestro constructor trabajando con un conjunto muy específico de bloques de Lego. Estos bloques son especiales: solo vienen en dos colores, Blanco (que representa el número 1) y Negro (que representa el número 0). Solo puedes construir torres (polinomios) usando estos dos colores, y cada torre debe comenzar y terminar con un bloque Blanco. En el mundo matemático, estas se llaman polinomios de Newman.

Los autores de este artículo se plantean una pregunta fundamental: ¿Puede construirse cualquier otro tipo de "torre" matemática dentro de una de estas torres especiales de Blanco y Negro?

Más específicamente, están examinando "torres de enteros" (polinomios con coeficientes de números enteros) que poseen una propiedad determinada llamada medida de Mahler baja. Piensa en la medida de Mahler como una puntuación de "tamaño" o "complejidad". Cuanto menor sea la puntuación, más "pequeña" o "simple" es la torre.

Aquí tienes un desglose de su viaje y descubrimientos:

1. La Gran Pregunta

Los matemáticos ya sabían que si permites que tus bloques sean Rojos, Blancos y Negros (los números -1, 0 y 1), entonces casi cualquier torre entera pequeña y simple puede encontrarse dentro de una torre más grande hecha con esos tres colores.

Pero, ¿qué pasa si estás estrictamente prohibido de usar bloques Rojos? ¿Qué pasa si solo puedes usar Blancos y Negros? ¿Sigue siendo válida la regla? ¿Puede encajar aún cada torre entera pequeña y simple dentro de una torre de Blanco y Negro?

2. La Gran Búsqueda (La lista "Known180")

Los autores decidieron probar esto en una lista masiva de 8.438 torres "pequeñas" conocidas (aquellas con una medida de Mahler menor que 1,3). Escribieron un programa informático para actuar como un faro de búsqueda.

El Método: Para cada torre pequeña de la lista, el ordenador intentó encontrar una torre "socios" (hecha de enteros) tal que, al multiplicarlas, el resultado fuera una torre Newman perfecta de Blanco y Negro.
La Restricción: Se le indicó al ordenador que dejara de buscar si la torre resultante se volvía demasiado alta (grado superior a 1.000).
Los Resultados:
- El Problema de la "Raíz Positiva": Primero, descartaron cualquier torre que tuviera una "raíz real positiva". Imagina una torre que tiene un punto débil en el lado soleado; matemáticamente, estas nunca pueden encajar dentro de una torre Newman.
- El Éxito: Para casi todas las torres restantes, ¡el ordenador encontró una coincidencia! Demostró que si una torre es lo suficientemente pequeña (grado 44 o menos) y no tiene esos "puntos débiles", puede construirse dentro de una torre Newman.
- El Misterio: Había tres torres tercas en la lista donde el ordenador no pudo encontrar una coincidencia dentro del límite de 1.000 grados. Los autores no dijeron que estas sean imposibles, solo que aún no han encontrado un socio para ellas.

3. El Muro de la "Proporción Áurea"

Existía una creencia de larga data de que la "Proporción Áurea" (aproximadamente 1,618) era el límite. La idea era: "Si tu torre es más pequeña que la Proporción Áurea, encaja".

Los autores (y otros a los que citan) demostraron que esto era falso. Encontraron torres específicas que son más pequeñas que la Proporción Áurea pero no pueden encajar dentro de ninguna torre Newman, sin importar cuán alta sea la torre Newman.

El Nuevo Récord: Encontraron una torre de grado 10 con un tamaño de aproximadamente 1,419. Esta es la torre "imposible" más pequeña encontrada hasta ahora.
La Implicación: Esto empuja el "límite de seguridad" hacia abajo. Si existe un número mágico (llamémoslo $\sigma$ ) que garantiza que una torre encajará, ese número debe ser menor que 1,419.

4. El Experimento del "Doble Problema"

En la sección final, los autores examinaron una famosa torre matemática llamada polinomio de Lehmer. La dieron la vuelta (sustituyendo $x$ por $-x$ ) para obtener una nueva torre, llamémosla $l(x)$ .

Se preguntaron: ¿Podemos construir una torre Newman que sea divisible por el cuadrado de $l(x)$ ( $l(x)^2$ )?

El Resultado: ¡Sí! Utilizaron su búsqueda informática para construir torres Newman hasta el grado 150 que contienen $l(x)^2$ como factor. Incluso proporcionaron los planos (en un código llamado hexadecimal) para estas torres masivas.

Luego se plantearon el siguiente nivel: ¿Qué pasa con el cubo de $l(x)$ ( $l(x)^3$ )?

El Resultado: Verificaron hasta el grado 160 y no encontraron nada. Ninguna torre Newman de ese tamaño podía ser dividida por $l(x)^3$ . Esto sugiere que, aunque puedes encajar el cuadrado de esta famosa torre, el cubo podría ser imposible de encajar en absoluto (o al menos, es increíblemente difícil de encontrar).

Resumen

Piensa en este artículo como una historia de detectives sobre encajar formas en una caja:

La Caja: Polinomios de Newman (solo 0s y 1s).
Los Objetos: Polinomios enteros con "tamaños" pequeños (medida de Mahler).
El Descubrimiento: La mayoría de los objetos pequeños encajan perfectamente dentro de la caja.
La Excepción: Hay algunos objetos específicos que son lo suficientemente pequeños para parecer que deberían encajar, pero no lo hacen. Los autores encontraron el más pequeño hasta la fecha, demostrando que el "límite" para encajar es menor de lo que pensábamos.
El Bonus: Construyeron con éxito cajas gigantes que contienen formas complejas específicas (versiones al cuadrado y al cubo del polinomio de Lehmer), mostrando lo flexibles que pueden ser estas torres de 0 y 1.

El artículo concluye que, aunque hemos resuelto muchos de estos rompecabezas de encaje, quedan algunos sin resolver, y la búsqueda del "límite" definitivo de lo que puede encajar continúa.

A continuación se presenta un resumen técnico detallado del artículo "Aspectos algorítmicos de los polinomios de Newman y sus divisores" de M. Idris y J.-M. Sac-Epée.

1. Planteamiento del Problema

El artículo aborda la pregunta fundamental en la teoría de números algebraica relativa a los polinomios de Newman (polinomios con coeficientes en $\{0, 1\}$ y un término constante igual a 1). Específicamente, investiga las condiciones bajo las cuales un polinomio con coeficientes enteros $p(x)$ divide a un polinomio de Newman.

La pregunta central es si existe una constante universal $\sigma$ tal que cualquier polinomio con coeficientes enteros $p(x)$ que cumpla:

No tenga raíces reales no negativas, y
Tenga una medida de Mahler $M(p) < \sigma$ ,
divida necesariamente a un polinomio de Newman.

Trabajos anteriores establecieron que si $M(p) < 2$ , $p(x)$ divide a un polinomio con coeficientes en $\{-1, 0, 1\}$ . Sin embargo, restringir los coeficientes a $\{0, 1\}$ es una condición mucho más estricta. Aunque la Proporción Áurea ( $g \approx 1.618$ ) fue inicialmente considerada un límite natural, se encontraron contraejemplos con medidas de Mahler alrededor de 1.556. El artículo tiene como objetivo refinar este límite y determinar las propiedades de divisibilidad de los polinomios con medidas de Mahler pequeñas.

2. Metodología

Los autores emplean una combinación de Programación Lineal Entera Mixta (MILP) y certificación algorítmica para resolver dos problemas distintos: encontrar múltiplos de Newman y certificar la no existencia de tales múltiplos.

A. Búsqueda de Múltiplos de Newman (Enfoque MILP)

Para determinar si un polinomio dado $p(x)$ divide a un polinomio de Newman, los autores formulan el problema como un sistema de desigualdades lineales.

Formulación: Dado un polinomio mónico $p(x)$ de grado $2d$ , buscan un polinomio $q(x)$ tal que el producto $N(x) = p(x)q(x)$ tenga coeficientes en $\{0, 1\}$ .
Restricciones: Dado que los términos constantes de $p$ y $q$ son 1, el término constante de $N$ es 1. Los coeficientes de $N(x)$ son combinaciones lineales de los coeficientes desconocidos de $q(x)$ . La condición de que todos los coeficientes de $N(x)$ deben ser 0 o 1 crea un sistema de desigualdades lineales con incógnitas enteras.
Implementación: Los autores implementaron esto en Julia utilizando el lenguaje de modelado JuMP y el optimizador Gurobi. Buscaron soluciones donde el grado del polinomio de Newman resultante no superara 1000.

B. Certificación de No Divisibilidad (Enfoque de Alcanzabilidad)

Para probar que un polinomio no divide a ningún polinomio de Newman, los autores utilizan un método algorítmico introducido por Hare y Mossinghoff.

Principio: Sea $\beta$ una raíz del polinomio candidato. Definen un conjunto $N'(\beta, d)$ que representa los valores $F(\beta)$ para todos los polinomios de Newman $F$ de grado $\le d$ , restringidos a un disco específico $I'(\beta)$ .
Algoritmo: El conjunto se construye recursivamente. Si el conjunto se estabiliza (es decir, $N'(\beta, d+1) = N'(\beta, d)$ ) y el 0 nunca se alcanza dentro de este conjunto, se demuestra que $\beta$ no es una raíz de ningún polinomio de Newman. En consecuencia, el polinomio minimal de $\beta$ no divide a ningún polinomio de Newman.
Implementación: Esto se implementó independientemente en Julia (usando Polynomials.jl y Nemo.jl) y en GP/PARI para asegurar la verificación cruzada.

C. Construcción de Múltiplos con Raíces Reiteradas

Los autores adaptaron el enfoque MILP para encontrar polinomios de Newman divisibles por $l(x)^2$ , donde $l(x)$ es el polinomio de Lehmer con $x \to -x$ .

Método: En lugar de desigualdades, resolvieron un sistema de ecuaciones lineales derivadas del residuo de la división euclidiana $N(x) = g(x)H(x) + R(x)$ . La condición $g(x) | N(x)$ requiere que $R(x) = 0$ .
Optimización: Resolvieron para coeficientes binarios $a_i \in \{0, 1\}$ para satisfacer las condiciones de anulación del residuo.

3. Resultados Clave

A. Divisibilidad de Polinomios con Medida de Mahler Pequeña

Los autores analizaron un conjunto de datos de 8.438 polinomios conocidos con medida de Mahler $< 1.3$ y grado $\le 180$ (conocido como Known180).

Hallazgo: Excluyendo los polinomios con raíces reales positivas, todos menos tres polinomios de esta lista se encontró que dividen a un polinomio de Newman de grado $\le 1000$ .
Teorema: Todo polinomio con coeficientes enteros de grado $\le 44$ con $M(p) < 1.3$ , sin raíces reales no negativas y sin factores ciclotómicos, divide a un polinomio de Newman. Esto se basa en el hecho de que Known180 es completo hasta el grado 44.
Casos sin Resolver: Tres polinomios específicos permanecen sin resolver (no se encontró ningún múltiplo de Newman hasta el grado 1000), dejando abierta la pregunta de si dividen a polinomios de Newman de grados superiores.

B. Mejora de la Constante Universal $\sigma$

Utilizando el método de certificación, los autores identificaron nuevos polinomios que no dividen a ningún polinomio de Newman, reduciendo así el límite superior para la constante hipotética $\sigma$ .

Nuevo Límite: Descubrieron un polinomio de grado 10:
$x^{10} - x^8 - x^5 + x + 1$
con una medida de Mahler de aproximadamente 1.419404632.
Significado: Esto mejora el mejor límite superior conocido previamente de $\approx 1.4366$ (Drungilas et al., 2023) y el límite anterior de $\approx 1.556$ (Hare & Mossinghoff). Si existe una constante $\sigma$ , debe ser $\le 1.419404632$ .
Conjunto de Datos: El artículo proporciona una tabla de 33 ejemplos certificados (grados 8–12) con medidas de Mahler $\le 1.556$ que no dividen a ningún polinomio de Newman.

C. Polinomios de Newman con Raíces Reiteradas

Los autores investigaron polinomios de Newman divisibles por $l(x)^2$ (donde $l(x)$ es el polinomio de Lehmer transformado).

Resultados: Construyeron explícitamente polinomios de Newman divisibles por $l(x)^2$ con grados hasta 150.
Resultado Negativo: Demostraron que ningún polinomio de Newman de grado $\le 160$ es divisible por $l(x)^3$ . Esto extiende la verificación previa de Mossinghoff (que se detuvo en el grado 120).
Datos: El artículo proporciona una tabla exhaustiva de estos polinomios codificados en formato hexadecimal.

4. Significado y Contribuciones

Refinamiento de Límites: El artículo ajusta significativamente los límites teóricos sobre la existencia de múltiplos de Newman, empujando el umbral conocido de medida de Mahler "prohibida" de $\approx 1.436$ a $\approx 1.419$ .
Marco Algorítmico: Demuestra la eficacia de la Programación Lineal Entera Mixta (MILP) para resolver problemas de teoría de números que involucran polinomios con coeficientes restringidos. Se muestra que el método es lo suficientemente flexible para manejar tanto restricciones de desigualdad (encontrar múltiplos) como restricciones de igualdad (cancelar residuos).
Datos Exhaustivos: Los autores proporcionan un conjunto de datos completo (análisis de Known180, no divisores certificados y múltiplos construidos) disponible para futuras investigaciones, incluyendo scripts de verificación en GP/PARI.
Resolución de Preguntas Abiertas: El trabajo confirma que para polinomios de bajo grado ( $\le 44$ ) con medida de Mahler pequeña, el obstáculo para dividir un polinomio de Newman es casi exclusivamente la presencia de raíces reales positivas, con solo tres excepciones menores pendientes de búsquedas de mayor grado.

5. Conclusión

El artículo concluye que, aunque la existencia de una constante universal $\sigma$ sigue siendo una pregunta abierta, el espacio de búsqueda para contraejemplos se ha reducido drásticamente. Los autores sugieren que su marco basado en MILP es una herramienta poderosa para futuras investigaciones sobre los polinomios de Borwein, Littlewood y Newman, permitiendo potencialmente mejoras adicionales en los límites y el descubrimiento de nuevas propiedades estructurales de los polinomios con coeficientes restringidos.