Aperiodicity and subword complexity in the binary expansion of powers of three

기술 요약: 3의 거듭제곱의 이진 전개에 있어서의 비주기성과 부분 단어 복잡도

문제 정의
본 논문은 정수 $3^m$ 형태의 이진 자릿수가 갖는 미세한 구조적 특성을 조사한다. 이전 연구들은 비영(non-zero) 이진 자릿수의 개수($s_2(3^m)$)와 "블록"(동일한 숫자의 연속된 최대 구간)의 개수가 $m$이 증가함에 따라 무한히 증가한다는 사실을 입증하였으나, 이러한 결과들이 자릿수의 배열을 완전히 규명하지는 못했다. 구체적으로, 본 논문은 다음 두 가지 공백을 다룬다:

1. 비주기성(Aperiodicity): $3^m$의 이진 전개 내에 긴 주기적 패턴(주기 $p$인 연속 구간)이 존재하는가? 기존 연구들은 긴 상수 구간(주기 $p=1$)의 존재를 배제하였으나, 고정된 주기 $p > 1$에 대한 동작은 알려지지 않았다.
2. 부분 단어 복잡도(Subword Complexity): $3^m$의 하위 자릿수로 형성된 유한 이진 단어는 "전체(full)" 복잡성을 보이는가? 무한 단어의 맥락에서 모스-헤들런드(Morse–Hedlund) 정리는 부분 단어 복잡도 $p(n) \le n$이면 결국 주기적임을 명시한다. 본 논문은 $3^m$의 유한 단어가 충분히 큰 $m$에 대해 $p_{3^m}(n) \ge n+1$이라는 하한을 만족하는지, 즉 그 길이 내에서 너무 단순하거나 주기적이지 않음을 입증하고자 한다.

방법론
증명은 초월수 이론과 조합론적 단어 분석의 결합에 의존한다:

• 로그에 관한 선형 형식(Linear Forms in Logarithms): 핵심 엔진은 대수적 수의 로그에 관한 베이커-뷔스톨츠(Baker and Wüstholz)의 효과적인 정리이다. 본 논문은 이 정리를 활용하여 "간격 원리(gap principles)"를 확립한다. 논리의 흐름은 다음과 같다: 만약 $3^m$의 이진 전개 내에 긴 주기적 구간이 존재한다면, 이는 특정 정수 항등식을 강제하며, 이는 2, 3 및 보조 정수들의 로그에 관한 비제로(non-zero) 선형 형식 $\Lambda$를 도출한다. 베이커-뷔스톨츠 정리는 $|\Lambda|$에 대한 하한을 제공하며, 이는 긴 주기적 창(window)의 존재로 인해 암시되는 작은 값과 모순된다.
  • 참신성: 본 논문은 새로운 주기-$p$ 실행 추정치(period-$p$ run estimate) (보조정리 2.2)를 도입한다. 고전적인 결과들이 상수 구간을 제한하기 위해 세 항의 선형 형식을 사용하는 반면, 본 연구는 임의의 고정된 주기 $p$를 갖는 주기적 실행을 제한하기 위해 사 항의 선형 형식을 도출한다.
• 조합론적 전파(Combinatorial Propagation): 부분 단어 복잡도를 다루기 위해, 본 논문은 모스-헤들런드 정리의 유한한 정량적 버전(보조정리 4.1)을 채택한다. 이 보조정리는 만약 어떤 단어가 낮은 부분 단어 복잡도(길이 $n$인 서로 다른 인자가 최대 $n$개)를 가진다면, 반드시 긴 주기적 인자를 포함해야 함을 확립한다. 이 주기적 인자는 이후 주기-$p$ 실행 추정치로 전달되어 큰 $m$에 대한 모순을 도출한다.
• 형식 검증: 본 논문의 모든 정리와 보조정리는 Lean 4 증명 보조기를 사용하여 형식적으로 검증되었다.

주요 기여 및 결과

1. 주기-$p$ 실행의 비주기성 (정리 A)
본 논문은 $3^m$의 이진 전개가 $p$-주기성을 깨뜨리는 위치의 개수 $B_p(3^m)$가 점근적으로 증가함을 증명한다.

• 결과: $B_p(3^m) \ge \frac{\log m}{\log \log m + C_p} - 2$ (여기서 $C_p > 0$인 상수).
• 함의: $3^m$의 이진 전개 내에서 고정된 $\log m$의 거듭제곱보다 깊은 수준의 창(window)은 $p$-주기적일 수 없다. 이는 $p=1$(상수 구간)에 대한 기존 결과(Blecksmith–Filaseta–Nicol; Bugeaud–Kaneko)를 모든 고정된 주기로 일반화한다.

2. 전체 하위 자릿수 부분 단어 복잡도 (정리 B)
본 논문은 $3^m$의 하위 자릿수로 형성된 유한 이진 단어의 부분 단어 복잡도에 대한 하한을 설정한다.

• 결과: 모든 길이 $n \ge 1$에 대하여, 복잡도 함수는 충분히 큰 모든 $m$에 대해 $p_{3^m}(n) \ge n + 1$을 만족한다.
• 임계값: 임계값 $m$은 효과적(effective)이다. 이는 $3^m$의 자릿수 선형 성장 $M(3^m) \approx m \log_2 3$이 주기-$p$ 실행 추정치로부터 도출된 $n^2 \log m$ 차수의 경계값을 추월할 때 발생한다.
• 함의: $3^m$의 유한 단어는 낮은 복잡도를 갖는다는 의미에서 결국 주기적이지 않으며, 무한 단어에서 주기성을 방지하는 조건인 "전체" 복잡성을 가진다.

의의 및 주장
저자는 이러한 결과들이 두 가지 특정 방향에서 3의 거듭제곱의 이진 자릿수 분포에 대한 이해를 강화한다고 주장한다:

• 기존 경계의 확장: 스튜어트(Stewart)의 정리와 후속 연구들이 $3^m$이 적은 희소 자릿수와 많은 블록을 가짐을 확립했으나, 본 논문은 비주기성 결과를 상수 구간뿐만 아니라 모든 고정된 주기 $p$로 확장한다.
• 유한 대 무한의 맥락: 본 논문은 대수적 무리수(무한 전개를 가짐)에 대한 연구와 자신의 기여를 구분한다. 본 논문은 단일 거듭제곱 $3^m$의 유한 단어에 대한 자릿수 변화 및 부분 단어 복잡도에 대한 최초의 정량적 결과를 제공한다.
• 최적성: 정리 B는 $3^m$의 유한 자릿수 단어에 대한 모스-헤들런드 정리의 상응물로 제시되며, "선형 형식 최적(linear-forms optimum)"에 위치한다. 저자는 초선형(superlinear) per-word 복잡성을 증명하는 것이 본 논문에서 다루지 않은 별개의 더 어려운 문제임을 언급한다.

이 연구는 베이커 이론(Baker's theory)을 통한 $3^m$의 산술적 성질과 그 자릿수 문자열의 조합론적 구조 사이의 상호작용에 의존하며, 이 수들에 내재된 "무질서" 또는 비주기성에 대한 효과적인 하한을 제공한다.