Quadratic Equations in Graph Products of Groups and the Exponent of Periodicity

이 논문은 자유 모노이드의 방정식에서 열린 문제인 '무한한 해의 존재가 임의의 큰 주기 지수를 갖는 해의 존재를 의미하는가'에 대해, 정규형을 정의하고 그래프 곱을 통해 보존되는 구조적 조건을 규명하여 유한 생성 라이트-앵글 아인 그룹, 비틀림이 없는 멱영 및 쌍곡 그룹, 그리고 바움슬라그-솔리타르 그룹 등 다양한 그룹에서 이 성질이 성립함을 증명합니다.

핵심

🧩 핵심 주제: "무한한 해 (Solution) 가 있다면, 규칙적인 패턴도 무한히 반복될까?"

이 논문의 주인공은 **볼커 디커트 (Volker Diekert)**와 그의 동료들입니다. 그들은 1977 년에 '문자 방정식'이 풀 수 있는지 (결정 가능성) 를 증명한 마카닌 (Makanin) 의 업적을 계승하여, 더 깊은 질문을 던집니다.

🎲 비유 1: 레고 방정식

상상해 보세요. 여러분에게 'A', 'B', 'C'라는 레고 블록이 있고, "A 와 B 를 어떻게 쌓으면 C 가 되는가?"라는 방정식이 있다고 칩시다.

• 해 (Solution): 이 방정식을 만족시키는 블록 쌓기 방법입니다.
• 해가 무한히 많다: 이 방정식을 만족시키는 블록 쌓기 방법이 끝없이 많다는 뜻입니다.

이제 중요한 질문이 나옵니다:

"만약 해가 무한히 많다면, 그 해들 속에 'AAAAAA...'처럼 같은 블록이 계속 반복되는 (주기적인) 패턴이 무한히 길어지는 경우가 반드시 존재할까?"

이 '반복되는 블록의 길이'를 수학자들은 **주기성 지수 (Exponent of Periodicity)**라고 부릅니다.

🕵️‍♂️ 과거의 미스터리

과거에는 "해가 무한히 많으면, 반드시 이런 반복 패턴이 무한히 길어지는 해가 있다"는 것이 증명되지 않았습니다. 마치 "사람이 무한히 많으면, 반드시 키가 2 미터 이상인 사람이 반드시 있어야 하는가?"를 증명하지 못했던 것과 비슷합니다. (물론 실제로는 2 미터 이상인 사람이 없을 수도 있죠.)

🚀 이 논문의 발견: "그래프 곱 (Graph Product) 의 마법"

이 논문은 이 미스터리를 **특정한 종류의 그룹 (수학적 구조)**에 대해 해결했습니다. 그들이 다룬 그룹은 **그래프 곱 (Graph Products)**이라고 불리는 것들입니다.

🕸️ 비유 2: 친구 관계와 레고

• 자유 군 (Free Group): 모든 레고 블록이 서로 다른 규칙을 따릅니다. (가장 자유로운 상태)
• 아벨 군 (Abelian Group): 모든 레고 블록이 서로 순서 상관없이 쌓입니다. (완전한 질서)
• 그래프 곱 (Graph Product): 이 두 가지의 중간입니다. 어떤 레고 블록끼리는 순서를 바꿔도 되지만 (친구 관계), 어떤 블록끼리는 순서를 바꿔서는 안 됩니다. 이를 그래프로 표현합니다.

이 논문은 그래프 곱이라는 구조를 가진 그룹들에서 다음과 같은 놀라운 사실을 증명했습니다:

"만약 이 그룹에서 방정식의 해가 무한히 많다면, 그 해들 중에는 반드시 'A, B, A, B, A, B...'처럼 같은 패턴이 무한히 길어지는 것이 존재한다!"

즉, **"해가 무한하다 = 규칙적인 반복 패턴도 무한하다"**는 결론을 내린 것입니다.

🌟 이 발견이 중요한 이유

1. 예측 가능성: 이제 우리는 "해가 무한히 많다"는 사실만 알면, 그 해들이 어떻게 생겼는지 (반복되는 패턴을 가진다는 것) 를 미리 알 수 있게 되었습니다.
2. 범위의 확장: 이 결과는 **오른쪽 각 아인슈타인 군 (Right-Angled Artin Groups)**이라는 매우 중요한 수학적 구조를 포함하며, **하이퍼볼릭 군 (Hyperbolic Groups)**이나 -nilpotent 군과 같은 다른 복잡한 그룹들에도 적용됩니다.
3. 실용성: 암호학 (Cryptology) 과 컴퓨터 과학에서 방정식을 푸는 알고리즘을 설계할 때, "무한한 해를 찾을 때 반복 패턴을 찾아라"라는 강력한 지침을 제공합니다.

📝 요약: 한 문장으로 정리하면?

"이 논문은 복잡한 수학적 구조 (그래프 곱) 에서 방정식을 풀 때, 해가 무한히 많다면 반드시 그 해들 속에 '끝없이 반복되는 패턴'이 숨어있음을 증명했습니다. 이는 마치 무한히 많은 레고 쌓기 방법이 있다면, 그중에는 '레고 A 와 B 를 끝없이 번갈아 쌓는 방법'이 반드시 있다는 것을 발견한 것과 같습니다."

이 발견은 수학자들이 방정식의 해를 더 잘 이해하고, 더 효율적으로 찾을 수 있는 길을 열어주었습니다.

기술 요약

이 논문은 자유 군 (free groups) 및 자유 아벨 군 (free Abelian groups) 을 포함하는 다양한 군 클래스에서 **2 차 방정식 (quadratic equations)**의 해 집합과 주기성 지수 (exponent of periodicity) 사이의 관계를 연구한 학술지 (Journal of Groups, Complexity, Cryptology, Vol. 18, Issue 1, 2026) 논문입니다. 저자들은 Volker Diekert, Silas Natterer, Alexander Thumm 입니다.

다음은 이 논문의 기술적 요약입니다.

---

1. 연구 배경 및 문제 제기

• 배경: 1977 년 Makanin 은 자유 모노이드 (free monoids) 에서 방정식의 가해성 (decidability) 을 증명했습니다. 그의 증명에서 핵심적인 역할을 한 개념이 **주기성 지수 (exponent of periodicity)**입니다. 단어 $w$의 주기성 지수 $\exp(w)$는 $w$가 $p^e$ 형태의 비자명한 인자를 포함하는 가장 큰 자연수 $e$로 정의됩니다.
• 열린 문제 (Problem 1.1): 자유 반군 (free semigroup) 에서 유한한 방정식 시스템 $S$가 무한히 많은 해를 가진다면, 해 집합의 주기성 지수 $\exp(S)$가 무한대 ($\infty$) 가 되는가?
  • Makanin 의 결과에 따르면, 해가 충분히 큰 주기성 지수를 가지면 무한히 많은 해가 존재합니다. 하지만 그 역 (무한한 해의 존재가 무한한 주기성 지수를 의미하는가) 은 여전히 미해결 문제입니다.
• 목표: 이 논문은 자유 군뿐만 아니라 **그래프 곱 (graph products)**으로 구성된 다양한 군 클래스, 특히 2 차 방정식 시스템에 대해 이 역명제가 성립하는 조건을 규명하고, 이를 증명하는 것입니다.

2. 방법론 및 주요 정의

논문은 다음과 같은 수학적 도구와 정의를 기반으로 합니다.

• 정규형 (Normal Forms): 군의 원소를 자유 모노이드의 단어 (word) 로 매핑하는 정규형 $nf: G \to \Gamma^*$를 도입합니다. 이를 통해 군 원소의 주기성 지수를 정의할 수 있습니다 ($\exp(nf(g))$).
• 허용 가능한 정규형 (Admissible Normal Forms):
  • 정규형 $nf$가 **허용 가능 (admissible)**하다는 것은, 임의의 $u, p, v \in G$ ($p \neq 1$) 에 대해 집합 $nf(up^*v)$가 무한하다면 그 주기성 지수가 무한대라는 성질을 의미합니다.
  • **완전 허용 가능 (perfectly admissible)**은 더 강한 조건으로, 단어의 길이가 충분히 길어지면 주기성 지수가 임의의 $n$ 이상으로 발산함을 의미합니다.
• 군 클래스 $\mathcal{G}$: 저자들은 다음 세 가지 조건을 만족하는 군 $G$와 정규형 쌍 $[G, \pi, nf]$의 집합을 정의합니다.
  1. $G$는 비순환 (torsion-free) 이며, 모든 $g \in G$에 대해 $g$의 제곱근 집합 $\{h \mid h^2 = g\}$이 유한함 (유한 제곱근 성질).
  2. $G$는 유한 생성되며, $nf$는$\pi$의 단면 (section) 임.
  3. $up^*v$가 무한하면 $nf(up^*v)$의 주기성 지수가 무한함.

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

3.1. 그래프 곱에 대한 닫힘 성질 (Closure Property)

• 정리 1.3: 만약 각 로컬 군 (local monoid) $M_i$가 허용 가능한 정규형 쌍을 가진다면, 이들의 그래프 곱 (graph product) $M$ 또한 자연스러운 구성을 통해 허용 가능한 정규형 쌍을 가집니다.
• 이는 그래프 곱 구조가 주기성 지수의 무한성 성질을 보존함을 의미합니다.

3.2. 2 차 방정식 시스템의 해와 주기성 지수

• 정리 1.4 (주요 정리): $[G, \pi, nf] \in \mathcal{G}$인 군 $G$에서 정의된 유한한 2 차 방정식 시스템 $S$가 무한히 많은 해를 가진다면, 적어도 하나의 변수 $X$에 대해 해 집합의 정규형 주기성 지수가 무한대 ($\exp(nf(\{\sigma(X)\})) = \infty$) 가 됩니다.
• 코롤러리 1.5 & 1.6: 이 결과는 **우각 아인슈타인 군 (Right-Angled Artin Groups, RAAGs)**을 포함한 다양한 군 클래스에 적용됩니다. RAAG 의 경우 표준적인 short-lex 정규형이 이 조건을 만족합니다.

3.3. 구체적인 군 클래스에 대한 적용

논문은 다음 군 클래스들이 위 조건을 만족함을 보였습니다:

1. 우각 아인슈타인 군 (RAAGs): 자유 부분 교환 군 (free partially commutative groups) 으로, 자유 군과 자유 아벨 군 사이의 구조를 가집니다.
2. Baumslag-Solitar 군: 특정 조건 ($p+q \neq 0$ 및 $p, q$의 홀짝성 조건 등) 을 만족하는 Baumslag-Solitar 군 $BS(p,q)$는 유한 제곱근 성질과 허용 가능한 정규형을 가집니다.
3. 유한 생성 비순환 가해군 (Strongly Polycyclic Groups): 특히 **유한 생성 비순환 멱영군 (torsion-free nilpotent groups)**은 유일 제곱근 성질을 가지며, 이 조건을 만족합니다.
4. 비순환 쌍곡군 (Torsion-free Hyperbolic Groups): Gromov 의 쌍곡군 이론을 적용하여, short-lex 정규형이 허용 가능하며 유일 제곱근 성질을 가짐을 증명했습니다.

4. 증명 전략

• 2 차 방정식의 분류: 2 차 방정식 시스템의 변수 발생 패턴 (각 변수가 0 번, 1 번, 2 번 나타나는 경우 등) 을 7 가지 경우로 나누어 분석했습니다.
• 귀납적 접근: 변수의 수를 줄이거나, 독립적인 방정식으로 분해하거나, 특정 변수를 제거하는 과정을 통해 시스템을 단순화했습니다.
• 구조적 성질 활용:
  • 유한 제곱근 성질: 해가 무한히 많을 때, 제곱근이 유한하므로 해가 특정 패턴 (예: $x u x v = 1$) 을 따라야 함을 이용했습니다.
  • 정규형의 성질: 그래프 곱에서의 정규형이 로컬 군의 정규형 성질을 어떻게 보존하는지 (Theorem 5.5) 를 증명하여, 복잡한 군 구조에서도 주기성 지수가 발산함을 보였습니다.
  • 자동자 (Automata) 이론: 정규 언어 (regular languages) 와 pumping lemma 를 사용하여, 무한한 해 집합이 반드시 높은 주기성 지수를 가진다는 것을 논리적으로 유도했습니다.

5. 의의 및 결론

• 이론적 기여: Makanin 의 자유 모노이드에 대한 결과를 비가환 군 (non-abelian groups) 으로 확장했습니다. 특히, "무한한 해의 존재 $\implies$ 무한한 주기성 지수"라는 명제가 자유 군뿐만 아니라 RAAG, 멱영군, 쌍곡군 등 광범위한 군 클래스에서 성립함을 증명했습니다.
• 복잡도 및 결정 문제: 이 결과는 방정식의 가해성 문제뿐만 아니라, 해의 개수 (유한/무한) 를 판별하는 문제에도 중요한 통찰을 제공합니다. Plandowski 와 Schubert 가 제안한 알고리즘적 접근법과 결합하여, 무한 해의 존재 여부를 결정하는 효과적인 절차가 가능함을 시사합니다.
• 미래 연구: 이 연구는 EDT0L 언어 (Equation solution sets are EDT0L languages) 와의 연결성을 보여주며, 다양한 대수적 구조에서의 방정식 이론 연구의 기초를 마련했습니다.

요약하자면, 이 논문은 그래프 곱 구조를 가진 다양한 군 클래스에서 2 차 방정식의 해 집합이 무한할 경우, 그 해들이 반드시 높은 주기성 지수 (arbitrarily large exponent of periodicity) 를 가진다는 것을 증명함으로써, 방정식 이론과 군론의 교차 영역에서 중요한 진전을 이루었습니다.