🔢 mathematics

Algorithmic aspects of Newman polynomials and their divisors

Dieser Artikel untersucht, welche ganzzahligen Polynome Newman-Polynome teilen, indem er bekannte Beispiele mit niedriger Mahler-Maß analysiert, spezifische Polynome identifiziert, die keines teilen (wodurch die obere Schranke für eine potenzielle universelle Konstante $\sigma$ verbessert wird), und die maximale Potenz des Polynoms von Lehmer bestimmt, die innerhalb bestimmter Gradgrenzen ein Newman-Polynom teilen kann.

Ursprüngliche Autoren: Musbahu Idris, Jean-Marc Sac-Épée

Veröffentlicht 2026-04-29

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Musbahu Idris, Jean-Marc Sac-Épée

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind ein Meisterbauer, der mit einem sehr spezifischen Satz von Lego-Steinen arbeitet. Diese Steine sind besonders: Sie gibt es nur in zwei Farben, Weiß (repräsentiert die Zahl 1) und Schwarz (repräsentiert die Zahl 0). Sie können nur Türme (Polynome) bauen, die aus diesen beiden Farben bestehen, und jeder Turm muss sowohl mit einem weißen als auch mit einem schwarzen Stein beginnen und enden. In der mathematischen Welt nennt man diese Newman-Polynome.

Die Autoren dieses Papers stellen eine fundamentale Frage: Kann jeder andere Typ mathematischen „Turms" innerhalb eines dieser speziellen Schwarz-Weiß-Türme gebaut werden?

Genauer betrachtet untersuchen sie „Ganzzahl-Türme" (Polynome mit ganzzahligen Koeffizienten), die eine bestimmte Eigenschaft namens kleines Mahler-Maß besitzen. Betrachten Sie das Mahler-Maß als einen „Größe"- oder „Komplexitäts"-Score. Je niedriger der Score, desto „kleiner" oder „einfacher" ist der Turm.

Hier ist eine Aufschlüsselung ihrer Reise und Entdeckungen:

1. Die große Frage

Mathematiker wussten bereits, dass, wenn Sie Ihren Steinen die Farben Rot, Weiß und Schwarz (die Zahlen -1, 0 und 1) erlauben, dann fast jeder kleine, einfache Ganzzahl-Turm innerhalb eines größeren Turms gefunden werden kann, der aus diesen drei Farben besteht.

Aber was, wenn Sie streng verboten sind, rote Steine zu verwenden? Was, wenn Sie nur Weiß und Schwarz verwenden dürfen? Gilt die Regel dann immer noch? Passt jeder kleine, einfache Ganzzahl-Turm immer noch in einen Schwarz-Weiß-Turm?

2. Die große Suche (Die „Known180"-Liste)

Die Autoren beschlossen, dies an einer massiven Liste von 8.438 bekannten „kleinen" Türmen (jene mit einem Mahler-Maß kleiner als 1,3) zu testen. Sie schrieben ein Computerprogramm, das als Suchscheinwerfer fungierte.

Die Methode: Für jeden kleinen Turm auf der Liste versuchte der Computer, einen „Partner"-Turm (bestehend aus ganzen Zahlen) zu finden, sodass das Produkt aus beiden ein perfekter Schwarz-Weiß-Newman-Turm ist.
Die Einschränkung: Der Computer erhielt den Befehl, die Suche abzubrechen, wenn der resultierende Turm zu hoch wurde (Grad höher als 1.000).
Die Ergebnisse:
- Das Problem des „positiven Wurzels": Zuerst verworfen sie jeden Turm, der eine „positive reelle Nullstelle" hatte. Stellen Sie sich einen Turm vor, der an der sonnenbeschienenen Seite eine Schwachstelle hat; mathematisch gesehen können diese niemals in einen Newman-Turm passen.
- Der Erfolg: Für fast jeden verbleibenden Turm fand der Computer ein Match! Es wurde bewiesen, dass, wenn ein Turm klein genug ist (Grad 44 oder weniger) und keine dieser „Schwachstellen" aufweist, er in einen Newman-Turm gebaut werden kann.
- Das Rätsel: Es gab drei hartnäckige Türme auf der Liste, für die der Computer innerhalb des 1.000-Grad-Limits kein Match finden konnte. Die Autoren sagten nicht, dass diese unmöglich sind, sondern lediglich, dass sie noch keinen Partner für sie gefunden haben.

3. Die „Goldener-Schnitt"-Mauer

Es bestand lange die Überzeugung, dass der „Goldene Schnitt" (ungefähr 1,618) die Grenze darstellt. Die Idee war: „Wenn Ihr Turm kleiner als der Goldene Schnitt ist, passt er."

Die Autoren (und andere, die sie zitieren) bewiesen, dass dies falsch war. Sie fanden spezifische Türme, die kleiner als der Goldene Schnitt sind, aber nicht in irgendeinen Newman-Turm passen, egal wie hoch der Newman-Turm wird.

Der neue Rekord: Sie fanden einen Turm 10. Grades mit einer Größe von etwa 1,419. Dies ist der kleinste bisher gefundene „unmögliche" Turm.
Die Implikation: Dies drückt die „Sicherheitsgrenze" nach unten. Wenn es eine magische Zahl gibt (nennen wir sie $\sigma$ ), die garantiert, dass ein Turm passt, muss diese Zahl kleiner als 1,419 sein.

4. Das „Doppelte-Problem"-Experiment

Im letzten Abschnitt untersuchten die Autoren einen berühmten mathematischen Turm namens Lehmersches Polynom. Sie drehten ihn von innen nach außen (Substitution von $x$ durch $-x$ ), um einen neuen Turm zu erhalten, nennen wir ihn $l(x)$ .

Sie fragten: Können wir einen Newman-Turm bauen, der durch $l(x)$ quadriert ( $l(x)^2$ ) teilbar ist?

Das Ergebnis: Ja! Sie nutzten ihre Computersuche, um Newman-Türme bis zum Grad 150 zu bauen, die $l(x)^2$ als Faktor enthalten. Sie lieferten sogar die Baupläne (in einem Code namens Hexadezimal) für diese riesigen Türme.

Dann stellten sie die nächste Frage: Was ist mit $l(x)$ kubiert ( $l(x)^3$ )?

Das Ergebnis: Sie prüften bis zum Grad 160 und fanden nichts. Kein Newman-Turm dieser Größe konnte durch $l(x)^3$ geteilt werden. Dies deutet darauf hin, dass, obwohl man das Quadrat dieses berühmten Turms unterbringen kann, die Kubikform vielleicht gar nicht unterzubringen ist (oder zumindest unglaublich schwer zu finden ist).

Zusammenfassung

Betrachten Sie dieses Paper als eine Detektivgeschichte über das Einpassen von Formen in eine Box:

Die Box: Newman-Polynome (nur 0er und 1er).
Die Objekte: Ganzzahl-Polynome mit kleinen „Größen" (Mahler-Maß).
Die Entdeckung: Die meisten kleinen Objekte passen perfekt in die Box.
Die Ausnahme: Es gibt einige spezifische Objekte, die klein genug sind, um so auszusehen, als würden sie passen, aber sie tun es nicht. Die Autoren fanden den bisher kleinsten, was beweist, dass die „Grenze" für das Einpassen niedriger ist als gedacht.
Der Bonus: Sie bauten erfolgreich riesige Boxen, die spezifische komplexe Formen enthalten (quadratische und kubische Versionen des Lehmer-Polynoms), was zeigt, wie flexibel diese 0-und-1-Türme sein können.

Das Paper schließt damit, dass wir zwar viele dieser Einpass-Rätsel gelöst haben, einige jedoch ungelöst bleiben und die Suche nach der ultimativen „Grenze" dessen, was passt, weitergeht.

1. Problemstellung

Der Artikel behandelt die fundamentale Frage der algebraischen Zahlentheorie bezüglich Newman-Polynomen (Polynome mit Koeffizienten in $\{0, 1\}$ und einem konstanten Term von 1). Insbesondere untersucht er die Bedingungen, unter denen ein Polynom mit ganzzahligen Koeffizienten $p(x)$ ein Newman-Polynom teilt.

Die Kernfrage ist, ob eine universelle Konstante $\sigma$ existiert, sodass jedes Polynom mit ganzzahligen Koeffizienten $p(x)$ mit:

Keine nicht-negativen reellen Nullstellen und
Mahler-Maß $M(p) < \sigma$ ,
notwendigerweise ein Newman-Polynom teilt.

Frühere Arbeiten zeigten, dass, wenn $M(p) < 2$ gilt, $p(x)$ ein Polynom mit Koeffizienten in $\{-1, 0, 1\}$ teilt. Die Einschränkung der Koeffizienten auf $\{0, 1\}$ ist jedoch eine viel strengere Bedingung. Während der Goldene Schnitt ( $g \approx 1,618$ ) zunächst als natürliche Schranke angesehen wurde, wurden Gegenbeispiele mit Mahler-Maßen um 1,556 gefunden. Der Artikel zielt darauf ab, diese Schranke zu verfeinern und die Teilbarkeitseigenschaften von Polynomen mit kleinen Mahler-Maßen zu bestimmen.

2. Methodik

Die Autoren kombinieren Mixed-Integer Linear Programming (MILP) und algorithmische Zertifizierung, um zwei unterschiedliche Probleme zu lösen: das Finden von Newman-Multiplen und die Zertifizierung des Nicht-Existierens solcher Multiplen.

A. Suche nach Newman-Multiplen (MILP-Ansatz)

Um zu bestimmen, ob ein gegebenes Polynom $p(x)$ ein Newman-Polynom teilt, formulieren die Autoren das Problem als System linearer Ungleichungen.

Formulierung: Gegeben ein normiertes Polynom $p(x)$ vom Grad $2d$ , suchen sie ein Polynom $q(x)$ , sodass das Produkt $N(x) = p(x)q(x)$ Koeffizienten in $\{0, 1\}$ besitzt.
Nebenbedingungen: Da die konstanten Terme von $p$ und $q$ 1 sind, ist der konstante Term von $N$ ebenfalls 1. Die Koeffizienten von $N(x)$ sind lineare Kombinationen der unbekannten Koeffizienten von $q(x)$ . Die Bedingung, dass alle Koeffizienten von $N(x)$ entweder 0 oder 1 sein müssen, erzeugt ein System linearer Ungleichungen mit ganzzahligen Unbekannten.
Implementierung: Die Autoren implementierten dies in Julia unter Verwendung der Modellierungssprache JuMP und des Optimierers Gurobi. Sie suchten nach Lösungen, bei denen der Grad des resultierenden Newman-Polynoms 1000 nicht überschritt.

B. Zertifizierung der Nicht-Teilbarkeit (Erreichbarkeitsansatz)

Um zu beweisen, dass ein Polynom kein Newman-Polynom teilt, nutzen die Autoren eine algorithmische Methode, die von Hare und Mossinghoff eingeführt wurde.

Prinzip: Sei $\beta$ eine Nullstelle des Kandidatenpolynoms. Sie definieren eine Menge $N'(\beta, d)$ , die die Werte $F(\beta)$ für alle Newman-Polynome $F$ vom Grad $\le d$ darstellt, eingeschränkt auf eine spezifische Scheibe $I'(\beta)$ .
Algorithmus: Die Menge wird rekursiv aufgebaut. Wenn die Menge stabilisiert (d. h. $N'(\beta, d+1) = N'(\beta, d)$ ) und innerhalb dieser Menge niemals 0 erreicht wird, ist bewiesen, dass $\beta$ keine Nullstelle eines Newman-Polynoms ist. Folglich teilt das Minimalpolynom von $\beta$ kein Newman-Polynom.
Implementierung: Dies wurde unabhängig in Julia (unter Verwendung von Polynomials.jl und Nemo.jl) sowie in GP/PARI implementiert, um eine Kreuzvalidierung sicherzustellen.

C. Konstruktion von Multiplen mit wiederholten Nullstellen

Die Autoren passten den MILP-Ansatz an, um Newman-Polynome zu finden, die durch $l(x)^2$ teilbar sind, wobei $l(x)$ das Lehmer-Polynom mit $x \to -x$ ist.

Methode: Anstelle von Ungleichungen lösten sie ein System linearer Gleichungen, das sich aus dem Rest der euklidischen Division $N(x) = g(x)H(x) + R(x)$ ergibt. Die Bedingung $g(x) | N(x)$ erfordert $R(x) = 0$ .
Optimierung: Sie lösten nach binären Koeffizienten $a_i \in \{0, 1\}$ , um die Bedingungen des verschwindenden Rests zu erfüllen.

3. Hauptergebnisse

A. Teilbarkeit von Polynomen mit kleinem Mahler-Maß

Die Autoren analysierten einen Datensatz von 8.438 bekannten Polynomen mit Mahler-Maß $< 1,3$ und Grad $\le 180$ (bekannt als Known180).

Ergebnis: Mit Ausnahme von Polynomen mit positiven reellen Nullstellen teilen alle außer drei Polynome in dieser Liste ein Newman-Polynom vom Grad $\le 1000$ .
Satz: Jedes Polynom mit ganzzahligen Koeffizienten vom Grad $\le 44$ mit $M(p) < 1,3$ , ohne nicht-negative reelle Nullstellen und ohne zyklotomische Faktoren, teilt ein Newman-Polynom. Dies basiert auf der Tatsache, dass Known180 bis zum Grad 44 vollständig ist.
Offene Fälle: Drei spezifische Polynome bleiben ungelöst (kein Newman-Multiple bis zum Grad 1000 gefunden), sodass die Frage offen bleibt, ob sie Newman-Polynome höheren Grades teilen.

B. Verbesserung der universellen Konstante $\sigma$

Mithilfe der Zertifizierungsmethode identifizierten die Autoren neue Polynome, die kein Newman-Polynom teilen, wodurch die obere Schranke für die hypothetische Konstante $\sigma$ gesenkt wurde.

Neue Schranke: Sie entdeckten ein Polynom vom Grad 10:
$x^{10} - x^8 - x^5 + x + 1$
mit einem Mahler-Maß von ungefähr 1,419404632.
Bedeutung: Dies verbessert die bisher beste bekannte obere Schranke von $\approx 1,4366$ (Drungilas et al., 2023) und die frühere Schranke von $\approx 1,556$ (Hare & Mossinghoff). Falls eine Konstante $\sigma$ existiert, muss sie $\le 1,419404632$ sein.
Datensatz: Der Artikel liefert eine Tabelle mit 33 zertifizierten Beispielen (Grade 8–12) mit Mahler-Maßen $\le 1,556$ , die kein Newman-Polynom teilen.

C. Newman-Polynome mit wiederholten Nullstellen

Die Autoren untersuchten Newman-Polynome, die durch $l(x)^2$ teilbar sind (wobei $l(x)$ das transformierte Lehmer-Polynom ist).

Ergebnisse: Sie konstruierten explizit Newman-Polynome, die durch $l(x)^2$ teilbar sind, mit Graden bis zu 150.
Negatives Ergebnis: Sie bewiesen, dass kein Newman-Polynom vom Grad $\le 160$ durch $l(x)^3$ teilbar ist. Dies erweitert Mossinghoffs vorherige Verifikation (die bei Grad 120 endete).
Daten: Der Artikel liefert eine umfassende Tabelle dieser Polynome, kodiert im Hexadezimalformat.

4. Bedeutung und Beiträge

Verfeinerung der Schranken: Der Artikel verschärft die theoretischen Schranken bezüglich der Existenz von Newman-Multiplen erheblich und drückt die bekannte „verbotene" Mahler-Maß-Schwelle von $\approx 1,436$ auf $\approx 1,419$ herab.
Algorithmischer Rahmen: Er demonstriert die Wirksamkeit von Mixed-Integer Linear Programming (MILP) bei der Lösung zahlentheoretischer Probleme, die Polynome mit eingeschränkten Koeffizienten betreffen. Die Methode erweist sich als flexibel genug, um sowohl Ungleichungsnebenbedingungen (Finden von Multiplen) als auch Gleichungsnebenbedingungen (Auslöschen von Resten) zu handhaben.
Umfassende Daten: Die Autoren stellen einen vollständigen Datensatz (Known180-Analyse, zertifizierte Nicht-Teiler und konstruierte Multiplen) für weitere Forschung zur Verfügung, einschließlich Verifikationsskripten in GP/PARI.
Lösung offener Fragen: Die Arbeit bestätigt, dass für Polynome niedrigen Grades ( $\le 44$ ) mit kleinem Mahler-Maß das Hindernis für die Teilbarkeit eines Newman-Polynoms fast ausschließlich das Vorhandensein positiver reeller Nullstellen ist, mit nur drei geringfügigen Ausnahmen, die weitere Suchen in höheren Graden erfordern.

5. Fazit

Der Artikel kommt zu dem Schluss, dass das Vorhandensein einer universellen Konstante $\sigma$ zwar eine offene Frage bleibt, der Suchraum für Gegenbeispiele jedoch drastisch eingegrenzt wurde. Die Autoren schlagen vor, dass ihr auf MILP basierender Rahmen ein leistungsfähiges Werkzeug für zukünftige Untersuchungen von Borwein-, Littlewood- und Newman-Polynomen ist, das potenziell weitere Verbesserungen der Schranken und die Entdeckung neuer struktureller Eigenschaften von Polynomen mit eingeschränkten Koeffizienten ermöglicht.