Quantitative tiling stability from quadratic discrepancy in Hamming spaces

Abstract

Quadratic ball discrepancy measures how uniformly a code meets Hamming balls over all centers and radii. Perfect codes minimize this quantity among codes of the same cardinality. We prove a quantitative refinement: at the parameters of every nontrivial perfect code, excess discrepancy is at least a positive multiple of the discrepancy at the correction radius. The latter equals the squared deviation of the covering multiplicity from one, divided by the square of the code cardinality. The comparison applies to all codes of that cardinality. For one-error parameters, the coefficient is at least one, which is sharp uniformly over the parameters; explicit coefficients depending on the parameters can be much larger. For two-error parameters of length at least five, we obtain a positive coefficient against an algebraic benchmark under the sphere-packing and Lloyd integrality conditions, even when existence of a perfect code is unknown. The multiplicity defect also measures the failure of uniform ball noise to smooth a code distribution. Consequently, the same discrepancy excess gives explicit bounds on holes, overlaps, and divergence from the uniform distribution.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.