Algorithmic aspects of Newman polynomials and their divisors

1. Énoncé du problème

Le papier aborde la question fondamentale en théorie algébrique des nombres concernant les polynômes de Newman (polynômes à coefficients dans $\{0, 1\}$ et un terme constant égal à 1). Plus précisément, il examine les conditions dans lesquelles un polynôme à coefficients entiers $p(x)$ divise un polynôme de Newman.

La question centrale est de savoir s'il existe une constante universelle $\sigma$ telle que tout polynôme à coefficients entiers $p(x)$ vérifiant :

1. Aucune racine réelle non négative, et
2. Une mesure de Mahler $M(p) < \sigma$,
   divise nécessairement un polynôme de Newman.

Des travaux antérieurs ont établi que si $M(p) < 2$, $p(x)$ divise un polynôme à coefficients dans $\{-1, 0, 1\}$. Cependant, restreindre les coefficients à $\{0, 1\}$ est une condition beaucoup plus stricte. Bien que le Nombre d'Or ($g \approx 1,618$) ait été initialement considéré comme une borne naturelle, des contre-exemples avec des mesures de Mahler autour de 1,556 ont été découverts. Le papier vise à affiner cette borne et à déterminer les propriétés de divisibilité des polynômes à faibles mesures de Mahler.

2. Méthodologie

Les auteurs utilisent une combinaison de Programmation Linéaire en Nombres Entiers Mixtes (PLM) et de certification algorithmique pour résoudre deux problèmes distincts : la recherche de multiples de Newman et la certification de la non-existence de tels multiples.

A. Recherche de multiples de Newman (Approche PLM)

Pour déterminer si un polynôme donné $p(x)$ divise un polynôme de Newman, les auteurs formulent le problème comme un système d'inégalités linéaires.

• Formulation : Étant donné un polynôme unitaire $p(x)$ de degré $2d$, ils cherchent un polynôme $q(x)$ tel que le produit $N(x) = p(x)q(x)$ ait des coefficients dans $\{0, 1\}$.
• Contraintes : Puisque les termes constants de $p$ et $q$ sont 1, le terme constant de $N$ est 1. Les coefficients de $N(x)$ sont des combinaisons linéaires des coefficients inconnus de $q(x)$. La condition que tous les coefficients de $N(x)$ doivent être 0 ou 1 crée un système d'inégalités linéaires avec des inconnues entières.
• Implémentation : Les auteurs ont implémenté cela en Julia en utilisant le langage de modélisation JuMP et l'optimiseur Gurobi. Ils ont recherché des solutions où le degré du polynôme de Newman résultant ne dépassait pas 1000.

B. Certification de la non-divisibilité (Approche de l'accessibilité)

Pour prouver qu'un polynôme ne divise aucun polynôme de Newman, les auteurs utilisent une méthode algorithmique introduite par Hare et Mossinghoff.

• Principe : Soit $\beta$ une racine du polynôme candidat. Ils définissent un ensemble $N'(\beta, d)$ représentant les valeurs $F(\beta)$ pour tous les polynômes de Newman $F$ de degré $\le d$, restreints à un disque spécifique $I'(\beta)$.
• Algorithme : L'ensemble est construit de manière récursive. Si l'ensemble se stabilise (c'est-à-dire $N'(\beta, d+1) = N'(\beta, d)$) et que 0 n'est jamais atteint dans cet ensemble, il est prouvé que $\beta$ n'est pas une racine d'aucun polynôme de Newman. Par conséquent, le polynôme minimal de $\beta$ ne divise aucun polynôme de Newman.
• Implémentation : Cela a été implémenté indépendamment en Julia (utilisant Polynomials.jl et Nemo.jl) et en GP/PARI pour assurer une vérification croisée.

C. Construction de multiples avec racines multiples

Les auteurs ont adapté l'approche PLM pour trouver des polynômes de Newman divisibles par $l(x)^2$, où $l(x)$ est le polynôme de Lehmer avec $x \to -x$.

• Méthode : Au lieu d'inégalités, ils ont résolu un système d'équations linéaires dérivé du reste de la division euclidienne $N(x) = g(x)H(x) + R(x)$. La condition $g(x) | N(x)$ exige que $R(x) = 0$.
• Optimisation : Ils ont résolu pour des coefficients binaires $a_i \in \{0, 1\}$ afin de satisfaire les conditions d'annulation du reste.

3. Résultats clés

A. Divisibilité des polynômes à faible mesure de Mahler

Les auteurs ont analysé un ensemble de données de 8 438 polynômes connus avec une mesure de Mahler $< 1,3$ et un degré $\le 180$ (connu sous le nom de Known180).

• Résultat : À l'exception des polynômes ayant des racines réelles positives, tous sauf trois polynômes de cette liste ont été trouvés diviser un polynôme de Newman de degré $\le 1000$.
• Théorème : Tout polynôme à coefficients entiers de degré $\le 44$ avec $M(p) < 1,3$, sans racines réelles non négatives et sans facteurs cyclotomiques, divise un polynôme de Newman. Cela repose sur le fait que Known180 est complet jusqu'au degré 44.
• Cas non résolus : Trois polynômes spécifiques restent non résolus (aucun multiple de Newman trouvé jusqu'au degré 1000), laissant ouverte la question de savoir s'ils divisent des polynômes de Newman de degrés supérieurs.

B. Amélioration de la constante universelle $\sigma$

En utilisant la méthode de certification, les auteurs ont identifié de nouveaux polynômes qui ne divisent aucun polynôme de Newman, abaissant ainsi la borne supérieure de la constante hypothétique $\sigma$.

• Nouvelle borne : Ils ont découvert un polynôme de degré 10 :
  $$x^{10} - x^8 - x^5 + x + 1$$
  avec une mesure de Mahler d'environ 1,419404632.
• Signification : Cela améliore la précédente meilleure borne supérieure connue d'environ 1,4366 (Drungilas et al., 2023) et la borne antérieure d'environ 1,556 (Hare & Mossinghoff). Si une constante $\sigma$ existe, elle doit être $\le 1,419404632$.
• Ensemble de données : Le papier fournit un tableau de 33 exemples certifiés (degrés 8–12) avec des mesures de Mahler $\le 1,556$ qui ne divisent aucun polynôme de Newman.

C. Polynômes de Newman avec racines multiples

Les auteurs ont investigué les polynômes de Newman divisibles par $l(x)^2$ (où $l(x)$ est le polynôme de Lehmer transformé).

• Résultats : Ils ont explicitement construit des polynômes de Newman divisibles par $l(x)^2$ avec des degrés allant jusqu'à 150.
• Résultat négatif : Ils ont prouvé qu'aucun polynôme de Newman de degré $\le 160$ n'est divisible par $l(x)^3$. Cela étend la vérification précédente de Mossinghoff (qui s'arrêtait au degré 120).
• Données : Le papier fournit un tableau complet de ces polynômes encodés au format hexadécimal.

4. Importance et contributions

1. Affinement des bornes : Le papier resserre considérablement les bornes théoriques concernant l'existence de multiples de Newman, repoussant le seuil de mesure de Mahler "interdit" connu d'environ 1,436 à environ 1,419.
2. Cadre algorithmique : Il démontre l'efficacité de la Programmation Linéaire en Nombres Entiers Mixtes (PLM) pour résoudre des problèmes de théorie des nombres impliquant des polynômes à coefficients restreints. La méthode s'avère suffisamment flexible pour gérer à la fois les contraintes d'inégalité (recherche de multiples) et les contraintes d'égalité (annulation des restes).
3. Données complètes : Les auteurs fournissent un ensemble de données complet (analyse Known180, non-diviseurs certifiés et multiples construits) disponible pour de futures recherches, y compris des scripts de vérification en GP/PARI.
4. Résolution de questions ouvertes : Ce travail confirme que pour les polynômes de faible degré ($\le 44$) à faible mesure de Mahler, l'obstacle à la division d'un polynôme de Newman est presque exclusivement la présence de racines réelles positives, avec seulement trois exceptions mineures en attente de recherches à plus haut degré.

5. Conclusion

Le papier conclut que bien que l'existence d'une constante universelle $\sigma$ reste une question ouverte, l'espace de recherche des contre-exemples a été considérablement réduit. Les auteurs suggèrent que leur cadre basé sur la PLM est un outil puissant pour les futures investigations sur les polynômes de Borwein, Littlewood et Newman, permettant potentiellement d'améliorer davantage les bornes et de découvrir de nouvelles propriétés structurelles des polynômes à coefficients restreints.