On a sequence of Kimberling and its relationship to the Tribonacci word

이 논문은 2017 년 클라크 킴벌링이 제안한 0 과 1 로 이루어진 수열에 대한 여러 추측을 Walnut 자동화 증명기를 활용하여 증명하고, 이 수열이 무한한 트리보나치 단어와 갖는 관계, 부분 단어 복잡도, 그리고 임계 지수를 규명합니다.

핵심

1. 이야기의 시작: "불규칙한 레시피" (킴벌링의 규칙)

킴벌링은 0 과 1 로 이루어진 긴 줄을 만들었습니다. 그는 아주 독특한 규칙을 사용했습니다.

• 규칙: "00 이 보이면 '0101'로 바꾸고, '1'이 보이면 '10'으로 바꾸고, '0'은 그냥 '0'으로 둬라."
• 비유: 마치 요리사가 재료를 섞는 방식입니다. 보통 요리사는 "밀가루 1 컵, 설탕 1 컵"처럼 정해진 비율 (함수) 을 따르지만, 킴벌링의 레시피는 "반죽 덩어리 (00) 를 보면 이 모양으로, 작은 알갱이 (1) 를 보면 저 모양으로" 변형시키는 매우 유연하고 복잡한 방식입니다.

이 과정을 반복하면 길이가 점점 늘어나는 숫자 열이 만들어지는데, 킴벌링은 이 열의 길이가 어떤 수학 공식으로 정확히 계산될 것이라고 추측했습니다.

2. 첫 번째 발견: "길이의 비밀" (킴벌링의 추측 증명)

저자들은 이 복잡한 레시피를 통해 만들어지는 숫자 열의 길이가 킴벌링이 예상한 공식과 완벽하게 일치함을 증명했습니다.

• 비유: 마치 레고 블록을 쌓을 때, "1 단계는 2 개, 2 단계는 4 개, 3 단계는 6 개..."라고 예측했는데, 실제로 쌓아보니 그 예측이 100% 정확하다는 것을 확인한 것과 같습니다.
• 도구: 이 증명을 위해 저자들은 **'월넛 (Walnut)'**이라는 컴퓨터 프로그램 (수학 증명을 자동으로 해주는 '로봇 변호사') 을 사용했습니다. 복잡한 논리를 사람이 일일이 따져보기보다 컴퓨터가 "참이다/거짓이다"를 확인하게 한 것입니다.

3. 두 번째 발견: "친구 관계" (트라이보나치 단어와의 연결)

이 논문에서 가장 흥미로운 부분은 이 숫자 열이 수학계에서 유명한 **'트라이보나치 (Tribonacci) 단어'**라는 다른 구조와 깊은 연관이 있다는 것을 발견한 것입니다.

• 트라이보나치 단어: 0, 1, 2 세 가지 숫자가 규칙적으로 반복되는 매우 유명한 수열입니다. (피보나치 수열의 3 단계 버전이라고 생각하시면 됩니다.)
• 발견: 킴벌링의 숫자 열은 사실 트라이보나치 단어를 '번역기'에 통과시킨 결과였습니다.
• 비유: 트라이보나치 단어가 원본 지도라면, 킴벌링의 숫자 열은 그 지도를 특정 언어 (0 과 1) 로 번역한 버전입니다. 저자들은 이 번역 규칙 (함수) 을 찾아냈고, "아! 이 두 가지는 사실 같은 것의 다른 모습이었구나!"라고 깨달았습니다.

4. 세 번째 발견: "미로의 복잡도" (패턴의 수와 반복)

저자들은 이 숫자 열이 얼마나 복잡한지, 그리고 얼마나 자주 같은 패턴이 반복되는지 분석했습니다.

• 패턴의 수 (Factor Complexity): 숫자 열에서 '010'이나 '100'처럼 짧은 조각들이 얼마나 다양하게 나타나는지 세는 것입니다. 저자들은 이 숫자 열이 **가장 복잡한 형태 (2의 n 제곱)**를 가진다는 것을 증명했습니다.
  • 비유: 이 열은 미로와 같습니다. 길이가 10 인 미로라면, 그 안에 들어갈 수 있는 모든 가능한 길이의 조합이 다채롭게 존재한다는 뜻입니다.
• 임계 지수 (Critical Exponent): "이 숫자 열에서 같은 패턴이 얼마나 길게 반복될까?"를 묻는 것입니다. 예를 들어 '010101'처럼 '01'이 3 번 반복되는 경우입니다.
  • 저자들은 이 반복의 한계가 약 3.19 배라는 것을 계산해냈습니다. 즉, 어떤 패턴도 3.19 번 이상 완벽하게 반복될 수는 없다는 뜻입니다. 이는 트라이보나치 단어와 똑같은 한계를 가집니다.

5. 결론: 왜 이 연구가 중요한가?

이 논문은 단순히 "어떤 숫자 열을 분석했다"는 것을 넘어, 복잡해 보이는 규칙을 가진 수열을 어떻게 체계적으로 분석할 수 있는지를 보여주는 교과서 (Primer) 역할을 합니다.

• 핵심 메시지: "복잡한 규칙 (인플레이션 규칙) 으로 만들어진 수열도, 잘 알려진 구조 (트라이보나치) 와 연결된다는 것을 발견하고, 컴퓨터 도구 (월넛) 를 활용하면 그 성질을 완벽하게 증명할 수 있다."
• 일상적인 비유: 마치 복잡한 도시의 교통 흐름을 분석할 때, 개별 차량의 움직임을 일일이 쫓는 대신, **지하철 노선도 (트라이보나치)**와 연결된다는 것을 발견하고, 그 노선도를 통해 전체 교통 체증의 패턴을 예측하는 것과 같습니다.

한 줄 요약:

"수학자가 만든 복잡한 0 과 1 의 나열이, 사실은 유명한 '트라이보나치'라는 수열의 변형이었으며, 컴퓨터를 이용해 그 길이, 패턴, 반복의 한계를 완벽하게 증명했습니다."

기술 요약

논문 요약: Kimberling 수열과 Tribonacci 단어의 관계

저자: Lubomíra Dvořáková, Edita Pelantová (체코 공과대학교), Jeffrey Shallit (워터루 대학교)
주제: Clark Kimberling이 2017 년에 정의한 이진 수열 (OEIS A288462) 의 성질 분석, Tribonacci 단어와의 관계 규명, 그리고 Walnut 자동화 증명기를 활용한 증명.

1. 연구 문제 (Problem)

2017 년 Clark Kimberling 은 특정 팽창 규칙 (inflation rules) 을 통해 정의된 이진 수열 $B = 0100101100\dots$를 제안했습니다.

• 정의: $B_0 = 00$으로 시작하여, $B_i$를 $00, 0, 1$로 이루어진 최대 블록으로 분해한 후 다음 규칙을 적용하여$B_{i+1}$을 생성합니다:
  • $00 \to 0101$
  • $1 \to 10$
  • $0 \to 0$(블록 분해 시$0$은$00$이 아닌 단일$0$으로 처리됨)
• 제안된 가설: Kimberling 은 이 수열의 길이 $|B_i|$가 특정 선형 재귀 수열 $c_i$와 일치하며, 관련 수열 (A288463, A288464) 에 대한 점근적 성질에 대한 여러 가설을 세웠습니다.
• 문제점: 이 규칙은 단순한 문자열 사상 (morphism) 이 아닌 복잡한 치환을 포함하므로 분석이 어렵고, Kimberling 의 가설들은 아직 증명되지 않았습니다.

2. 방법론 (Methodology)

이 논문은 조합론적 기법과 **자동화 이론 (Automata Theory)**을 결합하여 문제를 해결했습니다.

• Walnut 증명기 (Theorem-Prover): 논리식과 유한 상태 오토마타를 사용하여 수열의 성질을 자동으로 검증하는 도구인 Walnut 을 핵심 도구로 사용했습니다.
• Tribonacci 표현 (Tribonacci Representation): 정수를 Tribonacci 수 ($T_n$) 의 합으로 표현하는 방식을 사용하여 수열 $B$를 계산하는 결정적 유한 오토마타 (DFAO) 를 구성했습니다.
• 도출 수열 (Derived Sequence) 분석: Tribonacci 단어 ($TR$) 와 수열 $B$ 사이의 관계를 규명하기 위해 'return word' (반환 단어) 개념과 도출 수열 이론을 적용했습니다.
• 이중 특수 인자 (Bispecial Factors) 분석: 수열의 복잡도와 임계 지수 (critical exponent) 를 결정하기 위해 Tribonacci 단어의 이중 특수 인자 구조를 수열 $B$에 매핑하여 분석했습니다.

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

가. Kimberling 의 가설 증명

• 길이 증명: Kimberling 이 제안한 수열 $B_i$의 길이 $|B_i|$가 재귀식 $c_i = 2c_{i-1} - c_{i-4}$를 만족함을 증명했습니다.
• 관련 수열 증명: 수열 $B$에서 $n$번째 '1'과 '0'이 나타나는 인덱스 ($I_1(n), I_0(n)$) 에 대한 Kimberling 의 가설을 증명했습니다.
  • $I_0(n) \approx \psi n$ (여기서 $\psi$는 Tribonacci 상수, $X^3 - X^2 - X - 1 = 0$의 실근).
  • $I_1(n) \approx \gamma n$ (여기서 $\gamma = (\psi^2 + 1)/2$).
  • 구체적인 오차 범위를 제시하여 ($\lfloor \psi n \rfloor - 2 \le I_0(n) \le \lfloor \psi n \rfloor + 2$ 등) 가설을 정밀하게 입증했습니다.

나. Tribonacci 단어와의 관계 규명

• 동형성 증명: 수열 $B$가 Tribonacci 단어 $TR$과 밀접한 관련이 있음을 보였습니다. 구체적으로 $B = 0f(TR)$로 표현되며, 여기서 $f$는 사상 $0 \to 10, 1 \to 0, 2 \to 1$입니다.
• 자동화 구성: Tribonacci 표현을 입력으로 받아 $B[n]$을 출력하는 DFAO 를 Walnut 코드로 구현하여, 수열 $B$가 자동 수열 (automatic sequence) 임을 보였습니다.

다. 수열의 복잡도 및 임계 지수 결정

• 인자 복잡도 (Factor Complexity): 수열 $B$의 인자 복잡도가 $p(n) = 2n$ ($n \ge 1$) 임을 증명했습니다. 이는 $B$가 Rote 단어 (Rote word) 클래스에 속함을 의미합니다.
• 임계 지수 (Critical Exponent): 수열 $B$의 임계 지수 (무한 단어 내 반복되는 부분의 최대 지수) 를 계산했습니다.
  • 결과: $ce(B) = 2 + \frac{1}{\psi - 1} \approx 3.19148788$.
  • 이는 Tribonacci 단어의 임계 지수와 동일함을 보였습니다.

라. 균형성 (Balance) 분석

• Walnut 을 사용하여 수열 $B$가 3-balanced이지만 2-balanced는 아님을 증명했습니다 (즉, 같은 길이의 두 부분열에서 '1'의 개수 차이가 최대 3 임).

4. 의의 및 중요성 (Significance)

• 방법론적 모델 제시: 단순한 문자열이 아닌 복잡한 팽창 규칙으로 정의된 수열을 분석할 때, Walnut 과 같은 자동화 증명 도구와 조합론적 기법을 어떻게 결합하여 사용할 수 있는지 보여주는 사례 연구 (primer) 역할을 합니다.
• 구체적 수열의 성질 규명: Kimberling 의 미해결 문제들을 해결하여 OEIS 에 등재된 수열들의 수학적 성질을 완전히 규명했습니다.
• 이론적 연결: Tribonacci 단어라는 잘 알려진 구조와 새로운 수열 $B$ 사이의 깊은 구조적 유사성 (Rote 단어, 동일한 임계 지수 등) 을 발견함으로써, 문자열 조합론의 이론적 지평을 넓혔습니다.

5. 결론

이 논문은 Walnut 증명기를 활용하여 Kimberling 의 가설들을 rigorously(엄밀하게) 증명하고, 수열 $B$가 Tribonacci 단어의 변형임을 규명했습니다. 또한, 이 수열이 Rote 단어 클래스에 속하며 Tribonacci 단어와 동일한 임계 지수를 가진다는 중요한 결과를 도출하여, 자동 수열 이론과 문자열 조합론 분야에서 중요한 기여를 했습니다.