Using nonassociative algebras to classify skew polycyclic codes up to isometry and equivalence

논문 제목: 동형사상과 등거리사상 (Isometry) 을 통한 비결합 대수를 이용한 왜곡 다주기 부호 (Skew Polycyclic Codes) 분류
저자: Susanne Pumplün

이 논문은 **왜곡 다주기 부호 (Skew Polycyclic Codes)**의 기존 분류 체계의 한계를 극복하고, **비결합 대수 (Nonassociative Algebra)**의 구조를 활용하여 더 정교하고 엄격한 분류 기준을 제시합니다. 특히, 부호의 성능 파라미터 (길이, 차원, 해밍 거리) 를 보존하는 새로운 동치 (Equivalence) 와 등거리사상 (Isometry) 의 정의를 도입하여 기존에 중복되었던 부호 클래스를 통합하고, 새로운 부호 탐색의 효율성을 높이는 것을 목표로 합니다.

1. 연구 문제 (Problem)

• 기존 분류의 한계: 기존 왜곡 다주기 부호 (또는 왜곡 상수주기 부호) 에 대한 분류 연구는 주로 결합 대수 (Associative Algebra) 구조에 기반하거나, 자동사상 (Automorphism) 을 항등사상 (Identity) 으로 제한하는 '첸 동치 (Chen Equivalence)'와 같은 제한된 정의에 의존해 왔습니다.
• 중복 분류: 이러한 제한된 정의는 실제로는 동일한 성능을 가지지만, 정의상 다른 클래스로 분류되어 중복되는 부호를 생성하게 합니다. 이는 최적의 부호를 찾기 위한 탐색 공간을 불필요하게 확장시킵니다.
• 비결합 구조의 간과: 많은 왜곡 다주기 부호는 비결합 대수 구조 (Petit Ring) 를 갖는 환경에서 정의되는데, 기존 연구들은 이를 결합 대수로만 간주하거나 비결합성을 충분히 활용하지 못했습니다.

2. 방법론 (Methodology)

저자는 다음과 같은 방법론적 혁신을 통해 문제를 해결합니다:

1. 비결합 환경 링 (Petit Ring) 의 도입:

   • 왜곡 다주기 부호를 생성하는 다항식 $f(t)$로 나눈 몫환 $R/Rf$를 **비결합 단위원을 가진 링 (Petit Ring)**으로 간주합니다. $f$가 양쪽 이상 (two-sided ideal) 을 생성하지 않는 경우, 이 링은 비결합적이지만 여전히 링 구조를 가집니다.
   • 부호를 이 비결합 링의 주 왼쪽 아이디얼 (Principal Left Ideal) 로 재정의합니다.

2. 새로운 동치 및 등거리사상 정의:

   • 등거리사상 (Isometry): 두 부호 클래스가 해밍 가중치 (Hamming weight) 를 보존하는 링 동형사상 (Ring Isomorphism) 을 통해 연결될 때, 이를 '등거리사상'으로 정의합니다.
   • 동치 (Equivalence): 이 동형사상이 차수 $k=1$인 경우 (즉, $t \to \alpha t$ 형태) 를 '동치'로 정의합니다.
   • 일반화된 매핑: 기존 연구가 $t \to \alpha t$ (1 차) 로만 제한했던 것과 달리, $t \to \alpha t^k$ (고차) 형태를 포함하는 단항식 동형사상 (Monomial Isomorphism) $G_{\tau, \alpha, k}$를 고려합니다. 여기서 $\tau$는 계수환 $S$의 자동사상, $\alpha$는 가역원, $k$는 정수입니다.
   • 조건: 이러한 사상이 존재하려면 $\tau$가 $\sigma$와 교환 가능해야 하며, $k$와 $n$ (부호 길이) 및 $\sigma$의 위수 $m$ 사이에 특정 조건 ($k \equiv 1 \pmod m$, $\gcd(k, n)=1$ 등) 을 만족해야 합니다.

3. 대수적 분석:

   • 유한체 (Finite Fields) 와 유한 체인 링 (Finite Chain Rings), 갈루아 링 (Galois Rings) 에 대해 구체적인 동치 클래스의 수를 계산하고, 비결합 링과 결합 링 사이의 관계를 규명합니다.

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

A. 이론적 기여

• 더 엄격한 분류 체계: 기존의 '첸 동치'보다 더 넓은 범위의 동형사상을 허용함으로써, 실제로는 동일한 부호를 다른 클래스로 분류하는 오류를 수정하고 분류 클래스의 수를 줄였습니다.
• 비결합 대수 활용: 부호의 생성 다항식 $f$가 양쪽 이상을 생성하지 않는 경우에도, 비결합 Petit 링의 구조를 통해 부호를 체계적으로 분류할 수 있음을 보였습니다.
• 성능 파라미터 보존 증명: 제안된 등거리사상과 동치는 부호의 길이, 차원, 해밍 거리를 보존함을 증명했습니다.

B. 주요 정리 (Theorems)

• 정리 5.1 (동치 조건): 두 왜곡 다주기 부호 클래스가 동치일 필요충분조건은, $\tau \in \text{Aut}(S)$와 $\alpha \in S^\times$가 존재하여 계수 $a_i, b_i$가 특정 노름 (Norm) 식을 만족하는 것입니다.
  $$\tau(a_i) = N^\sigma_{n-i}(\sigma^i(\alpha)) b_i$$
• 정리 5.2 (등거리와 동치의 일치): 유한체 $K$에서 $m \ge n-1$이고 $f$가 양쪽 이상을 생성하지 않을 때, 동치 (Equivalence) 와 등거리사상 (Isometry) 은 일치합니다. 이는 고차 동형사상 ($k>1$) 이 존재하지 않음을 의미합니다.
• 정리 8.5, 8.7 (체인 링에서의 조건): 유한 체인 링 (Finite Chain Rings) 에서는 $k>1$인 등거리사상이 존재하기 위해 매우 엄격한 조건 ($k \equiv 1 \pmod m$, $m|n$ 등) 을 만족해야 하며, 대부분의 경우 $k=1$인 동치만 존재합니다.

C. 계산 결과 및 예시

• 클래스 수 감소: 유한체와 갈루아 링에 대한 예시 (Section 6, 8) 를 통해, 제안된 '동치' 개념을 적용하면 기존 '첸 동치'보다 훨씬 적은 수의 부호 클래스가 생성됨을 보였습니다.
  • 예: $F_{p^2}$에서 $n=2$인 경우, 기존에는 4 개의 클래스로 분류되었으나, 새로운 정의 하에서는 3 개 (또는 그 이하) 로 통합됩니다.
• 생성 다항식 관계 규명: 동치인 부호들의 생성 다항식이 어떻게 서로 변환되는지 명확한 수식을 제시하여, 한 부호의 생성자를 통해 동치인 다른 부호의 생성자를 쉽게 유도할 수 있게 했습니다.

4. 의의 및 중요성 (Significance)

1. 양자 오류 정정 부호 (QECC) 탐색 최적화:

   • 왜곡 다주기 부호는 Gray 맵과 CSS 구성을 통해 양자 오류 정정 부호를 만드는 데 핵심적으로 사용됩니다.
   • 본 연구는 중복된 부호 파라미터를 제거하고, **비동치 (Non-equivalent)**인 부호들만 대상으로 탐색을 수행할 수 있게 하여, 더 좋은 성능을 가진 양자 부호를 발견하는 효율성을 극대화합니다.

2. 이론적 통합:

   • 기존에 분리되어 있던 상수주기 부호, 다주기 부호, 왜곡 부호에 대한 분류 이론을 비결합 대수라는 통일된 프레임워크로 통합했습니다.
   • 특히, 비결합 링에서의 동형사상 이론을 부호 이론에 적용한 선구적인 연구입니다.

3. 실용적 도구 제공:

   • 두 부호가 동치인지 판별할 수 있는 명확한 대수적 조건 (계수 간의 노름 관계 등) 을 제공하여, 소프트웨어 기반의 부호 생성 및 분류 알고리즘에 직접 적용 가능한 기준을 마련했습니다.

요약

이 논문은 **비결합 대수 (Petit Ring)**의 구조를 활용하여 왜곡 다주기 부호의 분류 체계를 재정립했습니다. 기존에 제한적이었던 동치 정의를 확장하여 해밍 거리를 보존하는 더 일반적인 동형사상을 도입함으로써, 중복된 부호 클래스를 제거하고 분류의 정밀도를 높였습니다. 이는 유한체 및 유한 체인 링에서의 부호 분류를 간소화하며, 특히 양자 오류 정정 부호 개발을 위한 효율적인 탐색 전략을 제공합니다.