Levenshtein-type bounds for (a,b)-avoiding spherical codes
Abstract
We develop a Levenshtein-type linear programming framework (for maximal s-codes and for minimal energy) for (a,b)-avoiding spherical codes, that is, codes whose inner products between distinct points avoid (a,b). We introduce and investigate signed measures that are positive definite up to an appropriate degree and yield stationary auxiliary linear programming polynomials and exact quadrature formulas. We give explicit conditions for positivity of the quadrature weights and sufficient Krein-type conditions for nonnegative Gegenbauer coefficients (positive definiteness of the candidate optimal linear programming polynomials). Under these hypotheses and suitable node-location assumptions, the resulting cardinality bounds are optimal within the corresponding degree restriction and unique under natural nondegeneracy conditions. Under proper conditions on the quadrature nodes, we obtain universal lower energy bounds by utilizing Hermite interpolants as polynomial solutions of the respective linear program. Common test functions characterize optimality in the full polynomial linear programs under mild additional assumptions.
Related
- Constant-List Insertion--Deletion Codes:New Bounds and an Improvement of Levenshtein's Lower Bound
- Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences
- Conflict-avoiding codes and near-primitive roots
- New spherical codes by tuning an annealing solver
- Sharp Yamabe Bounds for Spherical Three-Space Forms via Four-Dimensional Poincaré--Einstein Compactness
BibTeX
@misc{boyvalenkov2026levenshteintype,
title = {{Levenshtein-type bounds for $(a,b)$-avoiding spherical codes}},
author = {Peter Boyvalenkov and Danila Cherkashin and Peter Dragnev and Peter Grabner},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.08709},
eprint = {2611.08709},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.08709},
}
RIS
TY - UNPB
TI - Levenshtein-type bounds for (a,b)-avoiding spherical codes
AU - Peter Boyvalenkov
AU - Danila Cherkashin
AU - Peter Dragnev
AU - Peter Grabner
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.08709
UR - https://arxiv.org/abs/2611.08709
AB - We develop a Levenshtein-type linear programming framework (for maximal s-codes and for minimal energy) for (a,b)-avoiding spherical codes, that is, codes whose inner products between distinct points avoid (a,b). We introduce and investigate signed measures that are positive definite up to an appropriate degree and yield stationary auxiliary linear programming polynomials and exact quadrature formulas. We give explicit conditions for positivity of the quadrature weights and sufficient Krein-type conditions for nonnegative Gegenbauer coefficients (positive definiteness of the candidate optimal linear programming polynomials). Under these hypotheses and suitable node-location assumptions, the resulting cardinality bounds are optimal within the corresponding degree restriction and unique under natural nondegeneracy conditions. Under proper conditions on the quadrature nodes, we obtain universal lower energy bounds by utilizing Hermite interpolants as polynomial solutions of the respective linear program. Common test functions characterize optimality in the full polynomial linear programs under mild additional assumptions.
ER -