# Typical sofic entropy and local limits for free group shift systems

Christopher Shriver

###### Abstract

We show that for any invariant measure $\mu$ on a free group shift system,
there are two numbers $h^{\flat}\leq
h^{\sharp}\in\\{-\infty\\}\cup[0,\log\lvert\mathtt{A}\rvert]$ which in some
sense are the typical upper and lower sofic entropy values. We also give a
condition under which $h^{\flat}=h^{\sharp}=\operatorname{f}(\mu)$. This can
be used to compute typical local limits of finitary Gibbs states over
sequences of random regular graphs. As examples, we work out typical local
limits of the Ising and Potts models.

We also show that, for Markov chains, the Kesten–Stigum second-eigenvalue
reconstruction criterion actually implies there are no good models over a
typical sofic approximation (i.e. $h^{\sharp}=-\infty$). In particular, we
have an exact value for the typical entropy $h^{\flat}=h^{\sharp}$ of the
free-boundary Ising state: it is equal to the annealed entropy
$\operatorname{f}$ for interaction strengths up to the reconstruction
threshold, after which it drops abruptly to $-\infty$.

###### Contents

  1. 1 Introduction
    1. 1.1 Typical sofic entropy values
    2. 1.2 Typical local limits
    3. 1.3 Kesten–Stigum bound for typicality
    4. 1.4 Acknowledgements
  2. 2 Definitions and basic lemmas
    1. 2.1 Sofic entropy
    2. 2.2 $\operatorname{f}$ invariant
    3. 2.3 Exponentially concentrated random sofic approximations
    4. 2.4 Upper and lower typical entropy functions $h^{\sharp}$, $h^{\flat}$
      1. 2.4.1 Properties of $\rho$
      2. 2.4.2 Properties of $h^{\sharp}$, $h^{\flat}$
      3. 2.4.3 Consequences of second-moment condition
  3. 3 Typical local limits for nearest-neighbor interactions
    1. 3.1 Ferromagnetic Ising model
    2. 3.2 Antiferromagnetic Ising model
    3. 3.3 Potts model
    4. 3.4 Proof of Lemma 3.5
  4. 4 Kesten–Stigum bound implies atypicality
  5. 5 Typical upper and lower sofic entropy values: Proof of Theorem 1.1

##  1 Introduction

Throughout, let $\mathtt{A}$ be a finite set (an “alphabet”), $\Gamma$ be the
free group of rank $r$, and
$\mu\in\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma})$ be a shift-invariant
measure. The shift action is defined precisely in Section 2. We will usually
identify $\Gamma$ with its left Cayley graph, which is a $2r$-regular tree.

In this paper, we consider the question of whether a typical random
$2r$-regular graph, having geometry locally like $\Gamma$, admits vertex
labelings whose average local statistics are close to $\mu$. We also
investigate how many such labelings a typical graph has and, as an
application, work out some typical local limits of Gibbs states on random
regular graphs.

Before stating the main results, we give a brief introduction to sofic
entropy. See Section 2 below for more precise definitions.

A sofic approximation to $\Gamma$ is a sequence $\Sigma$ of $2r$-regular
graphs which converge locally to the Cayley graph of $\Gamma$. These graphs
may be random or deterministic. In the deterministic case,
$\overline{\operatorname{h}}_{\Sigma}(\mu)$ is the upper exponential growth
rate of the number of vertex labelings of these graphs whose average local
statistics are consistent with $\mu$. We call these labelings _microstates_ or
_good models_ for $\mu$. If the graphs are random, then
$\overline{\operatorname{h}}_{\Sigma}$ refers to the upper exponential growth
rate of the _expected_ number of such labelings. Similarly,
$\underline{\operatorname{h}}_{\Sigma}$ denotes the lower exponential growth
rate. Sofic entropy was introduced by Lewis Bowen as an isomorphism invariant
which distinguishes between Bernoulli shifts (iid processes) over nonamenable
groups [Bow10a].

An important special case is when the random graphs are drawn from the uniform
permutation model $\mathbb{P}^{\mathrm{up}}$: given a finite set $V$, pick $r$
permutations in $\operatorname{Sym}(V)$ uniformly and independently. Then
produce a graph with vertex set $V$ by connecting each $v\in V$ to its images
under the $r$ permutations. This tuple of $r$ permutations can also be thought
of as an element of $\operatorname{Hom}(\Gamma,\operatorname{Sym}(V))$, where
the $i$th generator of $\Gamma$ acts on $V$ by the $i$th permutation. If
$\Sigma$ is this sequence of random graphs,
$\overline{\operatorname{h}}_{\Sigma}=\underline{\operatorname{h}}_{\Sigma}$
is called the $\operatorname{f}$ invariant [Bow10c, Bow10], which we will
denote by $\operatorname{f}(\cdot)$.

We will state some results for a more general kind of random sofic
approximation which we call “exponentially concentrated random sofic
approximations” and call the associated upper and lower “annealed” entropies
$\overline{\operatorname{h}}^{\mathrm{ann}}(\cdot)$ and
$\underline{\operatorname{h}}^{\mathrm{ann}}(\cdot)$. See Section 2.3 for
definitions. In the present paper we will only establish that the uniform
permutation model has this property, but the stochastic block models
introduced in [Shr22a] are other likely candidates.

###  1.1 Typical sofic entropy values

We say that $\mu$ satisfies the _second-moment criterion_ for a random sofic
approximation if for every joining $\lambda$ of $\mu$ with itself we have
$\overline{\operatorname{h}}^{\mathrm{ann}}(\lambda)\leq
2\underline{\operatorname{h}}^{\mathrm{ann}}(\mu)$; recall that a joining is a
shift-invariant coupling.

In the case of the uniform permutation model, an equivalent formulation is
that the product $\mu\times\mu$ has maximal $\operatorname{f}$ invariant among
all self-joinings of $\mu$. Note that we do not require the product to be the
_only_ joining with maximal $\operatorname{f}$. For Gibbs measures of nearest-
neighbor interactions with no hard constraints, the second-moment criterion is
implied by non-reconstruction [Shr21, Corollary 16].

In the uniform case, Proposition 4.1 of [Shr23] states that if $\mu$ satisfies
the second-moment criterion then
$\underline{\operatorname{h}}_{\Sigma}(\mu)=\overline{\operatorname{h}}_{\Sigma}(\mu)=\operatorname{f}(\mu)$
for a “typical” sofic approximation $\Sigma$ to $\Gamma$. In general, when we
say a property holds for a typical sofic approximation, we mean that there is
a sequence sets of homomorphisms
$\\{S_{n}\subset\operatorname{Hom}(\Gamma,\operatorname{Sym}(n))\\}_{n=1}^{\infty}$
such that $\mathbb{P}^{\mathrm{up}}(S_{n})\to 1$ and if $\sigma_{n}\in S_{n}$
for each $n$ then $\Sigma=\\{\sigma_{n}\\}_{n=1}^{\infty}$ is a sofic
approximation with that property.

This terminology somewhat obscures the order of quantifiers. In [Shr23], the
possibility of the sequence $\\{S_{n}\\}_{n=1}^{\infty}$ depending on $\mu$ is
not ruled out.

The first result of the present paper is a new version which is stronger in a
few ways: it shows that $\\{S_{n}\\}_{n=1}^{\infty}$ can be chosen independent
of $\mu$. Second, it shows there are typical upper and lower sofic entropy
values for $\mu$ even if $\mu$ does not satisfy the second-moment criterion.

We also allow any random sofic approximation which is exponentially
concentrated; see Section 2.3 for definitions. Note, however, that we only
verify this property for the uniform permutation model
$\mathbb{P}^{\mathrm{up}}$.

######  Theorem 1.1.

Let $\mathbb{P}$ denote an exponentially concentrated random sofic
approximation to $\Gamma$ and let $\mathtt{A}$ be a finite alphabet. Then
there exist upper semicontinuous functions
$h^{\sharp},h^{\flat}\colon\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma})\to\\{-\infty\\}\cup[0,\log\lvert\mathtt{A}\rvert]$
with the following property:

There exists a sequence
$\\{S_{n}\subset\operatorname{Hom}(\Gamma,\operatorname{Sym}(n)\\}_{n=1}^{\infty}$
such that $\mathbb{P}(S_{n})\to 1$ and if $\sigma_{n}\in S_{n}$ for each $n$
then $\Sigma=\\{\sigma_{n}\\}_{n=1}^{\infty}$ is a sofic approximation, and
for all $\mu\in\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma})$ we have

$\overline{\operatorname{h}}_{\Sigma}(\mu)=h^{\sharp}(\mu)$

and

$\underline{\operatorname{h}}_{\Sigma}(\mu)=h^{\flat}(\mu).$

We prove Theorem 1.1 in Section 5.

For the uniform permutation model, for every $\mu$ we have $h^{\flat}(\mu)\leq
h^{\sharp}(\mu)\leq\operatorname{f}(\mu)$ (Lemma 2.4), and if $\mu$ satisfies
the second-moment criterion, then the three quantities are equal (Cor. 2.7).

For more general sequences, since the upper and lower annealed entropies are
not always equal, in general we have
$h^{\flat}(\mu)\leq\underline{\operatorname{h}}^{\mathrm{ann}}(\mu)$ and
$h^{\sharp}(\mu)\leq\overline{\operatorname{h}}^{\mathrm{ann}}(\mu)$ (Lemma
2.4), and the second-moment criterion implies
$h^{\flat}(\mu)=\underline{\operatorname{h}}^{\mathrm{ann}}(\mu)$ and
$h^{\sharp}(\mu)=\overline{\operatorname{h}}^{\mathrm{ann}}(\mu)$ (Prop. 2.6).

######  Corollary 1.2.

For every $\mathbb{P}$ and $\mathtt{A}$, the typical entropies $h^{\sharp}$
and $h^{\flat}$ are isomorphism-invariant.

###### Proof.

This follows from Theorem 1.1 and isomorphism-invariance of
$\overline{\operatorname{h}}_{\Sigma},\underline{\operatorname{h}}_{\Sigma}$
for every sofic approximation $\Sigma$. ∎

###  1.2 Typical local limits

For precise definitions of terminology used here, see Section 3.

We use Theorem 1.1 to give a method for establishing typical local limits of
nearest-neighbor interactions. Given such an interaction and a sofic
approximation $\Sigma=\\{\sigma_{n}\\}_{n=1}^{\infty}$, we want to understand
the local statistics of the Gibbs states $\xi_{n}$ on the finite graphs
$\sigma_{n}$. If $n$ is large, then the graph of $\sigma_{n}$ is locally tree-
like at most vertices, so the marginal of the $\xi_{n}$ on the radius-$r$
neighborhood of most vertices can be compared to some fixed measure
$\mu\in\operatorname{Prob}(\mathtt{A}^{\Gamma})$.

If, for a typical sofic approximation, the average of these marginals
converges to $\mu$ in the weak topology as $n\to\infty$, we say that $\mu$ is
the typical local-on-average limit.

If all but a vanishing fraction of the marginals are close to $\mu$ as
$n\to\infty$, we say that $\mu$ is the typical local limit. We will establish
this stronger mode of convergence.

The idea is the following: Theorem 1.1 implies that if a measure $\mu$ is
$\operatorname{f}$-equilibrium and satisfies the second-moment criterion, then
it’s also equilibrium over typical $\Sigma$. This is because if
$\nu\in\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma})$ is any other state
then

$\operatorname{p}_{\Sigma}(\nu)=\overline{\operatorname{h}}_{\Sigma}(\nu)-u(\nu)=h^{\sharp}(\nu)-u(\nu)\leq\operatorname{f}(\nu)-u(\nu)=\operatorname{p}_{\operatorname{f}}(\nu)\leq\operatorname{p}_{\operatorname{f}}(\mu)=\cdots=\operatorname{p}_{\Sigma}(\mu).$

If $\mu$ is the unique $\operatorname{f}$-equilibrium state then the same
argument shows that $\mu$ is uniquely $\Sigma$-equilibrium over a typical
$\Sigma$. By [Shr23, Theorem 6.5], this means it must be the local-on-average
limit of Gibbs states over a typical sofic approximation.

In Section 3 we work out a few typical local limits over the uniform
permutation model $\mathbb{P}^{\mathrm{up}}$ using a refined version of this
method. After proving a general result (Proposition 3.1), as a first example
(Proposition 3.2) we show how this makes the ferromagnetic Ising case
(previously established in [MMS12]) easy. The antiferromagnetic case, which
does not seem to be in the literature, is also easily dealt with (Proposition
3.3).

Then we use calculations from [Gal+16] to work out the
$\mathbb{P}^{\mathrm{up}}$-typical local limit of the Potts model at all
temperatures but one – at the critical temperature where the ordered and
disordered states have the same pressure, we are unable to say exactly what
the limit is (Proposition 3.4).

Note that this method relies on there being only a few equilibrium states
among the uncountably many Gibbs states, which is a special property of
nonamenable systems: for nice enough interactions over amenable groups, all
Gibbs states are equilibrium [Tem84].

###  1.3 Kesten–Stigum bound for typicality

In this section we consider only the uniform permutation model.

As remarked above, if $\mu$ satisfies the second-moment criterion for the
uniform permutation model then
$h^{\flat}(\mu)=h^{\sharp}(\mu)=\operatorname{f}(\mu)$ (Cor. 2.7). If $\mu$ is
a Markov chain then this gives a simple formula for the typical entropy (see
Section 2.2). To complement this, we give a criterion which implies the
typical entropy of a $\Gamma$-indexed Markov chain is $-\infty$.

We call a measure $\mu$ _weakly typical_ if $h^{\sharp}(\mu)>-\infty$. This is
analogous to the notion of typicality introduced in [BS18]; see also [BBS22].

Given a Markov chain $\mu$ indexed by $\Gamma=\mathbb{F}_{r}$, let $\theta$
denote the second-largest (in absolute value) eigenvalue of its transition
matrix. The Kesten–Stigum bound for reconstruction states that if
$\lvert\theta\rvert^{2}(2r-1)>1$ then reconstruction is possible. (In fact,
this is the exact threshold for “census” reconstruction [MP03].) We prove the
following stronger version of this statement:

######  Theorem 1.3.

Suppose $\mu$ is a Markov chain indexed by $\Gamma$ and $\theta$ is the
second-largest eigenvalue of its transition matrix. If
$\lvert\theta\rvert^{2}(2r-1)>1$ then $\mu$ is not weakly typical.

We describe this as stronger because, for nearest-neighbor interactions with
no hard constraints (which in this case means the Markov transition matrix has
all positive entries), nonreconstruction implies the second moment criterion
[Shr21, Corollary 16] which implies typicality (by Theorem 1.1 or [Shr23,
Proposition 4.1]).

We actually show something which may be even stronger: that if
$\lvert\theta\rvert^{2}(2r-1)>1$ then the Koopman representation on
$L_{0}^{2}(\mu)$ is not weakly contained in the left-regular representation of
$\Gamma$. Here $L_{0}^{2}(\mu)$ is the Hilbert space of square-integrable
mean-zero functions on $(\mathtt{A}^{\Gamma},\mu)$. This weak containment is
implied by typicality (Thm. 4.1) but we do not know if the converse is true.

The proof is related to proofs of some correlation bounds for factors of iid
processes [BSV15, Lyo17].

As an example, we apply this to the Ising model: let $\mathtt{A}=\\{-1,+1\\}$,
and for each $\theta\in(-1/2,1/2)$ let
$\mu_{\theta}\in\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma})$ denote the
stationary Markov chain with uniform single-site marginal and transition
matrix

$\begin{pmatrix}\frac{1+\theta}{2}&\frac{1-\theta}{2}\\\
\frac{1-\theta}{2}&\frac{1+\theta}{2}\end{pmatrix}.$

This is a free boundary state with inverse temperature determined by $\theta$.
If $\theta<0$ then the model is considered antiferromagnetic.

This parametrization is convenient because $\theta$ is the second-largest
eigenvalue of the transition matrix.

######  Corollary 1.4.

If $\lvert\theta\rvert>\frac{1}{\sqrt{2r-1}}$ then $\mu_{\theta}$ is not
weakly typical.

Conversely, if $\lvert\theta\rvert\leq\frac{1}{\sqrt{2r-1}}$ then
$\mu_{\theta}$ is tail-trivial [BRZ95] so satisfies the second-moment
criterion [Shr21, Corollary 16]. Hence the Kesten–Stigum criterion gives an
exact threshold for typicality of the free-boundary Ising state. Combining the
previous corollary with Corollary 2.7 gives

$h^{\flat}(\mu_{\theta})=h^{\sharp}(\mu_{\theta})=\left\\{\begin{array}[]{ll}\log
2+r(\operatorname{H}(\tfrac{1-\theta}{2})-\log 2),&\theta^{2}(2r-1)\leq 1\\\
-\infty,&\text{else}\end{array}\right.$

where $\operatorname{H}(t)=-t\log t-(1-t)\log(1-t)$. See Figure 1 for a plot.

Figure 1: Typical entropy of free boundary Ising state with parameter
$\theta\in(-1/2,\,1/2)$. Outside the $\theta$ values marked with dashed lines,
the value drops to $-\infty$.

Any good model for $\mu_{\theta}$ on a finite graph $(V,E)$ determines a
bisection of the vertex set into two approximately equal-sized pieces with
about $\frac{1-\theta}{2}$ fraction of edges going from one piece to the
other. If $\theta$ is close to 1, then, it is intuitively clear that there
should typically be no good models. On the other hand, every such bisection
has approximately the edge statistics of $\mu_{\theta}$, but may have
different statistics over general neighborhoods, so is a good model for some
measure with Markov approximation $\mu_{\theta}$ but not necessarily
$\mu_{\theta}$ itself.

One of the main results of [DMS17] determines the asymptotic minimal cut
density of a random regular graph. It follows from this and Corollary 1.4 that
there is some range of $\theta$ for which there are typically good models for
_some_ measure whose Markov approximation is $\mu_{\theta}$, but no good
models for $\mu_{\theta}$ itself (at least for large $r$). Hence, given an
edge marginal, the Markov chain is not necessarily the “most typical” measure
with that edge marginal.

However, as is the case with reconstruction, the resulting bound for
typicality of the hardcore model is _not_ sharp: Let $\mathtt{A}=\\{1,0\\}$.
Given $\alpha\in[0,1/2]$, let
$\mu_{\alpha}\in\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma})$ be the
Markov chain with single-site marginal $(\alpha,\ 1-\alpha)$ and transition
matrix

$\begin{pmatrix}0&\frac{\alpha}{1-\alpha}\\\
1&\frac{1-2\alpha}{1-\alpha}\end{pmatrix}.$

This has second-largest eigenvalue $-\frac{\alpha}{1-\alpha}$. If we identify
elements of $\\{1,0\\}^{\Gamma}$ with subsets of $\Gamma$, then $\mu_{\alpha}$
is supported on independent sets (subsets containing no two adjacent
vertices). Any good model for $\mu_{\alpha}$ is a set of vertices of a finite
graph with density $\alpha$ and a vanishing fraction of adjacent vertices.

######  Corollary 1.5.

If $\frac{\alpha}{1-\alpha}>\frac{1}{\sqrt{2r-1}}$ (equivalently, if
$\alpha>\frac{1}{1+\sqrt{2r-1}}$) then the hardcore free-boundary state
$\mu_{\alpha}$ is not weakly typical.

This bound on the density $\alpha$ is not optimal, at least for large $r$,
since it’s larger than the maximal density of an independent set which is
$2\frac{\log r}{r}+o_{r\to\infty}(1)$ [FŁ92].

###  1.4 Acknowledgements

This material is based on work completed at the University of Texas at Austin
while supported by NSF Grant DMS 1937215.

Thanks to Tim Austin and Lewis Bowen for helpful conversations and for
comments on earlier drafts.

##  2 Definitions and basic lemmas

Throughout, let $\mathtt{A}$ be a finite alphabet, $\Gamma$ be the free group
of rank $r$ with generating set $\\{s_{1},\ldots,s_{r}\\}$ and identity $e$.

The shift action of $\Gamma$ is defined as follows: if
$\mathbf{x}\in\mathtt{A}^{\Gamma}$ and $g,h\in\Gamma$ then the label of
$g\cdot\mathbf{x}$ at $h$ is given by

$(g\cdot\mathbf{x})(h)=\mathbf{x}(hg).$

This is a left action. The action of $g\in\Gamma$ on
$\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma})$ is then given by
pushforwards:

$g\cdot\mu=(\mathbf{x}\mapsto g\cdot\mathbf{x})_{*}\mu.$

We will identify $\Gamma$ with its left Cayley graph, which is a $2r$-regular
tree with edges of the form $(g,s_{i}g)$ for $g\in\Gamma$ and
$i\in[r]=\\{1,2,\ldots,r\\}$.

###  2.1 Sofic entropy

We follow the notation conventions of [Aus16], but for simplicity assume the
sofic approximation maps are homomorphisms.

Given finite set $V$ and a homomorphism
$\sigma\in\operatorname{Hom}(\Gamma,\operatorname{Sym}(V))$ and a “microstate”
$\mathbf{x}\in\mathtt{A}^{V}$, we define the pullback labeling of $\mathbf{x}$
at $v\in V$ as the labeling $\Pi_{v}^{\sigma}\mathbf{x}\in\mathtt{A}^{\Gamma}$
defined by

$\left(\Pi_{v}^{\sigma}\mathbf{x}\right)(h)=\mathbf{x}(\sigma^{h}v).$

Note that with this definition we have
$g\cdot(\Pi_{v}^{\sigma}\mathbf{x})=\Pi_{\sigma^{g}v}^{\sigma}\mathbf{x}$,
since $\sigma$ is a homomorphism.

The empirical distribution of $\mathbf{x}$ over $\sigma$ is then defined by

$P_{\mathbf{x}}^{\sigma}=\frac{1}{\lvert V\rvert}\sum_{v\in
V}\delta_{\Pi_{v}^{\sigma}\mathbf{x}}\in\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma}).$

Since $\sigma$ is a homomorphism, the empirical distribution is always shift-
invariant.

Briefly, the sofic entropy of
$\mu\in\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma})$ over a sequence of
homomorphisms is the exponential growth rate of the number of microstates
whose empirical distribution is close to $\mu$ in the weak topology. To make
this precise, endow $\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma})$ with
the transportation metric

$\overline{d}(\mu,\nu)=\sup\left\\{\left\lvert\int f\,d\mu-\int
f\,d\nu\right\rvert\,:\,f\in\operatorname{Lip}_{1}(\mathtt{A}^{\Gamma})\right\\}$

where $\operatorname{Lip}_{1}(\mathtt{A}^{\Gamma})$ is the set of real-valued,
1-Lipschitz functions on $\mathtt{A}^{\Gamma}$, which we give the metric

$d(\mathbf{x},\mathbf{y})=\sum_{\gamma\in\Gamma}\mathbf{1}_{\\{\mathbf{x}(\gamma)\neq\mathbf{y}(\gamma)\\}}(5r^{2})^{-d(\gamma,e)}.$

For $\sigma\in\operatorname{Hom}(\Gamma,\operatorname{Sym}(V))$ we then define
the set of $\varepsilon$-good microstates for $\mu$ by

$\Omega(\sigma,\mu,\varepsilon)=\\{\mathbf{x}\in\mathtt{A}^{V}\,:\,\overline{d}(P_{\mathbf{x}}^{\sigma},\
\mu)<\varepsilon\\}.$

Here we could alternatively use open neighborhoods of $\mu$ instead of fixing
a metric, but using a metric will be convenient for defining
$h^{\flat},h^{\sharp}$. The choice of $5r^{2}$ in particular will be
convenient in the proof of Lemma 2.1.

We will consider both upper and lower exponential growth rates: if
$\Sigma=\\{\sigma_{n}\in\operatorname{Hom}(\Gamma,\operatorname{Sym}(V_{n}))\\}_{n=1}^{\infty}$
the upper sofic entropy over $\Sigma$ is defined by

$\overline{\operatorname{h}}_{\Sigma}(\mu)=\inf_{\varepsilon>0}\limsup_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\lvert\Omega(\sigma_{n},\mu,\varepsilon)\rvert$

and the lower sofic entropy by

$\underline{\operatorname{h}}_{\Sigma}(\mu)=\inf_{\varepsilon>0}\liminf_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\lvert\Omega(\sigma_{n},\mu,\varepsilon)\rvert.$

For a finite set $F\subset\Gamma$ and $\delta>0$, a homomorphism $\sigma$ is
called $(F,\delta)$-sofic if

$\frac{1}{\lvert V\rvert}\left\lvert\\{v\in
V\,:\,\sigma(\gamma_{1})\,v\neq\sigma(\gamma_{1})\,v\ \text{for all distinct
}\gamma_{1},\gamma_{2}\in F\\}\right\rvert>1-\delta.$

For example, if $F$ is the radius-$R$ ball centered at the identity, then this
requires that for all but a fraction $\delta$ of the vertices $v$, the
subgraph of $\sigma$ induced by the vertices within distance $R$ of $v$ is a
tree. In other words, the graph of $\sigma$ locally looks like the Cayley
graph of $\Gamma$, with quality parameters $(F,\delta)$.

The sequence $\Sigma$ is called a sofic approximation to $\Gamma$ if for any
$(F,\delta)$, for all large enough $n$ $\sigma_{n}$ is $(F,\delta)$-sofic. If
$\Sigma$ is a sofic approximation then these quantities are measure-conjugacy
invariants [Bow10a].

The quantities may depend on the choice of sofic approximation $\Sigma$, but
it is not fully understood how. It is known that for some measures, the value
can be $-\infty$ for some choices of $\Sigma$ and positive for others. But it
is not known whether two choices of $\Sigma$ can achieve distinct positive
values for the same measure.

###  2.2 $\operatorname{f}$ invariant

The $\operatorname{f}$ invariant is the exponential growth rate of the
expected number of good microstates over a uniformly random homomorphism: if
$\sigma_{n}$ is uniformly distributed over
$\operatorname{Hom}(\Gamma,\operatorname{Sym}(n))$ then

$\operatorname{f}(\mu)\coloneqq\inf_{\varepsilon>0}\limsup_{n\to\infty}\frac{1}{n}\log\operatorname*{\mathbb{E}}\lvert\Omega(\sigma_{n},\mu,\varepsilon)\rvert.$

The method of [Bow10c] shows that the limsup can be replaced by a liminf
without changing the value: in either case $\operatorname{f}$ is equivalently
given by the information-theoretic formula in [Bow10].

A result of [Bow10b] is that there is an especially simple formula for Markov
chains: if $p_{1}\in\operatorname{Prob}(\mathtt{A})$ is the single-site
marginal of $\mu$ and $p_{2}\in\operatorname{Prob}(\mathtt{A}^{2})$ is the
marginal on any pair of adjacent elements of $\Gamma$, then

$\operatorname{f}(\mu)=(1-2r)\operatorname{H}(p_{1})+r\operatorname{H}(p_{2})$

where $\operatorname{H}$ is the Shannon entropy.

The $\operatorname{f}$ invariant is also sometimes called the annealed
entropy, but in the present paper we will use that term for sofic entropy over
more general random sofic approximations. We use the term $\operatorname{f}$
invariant to make more clear when we are discussing the uniform case
specifically.

###  2.3 Exponentially concentrated random sofic approximations

A _random sofic approximation_ (by homomorphisms) is a sequence of random
homomorphisms
$\\{\sigma_{n}\in\operatorname{Hom}(\Gamma,\operatorname{Sym}(V_{n}))\\}_{n=1}^{\infty}$
such that for every $F,\delta$, the random homomorphism is $(F,\delta)$-sofic
with superexponentially high probability:

$\limsup_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\mathbb{P}\\{\sigma_{n}\text{ is not
$(F,\delta)$-sofic}\\}=-\infty.$

This implies the existence of a sequence of sets of homomorphisms
$\\{S_{n}^{\mathrm{sofic}}\\}_{n=1}^{\infty}$ such that
$\mathbb{P}(S_{n}^{\mathrm{sofic}})\to 1$ and if $\sigma_{n}\in
S_{n}^{\mathrm{sofic}}$ for all $n$ then $\\{\sigma_{n}\\}$ is a sofic
approximation. For the proof of Theorem 1.1, we will only need to use this
sequence, not the superexponential decay.

We say that two homomorphisms
$\sigma_{1},\sigma_{2}\in\operatorname{Hom}(\Gamma,\operatorname{Sym}(V))$
differ by a “switching” if for some $i,j\in V$ and $k\in[r]$

$\sigma_{1}^{k}(i)=\sigma_{2}^{k}(j)\quad\text{and}\quad\sigma_{1}^{k}(j)=\sigma_{2}^{k}(i),$

and $\sigma_{1},\sigma_{2}$ are otherwise identical. If $\sigma_{2}$ can be
obtained from $\sigma_{1}$ using a minimal number $m$ of switchings, then we
define $d(\sigma_{1},\sigma_{2})=m/\lvert V\rvert$.

We call a sequence of random homomorphisms _exponentially concentrated_ if
there is some constant $C>0$ such that for every $n\in\mathbb{N}$, 1-Lipschitz
$f\colon\operatorname{Hom}(\Gamma,\operatorname{Sym}(V_{n}))\to\mathbb{R}$,
and $t>0$ we have

$\mathbb{P}\\{\lvert
f(\sigma_{n})-\operatorname*{\mathbb{E}}[f(\sigma_{n})]\rvert>t\\}\leq
2e^{-C\lvert V_{n}\rvert t^{2}}.$

By [Shr21, Lemma 22], this holds for the uniform permutation model with
$C=\frac{1}{2r}$. The proof uses Azuma’s inequality, mimicking a similar
concentration inequality for the configuration model which also uses the
notion of “switching” [Wor99].

The exact dependence of the upper bound on $t$ is not important, but we do not
try to formulate the most general version here.

###  2.4 Upper and lower typical entropy functions $h^{\sharp}$, $h^{\flat}$

In this section, $\mathbb{P}$ and $\operatorname*{\mathbb{E}}$ refer to an
arbitrary (but fixed throughout) exponentially concentrated random sofic
approximation by homomorphisms.

For $h\in[0,\log|\mathtt{A}|]$ and
$\sigma\in\operatorname{Hom}(\Gamma,\operatorname{Sym}(n))$, let

$\rho_{\mu}(\sigma,h)=\inf\left\\{\varepsilon>0\,:\,\frac{1}{n}\log\left\lvert\Omega(\sigma,\mu,\varepsilon)\right\rvert\geq
h\right\\}.$

Note that
$\rho_{\mu}(\sigma,h)\leq\operatorname{diam}(\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma}))$.
Given a random sofic approximation we define the limits

$\overline{\rho}_{\mu}(h)=\limsup_{n\to\infty}\operatorname*{\mathbb{E}}\rho_{\mu}(\sigma_{n},h)$

and

$\underline{\rho}_{\mu}(h)=\liminf_{n\to\infty}\operatorname*{\mathbb{E}}\rho_{\mu}(\sigma_{n},h)$

where the expectations are over the random
$\sigma_{n}\in\operatorname{Hom}(\Gamma,\operatorname{Sym}(V_{n}))$.

For each $\sigma$ the function $\rho_{\mu}(\sigma,h)$ is nondecreasing in $h$,
so the expectations and limit functions are nondecreasing as well. Define

$h^{\flat}=\sup\\{h\in\mathbb{R}\,:\,\overline{\rho}_{\mu}(h)=0\\}\ \leq\
h^{\sharp}=\sup\\{h\in\mathbb{R}\,:\,\underline{\rho}_{\mu}(h)=0\\}\ \leq\
\log\lvert\mathtt{A}\rvert,$

using the convention that the supremum of the empty set is $-\infty$.

For the permutation model, it may be that $h^{\flat}\equiv h^{\sharp}$, but
this seems to be a difficult question; cf. [BBS22, Conjecture 1.4].

Note that since $\underline{\operatorname{h}}_{\Sigma}$ and
$\overline{\operatorname{h}}_{\Sigma}$ are independent of the choice of metric
on $\mathtt{A}^{\Gamma}$, Theorem 1.1 implies that $h^{\flat},h^{\sharp}$ are
independent of the metric as well.

####  2.4.1 Properties of $\rho$

The crucial property of $\rho_{\mu}(\cdot,h)$ is that it’s exponentially
concentrated around its mean. This follows from the exponential concentration
property of the random sofic approximation, once we show that it’s a Lipschitz
function:

######  Lemma 2.1.

For every $\mu\in\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma})$ and $h>0$,
the function $\sigma\mapsto\rho_{\mu}(\sigma,h)$ is $2$-Lipschitz. In
particular, over an exponentially concentrated random sofic approximation we
have

$\mathbb{P}\left\\{\left\lvert\rho_{\mu}(\sigma_{n},h)-\operatorname*{\mathbb{E}}[\rho_{\mu}(\sigma_{n},h)]\right\rvert>t\right\\}\leq
2\exp\left(\frac{-C\lvert V_{n}\rvert t^{2}}{4}\right).$

The constant $C$ here is the same one from the definition of exponential
concentration above, and does not depend on $\mu$ or $h$.

###### Proof.

We first show that if
$\sigma_{1},\sigma_{2}\in\operatorname{Hom}(\Gamma,\operatorname{Sym}(V))$
differ by a switching then for any microstate $\mathbf{x}\in\mathtt{A}^{V}$,
its empirical distributions
$P_{\mathbf{x}}^{\sigma_{1}},P_{\mathbf{x}}^{\sigma_{2}}$ are distance at most
$2/\lvert V\rvert$ apart. By definition of the transportation metric,

$\overline{d}(P_{\mathbf{x}}^{\sigma_{1}},P_{\mathbf{x}}^{\sigma_{2}})=\sup\left\\{\left\lvert\int
f\,dP_{\mathbf{x}}^{\sigma_{1}}-\int
f\,dP_{\mathbf{x}}^{\sigma_{2}}\right\rvert\,:\,f\in\operatorname{Lip}_{1}(\mathtt{A}^{\Gamma})\right\\}$

where $\operatorname{Lip}_{1}(\mathtt{A}^{\Gamma})$ is the set of real-valued,
1-Lipschitz functions on $\mathtt{A}^{\Gamma}$. For any such function, by
definition of the empirical distribution,

$\left\lvert\int f\,dP_{\mathbf{x}}^{\sigma_{1}}-\int
f\,dP_{\mathbf{x}}^{\sigma_{2}}\right\rvert\leq\frac{1}{\lvert
V\rvert}\sum_{v\in V}\left\lvert
f(\Pi_{v}^{\sigma_{1}}\mathbf{x})-f(\Pi_{v}^{\sigma_{2}}\mathbf{x})\right\rvert\leq\frac{1}{\lvert
V\rvert}\sum_{v\in V}d\left(\Pi_{v}^{\sigma_{1}}\mathbf{x},\
\Pi_{v}^{\sigma_{2}}\mathbf{x}\right).$

With $i,j\in V$ and $k\in[r]$ as in the definition of switching above, let
$B=\\{i,\sigma_{1}^{k}(i),j,\sigma_{1}^{k}(j)\\}$. If the $\sigma_{1}$-graph
distance between $v$ and $B$ is $R$, then the pullback names
$\Pi_{v}^{\sigma_{1}}\mathbf{x},\ \Pi_{v}^{\sigma_{2}}\mathbf{x}$ agree at
least on the radius-$R$ ball centered at $e\in\Gamma$. So

$d\left(\Pi_{v}^{\sigma_{1}}\mathbf{x},\
\Pi_{v}^{\sigma_{2}}\mathbf{x}\right)\leq\sum_{l=R+1}^{\infty}(5r^{2})^{-l}2r(2r-1)^{l-1}\leq\frac{(2/5r)^{R+1}}{1-2/5r}\leq
2\left(\frac{2}{5r}\right)^{R},$

and

$\displaystyle\overline{d}(P_{\mathbf{x}}^{\sigma_{1}},P_{\mathbf{x}}^{\sigma_{2}})$
$\displaystyle\leq\frac{1}{\lvert
V\rvert}\sum_{R=0}^{\infty}2\left(\frac{2}{5r}\right)^{R}\lvert\\{v\in
V\,:\,d(v,B)=R\\}\rvert$ $\displaystyle\leq\frac{1}{\lvert
V\rvert}\sum_{R=0}^{\infty}2\left(\frac{2}{5r}\right)^{R}4(2r-1)^{R-1}$
$\displaystyle\leq\frac{8}{\lvert
V\rvert}\sum_{R=0}^{\infty}\left(\frac{4}{5}\right)^{R}$
$\displaystyle\leq\frac{2}{\lvert V\rvert}.$

This implies that if $\sigma_{1},\sigma_{2}$ differ by a switching, the
minimum distance (in the transportation metric) from $\mu$ to get any
specified number of microstates differs by at most $2/\lvert V\rvert$.
Therefore $\rho_{\mu}(\sigma,h)$ is a Lipschitz function of the permutation
$\sigma$. ∎

We will also need continuity as a function of the measure $\mu$. In fact,
$\rho$ is Lipschitz in that sense as well:

######  Lemma 2.2.

For each $h$, $\overline{\rho}_{\mu}(h)$ and $\underline{\rho}_{\mu}(h)$ are
1-Lipschitz functions of $\mu$.

###### Proof.

For any $\sigma,h,$ and $\nu$, clearly

$\rho_{\mu}(\sigma,h)\leq\rho_{\nu}(\sigma,h)+d(\mu,\nu),$

and by reversing the roles of $\mu,\nu$ we get

$\left\lvert\rho_{\mu}(\sigma,h)-\rho_{\nu}(\sigma,h)\right\rvert\leq
d(\mu,\nu).$

The inequality is preserved after taking expectations and a limsup or liminf.
∎

####  2.4.2 Properties of $h^{\sharp}$, $h^{\flat}$

######  Lemma 2.3.

$h^{\sharp}(\mu)$ and $h^{\flat}(\mu)$ are upper semicontinuous functions of
$\mu$.

###### Proof.

Suppose $\mu_{k}\to\mu$, and let $h=\limsup_{k\to\infty}h^{\sharp}(\mu_{k})$.
Then for any $\delta>0$ we have $h^{\sharp}(\mu_{k})\geq h-\delta$ for
infinitely many $k$, so $\underline{\rho}_{\mu_{k}}(h-\delta)=0$ for
infinitely many $k$, and by continuity of $\underline{\rho}$ (Lemma 2.2)

$\underline{\rho}_{\mu}(h-\delta)=\lim_{k\to\infty}\underline{\rho}_{\mu_{k}}(h-\delta)=0.$

This implies $h-\delta\leq h^{\sharp}(\mu)$, so since $\delta>0$ is arbitrary,
$\limsup_{k\to\infty}h^{\sharp}(\mu_{k})\leq h^{\sharp}(\mu)$.

The same argument shows that $h^{\flat}$ is upper semicontinuous. ∎

######  Lemma 2.4.

For every $\mu$,
$h^{\sharp}(\mu)\leq\overline{\operatorname{h}}^{\mathrm{ann}}(\mu)$ and
$h^{\flat}(\mu)\leq\underline{\operatorname{h}}^{\mathrm{ann}}(\mu)$.

###### Proof.

For any $\delta>0$, by Markov’s inequality

$\mathbb{P}\left\\{\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert>\overline{\operatorname{h}}^{\mathrm{ann}}(\mu)+\delta\right\\}\leq\operatorname*{\mathbb{E}}\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert\,e^{-\lvert
V_{n}\rvert(\overline{\operatorname{h}}^{\mathrm{ann}}(\mu)+\delta)}$

which, by definition of $\overline{\operatorname{h}}^{\mathrm{ann}}$, for all
small enough $\varepsilon>0$ is bounded above by $e^{\lvert
V_{n}\rvert(\overline{\operatorname{h}}^{\mathrm{ann}}(\mu)+\delta/2)}e^{-\lvert
V_{n}\rvert(\overline{\operatorname{h}}^{\mathrm{ann}}(\mu)+\delta)}=e^{-\lvert
V_{n}\rvert\delta/2}$ for all large enough $n$. In particular, for all large
enough $n$

$\displaystyle\operatorname*{\mathbb{E}}\rho_{\mu}(\sigma_{n},\overline{\operatorname{h}}^{\mathrm{ann}}(\mu+\delta))$
$\displaystyle\geq\varepsilon\,\mathbb{P}\left\\{\rho_{\mu}(\sigma_{n},\overline{\operatorname{h}}^{\mathrm{ann}}(\mu+\delta))\geq\varepsilon\right\\}$
$\displaystyle=\varepsilon\,\mathbb{P}\left\\{\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert\leq\overline{\operatorname{h}}^{\mathrm{ann}}(\mu)+\delta\right\\}$
$\displaystyle\geq\varepsilon\,(1-e^{-\lvert V_{n}\rvert\delta/2}).$

This implies that
$\underline{\rho}_{\mu}(\overline{\operatorname{h}}^{\mathrm{ann}}(\mu)+\delta)>0$,
which, since $\delta>0$ is arbitrary, implies
$\overline{\operatorname{h}}^{\mathrm{ann}}(\mu)\geq h^{\sharp}(\mu)$.

The proof for lower entropies is the same, but with “for all large enough $n$”
replaced by “for infinitely many $n$” and $\underline{\rho}_{\mu}$ replaced by
$\overline{\rho}_{\mu}$. ∎

####  2.4.3 Consequences of second-moment condition

Recall the “second moment condition” is that
$\overline{\operatorname{h}}^{\mathrm{ann}}(\lambda)\leq
2\underline{\operatorname{h}}^{\mathrm{ann}}(\mu)$ for all self-joinings
$\lambda$ of $\mu$.

######  Lemma 2.5.

If $\mu$ satisfies the second-moment condition then

$\lim_{\varepsilon\to 0}\liminf_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\frac{\left(\operatorname*{\mathbb{E}}\lvert\Omega(\sigma_{n},\mu,\varepsilon)\rvert\right)^{2}}{\operatorname*{\mathbb{E}}\left[\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert^{2}\right]}=\lim_{\varepsilon\to
0}\limsup_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\frac{\left(\operatorname*{\mathbb{E}}\lvert\Omega(\sigma_{n},\mu,\varepsilon)\rvert\right)^{2}}{\operatorname*{\mathbb{E}}\left[\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert^{2}\right]}=0.$

###### Proof.

Note that
$\frac{\left(\operatorname*{\mathbb{E}}\lvert\Omega(\sigma_{n},\mu,\varepsilon)\rvert\right)^{2}}{\operatorname*{\mathbb{E}}\left[\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert^{2}\right]}\leq
1$ by Jensen’s inequality, so

$\limsup_{\varepsilon\to 0}\liminf_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\frac{\left(\operatorname*{\mathbb{E}}\lvert\Omega(\sigma_{n},\mu,\varepsilon)\rvert\right)^{2}}{\operatorname*{\mathbb{E}}\left[\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert^{2}\right]}\leq\limsup_{\varepsilon\to
0}\limsup_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\frac{\left(\operatorname*{\mathbb{E}}\lvert\Omega(\sigma_{n},\mu,\varepsilon)\rvert\right)^{2}}{\operatorname*{\mathbb{E}}\left[\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert^{2}\right]}\leq
0,$

and it suffices to show that

$\liminf_{\varepsilon\to 0}\liminf_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\frac{\left(\operatorname*{\mathbb{E}}\lvert\Omega(\sigma_{n},\mu,\varepsilon)\rvert\right)^{2}}{\operatorname*{\mathbb{E}}\left[\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert^{2}\right]}\geq
0.$

So assume for the sake of contradiction that for some $\eta>0$ there are
arbitrarily small $\varepsilon>0$ with

$\liminf_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\frac{\left(\operatorname*{\mathbb{E}}\lvert\Omega(\sigma_{n},\mu,\varepsilon)\rvert\right)^{2}}{\operatorname*{\mathbb{E}}\left[\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert^{2}\right]}\leq-\eta.$

By definition of $\underline{\operatorname{h}}^{\mathrm{ann}}$, for every
$\delta>0$ if $\varepsilon$ is small enough then

$\frac{1}{\lvert
V_{n}\rvert}\log\operatorname*{\mathbb{E}}\lvert\Omega(\sigma_{n},\mu,\varepsilon)\rvert\geq\underline{\operatorname{h}}^{\mathrm{ann}}(\mu)-\delta$

for all large $n$, so

$\limsup_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\operatorname*{\mathbb{E}}\left[\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert^{2}\right]\geq
2(\underline{\operatorname{h}}^{\mathrm{ann}}(\mu)-\delta)+\eta,$

and

$\inf_{\varepsilon>0}\limsup_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\operatorname*{\mathbb{E}}\left[\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert^{2}\right]\geq
2\underline{\operatorname{h}}^{\mathrm{ann}}(\mu)+\eta.$

The left-hand side is equal to the supremum of
$\overline{\operatorname{h}}^{\mathrm{ann}}(\lambda)$ where $\lambda$ ranges
over self-joinings of $\mu$, so this implies that the second-moment criterion
is violated.

Note also that the inequality does hold if $\eta=0$, and the supremum is
attained for some $\lambda$, so there must be a self-joining $\lambda$ with
$\overline{\operatorname{h}}^{\mathrm{ann}}(\lambda)=2\underline{\operatorname{h}}^{\mathrm{ann}}(\mu)$.
∎

######  Proposition 2.6.

If $\mu$ satisfies the second-moment condition then
$h^{\flat}(\mu)=\underline{\operatorname{h}}^{\mathrm{ann}}(\mu)$ and
$h^{\sharp}(\mu)=\overline{\operatorname{h}}^{\mathrm{ann}}(\mu)$.

###### Proof.

By the Paley-Zygmund inequality, for any $\delta\in(0,1)$

$\mathbb{P}\left\\{\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert>(1-\delta)\operatorname*{\mathbb{E}}\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert\right\\}\geq\delta^{2}\frac{\operatorname*{\mathbb{E}}[\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert]^{2}}{\operatorname*{\mathbb{E}}[\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert^{2}]}.$

By Lemma 2.5, the second-moment condition implies that for any $\eta>0$, for
arbitrarily small $\varepsilon>0$ we have

$\frac{\operatorname*{\mathbb{E}}[\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert]^{2}}{\operatorname*{\mathbb{E}}[\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert^{2}]}\geq
e^{-\eta\lvert V_{n}\rvert}$

for all large enough $n$.

  1. 1.

(Lower entropies are equal) By definition we have

$\operatorname*{\mathbb{E}}\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert\geq
e^{\lvert
V_{n}\rvert(\underline{\operatorname{h}}^{\mathrm{ann}}(\mu)-\delta)}$

for all large $n$. Hence for any $\eta,\delta>0$, for arbitrarily small
$\varepsilon>0$

$\mathbb{P}\\{\rho_{\mu}(\sigma_{n},\underline{\operatorname{h}}^{\mathrm{ann}}(\mu)-2\delta)\leq\varepsilon\\}\geq\mathbb{P}\\{\tfrac{1}{\lvert
V_{n}\rvert}\log\lvert\Omega(\sigma_{n},\mu,\varepsilon)\rvert>\underline{\operatorname{h}}^{\mathrm{ann}}(\mu)-\delta\\}\geq\delta^{2}e^{-\eta\lvert
V_{n}\rvert}$

for all large $n$. If for some $t>0$ we had
$\overline{\rho}_{\mu}(\underline{\operatorname{h}}^{\mathrm{ann}}(\mu)-2\delta)>\varepsilon+t$,
then Lemma 2.1 would imply

$\displaystyle\mathbb{P}\\{\rho_{\mu}(\sigma_{n},\underline{\operatorname{h}}^{\mathrm{ann}}(\mu)-2\delta)\leq\varepsilon\\}$
$\displaystyle\leq 2\exp\left(\frac{-C\lvert V_{n}\rvert t^{2}}{4}\right)$

for infinitely many $n$, so the above lower bound on the same probability
implies $t^{2}\leq 4\eta/C$. This means that
$\overline{\rho}_{\mu}(\underline{\operatorname{h}}^{\mathrm{ann}}(\mu)-2\delta)\leq\varepsilon+2\sqrt{\eta/C}$.
Taking $\varepsilon$ and then $\eta$ to 0 gives
$\overline{\rho}_{\mu}(\underline{\operatorname{h}}^{\mathrm{ann}}(\mu)-2\delta)$,
which means
$h^{\flat}(\mu)\geq\underline{\operatorname{h}}^{\mathrm{ann}}(\mu)-2\delta$.
Since $\delta>0$ is arbitrary, this shows
$h^{\flat}(\mu)=\underline{\operatorname{h}}^{\mathrm{ann}}(\mu)$.

  2. 2.

(Upper entropies are equal) By definition we have

$\operatorname*{\mathbb{E}}\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert\geq
e^{\lvert
V_{n}\rvert(\overline{\operatorname{h}}^{\mathrm{ann}}(\mu)-\delta)}$

for infinitely many $n$. Hence for any $\eta,\delta>0$, for arbitrarily small
$\varepsilon>0$

$\mathbb{P}\\{\rho_{\mu}(\sigma_{n},\overline{\operatorname{h}}^{\mathrm{ann}}(\mu)-2\delta)\leq\varepsilon\\}\geq\mathbb{P}\\{\tfrac{1}{\lvert
V_{n}\rvert}\log\lvert\Omega(\sigma_{n},\mu,\varepsilon)\rvert>\overline{\operatorname{h}}^{\mathrm{ann}}(\mu)-\delta\\}\geq\delta^{2}e^{-\eta\lvert
V_{n}\rvert}$

for infinitely many $n$. If for some $t>0$ we had
$\underline{\rho}_{\mu}(\overline{\operatorname{h}}^{\mathrm{ann}}(\mu)-2\delta)>\varepsilon+t$,
then Lemma 2.1 would imply

$\displaystyle\mathbb{P}\\{\rho_{\mu}(\sigma_{n},\overline{\operatorname{h}}^{\mathrm{ann}}(\mu)-2\delta)\leq\varepsilon\\}$
$\displaystyle\leq 2\exp\left(\frac{-C\lvert V_{n}\rvert t^{2}}{4}\right)$

for all large $n$, so $t^{2}\leq 4\eta/C$. This means that
$\underline{\rho}_{\mu}(\overline{\operatorname{h}}^{\mathrm{ann}}(\mu)-2\delta)\leq\varepsilon+2\sqrt{\eta/C}$.
Taking $\varepsilon$ and then $\eta$ to 0 gives
$\underline{\rho}_{\mu}(\overline{\operatorname{h}}^{\mathrm{ann}}(\mu)-2\delta)$,
which means
$h^{\sharp}(\mu)\geq\overline{\operatorname{h}}^{\mathrm{ann}}(\mu)-2\delta$.
Since $\delta>0$ is arbitrary, this shows
$h^{\sharp}(\mu)=\overline{\operatorname{h}}^{\mathrm{ann}}(\mu)$. ∎

In particular, since in the case of $\mathbb{P}^{\mathrm{up}}$ the upper and
lower annealed entropies are equal and
$\operatorname{f}(\mu\times\mu)=2\operatorname{f}(\mu)$, we get the following
simpler version:

######  Corollary 2.7.

If the product self-joining of $\mu$ has maximal $\operatorname{f}$ invariant,
then $\operatorname{f}(\mu)=h^{\flat}(\mu)=h^{\sharp}(\mu)$.

##  3 Typical local limits for nearest-neighbor interactions

First, we introduce three modes of convergence. Though the notation is
different, these all essentially appear in [MMS12, Definition 2.3]. A slight
difference is that we consider our permutation graphs to come with directed
and labeled edges, which fixes a particular identification of a vertex
neighborhood with a neighborhood of the identity in $\Gamma$.

If $\sigma\in\operatorname{Hom}(\Gamma,\operatorname{Sym}(V))$ and
$\zeta\in\operatorname{Prob}(\mathtt{A}^{V})$, the average empirical
distribution of $\zeta$ is defined by

$P_{\zeta}^{\sigma}=\frac{1}{\lvert\mathtt{A}^{V}\rvert}\sum_{\mathbf{x}\in\mathtt{A}^{V}}\zeta\\{\mathbf{x}\\}\,P_{\mathbf{x}}^{\sigma}\in\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma}).$

If
$\\{\sigma_{n}\in\operatorname{Hom}(\Gamma,\operatorname{Sym}(V_{n}))\\}_{n=1}^{\infty}$
is a sequence of homomorphisms and
$\zeta_{n}\in\operatorname{Prob}(\mathtt{A}^{V_{n}})$ for each $n$, then we
say the sequence $\\{\zeta_{n}\\}_{n=1}^{\infty}$ converges to
$\mu\in\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma})$ locally on average
(LOA) if $P_{\zeta_{n}}^{\sigma_{n}}$ converges to $\mu$ in the weak topology.

In the same setting, we say the local limit of
$\\{\zeta_{n}\\}_{n=1}^{\infty}$ is $\mu$ if for every open neighborhood
$\mathcal{O}$ of $\mu$ in $\operatorname{Prob}(\mathtt{A}^{\Gamma})$,

$\lim_{n\to\infty}\frac{1}{\lvert V_{n}\rvert}\left\lvert\\{v\in
V_{n}\,:\,(\Pi_{v}^{\sigma_{n}})_{*}\zeta_{n}\in\mathcal{O}\\}\right\rvert=1.$

That is, we require most of the local marginals of $\zeta_{n}$ to be close to
$\mu$, not just their average. The individual local marginals are not
necessarily shift-invariant.

More generally, we say the local limit is
$\mathfrak{m}\in\operatorname{Prob}(\operatorname{Prob}(\mathtt{A}^{\Gamma}))$
if

$\lim_{n\to\infty}\frac{1}{\lvert V_{n}\rvert}\sum_{v\in
V}\delta_{(\Pi_{v}^{\sigma_{n}})_{*}\zeta_{n}}=\mathfrak{m}.$

If the local limit in this sense is a point mass $\delta_{\mu}$, we just say
the local limit is $\mu$; this is equivalent to the previous definition. This
mode of convergence is easier to work with because we can always pass to
subsequential limits. In examples below, we will then show that the
subsequential limits are point masses.

Given an energy function $u\colon\mathtt{A}^{\Gamma}\to\mathbb{R}$, to each
$\sigma\in\operatorname{Hom}(\Gamma,\operatorname{Sym}(V))$ we associate the
finitary Gibbs state $\xi\in\operatorname{Prob}(\mathtt{A}^{V})$ defined by

$\xi\\{\mathbf{x}\\}\propto\exp\left(-\lvert V\rvert\int
u\,dP_{\mathbf{x}}^{\sigma}\right)=\exp\left(-\sum_{v\in
V}u(\Pi_{v}^{\sigma}\mathbf{x})\right).$

This is also called the Boltzmann distribution. We interpret
$u(\Pi_{v}^{\sigma}\mathbf{x})$ as the energy of interactions attributed to
the vertex $v$, so the sum $\sum_{v\in V}u(\Pi_{v}^{\sigma}\mathbf{x})$ is the
total energy. Note that the Gibbs state prefers individual microstates with
low energy.

We say $u$ is a nearest-neighbor interaction if it is of the form

$u(\mathbf{x})=h(\mathbf{x}(e))+\frac{1}{2}\sum_{\gamma\sim
e}J(\mathbf{x}(e),\,\mathbf{x}(\gamma))$

for a function $h\colon\mathtt{A}\to\mathbb{R}$ and a symmetric function
$J\colon\mathtt{A}^{2}\to\mathbb{R}$. We include the factor of $\frac{1}{2}$
to attribute to the spin at the identity $e$ half the energy due to
interactions with its neighbors.

Given an energy function $u$, we say the typical LOA limit is $\mu$ if for a
typical sofic approximation $\Sigma$ (in the sense of Theorem 1.1) the
finitary Gibbs states converge LOA to $\mu$. We use analogous terminology for
the other modes of convergence. This makes sense for any random sofic
approximation, but we mostly consider the uniform permutation model.

A state $\mu\in\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma})$ is called
$\Sigma$-equilibrium if it is a global maximizer of the (upper)
$\Sigma$-pressure defined by
$\overline{\operatorname{p}}_{\Sigma}(\mu)=\overline{\operatorname{h}}_{\Sigma}(\mu)-u(\mu)$,
where $u(\mu)=\int u\,d\mu$ is the average energy per site. The pressure
captures the competition between the Boltzmann weight of any individual good
model for $\mu$, which is determined by $u(\mu)$, and the number of good
models for $\mu$, which is measured by
$\overline{\operatorname{h}}_{\Sigma}(\mu)$.

For simplicity we will only consider random sofic approximations for which,
like the uniform permutation model, the upper and lower annealed entropies are
equal. This is a natural assumption for computing limits, since we do not want
different behavior on different subsequences. In this case we will call
maximizers of
$\overline{\operatorname{h}}^{\mathrm{ann}}-u=\underline{\operatorname{h}}^{\mathrm{ann}}-u$
annealed-equilibrium or, in the uniform case, $\operatorname{f}$-equilibrium.

A Gibbs measure is called extreme if it is an extreme point in the convex set
of all Gibbs measures for the interaction. This is equivalent to being tail-
trivial [Geo11, Theorem 7.7] which is equivalent to non-reconstruction [Mos01,
Proposition 15].

######  Proposition 3.1.

Consider any exponentially concentrated random sofic approximation such that
$\overline{\operatorname{h}}^{\mathrm{ann}}\equiv\underline{\operatorname{h}}^{\mathrm{ann}}$.

Let $\mathcal{E}\subset\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma})$ be
the set of states which are both annealed-equilibrium and Gibbs for a given
nearest-neighbor interaction.

Suppose every element of $\mathcal{E}$ satisfies the second-moment criterion.
Then, over a typical sofic approximation, any subsequential LOA limit of the
finitary Gibbs states is a mixture of states in $\mathcal{E}$.

If also every element of $\mathcal{E}$ is extreme, then any subsequential
local limit
$\mathfrak{m}\in\operatorname{Prob}(\operatorname{Prob}(\mathtt{A}^{\Gamma}))$
is supported on the convex hull of $\mathcal{E}$.

It is probably true that every annealed-equilibrium state is automatically
Gibbs, so the definition of $\mathcal{E}$ is probably redundant. If the
interaction has no hard constraints, this follows from [Shr22, Theorem A]. On
the other hand, [BM22] considered much more general interactions but did not
allow for random sofic approximations.

In the uniform case, this should generally provide a tractable approach to
computing local limits because $\operatorname{f}$-equilibrium states must be
Markov chains [Shr23, Lemma 6.9], the set of completely homogeneous Markov
chains which are Gibbs states is parametrized by “boundary laws”, and the
$\operatorname{f}$-pressure of a Gibbs Markov chain admits a relatively simple
expression in terms of its boundary law. See Section 3.3 below.

In examples below, we will actually show that the subsequential local limits
are all the same mixture of states in $\mathcal{E}$, so that the limits exist.

###### Proof of Proposition 3.1.

Since every element of $\mathcal{E}$ is annealed-equilibrium and satisfies the
second-moment criterion, $\mathcal{E}$ contains all $\Sigma$-equilibrium
measures for a typical sofic approximation $\Sigma$, and for any subsequence
of $\Sigma$. This is because if $\mu\in\mathcal{E}$ and
$\nu\in\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma})\setminus\mathcal{E}$
then, if $\Sigma^{\prime}$ is a subsequence of $\Sigma$,

$\displaystyle\overline{\operatorname{h}}_{\Sigma^{\prime}}(\nu)-u(\nu)$
$\displaystyle\leq\overline{\operatorname{h}}_{\Sigma}(\nu)-u(\nu)$
($\Sigma^{\prime}$ subsequence)
$\displaystyle=\operatorname{h}^{\sharp}(\nu)-u(\nu)$ (Thm. 1.1)
$\displaystyle\leq\overline{\operatorname{h}}^{\mathrm{ann}}(\nu)-u(\nu)$
(Lemma 2.4)
$\displaystyle<\underline{\operatorname{h}}^{\mathrm{ann}}(\mu)-u(\mu)$
($\nu\not\in\mathcal{E}$,
$\overline{\operatorname{h}}^{\mathrm{ann}}\equiv\underline{\operatorname{h}}^{\mathrm{ann}}$)
$\displaystyle=\operatorname{h}^{\flat}(\mu)-u(\mu)$ (Cor. 2.7)
$\displaystyle=\underline{\operatorname{h}}_{\Sigma}(\mu)-u(\mu)$ (Thm. 1.1)
$\displaystyle\leq\underline{\operatorname{h}}_{\Sigma^{\prime}}(\mu)-u(\mu)$
($\Sigma^{\prime}$ subsequence)
$\displaystyle\leq\overline{\operatorname{h}}_{\Sigma^{\prime}}(\mu)-u(\mu)$
($\underline{\operatorname{h}}\leq\overline{\operatorname{h}}$)

The claim about LOA limits then follows from [Shr23, Theorem 6.5]. Note that
we are only applying this theorem to individual deterministic sofic
approximations, so we do not need to worry about the rather strict definition
of local limits over random sofic approximations given in [Shr23].

Now suppose all elements of $\mathcal{E}$ are extreme. If $\mathfrak{m}$ is a
subsequential local limit then it is supported on the set of Gibbs measures
and its barycenter $\bar{\mu}$ is the LOA limit over the same subsequence.
Since, as we showed above, $\bar{\mu}$ is in the convex hull of $\mathcal{E}$,
$\mathfrak{m}$ must be supported on the convex hull of $\mathcal{E}$. ∎

The following subsections work out a few examples in the uniform case.

###  3.1 Ferromagnetic Ising model

Let $\mathtt{A}=\\{-1,+1\\}$. The energy function $u$ for the Ising model can
be defined by taking $h\equiv 0$ and
$J(\mathtt{a}_{1},\mathtt{a}_{2})=-J\mathtt{a}_{1}\mathtt{a}_{2}$ for some
fixed interaction strength $J>0$.

For low interaction strengths ($J\leq
J_{u}=\operatorname{arccoth}(2r-1)=\frac{1}{2}\log\frac{r}{r-1}$) there is a
unique Gibbs measure. For greater values of $J$ there are exactly three Gibbs
Markov chains: one is the free-boundary state $\mu^{FB}$, which we already
considered in Section 1.3 above. There are also plus- and minus-boundary
states $\mu^{+},\mu^{-}$ which are biased towards $+1$ and $-1$ respectively,
and each of which can be obtained from the other by interchanging $+1$ and
$-1$.

######  Proposition 3.2.

For the uniform permutation model, the typical local limit of the Ising model
is $(\mu^{+}+\mu^{-})/2$.

Note that this result is weaker than [MMS12], which establishes the local
limit for an _arbitrary_ sofic approximation. We include it to show how little
model-specific work is necessary to establish the typical local limit in this
case.

###### Proof.

We only need to consider temperatures below the uniqueness threshold – if
there is a unique Gibbs state then it must be the local limit over any sofic
approximation.

We first find the elements of $\mathcal{E}$. Any
$\operatorname{f}$-equilibrium state is a Markov chain, and the only Gibbs
Markov chains are $\mu^{+},\mu^{-},\mu^{FB}$. But $\mu^{FB}$ is not
$\operatorname{f}$-equilibrium [Shr23, Proposition 1.1]. So $\mu^{+},\mu^{-}$
are the unique $\operatorname{f}$-equilibrium states.

Since $\mu^{+}$ and $\mu^{-}$ are extreme [Geo11, Theorem 12.31(b)], any
subsequential local limit $\mathfrak{m}$ of the finitary Gibbs states must be
supported on convex combinations of $\mu^{+},\mu^{-}$. But every neighborhood
marginal of any of the finitary states must be symmetric in $+1/-1$, so
$\mathfrak{m}$ must be supported on Gibbs states which have this symmetry. The
only such convex combination of $\mu^{+}$ and $\mu^{-}$ is
$(\mu^{+}+\mu^{-})/2$. Since this is the only possible subsequential limit, it
must be the true limit. ∎

Note that for the analogous upgrade from LOA to local convergence in [MMS12]
they do not use the geometric property of extremality. Instead they show that
the plus and minus states uniquely minimize the energy among Gibbs states, and
use this fact in the same way.

###  3.2 Antiferromagnetic Ising model

At every temperature, there is a unique completely homogeneous Markov chain
$\mu^{\ast}$ which is a Gibbs state [Geo11, p. 253]. So $\mu^{*}$ is always
the unique $\operatorname{f}$-equilibrium state.

As in the ferromagnetic case, the reconstruction threshold is given by the
Kesten–Stigum bound [MM06, bottom of page 3]. Combined with Theorem 1.3, this
implies

######  Proposition 3.3.

In the non-reconstruction regime, $\mu^{\ast}$ is the typical local limit of
the antiferromagnetic Ising model. If instead $\mu^{\ast}$ is reconstructible,
then it is not weakly typical.

Since $\mu^{\ast}$ is ergodic, it would have to be typical to be the typical
local limit: by [Aus16, Corollary 5.7], if a sequence of measures converges
locally to $\mu^{*}$, then the measures are mostly supported on good models
for $\mu^{*}$. In particular, the sofic approximation must have good models
for $\mu^{*}$.

###  3.3 Potts model

Let $\mathtt{A}=[q]=\\{1,2,\ldots,q\\}$, and fix an interaction strength
$J>0$. This defines a nearest-neighbor interaction with $h\equiv 0$ (no
external field) and pair interaction

$J(\mathtt{a},\mathtt{b})=\left\\{\begin{array}[]{ll}-J,&\mathtt{a}=\mathtt{b}\\\
J,&\mathtt{a}\neq\mathtt{b}.\end{array}\right.$

Let $Q$ be the $q\times q$ matrix with $e^{J}$ in the diagonal entries and
$e^{-J}$ everywhere else. This is called the “transfer matrix” for the
interaction.

Given a “boundary law” $\ell=(\ell_{1},\ldots,\ell_{q})\in(0,+\infty)^{q}$,
let $B$ be the $q\times q$ matrix

$B=\left(\begin{array}[]{ccc}\ell_{1}&&0\\\ &\ddots&\\\
0&&\ell_{q}\end{array}\right)Q\left(\begin{array}[]{ccc}\ell_{1}&&0\\\
&\ddots&\\\ 0&&\ell_{q}\end{array}\right).$

After normalizing so that the entries sum to 1, we can think of this as a
probability distribution on $[q]\times[q]$. Let $\mu_{\ell}$ be the
$[q]$-valued $\mathbb{F}_{r}$-indexed Markov chain with edge marginals
proportional to $B$.

By [Geo11, Corollary 12.17], every Markov chain which is a Gibbs measure for
the Potts interaction can be obtained by some choice of $\ell$. Multiplying
$\ell$ by a positive scalar does not change $\mu_{\ell}$; if we normalize to
fix $\ell_{q}=1$, then the Markov chain $\mu_{\ell}$ is Gibbs if and only if
$\ell$ is a solution of

$\ell_{i}=\left(\frac{[\ell Q]_{i}}{[\ell Q]_{q}}\right)^{2r-1}\quad\forall\
i\in[q].$

For every $J$, one solution is $\ell\equiv 1$: the corresponding Markov chain
$\mu_{*}$ is called the disordered (or paramagnetic) state. A fairly complete
description of the other solutions can be found for example in [KRK14,
Gal+16], but here we only introduce the most relevant solutions.

If we fix $i\in[q]$ and look for a solution with $\ell_{i}=\ell^{*}$ and
$\ell_{j}=1$ for $j\neq i$, we get up to two solutions depending on $J$ (aside
from $\ell^{*}=1$). We call the solution with greater $\ell^{*}$ the $i$th
_ordered state_ $\mu_{i}$ (also called ferromagnetic). All $q$ ordered states
are equivalent up to permutations of the symbols $\\{1,\ldots,q\\}$. In
particular, they all have the same entropy and pressure.

Let $J_{p}=\frac{1}{2}\log\left(\frac{q-2}{(q-1)^{1-\frac{1}{r}}-1}\right)$;
this is sometimes called the ordered-disordered threshold.

######  Proposition 3.4.

In the uniform permutation model, if $J<J_{p}$ then the Potts typical local
limit is the disordered state $\mu_{*}$. If $J>J_{p}$ then the typical local
limit is the symmetric mixture of the ordered states.

If $J=J_{p}$ then, over a typical sofic approximation, every subsequential
local limit is supported on $\mu_{*}$ and the symmetric mixture of the ordered
states.

Comparing the values of $\operatorname{p}_{\operatorname{f}}(\mu_{\ell})$ for
different solutions $\ell$ is difficult to do rigorously. In this section we
will use the results of involved computations in [Gal+16]. Note that the
published version [Gal+16a] is abridged and does not contain many of the
results we need here.

Consider the function $\Phi(\ell)$ defined by

$\Phi(\ell)=r\log\frac{\ell Q\ell^{T}}{\|\ell\|_{p}^{2}}$

where $p=\frac{2r}{2r-1}$. The following lemma allows us to use $\Phi$ to
compare values of $\operatorname{p}_{\operatorname{f}}$:

######  Lemma 3.5.

If $\mu_{\ell}$ is a Gibbs state then
$\operatorname{p}_{\operatorname{f}}(\mu_{\ell})=\Phi(\ell)$.

See Section 3.4 for a proof.

Maximizing $\Phi$ is still fairly involved, but the work has already been done
in [Gal+16]:

######  Theorem 3.6 ([Gal+16]).

For $J<J_{p}$ the boundary law $\ell\equiv 1$ corresponding to the disordered
state is the unique maximizer of $\Phi$. For $J>J_{p}$ the boundary laws
corresponding to any of the ordered states are the only maximizers of $\Phi$.

######  Corollary 3.7.

Among Gibbs Markov chains, for $J<J_{p}$ the disordered state uniquely
maximizes $\operatorname{p}_{\operatorname{f}}$. For $J>J_{p}$ the ordered
states are the only maximizers of $\operatorname{p}_{\operatorname{f}}$.

###### Proof.

We only need to compare values of
$\operatorname{p}_{\operatorname{f}}(\mu_{\ell})$ for $\ell$ such that
$\mu_{\ell}$ is Gibbs, in which case
$\operatorname{p}_{\operatorname{f}}(\mu_{\ell})=\Phi(\ell)$. ∎

The last ingredient is that the maximizers of
$\operatorname{p}_{\operatorname{f}}$ are tail-trivial.

######  Proposition 3.8.

The Potts ordered states are tail-trivial.

This is proven in [Gal+16, Lemma 42].

The following result is stated in [Coj+23, Proposition 2.6] but no proof seems
to have been published. It can be proven using the same method as the previous
result.

######  Proposition 3.9.

The disordered state is tail-trivial for all
$J<\frac{1}{2}\log\left(1+\frac{q}{2r-2}\right)$. In particular, it is tail-
trivial for all $J<J_{p}$.

As pointed out in [Coj+23], $\frac{1}{2}\log\left(1+\frac{q}{2r-2}\right)$ is
the threshold up to which the messages $\ell\equiv 1$ corresponding to the
disordered state are a local maximum of $\Phi$. For the Ising case ($q=2$)
this coincides with the uniqueness threshold, so in general this is a
sufficient but not necessary condition for tail-triviality.

###### Proof.

Since the disordered state corresponds to $\ell\equiv 1$, its edge marginal is
simply the transfer matrix $Q$ except normalized so that the entries sum to 1.
The Markov transition matrix can be obtained from this by normalizing the
columns:

$\frac{1}{e^{J}+(q-1)e^{-J}}\left(\begin{array}[]{ccc}e^{J}&&e^{-J}\\\
&\ddots&\\\ e^{-J}&&e^{J}\end{array}\right).$

As in [Gal+16, Lemma 42], it suffices to show that the maximum total variation
distance (half the $1$-norm) between two columns is less than
$\frac{1}{2r-1}$. For any two distinct columns, the distance is
$\frac{e^{2J}-1}{e^{2J}+q-1}$. Solving

$\frac{e^{2J}-1}{e^{2J}+q-1}<\frac{1}{2r-1}$

for $J$ yields the condition

$J<\frac{1}{2}\log\left(1+\frac{q}{2r-2}\right).$

Since $J_{p}\leq\frac{1}{2}\log\left(1+\frac{q}{2r-2}\right)$ for $q\geq 2$,
the result follows. ∎

We can now prove the claimed typical local limits of the Potts model:

###### Proof of Proposition 3.4.

The above shows that $\mathcal{E}$ is $\\{\mu_{*}\\}$ if $J<J_{p}$, and the
set of the $q$ ordered states if $J>J_{p}$.

Let $\mathfrak{m}$ be a subsequential local limit along some typical sofic
approximation. Since every element of $\mathcal{E}$ is tail-trivial (extreme),
$\mathfrak{m}$ is supported on the convex hull of $\mathcal{E}$ (Proposition
3.1). In the disordered case $J<J_{p}$, this finishes the proof since
$\mathcal{E}$ has only one element.

For the ordered case $J>J_{p}$, as with the Ising example above,
$\mathfrak{m}$ must be supported on states which are invariant under permuting
the labels in $[q]$. The symmetric mixture of the ordered states is the only
convex combination of them with this property, so it is the only possible
subsequential local limit.

For the case $J=J_{p}$, the set $\mathcal{E}$ contains the disordered state
and all $q$ ordered states. There are two states in the convex hull of
$\mathcal{E}$ which are invariant under permutations of $[q]$: the disordered
state and the symmetric combination of the ordered states. So every
subsequential local limit $\mathfrak{m}$ is supported on these two states, but
we are not able to say how much weight is given to each. ∎

###  3.4 Proof of Lemma 3.5

As in the definition of $\Phi$, let $p=\frac{2r}{2r-1}$.

By [Geo11, Equation 12.13], if $\mu_{\ell}$ is Gibbs then the single-site
marginal of $\mu_{\ell}$ is
$\alpha=\frac{1}{Z_{\alpha}}(\ell_{1}^{p},\ldots,\ell_{q}^{p})$, and the edge
marginal is the measure
$\beta\in\operatorname{Prob}(\mathtt{A}\times\mathtt{A})$ given by
$\beta_{ij}=\frac{1}{Z_{\beta}}q_{ij}\ell_{i}\ell_{j}$, where $q_{ij}$ is the
$(i,j)$ entry of the transfer matrix $Q$. Note that the assumption that
$\mu_{\ell}$ is Gibbs ensures that both marginals of $\beta$ are $\alpha$.

The average energy per site $u(\mu_{\ell})$ is given by
$r\sum_{i,j=1}^{q}\beta_{ij}(-\log q_{ij})$.

Since $\mu_{\ell}$ is a Markov chain, we have

$\operatorname{f}(\mu_{\ell})=(1-2r)\operatorname{H}(\alpha)+r\operatorname{H}(\beta).$

Putting this all together gives

$\displaystyle\operatorname{p}_{\operatorname{f}}(\mu_{\ell})$
$\displaystyle=(1-2r)\sum_{i=1}^{q}-\alpha_{i}\log\alpha_{i}+r\sum_{i,j=1}^{q}-\beta_{ij}\log\beta_{ij}+r\sum_{i,j=1}^{q}\beta_{ij}\log
q_{ij}$ $\displaystyle=(1-2r)\sum_{i=1}^{q}-\alpha_{i}(p\log\ell_{i}-\log
Z_{\alpha})-r\sum_{i,j=1}^{q}\beta_{ij}(\log\beta_{ij}-\log q_{ij}).$

By definition of $\beta_{ij}$, and using that both marginals of $\beta$ are
$\alpha$, we get

$\displaystyle\sum_{i,j=1}^{q}\beta_{ij}(\log\beta_{ij}-\log q_{ij})$
$\displaystyle=\sum_{i,j=1}^{q}\beta_{ij}(\log\ell_{i}+\log\ell_{j}-\log
Z_{\beta})$
$\displaystyle=\sum_{i=1}^{q}\log\ell_{i}\sum_{j=1}^{q}\beta_{ij}+\sum_{j=1}^{q}\log\ell_{j}\sum_{j=1}^{q}\beta_{ij}-\log
Z_{\beta}$ $\displaystyle=2\sum_{i=1}^{q}\alpha_{i}\log\ell_{i}-\log
Z_{\beta}.$

So

$\operatorname{p}_{\operatorname{f}}(\mu_{\ell})=(1-2r)\log Z_{\alpha}+r\log
Z_{\beta}-(1-2r)p\sum_{i=1}^{q}\alpha_{i}\log\ell_{i}-2r\sum_{i=1}^{q}\alpha_{i}\log\ell_{i}.$

Since $p=\frac{2r}{2r-1}$, the last two terms cancel each other out, leaving

$\operatorname{p}_{\operatorname{f}}(\mu_{\ell})=(1-2r)\log Z_{\alpha}+r\log
Z_{\beta}=r\log\frac{Z_{\beta}}{Z_{\alpha}^{p/2}}=\Phi(\ell).$

##  4 Kesten–Stigum bound implies atypicality

In this section, we only consider the uniform permutation model, since we rely
on a result of [BC19] which is proved in that context.

The argument is loosely based on [Lyo17, Theorem 3.1, Corollary 3.2], a proof
attributed to Allan Sly that the Ising free boundary state is not a factor of
iid below the reconstruction threshold. The connection between this approach
and [BC19] was suggested by Tim Austin.

A similar correlation bound for factor of iid processes was proven in [BSV15]
using a very similar kind of spectral argument. An alternative approach to
proving Theorem 1.3 may be to show that graphings of typical processes are
Ramanujan and then apply the main result of [BSV15].

The following theorem was shared with me by Tim Austin, but is likely known to
others. See for example [BK20] for more discussion of connections between
sofic entropy and notions of weak containment.

######  Theorem 4.1.

Suppose $\mathtt{A}$ is a finite alphabet and
$\mu\in\operatorname{Prob}^{\mathbb{F}_{r}}(\mathtt{A}^{\mathbb{F}_{r}})$. If
$\mu$ is weakly typical then for any $A\in\mathbb{C}\mathbb{F}_{r}$

$\|\pi(A)\|_{L^{2}_{0}(\mu)}\leq\|\lambda(A)\|_{\ell^{2}(\mathbb{F}_{r})}.$

Here $L^{2}_{0}(\mu)$ is the space of square-integrable complex-valued
functions with mean zero, $\pi$ is the Koopman representation, and $\lambda$
is the left-regular representation. These representations naturally extend to
the group ring $\mathbb{C}\mathbb{F}_{r}$.

An equivalent conclusion of the theorem is that the Koopman representation on
$L^{2}_{0}(\mu)$ is weakly contained in the left-regular representation of
$\Gamma$ [BDV08, Theorem F.4.4].

###### Proof.

Suppose $f\in L^{2}_{0}(\mu)$ takes only finitely many distinct values, say
$\mathtt{B}\Subset\mathbb{C}$, and let $\nu\in\mathtt{B}^{\mathbb{F}_{r}}$ be
the factor of $\mu$ generated by $f$. Since $\mu$ is weakly typical, so is
$\nu$ [Aus16, Lem. 4.3 and Prop. 4.10]. Assume that $f$ is not $\mu$-almost-
surely zero.

Let $\sigma_{n}\colon\mathbb{F}_{r}\to\operatorname{Sym}(V_{n})$ be a
uniformly random homomorphism. Let $\lambda_{n}$ be the induced (random)
unitary representation on $\ell^{2}(V_{n})$. Write $A=\sum
a_{i}\gamma_{i}\in\mathbb{C}\mathbb{F}_{r}$.

Given $\mathbf{x}\in\mathtt{B}^{V_{n}}$,

$\displaystyle\|\lambda_{n}(A)\mathbf{x}\|^{2}$ $\displaystyle=\sum_{v\in
V_{n}}\left(\sum_{i}a_{i}\,\mathbf{x}(\sigma_{n}^{\gamma_{i}}\cdot
v)\right)^{2}$ $\displaystyle=\lvert V_{n}\rvert\int
G_{A}\,dP_{\mathbf{x}}^{\sigma_{n}}$

where $G_{A}\colon\mathbb{C}^{\mathbb{F}_{r}}\to\mathbb{C}$ is given by

$G_{A}(\mathbf{z})=\left(\sum_{i}a_{i}\mathbf{z}(\gamma_{i})\right)^{2}.$

Since $G_{A}$ is continuous, there is a weak-open neighborhood
$\mathcal{O}\ni\nu$ such that if $\mathbf{x}\in\Omega(\sigma_{n},\mathcal{O})$
then

$\left\lvert\frac{\|\lambda_{n}(A)\mathbf{x}\|^{2}}{\lvert V_{n}\rvert}-\int
G_{A}\,d\nu\right\rvert<\varepsilon.$

Since $f$ has mean 0, we can assume that $\mathbf{x}\cdot\mathbf{1}=0$, and
$\|\mathbf{x}\|^{2}\approx\lvert V_{n}\rvert\operatorname{Var}(\nu_{e})$. This
means that if there is some $\mathbf{x}\in\Omega(\sigma_{n},\mathcal{O})$ then

$\|\lambda_{n}(A)\|_{0}^{2}\geq\frac{\|\lambda_{n}(A)\mathbf{x}\|^{2}}{\|\mathbf{x}\|^{2}}\geq\frac{1}{\operatorname{Var}(\nu_{e})}\int
G_{A}\,d\nu-\varepsilon=\frac{\|\pi(A)f\|^{2}_{L^{2}(\mu)}}{\|f\|_{L^{2}(\mu)}^{2}}-\varepsilon$

where $\|\lambda_{n}(A)\|_{0}$ is the operator norm of $\lambda_{n}(A)$ on
$\mathbb{C}^{V_{n}}$ restricted to the orthogonal complement of the all ones
vector $\mathbf{1}$.

Now since $\nu$ is weakly typical, the probability that
$\Omega(\sigma_{n},\mathcal{O})$ is nonempty has limit superior 1. This proves
that for any $\varepsilon>0$

$\limsup_{n\to\infty}\mathbb{P}\left\\{\|\lambda_{n}(A)\|_{0}\geq\frac{\|\pi(A)f\|_{L^{2}(\mu)}}{\|f\|_{L^{2}(\mu)}}-\varepsilon\right\\}=1$

But [BC19] implies that $\|\lambda_{n}(A)\|_{0}$ converges to $\|\lambda(A)\|$
in probability. (The convergence for $A$ is not explicitly stated in this
terminology as a numbered theorem, since $A$ is a polynomial in the generators
rather than a self-adjoint linear combination. See the discussion in [BC19,
Section 1.3].) So we have

$\|\lambda(A)\|\geq\frac{\|\pi(A)f\|_{L^{2}(\mu)}}{\|f\|_{L^{2}(\mu)}}.$

Since $f$ was chosen arbitrarily from a dense subspace of $L^{2}_{0}(\mu)$,
this proves the theorem. ∎

To obtain from this the Kesten–Stigum bound, we now consider the averaging
operators $A_{m}=\sum_{\gamma\in S_{m}}\frac{1}{\lvert S_{m}\rvert}\gamma$
where $S_{m}=\\{v\in\mathbb{F}_{r}\,:\,d(e,v)=m\\}$. We first compute
$\|\lambda(A_{m})\|$, then establish a lower bound on $\|\pi(A_{m})\|$.

######  Proposition 4.2.

For every $m\in\mathbb{N}$,

$\|\lambda(A_{m})\|_{\ell^{2}(\mathbb{F}_{r})}=\left(m+1-\frac{m}{r}\right)\frac{1}{(2r-1)^{m/2}}.$

###### Proof.

$\lvert S_{m}\rvert\lambda(A_{m})$ is essentially the sum operator of [EW17,
Section 12.2], but on a different graph: let $G_{m}$ be the graph with vertex
set $\mathbb{F}_{r}$ and an edge between every pair of vertices whose distance
in $\mathbb{F}_{r}$ is exactly $m$ (deleting the original edges).

Within the proof of the upper bound of [EW17, Theorem 12.23], the following is
shown: if $\Lambda$ is a positive-valued function of the directed edges of
$G_{m}$ such that $\Lambda(v,w)=(\Lambda(w,v))^{-1}$ then

$\|\lvert
S_{m}\rvert\lambda(A_{m})\|_{\ell^{2}}\leq\rho\coloneqq\sup_{v\in\mathbb{F}_{r}}\sum_{w\sim_{G_{m}}v}\Lambda(v,w)$

where the sum is over vertices adjacent to $v$ in $G_{m}$.

Our desired upper bound will come from taking

$\Lambda(v,w)=(2r-1)^{(d(e,v)-d(e,w))/2}$

where $e\in\mathbb{F}_{r}$ is the identity and the distance here refers to the
original graph structure on $\mathbb{F}_{r}$. We will bound $\sum_{w\sim
v}\Lambda(v,w)$ by breaking up the sum according to $v$ and $w$’s nearest
common ancestor (again, in the original graph): we say their nearest ancestor
is $i$ above $v$ if the point on the simple path from $v$ to $w$ which comes
closest to $e$ is $i$ units closer to $e$ than $v$ is. Breaking up the sum
according to $i$ in this way, we get

$\displaystyle\sum_{w\sim v}\Lambda(v,w)$
$\displaystyle=\sum_{i=0}^{m}\sum_{w\,:\,\cdots}\Lambda(v,w)$
$\displaystyle=\sum_{i=0}^{m}\lvert\\{w\,:\,\cdots\\}\rvert\,(2r-1)^{(2i-m)/2}$

We bound this by noting that the set of $w$ whose nearest ancestor with $v$ is
$i$ above $v$ and whose distance from $v$ is $n$ is a subset of the vertices
which are $(m-i)$th generation descendants of that common ancestor. First
suppose $v$ is not the identity. If $i=0$, there are $(2r-1)^{m}$ of them;
otherwise there are at most $(2r-2)(2r-1)^{m-i-1}$ (or none if $v$ is closer
than distance $i$ to the identity). This gives

$\displaystyle\sum_{w\sim v}\Lambda(v,w)$
$\displaystyle\leq(2r-1)^{m}(2r-1)^{(-m)/2}+\sum_{i=1}^{m-1}(2r-2)(2r-1)^{m-i-1}\,(2r-1)^{(2i-m)/2}+(2r-1)^{m/2}$
$\displaystyle=(m+1-\tfrac{m-1}{2r-1})(2r-1)^{m/2}.$

If $v$ is the identity, then we can compute

$\sum_{w\sim
e}\Lambda(e,w)=2r(2r-1)^{m-1}(2r-1)^{-m/2}=\tfrac{2r}{2r-1}(2r-1)^{m/2}$

but for $r\geq 2$ this is smaller than the upper bound in the $v\neq e$ case
for all $m\geq 1$. So we get $\rho\leq(m+1-\tfrac{m-1}{2r-1})(2r-1)^{m/2}$,
which implies the claimed upper bound on $\|\lambda(A_{m})\|$.

We now prove the lower bound, again based on the $m=1$ case in [EW17, Theorem
12.23]. To simplify notation let $b=2r-1$ denote the branching factor. For the
remainder of the proof we only consider the original, standard graph structure
on $\mathbb{F}_{r}$. For each $N\geq 2m$ let
$f_{N}\in\ell^{2}(\mathbb{F}_{r})$ be given by

$f(v)=\left\\{\begin{array}[]{ll}b^{-\frac{1}{2}d(v,e)},&d(v,e)\leq N\\\
0,&\text{else}.\end{array}\right.$

A straightforward calculation shows

$\|f_{N}\|_{\ell^{2}}^{2}=1+N\frac{b+1}{b},$

and if $d(v,e)=n$ where $m\leq n\leq N-m$ then

$\lvert S_{m}\rvert\lambda(A_{m})f(v)=b^{-n/2}b^{m/2}(m+1-\tfrac{m-1}{b})$

so

$\displaystyle\big{\|}\lvert
S_{m}\rvert\lambda(A_{m})f\big{\|}_{\ell^{2}}^{2}$
$\displaystyle>\sum_{n=m}^{N-m}\left(b^{-n/2}b^{m/2}(m+1-\tfrac{m-1}{b})\right)^{2}\lvert\\{v\,:\,d(v,e)=n\\}\rvert$
$\displaystyle=b^{m}(m+1-\tfrac{m-1}{b})^{2}(N-2m+1)\tfrac{b+1}{b},$

and

$\lvert S_{m}\rvert\|\lambda(A_{m})\|_{\ell^{2}}\geq
b^{m/2}(m+1-\tfrac{m-1}{b})\sqrt{\frac{N-2m+1}{\frac{b}{b+1}+N}}.$

Taking $N\to\infty$ gives the lower bound. ∎

The following lemma will be used to get a lower bound on
$\|\pi(A_{m})\|_{L^{2}_{0}(\mu)}$ in terms of the second-largest eigenvalue.

######  Lemma 4.3.

Suppose $M$ is a $d\times d$ column-stochastic matrix, let $\theta$ be its
second-largest eigenvalue, and let $p$ be a stationary probability vector.
Then $M$ has a left $\theta$-eigenvector $f\in\mathbb{C}^{d}$ orthogonal to
$p$.

###### Proof.

Let $p\in\mathbb{R}^{d}$ be a stationary probability vector for $M$, or in
other words a right $1$-eigenvector whose entries sum to 1. Let
$U\subset\mathbb{C}^{d}$ be the orthogonal complement of $p$. Since $U$ has
codimension 1 and $\mathbf{1}\not\in U$,
$\mathbb{C}^{d}=U\oplus\operatorname{span}\\{\mathbf{1}\\}$.

Since $x^{T}Mp=x^{T}p$, multiplication by $M$ on the right preserves this
decomposition of $\mathbb{C}^{d}$. This implies that $M$ has a left
$\theta$-eigenvector in $U$. ∎

Note: if $1$ has algebraic multiplicity greater than 1 as an eigenvalue of
$M$, then we can take $\theta=1$.

######  Proposition 4.4.

Suppose $\mu$ is a completely homogeneous Markov chain on $\mathbb{F}_{r}$
with transition matrix $M$, and let $\theta$ be the second-largest eigenvalue
of $M$. Then for every $m\in\mathbb{N}$,

$\|\pi(A_{m})\|_{L^{2}_{0}(\mu)}\geq\lvert\theta\rvert^{m}.$

###### Proof.

Let $p\in\mathbb{R}^{\mathtt{A}}$ be the single-site marginal of $\mu$. Since
$p$ is a right $1$-eigenvector of $M$, by Lemma 4.3 we can pick some
$f\in\mathbb{C}^{\mathtt{A}}$ which is a left $\theta$-eigenvector of $M$ and
orthogonal to $p$.

Define $F\in L^{2}_{0}(\mu)$ by $F(\mathbf{z})=f(\mathbf{z}(e))$; note $F$ has
mean zero since $f$ is orthogonal to $p$. Multiplying $f$ by a scalar if
necessary, we can also assume
$\|F\|_{L^{2}(\mu)}=\operatorname{Var}_{p}(f)=1$. Since $\pi(A_{m})$ is self-
adjoint,

$\|\pi(A_{m})\|_{L^{2}_{0}(\mu)}\geq\lvert\langle F,\
\pi(A_{m})F\rangle\rvert=\left\lvert\frac{1}{\lvert
S_{m}\rvert}\sum_{\gamma\in S_{m}}\int
f(\mathbf{z}(e))\,\overline{f(\mathbf{z}(\gamma))}\,\mu(d\mathbf{z})\right\rvert.$

Since $\mu$ is completely homogenous, every term in the sum has the same
value. If $\gamma\in\mathbb{F}_{r}$ is distance $m$ from the identity,

$\displaystyle\int
f(\mathbf{z}(e))\,\overline{f(\mathbf{z}(\gamma))}\,\mu(d\mathbf{z})$
$\displaystyle=\sum_{\mathtt{a}_{1},\mathtt{a}_{2}\in\mathtt{A}}f(\mathtt{a}_{1})\overline{f(\mathtt{a}_{2})}\,\mathbb{P}_{\mathbf{z}\sim\mu}\\{\mathbf{z}(e)=\mathtt{a}_{1},\
\mathbf{z}(\gamma)=\mathtt{a}_{2}\\}$
$\displaystyle=\sum_{\mathtt{a}_{1},\mathtt{a}_{2}\in\mathtt{A}}f(\mathtt{a}_{1})\overline{f(\mathtt{a}_{2})}\,p(\mathtt{a}_{1})M^{m}_{\mathtt{a}_{2},\mathtt{a}_{1}}$
$\displaystyle=\sum_{\mathtt{a}_{1}\in\mathtt{A}}f(\mathtt{a}_{1})p(\mathtt{a}_{1})\sum_{\mathtt{a}_{2}\in\mathtt{A}}\overline{f(\mathtt{a}_{2})}M^{m}_{\mathtt{a}_{2},\mathtt{a}_{1}}.$

Now since $M$ has real entries and $f$ is a left $\theta$-eigenvector,

$\sum_{\mathtt{a}_{2}\in\mathtt{A}}\overline{f(\mathtt{a}_{2})}M^{m}_{\mathtt{a}_{2},\mathtt{a}_{1}}=\overline{\sum_{\mathtt{a}_{2}\in\mathtt{A}}f(\mathtt{a}_{2})M^{m}_{\mathtt{a}_{2},\mathtt{a}_{1}}}=\overline{\theta^{m}f(\mathtt{a}_{1})}.$

So since $\operatorname{Var}_{p}(f)=1$ and
$\operatorname*{\mathbb{E}}_{p}(f)=0$

$\int
f(\mathbf{z}(e))\,f(\mathbf{z}(\gamma))\,\mu(d\mathbf{z})=\overline{\theta^{m}}\sum_{\mathtt{a}_{1}\in\mathtt{A}}f(\mathtt{a}_{1})\overline{f(\mathtt{a}_{1})}p(\mathtt{a}_{1})=\overline{\theta^{m}}.$

Altogether this gives

$\|\pi(A_{m})\|_{L^{2}_{0}(\mu)}\geq\lvert\overline{\theta^{m}}\rvert=\lvert\theta\rvert^{m}$

as claimed. ∎

We can now prove the main result of this section:

###### Proof of Theorem 1.3.

We show that if a Markov chain $\mu$ on $\mathbb{F}_{r}$ is weakly typical,
the preceding results in this section imply that
$\lvert\theta\rvert^{2}(2r-1)\leq 1$.

If $\mu$ is weakly typical then the above implies that for every
$m\in\mathbb{N}$

$\lvert\theta\rvert^{m}\overset{\text{Prop.}~{}\ref{prop:repopbound}}{\leq}\|\pi(A_{m})\|_{L^{2}_{0}(\mu)}\overset{\text{Thm.}~{}\ref{thm:repopbound}}{\leq}\|\lambda(A_{m})\|_{\ell^{2}(\mathbb{F}_{r})}\overset{\text{Prop.}~{}\ref{prop:treeavgbound}}{=}\left(m+1-\frac{m}{r}\right)\frac{1}{(2r-1)^{m/2}},$

so

$\lvert\theta\rvert\leq\lim_{m\to\infty}\left(\left(m+1-\frac{m}{r}\right)\frac{1}{(2r-1)^{m/2}}\right)^{1/m}=\frac{1}{\sqrt{2r-1}}$

which is the claimed bound on $\theta$. ∎

##  5 Typical upper and lower sofic entropy values: Proof of Theorem 1.1

Recall that we have a sequence of finite sets $\\{V_{n}\\}_{n=1}^{\infty}$ and
for each $n$ a probability distribution on
$\operatorname{Hom}(\Gamma,\operatorname{Sym}(V_{n}))$, such that the sequence
of these probability distributions forms an exponentially concentrated random
sofic approximation.

Let $\gamma_{n}\in\operatorname{Hom}(\Gamma,\operatorname{Sym}(V_{n}))$ denote
a random homomorphism whose law is part of this sequence.

Recall that there is then a sequence of sets of homomorphisms
$\\{S_{n}^{\mathrm{sofic}}\subset\operatorname{Hom}(\Gamma,\operatorname{Sym}(V_{n}))\\}_{n=1}^{\infty}$
with $\mathbb{P}(S_{n}^{\mathrm{sofic}})\to 1$ such that if $\sigma_{n}\in
S_{n}$ for each $n$ then $\Sigma=\\{\sigma_{n}\\}_{n=1}^{\infty}$ is a sofic
approximation to $\Gamma$. All of the work in this section will go into using
exponential concentration to produce another sequence
$\\{S^{\prime}_{n}\\}_{n=1}^{\infty}$ of sets along which the number of good
models is controlled. We will then intersect that sequence with
$S_{n}^{\mathrm{sofic}}$.

For $\mu\in\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma})$,
$n\in\mathbb{N}$ and $\varepsilon,\delta>0$ we define the following four sets
of “bad” homomorphisms in
$\operatorname{Hom}(\Gamma,\operatorname{Sym}(V_{n}))$, which we write as
events in terms of $\gamma_{n}$: if $h^{\sharp}(\mu)$ and $h^{\flat}(\mu)$ are
finite, then

$\displaystyle\mathcal{F}^{\geq,\sharp}(\mu,\varepsilon,\delta,n)$
$\displaystyle=\left\\{\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert\Omega(\gamma_{n},\mu,\varepsilon)\right\rvert\geq
h^{\sharp}+\delta\right\\}$
$\displaystyle\mathcal{F}^{\geq,\flat}(\mu,\varepsilon,\delta,n)$
$\displaystyle=\left\\{\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert\Omega(\gamma_{n},\mu,\varepsilon)\right\rvert\geq
h^{\flat}+\delta\right\\}$
$\displaystyle\mathcal{F}^{\leq,\sharp}(\mu,\varepsilon,\delta,n)$
$\displaystyle=\left\\{\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert\Omega(\gamma_{n},\mu,\varepsilon)\right\rvert\leq
h^{\sharp}-\delta\right\\}$
$\displaystyle\mathcal{F}^{\leq,\flat}(\mu,\varepsilon,\delta,n)$
$\displaystyle=\left\\{\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert\Omega(\gamma_{n},\mu,\varepsilon)\right\rvert\leq
h^{\flat}-\delta\right\\}.$ If $h^{\flat}(\mu)=-\infty$ then we set
$\mathcal{F}^{\leq,\flat}(\mu,\varepsilon,\delta,n)=\varnothing$ and in the
definition of $\mathcal{F}^{\geq,\flat}(\mu,\varepsilon,\delta,n)$ we change
$h^{\flat}(\mu)+\delta$ to $0$. Make similar changes if
$h^{\sharp}(\mu)=-\infty$.

We first show that all of these sets have small probability:

  1. 1.

For each $\delta>0$ and small enough (depending on $\delta$) $\varepsilon>0$
there exists $\xi$ such that for all large $n$

$\mathbb{P}\left(\mathcal{F}^{\geq,\sharp}(\mu,\varepsilon,\delta,n)\right)<e^{-\xi\lvert
V_{n}\rvert}.$

_Proof:_

    1. (a)

in the case $h^{\sharp}\geq 0$: by definition of $h^{\sharp}$ we have
$\underline{\rho}_{\mu}(h^{\sharp}+\delta)>0$, and

$\mathcal{F}^{\geq,\sharp}(\mu,\varepsilon,\delta,n)=\left\\{\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert\Omega(\gamma_{n},\mu,\varepsilon)\right\rvert\geq
h^{\sharp}+\delta\right\\}\subseteq\left\\{\rho_{\mu}(\gamma_{n},h^{\sharp}+\delta)\leq\varepsilon\right\\}$

so if $\varepsilon$ is small compared to
$\underline{\rho}_{\mu}(h^{\sharp}+\delta)$ then this is exponentially
unlikely for all large $n$ by Lemma 2.1.

    2. (b)

in the case $h^{\sharp}=-\infty$: by definition of $h^{\sharp}$ we have
$\underline{\rho}_{\mu}(0)>0$, and

$\mathcal{F}^{\geq,\sharp}(\mu,\varepsilon,\delta,n)=\left\\{\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert\Omega(\gamma_{n},\mu,\varepsilon)\right\rvert\geq
0\right\\}\subseteq\left\\{\rho_{\mu}(\gamma_{n},0)\leq\varepsilon\right\\}$

so if $\varepsilon$ is small compared to $\underline{\rho}_{\mu}(0)$ then this
is exponentially unlikely for all large $n$.

  2. 2.

For each $\delta>0$ and small enough (depending on $\delta$) $\varepsilon>0$
there exists $\xi$ such that for infinitely many $n$

$\mathbb{P}\left(\mathcal{F}^{\geq,\flat}(\mu,\varepsilon,\delta,n)\right)<e^{-\xi\lvert
V_{n}\rvert}.$

_Proof:_

    1. (a)

if $h^{\flat}\geq 0$: by definition of $h^{\flat}$ we have
$\overline{\rho}_{\mu}(h^{\flat}+\delta)>0$, and

$\mathcal{F}^{\geq,\flat}(\mu,\varepsilon,\delta,n)=\left\\{\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert\Omega(\gamma_{n},\mu,\varepsilon)\right\rvert\geq
h^{\flat}+\delta\right\\}\subseteq\left\\{\rho_{\mu}(\gamma_{n},h^{\flat}+\delta)\leq\varepsilon\right\\}$

so if $\varepsilon$ is small compared to
$\overline{\rho}_{\mu}(h^{\flat}+\delta)$ then this is exponentially unlikely
for infinitely many $n$.

    2. (b)

if $h^{\flat}=-\infty$: by definition of $h^{\flat}$ we have
$\overline{\rho}_{\mu}(0)>0$, and

$\mathcal{F}^{\geq,\flat}(\mu,\varepsilon,\delta,n)=\left\\{\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert\Omega(\gamma_{n},\mu,\varepsilon)\right\rvert\geq
0\right\\}\subseteq\left\\{\rho_{\mu}(\gamma_{n},0)\leq\varepsilon\right\\}$

so if $\varepsilon$ is small compared to $\overline{\rho}_{\mu}(0)$ then this
is exponentially unlikely for infinitely many $n$.

  3. 3.

For each $\varepsilon,\delta>0$ there exists $\xi$ such that for infinitely
many $n$

$\mathbb{P}\left(\mathcal{F}^{\leq,\sharp}(\mu,\varepsilon,\delta,n)\right)\leq
e^{-\xi\lvert V_{n}\rvert}.$

_Proof:_

    1. (a)

if $h^{\sharp}\geq 0$: by definition of $h^{\sharp}$ we have
$\underline{\rho}_{\mu}(h^{\sharp}-\delta)=0$, and

$\mathcal{F}^{\leq,\sharp}(\mu,\varepsilon,\delta,n)=\left\\{\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert\Omega(\gamma_{n},\mu,\varepsilon)\right\rvert\leq
h^{\sharp}-\delta\right\\}\subseteq\left\\{\rho_{\mu}(\gamma_{n},h^{\sharp}-\tfrac{\delta}{2})\geq\varepsilon\right\\}$

which is exponentially unlikely for infinitely many $n$.

    2. (b)

if $h^{\sharp}=-\infty$: $\mathcal{F}^{\leq,\sharp}(\mu,\varepsilon,\delta,n)$
is defined to be empty, so the bound holds for all $n$ for any $\xi$.

  4. 4.

For each $\varepsilon,\delta>0$ there exists $\xi$ such that for all large $n$

$\mathbb{P}\left(\mathcal{F}^{\leq,\flat}(\mu,\varepsilon,\delta,n)\right)\leq
e^{-\xi\lvert V_{n}\rvert}.$

_Proof:_

    1. (a)

if $h^{\flat}\geq 0$: by definition of $h^{\flat}$ we have
$\overline{\rho}_{\mu}(h^{\flat}-\delta)=0$, and

$\mathcal{F}^{\leq,\flat}(\mu,\varepsilon,\delta,n)=\left\\{\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert\Omega(\gamma_{n},\mu,\varepsilon)\right\rvert\leq
h^{\flat}-\delta\right\\}\subseteq\left\\{\rho_{\mu}(\gamma_{n},h^{\flat}-\tfrac{\delta}{2})\geq\varepsilon\right\\}$

which is exponentially unlikely for all large $n$.

    2. (b)

if $h^{\flat}=-\infty$: $\mathcal{F}^{\leq,\flat}(\mu,\varepsilon,\delta,n)$
is defined to be empty, so the bound holds for all $n$ for any $\xi$.

Pick a sequence $(\delta_{m})_{m\in\mathbb{N}}$ decreasing with limit 0. For
each $m$, for every $\mu\in\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma})$
for small enough $\varepsilon>0$

  1. (a)

the bounds in items 1 and 2 above hold

  2. (b)

for every $\nu\in\mathrm{B}(\mu,\varepsilon)$, $h^{\sharp}(\nu)$ and
$h^{\flat}(\nu)$ are less than $h^{\sharp}(\mu)+\delta_{m}$ and
$h^{\flat}(\mu)+\delta_{m}$, respectively (or less than 0 if $h^{\sharp}(\mu)$
or $h^{\flat}(\mu)$ is $-\infty$). This uses upper semicontinuity of
$h^{\flat}$ and $h^{\sharp}$.

Then, by compactness, for each $m$ we can pick a a finite set of measures
$\mu_{m,1},\ldots,\mu_{m,K_{m}}$ with corresponding
$\varepsilon_{m,1},\ldots,\varepsilon_{m,K_{m}}$ such that
$\\{\mathrm{B}(\mu_{m,k},\varepsilon_{m,k})\\}_{k=1}^{K_{m}}$ covers
$\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma})$. We can also require that
$\limsup_{m\to\infty}\max\\{\varepsilon_{m,k}\,:\,1\leq k\leq K_{m}\\}=0$.

For $\diamond\in\\{\leq,\geq\\}$ and $\star\in\\{\flat,\sharp\\}$ let
$\mathcal{E}^{\diamond,\star}_{m,k,n}=\mathcal{F}^{\diamond,\star}(\mu_{m,k},\varepsilon_{m,k},\delta_{m},n)$,
except for $(\leq,\sharp)$ and $(\geq,\flat)$: in those cases we take this
definition for those infinitely many $n$ where the exponentially decaying
bound on their probability holds and define the sets to be empty otherwise.

For each $m$ let $\xi_{m}$ be such that
$\mathbb{P}(\mathcal{E}^{\diamond,\star}_{m,k,n})<e^{-\xi_{m}\lvert
V_{n}\rvert}$ for all large enough $n$ and all choices of
$\diamond\in\\{\leq,\geq\\}$, $\star\in\\{\flat,\sharp\\}$ and all
$k=1,\ldots,K_{m}$.

Choose an increasing sequence $N_{m}$ so that for all $n>N_{m}$

$\displaystyle\frac{1}{m}$ $\displaystyle\geq
4\sum_{i=1}^{m}K_{i}e^{-\xi_{i}\lvert V_{n}\rvert}$ and
$\displaystyle\mathbb{P}\left[\mathcal{E}^{\diamond,\star}_{i,k,n}\right]$
$\displaystyle\leq e^{-\xi_{i}\lvert V_{n}\rvert}\quad\text{ for all
}i\in[m],\ \diamond\in\\{\leq,\geq\\},\ \star\in\\{\flat,\sharp\\},\
k\in[K_{i}].$

Now let

$\mathcal{U}_{m,n}=\left(\bigcup_{i=1}^{m}\bigcup_{k=1}^{K_{i}}\mathcal{E}^{\geq,\flat}_{i,k,n}\cup\mathcal{E}^{\geq,\sharp}_{i,k,n}\cup\mathcal{E}^{\leq,\flat}_{i,k,n}\cup\mathcal{E}^{\leq,\sharp}_{i,k,n}\right)^{c}.$

For all $n>N_{m}$ we have

$\mathbb{P}\left(\mathcal{U}_{m,n}\right)\geq
1-4\sum_{i=1}^{m}K_{i}e^{-\xi_{i}\lvert V_{n}\rvert}\geq 1-\frac{1}{m}.$

Now for each $m$ and each $n\in(N_{m},N_{m+1}]$ let
$S_{n}^{\prime}=\mathcal{U}_{m,n}$. Note that for each $m,n$ we have
$\mathcal{U}_{m,n}\supset\mathcal{U}_{m+1,n}$. So if
$\Sigma=\\{\sigma_{n}\\}_{n=1}^{\infty}$ is such that $\sigma_{n}\in
S_{n}^{\prime}$ for each $n$, this ensures that for each $m$, for all
$n>N_{m}$ we have $\sigma_{n}\in\mathcal{U}_{m,n}$. In particular, for any
$\mu$:

  1. 1.

Given $m\in\mathbb{N}$ pick $k\in[K_{m}]$ such that
$\mu\in\mathrm{B}(\mu_{m,k},\varepsilon_{m,k})$. For all $n>N_{m}$ we have
$\sigma_{n}\not\in\mathcal{E}^{\geq,\sharp}_{m,k,n}$, so for all large $n$ we
have
$\sigma_{n}\not\in\mathcal{F}^{\geq,\sharp}(\mu_{m,k},\varepsilon_{m,k},\delta_{m},n)$.
Hence if $\varepsilon$ is small enough that
$\mathrm{B}(\mu,\varepsilon)\subset\mathrm{B}(\mu_{m,k},\varepsilon_{m,k})$
then

$\limsup_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert\leq\limsup_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert\Omega(\sigma_{n},\mu_{m,k},\varepsilon_{m,k})\right\rvert\leq
h^{\sharp}(\mu_{m,k})+\delta_{m},$

where we take $-\infty+\delta_{m}=-\infty$. Taking $\varepsilon\to 0$ then
gives

$\overline{\operatorname{h}}_{\Sigma}(\mu)\leq
h^{\sharp}(\mu_{m,k})+\delta_{m},$

and taking the lim sup as $m\to\infty$ gives
$\overline{\operatorname{h}}_{\Sigma}(\mu)\leq h^{\sharp}(\mu)$ by upper
semicontinuity of $h^{\sharp}$.

If $h^{\sharp}(\mu)=-\infty$, then this gives
$\overline{\operatorname{h}}_{\Sigma}(\mu)=h^{\sharp}(\mu)$.

  2. 2.

For each $m$, pick $k$ as in part 1. For all $n>N_{m}$ we have
$\sigma_{n}\not\in\mathcal{E}^{\geq,\flat}_{m,k,n}$. So for infinitely many
$n$ we have
$\sigma_{n}\not\in\mathcal{F}^{\geq,\flat}(\mu_{m,k},\varepsilon_{m,k},\delta_{m},n)$,
and if $\varepsilon$ is small enough

$\liminf_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert\leq
h^{\flat}(\mu_{m,k})+\delta_{m}.$

Taking $\varepsilon\to 0$ then $m\to\infty$ gives
$\underline{\operatorname{h}}_{\Sigma}(\mu)\leq h^{\flat}(\mu)$, by upper
semicontinuity of $h^{\flat}$.

If $h^{\flat}(\mu)=-\infty$, then this gives
$\underline{\operatorname{h}}_{\Sigma}(\mu)=h^{\flat}(\mu)$.

  3. 3.

Given $\varepsilon>0$, pick $m$ large enough that if we pick $k$ as in part 1
then
$\mathrm{B}(\mu_{m,k},\varepsilon_{m,k})\subset\mathrm{B}(\mu,\varepsilon)$;
this is possible because we required all $\varepsilon_{m,k}$ to be uniformly
small for large $m$, so whichever $\mathrm{B}(\mu_{m,k},\varepsilon_{m,k})$
contains $\mu$ must eventually be contained in $\mathrm{B}(\mu,\varepsilon)$.
This ensures that $h^{\sharp}(\mu)\leq h^{\sharp}(\mu_{m,k})+\delta_{m}$.

For all $n>N_{m}$ we have
$\sigma_{n}\not\in\mathcal{E}^{\leq,\sharp}_{m,k,n}$. So for infinitely many
$n$ we have
$\sigma_{n}\not\in\mathcal{F}^{\leq,\sharp}(\mu_{m,k},\varepsilon_{m,k},\delta_{m},n)$,
and

$\displaystyle\limsup_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert\Omega(\sigma_{n},\mu,\varepsilon)\right\rvert$
$\displaystyle\geq\limsup_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert\Omega(\sigma_{n},\mu_{m,k},\varepsilon_{m,k})\right\rvert$
$\displaystyle\geq h^{\sharp}(\mu_{m,k})-\delta_{m}$ $\displaystyle\geq
h^{\sharp}(\mu)-2\delta_{m}.$

Taking $m\to\infty$ then $\varepsilon\to 0$ gives
$\overline{\operatorname{h}}_{\Sigma}(\mu)\geq h^{\sharp}(\mu)$.

  4. 4.

Given $\varepsilon>0$, pick $m$ as in part 3. For all $n>N_{m}$ we have
$\sigma_{n}\not\in\mathcal{E}^{\leq,\flat}_{m,k,n}$. So for all large $n$ we
have
$\sigma_{n}\not\in\mathcal{F}^{\leq,\flat}(\mu_{m,k},\varepsilon_{m,k},\delta_{m},n)$,
and

$\displaystyle\liminf_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert\Omega(\sigma_{n},\mu,\varepsilon_{m})\right\rvert$
$\displaystyle\geq\liminf_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert\Omega(\sigma_{n},\mu_{m,k},\varepsilon_{m,k})\right\rvert$
$\displaystyle\geq h^{\flat}(\mu_{m,k})-\delta_{m}$ $\displaystyle\geq
h^{\flat}(\mu)-2\delta_{m}.$

Taking $m\to\infty$ then $\varepsilon\to 0$ gives
$\underline{\operatorname{h}}_{\Sigma}(\mu)\geq h^{\flat}(\mu)$.

Finally, if we take $S_{n}=S_{n}^{\prime}\cap S_{n}^{\mathrm{sofic}}$ for each
$n$, then $\\{S_{n}\\}_{n=1}^{\infty}$ is a sequence with the desired
property.

## References

  * [Aus16] Tim Austin  “Additivity Properties of Sofic Entropy and Measures on Model Spaces”  In _Forum of Mathematics, Sigma_ 4, 2016  DOI: 10.1017/fms.2016.18
  * [BBS22] Ágnes Backhausz, Charles Bordenave and Balázs Szegedy  “Typicality and Entropy of Processes on Infinite Trees”  In _Annales de l’Institut Henri Poincaré, Probabilités et Statistiques_ 58.4, 2022  DOI: 10.1214/21-AIHP1233
  * [BC19] Charles Bordenave and Benoît Collins  “Eigenvalues of Random Lifts and Polynomials of Random Permutation Matrices”  In _Annals of Mathematics_ 190.3, 2019  DOI: 10.4007/annals.2019.190.3.3
  * [BDV08] Bachir Bekka, Pierre De La Harpe and Alain Valette  “Kazhdan’s Property (T)”  Cambridge University Press, 2008  DOI: 10.1017/CBO9780511542749
  * [BK20] Peter J. Burton and Alexander S. Kechris  “Weak Containment of Measure-Preserving Group Actions”  In _Ergodic Theory and Dynamical Systems_ 40.10, 2020, pp. 2681–2733  DOI: 10.1017/etds.2019.26
  * [BM22] Sebastián Barbieri and Tom Meyerovitch  “The Lanford–Ruelle Theorem for Actions of Sofic Groups”  In _Transactions of the American Mathematical Society_ , 2022  DOI: 10.1090/tran/8810
  * [Bow10] Lewis Bowen  “A Measure-Conjugacy Invariant for Free Group Actions”  In _Annals of Mathematics_ 171.2, 2010, pp. 1387–1400  DOI: 10.4007/annals.2010.171.1387
  * [Bow10a] Lewis Bowen  “Measure Conjugacy Invariants for Actions of Countable Sofic Groups”  In _Journal of the American Mathematical Society_ 23.1, 2010, pp. 217–217  DOI: 10.1090/S0894-0347-09-00637-7
  * [Bow10b] Lewis Bowen  “Non-Abelian Free Group Actions: Markov Processes, the Abramov–Rohlin Formula and Yuzvinskii’s Formula”  In _Ergodic Theory and Dynamical Systems_ 30.6, 2010, pp. 1629–1663  DOI: 10.1017/S0143385709000844
  * [Bow10c] Lewis Bowen  “The Ergodic Theory of Free Group Actions: Entropy and the f-Invariant”  In _Groups, Geometry, and Dynamics_ , 2010, pp. 419–432  DOI: 10.4171/GGD/89
  * [BRZ95] P.. Bleher, J. Ruiz and V.. Zagrebnov  “On the Purity of the Limiting Gibbs State for the Ising Model on the Bethe Lattice”  In _Journal of Statistical Physics_ 79.1-2, 1995, pp. 473–482  DOI: 10.1007/BF02179399
  * [BS18] Ágnes Backhausz and Balázs Szegedy  “On Large-Girth Regular Graphs and Random Processes on Trees”  In _Random Structures & Algorithms_ 53.3, 2018, pp. 389–416  DOI: 10.1002/rsa.20769
  * [BSV15] Ágnes Backhausz, Balázs Szegedy and Bálint Virág  “Ramanujan Graphings and Correlation Decay in Local Algorithms”  In _Random Structures & Algorithms_ 47.3, 2015, pp. 424–435  DOI: 10.1002/rsa.20562
  * [Coj+23] Amin Coja-Oghlan et al.  “Metastability of the Potts Ferromagnet on Random Regular Graphs”  In _Communications in Mathematical Physics_ , 2023  DOI: 10.1007/s00220-023-04644-6
  * [DMS17] Amir Dembo, Andrea Montanari and Subhabrata Sen  “Extremal Cuts of Sparse Random Graphs”  In _The Annals of Probability_ 45.2, 2017, pp. 1190–1217  DOI: 10.1214/15-AOP1084
  * [EW17] Manfred Einsiedler and Thomas Ward  “Functional Analysis, Spectral Theory, and Applications” 276, Graduate Texts in Mathematics  Cham: Springer International Publishing, 2017  DOI: 10.1007/978-3-319-58540-6
  * [FŁ92] A.M Frieze and T Łuczak  “On the Independence and Chromatic Numbers of Random Regular Graphs”  In _Journal of Combinatorial Theory, Series B_ 54.1, 1992, pp. 123–132  DOI: 10.1016/0095-8956(92)90070-E
  * [Gal+16] Andreas Galanis, Daniel Stefankovic, Eric Vigoda and Linji Yang  “Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results”  arXiv, 2016  arXiv:1311.4839 [math-ph]
  * [Gal+16a] Andreas Galanis, Daniel Štefankovič, Eric Vigoda and Linji Yang  “Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results”  In _SIAM Journal on Computing_ 45.6, 2016, pp. 2004–2065  DOI: 10.1137/140997580
  * [Geo11] Hans-Otto Georgii  “Gibbs Measures and Phase Transitions”, De Gruyter Studies in Mathematics 9  Berlin: de Gruyter, 2011
  * [KRK14] C. Külske, U.. Rozikov and R.. Khakimov  “Description of the Translation-Invariant Splitting Gibbs Measures for the Potts Model on a Cayley Tree”  In _Journal of Statistical Physics_ 156.1, 2014, pp. 189–200  DOI: 10.1007/s10955-014-0986-y
  * [Lyo17] Russell Lyons  “Factors of IID on Trees”  In _Combinatorics, Probability and Computing_ 26.2, 2017, pp. 285–300  DOI: 10.1017/S096354831600033X
  * [MM06] Marc Mezard and Andrea Montanari  “Reconstruction on Trees and Spin Glass Transition”  In _Journal of Statistical Physics_ 124.6, 2006, pp. 1317–1350  DOI: 10.1007/s10955-006-9162-3
  * [MMS12] Andrea Montanari, Elchanan Mossel and Allan Sly  “The Weak Limit of Ising Models on Locally Tree-like Graphs”  In _Probability Theory and Related Fields_ 152.1-2, 2012, pp. 31–51  DOI: 10.1007/s00440-010-0315-6
  * [Mos01] Elchanan Mossel  “Reconstruction on Trees: Beating the Second Eigenvalue”  In _The Annals of Applied Probability_ 11.1, 2001  DOI: 10.1214/aoap/998926994
  * [MP03] Elchanan Mossel and Yuval Peres  “Information Flow on Trees”  In _The Annals of Applied Probability_ 13.3, 2003, pp. 817–844  DOI: 10.1214/aoap/1060202828
  * [Shr21] Christopher Shriver  “Metastability and Maximal-Entropy Joinings of Gibbs Measures on Finitely-Generated Groups”  In _arXiv:2103.04467 [math-ph]_ , 2021  arXiv:2103.04467 [math-ph]
  * [Shr22] Christopher Shriver  “Free Energy, Gibbs Measures, and Glauber Dynamics for Nearest-Neighbor Interactions”  In _Communications in Mathematical Physics_ , 2022  DOI: 10.1007/s00220-022-04537-0
  * [Shr22a] Christopher Shriver  “The Relative _f_ -Invariant and Non-Uniform Random Sofic Approximations”  In _Ergodic Theory and Dynamical Systems_ , 2022, pp. 1–38  DOI: 10.1017/etds.2022.27
  * [Shr23] Christopher Shriver  “Equilibrium and Nonequilibrium Gibbs States on Sofic Groups”  arXiv, 2023  arXiv:2305.11803 [math-ph]
  * [Tem84] A.. Tempelman  “Specific Characteristics and Variational Principle for Homogeneous Random Fields”  In _Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete_ 65.3, 1984, pp. 341–365  DOI: 10.1007/BF00533741
  * [Wor99] N.. Wormald  “Models of Random Regular Graphs”  In _Surveys in Combinatorics, 1999_ Cambridge University Press, 1999, pp. 239–298  DOI: 10.1017/CBO9780511721335.010