A binary error-correcting code of length nn and minimum distance dd is a packing of hard spheres of diameter dd on the Hamming hypercube H2nH_2^n, and the maximum code size A2(n,d)A_2(n,d) is the maximal packing density. Parisi and Zamponi (2006) analyzed the liquid phase of this hard-sphere model in the limit n→∞n\to\infty, d→∞d\to\infty, d/n=δd/n=\delta, and found that the liquid solution, continued to high reduced density, acquires negative entropy at ρVd−1∼n\rho V_{d-1}\sim n — only a polynomial factor above the Varshamov–Gilbert (VG) density, which sits at ρVd−1∼1\rho V_{d-1}\sim 1, hence essentially at the VG density at the level of the rate. They conjectured that a phase transition then occurs — most plausibly a glass transition as in the continuum large-dimension hard-sphere problem, or a first-order transition to a parity-sublattice phase for even dd — and that, if a glass preempts other phases, the maximal density is set at the VG level, i.e. the asymptotic rate satisfies R(δ)=1−H(δ)R(\delta)=1-H(\delta) and the VG bound is tight. The paper left the replicated-partition-function computation of the glass equation of state, the identification of the phase that determines φc(δ)\varphi_c(\delta), the characterization of the even-dd parity transition, and the finite-nn corrections to its saddle-point/HNC asymptotics open. Later work (cavity method 2012; loop-corrected belief propagation 2024/2025) supports VG-level asymptotics within successive approximations but explicitly cannot exclude denser solutions, and the replica computation of the glass phase for the discrete model has never been completed. The problem remains open.

Background

A code CC is a subset of the binary Hamming space H2n={0,1}nH_2^n=\{0,1\}^n; the Hamming distance between two strings is the number of positions in which they differ, and a code has minimum distance dd when any two of its codewords differ in at least dd bits. Writing A2(n,d)A_2(n,d) for the maximum size of such a code, the asymptotic rate is R(δ)=lim sup⁡n→∞(1/n)log⁡2A2(n,d)R(\delta)=\limsup_{n\to\infty}(1/n)\log_2 A_2(n,d) with δ=d/n\delta=d/n fixed. The classical Varshamov–Gilbert (VG) lower bound gives R(δ)≥RVG(δ)=1−H(δ)R(\delta)\ge R_{VG}(\delta)=1-H(\delta), where H(δ)=−δlog⁡2δ−(1−δ)log⁡2(1−δ)H(\delta)=-\delta\log_2\delta-(1-\delta)\log_2(1-\delta) is the binary entropy function, while the McEliece–Rodemich–Rumsey–Welch (MRRW) bound, obtained from Delsarte's linear-programming method (a linear program in the distance distribution of a code), gives an exponentially smaller upper bound; a large gap remains between them, and whether the VG bound is tight for binary codes is a classical open question. The problem admits a statistical-mechanics formulation: regard the codewords as particles on H2nH_2^n interacting through a hard-core potential (infinite repulsion below distance dd), so that the packing problem becomes the high-density behavior of a lattice gas. Procacci and Scoppola (1999) showed that convergence of the virial expansion (the low-density series for the pressure in powers of the density) reproduces the VG bound, so a 'liquid phase' certainly exists up to ρVd−1∼1\rho V_{d-1}\sim 1. Parisi and Zamponi studied the liquid at higher density via the hypernetted-chain (HNC) closure, an approximate integral equation for the pair correlation function h(i)h(i) at Hamming distance ii, whose solution is obtained in the limit n→∞n\to\infty by a saddle-point analysis of the Fourier transform kernel of the Hamming cube, Fn(a,i)F_n(a,i) (whose entries are Krawtchouk polynomials, the orthogonal polynomials associated with the binomial measure), which scales as exp⁡[nf(k,x)]\exp[n f(k,x)] with k=a/nk=a/n, x=i/nx=i/n. They found that the liquid solution can be continued to exponentially large reduced density ρ~=ρVd−1=exp⁡(nφ)\tilde\rho=\rho V_{d-1}=\exp(n\varphi), but its entropy becomes negative at φ∼log⁡(n)/n\varphi\sim\log(n)/n, i.e. at ρ~∼n\tilde\rho\sim n, which is only a polynomial factor above the VG density and thus invisible at the level of the rate R(δ)R(\delta). Since ρ~∼1\tilde\rho\sim 1 at the VG density, the largest achievable φ\varphi, written φc(δ)\varphi_c(\delta), measures the excess of the true maximal density over the VG value: the VG bound is tight, R(δ)=1−H(δ)R(\delta)=1-H(\delta), precisely when φc(δ)→0\varphi_c(\delta)\to 0 (the 2006 estimate, if no other phases exist, being φc∼log⁡(n)/n\varphi_c\sim\log(n)/n). Negative liquid entropy signals an instability, and the central physical question is what phase the system then enters, and hence which phase ultimately sets φc(δ)\varphi_c(\delta). In the continuum analog of hard spheres in Euclidean space Rn\mathbb{R}^n at large nn, Parisi and Zamponi computed, using the replica method (averaging over mm replicated copies of the system and then analytically continuing in mm, with replica symmetry breaking, RSB, describing glassy states), that the liquid undergoes a Kauzmann-type ideal glass transition (a transition to an amorphous, entropy-dominated glassy phase where the liquid's configurational entropy vanishes) close to the density where the naive liquid entropy becomes negative, and that the glass can be compressed up to a maximal 'jamming' density close to that same value; this suggests that the maximal packing density of continuum spheres is set by the glass. For the Hamming-space problem the same computation is blocked: positions are discrete, so the Gaussian single-particle density ansatz that made the continuum replica calculation tractable is unavailable. The 2006 paper also observed, from HNC solutions and preliminary Monte Carlo simulation, that for even dd particles partially localize on the parity sublattice (the set of strings of even, respectively odd, Hamming weight), anticipating a first-order transition to a fully sublattice-localized phase; for odd dd an exact mapping of H2nH_2^n with distance dd onto the even-weight subspace of H2n+1H_2^{n+1} with distance d+1d+1 relates the two cases. Jiang and Vardy (2004) proved by graph-theoretic means that binary codes beat the VG size by a factor of order log⁡V(n,d−1)\log V(n,d-1) for d/n≤0.499d/n\le 0.499 — a subexponential gain that leaves the rate-level VG bound unchanged but shows that the maximal size is strictly above the VG value. The liquid solution's negative-entropy threshold ρ~∼n\tilde\rho\sim n sits precisely at this subexponential scale, making the determination of the true maximum, and of the phase that achieves it, a sharp question.

Problem Statement

For the hard-sphere model on the binary Hamming space H2nH_2^n with minimum distance dd, in the limit n→∞n\to\infty, d→∞d\to\infty with δ=d/n∈(0,1/2)\delta=d/n\in(0,1/2) fixed, determine the high-density phase behavior above the density at which the liquid (virial/HNC) solution acquires negative entropy, and thereby the asymptotic maximal packing density — equivalently the asymptotic code rate R(δ)R(\delta), with φc(δ)\varphi_c(\delta) measuring the excess of the maximal density over the VG value — in particular whether R(δ)=1−H(δ)R(\delta)=1-H(\delta), i.e. whether the Varshamov–Gilbert bound is tight. The source paper poses the open targets (i)–(iii) below, which jointly serve this objective, together with item (iv), which it identifies as needed for comparison of the asymptotic theory with numerics: (i) establish whether the conjectured glass transition actually occurs in this discrete hard-sphere system and, if it does, compute the glass equation of state and the maximal glass-packing density, which requires a replicated-partition-function (RSB) analysis adapted to discrete configurations — no Gaussian single-particle density ansatz is available here, so the continuum computation of Parisi and Zamponi must be re-derived from scratch; (ii) decide whether the glass phase, the parity-sublattice localized phase observed for even dd, or other ordered/special configurations ultimately determine φc(δ)\varphi_c(\delta) — i.e. whether any such phase preempts the glass and invalidates the conjectured Varshamov–Gilbert tightness; (iii) characterize the parity-driven transition for even dd, indicated by preliminary Monte Carlo simulations to be first-order (its order, coexistence properties, and critical φ\varphi), by extensive numerical simulation and/or analytical treatment; and (iv) compute the asymptotic finite-nn corrections to the saddle-point and HNC formulas (prefactors and oscillatory terms controlled by Im⁡f(k,δ)\operatorname{Im} f(k,\delta)), which are needed to compare the asymptotic theory with numerics at accessible nn.

References

  1. Giorgio Parisi and Francesco Zamponi, 'On the High Density Behavior of Hamming Codes with Fixed Minimum Distance', Journal of Statistical Physics 123, 1145–1167 (2006). DOI: 10.1007/s10955-006-9142-7, https://doi.org/10.1007/s10955-006-9142-7 (arXiv: cond-mat/0602661, https://arxiv.org/abs/cond-mat/0602661).
  2. Abolfazl Ramezanpour and Riccardo Zecchina, 'Cavity approach to sphere packing in Hamming space', Physical Review E 85, 021106 (2012). DOI: 10.1103/PhysRevE.85.021106, https://doi.org/10.1103/PhysRevE.85.021106 (arXiv: 1201.3863, https://arxiv.org/abs/1201.3863).
  3. Abolfazl Ramezanpour and Saman Moghimi-Araghi, 'Loop corrections for hard spheres in Hamming space', Journal of Statistical Mechanics: Theory and Experiment (2025). DOI: 10.1088/1742-5468/adba42, https://doi.org/10.1088/1742-5468/adba42 (arXiv: 2409.03670, https://arxiv.org/abs/2409.03670).
  4. A. Procacci and B. Scoppola, 'Statistical mechanics approach to coding theory', Journal of Statistical Physics 96, 907–912 (1999). DOI: 10.1023/a:1004666811087, https://doi.org/10.1023/a:1004666811087.
  5. T. Jiang and A. Vardy, 'Asymptotic improvement of the Gilbert–Varshamov bound on the size of binary codes', IEEE Transactions on Information Theory 50(8), 1655–1664 (2004). DOI: 10.1109/TIT.2004.831751, https://doi.org/10.1109/TIT.2004.831751 (arXiv: math/0404325, https://arxiv.org/abs/math/0404325).
  6. R. J. McEliece, E. R. Rodemich, H. Rumsey and L. R. Welch, 'New upper bounds on the rate of a code via the Delsarte–MacWilliams inequalities', IEEE Transactions on Information Theory 23, 157–166 (1977). DOI: 10.1109/TIT.1977.1055688, https://doi.org/10.1109/TIT.1977.1055688.
  7. Giorgio Parisi and Francesco Zamponi, 'Amorphous packings of hard spheres for large space dimension', Journal of Statistical Mechanics: Theory and Experiment (2006) P03017. DOI: 10.1088/1742-5468/2006/03/P03017, https://doi.org/10.1088/1742-5468/2006/03/P03017.
  8. Giorgio Parisi and Francesco Zamponi, 'The ideal glass transition of hard spheres', Journal of Chemical Physics 123, 144501 (2005). DOI: 10.1063/1.2041507, https://doi.org/10.1063/1.2041507.
  9. Giorgio Parisi and Francesco Zamponi, 'Mean field theory of hard sphere glasses and jamming', Reviews of Modern Physics 82, 789–863 (2010). DOI: 10.1103/RevModPhys.82.789, https://doi.org/10.1103/RevModPhys.82.789 (arXiv: 0802.2180, https://arxiv.org/abs/0802.2180).
  10. V. Blinovsky, 'Proof of tightness of Varshamov–Gilbert bound for binary codes', arXiv preprint (2016). arXiv: 1606.01592, https://arxiv.org/abs/1606.01592 (unrefereed preprint; concerns linear binary codes and does not resolve the unrestricted question).
  11. Xue-Bin Liang, 'The q-ary Gilbert–Varshamov bound can be improved for all but finitely many positive integers q', arXiv preprint (2024). arXiv: 2403.08727, https://arxiv.org/abs/2403.08727.