Change a small fraction of the bonds in a spin glass. How much of the spin configuration changes? For the fair ±J Edwards–Anderson model, there is a short answer using Fourier analysis on the Boolean cube. The decisive observation is geometric: every surviving Fourier term for a two-spin correlation must contain a path between those spins. The usual noise operator then suppresses it.

This is an exposition of a known result. Chatterjee’s 2023 paper proved site-overlap disorder chaos at zero temperature for Gaussian couplings. Chen, Kim and Sen, first posted in 2024 and revised in 2025, extended the result to general symmetric disorder and all temperatures. Here is the fair-bimodal, bond-resampling specialization of their argument, written directly in the language of Boolean Fourier analysis.

The model and the quantity to control

Take a nonempty finite simple graph \(G=(V,E)\), with \(N=|V|\), no external field, and no fixed spins. This includes a nearest-neighbor box with free boundaries or a periodic torus. Give each edge an independent fair sign \(x_e\in\{-1,+1\}\). Set the coupling magnitude to one; another common magnitude can be absorbed into the inverse temperature \(\beta\).

The Gibbs measure is

\[ \mu_{x,\beta}(\sigma) =Z_{x,\beta}^{-1} \exp\!\left(\beta\sum_{\{u,v\}\in E}x_{\{u,v\}}\sigma_u\sigma_v\right). \]

Write \(\langle\cdot\rangle_x\) for its expectation. At \(\beta=\infty\), use the uniform measure on all ground states. This convention matters: bimodal disorder can have many ground states.

For \(0<\varepsilon\le1\), construct \(x^\varepsilon\) by independently replacing each bond with a fresh fair sign with probability \(\varepsilon\). Replacement actually changes the sign with probability \(\varepsilon/2\). Draw \(\sigma\) from \(\mu_{x,\beta}\) and \(\tau\) independently from \(\mu_{x^\varepsilon,\beta}\), conditional on the two disorders. Their site overlap is \(R=N^{-1}\sum_i\sigma_i\tau_i\).

The square removes the arbitrary global spin orientation. Let \(f_{ij}(x)=\langle\sigma_i\sigma_j\rangle_x\). Conditional independence gives

\[ \mathbb E_\varepsilon\langle R^2\rangle =\frac{1}{N^2}\sum_{i,j} \mathbb E_\varepsilon[f_{ij}(x)f_{ij}(x^\varepsilon)]. \]

Here the bracket averages the two spin samples; \(\mathbb E_\varepsilon\) averages the original bonds and their resampling. The problem has become a noise-stability calculation for bounded functions of independent bits.

Gauge symmetry forces a path

For \(S\subseteq E\), let \(\chi_S(x)=\prod_{e\in S}x_e\). These Walsh characters form an orthonormal basis under the uniform bond law, so

\[ \begin{aligned} f_{ij}(x)&=\sum_{S\subseteq E}\widehat f_{ij}(S)\chi_S(x),\\ \widehat f_{ij}(S)&=\mathbb E[f_{ij}(x)\chi_S(x)]. \end{aligned} \]

Assume \(i\ne j\). Flip spin \(v\) and all bond signs incident to \(v\). Every interaction is unchanged after this joint transformation. Therefore \(f_{ij}\) changes sign exactly when \(v=i\) or \(v=j\). Meanwhile, \(\chi_S\) changes sign exactly when the degree of \(v\) in the subgraph \(S\) is odd.

The transformed bonds still have the uniform law. Changing variables in the Fourier coefficient gives

\[ \widehat f_{ij}(S) =(-1)^{\mathbf 1_{\{v=i\}}+\mathbf 1_{\{v=j\}}+\deg_S(v)} \widehat f_{ij}(S). \]

A nonzero coefficient requires odd degree at \(i,j\) and even degree everywhere else.

Every connected component of a finite graph has an even number of odd-degree vertices. Thus \(i\) and \(j\) must lie in the same component of \(S\). That component contains a path between them, and consequently

\[ \widehat f_{ij}(S)\ne0 \quad\Longrightarrow\quad |S|\ge d_G(i,j). \]
Two possible Fourier supports. The first connects i to j and has even degree at every other vertex, with an optional attached cycle. The second leaves i and j in different components and therefore has zero Fourier coefficient.
Colored edges are the Fourier support S, not satisfied bonds or a physical spin cluster. A connecting path is necessary; cycles are allowed. The parity condition permits a coefficient to survive, but does not guarantee that it is nonzero.

That is the model-specific step. It works for Gibbs correlations at every temperature because the spin flip is a bijection of configurations, including the ground-state set.

The noise operator finishes the estimate

Set \(q=1-\varepsilon\). A resampled bit has conditional mean \(q x_e\), and the resampling is independent across edges. Hence \(\mathbb E[\chi_S(x^\varepsilon)\mid x]=q^{|S|}\chi_S(x)\). Orthogonality now gives the standard noise-stability identity:

\[ \mathbb E_\varepsilon[f_{ij}(x)f_{ij}(x^\varepsilon)] =\sum_S q^{|S|}\widehat f_{ij}(S)^2. \]

For \(i\ne j\), all surviving sets have at least \(d_G(i,j)\) edges. Parseval and \(|f_{ij}|\le1\) therefore give

\[ \begin{aligned} 0&\le \mathbb E_\varepsilon[f_{ij}(x)f_{ij}(x^\varepsilon)]\\ &\le q^{d_G(i,j)}\sum_S\widehat f_{ij}(S)^2\\ &\le q^{d_G(i,j)}. \end{aligned} \]

For \(i=j\), \(f_{ii}=1\), so the same bound holds with distance zero. For distinct disconnected vertices the correlation is zero by flipping one whole component. Summing yields

\[ \boxed{\displaystyle \mathbb E_\varepsilon\langle R^2\rangle \le \frac{1}{N^2}\sum_{i,j}q^{d_G(i,j)}.} \]

At \(\varepsilon=1\), read the diagonal contribution as one: the bound is \(1/N\). The spectral calculation is the familiar one from O’Donnell’s Analysis of Boolean Functions, §2.4. No influence estimate or hypercontractive inequality is needed.

How small can the perturbation be?

For a nearest-neighbor box of side length \(L\) in \(d\) dimensions, \(N=L^d\). The distance sum is bounded by the corresponding sum on the full lattice:

\[ \sum_j q^{d_G(i,j)} \le \left(\sum_{m\in\mathbb Z}q^{|m|}\right)^d =\left(\frac{1+q}{1-q}\right)^d. \]

The same bound holds on the torus by choosing a shortest coordinate representative for each vertex. Thus, for \(0<\varepsilon\le1\),

\[ \mathbb E_\varepsilon\langle R^2\rangle \le \frac{1}{L^d} \left(\frac{2-\varepsilon}{\varepsilon}\right)^d \le \left(\frac{2}{\varepsilon L}\right)^d. \]

In particular, \(\varepsilon_L\to0\) is allowed as long as \(\varepsilon_L L\to\infty\). For example, replacing bonds at rate \(L^{-1/2}\) makes the overlap tend to zero. Markov’s inequality turns the second-moment estimate into convergence in probability, under the full joint disorder-and-spin law.

The bound is uniform in temperature. It also holds for independently sampled uniform ground states, either by the same gauge argument or by taking \(\beta\to\infty\) in finite volume. It does not assert the conclusion for every deterministic rule that selects one of many ground states.

Why the broader paper uses Hermite analysis

Chen, Kim and Sen represent symmetric couplings as an odd function of a Gaussian variable. Fourier–Hermite analysis then treats several disorder laws, two kinds of perturbation, and hypergraph interactions within one framework. They explicitly connect bond resampling to Boolean noise sensitivity, citing Garban and Steif.

For fair ±J couplings and resampling, the Walsh basis exposes the argument with less machinery: gauge symmetry forces a path, and noise damps every Fourier term carrying that path. This is the elementary specialization of their Lemma 2.2, Proposition 2.4, and Theorem 1.3.

Finally, disorder chaos compares different bond realizations. It does not by itself establish a finite-temperature ordered phase for a single realization: the unperturbed overlap can already be small. Fixed boundary spins or an external field also change the gauge argument and require a separate treatment.

P.S. UGC and a ground-state approximation gap

Assuming the Unique Games Conjecture (UGC) is true—which OpenAI recently claimed to prove—there is a neat, already-known consequence for approximating Ising ground states on general interaction graphs. The implication below takes UGC as an assumption.

Give each edge a coupling \(J_{uv}\in\{-1,+1\}\), and let \(m=|E|\). Count satisfied bonds, meaning those with \(J_{uv}\sigma_u\sigma_v=+1\):

\[ \begin{aligned} S(\sigma)&=\sum_{\{u,v\}\in E} \frac{1+J_{uv}\sigma_u\sigma_v}{2},\\ H_J(\sigma)&=-\sum_{\{u,v\}\in E}J_{uv}\sigma_u\sigma_v =m-2S(\sigma). \end{aligned} \]

Writing \(\sigma_v=(-1)^{x_v}\), each satisfied bond is the XOR constraint \(x_u\oplus x_v=(1-J_{uv})/2\). Thus maximizing \(S\) is exactly Max-2-Lin over \(\mathbb F_2\). In the special case \(J_{uv}=-1\) on every edge, satisfied bonds are precisely edges crossing the spin-defined cut. Max-Cut is already an Ising ground-state problem on the same graph. No embedding gadgets are needed.

Khot, Kindler, Mossel and O’Donnell (KKMO), Theorem 1, show that UGC makes it NP-hard to approximate Max-Cut within any factor greater than the Goemans–Williamson constant \(\alpha_{\mathrm{GW}}\approx0.878567\). Consequently, for any fixed \(\eta>0\), finding spins guaranteed to satisfy \(S(\sigma)\ge(\alpha_{\mathrm{GW}}+\eta)S_{\mathrm{opt}}\) is NP-hard for the general \(\pm J\) class as well. This is an existing hardness theorem expressed in spin-glass language.

For a concrete ground-state energy-density gap, write \(E_0=\min_\sigma H_J(\sigma)\). KKMO’s theorem says that for every fixed \(-1<\rho<0\) and \(\delta>0\), it is NP-hard to distinguish a maximum satisfied fraction at least \((1-\rho)/2\) from one at most \(\arccos(\rho)/\pi+\delta\). The identity \(E_0=m-2S_{\mathrm{opt}}\) gives the following energy bounds in the two cases, respectively:

\[ \begin{aligned} E_0/m&\le\rho,\\ E_0/m&\ge 1-\frac{2}{\pi}\arccos(\rho)-2\delta. \end{aligned} \]

At the parameter giving \(\alpha_{\mathrm{GW}}\), \(\rho\approx-0.689158\). The two thresholds are approximately \(-0.689158\) versus \(-0.484039\), with arbitrarily small slack in the latter. These numbers are just KKMO’s gap converted into energy units; the \(0.878567\) approximation ratio itself applies to satisfied bonds, whose objective includes the constant offset \(m\).

The scope matters. These are worst-case instances on general graphs, not a hardness result for independently sampled fair bonds. Fixed-dimensional nearest-neighbor lattices admit polynomial-time approximation schemes for the satisfied-bond objective; see Bansal, Bravyi and Terhal. Also, this optimization hardness is a separate statement from the disorder-chaos estimate above. The connection back to the lectures is that KKMO’s proof uses Boolean noise stability and the Majority Is Stablest theorem.

Sources