Malnormal Subgroups of Finitely Presented Groups

이 논문은 재귀적으로 제시된 군이 유한하게 제시된 군으로의 준동형사상과 합동 확장 성질을 가진 말노말 (malnormal) 매장으로 존재할 수 있음을 증명하고, 클라파함 (Clapham) 의 정리를 정제하여 단어 문제의 결정 가능성 보존을 보이며, 올샨스키 (Ol'shanskii) 의 정리를 정제하여 계수 군을 유한하게 제시된 군에 길이 함수를 보존하는 말노말 매장 형태로 포함시킬 수 있음을 입증합니다.

핵심

1. 배경: 혼란스러운 도시와 규칙적인 도시

상상해 보세요. 세상에 두 가지 도시가 있습니다.

• 도시 A (원래의 그룹): 이 도시는 매우 복잡합니다. 길은 꼬여 있고, 규칙이 불명확하며, "어디로 가야 A 지점에 도착할까?"라는 질문에 답하는 것이 불가능할 수도 있습니다. 수학자들은 이 도시를 '재귀적으로 제시된 (recursively presented)' 그룹이라고 부릅니다. 규칙은 있지만, 그 규칙을 모두 나열하는 데는 시간이 무한히 걸리거나, 혹은 그 규칙들이 서로 충돌할 수 있어 예측이 안 됩니다.
• 도시 B (유한하게 제시된 그룹): 이 도시는 완벽하게 설계된 도시입니다. 모든 길과 건물이 유한한 개수이고, 규칙이 명확합니다. "어디로 가야 A 지점에 도착할까?"라는 질문에 기계가 즉시 답을 줄 수 있습니다.

히그만 (Higman) 이라는 전설적인 수학자는 이미 "어떤 복잡한 도시 A 도 결국 규칙적인 도시 B 의 한 구역으로 숨겨질 수 있다"는 것을 증명했습니다. 하지만 그 방법은 너무 거칠었습니다. 도시 A 를 도시 B 에 넣으면, 도시 A 의 고유한 특징 (길의 꼬임 정도, 규칙의 복잡함 등) 이 다 망가져 버렸습니다. 마치 복잡한 미로를 평평한 종이 위에 그려 넣은 것처럼, 원래의 입체감과 깊이가 사라진 것입니다.

2. 이 논문의 목표: "완벽한 위장술"

이 논문의 저자 프랜시스 와그너 (Francis Wagner) 는 히그만의 방법을 더 정교하게 다듬었습니다. 그는 다음과 같은 목표를 세웠습니다.

"복잡한 도시 A 를 규칙적인 도시 B 에 넣되, A 의 모든 특징 (길의 길이, 규칙의 복잡함, 심지어 '예측 불가능함' 여부까지) 을 그대로 보존하면서, A 가 B 안에서 '독립된 영토'처럼 행동하게 만들자."

여기서 **'독립된 영토'**라는 개념이 중요합니다. 수학 용어로 **'말노말 (Malnormal)'**이라고 하는데, 쉽게 말해 **"내 땅에 남이 들어오면, 내가 그 사람을 바로 알아보고 쫓아낼 수 있는 상태"**를 뜻합니다. A 가 B 안에 섞여 있으면서도, B 의 다른 부분과 엉켜서 혼란을 주지 않고 깔끔하게 분리되어 있다는 뜻입니다.

3. 해결책: "소음이 있는 S-머신" (Noisy S-machines)

저자가 이 위장술을 구현하기 위해 발명한 도구가 바로 **'소음이 있는 S-머신 (Noisy S-machines)'**입니다.

• S-머신이란? 컴퓨터 프로그램처럼 작동하는 가상의 기계입니다. 이 기계가 계산하는 과정을 수학적인 '그룹'으로 변환하면, 우리가 원하는 복잡한 구조를 가진 도시를 만들 수 있습니다.
• 소음 (Noise) 이란? 여기서 핵심입니다. 기존 기계들은 너무 깔끔하게 작동해서, 도시 A 를 넣으면 그 특징이 사라져 버렸습니다. 저자는 기계에 일부러 **'소음 (Noise)'**을 섞었습니다.
  • 비유: 마치 정교한 기계 장난감에 '방해 신호'를 섞어서, 장난감 자체가 원래의 복잡한 움직임을 유지하면서도, 외부에서는 그 소음 때문에 다른 장난감과 섞이지 않게 만드는 것입니다.
  • 이 '소음' 덕분에, 도시 A 는 도시 B 안에 들어갔을 때, B 의 다른 규칙들과 엉키지 않고 **독립된 영토 (말노말)**로 남을 수 있게 되었습니다.

4. 이 연구가 가져온 3 가지 놀라운 성과

이 논문은 단순히 도시를 숨기는 것뿐만 아니라, 숨겨진 도시의 성질까지 완벽하게 보존했습니다.

1. 길의 길이 보존 (기하학적 특징):

   • 도시 A 에서 한 지점에서 다른 지점까지 가는 거리가 100 걸음이라면, 도시 B 안에서도 여전히 100 걸음 (또는 그와 비례하는 거리) 이어야 합니다. 이 연구는 도시 A 가 도시 B 안에서 기하학적으로 왜곡되지 않고 그대로 존재함을 증명했습니다.

2. 규칙의 유무 보존 (알고리즘적 특징):

   • 만약 도시 A 가 "어디로 가야 하는지 답을 알 수 없는 (Word Problem 이 결정 불가능한)" 도시라면, 도시 B 도 그 구역만 보면 답을 알 수 없게 됩니다. 반대로 A 가 답을 알 수 있다면 B 도 답을 알 수 있습니다.
   • 즉, "복잡함은 복잡함대로, 단순함은 단순함대로" 유지됩니다. 이는 클라파함 (Clapham) 의 이전 연구를 훨씬 더 정교하게 발전시킨 것입니다.

3. 규칙의 확장성 (CEP 성질):

   • 도시 A 에 있는 어떤 규칙을 도시 B 전체로 확장할 수 있습니다. 마치 A 시의 조례를 B 주 전체에 적용하되, A 시의 고유한 법규가 무시되지 않도록 보장하는 것과 같습니다. 이는 수학적으로 매우 드문 성질로, 이 논문이 최초로 증명했습니다.

5. 결론: 왜 이것이 중요한가?

이 연구는 수학자들이 **"알 수 없는 것 (Uncomputable)"**과 "알 수 있는 것 (Computable)" 사이의 경계를 어떻게 다룰 수 있는지를 보여줍니다.

• 창의적인 비유: 마치 **위장 망토 (Camouflage)**를 입은 특수부대원처럼, 복잡한 정보를 가진 그룹을 정교한 시스템 안에 숨기되, 그 정보의 본질 (길이의 왜곡, 계산의 난이도 등) 을 전혀 훼손하지 않고, 시스템 전체가 그 정보를 '독립된 영역'으로 인식하게 만든 것입니다.

이 논문은 수학의 한계를 넘어서는 새로운 '위장 기술'을 개발함으로써, 추상적인 대수학이 어떻게 복잡한 알고리즘 문제와 연결될 수 있는지를 보여주는 걸작입니다. 단순히 "숨기는 것"을 넘어, **"숨겨진 상태에서도 원래의 모습을 완벽하게 유지하는 것"**이 가능하다는 것을 증명한 것입니다.

기술 요약

이 논문은 프랜시스 와그너 (Francis Wagner) 가 작성한 것으로, 군론 (Group Theory) 의 고전적인 히그만 매장 정리 (Higman embedding theorem) 를 정교하게 개선한 결과를 제시합니다. 주요 목적은 가산적으로 표현 가능한 (recursively presented) 유한 생성 군을 유한 표현 군 (finitely presented group) 에 매장할 때, 단순히 존재만 보장하는 것이 아니라 말노멀성 (malnormality), 합동 확장 성질 (congruence extension property, CEP), 기하학적 왜곡 (distortion), 그리고 단어 문제 (Word Problem) 의 결정 가능성까지 모두 보존하는 매장을 구성하는 것입니다.

다음은 논문의 상세한 기술적 요약입니다.

---

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

• 히그만 매장 정리 (Higman's Embedding Theorem): 유한 생성된 군 $G$가 유한 표현 군의 부분군으로 매장될 수 있는 필요충분조건은 $G$가 재귀적으로 표현 가능 (recursively presented) 하다는 것입니다.
• 기존 연구의 한계: 히그만 정리의 다양한 개선판들이 존재하지만, 대부분 특정 성질 (예: 단어 문제의 결정 가능성, 비리프시츠 매장, 켤레 문제 등) 중 하나만 보존하거나, 기하학적 성질 (왜곡) 을 제어하지 못했습니다.
• 미해결 문제: 오신 (Osin) 은 히그만 정리의 개선판으로 말노멀 매장 (malnormal embedding) 이 가능한지 질문했습니다. (부분군 $G \le H$가 말노멀하다는 것은 $h \notin G$일 때 $h^{-1}Gh \cap G = \{1\}$인 것을 의미합니다.)
• 목표: 이 논문은 오신의 질문을 해결하고, 다음과 같은 모든 조건을 동시에 만족하는 매장을 구성하는 것을 목표로 합니다:
  1. 목표 군 $H$는 유한 표현 군이다.
  2. 원본 군 $G$는 $H$의 말노멀 부분군이다.
  3. $G$는 합동 확장 성질 (CEP) 을 만족한다.
  4. $G$의 거리 함수와 $H$의 거리 함수가 동치 (equivalent) 이다 (즉, 왜곡이 없다).
  5. $G$의 단어 문제가 결정 가능하면 $H$의 단어 문제도 결정 가능하다.

2. 방법론 (Methodology)

이 논문은 S-머신 (S-machines) 과 Turing 머신을 기반으로 한 계산 모델을 확장하여 군을 구성하는 기법을 사용합니다.

• 노이즈 S-머신 (Noisy S-machines) 의 도입:

  • 기존 사피르 (Sapir) 의 S-머신은 계산 과정을 군의 관계식으로 시뮬레이션하지만, 말노멀성을 보장하기에는 Commutator 관계식이 방해가 됩니다.
  • 저자는 일반화된 S-머신 (Generalized S-machines) 을 도입하고, 여기서 노이즈 S-머신이라는 특수한 클래스를 정의합니다. 이는 테이프의 단어에 미리 정의된 자유군의 자동사상 (automorphism) 을 적용하는 과정에서 '노이즈' (특정 문자열) 를 도입하는 방식입니다.
  • 이 노이즈는 단일 규칙이나 규칙의 유한한 열이 한 단어의 부분열을 다른 부분열로 켤레 (conjugate) 시키는 것을 방지하여, 말노멀성을 보장하는 핵심 메커니즘이 됩니다.

• 주요 구성 요소:

  1. 초기 매장 (Initial Embedding): 임의의 재귀 표현 군을 특정 조합적 성질을 가진 군으로 확장합니다.
  2. 보조 머신 (Auxiliary Machines): $M_A^1$ (말노멀성 보장), $M_L^2$ (Turing 머신 시뮬레이션), $M_L^3, M_L^4, M_L^5, M_L^6$ 등을 순차적으로 구성하여 복잡한 계산 구조를 만듭니다.
  3. 메인 머신 ($M_L$): 여러 보조 머신들을 직렬 및 병렬로 결합하여, 입력이 특정 언어 $L$에 속하는지 판별하고, 그 결과를 군의 관계식으로 인코딩합니다.
  4. 군 구성 ($G(\Omega(ML))$): 생성된 S-머신에 기반한 유한 표현 군을 정의하고, '디스크 관계식 (disk relations)'을 추가하여 계산의 수용성을 반영합니다.

• 증명 도구:

  • 반캄펜 다이어그램 (Van Kampen Diagrams): 군의 관계식을 시각화하고, 영역 (Area) 을 계산하여 단어 문제의 복잡도를 분석합니다.
  • 가중치 함수 (Weight Functions): 다이어그램의 셀에 가중치를 부여하여, 디스크가 포함된 다이어그램의 총 가중치를 경계 (perimeter) 의 함수로 상한을 구합니다.
  • 최소성 (Minimality) 과 반사 (Transposition): 다이어그램의 구조를 분석하여 불필요한 부분 (예: 원뿔형 annulus) 을 제거하거나, θ-밴드를 셀을 가로질러 이동시키는 (transposition) 기법을 사용하여 말노멀성과 왜곡을 증명합니다.

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

A. 정리 A (Theorem A) 의 증명

유한 생성 군 $R$이 재귀적으로 표현 가능할 때, 다음을 만족하는 유한 표현 군 $H$와 매장 $\iota: R \hookrightarrow H$가 존재합니다:

1. 유한 표현성: $H$는 유한 표현 군입니다.
2. 말노멀성: $\iota(R)$은 $H$의 말노멀 부분군입니다.
3. CEP (Congruence Extension Property): $R$은 $H$에서 CEP-부분군입니다. 이는 $R$의 임의의 정규 부분군을 $H$의 정규 부분군으로 확장할 수 있음을 의미하며, 이는 이 논문에서 최초로 히그만 정리에 도입된 개념입니다.
4. 기하학적 왜곡 없음: $R$의 거리 함수 $|\cdot|_R$과 $H$의 거리 함수 $|\cdot|_H$의 제한은 동치입니다 ($c_1 |r|_R \le |r|_H \le c_2 |r|_R$). 즉, $R$은 $H$에서 왜곡되지 않은 (undistorted) 부분군입니다.
5. 단어 문제의 결정 가능성: $R$의 단어 문제가 결정 가능하면 $H$의 단어 문제도 결정 가능합니다.

B. 코롤러리 B (Corollary B)

유한 생성이라는 가정을 제거하고, 임의의 가산 군 $G$와 계산 가능한 길이 함수 $\ell: G \to \mathbb{N}$에 대해, $G$가 $H$에 말노멀하게 매장되면서 $G$의 거리 함수가 $\ell$과 동치인 매장을 구성할 수 있음을 보입니다. 이는 올샨스키 (Ol'shanskii) 의 결과를 CEP 와 말노멀성을 추가하여 개선한 것입니다.

C. 기술적 세부 사항

• 말노멀성 증명: 말노멀 반지 (annular) 다이어그램을 가정하고, 이를 분석하여 모순을 이끌어냅니다. 특히, '노이즈'가 도입된 관계식 때문에 특정 밴드가 존재할 수 없음을 보여줍니다.
• 단어 문제 결정성: 디스크 다이어그램의 가중치 (weight) 를 계산하여, 임의의 단어에 대한 디크 함수 (Dehn function) 가 계산 가능한 함수로 상한이 잡힌다는 것을 증명합니다. 이는 단어 문제의 결정 가능성을 보장합니다.

4. 의의 및 중요성 (Significance)

1. 히그만 정리의 완성도 향상: 기존 히그만 정리의 개선판들이 각기 다른 성질 (기하학적, 알고리즘적) 을 따로 다뤘다면, 이 논문은 대수적 (말노멀, CEP), 기하학적 (왜곡 없음), 알고리즘적 (단어 문제) 성질을 동시에 보존하는 매장을 최초로 구성했습니다.
2. 말노멀 부분군의 실현 가능성: 어떤 재귀 표현 군도 유한 표현 군의 말노멀 부분군으로 실현될 수 있음을 보여줌으로써, 상대적 쌍곡군 (relatively hyperbolic groups) 이론 등에서 중요한 역할을 하는 말노멀 부분군의 구조에 대한 이해를 넓혔습니다.
3. 새로운 계산 모델 (노이즈 S-머신): S-머신에 '노이즈'를 도입하여 말노멀성을 확보하는 기법은 향후 유사한 문제 (예: 켤레 문제의 결정 가능성과 말노멀성의 결합 등) 를 해결하는 데 중요한 도구가 될 것입니다.
4. CEP 의 도입: 히그만 매장 정리에 CEP 조건을 추가한 것은 군의 부분군 구조 연구에 새로운 방향을 제시합니다.

5. 결론

이 논문은 Francis Wagner 에 의해 작성된 것으로, 군론의 핵심 정리 중 하나인 히그만 매장 정리를 획기적으로 정교화했습니다. 저자는 '노이즈 S-머신'이라는 새로운 계산 모델을 개발하여, 유한 표현 군 안에 임의의 재귀 표현 군을 말노멀하게, 왜곡 없이, CEP 를 만족하며, 단어 문제의 결정성을 보존하는 방식으로 매장할 수 있음을 증명했습니다. 이는 대수적, 기하적, 알고리즘적 성질이 서로 어떻게 상호작용하며 보존될 수 있는지에 대한 깊은 통찰을 제공하며, 현대 군론 연구에 중요한 이정표가 됩니다.