The Thue-Morse Transform

이 논문은 이진 수열에 대한 '튀-모르 변환 (Thue-Morse transform)'을 도입하고, 이를 고전적인 튀-모르 수열에 반복 적용하여 프루헤 - 타리 - 에스콧 문제의 새로운 해를 도출하고, 관련 함수 방정식을 증명하며, 메르센 레벨에서의 인자 복잡도를 완전히 규명하고 $d$-진 및 피보나치 확장까지 제시합니다.

핵심

1. 핵심 아이디어: "거울과 필터" 게임

상상해 보세요. 0 과 1 로 이루어진 긴 줄이 있습니다. (예: 0, 1, 1, 0, 1, 0...)
이 줄에서 0 이 나오는 자리와 1 이 나오는 자리를 따로 떼어낸다고 가정해 봅시다.

• 0 이 나오는 자리들을 '착한 자리 (Evil numbers)'라고 부릅니다.
• 1 이 나오는 자리들을 '사악한 자리 (Odious numbers)'라고 부릅니다. (수학 용어라 생각만 하시면 됩니다.)

이제 이 두 가지 자리에 새로운 규칙을 적용합니다.

• 원래 줄의 0 이 있던 자리에, 원래 줄의 0 번째 숫자를 가져다 놓습니다.
• 원래 줄의 1 이 있던 자리에, 원래 줄의 1 번째 숫자를 반대로 (0 이면 1, 1 이면 0) 가져다 놓습니다.

이렇게 하면 새로운 0 과 1 의 줄이 만들어집니다. 이 과정을 반복하면 어떻게 될까요? 마치 거울을 계속 거울에 비추듯이, 새로운 줄이 또 새로운 줄을 만들어내는 **'수열의 탑 (Tower)'**이 세워집니다.

이 논문은 바로 이 '탑'의 각 층 (Level) 이 어떤 규칙을 따르는지를 밝혀낸 것입니다.

2. 마법의 가위 (마스크)

논문에서 가장 중요한 발견은 이 탑의 각 층이 매우 단순한 규칙으로 설명된다는 것입니다.

• 비유: 각 층은 마치 **구멍이 뚫린 마스크 (가위)**를 씌운 것과 같습니다.
• 숫자 $n$을 이진수 (0 과 1 의 조합) 로 바꿉니다. (예: 5 는 101)
• 그 층의 번호 $m$에 따라, 이진수의 특정 자리 (비트) 만을 선택하거나 제외합니다.
• 선택된 자리들의 숫자들을 더해서 (홀수면 1, 짝수면 0) 최종 숫자를 결정합니다.

즉, "어떤 층에 있느냐"에 따라 숫자의 어떤 자리를 볼지 정하는 '가이드'가 바뀐다는 뜻입니다. 이 가이드를 **마스크 (Mask)**라고 부릅니다. 이 논문의 핵심은 이 복잡한 과정을 "마스크로 비트를 선택하는 간단한 공식"으로 정리했다는 점입니다.

3. 왜 이걸까요? (수학적인 선물: PTE 문제)

이 수열을 만드는 게 단순히 재미있는 게임일까요? 아닙니다. 이 수열은 수학의 고전적인 난제인 **'푸레 - 테리 - 에스콧 (PTE) 문제'**를 해결하는 열쇠가 됩니다.

• 문제: "0 부터 N 까지의 숫자들을 두 그룹 (A 와 B) 으로 나누었을 때, 두 그룹의 숫자 합이 같고, 제곱의 합도 같고, 세제곱의 합도 같은 경우는?"
• 해결: 이 논문의 수열은 이 숫자들을 완벽하게 균형 잡힌 두 그룹으로 나눕니다. 마치 저울의 양쪽 접시에 무게가 정확히 같게 놓인 것처럼요.
• 새로운 발견: 기존의 방법으로는 해결할 수 없던 더 높은 차수 (4 제곱, 5 제곱 등) 의 문제도 이 '마스크'를 조절하면 해결할 수 있다는 것을 증명했습니다.

4. 더 깊은 이야기: 규칙의 변화

• 고전적인 경우: 가장 첫 번째 층 (원래 투 - 모르스 수열) 은 규칙이 매우 단순하고 일정했습니다.
• 새로운 발견: 두 번째 층, 세 번째 층으로 올라갈수록 규칙이 조금 더 복잡해집니다. 하지만 여전히 자동적으로 규칙을 따르는 (Automatic) 패턴이 존재합니다. 마치 로봇이 미리 정해진 프로그램대로 움직이듯이, 이 수열들도 정해진 알고리즘을 따릅니다.

5. 다른 세계로 확장하기

이 논문은 이 '마스크' 아이디어가 이진수 (2 진법) 에만 국한되지 않는다고 말합니다.

1. 다양한 진법 (d-ary): 2 진법뿐만 아니라 3 진법, 10 진법 등 어떤 진법에서도 같은 원리가 적용될 수 있음을 보여줍니다.
2. 피보나치 세계: 0 과 1 의 조합이 아닌, '피보나치 수열' (1, 1, 2, 3, 5...) 을 기반으로 한 숫자 체계에서도 비슷한 패턴이 발견될 수 있음을 시사합니다.

요약: 이 논문의 의미

이 논문은 **"0 과 1 의 줄을 반복해서 변형하면, 숨겨진 아름다운 구조와 강력한 수학 공식이 나타난다"**는 것을 증명했습니다.

• 마스크 비유: 각 층마다 다른 '구멍 뚫린 마스크'를 씌워 숫자를 선택하면, 복잡한 수열이 만들어지고, 이 수열은 숫자들의 균형을 맞추는 마법 같은 성질을 가집니다.
• 실용성: 이 원리는 암호학, 데이터 압축, 그리고 수학적 균형 문제를 푸는 데 새로운 도구가 될 수 있습니다.

결론적으로, 저자는 이 복잡한 수학적 탑을 **하나의 명확한 공식 (마스크 공식)**으로 정리하여, 앞으로 이 분야를 연구하는 사람들이 더 쉽게 접근하고 새로운 발견을 할 수 있는 길을 열어주었습니다.

기술 요약

이 논문은 Benoît Cloitre 에 의해 작성된 **"Thue–Morse Transform (Thue–Morse 변환)"**에 관한 연구로, 이진 수열 (binary sequences) 에 작용하는 새로운 연산자를 정의하고, 이를 고전적인 Thue–Morse 수열에 반복적으로 적용하여 생성되는 수열의 계층적 구조와 산술적 성질을 규명합니다.

주요 내용은 다음과 같습니다.

1. 연구 배경 및 문제 제기

• Thue–Morse 수열의 확장: 고전적인 Thue–Morse 수열 $t(n)$은 $n$의 이진 표현에서 1 의 개수의 홀짝성 (digit sum mod 2) 으로 정의됩니다. 이 수열은 Prouhet–Tarry–Escott (PTE) 문제의 해를 제공하는 등 중요한 수학적 성질을 가집니다.
• 새로운 연산자의 필요성: 기존 연구들은 주로 수열 자체의 반복 (morphisms) 에 초점을 맞췄으나, 본 논문은 **이진 수열에 작용하는 연산자 (Operator)**인 'Thue–Morse 변환 (TM-transform)'을 도입합니다.
• 핵심 질문: 고전적인 Thue–Morse 수열을 시드 (seed) 로 하여 TM-transform 을 반복적으로 적용하면 어떤 수열의 탑 (tower) 이 생성되며, 이 수열들은 어떤 산술적, 조합론적 구조를 가지는가?

2. 방법론 (Methodology)

2.1 Thue–Morse Transform 의 정의

임의의 이진 수열 $\sigma$ (0 과 1 을 무한히 포함하며 $\sigma(0)=0, \sigma(1)=1$) 가 주어졌을 때, 다음과 같이 정의됩니다:

• Evil numbers ($v_\sigma$): $\sigma(n)=0$인 위치 $n$들의 증가 수열.
• Odious numbers ($u_\sigma$): $\sigma(n)=1$인 위치 $n$들의 증가 수열.
• 변환 $\tau = T(\sigma)$: 다음 조건을 만족하는 유일한 이진 수열입니다.
  • $\tau(v_\sigma(n)) = \tau(n)$
  • $\tau(u_\sigma(n)) = 1 - \tau(n)$
  • $\tau(0) = 0$

이 변환은 수열의 0 과 1 의 위치를 이용해 새로운 수열을 재구성하는 과정입니다.

2.2 반복 탑 (Iterated Tower) 의 구성

고전적인 Thue–Morse 수열 $a_0 = t$를 시작점으로 하여 $a_{m+1} = T(a_m)$으로 정의된 수열의 탑을 연구합니다.

2.3 명시적 공식 유도 (Bit-mask Formula)

수열 $a_m(n)$이 단순한 재귀가 아니라 **이진 비트 마스크 (bit-mask)**를 통해 명시적으로 표현될 수 있음을 증명합니다.

• $n$의 이진 표현을 $n = \sum b_p(n) 2^p$라 할 때,
• $a_m(n) = \bigoplus_{p \ge 0, p \& m = 0} b_p(n)$
  • 여기서 $\oplus$는 XOR(모듈로 2 덧셈), $\&$는 비트 AND 연산입니다.
  • 즉, $m$의 이진 표현에서 1 이 아닌 비트 위치들 ($p \& m = 0$) 에 해당하는 $n$의 비트들을 XOR 합한 값이 $a_m(n)$이 됩니다.

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

3.1 Prouhet–Tarry–Escott (PTE) 문제의 새로운 해법

• 결과: 각 레벨 $m$의 수열 $a_m$은 자연수 구간에서 PTE 문제의 해를 제공합니다.
• 기여: 고전적인 Prouhet 구성 (레벨 0) 을 일반화합니다. 수열 $a_m$이 정의하는 0 과 1 의 집합은 특정 구간에서 $k$차까지의 거듭제곱 합이 같습니다 ($k < s_m L - 1$).
• 특징: 여기서 $s_m$은 주기 내 선택된 비트 위치의 개수이며, $L$은 구간의 길이와 관련됩니다. 마스크 $m$을 조절함으로써 PTE 문제의 차수 (degree) 를 정밀하게 제어할 수 있습니다.

3.2 일반화된 Evil/Odious 수와 함수 방정식

• 결과: 각 레벨 $m$에 대한 일반화된 evil 수 ($v_m$) 와 odious 수 ($u_m$) 에 대한 합성 공식 (composition formulas) 을 유도했습니다.
• 기여: 고전적인 경우 (Allouche et al.) 에서는 합성 시 보정항 (correction term) 이 상수였으나, 반복된 레벨에서는 보정항이 **자동 수열 (automatic sequence)**이 됩니다.
  • 예: $u_m(u_m(n)) = 2u_m(n) + 1 - c_m(n)$ (여기서 $c_m(n)$은 자동 수열).
• 의의: 변환의 반복이 생성하는 산술적 그림자 (arithmetic shadow) 가 시드 (seed) 경우보다 훨씬 풍부하고 복잡한 구조를 가짐을 보여줍니다.

3.3 인자 복잡도 (Factor Complexity) 분석

• 결과: 특히 $m = 2^k - 1$인 메르센 (Mersenne) 레벨에 대해 인자 복잡도 $p_{a_m}(n)$을 완전히 규명했습니다.
• 기여:
  • 초기 구간 ($n \le B+1$) 에서 선형 성장 ($2n$) 을 보입니다.
  • 파생 수열 (derived sequence) 을 이용한 desubstitution 기법을 통해 구간별 조각 함수 (piecewise formula) 를 유도했습니다.
  • 메르센 레벨이 아닌 경우의 복잡도도 관찰되었으나, 완전한 폐쇄형 공식은 미해결 과제로 남았습니다.

3.4 확장성 (Extensions)

• d-ary 일반화: 2 진법 (base 2) 에서 $d$진법 (base $d$) 으로 PTE 구성을 확장했습니다.
• 다른 시드 (Seeds):
  • Meta-Thue–Morse 수열 ($M_2$): Campbell 과 Cloitre 의 이전 연구에서 정의된 수열도 동일한 PTE 팩터화 구조를 가짐을 보였습니다.
  • Fibonacci Analogue: Zeckendorf 표기법 (피보나치 수열 기반) 을 사용한 Fibonacci–Thue–Morse 수열에 변환을 적용했으나, 이진법과 달리 비트가 독립적이지 않아 완전한 팩터화가 어렵고 복잡도가 높게 나타남을 논의했습니다.

4. 의의 및 중요성 (Significance)

1. 이론적 통합: Thue–Morse 수열의 반복적 구조를 단순한 수열의 나열이 아닌, 명시적인 비트 마스크 공식으로 통합하여 설명했습니다. 이는 수열의 구조를 이해하는 데 강력한 도구를 제공합니다.
2. PTE 문제의 확장: Prouhet 의 고전적인 구성을 넘어, 마스크 파라미터를 통해 PTE 해의 차수와 클래스 수를 유연하게 조절할 수 있는 새로운 무한한 해의 가족을 제시했습니다.
3. 자동 수열 이론의 심화: 일반화된 evil/odious 수의 합성 법칙에서 보정항이 상수가 아닌 자동 수열로 변한다는 점은 자동 수열 이론과 산수적 동역학 (arithmetic dynamics) 의 연결 고리를 강화합니다.
4. 복잡도 분석의 정밀화: 메르센 레벨에 대한 정확한 인자 복잡도 공식은 조합론적 수열 이론에 중요한 기여를 하며, 비메르센 레벨과 Fibonacci 유사체에 대한 연구 방향을 제시합니다.

요약

이 논문은 Thue–Morse 수열을 기반으로 한 새로운 변환 연산자를 정의하고, 이를 반복 적용하여 생성되는 수열의 탑이 명시적인 비트 마스크 공식을 가지며, PTE 문제의 고차 해를 제공하고, 복잡한 자동 수열적 성질을 가진다는 것을 증명했습니다. 이는 고전적인 Thue–Morse 이론을 현대적인 조합론 및 수론의 관점에서 심화하고 확장한 중요한 연구입니다.