Dead ends in square-free digit walks

기술 요약: 제곱 자유(Square-Free) 숫자 워크에서의 데드 엔드(Dead Ends)

문제 정의
본 논문은 제곱 자유 숫자 워크(square-free digit walks)에서 발생하는 "데드 엔드(dead ends)"의 존재와 밀도를 조사한다. 밑(base) $b$에서의 제곱 자유 워크는 제곱 자유 정수 $N_0$로 시작하여, 각 후속 항이 $N_{k+1} = bN_k + d$가 제곱 자유 상태를 유지하도록 하는 숫자 $d \in \{0, \dots, b-1\}$를 뒤에 붙여 형성되는 무한 수열 $N_0, N_1, N_2, \dots$를 구성하려고 시도한다.

양의 정수 $N$은 다음의 조건을 만족할 때 데드 엔드로 정의된다:

1. $N$은 제곱 자유이다.
2. 밑(base)의 모든 숫자 $d$에 대하여, 확장된 값 $bN + d$는 제곱 자유가 아니다.

Miller 등[5]이 제기한 핵심 질문은 무한한 제곱 자유 워크가 존재하는가 하는 점이다. 확률적 모델(Blind Unlimited Model)은 무한한 워크가 확률 1에 가깝게 존재함(즉, 10진법에서 데드 엔드의 점근적 밀도가 $\approx 5.218 \times 10^{-5}$임을 시사)을 제안하지만, 본 논문은 데드 엔드의 실제 산술적 밀도를 엄밀하게 분석하여 이러한 확률적 예측이 유효한지 결정한다.

방법론
저자들은 확률적 가정에 의존하는 대신, 기초적인 곱셈 정수론과 포함-배제의 원리를 결br 조합하여 사용한다.

1. 지시 함수(Indicator Functions): 문제는 뫼비우스 함수 $\mu(n)$를 사용하여 재정의된다. $\mu(n)^2$이 제곱 자유 정수의 지시 함수이므로, 데드 엔드 $N$의 지시 함수는 다음과 같이 표현된다:
   $$\mathbb{1}_{N \text{ is dead end}} = \mu(N)^2 \prod_{d \in D} (1 - \mu(bN + d)^2)$$
   여기서 $D$는 숫자의 집합이다.

2. 포함-배제(Inclusion-Exclusion): 곱셈 항은 숫자 집합의 모든 부분집합 $S$에 대한 합으로 전개된다. 이는 데드 엔드 개수 계산 함수 $D_b(X)$ (즉, $X$ 이하의 데드 엔드 개수)를, $n$과 그 모든 확장 $bn+d$($d \in S$)가 제곱 자유인 정수$n \le X$의 개수를 세는 계산 함수$Q_S(X)$의 교대합으로 변환한다.

3. 체 이론(Sieve Analysis): 고정된 부분집합 $S$에 대하여, $n$과 $bn+d$가 모두 제곱 자유라는 조건은 소수별로 분석된다. 저자들은 피해야 할 "나쁜" 나머지 클래스(residue classes) $\pmod{p^2}$를 정의한다. 중국인의 나머지 정리(Chinese Remainder Theorem)를 사용하여, 이러한 클래스를 피하는 정수의 밀도를 결정한다.

   • $p \nmid b$인 큰 소수 $p$에 대해, 조건 $p^2 \mid (bn+d)$는 $n$을 $\pmod{p^2}$에서의 단일 나머지 클래스로 강제한다. 결정적으로, 단일 소수의 제곱은 한 번에 최대 하나의 숫자 확지만을 차단할 수 있다.
   • 밀도는 국소적 인자(local factors) $(1 - \nu_{p,b}(S)/p^2)$의 무한 곱(오일러 곱)으로 표현된다. 여기서 $\nu_{p,b}(S)$는 금지된 나머지 클래스 $\pmod{p^2}$의 개수를 센다.

4. 오차항 제어(Error Term Control): 증명 과정에서는 매개변수 $z$까지 체를 자르는 것과 큰 소수의 기여로부터 발생하는 오차항을 주의 깊게 제한하며, $O(X/\sqrt{\log X})$의 오차항을 확립한다.

주요 결과

• 정리 1.1 (10진법): 10진법에서의 데드 엔드의 점근적 밀도는 존재하며 다음과 같이 주어진다:
  $$c_{\text{dead}} = \sum_{S \subseteq \{0,\dots,9\}} (-1)^{|S|} \prod_{p \text{ prime}} \left( 1 - \frac{\nu_p(S)}{p^2} \right)$$
  여기서 $\nu_p(S)$는 $p^2 \mid n$ 이거나 $p^2 \mid (10n+d)$를 만족하는 $d \in S$가 존재하는 $n \pmod{p^2}$의 클래스 개수이다.
  계산된 값은 $c_{\text{dead}} \approx 1.317 \times 10^{-9}$이다.

• 정리 1.2 (일반적인 밑 $b$): 이 결과는 임의의 밑 $b \ge 2$에 대해 일반화된다. 밀도 $c_{\text{dead}}(b)$는 오일러 곱의 교대합을 포함하는 유사한 폐쇄형 식(closed-form expression)으로 주어진다. 논문은 소수 밑 $b \in \{2, 3, 5, 7\}$에 대한 근사치를 제공한다.

• 확률적 모델과의 불일치: 실제 밀도($\approx 1.3 \times 10^{-9}$)는 확률적 예측($\approx 5.2 \times 10^{-5}$)보다 약 40,000배 더 작다. 저자들은 이를 산술적 의존성 때문이라고 설명한다. 단순한 확률적 모델은 숫자 확장 간의 독립성을 가정하지만, 실제로는 열 개의 확장이 동시에 실패하려면 많은 서로 다른 소수의 제곱에 의해 동시다발적으로 차단되어야 하며, 이는 독립 확률 모델이 제시하는 것보다 훨씬 더 엄격한 조건이다.

의의 및 주장

• 추측의 해결: 본 논문은 확률적 휴리스틱이 무한한 워크가 거의 확실하다고 예측하는 반면, 실제 산술 구조는 데드 엔드를 예측보다 훨씬 더 희귀하게 만든다는 것을 보여준다. 그러나 무한한 워크의 존재 여부는 여전히 미해결 과제로 남아 있다. 본 논문은 "장애물"(데드 엔드)의 희귀성을 정량화하지만, 무한한 경로의 존재를 증명하지는 않는다.
• 정형화(Formalization): 논문의 주요 주장은 메인 정리(정리 1.2)가 Lean/Mathlib에서 완전히 정형화되었으며, 그 증명이 AxiomProver라는 AI 도구에 의해 자동으로 생성되었다는 것이다. 이 시스템은 문제에 대한 자연어 진술만을 제공받았으며, 폐쇄형 공식을 자율적으로 도출하고 증명을 수행했다.
• 역사적 맥락 (업데이트): 저자들은 초기 arXiv 게시 이후, 메인 결과가 이미 Mirsky에 의해 1947년에 얻어진 것임을 알게 되었다고 언급한다. 논문은 2024년 Miller 등의 연구[5]가 이 선행 연구를 참조하지 못했음을 인정한다. 따라서 Lean 정형화는 유효한 자동 증명으로서 가치가 있으나, 저자들은 본 원고를 일차적인 연구 기여로서 학술지에 제출하지 않을 것이며, 대신 자동 정리 증명의 사례 연구로 활용할 것이라고 밝힌다.

결론
본 논문은 제곱 자유 숫자 워크에서의 데드 엔드 밀도에 대한 엄밀한 산술적 유도를 제공하며, 산술적 의존성으로 인해 확률적 예측으로부터 발생하는 거대한 편차를 드러낸다. 이 논문의 가장 참신한 기여는, AxiomProver를 사용하여 이 결과를 엔드 투 엔드(end-to-end)로 자동 정형화하는 데 성공함으로써, 현재의 AI 시스템이 해석적 정수론의 비자명한 문제를 다룰 수 있음을 입증한 데 있다.