A virtually nilpotent group whose Green series is not D-finite

코랑탱 보다르의 논문 "A VIRTUALLY NILPOTENT GROUP WHOSE GREEN SERIES IS NOT D-FINITE"에 대한 상세한 기술적 요약입니다.

1. 문제 제기 및 배경

그린 급수 (Green Series):
이 논문은 유한 생성 다중집합 $S$를 가진 군 $G$에 대한 그린 급수(코그로스 급수라고도 함) $\Gamma(G, S)(z)$를 조사합니다. 이는 다음과 같이 정의됩니다:
$$\Gamma(G, S)(z) = \sum_{\ell \geq 0} c_\ell z^\ell$$
여기서 $c_\ell$은 $(G, S)$의 케일리 그래프에서 항등원 $e_G$에서 시작하여 $e_G$로 끝나는 길이 $\ell$의 닫힌 경로 (closed paths) 의 개수입니다.

급수의 위계 (Hierarchy of Series):
저자는 이러한 급수를 특정 대수적 위계 내에서 분류하고자 합니다:
$$\text{Rational} \subset \text{Algebraic} \subset \text{Diagonal of Rational} \subset \text{D-finite} \subset \text{D-algebraic}$$

• D-finite (Holonomic): 급수의 계수가 다항식 계수를 가진 선형 재귀 관계를 만족하면 D-finite 입니다.
• 기존 결과:
  • $G$가 유한군일 때만 Rational 입니다.
  • $G$가 virtually free 일 때 Algebraic 입니다.
  • $G$가 virtually $F_m \times \mathbb{Z}^n$일 때 Diagonal of Rational 입니다.
  • 초다항식 성장을 보이는 아멘 (amenable) 군의 경우 D-finite 이 아닙니다 (Bell & Mishna).
  • $F_2 \times F_2$와 $SL_4(\mathbb{Z})$의 특정 생성 집합에 대해서는 D-finite 이 아닙니다 (Garrabrant & Pak).

미해결 문제:
**가상 멱영군 (virtually nilpotent groups)**의 경우 합의가 명확하지 않았습니다. 계수의 점근적 성장률이 종종 D-finite 급수의 성장률과 일치했지만, 급수 자체가 항상 D-finite 인지 여부는 알려지지 않았습니다. 파크 (Pak) 와 소우쿠프 (Soukup) 의 이전 연구에 따르면, 특정 멱영군 $UT_m(\mathbb{Z})$($m \approx 10^8$) 의 경우 급수가 Rational 급수의 대각선 (diagonal) 이 아니거나, 이를 계산하는 알고리즘이 존재하지 않는다는 것이 보였습니다. 그러나 그들은 급수가 엄밀히 비 D-finite (strictly non-D-finite) 임을 증명하지는 않았습니다.

목표:
구체적인 생성 집합을 가진 가상 멱영군의 그린 급수가 D-finite 이 아닌 최초의 예를 제시하는 것입니다.

---

2. 군과 생성 집합

이 논문은 반직곱 $H_3(\mathbb{Z}) \rtimes C_2$로 정의된 군 **$vH$**에 초점을 맞춥니다.

• 구조: $vH = \langle x, y, t \mid [x, [x, y]] = [y, [x, y]] = t^2 = e, txt = y \rangle$.
• 성질: 이는 가상 2-단계 멱영군입니다. 이전에는 가상이 아벨 군이 아닌 다항식 지오데식 성장을 가진 군의 첫 번째 예로 확인되었습니다.
• 생성 집합: 사용된 특정 다중집합은 $S = \{x, x^{-1}, t, t, t, t, t, t, t, t\}$입니다. 생성자 $t$의 중복도 (8 개 복사본) 에 유의하십시오.

주요 정리 (정리 1):
그린 급수 $\Gamma(vH, S)(z)$는 D-finite 이 아닙니다.

귀결:
$vH$가$SL_3(\mathbb{Z})$에 매장되므로,$SL_3(\mathbb{Z})$는 그린 급수가 D-finite 이 아닌 생성 다중집합을 허용합니다. 이는 이전까지 $m \geq 4$인 $SL_m(\mathbb{Z})$에 대해서만 알려져 있던 결과를 확장한 것입니다.

---

3. 방법론

증명 전략은 $F_2 \times F_2$에 대해 가라브란트 (Garrabrant) 와 파크가 사용한 접근법을 적용한 것으로, **부분 단어 복잡도 (subword complexity)**와 **승법적 수열 (multiplicative sequences)**에 의존합니다.

A. 축소된 단어 (Reduced Words) 로의 축소

저자는 먼저 그린 급수 $\Gamma(z)$를 "축소된" 단어 $R(z)$(즉시 후퇴 $xx^{-1}$가 없는 단어) 의 성장 급수와 연관시킵니다. 바르톨디 - 그리고르추크 (Bartholdi–Grigorchuk) 코그로스 공식의 변형을 사용하여, $\Gamma(z)$가 D-finite 일 필요충분조건이 $R(z)$가 D-finite 임을 보입니다.

B. 경로의 분해

축소된 단어의 집합 $R$은 $t$ 생성자의 개수에 따라 세 부분집합으로 분할됩니다:

1. $R_1$: $t$가 적은 단어 (최대 4 개, 또는 연속된 $t$가 있는 경우 6 개). 이 집합은 문맥 자유 언어에 해당하며 대수적 (따라서 D-finite) 인 급수를 생성합니다.
2. $R_3$: $t$가 많은 단어 (최소 8 개). 이러한 항의 기여도는 2 의 높은 거듭제곱으로 나누어떨어지므로, 2 의 특정 거듭제곱에 대해 무시할 수 있습니다.
3. $R_2$: 정확히 여섯 개의 $t$를 가지며 연속된 $t$가 없는 단어. 이것이 결정적인 집합입니다.

C. $R_2$의 조합론적 분석

$R_2$의 경로는 헤이젠베르크 부분군의 케일리 그래프에서 특정 기하학적 모양에 해당합니다. 이러한 경로의 계수는 정수 $(a, b, c, d)$에 대한 디오판토스 연립방정식을 푸는 문제로 환원됩니다:
$$a + b + c + d = n, \quad ab = cd$$
해의 개수 $|S_n|$은 2 의 거듭제곱에 대해 모듈로 분석됩니다. 저자는 계산을 단순화하기 위해 대칭성 (다이헤드랄 군 $D_8$의 작용) 을 식별합니다.

D. 승법 함수와의 연결

분석 결과, 해의 개수 $|S_n|$(특히 홀수 인덱스에 대해) 은 $n$을 나누는 가장 큰 정수 $m$이 되도록 정의된 함수 $m(n)$과 직접적으로 관련되어 있음이 드러납니다.
저자는 계수가 2 에 대해 모듈로일 때 승법 함수 $f(n)$의 값에 의존하는 유도 급수 $S(z)$를 구성합니다:
$$f(n) = m\left(\frac{n}{2^{\nu_2(n)}}\right) \pmod 4$$
여기서 $f(n) \in \{+1, -1\}$입니다.

E. 부분 단어 복잡도 논증

증명의 핵심은 정리 7(가라브란트 - 파크)에 기반합니다: 급수가 D-finite 이라면, 그 계수 (2 에 대해 모듈로) 의 부분 단어 복잡도는 $o(2^n)$이어야 합니다.
저자는 정리 9를 증명합니다: 위에서 구성한 특정 승법 함수 $f(n)$에 대해, 부분 단어 복잡도는 최대입니다 ($p_f(n) = 2^n$).

• 정리 9 의 증명: $f(q) = -1$인 소수 거듭제곱의 희소성과 중국인의 나머지 정리를 사용하여, 길이가 $n$인 임의의 $\pm 1$ 패턴이 어떤 $x$에 대해 $f(x+i)$에 의해 실현될 수 있음을 보입니다.

유도된 급수 $S(z)$의 계수가 최대 부분 단어 복잡도를 보이므로, $S(z)$는 D-finite 일 수 없습니다. $S(z)$는 D-finite 을 보존하는 연산 (짝수/홀수 항 추출, 선형 결합) 을 사용하여 $R(z)$로부터 구성되었으므로, 원래 급수 $R(z)$와 결과적으로 $\Gamma(z)$도 D-finite 일 수 없습니다.

---

4. 주요 기여

1. 가상 멱영군 사례의 해결: 이 논문은 가상 멱영군의 그린 급수가 D-finite 이라는 추측에 대한 최초의 반례를 제공합니다.
2. 파크 - 소우쿠프 결과의 정제: 가상 멱영군에 대해 급수가 단순히 Rational 급수의 대각선이 아니거나 비계산 가능한 것이 아니라, 엄밀히 D-finite 이 아님을 증명함으로써 파크와 소우쿠프의 결과를 강화했습니다.
3. $SL_3(\mathbb{Z})$로의 확장: $vH$를$SL_3(\mathbb{Z})$에 매장시킴으로써, 비 D-finite 현상을 차원 3 의 특수 선형 군으로 확장했습니다 (이전에는 $m \geq 4$인 경우에만 알려짐).
4. 방법론적 발전: 이 논문은 승법 수열의 부분 단어 복잡도 기법을 멱영 설정에 성공적으로 적용하여, 멱영군에서의 표준 점근적 성장률이 일반적으로 D-finite 행동을 모방한다는 어려움을 극복했습니다.

---

5. 의의 및 향후 방향

• 이론적 영향: 이 결과는 "아름다운" 기하학적 군 (예: 멱영군) 이 항상 "아름다운" 생성 함수를 산출한다는 직관에 도전합니다. 군 구조의 산술적 성질 (특히 생성자 $t$와 헤이젠베르크 부분군 간의 상호작용) 이 코그로스 급수에서 혼란스러운 행동을 유발할 수 있음을 강조합니다.
• 미해결 문제:
  • 이산 헤이젠베르크 군 $H_3(\mathbb{Z})$: 논문은 여기서 사용된 생성자 ($t$) 의 여러 복사본을 추가하는 특정 트릭이 즉시 $H_3(\mathbb{Z})$ 자체에는 적용되지 않는다고 지적합니다. $H_3(\mathbb{Z})$로 결과를 확장하는 것은 여전히 열려 있고 중요한 과제입니다.
  • 점근적 빈도: 저자는 제곱 자유 수의 점근적 밀도를 이용한 대안적 증명은 $\pi^2$와 카탈란 상수 $G$가 $\mathbb{Q}$ 위에서 선형 독립이라는 증명되지 않은 가정에 의존할 것이라고 언급합니다.
• 광범위한 맥락: 이 결과는 D-finite 과 비 D-finite 급수 사이의 경계가, 아벨 군이나 멱영군에 "가까운" 군의 경우 특히 이전에 생각했던 것보다 더 복잡함을 시사합니다.

요약하자면, 보다르의 논문은 조합론적 군론, 수론 (승법 함수), 그리고 형식 언어 이론 간의 정교한 상호작용을 활용하여, 상대적으로 온순한 가상 멱영군의 세계에서도 그린 급수가 최대 복잡도를 보일 수 있음을 입증합니다.