A Note on the Asymptotic Least Density of Covering Codes in [q]^n
Pith reviewed 2026-05-20 08:50 UTC · model grok-4.3
The pith
A small change to the optimization step improves the upper bound on the asymptotic least density of covering codes in [q]^n by a constant factor.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
By applying a slightly different optimization within the core theorem originally established by Krivelevich, Sudakov, and Vu, the upper bound on the asymptotic least density of covering codes of radius R in [q]^n can be improved by a constant factor.
What carries the argument
The modified optimization step applied inside the probabilistic method of the original core theorem.
If this is right
- The resulting upper bound is strictly smaller than the previous one by a positive constant factor.
- This improvement applies directly to the asymptotic analysis for covering codes over alphabet size q and length n.
- The modified approach maintains the validity of the probabilistic argument used in the original work.
Where Pith is reading between the lines
- This indicates that small tweaks in optimization choices can lead to better constants in similar probabilistic constructions for covering problems.
- Future work might explore other adjustments in the same framework to achieve further improvements.
Load-bearing premise
The modified optimization step can be integrated into the existing probabilistic argument without breaking any earlier steps or adding invalid constraints.
What would settle it
Computing the explicit numerical values of both the original and the improved bounds for large but finite q and R and checking if the new one is indeed smaller by a constant factor independent of n.
read the original abstract
In this short note we revisit the upper bound of the asymptotic least density of covering codes of radius $R$ in $[q]^n$ established by Krivelevich, Sudakov, and Vu. We show that by using a slightly different optimization in their core theorem we can obtain a constant factor improvement to their upper bound.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper revisits the upper bound on the asymptotic least density of covering codes of radius R in [q]^n due to Krivelevich, Sudakov, and Vu. It claims that a slight modification to the optimization step inside their core probabilistic theorem produces a constant-factor improvement to that upper bound.
Significance. If the modified parameter choice can be shown to preserve every inequality and existence probability in the original deletion/averaging argument, the note would deliver a modest but explicit constant-factor sharpening of a known upper bound on covering densities. Such an improvement, even if small, would be of interest in asymptotic coding theory provided the new optimum is computed and verified explicitly.
major comments (1)
- The manuscript states that a different optimization yields a constant-factor improvement but does not exhibit the new parameter values, the resulting explicit bound, or the verification that the altered choice remains valid inside the probabilistic argument of the KSV theorem. Without these details the central claim cannot be checked.
Simulated Author's Rebuttal
We thank the referee for the careful reading and for recognizing the potential interest of a constant-factor sharpening of the KSV bound. We address the single major comment below and will revise the manuscript to supply the requested explicit details.
read point-by-point responses
-
Referee: The manuscript states that a different optimization yields a constant-factor improvement but does not exhibit the new parameter values, the resulting explicit bound, or the verification that the altered choice remains valid inside the probabilistic argument of the KSV theorem. Without these details the central claim cannot be checked.
Authors: We agree that the note would be stronger and more verifiable if the new parameter values, the resulting explicit improvement factor, and a brief check that the modified choice preserves the key inequalities and positive existence probability are included. In the revision we will add a short paragraph (or appendix) that states the altered optimization problem, gives the concrete parameter values that achieve the improvement, computes the numerical constant factor gained over the original KSV choice, and confirms that every inequality used in the deletion/averaging argument continues to hold with the new parameters. Because the original KSV argument is a standard probabilistic deletion method whose only requirements are certain lower bounds on the success probability and upper bounds on the expected number of uncovered points, the verification reduces to re-plugging the new parameters into those same expressions and checking the signs; this is straightforward and will be carried out explicitly. revision: yes
Circularity Check
No significant circularity
full rationale
The paper is a short note that revisits the KSV upper bound on asymptotic covering density and claims a constant-factor improvement via a modified optimization inside the cited probabilistic argument. This adjustment is presented as preserving all original inequalities and existence probabilities without introducing new constraints or reducing to a fitted parameter. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear; the derivation relies on an external theorem by different authors plus an independent re-optimization, making the chain self-contained against the cited benchmark.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption The core theorem of Krivelevich, Sudakov, and Vu remains valid when the optimization step is altered in the manner described.
Reference graph
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.