The Weight Distribution of the Third-Order Reed-Muller Code of Length 2048

기술 요약: 길이 2048인 3차 리드-뮬러 코드의 무게 분포

문제 정의
리드-뮬러 코드 $RM(r, m)$의 무게 분포는 부호 이론의 고전적인 문제이지만, 폐쇄형 해(closed-form solution)는 차수 $r \le 2$ 및 그 쌍대 코드 $r \ge m-3$에 대해서만 알려져 있다. 3차 코드($r=3$)의 경우, 길이 1024($RM(3, 10)$)까지의 완전한 분포는 개별적인 계산을 통해 확립되었다. 본 논문은 이 연쇄 과정의 다음 단계인 길이 2048인 3차 리드-뮬러 코드$RM(3, 11)$의 무게 분포를 계산하는 문제를 다룬다. 부차적인 목표는 10개 변수를 가진 모든 3차 형식(cubic forms)에 대한 2차 비선형성 $d_2(f)$를 결정하여, $RM(3, 10)$내에서$RM(2, 10)$의 상대적 피복 반경(relative covering radius) $\rho_{2,3}(10)$을 확립하는 것이다.

방법론
계산은 Sarwate 유형의 재귀법에 의존하며, 이는 $RM(3, m+1)$의 무게 생성자(weight enumerator)를 모든 3차 형식 $f$에 대한 $f + RM(2, m)$의 제곱된 코셋 무게 생성자의 합으로 표현한다. 이때 코셋 생성자는$f$의$GL(m, 2)$-궤도(orbit)에 의해서만 결정되므로, 이 합은 궤도 크기에 따라 가중치가 부여된 궤도 대표들의 합으로 축소된다.

$m=10$에서의 주요 병목 구간은 방대한 수의 궤도(3,691,560개의 0이 아닌 궤도)와 단일 코셋 생성자를 평가하는 데 드는 비용이다. Brier와 Langevin의 표준 분할 공식은 $m=10$일 때 $2^{36}$개의 동차 이차 형식(homogeneous quadratic forms)에 대한 외부 열거를 요구하는데, 이는 전체 카탈로그 통과(catalog pass)를 수행하기에 계산적으로 불가능하다.

이를 극복하기 위해 저자들은 구조적 정리(정리 1)를 활용한다: 모든 비퇴화 불리언 3차 형식은 각 홀수 차원에서의 단일 궤도를 제외하고는 모든 비퇴화 하이퍼플레인 제한(hyperplane restriction)을 갖는다. $m=10$(짝수 차원)의 경우, 이 정리는 모든 비퇴화 궤도가 비퇴화인 하이퍼플레인에 대한 제한을 가짐을 보장한다. 이를 통해 코셋 생성자를 $2^{36}$이 아닌 $2^{26}$ 크기의 몫 공간(quotient space)을 통해 계산할 수 있게 되어, 궤도당 $2^{10}$의 절감 효과를 얻는다.

코셋 무게 생성자의 평가는 결과적인 아핀 코셋(affine cosets)에 대한 고속 월시-하다마드 변환(fast Walsh–Hadamard transforms)을 사용하여 수행된다. 전체 카탈로그 통과에는 약 65 CPU-년(CPU-years)이 소요되었다. 결과의 엄밀성을 검증하고 상한(upper bounds)을 개선하기 위한 효율성을 높이기 위해, 로컬 탐색 휴리스틱(그리디 하강, $\tau$-이동, 반복 로컬 탐색, 빔 탐색을 결합)이 개발되었다. 이 휴리스틱은 $wt(f+q)$를 최소화하는 명시적인 이차 보정$q$를 찾아내어, 전체 열거 비용의 극히 일부만으로 피복 반경에 대한 증명(certificate)을 제공한다.

주요 기여 및 결과

1. $RM(3, 11)$의 무게 분포:
   본 논문은 $RM(3, 11)$의 완전한 무게 분포(표 1)를 제시한다. 이 결과는 10개 변수를 가진 0이 아닌 3,691,560개의$GL(10, 2)$ 궤도의 제곱된 코셋 무게 생성자와 0 궤도의 기여를 합산하여 구성된다.

2. 2차 비선형성 및 상대적 피복 반경:
   각 코셋 생성자의 가장 낮은 0이 아닌 지수는 2차 비선형성 $d_2(f)$에 대응한다. 계산 결과, 10개 변수를 가진 모든 3차 형식에 대한 $d_2(f)$의 최댓값은 408이다.

• 정리 3: $RM(3, 10)$내에서$RM(2, 10)$의 상대적 피복 반경$\rho_{2,3}(10)$은 정확히 408이다.
• 이 최댓값은 179개의 서로 다른 궤도에서 나타난다. 이 궤도들의 대표들과 그들의 "키싱 넘버"(최소 무게를 달성하는 이차 형식의 개수)가 표 2에 나열되어 있다.
• 179개의 모든 극한 형식(extremal forms)은 비퇴화(nondegenerate)이다.

3. 피복 반경의 개선된 하한:
   이 결과는 $RM(2, 10)$의 피복 반경에 대한 기존 최적 하한을 400에서 408로 높였다. 179개의 궤도는 이 하한에 대한 명시적인 증거(witnesses) 역할을 한다.

4. 교대 랭크(Alternating Rank)와의 연결:
   본 논문은 $d_2(f)$와 3차 형식의 교대 랭크($arank$) 사이의 관계를 확립한다. 유도된 경계(정리 4)를 사용하여,$d_2(f) = 408$인 모든 형식에 대해 교대 랭크가 최소 6이어야 함을 보여준다.$m=10$에서 최대 교대 랭크는 7이다. 분석 결과, 179개의 극한 궤도 중 177개는$arank = 7$이며, 2개는$arank = 6$이다. 이는 극한 형식이 해당 차원의 최대 가능한 교대 랭크를 가져야 했던 낮은 차원($m \le 9$)의 사례와 대조된다.

5. 휴리스틱 탐색 및 코큐빅 경계(Cocubic Bounds):
   로컬 탐색 휴리스틱은 전체 열거 비용의 약 1,000분의 1의 비용으로 경계 $\rho_{2,3}(10) \le 408$을 성공적으로 재현하였다. 이를 7차 형식에 적용했을 때, 이 휴리스틱은 $RM(7, 10)$내에서$RM(6, 10)$의 상대적 피복 반경의 상한을 50에서 32로 개선하였다(보조정리 2).

의의
본 논문은 알려진 3차 코드의 연쇄를 확장함으로써 $RM(3, 11)$의 무게 분포를 해결했다는 점에서 그 의의를 찾는다. 비퇴화 하이퍼플레인 제한에 관한 구조적 정리는 이전 방식으로는 "손이 닿지 않았던(out of reach)" 전체 카탈로그 통과를 가능하게 한 핵심적인 동력으로 제시된다.

$\rho_{2,3}(10) = 408$의 결정은 피복 반경 문헌에서 $RM(2, 10)$의 최적 하한을 업데이트했다는 점에서 중요하다. 또한, 극한 궤도들에 대한 분석은 구조적 통찰을 제공한다: (기존의 기록이었던) 단항식 트레이스 형식(monomial trace forms)에서 이항 트레이스 다항식(binomial trace polynomials)으로의 전환과, 극한 형식이 최대 교대 랭크에 집중되어 있다는 점은 더 높은 차원($m > 10$)에서 고비선형성 형식을 탐색하는 새로운 방향을 제시한다. 저자들은 추가적인 부호 이론 및 불리언 함수 분석 연구를 촉진하기 위해 열거 데이터와 참조 코드를 공개한다고 밝혔다.