Dead ends in square-free digit walks

Evan Chen, Chris Cummins, Ben Eltschig, Dejan Grubisic, Leopold Haller, Letong Hong, Andranik Kurghinyan, Kenny Lau, H.m. Leather, Seewoo Lee, Aram Markosyan, Ken Ono, Manooshree Patel, Gaurang Pendharkar, Vedant Rathi, Alex Schneidman, Volker Seeker, Shubho Sengupta, Ishan Sinha, Jimmy Xin, Jujian ZhangarXiv 2026 · DOI · arXiv

Abstract: This paper provides a rigorous mathematical correction to a recent conjecture regarding "dead ends" in square-free digit walks. While previous stochastic models predicted a relatively high density of such numbers, the authors prove the true density is orders of magnitude smaller. Notably, the entire proof was automatically generated from a natural-language prompt and formalized in the Lean theorem prover using an AI tool called AxiomProver.

Introduction: Square-Free Digit Walks

A positive integer is square-free if it is not divisible by any perfect square greater than 1 (e.g., 10 is square-free, but 12 is not because it is divisible by $2^2$). A square-free digit walk involves starting with a square-free number and repeatedly appending digits such that the resulting number remains square-free.

A dead end occurs when a square-free number $N$ is reached where every possible one-digit extension in base $b$ ($bN + 0, bN + 1, \dots, bN + (b-1)$) results in a non-square-free number. In base 10, a 2024 study by Miller et al. suggested that infinite square-free walks occur with probability near 1, predicting an asymptotic dead-end density of approximately $5.218 \times 10^{-5}$ based on a stochastic independence model.

Stochastic Model vs. Arithmetic Reality

The stochastic model assumes that the square-freeness of $10N+0, 10N+1, \dots, 10N+9$ are independent events. However, this paper demonstrates that these events are highly dependent.

For any prime $p \ge 7$, the square $p^2$ is larger than the base (10). This implies the "One Prime, One Digit" rule: $p^2$ can "block" at most one digit extension at a time. To create a dead end, multiple distinct prime squares must "conspire" to block all ten possible extensions simultaneously. This requirement makes dead ends significantly rarer than a random model would suggest. The authors prove the true density in base 10 is:

[ c_{\mathrm{dead}} \approx 1.317 \times 10^{-9} ]

This value is roughly 40,000 times smaller than the stochastic prediction.

Methodology and AI Formalization

The authors employ classical tools from analytic number theory, including the Inclusion-Exclusion Principle, the Chinese Remainder Theorem (CRT), and Euler Products. The final density is expressed as a finite alternating sum of Euler products.

A unique aspect of this research is the use of AxiomProver. The authors provided the AI with a natural-language statement of the problem. The AI discovered the correct formula, generated a formal statement in the Lean 4 programming language, and produced a machine-verified proof. This serves as a successful case study for AI-driven formalization of graduate-level number theory.

Key Results

The paper provides a generalized formula (Theorem 1.2) for the asymptotic density of dead ends in any base $b \ge 2$. The density decreases rapidly as the base increases, as shown in the calculated constants for prime bases.

Calculated dead-end densities $c_{\text{dead}}(b)$ for prime bases $b$.

Historical Context and Future Work

In an update to the paper, the authors acknowledge that the core result was originally discovered by Leon Mirsky in 1947. This rediscovery highlights both the potential for modern research to overlook classical literature and the ability of AI to independently arrive at deep mathematical truths.

While the density of dead ends is now established, the original conjecture by Miller et al.—that an infinite square-free walk always exists from any starting point—remains open. Future work may also explore the limits of AI formalization in "frontier" mathematics where existing library lemmas are less prevalent.

Summary updated

Abstract

We study "dead ends" in square-free digit walks: square-free integers $N$ such that, in base $b$, every one-digit extension $bN+d$ is non-square-free. In base $10$, the stochastic independence model of Miller et al. suggests that infinite square-free walks occur with probability near $1$, corresponding to an asymptotic dead-end density of $\approx 5.218\times 10^{-5}$. We prove that the true asymptotic dead-end density satisfies \[ c_{\mathrm{dead}} \approx 1.317\times 10^{-9}, \] roughly a factor of $\sim 4\times 10^4$ smaller than the prediction. For every base $b\geq 2$, we prove that dead-end densities exist and are given by a closed-form expression (as a finite alternating sum of Euler products). The argument is fully formalized in Lean/Mathlib, and was produced automatically by AxiomProver from a natural-language statement of the problem.
BibTeX
@misc{chen2026dead,
  author = {Evan Chen and Chris Cummins and Ben Eltschig and Dejan Grubisic and Leopold Haller and Letong Hong and Andranik Kurghinyan and Kenny Lau and H.M. Leather and Seewoo Lee and Aram Markosyan and Ken Ono and Manooshree Patel and Gaurang Pendharkar and Vedant Rathi and Alex Schneidman and Volker Seeker and Shubho Sengupta and Ishan Sinha and Jimmy Xin and Jujian Zhang},
  title = {{Dead ends in square-free digit walks}},
  year = {2026},
  eprint = {2602.05095},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.05095},
}

Loading related content...

Figure