Equivalence of Families of Polycyclic Codes over Finite Fields

기술적 요약: 유한체 위의 다주기 코드 계열의 동치성

문제 제기
본 논문은 유한체 $\mathbb{F}_q$ 위의 다주기 코드 계열의 분류와 동치성에 대해 다룬다. 순환 코드와 상수 순환 코드는 몫환 $\mathbb{F}_q[x]/\langle x^n - \lambda \rangle$ 내의 아이디얼로 잘 이해되고 있지만, 다주기 코드는 임의의 비영 다항식 $f(x)$에 대한 $\mathbb{F}_q[x]/\langle f(x) \rangle$ 내의 아이디얼로 이러한 구조를 일반화한다. 부호 이론의 핵심적인 과제는 최적의 파라미터 (길이 $n$, 차원 $k$, 최소 거리 $d$) 를 갖는 코드를 구성하는 것이다. 대규모 파라미터에 대한 최적 코드의 완전한 컴퓨터 탐색은 계산적으로 처리 불가능하므로, 저자들은 다주기 코드를 동치 계열로 체계적으로 조직화하여 탐색 공간을 축소하는 것을 목표로 한다. 구체적으로, 본 논문은 두 환경 공간 (코드를 정의하는 몫환) 이 등거리 사상이 될 때를 규명하여, 연구자들이 이러한 동치 계열의 대표자들로 탐색을 제한할 수 있도록 한다.

방법론
저자들은 상수 순환 코드에 대해 이전에 정의된 $n$-동치 개념을 다주기 코드의 더 넓은 맥락으로 확장한다. 방법론은 세 단계로 진행된다:

1. 동치 정의: 다항식 $f(x) = x^n - \vec{a}(x)$와 $g(x) = x^n - \vec{b}(x)$에 연관된 두 다주기 코드 계열이 $n$-동치라고 정의되려면, $\alpha \in \mathbb{F}_q^*$가 존재하여 사상 $\Phi_\alpha: f(x) \mapsto f(\alpha x)$가 해밍 거리를 보존하는 $\mathbb{F}_q$-대수 동형사상을 몫환 $\mathbb{F}_q[x]/\langle g(x) \rangle$와 $\mathbb{F}_q[x]/\langle f(x) \rangle$ 사이에 유도해야 한다.
2. 대수적 특성화: 본 논문은 이 동치에 대한 필요충분조건을 유도한다. 이는 $\mathbb{F}_q$ 내의 이항식과 삼항식 방정식의 근을 분석하는 것을 포함한다. 주요 도구는 다음과 같다:
   • $\gcd(x^n - a, x^m - b)$의 차수와 $x^n - a = 0$의 해 개수에 관한 보조정리.
   • 동치 다항식의 계수 벡터를 관련시키기 위해 슈어 곱 (성분별 곱셈) 사용.
   • $\mathbb{F}_q^* \times \mathbb{F}_q^*$ 내 원시 요소의 거듭제곱에 의해 생성된 순환 부분군에 대한 군론적 분석.
3. 전문화와 일반화:
   • $\ell$-삼항식 코드: 연구는 먼저 $x^n - a_\ell x^\ell - a_0$ (단, $0 < \ell < n$) 형태의 삼항식에 연관된 코드에 초점을 맞춘다. 저자들은 동치 계열의 개수에 대한 명시적 공식을 유도하고, 삼항식 코드가 표준형 $x^n - x^\ell - 1$과 동치인 조건을 도출한다.
   • $p\ell$-삼항식 코드: 길이 $n = p^\ell + r$ (단, $p$는 $\mathbb{F}_q$의 표수) 인 코드에 대한 구체적인 분석이 수행되며, 아르틴 - 슈라이어 다항식과 트레이스 함수의 성질을 이용하여 기약 인수분해를 결정한다.
   • 일반 다주기 코드: $m$개의 비영 항을 갖는 벡터 $\vec{a}$로 정의된 임의의 다주기 코드로 결과가 일반화된다.

주요 기여 및 결과

• $(n, \ell)$-동치 정의: 본 논문은 $\ell$-삼항식 코드에 대한 동치 관계를 공식화한다. 두 계수 쌍 $(a_0, a_\ell)$과 $(b_0, b_\ell)$이 동치일 필요충분조건은 다항식 $a_0 x^n - b_0$와 $a_\ell x^{n-\ell} - b_\ell$이 $\mathbb{F}_q^*$ 내 공통 근을 갖는 것임을 증명한다.
• 동치 계열 계수: 저자들은 $\ell$-삼항식 코드에 대한 $n$-동치 계열의 개수에 대한 명시적 공식을 제공한다:
  $$N_{(n,\ell)} = (q-1) \gcd(q-1, n, \ell)$$
  $m$개의 비영 계수를 갖는 일반 다주기 코드의 경우, 계열의 개수는 다음과 같다:
  $$N = \frac{(q-1)^m}{\text{lcm}_{0 \le j \le m-1} \left( \frac{q-1}{\gcd(n-i_j, q-1)} \right)}$$
• 표준형으로의 축소:
  • $\gcd(n, n-\ell) = 1$이면, 임의의 $\ell$-삼항식 코드 계열이 다항식 $x^n - x^\ell - 1$과 연관된 계열과 동치임이 증명된다.
  • $\gcd(n, n-\ell) \neq 1$인 경우, 본 논문은 모든 동치 계열을 포괄하는 특정 대표자 (원시 요소 $\xi$의 거듭제곱 포함) 를 식별한다.
• 특정 삼항식의 인수분해: 본 논문은 $x^{p^\ell+1} - x^{p^\ell} - 1$ 및 $x^{p^\ell+s} - x^{p^\ell} - 1$ 형태의 삼항식 인수분해를 분석한다. 이러한 다항식이 기약 인수 (종종 아르틴 - 슈라이어 다항식 $x^p - x - \beta$ 포함) 로 분해되는 조건을 확립하여, 이러한 계열의 코드에 대한 가능한 생성 다항식에 직접적인 정보를 제공한다.
• 최적 코드 구성: 식별된 동치 계열의 대표자로 탐색을 제한함으로써, 저자들은 여러 최적 다주기 코드 예시를 구성한다. 주목할 만한 예시는 다음과 같다:
  • $\mathbb{F}_3$ 위의 $3\ell$-삼항식 코드에서 유도된 $[27, 3, 18]_3$ 코드와 $[81, 3, 55]_3$ 코드.
  • 알려진 경계 (예: 그리스머 경계) 와 일치하거나 도달하는 파라미터를 갖는 $\mathbb{F}_9$ 및 $\mathbb{F}_4$ 위의 최적 코드.

의의 및 주장
본 논문은 다주기 코드를 조직화하고 분류하기 위한 체계적인 프레임워크를 제공하는 데에 주요한 의의가 있다고 주장한다. 동치에 대한 명시적 기준을 수립함으로써, 이 연구는 최적 파라미터를 갖는 코드를 탐색하는 복잡성을 줄인다. 모든 가능한 계수 조합을 조사하는 대신, 연구자들은 각 동치 계열에 대한 유한한 대표자 집합에 집중할 수 있다.

또한, 저자들은 다주기 코드에서 이중성을 연구함에 있어 환경 공간의 동치성을 이해하는 것이 중요하다고 지적한다. 다주기 코드의 이중 코드가 반드시 동일한 환경 공간에 관해 다주기 코드가 되는 것은 아니지만, 종종 다른 공간에서 유래한 코드와 동치인 경우가 많기 때문에, 이러한 분류는 이중성에 관한 향후 이론적 결과의 기초를 제공한다. 본 논문은 이러한 결과들이 상수 순환 코드에서의 성공적인 동치 관계 적용을 더 일반적이고 복잡한 다주기 코드 영역으로 확장하여, 근사 최적 파라미터를 갖는 무한한 코드 계열을 구성하는 통로를 제공한다고 결론지었다.