🔢 mathematics

Algorithmic aspects of Newman polynomials and their divisors

Dit artikel onderzoekt welke gehele polynomen Newman-polynomen delen door bekende voorbeelden met lage Mahler-maat te analyseren, specifieke polynomen te identificeren die geen enkel Newman-polynoom delen (waardoor de bovengrens voor een potentiële universele constante $\sigma$ wordt verbeterd), en de maximale macht van Lehmer's polynoom te bepalen die een Newman-polynoom kan delen binnen specifieke graadlimieten.

Oorspronkelijke auteurs: Musbahu Idris, Jean-Marc Sac-Épée

Gepubliceerd 2026-04-29

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Musbahu Idris, Jean-Marc Sac-Épée

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een meesterbouwer bent die werkt met een zeer specifieke set Lego-blokken. Deze blokken zijn speciaal: ze komen alleen in twee kleuren, Wit (die het getal 1 voorstelt) en Zwart (die het getal 0 voorstelt). Je kunt alleen torens (polynomen) bouwen met deze twee kleuren, en elke toren moet beginnen en eindigen met een Wit blok. In de wiskundige wereld worden deze Newman-polynomen genoemd.

De auteurs van dit artikel stellen een fundamentele vraag: Kan elk ander type wiskundige "toren" worden gebouwd binnen een van deze speciale Wit-en-Zwart-torens?

Meer specifiek kijken ze naar "gehele torens" (polynomen met gehele getallen als coëfficiënten) die een bepaalde eigenschap hebben, genaamd een lage Mahler-maatstaf. Denk aan de Mahler-maatstaf als een "grootte"- of "complexiteits"-score. Hoe lager de score, hoe "kleiner" of "simpeler" de toren is.

Hier is een uiteenzetting van hun reis en ontdekkingen:

1. De Grote Vraag

Wiskundigen wisten al dat als je toestaat dat je blokken Rood, Wit en Zwart zijn (de getallen -1, 0 en 1), dan kan bijna elke kleine, simpele gehele toren worden gevonden binnen een grotere toren gemaakt van die drie kleuren.

Maar wat als je strikt verboden bent om Rode blokken te gebruiken? Wat als je alleen Wit en Zwart mag gebruiken? Geldt de regel dan nog steeds? Past elke kleine, simpele gehele toren nog steeds binnen een Wit-en-Zwart-toren?

2. De Grote Zoektocht (De "Known180"-lijst)

De auteurs besloten dit te testen op een enorme lijst van 8.438 bekende "kleine" torens (die met een Mahler-maatstaf kleiner dan 1,3). Ze schreven een computerprogramma om te fungeren als een zoeklicht.

De Methode: Voor elke kleine toren op de lijst probeerde de computer een "partner"-toren (gemaakt van gehele getallen) te vinden, zodat wanneer je ze met elkaar vermenigvuldigt, het resultaat een perfecte Wit-en-Zwart Newman-toren is.
De Beperking: De computer kreeg de opdracht om te stoppen met zoeken als de resulterende toren te hoog werd (graad hoger dan 1.000).
De Resultaten:
- Het "Positieve Wortel"-probleem: Eerst verwijderden ze elke toren die een "positieve reële wortel" had. Stel je een toren voor die een zwakke plek heeft aan de zonzijde; wiskundig gezien kunnen deze nooit binnen een Newman-toren passen.
- Het Succes: Voor bijna elke overgebleven toren vond de computer een match! Het bewees dat als een toren klein genoeg is (graad 44 of lager) en die "zwakke plekken" niet heeft, deze wel binnen een Newman-toren kan worden gebouwd.
- Het Mysterie: Er waren drie koppige torens op de lijst waar de computer geen match kon vinden binnen de limiet van 1.000 graden. De auteurs zeiden niet dat deze onmogelijk zijn, alleen dat ze nog geen partner voor hen hebben gevonden.

3. De "Gouden Snede"-Muur

Er was een lang bestaand geloof dat de "Gouden Snede" (ongeveer 1,618) de limiet was. Het idee was: "Als je toren kleiner is dan de Gouden Snede, past hij."

De auteurs (en anderen die ze citeren) bewezen dat dit onjuist was. Ze vonden specifieke torens die kleiner zijn dan de Gouden Snede, maar die niet binnen een Newman-toren passen, ongeacht hoe hoog de Newman-toren wordt.

Het Nieuwe Record: Ze vonden een 10e-graads toren met een grootte van ongeveer 1,419. Dit is de kleinste "onmogelijke" toren die tot nu toe is gevonden.
De Implicatie: Dit duwt de "veiligheidslimiet" naar beneden. Als er een magisch getal is (laten we het $\sigma$ noemen) dat garandeert dat een toren past, dan moet dat getal lager zijn dan 1,419.

4. Het "Dubbele Probleem"-Experiment

In het laatste gedeelte keken de auteurs naar een beroemde wiskundige toren genaamd het polynoom van Lehmer. Ze draaiden het ondersteboven (door $x$ te vervangen door $-x$ ) om een nieuwe toren te krijgen, laten we die $l(x)$ noemen.

Ze vroegen zich af: Kunnen we een Newman-toren bouwen die deelbaar is door $l(x)$ in het kwadraat ( $l(x)^2$ )?

Het Resultaat: Ja! Ze gebruikten hun computersonderzoek om Newman-torens tot graad 150 te bouwen die $l(x)^2$ als factor bevatten. Ze leverden zelfs de blauwdrukken (in een code genaamd hexadecimaal) voor deze enorme torens.

Toen stelden ze de volgende vraag: Wat dacht je van $l(x)$ in de derde macht ( $l(x)^3$ )?

Het Resultaat: Ze controleerden tot graad 160 en vonden niets. Geen enkele Newman-toren van die grootte kon worden gedeeld door $l(x)^3$ . Dit suggereert dat hoewel je het kwadraat van deze beroemde toren kunt passen, de kubus misschien helemaal niet past (of in ieder geval ontzettend moeilijk te vinden is).

Samenvatting

Beschouw dit artikel als een detectiveverhaal over het passen van vormen in een doos:

De Doos: Newman-polynomen (alleen 0'en en 1'en).
De Objecten: Gehele polynomen met kleine "groottes" (Mahler-maatstaf).
De Ontdekking: De meeste kleine objecten passen perfect binnen de doos.
De Uitzondering: Er zijn een paar specifieke objecten die klein genoeg zijn om eruit te zien alsof ze zouden moeten passen, maar dat doen ze niet. De auteurs vonden de kleinste tot nu toe, wat bewijst dat de "limiet" voor passen lager is dan we dachten.
De Bonus: Ze bouwden succesvol enorme dozen die specifieke complexe vormen bevatten (de gekwadrateerde en gekubede versies van het polynoom van Lehmer), wat laat zien hoe flexibel deze 0-en-1-torens kunnen zijn.

Het artikel concludeert dat hoewel we veel van deze paspuzzels hebben opgelost, een paar nog onopgelost blijven, en de zoektocht naar de ultieme "limiet" van wat kan passen, doorgaat.

1. Probleemstelling

Het artikel behandelt de fundamentele vraag in de algebraïsche getaltheorie met betrekking tot Newman-polynomen (polynomen met coëfficiënten in $\{0, 1\}$ en een constante term van 1). Specifiek onderzoekt het de voorwaarden waaronder een polynoom met geheeltallige coëfficiënten $p(x)$ een Newman-polynoom deelt.

De kernvraag is of er een universele constante $\sigma$ bestaat zodanig dat elk polynoom met geheeltallige coëfficiënten $p(x)$ met:

Geen niet-negatieve reële wortels, en
Mahler-maat $M(p) < \sigma$ ,
noodzakelijkerwijs een Newman-polynoom deelt.

Vorig werk stelde vast dat als $M(p) < 2$ , $p(x)$ een polynoom deelt met coëfficiënten in $\{-1, 0, 1\}$ . Het beperken van de coëfficiënten tot $\{0, 1\}$ is echter een veel strengere voorwaarde. Hoewel de Gulden Snede ( $g \approx 1.618$ ) aanvankelijk als een natuurlijke ondergrens werd beschouwd, werden tegenvoorbeelden gevonden met Mahler-maten rond de 1.556. Het artikel beoogt deze ondergrens te verfijnen en de delingskarakteristieken van polynomen met kleine Mahler-maten te bepalen.

2. Methodologie

De auteurs maken gebruik van een combinatie van Mixed-Integer Linear Programming (MILP) en algoritmische certificering om twee verschillende problemen op te lossen: het vinden van Newman-multiples en het certificeren van het niet-bestaan van dergelijke multiples.

A. Zoeken naar Newman-multiples (MILP-benadering)

Om te bepalen of een gegeven polynoom $p(x)$ een Newman-polynoom deelt, formuleren de auteurs het probleem als een systeem van lineaire ongelijkheden.

Formulering: Gegeven een monische polynoom $p(x)$ van graad $2d$ , zoeken ze een polynoom $q(x)$ zodat het product $N(x) = p(x)q(x)$ coëfficiënten heeft in $\{0, 1\}$ .
Beperkingen: Aangezien de constante termen van $p$ en $q$ 1 zijn, is de constante term van $N$ gelijk aan 1. De coëfficiënten van $N(x)$ zijn lineaire combinaties van de onbekende coëfficiënten van $q(x)$ . De voorwaarde dat alle coëfficiënten van $N(x)$ 0 of 1 moeten zijn, creëert een systeem van lineaire ongelijkheden met geheeltallige onbekenden.
Implementatie: De auteurs hebben dit geïmplementeerd in Julia met behulp van de modelleringstaal JuMP en de Gurobi-optimizer. Ze zochten naar oplossingen waarbij de graad van het resulterende Newman-polynoom 1000 niet overschreed.

B. Certificering van Niet-delbaarheid (Bereikbaarheidsbenadering)

Om te bewijzen dat een polynoom geen Newman-polynoom deelt, maken de auteurs gebruik van een algoritmische methode geïntroduceerd door Hare en Mossinghoff.

Principe: Laat $\beta$ een wortel zijn van het kandidaat-polynoom. Ze definiëren een verzameling $N'(\beta, d)$ die de waarden $F(\beta)$ voor alle Newman-polynomen $F$ van graad $\le d$ vertegenwoordigt, beperkt tot een specifieke schijf $I'(\beta)$ .
Algoritme: De verzameling wordt recursief opgebouwd. Als de verzameling stabiliseert (d.w.z. $N'(\beta, d+1) = N'(\beta, d)$ ) en 0 binnen deze verzameling nooit wordt bereikt, is bewezen dat $\beta$ geen wortel is van een Newman-polynoom. Bijgevolg deelt het minimale polynoom van $\beta$ geen Newman-polynoom.
Implementatie: Dit werd onafhankelijk geïmplementeerd in Julia (met Polynomials.jl en Nemo.jl) en GP/PARI om kruisverificatie te waarborgen.

C. Constructie van Multiples met Herhaalde Wortels

De auteurs pasten de MILP-benadering aan om Newman-polynomen te vinden die deelbaar zijn door $l(x)^2$ , waarbij $l(x)$ het Lehmer-polynoom is met $x \to -x$ .

Methode: In plaats van ongelijkheden, losten ze een systeem van lineaire vergelijkingen op, afgeleid van de rest bij Euclidische deling $N(x) = g(x)H(x) + R(x)$ . De voorwaarde $g(x) | N(x)$ vereist dat $R(x) = 0$ .
Optimalisatie: Ze losten op voor binaire coëfficiënten $a_i \in \{0, 1\}$ om aan de voorwaarden voor het verdwijnen van de rest te voldoen.

3. Belangrijkste Resultaten

A. Deling van Polynomen met Kleine Mahler-maat

De auteurs analyseerden een dataset van 8.438 bekende polynomen met Mahler-maat $< 1.3$ en graad $\le 180$ (bekend als Known180).

Vinding: Met uitzondering van polynomen met positieve reële wortels, bleek alleen drie polynomen in deze lijst geen Newman-polynoom van graad $\le 1000$ te delen.
Stelling: Elk polynoom met geheeltallige coëfficiënten van graad $\le 44$ met $M(p) < 1.3$ , zonder niet-negatieve reële wortels en zonder cyclotomische factoren, deelt een Newman-polynoom. Dit is gebaseerd op het feit dat Known180 compleet is tot graad 44.
Onopgeloste Gevallen: Drie specifieke polynomen blijven onopgelost (geen Newman-multiple gevonden tot graad 1000), waardoor de vraag openblijft of ze Newman-polynomen van hogere graden delen.

B. Verbetering van de Universele Constante $\sigma$

Met behulp van de certificeringsmethode identificeerden de auteurs nieuwe polynomen die geen Newman-polynoom delen, waardoor de bovengrens voor de hypothetische constante $\sigma$ werd verlaagd.

Nieuwe Ondergrens: Ze ontdekten een polynoom van graad 10:
$x^{10} - x^8 - x^5 + x + 1$
met een Mahler-maat van ongeveer 1.419404632.
Betekenis: Dit verbetert de vorige beste bekende bovengrens van $\approx 1.4366$ (Drungilas et al., 2023) en de eerdere ondergrens van $\approx 1.556$ (Hare & Mossinghoff). Als een constante $\sigma$ bestaat, moet deze $\le 1.419404632$ zijn.
Dataset: Het artikel biedt een tabel met 33 gecertificeerde voorbeelden (graden 8–12) met Mahler-maten $\le 1.556$ die geen Newman-polynoom delen.

C. Newman-polynomen met Herhaalde Wortels

De auteurs onderzochten Newman-polynomen die deelbaar zijn door $l(x)^2$ (waarbij $l(x)$ het getransformeerde Lehmer-polynoom is).

Resultaten: Ze construeerden expliciet Newman-polynomen die deelbaar zijn door $l(x)^2$ met graden tot 150.
Negatief Resultaat: Ze bewezen dat geen enkel Newman-polynoom van graad $\le 160$ deelbaar is door $l(x)^3$ . Dit breidt Mossinghoffs eerdere verificatie uit (die stopte bij graad 120).
Data: Het artikel biedt een uitgebreide tabel van deze polynomen, gecodeerd in hexadecimaal formaat.

4. Betekenis en Bijdragen

Verfijning van Grenzen: Het artikel verscherpt de theoretische grenzen aanzienlijk met betrekking tot het bestaan van Newman-multiples, en duwt de bekende "verboden" Mahler-maatdrempel van $\approx 1.436$ naar beneden tot $\approx 1.419$ .
Algoritmisch Kader: Het demonstreert de doeltreffendheid van Mixed-Integer Linear Programming (MILP) bij het oplossen van getaltheoretische problemen die betrekking hebben op polynomen met beperkte coëfficiënten. De methode blijkt flexibel genoeg om zowel ongelijkheidsbeperkingen (het vinden van multiples) als gelijkheidsbeperkingen (het opheffen van resten) aan te pakken.
Uitgebreide Data: De auteurs bieden een complete dataset (Known180-analyse, gecertificeerde niet-delers en geconstrueerde multiples) die beschikbaar is voor verder onderzoek, inclusief verificatiescripts in GP/PARI.
Oplossing van Open Vragen: Het werk bevestigt dat voor polynomen van lage graad ( $\le 44$ ) met kleine Mahler-maat, de belemmering voor het delen van een Newman-polynoom bijna uitsluitend het aanwezig zijn van positieve reële wortels is, met slechts drie kleine uitzonderingen die wachten op zoektochten naar hogere graden.

5. Conclusie

Het artikel concludeert dat hoewel het bestaan van een universele constante $\sigma$ een open vraag blijft, de zoekruimte voor tegenvoorbeelden drastisch is ingeperkt. De auteurs suggereren dat hun op MILP gebaseerde kader een krachtig hulpmiddel is voor toekomstig onderzoek naar Borwein-, Littlewood- en Newman-polynomen, wat mogelijk verdere verbeteringen in grenzen en de ontdekking van nieuwe structurele eigenschappen van polynomen met beperkte coëfficiënten mogelijk maakt.