Semidefinite lower bounds for covering codes

문제 정의
본 논문은 $K_q(n, r)$을 결정하는 문제를 다룬다. 여기서 $K_q(n, r)$은 단어 길이 $n$과 피복 반경(covering radius) $r$을 갖는 $q$-진 피복 코드(q-ary covering code)의 최소 크기로 정의된다. 코드 집합 $C \subseteq \{0, \dots, q-1\}^n$이 피복 반경 $r$을 갖는다는 것은, 코드워드들을 중심으로 하는 반지름 $r$인 해밍 볼(Hamming ball)들의 합집합이 전체 해밍 공간을 덮는다는 것을 의미한다. 이 문제의 특정 사례인 $K_3(n, 1)$은 "풋볼 풀 문제(football pool problem)"로 알려져 있으며, 이는 $n$번의 축구 경기에서 최대 한 번의 오차만을 보장하기 위해 필요한 최소 예측 횟수를 찾는 문제이다. 상한(upper bounds)은 일반적으로 명시적인 코드를 구성함으로써 설정되지만, 본 논문은 $K_q(n, r)$에 대한 개선된 하한(lower bounds)을 도출하는 데 초점을 맞춘다.

방법론
저자들은 행렬 컷(matrix cuts)을 사용하여 피복 코드에 대한 준정부호 계획법(SDP) 하한을 도입한 Gijswijt(2005)의 연구를 기반으로 한다. 본 논문에서 제시된 방법론은 세 가지 주요 기술적 발전을 통해 이 하한을 강화한다:

1. Lasserre 계층 제약 조건: 저자들은 0-1 프로그램에 대한 Lasserre 계층에서 영감을 얻은 새로운 준정부호 제약 조건을 도입한다. 구체적으로, 이들은 코드의 발생 벡터(incidence vector)로부터 유도된 행렬 $N$을 분석하며, 이는 $\sum \lambda_i A_i(u) \ge \beta$ 형태의 피복 부등식을 따르는 두 번째 레벨의 계층을 활용한다. 이는 코드워드들의 트리플(triples) 분포를 분석하는 과정을 포함한다.
2. Terwilliger 대수를 통한 대칭 감소: 결과적인 SDP를 계산 가능하게 만들기 위해, 저자들은 대칭 감소(symmetry reduction) 기법을 사용한다. 저자들은 해밍 스킴(Hamming scheme)의 Terwilliger 대수(이진 및 비이진 케이스 모두 포함)를 활용한다. 코드워드 쌍(pairs)과 트리플(triples)의 궤도(orbits)를 등거리 변환 군 $Aut(q, n)$(및 그 안정자 부분군$Aut_0(q, n)$)의 작용에 따라 식별함으로써, 행렬 변수의 차원을 줄인다.
   • 이진 케이스($q=2$)의 경우, 대수 $A_{2,n}$을 $\ast$-동형 사상 $\phi$를 사용하여 더 작은 행렬 블록들의 직합으로 블록 대각화하며, 이를 통해 복잡도를 $O(2^n)$에서 $O(n^3)$ 변수로 줄인다.
   • 비이진 케이스($q \ge 3$)의 경우에도 유사한 블록 대각화가 $A_{q,n}$에 적용되어, 복잡도가 $O(n^4)$ 변수로 줄어든다.
3. 강화된 목적 함수: 본 논문은 더 강력한 목적 함수를 제안한다. 코드 크기와 관련된 표준 선형 항을 최소화하는 대신, 저자들은 코드 크기의 3차 모멘트($|C|^3$)에 대응하는 행렬 변수의 트레이스(trace)를 최소화한다. 저자들은 이 3차 목적 함수가 이전에 사용되었던 선형 또는 이차 목적 함수보다 엄격하게 더 타이트한 하한을 산출함을 증명한다.

주요 기여

• 이론적 프레임워크: 본 논문은 오류 정정 코드에 대한 Schrijver의 경계를 피복 문제로 일반화하는 엄밀한 SDP 프레임워크를 구축한다. 저자들은 Lasserre 계층의 맥락 내에서 행렬 $N$과 경계 행렬(bordered matrices) $R(c, N)$에 대한 제약 조건을 공식적으로 도출한다.
• 대칭 감소 알고리즘: 저자들은 이진 및 비이진 해밍 스킴에 대한 관련 Terwilliger 대수의 블록 대각화를 위한 명시적인 공식을 제공한다. 여기에는 행렬 컷 부등식과 Lasserle 제약 조건을 축소된 변수 공간으로 변환하는 데 필요한 상세한 조합론적 계수($\eta$ 및 $\alpha$)가 포함된다.
• 계산 구현: 저자들은 Julia 프로그래밍 언어와 SDPA-GMP 솔버를 통해 고정밀 산술(512-bit BigFloats)을 사용하여 이러한 하한을 구현하였다. 또한 SDP 생성을 검증하기 위한 독립적인 코드를 개발하였다.

결과
저자들은 광범위한 파라미터($q, n, r$)에 걸쳐 $K_q(n, r)$에 대한 새로운 하한을 제시한다. 이 결과들은 이진($q=2$), 삼진($q=3$), 사진/오진($q=4, 5$) 케이스를 다루는 표 1, 2, 3에 정리되어 있다.

• 이진 케이스: 새로운 하한은 다양한 $n$ 및 $r$ 값에 대해 기존에 알려진 하한을 개선한다(예: $K_2(13, 1)$, $K_2(21, 1)$, $K_2(13, 2)$). 저자들은 처음에 $K_2(18, 1)$ 및 $K_2(30, 1)$에 대해 개선된 하한을 찾았으나, 해당 값들은 이후 Wu와 Chen(2026)에 의해 추월되었음을 언급한다.
• 비이진 케이스: $K_3(13, 3)$ 및 $K_3(14, 4)$와 같은 삼진 코드(풋볼 풀 문제)를 비롯하여 $q=4$ 및 $q=5$에 대해서도 상당한 개선이 보고되었다.
• 계산 규모: 본 논문은 대칭 감소된 SDP의 변수 수와 블록 크기를 보고한다. 예를 들어, 이진 케이스의 $n=32$인 경우, 축소된 SDP는 1,239개의 변수와 6,545의 제곱 블록 크기 합을 가진다. 계산 시간은 인스턴스 크기와 부등식 제약 조건의 0이 아닌 계수 수에 따라 몇 초에서 며칠까지 소요되었다.

의의
본 논문은 제안된 기술이 광범위한 피복 코드 파라미터에 대해 새로운 기록을 세우는 "더 날카로운 하한(sharper lower bounds)"을 도출한다고 주장한다. Lasserre 계층 접근법을 피복 코드로 확장하고 대칭 감소를 효과적으로 활용함으로써, 저자들은 알려진 하한과 상한 사이의 간극을 좁힐 수 있음을 입증한다. 이 연구는 이러한 하한을 계산하는 체계적인 방법을 제공하며, 트리플 분포 제약 조건이나 특정 목적 함수 최적화를 충분히 활용하지 않았던 이전의 LP 및 SDP 접근법에 대한 더 강력한 대안을 제시한다. 이 결과는 피복 코드 및 풋볼 풀 분야의 업데이트된 벤치마크 역할을 한다.