💻 computer science

On Variable-Bounded Non-Linear Expansions of Presburger Arithmetic

Dit artikel vestigt de beslisbaarheid van enkelvariabele uitbreidingen van Presburger-rekenkunde voor perfecte vaste machten en kubische polynomen door gebruik te maken van resultaten over hyperelliptische Diophantische vergelijkingen en algebraïsche krommen met laag geslacht, terwijl wordt aangetoond dat het opheffen van deze beperkingen leidt tot onbeslisbaarheid via coderingen van open Diophantische problemen.

Oorspronkelijke auteurs: Piotr Bacik, Joris Nieuwveld, Joël Ouaknine, Mihir Vahanwala, Madhavan Venkatesh, Emil Rugaard Wieser

Gepubliceerd 2026-05-19

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Piotr Bacik, Joris Nieuwveld, Joël Ouaknine, Mihir Vahanwala, Madhavan Venkatesh, Emil Rugaard Wieser

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 detective bent die probeert een enorm raadsel op te lossen. Het raadsel is een reeks wiskundige regels over gehele getallen (zoals 1, 2, 3, -5, enzovoort). Je doel is om te bepalen of een specifieke uitspraak over deze getallen waar of onwaar is.

In de wereld van de wiskunde heet dit Presburger-aritmetiek. Het is als een spel met strikte regels: je mag optellen, aftrekken, groottes vergelijken en controleren of getallen even of oneven zijn. Lange tijd wisten we dat dit spel "oplosbaar" (beslisbaar) was—dat wil zeggen dat er een gegarandeerde methode bestaat om elk vraag te beantwoorden dat je stelt, zelfs als het lang duurt.

Echter, het artikel waar je naar vraagt, onderzoekt wat er gebeurt wanneer we nieuwe, lastige regels aan dit spel toevoegen. Specifiek voegen we regels toe over polynomen (wiskundige uitdrukkingen zoals $x^2$ , $x^3$ , of $2n^3 - 5n + 3$ ).

Het Grote Probleem: De Valstrik van "Te Veel Variabelen"

De auteurs leggen uit dat als je het raadsel te ingewikkeld maakt—specifiek, als je toestaat dat veel verschillende getallen (variabelen) met deze nieuwe polynoomregels interageren—het spel onoplosbaar wordt. Het is als proberen een naald te vinden in een hooiberg die blijft groeien; geen enkele computer, hoe krachtig ook, kan een antwoord garanderen.

Dit komt omdat deze nieuwe regels krachtig genoeg zijn om het beroemde "Hilberts Tiende Probleem" te coderen, waarvan is bewezen dat het in het algemeen onoplosbaar is.

De Oplossing: De "Eén-Variabele" Afkorting

De belangrijkste ontdekking van de auteurs is een slimme omweg. Ze vragen zich af: Wat als we het spel beperken tot het gebruik van slechts één variabele per keer?

Stel je voor dat je probeert een specifiek getal $x$ te vinden dat voldoet aan een lijst met voorwaarden. Hoewel de voorwaarden complexe vormen (polynomen) bevatten, wordt het probleem weer oplosbaar als je alleen op zoek bent naar één getal.

Het artikel bewijst dat we voor raadsels met één variabele het antwoord kunnen bepalen in twee specifieke scenario's:

Het "Perfecte Macht"-Geval:
Stel je voor dat je op zoek bent naar getallen die perfecte kwadraten zijn ($1, 4, 9, 16...$), perfecte derdemachten ($1, 8, 27...$), of elke vaste macht. De auteurs tonen aan dat als je raadsel alleen deze "perfecte macht"-vormen bevat, je het kunt oplossen. Ze gebruiken diepe wiskunde over "hyperelliptische vergelijkingen" (fancy krommen) om te bewijzen dat de oplossingen ofwel eindig zijn, ofwel een voorspelbaar patroon volgen dat een computer kan controleren.
Het "Laag-Vorm"-Geval:
Stel je voor dat de vormen beperkt zijn tot simpele krommen: lijnen (graad 1), parabolen (graad 2), of kubische krommen (graad 3). De auteurs bewijzen dat als je raadsel alleen deze simpele vormen gebruikt, het ook oplosbaar is. Ze vertrouwen op het feit dat deze vormen niet genoeg "verdraaid" raken om een oneindige, onoplosbare rommel te creëren.

Hoe Ze Het Doen: De "Dichtheid"-Truc

De auteurs gebruiken een briljante strategie om te gaan met "negatieve" regels (bijvoorbeeld: "Vind een getal dat GEEN perfect kwadraat is").

De Positieve Regels: Eerst vinden ze alle getallen die voldoen aan de "positieve" regels (bijvoorbeeld: getallen die wel perfecte kwadraten zijn). Soms zijn er oneindig veel.
De Negatieve Regels: Vervolgens passen ze de "negatieve" regels toe. Ze bewijzen dat zelfs als je getallen moet uitsluiten, de getallen die je uitsluit zo schaars zijn (zoals het vinden van een paar specifieke korrels zand op een strand) dat ze niet het hele strand wegvegen.
De Conclusie: Als de "positieve" lijst oneindig is, en de "negatieve" regels slechts een klein, onbeduidend fractie ervan verwijderen, dan blijven er nog steeds oneindig veel getallen over. De computer kan zeggen: "Ja, er bestaat een oplossing!" zonder dat het exacte getal gevonden hoeft te worden.

Wereldlijke Voorbeelden uit het Artikel

De auteurs tonen aan dat deze logica beroemde historische wiskundige raadsels kan oplossen, mits ze worden geformuleerd als raadsels met één variabele:

Fermats Driehoekige Getallen: Bewijzen dat er geen driehoekig getal (zoals 1, 3, 6, 10) groter dan 1 bestaat dat ook een perfecte derdemacht is.
Fibonacci Derdemachten: Bewijzen dat 8 de grootste derdemacht is in de Fibonacci-reeks.
Catalans Vermoeden: Controleren of 9 en 8 de enige perfecte machten zijn met een verschil van precies 1.

De Grens: Wanneer Twee Variabelen het Spel Breken

Het artikel trekt ook een harde lijn. Als je twee variabelen toestaat (op zoek naar twee getallen, $x$ en $y$ , die samen werken), wordt het spel weer onoplosbaar, zelfs als je alleen perfecte kwadraten gebruikt.

Ze illustreren dit met het probleem van de "Perfecte Euler Baksteen": Kun je een rechthoekige doos bouwen waarbij alle zijden en alle diagonalen gehele getallen zijn? Dit is een probleem met drie variabelen. De auteurs tonen aan dat als we ons spel met één variabele voor twee variabelen konden oplossen, we dit bakstenen probleem zouden kunnen oplossen. Aangezien het bakstenen probleem na 300 jaar nog steeds een onopgelost mysterie is, moet ons spel met twee variabelen ook onoplosbaar zijn.

Samenvatting

Het Goede Nieuws: Als je je wiskundige raadsels beperkt tot één variabele en gebruikmaakt van ofwel "perfecte machten" ofwel "simpele krommen" (tot graad 3), kun je altijd een computerprogramma schrijven dat je vertelt of er een oplossing bestaat.
Het Slechte Nieuws: Zodra je een tweede variabele toevoegt of complexere krommen gebruikt, wordt het raadsel in het algemeen onoplosbaar.
De Methode: Ze gebruiken een mix van oude getaltheorie (Diophantische vergelijkingen) en moderne meetkunde om te bewijzen dat de "goede" raadsels patronen hebben die we kunnen benutten, terwijl de "slechte" te chaotisch zijn.

Dit artikel bouwt geen nieuwe app en geneest geen ziekte; het kaart simpelweg de grenzen aan van wat berekenbaar is in de wereld van de getallen, en laat ons precies zien waar de "magie" van oplosbaarheid eindigt en waar de "chaos" van het onbekende begint.

Technische Samenvatting: Over Variabele-Gebonden Niet-Lineaire Uitbreidingen van Presburger-Arithmetiek

Probleemstelling
Presburger-arithmetiek, de eerste-orde theorie van gehele getallen met optelling en orde, is beslisbaar. De uitbreiding ervan door niet-lineaire predikaten, zoals de verzameling van perfecte kwadraten ( $Z^2$ ) of algemene polynoomafbeeldingen, is echter in het algemeen geval bekend als onbeslisbaar. Deze onbeslisbaarheid vloeit voort uit het vermogen om vermenigvuldiging binnen deze theorieën te coderen. Hoewel de beslisbaarheid van het existentiële fragment van dergelijke uitbreidingen een groot open probleem blijft (bijvoorbeeld Büchi's conjectuur betreffende perfecte kwadraten), onderzoekt dit artikel een andere weg om beslisbaarheid te herstellen: het beperken van het aantal variabelen.

De auteurs richten zich op variabele-gebonden uitbreidingen van Presburger-arithmetiek met families van monadische polynoompredikaten. Specifiek onderzoeken ze fragmenten waarbij het aantal verschillende variabelen begrensd is door een constante $k$ (aangeduid als $FO_k$ , $\exists FO_k$ en $SMT_k$ ). De centrale uitdaging is dat zelfs voor een enkele variabele ( $k=1$ ) de beslisbaarheid van de vraag of twee polynoompredikaten elkaar snijden (bijvoorbeeld $f(u) = g(v)$ ) een sterk beperkt geval is van Hilbert's tiende probleem, wat over het algemeen open staat.

Methodologie
Het artikel maakt gebruik van een combinatie van getaltheoretische, algebraïsch-geometrische en maattheoretische technieken om de oplossingsverzamelingen van constraints binnen deze variabele-gebonden fragmenten te analyseren.

Pre-processing en Reductie: De beslissingsprocedure begint met het reduceren van willekeurige zinnen tot een vervullingsprobleem dat een conjunctie van constraints omvat. Deze constraints omvatten lineaire ongelijkheden ( $x > c$ ), modulaire rekenkunde ( $x \equiv_m c$ ) en polynoompredikaten van de vorm $R(ax+b)$ of hun negaties $\neg R(ax+b)$ . De auteurs maken gebruik van de Chinese Reststelling om modulaire constraints te consolideren en voeren een casusanalyse uit om begrende intervallen te elimineren, waardoor het probleem wordt gereduceerd tot het bepalen van de vervullbaarheid van constraints over een onbegrensd domein.
Omgaan met Positieve Constraints: De kern van de methodologie bestaat uit het karakteriseren van de oplossingsverzamelingen van systemen van positieve polynoomconstraints.
- Voor vaste machten (bijvoorbeeld $Z_k = \{n^k\}$ ) maken de auteurs gebruik van resultaten over hyperelliptische Diophantische vergelijkingen. Zij tonen aan dat de doorsnede van twee dergelijke constraints een eindige verzameling oplevert (als de graden hoog genoeg zijn) of een verzameling die geparametriseerd is door lineaire recurrente rijen (LRS) als de graden 2 zijn.
- Voor algemene polynomen van graad maximaal 3 rust de analyse op het geslacht van de resulterende algebraïsche krommen. Systemen die kubische polynomen bevatten, leiden vaak tot krommen van geslacht 1 (elliptische krommen) of hoger, die volgens Siegel's theorema of Baker's grenzen slechts eindig veel gehele punten hebben. Systemen die kwadratische polynomen bevatten, hebben betrekking op Pell-vergelijkingen, waarvan de oplossingen omkeerbare LRS vormen.
Omgaan met Negatieve Constraints (Dichtheidsargumenten): Een cruciaal inzicht is dat wanneer de oplossingsverzameling van positieve constraints oneindig is, de verzameling oplossingen die een negatieve constraint schenden (d.w.z. de positieve versie van het genegateerde predikaat voldoen), een relatieve dichtheid van nul heeft binnen de oorspronkelijke oplossingsverzameling.
- Voor polynoomafbeeldingen is de groeisnelheid van de afbeelding polynomiaal, terwijl de "verboden" verzameling (als deze voortkomt uit een ander polynoom) vaak met een andere snelheid groeit of schaars is.
- In gevallen waarin de oplossingsverzameling een LRS is, bewijzen de auteurs dat de indices van de "verboden" oplossingen rekenkundige progressies vormen. Dit maakt een effectieve controle mogelijk om te bepalen of er nog oplossingen overblijven na het uitsluiten van de nul-dichtheid subset.
Redundantie en Coalescentie: De auteurs definiëren begrippen van "redundante" en "soortgelijke" constraints. Redundante constraints kunnen worden verworpen, terwijl soortgelijke constraints kunnen worden samengevoegd tot een enkele constraint met behulp van $p$ -adische waarderingen en de Chinese Reststelling, waardoor het systeem wordt vereenvoudigd voordat de dichtheidsargumenten worden toegepast.

Belangrijkste Bijdragen en Resultaten

Het artikel stelt twee primaire beslisbaarheidsresultaten vast voor theorieën met één variabele ( $k=1$ ):

Beslisbaarheid met Vaste Machten: De theorie $FO_1\langle \mathbb{Z}; 0, 1, +, -, <, (\equiv_m)_{m\ge 2}, (Z_k)_{k\ge 2} \rangle$ is beslisbaar. Dit resultaat rust op de oplosbaarheid van hyperelliptische Diophantische vergelijkingen ( $w^k - nz^j = N$ ) en het feit dat systemen van dergelijke vergelijkingen eindig veel oplossingen hebben of oplossingen die geparametriseerd zijn door LRS.
Beslisbaarheid met Polynomen van Lage Graad: De theorie $FO_1\langle \mathbb{Z}; 0, 1, +, -, <, (\equiv_m)_{m\ge 2}, (R_i)_i \rangle$ is beslisbaar, waarbij elke $R_i$ overeenkomt met de afbeelding van een geheeltallig polynoom van graad maximaal 3. Dit resultaat maakt gebruik van het lage geslacht van de bijbehorende algebraïsche krommen (geslacht 0 of 1) en de structuur van oplossingen van simultane Pell-vergelijkingen.

Onbeslisbaarheidsresultaten
Om de grenzen van deze positieve resultaten af te bakenen, levert het artikel onbeslisbaarheidsbewijzen wanneer de variabelebegrenzing wordt opgeheven of specifieke predikaten worden gecombineerd:

Het existentiële fragment $SMT_2\langle \mathbb{Z}; 0, 1, +, -, Z^2 \rangle$ is onbeslisbaar. Dit wordt aangetoond door de ontkenning van Büchi's conjectuur te coderen, wat het definiëren van vermenigvuldiging met een beperkt aantal variabelen mogelijk maakt.
Met behulp van Jones's universele Diophantische vergelijkingen en Xiao's recente bewijs van Büchi's conjectuur, stellen de auteurs vast dat theorieën met aanzienlijk hogere variabele-aantallen (bijvoorbeeld $SMT_{600}$ of $SMT_{2200}$ met $Z^2$ ) onbeslisbaar zijn.

Betekenis
De betekenis van het artikel ligt in het identificeren van precieze grenzen waar beslisbaarheid kan worden hersteld in niet-lineaire uitbreidingen van Presburger-arithmetiek. Door het aantal variabelen te beperken tot één, tonen de auteurs aan dat diepgaande resultaten uit de Diophantische meetkunde (zoals de eindigheid van gehele punten op krommen van geslacht $\ge 2$ ) en de theorie van lineaire recurrente rijen voldoende zijn om beslissingsprocedures te construeren.

Het werk benadrukt een dichotomie: terwijl algemene niet-lineaire uitbreidingen onbeslisbaar zijn, en zelfs het existentiële fragment met twee variabelen en perfecte kwadraten onbeslisbaar is, blijft het geval met één variabele hanteerbaar voor brede families van predikaten. De auteurs merken op dat het uitbreiden van deze resultaten naar twee of drie variabelen wordt belemmerd door beroemde open problemen, zoals het bestaan van perfecte Euler-bakstenen (waarvoor 3 variabelen en $Z^2$ nodig zijn) en het probleem van de som van drie kubussen (waarvoor 2 variabelen en $Z^3$ nodig zijn). Het artikel biedt dus een rigoureus kader voor het begrijpen van de computationele complexiteit van arithmetische theorieën die worden beperkt door variabele-begrenzingen.