PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantitative tiling stability from quadratic discrepancy in Hamming spaces

Valery, Grishin, Aryeh Lev Zabokritskiy

arXiv:2608.25716v1cs.ITmath.CO

TL;DR

The paper addresses whether near-minimal quadratic ball discrepancy forces approximate perfect tiling, a question not answered by exact minimization alone. It derives coercive spectral and moment bounds for unrestricted codes and obtains explicit one- and two-error stability coefficients, with smoothing consequences and stated arithmetic scope limits.

  • Problem

    Exact minimization identifies perfect codes but does not provide explicit quantitative control of holes, overlaps, or approximate tiling when discrepancy is near the benchmark.

  • Method

    The paper combines spectral and moment identities with quadratic discrepancy comparisons to bound the squared ball-covering multiplicity defect for all fixed-parameter code subsets.

  • Results

    κn,q/q^2 ≥ 1 for one-error parameters, while two-error arithmetic parameters with n ≥ 5 and two distinct integral Lloyd roots admit an explicit positive coefficient without perfect-code existence.

  • Takeaways & Limitations

    Excess discrepancy controls tiling defects and consequently holes, overlaps, defective ambient points, and divergence measures of the uniform ball-noise output.

  • Takeaways & Limitations

    The two-error asymptotic is an asymptotic of the displayed expression, not an assertion that infinitely many admissible parameter pairs exist.

Abstract

from arXiv · show

Quadratic ball discrepancy defines an energy on codes in finite Hamming spaces. At perfect-code parameters, its exact minimizers are the perfect codes. We fix the alphabet size, length, and code cardinality and compare all codes with these parameters. We prove tiling-defect stability: excess discrepancy above the perfect-code benchmark controls the squared deviation of the distinguished ball-covering multiplicity from one. For one-error parameters satisfying sphere-packing and Lloyd integrality, the lower coefficient is $κ_{n,q}/q^2\geq1$. The uniform floor one is sharp, while the certified parameter-dependent coefficient can be much larger. An explicit parameter-dependent upper estimate is also available, and the two certified coefficients can be far apart. For any two-error parameter pair with $n\geq5$ satisfying sphere-packing divisibility and having two distinct integral Lloyd roots in the Hamming weight range, we obtain an explicit positive coefficient without assuming that a perfect code exists. For alphabets of size at least four, this conditional coefficient has a closed form and fixed-alphabet asymptotics. Direct certificates for the repetition and Golay families, combined with perfect-code classification, give tiling-defect stability for every nontrivial perfect code. Here stability concerns the ball-covering multiplicity profile, not symmetric-difference proximity to a particular perfect code. The defect is also a normalized chi-square smoothing error under uniform ball noise, so excess discrepancy controls holes, overlaps, defective ambient points, total variation, and Rényi divergence from uniformity of the ball-noise output. Competing codes need not be linear or satisfy a distance or error-correction constraint.

1. Introduction

The paper develops explicit quantitative stability for quadratic ball discrepancy in finite Hamming spaces, showing that excess energy controls failure of perfect tiling across broad arithmetic parameter regimes. It also connects the tiling defect to code smoothing and clarifies that competitors are unrestricted code subsets.

  • Motivation: The paper asks whether discrepancy near the perfect-code benchmark forces Hamming balls to form an approximate tiling, beyond the nonquantitative gap supplied by finiteness.The prior exact-minimizer result did not provide an explicit, interpretable, or parameter-uniform estimate or explain detection of holes and overlaps.
  • Core mechanism: Excess total quadratic discrepancy controls the squared radius-e tiling defect, preventing other radii from quantitatively compensating for a defect at the distinguished radius.When NVe = q^n, the radius-e discrepancy summand equals the multiplicity-defect term, but the paper proves that this local defect cannot be canceled globally.
  • Main results: For one-error parameters, the certified lower coefficient is κn,q/q^2 ≥ 1; the uniform floor one is sharp, while the parameter-dependent coefficient can be much larger.For q ≥ 4 the coefficient is evaluated explicitly, and an explicit upper coefficient may differ from the lower coefficient by many orders of magnitude.
  • Main results: For two-error parameters with n ≥ 5 and two distinct integral Lloyd roots, the paper gives an explicit positive coefficient without assuming that a perfect code exists.This is a conditional arithmetic result over every alphabet satisfying the hypotheses, not an existence assertion; for q ≥ 4 the coefficient has a closed form and fixed-alphabet asymptotics.
  • Scope: The stability notion controls the covering multiplicity function rather than symmetric-difference distance from a particular perfect code, and the competitors need not be linear or distance-constrained.The paper also uses a finite abelian-group relabeling only for Fourier analysis, preserving discrepancy and tiling quantities without restricting alphabet size.

2. The tiling defect and the main results

The paper defines a fixed-radius ball-covering defect and proves that discrepancy excess controls it, with explicit certificates covering perfect and certain formally admissible parameters.

  • Defect and setup: The squared tiling defect measures deviation of radius-e ball multiplicities from one, with holes and defective ambient points recorded separately.The setup fixes alphabet size q, length n, and code cardinality N, without requiring competitors to correct errors.
  • Defect and smoothing: The defect equals a normalized chi-square smoothing error when NVe = q^n, linking ball coverage to uniformity of ball-noise output.The same framework also yields bounds involving overlaps, holes, total variation, and Rényi divergence.
  • General certificate: A positive discrepancy certificate implies bounds on the tiling defect and associated smoothing and combinatorial errors.The proposition applies a parameter-only benchmark and constant σ to every N-word code satisfying NVe = q^n.
  • Main stability results: For nontrivial perfect codes, explicit coefficients include σn,q,1 = 1, the two-error coefficient from Corollary 5.10, binary repetition σ2e+1,2,e = 1, and Golay σ23,2,3 = 4136/25.Equality with the perfect-code benchmark holds exactly for perfect e-error-correcting codes.
  • Scope: The stability conclusion concerns the ball-multiplicity profile, not edit-distance or symmetric-difference proximity to a particular perfect code.The radius-one summand is subtracted because it vanishes for the perfect code while the remaining radii still favor its benchmark.

3. Spectral inputs

The spectral framework expresses discrepancy and tiling defect through Fourier coefficients and Krawtchouk weights, while moment and Lloyd-support identities supply the comparisons used in stability proofs.

  • Spectral framework: Fourier expansion writes discrepancy and tiling defect as sums over common nonnegative frequency coordinates with different weights.The stability argument compares these weights after subtracting the parameter-only benchmark.
  • Nonlinear codes: The nonnegative transform A⊥ applies to nonlinear codes as a Fourier quantity rather than as the distribution of a dual code.This keeps the spectral identities applicable beyond linear coding settings.
  • Ball transforms: Hamming-ball Fourier coefficients depend on frequency weight through q-ary Krawtchouk polynomials, and the coefficient vanishes at t = n.The displayed transform is organized by the weight w of the frequency.
  • Lloyd support: For a perfect code, the nonconstant Fourier spectrum is supported on integer roots of the Lloyd polynomial.These roots are the possible nonconstant dual Hamming weights used in the perfect-code analysis.
  • Moment identities: One-error moment identities and overlap counting connect code distance distributions to the radius-one tiling defect.Distinct radius-one balls intersect in q points at center distance one, two points at distance two, and otherwise not at all.

4. One-error stability

The one-error results give explicit lower and upper controls of the radius-one tiling defect by discrepancy excess, with a sharp uniform lower coefficient and sharper parameter-dependent bounds.

  • Uniform stability: Theorem 4.1 gives every prescribed-cardinality code a uniform one-error stability bound, with coefficient one best possible across admissible parameters.Sharpness holds for every odd n and at ternary Hamming parameters (3, 4, 9).
  • Proof mechanism: The proof treats the tiling defect as a centered second spectral moment and uses a quadratic minorant of W touching at weights k − 1 and k.Strict convexity and curvature bounds yield the certified coefficients.
  • Parameter-dependent comparison: Theorem 4.2 strengthens the lower bound to κn,q/q^2 ≥ 1 and supplies an explicit parameter-dependent upper coefficient.The two certified coefficients can differ by many orders of magnitude.
  • Equality and competitors: The benchmark is attained exactly by perfect one-error-correcting codes, while the conclusion applies to arbitrary subsets with the prescribed cardinality.No linearity, distance, or error-correction constraint is imposed on competing codes.
  • Parameter scope: The parameter-dependent coefficient can be much larger than the uniform floor one, but the numerical comparisons apply only at parameter sets satisfying both integrality conditions.The inequalities establishing the coefficient bounds do not require N = q^n/V to be an integer, whereas the theorem’s admissible one-error parameters do.

5. Two-error stability

The two-error analysis gives conditional stability certificates from arithmetic admissibility, including explicit positive coefficients for q≥4, without requiring a perfect code to exist. Direct binary and ternary arguments complete the all-alphabet two-error results, with sharp coefficients in the repetition case.

  • Conditional arithmetic framework: The two-error theorem assumes sphere-packing divisibility and two distinct integral Lloyd roots, treating these as arithmetic conditions rather than existence assumptions.The formal benchmark and comparison data need not be realized by a code.
  • Large-alphabet estimate: For q≥4, the conditional coefficient is positive, has a closed form, and admits fixed-q asymptotics.The asymptotic concerns the analytic expression, not infinitely many admissible parameter pairs.
  • Large-alphabet estimate: The proof compares an arbitrary code’s distance distribution with a formal two-root reference whose first four distance entries vanish as in a perfect two-error code.A discrepancy-potential gap is then compared with the radius-two intersection-moment gap.
  • Binary repetition codes: The coefficient-one bound for odd binary repetition codes is sharp for every odd length.Equality of the kernel comparison at distances n−2 and n−1 shows the coefficient cannot be increased.
  • All-alphabet theorem: The all-alphabet two-error theorem applies under the same arithmetic hypotheses, while nonexistent perfect codes leave a positive gap above the formal benchmark.The ternary Golay parameters provide a realized case where the benchmark is attained precisely by perfect two-error-correcting codes.

6. The remaining perfect codes

Direct certificates handle the binary Golay and remaining repetition families, and perfect-code classification then extends tiling-defect stability to every nontrivial perfect code. Equality in the benchmark characterizes perfect codes in the treated families.

  • Binary Golay family: Every perfect three-error-correcting code attains the benchmark, with equality holding precisely for perfect three-error-correcting codes.This supplies the direct certificate needed for the Golay branch.
  • Binary Golay family: The binary Golay certificate is attained by the classical binary Golay code, and equality at the benchmark forces perfection.The argument uses the parameter identity NV3 = 2^23.
  • Classification and coverage: For every nontrivial perfect code, the benchmark inequality has equality exactly when the competitor is perfect.The full-space and one-word codes are excluded as trivial cases without nonperfect competitors of the same cardinality.

7. Consequences

The stability estimates translate discrepancy excess into concrete coverage and smoothing controls for arbitrary same-size competitors. These controls concern local overlap structure rather than a minimum-distance requirement, and they do not constitute a wiretap security theorem.

  • Coverage and smoothing: The same stability framework applies to every competitor with the perfect code’s cardinality, through the stated global theorem and defect dictionary.The comparison is formulated for a nontrivial perfect code P and any same-size competitor C.
  • Coverage and smoothing: The discrepancy excess controls the exact fraction of uncovered ambient points, linking analytic smoothing error to combinatorial coverage failure.The left side of (91) is exactly the fraction of uncovered points.
  • Scope: The smoothing interpretation yields resolvability consequences, not a wiretap or cryptographic security theorem.A message-indexed encoder, channel model, and separate reliability and secrecy analyses would be additionally required.
  • Coverage and smoothing: The resulting bounds control holes, overlaps, close pairs, and failure of uniform ball noise to smooth the code distribution.The estimates apply to arbitrary competitors and quantify all local overlaps rather than imposing minimum distance.

8. Conclusion

The paper establishes quantitative stability of ball-covering multiplicities from excess quadratic discrepancy, while identifying limits and open extensions of the result.

  • Main conclusions: Excess total quadratic discrepancy controls tiling defect and derived defects such as holes, overlaps, close pairs, and nonuniform ball-noise smoothing.The estimates apply over finite alphabets and do not require competing codes to satisfy distance or error-correction constraints.
  • Main conclusions: For one-error parameters, the certified lower coefficient can greatly exceed the sharp uniform floor, while the explicit upper estimate may be much larger.The certified coefficients can therefore be far apart.
  • Main conclusions: For two-error parameters with n ≥5, an explicit positive coefficient is obtained under sphere-packing divisibility and two distinct integral Lloyd roots, without assuming a perfect code exists.For q ≥4, the coefficient has a closed form and fixed-alphabet asymptotics.
  • Scope: The result controls multiplicity-profile defect, not symmetric-difference proximity to a particular perfect code.A removal theorem establishing code proximity remains a separate problem.
  • Open problems: Optimal parameter-dependent stability constants remain open because the positivity certificates need not be optimal over code-realizable dual distributions.Extensions to broader error patterns and other association schemes require new positivity arguments.
  • Open problems: When exact tiling is unavailable, natural reference profiles include nearly-perfect covering codes, but total-discrepancy optimality beyond the studied settings remains unresolved.Radius-specific optimality does not automatically imply total discrepancy minimization across all radii.

Appendix A. Reproduced prerequisites

The appendix records Fourier, Parseval, convolution, and positivity identities that underpin discrepancy formulas and perfect-tiling certificates in finite Hamming spaces.

  • Fourier and coefficient identities: The reproduced prerequisites derive coefficient identities for Hamming-space polynomials using coordinatewise character orthogonality and Parseval.These identities connect polynomial coefficients and Fourier-weight contributions.
  • Distance distributions: The appendix expands Fourier squares over ordered codeword pairs and groups contributions by Hamming distance.Character orthogonality determines which coordinate choices contribute at each distance.
  • Perfect tiling: Perfect tiling is represented by the convolution identity 1_P ∗ 1_B(0,e) = 1_Xn.Fourier vanishing conditions then characterize the corresponding dual constraints.
  • Invariance identity: Barg’s invariance identity follows by expanding discrepancy squares, applying a threshold identity, and canceling constant terms.The resulting relation is stated in the paper’s normalization.
  • Positivity: Positive finite-difference representations establish monotonicity and complete monotonicity properties needed for the discrepancy comparisons.For q ≥4, the relevant alternating differences are strictly positive.
  • Integral-root cases: At binary two-error parameters, arithmetic arguments reduce the integral-root possibilities to n = 5 with N = 2 and roots (r, s) = (2, 4).For q = 3, the corresponding conclusion is n = 11 and N = 36.

Appendix B. The ternary local-slope certificate

The ternary appendix supplies an explicit coefficient certificate whose positivity is proved through coefficient extraction, telescoping identities, and finite-sum representations.

  • Role in the paper: The appendix reproduces the ternary coefficient certificate because it is a load-bearing input to the paper’s quantitative estimates.The perturbative subtraction and coefficientwise regrouping are identified as new contributions in Section 5.
  • Coefficient representation: The ternary slope coefficient γ_r is represented through coefficient differences involving the anti-reciprocal polynomial H_r(z).The anti-reciprocity identifies the relevant coefficients as −γ_r and γ_r.
  • Positivity certificate: The proof converts γ_r into a finite sum using a Parseval representation specialized to n = 3r + 1, q = 3, and w = 2r.A two-to-one substitution yields the displayed finite-sum form.
  • Telescoping certificate: A rational telescoping identity is verified after clearing denominators and summing over the coefficient index.Boundary identities complete the certificate.
  • Positivity certificate: For every r ≥1, the ternary slope coefficient satisfies γ_r ≥2.The initial values include γ_1 = 2, γ_2 = 15, γ_3 = 188, γ_4 = 2977, and γ_5 = 54468.
  • Quadrature comparison: The associated quadrature and Delsarte comparison use two Lloyd roots and nonnegative Newton coefficients to compare the relevant transformed quantities.The comparison yields g^TQ ≥ g^TQ* for the specified dual distributions.

Appendix D. Evaluation of the two-error coefficient

The appendix evaluates the two-error coefficient by combining Lloyd-root arithmetic with right-Newton expansions, finite-difference positivity, and an explicit endpoint formula.

  • Lloyd-root arithmetic: The two integral Lloyd roots satisfy arithmetic restrictions derived from their sum and separation identities, together with q | 2(n−2).The argument excludes initial candidate values through parity and square-integrality constraints.
  • Coefficient setup: For q ≥4 and n ≥5, the coefficient evaluation extends the definitions of F_t and M_t to all 0 ≤ t ≤ n.The quantities are defined by right-diagonal differences of the relevant functions.
  • Finite-difference structure: Complete monotonicity is characterized by nonnegative right-diagonal differences, while the moments M_t vanish for 5 ≤ t ≤ n.The corresponding F_t remain positive through t = n−1, with F_n = 0.
  • Closed-form evaluation: Evaluating the ratio at t = 4 gives ϑ_n,q = F_4/6 and supplies the fixed-q asymptotics.This follows from M_4 = 6 and the beta-integral evaluation.
  • Normalization: The appendix’s benchmark calculations are reproduced from earlier Golay appendices to preserve the exact normalizations used in later attainment assertions.These calculations support Propositions 5.9 and 6.1.

E.1. Reproduced benchmark evaluations.

The benchmark tables are established by exact evaluations of the weight functions, certificate polynomials, and Lloyd factors. The reproduced checks certify the ternary and binary Golay parameter bounds through explicit minimizing ratios.

  • For ternary perfect parameters, the nonconstant dual spectrum is restricted to weights 6 and 9, while minimum distance forces A1 = A2 = 0.Mass and first-moment identities are then applied to these restricted weights.
  • For the binary parameters, the perfect code has nonconstant dual-spectrum weights only at 8, 12, and 16, with p(8) = p(16) = 3 121 560 and p(12) = 705 432.The minimum-distance condition gives A1 = · · · = A4 = 0.
  • Exact evaluation of Wn,q(w), certificate polynomials, and Lloyd factors reproduces the benchmark tables and supplies an independent arithmetic verification.The archived verifier independently reproduces the same calculations.
  • For the ternary Golay parameters, the minimum nonzero ratio is 274/9, attained at w = 7 and w = 10, proving (76).The certificate also has c6(2) = c9(2) = 0.
  • For the binary Golay parameters, reflection symmetry reduces the check to 1 ≤ w ≤ 12, with roots at w = 8, 12 and their reflected counterpart w = 16.At the nonzero minimum, the ratio is 4136/25 at w = 11 and, by reflection, w = 13, proving (89).
Loading 2608.25716v1…