🔢 mathematics

Beatty Sequences for a Quadratic Irrational: Decidability and Applications

Dit artikel bewijst dat inhomogene Beatty-rijen gebaseerd op kwadratische irrationale getallen gesynchroniseerd zijn, wat leidt tot een deciderbaarheidsresultaat voor hun eerste-orde theorie met optelling en de oplossing van diverse open problemen.

Oorspronkelijke auteurs: Luke Schaeffer, Jeffrey Shallit, Stefan Zorcic

Gepubliceerd 2026-04-03

📖 4 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Luke Schaeffer, Jeffrey Shallit, Stefan Zorcic

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 enorme, oneindige rij van getallen hebt, zoals een lange trein die nooit stopt. In de wiskunde noemen we zulke rijen vaak Beatty-reeksen. Ze worden gemaakt door een magische formule: je neemt een getal $n$ (de treinwagon), vermenigvuldigt het met een speciaal, irrationaal getal (zoals de gulden snede, $\phi$ ), en ronds het af naar het dichtstbijzijnde gehele getal.

De auteurs van dit paper, Luke Schaeffer, Jeffrey Shallit en Stefan Zorcic, hebben een nieuwe manier gevonden om te begrijpen en te voorspellen wat er in deze rijen gebeurt. Ze gebruiken hiervoor een combinatie van wiskunde, computers en een beetje magie.

Hier is de uitleg in simpele taal:

1. De Magische Trein en de "Ostrowski-kaart"

Stel je voor dat je een trein hebt die rijdt op een spoor dat niet uit gewone meters bestaat, maar uit een heel speciaal soort meetlat. Deze meetlat is gebaseerd op een getal dat "kwadratisch irrationaal" heet (een getal dat je kunt schrijven met een wortel, zoals $\sqrt{2}$ of $\sqrt{5}$ ).

In de wiskunde gebruiken we voor deze getallen een speciale manier om getallen te schrijven, genaamd Ostrowski-representatie. Denk hierbij niet aan ons gewone tientallig stelsel (1, 2, 3...), maar aan een code die speciaal is gemaakt voor die magische trein.

2. De Automatische Poortwachter (De "Walnut")

Het grootste probleem met deze rijen is dat ze chaotisch lijken. Maar de auteurs zeggen: "Nee, ze zijn niet willekeurig! Ze volgen een heel strak patroon dat door een eenvoudige machine kan worden gelezen."

Ze introduceren een concept dat ze "gesynchroniseerd" noemen.

Vergelijking: Stel je voor dat je twee mensen hebt: één die de treinwagonnummer ( $n$ ) roept, en één die het resultaat ( $y$ ) roept.
De Automaat: De auteurs tonen aan dat er een kleine, simpele robot (een eindige automaat) bestaat die naar beide nummers kijkt. Als de robot de nummers in die speciale Ostrowski-code ziet, kan hij met 100% zekerheid zeggen: "Ja, dit $y$ is precies wat je krijgt als je $n$ in de formule stopt!" of "Nee, dat klopt niet."

Deze robot is zo simpel dat hij in een computerprogramma genaamd Walnut past. Walnut is als een super-rekenmachine die niet alleen rekent, maar ook logische bewijzen kan vinden.

3. Wat kunnen we hiermee? (De Kracht van de Robot)

Omdat we deze robot hebben, kunnen we vragen stellen die voorheen onmogelijk leken te beantwoorden. Het is alsof je een sleutel hebt die elk slot in de wiskundige wereld opent.

Hier zijn een paar voorbeelden van wat ze hebben gedaan:

De "Basis" van de Getallen: Kunnen we met deze rij getallen elk ander getal maken door ze bij elkaar op te tellen? (Bijvoorbeeld: kun je het getal 100 maken door twee getallen uit de rij bij elkaar op te tellen? Of drie? Of tien?). De robot kan dit voor elke rij bepalen. Het antwoord is vaak: "Ja, en je hebt maximaal $X$ getallen nodig."
Het Oplossen van Raadsels: Er waren oude raadsels van wiskundigen (zoals Don Reble en Graham) die al jaren onopgelost lagen. Ze vroegen zich af of bepaalde patronen in deze rijen zouden voorkomen. De auteurs draaiden hun formule in Walnut, en binnen een seconde gaf de computer het antwoord: "Ja, het patroon bestaat" of "Nee, het bestaat niet."
De "Gouden" Verhouding: Ze hebben bewezen dat voor de beroemdste rijen (zoals die met de gulden snede, $\phi$ ), we alles kunnen bewijzen wat we maar willen over hun optelling.

4. De "Terugwaartse" Magie

Een heel cool deel van het paper is dat ze ook het omgekeerde hebben bewezen. Als je een rij hebt die eruitziet alsof hij door zo'n robot kan worden gelezen, dan moet die rij per definitie gemaakt zijn van een kwadratisch irrationaal getal. Het is alsof je een vingerafdruk hebt: als de afdruk past, weet je precies wie de dader is.

Samenvatting in één zin

De auteurs hebben een brug gebouwd tussen de chaotische wereld van speciale getallenrijen en de strakke wereld van computerrobots, waardoor we nu met een druk op de knop (via software) complexe wiskundige mysteries kunnen oplossen die voorheen onmogelijk leken.

De kernboodschap: Wat er ook in die magische rijen gebeurt, het is niet willekeurig. Er zit een simpele, automatische logica achter die we nu volledig kunnen doorgronden en gebruiken om oude raadsels op te lossen.

Titel en Context

Titel: Beatty Sequences for a Quadratic Irrational: Decidability and Applications
Auteurs: Luke Schaeffer, Jeffrey Shallit, Stefan Zorcic (Universiteit van Waterloo)
Datum: 3 april 2026 (voorgesteld in het paper)

Dit paper onderzoekt de wiskundige eigenschappen van inhomogene Beatty-rijen van de vorm $(\lfloor n\alpha + \beta \rfloor)_{n \ge 1}$ , waarbij $\alpha$ en $\beta$ reële getallen zijn die tot hetzelfde kwadratische getallenlichaam behoren. De kernvraag is of de logische theorie van deze rijen (met optelling) beslisbaar is en hoe dit kan worden toegepast op problemen in de additieve getaltheorie.

1. Het Probleem

Beatty-rijen, gedefinieerd als $\lfloor n\alpha \rfloor$ , zijn al lang bestudeerd, maar de uitbreiding naar inhomogene rijen ( $\lfloor n\alpha + \beta \rfloor$ ) en de vraag naar de beslisbaarheid van hun eerste-orde logische theorie (met optelling) bleef een uitdaging, vooral voor algemene kwadratische irrationale getallen.

De auteurs willen beantwoorden:

Is de relatie $y = \lfloor n\alpha + \beta \rfloor$ "gesynchroniseerd" (synchronized) in de zin dat een eindige automaat deze kan herkennen?
Is de eerste-orde logische theorie van natuurlijke getallen met optelling en deze functie beslisbaar?
Kunnen we specifieke problemen in de additieve getaltheorie (zoals het vormen van een additieve basis) en open problemen van onderzoekers zoals Reble, Kimberling en Graham oplossen?

2. Methodologie

De kern van de methode is het combineren van automata-theorie met de Ostrowski-getalsystemen.

Ostrowski $\alpha$ -representatie: In plaats van het gebruikelijke decimale of binaire stelsel, gebruiken de auteurs het Ostrowski-getalsysteem gebaseerd op een kwadratisch irrationaal getal $\gamma$ . Dit systeem stelt elke natuurlijke getal $n$ uniek voor als een lineaire combinatie van de noemers $q_i$ van de convergenten van de kettingbreuk van $\gamma$ .
Gesynchroniseerde rijen (Synchronized Sequences): Een rij $(s_n)$ wordt "gesynchroniseerd" genoemd als er een eindige automaat bestaat die de representaties van $n$ en $s_n$ parallel leest en accepteert dan en slechts dan als $s_n$ de juiste waarde is.
Walnut Software: De auteurs implementeren hun beslissingsprocedures in Walnut, een gratis softwarepakket dat bewijst in de eerste-orde logica voor automatische rijen. Walnut kan automaten construeren en formules evalueren.
Kettingbreuken en Matrixbenadering: Voor kwadratische irrationale getallen (waarvan de kettingbreuk periodiek is) gebruiken ze matrixtechnieken om relaties tussen convergenten af te leiden, wat essentieel is om de synchronisatie te bewijzen.

3. Belangrijkste Bijdragen en Resultaten

A. Synchronisatie en Beslisbaarheid (Hoofdstuk 5)

Hoofdstelling (Theorema 9): Als $\gamma$ $γ$ een kwadratisch irrationaal getal is met een zuiver periodieke kettingbreuk, en $\alpha, \beta \in \mathbb{Q}(\gamma)$ $α, β \in Q (γ)$ , dan is de inhomogene Beatty-rij $(\lfloor n\alpha + \beta \rfloor)_{n \ge 1}$ $(⌊ n α + β ⌋)_{n \geq 1}$ $\gamma$ -Ostrowski gesynchroniseerd.
- Dit betekent dat er een eindige automaat bestaat die $n$ en $y$ in parallel leest (in hun Ostrowski-representatie) en accepteert als $y = \lfloor n\alpha + \beta \rfloor$ .
Corollarium 11: Als gevolg hiervan is de eerste-orde logische theorie van de natuurlijke getallen met optelling en de functie $n \mapsto \lfloor n\alpha + \beta \rfloor$ beslisbaar.
Omgekeerde stelling (Theorema 28): De auteurs bewijzen ook het omgekeerde: als de rij gesynchroniseerd is, moeten $\alpha$ en $\beta$ noodzakelijkerwijs tot het kwadratische getallenlichaam $\mathbb{Q}(\gamma)$ behoren.

B. Toepassingen in de Additieve Getaltheorie (Hoofdstuk 7)

Additieve Bases: Het paper toont aan dat het beslisbaar is of een verzameling $\{\lfloor n\alpha + \beta \rfloor\}$ een additieve basis van orde $r$ vormt (elk getal is som van $r$ elementen) of een asymptotische additieve basis (elk groot genoeg getal is som van $r$ elementen).
De auteurs kunnen de kleinste $h$ effectief berekenen waarvoor dit geldt.

C. Oplossen van Open Problemen (Hoofdstuk 8-13)

De auteurs gebruiken hun technieken om diverse open vragen op te lossen:

Reble's Vermoedens: Bewijs van conjectures over monochromatische rekenkundige progressies in het Fibonacci-woord (OEIS A189377, A189378, A189379).
Graham's Vraag: Beslisbaarheid van "eventual covering families" (ECF) voor paren $(\alpha_i, \beta_i)$ in hetzelfde kwadratische veld.
Hildebrand et al.: Een expliciete karakterisering van een rij $\tilde{c}(n)$ die het complement is van de vereniging van twee andere Beatty-rijen, en het bewijs dat $0 \le c(n) - \tilde{c}(n) \le 2$ .
Kimberling's Swappage-probleem: Een alternatief, geautomatiseerd bewijs van Kimberling's conjectures over "swappage"-rijen (OEIS A141104 etc.) en hun relatie met Beatty-rijen van $\phi^3$ .
Wortels van 2: Constructie van Ostrowski-automaten voor zeven rijen gerelateerd aan $\sqrt{2}$ (OEIS A097508, A001951, etc.) en het bewijzen van conjectures over hun onderlinge relaties.

D. Fractionele Delen (Hoofdstuk 14)

De auteurs tonen aan hoe men vergelijkingen van fractionele delen $\{ \alpha x + \beta \} < \{ \alpha' y + \beta' \}$ kan vertalen naar vergelijkingen met vloerfuncties ( $\lfloor \cdot \rfloor$ ), waardoor deze ook in Walnut kunnen worden geanalyseerd.

4. Significatie en Impact

Unificatie van Gebieden: Het paper verbindt de theorie van Beatty-rijen, continue breuken, automata-theorie en eerste-orde logica op een elegante manier.
Praktische Beslisbaarheid: Het biedt niet alleen een theoretisch bewijs van beslisbaarheid, maar levert ook een effectief algoritme (geïmplementeerd in Walnut) waarmee complexe stellingen over specifieke rijen binnen seconden bewezen kunnen worden.
Simpelheid: De methode wordt geprezen om zijn eenvoud vergeleken met eerdere, complexere benaderingen (zoals quantifier elimination). Het reduceert complexe getaltheoretische problemen tot het construeren en analyseren van eindige automaten.
Nieuwe Inzichten: Door het oplossen van open problemen van Reble, Kimberling en Graham, vult het paper gaten in de bestaande literatuur en biedt het nieuwe inzicht in de structuur van Sturmian-rijen en hun verbanden.

Conclusie

Dit paper toont aan dat voor kwadratische irrationale getallen de wereld van Beatty-rijen volledig "automatisch" is. De auteurs hebben een krachtig raamwerk ontwikkeld dat het mogelijk maakt om diepe wiskundige vragen over deze rijen te beantwoorden door ze te vertalen naar problemen die door eindige automaten kunnen worden opgelost. Dit opent de deur voor het geautomatiseerd bewijzen van stellingen in de combinatorische getaltheorie.