# On a nonhierarchical generalization
of the Perceptron GREM

Nicola Kistler  Nicola Kistler
J.W. Goethe-Universität Frankfurt, Germany<EMAIL_ADDRESS>and
Giulia Sebastiani  Giulia Sebastiani
J.W. Goethe-Universität Frankfurt, Germany<EMAIL_ADDRESS>
###### Abstract.

We introduce a nonlinear, nonhierarchical generalization of Derrida’s GREM and
establish through a Sanov-type large deviation analysis both a Boltzmann-Gibbs
principle as well as a Parisi formula for the limiting free energy. In line
with the predictions of the Parisi theory, the free energy is given by the
minimal value over all Parisi functionals/hierarchical structures in which the
original model can be coarse-grained.

###### Key words and phrases:

Mean Field Spin Glasses, Large Deviations, Gibbs-Boltzmann and Parisi
Variational Principles

###### 2000 Mathematics Subject Classification:

60J80, 60G70, 82B44

This work has been supported by a DFG research grant, contract number
2337/1-1.

##  1\. Introduction

The study of mean field spin glasses, started by physicists in the 1970’s and
culminated in the Parisi theory [6], has over time revealed a rich and
challenging mathematical structure. Despite the enormous progress over the
last decades, the whole Parisi picture and its presumed universality for mean
field models still remains not fully understood. Indeed, for the prototypical
models of the theory such as the Sherrington-Kirkpatrick [SK] model [15], a
rigorous treatment via large deviations techniques within the classical Gibbs-
Boltzmann formalism is still lacking, and one has to resort to sophisticated
machinery, in particular Guerra’s interpolations [8, 16] and the Ghirlanda-
Guerra identities [7]. These tools are remarkably efficient but cannot
provide, by their own nature, insights for given realization of the disorder.
We refer the reader to [9] and references therein for a comprehensive account
of the state of the art for the SK-model111A treatment of spin glasses which
is somewhat complementary to the Parisi theory goes through the TAP-Plefka
framework [17, 11]. The rigorous studies which bypass the interpolations/GG-
identities employ the Kac-Rice formula and some ensuing large deviations
estimates for the complexity/number of critical points of Gaussian random
fields. This type of analysis is to date however limited to spherical models
with REM-like ultrametric structure, see [13, 14] and references..

One of the most puzzling features of the Parisi theory is the ultrametricity,
namely the emergence in the infinite volume limit of hierarchical structures
closely related to the generalized random energy models, the GREM, introduced
by Derrida in the 1980’s [4, 5]. For a large class of SK-type Hamiltonians,
the ultrametricity has meanwhile been put on rigorous ground by Panchenko
[10]. The analysis relies crucially on the Ghirlanda-Guerra identities.

In order to shed some light on the origin of ultrametricity, simplified models
for spin glasses which are amenable to a rigorous solution via large deviation
techniques have been introduced by Bolthausen and the first author in [1, 2,
3]: the first paper deals with a nonhierarchical yet linear superposition of
Derrida’s GREMs, whereas the second paper analyses a non-linear version of the
GREM which is closely related to the perceptron model from neural networks [6]
and which we refer to henceforth as Perceptron GREM.

In the present paper we introduce a random Hamiltonian which is neither
hierarchical from the start nor given by linear superpositions of GREM-like
models. For such nonhierarchical, nonlinear generalization of the random
energy models we establish a quenched, Sanov-type large deviation principle
for the empirical distribution of the random energies which in turn allows to
derive a Boltzmann-Gibbs principle, as well as a Parisi formula for the free
energy in the thermodynamical limit. The limiting free energy turns out to be
given by the minimal value over multiple nonlinear Parisi functionals /
hierarchical structures.

What is perhaps more, our analysis suggests that the onset of ultrametricity
is intimately related to certain monotonicity properties of relative
entropies/Kullback-Leibler functionals, and shows how these monotonicities
lead to the optimal balance in the energy-entropy competition.

We emphasize that the spin glass we investigate here is nonlinear insofar the
sub-energies interact via a perceptron-like function, see (2.2) below for the
definition of the model, but the Hamiltonian still is a linear functional of
the empirical measures of the random energies. The case of nonlinear
functionals, which give rise to models which better approximate realistic spin
glasses such as the SK-model, will be addressed in a forthcoming work.

##  2\. Definition of the model and main results

We start with some notation: for $n\in\mathbb{N}$, we set
$I\overset{\text{\text{def}}}{=}\\{1,2,...,n\\}$ for the set of species. For
$J\subseteq I$ we denote by

$\mathcal{P}_{J}\overset{\text{\text{def}}}{=}\\{A\subseteq
J:A\neq\emptyset\\}$

the power set of $J$ (without empty set). For $N\in\mathbb{N}$, which will
play the role of the volume, and $j\in I$, we denote by

$\alpha_{j}\in\left\\{1,\cdots,2^{\frac{N}{n}}\right\\}$

the spins associated to the $j^{th}$-species. For $J\in\mathcal{P}_{I}$ we
identify the $|J|$-tuple $(\alpha_{j})_{j\in J}$ with

$\alpha_{\tiny{J}}\overset{\text{\text{def}}}{=}(\alpha_{j})_{j\in
J},\qquad\alpha_{\tiny{J}}\in\left\\{1,\cdots,2^{\frac{|J|N}{n}}\right\\}.$

By a slight abuse of notation, if $J=I$ we shorten $\mathcal{P}_{n}$ for
$\mathcal{P}_{I}$, and write $\alpha$ for a configuration, i.e. the whole
vector of spins $(\alpha_{1},\cdots,\alpha_{n})$.

Remark that we have altogether $2^{N}$ configurations, and since our
configuration space is in one-to-one correspondence with the set
$\\{1,\dots,2^{N}\\}$, to lighten notations, we will refer to the latter in
the counting procedures which we implement below.

Consider independent random variables

$\left\\{X^{J}_{\alpha_{\tiny{J}},i}\right\\}_{J\in\mathcal{P}_{n},i\in\mathbb{N}}$

with values in a given Polish space $S$ equipped with the Borel $\sigma$-field
$\mathcal{S}$, and defined on a probability space
$(\Omega,\mathcal{A},\mathbb{P})$. We assume that for $J\in\mathcal{P}_{n}$
each variable $X^{J}_{\alpha_{\tiny{J}},i}$ is distributed according to the
same probability distribution $\mu_{J}$. In this case, the product measure
$\mu\overset{\text{\text{def}}}{=}\bigotimes\limits_{J\in\mathcal{P}_{n}}\mu_{J}$
gives the joint distribution of the random vector

$X_{\alpha,i}\overset{\text{\text{def}}}{=}\left(X^{J}_{\alpha_{\tiny{J}},i}\right)_{J\in\mathcal{P}_{n}}.$
(2.1)

Since $|\mathcal{P}_{n}|=2^{n}-1$, the joint law $\mu$ is an element of
$\mathcal{M}^{+}_{1}(S^{2^{n}-1})$, the space of all probability distributions
on the product space $S^{2^{n}-1}$ which, endowed with the topology of weak
convergence, is Polish itself.

For $d\in\mathbb{N}$, $\nu\in\mathcal{M}^{+}_{1}(S^{d})$, we denote by
$B_{r}(\nu)$ the open ball centered in $\nu$ with radius $r>0$ in one of the
standard metrics (e.g. Prokhorov’s metric); a neighborhood or an open subset
are conceived in the corresponding topology. This turns
$\mathcal{M}^{+}_{1}(S^{d})$ into a complete, separable metric space.

For $d\in\mathbb{N}$, $\nu\in\mathcal{M}_{1}^{+}(S^{d})$ and $B$ a subset of
indeces, $B\subseteq\\{1,\cdots,d\\}$, we write
$\nu^{(B)}\in\mathcal{M}^{+}_{1}\left(S^{|B|}\right)$ for the marginal of
$\nu$ restricted to the coordinates corresponding to indices in $B$; with
$\pi_{B}:S^{d}\to S^{|B|}$ the associated natural projection, it thus holds
that

$\nu^{(B)}\overset{\text{\text{def}}}{=}\left(\pi_{B}\right)_{*}(\nu)=\nu\circ\pi_{B}^{-1}.$

Given a function $\phi:S^{2^{n}-1}\to\mathbb{R}$, our spin glass Hamiltonian
is then

$H_{N}(\alpha)=\sum\limits_{i\leq
N}\phi\left(X_{\alpha,i}\right)=N\int\phi(x)L_{N,\alpha}(dx)\,,$ (2.2)

where

$L_{N,\alpha}=\frac{1}{N}\sum\limits_{i=1}^{N}\delta_{X_{\alpha,i}}\,,$ (2.3)

is the empirical measure, a random element in
$\mathcal{M}_{1}^{+}\left(S^{2^{n}-1}\right)$. The partition function and free
energy associated to (2.2) are defined as

$Z_{N}(\phi)=2^{-N}\sum\limits_{\alpha=1}^{2^{N}}e^{H_{N}(\alpha)},\qquad\text{resp.}\quad
F_{N}(\phi)=\frac{1}{N}\log Z_{N}(\phi).$ (2.4)

This spin glass model is thus a generalization of the Perceptron GREM
discussed in [3] but which, unlike the latter, has no in-built ultrametric
structure.

For $d\in\mathbb{N}$, $\nu,\nu^{\prime}\in\mathcal{M}_{1}^{+}(S^{d})$, we
denote by

$H(\,\nu\,|\,\nu^{\prime}\,)\overset{\text{\text{def}}}{=}\begin{cases}\int\log\frac{d\nu}{d\nu^{\prime}}d\nu&\text{if}\quad\nu\ll\nu^{\prime}\\\
\infty&\text{otherwise.}\end{cases}$

the usual relative entropy of $\nu$ with respect to $\nu^{\prime}$. Finally,
for $J\in\mathcal{P}_{n}$, we set

$C_{J}\overset{\text{\text{def}}}{=}\left\\{\nu\in\mathcal{M}^{+}_{1}(S^{2^{n}-1}):H(\nu^{(\mathcal{P}_{J})}\,|\,\mu^{(\mathcal{P}_{J})})\leq\frac{|J|}{n}\log
2\right\\}.$ (2.5)

Our first result states that the quenched infinite volume free energy exists,
and is given by the solution of a Boltzmann-Gibbs variational principle. The
upshot is analogous to the control of the thermodynamical limit established in
[1] through second moment estimates on the energy levels for the case of
linear $\phi$, and with disorder given by Gaussian random variables.

######  Theorem 2.1.

Let $\phi:S^{2^{n}-1}\to\mathbb{R}$ be continuous and bounded. Then
$f(\phi)\overset{\text{\text{def}}}{=}\lim\limits_{N\to\infty}F_{N}(\phi)$
exists almost surely, and is given by

$f(\phi)=\sup_{\nu\in\mathcal{M}^{+}_{1}(S^{2^{n}-1})}\left\\{\int\phi
d\nu-\mathfrak{J}(\nu)\right\\}$ (2.6)

where the _quenched rate function_
$\mathfrak{J}:\mathcal{M}^{+}_{1}(S^{2^{n}-1})\to\overline{\mathbb{R}}$ is
given by

$\mathfrak{J}(\nu)\overset{\text{\text{def}}}{=}\begin{cases}H(\nu|\mu)&\mbox{if}\quad\nu\in\bigcap\limits_{J\in\mathcal{P}_{n}}C_{J}\\\
\infty&\mbox{otherwise}.\end{cases}$ (2.7)

Since the set $\mathcal{P}_{n}$ is partially ordered through the inclusion
relation, we can consider its totally ordered subsets, which are referred to,
with the terminology from [1], as chains. We set

$\mathcal{C}_{n}\overset{\text{\text{def}}}{=}\left\\{T=\left\\{A^{T}_{k}\right\\}_{k=0}^{n}:A^{T}_{0}=\emptyset,\,\forall
k\in I\setminus\\{n\\}:\;A^{T}_{k}\subset I,\,A^{T}_{k}\subset
A^{T}_{k+1},\,|A^{T}_{k}|=k,\,A^{T}_{n}=I\right\\}.$ (2.8)

Each element in $\mathcal{C}_{n}$ corresponds to a specific hierarchical
structure among all those in which the original model can be coarse-grained,
i.e. to each chain $T\in\mathcal{C}_{n}$ we can associate a Hamiltonian
$H^{T}_{N}$ which gives rise to a Perceptron GREM. To see how this goes, for
$T\in\mathcal{C}_{n}$, we define

$T_{k}\overset{\text{\text{def}}}{=}\\{J\subset I:J\subseteq
A^{T}_{k},J\not\subseteq A^{T}_{k-1}\\}\subset\mathcal{P}_{n}\,,\quad k\in I.$
(2.9)

The sets ${T}_{1},\cdots,{T}_{n}$ describe explicitely how a specific chain
$T$ assembles the $n$-levels into the corresponding hierarchical structure: if

$T=\left\\{\,\emptyset\subset\\{a_{1}\\}\subset\\{a_{1},a_{2}\\}\subset\cdots\subset\\{a_{1},\cdots,a_{n-1}\\}\subset\\{1,\cdots,n\\}\,\right\\}$
(2.10)

then the $\alpha_{a_{1}}$’s play the role of indeces for the first level,
$(\alpha_{a_{1}},\alpha_{a_{2}})$’s for the second etc..
Since $\mathcal{P}_{n}$ is the disjoint union of the $\\{T_{k}\\}_{k\in I}$
for any $J\in\mathcal{P}_{n}$ there is a unique

$k_{J}=k_{J}(T)\in I\;\text{for which}\;J\in{T}_{k_{J}}\,.$ (2.11)

Given these indeces we shorten222We stress that the order in which the random
sub-energies appear in the vectors (2.12) is the same as the one of the
original vector (2.1): if $\mathcal{P}_{n}=\\{J_{1},\cdots,J_{2^{n}-1}\\}$,
then the $c$-th variable is distributed according to $\mu_{J_{c}}$,
$\forall\,\,c\in\\{1,\cdots,2^{n}-1\\}$.

$Y^{T}_{\alpha,i}=\left(Y^{J}_{\alpha_{a_{1}},\cdots\alpha_{a_{k_{J}}},i}\right)_{J\in\mathcal{P}_{n}},$
(2.12)

where the $Y^{J}_{\cdot,\cdot}$-s are $\mu_{J}$-distributed and independent
both over the $\alpha$’s as well as over the $i$’s. Hence, the coarse grained
Hamiltonian corresponding to the chain $T\in\mathcal{C}_{n}$ is defined as

$H^{T}_{N}(\alpha)\overset{\text{\text{def}}}{=}\sum\limits_{i=1}^{N}\phi(Y^{T}_{\alpha,i})\,,$
(2.13)

with associated partition function and free energy in finite volume denoted by

$Z^{T}_{N}(\phi)=2^{-N}\sum\limits_{\alpha=1}^{2^{N}}e^{H^{T}_{N}(\alpha)},\quad
F^{T}_{N}(\phi)=\frac{1}{N}\log Z^{T}_{N}(\phi).$ (2.14)

The Hamiltonian (2.13) is in the form of a Perceptron GREM333 The coarse-
graining requires some burdening notation, but the procedure is quickly
understood through a concrete example which the reader may want to keep in
mind throughout: let $n=2$, and consider
$X_{\alpha,i}=(X^{\\{1\\}}_{\alpha_{1},i},\,\,\,X^{\\{2\\}}_{\alpha_{2},i},\,\,\,X^{\\{1,2\\}}_{(\alpha_{1},\alpha_{2}),i})\sim\mu_{\\{1\\}}\otimes\mu_{\\{2\\}}\otimes\mu_{\\{1,2\\}}$,
in which case $\phi:S^{3}\to\mathbb{R}$ and
$H_{N}(\alpha)=\sum_{i}\phi(X^{\\{1\\}}_{\alpha_{1},i},\,\,\,X^{\\{2\\}}_{\alpha_{2},i},\,\,\,X^{\\{1,2\\}}_{\alpha_{1},\alpha_{2},i})$.
There are two possible chains:
$R\overset{\text{\text{def}}}{=}\left\\{\\{1\\},\,\\{1,2\\}\right\\}$ or
$T\overset{\text{\text{def}}}{=}\left\\{\\{2\\},\,\\{1,2\\}\right\\}$. By way
of example we focus on the latter, in which case the sets (2.9) are given by
${T}_{1}=\left\\{\\{2\\}\right\\},{T}_{2}=\left\\{\\{1\\},\\{1,2\\}\right\\}$,
and the new sub-energies are given by
$Y^{\\{2\\}}_{\alpha_{2},i}\sim\mu_{\\{2\\}}$ for the ”first level”, and
$(Y^{\\{1\\}}_{(\alpha_{1},\alpha_{2}),i},Y^{\\{1,2\\}}_{(\alpha_{1},\alpha_{2}),i})\sim\mu_{\\{1\\}}\otimes\mu_{\\{1,2\\}}$
for the second. The Hamiltonian of the coarse-grained model is then
$H_{N}^{T}(\alpha)=\sum_{i}\phi(Y_{\alpha_{1},\alpha_{2},i}^{\left\\{1\right\\}},Y_{\alpha_{2},i}^{\left\\{2\right\\}},Y_{\alpha_{1},\alpha_{2},i}^{\left\\{1,2\right\\}})$.
The key aspect of the procedure is thus to replace the
$X^{\\{1\\}}_{\alpha_{1},i}$ with $Y^{\\{1\\}}_{\alpha_{1},\alpha_{2},i}$ the
latter being independent over the $\alpha_{2}^{\prime}s$: this eventually
induces a hierarchical correlation structure as in the Perceptron GREM.
introduced and solved in [3]: both a Gibbs variational principle, as well as a
Parisi-like formula, for the limiting free energy are available.

For later purposes, we need to recall how the Parisi variational principle for
the Perceptron GREM is constructed [3]: consider the standard simplex

$\Delta\overset{\text{\text{def}}}{=}\left\\{\bm{m}=(m_{1},\dots,m_{n}):\;0<m_{1}\leq
m_{2}\leq\dots\leq m_{n}\leq 1\right\\}\,,$ (2.15)

and recursively construct functions

$\displaystyle\phi^{T}_{n}$ $\displaystyle=\phi,$ (2.16)
$\displaystyle\phi^{T}_{k-1}\left(\bm{x}^{(1)},\cdots,\bm{x}^{(k-1)}\right)$
$\displaystyle=\frac{1}{m_{k}}\log\int\,\,\exp\left[m_{k}\phi^{T}_{k}\left(\bm{x}^{(1)},\cdots,\bm{x}^{(k-1)},\bm{y}\right)\right]\mu^{(T_{k})}(d\bm{y})\,,$

for $k\in I$, shortening also $\bm{x}^{(j)}=(x_{J})_{J\in T_{j}}$ and
$\mu^{(T_{k})}(d\bm{y})=\prod_{J\in\mathcal{P}_{k}^{T}\setminus\mathcal{P}_{k-1}^{T}}\mu_{J}(dy_{J})$,
and omitting the dependence of the $\phi$-functions on the parameter $\bm{m}$
to lighten notations.

We then set

$P^{T}(\bm{m})\overset{\text{\text{def}}}{=}\frac{\log
2}{n}\sum\limits_{k=1}^{n}\frac{1}{m_{k}}+\phi_{0}^{T}(\bm{m})\,.$ (2.17)

It is proved in [3, Theorem 2.3-2.5] that for continuous and bounded $\phi$,
the limit
$f^{T}(\phi)\overset{\text{\text{def}}}{=}\lim\limits_{N\to\infty}F^{T}_{N}$
exists almost surely and is given by the solution of the Boltzmann-Gibbs
variational principle

$f^{T}(\phi)=\sup_{\nu\in\mathcal{M}^{+}_{1}(S^{2^{n}-1})}\left\\{\int\phi(x)d\nu-\mathfrak{J}^{T}(\nu)\right\\}\,,$
(2.18)

with quenched rate function
$\mathfrak{J}^{T}:\mathcal{M}^{+}_{1}(S^{2^{n}-1})\to\overline{\mathbb{R}}$
given by

$\mathfrak{J}^{T}(\nu)\overset{\text{\text{def}}}{=}\begin{cases}H(\nu|\mu)&\mbox{if}\quad\nu\in\bigcap\limits_{k=1}^{n}C_{A^{T}_{k}}\\\
\infty&\mbox{otherwise},\end{cases}$ (2.19)

and the sets $C_{A^{T}_{k}}$ as in (2.5). Moreover, the solution can be given
in terms of the following Parisi variational principle

$f^{T}(\phi)=\min_{\bm{m}\in\Delta}P^{T}(\bm{m})\,.$ (2.20)

Our contribution here is to extend the above to the nonhierarchical
Hamiltonian (2.2).

######  Theorem 2.2.

Assume $\phi:S^{2^{n}-1}\to\mathbb{R}$ is continuous and bounded. Then

$f(\phi)=\min\limits_{T\in\mathcal{C}_{n}}f^{T}(\phi)=\min\limits_{T\in\mathcal{C}_{n}}\left\\{\min_{\bm{m}\in\Delta}P^{T}(\bm{m})\right\\}$
(2.21)

where $f(\phi)$ is the limiting free energy (2.6), and $f^{T}(\phi)$ the
limiting free energy (2.18) associated to the chain $T\in\mathcal{C}_{n}$.

In other words, the limiting free energy of the nonhierarchical Perceptron
GREM is given by the minimum among the free energies associated to all chains
in which the original model can be coarse-grained. The novelty compared to [3]
is thus the minimization in (2.21) over all $T\in\mathcal{C}_{n}$, i.e. over
all possible hierarchical structures: this feature is in full agreement with
the Parisi theory for the more sophisticated mean field spin glasses like the
SK-model, where the corresponding minimization is indeed over all
$q$-functions [6].

##  3\. The Gibbs variational principle

In this section we give a proof of Theorem 2.1. For this we will closely
follow the large deviation analysis of [3] of the Perceptron GREM, which is
flexible, and carries over to this more general setting quite swiftly. Lest
the reader is overwhelmed with innumerous pointers and references, and given
that the treatment is reasonably short, we will work out out all steps in
detail.

We first need some infrastructure: for an open subset
$U\subset\mathcal{M}^{+}_{1}(S^{2^{n}-1})$ we will denote by $M_{N}(U)$ the
random variable counting the number of $\alpha$-s for which the corresponding
empirical distribution (2.3) lies in $U$, to wit:

$M_{N}(U)=\\#\\{\alpha=1,\dots,2^{N}:L_{N,\alpha}\in U\\}.$

The following two lemmata state some well known properties of relative
entropies. The short and elementary proofs are given for completeness.

######  Lemma 3.1.

Let $S$ be a Polish space, $d\in\mathbb{N}$,
$\nu,\mu\in\mathcal{M}^{+}_{1}\left(S^{d}\right)$ with $\nu\ll\mu$,
$\mu=\bigotimes_{k=1}^{d}\mu_{k}$ for some $\mu_{k}\in\mathcal{M}^{+}_{1}(S)$,
$k\in\\{1,\cdots,d\\}$. Then for every nonempty $B\subseteq\\{1,\cdots,d\\}$,

  * $H(\nu\,|\,\mu)=H\left(\,\nu^{(B)}\,|\,\mu^{(B)}\,\right)+H\left(\,\nu\,|\,\nu^{(B)}\otimes\mu^{(B^{c})}\,\right)$ (3.1)

  * $H\left(\nu^{(B)}\,|\,\mu^{(B)}\right)\leq H\left(\nu\,|\,\mu\right)$ (3.2)

where $B^{c}=\\{1,\cdots,d\\}\setminus B$.

###### Proof.

The second claim (3.2) is an immediate consequence of (3.1), together with the
positivity of relative entropies. In order to see the first claim, let
$\\{S_{k}\\}_{k=1}^{d}$ be $d$ copies of $S$ and $B=\\{b_{1},\cdots,b_{M}\\}$,
$B^{c}=\\{a_{1},\cdots,a_{d-M}\\}$. Since the product space of Polish spaces
is Polish, specifically Radon,the disintegration Theorem holds for every
$\nu\in\mathcal{M}^{+}_{1}\left(S^{d}\right)$ and we can define the
conditional distribution $\nu^{(B^{c}|B)}$ of $\nu$ on
$S_{a_{1}}\times\cdots\times S_{a_{d-M}}$ given the projection on
$S_{b_{1}}\times\cdots\times S_{b_{M}}$. Expressing
$\nu=\nu^{(B)}\otimes\nu^{(B^{c}\mid B)}$ as a semi-direct product, it holds

$\displaystyle H(\nu\,|\,\mu)=\int\log\left(\frac{d\nu}{d\mu}\right)d\nu$
$\displaystyle=\int\log\left(\frac{d\nu^{(B)}}{d\mu^{(B)}}\right)d\nu+\int\log\left(\frac{d\nu^{(B^{c}|B)}}{d\mu^{(B^{c})}}\right)d\nu$
(3.3)
$\displaystyle=H\left(\,\nu^{(B)}\,|\,\mu^{(B)}\,\right)+\int\log\left(\frac{d\nu^{(B^{c}|B)}}{d\mu^{(B^{c})}}\right)d\nu\,.$

We now focus on the second term on the r.h.s. above: by well-known properties
of Radon-Nikodym derivatives444This step is somewhat informal, but see e.g.
[12]. we may write

$\displaystyle\frac{d\nu^{(B^{c}|B)}}{d\mu^{(B^{c})}}$
$\displaystyle=\frac{d\nu^{(B)}}{d\nu^{(B)}}\cdot\frac{d\nu^{(B^{c}|B)}}{d\mu^{(B^{c})}}=\frac{d\nu}{d\left(\nu^{(B)}\otimes\mu^{(B^{c})}\right)}\,,$
(3.4)

and therefore

$\int\log\left(\frac{d\nu^{(B^{c}|B)}}{d\mu^{(B^{c})}}\right)d\nu=\int\log\left(\frac{d\nu}{d\left(\nu^{(B)}\otimes\mu^{(B^{c})}\right)}\right)d\nu=H\left(\,\nu\,|\,\nu^{(B)}\otimes\mu^{(B^{c})}\,\right).$
(3.5)

Plugging this in (3.3) then yields (3.1).

∎

######  Lemma 3.2.

(Semicontinuity of relative entropies) With the notation of the previous
Lemma, the functions $\nu\to H(\nu\,|\,\mu)$, $\nu\to
H\left(\,\nu\,|\,\nu^{(B)}\otimes\mu^{(B^{c})}\,\right)$ are lower
semicontinuous in the weak topology.

###### Proof.

It is well known that for relative entropies the following representations
hold:

$H(\nu\,|\,\mu)=\sup\limits_{u\in\mathcal{U}}\left[\int ud\nu-\log\int
e^{u}d\mu\right],$ (3.6)

where $\mathcal{U}$ is the set of all bounded continous functions
$S^{d}\to\mathbb{R}$, and analogously for

$H\left(\,\nu\,|\,\nu^{(B)}\otimes\mu^{(B^{c})}\,\right)=\sup\limits_{u\in\mathcal{U}}\left[\int
ud\nu-\log\int e^{u}d\left(\nu^{(B)}\otimes\mu^{(B^{c})}\right)\right].$ (3.7)

But for $u\in\mathcal{U}$, the functionals

$\nu\to\int ud\nu,\quad\nu\to\log\int e^{u}d\mu,\quad\nu\to\log\int
e^{u}d\left(\nu^{(B)}\otimes\mu^{(B^{c})}\right)$

are all continuous: the claim of the Lemma thus steadily follows from this
observation and the representations (3.6) and (3.7). ∎

The next technical result is a generalization of [3, Lemma 3.1].

######  Lemma 3.3.

(Relative Sanov Theorem) Let $\alpha=(\alpha_{1},\cdots,\alpha_{n})$,
$\alpha^{\prime}=(\alpha^{\prime}_{1},\cdots,\alpha^{\prime}_{n})$ be two
configurations and $L_{N,\alpha},L_{N,\alpha^{\prime}}$ the associated
empirical distributions defined in (2.3). Assume that for
$A\in\mathcal{P}_{n},$

$\alpha_{j}=\alpha^{\prime}_{j},\,\;j\in
A\;\qquad\text{and}\qquad\alpha_{j}\neq\alpha^{\prime}_{j},\;j\in I\setminus
A.$

Then the couple $(L_{N,\alpha},L_{N,\alpha^{\prime}})$ satisfies a LDP with
good rate function

$\mathfrak{J}_{A}(\nu,\theta)=H(\nu^{\left(\mathcal{P}_{A}\right)}\,|\,\mu^{\left(\mathcal{P}_{A}\right)})+H\left(\,\nu\,|\,\nu^{\left(\mathcal{P}_{A}\right)}\otimes\mu^{\left(\mathcal{P}_{A}^{c}\right)}\,\right)+H\left(\,\theta\,|\,\theta^{\left(\mathcal{P}_{A}\right)}\otimes\mu^{\left(\mathcal{P}_{A}^{c}\right)}\,\right),$
(3.8)

if $\nu^{\left(\mathcal{P}_{A}\right)}=\theta^{\left(\mathcal{P}_{A}\right)}$
(and $=\infty$ otherwise), where
$\mathcal{P}_{A}^{c}=\mathcal{P}_{n}\setminus\mathcal{P}_{A}$.

###### Proof.

Let $S$ be a Polish space, $d\in\mathbb{N}$,

$\mathcal{P}^{\prime}=\\{b_{1},\cdots,b_{M}\\}\subseteq\\{1,\cdots,d\\},\mathcal{P}^{\prime}\neq\emptyset,$

and $\\{\bm{X}_{i}\\}$, $\\{\bm{Y}_{i}\\}$ two independent families of
indendent random variables with

$\bm{X}_{i}\sim\mu\in\bigotimes\limits_{k=1}^{d}\mathcal{M}^{+}_{1}(S_{k}),\qquad\bm{Y}_{i}\sim\mu^{\prime}\in\bigotimes\limits_{l=1}^{M}\mathcal{M}^{+}_{1}(S^{\prime}_{b_{l}}),$

where each $S_{k},S^{\prime}_{b_{l}}$ is a copy of $S$.
We consider the empirical distribution

$M_{N}=\frac{1}{N}\sum_{i=1}^{N}\delta_{(\bm{X}_{i},\bm{Y}_{i})}$ (3.9)

associated to vectors $(\bm{X}_{i},\bm{Y}_{i})\in S_{1}\times\cdots\times
S_{d}\times S^{\prime}_{b_{1}}\times\cdots\times S^{\prime}_{b_{M}}$ and the
natural projections

$\displaystyle\pi$ $\displaystyle:S_{1}\times\cdots\times S_{d}\times
S^{\prime}_{b_{1}}\times\cdots\times S^{\prime}_{b_{M}}\longrightarrow
S_{1}\times\cdots\times S_{d},$ (3.10) $\displaystyle\pi^{\prime}$
$\displaystyle:S_{1}\times\cdots\times S_{d}\times
S^{\prime}_{b_{1}}\times\cdots\times
S^{\prime}_{b_{M}}\longrightarrow\tilde{S}_{1}\times\cdots\times\tilde{S}_{d},$

where

$\tilde{S}_{k}\overset{\text{\text{def}}}{=}\begin{cases}S_{k}\quad&\text{if}\quad
k\in\mathcal{P}\\\ S^{\prime}_{k}\quad&\text{if}\quad k\notin\mathcal{P}\\\
\end{cases}\quad,\qquad\mathcal{P}\overset{\text{\text{def}}}{=}\\{1,\cdots,d\\}\setminus\mathcal{P}^{\prime}=\\{c_{1},c_{2},\cdots,c_{d-M}\\}.$

We define

$(L_{N},R_{N})\overset{\text{\text{def}}}{=}M_{N}\circ(\pi,\pi^{\prime})^{-1},$

which is a random element in $\mathcal{M}_{1}^{+}(S_{1}\times\cdots\times
S_{d})\times\mathcal{M}_{1}^{+}(\tilde{S}_{1}\times\cdots\times\tilde{S}_{d})$,
and

$\mathfrak{J}(\nu,\theta)\overset{\text{\text{def}}}{=}\begin{cases}H(\nu^{\left(\mathcal{P}\right)}\,|\,\mu^{\left(\mathcal{P}\right)})+H\left(\,\nu\,|\,\nu^{\left(\mathcal{P}\right)}\otimes\mu^{\left(\mathcal{P}^{\prime}\right)}\,\right)+H\left(\,\theta\,|\,\theta^{\left(\mathcal{P}\right)}\otimes\mu^{\prime}\,\right)&\mbox{if}\quad\nu^{\left(\mathcal{P}\right)}=\theta^{\left(\mathcal{P}\right)}\\\
\infty&\mbox{otherwise.}\end{cases}$ (3.11)

Applying Sanov’s Theorem to (3.9), and by continuous projection, we obtain
that the couple $(L_{N},R_{N})$ satisfies a LDP with good rate function

$\mathfrak{J}^{\prime}(\nu,\theta)=\inf\limits_{\rho}\left\\{H\left(\,\rho\,|\,\mu\otimes\mu^{\prime}\,\right):\quad\rho\pi^{-1}=\nu,\quad\rho\pi^{\prime-1}=\theta\right\\}.$

Since the projections (3.10) coincide on coordinates indexed in $\mathcal{P}$,
for all
$\rho\in\mathcal{M}^{+}_{1}\left(S_{1}\times\cdots\times S_{d}\times
S^{\prime}_{b_{1}}\times\cdots\times S^{\prime}_{b_{M}}\right)$ it holds
$(\rho\pi^{-1})^{(\mathcal{P})}=(\rho\pi^{\prime-1})^{(\mathcal{P})}$ and the
following implication is immediate

$\nu^{(\mathcal{P})}\neq\theta^{(\mathcal{P})}\Longrightarrow\mathfrak{J}^{\prime}(\nu,\theta)=\infty.$

We may thus henceforth assume $\nu^{(\mathcal{P})}=\theta^{(\mathcal{P})}$,
and consider $\tilde{\rho}=\tilde{\rho}(\nu,\theta)$ with marginal
$\nu^{(\mathcal{P})}=\theta^{(\mathcal{P})}$ on $S_{c_{1}}\times\cdots\times
S_{c_{d-M}}$, and conditional distribution on $S_{b_{1}}\times\cdots\times
S_{b_{M}}\times S^{\prime}_{b_{1}}\times\cdots\times S^{\prime}_{b_{M}}$ given
the projection on $S_{c_{1}}\times\cdots\times S_{c_{d-M}}$ as the product of
the conditional distribution of $\nu$ on $S_{b_{1}}\times\cdots\times
S_{b_{M}}$ given the projection on $S_{c_{1}}\times\cdots\times S_{c_{d-M}}$,
and of the conditional distribution $\theta$ on
$S^{\prime}_{b_{1}}\times\cdots\times S^{\prime}_{b_{M}}$ given the projection
on $S_{c_{1}}\times\cdots\times S_{c_{d-M}}$. In which case, applying (3.1),
we easily obtain

$H\left(\,\tilde{\rho}\,|\,\mu\otimes\mu^{\prime}\,\right)=H\left(\,\nu^{(\mathcal{P})}\,|\,\mu^{(\mathcal{P})}\,\right)+H\left(\,\nu\,|\,\nu^{(\mathcal{P})}\otimes\mu^{(\mathcal{P}^{\prime})}\,\right)+H\left(\,\theta\,|\,\theta^{(\mathcal{P})}\otimes\mu^{\prime}\,\right)$

and therefore $\mathfrak{J}\geq\mathfrak{J}^{\prime}$. Conversely, for any
$\rho$ satisfying $\rho\pi^{-1}=\nu$, $\rho\pi^{\prime-1}=\theta$, we claim
that

$\mathfrak{J}(\nu,\theta)\leq H(\rho\,|\,\mu\otimes\mu^{\prime})\,.$ (3.12)

(Remark that we can assume that the right hand side is finite). To see this,
we first write

$H\left(\,\rho\,|\,\mu\otimes\mu^{\prime}\,\right)=H\left(\,\rho\,|\,\tilde{\rho}(\nu,\theta)\,\right)+\int
d\rho\log\frac{d\tilde{\rho}(\nu,\theta)}{d(\mu\otimes\mu^{\prime})}.$

The first term is non-negative, while the second equals

$\int
d\tilde{\rho}(\nu,\theta)\log\frac{d\tilde{\rho}(\nu,\theta)}{d(\mu\otimes\mu^{\prime})}=\mathfrak{J}(\nu,\theta),$

and (3.12) follows. The statement of the Lemma corresponds then to the case

$d=2^{n}-1,\qquad\mathcal{P}^{\prime}=\mathcal{P}_{A}^{c}.$

∎

######  Proposition 3.4.

Let $\nu\in\mathcal{M}^{+}_{1}\left(S^{2^{n}-1}\right)$ be such that
$H(\nu\,|\,\mu)<\infty$, $\epsilon>0$ and $V$ an open neighborhood of $\nu$.
Then there exists an open neighborhood $U$ of $\nu$, $U\subset V$, and
$\delta>0$ for which

$\operatorname{\mathbb{P}}\left[M_{N}(U)\geq e^{N(\log
2-H(\nu\,|\,\mu)+\epsilon)}\right]\leq e^{-\delta N}.$

###### Proof.

By the semicontinuity property of the relative entropy, given $B_{r}(\nu)$ a
family of open balls with radius $r>0$, one has

$\inf\limits_{\rho\in B_{r}(\nu)}H(\rho\,|\,\mu)\to
H(\nu\,|\,\mu)\qquad\text{as}\quad r\to 0.$

Specifically, we can extract a sequence $\\{r_{k}\\}_{k\in\mathbb{N}}$ with
$r_{k}\to 0$ as $k\to\infty$ so that

$\inf\limits_{\rho\in
B_{r}(\nu)}H(\rho\,|\,\mu)=\inf\limits_{\rho\in\overline{B_{r}}(\nu)}H(\rho\,|\,\mu)\to
H(\nu\,|\,\mu).$

Therefore for every $\epsilon>0$, $V$ we may find $k\in\mathbb{N}$ for which

$\overline{B_{r_{k}}}(\nu)\subset V\quad\text{and}\quad\inf\limits_{\rho\in
B_{r_{k}}(\nu)}H(\rho\,|\,\mu)=\inf\limits_{\rho\in\overline{B_{r_{k}}}(\nu)}H(\rho\,|\,\mu)\geq
H(\nu\,|\,\mu)-\frac{\epsilon}{4}\,.$ (3.13)

All in all,

$\operatorname{\mathbb{E}}\left[M_{N}(B_{r_{k}}(\nu))\right]=\sum\limits_{\alpha=1}^{2^{N}}\operatorname{\mathbb{P}}\left[L_{N,\alpha}\in
B_{r_{k}}(\nu)\right]\leq
2^{N}\exp\left[-N\left(H(\nu\,|\,\mu)-\frac{\epsilon}{2}\right)\right],$

the last step by Sanov’s theorem together with (3.13).

The claim of the Proposition steadily follows from Markov’s inequality, and
$\delta=\epsilon/4$. ∎

######  Proposition 3.5.

Let $\nu\in\mathcal{M}^{+}_{1}\left(S^{2^{n}-1}\right)$ be such that for some
$J\in\mathcal{P}_{n}$,
$H\left(\,\nu^{(\mathcal{P}_{J})}\,|\,\mu^{(\mathcal{P}_{J})}\,\right)>|J|\log
2/n$ and $V$ an open neighborhood of $\nu$. Then there exists an open
neighborhood $U$ of $\nu$, $U\subset V$, and $\delta>0$ such that for $N$
large enough

$\operatorname{\mathbb{P}}\left[M_{N}(U)\neq 0\right]\leq e^{-\delta N}.$

###### Proof.

Let $J\in\mathcal{P}_{n}$ satisfy
$H\left(\,\nu^{(\mathcal{P}_{J})}\,|\,\mu^{(\mathcal{P}_{J})}\,\right)>|J|\log
2/n$. Similarly to the proof of Proposition 3.4 we can select a neighborhood
$W$ of
$\nu^{(\mathcal{P}_{J})}\in\mathcal{M}^{+}_{1}\left(S^{|\mathcal{P}_{J}|}\right)$
with

$\inf\limits_{\rho\in\overline{W}}H\left(\rho\mid\mu^{(\mathcal{P}_{J})}\right)=\inf\limits_{\rho\in
W}H\left(\rho\mid\mu^{(\mathcal{P}_{J})}\right)>\frac{|J|}{n}\log 2+2\delta,$

for some $\delta>0$. If we now define

$U\overset{\text{\text{def}}}{=}\left\\{\nu\in\mathcal{M}^{+}_{1}(S^{2^{n}-1}):\,\,\nu\in
V,\nu^{(\mathcal{P}_{J})}\in W\right\\},$

it follows from union bounds/subadditivity that

$\displaystyle\operatorname{\mathbb{P}}\left[M_{N}(U)\neq 0\right]$
$\displaystyle=\operatorname{\mathbb{P}}\left[\exists\alpha:\,L_{N,\alpha}\in
U\right]\leq\operatorname{\mathbb{P}}\left[\exists\alpha:\,(L_{N,\alpha})^{(\mathcal{P}_{J})}\in
W\right]$ (3.14)
$\displaystyle\leq\sum\limits_{\alpha_{J}=1}^{2^{|J|N/n}}\operatorname{\mathbb{P}}\left[\,(L_{N,\alpha})^{(\mathcal{P}_{J})}\in
W\right]$
$\displaystyle=2^{\frac{|J|}{n}N}\operatorname{\mathbb{P}}\left[\,(L_{N,\alpha})^{(\mathcal{P}_{J})}\in
W\right]\,,$

the last line using that the empirical measures are identically distributed.
Since the r.h.s. above is, by Sanov’s theorem, at most

$\displaystyle
2^{\frac{|J|}{n}N}\exp\left[-N\left(\inf\limits_{\rho\in\overline{W}}H\left(\rho\mid\mu^{(\mathcal{P}_{J})}\right)-\delta\right)\right]\leq
2^{\frac{|J|}{n}N}2^{-\frac{|J|}{n}N}e^{-\delta N}=e^{-\delta N},$ (3.15)

the proof of the Proposition is concluded. ∎

######  Proposition 3.6.

Assume that $\nu\in\mathcal{M}^{+}_{1}(S^{2^{n}-1})$ satisfies the
$C$-conditions (2.5) _strictly_ , namely that
$H\left(\nu^{(\mathcal{P}_{J})}|\mu^{(\mathcal{P}_{J})}\right)<|J|/n\log
2,\,J\in\mathcal{P}_{n}$. Let $V$ be an open neighborhood of $\nu$, and
$\epsilon>0$. Then there exists an open neighborhood $U$ of $\nu$ with
$U\subset V$ and $\delta>0$ such that for large enough $N$

$\operatorname{\mathbb{P}}\left[M_{N}(U)\leq e^{N(\log
2-H(\nu\,|\,\mu)-\epsilon)}\right]\leq e^{-\delta N}.$

###### Proof.

We claim that for all $\epsilon>0$ there exists $\delta>0$ and $U\subset V$ an
open neighborhood of $\nu$ for which

$\operatorname{\mathbb{V}\text{ar}}M_{N}(U)\leq e^{-2\delta
N}\left[\operatorname{\mathbb{E}}M_{N}(U)\right]^{2}\,.$ (3.16)

Assuming this for the time being, the proposition follows steadily as an
elementary application of Chebycheff’s inequality: indeed, by Sanov’s theorem,

$\operatorname{\mathbb{E}}M_{N}(U)=2^{N}\operatorname{\mathbb{P}}\left(L_{N,\alpha}\in
U\right)\geq 2^{N}\exp\left(-NH(\nu\,|\,\mu)-N\xi\,\right)\,,$ (3.17)

for $\xi>0$. Elementary manipulations then yield

$\displaystyle\operatorname{\mathbb{P}}\left[M_{N}(U)\leq
2^{N}\exp\left(-NH(\nu\,|\,\mu)-2N\xi\right)\,\right]$ (3.18)
$\displaystyle\quad\qquad=\operatorname{\mathbb{P}}\left[M_{N}(U)-\operatorname{\mathbb{E}}M_{N}(U)\leq
e^{-N\xi}\,2^{N}\exp\left(-NH(\nu\,|\,\mu)-N\xi\right)-\operatorname{\mathbb{E}}M_{N}(U)\,\right]$
$\displaystyle\quad\qquad\stackrel{{\scriptstyle\eqref{Sanov_basic}}}{{\leq}}\operatorname{\mathbb{P}}\left[M_{N}(U)-\operatorname{\mathbb{E}}M_{N}(U)\leq\left(e^{-N\xi}-1\right)\operatorname{\mathbb{E}}M_{N}(U)\right]$
$\displaystyle\quad\qquad\leq\operatorname{\mathbb{P}}\left[M_{N}(U)-\operatorname{\mathbb{E}}M_{N}(U)\leq-\frac{1}{2}\operatorname{\mathbb{E}}M_{N}(U)\right],$

for $N$ large enough. But the r.h.s. of (3.18) is at most

$\displaystyle\operatorname{\mathbb{P}}\left[|M_{N}(U)-\operatorname{\mathbb{E}}M_{N}(U)|\geq\frac{1}{2}\operatorname{\mathbb{E}}M_{N}(U)\right]$
$\displaystyle\leq
4\frac{\operatorname{\mathbb{V}\text{ar}}M_{N}(U)}{\left[\operatorname{\mathbb{E}}M_{N}(U)\right]^{2}}\stackrel{{\scriptstyle\eqref{second_moment}}}{{\leq}}4e^{-2N\delta}\leq
e^{-\delta N}\,,$ (3.19)

settling the claim of the proposition.

It thus remains to prove (3.16). To see how this goes, we first observe that,
under the assumptions of the proposition, there exists $\eta>0$ such that

$H\left(\,\nu^{(\mathcal{P}_{J})}\,|\,\mu^{(\mathcal{P}_{J})}\right)<\frac{|J|}{n}\log
2-\eta.$ (3.20)

Moreover, we claim that for $J\in\mathcal{P}_{n}$,

$\displaystyle\lim\limits_{r\to
0}\inf\limits_{\begin{subarray}{c}\rho,\theta\in\overline{B}_{r}(\nu)\\\
\rho^{(\mathcal{P}_{J})}=\theta^{(\mathcal{P}_{J})}\end{subarray}}\left\\{H(\rho\,|\,\mu)+H\left(\,\theta\,|\,\theta^{(\mathcal{P}_{J})}\otimes\mu^{(\mathcal{P}_{J}^{c})}\,\right)\right\\}=$
(3.21) $\displaystyle\hskip
113.81102pt=H(\nu\,|\,\mu)+H\left(\,\nu\,|\,\nu^{(\mathcal{P}_{J})}\otimes\mu^{(\mathcal{P}_{J}^{c})}\,\right).$

This can be checked through approriate upper- and lower bounds. The bound
”$\leq$” is straightforward: simply plug in $\rho=\theta=\nu$ on the l.h.s.
above. The bound ”$\geq$” is a consequence of the semicontinuity properties of
the relative entropies: in fact, by Lemma 3.2, one gets that for a sequence
$(\rho_{m},\theta_{m})$ with
$\rho_{m}^{(\mathcal{P}_{J})}=\theta_{m}^{(\mathcal{P}_{J})}$ and
$\rho_{m},\theta_{m}\to\nu$ it holds

$\displaystyle\liminf\limits_{m\to\infty}H(\rho_{m}\,|\,\mu)$
$\displaystyle\geq H(\nu\,|\,\mu),$ (3.22)
$\displaystyle\liminf\limits_{m\to\infty}H\left(\,\theta_{m}\,|\,\theta_{m}^{(\mathcal{P}_{J})}\otimes\mu^{(\mathcal{P}_{J}^{c})}\,\right)$
$\displaystyle\geq
H\left(\,\nu\,|\,\nu^{(\mathcal{P}_{J})}\otimes\mu^{(\mathcal{P}_{J}^{c})}\,\right),$

which settles the ”$\geq$”-case, and thus (LABEL:inf_3).

By (LABEL:inf_3), for $r$ small enough such that $\overline{B}_{r}(\nu)\subset
V,U=B_{r}(\nu)$ we have that for $J\in\mathcal{P}_{n}$, it holds:

$\displaystyle\inf\limits_{\begin{subarray}{c}\rho,\theta\in\overline{B}_{r}(\nu)\\\
\rho^{(\mathcal{P}_{J})}=\theta^{(\mathcal{P}_{J})}\end{subarray}}\left\\{H(\rho\,|\,\mu)+H\left(\,\theta\,|\,\theta^{(\mathcal{P}_{J})}\otimes\mu^{(\mathcal{P}_{J}^{c})}\,\right)\right\\}$
(3.23) $\displaystyle\hskip 85.35826pt\geq
H(\nu\,|\,\mu)+H\left(\,\nu\,|\,\nu^{(\mathcal{P}_{J})}\otimes\mu^{(\mathcal{P}_{J}^{c})}\,\right)-\frac{\eta}{2}$
$\displaystyle\hskip
85.35826pt=H(\nu\,|\,\mu)+H(\nu\,|\,\mu)-H\left(\,\nu^{(\mathcal{P}_{J})}\,|\,\mu^{(\mathcal{P}_{J})}\,\right)-\frac{\eta}{2},$

the last step by the chain rule (3.1). The r.h.s. above equals

$\displaystyle
2H(\nu\,|\,\mu)-H\left(\,\nu^{(\mathcal{P}_{J})}\,|\,\mu^{(\mathcal{P}_{J})}\,\right)-\frac{\eta}{2}\geq
2H(\nu\,|\,\mu)-\frac{|J|}{n}\log 2+\frac{\eta}{2},$ (3.24)

the last step using (3.20). All in all, we have established that

$\inf\limits_{\begin{subarray}{c}\rho,\theta\in\overline{U}\\\
\rho^{(\mathcal{P}_{J})}=\theta^{(\mathcal{P}_{J})}\end{subarray}}\left\\{H(\rho\,|\,\mu)+H\left(\,\theta\,|\,\theta^{(\mathcal{P}_{J})}\otimes\mu^{(\mathcal{P}_{J}^{c})}\,\right)\right\\}\geq
2H(\nu\,|\,\mu)-\frac{|J|}{n}\log 2+\frac{\eta}{2}\,.$ (3.25)

This inequality will play a crucial role in the control of the second moment
of the $M_{N}$-counting randon variable which stands behind (3.16): we begin
by writing

$\displaystyle\operatorname{\mathbb{E}}M_{N}^{2}(U)$
$\displaystyle=\sum\limits_{\alpha,\alpha^{\prime}=1}^{2^{N}}\operatorname{\mathbb{P}}\left[L_{\alpha,N}\in
U,L_{\alpha^{\prime},N}\in U\right]$ (3.26)
$\displaystyle\leq\sum_{\alpha_{j}\neq\alpha^{\prime}_{j},\,\,\forall j\in
I}p_{\alpha,\alpha^{\prime}}+\,\sum_{J\in\mathcal{P}_{n}}\sum\limits_{\begin{subarray}{c}\alpha_{j}=\alpha^{\prime}_{j}\,\,\forall\,j\in
J\\\ \alpha_{j}\neq\alpha_{j}^{\prime}\,\,\forall j\in I\setminus
J\end{subarray}}p_{\alpha,\alpha^{\prime}},$

where we have shortened, to lighten notations,

$p_{\alpha,\alpha^{\prime}}\overset{\text{\text{def}}}{=}\operatorname{\mathbb{P}}\left[L_{\alpha,N}\in\overline{U},L_{\alpha^{\prime},N}\in\overline{U}\right].$

Now, if $\alpha_{j}\neq\alpha^{\prime}_{j}$ for all $j\in I$, then the
associated empirical measures $L_{\alpha,N}$ and $L_{\alpha^{\prime},N}$ are
independent, and we may bound the corresponding contribution in (3.26) with
the square of the first moment to obtain

$\operatorname{\mathbb{E}}M_{N}^{2}(U)\leq\left[\operatorname{\mathbb{E}}M_{N}(\overline{U})\right]^{2}+\,\sum\limits_{J\in\mathcal{P}_{n}}\sum\limits_{\begin{subarray}{c}\alpha_{j}=\alpha^{\prime}_{j}\,\forall\,j\in
J\\\ \alpha_{j}\neq\alpha_{j}^{\prime}\,\forall j\in I\setminus
J\end{subarray}}p_{\alpha,\alpha^{\prime}}.$ (3.27)

In order to control the probabilities in the sum on the r.h.s. above, we
consider the generic situation where for some $J\in\mathcal{P}_{n}$,
$\alpha_{j}=\alpha^{\prime}_{j}\quad\forall j\in J$,
$\alpha_{j}\neq\alpha^{\prime}_{j}\quad\forall j\in I\setminus J$. In this
case, by the relative Sanov principle from Lemma 3.3, and for $N$ large
enough, it holds:

$p_{\alpha,\alpha^{\prime}}=\operatorname{\mathbb{P}}\left[L_{\alpha,N}\in\overline{U},L_{\alpha^{\prime},N}\in\overline{U}\right]\leq\exp\left[-N\inf\limits_{\begin{subarray}{c}\rho,\theta\in\overline{U}\\\
\rho^{(\mathcal{P}_{J})}=\theta^{(\mathcal{P}_{J})}\end{subarray}}\left\\{\mathfrak{J}_{J}(\rho,\theta)\right\\}+\frac{N\eta}{4}\,\,\right]\,,$
(3.28)

where the quenched rate function with prescribed marginals as above satisfies

$\displaystyle\mathfrak{J}_{J}(\rho,\theta)$
$\displaystyle=H(\rho^{\left(\mathcal{P}_{J}\right)}\,|\,\mu^{\left(\mathcal{P}_{J}\right)})+H\left(\,\rho\,|\,\rho^{\left(\mathcal{P}_{J}\right)}\otimes\mu^{\left(\mathcal{P}_{J}^{c}\right)}\,\right)+H\left(\,\theta\,|\,\theta^{\left(\mathcal{P}_{J}\right)}\otimes\mu^{\left(\mathcal{P}_{J}^{c}\right)}\right)$
(3.29)
$\displaystyle=H(\rho\,|\,\mu)+H\left(\,\theta\,|\,\theta^{\left(\mathcal{P}_{J}\right)}\otimes\mu^{\left(\mathcal{P}_{J}^{c}\right)}\,\right),$

the first step by definition, and the second by the chain rule from Lemma 3.1.
Plugging this into (3.28) we thus get

$\displaystyle p_{\alpha,\alpha^{\prime}}$
$\displaystyle\leq\exp\left[-N\inf\limits_{\begin{subarray}{c}\rho,\theta\in\overline{U}\\\
\rho^{(\mathcal{P}_{J})}=\theta^{(\mathcal{P}_{J})}\end{subarray}}\left\\{H(\rho\,|\,\mu)+H\left(\,\theta\,|\,\theta^{\left(\mathcal{P}_{J}\right)}\otimes\mu^{\left(\mathcal{P}_{J}^{c}\right)}\,\right)\right\\}+\frac{N\eta}{4}\right]$
(3.30) $\displaystyle\leq
2^{\frac{N|J|}{n}}\exp\left[-2NH(\nu\,|\,\mu)-\frac{N\eta}{4}\right]\,,$

the last inequality by the key bound (3.25), and therefore

$\displaystyle\sum\limits_{\begin{subarray}{c}\alpha_{j}=\alpha^{\prime}_{j}\quad\forall
j\in J\\\ \alpha_{j}\neq\alpha_{j}^{\prime}\quad\forall j\in I\setminus
J\end{subarray}}p_{\alpha,\alpha^{\prime}}$ $\displaystyle\leq
2^{(n-|J|)\frac{N}{n}}2^{\frac{N|J|}{n}}\left(2^{\frac{N}{n}}-1\right)^{(n-|J|)}2^{\frac{N|J|}{n}}\exp\left[-2NH(\nu\,|\,\mu)-\frac{N\eta}{4}\right]$
(3.31) $\displaystyle\leq
2^{2N}\exp\left[-2NH(\nu\,|\,\mu)-\frac{N\eta}{4}\right].$

Plugging this in (3.27), and recalling (3.17) with $\xi=\frac{\eta}{16}$, we
thus get that for $N$ large enough

$\operatorname{\mathbb{V}\text{ar}}M_{N}(U)\leq
2^{2N}(2^{n}-1)\exp\left[-2NH(\nu\,|\,\mu)-\frac{N\eta}{4}\right]\leq
e^{-\frac{N\eta}{8}}\left[\operatorname{\mathbb{E}}M_{N}(U)\right]^{2},$
(3.32)

which settles the claim (3.16) with $\delta=\frac{\eta}{16}$, say.

∎

###### Proof of Theorem 2.1.

We begin with a couple of elementary observations.

  * •

First recall that for $J\in\mathcal{P}_{n}$,

$C_{J}=\left\\{\nu\in\mathcal{M}^{+}_{1}(S^{2^{n}-1}):H(\nu^{(\mathcal{P}_{J})}\,|\,\mu^{(\mathcal{P}_{J})})\leq\frac{|J|}{n}\log
2\right\\}\,.$ (3.33)

These sets are compact thanks to the semicontinuity of $\nu\to H(\nu\,|\,\mu)$
from Lemma 3.2 . It thus follows that the intersection
$\bigcap_{J\in\mathcal{P}_{n}}C_{J}\subset\mathcal{M}^{+}_{1}(S^{2^{n}-1})$ is
itself compact, and in particular that there exists
$\nu^{\prime}\in\bigcap_{J\in\mathcal{P}_{n}}C_{J}$ such that

$\sup\limits_{\nu\in\bigcap\limits_{J\in\mathcal{P}_{n}}C_{J}}\left\\{\int\phi
d\nu-H(\nu\,|\,\mu)\right\\}=\int\phi d\nu^{\prime}-H(\nu^{\prime}\,|\,\mu).$

  * •

It is well known that $\nu\to H(\nu\,|\,\mu)$ is convex.

  * •

It clearly holds that $\mu\in\bigcap_{J\in\mathcal{P}_{n}}C_{J}$.

Given a convex combination
$\nu_{\lambda}\overset{\text{\text{def}}}{=}\lambda\mu+(1-\lambda)\nu^{\prime}$,
$0<\lambda<1$ we thus have

$H(\nu_{\lambda}^{(\mathcal{P}_{J})}\,|\,\mu^{(\mathcal{P}_{J})})<\frac{|J|}{n}\log
2\qquad\forall J\in\mathcal{P}_{n}.$

We also know that as $\lambda\to 0$, $\nu_{\lambda}\to\nu^{\prime}$ weakly and
$\int\phi d\nu_{\lambda}\to\int\phi d\nu^{\prime}$,
$H(\nu_{\lambda}\,|\,\mu)\to H(\nu^{\prime}\,|\,\mu)$. In particular, to
$\epsilon>0$ we can find $\lambda>0$ with

$\int\phi d\nu_{\lambda}-H(\nu_{\lambda}\,|\,\mu)\geq\int\phi
d\nu^{\prime}-H(\nu^{\prime}\,|\,\mu)-\epsilon.$ (3.34)

Moreover, since the map $\nu\to\int\phi(x)\nu(dx)$ is continuous, by
Proposition 3.6 we can find a neighbourhood $U$ of $\nu_{\lambda}$, and
$\delta>0$ such that

$\int\phi(x)\nu_{\lambda}(dx)-\int\phi(x)\rho(dx)\leq\epsilon\quad\forall\rho\in
U,$

and with the neighbourhood $U$ such that

$\operatorname{\mathbb{P}}\left[M_{N}(U)\leq
2^{N}e^{-H(\nu_{\lambda}\,|\,\mu)N-\epsilon N)}\right]\leq e^{-\delta N}.$

With this choice, we thus have for the partition function of our spin glass
(2.4) that

$\displaystyle Z_{N}(\phi)$
$\displaystyle=2^{-N}\sum\limits_{\alpha=1}^{2^{N}}\exp\left[N\int\phi(x)L_{N,\alpha}(dx)\right]$
(3.35) $\displaystyle\geq\exp\left[N\int\phi(x)\nu_{\lambda}(dx)-\epsilon
N\right]\exp\left[-H(\nu_{\lambda}\,|\,\mu)N-\epsilon N\right]$
$\displaystyle\geq\exp\left[N\sup\limits_{\nu\in\bigcap\limits_{J\in\mathcal{P}_{n}}C_{J}}\left\\{\int\phi(x)d\nu-H(\nu\,|\,\mu)\right\\}-3\epsilon
N\right].$

As $\epsilon$ is arbitrary, it follows from Borel-Cantelli that

$\liminf\limits_{N\to\infty}F_{N}(\phi)=\liminf\limits_{N\to\infty}\frac{1}{N}\log
Z_{N}(\phi)\geq\sup\limits_{\nu\in\bigcap\limits_{J\in\mathcal{P}_{n}}C_{J}}\left\\{\int\phi(x)d\nu-H(\nu\,|\,\mu)\right\\}\,,$
(3.36)

almost surely. This settles the ”first half of the theorem”, i.e. the lower
bound to the free energy.

In order to establish the upper bound, we distinguish two cases:

  * i)

For $\nu\in\bigcap\limits_{J\in\mathcal{P}_{n}}C_{J}$, we choose a radius
$r_{\nu}>0$ such that

$\operatorname{\mathbb{P}}\left[M_{N}(B_{r_{\nu}}(\nu))\geq e^{N(\log
2-H(\nu\,|\,\mu)+\epsilon)}\right]\leq e^{-\delta_{\nu}N},$

for large enough $N$ and some $\delta_{\nu}>0$; this is clearly possible in
virtue of Proposition 3.4. The radius $r_{\nu}$ is chosen however small enough
such that

$\left|\int\phi(x)\rho(dx)-\int\phi(x)\nu(dx)\right|\leq\epsilon,\qquad\forall\rho\in
B_{r_{\nu}}(\nu),$

(which is possible thanks to the aforementioned continuity of the map
$\rho\mapsto\int\phi(x)\rho(dx)$).

  * ii)

For $\nu\in
C_{I}\setminus\left(\bigcap\limits_{J\in\mathcal{P}_{n}}C_{J}\right)$ we still
have $H(\nu\,|\,\mu)\leq\log 2$ and we can resort to Proposition 3.5 to find
$r_{\nu}>0$ such that

$\operatorname{\mathbb{P}}\left[M_{N}(B_{r_{\nu}}(\nu))\neq 0\right]\leq
e^{-\delta_{\nu}N},$ (3.37)

for large enough $N$, and some $\delta_{\nu}>0$.

Using that $C_{I}\subset\bigcup_{\nu\in C_{I}}B_{r_{\nu}}(\nu)$, by
compactness we may extract a finite sequence $\\{\nu_{j}\\}_{j=1}^{m}\subset
C_{I}$ for which covering still holds, to wit

$C_{I}\subset\bigcup_{j=1}^{m}B_{r_{j}}(\nu_{j}),$

where we have also shortened $r_{j}\overset{\text{\text{def}}}{=}r_{\nu_{j}}$.
Moreover, if we set

$U\overset{\text{\text{def}}}{=}\bigcup_{j=1}^{m}B_{r_{j}}(\nu_{j}),\qquad\delta\overset{\text{\text{def}}}{=}\min\limits_{j\in\\{1,\cdots,m\\}}\delta_{\nu_{j}},$

it follows from Sanov theorem that

$\limsup\limits_{N\to\infty}\frac{1}{N}\log\operatorname{\mathbb{P}}\left[L_{N,\alpha}\notin
U\right]\leq-\inf\limits_{\nu\notin U}H(\nu\,|\,\mu)<-\log 2.$ (3.38)

Splitting the contributions to the partition function then steadily yields the
upper bound

$\displaystyle Z_{N}(\phi)$ $\displaystyle\leq
2^{-N}\sum_{l=1}^{m}\,\sum\limits_{\alpha:L_{N,\alpha}\in
B_{r_{l}}(\nu_{l})}\,\exp{\left[N\int\phi(x)L_{N,\alpha}(dx)\right]}+$ (3.39)
$\displaystyle\hskip 142.26378pt+2^{-N}\sum\limits_{\alpha:L_{N,\alpha}\notin
U}\exp{\left[\int\phi(x)L_{N,\alpha}(dx)\right]}\,.$

By (3.38), the second summand yields no contribution in the large $N$-limit.
Analogously, (3.37) establishes that the same applies to those terms in the
first summand for which
$\nu_{l}\notin\bigcap\limits_{J\in\mathcal{P}_{n}}C_{J}$. All in all we have

$\displaystyle Z_{N}$ $\displaystyle\leq
2^{-N}\sum\limits_{l:\,\,\nu_{l}\in\bigcap\limits_{J\in\mathcal{P}_{n}}C_{J}}\,\,\sum\limits_{\alpha:L_{N,\alpha}\in
B_{r_{l}}(\nu_{l})}\,\exp{\left[N\int\phi(x)L_{N,\alpha}(dx)\right]}$ (3.40)
$\displaystyle\leq e^{\epsilon
N}\sum\limits_{l:\,\,\nu_{l}\in\bigcap\limits_{J\in\mathcal{P}_{n}}C_{J}}\exp{\left[N\int\phi
d\nu_{l}\right]}M_{N}\left(B_{r_{l}}(\nu_{l})\right)$ $\displaystyle\leq
e^{2\epsilon
N}\sum\limits_{l:\,\,\nu_{l}\in\bigcap\limits_{J\in\mathcal{P}_{n}}C_{J}}\exp{\left[N\int\phi
d\nu_{l}-NH(\nu_{l}\,|\,\mu)\right]}$ $\displaystyle\leq e^{2\epsilon
N}m\exp{\left[N\sup\limits_{\nu\in\bigcap\limits_{J\in\mathcal{P}_{n}}C_{J}}\left\\{\int\phi
d\nu-H(\nu\,|\,\mu)\right\\}\right]}$

almost surely, for large enough $N$. Since $\epsilon$ is arbitrary we thus
have

$\limsup\limits_{N\to\infty}F_{N}(\phi)=\limsup\limits_{N\to\infty}\frac{1}{N}\log
Z_{N}(\phi)\leq\sup\limits_{\nu\in\bigcap\limits_{J\in\mathcal{P}_{n}}C_{J}}\left\\{\int\phi
d\nu-H(\nu\,|\,\mu)\right\\},$

almost surely. This being the sought upperbound, Theorem 2.1 follows. ∎

##  4\. The Parisi variational principle

In this section we prove Theorem 2.2. The following upper bound

$f(\phi)\leq\min\limits_{T\in\mathcal{C}_{n}}f^{T}(\phi),$ (4.1)

is immediate: since for any $T\in\mathcal{C}_{n}$,

$\bigcap\limits_{J\in\mathcal{P}_{n}}C_{J}\subset\bigcap\limits_{k=1}^{n}C_{A^{T}_{k}}\,,$

the Boltzmann-Gibbs variational principle (2.6) is analogous to the ones in
(2.18) with the only difference that the supremum in the former is taken on a
smaller set. This proves that $f(\phi)\leq f^{T}(\phi)$ for any
$T\in\mathcal{C}_{n}$, and thus settles (4.1).

On the other hand, the Parisi variational principle (2.20) established in [3],
states that for the Perceptron GREM

$f^{T}(\phi)=\min_{\bm{m}\in\Delta}P^{T}(\bm{m}).$ (4.2)

Combining (4.1) and (4.2) we thus have

$f(\phi)\leq\min_{T\in\mathcal{C}_{n}}\left\\{\min_{m\in\Delta}P^{T}(\bm{m})\right\\}\,,$
(4.3)

which is ”half of the theorem”.

In order to prove the ”second half”, namely the lower bound, some
infrastructure is needed. Following [3], for each $T\in\mathcal{C}_{n}$ we
define a probability distribution $G^{T}=G^{T}(\bm{m})$ on $S^{2^{n}-1}$ which
depends on the parameter $\bm{m}\in\Delta$. This generalized Gibbs measure is
associated to the Parisi functional $P^{T}$, recall (2.17) above, and is
described through

  * •

a measure $\gamma^{T}$ on $S$,

  * •

and, for $2\leq j\leq n$, Markov kernels $K^{T}_{j}$ with source
$S^{|\mathcal{P}_{j-1}^{T}|}=S^{2^{j-1}-1}$ and target
$S^{|T_{j}|}=S^{2^{j-1}}$.

Precisely, and recalling the functions
$\left\\{\phi^{T}_{k}\right\\}_{k=1}^{n}$ from (2.16), the generalized Gibbs
measure $G^{T}$ is given by the semi-direct product

$G^{T}=\gamma^{T}\otimes K^{T}_{2}\otimes\cdots\otimes K^{T}_{n}.$ (4.4)
$\gamma^{T}(dx)\overset{\text{\text{def}}}{=}\frac{\exp\left[m_{1}\phi_{1}^{T}(x)\right]\mu_{A^{T}_{1}}(dx)}{\exp\left[m_{1}\phi_{0}^{T}(x)\right]},$
$K^{T}_{j}(\bm{x}^{(1)},\cdots,\bm{x}^{(j-1)},d\bm{x}^{(j)})\overset{\text{\text{def}}}{=}\frac{\exp\left[m_{j}\phi_{j}^{T}(\bm{x}^{(1)},\cdots,\bm{x}^{(j)})\right]\mu^{(T_{j})}(d\bm{x}^{(j)})}{\exp\left[m_{j}\phi_{j-1}^{T}(\bm{x}^{(1)},\cdots,\bm{x}^{(j-1)})\right]}$

where555Notice that with this notation it holds in particular that
$(\bm{x}^{(1)},\cdots,\bm{x}^{(j-1)})=(x_{J})_{J\in\mathcal{P}_{j-1}^{T}}\in
S^{2^{j-1}-1}.$ $\bm{x}^{(j)}=\left(x_{J}\right)_{J\in T_{j}}\in S^{2^{j-1}}$
We also write

$G^{T}_{j-1}\overset{\text{\text{def}}}{=}\left(G^{T}\right)^{(\mathcal{P}_{j-1}^{T})}\equiv\gamma^{T}\otimes
K^{T}_{2}\otimes\cdots\otimes K^{T}_{j-1}$ (4.5)

for the marginal of $G^{T}$ on coordinates corresponding to elements of
$\mathcal{P}_{j-1}^{T}$.

In virtue of [3], the generalized Gibbs measure $G^{T}$ is the unique solution
to the Boltzmann-Gibbs variational principle to given chain: precisely, with

$\bm{m}\overset{\text{\text{def}}}{=}\arg\min_{\bm{n}\in\Delta}P^{T}(\bm{n})$
(4.6)

the optimal parameter in Parisi variational principle associated to a
$T$-chain, and recalling the Boltzmann-Gibbs variational principle (2.18), it
follows from [3, Theorem 2.3-2.5] that

$G^{T}(\bm{m})=\arg\sup_{\nu\in\mathcal{M}^{+}_{1}(S^{2^{n}-1})}\left\\{\Phi(\nu)-\mathfrak{J}^{T}(\nu)\right\\}\,.$
(4.7)

In particular, the measure $G^{T}(\bm{m})$ satisfies all constraints for the
empirical measures in the associated Boltzmann-Gibbs principle for the chain
$T$, i.e.

$G^{T}(\bm{m})\in\bigcap\limits_{k=1}^{n}C_{A_{k}^{T}}.$ (4.8)

Without loss of generality666Such form of the minimal chain can always be
achieved by re-labelling., we shall assume here that the minimal chain

$\mathcal{T}\overset{\text{\text{def}}}{=}\arg\min\limits_{T\in\mathcal{C}_{n}}f^{T}(\phi)\,,$
(4.9)

i.e. the one which minimizes all Parisi variational principles, is given by

$\mathcal{T}=\left\\{A^{\mathcal{T}}_{k}\right\\}_{k=0}^{n}\quad\text{with}\quad
A^{\mathcal{T}}_{k}\overset{\text{\text{def}}}{=}\\{1,2,\cdots,k-1,k\\}.$
(4.10)

We now claim that the generalized Gibbs measure
$G^{\mathcal{T}}_{\bm{m}^{\prime}}$ associated to the minimal chain satisfies
all constraints (2.5) or, which is the same, that

$\bm{m}^{\prime}\overset{\text{\text{def}}}{=}\arg\min_{\bm{m}\in\Delta}P^{\mathcal{T}}(\bm{m})\Longrightarrow
G^{\mathcal{T}}_{\bm{m}^{\prime}}\in\bigcap_{J\in\mathcal{P}_{n}}C_{J}.$
(4.11)

This amounts to saying that the measure $G^{\mathcal{T}}_{\bm{m}^{\prime}}$ is
a viable candidate for the Boltzmann-Gibbs variational principle for the
nonhierarchical Perceptron GREM: Theorem 2.1 would then imply that

$\displaystyle f(\phi)$ $\displaystyle\geq\int\phi
dG^{\mathcal{T}}(\bm{m}^{\prime})-H\left(G^{\mathcal{T}}(\bm{m}^{\prime})\mid\mu\right)$
(4.12)
$\displaystyle=\min_{T\in\mathcal{C}_{n}}\left\\{\min_{m\in\Delta}P_{T}(\bm{m})\right\\},$

with the second line by definition/construction of
$\mathcal{T},\bm{m}^{\prime}$, and Theorem 2.2 would follow.

It therefore remains to prove the key claim (4.11). This requires some
preliminary observations. Recalling that $\phi^{T}_{l}$ depends on $m_{j}$
only for $l\in\\{1,\cdots,j-1\\}$ a simple computation yields

$\displaystyle\partial_{j}P^{T}(\bm{m})=\frac{1}{m_{j}^{2}}\left[\int
H\left(\,K_{j}^{T}(\bm{x}^{(1)},\cdots,\bm{x}^{(j-1)},\cdot)\,|\,\mu^{\left(T_{j}\right)}\,\right)\,G^{T}_{j-1}(d\bm{x}^{(1)},\cdots,d\bm{x}^{(j-1)})-\frac{\log
2}{n}\right],$ (4.13)

cfr. also [3, eq. 3.13]. Using that $G^{T}_{j-1}\otimes K^{T}_{j}\equiv
G^{T}_{j}$, the integral in the above can be written as

$\displaystyle\int
H\left(\,K_{j}^{T}(\bm{x}^{(1)},\cdots,\bm{x}^{(j-1)},\cdot)\,|\,\mu^{\left(T_{j}\right)}\,\right)\,G^{T}_{j-1}(d\bm{x}^{(1)},\cdots,d\bm{x}^{(j-1)})$
(4.14) $\displaystyle\hskip
85.35826pt=\int\log\left(f(\bm{x}^{(j)}|\bm{x}^{(1)},\cdots,\bm{x}^{(j-1)})\right)G^{T}_{j}(d\bm{x}^{(1)},\cdots,d\bm{x}^{(j)})$

where we shortened $f(\cdot|\bm{x}^{(1)},\cdots,\bm{x}^{(j-1)})$ for the
Radon-Nikodym derivative of the measure
$K_{j}^{T}(\bm{x}^{(1)},\cdots,\bm{x}^{(j-1)},\cdot)$ with respect to
$\mu^{\left(T_{j}\right)}$. Following the steps (3.4)-(3.5) with
$\mu^{(B^{c})}:=\mu^{\left(T_{j}\right)}$, $\nu^{(B^{c}|B)}:=K^{T}_{j}$ (in
which case $\nu^{(B)}:=G^{T}_{j-1}$, $\nu:=G^{T}_{j}$) we get

$\int\log\left(f(\bm{x}^{(j)}|\bm{x}^{(1)},\cdots,\bm{x}^{(j-1)})\right)G^{T}_{j}(d\bm{x}^{(1)},\cdots,d\bm{x}^{(j)})=H\left(\,G^{T}_{j}\,|\,G^{T}_{j-1}\otimes\mu^{(T_{j})}\right),$

which implies

$\partial_{j}P^{T}(\bm{m})=\frac{1}{m_{j}^{2}}\left[H\left(\,G^{T}_{j}\,|\,G^{T}_{j-1}\otimes\mu^{(T_{j})}\right)-\frac{\log
2}{n}\right].$ (4.15)

Coming back to our main task, a proof that the minimal chain satisfies all
side constraints in the Boltzmann-Gibbs principle, let

$J=\left\\{j_{1}<j_{2}<\cdots<j_{M-1}<j_{M}\right\\}\in\mathcal{P}_{n}$ (4.16)

be a generic non-empty subset of $I$. The goal is thus to show that

$H\left(\,\left(G^{\mathcal{T}}\right)^{(\mathcal{P}_{J})}\,|\,\mu^{(\mathcal{P}_{J})}\,\right)\leq\frac{M}{n}\log
2.$ (4.17)

Recall the definition (2.11) of the index $k_{J}$ with the property that
$J\in\mathcal{T}_{k_{J}}$: under (4.10) it holds that
${\mathcal{T}}_{k}=\mathcal{P}_{k}^{\mathcal{T}}\setminus\mathcal{P}_{k-1}^{\mathcal{T}}\equiv\mathcal{P}_{(1,\cdots,k)}\setminus\mathcal{P}_{(1,\cdots,k-1)},k\in
I$, hence

$k_{J}=\max\\{j:\,j\in J\\}=j_{M}\,\geq\,M.$

In light of (4.15), which shows how the conditions on the relative entropies
relate to the partial derivatives of the Parisi functions, it is natural to
distinguish two cases, depending on the latter being negative or positive.

First case: $\partial_{k_{J}}P^{\mathcal{T}}(\bm{m}^{\prime})\leq 0$. It then
follows from (4.15)

$H\left(G^{\mathcal{T}}_{k_{J}}\,|\,G^{\mathcal{T}}_{k_{J}-1}\otimes\mu^{({\mathcal{T}}_{k_{J}})}\right)\leq\frac{\log
2}{n}.$ (4.18)

We distinguish two sub-cases:

  * i)

When $M=1$, namely when $J=\\{j_{1}\\}$ and $k_{J}=j_{1}$, we have
$\mathcal{P}_{J}=\\{J\\}\subseteq{\mathcal{T}}_{k_{J}}$. In particular, the
marginal of
$\,\,G^{\mathcal{T}}_{k_{J}-1}\otimes\mu^{({\mathcal{T}}_{k_{J}})}\,\,$ on
$\mathcal{P}_{J}$ is $\mu^{(\mathcal{P}_{J})}=\mu_{J}$ hence

$\displaystyle
H\left((G^{\mathcal{T}})^{(\mathcal{P}_{J})}\,|\,\mu^{(\mathcal{P}_{J})}\right)$
$\displaystyle=H\left((G^{\mathcal{T}})^{(\\{J\\})}\,|\,\mu_{J}\right)$ (4.19)
$\displaystyle\stackrel{{\scriptstyle\eqref{AM}}}{{\leq}}H\left(G_{k_{J}}^{\mathcal{T}}\,|\,G^{\mathcal{T}}_{k_{J}-1}\otimes\mu^{({\mathcal{T}}_{k_{J}})}\right)\stackrel{{\scriptstyle\eqref{deriv_non_pos}}}{{\leq}}\frac{\log
2}{n},$

which establishes (4.17) for $J$-s of cardinality one.

  * ii)

For sets of cardinality $M=2,\dots,n$ we proceed inductively: with

${\mathfrak{O}}\overset{\text{\text{def}}}{=}J\setminus{\\{k_{J}\\}}=\\{j_{1},j_{2},\dots,j_{M-1}\\}\,,$

we assume that

$H\left((G^{\mathcal{T}})^{(\mathcal{P}_{{\mathfrak{O}}})}\,|\,\mu^{(\mathcal{P}_{{\mathfrak{O}}})}\right)\leq\frac{M-1}{n}\log
2\,.$ (4.20)

and claim that

$H\left((G^{\mathcal{T}})^{(\mathcal{P}_{J})}\,|\,\mu^{(\mathcal{P}_{J})}\right)\leq\frac{M}{n}\log
2.$ (4.21)

To see this we first observe that, evidently, $|\mathfrak{O}|=M-1$, and

$\mathcal{P}_{\mathfrak{O}}\subseteq\mathcal{P}_{k_{J}-1}^{\mathcal{T}},\quad\mathcal{P}_{J}\subseteq\mathcal{P}_{{\mathfrak{O}}}\cup\mathcal{T}_{k_{J}},\qquad\mathcal{P}_{{\mathfrak{O}}}\cap\mathcal{T}_{k_{J}}=\emptyset,$

hence by the monotonicity property (3.2) it holds

$\displaystyle
H\left((G^{\mathcal{T}})^{(\mathcal{P}_{J})}\,|\,\mu^{(\mathcal{P}_{J})}\right)\leq
H\left((G^{\mathcal{T}})^{(\mathcal{P}_{{\mathfrak{O}}}\,\cup\,\mathcal{T}_{k_{J}})}\,|\,\mu^{(\mathcal{P}_{{\mathfrak{O}}}\,\cup\,\mathcal{T}_{k_{J}})}\right)$
(4.22)
$\displaystyle\stackrel{{\scriptstyle\eqref{chain_rule}}}{{=}}H\left((G^{\mathcal{T}})^{(\mathcal{P}_{{\mathfrak{O}}})}\,|\,\mu^{(\mathcal{P}_{{\mathfrak{O}}})}\right)+H\left((G^{\mathcal{T}})^{(\mathcal{P}_{\mathfrak{O}}\,\cup\,\mathcal{T}_{k_{J}})}\,|\,(G^{\mathcal{T}})^{(\mathcal{P}_{{\mathfrak{O}}})}\otimes\mu^{(\mathcal{T}_{k_{J}})}\right)$
$\displaystyle\stackrel{{\scriptstyle\eqref{indu}}}{{\leq}}\frac{M-1}{n}\log
2+H\left((G^{\mathcal{T}})^{(\mathcal{P}_{{\mathfrak{O}}}\,\cup\,\mathcal{T}_{k_{J}})}\,|\,(G^{\mathcal{T}})^{(\mathcal{P}_{{\mathfrak{O}}})}\otimes\mu^{(\mathcal{T}_{k_{J}})}\right)\,.$

For the second summand above we write

$\displaystyle
H\left((G^{\mathcal{T}})^{(\mathcal{P}_{{\mathfrak{O}}}\,\cup\,\mathcal{T}_{k_{J}})}\,|\,(G^{\mathcal{T}})^{(\mathcal{P}_{\mathfrak{O}})}\otimes\mu^{(\mathcal{T}_{k_{J}})}\right)$
$\displaystyle\stackrel{{\scriptstyle\eqref{AM}}}{{\leq}}H\left(G^{\mathcal{T}}_{k_{J}}\,|\,G^{\mathcal{T}}_{k_{J}-1}\otimes\mu^{(\mathcal{T}_{k_{J}})}\right)$
(4.23)
$\displaystyle\stackrel{{\scriptstyle\eqref{deriv_non_pos}}}{{\leq}}\frac{\log
2}{n},$

Plugging (4.23) into (LABEL:baa) therefore yields

$H\left((G^{\mathcal{T}})^{(\mathcal{P}_{J})}\,|\,\mu^{(\mathcal{P}_{J})}\right)\leq\frac{M-1}{n}\log
2+\frac{\log 2}{n}=\frac{M}{n}\log 2,$ (4.24)

settling the induction step (4.21).

Second case: $\partial_{k_{J}}P^{\mathcal{T}}(\bm{m}^{\prime})>0$. It will
become clear in the treatment that this is a somewhat degenerate situation
where the minimal chain is not unique. As a matter of fact, we will use such
lack of uniqueness to our advantage, in sofar we will deduce the validity of
the side constraints from the properties of the Parisi functional evaluated in
yet a second, well chosen (and also: minimal) chain. To see how this goes, we
first claim that for $k\in\\{2,\cdots,n\\}$ the following implication holds
true:

$\partial_{k}P^{\mathcal{T}}(\bm{m}^{\prime})>0\Longrightarrow\;\forall\,j=1,\cdots,k-1:\,m^{\prime}_{j}=m^{\prime}_{j+1}\,.$
(4.25)

We will prove the following, fully equivalent implication: with

$l=l(\mathcal{T},k)\overset{\text{\text{def}}}{=}\min\left\\{\,\,j:j\in\\{1,2,\cdots,k-2,k-1\\};\,\,\,m^{\prime}_{j}=m^{\prime}_{j+1}\,\,\right\\},$

we claim that

$\partial_{k}P^{\mathcal{T}}(\bm{m}^{\prime})>0\Longrightarrow l=1.$ (4.26)

Proceeding by contradiction, let us assume that $l>1$, in which case $l-1\geq
1$ and

$m^{\prime}_{l-1}<m^{\prime}_{l}=m^{\prime}_{l+1}=\cdots=m^{\prime}_{k-1}=m^{\prime}_{k}\leq
m^{\prime}_{k+1}$

(with $m^{\prime}_{n+1}=1$). Since
$\bm{m}^{\prime}=\arg\min_{\bm{m}\in\Delta}P^{\mathcal{T}}(\bm{m})$, the
function

$m_{k}\in[m^{\prime}_{l-1},m^{\prime}_{k+1}]\,\rightarrow
P^{\mathcal{T}}(m^{\prime}_{1},\cdots,m^{\prime}_{k-1},m_{k},m^{\prime}_{k+1},\cdots,m^{\prime}_{n})$

assumes its minimum in
$m_{k}=m^{\prime}_{k}\in(m^{\prime}_{l-1},m^{\prime}_{k+1}]$ and this implies
$\partial_{k}P^{\mathcal{T}}(\bm{m}^{\prime})\leq 0$, which contradicts our
working assumption unless $l=1$, hence

$m_{1}^{\prime}=m_{2}^{\prime}=\dots=m_{k}^{\prime},$ (4.27)

and (4.26) is settled.

The next, and final, step is to show - as anticipated - that if
$l(\mathcal{T},k_{J})=1$ we may find yet another chain $\mathcal{R}$ with the
same ”Parisi free energy” as the chain $\mathcal{T}$, but from which we may
also deduce the validity of the side constraints (4.17), namely that for
$J=\\{j_{1}<j_{2}<\cdots<j_{M}\\}$,

$H\left(\,\left(G^{\mathcal{T}}\right)^{(\mathcal{P}_{J})}\,|\,\mu^{(\mathcal{P}_{J})}\,\right)\leq\frac{M}{n}\log
2.$ (4.28)

Towards this goal, define

$\\{b_{1}<\cdots<b_{j_{M}-M}\\}\overset{\text{\text{def}}}{=}A^{\mathcal{T}}_{j_{M}}\setminus
J\equiv\\{1,2,\cdots,j_{M}-1,j_{M}\\}\setminus\\{j_{1},\cdots,j_{M}\\},$

denote by
$\mathcal{R}=\left\\{A^{\mathcal{R}}_{k}\right\\}_{k=0}^{n}\in\mathcal{C}_{n}$
the chain with

$A^{\mathcal{R}}_{k}\overset{\text{\text{def}}}{=}\begin{cases}(j_{1},j_{2},\cdots,j_{k-1},j_{k})&\text{if}\quad
k\in\\{1,\cdots,M\\}\\\
J\cup\left\\{b_{1},\cdots,b_{k-M}\right\\}&\text{if}\quad
k\in\\{M+1,\cdots,j_{M}-1\\}\\\ A^{\mathcal{T}}_{k}&\text{if}\quad
k\in\\{j_{M},\cdots,n\\}\end{cases},$ (4.29)

and consider the corresponding extremal parameter

$\bm{m}^{\prime\prime}=\text{argmin}_{\bm{m}\in\Delta}P^{\mathcal{R}}(\bm{m}).$

In light of (4.27), with $k=k_{J}$ and since $k_{J}=j_{M}$ we have for the
coordinates of the extremal parameter $\bm{m}^{\prime}$ associated to
$\mathcal{T}$ that $m_{1}^{\prime}=m_{2}^{\prime}=\dots=m_{j_{M}}^{\prime}$
and therefore

$\frac{m^{\prime}_{l}}{m^{\prime}_{l+1}}=1,\qquad l=1,\cdots,j_{M}-1.$

Due to the recursive construction (2.16), and shortening
$\bm{x}^{(j)}=(x_{J})_{J\in\mathcal{T}_{j}}$, it follows that

$\displaystyle\phi^{\mathcal{T}}_{0}(\bm{m}^{\prime})$
$\displaystyle=\frac{1}{m_{1}^{\prime}}\log\int
e^{{m_{1}^{\prime}}\phi^{\mathcal{T}}_{1}(\bm{x}^{(1)})}\mu^{(\mathcal{T}_{1})}(d\bm{x}^{(1)})$
(4.30)
$\displaystyle=\frac{1}{m_{1}^{\prime}}\log\int\exp\left[\frac{m^{\prime}_{1}}{m^{\prime}_{2}}\log\int
e^{m_{2}^{\prime}\phi^{\mathcal{T}}_{2}(\bm{x}^{(1)},\bm{x}^{(2)})}\mu^{(\mathcal{T}_{2})}(d\bm{x}^{(2)})\right]\mu^{({\mathcal{T}}_{1})}(d\bm{x}^{(1)})$
$\displaystyle=\frac{1}{m_{1}^{\prime}}\log\int\exp\left[{m_{2}^{\prime}\phi^{\mathcal{T}}_{2}(\bm{x}^{(1)},\bm{x}^{(2)})}\right]\mu^{({\mathcal{T}}_{1})}\otimes\mu^{({\mathcal{T}}_{2})}(d\bm{x}^{(1)},d\bm{x}^{(2)})\,.$

Again since $m_{1}^{\prime}=m_{2}^{\prime}$, the r.h.s. of (4.30) equals

$\displaystyle\frac{1}{m_{1}^{\prime}}\log\int\exp\left[{m_{1}^{\prime}\phi^{\mathcal{T}}_{2}(\bm{x}^{(1)},\bm{x}^{(2)})}\right]\mu^{({\mathcal{T}}_{1})}\otimes\mu^{({\mathcal{T}}_{2})}(d\bm{x}^{(1)},d\bm{x}^{(2)})$
(4.31)
$\displaystyle\qquad=\frac{1}{m_{1}^{\prime}}\log\int\exp\left[{m_{1}^{\prime}\phi^{\mathcal{T}}_{j_{M}}(\bm{x}^{(1)},\bm{x}^{(2)},\cdots,\bm{x}^{(j_{M})})}\right]\bigotimes_{l=1}^{j_{M}}\mu^{({\mathcal{T}}_{l})}(d\bm{x}^{(l)}),$

the last equality by iteration. All in all,

$\phi^{\mathcal{T}}_{0}(\bm{m}^{\prime})=\frac{1}{m_{1}^{\prime}}\log\int\exp\left[{m_{1}^{\prime}\phi^{\mathcal{T}}_{j_{M}}(\bm{x}^{(1)},\bm{x}^{(2)},\cdots,\bm{x}^{(j_{M})})}\right]\bigotimes_{l=1}^{j_{M}}\mu^{({\mathcal{T}}_{l})}(d\bm{x}^{(l)}),$
(4.32)

and in complete analogy for the $\mathcal{R}$-chain but this time with
$\bm{x}^{(j)}\overset{\text{\text{def}}}{=}(x_{J})_{J\in{\mathcal{R}}_{j}}$

$\phi^{\mathcal{R}}_{0}(\bm{m}^{\prime})=\frac{1}{m_{1}^{\prime}}\log\int\exp\left[{m_{1}^{\prime}\phi^{\mathcal{R}}_{j_{M}}(\bm{x}^{(1)},\bm{x}^{(2)},\cdots,\bm{x}^{(j_{M})})}\right]\bigotimes_{l=1}^{j_{M}}\mu^{({\mathcal{R}}_{l})}(d\bm{x}^{(l)}).$
(4.33)

Since
$\bigcup_{l=1}^{j_{M}}\mathcal{T}_{l}=\mathcal{P}^{\mathcal{T}}_{j_{M}}\equiv\mathcal{P}^{\mathcal{R}}_{j_{M}}=\bigcup_{l=1}^{j_{M}}\mathcal{R}_{l}$,
the product measures in (4.32) and (4.33) are the same, to wit

$\bigotimes_{l=1}^{j_{M}}\mu^{({\mathcal{R}}_{l})}=\bigotimes_{l=1}^{j_{M}}\mu^{({\mathcal{T}}_{l})}=\mu^{(\mathcal{P}^{\mathcal{T}}_{j_{M}})}=\bigotimes_{J\in\mathcal{P}_{\\{1,\cdots,j_{M}\\}}}\mu_{J}(dx_{J})\,.$
(4.34)

Furthermore, the form taken by the functions
$\phi^{\mathcal{R}}_{j_{M}}(\bm{m}^{\prime}),\cdots,\phi^{\mathcal{R}}_{n}(\bm{m}^{\prime})$
and respectively
$\phi^{\mathcal{T}}_{j_{M}}(\bm{m}^{\prime}),\cdots,\phi^{\mathcal{T}}_{n}(\bm{m}^{\prime})$
depends on the sets $\\{A_{k}^{\mathcal{T}}\\}_{k=J_{M}+1}^{n}$ only,
respectively $\\{A_{k}^{\mathcal{R}}\\}_{k=J_{M}+1}^{n}$: as these sets
coincide, it follows, in particular, that

$\phi^{\mathcal{R}}_{j_{M}}(\bm{m}^{\prime})\equiv\phi^{\mathcal{T}}_{j_{M}}(\bm{m}^{\prime}).$
(4.35)

Combining (4.32)-(4.35), we therefore see that

$\displaystyle P^{\mathcal{T}}(\bm{m}^{\prime})$ $\displaystyle=\frac{\log
2}{n}\sum_{k=1}^{n}\frac{1}{m_{k}^{\prime}}+\phi_{0}^{\mathcal{T}}(\bm{m}^{\prime})=\frac{\log
2}{n}\sum_{k=1}^{n}\frac{1}{m_{k}^{\prime}}+\phi_{0}^{\mathcal{R}}(\bm{m}^{\prime})=P^{\mathcal{R}}(\bm{m}^{\prime})\,,$
(4.36)

and by similar reasoning,

$G^{{\mathcal{T}}}(\bm{m}^{\prime})=G^{\mathcal{R}}(\bm{m}^{\prime}).$ (4.37)

From (4.36) and minimality of the chain $\mathcal{T}$, i.e.

$P^{\mathcal{T}}(\bm{m}^{\prime})=\min\limits_{\bm{m}\in\Delta}P^{\mathcal{T}}(\bm{m})\leq\min\limits_{\bm{m}\in\Delta}P^{\mathcal{R}}(\bm{m})=P^{\mathcal{R}}(\bm{m}^{\prime\prime}),$

if follows in particular that

$P^{\mathcal{R}}(\bm{m}^{\prime})=P^{\mathcal{R}}(\bm{m}^{\prime\prime}).$
(4.38)

By uniqueness of the minimum of the Parisi principle, see [3, Prop. 3.6], it
thus follows that $\bm{m}^{\prime}=\bm{m}^{\prime\prime}$, which together with
(4.37) implies

$G^{{\mathcal{T}}}(\bm{m}^{\prime})=G^{\mathcal{R}}(\bm{m}^{\prime})=G^{\mathcal{R}}(\bm{m}^{\prime\prime})\,.$
(4.39)

Since $A^{\mathcal{R}}_{M}=J$, we have

$\displaystyle
H\left(\,(G^{\mathcal{T}})^{(\mathcal{P}_{J})}\,|\,\mu^{(\mathcal{P}_{J})}\,\right)$
$\displaystyle=H\left(\,[G^{\mathcal{T}}(\bm{m}^{\prime})]^{(\mathcal{P}_{J})}\,|\,\mu^{(\mathcal{P}_{J})}\,\right)$
(4.40)
$\displaystyle=H\left(\,[G^{\mathcal{R}}(\bm{m}^{\prime\prime})]^{(\mathcal{P}_{M}^{\mathcal{R}})}\,|\,\mu^{(\mathcal{P}_{M}^{\mathcal{R}})}\,\right)\leq\frac{M}{n}\log
2,$

the last inequality since $G^{\mathcal{R}}(\bm{m}^{\prime\prime})\in
C_{A^{\mathcal{R}}_{M}}$, i.e. the measure
$G^{\mathcal{R}}(\bm{m}^{\prime\prime})$ satisfies the side constraints on the
empirical measures. This concludes the proof of Theorem 2.2.

$\square$

## References

  * [1] Bolthausen, Erwin, and Nicola Kistler. On a nonhierarchical version of the generalized random energy model. The Annals of Applied Probability 16.1 (2006): 1-14.
  * [2] Bolthausen, Erwin, and Nicola Kistler. On a nonhierarchical version of the generalized random energy model. II. Ultrametricity. Stoch. Proc. Appl. Vol. 119 (2009): 2357-2386.
  * [3] Bolthausen, Erwin, and Nicola Kistler. A quenched large deviation principle and a Parisi formula for a perceptron version of the GREM. Probability in Complex Physical Systems , Springer PROMS 11 (2012): 425-442.
  * [4] Derrida, Bernard. Random-energy model: An exactly solvable model of disordered systems. Physical Review B 24.5 (1981): 2613.
  * [5] Derrida, Bernard. A generalization of the random energy model that includes correlations between the energies. J. Phys. Lett. 46 (1985): 401-407.
  * [6] Mézard, Marc, Giorgio Parisi, and Miguel A. Virasoro. Spin glass theory and beyond. World Scientific, Singapore (1987).
  * [7] Ghirlanda, Stefano, and Francesco Guerra. General properties of overlap probability distributions in disordered spin systems. Towards Parisi ultrametricity. Journal of Physics A: Mathematical and General 31.46 (1998): 9149.
  * [8] Guerra, Francesco. Broken replica symmetry bounds in the mean field spin glass model. Comm. in Math. Phys. Vol. 233 (2002).
  * [9] Panchenko, Dmitry. The Sherrington-Kirkpatrick model. Springer Science & Business Media, 2013.
  * [10] Panchenko, Dmitry. The Parisi ultrametricity conjecture. Annals of Mathematics (2013): 383-393.
  * [11] Plefka, Timm. Convergence condition of the TAP equation for the infinite-ranged Ising spin glass model. Journal of Physics A: Mathematical and general 15.6 (1982): 1971.
  * [12] Polyanskiy, Yuri, and Yihong Wu. Lecture notes on Information Theory, MIT University Press (2017)
  * [13] Subag, Eliran. The geometry of the Gibbs measure of pure spherical spin glasses. Invent. Math., 210(1):135–209, 2017
  * [14] Subag, Eliran. The free energy of spherical pure p-spin models – computation from the TAP approach, arXiv preprint: 2101.04352
  * [15] Sherrington, David, and Scott Kirkpatrick. Solvable model of a spin-glass. Physical review letters 35.26 (1975): 1792.
  * [16] Talagrand, Michel The Parisi formula. Annals of Mathematics Second Series, Vol. 163, No. 1 (2006): 221-263.
  * [17] Thouless, David J., Philip W. Anderson, and Robert G. Palmer. Solution of ’solvable model of a spin glass’. Philosophical Magazine 35.3 (1977): 593-601.


* (32) J. M. Zhang and R. Dong, Eur. J. Phys. 31, 591 (2010); D. Raventós, T. Graß, M. Lewenstein, and B. Juliá-Díaz, J. Phys. B 50, 113001 (2017).
  * (33) T. D. Kühner and H. Monien, Phys. Rev. B 58, 14741(R) (1998).
  * (34) V. F. Elesin, V. A. Kashurnikov, and L. A. Openov, JETP Lett. 60, 177 (1994).
  * (35) M. Girardeau, J. Math. Phys. 1, 516 (1960).
  * (36) T. Kinoshita, T. Wenger, and D. S Weiss, Science 305, 1125 (2004).
  * (37) V. I. Yukalov and M. Girardeau, Laser Phys. Lett. 2, 375 (2005).
  * (38) C. Yannouleas and U. Landman, Rep. Prog. Phys. 70, 2067 (2007).
  * (39) J. A. Sheikh, J. Dobaczewski, P. Ring, L. M. Robledo, and C. Yannouleas, arXiv:1901.06992.
  * (40) J. M. Landsberg, _Tensors: Geometry and Applications_ (AMS, Rhode Island, 2012).
  * (41) A. R. P. Rau, Am. J. Phys. 80, 406 (2012); J. Astrophys. Astron. 17, 113 (1996).
  * (42) H. Bethe, Z. Phys. 57, 815 (1929).
  * (43) E. A. Hylleraas, Z. Phys. 60, 624 (1930); 63, 291 (1930).
  * (44) S. Chandrasekhar, Astrophys. J. 100, 176 (1944).
  * (45) J. M. Zhang, D. Braak, and M. Kollar, Phys. Rev. Lett. 109, 116405 (2012); Phys. Rev. A 87, 023613 (2013).
  * (46) E. N. Economou, _Green’s Functions in Quantum Physics_ 3rd ed. (Springer-Verlag, Berlin, 2006)
  * (47) A. S. Dehkharghani, A. G. Volosniev, E. J. Lindgren, J. Rotureau, C. Forssén, D. V. Fedorov, A. S. Jensen, N. T. Zinner, Scientific Reports 5, 10675 (2015); A. S. Dehkharghani, A. G. Volosniev, N. T. Zinner, Phys. Rev. A 92, 031601(R) (2015); A. S. Dehkharghani, A. G. Volosniev, and N. T. Zinner, Phys. Rev. Lett. 121, 080405 (2018).
  * (48) S. Pilati and M. Troyer, Phys. Rev. Lett. 108, 155301 (2012).
  * (49) Note that by Proposition 3, any state of a two-site Bose-Hubbard model is necessarily a permanent state. We are therefore not interested in such trivial cases.
  * (50) A. J. Coleman, Rev. Mod. Phys. 35, 668 (1963).
  * (51) R. E. Borland and K. Dennis, J. Phys. B 3, 887 (1970).
  * (52) R. E. Borland and K. Dennis, J. Phys. B 5, 7 (1972).
  * (53) M. Altunbulak and A. Klyachko, Commun. Math. Phys. 282, 287 (2008).
  * (54) C. Schilling, D. Gross, and M. Christandl, Phys. Rev. Lett. 110, 040404 (2013).
  * (55) C. P. Chen and H. Schomerus, Phys. Rev. B 104, 205411 (2021).