Projective systems and bounds on the length of codes of non-zero defect

기술 요약: 사영 체계와 비제로 결함(Non-Zero Defect) 부호의 길이에 대한 상한

문제 정의
본 논문은 고정된 싱글톤 결함(Singleton defect) $s = n - k + 1 - d > 0$을 갖는 선형 $[n, k, d]_q$ 부호의 최대 길이 $n$을 결정하는 코딩 이론의 근본적인 문제를 다룬다. 결함이 0인 경우($s=0$, 최대 거리 분리(MDS) 부호)는 "MDS 부호에 관한 주요 추측(Main Conjecture on MDS codes)" 하에 잘 연구되어 왔으나, 결함이 0이 아닌 경우(Almost-MDS 또는 일반적으로 $A^s$MDS)의 상한은 덜 통합되어 있다. 구체적으로, 저자들은 $m_s(k, q)$ (비퇴화 $A^s$MDS 부호의 최대 길이)와 $m_s^t(k, q)$ (쌍대 부호가 추가적으로 $A^t$MDS인 경우의 최대 길이) 파라미터를 조사한다. 문헌에서 확인된 핵심적인 간극은 충분한 길이를 가진 코드에 대해 $A^s$MDS 부호가 반드시 $A^s$MDS 쌍대 부호를 갖는지(즉, $N^s$MDS 부호인지)에 대한 조건이다.

방법론
저자들은 선형 부호를 $PG(k-1, q)$ 내의 유한 점 집합(multisets of points)으로 나타내는 Tsfasman과 Vlăduţ이 제안한 사영 체계(projective systems) 프레임워크를 채택한다. 이러한 기하학적 관점은 코딩 이론적 파라미터를 점 집합, 아크(arcs), 플랫(flats)의 성질로 변환할 수 있게 한다.

• 기하학적 변환: $[n, k, d]_q$ 부호는 어떤 초평면(hyperplane)도 $n-d$개 이상의 점을 포함하지 않는 $PG(k-1, q)$내의$n$개 점의 멀티셋$G$로 간주된다. 싱글톤 결함$s$는 초평면에 포함되는 최대 점의 개수가$k+s-1$임을 의미한다.
• 몫 기하학(Quotient Geometry, 단축): 본 논문은 코드 단축(shortening)의 기하학적 형태를 활용한다. 저자들은 주 공간(ambient space) $PG(k-1, q)$를 플랫$\Lambda$에 의한 몫(quotient)으로 취함으로써, 결과적으로 생성되는 저차원 코드의 성질을 바탕으로 원래 코드의 길이에 대한 상한을 도출한다. 이 기법은 차원을 귀납적으로 축소하고 서로 다른 $k$ 사이의 상한을 연결하는 데 사용된다.
• 조합론적 계수(Combinatorial Counting): 저자들은 길이 최대 부호가 만족해야 하는 정수 조건(이항 계수를 통해)을 도출하기 위해 펜슬(pencils) 형태의 초평면과 플랫을 이용한 계수 논법을 사용한다.

주요 기여 및 결과

1. 코드 길이에 대한 통합된 상한:
   본 논문은 기존 결과들(예: De Boer, Dodunekov, Landjev, Faldum & Willems의 연구)을 포괄하거나 개선하는 일련의 $m_s(k, q)$ 및 $m_s^t(k, q)$ 상한을 도출한다.

   • 일반 상한: $k \ge 3$인 경우, $m_s(k, q) \le (s+1)(q+1) + k - 2$이다.
   • 정교화된 상한: 특정 조건(예: $0 < s < q-2$ 및 $(s+2, q) \neq (2^e, 2^h)$) 하에서, 상한은 $m_s(k, q) \le (s+1)(q+1) + k - 4$로 강화된다.
   • 쌍대 코드 제약: 저자들은 코드가 충분한 길이($n > s(q+1) + k - 1$)를 가질 경우, 그 쌍대 코드는 반드시 AMDS 부호($t=1$)여야 함을 입증한다. 이는 $N^s$MDS 부호에 대한 충분 조건이 공허해졌던 기존 문헌의 간극을 해결한다.

2. 사영성 및 구조:
   본 논문은 긴 코드들이 반드시 사영적(projective)(즉, 중복된 좌표가 없음)이어야 하는 충분 조건을 제공한다.

   • 만약 $n > s(q+1) + k - 1$이면, 해당 코드는 사영적이다.
   • 만약 $n$이 특정 임계값을 초과하면, 해당 코드는 반드시 **그리스미어 상한(Griesmer bound)**을 충족해야 한다.
   • $k \ge 3$인 경우, 충분히 긴 코드들은 필연적으로 사영적이며 AMDS 쌍대 부호를 가짐을 보여준다.

3. 고차원에서의 길이 최대 부호의 비존재성:
   저자들은 길이 최대 $A^s$MDS 코드가 존재할 수 있는 최대 차원 $k$인 파라미터 $\kappa(s, q)$를 조사한다.

   • 저자들은 다양한 $s$와 $q$에 대한 $\kappa(s, q)$의 명시적 값과 상한을 제공한다(표 2와 3에 요약됨).
   • 추측: 계산적 증거와 이론적 상한을 바탕으로, 저자들은 두 가지 추측을 제안한다:
     • 약한 추측(Weak Conjecture): $q > 3$인 경우, 선형 길이 최대 부호의 차원 $k \ge 5$는 존재하지 않는다 ($\kappa(s, q) \le 4$).
     • 강한 추측(Strong Conjecture): $q > 3$인 경우, $\kappa(s, q)$는 $q$의 패리티(parity)와 $s+2$의 $q$에 대한 가해성(divisibility)에 따라 정확히 2, 3, 또는 4이다. 구체적으로, 차원이 5 이상인 길이 최대 부호는 존재하지 않는다.

4. $N^s$MDS 부호의 조건:
   본 논문은 $A^s$MDS 부호가 반드시 $N^s$MDS 부호(쌍대가 또한 $A^s$MDS인 부호)가 되기 위한 $n$과 $k$에 대한 충분 조건을 확립한다. 구체적으로, $1 < s < q-1$, $k > (s-1)(q+1)-1$, 그리고 $n > s(q+1) + k - 3$이면 해당 코드는 $N^s$MDS이다.

의의 및 주장
저자들은 자신들의 기하학적 접근 방식이 MDS 부호를 다루는 방식과 유사하게, 비제로 결함의 부호를 효과적으로 다루며 기존의 연구 범위를 통합하고 확장한다고 주장한다. 본 연구의 주요 의의는 다음과 같다:

• 통합: 사영 체계 프레임워크가 MDS 부호를 다루는 것과 마찬가지로 결함이 0이 아닌 부호도 효과적으로 처리할 수 있음을 입증한다.
• 구조적 통찰: 결함이 0이 아닌 "긴" 코드들은 구조적으로 제약을 받는다는 것을 보여준다: 즉, 이들은 반드시 사영적이어야 하며, 그리스미어 상한을 충족하며, AMDS 쌍대 부호를 가져야 한다.
• 간극 메우기: Tong과 Liao & Liao의 기존 연구의 한계를 수정하여, $N^s$MDS 부호에 대한 비공허한(non-vacuous) 충분 조건을 제공한다.
• 추측적 한계: 길이 최대 부호의 지형이 $q > 3$인 경우 유한하고 작은 차원 내에 존재함을 시사하며, 이는 이러한 부호에 대한 탐색이 실질적으로 $k \le 4$인 차원으로 제한될 수 있음을 제안한다.

저자들은 차원 $k > 4$에서 알려진 선형 길이 최대 부호의 유일한 예가 테르나리 골레이 코드(ternary Golay code)의 쌍대 코드($[11, 5, 6]_3$)와 확장된 테르나리 골레이 코드($[12, 6, 6]_3$)뿐임을 언급하며, 이는 $q > 3$일 때 다른 코드들은 존재하지 않을 것이라는 추측을 뒷받침한다.