$2$-quasi-perfect Lee codes and abelian Ramanujan graphs: a new construction and relationship

논문 요약: 2-준완전 리 코드와 아벨 람마누잔 그래프

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

• 배경: 리 거리 (Lee distance) 하에서 오류 정정 부호인 '리 코드 (Lee code)'는 코딩 이론, 정수론, 대수기하학, 조합론의 교차점에 위치합니다. 완벽한 리 코드 (Perfect Lee codes) 의 존재성은 골롬 - 웰치 (Golomb-Welch) 추측에 의해 제한적이므로, 연구의 초점은 '준완전 (Quasi-perfect)' 또는 '거의 완벽한' 부호 구성으로 이동했습니다.
• 문제:
  • 임의의 큰 길이를 갖는 2-준완전 (2-quasi-perfect) 리 부호를 명시적으로 구성하는 것은 여전히 어려운 난제입니다.
  • 기존 구성 (Camarero-Martínez, Mesnager-Tang-Qi 등) 은 특정 다항식의 해 집합에 기반하여 이루어졌으나, 이러한 대수적 구조가 왜 그러한 부호를 생성하는지에 대한 통합된 이론적 틀이 부재했습니다.
  • 아벨 람마누잔 그래프 (Abelian Ramanujan graphs) 는 스펙트럼 갭 (spectral gap) 측면에서 최적의 의사무작위성을 가지며, 이는 리 부호의 덮기 반경 (covering radius) 에 유리한 작은 지름을 가집니다. 그러나 모든 아벨 람마누잔 그래프가 최적의 2-준완전 부호를 생성하는지는 명확하지 않았습니다.

2. 방법론 (Methodology)

저자는 다음과 같은 두 가지 주요 접근법을 통해 문제를 해결했습니다.

1. 새로운 명시적 구성 (New Explicit Construction):

   • 유한체 $F_q$ ($q=p^k, p \ge 5$) 의 곱셈군 $F_q^*$ 에서 정의된 집합 $H_q = \{(a, a^3) \mid a \in F_q^*\}$ 를 생성 집합 (generating set) 으로 사용하는 선형 부호를 구성했습니다.
   • 이 부호는 $F_q^2$ 의 가법군 위에서 정의된 케일리 그래프 (Cayley graph) 와 밀접하게 연관되어 있습니다.
   • 대수기하학 (Hasse-Weil 경계, 절대 기약성 등) 을 활용하여 이 부호가 2-준완전 조건을 만족함을 증명했습니다.

2. 이론적 통합 (Theoretical Unification):

   • 기존 Mesnager-Tang-Qi (MTQ) 가 구성한 2-준완전 리 부호들을 잘 알려진 아벨 람마누잔 그래프인 Li's graphs (리 그래프) 와 Finite Euclidean graphs (유한 유클리드 그래프) 와 연결했습니다.
   • MTQ 부호들이 사실은 특정 이차 형식 (quadratic form) 에 의해 정의된 유한 유클리드 그래프의 생성 집합에서 비롯됨을 보임으로써, 기존 구성들을 하나의 통합된 프레임워크로 설명했습니다.

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

가. 새로운 2-준완전 리 부호의 구성 (Theorem 4)

• 구성: $p \ge 5$ 인 소수이고 $q=p^k \ge 14$ 일 때, 생성 집합 $H_q = \{(a, a^3) \mid a \in F_q^*\}$ 로부터 유도된 선형 부호 $C(F_q^2, H_q)$ 를 제안했습니다.
• 성능: 이 부호는 길이 $n = \frac{q-1}{2}$, 차원 $k = \frac{q-1}{2} - 2k$ 인 2-준완전 $p$-진 리 부호입니다.
• 특징:
  • 이 부호는 Forey et al. [7] 이 발견한 '아벨 거의 람마누잔 그래프'와 연결되어 있으며, 기존에 알려진 MTQ 부호들과는 다른 대수적 구조를 가집니다.
  • 특히 $p \equiv 1, 7 \pmod{12}$ 인 소수에 대해서는 새로운 파라미터를 제공합니다.
  • 증명 핵심: $H_q$ 의 2-합집합 (sumset) 크기가 정확히 계산되고, 3-합집합이 전체 공간 $\Gamma$ 를 덮는다는 것을 대수기하학적 곡선 (타원곡선 등) 의 점 개수 추정 (Hasse-Weil bound) 을 통해 증명했습니다.

나. MTQ 부호와 아벨 람마누잔 그래프의 통합 (Section 5)

• Li's Graphs 연결: MTQ 부호 중 $H_+$ (노름이 1 인 원소 집합) 를 사용하는 경우, 이는 Winnie Li 가 정의한 Li's graph (Cayley graph over $F_{q^2}$ with norm 1) 와 동일함을 보였습니다.
• 유한 유클리드 그래프 연결: MTQ 부호의 다른 경우 ($H_-$) 와 모든 비퇴화 이차 형식 $Q$ 에 의해 정의된 부호는 유한 유클리드 그래프와 동형임을 증명했습니다.
• 통합적 관점: Proposition 18 을 통해, 모든 비퇴화 이차 형식 $Q$ 에 대한 부호 $C(F_q^2, E_Q)$ 는 좌표 치환 및 부호 변경을 통해 MTQ 부호의 두 가지 기본 형태 ($H_+$ 또는 $H_-$) 중 하나로 귀결됨을 보였습니다. 이는 기존 구성들이 사실은 유한 유클리드 그래프의 특수한 경우임을 규명했습니다.

다. 그래프 이론적 통찰

• 제안된 부호들과 관련된 케일리 그래프들은 (almost) Ramanujan 그래프입니다.
• 역설적 발견: 2-준완전 부호는 매우 엄격한 구조적 조건 (Lemma 2) 을 요구하지만, 이를 생성하는 그래프들은 스펙트럼적으로 무작위 그래프와 구별되지 않는 (semicircle distribution) 강한 의사무작위성을 가집니다. 즉, 스펙트럼적 무작위성 (global) 이 국소적 구조적 규칙성 (local) 을 배제하지 않는다는 흥미로운 이분법을 제시했습니다.

4. 의의 및 결론 (Significance)

1. 이론적 통합: 2-준완전 리 부호의 다양한 구성들을 아벨 람마누잔 그래프 (Li's graphs, Finite Euclidean graphs) 의 관점에서 통합하여 설명하는 새로운 이론적 틀을 제시했습니다.
2. 새로운 구성: 임의의 큰 길이를 갖는 새로운 2-준완전 리 부호의 무한한 가족을 명시적으로 구성하여, 기존에 존재하던 구성들의 한계를 극복했습니다.
3. 학제간 연결: 코딩 이론 (리 부호), 정수론 (유한체, 노름), 대수기하학 (곡선의 점), 그리고 스펙트럼 그래프 이론 (람마누잔 그래프) 간의 깊은 연관성을 규명했습니다.
4. 미래 전망: 아벨 (almost) 람마누잔 그래프가 새로운 준완전 리 부호의 생성 집합을 제공할 수 있는지에 대한 연구 방향을 제시하며, 스펙트럼 특성과 부호의 구조적 성질 간의 관계를 심화 연구할 필요성을 강조했습니다.

이 논문은 코딩 이론의 오랜 난제 중 하나인 2-준완전 리 부호의 구성 문제를 해결함과 동시에, 그래프 이론과의 깊은 연관성을 통해 해당 분야의 이론적 기반을 확고히 했다는 점에서 중요한 의의를 가집니다.