← Eyal Merhavi · Labelings, models, and gauge theory

Chapter 7 of Labelings, models, and gauge theory, rendered from the executed notebook. Code cells and their outputs are shown as they ran.

Run this chapter in your browser ↗ · Source on GitHub ↗
Runs on JupyterLite. The first time, it downloads Python and its libraries (about 40 MB).

Chapter 7 — A gap you can prove

Two things in this course have been forgetting. In chapter 4, the heat-bath sampler started from an arbitrary labeling and, after enough sweeps, forgot where it started. In chapter 5, two layers of a board forgot each other at a rate we called the gap. We measured both, but proved neither.

This chapter proves that they are the same phenomenon, and turns it into a theorem. If every edge listens only weakly to its neighbors, then two samplers fed the same random numbers are forced to agree. From that one fact follow decaying correlations and then a positive gap, with an explicit number. The result holds for every compact label group, every dimension and every board width. It is the small-stiffness end of the mass-gap story of chapter 6 (physicists say "strong coupling"), proved from scratch. Its method is a standard tool of computer science, the coupling argument used to show that Markov chain samplers run fast.

The last section is the honest part. It explains exactly why this theorem, and every theorem of its kind, stops short of the Millennium problem. It also explains what the 2026 existence proof does and does not supply toward closing the distance.

What you'll learn

Prerequisites: chapters 2 (models), 4 (heat bath, face remainders) and 5 (transfer matrix, levels). The last section uses chapter 6.

import itertools
import numpy as np
import matplotlib.pyplot as plt
from scipy.sparse.linalg import LinearOperator, eigsh

from lgt import *
from lgt import viz
from lgt.grid import GridModel

viz.use_style()
rng = np.random.default_rng(7)

7.1 How much does one edge listen to another?

Recall the heat bath (chapter 4). To update one edge ee, you hold every other label fixed and draw U(e)U(e) from its conditional distribution. That distribution depends only on the face remainders of the faces through ee (glossary 4.8):

μe(dx∣U)∝exp⁡(−β∑f∋eφ(xrf(e)))σ(dx). \mu_e(dx\mid U)\ \propto\ \exp\Big(-\beta\sum_{f\ni e}\varphi\big(x\,r_f(e)\big)\Big)\,\sigma(dx).

Change the label of some other edge e′e', and the conditional distribution at ee may move. If ee and e′e' share no face, it does not move at all. If they share a face, it moves a little. To say "a little" precisely, we need a distance between distributions.

Definition (distance between distributions). For two distributions p,qp,q on the same set, d(p,q)∈[0,1]d(p,q)\in[0,1] is the largest difference in probability they assign to any event:

d(p,q)=maxA|p(A)−q(A)|=12∑x|p(x)−q(x)|. d(p,q)=\max_{A}\,\big|p(A)-q(A)\big|=\tfrac12\sum_x|p(x)-q(x)| .

For distributions with densities, the sum becomes an integral. (Probabilists call this the total variation distance.)

Definition (influence). For edges e≠e′e\neq e', the influence of e′e' on ee is C(e,e′)∈[0,1]C(e,e')\in[0,1]:

C(e,e′)=max⁡{d(μe(⋅∣U),μe(⋅∣U′)):U,U′ differ only at e′}. C(e,e')=\max\Big\lbrace d\big(\mu_e(\cdot\mid U),\,\mu_e(\cdot\mid U')\big)\ :\ U,U'\text{ differ only at }e'\Big\rbrace .

Set C(e,e)=0C(e,e)=0. The influence number of the model is the most any edge listens in total:

α=maxe∑e′C(e,e′). \alpha=\max_e\sum_{e'}C(e,e').

Finally, the influence distance between two sets of edges is the fewest steps between them, where one step moves between two edges that share a face. (Probabilists call CC Dobrushin's interdependence matrix, and α<1\alpha<1 Dobrushin's condition.)

The influence of one face on an edge is controlled by a small lemma about tilting a distribution. Here tanh\operatorname{tanh} is the hyperbolic tangent; for small cc, tanh⁡(c/4)≈c/4\tanh(c/4)\approx c/4.

Fact 7.1 (tilting by a bounded factor). Let pp be a distribution and gg a positive function whose largest value is at most ece^{c} times its smallest. Let pg∝gpp_g\propto g\,p be pp reweighted by gg. Then d(p,pg)≤tanh⁡(c/4)d(p,p_g)\le\tanh(c/4), with equality for a well-chosen two-point pp.

Proof. Rescale gg so that it takes values in [b,1][b,1] with b=e−cb=e^{-c}, and let m=⟨g⟩p∈[b,1]m=\langle g\rangle_p\in[b,1]. Then

d(p,pg)=⟨(1−g/m)+⟩p. d(p,p_g)=\big\langle\big(1-g/m\big)_+\big\rangle_p .

Fix mm. The function g↦(1−g/m)+g\mapsto(1-g/m)_+ is convex, so it lies below its chord between bb and 11. At g=1g=1 it is 00, because m≤1m\le1. Averaging the chord gives d≤s(1−b/m)d\le s\,(1-b/m), where ss is the weight the chord puts on bb; the mean constraint forces s=(1−m)/(1−b)s=(1-m)/(1-b). Substituting,

d≤(1−m)(m−b)(1−b)m=1+b−(m+b/m)1−b≤1+b−2b1−b=1−b1+b=tanh⁡c4, d\le\frac{(1-m)(m-b)}{(1-b)\,m}=\frac{1+b-(m+b/m)}{1-b}\le\frac{1+b-2\sqrt b}{1-b}=\frac{1-\sqrt b}{1+\sqrt b}=\tanh\frac c4,

using m+b/m≥2bm+b/m\ge2\sqrt b. Equality holds when gg takes only the values bb and 11 and m=bm=\sqrt b. ▫\square

Now apply it to the grid. Let Φ=max⁡φ−min⁡φ\Phi=\max\varphi-\min\varphi be the spread of the face cost. For the coin model, Φ=2\Phi=2. For SU(2)SU(2) with φ=2−tr\varphi=2-\operatorname{tr}, Φ=4\Phi=4.

Fact 7.2 (influence on a grid). On a dd-dimensional torus grid with every side at least 3, take any compact GG and any face cost of spread Φ\Phi. Then C(e,e′)≤tanh⁡(βΦ/2)C(e,e')\le\tanh(\beta\Phi/2) when ee and e′e' share a face, and C(e,e′)=0C(e,e')=0 otherwise. Every edge shares a face with exactly 6(d−1)6(d-1) other edges. So the influence number satisfies α≤6(d−1)tanh⁡(βΦ/2)\alpha\le6(d-1)\tanh(\beta\Phi/2).

Proof. With side at least 3, two edges share at most one face ff. Changing U(e′)U(e') changes only rf(e)r_f(e), so it reweights μe\mu_e by g(x)=exp⁡(−β[φ(xrf′)−φ(xrf)])g(x)=\exp\big(-\beta[\varphi(xr_f')-\varphi(xr_f)]\big). The exponent lies in [−βΦ,βΦ][-\beta\Phi,\beta\Phi], so max⁡g/min⁡g≤e2βΦ\max g/\min g\le e^{2\beta\Phi}. Fact 7.1 with c=2βΦc=2\beta\Phi gives the bound. For the count: ee lies in 2(d−1)2(d-1) faces, each with 3 other edges, all distinct. ▫\square

Let's check Fact 7.2 against the actual conditional distributions. For the coin model we can try every configuration of the remainders. For SU(2)SU(2) we draw random remainders, including the worst kind of change (one remainder flipped to its negative), and compute the distance by sampling the 3-sphere.

def coin_influence(beta, d):
    """Exact worst influence for the coin model: P(+1) = logistic(2 beta * sum of remainders)."""
    worst = 0.0
    for rs in itertools.product([1, -1], repeat=2 * (d - 1)):
        A, A2 = sum(rs), sum(rs) - 2 * rs[0]           # change the first face's remainder
        p, p2 = 1 / (1 + np.exp(-2 * beta * A)), 1 / (1 + np.exp(-2 * beta * A2))
        worst = max(worst, abs(p - p2))
    return worst

def su2_influence(beta, d, trials=60, n=100_000):
    """Sampled worst influence for SU(2): density on S^3 proportional to exp(2 beta <x, sum of remainders>)."""
    G, worst = SU2(), 0.0
    x = G.uniform(rng, (n,))
    for _ in range(trials):
        r = G.uniform(rng, (2 * (d - 1),)); r2 = r.copy(); r2[0] = -r[0]
        w1, w2 = np.exp(2 * beta * x @ r.sum(0)), np.exp(2 * beta * x @ r2.sum(0))
        worst = max(worst, 0.5 * np.mean(np.abs(w1 / w1.mean() - w2 / w2.mean())))
    return worst
print("        beta   worst influence   Fact 7.2 bound")
for beta in [0.02, 0.1, 0.3]:
    print(f"coin  {beta:5.2f}       {coin_influence(beta, 4):.4f}          {np.tanh(beta):.4f}")
for beta in [0.02, 0.1, 0.3]:
    print(f"SU(2) {beta:5.2f}       {su2_influence(beta, 4):.4f}          {np.tanh(2 * beta):.4f}")
        beta   worst influence   Fact 7.2 bound
coin   0.02       0.0200          0.0200
coin   0.10       0.0987          0.0997
coin   0.30       0.2685          0.2913
SU(2)  0.02       0.0171          0.0400
SU(2)  0.10       0.0846          0.1974
SU(2)  0.30       0.2486          0.5370

Every measured influence sits below its bound. For the coin model at small β\beta the bound is almost exact. For SU(2)SU(2) it is loose by about a factor of 2, because a smooth density on the 3-sphere cannot concentrate the way the worst two-point distribution of Fact 7.1 does.

Recap. The influence C(e,e′)C(e,e') is how far the heat-bath distribution at ee can move when you change the label at e′e'. On a grid it is at most tanh⁡(βΦ/2)\tanh(\beta\Phi/2) for neighbors and zero otherwise. So the influence number obeys α≤6(d−1)tanh⁡(βΦ/2)\alpha\le6(d-1)\tanh(\beta\Phi/2), which is below 1 for small enough β\beta.

Check yourself

  1. For the 4D coin model, below which β\beta does Fact 7.2 guarantee α<1\alpha<1?
Answer

18tanh⁡β<118\tanh\beta<1, so β<artanh⁡(1/18)≈0.0556\beta<\operatorname{artanh}(1/18)\approx0.0556. Compare the jump that chapter 4 found at β≈0.44\beta\approx0.44: the guarantee covers only a small part of the region below the jump.

  1. Why does the influence not depend on how many faces pass through ee?
Answer

Changing U(e′)U(e') changes the remainder of only the one face that ee and e′e' share. The other faces through ee reweight both conditional distributions by the same factor, which cancels in the normalization.

  1. What is Φ\Phi for SU(3)SU(3) with φ=3−Re⁡tr\varphi=3-\operatorname{Re}\operatorname{tr}?
Answer

Re⁡tr\operatorname{Re}\operatorname{tr} is a sum of three cosines of angles adding up to a multiple of 2π2\pi. It is largest, 33, at the identity and smallest, −3/2-3/2, when all three angles are 2π/32\pi/3, i.e. at e2πi/3Ie^{2\pi i/3}I. So Φ=3−(−3/2)=4.5\Phi=3-(-3/2)=4.5.

7.2 Two samplers, one set of dice

Here is the idea that powers the rest of the chapter. Run two heat-bath samplers side by side, started from different labelings, and feed them the same random numbers. Whenever their conditional distributions at an edge are close, the shared randomness makes them pick the same label. Disagreements can then only survive by being passed from neighbor to neighbor. If every edge listens to its neighbors with total strength α<1\alpha<1, disagreements die faster than they spread.

Definition (coupling). A coupling of two distributions p,qp,q is a pair of random variables (X,Y)(X,Y), drawn jointly, with X∼pX\sim p and Y∼qY\sim q. For any coupling, P(X≠Y)≥d(p,q)P(X\neq Y)\ge d(p,q). There is always a coupling with P(X≠Y)=d(p,q)P(X\neq Y)=d(p,q), called a best coupling:

For the coin model the heat bath draws +1+1 when a uniform random number uu falls below P(+1)P(+1). Two samplers using the same uu disagree exactly when uu falls between their two values of P(+1)P(+1), which happens with probability |P(+1)−P′(+1)|=d|P(+1)-P'(+1)|=d. So "same random numbers" is the best coupling.

Fact 7.3 (coupled samplers forget). Run two heat-bath samplers of the same model, updating edges in the same order, and use a best coupling at every update. Let ρt(e)\rho_t(e) be the probability that the two labels at ee differ after tt sweeps. Then max⁡eρt(e)≤αtmax⁡eρ0(e)\max_e\rho_t(e)\le\alpha^t\,\max_e\rho_0(e).

Proof. Look at one update of edge ee, with current labelings XX and YY. Walk from XX to YY by changing their differing labels one at a time. Each change of a label at e′e' moves the conditional distribution at ee by at most C(e,e′)C(e,e'), so

d(μe(⋅∣X),μe(⋅∣Y))≤∑e′C(e,e′)𝟏[X(e′)≠Y(e′)]. d\big(\mu_e(\cdot\mid X),\mu_e(\cdot\mid Y)\big)\ \le\ \sum_{e'}C(e,e')\,\mathbf 1[X(e')\neq Y(e')].

The best coupling makes the new labels differ with exactly that probability. Averaging over X,YX,Y, the new ρ(e)\rho(e) is at most ∑e′C(e,e′)ρ(e′)≤αmax⁡ρ\sum_{e'}C(e,e')\rho(e')\le\alpha\max\rho. So the maximum never grows during a sweep. After a full sweep every edge has been updated once, so every ρ(e)\rho(e) is at most α\alpha times the maximum at the start of the sweep. ▫\square

Fact 7.3 is the first appearance of the computer-science bridge. If one sampler starts from the model itself, it stays distributed as the model, so the other sampler's labels agree with a true sample except with probability at most αt\alpha^t. With |E||E| edges, after t≈log⁡|E|/log⁡(1/α)t\approx\log|E|/\log(1/\alpha) sweeps every label agrees. (Computer scientists call this the path-coupling proof of rapid mixing. Its best-known use shows that the heat bath for graph colorings mixes fast when there are more than 2Δ2\Delta colors, Δ\Delta the maximum degree. The structure is the same: bounded degree, weak dependence.)

Let's watch it happen on the 4D coin model. One sampler starts with every label +1+1, the other with random labels; both use the same random numbers.

def coupled_disagreement(beta, L=6, sweeps=30, seeds=4):
    """Fraction of edges where two coupled heat-bath samplers disagree, after each sweep."""
    runs = []
    for seed in range(seeds):
        X = GridModel((L,) * 4, Z2(), beta).cold_start()
        Y = GridModel((L,) * 4, Z2(), beta).hot_start(np.random.default_rng(100 + seed))
        rX, rY = np.random.default_rng(seed), np.random.default_rng(seed)   # same dice
        frac = [np.mean(X.U != Y.U)]
        for _ in range(sweeps):
            X.sweep(rX); Y.sweep(rY)
            frac.append(np.mean(X.U != Y.U))
        runs.append(frac)
    return np.mean(runs, axis=0)
fig, ax = plt.subplots(figsize=(8, 4.2))
t = np.arange(31)
for beta, col in [(0.03, viz.TEAL), (0.05, viz.INK), (0.2, viz.GOLD), (0.6, viz.CORAL)]:
    alpha = 18 * np.tanh(beta)
    ax.semilogy(t, np.maximum(coupled_disagreement(beta), 1e-5), "o-", ms=3, color=col,
                label=rf"$\beta={beta}$, bound on $\alpha$: {alpha:.2f}")
    if alpha < 1:
        ax.semilogy(t, 0.5 * alpha ** t, "--", color=col, lw=1)
ax.set(ylim=(1e-5, 1), xlabel="sweeps", ylabel="fraction of edges that disagree",
       title="4D coin model: two samplers, same random numbers (dashed: Fact 7.3)")
ax.legend(fontsize=9); plt.show()
On a log scale, the fraction of edges on which two coupled samplers disagree, over 30 sweeps of the 4D coin model. At stiffness 0.03 and 0.05 it falls to zero within 5 and 9 sweeps, below dashed guarantee lines; at 0.2 and 0.6 it levels off and never dies.

Look at the two regimes. For α<1\alpha<1 (teal, ink), disagreements vanish entirely within a few sweeps, below the dashed guarantee. (The plot floors exact zero at 10−510^{-5}.) For β=0.2\beta=0.2 and 0.60.6, Fact 7.2 gives no guarantee, and the disagreements never die. They fail in two different ways:

Recap. A coupling runs two random processes on shared randomness. With the best coupling at every update, the chance that two heat-bath samplers disagree at any edge shrinks by a factor α\alpha per sweep. When α<1\alpha<1 the sampler forgets its start geometrically fast.

Check yourself

  1. In the proof, why is it important that the samplers use the best coupling rather than independent random numbers?
Answer

With independent draws, two identical conditional distributions would still give different labels most of the time, so disagreements would never die. The best coupling makes the disagreement probability equal to the distance between the conditional distributions, which is what the influences bound.

  1. On the 646^4 coin model at β=0.03\beta=0.03, roughly how many sweeps does Fact 7.3 need before all 51845184 labels agree with probability at least 0.990.99?
Answer

α≤18tanh⁡0.03≈0.54\alpha\le18\tanh0.03\approx0.54. We need 5184⋅12αt<0.015184\cdot\tfrac12\alpha^t<0.01, so t>ln⁡(259200)/ln⁡(1/0.54)≈20t>\ln(259200)/\ln(1/0.54)\approx20 sweeps. In the plot it took fewer: the bound is a guarantee, not a prediction.

7.3 From forgetting to decorrelation

Forgetting in time (sweeps of a sampler) now gives forgetting in space (distance on the board). The trick: a correlation between AA and BB measures how much conditioning on BB moves the average of AA. Conditioning on BB is the same as reweighting the model by BB. A reweighted model is a new model whose conditional distributions agree with the old one at every edge that BB does not read. So we can couple a sampler of the old model with a sampler of the reweighted one. Their disagreements are created only on BB's edges, and they fade with influence distance.

For a function AA of a labeling, write osc⁡(A)=max⁡A−min⁡A\operatorname{osc}(A)=\max A-\min A. Say AA reads a set of edges SAS_A if it depends only on their labels.

Fact 7.4 (decorrelation). Suppose α<1\alpha<1. Let AA read SAS_A, let BB read SBS_B, and let DD be the influence distance between SAS_A and SBS_B. Then the correlation of AA and BB is at most osc⁡(A)osc⁡(B)|SA|αD/(1−α)\operatorname{osc}(A)\,\operatorname{osc}(B)\,|S_A|\,\alpha^{D}/(1-\alpha) in absolute value.

In one line:

|⟨AB⟩−⟨A⟩⟨B⟩|≤osc⁡(A)osc⁡(B)|SA|αD1−α. \big|\langle AB\rangle-\langle A\rangle\langle B\rangle\big|\ \le\ \operatorname{osc}(A)\,\operatorname{osc}(B)\,|S_A|\,\frac{\alpha^{D}}{1-\alpha}.

Proof.

Step 1 (reweight). Replace BB by B′=B−min⁡B≥0B'=B-\min B\ge0; this does not change the correlation. If ⟨B′⟩=0\langle B'\rangle=0 the correlation is 00. Otherwise let ν\nu be the model reweighted by B′B', that is, ν(dU)=B′(U)μ(dU)/⟨B′⟩\nu(dU)=B'(U)\mu(dU)/\langle B'\rangle. Then ⟨AB⟩−⟨A⟩⟨B⟩=⟨B′⟩(⟨A⟩ν−⟨A⟩)\langle AB\rangle-\langle A\rangle\langle B\rangle=\langle B'\rangle\big(\langle A\rangle_\nu-\langle A\rangle\big), and ⟨B′⟩≤osc⁡(B)\langle B'\rangle\le\operatorname{osc}(B).

Step 2 (same conditionals off SBS_B). At an edge e∉SBe\notin S_B, the factor B′B' does not depend on U(e)U(e). It cancels from the conditional distribution, so ν\nu and μ\mu have the same heat bath at ee.

Step 3 (couple). Run a heat-bath sampler XX of μ\mu and one YY of ν\nu, started from samples of μ\mu and ν\nu, so that at every time X∼μX\sim\mu and Y∼νY\sim\nu. Use best couplings. An update at ee produces a disagreement with probability at most ∑e′C(e,e′)ρ(e′)\sum_{e'}C(e,e')\rho(e') if e∉SBe\notin S_B, and at most 11 if e∈SBe\in S_B. Let

ρ*=∑k≥0Ck𝟏SB,so thatρ*=𝟏SB+Cρ*. \rho^*=\sum_{k\ge0}C^k\,\mathbf 1_{S_B},\qquad\text{so that}\qquad\rho^*=\mathbf 1_{S_B}+C\rho^* .

The sum converges because every row of CC sums to at most α<1\alpha<1. Exactly as in Fact 7.3, the excess max⁡e(ρt(e)−ρ*(e))+\max_e(\rho_t(e)-\rho^*(e))_+ shrinks by a factor α\alpha per sweep. So ρt≤ρ*+αt\rho_t\le\rho^*+\alpha^t.

Step 4 (read off AA). |⟨A⟩ν−⟨A⟩|=|𝔼[A(Yt)−A(Xt)]|≤osc⁡(A)∑e∈SAρt(e)\big|\langle A\rangle_\nu-\langle A\rangle\big|=\big|\mathbb E[A(Y_t)-A(X_t)]\big|\le\operatorname{osc}(A)\sum_{e\in S_A}\rho_t(e). Now let t→∞t\to\infty.

Step 5 (count paths). Ck(e,e′)C^k(e,e') is a sum over chains of kk face-sharing steps from ee to e′e', so it vanishes unless k≥Dk\ge D. Each power satisfies ∑e′Ck(e,e′)≤αk\sum_{e'}C^k(e,e')\le\alpha^k. So ρ*(e)≤∑k≥Dαk=αD/(1−α)\rho^*(e)\le\sum_{k\ge D}\alpha^k=\alpha^D/(1-\alpha) for e∈SAe\in S_A. ▫\square

Notice what the proof never used: reframings, the group structure, or the dimension. Only the sparsity of who-listens-to-whom (a bounded-degree influence graph) and the weakness of each link matter. (Probabilists call this Dobrushin's uniqueness theorem. Computer scientists know its relatives as "spatial mixing" and "correlation decay", the engine of several deterministic approximate-counting algorithms.)

Checking Fact 7.4 exactly. We need a model where correlations at long distances can be computed exactly, not sampled. The transfer matrix of chapter 5 does that. Take the 3D coin model, layered so that each layer is a 3×33\times3 torus. Its 18 layer edges give 2182^{18} layer labelings, and the invariant functions form a subspace of dimension 1024. The helper below applies TT without ever writing it down, using two facts:

Its derivation is in the helper's comments.

# --- helpers: the exact transfer matrix of the 3D coin model on a W x W torus layer ----------------
# Layer labeling a in {+1,-1}^n (n = 2 W^2 layer edges). Summing the step edges over all their values is
# the same as summing over reframings of the upper layer (Fact 5.1), so on invariant functions
#     T = 2^(W^2) * D^(1/2) K D^(1/2),   K(a,b) = prod_e exp(-beta (1 - a_e b_e)),
# with D(a) = exp(-beta * total cost of the faces inside the layer) (split half and half between slabs).
# K is a tensor power of a 2x2 matrix, diagonal in the "parity" basis chi_S(a) = prod_{e in S} a_e,
# with eigenvalue (1+q)^(n-|S|) (1-q)^|S|, q = exp(-2 beta). chi_S is invariant exactly when S has even
# degree at every vertex. We apply K with a fast Walsh-Hadamard transform (n passes of sums/differences).

def layer_geometry(W):
    edges = [((x, y), mu) for x in range(W) for y in range(W) for mu in (0, 1)]
    eid = {e: i for i, e in enumerate(edges)}
    head = lambda v, mu: ((v[0] + (mu == 0)) % W, (v[1] + (mu == 1)) % W)
    faces = [[eid[((x, y), 0)], eid[(head((x, y), 0), 1)], eid[(head((x, y), 1), 0)], eid[((x, y), 1)]]
             for x in range(W) for y in range(W)]
    at_vertex = {}
    for (v, mu), i in eid.items():
        at_vertex.setdefault(v, []).append(i); at_vertex.setdefault(head(v, mu), []).append(i)
    return len(edges), faces, at_vertex

def walsh(f, n):
    x = f.reshape((2,) * n)
    for ax in range(n):
        a, b = np.take(x, 0, axis=ax), np.take(x, 1, axis=ax)
        x = np.stack([a + b, a - b], axis=ax)
    return x.reshape(-1)

class CoinLayerTransfer:
    """T / 2^(W^2) restricted to invariant functions of a W x W torus layer of the 3D coin model."""
    def __init__(self, W, beta):
        n, faces, at_vertex = layer_geometry(W)
        idx = np.arange(2 ** n, dtype=np.int64)
        bit = lambda i: np.int64(1) << (n - 1 - i)
        self.label = lambda i: 1 - 2 * ((idx & bit(i)) != 0)        # value of layer edge i, per labeling
        S_in = sum(1 - np.prod([self.label(e) for e in f], axis=0) for f in faces)
        self.Dh, self.n, self.faces = np.exp(-beta * S_in / 2), n, faces
        pop = lambda m: np.bitwise_count((idx & m).astype(np.uint64)).astype(np.int64)
        even = np.ones(2 ** n, dtype=bool)
        for es in at_vertex.values():
            even &= pop(np.bitwise_or.reduce([bit(e) for e in es])) % 2 == 0
        q, size = np.exp(-2 * beta), pop(np.int64(-1) & (2 ** n - 1))
        self.diag = even * (1 + q) ** (n - size) * (1 - q) ** size / 2 ** n
    def apply(self, f):
        return self.Dh * walsh(self.diag * walsh(self.Dh * f, self.n), self.n)
    def top(self, k=2):
        op = LinearOperator((2 ** self.n,) * 2, matvec=self.apply, dtype=float)
        vals, vecs = eigsh(op, k=k, which="LA")
        order = np.argsort(vals)[::-1]
        return vals[order], vecs[:, order]

First, a sanity check of the helper. The face product of one face inside layer 0, A=UfA=U_f, is an invariant. On a board with infinitely many layers, the average of A(a0)A(at)A(a_0)A(a_t) is ψ0⊤MA(T/λ0)tMAψ0\psi_0^{\top}M_A(T/\lambda_0)^tM_A\psi_0, where ψ0\psi_0 is the top eigenvector and MAM_A multiplies by AA (chapter 5, section 5.5). Fact 7.4 bounds the correlation by 2⋅2⋅4αt/(1−α)2\cdot2\cdot4\,\alpha^t/(1-\alpha), with α≤12tanh⁡β\alpha\le12\tanh\beta in 3D.

beta = 0.05
TL = CoinLayerTransfer(3, beta)
(lam0, _), vecs = TL.top()
psi0 = vecs[:, 0]
A = np.prod([TL.label(e) for e in TL.faces[0]], axis=0).astype(float)       # one face product
v, mean_A = A * psi0, psi0 @ (A * psi0)
alpha = 12 * np.tanh(beta)
print(f"beta = {beta}, alpha <= {alpha:.3f}")
for t in range(1, 3):
    v = TL.apply(v) / lam0
    corr = psi0 @ (A * v) - mean_A ** 2
    print(f"t = {t}: exact correlation {corr:.3e}   Fact 7.4 bound {16 * alpha ** t / (1 - alpha):.3e}")
print(f"tanh(beta)^4 = {np.tanh(beta) ** 4:.3e}")
beta = 0.05, alpha <= 0.600
t = 1: exact correlation 6.198e-06   Fact 7.4 bound 2.395e+01
t = 2: exact correlation 3.852e-11   Fact 7.4 bound 1.436e+01
tanh(beta)^4 = 6.229e-06

The exact correlation falls by a factor of about tanh⁡(β)4≈6×10−6\tanh(\beta)^4\approx6\times10^{-6} per layer. (Beyond t=2t=2 it drops below rounding error.) The guaranteed rate is α=0.6\alpha=0.6 per layer, and the guaranteed constant is far above 1 at these distances. The bound is extremely generous, but it is a proof, and it holds for every board width at once. The factor tanh⁡(β)4\tanh(\beta)^4 has a simple meaning: to correlate a face in layer tt with one in layer 00, the model has to pass the information through the four side faces of the cube between them.

Recap. Reweighting by BB creates a model that agrees with the original everywhere except on BB's edges. Coupling samplers of the two models shows that the disagreement leaks from SBS_B to SAS_A only along chains of influences, each costing a factor α\alpha. So correlations decay like αdistance\alpha^{\text{distance}}.

Check yourself

  1. Fact 7.4 has |SA||S_A| but not |SB||S_B| in the bound. Why the asymmetry?
Answer

Disagreements are created on SBS_B, with probability at most 1 per edge. But we bound their arrival at each edge of SAS_A by a sum over all sources, which is already included in ρ*\rho^*. Then we add over the edges of SAS_A that AA reads. (Applying the fact with AA and BB swapped gives the other version; use whichever is smaller.)

  1. Does Fact 7.4 say anything about non-invariant functions, such as a single label?
Answer

Yes. It holds for all functions, but for a single label it is vacuous: single labels average to zero (chapter 3), and so do their products at different edges. The real content is about invariants such as face products and loop observables.

7.4 From decorrelation to a gap

Chapter 5 showed, by experiment, that the gap is the rate at which layers forget each other. Now we can run that observation backwards as a proof. Decorrelation at rate α\alpha per layer forces every level to sit at least ln⁡(1/α)\ln(1/\alpha) above the lowest.

Fact 7.5 (a provable gap). Take a layered torus grid in dd dimensions whose layers are (d−1)(d-1)-dimensional tori of side W≥3W\ge3. Let GG be any compact group and φ\varphi any face cost of spread Φ\Phi. If α=6(d−1)tanh⁡(βΦ/2)<1\alpha=6(d-1)\tanh(\beta\Phi/2)<1, then every level of the transfer matrix satisfies En≥ln⁡(1/α)E_n\ge\ln(1/\alpha) for n≥1n\ge1. In particular the gap is at least ln⁡(1/α)\ln(1/\alpha), for every width WW.

Proof. We write it for finite GG. For compact GG, replace sums by integrals; the Perron–Frobenius theorem for matrices is then replaced by its version for positive integral kernels (Jentzsch's theorem).

Step 1 (the top eigenvector is positive). Every entry T(a,b)T(a,b) is a sum of positive weights, and TT is symmetric (chapter 5). By the Perron–Frobenius theorem, λ0\lambda_0 is simple and has an eigenvector ψ0\psi_0 with every entry positive.

Step 2 (a test function for each level). Let ψn\psi_n be a unit eigenvector for λn\lambda_n, n≥1n\ge1, so ψn⟂ψ0\psi_n\perp\psi_0. Define the function of a layer labeling F=ψn/ψ0F=\psi_n/\psi_0; this is legal because ψ0>0\psi_0>0. On a board with NN layers, the average of F(a0)F(at)F(a_0)F(a_t) is tr⁡(MFTtMFTN−t)/tr⁡TN\operatorname{tr}(M_FT^tM_FT^{N-t})/\operatorname{tr}T^N. As N→∞N\to\infty, TN−t/λ0N−tT^{N-t}/\lambda_0^{N-t} tends to ψ0ψ0⊤\psi_0\psi_0^\top. So the average tends to

ψ0⊤MFTtMFψ0λ0t=ψn⊤Ttψnλ0t=(λnλ0)t, \frac{\psi_0^\top M_FT^tM_F\psi_0}{\lambda_0^t}=\frac{\psi_n^\top T^t\psi_n}{\lambda_0^t}=\Big(\frac{\lambda_n}{\lambda_0}\Big)^t,

and ⟨F⟩→ψ0⊤ψn=0\langle F\rangle\to\psi_0^\top\psi_n=0.

Step 3 (apply Fact 7.4). F(a0)F(a_0) reads the (d−1)Wd−1(d-1)W^{d-1} layer edges of layer 0, and F(at)F(a_t) those of layer tt. A face touches at most two consecutive layers, so the influence distance between layer 0 and layer tt is at least min⁡(t,N−t)\min(t,N-t). Fact 7.4 gives, uniformly in NN,

|⟨F(a0)F(at)⟩−⟨F⟩2|≤Kαmin⁡(t,N−t),K=osc⁡(F)2(d−1)Wd−1/(1−α). \big|\langle F(a_0)F(a_t)\rangle-\langle F\rangle^2\big|\le K\alpha^{\min(t,N-t)},\qquad K=\operatorname{osc}(F)^2\,(d-1)W^{d-1}/(1-\alpha).

Step 4 (take roots). Let N→∞N\to\infty: (λn/λ0)t≤Kαt(\lambda_n/\lambda_0)^t\le K\alpha^t for every tt. Take tt-th roots and let t→∞t\to\infty: λn/λ0≤α\lambda_n/\lambda_0\le\alpha. ▫\square

Step 4 is where the width disappears. KK grows with WW, but it is a constant in tt, and the tt-th root kills it. The rate α\alpha only knows about one edge and its 6(d−1)6(d-1) neighbors.

Now the comparison with exact gaps. For the 2D coin model chapter 5 gave E1=−Wln⁡tanh⁡βE_1=-W\ln\tanh\beta. For the 3D coin model with 3×33\times3 layers, the helper computes it.

betas = np.geomspace(0.004, 1.0, 26)
E1_3d = []
for b in betas:
    (l0, l1), _ = CoinLayerTransfer(3, b).top()
    E1_3d.append(-np.log(l1 / l0))
E1_3d = np.array(E1_3d)
floor = lambda d: np.where(6 * (d - 1) * np.tanh(betas) < 1, -np.log(6 * (d - 1) * np.tanh(betas)), np.nan)
print("beta     exact E1 (3D, W=3)   proven floor (3D)")
for i in [0, 8, 12, 14]:
    print(f"{betas[i]:.4f}   {E1_3d[i]:8.3f}             {floor(3)[i]:.3f}")
beta     exact E1 (3D, W=3)   proven floor (3D)
0.0040     16.564             3.037
0.0234     11.264             1.270
0.0566      8.616             0.387
0.0881      7.294             nan
fig, ax = plt.subplots(figsize=(8, 4.4))
ax.plot(betas, -3 * np.log(np.tanh(betas)), color=viz.MUTED, lw=1.5, label="exact gap, 2D, $W=3$")
ax.plot(betas, E1_3d, "o-", ms=3, color=viz.INK, label="exact gap, 3D, $3\\times3$ layers")
ax.plot(betas, floor(2), color=viz.TEAL, lw=2.5, label="proven floor $\\ln(1/\\alpha)$, 2D (any $W$)")
ax.plot(betas, floor(3), color=viz.CORAL, lw=2.5, label="proven floor $\\ln(1/\\alpha)$, 3D (any $W$)")
ax.axvspan(betas[0], np.arctanh(1 / 12), color=viz.CORAL, alpha=0.08)
ax.set(xscale="log", ylim=(0, 18), xlabel=r"stiffness $\beta$", ylabel="gap $E_1$",
       title="Coin model: true gaps and the floor that Fact 7.5 proves")
ax.legend(fontsize=9); plt.show()
Gap E_1 against stiffness on a log axis. The exact gaps in 2D and 3D fall from about 16 towards 0; the proven floors, a teal line for 2D and a coral line for 3D, stay well below them. A shaded band marks where the 3D guarantee applies.

Look at the shaded region, where the 3D guarantee applies: the coral floor stays under the exact gap, as it must. It is far under, by a factor of about 8. The floor is crude but universal. It holds for every width at once and for every compact group with the same spread, and it knew nothing about this particular board beyond "each edge has 12 neighbors". As β\beta grows past artanh⁡(1/12)≈0.083\operatorname{artanh}(1/12)\approx0.083, the floor drops to zero and the theorem says nothing. The true 3D gap keeps going, and becomes small near β≈0.76\beta\approx0.76, where the 3D coin model has a jump of its own.

One more observation: at small β\beta the exact 3D gap is about −3ln⁡tanh⁡β-3\ln\tanh\beta, the same as the 2D gap with W=3W=3. The lightest state is a loop of length 3 wrapping around the layer. That is the "flux loop" of chapter 5, whose level grows with its length.

Recap. Each level EnE_n is the decay rate of the correlation of a specific layer function, F=ψn/ψ0F=\psi_n/\psi_0. Fact 7.4 bounds every such correlation by a constant times αt\alpha^t. Taking tt-th roots removes the constant, so En≥ln⁡(1/α)E_n\ge\ln(1/\alpha) for every n≥1n\ge1 and every width. The exact gaps of the coin model confirm the floor.

Check yourself

  1. Why do we need ψ0\psi_0 to be positive everywhere?
Answer

To divide by it: F=ψn/ψ0F=\psi_n/\psi_0 must be a genuine function of the layer labeling, with MFψ0=ψnM_F\psi_0=\psi_n. Perron–Frobenius guarantees positivity because every entry of TT is positive.

  1. For 4D SU(2)SU(2) with φ=2−tr\varphi=2-\operatorname{tr}, what does Fact 7.5 prove at β=0.01\beta=0.01?
Answer

Φ=4\Phi=4, so α≤18tanh⁡(0.02)≈0.36\alpha\le18\tanh(0.02)\approx0.36, and E1≥ln⁡(1/0.36)≈1.02E_1\ge\ln(1/0.36)\approx1.02 on every 4D torus grid, whatever its width. The correlation length is at most about 1 grid step.

  1. The 2D gap −Wln⁡tanh⁡β-W\ln\tanh\beta grows with WW. Is that consistent with a floor that does not depend on WW?
Answer

Yes. A floor is only a lower bound, and −Wln⁡tanh⁡β≥−3ln⁡tanh⁡β>ln⁡(1/(6tanh⁡β))-W\ln\tanh\beta\ge-3\ln\tanh\beta>\ln(1/(6\tanh\beta)) for all W≥3W\ge3. The floor cannot grow with WW because it is proved one edge at a time, without ever looking at the size of the layer.

7.5 Why this does not prove the Millennium gap

Fact 7.5 is a real theorem about lattice Yang–Mills. With G=SU(N)G=SU(N) on a 4D grid it is the small-β\beta entry "positive gap at small β\beta, proved" in chapter 6's status table, re-derived with a computer-science tool. Here is how far it reaches:

Model (4D) Spread Φ\Phi Fact 7.5 applies for our β<\beta< physicists' βphys<\beta_{\text{phys}}< Where continuum physics is simulated (βphys\beta_{\text{phys}})
coin 2 0.056 – –
SU(2)SU(2) 4 0.028 0.056 2.3 – 3
SU(3)SU(3) 4.5 0.025 0.074 5.7 – 7

The gap between the last two columns is a factor of 40 to 100. But the true obstruction is not the size of the constants. There are three separate reasons, in increasing order of depth.

1. Influence grows with stiffness. At large β\beta each edge listens strongly to its neighbors, so α>1\alpha>1. This is not only a weakness of the bound: as correlations reach further, the heat-bath sampler of chapter 4 really does slow down, because forgetting in space and forgetting in time go together. Sharper tools from computer science ("spectral independence", block dynamics, "high-dimensional expanders") push the threshold further. But they all certify the same kind of thing: correlations die within a bounded number of grid steps, with constants fixed in advance. Reason 3 shows why that kind of certificate must fail along the continuum path.

2. The board's geometry is not the issue. The hint "use expander graphs" points at a real principle, local-to-global: a local condition on a sparse graph (α<1\alpha<1 on the influence graph) gives a global conclusion. But Fact 7.5 already works on the 4D grid, which is a poor expander: a box of side ℓ\ell has ℓ4\ell^4 vertices but only about ℓ3\ell^3 boundary edges. Expansion of the board plays no role. What matters is the weakness of each link, and that is exactly what fails at large β\beta.

3. The scale problem (the deep one). The Millennium gap is not "the gap is positive". From chapter 6: as the grid spacing ε→0\varepsilon\to0, with β(ε)\beta(\varepsilon) growing like 116π2ln⁡(1/ε)\tfrac{11}{6\pi^2}\ln(1/\varepsilon) for SU(2)SU(2), one needs

E1(β(ε))ε→Δ,0<Δ<∞. \frac{E_1(\beta(\varepsilon))}{\varepsilon}\ \longrightarrow\ \Delta,\qquad 0<\Delta<\infty .

A bound like E1≥ln⁡(1/α)E_1\ge\ln(1/\alpha), a constant in grid units, would give E1/ε→∞E_1/\varepsilon\to\infty if it held along the continuum path: every particle infinitely heavy, and the limit would be trivial. So a proof must show that the gap in grid units shrinks, exponentially in β\beta, at the rate set by asymptotic freedom, and no faster. That is a statement connecting all scales at once. No single-scale argument can deliver it.

What a proof would need, in our terms. Group the grid into blocks of side 2k2^k. The distribution of suitable block labels is again a model, with a more complicated but still local cost. Asymptotic freedom says its effective stiffness decreases as the blocks grow. So the natural plan, Balaban's, is:

The first step is done. The last is this chapter, plus a locality lemma. The middle step is the open problem. The UV methods work by expanding around consistent labelings, which needs large stiffness. The IR method needs stiffness below about 0.03. Between them is the smooth crossover you saw in chapter 6's Creutz plot, where the model is neither nearly consistent nor nearly independent, and no known method controls it. The 2026 proof itself avoids this region. Per the committee's assessment, its large-volume step rests on compactness, flip-positivity and the transfer-matrix representation, and it proves no clustering of correlations. That is why it obtains existence along a subsequence, a mixture of phases, and no gap.

Recap. Fact 7.5 covers only β\beta below a few hundredths, far from where the continuum lives. Beyond that, influence is too strong. More fundamentally, the Millennium gap needs the grid-unit gap to shrink at exactly the asymptotic-freedom rate, which is a multi-scale statement. The missing piece is control of the crossover between the near-consistent regime (handled by the 2026 existence proof) and the near-independent regime (handled by this chapter).

Check yourself

  1. Suppose someone proves E1(β)≥0.1E_1(\beta)\ge0.1 for all β\beta in 4D SU(2)SU(2). Would that solve the Millennium gap?
Answer

No, it would refute the expected continuum limit. Along the continuum path the gap in physical units would be E1/ε≥0.1/ε→∞E_1/\varepsilon\ge0.1/\varepsilon\to\infty, so the limiting theory would have no particles at all. Physicists expect E1(β)→0E_1(\beta)\to0 like e−6π2β/11e^{-6\pi^2\beta/11}.

  1. What lower bound on E1(β)E_1(\beta) in grid units, for large β\beta, would a solution need to prove (for SU(2)SU(2), leading order)?
Answer

E1(β)≥ce−6π2β/11E_1(\beta)\ge c\,e^{-6\pi^2\beta/11} for some c>0c>0 and all large β\beta, along with the existence of the limit. Then E1/εE_1/\varepsilon stays bounded below. (An upper bound of the same form, needed for a non-trivial limit, is expected from asymptotic freedom.)

Chapter recap

Dictionary

Our term Other names
distance between distributions d(p,q)d(p,q) total variation distance
best coupling maximal (optimal) coupling
influence C(e,e′)C(e,e') Dobrushin interdependence matrix
α<1\alpha<1 Dobrushin's uniqueness condition; in physics, a "high-temperature" or "strong-coupling" condition
two samplers on the same random numbers synchronous coupling; path coupling (Bubley–Dyer)
sampler forgets geometrically rapid mixing of Glauber dynamics
correlations decay with influence distance spatial mixing, correlation decay, uniqueness of the Gibbs measure
Fact 7.5 for SU(N)SU(N) mass gap at strong coupling (Osterwalder–Seiler 1978, by cluster expansion)
blocking the grid renormalization group (block-spin transformation); Balaban's program
the crossover the intermediate-coupling regime; the gap between perturbative and strong-coupling control

What's next

This chapter ends the elementary road. Two directions continue it. On the computer-science side: can spectral independence or block (multi-scale) dynamics give a gap that shrinks at a controlled rate for the 3D coin model, where the answer is known from its exact relation to the 3D Ising model? On the physics side: the 2026 proof's blocking machinery, read in our terms, is the natural place to look for the crossover step. Read the notes in notes/yang_mills_existence_2026.md with this chapter's three-step plan in mind. The research memo notes/crossover/README.md takes the middle step further: it shows that the simplest blocking scheme runs on the curvature of SU(2)SU(2) (and stalls for the circle), measures how wide the crossover really is, and lists what a certificate tight enough to cross it would need.