============================================================
THE FREE ENERGY OF THE ISING RANDOM PERCEPTRON
A reader-friendly, mathematically faithful edition
============================================================
How to read this edition
------------------------
This file is a complete, self-contained guide to the paper "The free
energy of the Ising random perceptron" (LaTeX source in
ising_perceptron_free_energy_original.txt). It is written in layers.
Part I. The story in plain language.
Part II. The model, the two recursions, and the main theorem.
Part III. The proof at a glance: what each of the six stages does.
Part IV. The engine room: each hard lemma, what it says and why.
Part V. Formal statements, constants, and a dependency chart.
Part VI. Glossary, notation, and questions a first-time reader asks.
A reader with high-school algebra should read Parts I, II, III and VI
first. Parts IV and V are the reference layers. No hypothesis has been
weakened, no step has been replaced by hand-waving, and no theorem is
quoted without saying exactly what it gives. The few genuinely deep
inputs are named BLACK BOX A-E, stated in Part V, and their use is
flagged wherever they appear.
All formulas are plain ASCII. sum_ and int_ mean what they look like,
sqrt(2) is a square root, E is expectation, log is natural log,
a -> b means "a tends to b", and 1{P} is the indicator of the event P.
============================================================
PART I. THE STORY IN PLAIN LANGUAGE
============================================================
1. What is the problem?
-----------------------
An Ising perceptron weighs sign patterns by how well they answer a list
of random questions.
The objects:
* N spins, each +1 or -1, collected into a vector x in {-1,+1}^N.
There are 2^N of them.
* M random questions, called patterns, each a random Gaussian vector
g^a in R^N. The questions have fixed density alpha = M/N.
* The answer of x to question a is its projection,
b_a(x) = (1/sqrt N) sum_i g^a_i x_i.
For a fixed x this is a standard Gaussian number.
* A reward function f, the "log-potential", bounded and possibly very
nonlinear. Configuration x gets the weight
exp( sum_{a=1}^M f(b_a(x)) ).
The question of the paper is: how big is the total weight?
The counting convention shifts everything by one constant. The paper
counts with the uniform probability nu_N, so each x starts with weight
2^{-N}, and defines
Z_N(f) = sum_x 2^{-N} exp( sum_a f(b_a(x)) ),
p_N(f) = (1/N) log Z_N(f).
Then p_N is the pressure, the exponential growth rate of the total
weight. Counting configurations instead of using nu_N adds log 2 to p_N.
If f = beta phi with beta an inverse temperature, the physical free
energy per spin is -p_N/beta.
Two regimes anchor everything:
* f = 0: every configuration weighs the same, and p_N = 0 exactly.
* f(s) = t s linear: p_N can be computed exactly, see section 3.
Everything between those two is the actual problem.
2. Why is it hard?
------------------
For a fixed configuration x, the energy sum_a f(b_a(x)) is a sum of
M = alpha N nonlinear functions of correlated Gaussians. As a function
of x it is a violently non-Gaussian object, and the correlations between
its values at different x are exactly what decides which configurations
win.
So the classical machinery for Gaussian spin glasses, which requires the
energy to be a Gaussian process indexed by the configurations, does not
apply directly. That is why this is a separate paper and not a
corollary of the Parisi formula.
What does survive is the geometry of the winners. Two configurations x
and x' have an overlap
R(x,x') = (1/N) sum_i x_i x'_i in [-1,1],
and under two independent samples of the weighted measure this overlap
is the single most informative statistic. The answer is a variational
problem over its distribution.
3. One exact computation, and why one number is not enough
----------------------------------------------------------
Take f(s) = t s. Then sum_a t b_a(x) = x . theta with
theta_i = (t/sqrt N) sum_a g^a_i,
and the sum over x factors coordinate by coordinate:
Z_N = sum_x 2^{-N} exp(x . theta) = prod_{i=1}^N cosh(theta_i).
The theta_i are independent Gaussian with variance H_N = t^2 M/N -> H =
alpha t^2, so by the law of large numbers, which says that an average of
N independent identically distributed well-behaved quantities settles at
its mean,
p_N = (1/N) sum_i log cosh(theta_i) -> E log cosh( sqrt(H) G ).
Remember this formula. Section 10 verifies that the general variational
formula reproduces it exactly, and that is one of the two honest checks
of the whole theory.
Now the hard part. Draw two independent configurations x, x' from the
weighted measure. Their overlap says how similar the good configurations
are. At small density the questions barely constrain anything, and
R(x,x') is almost always near 0. At large density the weighted measure
can freeze into clusters: samples inside a cluster agree nearly
completely, samples across clusters are nearly orthogonal. Then the
overlap is genuinely random, with two values of comparable probability.
A single number cannot describe that. The whole law of the overlap is
needed. Since in the limit that law lives on [0,1], it is described by
its nondecreasing inverse distribution function
q: (0,1) -> [0,1], mu([0,r]) = |{u : q(u) <= r}|,
where |.| is Lebesgue measure. Such a q is an overlap path, or overlap
quantile. The set of them is Q. Two degenerate examples:
q identically 0 all overlaps are 0 (no clustering)
q identically 1 all overlaps are 1 (one frozen cluster)
and everything between describes a tree of nested clusters.
4. The shape of the clusters: a tree, and one rule that captures it
-------------------------------------------------------------------
Three samples x^1, x^2, x^3 have three overlaps, and in the limit they
are almost surely ultrametric:
R_12 >= min( R_13, R_23 ).
Ultrametricity is exactly the statement that the samples sit at the
leaves of a tree: the similarity of two samples is the height of their
lowest common ancestor.
A finite version of such a tree is a Ruelle probability cascade. Fix
levels 0 = zeta_0 < zeta_1 < ... < zeta_k = 1. Build a tree by
splitting weight at each vertex among children whose weights are the
points of a Poisson process with intensity zeta x^{-1-zeta} dx at
depth zeta. A leaf gamma gets weight v_gamma, the product of the edge
weights along its path divided by the total. Two sampled leaves have
common level gamma^eta, the depth of their last common vertex, and
P( gamma^1 ^ gamma^2 = i ) = w_i := zeta_{i+1} - zeta_i .
One rule makes all of this usable. Suppose n samples have already landed
in a cluster of size m at level i. Then the next sample joins that
cluster with probability
(m - zeta_i) / n,
and otherwise it forms a fresh child at that vertex. In array form, for
a scalar array B of common levels and every n >= 2,
law( B_{1,n+1} | first n x n block of B )
= (1/n) law(B_12) + (1/n) sum_{l=2}^n delta(B_{1l}) .
This is the Ghirlanda-Guerra identity. All of the tree's combinatorics
is in that one line. It also explains why the final answer is a
finite-step recursion: the pattern field can be built one level at a
time, and each level only asks what happened at the levels below.
Two warnings, then the punchline.
* Ultrametricity and nonnegativity of overlaps are theorems, not
assumptions. That is BLACK BOX A, stated in Part V. The original
proves it from a duplication argument: a sampled block can always be
extended by a copy of an existing index, and copies turn a violated
triangle into a contradiction with positive semidefiniteness.
* Reweighting a cascade by a positive factor preserves the tree law
and tilts only the marks attached to vertices. That is BLACK BOX B.
It is used three separate times: to evaluate a fresh pattern, to
restore two deleted patterns, and to read off the cavity
magnetization.
5. The answer, in one sentence
------------------------------
The limiting pressure is the best trade-off between two explicit
quantities, minimized over the overlap path:
lim (1/N) log Z_N = min over q in Q of
{ alpha * (pattern reward of q)
+ (spin entropy of q) } .
Both bracketed terms are short Gaussian recursions, both are honest
averages of Gaussian variables, and the infimum is attained by the
actual overlap path of the system. That is the whole theorem.
6. Why it is worth the trouble
------------------------------
* It is universal. Every fixed density, every bounded activation, no
sign condition, no symmetry, no smallness. Earlier rigorous results
needed small density (Talagrand; Bolthausen-Nakajima-Sun-Xu), or
special activations, or hard constraints, i.e. rewards that are zero
or minus infinity.
* The infimum is a genuine variational formula and not merely an upper
bound from a clever guess. The lower half of the proof is what makes
it stick, and that half is where the new ideas are.
* The two halves use genuinely different mechanisms. The upper bound
enriches the model with a tree and forces it to confess its overlap
structure. The lower bound adds a few spins and reads the entropy off
coordinate symmetry. Neither is a corollary of the other.
============================================================
PART II. THE MODEL, THE TWO RECURSIONS, THE THEOREM
============================================================
7. Standing notation
--------------------
N number of spins, large.
alpha pattern density, fixed and positive.
M number of patterns, floor(alpha N).
x a configuration in {-1,+1}^N.
nu_N uniform probability on the cube, mass 2^{-N} each.
g^a the a-th pattern, standard Gaussian in R^N.
b_a(x) (1/sqrt N) g^a . x, standard Gaussian for fixed x.
f bounded Borel log-potential.
Z_N(f) sum_x 2^{-N} exp( sum_a f(b_a(x)) ).
p_N(f) (1/N) log Z_N(f), the pressure.
R(x,x') (1/N) x . x', the overlap, in [-1,1], multiples of 2/N.
G the Gibbs measure, weight/Z_N, a probability on the cube.
<...> expectation over independent samples (replicas) from G.
E expectation over the patterns and any other randomness.
G and G_1, G_2, ... are also used for standard Gaussian variables
where no conflict is possible; context always decides.
An overlap path is a nondecreasing function q: (0,1) -> [0,1], with
paths that agree almost everywhere identified. The set of overlap paths
is Q. A step path is constant on the intervals of a finite partition
0 = zeta_0 < zeta_1 < ... < zeta_k = 1,
w_i = zeta_{i+1} - zeta_i, q_i = value of q on (zeta_i, zeta_{i+1}).
A field path is a nonnegative nondecreasing step function h on the same
kind of partition, written (h_0, ..., h_{k-1}). Sums and integrals over
paths are always over Lebesgue measure on (0,1).
8. The operator that builds everything
--------------------------------------
8.1 Definition. For s >= 0, 0 <= d <= 1, and a suitable function U,
(T_{s,d} U)(x) = (1/d) log E exp( d U(x + sqrt(s) G) ), d > 0,
(T_{s,0} U)(x) = E U(x + sqrt(s) G).
Three facts, used constantly and never mentioned again:
(a) T is monotone: U <= W pointwise implies T U <= T W.
(b) If U takes values in [a,b], so does T_{s,d} U. (For d > 0 this is
monotonicity of (1/d) log followed by Jensen.)
(c) A zero-variance transform is the identity: T_{0,d} U = U.
Reading: add an independent Gaussian of variance s to the argument of U,
then take a soft maximum with stiffness d. As d -> 0 the soft maximum
becomes a plain average; d = 1 is the honest log-average. The parameter
d will always be one of the zeta_i, i.e. a depth in the tree, and s will
always be a variance increment along the tree. That is not an accident:
it is exactly where the tree meets the Gaussian field.
8.2 The pattern recursion. Take a step path q with partition zeta_i and
values q_i, and append q_{-1} = 0 and q_k = 1. Start at U_k = f and set
U_{i-1} = T_{q_i - q_{i-1}, zeta_i} U_i , i = k, k-1, ..., 0,
V_f(q) = U_{-1}(0).
This is the reward contributed by one fresh pattern, averaged, when the
pattern field is built along a tree whose overlap quantile is q. Read it
from the top:
level k: coefficient zeta_k = 1 and variance 1 - q_{k-1}: an honest
log-average over the part of the fresh pattern that is not
explained by the shared structure.
levels i = k-1 ... 1: coefficient zeta_i, variance q_i - q_{i-1}:
the field climbs one level, gains that much variance, and
is reweighted with stiffness zeta_i.
level 0: coefficient zeta_0 = 0, so the first transform is a plain
average over variance q_0 at the root.
Three values worth memorizing.
q = 0 (all q_i = 0): V_f(0) = log E exp( f(G) ).
q = 1 (all q_i = 1): V_f(1) = E f(G).
q = r constant: V_f(r) = E_G log E_{G'} exp f( sqrt(r) G
+ sqrt(1-r) G' ).
The first two follow because all the variance increments vanish except
the very first or the very last. The third is the one-level case.
Refining a partition without changing the values inserts a zero-variance
transform, so by 8.1(c) V_f does not depend on the partition. For smooth
compactly supported f, V_f is Lipschitz in the L^1 distance between
step paths, hence extends uniquely and continuously to all of Q. For
bounded Borel f the same holds with a constant depending on f; that is
section 18.
8.3 The field recursion. For a field path h on the same partition, with
h_{-1} = 0, set
U_{k-1}(x) = log cosh(x) - h_{k-1}/2 ,
U_{i-1} = T_{h_i - h_{i-1}, zeta_i} U_i , i = k-1, ..., 0,
ell(h) = U_{-1}(0).
Same climb, no patterns. The terminal value is the one-coordinate spin
sum log 2 cosh(x) minus the deterministic variance correction h_{k-1}/2,
and there is no final coefficient-one interval, because there are no
patterns left to average. One-level case:
ell(H) = E log cosh( sqrt(H) G ) - H/2 .
The -H/2 is not cosmetic. It is precisely the term that cancels the
diagonal of the hierarchical Gaussian field in every interpolation below,
and it is also what makes ell concave (Part IV, section 15).
8.4 The entropy. For q in Q,
S_I(q) = sup over field step paths h of
{ ell(h) + (1/2) int_0^1 h(u) q(u) du } .
Two readings, both worth having.
(i) Convex dual reading. ell is concave, so the supremum of ell(h) plus
a linear functional of h is the concave conjugate of ell: the
quantity that makes ell(h) + (1/2) int h q an upper bound for all
h at once. It is an entropy because it counts how many spin
configurations are compatible with the clustering pattern q.
(ii) Matching reading. For each h there is a derivative path rho_h,
defined in section 14.4, with 0 <= rho_h <= 1. Then
S_I(rho_h) = ell(h) + (1/2) int_0^1 h(u) rho_h(u) du ,
so the supremum is attained exactly when the trial path q equals
rho_h. In words: every field h names the overlap path it produces,
and S_I is the upper envelope of that family of explicit concave
functions of q.
Reading (ii) is the whole strategy of the lower bound: show that the
system's field h produces the system's own overlap path, and then the
supremum is attained and the inequality becomes an equality. Everything
else in the paper is bookkeeping, done honestly.
9. The main theorem
-------------------
THEOREM. For every alpha > 0 and every bounded Borel f: R -> R,
lim_{N -> inf} E p_N(f)
= P_f(alpha)
:= min over q in Q of { alpha V_f(q) + S_I(q) },
and p_N(f) converges to P_f(alpha) in probability. The value is
finite; indeed
-alpha ||f||_inf <= P_f(alpha) <= alpha log E exp( f(G) ).
There is no condition on the sign of f, no symmetry, no concavity, no
restriction on beta when f = beta phi, and no restriction on alpha.
9.1 Why the bounds hold. V_f in [ -||f||_inf, ||f||_inf ] by 8.1(b). Also
S_I >= 0 (take h = 0), S_I(0) = 0 (ell(0) = 0 and the linear term
vanishes), and S_I is nondecreasing in q. So taking q = 0 in the
variational problem gives at most alpha V_f(0) = alpha log E exp(f(G)),
and taking any q gives at least -alpha ||f||_inf. That pins the value.
9.2 Why convergence in probability follows. Changing one whole pattern
row changes log Z_N by at most 2 ||f||_inf, so it changes
p_N = (1/N) log Z_N by at most 2 ||f||_inf / N. The independent-input
variance bound (section 19, bound (V2)) then gives
Var(p_N) <= 4 M ||f||_inf^2 / N^2 = O(1/N),
and Chebyshev converts the expectation limit into convergence in
probability. The hard statement is the expectation limit; the variance
argument is a two-line afterthought. It is included because a free energy
that only converges on average is not a free energy.
9.3 Why it is an infimum and not a sup. The upper bound produces, for
each fixed trial q, the inequality limsup E p_N <= alpha V_f(q) +
S_I(q). Then minimizing over q is free. The lower bound has to produce
the reverse inequality for the true q, and cannot pick q in advance: it
must show that the system's own q, read off its own overlap
distribution, satisfies alpha V_f(q) + S_I(q) <= liminf E p_N. That is
strictly harder, and it is where the cavity computation and coordinate
exchangeability are spent.
10. Reading the formula
-----------------------
10.1 The three sentences. alpha V_f(q) is the average reward the patterns
pay when the pattern field climbs a tree with overlap quantile q.
S_I(q) is the entropy of the spins at that same q. The system gets to
choose its clustering and picks the one minimizing the sum. The infimum
is attained by the actual overlap path, not merely approached.
10.2 Why alpha multiplies only V_f. p_N is per spin. Each pattern is one
constraint and costs entropy of order one, and there are alpha N of them.
So the pattern term is extensive with density alpha, while the spin
entropy term is intrinsic to the spin cube and carries no alpha.
10.3 Check one: f constant. If f = c then U_i = c plus constants, and
V_f(q) = c for every q. Since S_I >= 0 and S_I(0) = 0, the infimum is
alpha c, exactly as the direct computation gives.
10.4 Check two: f linear, done completely. Let f(s) = t s with t real.
The point is that affine functions survive T exactly. If U(x) = c + a x
and d > 0, then
T_{s,d} U(x) = c + a x + d a^2 s / 2,
because (1/d) log E exp( d a (x + sqrt(s) G) ) = a x + d a^2 s / 2. The
slope a is unchanged, and only the constant grows. When d = 0 the same
formula holds with the growth term absent, which is consistent with
putting d = zeta_i.
So in the pattern recursion the slope stays t and the constants
accumulate d a^2 s / 2 = zeta_i t^2 (q_i - q_{i-1}) / 2 at each level.
Summing with q_{-1} = 0 and q_k = 1 and summation by parts,
sum_{i=0}^{k} zeta_i (q_i - q_{i-1})
= zeta_k q_k - sum_{i=0}^{k-1} (zeta_{i+1} - zeta_i) q_i
= 1 - int_0^1 q(u) du ,
hence
V_f(q) = (t^2 / 2) ( 1 - int_0^1 q(u) du ).
Put H = alpha t^2. The objective becomes
alpha V_f(q) + S_I(q) = H/2 - (H/2) int q + S_I(q).
Now test the constant field h = H inside S_I:
S_I(q) >= ell(H) + (H/2) int q ,
so every objective is at least H/2 + ell(H). That lower bound is
independent of q, which is the first sign that the answer is exactly
H/2 + ell(H). For the matching upper bound, take the constant path
q_* = E tanh^2( sqrt(H) G ) .
For the constant field h = H the derivative path rho_h is computed in one
step: the chain has a single level with coefficient zeta_0 = 0, so its
only randomness is a Gaussian of variance H, and
rho_H = E [ U_0'(Z_0)^2 ] = E tanh^2( sqrt(H) G ) = q_* .
By reading (ii) of 8.4, the supremum defining S_I(q_*) is attained at
h = H, and therefore
S_I(q_*) = ell(H) + (H/2) q_* = ell(H) + (H/2) int q_* .
Substituting into the objective, the two int q_* terms cancel:
alpha V_f(q_*) + S_I(q_*)
= H/2 - (H/2) q_* + ell(H) + (H/2) q_*
= H/2 + ell(H) = E log cosh( sqrt(H) G ) .
Compare section 3: the same number, obtained there by the law of large
numbers and here by the variational formula. This is a real check. Every
step of it is elementary and every constant matters: H = alpha t^2, the
field trial is h = H (not H/2), and the -H/2 inside ell is what makes the
endgame cancel.
10.5 What the theorem does not say.
* It does not take beta to infinity. For fixed beta the formula
applies. A hard constraint is a reward of 0 or -infinity, i.e. a
limit beta -> infinity, and exchanging that limit with N -> infinity
needs extra work. The paper says so, and points at the hard-constraint
literature (Ding-Sun, Huang, Nakajima-Sun, Perkins-Xu, Abbe-Li-Sly)
for what is known in that regime.
* It does not identify the overlap path for a specific system beyond
saying that it minimizes the functional. In the linear case the
minimizer is the constant q_* above, and the system really is
replica symmetric. In general the minimizer can be a genuine
multi-level path, and then the weighted measure really does have a
nontrivial tree of clusters.
* It does not claim a limit for every realization of the patterns at
once. It gives the expectation, and then separately probability
concentration via the variance estimate of 9.2.
============================================================
PART III. THE PROOF AT A GLANCE
============================================================
11. The shape of the proof
--------------------------
First assume f is smooth and compactly supported. That is not a
technicality: it lets every derivative below be taken and bounded, and
it pins down the two inequalities. Sections 21 and 22 remove smoothness
afterwards, and they do it with estimates that are uniform in N and in
the overlap path, which is why the removal costs nothing structurally.
The two halves are:
UPPER. For every fixed trial path q in Q,
limsup E p_N <= alpha V_f(q) + S_I(q).
Minimizing over q is then free.
LOWER. liminf E p_N >= min over q of { alpha V_f(q) + S_I(q) }.
The lower half cannot choose q in advance. It has to find the system's own
overlap path p and its own field h, and show that the pair (p,h) achieves
the minimum, i.e. that alpha V_f(p) + S_I(p) bounds liminf from below.
This asymmetry is the reason the paper is long.
The six stages, in order:
1. Variations. Derivatives of V_f and ell in the path, Lipschitz
bounds, a tail-order monotonicity, and concavity
of ell with an explicit supporting inequality.
(Part IV, sections 15 and 16.)
2. Upper bound. Enrich, penalize, concentrate, extract overlap
identities, synchronize, contradict.
(Section 12 below, details in Part IV,
section 17.)
3. Restored marks. Delete two patterns, restore them as Gaussian
marks, identify the empirical gradient covariance
B_N as a deterministic function of the overlap.
(Section 13, details in Part IV, section 18.)
4. Cavity. Add L spins, Taylor expand, reduce the increment
to one explicit exponential tilting, evaluate it.
(Section 13, details in Part IV, section 19.)
5. Exchangeability. Coordinate symmetry identifies the cavity
magnetization with the bulk overlap, which is
exactly the statement that the entropy sup is
attained. (Section 13, details in section 19.)
6. Telescoping. Sum increments over residue classes, divide by N,
let L go to infinity, remove the perturbation.
(Section 13.)
Stage 1 is where the two functionals earn their keep, and stages 3-5 are
where the perceptron differs from a Gaussian spin glass. Nothing in
stages 2 and 6 depends on f being an activation rather than an abstract
energy, but stages 3-5 use the pattern structure three separate times.
12. The upper bound: making the model confess its overlap structure
-------------------------------------------------------------------
12.1 The strategy in one paragraph. Suppose the claimed bound failed for
some trial path q, by an amount eta > 0. Add small extra ingredients to
the model that cost almost nothing in pressure but make its own
parameters stationary: a tree label, a hierarchical Gaussian field, a
Poissonized pattern count, and a vanishing perturbation with a small
quadratic price on its coefficients. At the resulting minimizer, the
model is forced to obey overlap identities (because the coefficients
cannot move without losing pressure), those identities order the spin
overlaps against the tree overlaps (because both arrays are ultrametric
and cannot cross), the ordering turns the assumed excess into a clean
statement about V_f, and the derivative in the pattern density then has
the wrong sign. Contradiction.
12.2 The enriched model, in words. Four additions, each with a job.
(a) A tree label. The Gibbs measure lives on pairs (x, gamma) where
gamma is a leaf of the finite cascade with levels zeta_i, the same
levels as the trial path q. Leaf weights are v_gamma. The job of
gamma is to carry the trial overlap structure so the model can be
compared against it level by level.
(b) A hierarchical field. Add the energy z(gamma) . x - (N/2) h_{k-1},
where the N coordinates of z are independent centered Gaussian
fields on the tree with covariance h_{gamma^eta}. So two spins
sitting at leaves that share a deep ancestor feel strongly
correlated fields, and the strength of that correlation is the
trial field path h. The deterministic -(N/2) h_{k-1} is the
diagonal correction, exactly the -h_{k-1}/2 of the field recursion
multiplied by N.
(c) Poisson patterns. Replace floor(alpha N) patterns by a Poisson
number K of mean N t, 0 <= t <= alpha. The point is that the
derivative in t is then explicit: adding one pattern on average,
d/dt F_N(t) = -E log < exp f( ghat . x / sqrt N ) >,
with ghat a fresh standard Gaussian pattern and F_N = -E P_N the
negated pressure. At t = 0 with no perturbation, the spin sum at a
leaf factors and gives exactly ell(h). That is the initial value
that ties the enriched model to the field recursion.
(d) A perturbation with a price. Enumerate the monomials
kappa_j(R,T) = R^p T^d with p + d >= 1, take independent centered
Gaussian fields Y_j with those covariances, and add
sqrt(N) e_N sum_j 2^{-j} u_j Y_j , e_N = N^{-1/16}.
Switching it on costs O(e_N^2) in expected pressure, which is
nothing; but at the energy scale a single coefficient is
N^{7/16}, which is large. The coefficients u_j are then priced by
sum_j 2^{-j} (u_j - 3/2)^2, a strictly convex penalty with a
minimum at u_j = 3/2.
12.3 Why the price is the whole trick. At a minimizer of
J_N(t,h,u) = F_N(t,h,u) - (1/2) sum_i w_i q_i h_i + S_I(q)
+ t { V_f(q) + delta } + sum_j 2^{-j} (u_j - 3/2)^2 ,
the coefficient u_j is interior (the penalty pins it), so the first
derivative of the pressure in u_j must balance the penalty slope, and the
second derivative must be dominated by the penalty curvature. Those two
statements are a fluctuation estimate:
E< |Y_j - E<Y_j>| > = o( sqrt(N) e_N ) = o( N^{7/16} ),
for each fixed j, where the outer average is over the patterns and the
inner one over the reweighted tree. Two ingredients produce it. The
second-derivative statement gives the thermal fluctuation of Y_j, i.e.
its variation over samples at fixed disorder, bounded by
C_j e_N^{-1}. The first-derivative statement, combined with convexity of
the pressure in u_j and with the O(1/N) concentration of the pressure,
gives the disorder fluctuation of <Y_j>, through the comparison of one
sided difference quotients with their expectations. Neither estimate
uses any structure of the model beyond convexity and concentration. This
is the contact-point mechanism, BLACK BOX C.
Feasibility of the minimum rests on an explicit growth estimate. Since
log cosh x <= |x| one shows
ell(h) <= (E|G|) sqrt(h_0) + C_zeta - (1/2) sum_i w_i h_i ,
so raising the top field value H raises J_N linearly, and for large fixed
H the minimizer cannot sit at h_{k-1} = H. On the other side, testing
t = alpha, h = 0, u = 3/2 gives J_N <= -eta/2, so the minimizer cannot sit
at t = 0 either, nor can it sit at u_j = 3/2 for fixed j. Everything that
needs differentiating is interior. Note where q_{k-1} < 1 is used: it
makes the linear coefficient w_{k-1}(1 - q_{k-1})/2 strictly positive.
That is exactly why section 16 proves the variational infimum can be
taken over such paths.
12.4 From the fluctuation estimate to the overlap identities. Gaussian
integration by parts in Y_j, plus the o(N^{7/16}) estimate, gives, for
every bounded continuous D of the first n x n block of (R,T),
E< D kappa_j(R_{1,n+1}, T_{1,n+1}) >
= (1/n) E<D> E<kappa_j(R_12,T_12)>
+ (1/n) sum_{l=2}^n E< D kappa_j(R_{1l},T_{1l}) > + o(1).
Polynomial approximation and the fact that continuous tests determine
finite measures upgrade this to the full Ghirlanda-Guerra identity for
the joint array (R,T). That is the model confessing its structure.
12.5 Synchronization. Now BLACK BOX A applies to R, to T, and to R + T:
all three are bounded symmetric exchangeable Gram arrays with constant
diagonal, all three obey the identities. So all three are ultrametric and
nonnegative. If the two-replica support of (R_12, T_12) contained two
strictly crossed points, one could force, on a positive-probability
event, R_23 = R_12 and T_23 = T_13, making R_23 + T_23 strictly smaller
than both R_12 + T_12 and R_13 + T_13, which ultrametricity of R + T
forbids. Hence the support is ordered in both coordinates, and the
conditional law of R_12 given T_12 = i/k is the law of p(U) for U uniform
on (zeta_i, zeta_{i+1}), where p is the quantile of the spin overlap.
In words: the trial tree and the real clusters line up, block by block.
12.6 The two contradictions. Minimality in h, together with the explicit
field derivative of F_N, gives, for every nonnegative nondecreasing
direction lambda on the trial partition,
int_0^1 p lambda >= int_0^1 q lambda .
Taking lambda = 1{u > s} for each s and using that the tail integral of p
is concave, the inequality holds for every s. By the tail-order
proposition (section 16), V_f(p) <= V_f(q). Minimality in t gives
d/dt J_N at the minimizer = -V_f(p) + V_f(q) + delta + o(1) ,
which the limit evaluates to something >= delta > 0, contradicting
first-order minimality. Done: the upper bound holds for every trial q.
13. The lower bound: adding spins and reading entropy off symmetry
------------------------------------------------------------------
13.1 What has to be produced. The system's own overlap path p, the
system's own field h, and the identity
S_I(p) = ell(h) + (1/2) int_0^1 p h ,
which is what turns the supporting inequality into attainment. Then the
increment computation below delivers exactly alpha V_f(p) + S_I(p) and
the telescope finishes.
13.2 Making the overlap structure rigid. Add a tiny perturbation to the
energy: for a deterministic parameter vector v in [1,2]^N and fields Y_j
of covariance R^j,
H^v_N(x) = s_N sum_j 2^{-j} v_j Y_j(x), s_N = N^{3/8} .
Its covariance is s_N^2 xi^v_N(R) with xi^v_N(r) = sum_j 4^{-j} v_j^2 r^j,
bounded uniformly in v and r, so the expected pressure changes by at most
C s_N^2 = C N^{3/4} = o(N). The point of the perturbation is that one can
differentiate in v_j and learn that the Gibbs average of Y_j is nearly
constant, which is what forces the overlap identities to hold for the
"omitted" system at hand. The set of parameters where this works,
G_N = { v : sum_{j<=J_N} a_{j,N}(v) <= delta_N } ,
has pi-measure tending to one, with a_{j,N} the scaled mean absolute
deviation of Y_j and delta_N -> 0 slowly. So for a typical v the overlap
structure is rigid: the Ghirlanda-Guerra identities hold, hence BLACK BOX
A applies, hence the covariances below are forced.
13.3 Deleting and restoring two patterns. Delete the last two patterns.
In the omitted system the overlap array satisfies the identities. Now
restore them, one at a time, as independent fresh Gaussian fields with
covariance R and unit diagonal. Restoring is a bounded reweighting, so it
does not change the limiting overlap law; it only tilts the marks. The
observables that matter are the empirical gradient covariance and the
dilation correction,
B_N(x,x') = (1/N) sum_a f'(b_a(x)) f'(b_a(x')) ,
C_N(x) = (1/N) sum_a ( f''(b_a(x)) - b_a(x) f'(b_a(x)) ) .
Two patterns, not one, because one restored pattern gives the conditional
mean of f' and hence the first moment of B_N, while two independent
restored patterns give the conditional mean of the product and hence the
second moment. First plus second moment kills the variance, and B_N
becomes deterministic given the overlap:
B_N(x,x') -> a(R(x,x')) for x != x', B_N(x,x) -> a_d, C_N -> c,
with a deterministic nondecreasing a, 0 <= a <= a_d <= alpha ||f'||_inf^2,
and one identity linking the constants to the path:
c + a_d = int_0^1 r a(r) mu(dr) .
That identity is Gaussian integration by parts in a single pattern row,
summed over rows; it is exact at finite N.
The reason a is nondecreasing and lives on the tree: BLACK BOX B says the
restored marks are conditionally independent below their common level,
so the conditional mean of the product given common level i is the square
of the conditional mean at level i, and those squares grow with i because
they form a martingale. A nondecreasing function of a tree level is a
nondecreasing function of the overlap. This is the one place where the
"independent residual on every visit, even two visits to the same leaf"
rule matters: if a leaf had one permanent residual, two visits to it
would have covariance a_d instead of the correct shared value, and the
whole identification would be wrong.
13.4 The cavity step. Add L spins (L fixed, then L -> infinity at the
very end). Write a spin in dimension N+L as (x,z) and a pattern as
(g^a, y_a). Expanding f at the rescaled argument sqrt(N/(N+L)) b_a(x) and
shifting by the L new coordinates (y_a . z)/sqrt(N+L) through second
order, the energy becomes, up to a remainder whose supremum has expected
size o(1),
sum_a f(b_a(x)) + H^v_N(x) + log W(x,z) + Q(x,z) ,
with
W(x,z) = exp( z . Y(x) + (L/2) C_N(x) + sum_{a=M+1}^{M+d} f(b_a(x)) ),
Y(x) = N^{-1/2} sum_{a<=M} f'(b_a(x)) y_a ,
Q(x,z) = (1/(2N)) sum_{a<=M} f''(b_a(x)) ( (y_a.z)^2 - L ).
So the L new spins see a Gaussian linear field whose covariance is exactly
B_N, plus the deterministic (L/2) C_N, plus d fresh patterns, plus a
quadratic correction Q. The correction is removable because z . Y(x) and
Q(x,z) have Gaussian exponential moments uniformly in x, z, so Q can be
discarded at a cost O(L N^{-1/2}) in the normalized measures. And W is
bounded away from zero: since the cavity prior is a product of symmetric
signs, G_0(W) >= exp(-C_L) for a constant depending only on L. That lower
bound is what makes every normalization safe.
13.5 Evaluating the tilt. Use BLACK BOX B on the tree. Each visit to a
leaf contributes its own residual of variance a_d - h_top, so the L
coordinates contribute L independent log cosh factors plus a constant;
the d fresh patterns contribute d copies of V_f; the deterministic bulk
term contributes L c/2. With c + a_d = int r a dmu = int p h, the whole
increment is
Delta_{N,L} = L ( ell(h) + (1/2) int_0^1 p h ) + d V_f(p) + o(1) ,
where d = M_{N+L} - M_N = alpha L + O(1). Note how the L log cosh factors
are exactly ell, and how the diagonal pieces assemble into int p h. That
is the payoff for carrying the -h/2 subtraction from the beginning.
13.6 Exchangeability closes the loop. The (N+L)-spin model is invariant
under permuting coordinates, so replacing one distinguished coordinate by
all others and averaging gives, for any bounded continuous D_0,
E< D_0(R^+_12) z_1^1 z_1^2 >_{N+L}
= E< D_0(R^+_12) R^+_12 >_{N+L} ,
because the average of z_i^1 z_i^2 over i is the overlap. On the other
hand, under the cavity tilt, the conditional mean of z_1^1 z_1^2 given
the pair's common level i is exactly the derivative path value
(rho_h)_i. Comparing the two descriptions and passing to the limit gives
rho_h = p. So the field h produces the overlap path p, the entropy
supremum is attained, and
S_I(p) = ell(h) + (1/2) int_0^1 p h .
13.7 Telescoping. Combining 13.5 and 13.6,
lim Delta_{N,L} = L { S_I(p) + alpha V_f(p) } + (d - alpha L) V_f(p) ,
and since |d - alpha L| <= 1 and |V_f| <= ||f||_inf,
liminf inf_{v in G_N} Delta_{N,L}(v) >= L P_f(alpha) - ||f||_inf .
The uniform lower bound of the cavity comparison controls the complement
of G_N, and the parameter integral over the same product measure in both
dimensions is exactly F_{N+L} - F_N. Hence
liminf (F_{N+L} - F_N) >= L P_f(alpha) - ||f||_inf .
Telescope separately in the L residue classes modulo L, divide by N, let
the floor error go to zero, then let L -> infinity, then remove the
perturbation using F_N/N - E p_N = O(N^{-1/4}). That is the lower bound.
14. The whole proof in ten lines
--------------------------------
1. Derivative formulas in the path (sections 15, 16).
2. Tail order: spreading overlaps upward cannot raise V_f.
3. Concavity of ell, so ell(h) + (1/2) int h q is a supporting plane.
4. Enrich with a tree and a priced perturbation; add a Poisson count.
5. Concentration and convexity give fluctuation control at the
deterministic minimizer; hence the overlap identities.
6. Synchronization: the trial tree cannot cross the real clusters.
7. Two contradictions at the minimizer: in h and in t. Upper bound.
8. Delete two patterns, restore them twice, identify B_N = a of R and
the constant identity c + a_d = int r a dmu.
9. Add L spins; the increment is one explicit tilt; evaluate it on the
tree; get L(ell(h) + (1/2) int p h) + d V_f.
10. Coordinate exchangeability gives rho_h = p, hence S_I(p) is
attained; telescope in L; remove the perturbation.
Nothing else is used. Part IV fills in the technical content of steps 1,
3, 5, 8 and 9.
============================================================
PART IV. THE ENGINE ROOM
============================================================
15. First variations
--------------------
15.1 The tilted kernel. In either recursion the increments are s_i and the
coefficients are zeta_i. Define, for a Gaussian law N(x,s) of mean x and
variance s,
K_i(x,dy) = exp( zeta_i ( U_i(y) - U_{i-1}(x) ) ) N(x, s_i)(dy) .
This is a probability kernel, and the reason is the definition of T: the
normalizing identity exp(zeta_i U_{i-1}(x)) = E exp(zeta_i U_i(x +
sqrt(s_i) G)) is exactly the statement that K_i(x, .) has total mass one.
When zeta_i = 0 the exponential is one and K_i is plain Gaussian
convolution; when s_i = 0 it is the point mass at x.
It defines a Markov chain: start at Z_{-1} = 0 and sample Z_i from
K_i(Z_{i-1}, .). Every expectation below is along that chain.
15.2 Three identities. Write W = T_{s,d}U and let K be the kernel above.
(a) Spatial derivatives propagate: W'(x) = K U'(x).
(b) A perturbation of the terminal function propagates the same way:
(d/d eps) T_{s,d}(U + eps A) at eps = 0 equals K A.
(c) Heat equation: dW/ds = (1/2) { W'' + d (W')^2 }
= (1/2) K { U'' + d (U')^2 } .
Identity (c) is the standard one: with d = 1 write f_s = E exp(U(x +
sqrt s G)) so that W = log f_s and f_s satisfies the heat equation; then
W_s = (1/2)(f_{s,xx}/f_s) = (1/2)(W_{xx} + W_x^2). For general d apply
the same computation to e^{dW} = E exp(dU(x + sqrt s G)).
Consequence, used without comment from here on: m_i := U_i'(Z_i) is a
martingale along the chain, because K_i U_i' = U_{i-1}' by (a). Hence
E[U_i'(Z_i)^2] is nondecreasing in i, by the conditional Jensen inequality
applied to the martingale.
15.3 Lemma (first variations). On a fixed partition, with
w_i = zeta_{i+1} - zeta_i,
d/da V_f(q + a qdot) = -(1/2) sum_{i=0}^{k-1} w_i qdot_i
E[ U_i'(Z_i)^2 ] ,
d/da ell(h + a hdot) = -(1/2) sum_{i=0}^{k-1} w_i hdot_i
E[ U_i'(Z_i)^2 ] ,
with all functions and chains computed at the current path. Endpoint
derivatives are understood from within the feasible segment.
Derivation, pattern case. Moving q_i upward lengthens the transition that
ends at level i and shortens the transition that leaves level i, with the
same spatial function U_i at level i. By (c) the incoming derivative,
expressed at level i before propagation through the preceding kernels, is
(1/2){U_i'' + zeta_i (U_i')^2}, and the outgoing derivative is
-(1/2){U_i'' + zeta_{i+1}(U_i')^2}. Their sum is -(1/2)(zeta_{i+1} -
zeta_i)(U_i')^2 = -(1/2) w_i (U_i')^2. Identity (b) carries this back to
the root, and counting how many of the levels are at or below i gives
E[U_i'(Z_i)^2]. Summing over i gives the displayed formula. The field
case is identical except at the last level, where the terminal value
log cosh x - h_{k-1}/2 contributes the extra -1/2, and the identity
(1/2){ (log cosh)'' + zeta_{k-1} ((log cosh)')^2 - 1 }
= -(1 - zeta_{k-1}) (1/2) tanh^2
supplies the same formula with w_{k-1} = 1 - zeta_{k-1}.
Degenerate increments are legitimate: a Gaussian transform of a bounded
function has bounded derivatives of all orders, so every term above is
uniformly integrable on a compact parameter set, and both sides depend
continuously on the increments as they shrink to zero.
15.4 The derivative path. For the field recursion define
rho_h(u) = E[ U_i'(Z_i)^2 ] for u in (zeta_i, zeta_{i+1}) .
Then rho_h is a nondecreasing function with values in [0,1]: the value 1
is the terminal bound |tanh| <= 1, and monotonicity in i is the martingale
statement of 15.2. Subdividing an interval inserts a zero-variance
transition, which repeats the same derivative and the same chain value, so
subdivision does not change rho_h. Therefore rho_h is itself an admissible
overlap path: the overlap quantile that the field h produces.
16. Lipschitz bounds, tail order, and reduction to finite trials
----------------------------------------------------------------
16.1 Lipschitz. Integrate 15.3 along the segment joining two paths and use
the terminal derivative bounds |f'| <= ||f'||_inf and |tanh| <= 1:
|V_f(p) - V_f(q)| <= (1/2) ||f'||_inf^2 ||p - q||_1 ,
|ell(h') - ell(h)| <= (1/2) ||h' - h||_1 .
Consequently V_f extends uniquely and continuously from step paths to all
of Q, and ell extends to all bounded nonnegative nondecreasing fields.
Everything the theorem says about a general q is read off this extension.
16.2 Tail order. If two paths satisfy
int_s^1 p(u) du >= int_s^1 q(u) du for every s in [0,1] ,
then V_f(p) <= V_f(q).
Proof on a common partition. Put a_i = w_i (p_i - q_i) and
A_j = sum_{i>=j} a_i, so the hypothesis says A_j >= 0 for every j. For any
nonnegative nondecreasing sequence c_i, summation by parts gives
sum_i a_i c_i = c_0 A_0 + sum_{j>=1} (c_j - c_{j-1}) A_j >= 0 .
Take c_i = E[U_i'(Z_i)^2] at each point of the segment from q to p, which
is nonnegative and nondecreasing by 15.4. The derivative of V_f along the
segment is -(1/2) sum_i a_i c_i <= 0, so V_f decreases along the segment
and V_f(p) <= V_f(q). For general paths average both on finer and finer
uniform partitions, apply the step result, and use 16.1 to pass to the
limit.
Why this is the right statement. The hypothesis says p sits above q in the
sense of tail mass, i.e. p is more spread upward. Spreading overlaps
upward cannot increase the reward: it means the good configurations are
less alike, so the patterns are being answered by a less concentrated
crowd of configurations. This is the monotonicity that the upper bound
uses in 12.6.
16.3 Corollary (finiteness and finite trials).
S_I >= 0, S_I(0) = 0, S_I nondecreasing in q,
|V_f| <= ||f||_inf, V_f(0) = log E exp(f(G)),
the variational infimum is finite, and it is unchanged if one minimizes
only over step paths with top value q_{k-1} < 1.
Proof. h = 0 is a trial, giving S_I >= 0. Also ell(0) = 0 (the terminal
log cosh averages to 0 at 0), and integrating the field variation along
a -> a h gives ell(h) <= 0 for nonnegative h. Monotonicity in q is
immediate from the formula, since h >= 0. V_f(0) is 8.2. Bounds on V_f and
S_I >= 0 give -alpha ||f||_inf <= inf <= alpha V_f(0).
For the reduction, take any q and let q_m be (1 - 1/m) times the essential
infimum of q on each interval of the uniform m-partition. Then
0 <= q_m <= q almost everywhere, sup q_m <= 1 - 1/m, and q_m -> q in L^1.
So S_I(q_m) <= S_I(q) by monotonicity and V_f(q_m) -> V_f(q) by 16.1, and
the infimum over the restricted class is no larger than the general one.
The other inequality is trivial since the class is smaller.
17. Concentration, convexity, and the contact point
---------------------------------------------------
17.1 Concentration of the enriched pressure. For each fixed field cap
H < infinity there is C_H with
Var( P_N(t,h,u) ) <= C_H / N
whenever 0 <= t <= alpha, 0 <= h_0 <= ... <= h_{k-1} <= H and u in
[1,2]^N.
Proof, in four moves.
(i) Put the patterns, the Poisson count and the common root Gaussian
variables into the root data. Apply the marked cascade transformation
(BLACK BOX B) to the spin log integral at each leaf. It gives
E[ L_N | root ] = X_0 , E[ (L_N - X_0)^2 | root ] <= C_zeta ,
where L_N = N P_N and X_0 is the recursion value at the root: the
difference L_N - X_0 is the log ratio of a tilted and an untilted
cascade total, and those totals have the same conditional law.
(ii) The coefficient vector of the common Gaussian variables in the
energy has norm at most C_H sqrt(N), since the common variances sum
to at most N H plus the perturbation. The log integral is 1-Lipschitz
in those variables (a difference of log integrals is at most the
supremum of the difference of energies), and every log-transform in
the recursion preserves a uniform change bound. So X_0 has Gaussian
variance at most C_H N by the Lipschitz variance bound (V1).
(iii) Replacing one pattern changes X_0 by at most 2 ||f||_inf, because
the bound holds at every leaf and is preserved by each transform.
With K independent patterns, the independent-input bound (V2) adds
at most C K.
(iv) The conditional mean E[X_0 | K = m] changes by at most ||f||_inf
between m and m+1. Comparing with an independent Poisson copy K' and
using (V2) for integer-valued functions bounds the variance of that
mean by ||f||_inf^2 N t.
Total: Var(L_N) = O_H(N), and division by N^2 gives C_H/N.
17.2 Coercivity of the field cap. From log cosh x <= |x| and
|x + y| <= |x| + |y|,
T_{s,d}(|.| + c)(x) <= |x| + c + d s / 2 + (log 2)/d for d > 0,
because e^{d|x + sqrt(s)G|} <= e^{d|x|}(e^{d sqrt(s) G} +
e^{-d sqrt(s) G}) and the expectation of the bracket is 2 e^{d^2 s/2}.
Propagating this bound from the top of the field recursion down to level 0
and then averaging |sqrt(h_0) G| at the root gives
ell(h) <= (E|G|) sqrt(h_0) + C_zeta - (1/2) sum_i w_i h_i ,
C_zeta = sum_{i=1}^{k-1} (log 2)/zeta_i ,
where the variance bookkeeping uses
-(1/2) h_{k-1} + (1/2) sum_{i=1}^{k-1} zeta_i (h_i - h_{i-1})
= -(1/2) sum_{i=0}^{k-1} w_i h_i .
Consequently, on the face h_{k-1} = H, the objective J_N of 12.3 is at
least
w_{k-1}(1 - q_{k-1}) H / 2 - (E|G|) sqrt(H) - C_zeta
- 2 alpha ||f||_inf - O(e_N^2) ,
whose leading coefficient is strictly positive because q_{k-1} < 1. This
is where 16.3 is used. Choose H so that this bound is positive for all
large N in the violating sequence, and note that J_N at t = 0 is at least
-O(e_N^2) by the entropy definition, while J_N at t = alpha, h = 0,
u = 3/2 is at most -eta/2. Hence a minimizer exists with t_N > 0,
h_{N,k-1} < H, and (comparing with all other u_j = 3/2) each fixed u_{N,j}
strictly inside (1,2) with penalty sum_j 2^{-j}(u_{N,j} - 3/2)^2 = O(e_N^2).
17.3 Two fluctuation estimates. Fix j and hold all other coordinates at
the minimizer. Write g(v) = E P_N(... , v , ...) and a_{N,j} = sqrt(N)
e_N 2^{-j}.
(i) Convexity and thermal fluctuation. P_N is convex in u_j, because it
is a log-integral of an energy affine in v. Ordinary Gibbs
differentiation gives
d P_N / d u_j = (e_N 2^{-j} / sqrt(N)) < Y_j > ,
g''(u_{N,j}) = e_N^2 4^{-j} E< (Y_j - <Y_j>)^2 > .
Interior minimality of J_N gives g''(u_{N,j}) <= 2 . 2^{-j}, so
E< |Y_j - <Y_j>| > <= C_j e_N^{-1} .
(ii) Convexity and disorder fluctuation. For a differentiable convex
random function its derivative at a point lies between the backward
and forward difference quotients. Apply this to P_N with step s and
subtract the mean derivative. Minimality of J_N in the interval
gives, after the linear terms cancel,
0 <= g(u_{N,j} + s) - g(u_{N,j}) - s g'(u_{N,j}) <= 2^{-j} s^2 ,
and each random function value may be replaced by its mean at a cost
of at most C_H/(s sqrt(N)) in L^1, by 17.1. With s = N^{-1/4}, which
is allowed by the penalty bound, this gives
E | dP_N/du_j - g'(u_{N,j}) | <= C_j N^{-1/4} = o(e_N^2) .
Multiplying by sqrt(N)/(e_N 2^{-j}) and adding (i),
E< | Y_j - E<Y_j> | > = o( sqrt(N) e_N ) = o( N^{7/16} ) .
The two contributions are O_j(N^{1/16}) from (i) and O_j(N^{5/16})
from (ii), against the scale N^{7/16}. Every statement concerns one
fixed j at a time; there is no uniformity in j.
17.4 The array identity. Gaussian integration by parts in Y_j, for a
bounded continuous D of the first n x n joint block of (R,T), reads
E< Y_j(1) D > = a_{N,j} u_{N,j} E< D ( sum_{l=1}^n kappa_j(R_{1l},T_{1l})
- n kappa_j(R_{1,n+1},T_{1,n+1}) ) > .
Its one-replica form identifies E<Y_j> as the same coefficient times
kappa_j(1,(k-1)/k) - E<kappa_j(R_12,T_12)>. Substituting, and using the
o(N^{7/16}) estimate to replace <Y_j> by its mean, then cancelling the
constant diagonal and dividing by n a_{N,j} u_{N,j}, gives
E< D kappa_j(R_{1,n+1},T_{1,n+1}) >
= (1/n) E<D> E<kappa_j(R_12,T_12)>
+ (1/n) sum_{l=2}^n E< D kappa_j(R_{1l},T_{1l}) > + o(1) .
Linearity and uniform polynomial approximation on the compact range of
(R,T) give the identity for every continuous function of a pair, and
continuous tests of a finite block determine its measure, so the full
conditional-law form of the Ghirlanda-Guerra identity follows. That is
BLACK BOX A's hypothesis, verified for the joint array.
17.5 The derivative in time. Poisson differentiation gives
dF_N/dt = -E log < exp f( ghat . x / sqrt N ) > ,
where ghat is a fresh independent standard Gaussian pattern, and the
bound ||f||_inf makes the differentiation legitimate. The lemma of
section 20 evaluates the limit of that expression as V_f(p), where p is
the quantile of the limiting spin overlap. That is the last ingredient
of 12.6.
18. Restored marks: the marked cascade computations
---------------------------------------------------
18.1 The transformation, stated in the form actually used. Take a finite
cascade with levels zeta_i, leaf weights v_gamma, and marks drawn on
vertices from probability kernels that may depend on the marked ancestor
path and its depth but never on numerical child indices. Let X_{k-1} be a
terminal log factor depending on the marked path. For i >= 1 let E_i
integrate the level-i child-mark kernel conditional on the marked path
through level i-1, without averaging weights or root data, and set
X_{i-1} = (1/zeta_i) log E_i exp( zeta_i X_i ) , i = k-1, ..., 1 .
Then, for Z = sum_gamma v_gamma exp( X_{k-1}(gamma) ),
E[ log Z | root data ] = X_0 ,
E[ (log Z - X_0)^2 | root data ] <= 4 E[ (log T)^2 ] ,
with T the unmarked total. And, after reweighting by exp(X_{k-1}) and
relabeling children, the joint law of weights and marks is generated by:
draw an ordinary unmarked cascade, independently of the root data, and
draw marks with kernels of density exp( zeta_i (X_i - X_{i-1}) ) relative
to the original ones, independently on distinct children given ancestor
marks. Root data keep their original law.
Three consequences, each used somewhere:
(a) Sampling reweighted leaves preserves the shape law. Conditioning on
a sampled shape therefore leaves exactly those tilted mark kernels
along the sampled branches. The tree geometry is untouched by
reweighting.
(b) If the original mark kernels factor over independent components and
the terminal log factor is a sum of the separate component log
factors, then the transforms add and the tilted component kernels
factor. This is what keeps the L cavity coordinates and the d fresh
patterns independent of each other.
(c) The root keeps its own law and gets no extra tilt.
Proof sketch. Multiply each edge point at level i by exp(X_i - X_{i-1})
and reorder children. By the recursion, the conditional zeta_i-th moment
of that multiplier is one, so the Poisson intensity is unchanged, and the
marked Poisson mapping calculation tilts the attached mark kernel exactly
by the displayed density. Doing this from the last level upward preserves
the conditional law of each transformed subtree, which is what gives
independence. Products of edge multipliers telescope, and the raw total
ratio Z = e^{X_0} T*/T with T, T* equal in conditional law gives the two
moment statements.
18.2 Restoring two patterns preserves the overlap law. Conditional on the
omitted system, the two deleted pattern rows are independent fresh
Gaussian fields with covariance R and unit diagonal. Restoring them
multiplies the measure by exp(f(b_1*)) exp(f(b_2*)), which is bounded
above and away from zero on the compact range of f. Uniform approximation
of z -> z^{-r} and of log z on that range by low-degree polynomials turns
every reweighted expectation into a finite combination of unreweighted
ones with finitely many extra replicas. Those pass to the array limit, so
the full system's limiting overlap law is the omitted system's law. On
cascades the same statement is 18.1(a): the shape law is preserved by the
reweighting, and the rounding argument passes it back to the real model.
18.3 First and second moments of the restored marks. Fix a rounding of
the overlap law into levels, and let M_i be the tilted conditional mean of
f'(b_1*) at a leaf at level i, i.e. its mean under the tilted kernels of
18.1, given the mark path through that level. Two continuations below the
common level use conditionally independent kernels and, crucially,
separately sampled final residuals. Hence, writing d_i for the tilted
conditional mean of the product f'(b_1*(x^1)) f'(b_1*(x^2)) given common
level i,
d_i = E[ M_i^2 ] , 0 <= d_i <= d_{i+1} <= d_d <= ||f'||_inf^2 ,
where the monotonicity is the martingale property of conditional means and
d_d is the single-visit tilted mean of f'^2. Averaging the tilted mark path
over the root, whose law is unchanged, gives constants d_d and
e = tilted mean of g(z) = f''(z) - z f'(z) ,
both independent of the sampled shape. Independence across components
gives product means d_d^2 and e^2, which is exactly what removes the
variance.
18.4 Identification of the empirical covariances. Recall
B_N(x,x') = (1/N) sum_a f'(b_a(x)) f'(b_a(x')) ,
C_N(x) = (1/N) sum_a ( f''(b_a(x)) - b_a(x) f'(b_a(x)) ) .
Pattern exchangeability in the full system, for bounded continuous D,
E< D(R_12) B_N(x^1,x^2) > = (M_N/N) E< D(R_12) A_{M_N} > ,
E< B_N(x^1,x^2)^2 > = (M_N(M_N-1)/N^2) E< A_{M_N-1} A_{M_N} > + O(1/N),
with A_a = f'(b_a(x^1)) f'(b_a(x^2)). The repeated-row term is O(1/N)
because A_a is bounded. Passing to the limit and inserting the restored
mark moments,
E[ D(R_12) B_12 ] = int D(r) a(r) mu(dr) ,
E[ B_12^2 ] = int a(r)^2 mu(dr) ,
with a deterministic nondecreasing a built from the limits of d_m. Hence
E[B_12 | R_12] = a(R_12), and subtracting the second moment of that
conditional mean from E[B_12^2] gives
E[ (B_12 - a(R_12))^2 ] = 0 ,
so B_lm = a(R_lm) almost surely for l != m. The identical first- and
second-moment computation applied to f'(b_a(x^1))^2 and to
g(b_a(x^1)) gives B_ll = a_d and C_l = c. Replica exchangeability and a
countable intersection make all of it hold simultaneously.
18.5 The identity linking the constants. Gaussian integration by parts in
the coordinates of one pattern row, including the derivative of the
normalized Gibbs density, gives
E< b_a(x^1) f'(b_a(x^1)) >
= E< f''(b_a(x^1)) + f'(b_a(x^1))^2
- R_12 f'(b_a(x^1)) f'(b_a(x^2)) > .
The perturbation is independent of that row and contributes no derivative.
Summing over a and dividing by N gives the exact finite-size identity
E< C_N(x^1) + B_N(x^1,x^1) > = E< R_12 B_N(x^1,x^2) > ,
and passing to the joint array limit gives
c + a_d = int_0^1 r a(r) mu(dr) = int_0^1 p(u) h(u) du ,
where p is the quantile of mu and h = a of p. This is the identity that
makes the diagonal pieces of the cavity increment assemble into the
entropy term. It is used in 19.7.
19. The cavity increment: algebra, evaluation, exchangeability
--------------------------------------------------------------
19.1 Setup. Write a spin in dimension N+L as (x,z) with x in {-1,+1}^N
and z in {-1,+1}^L, and a pattern as (g^a, y_a). Put
lambda_N = sqrt( N/(N+L) ) ,
R^+((x,z),(x',z')) = ( N R(x,x') + z . z' ) / (N+L) ,
so |R^+ - R| <= 2L/N. The larger pattern argument is lambda_N b_a(x) +
(y_a . z)/sqrt(N+L).
19.2 Replacing the perturbation. Since the series xi^v_N and their first
derivatives are bounded on [-1,1] and the tail is O(4^{-N}),
sup | s_{N+L}^2 xi^v_{N+L}(R^+) - s_N^2 xi^v_N(R) |
<= C_L ( N^{-1/4} + N^{3/4} 4^{-N} ) = o(1) ,
uniformly over spins, cavity spins and parameters. Gaussian interpolation
then controls both the expected log partition function and every fixed
bounded finite-replica test by this bound, so the perturbation may be
taken to be the bulk one.
19.3 Taylor bookkeeping. Compact support of f makes every scale
derivative bounded, so uniformly in s,
f(lambda_N s) = f(s) - (L/(2N)) s f'(s) + O_L(N^{-2}) ,
f^{(j)}(lambda_N s) = f^{(j)}(s) + O_L(N^{-1}) , j = 1, 2 .
Expanding the translation by (y_a . z)/sqrt(N+L) to second order, its
third-order remainder is bounded by C_L N^{-3/2} |y_a|^3, and replacing
denominators sqrt(N+L), N+L by sqrt(N), N adds terms bounded by
C_L(N^{-2} + N^{-3/2}|y_a| + N^{-2}|y_a|^2). Summing over the M_N = O(N)
old rows gives expected uniform error O_L(N^{-1/2}). Each of the d = O_L(1)
new rows may be replaced by f(b_a(x)) at expected uniform cost
O_L(N^{-1} + N^{-1/2} E|y_a|).
19.4 The result of the expansion. Up to a remainder whose supremum has
expected size o(1),
energy = sum_a f(b_a(x)) + H^v_N(x) + log W(x,z) + Q(x,z) ,
W(x,z) = exp( z . Y(x) + (L/2) C_N(x) + sum_{a=M+1}^{M+d} f(b_a(x)) ) ,
Y(x) = N^{-1/2} sum_{a<=M} f'(b_a(x)) y_a ,
Q(x,z) = (1/(2N)) sum_{a<=M} f''(b_a(x)) ( (y_a . z)^2 - L ) .
Conditionally on the bulk data, Y(x) is a vector Gaussian field with
covariance B_N in each of its L coordinates, independent of the d new
bulk pattern fields. The deterministic quadratic part L sum_a
f''(b_a(x))/(2N) together with the dilation term is exactly (L/2) C_N(x).
19.5 A uniform lower bound for W. With G_0 = G_N^v (x) nu_L the bulk
measure times the independent cavity prior, and A(x) = (L/2) C_N(x) +
sum_{a > M} f(b_a(x)), bounded uniformly by C_L,
G_0(W) = G_N^v( exp(A(x)) prod_{i=1}^L cosh( Y_i(x) ) )
>= exp(-C_L) =: kappa_L > 0 .
This bound concerns the untilted measure and is what makes every
normalization below safe.
19.6 Removing Q. For fixed spin state and fixed bulk data the variables
y_a . z are independent N(0, L), so
E_y Q(x,z)^2 <= C_L / N , E_y exp( t |Q(x,z)| ) <= C_{L,t} ,
for every fixed t and large N. The second follows by direct computation:
with c_a = f''(b_a(x))/(2N),
log E_y exp( t c_a ((y_a . z)^2 - L) )
= -t L c_a - (1/2) log(1 - 2t L c_a) = O_{L,t}(c_a^2) ,
where the linear terms cancel and summing gives O_{L,t}(N^{-1}). Also
E_y exp(t z . Y(x)) <= C_{L,t}, because the conditional variance is
L B_N(x,x) <= C_L. Writing P_W = W dG_0 / G_0(W) for the normalized
approximation, these bounds give
E P_W(|Q|) + E P_W(|e^Q - 1|) <= C_L N^{-1/2} .
Then Jensen and log t <= t - 1 sandwich the log partition integral,
-P_W(|Q|) <= log P_W(e^Q) <= P_W(|e^Q - 1|) ,
so removing Q costs o(1) in the expected log integral. For normalized
replica tests, the elementary bound below replaces any lower estimate
for P_W(e^Q): for a probability P and positive integrable Y with m = P(Y),
P|Y/m - 1| <= |1 - m| + P|Y - 1| <= 2 P|Y - 1| ,
applied with P = P_W and Y = e^Q.
19.7 Evaluating the increment on a cascade. Round the pair (r, a(r))
jointly on successively finer meshes of [0,1] x [0, a_d], keep the bins of
positive mu-probability, and choose representatives ordered in both
coordinates. The resulting step paths (p_m, h_m) converge to (p,h) in L^1
and approximate both coordinates on sampled off-diagonal entries, and the
construction never splits an interval on which p is constant. That last
property matters: overlap tests identify only conditional means of the
field derivative, and keeping the derivative paths measurable as functions
of p is what lets them identify the whole path.
In such a finite cascade the linear-field residual on each visit has
coordinate variance a_d - h_top, so averaging over the L cavity spins
contributes the constant (L/2)(a_d - h_top) to the leaf log factor, and
the L independent log cosh factors contribute L(ell(h_m) + h_top/2). Each
of the d independent pattern components contributes V_f(p_m), the
deterministic bulk factor contributes L c/2, and the additive-component
property of 18.1(b) keeps all of them independent. With
c + a_d = int r a dmu = int p h from 18.5, the total is
L ( ell(h_m) + (1/2) int p_m h_m ) + d V_f(p_m) ,
and continuity in the path (16.1) gives the increment limit
lim_N Delta_{N,L}(v(N)) = L ( ell(h) + (1/2) int_0^1 p h ) + d V_f(p) .
Unbounded fields are handled before this by clipping: with [t]_D =
max(-D, min(t,D)) and W_D the clipped factor, symmetry under z -> -z and
oddness of the clip keep G_0(W_D) >= kappa_L, the Gaussian tail estimate
sup over Var(T) <= C_L of E[ e^{|T|} 1{|T| > D} ] -> 0
gives sup over N,v of E G_0|W - W_D| -> 0, and hence the log difference
and every r-replica test difference are controlled by kappa_L^{-1} times
that quantity. So evaluate the clipped factor by array limits, then remove
the clip.
19.8 Exchangeability. Under the cavity tilt, the conditional mean of
z_1^1 z_1^2 given the pair's common level i equals (rho_h)_i. Check it for
one coordinate: for a shared leaf field t and independent residual eta of
variance a_d - h_top,
E_eta exp( z_1 (t + eta) ) = exp( z_1 t ) exp( (a_d - h_top)/2 ) ,
and the second factor does not depend on z_1, so after residual averaging
the spin magnetization is tanh t. Two visits, even to the same leaf, use
separate residuals and separate spins, and below their shared level their
mark paths are conditionally independent. Propagating the leaf
magnetization backwards along the tilted kernels therefore gives U_i' at
level i, and the product mean is its averaged square.
On the other hand the finite-size model is invariant under coordinate
permutations, so for every bounded continuous D_0,
E< D_0(R^+_12) z_1^1 z_1^2 >_{N+L} = E< D_0(R^+_12) R^+_12 >_{N+L} ,
because replacing the distinguished coordinate by any of the N+L and
averaging produces the overlap. Comparing the two descriptions,
int_0^1 D_0(p_m(u)) rho_{h_m}(u) du -> int_0^1 D_0(p(u)) p(u) du .
The paths rho_{h_m} are nondecreasing with values in [0,1] and are
measurable with respect to sigma(p): their bins were built from p and a(p)
without splitting flat intervals of p. Bounded monotone selection gives an
L^1-convergent subsequence, and the space of sigma(p)-measurable functions
is L^1-closed (conditional expectation onto sigma(p) is an L^1
contraction). So the limit rho is sigma(p)-measurable, continuous tests
force rho - p to have zero conditional mean given p, and hence rho = p.
That is S_I(p) = ell(h) + (1/2) int p h, the attainment of the entropy
supremum.
19.9 Telescoping. With d = alpha L + O(1) and |V_f| <= ||f||_inf,
lim Delta_{N,L} = L { S_I(p) + alpha V_f(p) } + (d - alpha L) V_f(p)
>= L P_f(alpha) - ||f||_inf ,
on every good subsequence. Since the good parameter sequence was
arbitrary, the infimum over G_N inherits the bound, the uniform lower
bound of 19.5-19.6 controls the complement of G_N, and integrating over
the same product measure in both dimensions gives
liminf ( F_{N+L} - F_N ) >= L P_f(alpha) - ||f||_inf .
Telescope in each of the L residue classes modulo L, divide by N, let the
floor error vanish, then L -> infinity, then remove the perturbation with
F_N/N - E p_N = O(N^{-1/4}).
20. Cascades: quantization, Gram positivity, and one fresh pattern
------------------------------------------------------------------
20.1 Quantization. Let B be nonnegative and ultrametric off the diagonal,
with constant diagonal D and entries at most D. Apply a nonnegative
nondecreasing finite-valued map to the off-diagonal entries, keep the
diagonal at D. The result is still a Gram array. If B also has the
Ghirlanda-Guerra property, the quantized off-diagonal law is the finite
cascade law with the quantized levels.
Proof. Let c_0 < ... < c_s be the distinct quantized values and let A_j be
the matrix with entries 1 when two indices are in the same class at level
c_j and 1 on the diagonal. Each A_j is positive semidefinite, because its
quadratic form is a sum over classes of squared within-class sums. The
quantized matrix equals
c_0 1 1^T + sum_{j=1}^s (c_j - c_{j-1}) A_j + (D - c_s) I ,
a nonnegative combination of positive semidefinite matrices. The
Ghirlanda-Guerra property passes through the map by the tower rule, so
BLACK BOX B identifies the law. The same decomposition works coordinate by
coordinate for finitely many nondecreasing functions a_j(r) of the scalar
overlap, using joint bins of r chosen as a function of r alone so that no
atom is split; that is what section 19's rounding uses.
20.2 Uniqueness and continuity. For fixed diagonal D, the law of a
nonnegative ultrametric Ghirlanda-Guerra array with values in [0,D] is
determined by its two-replica marginal, and such a law exists for every
marginal on [0,D]. If quantiles converge in L^1, then every fixed finite
replica block converges in bounded-Lipschitz distance. Proof: round both
candidates on finer and finer meshes, use 20.1 and 18.1 to identify the
rounded laws, and let the rounding error vanish; existence comes from
finite cascades plus compactness; continuity comes from coupling the
marginals by a common uniform variable, whose Wasserstein distance is at
most the L^1 quantile distance.
20.3 One fresh pattern on a cascade. Let the limiting spin overlap array
have diagonal 1, be Gram, nonnegative and ultrametric, and satisfy the
Ghirlanda-Guerra identity. Let p be its quantile. For a fresh independent
Gaussian pattern field g with conditional covariance R and bounded
continuous f,
lim E log < exp f( g(x) ) > = V_f(p) .
Proof. Round p into levels p_0 <= ... <= p_{k-1} with probabilities w_i,
keeping diagonal 1, and represent the rounded structure by a finite
cascade. At each visit to a leaf, integrate an independent residual of
variance 1 - p_{k-1}. The terminal shared-field log factor is then
U_{k-1}(x) = log E exp( f( x + sqrt(1 - p_{k-1}) G ) ) ,
the remaining branch transforms have coefficients zeta_{k-1}, ..., zeta_1
by 18.1, and the common root Gaussian is averaged with coefficient zero,
because zeta_0 = 0. Those are precisely the defining transforms of the
pattern recursion on the rounded step path: the final coefficient is one
and the initial coefficient is zero. Sending the rounding error to zero
and using 20.2 proves the identity, and for bounded continuous f it also
identifies the continuous extension of V_f.
20.4 Two visits to one leaf. The residual of variance 1 - p_{k-1} belongs
to the visit, not to the leaf. Two replicas visiting the same leaf use two
independent residuals, so their fields have covariance p_{k-1}, exactly
the shared value, and not 1. Giving a leaf one permanent residual would
raise the off-diagonal covariance to 1 and break 18.3 and 19.8 at once.
This is also why the cavity magnetization computation in 19.8 is written
with a per-visit residual.
21. Removing smoothness: bounded Borel activations
---------------------------------------------------
21.1 Lemma (uniform approximation). Let f, g be bounded Borel with
|f|, |g| <= K. Then
|E p_N(f) - E p_N(g)| <= alpha e^{2K} ||f - g||_{L^1(gamma)} ,
sup over step q of |V_f(q) - V_g(q)| <= e^{2K} ||f - g||_{L^1(gamma)} ,
where gamma is standard Gaussian probability. The constants do not depend
on N or on the path.
Proof of the first. Interpolate f_t = (1-t) f + t g. The derivative of
E p_N along the interpolation is, by Gibbs differentiation,
(1/N) sum_a E< (g - f)( b_a(x) ) > .
Remove pattern a from the measure and restore it. The removed log factor
lies in [-K, K], so a nonnegative Gibbs average changes by a factor at
most e^{2K} when it is restored. Conditional on all other patterns and on
a sampled spin x, the fresh field b_a(x) is standard Gaussian, so the
summand is at most e^{2K} ||g - f||_{L^1(gamma)}. Summing and using
M_N/N <= alpha finishes.
Proof of the second. Fix a step path. Interpolating the terminal function
from f to g and differentiating the recursion, the derivative propagates
through the kernels and equals the tilted expectation of (g - f)(Z_k),
where Z is the tilted chain and the density of the tilted path measure
with respect to the untilted independent Gaussian increments is
exp(telescoped exponent) with
telescoped exponent = f_t(Z_k) - sum_{i=0}^{k-1} w_i U_i(Z_i) .
Check it for one level: the exponent is U_1(Z_1) - U_0(Z_0) =
f_t(Z_1) - w_0 U_0(Z_0) since zeta_1 = 1 and w_0 = 1 - zeta_0. Every
function on the right takes values in [-K, K], so the density lies in
[e^{-2K}, e^{2K}]. Without the tilt, Z_k is standard normal, because the
total variance is q_k - q_{-1} = 1. Hence the derivative is at most
e^{2K} E|g - f|(G) in absolute value.
21.2 Consequences. Choose f_j in C_c^infinity with |f_j| <= K and
||f_j - f||_{L^1(gamma)} -> 0 (truncate, approximate on a compact interval,
mollify with a nonnegative smooth kernel). Then
|P_f(alpha) - P_{f_j}(alpha)|
<= alpha sup over q of |V_f(q) - V_{f_j}(q)| -> 0 ,
because the entropy functional S_I does not depend on f at all. Together
with 21.1 for the pressure, the smooth formula gives the theorem for
bounded Borel f. For convergence in probability, changing one pattern row
changes p_N by at most 2 ||f||_inf / N, so Var(p_N) <= 4 M ||f||_inf^2/N^2
= O(1/N) and Chebyshev finishes. Nothing in this section uses smoothness of
the overlap path, which is why the bound in 21.1 is uniform in the path and
can be applied to the variational value directly.
22. Unbounded activations: the integrable class, and why a restriction is needed
--------------------------------------------------------------------------------
22.1 The class. Suppose f: R -> R is Borel and
E|f(G)| + E exp( f(G) ) < infinity .
For J, K > 0 put f_{J,K} = min{ K, max{ -J, f } }. Then the ordered limit
V_f = lim_{J -> infinity} lim_{K -> infinity} V_{f_{J,K}}
exists uniformly on Q and is continuous in L^1, the formula holds with this
V_f in expectation and in probability, and the value is finite.
22.2 Two clipping estimates. Let P be any probability on the real line, t
its coordinate function, t_J = max(t, -J), and r = (-J - t)_+. Then
(lower) 0 <= log P(e^{t_J}) - log P(e^t) <= P(r) ,
(upper) 0 <= log P(e^{t_J}) - log P(e^{min(t_J,K)})
<= e^J P( (e^t - e^K)_+ ) .
Proof of the lower bound. Write the difference as minus the log of
P(e^{t_J} e^{-r})/P(e^{t_J}). By log <= exp - 1 and then Jensen under the
e^{t_J} tilt, it is at most the tilted mean of r, which is at most P(r).
The last step is the covariance inequality: e^{max(t,-J)} is increasing in
t while (-J - t)_+ is decreasing in t, so their covariance under P is
nonpositive. Proof of the upper bound: after the lower clip the
exponential is at least e^{-J}, so log(1 + x) <= x gives the bound.
22.3 Uniform error. Define
eps_{J,K} = E( -J - f(G) )_+ + e^J E( e^{f(G)} - e^K )_+ .
Replacing one pattern factor at a time in the finite spin system, and
using that the omitted factor is independent of the base probability with a
standard normal fresh field, gives
E| p_N(f) - p_N(f_{J,K}) | <= alpha eps_{J,K} ,
sup over step q of | V_f(q) - V_{f_{J,K}}(q) | <= eps_{J,K} .
The order of the limits matters and the estimates explain why: the lower
clip is controlled by integrability of |f|, the upper clip after the lower
clip is controlled by integrability of e^f, and the factor e^J must not
meet the tail of e^f until the lower clip has already been paid for.
22.4 Finiteness and the order of limits. Two applications of Jensen to the
same cascade integral give, first on step paths and then on all of Q,
E f(G) <= V_f(q) <= log E exp( f(G) ) ,
with equality in the second at q = 0. Since S_I >= 0 and S_I(0) = 0,
alpha E f(G) <= P_f(alpha) <= alpha log E exp( f(G) ) ,
so the value is finite. At fixed J, the bounded case applies; letting
K -> infinity, the bounded functionals are uniformly Cauchy on the dense
set of step paths and hence on Q; letting J -> infinity and applying the
lower clipping bound with f replaced by max(f, -J') shows the limits
differ by at most E(-J - f(G))_+, which vanishes. Convergence in
probability follows from Markov applied to the clipped difference, taking
N -> infinity, then K -> infinity at fixed J, then J -> infinity. No
variance estimate for the unbounded model is needed.
22.5 Why something must be assumed. Take f(s) = s^4 and, for the first
pattern, the configuration x with x_i = sign(g^1_i). The law of large
numbers gives
b_1(x) = N^{-1/2} sum_i |g^1_i| -> sqrt(2/pi) sqrt(N)
in probability. Every other pattern contributes a nonnegative amount, and
the configuration has prior weight 2^{-N} under nu_N. Then
p_N(f) >= b_1(x)^4 / N - log 2 -> infinity
in probability. So the pressure genuinely diverges, and no hypothesis-free
statement is possible for unbounded activations.
23. Random-sign patterns, and two counterexamples
-------------------------------------------------
23.1 The statement. Replace the Gaussian pattern entries by independent
uniform signs in {-1, +1}. If f is bounded Borel and its discontinuity set
has Gaussian measure zero, then the expected pressure and the pressure in
probability converge to the same value P_f(alpha).
23.2 Smooth case by coordinate replacement. Let f be smooth and compactly
supported. Regard the normalized pressure as a function of a single pattern
entry. Three differentiations of the finite spin sum give a bound
C_f N^{-5/2}: each derivative of the pattern argument supplies x_i/sqrt(N),
and the normalized log partition supplies a factor 1/N, while the rest are
bounded Gibbs moments of f', f'', f'''. Taylor expansion through degree two
with matching first and second moments of the Gaussian and the sign
therefore bounds each entry replacement by C_f N^{-5/2}. There are M_N N =
O(N^2) entries, so replacing them one at a time gives expected-pressure
error O_f(N^{-1/2}), which vanishes.
23.3 General case. Take smooth approximants f_j with |f_j|, |f| <= K and
||f_j - f||_{L^1(gamma)} -> 0. The pattern-deleting argument of 21.1
applies verbatim, so
|E p_N^sign(f) - E p_N^sign(f_j)|
<= alpha e^{2K} E | f(X_N) - f_j(X_N) | ,
where X_N = N^{-1/2} sum_i epsilon_i is the fresh sign field at a fixed
state: conditional on the hypercube state, that field has the same law for
every state. Now X_N -> G in distribution (the same third-order
calculation plus E X_N^2 = 1), and |f - f_j| is bounded and continuous
outside a Gaussian-null set, so the bounded almost-everywhere-continuous
test criterion gives
E | f(X_N) - f_j(X_N) | -> E | f(G) - f_j(G) | .
Then N -> infinity at fixed j, and finally j -> infinity. Convergence in
probability uses the same bounded-difference estimate as before, valid for
independent sign rows too.
23.4 Why the regularity condition cannot be dropped. Take f = 1 on the
rationals. For Gaussian patterns every field b_a(x) is irrational almost
surely (finitely many states, finitely many rows at each size), so p_N = 0
for all N. For sign patterns every field is rational, so p_N = M_N/N for
square N, while for odd nonsquare N the field is nonzero irrational and
p_N = 0. The two subsequences have different limits. This is exactly the
kind of pathology the Gaussian-null discontinuity condition excludes.
============================================================
PART V. FORMAL STATEMENTS, CONSTANTS, AND DEPENDENCIES
============================================================
24. Constants and normalizations, in one table
----------------------------------------------
M_N floor(alpha N), the pattern count.
nu_N uniform probability on {-1,+1}^N.
Z_N, p_N 8.2 and 9. Adding log 2 to p_N if counting.
q, h overlap path (nondecreasing, [0,1]-valued) and
field path (nonnegative nondecreasing step function).
zeta_i, w_i partition points and gaps, w_i = zeta_{i+1} - zeta_i.
T_{s,d} 8.1, the soft-maximum transform. d = zeta_i always.
V_f, ell, S_I 8.2, 8.3, 8.4.
rho_h 15.4, the overlap path produced by the field h.
s_N N^{3/8}, the lower-bound perturbation scale; its
pressure cost is s_N^2 = N^{3/4}, hence o(N).
xi^v_N(r) sum_j 4^{-j} v_j^2 r^j, the normalized covariance
profile of that perturbation.
t_j s_N 2^{-j}, one perturbation coefficient.
e_N N^{-1/16}, the upper-bound perturbation scale. Its
pressure cost is e_N^2; its energy scale is
sqrt(N) e_N = N^{7/16}.
kappa_j(R,T) R^p T^d with p + d >= 1, the perturbation monomials.
a_{N,j} sqrt(N) e_N 2^{-j}.
C_zeta sum_{i=1}^{k-1} (log 2)/zeta_i, from 17.2.
kappa_L exp(-C_L), the lower bound for G_0(W) in 19.5.
lambda_N sqrt(N/(N+L)), the cavity rescaling.
d M_{N+L} - M_N, so |d - alpha L| <= 1.
H alpha t^2, the only constant in the linear example.
Warning about overloaded symbols, inherited from the original. The letter
e is used for the perturbation scale N^{-1/16}, for the Euler number, and
for a good-parameter error sum; this edition writes eps_N for the last of
these: eps_N = sum_{j <= J_N} int a_{j,N} d pi -> 0, with a_{j,N} the
scaled mean absolute deviation of Y_j and delta_N = sqrt(eps_N) + 1/N the
threshold defining G_N. Also G is both the Gibbs measure and a standard
Gaussian variable; the context is always decisive. The letters f, x, e, s
and z all do double duty in the original for functions, states, quantities
and coordinates; here the pattern coordinates of a cavity spin are always
z = (z_1, ..., z_L) and the perturbation vector is always u.
25. The black boxes, stated
---------------------------
BLACK BOX A (Ghirlanda-Guerra property implies positivity and
ultrametricity). Let B be a bounded, symmetric, exchangeable array with
constant diagonal, whose finite restrictions are positive semidefinite,
and suppose that for every n >= 2
law( B_{1,n+1} | first n x n block ) = (1/n) mu
+ (1/n) sum_{l=2}^n delta(B_{1l}) , mu = law(B_12).
Then almost surely, for distinct indices,
B_{lm} >= 0 and B_{12} >= min( B_{13}, B_{23} ) .
Proved in the original by a duplication argument, using the moments
E[1_A (1 + z W)^{-n}] = P(A) (1 + z)^{-b}; the identity originates with
Ghirlanda and Guerra (1998), the duplication mechanism with Panchenko
(2013). Used in: 12.5 (synchronization), 17.4 (to pass from the joint
identity to the array limit), 18.4, 19.7.
BLACK BOX B (cascade law and its reweighting). For a finite cascade with
levels zeta_i and Poisson intensities zeta_i x^{-1-zeta_i} dx, the total
weight is almost surely finite and positive with finite second log moment,
the common-level array satisfies the Ghirlanda-Guerra property, and
P( gamma^1 ^ gamma^2 = i ) = w_i .
Conversely, a weakly exchangeable ultrametric scalar array with the
Ghirlanda-Guerra property and finitely many off-diagonal values has the
same off-diagonal law as such a cascade with those levels. Reweighting by
a terminal log factor preserves the tree law and tilts only the vertex
marks, with kernels of density exp( zeta_i (X_i - X_{i-1}) ) where
X_{i-1} = (1/zeta_i) log E_i exp(zeta_i X_i); additive terminal log
factors give additive transforms and conditionally independent component
kernels; and conditioning on a sampled shape does not further tilt.
Sources: Ruelle (1987) for cascades, Bolthausen and Sznitman (1998) for
the weights-and-ancestry sampling law, Panchenko and Talagrand (2007) for
the reweighting and its use in interpolation. The original derives the
sampling calculations including repeated visits to one leaf from the
Poisson construction. Used in: 8.2-8.4 (what the recursions mean), 17.1,
18.1, 18.3, 19.5-19.8, 20.1-20.3.
BLACK BOX C (contact points for nonconvex interactions). A quadratic
penalty in a parameter, together with a concentration estimate, produces
fluctuation control at a deterministic minimizer, hence overlap
identities for the joint array at that minimizer. Source: Mourrat (2021),
Section 4, equations (4.19)-(4.28), for the Gaussian bipartite case; the
enrichment with cascade labels is Mourrat and Panchenko (2020). The
perceptron derivation of the price and the concentration is the paper's
own, because the pattern term is not Gaussian. Used in: 12.3, 17.2, 17.3.
BLACK BOX D (concavity of the centered-Ising field functional). ell is
concave on nonnegative nondecreasing step paths, hence so is its
continuous extension, and the supporting inequality of 27.5 holds.
Sources: Chen, Issa and Mourrat (2026), Propositions 2.2 and 2.4, where
ell(h) = -psi(h/2) in their normalization; independently Ho (2026),
Theorem 1.8, by a Parisi PDE concavity argument with the opposite sign and
a different covariance normalization. The proof in section 27 below is
the paper's own, written to cover repeated field levels and zero initial
variance. Used in: 8.4 (reading ii), 19.8, 27.5.
BLACK BOX E (cavity variational principle). Adding finitely many
coordinates and comparing the resulting increment with a variational
increment is legitimate, and the entropy of the added coordinates is the
supremum over fields of a concave functional plus a linear term. Source:
Aizenman, Sims and Starr (2003), in the spirit of their extended
variational principle for the SK model. Used structurally in: 13, 19.
Two further tools, not black boxes, proved in section 28: Gaussian
interpolation with its replica derivative formula (Guerra 2003, and the
same computation in the original), and the order-preservation property of
a folded Gaussian kernel (classical; see Panchenko 2005, Lemma 2(d)).
26. Dependency chart
--------------------
Read an arrow as "uses". Everything below uses only 8.1 and elementary
Gaussian facts unless stated.
15 first variations
|
+--> 16 Lipschitz, tail order, reduction to finite trials
| |
| +--> 17.2 coercivity (needs 16.3 for q_{k-1} < 1)
| +--> 12.6 tail comparison
| +--> 19.7 continuity in the path
|
+--> 21.1 second part (the telescoped density)
+--> 20.2 continuity, 20.3 identification of V_f
17 concentration and contact point
uses BLACK BOX B in 17.1(i) and BLACK BOX C in 17.2-17.3
|
+--> 17.4 joint overlap identities
|
+--> 12.5 (BLACK BOX A on R, T, R+T)
18 restored marks
uses BLACK BOX A (rigidity from the good set), BLACK BOX B
(tilted kernels, per-visit residuals), and 16.1 for the monotone a
|
+--> 18.4 B_N = a of R, B_ll = a_d, C_N = c
+--> 18.5 c + a_d = int r a dmu
|
+--> 19.7 assembling the increment
19 cavity
uses 18.4, 18.5, 20.2 (rounding by quantiles), 18.1(b)
(independence across components), coordinate exchangeability
|
+--> 19.9 liminf of F_{N+L} - F_N >= L P_f - ||f||_inf
upper half: 12, using 16.2, 16.3, 17.4, 20.3, BLACK BOX A, C
lower half: 19, using 18, 20.2, BLACK BOX B, E
both halves: 8.1-8.4, and then 21-23 to remove smoothness
External inputs by subject, for a reader who wants to follow one thread:
spin glasses and the Parisi formula
Guerra 2003 (broken replica symmetry bounds)
Talagrand 2006 (Parisi formula, even interactions)
Panchenko 2014 (mixed p-spin, including odd)
Mourrat and Panchenko 2020 (Hamilton-Jacobi enrichment)
Mourrat 2021, 2023 (nonconvex interactions, vector spins)
Chen and Mourrat 2025 (vector spins, critical point description)
Chen, Issa and Mourrat 2026 (centered Ising spins, concavity)
Ho 2026 (Parisi PDE concavity)
Panchenko 2015 (multi-species synchronization)
Panchenko 2005 (folded kernels preserve monotone evenness)
cascades and ultrametricity
Ruelle 1987, Bolthausen and Sznitman 1998,
Ghirlanda and Guerra 1998, Panchenko 2013,
Panchenko and Talagrand 2007 (two papers)
cavity and interpolation
Aizenman, Sims and Starr 2003, Guerra 2003,
Chatterjee 2006 (Lindeberg)
perceptron and storage
Gardner 1988, Gardner and Derrida 1988, Krauth and Mezard 1989,
Talagrand 2000 (intersecting half-spaces), Talagrand 2002
(Gaussian perceptron, high temperature),
Bolthausen, Nakajima, Sun and Xu 2022 (Gardner formula at small
density), Ding and Sun 2025, Huang 2024,
Shmalo 2026 (computer-assisted verification of the analytic
conditions at zero margin; a preprint whose verification the
original explicitly flags as not independently reproduced),
Nakajima and Sun 2023 (sharp thresholds and universality for
hard-constraint classes), Perkins and Xu 2024 (frozen 1-RSB for
the symmetric perceptron), Abbe, Li and Sly 2021 (lognormal limit,
symmetric perceptron, random signs)
companion
the paper's own companion, "The free energy of the spherical random
perceptron", which develops the scalar enrichment and the
two-pattern cavity strategy for spherical spins.
27. Concavity of ell and the supporting inequality
--------------------------------------------------
This section is the proof referred to in BLACK BOX D. It is included
because the paper needs it in a form covering repeated field levels and
zero initial variance, and because it is short enough to check line by
line.
27.1 Lemma (a folded Gaussian transition is order preserving). Let U be
even and convex, with finite normalizers E exp( d U(x + sqrt(s) G) ) for
all x, where s >= 0 and d >= 0. Let K be the associated tilted kernel of
15.1. If A is bounded, even and nondecreasing in |x|, then K A has the
same three properties; and if A is bounded, even and nonincreasing in
|x|, so is K A.
Proof. Evenness is reflection, and s = 0 is immediate. For s > 0 the law
of the new absolute value y >= 0, started at x >= 0, has density
proportional to
exp( -y^2/(2s) ) cosh( x y / s ) exp( d U(y) ) .
For x_2 >= x_1 >= 0 the ratio of the two normalized densities is a
positive constant times cosh(x_2 y/s)/cosh(x_1 y/s). Its logarithmic
derivative in y is
(x_2/s) tanh( x_2 y / s ) - (x_1/s) tanh( x_1 y / s ) >= 0 ,
because a -> a tanh(a y/s) is nondecreasing on [0, infinity). So the
density ratio L(y) is increasing. For two independent copies Y, Y' with
the law started at x_1,
Cov( A(Y), L(Y) ) = (1/2) E[ (A(Y) - A(Y'))(L(Y) - L(Y')) ] >= 0 ,
since both factors have the same sign. With E L(Y) = 1 this says
K A(x_2) >= K A(x_1). Negating A gives the reversed statement. The
normalizers are part of L and do not disturb its monotonicity.
27.2 The Hessian. Work in the open cone 0 < h_0 < ... < h_{k-1}, where all
derivatives exist. Write m_i = U_i' and rho_i = E[ m_i(Z_i)^2 ], as in
15.4, and let A be the matrix
A_{ij} = w_i d rho_i / d h_j = -2 d^2 ell / d h_i d h_j .
A is symmetric by symmetry of second derivatives. Two claims:
(i) A_{ij} <= 0 for i != j
(ii) sum_j A_{ij} >= 0 for every i.
Given them, positivity is a two-line check: for any vector v,
v^T A v = sum_i ( sum_j A_{ij} ) v_i^2
+ sum_{i<j} ( -A_{ij} ) ( v_i - v_j )^2 >= 0 .
So A is positive semidefinite, the Hessian of ell is negative
semidefinite on the cone, and ell is concave along segments inside it.
First, every U_i is even and convex. Evenness is preserved by the
transforms. For convexity with d > 0 use convexity of U and Holder: for
0 <= a <= 1,
E exp( d U( a x + (1-a) y + sqrt(s) G ) )
<= ( E exp( d U(x + sqrt(s) G) ) )^a
( E exp( d U(y + sqrt(s) G) ) )^{1-a} ,
and take logarithms; expectation preserves convexity when d = 0. The
terminal subtraction in the field recursion is constant in x. Hence m_i
is odd, m_i(x) >= 0 for x >= 0, m_i^2 is even and nondecreasing in |x|,
and all U_i have at most linear growth, so the normalizers in 27.1 are
finite.
27.3 The cross signs. This is claim (i). Stop the propagation of 15.3 at
level i, which gives, for j > i,
d U_i(x) / d h_j = -(w_j/2) ( K_{i+1} ... K_j m_j^2 )(x) .
By repeated use of 27.1 that function is even and nonincreasing in |x|,
so its derivative is <= 0 for x > 0 and >= 0 for x < 0, while m_i has the
opposite sign. Hence the direct derivative of m_i^2 is pointwise <= 0.
The remaining terms come from differentiating the probability kernels in
rho_i = K_0 ... K_i ( m_i^2 ), and each of them contributes, at a fixed
starting point,
zeta_l Cov_{ K_l(x,.) }( H_l, A_l ) <= 0 ,
where H_l = K_{l+1} ... K_i ( m_i^2 ) is even and nondecreasing in |x| and
A_l is even and nonincreasing in |x|; the sign is the covariance identity
of 27.1. The case l = 0 contributes zero because zeta_0 = 0. These are all
the terms in the product rule, so (i) holds.
27.4 The row sums. This is claim (ii). Increase every h_i by the same
a >= 0. No variance increment h_i - h_{i-1} changes, and every U_i with
i >= 0 changes only by the additive constant -a/2, so no spatial
derivative and no kernel changes. The only change is that the initial
variance grows from h_0 to h_0 + a. The function reached at level i is
even and nondecreasing in |x|, so coupling the initial values as
sqrt(h_0 + a) G gives (ii).
27.5 Theorem (concavity and support). ell is concave on nonnegative
nondecreasing step paths, and for any two such paths on a common
partition,
ell(h') <= ell(h) - (1/2) int_0^1 ( h'(u) - h(u) ) rho_h(u) du .
Concavity extends to the continuous extension on bounded nonnegative
nondecreasing fields.
Proof. 27.2 gives negative semidefinite Hessian on the open cone, hence
concavity and, using the first variation at the starting point, the
supporting inequality there. For arbitrary steps h, h' on the partition,
replace h_i and h_i' by h_i + eps(i+1) and h_i' + eps(i+1); both are in
the open cone, their difference is unchanged, and eps -> 0 with 15.3's
continuity gives the closed cone. Distinct partitions are handled by
common refinement, and bounded paths by L^1 approximation with 16.1.
27.6 What it buys. Taking h' = h + a phi and differentiating at a = 0
recovers the first variation. Taking h' equal to any trial field shows
that h maximizes ell(h') + (1/2) int h' rho_h over h'. Therefore
S_I(rho_h) = ell(h) + (1/2) int_0^1 h(u) rho_h(u) du ,
and the supremum defining S_I is attained at h whenever the trial overlap
path equals rho_h. Equivalently, h/2 lies in the subgradient of the
concave functional S_I at rho_h. This is the identity that 19.8 makes
true for the model itself: the field read off from the restored pattern
covariances, paired with the overlap path read off from the replicas,
sits exactly at the top of the entropy functional.
28. Toolkit
-----------
28.1 Lemma (Gaussian interpolation). Let P be a probability, possibly
random but independent of the Gaussian fields below, and let H_0, H_1 be
centered Gaussian energies with covariances C_0, C_1 on the same index
set. Interpolate H_t = sqrt(1-t) H_0 + sqrt(t) H_1 and put
Delta = C_1 - C_0. Then
d/dt E log P( e^{H_t} ) = (1/2) E< Delta_11 - Delta_12 >_t .
For a bounded r-replica test F independent of these fields,
d/dt E< F >_t = (1/2) E< F ( sum_{a,b=1}^r Delta_ab
- 2r sum_{a=1}^r Delta_{a,r+1}
+ r(r+1) Delta_{r+1,r+2} - r Delta_{r+1,r+1} ) >_t ,
whose absolute value is at most ( 2 r^2 + r ) ||F||_inf ||Delta||_inf. If
an independent centered Gaussian field Y of covariance C enters the energy
with coefficient s, then
E< Y(1) F > = s E< F ( sum_{a=1}^r C_{1a} - r C_{1,r+1} ) > .
Proof. For finitely many states, differentiate the coupling and apply
ordinary Gaussian integration by parts, which contracts one half of the
energy Hessian with Delta. A derivative of a normalized r-replica integral
inserts the sum over its r sampled states minus r times one extra replica;
a second derivative and contraction give the second display. Countable
index sets are handled by truncating to finite label sets chosen
independently of the added fields and using the moment bounds below.
28.2 Variance bounds.
(V1) Gaussian Lipschitz. A function of finitely many standard Gaussian
variables with Euclidean Lipschitz constant A has variance <= A^2.
Proof: interpolate two standard Gaussian copies from independent to
identical with cross covariance t times the identity, differentiate
the product expectation, integrate from 0 to 1, and bound the
gradient. Truncation and smoothing extend it to Lipschitz
functions.
(V2) Independent inputs. A function whose value changes by at most c_i
when input i is replaced has variance <= sum_i c_i^2. Proof:
reveal inputs successively and sum the variances of the martingale
differences, each bounded by c_i^2.
(V3) Poisson. If a is Lipschitz with constant c on the integers and K is
Poisson with mean lambda, then Var(a(K)) <= c^2 lambda. Proof: for
an independent copy K', Var(a(K)) = (1/2) E[(a(K) - a(K'))^2] <=
(c^2/2) E[(K - K')^2] = c^2 lambda.
28.3 Poisson and stable facts, used only in section 18. For a Poisson
point process of intensity C x^{-1-b} dx with 0 < b < 1, the sum S of its
points has
E exp(-tS) = exp(-c t^b) , c = C Gamma(1-b)/b ,
so E S^r < infinity for 0 < r < b, E S^{-r} < infinity for every r > 0, and
E (log S)^2 < infinity. The proof is the Poisson exponential formula: the
exponent is -C int_0^infinity (1 - e^{-t x}) x^{-1-b} dx = -c t^b, and the
moment statements follow by integrating 1 - E e^{-tS} and E e^{-c t^b}
against suitable powers, as in the original.
28.4 Measure facts. A bounded Borel measure on a compact metric space is
determined by its integrals against continuous functions; convergence of
quantiles in L^1 implies convergence of the corresponding measures in
bounded-Lipschitz distance (couple by a common uniform variable, and the
Wasserstein distance is at most the L^1 quantile distance); a quantile q
describes the law of q(U) for U uniform on (0,1).
============================================================
PART VI. GLOSSARY, NOTATION, AND FIRST QUESTIONS
============================================================
29. Glossary
------------
cascade (Ruelle): a random tree with Poisson weights, used as a
representative of an ultrametric overlap structure. Section 4, BLACK
BOX B.
cavity: the operation of adding a few spins or patterns and asking how
the pressure changes. Sections 13.4-13.7 and 19.
contact point: a deterministic minimizer of a penalized functional at
which the model's own parameters become stationary, so that overlap
identities can be extracted. BLACK BOX C.
Gibbs measure: the weight normalized to a probability; the object whose
samples are called replicas. Section 1.6.
Ghirlanda-Guerra identity: the conditional law statement that the next
replica either starts a new cluster or joins an existing one
proportionally to size. Section 4, BLACK BOX A.
Gram array: an array all of whose finite restrictions are positive
semidefinite. Overlap arrays are Gram arrays because they are inner
products of vectors.
log-potential: the function f applied to a projection, giving the reward
of one pattern. Bounded Borel in the main theorem.
overlap: R(x,x') = (1/N) x . x', the scaled inner product of two
configurations. Section 1.3.
overlap path (quantile): the nondecreasing inverse distribution function
q of the limiting overlap law. Section 3.
perceptron: a pattern-based storage or classification rule; here, the
weighted count of sign patterns by their performance on M random
questions. Section 1.
Poissonization: replacing a fixed count M = floor(alpha N) by a Poisson
count of mean N t, so that the count can be differentiated. Section
12.2(c).
pressure: (1/N) log Z_N, the exponential growth rate of the total
weight. Section 1.5.
replica: an independent sample from the Gibbs measure, with the patterns
held fixed. Overlaps between replicas describe the structure of the
weights.
replica symmetric: the case where the overlap is asymptotically constant,
so the minimizer q is a single number r. The linear activation is
replica symmetric; general activations need not be.
soft maximum: the transform T_{s,d}, with stiffness d and added variance
s. Section 8.1.
storage capacity: the largest density alpha for which a hard-constraint
perceptron can satisfy all patterns. Not the subject here, but the
reason the model is studied.
tilt (reweighting): multiplying a measure by a positive factor and
renormalizing. On cascades it preserves the tree and tilts the marks.
ultrametricity: for three samples, R_12 >= min(R_13, R_23). Equivalently,
samples sit at leaves of a tree. Section 4.
V_f: the pattern reward of a fresh pattern under overlap path q, computed
by the pattern recursion. Section 8.2.
ell: the spin-side functional, computed by the field recursion from
log cosh. Section 8.3. It is concave (section 27).
S_I: the Ising entropy, the supremum of ell(h) + (1/2) int h q over field
paths. Section 8.4.
rho_h: the overlap path produced by the field h; the derivative path of
the field recursion. Section 15.4. The lower bound proves rho_h = p for
the system's own h and p.
30. Notation index
------------------
alpha pattern density, M = floor(alpha N).
N, M spins, patterns.
x, z spin vector in {-1,+1}^N; cavity spin vector in {-1,+1}^L.
g^a, y_a pattern vector; its projection onto the L new coordinates.
b_a(x) (1/sqrt N) g^a . x.
R, R^+ overlaps in dimensions N and N+L.
Z_N, p_N partition function, pressure.
nu_N uniform prior on the cube.
G, <...> Gibbs measure; replica expectation.
E expectation over patterns and other randomness.
f log-potential.
q, Q overlap path; the set of overlap paths.
h field path.
T_{s,d} the transform of 8.1.
V_f, ell the two functionals of 8.2 and 8.3.
S_I entropy of 8.4.
zeta, w partition points and gaps.
rho_h derivative path of 15.4.
B_N, C_N empirical gradient covariance and dilation correction.
a, a_d, c their limits: off-diagonal function, diagonal, constant.
p quantile of the limiting overlap law.
h (again) in the lower bound, h = a of p, so the field is read off
the restored covariance.
kappa_j monomial covariances R^p T^d, p + d >= 1.
u perturbation coefficients.
s_N, e_N N^{3/8} and N^{-1/16}, the two perturbation scales.
L, lambda_N cavity size and rescaling.
K, t Poisson count and its mean.
h_i, H field path values; the field cap is H.
kappa_L exp(-C_L), the uniform lower bound for G_0(W).
31. Questions a first-time reader asks
--------------------------------------
Q1. Why not just compute Z_N?
Because there are 2^N terms, each involving a product over M = alpha N
patterns, and the answer depends on N in a nontrivial way. The theorem
computes the exponential rate for every alpha at once, in closed
variational form.
Q2. Where does the tree in the answer come from?
Not from a modelling assumption. It comes from ultrametricity (BLACK BOX
A), which is a theorem about the limiting overlap array, and from the
fact that a finite ultrametric array with overlap identities is
distributed as a finite cascade (BLACK BOX B). The tree is a
consequence, and it is what makes the answer finite-dimensional.
Q3. Why is the answer a minimum?
Because the pressure is a free energy with a sign convention: energy
gain appears as alpha V_f and it is a reward, while S_I is the entropy
of the configurations that realize the clustering. The two compete and
the system picks the best compromise. If one wrote the functional with
the opposite sign, it would be a maximum. There is nothing to remember
beyond the identity of the two terms.
Q4. Is the minimum attained, or only approached?
Attained, by the actual overlap path of the system. That is exactly the
content of 19.8 plus 27.6: rho_h = p, so the supremum inside S_I is
attained and the variational inequality is an equality.
Q5. What happens for a hard constraint, i.e. f = -infinity outside an
interval?
The theorem does not cover it, and the paper says so. Hard constraints
are a different regime with their own literature (Ding-Sun, Huang,
Nakajima-Sun, Perkins-Xu, Abbe-Li-Sly). Passing beta -> infinity in the
present formula would need control of the order of limits.
Q6. Can I actually evaluate V_f, ell, S_I with a computer?
Yes, at any finite accuracy. Discretize q and h into a partition with k
levels, and evaluate the recursions from the top down: each step needs
an expectation of a smooth function of a Gaussian, which a quadrature
does. The supremum over h inside S_I is a concave maximization (ell is
concave and the second term is linear), so it is well behaved; V_f is
Lipschitz in L^1 with constant (1/2) ||f'||_inf^2 by 16.1, so
minimizing in q is stable under discretization. The one thing to watch
is that the answer can be genuinely multi-level: a single number r is
not enough in general.
Q7. Why delete two patterns rather than one?
One restored pattern gives the conditional mean of f' and hence the
first moment of B_N. Two independent restored patterns give the
conditional mean of the product, which is the price of the second
moment. First plus second kills the variance of B_N, so B_N is
deterministic given R. One pattern alone would leave a fluctuating
covariance.
Q8. Why is the number of patterns Poissonized in the upper bound only?
In the upper bound the pattern density is the parameter that generates
the contradiction, and a Poisson count has an exact derivative in t,
namely the fresh-pattern expectation. In the lower bound the count is
kept deterministic, and the floor error |d - alpha L| <= 1 is absorbed
at the end. Both choices are bookkeeping, not substance.
Q9. Where does the -h/2 come from and why is it not optional?
It is the diagonal of the hierarchical Gaussian field: the field at a
leaf has variance h_top, so the logarithmic moment generating function
of a spin sum carries a deterministic -h_top/2. Dropping it would break
the cancellation in the cavity increment 19.7, would break the identity
in 18.5, and would destroy the concavity proof of 27.4, where a uniform
shift of all h_i must change nothing but the initial variance.
Q10. Is the proof shorter than it looks?
Yes and no. The skeleton is ten lines (section 14). The length is in
the estimates that make each of those lines uniform in N and in the
path. If you are learning the subject, read Parts I-III and section 27;
read 17-19 when you want to see the two mechanisms that are specific to
the perceptron: restored pattern covariances and coordinate
exchangeability.
32. What to remember, and what is still open
--------------------------------------------
Three sentences to take away.
* The limiting pressure of the Ising perceptron with Gaussian patterns
is the minimum of alpha times a Gaussian pattern recursion plus an
Ising entropy, over nondecreasing overlap quantiles.
* The two halves of the proof fail for opposite reasons: the upper
bound needs the model to be forced to disclose its overlap structure,
and the lower bound needs the model's own field to be identified with
its own overlap path.
* Neither half is a corollary of the Parisi formula, because the
pattern energy of this model is not a Gaussian process indexed by the
spins. That is the entire reason the paper exists.
Honest list of what is not settled here.
* Zero temperature, i.e. hard constraints. Not covered, actively
studied elsewhere, and the order of limits is the obstruction.
* Rates. The theorem gives the limit and concentration at rate O(1/N)
in variance, but no rate of convergence of the expected pressure
beyond the O(N^{-1/4}) perturbation bookkeeping in the lower bound.
* The minimizer. The theorem says the system's own path minimizes, but
it does not give a criterion for when a single-level path suffices,
i.e. when the model is replica symmetric, apart from the linear
example. Determining the minimizer for a given f and alpha is a
separate computation, and it is the one a practitioner actually wants.
* The spherical twin. The companion paper handles spherical spins with
a scalar enrichment and the same two-pattern cavity strategy; the
Ising case needs its own entropy calculation, which is section 27.
If you have read this far and can rederive the two checks of section 10
without looking, you understand the theorem. If you can also explain to
someone else why two visits to one cascade leaf need two residuals, you
understand the proof.