On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
Aukosh Jagannath Subhabrata Sen
math.PR math.CO





We establish a strict asymptotic inequality between a class 
of graph partition problems on the sparse and random regular graph ensembles with the same
average degree. 
Along the way, we establish a variational representation for the ground state energy
for generalized mixed p-spin glasses and derive strict comparison inequalities
for such models as the alphabet changes.


Sectoring in Multi-cell Massive MIMO Systems
    Shahram Shahsavari, Parisa Hassanzadeh, Alexei Ashikhmin, and Elza Erkip
S. Shahsavari, P. Hassanzadeh  and  E. Erkip are with the ECE Department of New York University, Brooklyn, NY. Email: {shahram.shahsavari,ph990, elza}@nyu.eduA. Ashikhmin is with Bell Labs, Nokia, Murray Hill, NJ, USA. Email:  alexei.ashikhmin@nokia.com
    December 30, 2023
==========================================================================================================================================================================================================================================================================================================================================





§ INTRODUCTION

Consider the following graph partition problem, called the unbalanced cut problem.
Let G=(V,E) be a graph and let V_1,V_2⊂ V
be a partition of the vertex set, V, such that 

    V_1  =αV     and     V_2  =(1-α)V,

where 0<α<1/2 is a fixed number.
Let (V_1,V_2) denote the number of edges joining V_1 to V_2. 
We are interested in the maximum
of this quantity over all such partitions, which we denote by 

    _α(G)=max_V_1=αV
    V_2=(1-α)V(V_1,V_2).

Observe, for example, that when α=1/2 this is the maximum bisection problem (Note that the quantity is only well-defined when α is rational).

We aim to compare this quantity asymptotically between two well-known 
random graph models. The first ensemble we consider is
the sparse random graph, G(N,d/N), where each
edge is added independently with probability d/N, where d is
a fixed constant. The second ensemble we
consider is the random d-regular graph, d, where 
a d-regular graph on N vertices is selected uniformly at random. 
These random graphs are typically sparse: such a graph on N vertices has O(N) edges with high probability.
Our main result is a strict comparison between the unbalanced cut problem on these two ensembles in the mean field approximation, i.e., for asymptotically large degrees. 


For any 0< α < 1/2, 
there is a constant C(α)>0 such that

    lim inf_d→∞lim inf_N→∞_α(G(N,d/N))-_α(d)/√(d)N≥ C(α)

almost surely.


The  novelty in this inequality is the fact that C(α) is strictly positive. Indeed, for the maximum bisection problem (α=1/2) it is known that that this difference is in fact zero <cit.>.
From a combinatorial perspective, this inequality is surprising: intuitively, it suggests
that the rigidity of the edge structure of random regular graphs, in comparison to that of graphs, has macroscopic ramifications for cut problems. 
The curious reader might also wonder if C(α) is 
in fact the sharp constant. We do not believe that this is the case. Instead, our
approach yields a natural conjecture regarding the sharp constant. 
in terms of a minimizer of _T. We discuss this conjecture in Section <ref>.   

The core of our approach is a connection between
the unbalanced cut problem — a priori a question of pure combinatorics— to
the ground state energy of the Generalized Sherrington-Kirkpatrick model—a priori a question
of statistical physics.  Before presenting this connection,
let us first place it in context.


If instead of _α(G) one considers the minimum α-cut problem, i.e., taking a minimum in (<ref>) instead of a maximum, the inequality (<ref>) is reversed in the obvious way with no change to the proof.




 §.§ Background


Graph partition problems are classical combinatorial optimization problems, having applications in Computer Science, 
Statistics and Machine Learning <cit.>. These problems are described as follows. 
Given a graph G= (V,E), we seek to divide the set of vertices into two or more parts 
such that the number of edges between the distinct parts is optimized.  
For example, the well-known MaxCut problem seeks to partition the vertex set into two parts, 
V_1 and V_2, such that the number of edges connecting the two parts, (V_1,V_2), is maximized. 
Another example  is the maximum bisection problem,  _1/2(G).
The study of these problems in the
sparse regime has received much attention
from the combinatorics community <cit.>, though
they remain very challenging.
Graph partition problems have also been studied extensively in the physics literature
 as they are predicted to lie in a canonical class of models called spin glasses. 

Connections between spin glasses
and combinatorial optimization problems are by now classical observations. 
This perspective has received a tremendous amount of attention
in the physics, mathematics, and combinatorics literatures. It is impossible
to provide here anywhere near a complete survey of this literature. Instead we point the reader to the texts
<cit.>. Although many of the predictions of the physics literature
have been verified, we are very far from understanding the full picture.
For a sample of recent, rigorous results in this direction see <cit.>. 


In the setting of graph partition problems, this connection goes back at least to the work of Fu–Anderson <cit.>. 
 Recently, there has been significant progress in formalizing this connection. 
First, Bayati–Gamarnik–Tetali <cit.>  
explored this connection by using a sub-additivity argument to establish the existence of a deterministic 
limit for the MaxCut on sparse and random regular graphs. In this light, 
it is natural to study this deterministic limiting value as a function of the degree, d. 


In the large degree limit, or mean field approximation, it is not hard to see that the leading order contribution is of order d and is essentially  the expected value of the objective function.
Evidently, the heart of the matter is then in subsequent terms of the expansion in d. Indeed, the next term, often of order √(d), is highly nontrivial, and related to the ground state energy of mean field spin glasses.
This idea was partially formalized by Dembo, Montanari, and one of the authors in  <cit.>, 
where it was shown that asymptotically
first in the vertex number and then in the degree, the normalized
MaxCut, maximum bisection, and the minimum bisection of the and 
the random d-regular graph ensembles are equal to second order in d.
Again, the first order contribution is that of a random labeling 
of the vertices, d/4. The second order term, of order √(d), is (essentially)
the ground state energy of the Sherrington-Kirkpatrick model <cit.>.


In subsequent work, one of the authors <cit.> generalized this result 
to a family of combinatorial optimization problems, where the objective is of a tensorial nature. 
For a general class of these problems on or random regular hypergraphs, 
a similar asymptotic appears, where this time the order √(d) term is the ground 
state energy of a suitably chosen spin glass model. 
From this perspective, it is natural to believe that for a wide class of these problems,
the optimal value should be the same on these two ensembles, up to o(√(d)) corrections.
To this end, <cit.> derives broad sufficient conditions for the normalized maxima to have the same value, up to lower order contributions in d.  
In this paper, we show, surprisingly, that this belief is flawed. 
Theorem <ref> establishes that even a small perturbation of the maximum bisection problem has widely different behavior on and random regular graphs. 

Theorem <ref> is also significant for a number of conceptual reasons. First, it establishes a strict inequality between these statistics on and random regular graphs— which is difficult to establish using purely combinatorial techniques. Second,
 aside
from solving an interesting question of combinatorics, it leads us to resolve an important  question
of  independent interest in the theory of spin glasses, namely the ground state energy of the generalized mixed p-spin glass model. Resolving these spin-glass questions is in fact our main technical contribution in this paper.



 §.§ Generalized mixed p-spin models and their connection to Theorem <ref>

At the heart of thm:cut_difference is a connection between the unbalanced cut problem and what are called   Generalized mixed p-spin models which were introduced by Panchenko in <cit.>. These are natural
generalizations of the Ising p-spin model <cit.> to the case where the spins take values in a  finite alphabet 
Σ⊂. (The Ising p-spin model corresponds to Σ={±1}.)


More precisely, let Σ⊂ be
a finite set called the alphabet, and let the configuration space be defined as
Σ^N. The Hamiltonian for this model is the centered
Gaussian process indexed by Σ^N with covariance 

    H_N(σ^1)H_N(σ^2)=Nξ(R(σ^1,σ^2)),

where ξ(t)=∑_p≥2β_2p^2t^2p is an even power
series and 

    R(σ^1,σ^2)=1/N∑_i=1^Nσ_i^1σ_i^2,

is called the overlap. Let 

    =max_ϵ∈Σϵ^2     and       =min_ϵ∈Σϵ^2.

We assume that ξ(+ϵ)<∞ for some >0 so
that this process is well-defined. 

The application to graph-partition problems (Theorem <ref>) motivates our interest  in the restricted
normalized ground state energy of this process, 

    GS_N(A_N):=max_σ∈ A_NH_N(σ)/N,

where A_N⊂Σ^N. Specifically, we are interested in
two cases, either A_N=Σ^N or 

    A_N=A_N(T,ϵ_N)={σ∈Σ^N:R(σ,σ)∈(T-ϵ_N,T+ϵ_N)} ,

for some ϵ_N→0 sufficiently slowly.

To understand why, we will show by an application of the results of <cit.> that
the proof of Theorem <ref> can be reduced to a strict comparison between 
the limiting ground state energies of two generalized Sherrington-Kirkpatrick (SK) models— models for which ξ(t)=2 t^2.
For a formal statement, we refer the reader to Lemma <ref>. For the graph, we obtain 
the SK model, while for the random regular graph, we obtain a generalized SK model, 
both constrained in a certain natural fashion. 
Consequently, if an inequality sufficed, one could then use a well-known
 Guerra-type <cit.> or Slepian-type <cit.> interpolation
to easily obtain the desired estimate. 
We are interested, however,
in a strict inequality asymptotically in N.

To accomplish this goal, our approach is to provide a quantitative understanding 
of the derivative of this interpolation. 
This is accomplished by a fine analysis of the limiting ground state energy in generalized mixed p-spin models. 
The derivative is naturally related to the minimizers
of a certain family of variational problems called “Parisi variational problems”,
and the question pertains to the scaling of the minimizers of these problem as one 
tunes a certain parameter, called the temperature. This naturally
leads us to a question of Γ-convergence of such variational problems <cit.>. 
This approach will not only yield that this constant is positive but will also yield 
a natural conjecture as to the sharp constant. 
We explain this in greater detail in  sec:annealing-intro
 and 
discuss the aforementioned conjecture in  sec:conj1.

 

 §.§ Ground State Energies of Generalized Mixed p-spin models

In this section, we explain our results regarding
variational representations for ground state energies of generalized mixed p-spin models.


The question of the ground state energy is natural from a statistical physics perspective, and has recently received considerable attention in the
mathematics literature. In the case that the configuration space is the sphere, S^N-1(√(N)), a variational formula
was independently provided by Chen–Sen<cit.> and Tobasco with one of the authors <cit.>.
In the case that the alphabet is Σ = {± 1}, called the Ising spin setting, a variational representation was obtained by Auffinger–Chen in <cit.>. These representations have since been 
used to study a wide variety of questions  <cit.> . 

We derive a variational representation for the normalized ground state energy of generalized mixed p-spin models as a consequence of our approach. 
To this end, we introduce the following notation. 

Let T∈[,]. Let ([0,T]) be
the positive cone of Radon measures on [0,T].
Let _T⊂([0,T]) be the set of measures of the
form 

    _T={ν∈([0,T]):ν=m(t)dt+cδ_T,   m(t)≥0 non-decreasing and cadlag},

equipped with the weak-* topology. Note, in particular, finitness enforces ∫_0^T m(t) dt < ∞.  On this space we define the
ground state energy functional _T:_T×→. For ν=mdt+cδ_T,
we let

    _T(ν,λ)=u_ν,λ(0,0)-λ T-1/2∫_0^Tξ”(s)sdν(s),

where u_ν,λ is the unique weak solution to

    ∂_tu+ξ”/2(Δ u+m(s)(∂_xu)^2)=0     (t,x)∈[0,T) ×
    
    u(T,x)=f(x,λ,c)     x∈,

where 

    f(x,λ,c)= sup_ϵ∈Σ{ϵ x+(λ+ξ”(T)/2· c)ϵ^2}   if    T ∈ (, ), 
    max_ϵ^2= T{ϵ x+(λ+ξ”(T)/2· c)ϵ^2}   if    T ∈{, }.

(For a notion of weak solution of such PDEs see <cit.>
and for  basic regularity in this setting see app:pde.) We then have
the following. 


For any ϵ_N→0 sufficiently slowly, 

    lim_N→∞GS_N(A_N)=inf_ν∈_T
    λ∈_T(ν,λ)

almost surely. Furthermore 

    lim_N→∞GS_N(Σ^N)=sup_Tinf_ν∈_T
    λ∈_T(ν,λ)

almost surely. 





We note here that one can eliminate
the dependence of this variational problem on c by making the substitution λ↦λ- c/2ξ”(T).
We leave the problem in this form for two key reasons: first, our derivation of this result will be by way of Γ-convergence for which one must allow c to be non-zero (see the discussion in the next section); second,
our main application, the proof of thm:cut_difference, will use this formula and said Γ-convergence result to characterize limit points of certain sequences of measures, which may have non-zero c. For the discussion of the physical interpretation 
of c see <cit.> and app:appendix-at.


To return to our combinatorial motivations, 
let us begin by first observing that as a corollary 
to thm:variational_rep and en route to proving thm:cut_difference, we also provide explicit formulas for _α to second order
in the degree. In the following, we let ^1_T(ν,λ) denote the functional 
eq:local-zero-temp-pfunc with Σ={± 1-(2α -1)} and ξ(t)=2t^2. Let  
    T(α)=4α(1-α).
 Finally, let  ^2:_1×→ denote the functional

    𝒫^2(ν,h)=u_ν,0(0,h)-1/2∫_0^1ξ”(s)sdν(s),

where u is the unique solution to (<ref>) with alphabet Σ ={+1,-1} and ξ(t)=2t^2, i.e.,
with final time data f(x,0,c)=|x|+2c. 


For any 0<α<1/2 we have that,

    lim_d→∞lim_N→∞_α(d)-N dα(1-α)/√(d)N   = 1/4inf_ν,λ_T(α)^1(ν,λ)
    lim_d→∞lim_N→∞_α(G(N,d/N))-N dα(1-α)/√(d)N   = 1/4inf_ν,h[ ^2(ν,h)-(2α-1)h].







 §.§ An analytical approach to annealing

At the heart of the recent work regarding variational representations for ground state energies
is an analytical approach to the notion of annealing. 
Annealing,
that is, adding a temperature and sending it to zero, is natural from 
the point of view of statistical physics
and underlies well-known algorithms for optimization <cit.>.

The idea, roughly, is as follows.
The ground state energy can be computed as the limit of an important quantity called the free energy 
which is defined as follows. Recall the Hamiltonian H_N from (<ref>). 
The free energy at inverse temperature β is defined as 

    F_N(β,ξ) = 1/Nlog∫_Σ^N e^β H_N(σ)dσ,

where dσ is the counting measure, and the restricted free energy corresponding to a set A⊂Σ^N 
and inverse temperature β is defined as

    F_N(β,ξ;A) = 1/Nlog∫_A e^β H_N(σ)dσ.

In our setting, we are interested in A_N of the form eq:A_N-def.

In these models, a variational expression for the free energy at a fixed temperature
is obtained using a  “Parisi-type formula”. 
For  Σ={± 1}, this was proved by Talagrand in <cit.>
and Panchenko in <cit.>. 
For general alphabets, the variational problem was derived by Panchenko in <cit.> 
(and more recently again in <cit.>) 
where he showed that for any T∈ [d,D] and any _N→0 sufficiently slowly

    F_N(β,ξ;A_N(T,_N))   → F(β,ξ;T)
    
    F_N(β,ξ)   → F(β,ξ)

where 

    F(β,ξ;T)   = βinf_ν∈ X_β, T,λ∈_β,T(ν,λ)
    
    F(β,ξ)   →βsup_T∈[,] F(β,ξ;T)

Here _β,T is called the local Parisi functional. For its precise definition see eq:pfunc-def.
It is not difficult to see that 

    1/βF(β,ξ;T)β→∞⟶lim_N→∞ GS_N(A_N).

Thus the question of ground state energies is related to the large β limit
of these variational problems. 

A natural approach to the asymptotic analysis of variational problems is
De Georgi's notion of Γ-convergence <cit.>.
Our approach, following <cit.>, is to study the Γ-limit of _β,T. As a direct consequence, we obtain a variational representation for the limiting ground state energy, similar to <cit.>. Further, this allows us to control zero temperature asymptotics of physically relevant quantities, and derive strict comparison inequalities. 
We remark here that
upper bounds only require the Γ-liminf inequality, and have been used in the recent progress in  
<cit.>.

Due to the natural topology of the Γ-limit,
one formally expects the need to understand how the nonlinear term —
the solution in space-time of a Hamilton–Jacobi–Bellman
equation, where
the coefficient of the non-linearity is the variable of optimization —
behaves as one allows this coefficient to become the derivative
of a Dirac mass. More precisely, one needs an appropriate
limiting notion of solution for such situations. (This explanation is necessarily vague,
for a more precise description see sec:gamma-parisi-intro.)
Auffinger–Chen <cit.> observed that in the case Σ ={±1},
the linear term in the functional exactly cancels this effect, allowing one 
to avoid this issue.
If one perturbs the problem
by allowing the spins to take values {±1+ϵ}, however,
the arguments
in the literature do not apply. We are then forced to tackle the question
of the limit of the non-linear term.
To this end, we introduce a notion of annealed solution which yields an interpretation for the solution of the
PDE in this singular regime as an appropriate zero-temperature Γ-limit.
The Γ-convergence of _β,T then follows.




 §.§ Acknowledgements

The authors thank Amir Dembo for introducing them to the unbalanced cut problem.
The authors thank Jonathan Shi for pointing out an error in an earlier version of this manuscript.  
A.J. thanks Ian Tobasco for fruitful discussions,
 as well as the University of Toronto and Harvard University
mathematics departments for their hospitality where part of this research was conducted. 
This research was conducted while A.J. was supported by NSF OISE-1604232
and NSERC [RGPIN-2020-04597, DGECR-2020-00199].
Cette recherche a été financée par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG).



 §.§ Outline of proof of Theorem 1.1


Let us now briefly outline the proof of Theorem 1.1. The starting point in our argument is Lemma lemma:gaussiancomp, which establishes that one can approximate 
_α on Erdős-Rényi and random regular graphs up to o(√(d)) corrections 
by the ground state energies of certain Generalized SK models. 
We then apply a Gaussian interpolation argument in lem:int_by_parts to compare the corresponding free energies. 
The error term in this comparison is a quantity that depends on the minimizer of the corresponding variational problems. Finally, we send β→∞, and analyze the limiting variational problem to prove a sign on the limit of this error term in Theorem <ref>.



 §.§ Outline of paper

The remainder of this paper is organized as follows.
In the next section, we reduce the proof of thm:cut_difference
to an inequality about asymptotics of “overlaps” of spin glass models (we introduce
this notion presently). 
In order to study this question, we introduce, in sec:gamma-parisi-intro,
 the Parisi boundary value
problem and the notion of annealed solutions to this problem. 
In sec:loc-free-energy, we present 
Panchenko's Parisi-type formula for the Free energy in this setting
and use the notion of annealed solutions to compute its Γ-limit. 
We then prove pre-compactness and convergence of the minimizers of this problem. 
We then turn briefly in sec:analysis-zero-temp to computing the first variation of the ground 
state functional _T. Finally, Section <ref> establishes the main spin glass estimate necessary for thm:cut_difference.
For the benefit of the reader, we briefly present some basic analytical and topological results
used in this paper in the appendix. 




§ THE UNBALANCED CUT PROBLEM

In this section, we establish Theorem <ref>. To this end, 
let G_1 ∼ G(N, d/N) and G_2 ∼ d be defined on the same probability space (Ω, ℱ, ). Recall that the random graph G(N, d/N) has vertex set [N], and the edges are added independently with probability d/N each. For ease of computation, we consider d to be drawn from the configuration model <cit.>. While this is a multi-graph in general, it is easy to see that conditioned on simplicity, the graph obtained is actually uniformly distributed. Further, the probability of the obtained graph being simple is bounded away from zero (see for example <cit.> and references therein). Thus it suffices to establish our result for the configuration model. 




 §.§ Concentration of 

Our first result establishes the concentration properties of  on G_1 and G_2 around their respective expectations. 



For any ε>0 sufficiently small, there exists a universal constant C(d, ϵ)>0 

    [ | (G_1)/N - [ (G_1)/N] | > ε]    ≤ 5 exp[- C(d, ε) N  ] 
    [ | (G_2)/N - [ (G_2)/N] | > ε]    ≤  2 exp[- N ε^2/d].




The concentration argument for  random regular graph G_2 follows immediately upon an application of <cit.>. 
Next, we establish the result for the random graph G_1. To this end, 
let E denote the number of edges in G_1 and observe that  
|E| ∼Bin( N  2, d/N). Thus [|E|] = (N-1)d/2. We have, 

    [ | (G_1) - [(G_1) ] | > N ε] 
       ≤[ | (G_1) - [(G_1) | |E| ]  | > Nε/2] + [ | [(G_1) | |E| ]  - [(G_1) ] | > N ε/2]. 
        := I + II.


To control I, we proceed as follows. We set ℰ = {  |E| ≤[|E|] + N ε_0 }, for some ε_0>0 to be chosen appropriately. 

    I    ≤[ 1(ℰ) [ | (G_1) - [ (G_1) | |E| ] | > N ε/2| |E| ]  +  [ ℰ^c]. 
       ≤ 2 exp[ - N^2 ε^2/8 [ [|E|] + N ε_0 ]] + exp[ - 2/3N ε_0^2/d],

where we bound the first term using the Azuma-Hoeffding inequality on the traditional edge-exposure martingale, and the second term by the Chernoff bound. 

To control II, let G_1' = ([N], E') ∼ G(N, d/N) be an random graph independent of G_1. We claim that 

    | [(G_1) | |E| ] - [ (G_1') | |E'| ]  | ≤| |E| - |E'| |.

Given the claim, we have, using Jensen's inequality, 

    | [ (G_1) | |E|  ] - [(G_1) ] | ≤_|E'||  [ (G_1) | |E|  ]  -  [ (G_1') | |E'|  ]  | 
       ≤_|E'|[ | |E| - |E'| | ] ≤| |E| - [|E|] | + | |E'| - [ |E'| ] | ≤| |E| - [|E|] | + C √(N d),

for some constant C>0, where the last inequality follows using Cauchy-Schwarz. Thus we have the bound,

    II < [ | |E| - [|E|]  | > N ε/2 - C √(Nd)] ≤ 2 exp[- N ε^2/6d],

where the last inequality follows using the Chernoff bound. 
 This completes the proof, modulo the claim (<ref>), once we optimize over ε_0. To prove this claim, we proceed as follows.

Given |E|, |E'|, we will construct a coupling (H, H') such that marginally, H and H' are distributed as G_1 conditioned to have |E| and  |E'| edges respectively. Assume without loss of generality, that |E'| > |E|. Start with an empty graph on [N]. Add edges sequentially, uniformly at random. At the end of |E| steps, 
call the graph formed H.  Continue adding edges, and at the end of |E'| steps call the graph H'. Under this construction, 

    | (H) - (H') | ≤| |E'| - |E| |
 
almost surely. Taking the expectation of this inequality with respect to the joint law of (H, H') and applying Jensen's inequality yields (<ref>), as desired. 









 §.§ Comparison to a Gaussian problem
 
In light of Lemma <ref>, it suffices to compare the expectations of  on G_1 and G_2. To this end, we introduce the following notation. 
For any graph G= (V,E) with |V| = N, assume that  V= [N] without loss of generality. Observe that every partition V= V_1 ⊔ V_2 of a graph can be represented by a vector σ∈{± 1}^N, with the two parts being encoded as V_1 = { i : σ_i =1} and vice versa. Therefore, every partition with |V_1| = α N, |V_2| = (1-α)N corresponds to a unique vector σ∈{± 1}^N such that ∑_i σ_i = N (2α -1). We set 
 
    S_N(α) = {σ∈{± 1 }^N : ∑_i σ_i = N (2 α -1) }.

 Next, we consider a GOE matrix J = (J_ij)_N × N and define g_i = ∑_j J_ij/√(N). For σ∈ S_N(α), we define,
 
    H_0(σ)    = ∑_ijJ_ij/√(N)σ_i σ_j,  
    
     H_1(σ)    = ∑_ijJ_ij/√(N)σ_i σ_j - 2 (2α -1) ∑_i g_i σ_i + (2α-1)^2∑_ijJ_ij/√(N).

 We have the following lemma. 
 
 
 As N→∞, we have,
 
    [ (G_1)/N]    = d α (1-α) + √(d)/4N[ max_σ∈ S_N(α) H_0(σ) ] + o(√(d)). 
    [ (G_2)/N]   = d α(1-α) + √(d)/4N[ max_σ∈ S_N(α) H_1(σ)] + o(√(d)).

 
 
 
 

 
 We start with the proof of (<ref>). This follows directly from <cit.>. In this case, we have
 p=2, A_N = S_N(α), f : {-1, 1}^2 →ℝ, f(x,y)= 1_{x ≠ y} = (1- x y)/2 and κ_1 = 1. Further, we note that on the set A_N, the contribution from the expectation is exactly α (1- α), and this completes the proof. 
 
 Next we consider (<ref>). This will be established using <cit.>. Using the same setup as above, we obtain that for random regular graphs, 
 
    [ (d)/N] = d α (1-α) + √(d)/2N[ max_σ∈ S_N(α)[ ∑_ijJ_ij/√(N)1_{σ_i  ≠σ_j } - 2/N∑_ij g_i 1_{σ_i ≠σ_j }] ] + o_d(√(d)).

 We note that for σ∈ S_N(α), ∑_i σ_i = N(2 α -1) and 1_{x ≠ y} = (1- xy)/2. Plugging these into the equation above completes the proof upon noting that the last term in (<ref>) is o_N(1) with high probability. 
 



 §.§ Proof of Theorem <ref>

The following Theorem establishes a strict lower bound on the difference between limiting ground state energies of the two generalized SK models. The proof is deferred to section <ref>. 


For 0< α < 1/2, there exists a constant C_0(α)>0 such that 

    lim inf_N →∞1/N[ [max_σ∈ S_N(α) H_0(σ) ] - [ max_σ∈ S_N(α) H_1(σ) ]  ] > C_0(α).
 



 
 Now, we note that Lemma <ref> immediately implies that 

    [(G_1)] - [(G_2)]/N √(d) = 1/4N[ [max_σ∈ S_N(α) H_0(σ) ] - [ max_σ∈ S_N(α) H_1(σ) ]  ] + o_d(1).

The proof of Theorem <ref> can be completed by combining thm:diff_groundstate, Lemma <ref> and (<ref>), using a simple Borel-Cantelli argument. 




 §.§ Proof of thm:diff_groundstate

For v ∈ [0,1], consider the interpolating Hamiltonian
 
    H_v(σ) = ∑_ijJ_ij/√(N) (σ_ i - √(v) ( 2α -1) )(σ_ j - √(v) ( 2α -1)),

and  the interpolating free energy 
 
    F_N(v, β; α) = 1/N[ log∑_σ∈ S_N (α)exp(β H_v(σ) )].

 At v=0 and v=1 these are the free energies for the Hamiltonians H_0 and H_1 respectively.
 It is convenient to make the change of variables σ↦τ where
 
    τ_i = σ_i - √(v)(2α-1) .

Under this change of variables,  H_v is a generalized mixed p-spin model with ξ(t)=2t^2 and
 where the spins take values in the set Σ(v,α), such that 
 
    Σ(v,α) = { 1- √(v) ( 2 α -1) , - 1 - √(v) (2α -1) }.

 Furthermore, if we define
  
    S_N(v,α) = {τ∈Σ(v,α)^N : ∑1{τ_i = 1 - √(v) (2α -1) } = N α}

 we can equivalently write 
 
    F_N(v, β ; α) = 1/N[ log∑_τ∈ S_N(v,α)exp(β H_v (τ))],

 where we abuse some notation and index the interpolating Hamiltonian by the new spins τ. 
  For τ, τ' ∈ S_N(v,α), we define the overlap as usual 
 
    R(τ, τ') = 1/N∑_i=1^Nτ_i τ_i'.

 We define 
 
    T(v,α) = α (1 - √(v) (2 α -1 ))^2 + (1 - α) (1 + √(v)(2 α -1 ))^2.

 and note that for α≠ 1/2 and v > 0, 
    τ∈ S_N(v,α) τ^2 = N T(v, α).
 
 In other words, for α≠ 1/2 and v>0, S_N(v,α) specifies sets with a constant “self-overlap". Note that at this
 juncture, we immediately obtain Corollary <ref>.
 
 
This follows by combining (<ref>), (<ref>), and (<ref>)  with thm:variational_rep in the case v=1 and Theorem <ref> in the case v=0.

 
 
 We will need the following results to complete the proof. 
  First, we obtain the following explicit expression for the derivative of the interpolating free energy in v using integration by parts. To this end, we will need the following definition. For any function f: S_N(v,α) →ℝ, we define the expectation under Gibbs measure of the interpolated Hamiltonian 
  
    ⟨ f ⟩_v = ∑_τ∈ S_N(v,α) f(τ) exp(β H_v (τ))/∑_τ∈ S_N(v,α)exp(β H_v (τ)).



 
 
 For each N ≥ 1, and α∈ (0, 1/2), we have, 
 
    1/β∂/∂ v F_N(v, β; α) = - 2 β (2α -1)^2 (1- √(v))/√(v)[ T(v) - ⟨ R_12⟩_v].

 
   The proof will be deferred to the end of the subsection. 
 
 Next, we will need the following crucial theorem. 
  
 
For all α∈ (0, 1/2) and v ∈ (0,1), there exists an explicit constant C_1(v,α)>0 such that  
 
    lim inf_β→∞lim inf_N →∞β[T^2 - ⟨ R_12^2 ⟩_v] > C_1(v,α).

 
The proof of this estimate will require the full machinery of the method of annealing. 
 We establish this result in Section <ref>. 
 Before turning to these results, however,  we establish thm:diff_groundstate. 
 
 Central to our approach is
the following well-known elementary observation  (see, e.g., <cit.>).

The following inequality holds for any A_N ⊂Σ^N and β >0. 

    | 1/β F_N(β, ξ; A_N)  - GS_N(A_N) | ≤log |Σ|/β.


 
 
 

We observe that the thesis of thm:diff_groundstate can be equivalently formulated as 
 
    lim inf_N→∞lim inf_β→∞1/β [F_N(0, β ; α) - F_N(1, β; α)] > C_0(α) >0 .

 
 In light of Lemma <ref>, it suffices to establish 
  
    lim inf_β→∞lim inf_N →∞1/β [F_N(0, β; α) - F_N (1, β ;α)] > C_0(α) .

 To this end, we have, 
 
    1/β[ F_N(1, β; α) - F_N(0, β; α) ] = ∫_0^11/β∂/∂ v F_N(v,β;  α)  v.

 

 Using (<ref>) and Lemma <ref>, it suffices to establish that for all v ∈ (0,1), 
 
    lim inf_β→∞lim inf_N →∞β[ T - ⟨ R_12⟩_v] > C_0(v, α) >0  .

 Note that T ≥ | R_12  | and thus (T - ⟨ R_12⟩_v ) ≥ (T^2 - ⟨ R_12^2 ⟩_v)/ 2 T. Thus the proof of thm:diff_groundstate follows upon applying Theorem <ref>.  
 
 
We establish Lemma <ref> in the rest of this section. 


 
 The result will follow directly by integrating by parts <cit.>. To see this, we begin by observing that
 
    1/β∂/∂ v F_N(v, β ; α) = 1/N[ ⟨∂/∂ v H_v (σ) ⟩_v].

 We note that 
 
    ∂/∂ v H_v(σ) = - (2α -1)/√(v)∑_ijJ_ij/√(N) (σ_i - √(v) (2α -1)).

 Moreover, we note that for τ∈ S_N(v, α), ∑_i τ_i = N (2α -1) ( 1- √(v)). Therefore, we have, 
 
    [ H_v(σ^1) ∂/∂ v H_v(σ^2) ] = - N2 ( 2α -1)^2 (1 -√(v)) /√(v) R(τ^1, τ^2) .

 Thus we have, by Gaussian integration-by-parts for Gibbs averages (see, e.g., <cit.>), that
 
    1/β∂/∂ v  F_N(v , β;  α) = - 2 β  ( 2α -1)^2 (1 -√(v)) /√(v)[ ( T - ⟨ R(τ^1, τ^2) ⟩_v )].

 This completes the proof. 
 












§ ANNEALED SOLUTIONS OF PARISI INITIAL VALUE PROBLEMS

In the study of mean field spin glasses, a central role
is played by the Parisi boundary value problem, which is defined as follows.
For β>0, let X_β,T⊂_T
denote the set of measures of the form 

    X_β,T={ν=βμ[0,t]dt,  μ∈([0,T])} .

Equip the product space _T× with the  product topology,
where we recall that _T was given the weak-* topology.

On this space define for every (t,x)∈[0,T)× 
the functional _β,T(ν,λ;t,x) given by

    _β,T(ν,λ;t,x)=
    
    u^β_ν,λ(t,x)    ν=βμ([0,t])dt
    
    +∞   otherwise,

where u_ν,λ^β(t,x) is the weak solution to 
the Parisi boundary value problem

    ∂_tu+ξ”/2(Δ u+βμ([0,s])(∂_xu)^2)=0
    
    u(T,x)=f_β(x,λ)

with boundary data 

    f_β(x,λ)=
    1/βlog∫_{σ^2=T}e^β(ϵ x+λϵ^2)dϵ   T∈{,}
    1/βlog∫_Σe^β(ϵ x+λϵ^2)dϵ   otherwise.

Here dσ is the counting measure on Σ. 






A central role in our study will be played by _β,T(ν,λ;t,x). 
More precisely, we will be interested in the limit of this functional as β→∞
along sequences (ν_β,λ_β) where ν_β∈ X_β.
The main issue in understanding this limit is as follows. 
On _T×, 
a typical convergent sequence,
(ν_β) with ν_β∈ X_β, satisfies

    ν_β→ν = m(t)dt+cδ_T.

Thus one must have a method of interpreting u^β_ν_β,λ_β(t,x)
in this limit. A naive approach does not suffice: in this limit
the coefficient in front of the non-linearity formally converges
to an expression of the form f(t) = m(t)+cδ'_T where
m is some cadlag non-decreasing function and δ'_T is the distributional
derivative of the Dirac mass at T.
Evidently,  care must be taken in this limiting procedure.



To this end we introduce a notion of solution that
respects this mode of convergence called an annealed solution. The 
main idea is that the singular contribution is,
effectively, a change of initial data. 
More precisely, we are led to the following definition.


We say that ϕ_ν,λ(t,x) is an annealed solution to eq:zero-temp-pde,
if for every (t,x)∈ [0,T)×, we have that


  * (lim inf condition) If (ν_β,λ_β)→(ν,λ), then for u^β_ν_β,λ_β the solution
of eq:ppde-finite-beta, we have that

    lim inf u^β_ν_β,λ_β(t,x)≥ϕ_ν,λ(t,x).


  * (lim sup condition) There is a sequence (ν_β,λ_β)→(ν,λ) such that for u^β_ν_β,λ_β, the solution
of (<ref>), we have that

    lim u^β_ν_β,λ_β(t,x) = ϕ_ν,λ(t,x).









The goal of this section is to interpret the weak solution, u, of eq:zero-temp-pde,
as an  annealed solution. 

For every ν and λ, the weak solution to (<ref>), u_ν,λ(t,x),  is an
annealed solution.


Before turning to the proof of this result, let us pause to make two comments.

We note here that the definition of annealed solution is such that the non-linear terms in (<ref>) will Γ-converge. 


Although we only use this result at the point (0,0), our argument extends to general (t,x) with no change. Furthermore, working with general (t,x) clarifies the proof substantially. Moreover, we imagine that this notion will be useful in future research.
Indeed, it is known <cit.> that the solution  u^β and its derivatives have physical interpretations, where the values at a given point in space-time are related to Gibbs averages of natural quantities. 
We expect the notion of annealed solutions to provide
insights into the zero-temperature behavior of these physical quantities. 















The proof of  thm:annealed-soln-thm is in two parts. In the following, we will omit
the dependence on (t,x) and T whenever it is clear for readability. We
will frequently make use of basic regularity of u^β and u. For the former see <cit.> and the
latter see app:pde.


We divide the proof of this theorem into two lemmas. 
We begin in lem:gamma-limsup below, by proving the lim sup condition.
We then turn to the lim inf condition in lem:gamma-liminf. 








For every every (t,x)∈ [0,T)×, and every (ν, λ) ∈_T×ℝ, there exists a sequence (ν_β,λ_β)→(ν,λ)
such that 

    lim u^β_ν_β,λ_β(t,x) = u_ν,λ(t,x)

where u_ν,λ is the weak solution to (<ref>).



Our goal is to construct such a recovery sequence.  To this end, 
fix ν and λ. Let λ_β=λ.
To construct ν_β,  we remind the reader of the 
following construction from <cit.>. 

Let ν∈_T and let c_β(ν)=c if ν({1})=c>0 and c_β(ν)=β^-1 otherwise. For β sufficiently large,  there exists a q_β∈ (0,T) with the following properties:
 
 
  * ∫_q_β^T m(t)dt+c_β=β(T-q_β)
 
  * q_β→ T
 
  * m(q_β)≤β.
 
 In particular, if 
 
    μ_β=  m(t)/β    t<q_β
    
     1     t≥ q_β

 then dν_β=βμ_β([0,t])dt∈ X_β and ν_β→ν.
 



Let us now show that this sequence allows us to recover the value of the function.
To this end, we solve the Parisi PDE eq:ppde-finite-beta
in the interval [q_β, T] using the Hopf-Cole transform. 
This yields, 

    u^β_ν_β,λ_β(q_β,x) 
    = 1/βlog∫exp[β( x + (λ+β/2(ξ'(T)-ξ'(q_β))^2))]d.

Since u^β=u^β_ν_β,λ_β and u=u_ν,λ solve the same PDE in the time interval (0,q_β), their difference, w= u^β - u, solves the boundary
value problem, 

    ∂_t w + ξ”(t) /2( Δ w + m(t) (∂_x u^β + ∂_x u ) ∂_x w ) = 0,    (t,x) ∈ (0, q_β) ×ℝ,  
    
    w(q_β, x) = u^β(q_β, x) - u(q_β, x)     x ∈.

Since ∂_x u^β and ∂_x u are both in C_tC^∞_x and m(t)∈ L^∞([0,q_β]) for s<q_β<T,  this is a linear heat equation and  
 we have the representation 

    w(t,x)    = _Z_t = x [w(q_β, Z_q_β)], 
     Z_t    = ξ”(t) m(t) (∂_x u^β + ∂_x u)  t  + √(ξ”(t)) W_t .

Thus we immediately obtain 

    |u^β(t,x) - u(t,x) | =  | w(t,x) | ≤ u^β(q_β, ·) - u(q_β, ·) _∞.

The proof of the lim sup condition will be complete once we establish that the right-hand side vanishes 
as β→∞. 

To this end, we note that 

    u^β(q_β, ·) - u(q_β, ·) _∞≤ u^β(q_β, ·) - u(T, ·) _∞ +  u (T, ·) - u(q_β, ·) _∞.

Let us first show that by (<ref>) and (<ref>)  the first term vanishes. 
Indeed, 

    u^β(q_β,x)-u(T,x)   ≤sup_{ x + (λ+(∫_q_β^T m(t)dt +c_β)ξ'(T)-ξ'(q_β)/2(T-q_β)·^2)} - u(T,x) +o_β(1)
       ≤/2(∫_q_β^T m(t)dt +c_β)ξ'(T)-ξ'(q_β)/T-q_β-cξ”(T) +o_β(1)

where the error terms o_β(1) are uniform in x. This goes to zero as β→∞ by lem:recovery-sequence. 


It remains to bound the second term. To see this,  note that by Itô's lemma,

    u(q_β, x) = _Z̃_q_β = x[ u(T, Z̃_T) ],

where Z_s is the Itô process

    Z̃_s = ξ”(s) m(s) ∂_x u( s, Z̃_s)  s + √(ξ”(s)) W_s .

Thus since u is Lipschitz in space uniformly in time,

    ũ_λ, ν(q_β, ·) - ũ_λ, ν(T, ·) _∞≤∂_x ũ_λ, ν_∞| Z̃_T - Z̃_q_β | → 0

as β→∞ using elementary properties of diffusions, as q_β→ T as β→∞. 
 


We now turn to the lim inf-condition.
For this we recall the dynamic programming  formulation 
of these PDEs.
Let _t^T be the space of all bounded processes on [t,T] that are progressively measurable
with respect to the filtration of Brownian motion. In the following, for a measure μ, we let μ(s)=μ([0,s]).


The weak solution u_ν,λ^β of eq:ppde-finite-beta corresponding to ν = βμ(s)ds   solves

    u^β_ν,λ(t,x) = sup_α∈_t^T_X_t^α =x( f_β(X_T^α,λ) - β/2∫_t^Tξ”(s)βμ(s)α^2_sds)

where X^α solves

    dX^α_s = ξ”(s)βμ(s)α_sds+√(ξ”(s))dW_s

with initial data X_t=x. Furthermore, any optimal control, α^*, satisfies

    μ(s)α_s^* =μ(s)∂_x u_ν,λ^β(s,X_s)    a.s.

where X_s solves:

    dX_s = ξ”(s)βμ(s)∂_x u_ν,λ^β(s,X_s)ds+√(ξ”(s))dW_s.


Furthermore, the weak solution u of eq:zero-temp-pde corresponding to ν = m(s)ds+cδ_T  solves

    u_ν,λ(t,x) = sup_γ∈ℬ_t^T_X̃_t^γ = x [ u_ν,λ(T, X̃_T^γ) - 1/2∫_t^Tξ”(s) m(s) γ^2_s  s ],

where X̃^γ has initial data X̃^γ_t =x and solves the SDE

    X̃^γ_s = ξ”(s) m(s) γ_s  s + √(ξ”(s)) W_s.




This result is an immediate consequence of the verification argument <cit.>. 
For u^β, this is immediate  after recalling that u is smooth in space and weakly differentiable in time, with bounded derivatives <cit.>. 
See <cit.> for a proof that applies essentially unchanged to our setting.
For u, the same proof applies after observing that the solution has the regularity from lem:ppde-reg-zero-temp.
The only point to note is that one should apply Itô's lemma for times t<T and then pass to a limit as t→ T. 
Similar arguments appear frequently in the literature, see, e.g., <cit.>, so we omit it.
Before turning to the lower bound, note the following.

Consider the function 

    ψ(x,y)=max_∈Σ[  x+^2y ].

For every y, this function is differentiable in x Lebesgue a.e.
Furthermore, the derivative is continuous in x Lebesgue a.e. and is given by 

    ∂_xψ(x,y)=_*,

where _* is the unique solution to ψ(x,y)=_*x+_*^2y.


Fix y. Then x↦ψ(x,y) is convex in x. Thus by Alexandrov's theorem <cit.>, it is differentiable in x Lebesgue a.e. with a derivative
that is continuous in x Lebesgue a.e.. Combining this with Danskin's
envelope theorem <cit.>, we see that the derivative is given by

    ∂_xψ(x,y)=_*,

where _* is such that ψ(x,y)=_*x+_*^2y.
 (Implicit in this argument is that there is a unique such _*
for almost every x, by another application of Alexandrov's theorem.)

With these in hand we can now prove the lower bound. 


For every (t,x)∈ [0,T)× and every (ν, λ) ∈×ℝ, if (ν_β ,λ_β) ∈×ℝ with (ν_β, λ_β) → (ν, λ), then

    lim inf u^β_ν_β,λ_β(t,x)≥ u_ν,λ(t,x)

where u_ν,λ is the weak solution to (<ref>).




We focus on the case T∈(,). The case T∈{,} is the same
 after taking λ=0 everywhere, as in this case the functional is constant in λ. 

 Let 

    ϕ(x) = argmax_∈Σ[ x + ( λ + c/2ξ”(T) )^2  ].

Observe that by lem:psi-diff, ϕ∈ L^∞(). Thus for any M>0, we can consider a sequence of smooth, 
compactly supported function ϕ_n
such that ϕ_n→ f strongly in L^2([-M,M]) and almost everywhere, where f is as in (<ref>).
Furthermore, one may take ϕ_n such that

    ϕ_n_∞≤ C

for some C>0 that does not depend on M or n. 
Fix γ∈ℬ_0^T,  τ∈(t,T), and for each n, consider the control

    α_s^τ,n = γ_s    if  s ≤τ
    ϕ_n(X̃^γ_s)    if   s > τ.

Note that α_s^τ,n is a bounded, progressively measurable control. 
Further, the continuity of ϕ_n ensures the left-continuity of α^τ,n_s as s ↑ T. 


By topological properties of _T, see lem:convergence,  we have that for each n,

    ∫_t^Tξ”(s) (α_s^τ,n)^2 ν_β(s) 
       β→∞→∫_t^τξ”(s) γ_s^2 m(s)  s +  ∫_τ^Tξ”(s) ( ϕ_n(X̃^γ_s) )^2ν(s)=: D_τ,n(ν)

We then let τ↑ T through the continuity points of ν to derive 

    D_τ(ν) →∫_t^Tξ”(s) γ_s^2 m(s)  s + c (ϕ_n(X̃^γ_T) )^2 ξ”(T)
 
almost surely.   

Similarly, we have that

    lim_β→∞X_T^α^τ,n   →∫_0^τξ”(s) γ_s m(s)  s + ∫_τ^Tξ”(s) ϕ_n(X̃^γ_s) ν(s) + ∫_0^T√(ξ”(s)) W_s + x =: Z_T(τ,ν),

almost surely.
As before, we let τ↑ T to obtain, 

    Z_T(τ, ν) →X̃_T^γ + c ϕ_n(X̃^γ_T) ξ”(T).

By the dynamic programming principle (<ref>),

    lim inf_β→∞ u^β_ν_β,λ_β(t,x)
    ≥lim inf_β→∞_X_t^α^τ,n=x[f_β(X_T^α^τ,n,λ_β) - 1/2∫_0^Tξ”(s) (α_s^τ,n)^2 ν_β(s) ].

If we combining these results with the fact that 

    f_β(x,λ) ≥ f(x,λ,0),

we may send β→∞, followed by τ↑ T and use the dominated convergence theorem to conclude that 

    lim inf_β→∞ u^β_ν_β,λ_β(t,x)    ≥lim inf_β→∞_X_t^α^τ,n=x[ sup_∈Σ[ X_T^α^τ,n + λ_β^2 ] - 1/2∫_0^T ξ”(s) (α_s^τ,n)^2 ν_β(s) ] 
    ≥[ζ_n],

where we define 

    ζ_n= [ sup_∈Σ(X̃_T^γ + c ϕ_n(X̃^γ_T) ξ”(T))+  λ^2) - 1/2∫_0^Tξ”(s) γ_s^2 m(s)  s - c/2 (ϕ_n(X̃^γ_T) )^2 ξ”(T) ].

Finally, it remains to send n →∞. We observe that 

    [ζ_n] = [ζ_n 1(X̃^γ_T ∈ [-M, M] ) ] + [ζ_n 1 (X̃^γ_T ∉ [-M,M] )].

Conditionally on the event X̃^γ_T ∈ [-M, M], ϕ_n(X̃^γ_T) →ϕ(X̃^γ_T) almost surely as n →∞. We define 

    ζ_∞ = sup_Σ[ ( X̃_T^γ + c ϕ(X̃^γ_T) ξ”(T)  ) + λ^2  ] - 1/2∫_0^Tξ”(s) γ_s^2 m(s)  s - c/2 (ϕ(X̃^γ_T) )^2 ξ”(T).

By the dominated covergence theorem, we may send first n→∞ and then M→∞ to obtain,

    lim_M →∞lim_n→∞[ζ_n 1(X̃^γ_T ∈ [-M, M]) ] = [ζ_∞].

Similarly, since ϕ_n and γ are bounded and λ,ν are fixed, we see
that ζ_n is uniformly bounded, so that 
by Hölders inequality,

    [ζ_n1 (X̃^γ_T ∉ [-M,M] ) ] ≤ζ_n_∞[X̃^γ_T ∉ [-M, M]].

We let M →∞ to control this term and obtain the lower bound

    lim inf_β→∞ u^β_ν_β,λ_β(t,x)  ≥[ζ_∞].

Finally, after recalling the choice of ψ  and maximizing in γ,
a  direct computation yields that 

    sup_γ[ζ_∞] = u_ν,λ(t,x).

The result then follows. 






§ LOCAL FREE ENERGIES: THEIR DERIVATIVES AND ZERO TEMPERATURE LIMITS


Our starting point for this section is equation  eq:loc-fe.
Following <cit.>, we refer to F(β,ξ;T) as the local free energy. 
The functional _β,T:_T×→ in eq:loc-fe 
 is called the local Parisi functional  and is
given by 

    _β,T(ν,λ)=_β,T(ν,λ;0,0)-λ T-β/2∫_0^Tξ”(s)sμ([0,s])ds,

where _β,T is defined in eq:finite_temp_functional. In particular, recall that _β,T is infinite on _T∖ X_β,T, so that _β,T is infinite as well. 
In this section, we study basic properties of this functional.  
First, in sec:diff-fe, we compute the derivative of the variational problem eq:loc-fe in β and relate this to the minimizer of _β,T. In sec:gamma-conv-local-fe,
we then compute the Γ-limit of the sequence (_β,T)_β as β tends to infinity and establish a  precompactness theorem regarding the corresponding sequence of minimizers. We end this section by applying this Γ-convergence result to prove thm:variational_rep.









 §.§ Differentiability of the Local Free energy
 

We begin by showing that eq:loc-fe is differentiable in β
and to provide an expression for this derivative in terms of the minimizer of the 
variational problem. For the purposes of this section, it is convenient to restrict
_β,T to the space X_β,T, defined in (<ref>). Furthermore, it is convenient to 
view this as a function of μ where ν =βμ([0,s])ds.
To this end, we denote 

    P_β,T(μ,λ)= β_β,T(ν,λ/β) = v_μ,λ(0,0)-λ T-β^2/2∫_0^Tξ”(s)sμ([0,s])ds

where ν = βμ([0,s])ds and v_μ,λ(t,x)=β u_ν,λ/β(t,x/β), where u^β solves (<ref>).  In this notation,

    F(β,ξ;T)= inf_μ,λP_β,T(μ,λ)

When it is clear, we will also omit dependence on T in our notation.
The main result of this section is the following. 


We have that

    ∂_β F(β,ξ;T) = β∫ (ξ(T)-ξ(t) )dμ

where for T>0, μ is the unique minimizing measure of P_β,T.


In the case that Σ={±1}, this result was obtained earlier in <cit.>.
An alternative proof was provided in <cit.>. Both of these 
arguments use in an essential way that the initial data satisfies
(∂_x f)^2 +∂_x^2 f = const. which does not hold in the general setting. 


The results of  <cit.> hold in the more general
setting that Σ is an arbitrary compact set and where the integral in this definition with respect to any measure ρ with
support Σ. 
This result also extends to this setting with no change, however
for the sake of exposition and with an eye toward our eventual application,
we do not consider this setting here. 



We begin the proof of thm:beta-deriv-overlap with the following lemmas.  
The first result is regarding the convexity of P_β,T and the uniqueness (or non-uniqueness) of minimizers.
This
was first proved in <cit.>, see also <cit.>.

If T∈ (,), the map P_β,T is strictly convex in (λ,μ).
If T∈{,}, and {σ^2=T}=2, the map is strictly convex in μ.
If T=0, the map is identically zero. 
Otherwise the map is convex and the functional is uniquely minimized at μ=δ_0. 

We defer the proof of this to the end of the section.

We note here that since u_ν,λ has the representation (<ref>), v_μ,λ has the representation

    v_μ,λ(t,x) = sup_α∈_T[ β f_β (X^α_T/β,λ/β) - β^2/2∫_t^T ξ”(s)μ(s)α_s^2ds]

with an optimal control 

    α^*_s = ∂_x v_μ,λ(t,x)

and optimal trajectory X̂_s which solves

    dX̂_s = β^2ξ”(s)μ(s)∂_x v_μ,λ(t,x)ds + √(β^2ξ”(t))dW_t.



Consequently, we have the following characterization 
of minimizers of P_β,T. In the following let

    G_μ,λ(t)=∫_t^Tβ^2ξ”(s)( (∂_x v_μ,λ)^2(s,X̂_s) - s)ds.



If T∈(,), there is a unique minimizing pair (μ,λ). Furthermore this pair 
satisfies 

    μ(G(s)=min_t∈[0,T] G(t))     = 1,
    ∂_λ v_μ,λ(0,0)    = T.
 
Finally  we have that for every q in the support of the
optimizing μ, 

    ∂_x v_μ,λ(q,X̂_q)^2 = q.

If T=, or T= with >0 then the above still holds, with the exception of eq:fixed-point-T.
If T=0, all measures minimize and the above conditions are vacuous. 


Note that in the case T∈{,}, if we instead work with the definition of f_β(x,λ) that
does not change in T, we see that eq:fixed-point-T still holds, except in a limiting sense.

We defer this proof to the end of the section as well. 

In the subsequent discussion we will be repeatedly differentiating an optimization problem. These
results generally go by the name of  “envelope theorems”. The two envelope theorems we shall use
are Danskin's theorem <cit.>, as well as the following lemma from <cit.>.


Let K be a metric space and I = [a,b) be a half open interval. Let f be a real valued
function on K× I and g(y)=sup_x∈ K f(x,y). Suppose that there is a K-valued
continuous function a(y) on I such that g(y)=f(a(y),y) and ∂_y f is jointly continuous
on K× I. Then g is right differentiable with derivative ∂_y f(a(y),y)

In the following, it is useful to equip the space _T with the L^2 metric and ([0,T])
with the metric d(μ,ν) = ∫μ([0,t])-ν([0,t])dt which metrizes the weak-* topology on this set.

Let us now prove the main result of this section.

The following argument is a modification of <cit.>.
Fix β,λ. For ease of notation, let v=v_μ,λ, and similarly for u when it is unambiguous, and also let g(x)=β f_β(x,λ/β). Let us take T>0 as the case T=0 is vacuous, by lem:strict-convexity-finite-beta.
Since u^β has the variational representation  eq:dpp-finite-beta,
we may apply lem:wei-kuo to obtain

    ∂_β v(t,x)    = ∂_x v(T,X̂_T)(2β∫_t^Tμ(s)ξ”(s)∂_x v(s,X̂_s)ds+∫_t^T √(ξ”)dW_s)
               - β∫_t^Tμ(s)ξ”(s)(∂_x v(s,X̂_s))^2ds.

(We use here, implicitly, that the map β↦ v^β is continuous.)
Since w=∂_x v weakly solves the heat equation

    ∂_t w+L w =0

with initial data w(T,·)=∂_x g, where L=β^2ξ”/2(∂_x^2 +2μ∂_x v ∂_x)
is the infinitesimal generator of  eq:local-field, it follows that ∂_x v(s,X̂_s)
is a martingale:

    ∂_x v(s,X̂_s)=∫_0^s ∂_x^2 v(s',X̂_s')√(β^2ξ”(s'))dW_s'+∂_x v(0,0).

Thus 

    ∂_β v(0,0)=β{∫_0^Tμ(s)ξ”(s) (∂_x v)(s,X̂_s)^2ds + ∫_0^Tξ”(s)∂_x^2 v(s,X̂_s)ds}.

Integrating the second term by parts,  using Itô's lemma and the fact that ξ'(0)=0, we
see that

    ∫ _0^T ξ”(s)∂_x^2v(s,X̂_s)ds = ξ'(T) ∂_x^2 v(T,X̂_T) + β^2∫_0^T μ(s) ξ'(s)ξ”(s)  (∂_x^2 v(s,X̂_s) )^2ds.

Integrating the first term by parts and applying Itô's lemma again, we see that 

    ∫_0^Tμ(s) ξ”(s)  (∂_x v)^2(s,X̂_s)ds    = ξ'(T) (∂_x v)^2(T,X̂_T)-∫_0^T ξ'(s) (∂_x v)^2(s,X̂_s)dμ
            -β^2∫_0^T μ(s) ξ'(s) ξ”(s)  (∂_x^2 v(s,X̂_s))^2 ds.

Combining these results, we obtain

    ∂_β v(0,0) = β{ξ'(T)( ∂_x^2 v(T,X̂_T)+(∂_x v)^2(T,X̂_T)) - ∫_0^Tξ'(s)(∂_x v)^2(s,X̂_s)dμ}.

Differentiating P_β,T in β, applying eq:fixed-point-q, and integrating by parts, we see that at the optimal μ_*, 

    ∂_β P_β,T(μ_*,λ) = β{ξ'(T)[( ∂_x^2 v_μ_*,λ(T,X̂_T)+(∂_x v_μ_*,λ)^2(T,X̂_T)) -T ] +∫_0^Tξ(T)-ξ(t)dμ_*(t)}.

Let us now show that at (μ_*,λ_*),

    ( ∂_x^2 v_μ_*,λ_*(T,x)+(∂_x v_μ_*,λ_*)^2(T,x)) =T.

To this end, observe that if we define π_x,λ(d) by 

    π_x,λ(d)=e^ x + ^2 λ/∫ e^ x+^2 λdd,

then we have

    ∂_x g = ,   ∂_x^2 g=^2-^2,    and   ∂_λ g =^2

where · denotes expectation with respect to π_x,λ. Thus

    ∂_x^2 g + (∂_x g)^2 = ∂_λ g.

In the case that T= or T=, if we take λ in the above expression to either -∞ or 
+∞ respectively, then we obtain the desired expression. 

It remains to consider the case T∈(,).
By a classical differentiable dependence argument  (see, e.g., <cit.>),
v is classically differentiable in λ, and w=∂_λ v
weakly solves the Cauchy problem

    ∂_t w + L w = 0
 
with boundary data w(T,·)=∂_λ g. Thus 

    ∂_λ v_μ_*,λ_*(0,0) = ∂_λg̅(X̂_T),

where g̅ is g evaluated at λ=λ_*.
As a result eq:combines-to-T then follows from eq:fixed-point-T at λ =λ_*, 
the optimal λ.

Combining these results with Danskin's envelope theorem <cit.>, we see that

    ∂_β F = ∂_β P_β,T(μ_*,λ_*)= β∫_0^T ξ(T)-ξ(t)dμ_*(t)

as desired.




Let us begin with the first case T∈(,). The proof in the case T∈{,} and {σ^2=T}=2
is identical. This proof is verbatim the argument in <cit.>.

Take (μ_0,λ_0),(μ_1,λ_1) distinct in ([0,T])×. 
Let μ_θ = θμ +(1-θ)ν and define λ_θ analogously.
 Let α^θ be the optimal control for the Parisi PDE corresponding to (μ_θ,λ_θ).
 Consider the processes Y_t and Z_t which solve
 
    dY_t = β^2ξ”(t)μ_0(t)α_t^θ dt+√(β^2ξ”(t))dW_t    and    dZ_t =β^2ξ”(t)μ_1(t)α_t^θ dt+√(β^2ξ”(t))dW_t,

with initial data Z_0=Y_0=0. 

Therefore by the strict convexity of g(λ,x) = β f_β(x/β,λ/β) in the pair (λ,x), 
 and the dynamic programming principle eq:dpp-finite-beta,
 
    v_μ_θ,λ_θ(0,0)    = [g(λ_θ,X̂_T^α^θ)-β^2/2∫_0^T ξ”(s)μ_θ(s)(α_s^θ)^2ds ]
       ≤θ[g(λ_1,Z_T)  - β^2/2∫_0^T ξ”(s)μ_1(s)(α_s^θ)^2ds]
            +(1-θ)[ g(λ_0,Y_T) -  β^2/2∫_0^T ξ”(s)μ_0(s)(α_s^θ)^2ds]
       ≤θ v_μ_1,λ_1(0,0)+(1-θ)v_μ_0,λ_0(0,0).

 Furthermore the first inequality is strict if either λ_1≠λ_0 or P(Y_T≠ Z_T)>0.
 Thus it remains to show that this probability is positive provided μ_0≠μ_1. 
 
To this end, observe that it suffices to show that 
 
    (Y_T-Z_T)>0.

By Itô's lemma,
 
    (Y_1-Z_1)=∫_[0,T]^2Δ_sΔ_t K(s,t)ds dt,

 where Δ_s = ξ”(s)(μ_0(s)-μ_1(s)) and 
 
    K(s,t)=[(α_s^θ-α_0^θ)·(α_t^θ-α_0^θ)],

so it suffices to show that K is positive definite.  By Itô's Isometry,
 
    K(s,t)=p(t∧ s)
 
 where 
 
    p(s) =∫_0^sβ^2ξ”(t)∂_x^2 v(t,X_t^θ)dt.

 By eq:f-derivs, ∂_x^2 f>0. Thus by Itô's lemma,
 we have the maximum principle: 
 
    ∂_x^2 v(t,x) = _X_t=x( ∂_x^2 f(X_T)+ ∫_t^Tξ”(s)μ(s)∂_x^2v(s,X_s)ds)>0 .

 This immediately implies that p is strictly increasing, so that K is positive-definite as desired. 
 
 In the remaining case, σ^2=T=1, and one can explicitly solve the PDE to find that
 
    P_β,T(μ,λ)=β^2/2∫_0^T ξ”(s)μ(s)(T^2-s)ds

 which is evidently maximized at μ= δ_0 and uniquely so if and only if T^2>0.
 
In the subsequent it will be useful to define the following log-moment 
generating function,

    ψ(θ)=log∫ e^θ^2d.

Observe that, ψ is continuous and monotone, with 

    lim_θ→∞ψ(θ)/θ  =,      lim_θ→-∞ψ(θ)/θ  =.

Note that in the case that =, ψ is constant.

For every μ,λ,β,ξ, and T∈(,), we have that

    v_μ,λ≥ψ( λ).



By the parabolic comparison principle (lem:ppde-reg-zero-temp), we see
that 
v_μ,λ(t,x)≥ v_δ_T,λ(t,x). Thus

    v_μ,λ(0,0)≥log∫ e^( B_β^2ξ'(T)+λ^2)d,

where B_t is a standard Brownian motion run until time t.
Using again the convexity of the map 

    x↦log∫ e^ x+λ^2d,

(see eq:f-derivs) we have that this is lower bounded by 

    v_μ,λ(0,0)≥log∫ e^λ^2d=ψ(λ)

as desired.



That a minimizer is unique follows by lem:strict-convexity-finite-beta. 
That a minimizer exists can be seen as follows.
Firstly, μ∈([0,1]) which we may equip with the weak-* topology. 
Thus it suffices to show that we may restrict λ to a compact set if T∈(,),
as in the other case we may take λ=0.
To this end, suppose first that T∈(,). 
Observe that for any μ, we then have that by lem:mgf-bound

    P_β,T(μ,λ)≥ψ(λ)-λ T-∫ sξ”(s)ds.

Thus the limit of the right hand side as λ→±∞ is infinity. Thus we may restrict
to a compact set. The result then follows by (lower semi)continuity of P_β,T.

Let us now prove  eq:G-minimizing. 
Let γ_t=(μ_t,λ) be a path such that μ_t 
is weakly differentiable on (0,1) and right weakly differentiable at t=0 in the sense that

    lim_t→ 0^+μ_t-μ/t = μ̇

weak-* as measures for some signed measure μ̇. 

By the same argument as in <cit.>,
we have that P_β,T(μ_t,λ) is right differentiable at t=0, and 

    d/dt^+P_β,T(μ_t,λ)=∫ G(t) dμ̇.

The only difference is to notice that since ∂_x f from is uniformly bounded in (x,λ) by (<ref>), ∂_x u is uniformly bounded in
(t,x,λ) as well, using lem:ppde-reg-zero-temp.
Thus by the first order optimality conditions for  convex functions,

    ∫ G(t) d μ̇≥0

for all such paths. Taking μ̇= μ_1-μ_0 yields eq:G-minimizing. To obtain (<ref>), we differentiate
the variational formula in λ and use that v is classically differentiable in λ as explained above (<ref>).

It remains to prove eq:fixed-point-q.
Since G is differentiable, we see that

    ξ”(q)/2( (∂_x v)^2(q,X_q)-q)=0.

This yields eq:fixed-point-q for q≠0, and for q=0 if ξ”(0)≠ 0. 
To see this for the point q=0, it suffices to show that

    (∂_x v(0,0))^2 ≤inf(μ).

To this end, let q_0=inf(μ). Observe that by eq:G-minimizing,

    G(q_0)≤ G(q_0+)

for >0 sufficiently small. Averaging this inequality
and using the definition of G, we see that there is some 
t∈(q_0,q_0+) such that

    (∂_x v(t,X_t))^2 ≤ t.

As observed in eq:max-princ, ∂_x^2 u>0. So by Itô's isometry, t↦ (∂_xv)^2(t,X_t) is strictly increasing.
Thus 

    (∂_x v)^2(0,0)=(∂_x v)^2(0,X̂_0)≤ t≤ q_0+.

Sending →0 yields eq:support-lower-bound.
The remaining cases can be proved in an identical fashion.





 §.§ Γ-convergence of the local free energy

We now turn to proving the Γ-convergence of the local free energy functional.
We begin by recalling the notion of sequential Γ-convergence. 


Let X be a topological space. We say that a sequence of functionals F_n : X → [- ∞, ∞] sequentially Γ-converges to F : X → [-∞, ∞] if 


  * The Γ-lim inf inequality holds: For every x and sequence x_n → x, 
    lim inf_n →∞ F_n(x_n) ≥ F(x).
 

  * The Γ-lim sup inequality holds: For every x, there exists a sequence x_n → x such that 
    lim sup_n →∞ F_n(x_n) ≤ F(x).


For a sequence of functionals F_β indexed by a real parameter β, we say that F_β sequentially Γ-converges to F if for any sequence β_n →∞, the sequence F_β_n sequentially Γ converges to F. 






For every T∈[,], we have that 

    _β, TΓ→_T.




Recall from (<ref>) that we may write _β,T in the form

    _β,T(ν,λ)=_β,T(ν,λ; 0,0) +ℓ_1(λ)+ℓ_2(ν),

where ℓ_i are both linear functionals that do not vary in β. 
For (t,x) ∈ [0,T]×ℝ, set 

    _T(ν,λ;t,x) = u_ν,λ(t,x).

For (t,x) ∈ [0,T]×ℝ, recall the functional ℱ_β,T(·, ·; t,x) from (<ref>), and note that Theorem <ref> immediately implies that ℱ_β,T(·, ·; 0,0) Γ→ℱ_T(·, ·; 0,0). The desired conclusion follows immediately using (<ref>) and the stability of Γ-convergence under continuous perturbations <cit.>.




Our interest in the Γ-convergence of these functions
is of course to understand convergence of minima and minimizers.
To this end, we need a precompactness theorem for such minimizers.




If T∈(,), then _β,T has a unique  sequence of minimizers
(ν_β,λ_β) which is precompact. Furthermore
any limit point of this sequence converges to a minimizer of _T(ν,λ).
If T= or , then the family ν_β is precompact, we
may take λ=0,
and any limit point of this
sequence is such that (ν,λ) is a minimizing pair.



Let us now turn to the precompactness theorem thm:conv-minimizers-thm. 
Before we begin the proof, 
we need the following theorem regarding the compactness of λ. 


There is a β_0(Σ) such that if β≥β_0, 
T∈(,), and _β,T(λ,ν)≤ M, then 

    λ≤M+1/min{-T,T-}.



Observing that the last term in (<ref>) is negative, 

    M≥ u_ν,λ(0,0)-λ T.
 
 In this case, 
lem:mgf-bound implies that 

    M ≥1/βψ(λβ)-λ T.
 
Observe that there is a c>0 that depends only on Σ such that

    1/βψ(βλ)≥max{λ,λ} -c/β.

Taking β_0=c^-1 and re-arranging yields the result.



We are now in the position to prove the precompactness theorem.


That there is a unique minimizing pair for finite β is proved in lem:optimality-finite-beta.
We begin by studying the precompactness of this sequence.

Let us first show that the collection of minimizing ν_β are precompact.
 To this end, observe that,
by eq:loc-fe-conv,
 F(β) is the point-wise limit of free energies. 
As functions, these are convex and smooth in β.
Furthermore, they satisfy
 
    ∂_β F(β;T) = lim_N→∞ F'_N(β;T)=lim_N→∞1/N⟨ H_N(σ)⟩≤ C(ξ).

Here ⟨·⟩ denotes integration with respect to the Gibbs measure,

    η({σ})∝ e^β H_N

and we use that 
the expect normalized maximum of H_N is bounded by a function of ξ alone <cit.>. 

 By thm:beta-deriv-overlap and Fubini's theorem, it then follows that 
 
    ∫ξ'(t)βμ(t)dt≤ C(ξ)

 By the Harris-FKG inequality, this implies that the total variation norm of ν_β satisfies ν_β≤ C'(ξ). Thus the minimizing ν_β
 are pre-compact.
 
We now study the pre-compactness of λ_β. 
Suppose first that T∈(,). In this case,  there is some M such that  eventually
 
    _β,T(ν_β,λ_β)≤ M.

 Similarly by the above estimate, we may assume that ν_β≤ C. 
 The result then follows by  eq:coercive-lambda-bound.
The case T= and T= are obvious. 
 
 


 §.§ Variational representation for the Ground State Energy

With the above in hand, the proof of  Theorem <ref> is essentially immediate.  

   cor:gamma-conv-main-thm establishes Γ-convergence of the functional 𝒫_β,T to 𝒫_T. 
Furthermore, the minimizers of 𝒫_β,T are pre-compact by Theorem <ref>. Thus by the fundamental theorem of Γ-convergence, the minima converge, i.e., 

    inf_ν∈𝒜_T, λ∈ℝ𝒫_β,T(ν, λ)  →inf_ν∈𝒜_T, λ∈ℝ𝒫_T(ν,λ)

as β→∞. Lemma <ref> implies 

    1/β F_N(β, ξ; A_N) - log |Σ|/β≤  GS_N(A_N) ≤1/β F_N(β, ξ; A_N) + log |Σ| /β.

We let N→∞, followed by β→∞ and use (<ref>) to derive that 

    lim_N →∞  GS_N(A_N) = inf_ν∈𝒜_T, λ∈ℝ𝒫_T(ν,λ) =: E(ξ;T).

Another application of Lemma <ref> implies that 

    |1/β F(β, ξ; T) - E(ξ; T) | ≤log |Σ|/β.

Thus the family {1/β  F(β , ξ; ·) : β >0 } is uniformly convergent, and thus the supremum converges, 

    sup_T1/β F(β, ξ ; T) →sup_T E(ξ ; T)

when β→∞. Finally, using Lemma <ref>, we have

    lim inf_N →∞ GS_N(Σ^N)    ≥lim inf_N →∞ F_N(β, ξ ) - log |Σ|/β
       ≥lim inf_N →∞ F_N(β, ξ; T) - log |Σ|/β = F(β,ξ; T)  - log |Σ|/β.

We let β→∞ and take supremum over T to derive the lower bound 

    lim inf_N →∞ GS_N(Σ^N) ≥sup_T E(ξ; T).

To derive the upper bound, we observe that  

    lim sup_N →∞ GS_N(Σ^N) ≤lim sup_N →∞ F_N(β, ξ) + log |Σ|/β = F(β, ξ) + log |Σ|/β.

It is easy to see that F(β, ξ) = sup_T F(β, ξ; T) and then we let β→∞ to obtain 

    lim sup_N →∞ GS_N(Σ^N) ≤sup_T E(ξ, T).
 



§ ANALYSIS OF THE ZERO TEMPERATURE PROBLEM



 
In this section, we briefly turn to calculating the first variation of the functional _T from (<ref>)  



Fix ν_0,ν_1∈ with ν_1({T})=ν_0({T}) and λ.
Let ν_θ=(1-θ)ν_0+θν_1. We have that

    d/dθ|_θ=0_T(ν_θ)=1/2∫_0^Tξ”(t)( u_x(t,X_t)^2-t)d(ν_1-ν_0).




Let m_θ=(1-θ)m_0+θ m_1. Let X_T^α,m_θ
be the process in lem:dpp corresponding to m_θ with initial
data x=0. Consider the auxiliary function Ξ:_T×[0,1]→

    Ξ(α,θ)     =[ψ(X_T^α,m_θ,λ+ξ”(T)/2c)-1/2∫_0^Tξ”(s)m_θ(s)α_s^2ds].

Since ψ is continuous, it is clear that Ξ is jointly continuous
in (α,θ). 
Consider the function 

    ψ(x,y)=max_∈Σ[  x+^2y ].

Recall from lem:psi-diff that ψ is a.e. differentiable
with a.e. continuous derivative which satisfies

    ∂_xψ(x,y)=_*,

where _* is such that ψ(x,y)=_*x+_*^2y. 
Thus ∂_θΞ(α,θ) is jointly continuous
in the pair θ,α. By lem:dpp, if we let

    α_*(θ)=u_x^θ(s,X_s^θ),

then these achieve optimality in (<ref>). Furthermore, the map θ↦α_*(θ)
is continuous by lem:continuity. Thus by lem:wei-kuo, we have that 

    d/dθ|_θ=0_T(ν_θ)=1/2∫_0^Tξ”(t)( u_x^2-t)(m_1(t)-m_0)dt,

as desired.




Our next result is a convexity property of the zero temperature functional _T, and should be compared to Lemma <ref>. 


For λ∈ℝ and ν∈𝒜, ν(t) = m(s)  t + c δ_T, 
the ground state Parisi functional _T is convex in (m,c,λ). 

Combining Lemmas <ref> and <ref> immediately yields the following corollary. 


Let λ_*, ν_* be any minimizer of _T. Set ν_*(s) = m_*(s)  s + c_* δ_T. Consider any measure ν_1(s) = m_1(s)  s + c_* δ_T and define the path ν_θ = θν_1 + (1- θ) ν_*. Then we have, 

    /θ^+_T(λ_*, ν_θ) |_θ=0≥ 0.



 
 

§ PROOF OF THEOREM <REF>

 
 We prove Theorem <ref> in this section. 
Recall the interpolating free energy F_N(v,β;α) from  (<ref>). Further, recall that by Panchenko's theorem <cit.>, see (<ref>),

    F_N(v,β ; α )→ F(v,β; α),

where F(v,β; α) is the local free energy (<ref>) corresponding to ξ(t)=2 t^2,
Σ=Σ(v,α) and 
T=T(v,α).[We note here that we may take _N =0 in (<ref>). The “fattening” by _N was necessary in <cit.>, only because they needed to work with self-overlaps which were possibly un-realizable, e.g., irrational. In our setting, however, we are implicitly in the regime where the set with self-overlap T is non-empty infinitely often in N. ]



Our proof of Theorem <ref> will crucially use the ground state energy functional (<ref>).  
We adapt the ground state energy functional  to this setting for the convenience of the reader. Fix v ∈ [0,1] and define the functional 𝒫(·, · ;v) : ℝ×𝒜_T →ℝ such that 

    𝒫(λ, ν; v) = - λ T + ũ_λ, ν(0,0) - 2 ∫_0^T s ν(s),

where we set T:= T(v) as in (<ref>), and where for  ν(s) = m(s)  s + c δ_T, ũ_λ,ν solves 

    ∂_t ũ_λ, ν + 2 ( Δũ_λ,ν + m(t) (∂_x ũ_λ,ν )^2 )=0,    (t,x)∈ [0,T]×
    ũ_λ,ν(T, x) = f̃(x,λ,c).

where 

    f̃(x,λ,c) = | x - 2 ( λ + 2c )√(v) (2 α -1) | - √(v) (2 α -1 ) x + ( λ + 2c) ( 1 + v(2 α -1)^2 ).


 
 

Recall the local Parisi functional 𝒫_β,T(ν, λ) (<ref>), and the pre-compactness of its minimizers, as established in Theorem <ref>. 
Next, we will establish the following crucial property about the minimizers. 


Fix any α∈ (0, 1/2) and v ∈ (0,1). Let (ν_*, λ_*) be any limit point of the minimizers (ν_β, λ_β). Then ν_* ≠ 0. 

We defer the proof of this result  to the end of the section.
Given these results, we are now in a position to establish Theorem <ref>. 




 By  Gaussian integration of parts for Gibbs measures <cit.>, we observe that 
 
    ∂_β F_N(v,  β ; α) =2 β[T^2 - ⟨ R_12^2 ⟩_v].

 
 We note that for any fixed v, α, F_N( v, β; α ) is convex in β and converges to F(v, β; α ), which is differentiable in β by Theorem <ref>. Thus by Griffith's lemma for convex functions, 
 
    ∂_β F_N(v, β; α) →∂_β F(v, β; α).

 Using Theorem <ref>, we have 
 
    ∂_β F(v, β; α) =2 β∫ (T^2 - x^2 ) μ_β(x),

 where μ_β is the minimizer of the local free energy functional 𝒫_β,T. 
 The minimizers of 𝒫(·, ·; v) are functions of v, but for ease of notation, we will keep this dependence implicit.  
 
 
We set ν_β(t) = βμ_β([0,t])  t, where μ_β is unique minimizer of 𝒫_β,T. Let (ν_*, λ_*) be any limit point of (ν_β, λ_β).  Recall that by Theorem <ref>, such a limit point exists. 
Using lem:convergence and  Lemma <ref>, we have,  that for any subsequence converging to this limit point, 
 
    lim_k →∞β_k∫ (T^2 - x^2) μ_β_k(x)  =  ∫ 2 x ν_*(x)>0.

This observation implies  
 
    lim inf_β→∞β∫ (T^2 - x^2) μ_β(x)>0 .

 Setting 
 
    C_1(α) = lim inf_β→∞β∫ (T^2 - x^2) μ_β(x) >0

 gives us the desired constant, and completes the proof. 
 

It remains to prove Lemma <ref>. We outline this in the rest of the section. 



 Fix v ∈ (0,1) and assume for the sake of contradiction that ( 0,λ_*)  is a limit point of (ν_β,λ_β). By Theorem <ref>, (λ_*, 0) is a minimizer of 𝒫(·, ·; v) and λ_* is finite. 
For any probability measure μ on [0,T], we can construct the path on measures ν_θ =  (1- θ) ν_1, where we set ν_1(s) = μ([0,s])  s. In this case, if we apply Fubini's theorem to  Lemma <ref>, we obtain

    /θ^+𝒫( ν_θ, λ; v) |_θ=0= ∫ G_v  μ  ,
 
where G_v is defined as

    G_v(t)=∫_t^Tξ”(s)( (∂_x ũ)^2(s,X_s) - s)ds,

where ũ is the solution to (<ref>) corresponding to 0. 
As 0 as assumed to be a minimizer, an application of Corollary <ref> implies 
∫ G_v μ≥ 0. Further, μ is an arbitrary probability measure on [0,T], 
and thus G_v(s ) ≥ 0 on [0,T]. We will establish that G_v(T) = G'_v(T) = 0 while 
lim_t ↑ T G”_v(t) = ∞. Thus G_v(t) is negative for t sufficiently close to T, and this yields a contradiction. 


To this end, we note that the definition of G_v immediately implies that G_v(T) =0. We will next establish that 

    [(∂_xũ)^2(T, B_4T)] =T,

which implies G'_v(T) =0. To this end, note that the weak derivatives of ũ satisfy the relation

    (∂_x ũ)^2 (T ,x) = ∂_λũ(T,x).

Now, note that λ_β are pre-compact, and thus bounded, implying that λ_* is finite. 
Differentiating the functional in λ as in lem:optimality-finite-beta, and setting this to zero,  we obtain 

    T = ∂_λ_*ũ(0,0) = [∂_λ_*ũ(T, B_4T) ] = [(∂_x ũ)^2(T, B_4T)],

where the second equality follows from the observation that ∂_λ_*ũ satisfies the heat equation with boundary data ∂_λ_*ũ(T, x). 

Finally, we prove that lim_t ↑ T G_v”(t) = ∞. We have, for t < T, 

    G_v”(t) = 4 ( / t [( ũ_x)^2(t, B_4t)] - 1 ).

Using Itô Lemma's we immediately obtain that for such t,

    / t[(ũ_x)^2(t, B_4t)] =4 [ (ũ_xx)^2(t,B_4t)].

Note that ũ_xx solves the heat equation 

    ( ∂_t  +  4/2Δ )ũ_xx = 0     
    ũ_xx(T, · ) =2  δ_2 λ_* a(v)(·)

in the sense of distributions, where a(v) = √(v)(2α -1). In particular, by a standard argument <cit.> (or an explicit computation) we have,

    ũ_xx(t,x) = 2/√(8π (T-t) )exp( - (x- 2 λ_* a(v) )^2/8(T-t)),

for t < T. Finally, this immediately implies 

    [(ũ_xx)^2(t, B_4t)  ] = 1/2π (T-t)[exp( - (B_4t - 2 λ_* a(v))^2/4(T-t)) ] = 1/2 π√(T^2 - t^2)exp(-  ( λ_* a(v) )^2 /T+t).

We let t ↑ T to complete the proof. 







§ A CONJECTURE REGARDING THE SHARP CONSTANT IN THM:CUT_DIFFERENCE

In this section, we record the conjecture regarding the sharp constant in Theorem <ref>. To this end
, define
 
    Σ(v,α)    = { 1- √(v) ( 2 α -1) , - 1 - √(v) (2α -1) }, 
    
     T(v,α)    = α (1 - √(v) (2 α -1 ))^2 + (1 - α) (1 + √(v)(2 α -1 ))^2 ,

and then we 
have the following.


We have that

    lim_d→∞lim_N→∞_α(G(N,d/N))-_α(d)/√(d)N=K(α),

where

    K(α)=2(2α-1)^2∫_0^1 (1 -√(v))/√(v)ν_v([0,T(v,α)])dv.

and where ν_v is a minimizer of _T(v,α).


The motivation for this conjecture is as follows.
By lem:int_by_parts
one formally expects that

    lim_d→∞lim_N→∞   _α(G(N,d/N))-_α(d)/√(d)N
               =lim_β→∞lim_N→∞ 2(2α-1)^2∫1-√(v)/√(v)βT(v)-R_12_v dv,

In the physics literature, a basic tenet of the replica symmetry breaking method is  <cit.> that in generic situations
we have the correspondence

    lim_N→∞T-R_12=β∫ (T-x)dμ_β(x),

where μ_β is such that βμ_β dt the minimizer of _β,T from (<ref>). 
The conjecture then comes from combining this correspondence with thm:conv-minimizers-thm. 
The question as to when this correspondence holds is a major open problem in the mathematical study
of mean field spin glasses. For references in this direction see <cit.>.



§ BASIC PROPERTIES OF THE PARISI PDE

In this section, we briefly review the properties of solutions to Parisi-type PDEs.




There is a unique weak solution to eq:zero-temp-pde, which satisfies 


  * ∂_x u∈ L_t^∞L_x^∞ with ∂_x u_L_t,x^∞≤∂_x f_L_t,x^∞≤ C(Σ)

  * For any T_0<T, u is continuous in space time, with smooth
bounded spatial derivatives satisfying 

    ∂_x^nu_L^∞([0,T_0]×ℝ )≤ C(T_0,T,Σ)

and is weakly differentiable in time with ∂_t∂_x^nu_L^∞([0,T_0]×ℝ)≤ C(T_0,T,Σ).

Furthermore, if u,v are two solutions corresponding to μ and
ν respectively where μ,ν∈ are of the form 

    μ    =m_1dt+cδ_1
    ν    =m_2dt+cδ_1

then

    u-v_L_t,x^∞≤ C(ξ)m_1-m_2_L^1

and we have the parabolic comparison principle:
 if m_1≤ m_2 pointwise for all t then u≤ v. Finally, the same results hold for the weak solutions u to (<ref>).


This is a standard argument, see, e.g., <cit.>. For the reader's convenience
we briefly sketch the main points. We begin first with the existence
for a dense class of ν's. Assume that ν=m(t)dt+cδ_1.
The existence for m which is a bounded step function with finitely
many jumps, can be seen by an application of the Cole-Hopf transformation.
That the derivative is bounded in space for such solutions can be
seen either by explicit differentiation or the maximum principle.
This yields

    ∂_x u_L_t,x^∞≤∂_xf_L^∞_x.

By lem:psi-diff,  f is differentiable in x Lebesgue a.e. 
and  ∂_xf ∈ L^∞. Furthemore,

    ∂_xf=argmax_ϵ∈Σ{ xϵ+(λ+c/2ξ”(T))ϵ^2}

a.e. which is bounded by a constant that depends at most on Σ.
Observe furthermore, that the regularity claims in this setting can
be seen by explicit differentiation. 

We now prove the Lipschitz estimate in m for m as above and the corresponding comparison principle. This
follows by the same argument as in <cit.>. Indeed,
if w=u-v then w solves 

    w_t+ξ”/2(w_xx+m_1(u_x+v_x)w_x+(m_1-m_2)v_x^2)     =0

with initial data w(T,x)=0. Since u_x,v_x are uniformly
lipschitz on any subinterval of the form [0,T_0]⊂[0,T),
and m_i(t) are both uniformly bounded on such sub intervals,
we see that we may solve the SDE 

    dX_t=ξ”m_11/2(u_x+v_x)(t,X_t)+√(ξ”)dW_t,

where W_t is a standard Brownian motion. Observe that w has
the same regularity as u and v. In particular, by the smoothing
property of the heat equation, we have that on [0,T_0]×
w,w_x,w_xx∈ C_b([0,T_0],), and w is weakly differentiable
in time with w_t∈ L^∞ which is Lipschitz in x uniformly
in t. Thus we may apply Itô's lemma (see, e.g., <cit.>) to obtain 

    w(t,x)=_X_t=x(∫_t^T_01/2ξ”(s)(m_1-m_2)v_x^2)≤ C(Σ,ξ)m_1-m_2_L^1.

Similarly, sending t→0 and T_0→ T, yields the desired conclusions. 

We now show the existence for general m. By an extension argument,
if m_n→ m in L^1, then u_n→ u for some function
u. To see that u is a weak solution observe that it suffices
to show that 

    m_n(∂_xu_n)^2→ m(∂_xu)^2

 in the sense of distributions. This follows since ∂_xu_n
are uniformly bounded. To prove uniqueness, observe that by a similar
Duhamel's principle argument to <cit.> using the modified
heat kernel estimates from <cit.>, we have that 

    ∂_xw_L^∞([t,T]×ℝ)≤u_x+v_x_L^∞_t,x∫_t^T∂_xw_L^∞([s,T] ×ℝ)C(Σ,ξ)/√(s-t)m(s)ds.

Since m(t) is monotone and blows up at most at T, the integrand
is integrable, so that by Gronwall's inequality, ∂_xw=0.
Thus we have the existence and uniqueness of u and the regularity
of u_x. The regularity of the higher spatial derivatives follows
by the smoothing property of the heat semigroup, and the regularity
in time follows from rearranging eq:zero-temp-pde and using the fact that
on T_0<T, m is bounded. 



The map ν↦ u_x is continuous in the topology of pointwise
convergence. In particular, if ν_n→ν weak-*, then u^n→ u
and ∂_xu^n→∂_xu uniformly on compacta.


By the same Duhammel's principle and parabolic Bootstrapping argument
as in  <cit.>, there are a continous function
{F_i(x,y)}_i∈[3] such that for every T_0<T, 

    ∂_x^iu_L^∞([0,T_0]×)   ≤ F_i(ν(T_0),ν({1})).

Since the maps ν↦ν([0,t]) and ν↦ν({1})
are upper semi-continuous in the weak-* topology on , we see
that if ν_n→ν, weak-* the family {u^n} and {∂_xu^n}
are uniformly lipschitz in space. Furthermore, since they weakly solve
the Parisi PDE and the (spatially) differentiated form of this equation,
we see that they are also uniformly lipschitz in time. Thus the families
are both equicontinuous. Thus u^n→ u and ∂_xu^n→∂_xu
uniformly on compacts by the Arzela-Aiscoli theorem. 





§ THE WEAK-* TOPOLOGY ON _T

In the preceding section, we frequently work with the space _T equipped with
the weak-* topology. We provide here certain basic properties
of this space. 


Suppose that ν_β→ν with ν_β = m_β(t)dt+c_βδ_T and ν=m(t)dt+cδ_T. We then have the following.


  (i) The measure dm_β converges vaguely to dm. That is, for every t<T, 
that is a continuity point of m,

    m_β(t)→ m(t).


  (ii) Let q_β→1  be such that m_β(q_β^-)→ m(1^-), where the - denote the left limit,
and suppose that m(1^-)<∞. Then

    c = lim_[q_β,T]β(T-t)dm_β.
 

  (iii) For any f∈ C^1([0,T]),

    limβ∫ f(T)-f(t)dm_β = ∫ f' dν.


  (iv) For any bounded Borel measurable ψ with lim_s↑ Tψ(s)=ψ(T),

    ∫ψ(s)dν_β(s)→∫ψ(s)dν(s).




The first three points were proved in <cit.>. It remains to prove the last point.
Let ψ be as above.  Without loss of generality, assume that ψ_∞≤1.
Observe that by (1), since ν_β→ν  weak-*, m_β(t) → m(t) Lebesgue
almost surely on [0,T). Furthermore,  for any t ∈ [0,T), lim sup_β→∞ m_β(t) ≤ m(t). 
Thus, for any t ∈ [0, T),we have that, 

    ∫_0^t ψ(s) m_β(s)  s →∫_0^t ψ(s) m(s)  s,

 as β→∞, by the dominated convergence theorem.
Therefore, 

    | ∫_0^Tψ(s) ν_β(s) - ∫_0^Tψ(s) ν(s) | 
       ≤|  ∫_0^tψ(s) ν_β(s) - ∫_0^tψ(s) ν(s)| + |  ∫_t^Tψ(s) ν_β(s) - ∫_t^Tψ(s) ν(s) |.

By (<ref>),

    lim sup_β→∞| ∫_0^Tψ(s) ν_β(s) - ∫_0^Tψ(s) ν(s) | ≤lim sup_β→∞|  ∫_t^Tψ(s) ν_β(s) - ∫_t^Tψ(s) ν(s) |.

Finally, by triangle inequality, we have, 

    |  ∫_t^Tψ(s) ν_β(s) - ∫_t^Tψ(s) ν(s) | ≤ν_β([0,T]) max_t ≤ s ≤ T | ψ(s) - ψ(T)| + | ν_β((t, T])- c | + ∫_t^T m(s)  s.

We let β→∞, and let t ↑ T  to conclude that 

    |  ∫_t^Tψ(s) ν_β(s) - ∫_t^Tψ(s) ν(s) |  → 0

as β→∞. This completes the proof. 




§ CONSTRAINED GROUND STATES ON THE DISCRETE HYPERCUBE

In this section, we derive a variational representation for the ground state of a mixed Ising spin glass, with an additional magnetization constraint. For σ∈{± 1}^N, we set m(σ) = 1/N∑_iσ_i. 

 For any a ∈[-1,1]∩ℚ and ϵ_N→0,
we have, for ξ convex,

    lim_N→∞max_σ∈{±1}^N
    
    m(σ)∈[a-ϵ_N,a+ϵ_N]
    H(σ)/N=inf_ν,h[𝒫^2(ν,h)-a· h],

where 𝒫^2 is given in (<ref>). 


The proof of this result follows in a few steps. For a∈[-1,1], define

    G_N(a;η)     =max_σ∈{±1}^N
    
    m ∈ [a- η, a +η]
    H(σ)/N, 
    
    E_N(h)     =max_σ∈{±1}^N[H(σ)/N+hm(σ)].

As shown in <cit.>, we have 

    lim_N →∞ E_N(h)=E(h)=inf_ν𝒫^2(ν,h).

We also have the following result which is folklore in the spin glass literature.
We include a proof for the convenience of the reader. 

For any η>0 and a∈[-1,1], we have 

    lim_η→0lim_N→∞G_N(a;η)=G(a)

is well defined. Furthermore, G(a) is concave and continuous for all a∈[-1,1]. 



The result follows by a modification of the Guerra-Toninelli argument
<cit.>. We first show existence. Fix η>0, and consider

    G_N+M(a;η)=max_m∈ [a- η, a+ η]H_N+M(σ)/N+M.

For N,M sufficiently large, {σ∈{± 1}^N+M:  m(σ) ∈ [a-η, a+ η] } is non-empty,
so that this is well defined.

We decompose σ∈{± 1}^N + M as σ = (ρ, ϵ), with ρ∈{± 1}^N, ϵ∈{± 1}^M.
Consider now the interpolating Hamiltonian for σ=(ρ,ϵ),
defined by

    H_N+M,t(ρ,ϵ)=√(t)H_N+M(σ)+√(1-t)(H_N(ρ)+H_M(ϵ)),

for t∈ [0,1], where we view the Hamiltonians at different N's to be independent.
For σ^i=(ρ^i,ϵ^i) with i=1,2, let 

    R_12=1/N+M(σ^1,σ^2),   R_12^ρ=1/N(ρ^1,ρ^2),   R_12^ϵ=1/M(ϵ^1,ϵ^2).

For any β>0 define

    ϕ_β(t)=1/β(N+M)log∑_m∈ [a-η, a+η]e^β H_N,t(σ).

This satisfies  

    ϕ'_β(t)=1/N +M⟨∂_tH_N,t⟩ =β/N+M ⟨ C_11-C_12⟩

with 

    C_12=[∂_tH_t(σ^1)H_t(σ^2)]=(N+M)ξ(R_12)-Nξ(R_12^ρ)-Mξ(R_12^ϵ),

where the second equality follows using Gaussian integration by parts.
Note that C_11=0. Furthermore, since R_12=λ R_12^ρ+(1-λ)R_12^ϵ
with λ=N/N+M, we have 

    ξ(R_12) ≤λξ(R_12^ρ)+(1-λ)ξ(R_12^ϵ)

by convexity of ξ. Thus ϕ'_β(t)≥ 0, so that
ϕ_β(0)≤ϕ_β(1).
Sending β→∞, this yields

    max_m∈ [a-η, a+ η]H_N+M(σ)/N+M≥max_m∈ [a- η, a+ η]H_N+H_M/N+M

Now note that since m(σ)=λ m(ρ)+(1-λ)m(ϵ),
we have that 

    {σ=(ρ,ϵ):m(ρ)∈ [a-η, a+ η],m(ϵ)∈ [a-η,a+η]}⊆{σ:m(σ) ∈ [a-η, a+η]}

Consequently, G_N+M(a;η)≥λ G_N(a;η)+(1-λ)G_M(a;η).
Thus the sequence NG_N(a;η) is super-additive, so that G_N(a;η) has a limit. 


To establish continuity of G(·; η), fix a,b ∈ [-1,1], and η >0. For each σ∈{ m(σ) ∈ [a-η, a+ η]}, let π(σ) denote a configuration in {m(σ) ∈ [b - η, b+ η]} which minimizes the Hamming distance. Similarly, for each σ∈{m(σ) ∈ [b-η, b+ η]}, let π'(σ) denote the configuration with magnetization in [a-η, a+ η] which minimizes the Hamming distance. Recall that Var(H_N(σ) - H_N(τ) )= 2N (ξ(1) - ξ(R_12 )), where N · R_12 = (σ, τ). Thus 

    1/Nmax{max_m∈[a-η, a+ η]Var( H_N(σ) - H_N(π(σ))  ) , max_m∈[b-η, b+ η]Var( H_N(σ) - H_N(π'(σ))  ) }≤ C(ξ') |a-b|

uniformly in N, where C(ξ') is a universal constant dependent on ξ'. 
We have, 

    |G_N(a;η) - G_N(b; η)| ≤1/Nmax_m∈[a-η, a+ η] | H_N(σ) - H_N(π(σ)) | + 1/N𝔼max_m∈[b-η, b+ η]  | H_N(σ) - H_N(π'(σ)) |.

Note that for any collection of dependent, centered gaussians { Z_i: 1≤ i ≤ r}, 𝔼[max |Z_i|] ≤ 2 𝔼[max Z_i] ≤ 2 √(2 σ^2 log r), where σ^2 = max_1≤ i ≤ rVar(Z_i). Applying this bound individually to the two terms in the display above, with r ≤ 2^N, we get 

    |G_N(a;η) - G_N(b; η)| ≤ C'(ξ') √(|a-b|)
 
for some universal constant C'(ξ')>0, uniformly in N. 
Finally, we let N →∞, and obtain the continuity of G(·;η). 


To obtain concavity, let λ∈[0,1] be rational and work along a subsequence
such that λ N is an integer. 
 By the same interpolation
argument, we obtain that 

    G_N(λ a+(1-λ)b;η)≥λ G_λ N(a;η)+(1-λ)G_(1-λ)N(b;η).

Sending N→∞ yields

    G(λ a+(1-λ)b; η)≥λ G(a; η)+(1-λ)G(b; η).

Using the continuity of G(·; η), we obtain the concavity of  G(·;η) for each η. 

Finally, since the map η↦ G_N(a;η)
is increasing, we see η↦ G(a;η) is as well. Thus the pointwise limit G(a)=lim_η→0 G(a;η)
is well-defined, continuous, and concave.


Since G(a) is continuous, we may apply a standard covering argument
(along with the definitions of G_N and E_N) to obtain

    E(h)=max_a∈[-1,1]{ha+G(a)}.

Extending G(a) by -∞ off of [-1,1], we have, by
concavity of G(a), 

    G(a)=inf_h[E(h)-ha].

The result then follows by (<ref>). 


plain


