Superlinear complexity of the $(3/2)^n$ steering word

기술 요약: $(3/2)^n$ 조향 단어(Steering Word)의 초선형 복잡도

문제 정의
본 논문은 함수 $x \mapsto \frac{3}{2}x$에 의한 1의 궤도(orbit)가 생성하는 기호 역학(symbolic dynamics)을 조사하며, 특히 근사 정수 반올림 오차(nearest-integer rounding errors)의 수열에 초점을 맞춘다. 수열 $\|(\frac{3}{2})^n\|$(최근접 정수까지의 거리)의 분포는 수론 분야의 오래된 미해결 난제이지만, 본 연구는 "조향 단어(steering word)" $T = (t_n)_{n \geq 0}$에 주목한다. 이 단어는 각 단계에서 선택된 정수 평행 이동(integer translates)을 기록하며, $m_n = \text{round}((\frac{3}{2})^n)$일 때 $t_n = 2m_{n+1} - 3m_n$으로 정의된다. 다루고자 하는 핵심 질문은 $T$의 부분 단어 복잡도(subword complexity) $p_T(k)$이며, 이는 $T$에 포함된 길이 $k$인 서로 다른 인자(factor)의 개수를 의미한다. 본 논문의 목적은 이 복잡도가 **초선형(superlinear)**임, 즉 $\lim_{k \to \infty} p_T(k)/k = \infty$임을 증명하는 것이다.

방법론
증명 전략은 대수적 수의 복잡도 연구(특히 Adamczewski–Bugeaud 방법)에서 사용되는 방법론을 이 동역학적 설정으로 전이하는 세 가지 단계로 구조화되어 있다. 이 논증은 **부공 정리(Subspace Theorem)**에 크게 의존하며, Lean-4를 통해 완전히 형식화되었음이 명시되어 있다.

1. 단계 0: 정확한 항등식 및 무조건적 경계 (섹션 2)
   저자는 정확한 "반복 항등식(repetition identity)"을 도출한다. 만약 길이 $k$인 인자가 위치 $a$와 $c$ ($a < c$)에서 반복된다면, 이는 관계식 $3^k(\varepsilon_c - \varepsilon_a) = 2^k(\varepsilon_{c+k} - \varepsilon_{a+k})$를 강제한다. 여기서 $\varepsilon_n$은 반올림 오차이다.

   • 이 항등식은 다음과 같은 가해성 조건(divisibility condition)을 도출한다: $2^k \mid (m_c - m_a)$.
   • 궤도의 성장 특성과 결합하여, 이는 긴 반복이 단어 내에서 임의로 늦게 발생할 수 없음을 확립한다.
   • 무조건적 결과: 본 논문은 $T$가 결국 주기적(eventually periodic)이지 않음을 증명하며, $p_T(k) \geq \frac{41}{24}k - 3$이라는 선형 하한을 설정한다. 이는 비주기적 단어의 Morse–Hedlund 하한($k+1$)보다 엄격히 높다.

2. 단계 1: 디오판토스 커널로의 환원 (섹션 3)
   초선형 복잡도를 증명하는 문제는 **커널(Kernel, K)**이라 불리는 단일 디오판토스 명제로 환원된다.

   • 명제 (K): 모든 유리수 $\theta \in (0, 1)$에 대하여, $2 \leq a < c$를 만족하며 $\|(\frac{3}{2})^c - (\frac{3}{2})^a\| \leq \theta^c$를 만족하는 쌍 $(a, c)$의 집합은 유한하다.
   • 이는 "지수적 쌍 반발(exponential pair repulsion)" 성질을 나타내며, 궤도 점들 사이의 거리의 하한을 기초값 $2^{-1}$에서 임의의 밑 $\theta < 1$로 개선한다.
   • 이 환원은 (K)가 성립하면 $p_T(k)/k \to \infty$임을 보여준다.

3. 단계 2: 커널의 확립 (섹션 4 & 5)
   (K)의 증명은 잠재적 해들의 집합을 세 가지 "슬라이스(slice)"로 분할하고 디오판토스 근사론의 심층적인 결과들을 적용함으로써 이루어진다.

   • 유한 간격 슬라이스(Bounded Gap Slice): 고정된 간격 $c-a$에 대해, Corvaja–Zannier 주 정리(Schmidt Subspace Theorem의 결과물)를 사용하여 유한성을 증명한다.
   • 거대 간격 슬라이스(Huge-Gap Slice): $a \leq \epsilon' c$인 영역의 경우, 이 문제를 pseudo-Pisot 배제의 특수한 사례로 취급함으로써 역시 Corvaja–Zannier 정리를 통해 유한성을 확립한다.
   • 중간 대역(Middle Band): 간격이 증가하지만 $a$가 $c$에 비해 무시할 수준이 아닌 나머지 영역의 경우, 저자는 **간격 이분법(gap dichotomy)**을 사용한다. 만약 해의 집합이 무한하다면, 서로 다른 간격을 가진 부분 집합을 추출할 수 있다. 이는 Nair–Kumar–Rout S-단위 튜플 정리를 통한 모순으로 이어지며, 이는 $(\frac{3}{2})^c$가 어떤 $c$에 대해 정수가 됨을 의미하는데, 이는 불가능하다.

주요 기여 및 결과

• 주 정리 (Theorem 1.1): 조향 단어 $T$의 부분 단어 복잡도는 초선형($p_T(k)/k \to \infty$)이다.
• 무조건적 하한: 본 논문은 증명되지 않은 추측에 의존하지 않고 도출된, 명시적이고 무조건적인 선형 하한 $p_T(k) \geq \frac{41}{24}k - 3$을 제공한다.
• 형식화: 전체 논증은 Lean-4로 형식화되었다. 이 형식화는 Evertse–Schlickewei의 3변수 Subspace Theorem에만 의존하므로, Corvaja–Zannier 및 Nair–Kumar–Rout 결과에 대한 논리적 의존성을 검증한다.
• 비주기성: 조향 단어가 결국 주기적이지 않다는 엄밀한 증명을 제공한다.

의의 및 주장
본 논문은 심볼릭 역학과 디오판토스 근사론을 연결함으로써 이 특정 자율적 동역학계의 복잡도 문제를 해결했다고 주장한다.

• 방법론적 전이: 대수적 수에 주로 사용되는 Adamczewski–Buseaud 방법을 동역학적 단어로 성공적으로 적응시켰다. 저자는 $(3/2)$-동역학의 자율적 특성이 반복되는 인자들을 접두사 고정(prefix-anchoring) 없이 깔끔한 디오판토스 부등식으로 압축할 수 있게 하여 계산 과정을 단순화한다고 언급한다.
• 심층 정리로의 의존: 초선형 성장에 관한 증명은 Corvaja–Zannier 정리(동료 검토 완료)와 Nair–Kumar–Rout 정리(집필 당시 프리프린트 상태)에 조건부로 의존한다. 그러나 Lean-4 형식화는 이러한 의존성들이 Subspace Theorem의 논리적 귀결임을 확인하는 역할을 한다.
• 한계: 초선형 성장에 관한 결과는 **비효과적(ineffective)**이다. 즉, Subspace Theorem은 예외적 집합(디오판토스 부등식의 해의 개수)의 크기에 대한 명시적인 경계를 제공하지 않는다. 본 논문은 $\|(\frac{3}{2})^n\| \to 0$의 밀도와 관련된 더 넓은 미해결 문제를 해결하려는 것이 아니라, 반올림 수열의 조합론적 복잡도를 규명하는 데 목적이 있다.