On the word problem for just infinite groups

이 논문은 유한 생성 정밀 무한군의 경우 레커시브 열거 가능한 관계 집합을 가진 표현에 대해 단어 문제가 균일하게 결정 가능함을 증명하고, 가산 생성 정밀 무한군에 대해서는 대부분의 경우 결정 가능하지만 국소 유한군의 특정 표현에서는 결정 불가능한 사례를 구성하여 그 복잡성을 규명합니다.

핵심

🎒 핵심 비유: "무한한 레고 성"과 "진짜 vs 가짜"

수학자들은 복잡한 수학적 구조를 레고 블록으로 만든 성이라고 상상합니다.

• 생성자 (Generators): 성을 쌓는 기본 레고 블록들.
• 관계 (Relations): "이 블록은 저 블록 위에 올려야 한다", "이 두 블록은 붙으면 사라진다" 같은 규칙들.
• 단어 문제 (Word Problem): "주어진 레고 블록 조합 (단어) 으로 만든 성이, 사실은 빈 공간 (1, 즉 0) 인가?"를 판단하는 문제입니다. 즉, "이 블록 조합은 정말로 아무것도 안 만드는 걸까, 아니면 뭔가 복잡한 성을 만드는 걸까?"를 알아내는 것입니다.

이 논문은 **"규칙이 무한히 많은 레고 성"**에서 이 문제를 풀 수 있는지, 그리고 어떤 경우에는 불가능한지를 연구합니다.

---

📜 이 논문의 주요 발견 3 가지

1. "작은" 무한 성 (유한 생성군) 은 모두 해결 가능하다!

상황: 레고 블록의 종류가 유한한 개수 (예: 빨강, 파랑, 초록 3 개) 로 정해져 있고, 규칙은 컴퓨터가 계속 찾아서 알려주는 방식 (재귀 열거 가능) 으로 주어집니다.
결론: 이 경우, **"이 조합이 빈 공간인가?"**라는 질문에 대한 답을 항상 찾을 수 있는 알고리즘이 존재합니다.

• 비유: 두 명의 탐정이 동시에 수사를 합니다.
  • 탐정 A: "이 조합이 빈 공간이 맞다면, 규칙들을 계속 적용하다 보면 언젠가 빈 공간이 될 거야!"라고 증명하려 합니다.
  • 탐정 B: "아니야, 이 조합은 빈 공간이 아니야! 만약 빈 공간이라면, 이 성을 더 단순하게 만들었을 때 유한한 크기의 성이 되어야 해. 유한한 성의 규칙을 하나하나 만들어보면서 확인해 보자!"라고 반증하려 합니다.
  • 결과: 이 두 탐정 중 하나는 반드시 "정답"을 찾아서 멈추게 됩니다. 왜냐하면 이 특수한 성 (직접 무한군) 의 성질상, 답은 '예'이거나 '아니오' 중 하나이기 때문입니다.

2. "엄청나게 큰" 무한 성 (가산 생성군) 은 상황에 따라 다르다

상황: 레고 블록의 종류가 무한히 많을 때 (1 번, 2 번, 3 번... 무한대로).
결론:

• 일반적인 경우: 모든 규칙을 한 번에 다 보고 답을 내는 보편적인 알고리즘은 존재하지 않습니다. (컴퓨터가 영원히 멈추지 않고 돌아갈 수 있습니다.)

• 하지만, 특정 조건이 충족되면 해결 가능합니다.

  • 조건 1: 성이 '국소 유한 (Locally Finite)'하지 않을 때 (즉, 일부 블록만으로도 무한한 성을 만들 수 있을 때).
  • 조건 2: 성이 '단순군 (Simple Group)'일 때 (규칙을 깨뜨릴 수 있는 내부 구조가 없을 때).
  • 조건 3: 성이 '모노리식 (Monolithic)'일 때 (모든 규칙이 하나의 핵심 축을 공유할 때).
  • 조건 4: 성이 '국소 유한'하지만, 블록 개수가 커질수록 성의 크기가 얼마나 커지는지 예측할 수 있는 함수가 있을 때.

• 비유: 블록이 무한히 많으면, "이 조합이 빈 공간인가?"를 판단하는 것이 마치 "무한한 도서관에서 특정 책이 존재하는지 찾는 것"처럼 어렵습니다. 하지만 도서관이 특별한 구조를 가지고 있거나 (단순군), 책의 크기가 규칙적으로 변한다면 (예측 가능한 함수), 우리는 그 도서관의 특정 구역만 조사해서 답을 찾을 수 있습니다.

3. "해결 불가능한" 함정 (Undecidable Word Problem)

상황: 규칙이 무한히 많고, 성이 '국소 유한'하며, 크기를 예측할 수 없는 특수한 경우.
결론: 이 경우, **"이 조합이 빈 공간인가?"**라는 질문에 대한 답을 절대 찾을 수 없는 레고 성을 만들 수 있습니다.

• 비유: 악마가 만든 레고 성입니다.
  • 이 성의 규칙은 컴퓨터가 만들어내지만, 그 규칙들의 숨겨진 패턴은 **컴퓨터가 풀 수 없는 난제 (할 수 없는 문제)**와 연결되어 있습니다.
  • 예를 들어, "이 블록이 0 이 되는지"를 확인하는 것은 "어떤 컴퓨터 프로그램이 영원히 멈추지 않고 돌아가는지 (정지 문제)"를 확인하는 것과 똑같이 어렵습니다.
  • 논문의 저자는 이런 '악마의 레고 성'을 실제로 구성해 보였습니다. 이 성에서는 규칙을 아무리 많이 알아내도, 특정 블록이 0 인지 아닌지 영원히 알 수 없습니다.

---

💡 요약: 이 논문이 우리에게 주는 메시지

1. 규칙이 적으면 (유한 생성): 아무리 규칙이 복잡하게 나열되어 있어도, 이 특수한 종류의 성에서는 항상 답을 찾을 수 있습니다. (우리는 해결책을 찾았습니다!)
2. 규칙이 많으면 (가산 생성):
   • 대부분의 경우, 특별한 조건 (성질의 단순함이나 크기 예측 가능성) 이 있으면 답을 찾을 수 있습니다.
   • 하지만, 가장 악랄한 경우에는 답을 찾을 수 없는 함정이 존재합니다. 수학적으로 증명된 '해결 불가능한 영역'이 있다는 것입니다.

🌟 마치며

이 논문은 수학자들이 "무한한 규칙 속에서도 진실을 찾을 수 있는가?"라는 질문에 대해, **"대부분의 경우에는 찾을 수 있지만, 아주 특별한 함정만 피하면 된다"**는 것을 증명했습니다. 마치 복잡한 미로에서 대부분의 길은 지도가 있지만, 몇몇 길은 지도 자체가 존재하지 않는다는 것을 발견한 것과 같습니다.

저자 알렉세이 탈람부차는 이 복잡한 수학적 구조를 분석하여, 우리가 어디까지 알고 어디부터는 영원히 모를 수 있는지의 경계를 그렸습니다.

기술 요약

논문 요약: 유한 생성 및 가산 생성 정단위군 (Just Infinite Groups) 의 단어 문제 (Word Problem)

저자: 알렉세이 탈람부츠 (Alexey Talambutsa)
주제: 정단위군 (Just Infinite Groups) 에 대한 단어 문제의 결정 가능성 (Decidability)

1. 연구 배경 및 문제 제기

정단위군 (Just Infinite Group) 은 무한군이지만, 모든 비자명한 정규 부분군에 대한 몫군이 유한군인 군을 의미합니다. 이 군들은 단순군, 무한 순환군, 디헤드럴 군, 그리고 그릴고르추크 (Grigorchuk) 군 등 다양한 중요한 군들을 포함합니다.

이 논문은 정단위군의 단어 문제 (Word Problem) 에 초점을 맞추고 있습니다. 단어 문제란 주어진 생성자와 관계식 (relations) 으로 표현된 군에서, 임의의 단어가 항등원과 같은지 여부를 알고리즘적으로 판별할 수 있는지의 문제입니다.

• 유한 생성 (Finitely generated) 경우: 기존에 알려진 결과 (Kuznetsov, Dyson-Mostowski 등) 를 바탕으로 하지만, Wilson-Grigorchuk 분류 정리를 직접 사용하지 않고 정의에서 직접 유도하는 새로운 접근법을 제시합니다.
• 가산 생성 (Countably generated) 경우: 생성 집합이 무한한 경우, 단어 문제의 결정 가능성은 어떻게 변하는지, 그리고 어떤 조건에서 결정 불가능 (Undecidable) 해지는지를 탐구합니다.

2. 주요 방법론 (Methodology)

저자는 다음과 같은 수학적 도구와 알고리즘적 기법을 사용합니다:

1. 병렬 알고리즘 (Parallel Algorithms):

   • Kuznetsov 의 정리와 Dyson-Mostowski 정리의 아이디어를 결합하여, 두 개의 알고리즘을 병렬로 실행합니다.
   • 알고리즘 1: 주어진 단어 $x=1$ 임을 증명하려 시도 (관계식을 통해 $x$ 가 1 로 귀결되는지 탐색).
   • 알고리즘 2: $x \neq 1$ 임을 증명하려 시도 (군을 $x=1$ 로 추가한 몫군이 유한한지, 혹은 특정 구조를 갖는지 확인).
   • 정단위군의 성질에 의해 두 경우 중 하나는 반드시 유한 시간 내에 종료되므로, 전체적으로 결정 가능해집니다.

2. 정단위군의 성질 활용:

   • 정단위군 $G$ 에서 $x \neq 1$ 인 경우, $x$ 로 생성된 정규 폐포 (normal closure) $N_{cl}(x)$ 에 의한 몫군 $G/N_{cl}(x)$ 는 유한군이 됩니다. 이 성질을 이용하여 유한군의 곱셈표를 탐색하는 방식으로 $x \neq 1$ 을 증명합니다.

3. 구성적 반례 (Constructive Counterexamples):

   • 가산 생성 정단위군 중 단어 문제가 결정 불가능한 경우를 구성하기 위해, 그림자 집합 (Shaded Sets) 이라는 특수한 재귀적으로 열거 가능한 (r.e.) 집합을 정의합니다.
   • Busy Beaver 함수 ($BB(n)$) 의 비계산성을 이용하여, 특정 생성자가 1 인지 여부가 결정 불가능한 관계를 가진 군의 프레젠테이션을 구성합니다.

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

3.1. 유한 생성 정단위군 (Finitely Generated Just Infinite Groups)

• 주요 정리 (Theorem 1): 유한 생성 정단위군에 대해, 재귀적으로 열거 가능한 관계식 집합을 가진 프레젠테이션이 주어지면, 단어 문제는 균일하게 결정 가능 (Uniformly Decidable) 합니다.
• 의의: 이 결과는 Wilson-Grigorchuk 분류 정리 (Branch, Simple, Hereditarily Just Infinite 로 분류) 에 의존하지 않고, 정단위군의 정의와 고전적인 결정 가능성 정리 (Kuznetsov, Dyson-Mostowski) 만을 사용하여 직접 증명되었습니다. 이는 단순군과 잔류 유한군 (residually finite) 에 대한 기존 결과를 정단위군 전체로 자연스럽게 확장한 것입니다.

3.2. 가산 생성 정단위군 (Countably Generated Just Infinite Groups)

• 균일 단어 문제의 부재 (Theorem 2): 생성 집합이 가산 무한인 경우, 균일 단어 문제 (Uniform Word Problem) 는 결정 불가능합니다. 즉, 프레젠테이션이 입력으로 주어지는 경우 알고리즘이 존재하지 않습니다. 이는 무한 순환군조차도 예외가 아님을 보여줍니다.
• 고정 프레젠테이션의 결정 가능성:
  • 단순군 (Simple Groups): 가산 생성 단순군의 고정 프레젠테이션에 대해서는 단어 문제가 결정 가능합니다 (Theorem 3).
  • 국소 유한이 아닌 정단위군: 국소 유한 (locally finite) 이 아닌 정단위군의 경우, 고정 프레젠테이션에 대해 단어 문제가 결정 가능합니다 (Theorem 4).
  • 국소 유한 정단위군 (Locally Finite): 이 경우 결정 가능성은 추가 조건에 달려 있습니다. Theorem 5에 따르면, 단어 문제가 결정 가능하기 위한 필요충분조건은 생성자의 부분집합으로 생성된 부분군의 크기를 계산할 수 있는 계산 가능한 비감소 무계 함수 $f(k)$ 가 존재하는 것입니다.
  • 모노리식 군 (Monolithic Groups): 모든 모노리식 정단위군 (잔류 유한이 아닌 경우) 에 대해 고정 프레젠테이션의 단어 문제는 결정 가능합니다 (Theorem 6).

3.3. 결정 불가능한 사례의 구성 (Undecidable Cases)

• Theorem 7: 가산 생성 정단위군 중 국소 유한 (locally finite) 이면서 잔류 유한 (residually finite) 인 군 (예: Wilson 이 구성한 $WC$ 군) 에 대해, 재귀적으로 열거 가능한 관계식을 가지지만 단어 문제가 결정 불가능한 프레젠테이션이 존재함을 증명했습니다.
• 구체적 구성: Post 의 단순 집합 (Post's simple set) 과 유사한 성질을 가진 "그림자 집합"을 이용해, 특정 생성자가 1 인지 여부를 결정하는 것이 정지 문제 (Halting Problem) 와 동치이도록 관계를 구성했습니다.
• 중요한 발견: 같은 군 (Group) 에 대해, 어떤 프레젠테이션은 단어 문제가 결정 가능하지만, 다른 프레젠테이션 (특히 가산 생성과 특수한 관계식 구조를 가진 경우) 은 결정 불가능할 수 있음을 보였습니다.

4. 결론 및 의의 (Significance)

1. 이론적 확장: 정단위군의 단어 문제 해결을 위해 복잡한 분류 정리를 거치지 않고, 군의 정의와 기본 알고리즘적 성질만으로 해결책을 제시함으로써 이론의 기초를 다졌습니다.
2. 생성 집합의 영향: 유한 생성과 가산 생성 사이의 결정 가능성 격차를 명확히 했습니다. 유한 생성에서는 균일 결정 가능성이 보장되지만, 가산 생성에서는 프레젠테이션의 구조에 따라 결정 불가능한 경우가 발생할 수 있음을 보였습니다.
3. 알고리즘적 한계와 가능성: 정단위군이라는 넓은 클래스 내에서 단어 문제가 언제 결정 가능하고 언제 불가능한지에 대한 정확한 조건 (국소 유한성, 잔류 유한성, 모노리식 성질 등) 을 제시했습니다.
4. 새로운 방향 제시: "단어 문제가 결정 가능한 군은 유한 생성 단순군에 매장될 수 있는가?"라는 Boone-Higman 추측의 약화된 버전 (정단위군 버전) 을 제안하며, 향후 연구의 방향을 제시했습니다.

이 논문은 군론의 알고리즘적 문제 해결에 있어 정단위군 클래스의 복잡성과 구조적 특성을 심층적으로 분석한 중요한 연구로 평가됩니다.