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.
Related
- Perfect codes as exact minimizers of quadratic discrepancy in q-ary Hamming spaces
- Quantitative comparison of closed- and open-loop linear-quadratic N-player differential games
- Quantitative finite-population approximation of heterogeneous linear--quadratic mean-field control with common noise
- Quantitative Universality of Approximate Message Passing for Rank-One Quadratic Sensing
- Input-to-State Stability Framework for Fully Distributed Primal-Dual Dynamics for Quadratic GNEPs Without Multiplier Consensus
BibTeX
@misc{valery2026quantitative,
title = {{Quantitative tiling stability from quadratic discrepancy in Hamming spaces}},
author = {Valery and Grishin and Aryeh Lev Zabokritskiy},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.25716},
eprint = {2608.25716},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.25716},
}
RIS
TY - UNPB
TI - Quantitative tiling stability from quadratic discrepancy in Hamming spaces
AU - Valery
AU - Grishin
AU - Aryeh Lev Zabokritskiy
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2608.25716
UR - https://arxiv.org/abs/2608.25716
AB - 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.
ER -