Hamming 空间中由二次差异度导出的定量铺砌稳定性
Quantitative Tiling Stability From Quadratic Discrepancy In Hamming Spaces
Valery, Grishin, Aryeh Lev Zabokritskiy
AI 速读 基于摘要
作者证明:在完美码参数处,任何同基数码的二次球差异度超出最小值至少是 packing 半径处差异度的显式正倍数,并借此给出洞、重叠与均匀分布偏差的显式界。
cs.IT · math.CO
查看原文摘要
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 perfect code other than a one-word code or the full space, the discrepancy excess over the minimum is at least an explicit positive multiple of the discrepancy at the packing radius. The latter equals the tiling defect divided by the square of the code cardinality. This defect is the total squared deviation of the covering multiplicity from one. The comparison applies to all codes of that cardinality. For one-error perfect codes, the coefficient is at least one, and no larger constant holds for all such codes; explicit coefficients depending on the parameters can be much larger. The tiling 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.