Balanced Fibonacci word rectangles, and beyond

1. 문제 정의 (Problem Statement)

• 배경: 무한 수열 $(a_i)_{i \ge 0}$로부터 정의된 무한 행렬 $A$를 고려합니다. 여기서 $A$의 $(k, \ell)$ 성분은 $a_{k+\ell}$입니다.
• 단어 직사각형 (Word Rectangle): 이 행렬에서 시작 인덱스 $i$를 가지는 $m \times n$ 크기의 부분 행렬 $A(i, m, n)$을 '단어 직사각형'이라고 부릅니다.
• 균형성 (Balance): $m \times n$ 크기의 모든 직사각형 $A(i, m, n)$에 포함된 1 의 개수 (또는 특정 문자의 개수) 를 $T(i, m, n)$이라고 할 때, 모든 $i$에 대해 $T(i, m, n)$이 가질 수 있는 서로 다른 값의 개수가 최대 2 개 이하인 경우, 해당 $(m, n)$ 쌍을 '균형적 (balanced)'이라고 정의합니다.
• 목표: 피보나치 단어 및 기타 특정 무한 단어에 대해, 어떤 $(m, n)$ 쌍이 균형적인지를 결정하는 것입니다. 기존 연구 (Anselmo et al.) 는 피보나치 수가 최대인 경우 등 일부 특수한 경우를 증명했으나, 일반적인 $(m, n)$ 쌍에 대한 완전한 분류는 이루어지지 않았습니다.

2. 방법론 (Methodology)

저자들은 **유한 오토마타 (Finite Automata)**와 논리식 자동화 (Automata-based Logic) 기법을 핵심 도구로 사용합니다.

• 스투르미안 단어와 오토마타:
  • 무리수 $\alpha$에 대응하는 스투르미안 특성 단어 $a_i = \lfloor (i+1)\alpha \rfloor - \lfloor i\alpha \rfloor$를 고려합니다.
  • Lemma 1: $m \times n$ 블록이 균형적이기 위한 필요충분조건은, $\Delta(i, m, n) = T(i+1, m, n) - T(i, m, n)$ 시퀀스에 $1, 0, \dots, 0, 1$ 또는 $-1, 0, \dots, 0, -1$ 형태의 블록이 존재하지 않는다는 것입니다.
  • Ostrowski $\alpha$-수계: $\alpha$가 2 차 무리수 (quadratic irrational) 일 때, $\lfloor n\alpha \rfloor$를 계산하는 유한 오토마타가 존재함이 알려져 있습니다. 이를 통해 1 차 논리식 (first-order logic) 으로 균형 조건을 표현하고, 이를 오토마타로 변환할 수 있습니다.
• Walnut 도구 사용:
  • 논문의 모든 계산과 오토마타 생성은 Walnut이라는 오픈 소스 소프트웨어를 사용하여 수행되었습니다. Walnut 은 오토마타 이론과 논리식을 결합하여 수열의 성질을 자동 증명하는 도구입니다.
  • 피보나치 단어의 경우 Zeckendorf 수계 (피보나치 수의 합으로 정수를 표현) 를, Tribonacci 단어의 경우 Tribonacci 수계를, Thue-Morse 단어의 경우 음의 2 진수 (base -2) 표현을 사용하여 오토마타를 구성했습니다.

3. 주요 결과 및 기여 (Key Contributions & Results)

A. 피보나치 단어 (Fibonacci Word)

• 정리 2 (Theorem 2): 2 차 무리수 $\alpha$에 대응하는 스투르미안 행렬의 $m \times n$ 블록이 균형적인지 여부를 결정하는 유한 오토마타를 구성하는 알고리즘이 존재합니다.
• 코롤러리 3 (Corollary 3): 피보나치 단어의 경우, **15 개의 상태 (states)**를 가진 오토마타 (그림 1) 가 모든 균형적인 $(m, n)$ 쌍을 정확히 받아들이는 것을 증명했습니다.
• 새로운 특성화 (Theorem 7): 오토마타의 경로를 분석하여 $m \le n$인 경우, $m$과 $n$의 Zeckendorf 전개 (피보나치 수의 합) 를 기반으로 한 인간이 읽을 수 있는 균형 조건을 도출했습니다. 이는 Anselmo et al. 의 결과를 일반화합니다.
• 밀도 결과 (Proposition 6): 주어진 $m$에 대해 균형적인 $n$의 밀도가 하한을 가진다는 것을 증명했습니다.

B. Tribonacci 단어

• 문제: Tribonacci 단어 (0, 1, 2 로 구성) 로 만들어진 직사각형이 서로에 대해 **2-균형 (2-balanced)**인 $(m, n)$ 쌍을 찾습니다.
• 정리 10 (Theorem 10):
  • $m=1$: 모든 $n$에 대해 2-균형입니다.
  • $m=2$: 77 개의 상태를 가진 Tribonacci 오토마타가 균형적인 $n$을 받아들이며, 그 패턴은 복잡합니다.
  • $m \ge 3$: 어떤 $n$에 대해서도 2-균형인 직사각형이 존재하지 않습니다. (특정 $3 \times 3$ 서브행렬의 불일치를 통해 증명).

C. Thue-Morse 단어

• 특징: Thue-Morse 단어는 $t_{2k} + t_{2k+1} = 1$ 등의 대칭성을 가집니다.
• 정리 11 (Theorem 11): $m \times n$ 직사각형의 1 의 개수 편차는 항상 $|2|A|_1 - mn| \le 4$ 이내입니다. 균형은 1, 2, 3, 4 중 하나입니다.
• 정리 12 (Theorem 12): 92 개의 상태를 가진 오토마타가 입력 $(m, n)$에 대한 균형 값을 계산합니다.
  • 계산 과정은 매우 복잡하여 (최대 3 천만 개 이상의 상태, 100GB RAM 사용) Walnut 과 Maple 을 활용한 대규모 계산이 필요했습니다.
• 정리 14 (Theorem 14): $m, n \ge 3$일 때, 균형이 정확히 3 인 경우는 $m$과 $n$이 모두 홀수일 때입니다.

4. 의의 및 결론 (Significance & Conclusion)

1. 자동화 증명 (Automated Proofs): 수열의 균형성과 같은 조합론적 성질을 유한 오토마타와 논리식을 통해 완전히 자동화하여 증명할 수 있음을 보였습니다. 이는 인간의 직관이나 수동 증명이 어려운 복잡한 패턴을 기계적으로 분석할 수 있는 강력한 방법을 제시합니다.
2. 일반화 가능성: 피보나치 단어뿐만 아니라 2 차 무리수에 대응하는 모든 스투르미안 단어, 그리고 Tribonacci, Thue-Morse 단어와 같은 다른 중요한 무한 단어에 대한 균형 문제를 체계적으로 해결할 수 있는 프레임워크를 제공했습니다.
3. 구체적 알고리즘: 단순히 존재성을 증명하는 것을 넘어, 실제 균형 조건을 판별하는 오토마타를 구성하고 (Walnut 코드 공개), 이를 통해 새로운 수학적 명제 (Proposition 5, 6 등) 를 검증했습니다.
4. 도구 활용: Walnut 과 같은 오토마타 기반 도구를 사용하여 대규모 계산 (수천만 상태의 오토마타) 을 수행하고 그 결과를 수학적으로 엄밀하게 검증한 사례로서, 컴퓨터 보조 수학 (Computer-Assisted Mathematics) 의 중요성을 보여줍니다.

이 논문은 조합론적 수열 이론과 오토마타 이론의 교차점에서, "균형"이라는 고전적인 문제를 새로운 관점에서 완전히 해결하고 확장했다는 점에서 중요한 의의를 가집니다.