Dead ends in square-free digit walks

Technische Samenvatting: Doodlopende paden in kwadraatvrije cijferlopen

Probleemstelling
Het artikel onderzoekt het bestaan en de dichtheid van "doodlopende paden" (dead ends) in kwadraatvrije cijferlopen. Een kwadraatvrije loop in grondtal $b$ begint met een kwadraatvrij getal $N_0$ en probeert een oneindige sequentie $N_0, N_1, N_2, \dots$ te construeren waarbij elke opeenvolgende term wordt gevormd door een cijfer $d \in \{0, \dots, b-1\}$ toe te voegen, zodanig dat $N_{k+1} = bN_k + d$ kwadraatvrij blijft.

Een positief geheel getal $N$ wordt gedefinieerd als een doodlopend pad indien:

1. $N$ kwadraatvrij is.
2. Voor elk cijfer $d$ in het grondtal de uitbreiding $bN + d$ niet kwadraatvrij is.

De centrale vraag, gesteld door Miller et al. [5], is of er oneindige kwadraatvrije lopen bestaan. Hoewel een stochastisch model (het "Blind Unlimited Model") suggereert dat oneindige lopen met een waarschijnlijkheid nabij 1 bestaan (wat impliceert dat doodlopende paden zeldzaam zijn, met een asymptotische dichtheid van $\approx 5,218 \times 10^{-5}$ in grondtal 10), analyseert dit artikel rigoureus de werkelijke rekenkundige dichtheid van doodlopende paden om te bepalen of de stochastische voorspelling standhoudt.

Methodologie
De auteurs maken gebruik van een combinatie van elementaire multiplicatieve getaltheorie en inclusie-exclusie-principes, waarbij zij de probabilistische aannames van het stochastische model vermijden.

1. Indicatorfuncties: Het probleem wordt geherformuleerd met behulp van de Möbius-functie $\mu(n)$. Aangezien $\mu(n)^2$ de indicatorfunctie is voor kwadraatvrije gehele getallen, kan de indicator voor een doodlopend pad $N$ worden uitgedrukt als:
   $$\mathbb{1}_{N \text{ is doodlopend}} = \mu(N)^2 \prod_{d \in D} (1 - \mu(bN + d)^2)$$
   waarbij $D$ de verzameling van cijfers is.

2. Inclusie-exclusie: De productterm wordt uitgebreid naar een som over alle deelverzamelingen $S$ van de cijferverzameling. Dit transformeert de telfunctie $D_b(X)$ (het aantal doodlopende paden $\le X$) in een alternerende som van telfuncties $Q_S(X)$, waarbij $Q_S(X)$ het aantal gehele getallen $n \le X$ telt waarvoor zowel $n$ als alle uitbreidingen $bn+d$ (voor $d \in S$) kwadraatvrij zijn.

3. Zeefanalyse: Voor een vaste deelverzameling $S$ wordt de voorwaarde dat $n$ en $bn+d$ kwadraatvrij zijn, geanalyseerd per priemgetal. De auteurs definiëren "slechte" residuklassen modulo $p^2$ die vermeden moeten worden. Met behulp van de Chinese Reststelling bepalen zij de dichtheid van gehele getallen die deze klassen vermijden.

   • Voor grote priemgetallen $p$ (waarbij $p \nmid b$), dwingt de voorwaarde $p^2 \mid (bn+d)$ de waarde $n$ in een enkele residuklasse modulo $p^2$. Cruciaal is dat een enkel kwadraat van een priemgetal maximaal één cijferuitbreiding tegelijk kan blokkeren.
   • De dichtheid wordt uitgedrukt als een oneindig product (Eulerproduct) van lokale factoren $(1 - \nu_{p,b}(S)/p^2)$, waarbij $\nu_{p,b}(S)$ het aantal verboden residuklassen modulo $p^2$ telt.

4. Fouttermcontrole: Het bewijs controleert zorgvuldig de fouttermen die voortvloeien uit het afkappen van de zeef bij een parameter $z$ en uit de bijdrage van grote priemgetallen, waarbij een foutterm van $O(X/\sqrt{\log X})$ wordt vastgesteld.

Belangrijkste Resultaten

• Stelling 1.1 (Grondtal 10): De asymptotische dichtheid van doodlopende paden in grondtal 10 bestaat en wordt gegeven door:
  $$c_{\text{dead}} = \sum_{S \subseteq \{0,\dots,9\}} (-1)^{|S|} \prod_{p \text{ priem}} \left( 1 - \frac{\nu_p(S)}{p^2} \right)$$
  waarbij $\nu_p(S)$ het aantal residuklassen $n \pmod{p^2}$ is waarvoor $p^2 \mid n$ of $p^2 \mid (10n+d)$ voor enig $d \in S$.
  De berekende waarde is $c_{\text{dead}} \approx 1,317 \times 10^{-9}$.

• Stelling 1.2 (Algemeen Grondtal $b$): Het resultaat generaliseert naar elk grondtal $b \ge 2$. De dichtheid $c_{\text{dead}}(b)$ wordt gegeven door een vergelijkbare gesloten vorm met een alternerende som van Eulerproducten. Het artikel biedt berekende benaderingen voor priem grondtallen $b \in \{2, 3, 5, 7\}$.

• Discrepantie met Stochastische Modellen: De werkelijke dichtheid ($\approx 1,3 \times 10^{-9}$) is ongeveer $40.000$ keer kleiner dan de stochastische voorspelling ($\approx 5,2 \times 10^{-5}$). Het artikel schrijft dit toe aan rekenkundige afhankelijkheden: het naïeve stochastische model gaat uit van onafhankelijkheid tussen de cijferuitbreidingen, maar in werkelijkheid vereist de eis dat alle tien uitbreidingen tegelijkertijd falen de simultane obstructie door vele verschillende kwadraten van priemgetallen, een conditie die veel strikter is dan het onafhankelijke probabilistische model suggereert.

Betekenis en Claims

• Resolutie van Vermoeden: Het artikel toont aan dat hoewel de stochastische heuristiek voorspelt dat oneindige lopen bijna zeker zijn, de werkelijke rekenkundige structuur de doodlopende paden aanzienlijk zeldzamer maakt dan voorspeld. De existentie van een oneindige loop blijft echter een open probleem; het artikel kwantificeert de zeldzaamheid van de "obstructies" (doodlopende paden), maar bewijst niet het bestaan van een oneindig pad.
• Formalisering: Een primaire claim van het artikel is dat de hoofdstelling (Stelling 1.2) volledig is geformaliseerd in Lean/Mathlib en dat het bewijs automatisch is geproduceerd door een AI-tool genaamd AxiomProver. Het systeem kreeg enkel een natuurlijke taalformulering van het probleem en leidde autonoom de gesloten formule en het bewijs af.
• Historische Context (Update): De auteurs merken op dat zij na de initiële arXiv-publicatie hebben vernomen van Kannan Soundararajan dat het hoofddoel reeds door Mirsky in 1947 [6] was verkregen. Het artikel erkent dat de 2024-studie van Miller et al. [5] naliet naar dit eerdere werk te verwijzen. Bijgevolg, hoewel de Lean-formalisering een geldige automatische bewijsvoering vormt, stellen de auteurs dat het manuscript niet zal worden ingediend voor publicatie in een wetenschappelijk tijdschrift als primair onderzoeksbijdrage, maar dient als een casestudy voor automatisch bewijzen.

Conclusie
Het artikel biedt een rigoureuze rekenkundige afleiding van de dichtheid van doodlopende paden in kwadraatvrije cijferlopen, waarbij een enorme afwijking van stochastische voorspellingen wordt aangetoond door getaltheoretische afhankelijkheden. De meest innovatieve bijdrage, zoals geformuleerd door de auteurs, is de succesvolle end-to-end automatische formalisering van dit resultaat met behulp van AxiomProver, wat het vermogen van huidige AI-systemen aantoont om niet-triviale problemen in de analytische getaltheorie aan te pakken.