New upper and lower bounds on covering codes K_q(n,R) for alphabets of size 5 <= q <= 21
Abstract
Let K_q(n,R) denote the minimum cardinality of a q-ary code of length n with covering radius R. We improve the known bounds on K_q(n,R) in 83 cases (82 distinct cells). On the upper-bound side we give 25 improved bounds for 5<=q<=15 -- twenty-four found by search and one propagated by monotonicity -- using two complementary methods: an engineered focused local search seeded with structural constructions, and a large-neighbourhood search driven by exact full-space coverage transforms that evaluates every candidate codeword position simultaneously. These are, to our knowledge, the first improvements to any upper bound on K_q(n,R) with q >= 5 since the 2011 revision of Keri's tables; several bounds decrease by more than 20%, e.g. K_6(8,4)<=166 (previously 216) and K_8(10,5)<=1883 (previously 2461). On the lower-bound side we give 58 improved bounds for 6<=q<=21, obtained from the semidefinite programming hierarchy of Gijswijt and Polak, whose published results cover q<=5, by combining an exact-arithmetic reimplementation of the reduced program with a multiprecision solution pipeline. Every new lower bound is certified by a rational dual solution validated by a standalone exact-arithmetic checker; no floating-point computation is part of the trusted base. The same pipeline also gives strong numerical evidence of limits: on a dozen further cells the certified value of the relaxation, which the solver reports as optimal to within its working precision, lies below the best known bound, indicating that no improvement is available there at this level of the hierarchy. One cell is improved from both sides: 441<=K_6(10,4)<=2751, previously 417--2952. All codes and certificates are provided in machine-readable form together with standalone verifiers.
Related
- New lower bounds for binary constant-weight codes from prescribed-automorphism search, and two quantum codes meeting their upper bounds
- Asymptotic Bounds on Generalized Covering Radii of Binary Primitive BCH Codes
- Asymptotically Tight Bounds for Generalized Covering Radii of Binary Primitive BCH Codes at All Higher Orders
- Explicit upper and lower bounds on certain functions related to ζ(s) for s>1
- Upper and lower bounds for heat kernels with very strong degeneracy
BibTeX
@misc{marosi2026upper,
title = {{New upper and lower bounds on covering codes K_q(n,R) for alphabets of size 5 <= q <= 21}},
author = {Mark Marosi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.19872},
eprint = {2608.19872},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.19872},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - New upper and lower bounds on covering codes K_q(n,R) for alphabets of size 5 <= q <= 21
AU - Mark Marosi
PY - 2026
DA - 2026/09/02
PB - arXiv
DO - 10.48550/arxiv.2608.19872
UR - https://arxiv.org/abs/2608.19872
AB - Let K_q(n,R) denote the minimum cardinality of a q-ary code of length n with covering radius R. We improve the known bounds on K_q(n,R) in 83 cases (82 distinct cells). On the upper-bound side we give 25 improved bounds for 5<=q<=15 -- twenty-four found by search and one propagated by monotonicity -- using two complementary methods: an engineered focused local search seeded with structural constructions, and a large-neighbourhood search driven by exact full-space coverage transforms that evaluates every candidate codeword position simultaneously. These are, to our knowledge, the first improvements to any upper bound on K_q(n,R) with q >= 5 since the 2011 revision of Keri's tables; several bounds decrease by more than 20%, e.g. K_6(8,4)<=166 (previously 216) and K_8(10,5)<=1883 (previously 2461). On the lower-bound side we give 58 improved bounds for 6<=q<=21, obtained from the semidefinite programming hierarchy of Gijswijt and Polak, whose published results cover q<=5, by combining an exact-arithmetic reimplementation of the reduced program with a multiprecision solution pipeline. Every new lower bound is certified by a rational dual solution validated by a standalone exact-arithmetic checker; no floating-point computation is part of the trusted base. The same pipeline also gives strong numerical evidence of limits: on a dozen further cells the certified value of the relaxation, which the solver reports as optimal to within its working precision, lies below the best known bound, indicating that no improvement is available there at this level of the hierarchy. One cell is improved from both sides: 441<=K_6(10,4)<=2751, previously 417--2952. All codes and certificates are provided in machine-readable form together with standalone verifiers.
ER -