Sharper upper bounds for $q$-ary $B_2$ codes from Toeplitz SDPs

논문 요약: Toeplitz SDP 를 통한 q 진법 B2 코드의 더 날카로운 상한 bound

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

• B2 코드 (B2 Codes): $q$ 진법 코드 $C_n$이 B2 코드라는 것은, 코드 내 임의의 두 코드워드 $c_i, c_j$ ($1 \le i \le j \le M$) 의 합 $c_i + c_j$가 모두 서로 달라야 한다는 조건을 만족하는 것을 의미합니다. 이는 $q=2$일 때 2-separable 코드와 동일합니다.
• 목표: B2 코드의 점근적 레이트 (asymptotic rate) $R = \limsup_{n \to \infty} \frac{1}{n} \log_q |C_n|$에 대한 상한 (upper bound) 을 구하는 것입니다.
• 기존 접근법의 한계: 저자의 이전 연구 [5] 및 관련 문헌에서는 두 독립적인 확률 변수 $X, Y$의 차이 $D = X - Y$에 대한 엔트로피 $H(D)$를 상한으로 잡기 위해, 단순히 충돌 확률 제약 조건인 $P(X=Y) \ge 1/q$만을 사용했습니다. 이는 $H(D)$의 상한을 구할 때 필요한 구조적 정보를 충분히 활용하지 못해, 실제 가능한 값보다 다소 완만 (coarse) 한 bound 를 제공했습니다.

2. 방법론 (Methodology)

이 논문은 $X-Y$의 확률 질량 함수 (pmf) 가 갖는 푸리에 해석학적 (Fourier-analytic) 구조를 완전히 활용하여 엔트로피 상한을 정교화합니다.

• 푸리에 표현 및 비음성 다항식:

  • $X, Y$가 독립이고 동일 분포 (i.i.d.) 를 따를 때, 차이 $D=X-Y$의 pmf 는 원래 pmf 의 자기상관 (autocorrelation) 입니다.
  • 이에 따라 $D$의 특성 함수 (characteristic function) 는 $|\phi(\theta)|^2$ 형태가 되며, 이는 $[0, 2\pi]$에서 비음성 (nonnegative) 삼각 다항식이 됩니다.
  • 즉, $D$의 pmf $r_k$는 차수가 $q-1$ 이하인 비음성 삼각 다항식 $R(\theta) = \sum r_k e^{ik\theta}$의 계수여야 합니다.

• 볼록 최적화 문제 (Convex Optimization):

  • 기존의 단순한 제약 ($r_0 \ge 1/q$) 대신, $R(\theta) \ge 0$ (모든 $\theta$에 대해) 이라는 조건을 추가하여 엔트로피 최대화 문제를 정의합니다.
  • 이 조건은 Toeplitz 행렬의 양의 준정부호 (Positive Semidefinite, PSD) 조건과 동치입니다. 즉, $T^{(N)}(r) \succeq 0$ (모든 $N \ge 1$) 인 조건을 부과합니다.

• 반정규 계획법 (SDP) 활용:

  • 무한한 PSD 조건을 처리하기 위해, $N \le N_{max}$까지의 조건을 잘라낸 Truncated Toeplitz SDP를 수치적으로 해결합니다.
  • 이를 통해 $H(D)$의 새로운, 더 엄격한 상한 $h^F_q$를 계산합니다.

• 코드 레이트 bound 유도:

  • 개선된 엔트로피 상한 $h^F_q$를 기존 [5] 의 prefix-suffix 방법론에 대입하여, B2 코드의 점근적 레이트 상한을 도출합니다.
  • 최종 레이트 상한은 $R_b \le \frac{h^F_q}{\log q + h^F_q}$로 주어집니다.

3. 주요 기여 (Key Contributions)

1. 푸리에 기반 완화 (Fourier-analytic Relaxation): i.i.d. 차이 분포 $D=X-Y$에 대해, 특성 함수가 비음성 삼각 다항식이라는 사실을 활용하여 엔트로피 최적화 문제를 재정의했습니다.
2. Toeplitz PSD 조건과의 동치성 증명: 푸리에 계수의 비음성 조건이 Toeplitz 행렬의 양의 준정부호 조건과 동치임을 명시적으로 증명하여, 이를 SDP 로 변환할 수 있는 이론적 기반을 마련했습니다.
3. 엄격한 엔트로피 상한 도출: 기존 문헌에서 사용되던 단순 충돌 확률 제약보다 강력한 조건을 적용함으로써, $H(X-Y)$의 상한을 엄격하게 줄였습니다.
4. 새로운 레이트 상한 기록: 수치 계산을 통해 $q \in \{9, 10, 11, 12, 13\}$에 대해 기존 문헌 (Lindström, Wang 등) 의 최상위 bound 보다 더 작은 (더 좋은) 레이트 상한을 제시했습니다.

4. 수치적 결과 (Results)

• 계산 방법: $N_{max}=100$까지 잘라낸 Toeplitz SDP 를 사용하여 $h^F_q$를 계산하고, 이를 통해 $R_q^{new}$를 구했습니다.
• 비교 결과:
  • q=9: 기존 최상위 bound (Wang [7]) 인 0.55841 보다 개선된 0.55792 달성.
  • q=10: 0.55727 $\to$ 0.55611
  • q=11: 0.55626 $\to$ 0.55457
  • q=12: 0.55536 $\to$ 0.55323
  • q=13: 0.55454 $\to$ 0.55206
• 모든 경우에서 기존 문헌 (Lindström [3], 이전 저자 연구 [5], Wang [7]) 보다 더 엄격한 (작은) 상한 값을 제시했습니다.

5. 의의 및 향후 전망 (Significance & Outlook)

• 이론적 의의: 정보 이론적 상한 (Information-theoretic upper bounds) 을 구할 때, 단순한 확률 제약이 아닌 **푸리에 구조 (Fourier structure)**와 **선형 대수적 제약 (SDP)**을 결합하는 것이 얼마나 강력한지 보여주었습니다. 특히, "자기상관"으로 생성될 수 없는 고엔트로피 분포를 배제함으로써 bound 를 정밀화했습니다.
• 실용적 의의: 통신 시스템 및 데이터 저장에서 B2 코드와 같은 구조를 가진 코드의 최대 전송 효율에 대한 이론적 한계를 더 정확하게 규명했습니다.
• 향후 연구 방향:
  • 완화 (relaxation) 의 간격 (gap) 분석: 푸리에 비음성 조건이 실제 스펙트럴 인자 (spectral factor) 존재 조건과 얼마나 차이가 있는지 연구.
  • 고차 합집합 (higher-order sumsets, 예: $B_h$ 조건) 에 대한 확장.
  • 추가적인 모멘트 제약 (moment constraints) 을 도입하여 relaxation 을 더 강화하는 방법 모색.

이 논문은 정보 이론과 최적화 이론 (특히 SDP) 의 교차점을 활용하여 고전적인 코딩 이론 문제를 해결한 성공적인 사례로 평가됩니다.