Infinite Words with very Low Factor Complexity: an introduction to Combinatorics on Words

이 논문은 무한 단어의 최소 인자 복잡도를 중심으로 스투미안 단어와 라우지 그래프 등 고전적 도구와 1999 년 티드만의 정리에 대한 새로운 대수적 증명 등을 다루며, 동역학·대수·산술과의 상호작용을 소개하는 조합론적 단어 입문서입니다.

핵심

📖 핵심 주제: "단순함의 한계"

생각해 보세요. 무한히 긴 문자열이 있다고 칩시다. 예를 들어 121212...처럼 반복되거나, 1234567890...처럼 모든 숫자가 섞여 있는 경우죠.

이때 **"복잡도 **(Complexity)라는 개념이 나옵니다.

• 비유: 이 문자열을 레고 블록으로 만든다고 상상해 보세요.
• 규칙: 길이가 1 인 블록 (A, B, C...) 을 몇 개 쓰나요? 길이가 2 인 블록 (AB, BC...) 은 몇 개 쓰나요?
• 질문: "이 문자열이 얼마나 복잡한가?"를 묻는 것입니다.

논문의 핵심 질문은 이것입니다:

**"단순한데, 너무 단순하지도 않은 **(반복되지 않는)

---

1️⃣ 1 장: 2 개의 알파벳 (레고 A 와 B) 일 때의 정답

먼저 알파벳이 2 개 (A, B) 일 때를 생각해 봅시다.

• 너무 단순한 경우: AAAAA... (A 만 반복) → 복잡도가 1 입니다. (지루함)
• 반복되는 경우: ABABAB... → 복잡도가 2 입니다. (지루함)
• 모든 경우: ABCDEF... (모든 조합이 다 나옴) → 복잡도가 매우 큽니다. (너무 복잡함)

**모스 - 헤들런드 **(Morse-Hedlund)는 1938 년에 이렇게 말했습니다.

"만약 길이가 $n$인 블록의 종류가 $n$개보다 적다면, 그 문자열은 결국 반복되는 패턴을 가진다."

그렇다면 반복되지 않으면서 가장 단순한 문자열은 무엇일까요?

• 답은 $n+1$개입니다. (길이가 1 인 블록은 2 개, 길이가 2 인 블록은 3 개...)
• 이 특별한 문자열들을 **스투르미안 **(Sturmian)이라고 부릅니다.

🌟 스투르미안 단어의 비밀:
이 단어들은 **황금비 **(Golden Ratio)와 깊은 연관이 있습니다.

• 비유: 원형 탁구대 위에서 공을 튕겨 보내면, 공이 벽에 닿는 순서가 바로 스투르미안 단어가 됩니다.
• 이 공의 각도가 **무리수 **(irrational number)일 때만, 공은 절대 같은 궤적을 반복하지 않으면서도 가장 효율적으로 (단순하게) 움직입니다.

---

2️⃣ 2 장: 알파벳이 3 개 이상일 때의 난제

이제 알파벳이 3 개 (A, B, C) 이상일 때는 어떨까요?

• 단순히 "반복되지 않는다"는 조건만으로는 부족합니다.
• 예를 들어 ABCABC...처럼 반복되지는 않지만, A만 계속 나오고 B, C는 가끔 나오는 식으로 편향될 수 있습니다.

새로운 기준: "균형 잡힌 비율"
논문의 저자들은 "각 알파벳이 나타나는 비율이 **서로 유리수 **(분수)이어야 한다"고 제안합니다.

• 비유: 3 가지 재료를 섞어 요리를 할 때, A, B, C 의 비율이 1:1:1이나 1:2:3처럼 깔끔한 분수라면, 결국 이 요리는 어떤 패턴으로 반복될 가능성이 큽니다.
• 하지만 비율이 무리수로 섞여 있다면 (예: $\sqrt{2} : \pi : e$), 그 요리는 절대 반복되지 않는 진정한 '혼합' 상태가 됩니다.

**티데만 **(Tijdeman)
이런 '균형 잡힌' 3 개 이상의 알파벳 문자열에서, 가장 낮은 복잡도는 무엇일까요?

• 답은 $(d-1)n + 1$입니다. ($d$는 알파벳 개수, $n$은 블록 길이)
• 예: 알파벳 3 개면 복잡도는 $2n+1$입니다.

---

3 장: 새로운 증명 방법 (수학의 마법)

이 논문은 1999 년 티데만이 증명한 이 사실을, **2022 년에 저자와 동료인 카세이뉴 **(Cassaigne)했습니다.

• **기존 방법 **(티데만) 복잡한 조합론적 논리와 '경로'를 세는 방식. (마치 미로에서 길을 찾는 것)
• **새로운 방법 **(저자) **선형 대수 **(Linear Algebra)를 사용했습니다.
  • 비유: 문자열의 흐름을 전기 회로나 **수관 **(파이프)으로 보았습니다.
  • 각 알파벳이 흐르는 '전류'나 '물'의 양을 계산하는 **행렬 **(Flow Matrix)을 만들었습니다.
  • 이 행렬을 분석하면, "왜 복잡도가 이 정도는 되어야만 하는가?"를 수학적 법칙처럼 증명할 수 있었습니다.

**🎁 추가 발견: "덴드릭 **(Dendric)
이 새로운 증명 과정에서 흥미로운 사실을 발견했습니다.

• 이 최소 복잡도를 가진 단어들은 모두 **나무 **(Tree) 구조와 닮아 있습니다.
• 비유: 레고 블록을 연결할 때, 한 블록에서 여러 갈래로 뻗어나가도 **어디로 가든 다시 합쳐지는 고리 **(Cycle)가 없는 구조입니다.
• 이를 **덴드릭 **(Dendric)이라고 부르는데, 이 단어들은 수학적으로 매우 '예쁘고' 구조화된 형태를 가집니다.

---

📝 요약: 이 논문이 우리에게 주는 메시지

1. 질문: "무한히 긴 문자열 중, 반복되지 않으면서도 가장 단순한 것은 무엇인가?"
2. 2 개 알파벳: 스투르미안 단어 (황금비와 연결됨).
3. 3 개 이상 알파벳: 티데만의 최소 복잡도 (알파벳 비율이 무리수일 때).
4. 방법: 복잡한 논리 대신 **행렬 **(수학의 도구)을 이용해 더 깔끔하게 증명함.
5. 결론: 이러한 단어들은 **나무 **(Dendric)처럼 가지치기가 잘 된 아름다운 구조를 가짐.

한 줄 평:

"수학자들은 무한히 긴 문자열 속에서 가장 효율적인 패턴을 찾아냈고, 그것이 황금비와 나무처럼 자연의 법칙과 닮아 있다는 것을 증명했습니다."

이 논문은 추상적인 수학이 어떻게 **동역학 **(움직임)과 **대수학 **(수식)을 연결하며, 세상의 복잡한 패턴을 이해하는 열쇠가 되는지 보여주는 훌륭한 사례입니다.

기술 요약

이 논문은 Mélodie Andrieu 가 작성한 "무한 단어의 매우 낮은 인자 복잡도 (Infinite Words with very Low Factor Complexity)"에 대한 강의 노트로, 조합론적 단어 이론 (Combinatorics on Words), 동역학, 대수학, 그리고 산술 간의 상호작용을 다룹니다. 특히, 이진 (binary) 및 d-진 (d-ary) 알파벳을 가진 무한 단어의 **최소 인자 복잡도 (minimal factor complexity)**를 규명하는 것이 핵심 주제입니다.

다음은 이 논문의 기술적 요약입니다.

---

1. 연구 문제 (Problem)

이 논문은 다음과 같은 근본적인 질문들을 다룹니다:

• 최소 복잡도: 이진, 삼진, 혹은 일반적인 유한 알파벳을 가진 '비자명 (non-trivial)' 무한 단어의 최소 인자 복잡도는 무엇인가?
• 비자명성의 정의: '비자명성'을 어떻게 엄밀하게 정의해야 하는가? (단순히 비주기적인 것만으로는 충분하지 않을 수 있음)
• 달성자: 어떤 단어들이 이 최소 복잡도를 달성하는가?
• 구조: 이러한 단어들은 얼마나 많으며, 그 구조는 어떻게 되는가?

배경:

• Morse 와 Hedlund 의 1938 년 정리에 따르면, 이진 단어에서 복잡도 함수 $p_w(n)$이 유계이거나 $p_w(n) \le n$인 경우, 그 단어는 결국 주기적 (eventually periodic) 이다.
• 따라서 비주기적 이진 단어의 최소 복잡도는 $p_w(n) = n+1$이며, 이를 만족하는 단어를 Sturmian 단어라고 부른다.
• 문제점: $d \ge 3$인 경우, 단순히 "비주기적"이라는 조건만으로는 Sturmian 단어를 자연스럽게 일반화한 클래스를 정의하기 어렵다. 예를 들어, 복잡도가 $n+d-1$인 단어들이 존재하지만, 이들은 Sturmian 단어를 임의로 변형한 인위적인 구조를 가질 수 있다.

2. 방법론 (Methodology)

논문은 크게 세 장으로 구성되어 있으며, 다음과 같은 방법론을 사용한다:

• 제 1 장 (Sturmian 단어의 재해석):

  • Sturmian 단어를 복잡도 $n+1$의 정의에서 출발하여, **연분수 (continued fractions)**와의 연결, 재규격화 (renormalization) 과정, 그리고 동역학적/기하학적 모델 (원 위의 회전, 구면 billiard, 선형 흐름 등) 을 통해 체계적으로 소개한다.
  • Sturmian 단어의 핵심 성질인 **문자 주파수의 유리수적 독립성 (rational independence of letter frequencies)**을 강조한다.

• 제 2 장 (Tijdeman 정리의 일반화):

  • $d \ge 3$인 경우, "비주기적" 대신 **"문자 주파수의 유리수적 독립성"**을 비자명성의 조건으로 제시한다.
  • R. Tijdeman (1999) 의 정리를 소개하여, 유리수적으로 독립적인 주파수를 가진 $d$-진 단어의 최소 복잡도가 $p_w(n) = (d-1)n + 1$임을 보인다.
  • 기존 연구들 (Arnoux-Rauzy 단어, episturmian 단어 등) 이 이 최소 복잡도 클래스에 속함을 논의한다.

• 제 3 장 (대수적 증명 및 새로운 결과):

  • Tijdeman 의 원래 정리를 **대수적 방법 (linear algebra)**으로 재증명한다.
  • Rauzy 그래프와 새로운 개념인 **Flow Matrix (흐름 행렬)**를 도입하여, 단어의 인자 주파수와 행렬의 핵 (kernel) 사이의 관계를 분석한다.
  • Rank-Nullity 정리와 유리수/실수 선형 공간의 차원을 이용하여 복잡도 하한을 유도한다.
  • 이 대수적 증명을 통해, 최소 복잡도를 가진 단어들이 덴드릭 (dendric) 구조를 가진다는 새로운 결과를 도출한다.

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

A. Tijdeman 정리의 강화 및 대수적 증명 (Theorem 3.1)

• 기존 Tijdeman 정리 (1999): 단어의 문자 주파수 집합 $F_w$에서 정의된 '최소 무리수 차수 (minimal degree of irrationality, $\delta_w$)'를 사용하여 복잡도 하한을 제시했다.
• 강화된 정리 (Andrieu & Cassaigne, 2022): **최대 무리수 차수 (maximal degree of irrationality, $\Delta_w$)**를 사용하여 더 강력한 하한을 제시한다.
  • 결과: $p_w(n) \ge (\Delta_w - 1)(n - 1) + d$.
  • 의미: 만약 단어의 주파수 집합 내에서 더 높은 차수의 무리수적 독립성을 가진 점들이 존재한다면, 복잡도는 더 빠르게 성장해야 함을 의미한다. 이는 Tijdeman 의 원래 증명보다 더 정밀한 정보를 제공한다.

B. 최소 복잡도 단어의 구조적 특성: 덴드릭성 (Theorem 3.2)

• 새로운 결과: 유리수적으로 독립적인 주파수를 가지며 Tijdeman 의 최소 복잡도 $p_w(n) = (d-1)n + 1$을 달성하는 모든 $d$-진 단어는 **덴드릭 (dendric)**이다.
• 덴드릭 단어: 모든 인자 (factor) 의 확장 그래프 (extension graph) 가 트리 (tree) 구조를 가지는 단어.
• 의미: 이는 최소 복잡도 단어들이 단순한 복잡도 수치 이상으로 매우 특정한 조합론적 구조를 공유함을 보여준다. 덴드릭 단어는 복잡도가 정확히 $(d-1)n+1$인 것과 동치이며, 이는 Sturmian 단어의 일반화로서 중요한 성질이다.

C. 대수적 증명 기법의 정립

• Flow Matrix: Rauzy 그래프의 인접 행렬과 유사하지만, 인자의 시작과 끝을 고려하여 $+1, -1, 0$ 값을 갖는 직사각형 행렬을 정의했다.
• Kirchhoff 법칙의 적용: 단어의 인자 주파수가 이 Flow Matrix 의 핵 (kernel) 에 속한다는 것을 보임으로써, 전기 회로의 키르히호프 법칙과 유사한 '보존 법칙'을 조합론적 단어에 적용했다. 이는 기존에 주로 사용되던 순수 조합론적 증명과는 다른 새로운 접근법이다.

4. 의의 (Significance)

1. 이론적 통합: Morse-Hedlund 정리를 이진 알파벳에서 $d$-진 알파벳으로 성공적으로 일반화했다. 이를 위해 '비주기성' 대신 '유리수적 독립성'이라는 더 강력한 조건을 도입하여, Sturmian 단어의 본질적인 성질을 보존하면서 고차원 일반화를 가능하게 했다.
2. 새로운 증명 도구: 선형대수학 (행렬의 핵, 랭크 - 널리티 정리) 을 조합론적 단어 이론에 적용하는 새로운 프레임워크를 제시했다. 이는 향후 복잡한 단어 클래스의 복잡도 분석에 강력한 도구가 될 것이다.
3. 구조적 통찰: 최소 복잡도를 가진 단어들이 단순히 복잡도 값이 작은 것을 넘어, '덴드릭'이라는 강력한 조합론적 구조를 공유함을 증명했다. 이는 $d \ge 3$인 경우의 Sturmian 일반화 클래스를 완전히 특징짓는 (characterize) 중요한 진전이다.
4. 개방적 문제 제시: $d \ge 3$인 경우, 덴드릭성 외에 기하학적/동역학적 관점에서의 완전한 특징화 (characterization) 는 여전히 열린 문제로 남아있음을 지적하며 향후 연구 방향을 제시했다.

요약

이 논문은 무한 단어의 최소 복잡도 문제를 해결하기 위해, Tijdeman 의 정리를 재발견하고 대수적 기법을 통해 강화한 뒤, 그 결과로 최소 복잡도 단어들이 반드시 '덴드릭' 구조를 가져야 함을 증명했다. 이는 조합론적 단어 이론에서 복잡도, 대수, 동역학이 어떻게 긴밀하게 연결되는지를 보여주는 중요한 성과이다.