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

1. Problem Statement

The paper addresses the problem of determining the asymptotic rate upper bounds for $q$-ary $B_2$ codes.

• Definition: A $q$-ary code $C_n \subset \{0, \dots, q-1\}^n$ is a $B_2$ code if all pairwise sums of its codewords (over the reals) are distinct. That is, $c_i + c_j = c_k + c_l$ implies $\{i, j\} = \{k, l\}$.
• Goal: To find the maximum possible asymptotic rate $R = \limsup_{n \to \infty} \frac{1}{n} \log_q |C_n|$.
• Context: Previous bounds (e.g., Lindström, Wang, and the author's own prior work [5]) relied on information-theoretic arguments involving the entropy of the difference between two independent random variables, $D = X - Y$. However, these methods used coarse relaxations, primarily relying only on the constraint that the collision probability $P(X=Y) \ge 1/q$.

2. Methodology

The author refines the entropy maximization step in the rate bound derivation by exploiting the full Fourier-analytic structure of the difference distribution.

A. Fourier Representation of the Difference

Let $X$ and $Y$ be i.i.d. random variables on $\{0, \dots, q-1\}$ with probability mass function (pmf) $p$. The difference $D = X - Y$ has a pmf $r$.

• The characteristic function of $D$ is $\psi_D(\theta) = |\phi(\theta)|^2$, where $\phi(\theta)$ is the characteristic function of $X$.
• Consequently, the pmf $r$ is the autocorrelation of $p$.
• In the frequency domain, the trigonometric polynomial $R(\theta) = \sum r_k e^{ik\theta}$ must be non-negative for all $\theta \in [0, 2\pi]$ because it equals $|\phi(\theta)|^2$.

B. Convex Optimization Formulation

The paper formulates a new entropy maximization problem to bound $H(D)$:

• Objective: Maximize $H(r) = -\sum r_k \log r_k$.
• Constraints:
  1. $r_k \ge 0$ and $\sum r_k = 1$ (valid pmf).
  2. $r_{-k} = r_k$ (symmetry).
  3. $r_0 = P(X=Y) \ge 1/q$ (collision constraint).
  4. New Constraint: $R(\theta) \ge 0$ for all $\theta$. This enforces that $r$ is a valid autocorrelation of a pmf on the specific support.

C. Toeplitz Semidefinite Programming (SDP)

The non-negativity constraint $R(\theta) \ge 0$ is equivalent to an infinite family of Toeplitz Positive Semidefinite (PSD) constraints.

• By the Fejér–Riesz theorem and properties of positive trigonometric polynomials, $R(\theta) \ge 0$ if and only if the Toeplitz matrices $T^{(N)}(r)$ formed by the coefficients $r_k$ are PSD for all $N \ge 1$.
• The author solves a truncated version of this problem numerically, imposing $T^{(N)}(r) \succeq 0$ for $N \le N_{max}$ (specifically $N_{max}=100$). This converts the problem into a standard convex optimization problem solvable via SDP solvers.

3. Key Contributions

1. Fourier-Analytic Relaxation: The paper introduces a relaxation for the i.i.d. difference distribution that utilizes the fact that its characteristic function is a non-negative trigonometric polynomial of degree at most $q-1$.
2. Equivalence to Toeplitz SDP: It explicitly establishes the equivalence between the non-negativity of the trigonometric polynomial and the positive semidefiniteness of an infinite family of Toeplitz matrices, allowing the problem to be solved via numerical SDP.
3. Improved Entropy Bound: By enforcing the full spectral positivity (rather than just the collision probability), the paper derives a strictly smaller upper bound on the entropy $H(X-Y)$ compared to previous methods.
4. New Rate Bounds: The refined entropy bound is plugged into the prefix-suffix method (a standard technique for $B_2$ codes) to derive new, tighter asymptotic upper bounds on the code rate.

4. Results

The author evaluates the new bound numerically for $q \in \{9, 10, 11, 12, 13\}$. The results are summarized in Table I of the paper:

• Comparison: The new bounds ($R_{new}^q$) are strictly lower (tighter) than the best previously known bounds from:
  • Lindström [3]
  • Della Fiore–Dalai [5] (the author's previous work)
  • Wang [7]
• Specific Improvements:
  • For $q=9$, the bound drops from $\approx 0.5615$ (previous best) to 0.5579.
  • For $q=13$, the bound drops from $\approx 0.5555$ to 0.5521.
• Convergence: The numerical values stabilize as the truncation parameter $N_{max}$ increases, confirming the validity of the approximation.

5. Significance

• Theoretical Advancement: This work demonstrates that ignoring the "spectral factorization" constraint (i.e., assuming any non-negative trigonometric polynomial corresponds to a valid difference distribution) leads to loose bounds. Enforcing the Toeplitz PSD structure captures the necessary conditions for a sequence to be an autocorrelation of a non-negative sequence, significantly tightening the entropy bound.
• Methodological Impact: It bridges combinatorial coding theory with harmonic analysis and convex optimization (SDP). This approach offers a systematic way to improve bounds for other code families where the problem can be reduced to controlling the entropy of structured discrete differences.
• Future Directions: The paper suggests that further tightening is possible by adding moment constraints or extending the method to higher-order sumsets (e.g., $B_h$ codes), though this would increase the complexity of the harmonic-analytic constraints.

In summary, the paper provides a rigorous mathematical framework to improve the theoretical limits of $B_2$ codes by replacing a simple probabilistic constraint with a sophisticated spectral positivity constraint solvable via Semidefinite Programming.