The Conjugacy Relation on One-sided Subshifts is Non-treeable

이 논문은 기술적 집합론의 관점에서 한쪽 방향 서브시프트의 켤레 관계를 연구하여, 알파벳 집합이 $\{0,1\}$인 경우 해당 관계가 비-트리형 (non-treeable) 이고 비-아멘 (non-amenable) 임을 증명합니다.

핵심

이 논문은 수학적 세계의 **'동역학 시스템'**이라는 복잡한 개념을 연구한 것입니다. 조금 더 쉽게 말하면, **"규칙에 따라 변하는 패턴들의 세계"**를 다루고 있죠.

저자 이루원 (Ruiwen Li) 은 이 패턴들이 서로 얼마나 '비슷한지' 또는 '다른지'를 분류하는 것이 얼마나 어려운 일인지, 그리고 그 분류 체계가 얼마나 복잡한 구조를 가지고 있는지를 증명했습니다.

이 복잡한 수학적 내용을 일상적인 비유로 풀어보겠습니다.

---

1. 배경: 거대한 패턴 도서관

상상해 보세요. 무한히 긴 줄무늬가 있는 천들이 무수히 많이 있다고 칩시다. 이 천들은 '0'과 '1'이라는 두 가지 색으로만 이루어져 있고, 규칙에 따라 왼쪽으로 계속 미끄러져 나갑니다 (이를 **시프트 (Shift)**라고 합니다).

이 천들 중에는 어떤 규칙을 따르는 것들도 있고, 어떤 것은 전혀 규칙이 없는 것처럼 보이는 것들도 있습니다. 수학자들은 이 천들 (시스템) 들을 **'동역학 시스템'**이라고 부릅니다.

이제 중요한 질문이 생깁니다:

"이 두 개의 천이 본질적으로 같은 것일까, 아니면 다른 것일까?"

만약 한 천을 잘게 잘라 다시 붙이거나, 색을 바꾸는 등의 작업 (수학적으로는 '공액, Conjugacy') 을 통해 다른 천으로 완벽하게 변형시킬 수 있다면, 우리는 이 두 천이 **'동일한 시스템'**이라고 말합니다.

2. 문제: 분류의 난이도

수학자들은 이 '동일한가?'라는 질문을 답하는 방법 (분류법) 의 난이도를 연구합니다.

• 쉬운 분류: 만약 두 천이 같은지 말하기 위해 단순히 '첫 번째 색'만 보면 된다면 아주 쉽습니다.
• 어려운 분류: 만약 두 천이 같은지 알려면 천의 끝까지 모두 비교해야 하거나, 아주 복잡한 계산이 필요하다면 매우 어렵습니다.

이 논문은 **한쪽 방향 (오른쪽) 으로만 흐르는 패턴들 (One-sided Subshifts)**에 대해 연구했습니다. 마치 한 방향으로만 흐르는 강물처럼, 과거는 알 수 없고 미래만 계속 이어지는 시스템입니다.

3. 핵심 발견: "나무"로 정리할 수 없는 혼란

논문은 이 패턴들을 분류하는 관계가 "나무 (Tree)" 구조로 정리될 수 없다고 증명했습니다.

비유로 설명하자면:

• 나무 구조 (Treeable): 가족 관계도나 회사 조직도처럼, "누가 누구의 부모인가?"를 따라가면 누구나 한 가지 명확한 가계도로 정리될 수 있는 상태입니다. 이는 비교적 단순하고 정리하기 쉬운 구조입니다.
• 나무가 아닌 구조 (Non-treeable): 마치 거미줄이나 복잡한 지하철 노선도처럼, 한 지점에서 출발하면 여러 갈래로 뻗어 나가고, 다시 합쳐지기도 하며, 순환하기도 하는 복잡한 구조입니다.

이 논문은 **"한쪽 방향 패턴들의 분류 체계는 거미줄처럼 복잡하게 얽혀 있어서, 단순한 나무 구조 (가계도) 로 정리할 수 없다"**고 결론 내렸습니다.

또한, 이 구조는 **'아멘 (Amenable)'**하지 않다고 했습니다.

• 아멘한 구조: 공평하게 나누어 먹을 수 있는 케이크처럼, 균형을 잡기 쉬운 상태.
• 비아멘한 구조: 균형을 잡을 수 없거나, 예측 불가능하게 뒤죽박죽인 상태.

즉, 이 패턴들의 세계는 정리할 수도 없고, 균형을 잡을 수도 없는 매우 혼란스럽고 복잡한 세계라는 뜻입니다.

4. 연구 방법: 레고 블록으로 만든 미로

저자는 이 복잡한 성질을 증명하기 위해 다음과 같은 방법을 썼습니다.

1. 가상의 세계 건설: '0'과 '1'뿐만 아니라 특수한 기호들을 섞어 복잡한 규칙 (금지된 단어) 을 가진 가상의 패턴 세계를 만들었습니다.
2. 변환 도구 개발: 이 가상의 세계를 뒤집거나 바꾸는 '변환기 (Automorphism)'들을 만들었습니다. 이 변환기들은 마치 레고 블록을 조립하고 해체하는 도구처럼 작동합니다.
3. 복잡성 증명: 이 변환기들을 조합하면, 단순한 나무 구조로는 설명할 수 없는 아주 복잡한 '미로'가 만들어짐을 보였습니다.
4. 실제 세계로 연결: 이 가상의 복잡한 미로가, 우리가 알고 있는 '0'과 '1'로만 이루어진 실제 한쪽 방향 패턴들 (One-sided subshifts) 에도 그대로 적용됨을 증명했습니다.

5. 요약 및 의미

이 논문의 핵심 메시지는 다음과 같습니다.

"우리가 생각했던 것보다, 한쪽 방향으로만 흐르는 패턴들의 세계는 훨씬 더 복잡하고 예측 불가능하다. 이 세계의 패턴들을 '같은 것'과 '다른 것'으로 나누는 일은, 단순한 가계도 (나무) 로 정리할 수 없을 정도로 엉켜있고, 균형을 잡을 수 없는 (비아멘한) 혼란스러운 상태이다."

이는 수학자들이 오랫동안 궁금해하던 **"이런 패턴들을 분류하는 것이 정말로 어려운가?"**라는 질문에 **"네, 매우 어렵고 그 복잡성은 나무 구조를 벗어난 수준이다"**라고 답한 것입니다.

한 줄 요약:

한쪽 방향으로 흐르는 무한한 패턴들을 분류하는 일은, 단순한 가계도로 정리할 수 없는 복잡한 미로와 같으며, 이는 수학적으로 매우 높은 난이도의 문제임을 증명했다.

기술 요약

논문 요약: 한쪽 방향 서브시프트 (One-sided Subshifts) 의 켤레 관계의 비-트리어빌리티

1. 연구 배경 및 문제 제기

• 배경: 기술적 집합론 (Descriptive Set Theory) 은 표준 보렐 공간 (Standard Borel spaces) 상의 동치 관계의 복잡성을 비교하는 틀을 제공합니다. 동치 관계 $E$가 $F$로 보렐 환원 (Borel reducible) 가능하면 ($E \le_B F$), $F$가 더 복잡하다고 간주합니다.
• 주요 대상: 동적 시스템 (Dynamical systems) 의 켤레 (Conjugacy) 관계. 특히, **한쪽 방향 서브시프트 (One-sided subshifts)**의 켤레 관계에 초점을 맞춥니다.
• 기존 연구:
  • 양방향 서브시프트 (Two-sided subshifts) 의 켤레 관계는 Curtis-Hedlund-Lyndon 정리에 의해 가산 (countable) 보렐 동치 관계임이 알려져 있으며, Clemens [5] 에 의해 보편적 가산 보렐 동치 관계 $E_\infty$와 보렐 바이리덕터블 (Borel bireducible) 임이 증명되었습니다.
  • 그러나 한쪽 방향 서브시프트의 켤레 관계의 정확한 복잡성은 오랫동안 미해결 문제였습니다. Clemens [5] 는 이 문제를 명시적으로 제기했습니다 (Question 1.1).
• 문제: 알파벳 집합 $\{0, 1\}$을 갖는 한쪽 방향 서브시프트 (특히 전이적인 경우) 의 켤레 관계의 복잡성은 무엇인가? 구체적으로, 이 관계가 **비-트리어블 (non-treeable)**하고 **비-아메너블 (non-amenable)**한가?

2. 연구 방법론 (Methodology)

저자는 다음과 같은 단계적 접근을 통해 문제를 해결했습니다.

1. 기초 구조 설정:

   • 알파벳 $A = \{a_i, \tilde{a}_i, \# \mid 1 \le i \le 6\}$를 사용하여 특수한 서브시프트 클래스 $S(A)$를 구성했습니다. 이는 금지된 단어 집합 $\{ \#w\# \mid w \in R \}$을 통해 정의됩니다.
   • $S(A)$는 비트리스 위상 (Vietoris topology) 하에서 콤팩트 거리 공간이 됩니다.

2. 군 작용 (Group Action) 의 구성:

   • $Aut(A^Z, \#)$ (특수한 조건을 만족하는 켤레 사상들의 군) 의 부분군 $\Gamma$를 구성했습니다.
   • $\Gamma$는 6 개의 생성원 $f_1, \dots, f_6$로 생성되며, 각 $f_i$는 블록 코드 (block code) 를 통해 정의된 자동사상입니다.
   • 핵심 Lemma: $\Gamma$는 $(\mathbb{Z}_2 * \mathbb{Z}_2 * \mathbb{Z}_2)^2$와 동형 (isomorphic) 이며, $\Gamma$에는 '거의 자명한 (almost trivial)' 비항등원 (non-identity element) 이 존재하지 않습니다.

3. 동치 관계의 성질 분석:

   • $\Gamma$가 $S(A)$에 작용하여 유도된 동치 관계 $E$를 고려합니다.
   • Pemantle-Peres 의 결과와 Gao 등 [10] 의 정리를 활용하여, $\Gamma$가 $F_2 \times F_2$ (자유 군의 직곱) 를 부분군으로 포함하고 아메너블 (amenable) 이 아니므로, 유도된 동치 관계 $E$는 비-트리어블하고 비-아메너블임을 증명했습니다.

4. 보렐 환원 (Borel Reduction) 을 통한 확장:

   • 핵심 구성 (Encoding): 알파벳 $A$의 심볼들을 2 진수 문자열 $\{0, 1\}$로 인코딩하는 함수 $\rho$를 정의했습니다.
     • $\rho(a_i), \rho(\tilde{a}_i), \rho(\#)$는 모두 길이가 22 인 고유한 패턴으로 설계되어, 서브시프트 내에서 '유일하게 읽을 수 있음 (uniquely readable)'을 보장합니다.
   • 매핑 $\phi$: $S(A)$의 원소 $X$를 한쪽 방향 서브시프트 $\phi(X) \subset \{0, 1\}^{\mathbb{N}}$로 매핑합니다.
   • 보장: 이 매핑 $\phi$는 보렐 가측 (Borel measurable) 이며, $X_1 E X_2$일 때 $\phi(X_1)$과 $\phi(X_2)$가 켤레 (conjugate) 가 되도록 설계되었습니다.
   • 이를 통해 $S(A)$ 위의 비-트리어블/비-아메너블 동치 관계가 $\{0, 1\}$ 알파벳을 갖는 전이적 한쪽 방향 서브시프트의 켤레 관계로 보렐 환원됨을 보였습니다.

3. 주요 결과 (Key Results)

• 주요 정리 (Theorem 1.2): 알파벳 집합 $\{0, 1\}$을 갖는 전이적 (transitive) 한쪽 방향 서브시프트들의 켤레 관계는 **비-트리어블 (non-treeable)**하고 **비-아메너블 (non-amenable)**한 가산 보렐 동치 관계입니다.
• 의미:
  • 이 결과는 Clemens 의 질문 (Question 1.1) 에 부분적으로 답하는 것입니다.
  • 양방향 서브시프트의 켤레 관계가 보편적 가산 관계 ($E_\infty$) 와 동급임을 알았지만, 한쪽 방향의 경우에도 그 복잡성이 매우 높음 (트리 구조로 표현할 수 없으며, 아메너블 군의 작용으로 설명될 수 없음) 을 보였습니다.
  • 특히, 알파벳 크기를 $\{0, 1\}$로 줄여도 이러한 높은 복잡성이 유지됨을 증명했습니다.

4. 의의 및 기여 (Significance)

• 이론적 기여: 동적 시스템 분류 이론 (Classification theory of dynamical systems) 에서 한쪽 방향 서브시프트의 켤레 관계가 기술적 집합론적으로 매우 복잡한 관계임을 최초로 명확히 규명했습니다.
• 방법론적 혁신: 기존 양방향 서브시프트 연구 [7] 에서 사용된 구성을 수정하여 한쪽 방향 시스템에 적용할 수 있도록 했습니다. 특히, 알파벳 크기를 줄이는 과정에서 발생하는 비자명성 (nontriviality) 을 해결하기 위해 새로운 인코딩 기법 ($\rho$ 함수) 과 군 작용의 변형을 도입했습니다.
• 복잡성 계층의 확장: 비-트리어블하고 비-아메너블한 동치 관계가 다양한 동적 시스템 클래스 (Cantor 시스템, Interval 시스템 등) 에서 발견되었으나, 한쪽 방향 서브시프트라는 중요한 클래스에서도 동일한 복잡성이 존재함을 보여줌으로써, 동적 시스템 분류의 난이도 범위를 확장했습니다.

5. 결론

이 논문은 기술적 집합론의 관점에서 한쪽 방향 서브시프트의 켤레 관계가 단순한 구조 (트리어블/아메너블) 로 분류될 수 없음을 증명했습니다. 이는 동적 시스템의 동형 분류 문제가 본질적으로 매우 어렵다는 것을 다시 한번 확인시켜 주며, 향후 더 넓은 클래스의 동적 시스템에 대한 복잡성 연구의 기초를 제공합니다.