On modulo-recurrence and window complexity in infinite words

이 논문은 슈투름(Sturmian) 단어와 최대 복잡도 단어를 분석하기 위해 균등 및 강 모듈로-재귀(uniform and strong modulo-recurrence) 개념을 도입하고, 튜 머스(Thue-Morse) 단어에 대한 윈도우 복잡도와 고전적 복잡도 사이의 새로운 관계를 확립하며, 특정 유계 또는 아선형 윈도우 복잡도 거동을 보이는 비주기적 재귀 단어를 구성하는 동시에 그러한 복잡도가 균등 재귀적 비주기 단어에 대해서는 반드시 유계가 아님을 증명한다.

핵심

무한히 이어지는 구슬 줄을 상상해 보세요. 각 구슬은 작은 알파벳(예: A, B, 또는 C)의 글자를 나타냅니다. 이 줄은 끝나지 않습니다. 수학자들은 이를 "무한 단어(infinite word)"라고 부릅니다. 당신이 묻고 있는 이 논문은 이러한 문자열이 어떻게 행동하는지를 연구하며, 특히 두 가지 측면, 즉 패턴이 얼마나 자주 반복되는가와 특정 길이에서 얼마나 많은 서로 다른 패턴이 존재하는가를 살펴봅니다.

이 논문의 아이디어를 쉬운 비유를 사용하여 정리해 드립니다.

1. 두 명의 주인공: 재귀성과 복잡성

이 논문을 이해하려면 저자들이 조사하고 있는 두 가지 핵심 개념을 알아야 합니다.

• 재귀성 (Recurrence, "다시 나타남"): 아주 긴 영화를 보고 있다고 상상해 보세요. 만약 특정 장면(이것을 "인자(factor)" 또는 "단어(word)"라고 합니다)이 등장했다면, 그 장면이 다시 나타날까요?
  • 재귀적(Recurrent): 네, 모든 장면은 무한히 많은 횟수로 다시 나타납니다.
  • 균등 재귀적(Uniformly Recurrent): 단순히 다시 나타나는 것을 넘어, 규칙적으로 나타납니다. 특정 장면을 다시 보기 위해 너무 오래 기다릴 필요가 없습니다. 특정 시간 내에 반드시 다시 나타난다는 것이 보장됩니다.
• 복잡성 (Complexity, "다양성 측정"): 만약 당신이 5초마다 스냅샷을 찍는다면, 얼마나 많은 서로 다른 5초짜리 클립들을 보게 될까요?
  • 낮은 복잡성: 매우 적은 수의 고유한 클립을 보게 됩니다 (아마도 영화가 똑같은 루프를 반복하고 있을 것입니다).
  • 높ity 높은 복잡성: 매우 다양한 종류의 고유한 클립들을 보게 됩니다.
  • 윈도우 복잡성 (Window Complexity): 이것이 이 논문의 특별한 변주입니다. 모든 가능한 5초짜리 클립을 보는 대신, 특정 "윈도우(창)" 위치(예: 0초, 5초, 10초, 15초 등에서 시작하는 클립만)에서만 클립을 본다고 상상해 보세요. "윈도우 복잡성"은 오직 그 특정 윈도우들 안에서 발견되는 고유한 클립의 개수를 셉니다.

2. 새로운 개념: 모듈로-재귀성 (Modulo-Recurrence)

저자들은 모듈로-재귀성이라는 멋진 용어를 도입합니다.

• 비유: $k$개의 시간이 있는 시계를 상상해 보세요. 어떤 단어가 "모듈로-재귀적"이라는 것은, 그 문자열에서 찾을 수 있는 모든 패턴이 시계의 모든 가능한 시간에 나타난다는 것을 의미합니다.
  • 만약 어떤 패턴이 1시에 나타난다면, 그것은 반드시 2시, 3시, 그리고 그 이후의 시간에도 나타나야 합니다.
  • 이것은 마치 이렇게 말하는 것과 같습니다: "당신이 어느 시간에 확인하더라도, 그 특정 패턴을 발견할 수 있습니다."

또한, 그들은 **강한 모듈로-재귀성(Strong Modulo-Recurrence)**을 정의합니다. 이는 훨씬 더 강력한 버전입니다. 이는 특정 "변환"(글자를 바꾸는 규칙, 예를 들어 모든 'A'를 'AA'로, 모든 'B'를 'B'로 바꾸는 것)을 적용하더라도, 해당 변환이 특정 수학적 규칙을 따른다면, 패턴이 여전히 이 "모든 시간에 나타나는" 성질을 유지함을 의미합니다.

그들이 발견한 것:

• 슈투르미안 단어 (Sturmian Words): 이들은 매우 구조화된 특수한 무한 문자열입니다 (마치 완벽한 리듬과 같습니다). 저자들은 이들이 "강한 모듈로-재귀적"임을 증명했습니다. 이들은 매우 잘 정돈되어 있습니다.
• 최대 복잡성 단어 (Maximal Complexity Words): 이들은 가능한 모든 글자의 조합을 포함하는 문자열입니다 (혼란스럽지만 완전합니다). 이들 역시 "강한 모듈로-재귀적"입니다.

3. 튀에-모스 단어 (Thue-Morse Word, 유명한 사례)

튀에-모스 단어는 유명한 수학적 수열입니다 (마치 모두가 아는 유명한 노래와 같습니다). 이는 간단한 규칙에 의해 생성됩니다: 'A'로 시작하여, A를 'AB'로, B를 'BA'로 바꾸는 과정을 반복합니다.

저자들은 이 유명한 단어의 윈도우 복잡성을 조사했습니다.

• 발견: 그들은 얼마나 많은 고유한 "윈도우" 패턴이 존재하는지에 대한 정확한 공식을 찾아냈습니다.
• 결과: 윈도우 크기가 홀수라면, 윈도우 복잡성은 전체 복잡성과 정확히 같습니다 (모든 것을 보게 됩니다). 만약 윈도우 크기가 짝수라면, 윈도우 복잡성은 더 낮아집니다 (윈도우가 패턴들을 건너뛰기 때문에 일부 패턴을 놓치게 됩니다).

4. 해결된 주요 질문들

이 논문은 이러한 무한 문자열에 관한 세 가지 구체적인 질문을 다룹니다.

질문 A: 어떤 문자열이 "재귀적"(패턴이 반복됨)이면서 동시에 "유계된 윈도우 복잡성"(윈도우가 항상 작고 고정된 수의 패턴만을 보여줌)을 가질 수 있는가?

• 논문의 답변: 예.
• 비유: 저자들은 맞춤 제작된 무한 문자열을 만들었습니다. 그것은 계속 루프를 도는 테이프와 같지만, 그들이 사용하는 "윈도우"는 매우 넓게 떨어져 있어서, 테이프가 아무리 길어져도 항상 3개 또는 4개의 서로 다른 패턴만을 보게 됩니다. 이는 어떤 문자열이 윈도우 관점에서는 복잡하지 않더라도 재귀적일 수 있음을 증명합니다.

질문 B: 윈도우 복잡성이 증가하되, 매우 느리게(예: 제곱근이나 세제곱근처럼) 증가하는 문자열을 만들 수 있는가?

• 논문의 답변: 예.
• 비유: 그들은 윈도우 패턴의 수가 증가하지만, 매우 느리게 증가하는(문자열의 길이보다 훨씬 느리게) 일련의 문자열들을 만들어냈습니다. 이는 정원은 점점 커지지만, 특정 관찰 지점에서 보이는 새로운 꽃의 종류는 아주 서서히 늘어나는 것과 같습니다.

질문 C: 만약 어떤 문자열이 "균등 재귀적"(매우 규칙적임)이면서 "비주기적"(절대 진정한 반복 루프를 형성하지 않음)이라면 어떻게 되는가?

• 논문의 답변: 윈도우 복잡성은 반드시 유계되지 않아야(unbounded) 합니다.
• 비유: 만약 문자열이 완벽하게 규칙적이라면 (패턴을 다시 보기 위해 오래 기다릴 필요가 없지만), 동시에 단순한 반복 루프에 빠지지 않는다면 (비주기적), 당신의 "윈도우"에서 보이는 패턴의 종류는 반드시 영원히 계속 증가해야 합니다. 당신은 완벽하게 규칙적이면서도 결코 루프를 돌지 않으면서, 동시에 고정된 적은 수의 윈도우 패턴만을 보여주는 문자열을 가질 수 없습니다. 윈도우의 "다양성"은 결국 폭발적으로 늘어날 것입니다.

요약

이 논문은 무한한 글자 문자열에 관한 탐정 소설과 같습니다.

1. 그것은 특정 간격으로 패턴이 나타나는 방식(모듈로-재귀성)을 정의합니다.
2. 잘 정돈된 유명한 문자열(슈투르미안)과 혼란스러운 문자열(최대 복잡성) 모두가 이 특별한 성질을 가지고 있음을 증명합니다.
3. 재귀적이지만 윈도우 관점에서는 매우 낮은 고정된 다양성을 가진 "트릭" 문자열을 구축합니다.
4. 마지막으로, 엄격한 규칙을 증명합니다: 만약 문자열이 완벽하게 규칙적이지만 반복되지 않는다면, 그 윈도우의 다양성은 반드시 무한히 증가해야 합니다. 두 마리 토끼를 다 잡을 수는 없습니다. 즉, 완벽하게 규칙적이면서 비주기적이면서 동시에 제한된 윈도우 패턴만을 가질 수는 없습니다.

기술 요약

기술 요약: 무한 단어의 모듈로-재귀성 및 윈도우 복잡도에 관하여

문제 정의
본 논문은 무한 단어의 구조적 특성, 특히 재귀적 성질과 복잡도 함수 사이의 상호작용을 중점적으로 조사한다. 고전적인 부분 단어 복잡도($P(n)$)가 단어의 길이 $n$인 서로 다른 인자(factor)의 개수를 세는 잘 확립된 도구라면, 저자들은 새로운 개념인 윈도우 복잡도($P^w(n)$)를 검토한다. 윈도우 복잡도는 위치가 $n$의 배수인 위치에서 나타나는 길이 $n$인 서로 다른 인자($n$-윈도우 인자)의 개수를 센다.

이 논문이 다루는 핵심 문제는 모듈로-재귀성(모든 인자가 임의의 $k$에 대한 모든 모듈로 위치에서 나타나는 성질)과 윈도우 복잡도의 거동에 기초하여 무한 단어를 특징짓는 것이다. 구체적으로, 저자들은 다음을 목표로 한다:

1. 균등 모듈로-재귀성(uniformly modulo-recurrent) 및 강한 모듈로-재귀성(strongly modulo-recurrent) 변형을 도입하여 모듈로-재귀성의 개념을 정교화한다.
2. 특정 클래스의 단어(슈투르미안, 튜에-모스)에 대해 윈도우 복잡도와 고전적 복잡도 사이의 관계를 결정한다.
3. 유계인 윈도우 복잡도를 갖는 비주기적 재귀 단어의 존재 여부에 관한 열린 문제를 해결한다.
4. 재귀 단어 군(families)에 대한 윈도우 복잡도의 경계값을 설정하고, 균등 재귀적인 비주기적 단어는 반드시 무한한 윈도우 복잡도를 가짐을 증명한다.

방법론
저자들은 재귀, 모피즘(morphism), 인자 집합의 정의를 활용하여 단어에 대한 조합론적 방법을 사용한다. 방법론은 다음과 같다:

• 정의 및 특징 규명: 균등 모듈로-재귀적 및 강한 모듈로-재귀적 단어에 대한 공식적인 정의를 도입한다.
• 모피즘 분석: 슈투르미안 모피즘의 성질과 유클리드 알고리즘(라우지 쌍 구성을 통한)을 사용하여, 서로소인 글자 길이를 가진 모피즘 하에서 재귀적 성질이 어떻게 보존되는지 분석한다.
• 구성적 예시: 특정 복잡도 거동을 보여주기 위해 정수 수열과 재귀적 연결을 사용하여 무한 단어를 명시적으로 구성한다.
• 정수론적 논증: 구성된 단어 내 인자의 분포를 분석하기 위해 서로소 정수의 성질(프로베니우스 동전 문제의 함의) 및 베르트랑-체비쇼프 정리와 같은 결과들을 적용한다.
• 비둘기집 및 주기성 논증: 주기성 조건을 도출하기 위해 세 인자의 튜플(triple)에 대한 계산법을 사용한다.

주요 기여 및 결과

1. 정교화된 재귀 개념:

   • 본 논문은 균등 모듈로-재귀적 단어(모듈로-재귀성의 균등 버전)와 강한 모듈로-재귀적 단어(글자 길이가 서로소인 모피즘 하에서도 모듈로-재귀성이 보존되는 단어)를 도입한다.
   • 슈투르미안 단어와 최대 복잡도 단어(참퍼노 운스 단어)는 강한 모듈로-재귀적임을 증명한다.
   • 차이점이 존재한다: 슈투르미안 단어는 강한 모듈로-재귀적이지만, 튜에-모스 단어는 균등 재귀적이지만 모듈로-재귀적이지는 않다.

2. 튜에-모스 단어의 윈도우 복잡도:

   • 튜에-모스 단어 $t$에 대하여 윈도우 복잡도 $P^w(n)$와 고전적 복잡도 $P(n)$ 사이의 정확한 관계를 확립한다.
   • 결과는 다음과 같이 주어진다: $P^w(n) = P\left(\frac{n}{2^{\nu_2(n)}}\right)$, 여기서 $\nu_2(n)$은 2-아딕 밸류에이션(2-adic valuation)이다.
   • 결과적으로, $n$이 홀수일 때만 $P^w(n) = P(n)$이다.

3. 비주기적 단어에서의 유계 윈도우 복잡도:

   • 저자들은 급격히 성장하는 정수 수열 $(k_n)$ (단, $k_{n+1} = (2k_n)!$)을 사용하여 유계 윈도우 복잡도를 갖는 재귀적, 비주기적 단어를 구성함으로써 기존 문헌[10]에서 제기된 질문에 답한다.
   • 이 특정 단어 $u$에 대해, 모든 $n$에 대하여 $P^w(n) \leq 4$임이 증명되는 반면, $P(n) \geq n+1$이다. 이는 모든 $n \geq 2$에 대해 $P^w(n) < P(n)$인 단어가 존재함을 확인해 준다.

4. 다항식 윈도우 복잡도를 갖는 군(Families):

   • 윈도우 복잡도 $P^w(n)$가 $P^w(n) = O(n^\alpha)$ (단, $0 < \alpha < 1$)를 만족하는 비주기적 재귀 단어 군을 구성한다.
   • 또한, 이 군에 대해 무수히 많은 $n$에 대하여 $P^w(n) \geq n^\alpha$가 성립한다. 이는 특정 비주기적 재귀 단어들에 대해 윈도우 복잡도가 다항식적으로 성장할 수 있지만, 선형 성장보다는 엄격히 느릴 수 있음을 보여준다.

5. 균등 재귀적 비주기적 단어의 무한성:

   • 본 논문은 근본적인 한계를 설정한다: 만약 균등 재귀적 단어 $u$가 유계 윈도우 복잡도를 갖는다면(구체적으로, $\liminf P^w(n)P^w(n+1) < \infty$라면), $u$는 반드시 주기적이어야 한다.
   • 따져보기(Corollary): 모든 균등 재귀적 비주기적 단어의 윈도우 복잡도는 무한하다. 이는 점 3의 결과, 즉 유계 윈도우 복잡도를 갖는 구성된 단어가 재귀적이지만 균등 재귀적이지는 않다는 결과와 대조된다.

의의
본 논문은 재귀적 성질을 특정 모듈로 위치에서의 인자 분포와 연결함으로써 무한 단어의 구조적 제약에 대한 더 깊은 이해를 제공한다. "강한 모듈로-재귀성"의 도입은 모피즘 변환 하에서 단어를 분석하기 위한 견고한 프레임워크를 제공한다. 유계 윈도우 복잡도를 갖는 비주기적 재귀 단어를 구성한 것은 기존의 열린 문제를 해결하며, 윈도우 복잡도가 일반적인 재귀 단어에 대해 고전적인 부분 단어 복잡도보다 엄격히 약한 척도임을 입증한다. 그러나 최종 결과는 균등 재귀적 비주기적 단어라는 더 엄격한 클래스의 경우, 윈도우 복잡도가 유계로 남을 수 없음을 명확히 함으로써, 균등 재귀성과 복잡도 함수의 성장 사이의 긴밀한 연결을 강화한다.