🔢 mathematics

An AI Proof of 18-Variable Undecidability for Diophantine Equations over $\mathbb Z[i]$

Dit artikel presenteert een door AI gegenereerd bewijs dat de oplosbaarheid van Diophantische vergelijkingen over de Gaussische gehele getallen onbeslisbaar is met slechts 18 variabelen, waarmee de eerdere grens van 20 variabelen van Matiyasevich en Sun wordt verbeterd door geoptimaliseerde technieken voor het besparen van variabelen.

Oorspronkelijke auteurs: Yuchen Ding, Junfeng Li

Gepubliceerd 2026-06-12

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yuchen Ding, Junfeng Li

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

De Grote Visie: De "Onoplosbare Puzzel"

Stel je voor dat je een enorme, magische puzzeldoos hebt. In de doos zit een complexe vergelijking (een wiskundig probleem) met veel onbekende getallen (variabelen). Jouw doel is om te achterhalen: "Heeft deze vergelijking een oplossing?"

Al een lange tijd wisten wiskundigen dat als je genoeg variabelen hebt, deze vraag onmogelijk te beantwoorden is met een computerprogramma. Het is alsof je probeert een regelboek te schrijven dat kan vertellen of elke mogelijke doolhof een uitgang heeft; uiteindelijk worden de doolhoven zo kronkelig dat geen enkel regelboek ze allemaal kan dekken.

Dit paper gaat over een specifiek type puzzeldoos genaamd Gaussische getallen (getallen die eruitzien als $a + bi$, waarbij $i$ de vierkantswortel van -1 is). De auteurs, Yuchen Ding en Junfeng Li, gebruikten een AI om te bewijzen dat als je puzzeldoos 18 onbekenden heeft, er geen computerprogramma bestaat dat altijd kan vertellen of er een oplossing bestaat.

Het Vorige Record: 20 Variabelen

Vóór dit paper was het best bekende resultaat (door wiskundigen Matiyasevich en Sun) dat je 20 onbekenden nodig had om de puzzel onoplosbaar te maken. Zij hadden een specifiek recept om deze onmogelijke puzzels te bouwen.

De auteurs van dit paper zeiden: "Wij kunnen het met minder stukjes." Het lukte hen om het recept te verkleinen van 20 stukjes naar 18.

Hoe Ze Het Deden: Twee Slimme Trucs

Om te begrijpen hoe ze twee variabelen hebben bespaard, stel je voor dat je een machine bouwt om te testen of een getal "echt" (een geheel getal) is binnen een wereld van complexe getallen.

Truc 1: De "Geen Extra Beker"-Strategie

De Oude Manier:
Stel je voor dat je een recept hebt dat vereist dat je ingrediënten mengt, maar de instructies bevatten breuken. Om de wiskunde werkbaar te maken voor een computer, heb je meestal een extra beker nodig (een nieuwe variabele) om de noemers (de onderkant van de breuken) weg te werken, zodat alles een geheel getal wordt. Deze extra beker neemt ruimte in beslag binnen je limiet van 20 variabelen.

De Nieuwe Manier:
De auteurs realiseerden zich dat ze die extra beker niet nodig hadden. In plaats van een nieuwe variabele toe te voegen om de breuken op te schonen, voegden ze simpelweg twee strikte regels toe aan de bestaande ingrediënten.

Analogie: In plaats van een nieuwe emmer mee te brengen om de gemorste vloeistof op te vangen, hebben ze de deksels van de bestaande emmers gewoon strakker aangetrokken zodat er niets kon morsen.
Resultaat: Ze bespaarden één variabele door de wiskunde "schoon" te houden zonder een hulpvariabele nodig te hebben.

Truc 2: Het "Magische Sleutel"-Gadget

De Oude Manier:
In het oude recept, om te garanderen dat een specifiek getal niet nul was (wat cruciaal is voor het werken van de puzzel), hadden ze twee aparte variabelen nodig die fungeerden als een "veiligheidscontrole". Het was alsof je twee verschillende sleutels gebruikte om een deur te openen, alleen maar om te controleren of deze niet klemde.

De Nieuwe Manier:
De auteurs hebben een speciaal "Magische Sleutel"-gadget uitgevonden. Ze creëerden een specifieke formule: $(2R + 1)(3R + 1)$ .

De Magie: Deze formule is nooit gelijk aan nul, ongeacht welk getal je erin stopt. Echter, als je een niet-nul getal hebt dat je wilt "controleren", kun je een waarde voor $R$ vinden waardoor deze formule deelbaar is door jouw getal.
De Besparing: Omdat deze enkele formule het werk van twee aparte veiligheidscontroles doet, hadden ze slechts één variabele ( $R$ ) nodig in plaats van twee.
Resultaat: Ze bespaarden de tweede variabele.

De Eindtelling

Door deze twee trucs te combineren, verminderden ze het totaal aantal onbekenden dat nodig is om te bewijzen dat de puzzel onoplosbaar is:

10 variabelen voor de hoofd-puzzel (uit eerder werk).
3 variabelen voor de eerste "gehele getal test" (controleren of getallen gehele getallen zijn).
3 variabelen voor de tweede "gehele getal test".
1 variabele voor de "combinatie"-stap.
1 variabele voor het "Magische Sleutel"-gadget.
Totaal: 18 variabelen.

Wat Dit Betekent

Het paper bewijst dat voor elk computerprogramma er een limiet is aan hoeveel variabelen het kan afhandelen voordat het probleem onoplosbaar wordt.

Vóór: De limiet was bekend als 20.
Nu: De limiet is bewezen als 18 (of misschien zelfs lager, maar 18 is de nieuw bevestigde bodem).

De auteurs benadrukken dat ze niet het absoluut laagste mogelijke aantal hebben gevonden (misschien is het 17 of 16), maar dat ze erin zijn geslaagd de lat van 20 naar 18 te verlagen met behulp van deze twee specifieke "ruimtebesparende" trucs.

Samenvatting

Beschouw het als het inpakken voor een reis. De oude regel luidde: "Je hebt 20 koffers nodig om al je kleding mee te nemen." Deze auteurs keken naar de kleding, realiseerden zich dat ze de kleding compacter konden vouwen (Truc 1) en een compressiezak konden gebruiken (Truc 2), en bewezen: "Eigenlijk heb je maar 18 koffers nodig."

Dit betekent niet dat de reis makkelijker is; het betekent alleen dat de drempel van "onmogelijkheid" bereikt wordt met minder middelen dan we voorheen dachten.

Technische Samenvatting: Een AI-bewijs van 18-variabele onbeslisbaarheid voor Diofantische vergelijkingen over $\mathbb{Z}[i]$

Probleemstelling
Dit artikel behandelt de vorm van Hilbert's tiende probleem over de ring van Gaussische gehele getallen, $\mathbb{Z}[i]$ . Het probleem vraagt naar een algoritme om te beslissen of een willekeurige polynoomvergelijking over een gegeven ring een oplossing heeft. Terwijl de onbeslisbaarheid van dit probleem over de gehele getallen $\mathbb{Z}$ werd vastgesteld door de stelling van Matiyasevich, Davis, Putnam en Robinson, betreft een natuurlijke verfijning hiervan het minimum aantal onbekenden dat vereist is om onbeslisbaarheid te handhaven. Vorig werk door Matiyasevich en Sun stelde vast dat onbeslisbaarheid standhoudt voor vergelijkingen met 20 onbekenden over $\mathbb{Z}[i]$ . Dit artikel presenteert een bewijs dat deze grens reduceert naar 18 onbekenden.

Methodologie en Raamwerk
Het bewijs behoudt het algemene raamwerk dat door Matiyasevich en Sun is vastgesteld, welke steunt op drie kerncomponenten:

Sun's Fixed-Variable Theorem: Het gebruik van een recursief opsombare maar niet-recursieve verzameling $A \subseteq \mathbb{N}$ en een polynoom $P(Z_0, \dots, Z_{10})$ waarvoor lidmaatschap in $A$ equivalent is aan het bestaan van oplossingen in gehele getallen voor $P(a, z_1, \dots, z_{10}) = 0$ met $z_{10} \neq 0$ .
Diofantische Test voor Rationale Hele Getallen: Het gebruik van een specifieke polynoomtest (Lemma 3) om te bepalen of elementen in $\mathbb{Z}[i]$ daadwerkelijk rationale gehele getallen zijn.
Rationaliteitscriterium: Het toepassen van een criterium (Lemma 4) over $\mathbb{Q}(i)$ om variabelen te dwingen rationele gehele getallen te zijn op basis van de rationaliteit van een specifiek geconstrueerde som.

De auteurs bereiken de reductie van 20 naar 18 variabelen door twee specifieke modificaties aan te brengen in de vorige constructie:

Belangrijkste Bijdragen en Technische Modificaties

Eliminatie van de Variabele voor het Wegwerken van Noemers:
In de constructie met 20 variabelen werd een hulpvariabele geïntroduceerd om noemers weg te werken bij het toepassen van het rationaliteitscriterium. De auteurs vervangen dit door twee directe integer-condities die worden opgelegd aan de variabelen $Z_1, \dots, Z_{10}$ .
Laat $Y = 2 \prod_{k=1}^{10} (3Z_k + 1)$ . In plaats van een variabele toe te voegen om noemers weg te werken, legt het bewijs de condities op:
$Y^{10} \in \mathbb{Z} \quad \text{en} \quad Y^{11} + \sum_{k=1}^{10} Z_k Y^{10-k} \in \mathbb{Z}.$
Omdat $Y \neq 0$ , zorgen deze condities ervoor dat de hoeveelheid $Y + \sum Z_k Y^{-k}$ een rationaal getal is. Door het rationaliteitscriterium worden alle $Z_k$ hiermee gedwongen rationale gehele getallen te zijn. Deze modificatie bespaart één variabele.
Absorptie van de Niet-Nul Conditie via een Eén-Variabele Gadget:
De vorige constructie vereiste twee variabelen om een niet-nul conditie af te dwingen (specifiek voor de productterm $Z_{10}V_0V_1$ ). De auteurs introduceren een één-variabele polynoom-gadget $Q(R) = (2R + 1)(3R + 1)$ .
- Eigenschappen: $Q(R)$ verdwijnt nooit op $\mathbb{Z}[i]$ . Bovendien bestaat er voor elke niet-nul integer $n$ een integer $R$ waarvoor geldt dat $n \mid Q(R)$ .
- Toepassing: Deze gadget wordt geïntegreerd in de "relation-combining lemma" (Lemma 2). In plaats van een aparte vergelijking om het niet-verdwijnen af te dwingen, wordt de conditie geabsorbeerd in de enkele vergelijking $f(C_0, C_1, N, Q(R), M) = 0$ . Als $N=0$ , reduceert de vergelijking tot $Q(R)^4 = 0$ , wat onmogelijk is. Zo dwingt de vergelijking impliciet af dat $N \neq 0$ zonder een extra variabele te vereisen. Deze modificatie bespaart een tweede variabele.

Variabele-overzicht
Het resulterende systeem maakt exact gebruik van 18 variabelen:

$Z_1, \dots, Z_{10}$ : De 10 variabelen uit de fixed-variable input van Sun.
$V_0, X_0, Y_0$ en $V_1, X_1, Y_1$ : Twee sets van 3 variabelen die worden gebruikt voor de integer-tests op $U_0 = Y^{10}$ en $U_1 = W$ (waarbij $W$ is afgeleid van de som).
$M$ : De combinerende variabele uit de relation-combining lemma.
$R$ : De enkele variabele van de niet-nul gadget.
Totaal: $10 + 3 + 3 + 1 + 1 = 18$ .

Hoofdresultaat
Het artikel bewijst Stelling 1: Er bestaat geen algoritme om te beslissen of een willekeurige polynoomvergelijking $F(X_1, \dots, X_{18}) = 0$ met coëfficiënten in $\mathbb{Z}$ een oplossing heeft in $\mathbb{Z}[i]^{18}$ .

Het bewijs toont aan dat lidmaatschap van de niet-recursieve verzameling $A$ kan worden gerepresenteerd door een enkele polynoomvergelijking over $\mathbb{Z}[i]$ in 18 onbekenden. Volgens Lemma 1 kunnen de eindige stelsels van vergelijkingen die voortvloeien uit de constructie worden gecombineerd tot een enkele polynoomvergelijking zonder nieuwe variabelen te introduceren, waarbij de integer-coëfficiënten behouden blijven.

Betekenis en Claims
De auteurs stellen dat dit resultaat de 20-onbekende stelling van Matiyasevich en Sun verbetert door het aantal variabelen met twee te reduceren. Het artikel merkt expliciet op dat het geen aanspraak maakt op absolute optimaliteit; het verder verlagen van het aantal (bijv. naar 17) zou aanvullende verbeteringen vereisen, zoals een kleinere integer-test, een gedeelde getuige voor de integer-condities, een sterkere fixed-variable input, of een andere combinerende mechanisme. Het werk dient als een technische verfijning binnen het gevestigde raamwerk van de Diofantische onbeslisbaarheid over Gaussische gehele getallen.