Rationality and computability of the covering radius for sofic shifts

논문 요약: SOFIC SHIFTS 에 대한 커버링 반지름의 유리수성과 계산 가능성
(RATIONALITY AND COMPUTABILITY OF THE COVERING RADIUS FOR SOFIC SHIFTS)

저자: Tom Meyerovitch, Aidan Young
주제: 정보 이론, 동적 시스템 (Symbolic Dynamics), 게임 이론, 알고리즘

---

1. 연구 배경 및 문제 제기 (Problem)

• 커버링 반지름 (Covering Radius): 유한한 코드 $C$의 커버링 반지름은 모든 가능한 시퀀스에 대해 코드 내의 어떤 원소와 최대 $R$개의 좌표 차이만 나게 하는 최소 거리 $R$을 의미합니다. 이는 잡음 채널을 통한 데이터 전송에서 오류 정정 능력과 밀접한 관련이 있습니다.
• 시프트 공간 (Shift Space) 으로 확장: 무한한 시퀀스 공간인 시프트 공간 $S$에 대해 커버링 반지름을 정의할 수 있습니다. 이는 길이 $n$인 허용 가능한 단어들의 집합 $C_n(S)$에 대한 커버링 반지름 $R(C_n(S))$을 $n$으로 나눈 값의 극한 ($n \to \infty$) 으로 정의됩니다.
• 연구 질문:
  1. 소픽 시프트 (Sofic shift) 의 커버링 반지름은 항상 **유리수 (Rational number)**인가?
  2. 소픽 시프트의 커버링 반지름을 계산하는 일반적인 알고리즘이 존재하는가?
  • 기존 연구 [3] 에서는 특정 예시 (Run length-limited shifts 등) 에 대해 커버링 반지름이 유리수임을 확인했으나, 일반적인 소픽 시프트에 대한 증명은 부재했습니다.

2. 방법론 (Methodology)

저자들은 이 문제를 해결하기 위해 두 명의 플레이어 (Alice 와 Bob) 가 참여하는 제로섬 게임 (Zero-sum game) 프레임워크를 도입했습니다.

• 비대칭 평균 보상 게임 (Non-alternating Mean Payoff Game):
  • 게임 규칙: Alice 는 그래프 $H$에서 길이 $n$의 보행 (walk) $p$를 선택하고, Bob 은 이를 관찰한 후 그래프 $G$에서 길이 $n$의 보행 $q$를 선택합니다. Bob 은 Alice 에게 $\sum P(q_i, p_i)$만큼의 보상을 지급합니다.
  • 목표: Alice 는 보상을 최대화하려 하고, Bob 은 이를 최소화하려 합니다. 게임의 값 $V(G, H, P)$는 $n \to \infty$일 때 평균 보상 $\frac{1}{n} \sum P(q_i, p_i)$의 극한값입니다.
• 열대 합성곱 (Tropical Convolution):
  • 정수 값 함수 공간에서 정의된 연산 $(f * g)(u, w) = \min_v (f(u, v) + g(v, w))$을 사용하여 보행의 연결 (concatenation) 과 최적 전략의 성질을 분석했습니다. 이는 기존 합성곱을 $(\min, +)$ 연산으로 대체한 열대 기하학 (Tropical geometry) 의 개념입니다.
• 최적 전략 공간 (Space of Optimal Strategies):
  • 게임의 균형 전략 (Nash equilibrium) 을 따르는 보행들의 집합을 정의하고, 이 집합이 생성하는 시프트 공간이 **소픽 시프트 (Sofic shift)**임을 증명했습니다.

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

이 논문은 다음과 같은 두 가지 주요 정리를 증명했습니다.

정리 A (유리수성):

• 내용: 기본 (primitive) 소픽 시프트 $X_G$의 커버링 반지름 $R(X_G)$은 항상 유리수입니다.
• 증명 논리: 커버링 반지름 문제를 특정 그래프 $G$와 $H$, 그리고 보상 함수 $P$를 가진 게임의 값 $V(G, H, P)$로 변환합니다. $V(G, H, P)$가 유리수임을 증명함으로써 정리 A 를 유도합니다.

정리 B (계산 가능성):

• 내용: 기본 라벨링 그래프 $G$를 입력으로 받아 커버링 반지름 $R(X_G)$을 유한 시간 내에 계산하는 알고리즘이 존재합니다.
• 알고리즘 원리:
  1. 게임 값 $V(G, H, P)$를 계산하기 위해 "비개선 가능 보행 (non-improvable walks)"의 집합을 추적합니다.
  2. 열대 합성곱과 함수의 최대/최소 값을 분석하여, 일정 길이 $N$ 이후에는 최적 전략 집합이 주기적인 패턴을 보임을 증명합니다 (Lemma 4.8).
  3. 이 주기성을 이용하여 유한한 단계 내에서 게임의 값 (즉, 커버링 반지름) 을 정확히 계산할 수 있습니다.

추가 결과 (Theorem F 및 Corollary 5.4):

• 소픽성 증명: 게임의 최적 전략으로 정의된 시프트 공간 $X^\dagger_H$와 $Y^\dagger_{(H,G)}$가 소픽 시프트임을 증명했습니다.
• 주기적 전략의 존재: 모든 기본 그래프에 대해, 게임의 균형 값에 도달하는 주기적 (periodic) 보행이 항상 존재함을 보였습니다. 즉, 최적 전략은 무한히 복잡하지 않고 주기적인 패턴으로 구현 가능합니다.

4. 의의 및 의의 (Significance)

1. 이론적 해결: 소픽 시프트의 커버링 반지름이 항상 유리수이며 계산 가능하다는 것을 증명함으로써, 정보 이론과 동적 시스템의 교차 영역에서 중요한 미해결 문제를 해결했습니다.
2. 알고리즘적 실용성: 커버링 반지름을 단순히 추정하는 것을 넘어, 주어진 소픽 시프트에 대해 정확한 값을 계산하는 구체적인 알고리즘을 제시했습니다. 이는 실제 데이터 저장 및 전송 시스템의 오류 정정 능력 분석에 직접적으로 활용될 수 있습니다.
3. 게임 이론과 동적 시스템의 융합: 제로섬 게임 (Mean Payoff Games) 의 이론을 시프트 공간의 기하학적 성질 (커버링 반지름) 을 분석하는 데 성공적으로 적용했습니다. 특히, 게임의 최적 전략 공간이 소픽 시프트라는 사실은 게임 이론적 접근이 동적 시스템의 구조를 이해하는 강력한 도구가 됨을 보여줍니다.
4. 열대 기하학의 적용: 열대 합성곱 (Tropical convolution) 을 사용하여 그래프 보행의 최적화 문제를 체계적으로 다룸으로써, 향후 유사한 조합론적 문제 해결에 새로운 도구를 제공했습니다.

5. 결론 및 향후 과제

• 한계: 현재 연구는 기본 (primitive) 그래프에 국한되어 있습니다. 비기본 (reducible) 그래프의 경우 정리 D 와 같은 일부 명제가 성립하지 않을 수 있습니다.
• 향후 연구 방향:
  • 기본성 가정을 제거하고 일반적인 그래프에 대한 정리 A 와 B 의 확장.
  • 보상 함수 $P$가 실수 (Real number) 값을 가질 때의 계산 가능성 및 유리수성 여부 (현재는 유리수 또는 대수적 수에 국한됨).
  • 더 일반적인 보상 함수 (예: $Q(\sqrt{2})$) 에 대한 정확한 값 계산 알고리즘의 존재 여부.

요약하자면, 이 논문은 소픽 시프트의 커버링 반지름이 계산 가능한 유리수임을 증명하고, 이를 게임 이론과 열대 합성곱을 통해 체계적으로 분석한 획기적인 연구입니다.