🔢 mathematics

Almost Golomb Sequences

Dit artikel introduceert 'bijna Golomb-reeksen', die ontstaan door de zelfreferentiële definitie van de Golomb-reeks te beperken tot een schuifvenster, waardoor de gladde machswet vervangt door oscillatoire lineaire groei en de reeksen $r$ -regulier worden, met als verrassend resultaat dat de oorspronkelijke Golomb-reeks de maximale multipliciteit binnen deze familie bepaalt.

Oorspronkelijke auteurs: Benoit Cloitre

Gepubliceerd 2026-04-06

📖 4 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Benoit Cloitre

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 heel speciale rijtje nummers aan het maken bent. Je hebt een simpele regel: elk getal in de rij moet precies zo vaak voorkomen als de waarde van dat getal zelf.

Dit is het beroemde Golomb-rijtje. Het is als een spiegel die zichzelf beschrijft. Als het getal 3 in de rij staat, dan moet het getal 3 precies drie keer in de rij voorkomen. Als het getal 5 staat, moet het vijf keer voorkomen. Dit rijtje groeit heel soepel en voorspelbaar, als een golvende lijn die langzaam omhoog kruipt.

De auteur van dit artikel, Benoît Cloitre, vraagt zich af: "Wat gebeurt er als we deze regel een beetje 'kortsluiten'?"

In plaats van naar alle vorige getallen te kijken om te beslissen hoeveel keer een getal moet verschijnen, kijken we alleen naar de laatste paar getallen. Stel, we kijken alleen naar de laatste 3 getallen (of 4, of 5, etc.). Dit noemen we een "sliding window" (een schuifraam).

Dit lijkt op een kleinigheidje, maar het verandert de hele natuur van de rijtjes. Hier is wat de paper ontdekt, vertaald naar alledaagse taal:

1. Van Soepel naar Trillend

Het originele Golomb-rijtje groeit als een soepele helling. Maar de nieuwe "Bijna-Golomb"-rijtjes (zoals de paper ze noemt) gedragen zich heel anders. Ze groeien nog steeds lineair (ze worden steeds groter), maar ze trillen.

Stel je voor dat je een trap beklimt.

De originele Golomb-trap is een gladde helling.
De nieuwe trappen hebben traptreden die soms hoog zijn en soms laag, in een vast patroon. Ze groeien niet meer soepel, maar in een ritme dat op en neer gaat.

2. Het Geheim van de "Correctie"

Waarom trillen ze? Omdat de regel die we gebruiken (kijken naar de laatste paar getallen) niet altijd perfect werkt. Soms moet je een klein beetje "bijsturen".

De auteur ontdekt dat deze bijsturingen (die hij correcties noemt) een heel eigen ritme hebben. Ze volgen een soort code die je kunt lezen als je kijkt naar het getal in een ander talstelsel (bijvoorbeeld in het binaire of ternaire stelsel).

Voor de rijtjes met een venster van grootte 2 of 3, kunnen we deze code heel precies uitschrijven. Het is alsof we de formule hebben gevonden om de trillingen te voorspellen.
Het is alsof de rijtjes een geheime taal spreken die we nu hebben ontcijferd.

3. De Grote Verrassing: De Meester keert terug

Dit is het meest fascinerende deel van het verhaal.
De auteur heeft gekeken naar hoe vaak de verschillende getallen in deze nieuwe rijtjes voorkomen. Hij vroeg zich af: "Hoe vaak kan een getal maximaal voorkomen in een rijtje met een venster van grootte $r$ ?"

Hij noemt dit het maximum aantal keren ( $M(r)$ ).

Toen hij dit voor verschillende venstergroottes ( $r=2, 3, 4, \dots$ ) uitrekende, zag hij iets verbazingwekkends gebeuren. De manier waarop dit maximum toeneemt, volgt precies de regels van het originele Golomb-rijtje!

Het is alsof je een nieuwe soort plant hebt gekweekt (de nieuwe rijtjes), en als je kijkt hoe groot ze kunnen worden, blijkt dat de groeiregels van de oude, originele plant (Golomb) nog steeds de baas spelen. De "oude meester" (Golomb) zit verstopt in de structuur van de "nieuwe leerlingen".

De paper stelt een hypothese: Als je weet hoe vaak een getal in het originele Golomb-rijtje voorkomt, kun je precies voorspellen bij welke venstergrootte de nieuwe rijtjes beginnen om dat getal vaak genoeg te laten verschijnen.

4. Waarom is dit belangrijk?

In de wiskunde zijn er rijtjes die heel "regulier" zijn (je kunt ze makkelijk voorspellen) en er zijn er die heel "chaotisch" zijn.

Het originele Golomb-rijtje is een beetje raar: het is niet zo makkelijk te voorspellen met simpele formules.
De nieuwe "Bijna-Golomb"-rijtjes zijn juist heel gestructureerd en voorspelbaar (ze zijn "automatisch").

De paper laat zien dat we door een simpele verandering (het venster kleiner maken) een chaotisch systeem kunnen omtoveren in een gestructureerd systeem, maar dat de "ziel" van het oude systeem (Golomb) toch terugkomt in de vorm van een verborgen patroon.

Samenvatting in één zin

De auteur heeft ontdekt dat als je de regels van een beroemde wiskundige puzzel (Golomb) een beetje "kortsluit" door alleen naar de laatste paar stappen te kijken, je een nieuw, trillend ritme krijgt dat toch volledig wordt bestuurd door de oude, originele puzzel. Het is een mooie ontdekking van hoe oude wiskundige wetten zich herhalen, zelfs in nieuwe, aangepaste situaties.

Titel: Almost Golomb Sequences

Auteur: Benoît Cloitre
Onderwerp: Getaltheorie, Combinatoriek, Automatische Sequenties

1. Probleemstelling en Achtergrond

Het artikel onderzoekt een generalisatie van de beroemde Golomb-sequentie ( $G(n)$ ). De Golomb-sequentie is de unieke niet-dalende rij van positieve gehele getallen waarbij het getal $n$ precies $G(n)$ keer voorkomt. Deze rij wordt gedefinieerd door de globale zelfreferentiële regel:
$G\left(\sum_{k=1}^n G(k)\right) = n$
Deze rij groeit soepel als een macht van $n$ (geleid door de gulden snede $\phi$ ) en is niet $k$ -regulier voor enig $k \ge 2$ .

Het centrale probleem in dit artikel is wat er gebeurt als men de "oneindige" cumulatieve som in de definitie vervangt door een schuifvenster van een vaste grootte $r$ . Dit leidt tot de Bijna-Golomb-sequenties (Almost Golomb sequences) van orde $r$ , gedefinieerd door:
$a\left(\sum_{j=0}^{r-1} a(n-j)\right) = n$
met de voorwaarde dat $a(n)$ het kleinste gehele getal is dat voldoet aan de vergelijking en $a(n) \ge a(n-1)$ . De auteurs onderzoeken hoe deze "finite-memory" (beperkt geheugen) truncatie de fundamentele eigenschappen van de sequentie verandert ten opzichte van de originele Golomb-sequentie.

2. Methodologie

De auteurs hanteren een combinatie van analytische, constructieve en computergestuurde methoden:

Constructieve Bewijzen: Voor kleine waarden van $r$ (namelijk $r=2$ en $r=3$ ) worden expliciete formules afgeleid die de sequentie ontwarren ("denesting") in termen van $r$ -adische recursies (bijv. $a(rn+i)$ uitgedrukt in $a(n)$ ).
Hybride Methode (Walnut): Voor $r=4$ en $r=5$ worden de recursieregels eerst wiskundig geïdentificeerd en vervolgens geverifieerd met Walnut, een theorema-prover voor automatische sequenties. Dit bevestigt de correctheid van de afgeleide formules voor alle $n$ .
Automata-theorie: De auteurs gebruiken de theorie van $k$ -automatische en $k$ -reguliere sequenties (volgens Allouche en Shallit). Ze analyseren de kernel van de sequentie en construeren deterministische eindige automaten met output (DFAO) voor de correctieseries die nodig zijn om de recursies te beschrijven.
Asymptotische Analyse: Door het bestuderen van specifieke deelrijen (bijv. langs meetkundige progressies) en het gebruik van lemma's over de periodiciteit van toestanden in automaten, wordt het gedrag van de verhouding $a(n)/n$ onderzocht.

3. Belangrijkste Bijdragen en Resultaten

A. Verandering in Groeigedrag en Regulariteit

Van Analytisch naar Automatisch: Terwijl de Golomb-sequentie een gladde, sublineaire groei heeft met een irrationele exponent, vertonen de Bijna-Golomb-sequenties lineaire groei ( $a(n) \asymp n$ ) met discrete oscillaties.
$r$ -Regulariteit: Het belangrijkste theoretische resultaat is dat voor elke $r \ge 2$ de sequentie $(a(n))$ $r$ -regulier is. Dit betekent dat de $\mathbb{Z}$ -module opgespannen door de $r$ -kernel (de deelrijen $a(r^k n + j)$ ) eindig gegenereerd is. Dit staat in schril contrast met de originele Golomb-sequentie, die niet $k$ -regulier is.

B. Expliciete "Denesting"-Formules

De auteurs leiden expliciete formules af die de recursie ontwarren tot een "divide-and-conquer" structuur gebaseerd op de basis- $r$ representatie van $n$ :

Voor $r=2$ : Er wordt een gesloten vorm afgeleid voor blokken $[2^k, 2^{k+1})$ . De sequentie voldoet aan een Mallows-achtige geneste recursie:
$a(n+1) = 1 + a(n + 1 - a(a(n)+1) + a(a(n)-1))$
De differentie-sequentie $d(n) = a(n+1)-a(n)$ wordt gegenereerd door een simpel cellulair automaton.
Voor $r=3, 4, 5$ : De formules bevatten binair correctieseries ( $\varepsilon_i(n)$ ) die $r$ -automatisch zijn. Bijvoorbeeld voor $r=3$ :
$a(3n) = a(n-2) + a(n-1) + a(n) + 1 + \varepsilon(n-1)$
Deze correctieseries worden beschreven door specifieke DFAO's.

C. Non-convergentie van $a(n)/n$

Een cruciaal resultaat is dat de verhouding $a(n)/n$ niet convergeert voor enige $r \ge 2$ . In plaats van naar één constante te gaan, oscilleert de verhouding tussen twee expliciete rationale limieten.

Voor $r=2$ : Limieten zijn $3/4$ en $2/3$ .
Voor $r=3$ : Limieten zijn $8/15$ en $5/8$ .
Voor $r=4$ en $r=5$ : Er worden eveneens twee verschillende rationale limieten gevonden (bijv. $25/48$ en $10/21$ voor $r=4$ ).
Dit wordt bewezen door de periodiciteit van de correctieseries langs meetkundige progressies te analyseren.

D. Combinatorische Interpretaties

$r=2$ : De multipliciteit van een getal $m$ in de rij hangt af van de tweede meest significante bit van $m-1$ . De differentie-sequentie volgt een booleaanse "AND"-regel op een cellulair automaton.
$r=3$ : De sequentie heeft een palindromische substitutiestructuur. De auteurs beschrijven een mechanisme van "vertraagde feedback" dat de oscillaties verklaart.

E. De "Golomb Meta-structuur" (Conjectuur)

De auteurs ontdekken een verrassende numerieke relatie tussen de familie van Bijna-Golomb-sequenties en de originele Golomb-sequentie zelf.

Laat $M(r)$ de maximale multipliciteit zijn in de sequentie van orde $r$ .
Laat $j_k$ de kleinste orde $r$ zijn waarbij $M(r) \ge k$ .
De data suggereren dat de verschillen $j_{k+1} - j_k$ exact overeenkomen met de Golomb-sequentie $G(k)$ voor $k \ge 4$ .
Dit leidt tot de Prefix Conjecture en Domination Lemma, die stellen dat de initiële blokken van de Bijna-Golomb-sequenties de "vingerafdruk" dragen van de Golomb-sequentie. Als deze conjecturen waar zijn, geldt asymptotisch $M(r) \sim C r^{\phi-1}$ , waarbij $\phi-1$ dezelfde exponent is als bij de groei van de Golomb-sequentie zelf.

4. Significatie en Conclusie

Dit artikel toont aan dat het beperken van het geheugen in een zelfreferentiële definitie (van oneindig naar een venster van grootte $r$ ) de aard van de sequentie fundamenteel verandert:

Het transformeert een chaotische, niet-reguliere structuur in een automatische, $r$ -reguliere structuur.
Het vervangt soepele groei door lineaire groei met oscillaties.
Het onthult een diepe, onverwachte verbinding waarbij de originele Golomb-sequentie de wetmatigheid bepaalt voor de familie van sequenties die eruit voortvloeit (de meta-structuur).

De resultaten bieden nieuwe inzichten in de theorie van zelfreferentiële rijen, cellulair automata en de interactie tussen analytische groei en automatische structuren. De open vragen over de fase-overgang voor $r \to \infty$ en de uitbreiding van de combinatorische interpretaties naar hogere $r$ vormen een rijk onderzoeksgebied voor de toekomst.