The Optimal Asymptotic Rate of Generalized Covering Codes
Abstract
Let Gq be an alphabet of size q≥2. We determine the optimal asymptotic rate of generalized covering codes C⊆ Gqn, whose covering centers in Gqt× n are constrained to the product form Ct. For every fixed integer t≥1 and every ρ∈[0,1], we prove that κt(ρ,q)= 1−Hqt(ρ),&0≤ρ<1−q−t, 0,&1−q−t≤ρ≤1, where κt(ρ,q) denotes the minimum asymptotic rate n−1logq|C| among codes whose t-th covering radius is at most ρn, and Hqt is the qt-ary entropy function. When q is a prime power, we prove that the same formula holds under the additional requirement that C≤𝔽qn. Thus, both the product-form constraint and linearity are asymptotically cost-free: the resulting rate is the ordinary sphere-covering rate over an alphabet of size qt. This extends the recent t=2 result of Elimelech and Schwartz for codes without a linearity constraint and the classical t=1 result of Cohen and Frankl for linear codes, thereby resolving both open problems posed by Elimelech and Schwartz. Our proofs are probabilistic and combine tools from information theory and probabilistic combinatorics, including the method of types, Janson's inequality, the second-moment method, and a structured alteration argument. Direct applications of Janson's inequality and the second-moment method are obstructed by highly dependent pairs of candidate error matrices. We overcome this obstruction by restricting the errors to a balanced exact-type class of optimal exponential size. Standard type-class estimates, together with Shearer's inequality, then give the required bounds on the number of error-matrix pairs whose selected rows have a prescribed difference.
Related
- Asymptotic Bounds on Generalized Covering Radii of Binary Primitive BCH Codes
- The Exact Second Generalized Covering Radius of Binary Primitive Triple-Error-Correcting BCH Codes
- The generalized covering radii of Melas codes
- Subspace coverings and generalized covering radii of generalized Zetterberg codes
- Auxiliary Codes and the Generalized Packing-Covering Conjecture
BibTeX
@misc{li2026optimal,
title = {{The Optimal Asymptotic Rate of Generalized Covering Codes}},
author = {Hengzhuo Li and Chong Shangguan and Hengjia Wei},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.24856},
eprint = {2608.24856},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.24856},
}
RIS
TY - UNPB
TI - The Optimal Asymptotic Rate of Generalized Covering Codes
AU - Hengzhuo Li
AU - Chong Shangguan
AU - Hengjia Wei
PY - 2026
DA - 2026/08/30
PB - arXiv
DO - 10.48550/arxiv.2608.24856
UR - https://arxiv.org/abs/2608.24856
AB - Let G_q be an alphabet of size q≥2. We determine the optimal asymptotic rate of generalized covering codes C⊆ G_q^n, whose covering centers in G_q^t× n are constrained to the product form C^t. For every fixed integer t≥1 and every ρ∈[0,1], we prove that κ_t(ρ,q)= 1−H_q^t(ρ),&0≤ρ<1−q^−t, 0,&1−q^−t≤ρ≤1, where κ_t(ρ,q) denotes the minimum asymptotic rate n^−1log_q|C| among codes whose t-th covering radius is at most ρn, and H_q^t is the q^t-ary entropy function. When q is a prime power, we prove that the same formula holds under the additional requirement that C≤𝔽_q^n. Thus, both the product-form constraint and linearity are asymptotically cost-free: the resulting rate is the ordinary sphere-covering rate over an alphabet of size q^t. This extends the recent t=2 result of Elimelech and Schwartz for codes without a linearity constraint and the classical t=1 result of Cohen and Frankl for linear codes, thereby resolving both open problems posed by Elimelech and Schwartz. Our proofs are probabilistic and combine tools from information theory and probabilistic combinatorics, including the method of types, Janson's inequality, the second-moment method, and a structured alteration argument. Direct applications of Janson's inequality and the second-moment method are obstructed by highly dependent pairs of candidate error matrices. We overcome this obstruction by restricting the errors to a balanced exact-type class of optimal exponential size. Standard type-class estimates, together with Shearer's inequality, then give the required bounds on the number of error-matrix pairs whose selected rows have a prescribed difference.
ER -