Algorithmic aspects of Newman polynomials and their divisors

1. Enunciato del Problema

L'articolo affronta la domanda fondamentale nella teoria dei numeri algebrici riguardante i polinomi di Newman (polinomi con coefficienti in $\{0, 1\}$ e un termine costante pari a 1). Nello specifico, indaga le condizioni sotto le quali un polinomio a coefficienti interi $p(x)$ divide un polinomio di Newman.

La domanda centrale è se esista una costante universale $\sigma$ tale che qualsiasi polinomio a coefficienti interi $p(x)$ con:

1. Nessuna radice reale non negativa, e
2. Misura di Mahler $M(p) < \sigma$,
   divida necessariamente un polinomio di Newman.

Lavori precedenti hanno stabilito che se $M(p) < 2$, $p(x)$ divide un polinomio con coefficienti in $\{-1, 0, 1\}$. Tuttavia, restringere i coefficienti a $\{0, 1\}$ è una condizione molto più severa. Sebbene la Sezione Aurea ($g \approx 1.618$) fosse inizialmente considerata un limite naturale, sono stati trovati controesempi con misure di Mahler intorno a 1.556. L'articolo mira a rifinire questo limite e determinare le proprietà di divisibilità dei polinomi con piccole misure di Mahler.

2. Metodologia

Gli autori impiegano una combinazione di Programmazione Lineare Intera Mista (MILP) e certificazione algoritmica per risolvere due problemi distinti: trovare multipli di Newman e certificare la non esistenza di tali multipli.

A. Ricerca di Multipli di Newman (Approccio MILP)

Per determinare se un dato polinomio $p(x)$ divide un polinomio di Newman, gli autori formulano il problema come un sistema di disuguaglianze lineari.

• Formulazione: Dato un polinomio monico $p(x)$ di grado $2d$, cercano un polinomio $q(x)$ tale che il prodotto $N(x) = p(x)q(x)$ abbia coefficienti in $\{0, 1\}$.
• Vincoli: Poiché i termini costanti di $p$ e $q$ sono 1, il termine costante di $N$ è 1. I coefficienti di $N(x)$ sono combinazioni lineari dei coefficienti incogniti di $q(x)$. La condizione che tutti i coefficienti di $N(x)$ debbano essere 0 o 1 crea un sistema di disuguaglianze lineari con incognite intere.
• Implementazione: Gli autori hanno implementato questo approccio in Julia utilizzando il linguaggio di modellazione JuMP e l'ottimizzatore Gurobi. Hanno cercato soluzioni in cui il grado del polinomio di Newman risultante non superasse 1000.

B. Certificazione della Non-Divisibilità (Approccio di Raggiungibilità)

Per dimostrare che un polinomio non divide alcun polinomio di Newman, gli autori utilizzano un metodo algoritmico introdotto da Hare e Mossinghoff.

• Principio: Sia $\beta$ una radice del polinomio candidato. Definiscono un insieme $N'(\beta, d)$ che rappresenta i valori $F(\beta)$ per tutti i polinomi di Newman $F$ di grado $\le d$, limitati a un disco specifico $I'(\beta)$.
• Algoritmo: L'insieme è costruito ricorsivamente. Se l'insieme si stabilizza (cioè $N'(\beta, d+1) = N'(\beta, d)$) e lo 0 non viene mai raggiunto all'interno di questo insieme, è dimostrato che $\beta$ non è una radice di alcun polinomio di Newman. Di conseguenza, il polinomio minimo di $\beta$ non divide alcun polinomio di Newman.
• Implementazione: Questo è stato implementato indipendentemente in Julia (utilizzando Polynomials.jl e Nemo.jl) e in GP/PARI per garantire la cross-verifica.

C. Costruzione di Multipli con Radici Multiple

Gli autori hanno adattato l'approccio MILP per trovare polinomi di Newman divisibili per $l(x)^2$, dove $l(x)$ è il polinomio di Lehmer con $x \to -x$.

• Metodo: Invece di disuguaglianze, hanno risolto un sistema di equazioni lineari derivate dal resto della divisione euclidea $N(x) = g(x)H(x) + R(x)$. La condizione $g(x) | N(x)$ richiede che $R(x) = 0$.
• Ottimizzazione: Hanno risolto per coefficienti binari $a_i \in \{0, 1\}$ per soddisfare le condizioni di annullamento del resto.

3. Risultati Chiave

A. Divisibilità dei Polinomi con Piccola Misura di Mahler

Gli autori hanno analizzato un dataset di 8.438 polinomi noti con misura di Mahler $< 1.3$ e grado $\le 180$ (noto come Known180).

• Risultato: Escludendo i polinomi con radici reali positive, tutti tranne tre polinomi in questa lista sono stati trovati dividere un polinomio di Newman di grado $\le 1000$.
• Teorema: Ogni polinomio a coefficienti interi di grado $\le 44$ con $M(p) < 1.3$, senza radici reali non negative e senza fattori ciclotomici, divide un polinomio di Newman. Questo si basa sul fatto che Known180 è completo fino al grado 44.
• Casi Irrisolti: Tre polinomi specifici rimangono irrisolti (nessun multiplo di Newman trovato fino al grado 1000), lasciando aperta la questione se dividano polinomi di Newman di gradi superiori.

B. Miglioramento della Costante Universale $\sigma$

Utilizzando il metodo di certificazione, gli autori hanno identificato nuovi polinomi che non dividono alcun polinomio di Newman, abbassando di conseguenza il limite superiore per la costante ipotetica $\sigma$.

• Nuovo Limite: Hanno scoperto un polinomio di grado 10:
  $$x^{10} - x^8 - x^5 + x + 1$$
  con una misura di Mahler di circa 1.419404632.
• Significato: Questo migliora il precedente miglior limite superiore noto di $\approx 1.4366$ (Drungilas et al., 2023) e il limite precedente di $\approx 1.556$ (Hare & Mossinghoff). Se esiste una costante $\sigma$, deve essere $\le 1.419404632$.
• Dataset: L'articolo fornisce una tabella di 33 esempi certificati (gradi 8–12) con misure di Mahler $\le 1.556$ che non dividono alcun polinomio di Newman.

C. Polinomi di Newman con Radici Multiple

Gli autori hanno investigato i polinomi di Newman divisibili per $l(x)^2$ (dove $l(x)$ è il polinomio di Lehmer trasformato).

• Risultati: Hanno esplicitamente costruito polinomi di Newman divisibili per $l(x)^2$ con gradi fino a 150.
• Risultato Negativo: Hanno dimostrato che nessun polinomio di Newman di grado $\le 160$ è divisibile per $l(x)^3$. Questo estende la precedente verifica di Mossinghoff (che si fermava al grado 120).
• Dati: L'articolo fornisce una tabella completa di questi polinomi codificati in formato esadecimale.

4. Significato e Contributi

1. Raffinamento dei Limiti: L'articolo stringe significativamente i limiti teorici riguardanti l'esistenza di multipli di Newman, spingendo la soglia nota delle misure di Mahler "proibite" da $\approx 1.436$ a $\approx 1.419$.
2. Quadro Algoritmico: Dimostra l'efficacia della Programmazione Lineare Intera Mista (MILP) nella risoluzione di problemi di teoria dei numeri che coinvolgono polinomi a coefficienti ristretti. Il metodo si mostra abbastanza flessibile da gestire sia vincoli di disuguaglianza (trovare multipli) sia vincoli di uguaglianza (annullare i resti).
3. Dati Completi: Gli autori forniscono un dataset completo (analisi Known180, non-divisori certificati e multipli costruiti) disponibile per ulteriori ricerche, inclusi script di verifica in GP/PARI.
4. Risoluzione di Questioni Aperte: Il lavoro conferma che per polinomi di basso grado ($\le 44$) con piccola misura di Mahler, l'ostacolo alla divisione di un polinomio di Newman è quasi esclusivamente la presenza di radici reali positive, con solo tre eccezioni minori in attesa di ricerche su gradi superiori.

5. Conclusione

L'articolo conclude che, sebbene l'esistenza di una costante universale $\sigma$ rimanga una questione aperta, lo spazio di ricerca per i controesempi è stato drasticamente ristretto. Gli autori suggeriscono che il loro quadro basato su MILP è uno strumento potente per future indagini sui polinomi di Borwein, Littlewood e Newman, permettendo potenzialmente ulteriori miglioramenti nei limiti e la scoperta di nuove proprietà strutturali dei polinomi a coefficienti ristretti.