🔢 mathematics

On the sequence $\mathrm{gcd}(a^n-1,b^n-1)$

Dit artikel onderzoekt de rij $g_n = \gcd(a^n-1, b^n-1)$ door te bewijzen dat deze een lineaire recursie ver satisfies dan wel niet als $a$ en $b$ multiplicatief afhankelijk zijn, waarbij de periodiciteit van gemeenschappelijke deelbaarheidsrijen voor onafhankelijke basissen wordt vastgesteld, exacte formules voor de lokale structuur ervan worden afgeleid, en structurele reducties richting de integer Ailon–Rudnick-conjectuur worden geboden.

Oorspronkelijke auteurs: Khai-Hoan Nguyen-Dang

Gepubliceerd 2026-06-09

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Khai-Hoan Nguyen-Dang

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 twee gigantische, magische machines hebt. Laten we ze Machine A en Machine B noemen.

Machine A neemt een getal $n$ en spuwt een gigantisch getal uit: $a^n - 1$ .
Machine B neemt hetzelfde getal $n$ en spuwt een ander gigantisch getal uit: $b^n - 1$ .

Stel je nu voor dat je een "Grootste Gemene Deler" (GGD) detector hebt. Deze detector kijkt naar de twee getallen die de machines zojuist geproduceerd hebben en vindt het grootste getal dat beide getallen perfect deelt. Laten we dit gedeelde getal $g_n$ noemen.

Het artikel van Khai-Hoan Nguyen-Dang is een diepgaand onderzoek naar het gedrag van deze reeks gedeelde getallen ( $g_1, g_2, g_3, \dots$ ). De auteur vraagt: Is er een eenvoudig, voorspelbaar patroon aan deze gedeelde getallen?

Hier is de uiteenzetting van de bevindingen van het artikel, gebruikmakend van eenvoudige analogieën:

1. De twee soorten machines

De auteur ontdekt dat het gedrag van deze machines volledig afhangt van de relatie tussen hun begininstellingen, $a$ en $b$ .

De "Afhankelijke" Machines (Voorspelbaar):
Als $a$ en $b$ "multiplicatief afhankelijk" zijn, betekent dit dat de een slechts een macht van de ander is (zoals 4 en 8, waarbij $4=2^2$ en $8=2^3$ ).
- Het resultaat: Wanneer de machines afhankelijk zijn, volgt de reeks gedeelde getallen ( $g_n$ ) een zeer strikte, eenvoudige regel die een lineaire recursie wordt genoemd.
- De analogie: Denk hierbij aan een harmonieus muziekkorps dat een lied speelt. Als de trommels en de trompetten perfect gesynchroniseerd zijn (afhankelijk), volgt hun gecombineerde ritme een eenvoudige, herhalende beat die je eeuwig kunt voorspellen. Het artikel bewijst dat als de reeks dit eenvoudige ritme volgt, de machines moeten afhankelijk zijn.
De "Onafhankelijke" Machines (Chaotisch):
Als $a$ en $b$ "multiplicatief onafhankelijk" zijn (zoals 2 en 3, waarbij de een niet de macht van de ander is), zijn ze als twee muzikanten die totaal verschillende liedjes spelen.
- Het resultaat: In dit geval kan de reeks gedeelde getallen ( $g_n$ ) niet worden voorspeld door een eenvoudige, constante regel. Het is te chaotisch.
- De analogie: Als je probeert het muziekkorps een eenvoudige beat op te leggen terwijl de muzikanten onafhankelijke liedjes spelen, breekt het systeem. Het artikel bewijst dat hoe je ook probeert een eenvoudige regel op deze getallen toe te passen, deze uiteindelijk zal falen.

2. De "Geest"-patronen

De auteur stelt ook een diepere vraag: Zelfs als de hele reeks chaotisch is, is er dan een deel ervan dat voorspelbaar is? Met andere woorden, is er een kleinere reeks die beide machine-outputs deelt en een eenvoudige regel volgt?

De bevinding: Als de machines onafhankelijk zijn, is het antwoord nee, tenzij die kleinere reeks slechts een saaie, herhalende lus (periodiek) is.
De analogie: Stel je voor dat je probeert een verborgen ritme te vinden binnen de chaotische ruis van de twee muzikanten. Het artikel bewijst dat de enige "ritmes" die je kunt vinden, simpelweg korte, herhalende lussen zijn die steeds weer opnieuw voorkomen. Er zijn geen verborgen, complexe, langetermijnpatronen te vinden.

3. Het in kaart brengen van de "Slechte" plekken

Het artikel zoomt vervolgens in om precies te kijken naar wanneer het gedeelde getal $g_n$ groter is dan 1 (oftewel: wanneer de machines een gemeenschappelijke factor delen).

De "Slechte Set": De auteur maakt een precieze kaart van alle getallen $n$ waar de machines een gemeenschappelijke factor delen.
De analogie: Stel je een kalender voor. Op de meeste dagen produceren de machines getallen die niets met elkaar gemeen hebben. Maar op bepaalde dagen delen ze een geheim. Het artikel biedt een formule om "pijlen" op de kalender te tekenen die precies wijzen naar welke dagen deze geheimen plaatsvinden.
- Het blijkt dat deze "geheime dagen" slechts een verzameling van specifieke herhalende schema's (rekenkundige progressies) zijn.
- Als we de machines zo normaliseren dat ze op dag 1 geen geheim delen, laat het artikel zien dat de "slechte dagen" exact de dagen zijn die vallen op de schema's van specifieke priemgetallen.

4. Het "Ailon–Rudnick" Mysterie

Ten slotte pakt het artikel een beroemd onopgelost raadsel aan, de Ailon–Rudnick Conjectuur.

Het raadsel: Als de machines onafhankelijk zijn en op dag 1 geen geheim delen, zullen ze dan uiteindelijk getallen produceren die geen gemeenschappelijke factoren hebben (dat wil zeggen $g_n = 1$ ) voor oneindig veel dagen?
De bijdrage van het artikel: De auteur lost het hele raadsel niet op, maar breekt het af in kleinere, beheersbare stukken. De auteur laat zien dat om het raadsel op te lossen, je alleen specifieke soorten "slechte dagen" (zoals priemgetallen) hoeft te controleren en naar specifieke algebraïsche "vingerafdrukken" (resultanten) moet kijken.
De analogie: In plaats van te proberen te bewijzen dat de hele kalender grotendeels leeg is van geheimen, zegt de auteur: "Laten we alleen naar de dinsdagen kijken. Als we kunnen bewijzen dat er geen geheimen zijn op dinsdagen, hebben we enorme vooruitgang geboekt." De auteur biedt een checklist van voorwaarden die, indien voldaan, het mysterie zouden oplossen.

Samenvatting

Kortom, dit artikel is een rigoureuze studie naar het ritme van gedeelde factoren tussen twee exponentiële reeksen.

Als de bases gerelateerd zijn: Het ritme is eenvoudig en voorspelbaar.
Als de bases ongerelateerd zijn: Het ritme is chaotisch, en er bestaan geen verborgen eenvoudige patronen (behalve saaie lussen).
De "Slechte" dagen: De auteur brengt exact in kaart wanneer deze gedeelde factoren voorkomen, waardoor een vaag mysterie wordt omgezet in een precieze lijst van herhalende schema's.
De Grote Conjectuur: Het artikel biedt een nieuwe, scherpere set instrumenten om wiskundigen te helpen eindelijk te bewijzen of deze machines ooit stoppen met het delen van geheimen.

Technische Samenvatting: Over de reeks $\gcd(a^n - 1, b^n - 1)$

Probleemstelling

Dit artikel onderzoekt de rekenkundige structuur van de reeks $(g_n)_{n \ge 1}$ gedefinieerd door $g_n := \gcd(a^n - 1, b^n - 1)$ voor gehele getallen $a, b \ge 2$ . De reeks bevindt zich van nature op het snijvlak van twee klassieke gebieden: de grootste gemeenschappelijke delers van exponentiële reeksen en de theorie van deelbaarheidsreeksen.

De centrale motivatie komt voort uit de Ailon–Rudnick-conjectuur in de context van gehele getallen. Hoewel Ailon en Rudnick een sterk functioneel-veldtheorema bewezen dat stelt dat als $f, g \in \mathbb{C}[T]$ multiplicatief onafhankelijk zijn, $\gcd(f^n - 1, g^n - 1)$ begrensd wordt door een polynoom, blijft de casus met gehele getallen onopgelost. De conjectuur stelt dat als $a$ en $b$ multiplicatief onafhankelijk zijn en $\gcd(a-1, b-1)=1$ , dan $\gcd(a^n - 1, b^n - 1) = 1$ voor oneindig veel $n$ .

Het doel van dit artikel is om exact te duiden wat wel en niet verklaard kan worden over $(g_n)$ aan de hand van de kaders van constant-coëfficiënt lineaire recurrente en lineaire deelbaarheidsreeksen (LDS).

Methodologie

De auteur maakt gebruik van een combinatie van algebraïsche getaltheorie, analytische grenzen en structurele classificatietheorema's:

Rigiditeit van Lineaire Recurrenten: Het artikel maakt gebruik van het klassieke principe dat algebraïsche gehele getallen met alle geconjugeerden in de gesloten eenheidsschijf wortels van eenheid zijn (Kroneckers Lemma). Dit wordt toegepast op de genererende functies van lineaire recurrenten om aan te tonen dat reeksen met subexponentiële groei uiteindelijk polynomiaal zijn op rekenkundige progressies.
Subexponentiële Grenzen: De fundamentele kwantitatieve input is het theorema van Bugeaud, Corvaja en Zannier, dat vaststelt dat voor multiplicatief onafhankelijke $a, b$ , $\log \gcd(a^n - 1, b^n - 1) \le \epsilon n + O_\epsilon(1)$ .
Classificatie van LDS: Het werk leunt zwaar op de recente classificatie van gehele lineaire deelbaarheidsreeksen door Granville, die dergelijke reeksen ontleedt in periodieke, machts- en polynomiaal gegenereerde componenten.
Lokale Arithmetica (LTE): Het artikel gebruikt de Lifting The Exponent (LTE) lemma om exacte formules af te leiden voor de $p$ -adische valuaties van $g_n$ .
Cyclotomische Resultanten: Om de Ailon–Rudnick-conjectuur voor priemindices aan te pakken, maakt het artikel gebruik van eigenschappen van cyclotomische polynomen en resultanten om het probleem te reduceren tot eindige certificaten en lokale dekkingproblemen.

Belangrijkste Bijdragen en Resultaten

1. Classificatie van de GCD-reeks als een Lineaire Recurrent

Het artikel vestigt een scherp rigiditeitstheorema met betrekking tot de vraag of $(g_n)$ een constant-coëfficiënt lineaire recurrent voldoet.

Theorema 1.1: De reeks $(g_n)$ $(g_{n})$ voldoet aan een constant-coëfficiënt lineaire recurrent dan en slechts dan als $a$ $a$ en $b$ $b$ multiplicatief afhankelijk zijn.
- Indien afhankelijk, bestaan er gehele getallen $c \ge 2$ en $r, s \ge 1$ zodan dat $a=c^r, b=c^s$ . In dat geval is $g_n = c^{\gcd(r,s)n} - 1$ , wat een eenvoudige lineaire recurrent is.
- Indien onafhankelijk, voldoet geen enkel deel van de reeks aan een lineaire recurrent.
Corollary 3.4: Bijgevolg is $(g_n)$ een lineaire deelbaarheidsreeks (LDS) dan en slechts dan als $a$ en $b$ multiplicatief afhankelijk zijn.

2. Rigiditeit van Gemeenschappelijke LDS-factoren

Het artikel onderzoekt of een niet-triviale lineaire deelbaarheidsreeks beide termen $a^n - 1$ en $b^n - 1$ simultaan kan delen in de onafhankelijke casus.

Theorema 1.2 / Theorema 4.3: Als $a$ $a$ en $b$ $b$ multiplicatief onafhankelijk zijn, dan is elke gehele lineaire deelbaarheidsreeks $(W_n)$ $(W_{n})$ die voldoet aan $W_n \mid a^n - 1$ $W_{n} ∣ a^{n} - 1$ en $W_n \mid b^n - 1$ $W_{n} ∣ b^{n} - 1$ periodiek.
- Dit resultaat combineert de Bugeaud–Corvaja–Zannier-grens (subexponentiële groei) met de classificatie van Granville voor LDS. Dit impliceert dat het "lineaire recurrent"-mechanisme de niet-triviale gemeenschappelijke factoren in de onafhankelijke casus niet kan verklaren; elke dergelijke gemeenschappelijke factor moet periodiek zijn.

3. Lokale Structuur en Support-formules

Het artikel biedt exacte formules voor de support en de valuaties van $g_n$ , waarbij de "slechte verzameling" $\{n : g_n > 1\}$ wordt geïdentificeerd.

Support-formule (Proposition 5.1): Voor een priemgetal $p \nmid ab$ , laat $L_p = \text{lcm}(\text{ord}_p(a), \text{ord}_p(b))$ . Dan geldt $p \mid g_n \iff L_p \mid n$ .
Valuatie-formule (Proposition 5.2): Voor oneven priemgetallen $p \nmid ab$ , indien $L_p \mid n$ , dan is $v_p(g_n) = c_p + v_p(n)$ , waarbij $c_p = \min(v_p(a^{L_p}-1), v_p(b^{L_p}-1))$ .
Karakterisering van de Slechte Verzameling (Corollary 5.4): Onder de normalisatie $\gcd(a-1, b-1)=1$ , is de verzameling $\{n \ge 1 : g_n > 1\}$ exact de vereniging van rekenkundige progressies:
$\{n \ge 1 : g_n > 1\} = \bigcup_{p \nmid ab} L_p \mathbb{N}$
De Ailon–Rudnick-conjectuur is hiermee equivalent aan de infinitude van het complement van deze vereniging.

4. Reducties naar de Ailon–Rudnick-conjectuur

Het artikel leidt verschillende structurele reducties af die de moeilijkheid van de conjectuur isoleren tot lokale dekkingproblemen, waardoor lineaire recurrentmechanismen worden geëlimineerd.

Primitive-Support Criterium (Proposition 5.6): De slechte verzameling kan worden gecomprimeerd tot een vereniging van progressies gegenereerd door een primitieve verzameling $B$ van minimale perioden $L_p$ . Als $\sum_{d \in B} 1/d < \infty$ , heeft de goede verzameling een positieve lagere asymptotische dichtheid.
Priemindex-Reductie (Theorem 6.2): Voor een priemgetal $\ell$ buiten een eindige uitzonderlijke verzameling $\Sigma(a,b)$ , geldt $g_\ell > 1$ dan en slechts dan als $A_\ell = \frac{a^\ell-1}{a-1}$ en $B_\ell = \frac{b^\ell-1}{b-1}$ een gemeenschappelijke primitieve divisor delen (d.w.z. er bestaat een priemgetal $p$ met $\text{ord}_p(a) = \text{ord}_p(b) = \ell$ ).
Eindig Certificaat (Theorem 6.4): Indien $g_\ell > 1$ , bestaan er gehele getallen $1 \le u, v \le \lceil \sqrt{\ell} \rceil$ en een priemgetal $p \equiv 1 \pmod \ell$ zodan dat $p \mid a^u - b^v$ of $p \mid a^u b^v - 1$ .
Resultant-Compressie (Corollary 6.6): De conditie $g_\ell > 1$ impliceert de existentie van een priemgetal $p \equiv 1 \pmod \ell$ dat de cyclotomische resultant $R_\ell(b-a) = \text{Res}_X(\Phi_\ell(X), \Phi_\ell(X + b-a))$ deelt.

Betekenis en Claims

Het artikel claimt een definitieve structurele analyse van de reeks $(g_n)$ te bieden binnen de context van lineaire recurrenten en deelbaarheidsreeksen.

Eliminatie van Lineaire Mechanismen: De primaire betekenis is het bewijs dat de reeks $(g_n)$ zelf geen lineaire deelbaarheidsreeks is (tenzij $a, b$ afhankelijk zijn), en dat geen enkele niet-periodieke lineaire deelbaarheidsreeks een gemeenschappelijke factor kan zijn in de onafhankelijke casus. Dit suggereert dat de Ailon–Rudnick-conjectuur niet kan worden opgelost door $(g_n)$ te modelleren als een lineaire recurrent.
Lokalisatie van de Moeilijkheid: Door exacte lokale formules en reducties vast te stellen, betoogt het artikel dat de resterende moeilijkheid van de conjectuur een lokaal dekkingprobleem is dat wordt beheerst door multiplicatieve orden en priemindex-obstactels, in plaats van een globaal lineair recurrent fenomeen.
Exacte Karakterisering: Het artikel levert de eerste exacte support- en valuatieformules voor de algemene casus, waarbij de slechte verzameling wordt geïdentificeerd als een expliciete vereniging van rekenkundige progressies bepaald door lokale perioden $L_p$ .

De auteur concludeert dat de "lineaire recurrentmechanismen" volledig begrepen en geëlimineerd zijn; het probleem reduceert zich nu tot het analyseren van de dichtheid en de dekkingseigenschappen van de verzameling lokale perioden $\{L_p\}$ .