Sharper upper bounds for $q$-ary and constant-weight $B_2$ codes
This work addresses incremental improvements in coding theory by providing sharper bounds for error-correcting codes, which is important for researchers in information theory and communications.
The paper tackles the problem of deriving upper bounds for q-ary and constant-weight B2 codes by developing refined entropy bounds through Fourier analysis and convex relaxations, resulting in improved asymptotic rate bounds for specific q values and a new bound for constant-weight codes.
We derive refined entropy upper bounds for $q$-ary $B_2$ codes by exploiting the Fourier structure of the i.i.d. difference distribution $D=X-Y$. Since the pmf of $D$ is an autocorrelation, its Fourier series is a nonnegative trigonometric polynomial of degree at most $q-1$. This leads to a natural convex relaxation over candidate difference distributions, equivalently expressible through an infinite family of positive semidefinite Toeplitz constraints. The resulting formulation admits a simple Gram interpretation and yields certified upper bounds through truncated semidefinite programs. Combined with the prefix-suffix method, this gives improved asymptotic rate upper bounds for $q$-ary $B_2$ codes; in particular, for $q\in\{9,10,11,12,13\}$ the resulting values improve on the best bounds known in the literature. We also study binary constant-weight $B_2$ codes. Extending the distance-distribution method of Cohen, Litsyn, and Zémor to the constant-weight setting, and combining it with Litsyn's asymptotic linear-programming bound for constant-weight codes, we derive a new upper bound on the constant-weight $B_2$ rate.