Sharper upper bounds for q q -ary and constant-weight B 2 B_{2} codes
Stefano Della Fiore · 2026
Read Sharper upper bounds for q q -ary and constant-weight B 2 B_{2} codes by Stefano Della Fiore (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-27639.txt.
Introduction
Della Fiore sharpens size limits for a special family of codes. B2 codes keep all pair sums distinct. He studies q-ary and constant-weight versions. Difference distributions carry a Fourier structure he exploits. That structure yields a convex relaxation of the problem. Truncated semidefinite programs then certify upper bounds. For q from nine to thirteen, bounds beat the literature. A new bound also covers constant-weight rates.
Catalog record
| CREATOR | Stefano Della Fiore |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 22484 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.27639
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Sharper upper bounds for q q -ary and constant-weight B 2 B_{2} codes Stefano Della Fiore Abstract We derive refined entropy upper bounds for q q -ary B 2 B_{2} codes by exploiting the Fourier structure of the i.i.d. difference distribution D = X − Y D=X-Y . Since the pmf of D D is an autocorrelation, its Fourier series is a nonnegative trigonometric polynomial of degree at most q − 1 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 q -ary B 2 B_{2} codes; in particular, for q ∈ { 9 , 10 , 11 , 12 , 13 } 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 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 B_{2} rate. I Introduction Let [0,q-1]=\{0,1,\dots,q-1\} , and let C_{n}\subset[0,q-1]^{n} be a q -ary code of length n with |C_{n}|=M . We define the asymptotic rate of a family of codes \{C_{n}\} by R=\limsup_{n\to\infty}\frac{1}{n}\log_{q}|C_{n}|, while logarithms without subscript are taken in base 2 . Definition I.1 A q -ary code C_{n}=\{c_{1},\dots,c_{M}\}\subset[0,q-1]^{n} is a B_{2} code if all sums c_{i}+c_{j},\qquad 1\leq i\leq j\leq M, computed over the reals, are distinct. For q=2 , this is equivalent to the usual notion of a \bar{2} -separable code. Upper bounds on the rate of q -ary B_{2} codes were obtained in [ 2 , 3 , 4 , 7 , 8 ] ; see also the references therein. The constant-weight binary setting was recently investigated in [ 9 ] . A standard route to asymptotic upper bounds is to relate the code cardinality to the entropy of suitably chosen random variables associated with prefixes and suffixes of codewords. For q -ary B_{2} codes, the key local object is the integer difference D=X-Y, where X and Y are i.i.d. q -ary random variables. The strength of the resulting rate bound depends on how sharply one can upper bound \Ent(D) . In our earlier work [ 6 ] , this entropy term was bounded through a coarse relaxation based only on the collision constraint \mathbb{P}(X=Y)=\sum_{a=0}^{q-1}\mathbb{P}(X=a)^{2}\geq\frac{1}{q}, which led to a closed-form upper bound on \Ent(D) , and hence to an explicit asymptotic rate bound. The starting point of the present paper is that the difference distribution D=X-Y carries substantially more structure than this single scalar constraint. Its probability mass function is an autocorrelation, and therefore its Fourier series is a nonnegative trigonometric polynomial of degree at most q-1 . Equivalently, its coefficients satisfy an infinite family of Toeplitz positive semidefinite constraints. This observation leads to a natural convex relaxation over candidate difference distributions. The relaxation is strong enough to improve the entropy bound, yet remains numerically tractable through truncated semidefinite programs (SDPs). At the same time, the Toeplitz formulation admits a direct Gram interpretation, which makes the origin of the semidefinite constraints transparent. This Fourier–Toeplitz viewpoint yields a refinement of the entropy step in the prefix–suffix method and leads to a new upper bound on the asymptotic rate of q -ary B_{2} codes. Numerically, the resulting bound improves on the best values previously available to us for q\in\{9,10,11,12,13\} . The paper also contains a second result, concerning binary constant-weight B_{2} codes of length n and weight w=\alpha n(1+o(1)) . In this setting the relevant tool is not the prefix–suffix decomposition, but the distance-distribution method underlying the binary bound of Cohen, Litsyn, and Zémor [ 4 ] . We show that this argument admits a constant-weight refinement. The B_{2} property still provides the required combinatorial control on the distance distribution, while the matching lower estimate is obtained from Litsyn’s asymptotic linear-programming bound for constant-weight codes [ 5 ] . This leads to a new upper bound on the asymptotic rate r_{B_{2}}^{\mathrm{cw}}(\alpha) , improving the recent bound of Sima, Li, Shomorony, and Milenković [ 9 ] . The paper is organized as follows. In Sections II and III we develop the Fourier and Toeplitz relaxations for the difference distribution and derive the corresponding entropy bound. In Section IV we combine this bound with the prefix–suffix argument to obtain a new upper bound for q -ary B_{2} codes, and in Section V we report the resulting numerical values. Section VI is devoted to the constant-weight binary setting, where we derive a Cohen–Litsyn-type upper bound and compare it with the recent result of [ 9 ] . II Fourier representation of the difference distribution Let X be a random variable with values in [0,q-1] and pmf P=(p_{0},\dots,p_{q-1}) , and let Y be an independent copy of X . Consider the integer difference D=X-Y. Then D takes values in \{-(q-1),\dots,q-1\} and its pmf r=(r_{-(q-1)},\dots,r_{q-1}) is r_{k}=\mathbb{P}(D=k)=\sum_{i=0}^{q-1}p_{i}p_{i+k},\qquad k=-(q-1),\dots,q-1, (1) with the convention p_{j}=0 for j\notin\{0,\dots,q-1\} . Introduce the characteristic function of X , \phi(\theta)=\mathbb{E}[e^{i\theta X}]=\sum_{j=0}^{q-1}p_{j}e^{ij\theta},\qquad\theta\in[0,2\pi], and the characteristic function of D , \psi_{D}(\theta)=\mathbb{E}[e^{i\theta(X-Y)}]=\phi(\theta)\overline{\phi(\theta)}=|\phi(\theta)|^{2}. (2) On the other hand, by Fourier series, \psi_{D}(\theta)=\sum_{k=-(q-1)}^{q-1}r_{k}e^{ik\theta}=:R(\theta), (3) where R(\theta) is a trigonometric polynomial of degree at most q-1 with real symmetric coefficients r_{-k}=r_{k} . Combining ( 2 ) and ( 3 ), R(\theta)=|\phi(\theta)|^{2}\geq 0,\qquad\theta\in[0,2\pi]. (4) Moreover, the coefficients satisfy the inversion formula \displaystyle r_{k} \displaystyle=\frac{1}{2\pi}\int_{0}^{2\pi}R(\theta)e^{-ik\theta}\,d\theta \displaystyle=\frac{1}{2\pi}\int_{0}^{2\pi}|\phi(\theta)|^{2}e^{-ik\theta}\,d\theta,\qquad|k|\leq q-1. In particular, r_{0}=\mathbb{P}(X=Y)=\sum_{i=0}^{q-1}p_{i}^{2}=\frac{1}{2\pi}\int_{0}^{2\pi}|\phi(\theta)|^{2}\,d\theta. By Cauchy–Schwarz, r_{0}=\sum_{i=0}^{q-1}p_{i}^{2}\geq\frac{1}{q}. (5) III Entropy bounds via Fourier positivity and Toeplitz Gram matrices Let X,Y be i.i.d. on [0,q-1] with pmf P and let D=X-Y . Define h_{q}^{\star}:=\sup\Ent(D), where the supremum is over all P , and \Ent denotes Shannon entropy (in bits), with the convention 0\log 0:=0 . In [ 6 ] we used the relaxed bound \Ent(D)\leq\bar{h}_{q}:=\Ent\!\Big(\tfrac{1}{q},\underbrace{\tfrac{1}{2q},\dots,\tfrac{1}{2q}}_{2q-2\ \text{times}}\Big)=\frac{1}{q}\log q+\frac{q-1}{q}\log(2q), (6) obtained by maximizing entropy under the sole constraint r_{0}\geq 1/q . III-A Fourier-analytic relaxation Definition III.1 For fixed q\geq 2 define h_{q}^{\mathrm{F}} as the optimal value of \displaystyle\text{maximize} \displaystyle-\sum_{k=-(q-1)}^{q-1}r_{k}\log r_{k} (7) \displaystyle\text{subject to} \displaystyle r_{k}\geq 0,\quad\sum_{k=-(q-1)}^{q-1}r_{k}=1,\quad r_{-k}=r_{k}, \displaystyle r_{0}\geq\frac{1}{q}, \displaystyle R(\theta):=\sum_{k=-(q-1)}^{q-1}r_{k}e^{ik\theta}\geq 0\quad\text{for all }\theta\in[0,2\pi]. Lemma III.2 For every q\geq 2 , h_{q}^{\star}\leq h_{q}^{\mathrm{F}}\leq\bar{h}_{q}. Proof: Any i.i.d. difference pmf r satisfies the probability and symmetry constraints, the collision constraint r_{0}\geq 1/q by ( 5 ), and Fourier nonnegativity R(\theta)=|\phi(\theta)|^{2}\geq 0 by ( 4 ). Hence it is feasible for ( 7 ), giving h_{q}^{\star}\leq h_{q}^{\mathrm{F}} . Dropping R(\theta)\geq 0 enlarges the feasible set and yields ( 6 ), so h_{q}^{\mathrm{F}}\leq\bar{h}_{q} . ∎ III-B Toeplitz formulation and Gram interpretation Define r_{k}=0 for |k|\geq q . For N\geq 1 let the Toeplitz matrix T^{(N)}(r) be T^{(N)}(r)_{ij}=r_{i-j},\qquad i,j\in\{0,\dots,N-1\}. Since r comes from an autocorrelation as in ( 1 ), then Toeplitz positive semidefiniteness is immediate from a Gram construction. Let p=(p_{0},\dots,p_{q-1}) and extend it to a length- (N+q-1) vector \tilde{p}=(p_{0},\dots,p_{q-1},0,\dots,0) . For i\in\{0,\dots,N-1\} let \tilde{p}^{(i)} be the shift of \tilde{p} by i positions (padding with zeros). Then \langle\tilde{p}^{(i)},\tilde{p}^{(j)}\rangle=\sum_{t}\tilde{p}_{t-i}\tilde{p}_{t-j}=\sum_{u}p_{u}p_{u+(i-j)}=r_{i-j}. Hence T^{(N)}(r) is the Gram matrix of the vectors \{\tilde{p}^{(0)},\dots,\tilde{p}^{(N-1)}\} and therefore T^{(N)}(r)\succeq 0 . The relaxation keeps the necessary Gram condition while optimizing