Pith. sign in

REVIEW 4 minor 3 cited by

Expansion creates spin-glass order in finite-connectivity models: a rigorous and intuitive approach from the theory of LDPC codes

T0 review · 0 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Expansion in a code forces the low-temperature Gibbs state of a finite-connectivity spin model to shatter into exponentially many tiny, incongruent components.

desk verdict Rigorous first proof of finite-temperature spin-glass order on finite-connectivity graphs via code expansion; solid theorem with clearly disclosed scope limits. read the letter →

arxiv 2507.13342 v1 pith:WBP2RZNY submitted 2025-07-17 cond-mat.stat-mech cond-mat.dis-nnmath-phmath.MP

Benedikt Placke , Grace M. Sommers , Nikolas P. Breuckmann , Tibor Rakovszky , Vedika Khemani This is my paper · ORCID
classification cond-mat.stat-mechcond-mat.dis-nnmath-phmath.MP MSC 82B2082B4494B35
keywords spinglassorderLDPCcodesexpandergraphscodeexpansionGibbsstatedecompositionconfigurationalentropyfinite-connectivitymodelsTanner-Isingmodel
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Spin-glass order has so far been rigorously established only in mean-field models with all-to-all connectivity. This paper claims to prove finite-temperature spin-glass order for a family of sparse, finite-connectivity spin models built from low-density parity check (LDPC) codes on expander graphs. The mechanism is code expansion: every small set of flipped spins creates a proportional number of violated local constraints, so all low-energy states sit inside deep energy wells. Under two assumptions—sufficiently strong expansion beyond a rate-dependent threshold, and parity-check matrices with full rank (no redundant constraints)—the low-temperature Gibbs state decomposes into exponentially many disjoint components, each carrying an exponentially small fraction of the total weight, and almost all components contain no ground state. If correct, this is the first rigorous derivation of spin-glass order on closed finite-degree interaction graphs, including loop-rich geometries where cavity methods are uncontrolled.

What carries the argument

The load-bearing object is code expansion, Definition III.1: $H\in\mathbb{F}_2^{m\times n}$ is $(\delta,\gamma)$-expanding if $|Hx|>\gamma|x|$ whenever $|x|<\delta n$, meaning every small error violates a proportional number of checks. Because the energy is $E(x)=|Hx|$, the triangle inequality yields Eq. (20), $E(y)-E(x)\ge\gamma|x\oplus y|-2E(x)$, which implies that any state with energy density below $\delta\gamma/2$ is surrounded by an extensive energy barrier. Full rank of $H$ supplies the exact partition function and the count of states at each energy; combining the Hamming-ball upper bound on cluster size (Lemma D.6) with this exact counting gives Eq. (D11), a lower bound $s_{\mathrm{conf}}\ge r+s(T)$ that is positive for $\gamma>\gamma^*(r)$ at small $T$. That positivity is what proves shattering and incongruence.

What would settle it

Run the exact low-temperature calculation for a family of Gallager codes that provably satisfy rank $H_n=m$ and $\gamma>\gamma^*(r)$, for instance the $(5,6)$-ensemble used in Figure 8, and compute the configurational entropy of the explicit Gibbs decomposition from the closed-form partition function; if $s_{\mathrm{conf}}(T)$ fails to exceed $r$ at arbitrarily low temperature as the lower bound predicts, the theorem is false.

Watch

Extended reading notes

Core claim

The central claim is Theorem IV.2: for any family of LDPC codes $H_n$ with rate $r$ that is $(\delta,\gamma)$-expanding with $\gamma>\gamma^*(r)$ and has rank $H_n=m$, the associated classical spin model—energy equal to the number of violated parity checks—realizes spin-glass order at sufficiently low temperature. Spin-glass order is defined concretely as shattering: no Gibbs component carries more than an exponentially small fraction of the Gibbs weight, together with incongruence: the configurational entropy density $s_{\mathrm{conf}}(T)$ strictly exceeds its zero-temperature value $s_{\mathrm{conf}}(0)=r$. The proof constructs an explicit Gibbs-state decomposition, first showing that the energy landscape below a cutoff shatters into clusters separated by extensive Hamming distance and extensive energy barriers, and then converting those barriers into free-energy bottlenecks. The no-redundancy condition gives the exact partition function $Z=2^{n-m}(1+e^{-\beta})^m$, which makes the counting argument precise enough to show $s_{\mathrm{conf}}(T)>r$ for small $T$. Rigorous instantiations are Gallager-type diluted ferromagnetic $p$-spin models for sufficiently large but finite $p$.

Load-bearing premise

The load-bearing premise is that the code satisfies both a sufficiently strong expansion condition ($\gamma>\gamma^*(r)$, meaning every small error creates a large enough number of violated constraints) and full rank of $H_n$ (no redundant constraints); if either fails, the counting estimates that force shattering and incongruence collapse.

Editorial extensions

If this is right

  • Rigorous low-temperature spin-glass order for diluted ferromagnetic $p$-spin models on random regular graphs, for sufficiently large but finite $p$.
  • The argument is independent of local tree-likeness, so the same conclusion applies in principle to loop-rich expander geometries such as hyperbolic tessellations, where cavity methods become uncontrolled.
  • Every Gibbs component is protected by an extensive free-energy barrier, so any local, detailed-balance stochastic dynamics is a passive memory: initialized in a typical low-temperature component, it remains there for a time growing exponentially with system size.
  • The proof establishes a nontrivial overlap distribution consistent with one-step replica symmetry breaking, but it does not prove that the cavity or RSB solution is exact, and it does not rigorously establish the intermediate weak-ergodicity-breaking phase seen numerically.
  • The exact partition function is analytic at all nonzero temperatures, so these models provide examples where a trivial partition function coexists with a nontrivial low-temperature Gibbs-state decomposition.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper: improved coding-theory lower bounds on $\gamma$ for Sipser-Spielman and hyperbolic Tanner-Ising codes would immediately convert the numerical evidence in Section V into rigorous examples, since the remaining obstruction is the expansion bound rather than the physics.
  • Beyond the paper: the no-redundancy assumption is likely replaceable by subextensive redundancies; the partition function then admits a lower bound via a Kramers-Wannier-type duality, which should preserve the entropy inequality.
  • Beyond the paper: a plausible testable extension is that the intermediate phase $T_G<T<T_{\mathrm{mem}}$ has exponentially many components but one dominant component, with only weak dynamical signatures, mirroring the Bethe-lattice Ising model; the present theorem proves only the low-temperature shattered phase.
  • Beyond the paper: a weaker 'linear confinement' condition with $\delta(n)$ growing only logarithmically may suffice, which would extend the result to codes with subextensive confinement and hence to a broader family of locally constrained spin models.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper proves that families of classical spin models associated with sufficiently expanding, redundancy-free LDPC codes display spin-glass order at low temperatures, in the precise sense of a Gibbs-state decomposition into exponentially many components separated by extensive free-energy barriers, with no component carrying more than an exponentially small fraction of the weight and with most components not containing ground states. The proof proceeds by first showing that code expansion creates extensive energy barriers around all low-energy-density states, then, under strong expansion and full rank of the parity-check matrix, proving shattering and incongruence of the low-energy landscape by a counting argument, and finally lifting these properties to the Gibbs state using the exact partition function and microcanonical concentration. The rigorous results apply to Gallager-type codes (diluted p-spin models) with sufficiently large bit degree. The paper also presents Monte Carlo and cavity-method studies of two Sipser-Spielman-type Tanner-Ising models on high-girth random regular graphs and hyperbolic tessellations, providing evidence for two separate transitions associated with weak ergodicity breaking and spin-glass order, while explicitly noting that these numerical models are not covered by the rigorous theorem.

Significance. If correct, this is the first rigorous demonstration of finite-temperature spin-glass order on closed finite-degree interaction graphs, a problem that has remained open beyond mean-field models. The strength of the paper is that the central argument is elementary and self-contained: the proof in Appendix D states precise assumptions, gives explicit counting bounds, and derives the exact partition function rather than assuming it. The paper is also honest about its scope: the numerical Tanner-Ising models do not satisfy the available rigorous expansion bounds, and the authors say so explicitly. The proof is not machine-checked, but the counting and bottleneck steps are checkable by hand. The work connects coding theory and statistical mechanics in a way that is likely to be influential and offers a concrete path toward rigorous results on loopy non-Euclidean graphs if sharper expansion bounds become available.

minor comments (4)
  1. [Sec. V A / Table I] The construction of the numerical model says that the authors add all seven nonzero linear combinations of the three local Hamming checks, a set that is linearly dependent, yet Table I states that the parity-check matrix H_G has no redundancies. Please clarify that the no-redundancy statement refers to the minimal three-check representation of the global code, while the simulated Hamiltonian is the symmetrized (locally redundant) form.
  2. [App. D, Theorem D.8 and Eq. (D11)] The theorem states that γ* depends only on the rate r, but the proof does not give an explicit threshold. From the small-ε expansion of the bound r + (1−r)h(ε/(1−r)) − h(2ε/γ), any fixed γ > 2 suffices to make the bound strictly exceed r for sufficiently small ε; stating this explicitly would make the theorem easier to verify.
  3. [Sec. II D, Eq. (10)] The replica identity displays no disorder average, although the text says that the overline denotes the disorder average. Adding the missing average to the equation would avoid ambiguity.
  4. [Sec. III C and Sec. IV] There are several typographical errors that should be corrected in a final version, including 'whcih', 'dam', 'the the system', and the reference to 'Theorem D.1' where 'Definition D.1' is meant.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the spin-glass conclusion is derived from explicit axioms (expansion, full rank) and an explicit counting/partition-function argument; the only self-citations are not load-bearing.

full rationale

The central derivation is self-contained. The load-bearing inputs are Definition III.1 ((δ,γ)-expansion) and the explicit assumption rank H = m (no redundancies); neither is derived from the target conclusion. The exact partition function in Lemma D.10, Z = 2^{n-m}(1+e^{-β})^m, is derived from full rank rather than imposed. The counting identity |Ω(ϵ)| = 2^{rn} B_m(ϵn) in Eq. (D9) follows from linearity and full rank, and together with the cluster-diameter bound (Lemma D.6) it yields the lower bound s_conf ≥ r + (1−r) log_2 Υ(ϵ/(1−r)) − log_2 Υ(2ϵ/γ) in Eq. (D11), which is strictly larger than r for γ > γ* and sufficiently small ϵ. The Gibbs-state step uses concentration on the microcanonical shell and the bottleneck condition; no fitted parameter is renamed as a prediction. The numerical T_G and T_mem in Sec. V are simulation outputs, and the authors explicitly state that the rigorous theorem does not cover those models because the available γ bounds are trivial (Sec. IV C 2). The self-citations that appear, notably Ref. [61] for context and Ref. [111] for a version of the bottleneck theorem, are not load-bearing: the bottleneck theorem is also credited to the external reference [63], and the central uniqueness/counting arguments do not reduce to the authors' prior work. Thus the derivation does not reduce to its own inputs.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claim adds the connection between code expansion and Gibbs-state shattering. It imports expansion and rank-fullness as axioms; none are fitted to the numerical data. No new particles, forces, or physical entities are introduced. The finite constants in the proof, such as epsilon, xi, omega, and beta*, are chosen analytically and are not optimized against numerics.

assumptions (6)
  • domain assumption The energy of any configuration equals the Hamming weight of its syndrome, H(σ) = |Hx| (Eq. 14).
    This is the definition of the spin model associated with a parity-check matrix, and it underpins the use of code expansion as an energy barrier statement.
  • domain assumption The parity-check matrix H has full rank (no redundancies) for every n in the family.
    Used in Lemma D.10 to obtain the closed-form partition function and in Eq. (D9) to count states at fixed energy. Without it the counting argument behind shattering fails.
  • domain assumption The code family is (δ,γ)-expanding with γ > γ*(r).
    This is the central structural input imported from coding theory; it is proved only for some ensembles, notably Gallager codes with sufficiently large bit degree.
  • standard math Gallager (w_bit, w_check) random code ensembles have full rank with high probability (Lemma C.1) and are unique-neighbor expanders with sufficiently large γ for large enough w_bit (Theorem C.3).
    These cited coding-theory results are used to instantiate the theorem for diluted p-spin models and are not reproved in the paper.
  • standard math Hamming ball volume bounds (Ref. 110) and concentration of the energy under full rank via Hoeffding's inequality (Lemma D.10).
    Standard combinatorial and probabilistic estimates used to convert cluster-size bounds into configurational entropy bounds.
  • standard math The classical bottleneck theorem for Markov chains (Theorem D.13, citing Refs. 63 and 111).
    Connects bottleneck ratios to the dynamic stability of Gibbs state components and is imported without proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Expansion creates spin-glass order in finite-connectivity models: a rigorous and intuitive approach from the theory of LDPC codes." pith.science (2026). https://pith.science/paper/WBP2RZNY

@misc{pith2026250713342,
  author       = {Pith},
  title        = {Pith review of: Expansion creates spin-glass order in finite-connectivity models: a rigorous and intuitive approach from the theory of LDPC codes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WBP2RZNY}},
  note         = {Machine review of arXiv:2507.13342}
}
read the original abstract

Complex free-energy landscapes with many local minima separated by large barriers are believed to underlie glassy behavior across diverse physical systems. This is the heuristic picture associated with replica symmetry breaking (RSB) in spin glasses, but RSB has only been rigorously verified for certain mean-field models with all-to-all connectivity. In this work, we give a rigorous proof of finite temperature spin glass order for a family of models with local interactions on finite-connectivity, non-Euclidean expander graphs. To this end, we bypass the RSB formalism entirely, and instead exploit the mathematical equivalence of such models to certain low-density parity check (LDPC) codes. We use code expansion, a property of LDPC codes which guarantees extensive energy barriers around ground states. Together with mild additional assumptions, this allows us to construct an explicit decomposition of the low-temperature Gibbs state into disjoint components, each hosting an asymptotically long-lived state associated with a local minimum of the landscape. Each component carries at most an exponentially small fraction of the total weight, and almost all components do not contain ground states -- which we take together to define spin-glass order. The proof is elementary, and treats various expanding graph topologies on the same footing, including those with short loops where existing approaches such as the cavity method fail. Our results apply rigorously to diluted p-spin glasses for sufficiently large p, and while unproven, we also expect our assumptions to hold in a broader family of codes. Motivated by this, we numerically study two simple models, on random regular graphs and a regular tesselation of hyperbolic space. We show that both models undergo two transitions as a function of temperature, corresponding to the onset of weak ergodicity breaking and spin glass order, respectively.

Figures

Figures reproduced from arXiv: 2507.13342 by the authors.

Figure 1
Figure 1. FIG. 1. Different interaction graphs: (a) Fully connected, [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2. The energy landscape of expander LDPC codes, and resulting phase diagram. (a) Expander codes have extensive [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. FIG. 3. Flowchart sketching the sequence of implications from [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (24 more)
Figure 4
Figure 4. Figure 4: FIG. 4. Sketch of a system with multiple Gibbs states. [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]
Figure 5
Figure 5. Figure 5: FIG. 5. Tanner-Ising models. The models considered in this work are defined on expander graphs, e.g. locally tree-like [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]
Figure 6
Figure 6. Figure 6: FIG. 6. Immobile excitations in Tanner-Ising models. Flip [PITH_FULL_IMAGE:figures/full_fig_p013_6.png]
Figure 7
Figure 7. Figure 7: FIG. 7. Sketch of the lower bound, [PITH_FULL_IMAGE:figures/full_fig_p014_7.png]
Figure 8
Figure 8. Figure 8: FIG. 8. Lower bound for the configurational entropy [PITH_FULL_IMAGE:figures/full_fig_p015_8.png]
Figure 9
Figure 9. Figure 9: FIG. 9. Illustration of a codeword (a), and a state with a [PITH_FULL_IMAGE:figures/full_fig_p018_9.png]
Figure 10
Figure 10. Figure 10: FIG. 10. Results of Metropolis dynamics simulations on [PITH_FULL_IMAGE:figures/full_fig_p019_10.png]
Figure 11
Figure 11. Figure 11: FIG. 11. Numerical evidence for the glass transition on high-girth random regular graphs. (a) Late-time average energy [PITH_FULL_IMAGE:figures/full_fig_p020_11.png]
Figure 12
Figure 12. Figure 12: FIG. 12. Results for metropolis dynamics simulations on [PITH_FULL_IMAGE:figures/full_fig_p021_12.png]
Figure 13
Figure 13. Figure 13: FIG. 13. (a) Depth [PITH_FULL_IMAGE:figures/full_fig_p022_13.png]
Figure 14
Figure 14. Figure 14: FIG. 14. Fixed points of the recursion [ [PITH_FULL_IMAGE:figures/full_fig_p024_14.png]
Figure 15
Figure 15. Figure 15: FIG. 15. Left: Mutual information between root and bound [PITH_FULL_IMAGE:figures/full_fig_p025_15.png]
Figure 17
Figure 17. Figure 17: FIG. 17. (a) Cayley tree with forward-branching number [PITH_FULL_IMAGE:figures/full_fig_p031_17.png]
Figure 18
Figure 18. Figure 18: FIG. 18. Fixed points of the root magnetization under po [PITH_FULL_IMAGE:figures/full_fig_p032_18.png]
Figure 21
Figure 21. Figure 21: FIG. 21. Tanner graph for a Gallager code with [PITH_FULL_IMAGE:figures/full_fig_p033_21.png]
Figure 19
Figure 19. Figure 19: FIG. 19. Magnetization of the central site, [PITH_FULL_IMAGE:figures/full_fig_p033_19.png]
Figure 20
Figure 20. Figure 20: FIG. 20. Memory time of the Ising model on the tree as [PITH_FULL_IMAGE:figures/full_fig_p033_20.png]
Figure 22
Figure 22. Figure 22: FIG. 22. Sketch of the various energy scales and distances [PITH_FULL_IMAGE:figures/full_fig_p043_22.png]
Figure 23
Figure 23. Figure 23: FIG. 23. Number of redundant checks in Tanner codes defined [PITH_FULL_IMAGE:figures/full_fig_p046_23.png]
Figure 24
Figure 24. Figure 24: FIG. 24 [PITH_FULL_IMAGE:figures/full_fig_p050_24.png]
Figure 25
Figure 25. Figure 25: FIG. 25. (a) Fixed points under uniform bulk field [PITH_FULL_IMAGE:figures/full_fig_p051_25.png]
Figure 27
Figure 27. Figure 27: FIG. 27. Fixed points of the recursion relation for the two [PITH_FULL_IMAGE:figures/full_fig_p052_27.png]
Figure 26
Figure 26. Figure 26: FIG. 26. Two-copy tensor network used to calculate the vari [PITH_FULL_IMAGE:figures/full_fig_p052_26.png]
Figure 28
Figure 28. Figure 28: FIG. 28. Variance of the bulk magnetization with free bound [PITH_FULL_IMAGE:figures/full_fig_p053_28.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Topological states and flat bands in exactly solvable decorated Cayley trees

    cond-mat.mes-hall 2025-11 conditional novelty 7.0 of 10

    Flat bands on decorated Cayley trees map exactly onto topological edge states of 1D SSH chains, and persist on infinite Bethe lattices by a covering construction.

  2. Lifting Lifted Product Codes

    quant-ph 2026-07 conditional novelty 6.5 of 10

    Group-extension lifts systematically enlarge any LP code, transfer logical gadgets via chain maps (often with less surgery overhead), improve some code parameters, and give candidate thermodynamic families with cohere...

  3. Superconductivity in hyperbolic spaces: Regular hyperbolic lattices and Ginzburg-Landau theory

    cond-mat.supr-con 2025-09 conditional novelty 6.0 of 10

    On hyperbolic lattices, superconductivity can appear only at the boundary above the bulk critical temperature, and rough boundaries with dangling bonds can raise Tc severalfold.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages · cited by 3 Pith papers

  1. [1]

    Choose a vertexvrandomly among those vertices inGwith degrees min

    work page

  2. [2]

    Table of expander graphs referenced in this work

    Choose a second vertexuamong those vertices inG with degrees min and graph distance dist(u, v)> g 36 HGRRG (s= 7) Hyperbolic{3,7}LPS girthN v Ne λ2 systoleN v Ne λ2 p q N v Ne λ2 3 38 133 3.92 4 24 84 2.65 7 11 1320 5280 5.12 4 218 763 4.67 6 72 252 4.76 7 13 2184 8736 5.00 5 1298 4543 4.80 7 156 546 5.30 7 17 4896 19584 5.11 6 7778 27223 4.87 7 192 672 5...

    work page

  3. [3]

    Constructing expander graphs There are many known constructions of expander graphs, both random and explicit. We will here review three of them which are relevant for this work which are (1) a family of random-regular graphs with guaranteed girth (that is the size of the shortest loop) (2) regular tesselations of the hyperbolic plane, and (3) a symmet- ri...

    work page

  4. [4]

    However, as shown in Ref

    Add the edge (u, v) toG The procedure described above can get stuck in princi- ple, for example if at any point all vertices with minimum degree left in the graph are close. However, as shown in Ref. 94, the procedure terminates with high probability. Of course, the family of RRGs constructed here is not exactly the same as the one considered by Friedman ...

    work page

  5. [5]

    clusters

    Clustering and Configurational Entropy of the Energy Landscape We start by characterizing the complexity of the low energy landscape. We do this by analyzing the structure of the configuration space below a given cutoff energy densityϵ: Ω(ϵ) ={x;|Hx|< ϵn}.(D1) We will show that this set, for certain models at suffi- ciently lowϵ, can be decomposed into ex...

    work page

  6. [6]

    thermodynamic limit

    Spin Glass Order from Expansion In the previous section, we showed that certain non- redundant expander codes display a complex energy landscape, i.e., the set of configurations below a given en- ergy density cutoff has a complex cluster decomposition with shattering and incongruence. In this subsection, we will be interested in properties of theGibbs dis...

    work page

  7. [7]

    EachΩ j is surrounded by a bottleneck: there exists η >0, and a function∆(n)with∆(n)− − − − → n→∞ 0 such that pG[∂ηΩj,n] pG[Ωj,n] ≤∆(n) (D29) where theη-boundary of a subsetΩis defined as ∂ηΩ≡ {x∈Ω c; dist(x,Ω)≤ηn}

    work page

  8. [8]

    relevant

    The setΛcontains only a vanishing fraction of the weight pG,n(Λn)− − − − → n→∞ 0.(D30) We callΛthe “junk” set. Gibbs state components are then defined as the (normal- ized) restrictions ofp G toΩ j: p(Ωj,n) G,n = 1Ωj,n ·p G,n pG,n(Ωj,n) (D31) where1 Ω is the indicator function of the setΩ. The Gibbs distribution can now be written the convex sum of its co...

    work page

Show all 24 references
  1. [9]

    AllΩ j are typical subsets (Theorem D.11), 2.diam[Ω j ∩Ξ ω(β)]≤2n(⟨ε⟩ β +ω)/γwithΞ ω(β)the microcanonical shell [Eq. (D13)]

  2. [10]

    Energy density Configuration Space T typical cluster atypical cluster 0 FIG

    The{Ω j}andΛ≡F n 2 /(⊎M j=1Ωj)define a decom- position of the Gibbs state in the sense of Theo- rem D.14. Energy density Configuration Space T typical cluster atypical cluster 0 FIG. 22. Sketch of the various energy scales and distances involved in the Gibbs state decompositio...

  3. [11]

    Definition E.1.We call a binary matrixH∈F m×n 2 (w, b)-sparseif each row has Hamming weight≤wand each column has Hamming weight≤b

    General results We will always assume that the number of checks is proportional to the number of bitsm= Θ(n). Definition E.1.We call a binary matrixH∈F m×n 2 (w, b)-sparseif each row has Hamming weight≤wand each column has Hamming weight≤b. Theorem E.2.Consider an expander cod...

  4. [12]

    Gallager codes We now show that random LDPC codes satisfy the assumptions of Theorem E.2 and Theorem E.4. By??C.1??C.3 choosing the left-degreeℓto be odd and large enough we obtain a Gallager code withH G be- ing full-rank, (r, ℓ)-sparse and (δ >0, γ >2)-expanding and thus sat...

  5. [13]

    symmetrized

    No redundancies Given a parity check matrixH∈F m×n 2 with full rank m, the energy of a statex∈F n 2 is given byE:=|s|, whereHx=s∈F m 2 is called the syndrome ofx. Sinces i ∈ {0,1}and hence|s|= P i si, we can write the Gibbs distribution as pG ∝e −βE(σ) =e −β|s| = Y i e−βsi .(G...

  6. [14]

    symmetrized

    Local redundancies We now discuss the case of how to sample from the Gibbs distribution of the “symmetrized” models con- sidered in the main text. The symmetrized model is based on the Tanner code on a graphG,T G, H(sym) L , where given a local codeH L ∈F m0 2 without redundan...

  7. [15]

    redundant

    Constant number of redundancies Consider now the general case of a parity check matrix H∈F m×n 2 with rankm 0. As before, we want to sample from the Gibbs distributionp G ∝e −β|s|. In the case of no redundancies, we can simply choose a randomsby sampling the syndrome component...

  8. [16]

    We can represent this conveniently as a tensor network (see also Refs

    T ensor network formulation The unnormalized Gibbs state,e −βE(σ) , of a Tanner code factorizes into Q v e−βEv(σv) whereσ v denotes the spin configuration on the edges adjacent tov. We can represent this conveniently as a tensor network (see also Refs. [112, 113] for similar t...

  9. [17]

    inconsistent

    Recursion relation for general boundary conditions Consider forming a rooted tree by joining together s−1 branches, where theith branch has boundary con- figurationσ (i) ∂ , partition functionZ ∂(σ(i) ∂ ), and condi- tional magnetizationm i on the root spin. Letm= (m2, ..., ms...

  10. [18]

    ferromagnetic

    Memory transition An exceptional case where the fixed point distribution isanalytically solvable isα=∞, where the only al- lowed boundary configurations are those consistent with a global codeword. As a result, the distribution at depth rconcentrates onto a pair of delta funct...

  11. [19]

    ForT < Tmem,h opp bulk(T)>0: up to this point, a strong enough negative boundary field can overwhelm the positive boundary field

    Turning on a bulk field, we leth opp bulk(T) denote the magnitude of the largest bulk field at which negatively magnetized and positively magnetized stable fixed points coexist. ForT < Tmem,h opp bulk(T)>0: up to this point, a strong enough negative boundary field can overwhel...

  12. [20]

    annealed

    Spin glass transitions As we have seen, the tensor network formulation natu- rally allows us to calculate bulk observables conditioned on a particular boundary configurationσ ∂. In partic- ular, lettingσdenote the configuration of spins on the interior, we can consider the mag...

  13. [21]

    Sample the spin configurationσ 2, ..., σs with Boltz- mann weightT v(σ, σ2, ..., σs)

  14. [22]

    For eachσ i, independently samplem i from popu- lation ˜Q(r) σi

  15. [23]

    spin glass

    Set thejth element of the population ˜Q(r+1) σ equal toF(m 2, ..., ms). This method was used in Ref. [52] to analyze theq- state Potts model with spin degrees of freedom at the vertices of a tree. For those models, theσ i in step (1) can be sampled independently, a simplificat...

  16. [24]

    We measure the entropy density in bits, so thats= β(ε−f)/ln(2) whereε, fare the energy density and free- energy density, respectively, at a given temperature

    Configurational entropy As discussed in the main text, the configurational entropy is the difference of two terms,s β ands α=1. We measure the entropy density in bits, so thats= β(ε−f)/ln(2) whereε, fare the energy density and free- energy density, respectively, at a given tem...

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.