Perfect codes as exact minimizers of quadratic discrepancy in q-ary Hamming spaces

arXiv:2608.01134 2026 Regularization 1 ideas extracted · analyzed Aug 31, 2026

What the math gives to ML

The paper supplies an exact global objective for measuring how uniformly a finite set of q-ary codewords covers all Hamming balls, with perfect codes attaining the minimum whenever they exist. This is transferable as a structured regularizer for discrete representation systems such as VQ tokenizers, product quantizers, and error-robust codebooks: instead of only separating codewords, it encourages every region of the discrete Hamming space to receive the correct mass at multiple radii. The exact theorem applies to hard fixed-cardinality subsets, while neural use requires a differentiable soft-assignment relaxation and should be evaluated for robustness and codebook utilization rather than claiming perfect-code optimality.

Ideas from this paper

Unverified 2026

Hamming-ball coverage regularizer

Add a multiscale Hamming-ball discrepancy penalty to a learned discrete codebook or tokenizer. The penalty forces the selected codewords to distribute their mass so that every center and radius sees approximately the global expected fraction of codewords, discouraging collapsed or highly clustered codebooks and potentially improving robustness to symbol substitutions.

Useful5/10
Difficulty5/10
Novelty7/10
Paper: Perfect codes as exact minimizers of quadratic discrepancy in q-ary Hamming spaces arXiv:2608.01134