Expanding groups with large diameter

논문 요약: 대형 지름을 가진 확장 군 (Expanding Groups with Large Diameter)

저자: Sean Eberhard, Luca Sabatini
주제: 유한 군의 생성 집합 (generating set) 선택에 따른 카이레이 그래프 (Cayley graph) 의 스펙트럼 갭 (spectral gap) 과 지름 (diameter) 간의 의존성 연구.

1. 연구 배경 및 문제 제기

• 배경: 무한 군의 경우, 생성 집합의 선택에 관계없이 성장 유형, 끝의 개수, 쌍곡성 (hyperbolicity), amenability, 성질 (T) 등 여러 중요한 성질이 불변입니다. 그러나 유한 군의 열 (sequence) 에서는 상황이 다릅니다.
• 기존 연구: Alon, Lubotzky, Wigderson (1986) 은 특정 유한 군이 한 생성 집합에 대해서는 확장자 (expander) 가 되지만 다른 생성 집합에 대해서는 그렇지 않음을 보였습니다. 또한 Kassabov 등은 대칭군과 거의 모든 비가환 유한 단순군이 적절한 생성 집합에 대해 확장자임을 증명했습니다.
• Pyber-Szabó 의 질문 (2013): 만약 유한 군의 열 $(G_n)$ 이 어떤 유계 크기 (bounded-size) 의 생성 집합 $X_n$ 에 대해 확장자 (expander) 라면, 임의의 다른 생성 집합 $Y_n$ 에 대해서도 지름이 다항 로그 (polylogarithmic), 즉 $O((\log |G_n|)^C)$ 이하로 제한되는가?
  • 이는 "다항 로그 지름이 군의 고유한 성질인가?"라는 질문과 연결됩니다.
• 목표: 이 논문은 위 질문에 대해 부정적인 답변을 제시하며, 확장자 성질을 가진 생성 집합이 존재함에도 불구하고, 다른 생성 집합에 대해서는 초다항 로그 (super-polylogarithmic) 혹은 지수적으로 큰 지름을 가질 수 있음을 증명합니다.

2. 주요 결과 (Theorem 1.2)

저자들은 다음과 같은 정리를 증명합니다:

• 상수 $\delta, \varepsilon > 0$와 유한 군의 열 $(G_n)$ ($|G_n| \to \infty$) 이 존재하여, 유계 크기의 생성 집합 $X_n, Y_n \subseteq G_n$ 을 가집니다.
  • (a) $\text{Cay}(G_n, X_n)$ 은 $\varepsilon$-확장자 (expander) 입니다. (즉, 스펙트럼 갭이 양수입니다.)
  • (b) $\text{Cay}(G_n, Y_n)$ 의 지름은 $\text{diam} \ge \exp(\delta \sqrt{\log |G_n|})$ 입니다.
• 이는 지름이 매우 크더라도 (지수적 크기), 군은 여전히 확장자일 수 있음을 의미합니다.

3. 구성 방법론 (Construction)

논문에서 제시된 군 $G$ 와 생성 집합 $X, Y$ 의 구체적인 구성은 다음과 같습니다.

• 군 구조:

  • $G = V_0 \rtimes S_n$ (반직곱, semidirect product).
  • $V = \mathbb{F}_p^n$ (유한체 위의 벡터 공간).
  • $V_0 \subset V$: $V$ 의 '삭제된 치환 모듈 (deleted permutation module)', 즉 모든 성분의 합이 0 인 부분공간 ($\mathbf{1}^\perp$). 차원은 $n-1$.
  • $S_n$: $n$ 차 대칭군.
  • 소수 $p$ 는 $n$ 에 대해 지수적으로 큽니다 ($p \sim e^{cn}$).
  • 군의 크기: $|G| = p^{n-1} n! \approx \exp(cn^2)$.

• 생성 집합:

  • 두 생성 집합 $X, Y$ 모두 $\{v\} \cup T$ 형태입니다. 여기서 $v \in V_0$ 이고 $T \subset S_n$ 입니다.
  • 나쁜 생성 집합 $Y$:
    • $v = (1, -1, 0, \dots, 0)$ (단순한 선택).
    • $T = \{(1, 2), (1, 2, \dots, n)\}$ (대칭군의 표준 생성 집합).
    • 이 경우 $V_0$ 내에서의 이동이 매우 느려, 지름이 $p$ 에 비례하여 매우 커집니다 ($\text{diam} \ge p \sim e^{cn}$).
  • 좋은 생성 집합 $X$:
    • $T$ 는 Kassabov 의 결과에 따라 $S_n$ 을 확장하는 유계 크기 집합을 선택합니다.
    • 핵심: $v \in V_0$ 를 적절히 선택하여 전체 군 $G$ 가 확장자가 되도록 합니다. 저자들은 무작위적으로 선택된 $v$가 이 조건을 만족함을 보입니다.

4. 증명 방법론 및 핵심 기술

4.1. 확장성 증명 (Theorem 1.2(a))

• Kazhdan 상수 활용: 스펙트럼 갭과 Kazhdan 상수 ($\kappa$) 의 관계를 이용합니다.
• 반직곱의 확장성: Proposition 3.4 를 통해 $G = N \rtimes H$ 의 Kazhdan 상수가 $N$ 과 $H$ 의 Kazhdan 상수로 하향 평가될 수 있음을 보입니다.
  • $\kappa(G, X) \ge C \cdot \kappa(V_0, vS_n) \cdot \kappa(S_n, T)$.
  • $T$ 는 $S_n$ 에 대해 확장자이므로 $\kappa(S_n, T)$ 는 양수입니다.
  • 따라서 $V_0$ 에서 $vS_n$ 에 대한 갭을 확보하는 것이 핵심입니다.

4.2. 지수합 (Exponential Sums) 추정 (Theorem 1.3)

• $V_0$ 의 확장성은 $v$ 와 $w$ 에 대한 **치환형 지수합 (permutational exponential sum)**의 크기를 제한하는 문제로 귀결됩니다.

• 목표: 모든 비상수 벡터 $w \in V$ 에 대해 다음이 성립하는 $v$ 를 찾는 것:
  $$\left| \frac{1}{n!} \sum_{\sigma \in S_n} e_p(\langle v, w^\sigma \rangle) \right| \le 1 - \varepsilon$$
  (여기서 $e_p(x) = \exp(2\pi i x/p)$).

• 확률론적 접근 (Probabilistic Method):

  • $v$ 를 $V_0$ 에서 균일하게 무작위 선택합니다.
  • Lemma 4.1 (Hoeffding 부등식): $w$ 가 단순한 형태 (support-one) 일 때, 지수합이 1 에 가까울 확률은 매우 낮음을 보입니다. $p$ 가 매우 크더라도 ($p \le e^{\delta n}$), 합집합 법칙 (union bound) 을 적용할 수 있습니다.
  • Lemma 4.2 (결정론적 스위칭): 모든 $w$ 에 대해 성립하게 하기 위해, Cauchy-Schwarz 부등식을 기반으로 한 **스위칭 논증 (switching argument)**을 사용합니다.
    • 임의의 $w$ 에 대해, $w$ 와 $w^\tau$ (전치) 를 비교하여 $| \lambda_{v,w} |^2$ 를 $| \lambda_{v,u} |^2$ (단순한 형태) 와 관련시킵니다.
    • 이를 통해 복잡한 $w$ 에 대한 문제를 단순한 $u$ 에 대한 문제로 환원시킵니다.
  • 결과: $p$ 가 $n$ 에 대해 지수적으로 크더라도, 무작위 $v$ 가 조건을 만족할 확률이 1 에 수렴함을 보임으로써 존재성을 증명합니다.

5. 의의 및 기여

1. Pyber-Szabó 질문의 부정적 답변: 확장자 성질 (spectral gap) 이 있다고 해서 모든 생성 집합에 대해 지름이 작아지는 것은 아님을 명확히 보였습니다. 즉, "다항 로그 지름"은 군의 고유한 성질이 아닙니다.
2. 새로운 반례 구성: Alon-Lubotzky-Wigderson 과 Kassabov 의 이전 작업과 유사한 구조 ($C_p \rtimes S_n$ 형태) 를 사용하되, 소수 $p$ 를 $n$ 에 대해 지수적으로 크게 설정함으로써 새로운 현상을 포착했습니다.
3. 기술적 혁신:
   • $p$ 가 매우 클 때 발생할 수 있는 합집합 법칙의 실패 문제를, Cauchy-Schwarz 기반의 스위칭 논증과 확률론적 방법을 결합하여 해결했습니다.
   • 이는 대수적 조합론과 확률론적 방법의 강력한 결합을 보여줍니다.
4. 개방된 문제:
   • (b) 조건에서 지름의 최적 상한 (optimal bound) 은 무엇인가? (현재는 $\exp(\delta \sqrt{\log |G|})$ 정도).
   • $\varepsilon(\delta)$ 의 정확한 함수 형태에 대한 연구가 필요합니다.

6. 결론

이 논문은 군의 생성 집합 선택이 그래프의 기하학적 성질 (지름) 에 얼마나 민감하게 영향을 미치는지를 극단적인 예시를 통해 보여주었습니다. 확장자 성질은 생성 집합에 의존적일 수 있으며, 매우 큰 지름을 가진 확장자 군을 구성할 수 있음을 증명함으로써, 군의 확장과 지름에 대한 기존 통념을 도전하고 새로운 연구 방향을 제시했습니다.