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.
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