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

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.

New lower bounds for binary constant-weight codes from prescribed-automorphism search, and two quantum codes meeting their upper bounds
Chris Dzoba
arXiv16 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Improved Bounds For The Lipschitz Retraction Constant In Classical Banach Spaces
Shriram Mahesh
arXiv11 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv
Sharper Bounds for the Complex Grothendieck Constant
Steven Heilman, Chris Jones, Giulio Malavolta
arXiv21 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEs Quantum physics & quantum informationarXiv
A G-Invariant Erdős--Hanani Theorem with Applications to Optical Orthogonal and Constant-Weight Codes
Yeow Meng Chee
arXiv7 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
New Bounds for the Euclidean TSP Constant
Zhuolun Dong, Junyu Cao
arXiv2 Oct 2026PreprintarXiv licenceFull textOptimisation & control ProbabilityarXiv

Cite

BibTeX RIS

BibTeX

@misc{akhiiarov2026envelopes,
  title = {{Envelopes of upper bounds for nonbinary constant-weight and constant-composition codes}},
  author = {Artur Akhiiarov and Peter Boyvalenkov and Danila Cherkashin and Andrei Raigorodskii},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.23869},
  eprint = {2609.23869},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.23869},
}

RIS

TY  - UNPB
TI  - Envelopes of upper bounds for nonbinary constant-weight and constant-composition codes
AU  - Artur Akhiiarov
AU  - Peter Boyvalenkov
AU  - Danila Cherkashin
AU  - Andrei Raigorodskii
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.23869
UR  - https://arxiv.org/abs/2609.23869
AB  - 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.
ER  -

Abstract

Related

Cite