PaperlayerView exact revision on arXiv

Source-linked AI summary

The half-rate linear programming bound for binary codes is $\frac12-\frac1\pi$

Andrew Salmon

arXiv:2609.03736v2math.COcs.ITmath.IT

TL;DR

The paper addresses the high-dimensional binary-coding analogue of a sphere-packing linear-programming result. It proves a half-rate Delsarte bound exactly at one distance, using Krawtchouk uncertainty results and a hierarchy construction.

  • Problem

    The paper studies the asymptotic Delsarte rate bound for binary codes, whose computation remains challenging.

    Source: §1 · p. 2

  • Method

    It connects Krawtchouk eigenfunction uncertainty to the Delsarte program, using mass concentration for a lower bound and an N-qubit projection construction for the hierarchy.

    Source: §1 · p. 3, §3 · p. 14, §4.2 · p. 25

  • Results

    At δπ, the paper determines the Delsarte rate bound exactly as 1/2.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    At rate 1/2, feasible Delsarte dual solutions can be treated as Krawtchouk eigenfunctions, supporting a mass-concentration lower-bound approach.

    Source: §3 · p. 14

    The stated moving-subspace framework is set for finite groups and finite-dimensional unitary H-modules.

    Source: §2 · p. 5

Abstract

from arXiv · show

In their work on sphere packing and the modular bootstrap, Afkhami-Jeddi, Cohn, Hartman, de Laat, and Tajdini conjectured the exact high-dimensional exponent of the Cohn-Elkies sphere-packing linear program. OpenAI's Chapter 1 subsequently proved their conjecture by establishing that both Fourier sign-uncertainty radii are $(1/\pi+o(1))\sqrt d$. We prove the binary coding analogue: \[ R_D\!\left(\frac12-\frac1\pi\right)=\frac12. \] We also formulate the two Krawtchouk sign-uncertainty problems and determine both of their asymptotics. If $A^{\mathrm K}_{\pm}(n)$ denotes the smallest radius $r$ for which a nonzero Krawtchouk $(\pm1)$-eigenfunction $f$ exists with $f(0) = 0$ and $f(x) \ge 0$ for all $|x| \ge r$, then \[ \frac{A^{\mathrm K}_{\pm}(n)}n\longrightarrow \frac12-\frac1\pi. \] The lower bound proves a mass-concentration principle similar to OpenAI's Chapter 1 for Hamming space. The upper bound, on the other hand, follows the approach of the spherical-code construction in OpenAI's Chapter 2. Gay, Jeronimo, and Liu formulated a hierarchy for binary codes analogous to the spherical-code construction and improved the best known binary coding rate bounds by evaluating the first level of the corresponding hierarchy. We prove this hierarchy bounds the Delsarte program and give a construction at arbitrarily deep levels of the hierarchy, attaining the upper bound in the limit. The construction uses an $N$-qubit generalization of the pure-state channel of Alrabiah and Guruswami.

1. Introduction

The paper determines the half-rate Delsarte bound exactly at a point in (0, 1/2), and develops Krawtchouk uncertainty results and a hierarchy construction around that determination. It draws on both a mass-concentration argument and an N-qubit projection construction.

1. Introduction

  • The paper formulates Krawtchouk sign-uncertainty problems for both eigenvalue signs and proves lower bounds for both.The eigenfunctions vanish at layer zero and are nonnegative on all layers from a specified radius onward.Source: §1 · pp. 2–3
  • The paper relates the (−1)-eigenfunction uncertainty radius to the Delsarte bound at rate 1/2, despite the absence of a Euclidean-style rescaling connection.The authors motivate the relation by observing that feasible Delsarte solutions at rate 1/2 behave like weight enumerators of self-dual codes.Source: §1 · p. 3
  • The main theorem gives the first exact determination of the Delsarte rate bound RD(δ) at some point δ in (0, 1/2), with the paper’s primary interest being the half-rate linear-programming bound.Source: §1 · p. 2
  • A mass-concentration inequality yields the lower bound for the (−1)-eigenfunction uncertainty problem, while a half-disk Dirichlet problem controls Krawtchouk polynomials.Cauchy’s formula is then used to control their coefficients.Source: §1 · p. 4
  • The upper-bound strategy extends the finite moving-subspace bound to higher multiplicity spaces and uses a semiclassical limit.The N-qubit projection construction gives a construction at hierarchy level 2N+1, with value J_N.Source: §1 · p. 4

Use of generative artificial intelligence

  • The generative-AI disclosure credits GPT-5.6 Sol with drafting and proof-related assistance, while the author takes responsibility for the article’s statements and proofs.The disclosure also credits Sol with suggesting the N-qubit projection construction and computation of J.Source: Use of generative artificial… · pp. 4–5

2. A Hecke-algebra generalization of the finite moving-subspace bound

This section extends the finite moving-subspace bound to generalized Hecke algebras for arbitrary finite-dimensional H-modules, developing tools to connect it to scalar kernels on G/H and analyze Horn-pair asymptotics. It shows that normalized Horn pairs can be asymptotically realized by the construction, yielding ordinary radial Krawtchouk dual certificates and an associated rate bound.

2.1. Hecke algebra preliminaries.

  • The induced representation’s commutant forms the generalized Hecke algebra, and multiplication by a positive-type coordinate induces a unital completely positive map.The associated isotypic map Θ is completely positive, subunital, and self-adjoint for the ordinary operator trace.Source: §2.1 · pp. 5, 7

2.2. The generalized moving-subspace bound.

  • The bilinear trace contraction preserves positive cones, transporting positive bundle-kernel constructions into positive-type scalar kernels on G/H.This contraction underlies the generalized moving-subspace bound, which yields a feasible scalar kernel for bounding Schrijver’s ϑ′ and specializes to the Hamming-space linear programming bound.Source: §2.2 · p. 8

2.3. Horn pairs and asymptotic bounds.

  • The section defines normalized Horn pairs through Γ(K, L) = 2 tr(K^1/2L^1/2) and Φ(K, L) = Ent(K) + Ent(L) − Ent(K + L).Gay, Jeronimo, and Liu identify Φ with uniform-prior Holevo information and (1 − Γ)/2 with pretty-good-measurement bit error, then use Φ in a matrix hierarchy [GJL26, Proposition 8.1] [GJL26, Definition 8.2 and Theorem 8.3].Source: §2.3 · p. 10
  • Keyl–Werner concentration gives convergence in probability of normalized partition row lengths to the density matrix spectrum.The section applies this result to show that the relevant B_n- and S_n-isotypic projections concentrate on types whose normalized partition data approach the spectra of K, L, and K + L.Source: §2.3 · p. 11

2.3. Horn pairs and asymptotic bounds

  • The trace of the ambient operator concentrates on the joint typical subspace, enabling asymptotic dimension and rank bounds for supported positive Hecke operators.The proof combines these bounds using the entropies of K, L, and G.Source: §2.3 · p. 12
  • Every normalized Horn pair has an asymptotic realization through the generalized moving-subspace construction.The realization uses positive Hecke operators supported on the joint typical subspace, with eigenvalues approaching the Horn-pair value.Source: §2.3 · pp. 13–14
  • The asymptotic realization yields an ordinary radial Krawtchouk dual certificate with objective bounded by a constant multiple of Dρn/rρn, proving the associated rate bound.This uses Theorem 2.11 when Λn − τn is bounded below by a positive constant.Source: §2.3 · p. 14

3. The half-disk uncertainty principle

The section develops Krawtchouk mass concentration to bound sign-uncertainty radii and the Delsarte linear-programming rate at one half, and gives a dilution criterion for normalized Horn pairs. It also uses normalized Horn pairs to bound the Delsarte rate and concludes that J cannot exceed 2/π.

3. The half-disk uncertainty principle.

  • At rate 1/2, feasible dual solutions of the Delsarte program give Krawtchouk eigenfunctions, motivating a mass-concentration bound.The section relates this perspective to the analogy between Delsarte dual solutions and weight enumerators for self-dual codes.Source: §3 · p. 14

3.1. The analytic core.

  • For every fixed c < δπ, every g ∈ E+ has the sum in Equation (3.18) over indices i < ⌈cn⌉ bounded by Cc e^−γc n, with Cc, γc > 0.Source: §3.1 · p. 17

3.2. The Krawtchouk sign uncertainty principle.

  • The mass-concentration theorem yields liminf A^K_±(n)/n ≥ 1/2 - 1/pi for both Krawtchouk sign-uncertainty problems.The argument uses the Hamming-space analogue of the mass-concentration mechanism in [Ope26, Chapter 1].Source: §3.2 · pp. 17–18

3.3. Why the rate is one half.

  • For every c < 1/2 - 1/pi, the rate-one-half Delsarte bound satisfies R_D(c) ≥ 1/2.The proof uses the mass bound for (−1)-eigenfunctions and a shortening argument to pass to the endpoint.Source: §3.3 · p. 20

3.4. The upper bound on J.

  • For a normalized Horn pair, the dilution lemma applies when 0 < δ < 1/2 and 1 - 2δ < Γ(K, L).Source: §3.4 · p. 21
  • For every normalized Horn pair, 1/2 ≤ R_D(δπ) ≤ (2/π)Γ(K,L)Φ(K,L).The bound follows by scaling the pair and letting the scale decrease to (1 − 2δ)/Γ.Source: §3.4 · p. 21
  • Every normalized Horn pair satisfies J(K,L) ≤ 2/π.If J(K,L) were larger, the argument would produce a normalized positive pair with Φ = 1/2 and Γ > 2/π, contradicting Corollary 3.12.Source: §3.4 · p. 21

4. Construction of Horn pairs approaching J = 2/π

This section constructs normalized finite-dimensional Horn pairs with J-values approaching 2/π, using projective-channel and N-qubit formulations followed by a Chebyshev specialization. The Chebyshev construction gives an explicit error term, derived by evaluating the defining integrals and reducing them to a cotangent expansion.

4. Construction of Horn pairs approaching J = 2/π

  • Commuting K and L pairs do not suffice to reach the target, so the construction must account for their relative position.The section notes that the fixed-dimension feasible set is convex, but J is not concave.Source: §4 · p. 22
  • J_N = (1/2^N) cot(π/4^N) = 2/π − π/(24N^2) + O(N^-4), so the constructed Horn pairs approach 2/π.The resulting Gram-symmetrized pair has parameters (Φ, Γ) = (1/2, J_N).Source: §4 · p. 24

4.1. Projective channels and the pretty good measurement.

  • The pretty good criterion implies that ppgm(σ0, σ1) < δ gives R_D(δ) ≤ χ(σ0, σ1), and it bounds the Delsarte bound [AG26, Theorem 1].The section identifies this as the asymptotic form of the pretty good criterion.Source: §4.1 · p. 24

4.2. The N-qubit projection.

  • For the N-qubit state and projection, J(K, L) = (u + v)/2, with v from the ordinary covariance and u from a rank-one perturbed covariance.The construction generalizes the binary pure-state channel and recovers it when N = 1.Source: §4.2 · pp. 25–27

4.3. The Chebyshev specialization.

  • The Chebyshev specialization makes both scalar measures explicit, and both corresponding integrals approach 2/π.Its η entries are cosines of the midpoints of N equal subintervals of [0, π], with equal weights.Source: §4.3 · p. 29
  • The proof evaluates both integrals, rewrites sine sums as imaginary parts of geometric series, and uses a cotangent identity and Laurent expansion.It uses cot x + csc x = cot(x/2) and the monotonicity of x cot x as x approaches 0 from above.Source: §4.3 · p. 31
  • For this specialization, the difference 2/π − J(K_N, L_N) equals π/(24N^2) + O(N^-4), and therefore J(K_N, L_N) approaches 2/π as N grows.Source: §4.3 · p. 31

5. The upper bound

Gram-symmetrized Horn pairs provide the parameters used with Theorem 2.20 to obtain a strict Delsarte rate bound above δπ. This bound yields the matching upper limits for the Krawtchouk sign-uncertainty radii.

5. The upper bound

  • Gram symmetrization turns each cited object into a pair whose Φ value is exactly 1/2 and whose Γ value is J(K_N, L_N).For all sufficiently large N, J_N > 1 − 2δ.Source: §5 · pp. 31–32
  • For every δ > δπ, R_D(δ) < 1/2, giving a strict upper bound above the threshold δπ.The proof first establishes the bound for δπ < δ < 1/2, then extends it by monotonicity.Source: §5 · p. 32
  • LP_n(d_n) < 2^(n/2) rules out the Delsarte-feasible alternative with objective 2^(n/2), forcing alternative (i).Here d_n = ⌈δn⌉ for fixed δ ∈ (δπ, 1/2).Source: §5 · p. 32
  • The Krawtchouk radii satisfy A^K_−(n)/n ≤ δ in the limit for δ > δπ, and Proposition 3.6 transfers the upper limit to the positive sign.Together with the common lower bound, this proves the stated asymptotics for both signs.Source: §5 · p. 32
Loading 2609.03736v2…