Two structural restrictions that could have made generalized covering codes less efficient turn out to cost nothing in the asymptotic limit. The study finds that product-form centers can reach the same optimal rate as the ordinary sphere-covering problem. For prime-power alphabet sizes, requiring the codes to be linear also leaves that rate unchanged.
The result covers every fixed alphabet size q of at least 2 and every fixed covering order t of at least 1. The objects are t-by-n target matrices, and the t-th covering radius is measured relative to block length. The comparison is with ordinary covering over an alphabet with q to the power of t symbols, the benchmark used for the sphere-covering bound.
A benchmark with a zero-rate edge
The benchmark has a sharp two-part form. Below the threshold set by one minus q to the power of negative t, the optimal rate follows the entropy expression for an alphabet with q to the power of t symbols. At or above that threshold, the optimal rate is zero. The unrestricted theorem says the product-form setting reaches exactly this piecewise rate, including the high-radius zero-rate regime.
The lower bound comes from the sphere-covering volume argument. The constructions meet that bound in the nontrivial range, which establishes the optimal unrestricted rate. The linear theorem places the prime-power linear setting at the same benchmark.
The proof uses carefully structured randomness
Instead of counting every error within the allowed distance, the proof uses a balanced exact-type error family, a controlled subset of the full metric ball. It lies inside that ball and has the same exponential size, so the replacement preserves the asymptotic scale being measured.
The proofs are probabilistic and combine the method of types, which groups errors by shared patterns, with Janson's inequality, the second-moment method and structured alteration. Type-class estimates and Shearer's inequality provide the counts for pairs of error matrices whose differences are prescribed on selected rows.
For unrestricted codes, the construction samples t auxiliary codes independently and takes their union. The independence between rows is paired with Janson's inequality, and a union bound then gives complete coverage of the target matrices.
Linearity survives the construction
The linear case starts with a random generator matrix for the code, which covers all but a vanishing fraction of target matrices. A structured alteration then repeatedly squares the density of the uncovered targets and completes coverage with only logarithmic dimension overhead. The theorem states that linear codes attain the same piecewise rate as unrestricted codes.
A finite-length statement supports the asymptotic result. For covering order t at least 2, a rational auxiliary radius between zero and the threshold, and sufficiently large block lengths, a linear code exists with t-th covering radius no greater than that radius times the block length. Its dimension is bounded by the entropy expression evaluated at the auxiliary radius times the block length, plus a remainder of logarithmic order.
The per-target failure estimate in the random linear construction is uniform across target matrices and decreases at an order proportional to the inverse square of one plus the block length. This is an asymptotic probability bound used in the existence proof, not a statistical confidence interval.
A theorem, not a finished code
The result has a practical limitation: it establishes that suitable codes exist, but does not give explicit unrestricted or linear codes that attain the rate. The paper identifies such explicit constructions as an open problem.
The finite-length guarantee is also narrower than the asymptotic result. It is stated for rational auxiliary radii and sufficiently large lengths, with the threshold for sufficiently large and the logarithmic constants left implicit. The paper is an arXiv version 2 preprint dated 30 August 2026, and its conclusions remain mathematical existence and rate guarantees with explicit constructions unresolved.
Paper data and sources
Original title: The Optimal Asymptotic Rate of Generalized Covering Codes
Authors: Hengzhuo Li, Chong Shangguan, Hengjia Wei
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-25
DOI: Not available
Original paper · Full text