A Generic Construction of $q$-ary Near-MDS Codes Supporting 2-Designs with Lengths Beyond $q+1$

논문 개요 및 기술적 요약

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

• NMDS 코드와 2-디자인의 중요성: 선형 코드 $C$ 와 그 쌍대 코드 $C^\perp$ 가 모두 거의 최대 거리 분해 가능 (AMDS) 인 경우, 이를 근사 최대 거리 분해 가능 (Near-MDS, NMDS) 코드라고 합니다. NMDS 코드는 조합론적 디자인, 유한 기하학, 암호학 등 다양한 분야에서 중요한 응용을 가지며, 특히 NMDS 코드가 $t$-디자인을 지지할 때 그 구조적 가치가 큽니다.
• 기존 연구의 한계: 2020 년 Ding 과 Tang 이 NMDS 코드가 2-디자인을 지지하는 첫 번째 무한족을 제시한 이후, 여러 연구가 이어졌으나, 모든 기존 구성은 코드 길이 $n$ 이 $q+1$ 이하인 경우로 제한되었습니다.
• 핵심 문제: MDS 추측에 따르면 $q$-ary MDS 코드의 최대 길이는 $q+1$ (일부 예외 제외) 입니다. 반면 NMDS 코드는 이론적으로 $q+1$ 을 초과할 수 있으나, $n > q+1$ 이면서 동시에 2-디자인을 지지하는 $q$-ary NMDS 코드의 구성은 매우 드물었습니다. 기존에 알려진 사례는 2 진법이나 3 진법에서 발견된 몇 가지 희귀한 (sporadic) 경우나 극단적인 (extremal) 코드에 국한되어 있었습니다.
• 연구 목표: $q+1$ 을 초과하는 길이를 가지면서도 2-디자인을 지지하는 일반적인 (generic) 구성 방법을 제시하는 것입니다.

2. 방법론 (Methodology)

저자들은 타원 곡선 코드 (Elliptic Curve Codes), 유한 아벨 군, 부분집합 합 (Subset Sums), 그리고 조합론적 디자인 간의 새로운 연결 고리를 활용하여 다음과 같은 구성을 제시합니다.

• 타원 곡선 코드의 활용:
  • $E/\mathbb{F}_q$ 를 타원 곡선으로 두고, 유리점 집합 $E(\mathbb{F}_q)$ 를 사용하여 길이가 $n = |E(\mathbb{F}_q)|$ 인 코드를 구성합니다.
  • Hasse-Weil 경계에 따라 $n$ 은 $q+1 \pm 2\sqrt{q}$ 범위에 위치할 수 있어, $n > q+1$ 인 경우를 자연스럽게 포착할 수 있습니다.
• 부분집합 합과 NMDS 성질의 연결:
  • 코드 $C(E, P, D)$ 가 NMDS 가 되기 위한 필요충분조건을 $E(\mathbb{F}_q)$ 군 내의 부분집합 합 문제로 변환했습니다.
  • 구체적으로, $Q_D$ 가 $E(\mathbb{F}_q)$ 의 특정 점일 때, $P \subset E(\mathbb{F}_q)$ 의 $k$-부분집합 중 합이 $Q_D$ 가 되는 경우의 수 $N(P, k, Q_D)$ 가 0 이면 MDS, 0 보다 크면 NMDS 가 됩니다.
• 2-디자인 생성 조건:
  • $E(\mathbb{F}_q) \cong \mathbb{Z}_p \oplus \mathbb{Z}_p$ (여기서 $p$ 는 홀수 소수) 인 구조를 가진 타원 곡선을 선택합니다.
  • 부분집합 합 이론 (Theorem 10, 13) 을 적용하여, $p \mid k$ 이고 $Q_D = \infty$ (무한점) 인 경우, 최소 가중치 코드의 지지 집합이 2-디자인을 이룬다는 것을 증명했습니다.
• 일반화된 Assmus-Mattson 정리의 적용:
  • 구성된 코드는 고전적인 Assmus-Mattson 정리의 조건을 만족하지 않지만, Tang, Ding, Xiong 이 제안한 일반화된 Assmus-Mattson 정리를 만족하여 모든 고정 가중치의 코드가 2-디자인을 지지함을 보입니다.

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

• 최초의 일반적 구성 (First Generic Construction):

  • $q+1$ 을 초과하는 길이 ($n=p^2$) 를 가지며 2-디자인을 지지하는 $q$-ary NMDS 코드의 첫 번째 무한족을 구성했습니다.
  • 구성 조건: $q$ 는 소수 멱 ($q \ge 7$), $p$ 는 홀수 소수이며, $\gcd(p^2-q-1, q)=1$, $p \mid q-1$, 그리고 $-2\sqrt{q} \le p^2-q-1 \le 2\sqrt{q}$ 를 만족해야 합니다.
  • 이 조건 하에서 매개변수 $[p^2, 2k, p^2-2k]$ ($p \mid k$) 를 갖는 NMDS 코드가 존재하며, 이는 $n=p^2 > q+1$ 입니다.

• 디자인 파라미터의 명시적 도출:

  • 구성된 코드의 최소 가중치 코드가 지지하는 2-디자인의 파라미터 $\lambda$ 와 쌍대 코드의 $\lambda^\perp$ 를 명시적인 공식으로 유도했습니다.
  • 예시: $q=7, p=3$ 인 경우, $[9, 6, 3]$ NMDS 코드가 구성되며, 이는 2-(9, 3, 1) 디자인 (Steiner triple system $S(2,3,9)$) 을 지지합니다.

• 가중치 분포 (Weight Distribution) 결정:

  • 구성된 NMDS 코드와 그 쌍대 코드의 가중치 분포를 부분집합 합 이론과 NMDS 코드의 점화식을 이용하여 완전히 결정했습니다.
  • 모든 가중치 $w$ ($d \le w \le n$) 에 대해 $A_w > 0$ 임을 증명하여, 코드가 다양한 가중치에서 디자인을 지지함을 보였습니다.

• 풍부한 파라미터 집합:

  • 컴퓨터 탐색을 통해 $p < 2000$ 범위 내에서 38 개의 유효한 $(q, p)$ 매개변수 쌍을 찾았으며, 이를 통해 $q+1$ 을 훨씬 초과하는 길이 (예: $n=4489, 6241, \dots$) 를 가진 NMDS 코드들의 무한족 존재를 추론했습니다.

4. 의의 및 결론 (Significance)

• 이론적 돌파구: NMDS 코드의 길이 제한 ($q+1$) 을 넘어서는 2-디자인을 지지하는 코드의 존재성을 처음으로 일반화하여 증명했습니다. 이는 기존에 희귀한 예시들만 존재했던 영역을 무한족으로 확장한 것입니다.
• 새로운 디자인의 발견: 고전적인 Assmus-Mattson 정리를 만족하지 않는 새로운 2-디자인의 무한족을 제공하여, 조합론적 디자인 이론의 지평을 넓혔습니다.
• 구체적 구성 가능성: 타원 곡선의 유리점 군 구조와 부분집합 합 이론을 결합한 구체적인 구성 알고리즘을 제시하여, 실제 암호학 및 통신 시스템에 적용 가능한 새로운 NMDS 코드 계열을 제공합니다.
• 미래 연구 방향: 다양한 유리점 군 구조를 가진 타원 곡선을 활용하면 더 높은 $t$-디자인이나 다른 파라미터를 가진 디자인을 얻을 수 있을 것으로 기대되며, 이는 향후 연구의 중요한 방향이 될 것입니다.

이 논문은 대수기하학 코드, 조합론적 디자인, 그리고 유한군 이론을 융합하여 선형 코드 이론의 중요한 난제를 해결한 획기적인 연구로 평가됩니다.