CS Paper Radar

Envelopes of upper bounds for nonbinary constant-weight and constant-composition codes

Artur Akhiiarov, Peter Boyvalenkov, Danila Cherkashin, Andrei Raigorodskii

cs.IT math.CO ·submitted 2026-09-20 21:02 UTC · v2
surveytheory

Abstract

Deriving upper bounds on code size from existing bounds is a classical approach in coding theory, dating back to the seminal results of Elias, Bassalygo, and Levenshtein. We study a framework encompassing the Bassalygo--Elias and Levenshtein inequalities for binary and nonbinary (constant-weight) codes and provides certain generalizations. The asymptotic cost of transferring a bound between different symbol compositions is expressed in terms of mutual information, yielding an information-theoretic optimal transport formulation. We determine the optimal permutation-transport cost between arbitrary compositions in terms of their least common majorant in the majorization order. Specializing to symmetric constant-weight compositions yields explicit transport profiles. As a byproduct, we establish unimodality of the asymptotic constant-weight rate as a function of the relative weight. We prove that the resulting closure operators are idempotent and that applying transport before outer Bassalygo--Elias averaging leaves the unrestricted bound obtained from the same input unchanged. We also establish necessary and sufficient conditions for an upper bound to be a fixed point of the closure operator. Since the asymptotic rate function is an upper bound for itself and it is a fixed point, we conclude the Schur concavity of the constant-composition rate function. Finally, we survey existing upper bounds for binary and nonbinary constant-weight and constant-composition codes, combine them into optimized envelopes within the transport framework, and obtain improved theoretical and numerical bounds.

Comment
39 pages, 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Entropy/Length Profile Bounds for the Conversion of (Non)linear Codes in the Merge Regime

cs.IT ·2026-10-11 ·Songping Ge, Han Cai, Xiaohu Tang
similarity 0.66
Abstract · 26 pages, 1 figure

Code conversion changes the parameters of encoded data while avoiding complete decoding and re-encoding. Existing general bounds largely rely on the algebraic structure of linear codes. This paper develops an information-theoretic framework for nonlinear code conversion in the merge regime. Using the entropy/length profile (ELP), we derive upper bounds on the number of unchanged symbols and lower bounds on the number of read symbols for arbitrary $(n,M)_q$ codes, without assuming linearity or requiring $\log_q M$ to be an integer. We also obtain joint bounds for multiple initial codes and consequences involving minimum distance. For linear codes, the proposed bounds reduce to the corresponding generalized Hamming weight (GHW) bounds. The construction based on Hamming codes converts Hamming codes of redundancy two into a Hamming code of any larger redundancy and simultaneously attains the general bounds on unchanged and read symbols. The construction based on quasigroups shows that new bounds remain tight for genuinely nonlinear codes of nonintegral dimension and at a nonintegral entropy threshold, which, to the best of our knowledge, is the first construction of convertible codes for nonlinear codes.

0.29

Quantum channel bounds for constant-composition codes

cs.IT math.CO ·2026-11-07 ·Artur Akhiiarov, Peter Boyvalenkov, Danila Cherkashin, Andrei Raigorodskii
similarity 0.60
Abstract · 45 pages, 1 figure, 5 tables

We extend the quantum-channel optimization of Alrabiah and Guruswami to $q$-ary constant-composition codes. We study explicit channel and flag constructions that recover selected classical asymptotic upper bounds, including the Ben-Haim--Litsyn, moving-subspace and Horn-channel bounds. We give two equivalent formulations, Gram and flag, and prove stability of the obtained upper bounds under permutation transport and generalized shortening. A hierarchy defined by bounding the output-state ranks within each flag improves strictly between consecutive levels at every composition and every positive distance below the Plotkin threshold. We provide finite matrix parametrizations of these bounds (i.e., the number of variables does not depend on the length of codes under consideration). Numerical optimization rapidly produces improvements over the known asymptotic upper bounds throughout all tested nonbinary parameter ranges. For rational input data, each finite level admits near-optimal feasible rational descriptions of polynomial length. Their feasibility can be checked exactly and their objective values computed to any prescribed accuracy in polynomial time; the associated threshold problem with a prescribed gap belongs to $\mathsf{PromiseNP}$.

0.27

Weak Composition Theorems for Randomized Communication

cs.CC ·2026-11-12 ·Pachara Sawettamalya
theory similarity 0.60
Abstract

We present two results towards the randomized communication complexity of composed functions. Our contributions include: - \textbf{Lifting-by-Influence.} For any binary function $f$ and any outer gadget $g:\{0,1\}^n \rightarrow \mathbb{R}$, we show that up to additive terms, computing $g \circ f^n$ information-theoretically requires solving at least $\operatorname{Inf}(g)$ instances of $f$, where $\operatorname{Inf}(g)$ denotes the total influence of $g$. To our knowledge, this is the first composition lower bound for randomized communication that applies to \emph{every} choice of $f$ and $g$. - \textbf{Symmetric Composition.} When $g$ is a symmetric function with a value transition at Hamming weight $d$, we strengthen the number of required instances to $\min\{d,n+1-d\}$. As an implication, this recovers the previously known direct-sum theorem, XOR lemma, and majority lemma. Our proofs develop novel and distinctive usages of the classical \emph{input embedding} argument of Barak, Braverman, Chen, and Rao (SICOMP 2013). As an additional ingredient, we introduce a new public sampling framework that avoids auxiliary communication during the recovery phase of the protocol, ultimately reducing the extra cost from $O(n)$ bits of information to just $O(1)$.

0.06

Auxiliary Codes and the Generalized Packing-Covering Conjecture

cs.IT ·2026-09-16 ·Isaac Barouch Essayag, Aryeh Lev Zabokritskiy
theory similarity 0.60
Abstract · 10 pages, 2 tables. Revised exposition and references; clarified the auxiliary-code method and improved presentation

The generalized packing--covering conjecture asks whether, at every order, the packing radius of a linear code is at most its covering radius. We prove the conjecture for every linear code of redundancy at most fourteen over every finite field, extending the previously established range of redundancies at most seven. We also prove the bound on generalized Hamming weights $d_t(C)\le2R_t(C)+1$ whenever the alphabet size $q$ satisfies $q\ge R_t(C)$. Both results use an auxiliary-code criterion that converts a covering property in the syndrome space into a weight bound. For binary primitive BCH codes, the packing radius is strictly smaller than the covering radius for every fixed error parameter and order, both at least two, once the extension degree is sufficiently large; this follows from existing covering bounds.

0.37

New Results on the Subfield Metric

cs.IT ·2026-11-13 ·Ana Kosovac, Jeanette Plechinger, Nikola Spirovski, Violetta Weger
similarity 0.59
Abstract

In this paper, we further develop the theory of the recently introduced $λ$-subfield metric. We investigate extremal codes, classical bounds and asymptotic densities in this setting. We first study codes attaining a Singleton-type bound, called Maximum $λ$-subfield Distance (M$λ$D) codes. We establish structural restrictions on their parameters and extend the theory to sublinear codes. We then investigate the asymptotic density of M$λ$D codes in several parameter regimes and compare their behavior with that of MDS and MRD codes. We then turn to a Plotkin-like bound, where we construct a family of constant-weight codes attaining the bound and classify all non-degenerate linear constant-weight codes for $λ>1$. Finally, we complement the collection of classical coding-theoretic bounds available for the $λ$-subfield metric by deriving Griesmer-, Elias- and Johnson-type bounds.

0.11

An upper bound on non-overlapping codes

cs.IT math.CO ·2026-11-16 ·Simon R. Blackburn
theory similarity 0.59
Abstract · 22 pages

Non-overlapping codes (also known as bifix-free codes or strong comma-free codes) have now been studied for over 60 years as part of information theory, with regular new applications appearing and much recent interest. Let $X$ be a binary non-overlapping code of length $n$. The paper contains a self-contained proof that \[ |X|\leq \left(\frac{5}{6e} +O(n^{-1})\right)\frac{2^n}{n} \] as $n\rightarrow\infty$. This improves, by a factor of $5/6$, the best previously known bound due to Levenshtein (1970). The paper builds on work by Fimmel, Michel, Pirot, Sereni and Strüngmann (2019), and by Stanovnik, Mo\v skon and Mraz (2024).

0.26

Concatenated Codes with One Inner Code: Low-Rate Gilbert-Varshamov Asymptotics from Algebraic-Geometric Codes

cs.IT ·2026-11-12 ·Yota Maeda, Ruho Kondo
theory similarity 0.59
Abstract · 25 pages

Constructing codes that attain the Gilbert-Varshamov (GV) bound while admitting efficient encoding and decoding is a fundamental problem in coding theory. We study concatenated codes that reuse a single binary inner code across all outer coordinates. To exploit existing encoding and decoding algorithms, we restrict the outer codes to random subcodes of scaled copies of prescribed algebraic codes and investigate their minimum distance. Our first contribution is a general upper bound on the minimum-distance failure probability that separates two terms controlled by the inner code's bias moments and the dual weight distribution of the prescribed code, together with sufficient conditions for exponential decay. Our second contribution is a concrete construction satisfying these conditions using algebraic-geometric codes from the Garcia-Stichtenoth tower. For every sufficiently small $\varepsilon>0$, we construct a family of random binary codes $C_m$ whose rates approach $\varepsilon^2$ and satisfy \[ \Pr\left[δ(C_m)\geq\frac12-\sqrt{\frac{\ln 2}{2}}\left(\varepsilon+\frac{\varepsilon^3}{2}\right)\right]\geq 1-2^{-c\varepsilon^4N_m}, \] for all sufficiently large $m$, where $N_m$ is the block length and $c>0$ is independent of $\varepsilon$ and $m$. Thus, the distance guarantee matches the leading coefficient of the GV bound at low rates. For each fixed $\varepsilon$, the construction uses a single inner encoding map throughout the family and admits polynomial-time encoding and unique decoding within a guaranteed radius. This answers the question of Doron, Mosheiff, and Wootters for subcodes of scaled algebraic geometry codes at low rates.

0.18

On the Average List Size of VT Codes under Two Insertions or Two Deletions

cs.IT ·2026-10-11 ·Anisha Banerjee, Roni Con, Antonia Wachter-Zeh, Eitan Yaakobi
theory similarity 0.59
Abstract · Submitted to ITW 2027

Levenshtein's classical theorem shows that any code that can uniquely decode from \(t\) deletions can also uniquely decode from \(t\) insertions. This symmetry, however, does not generally hold in the list-decoding regime. Several prior results on the capacity and radii of list-decoding from insertions and deletions suggest that insertions are easier to handle than deletions. In an effort to better understand this asymmetry between insertions and deletions under list-decoding, we study an analogous version of McEliece's \emph{average list size problem}. More precisely, given a binary code \(\mathcal{C}\) of length \(n\) that uniquely corrects \(t'\) insertions (or deletions), we are interested in the average number of codewords returned by a \(t\)-insertion (or deletion) list decoder, where \(t' < t\). Focusing on the case of \(t'=1\) and \(t=2\), we find that under two insertions, this quantity is at most \((n+12)/4\) for any VT code of length \(n\), whereas under two deletions it is at least \(n/2 - 10\) when averaged over all length-\(n\) VT codes. The nearly factor-of-two gap between these upper and lower bounds serves to confirm the relative ease of list-decoding of insertions compared to deletions from an average-case perspective.

0.22