# Algebraic dynamical systems from LDPC codes satisfy a strong negation of the
weak Pinsker property

Tim Austin111supported in part by NSF grant DMS-1855694, Lewis
Bowen222supported in part by NSF grant DMS-2154680 and Christopher
Shriver333supported in part by NSF grant DMS-1937215

###### Abstract

We construct an explicit algebraic example of a subshift of finite type over a
group $\Gamma$ with an invariant Markov measure which has completely positive
sofic entropy (with respect to ‘most’ sofic approximations) and yet does not
have a direct Bernoulli factor, because its model spaces shatter into
exponentially many clusters of sub-exponential size. The example and its
analysis are related to random low-density parity-check (LDPC) codes.

Keywords: sofic entropy, LDPC codes, weak Pinsker property, Bernoulli shifts,
algebraic dynamics
MSC:37A35

###### Contents

  1. 1 Introduction
    1. 1.1 Background: classical entropy theory
    2. 1.2 Background: sofic entropy theory
    3. 1.3 Main results
    4. 1.4 Probabilistic versions of the main theorems
    5. 1.5 Outline of the paper
    6. 1.6 Notational conventions
    7. 1.7 Acknowledgements
  2. I General systems
    1. 2 Preliminaries
      1. 2.1 Sofic groups
      2. 2.2 Sofic entropy
      3. 2.3 Almost-Lipschitz approximations
    2. 3 Bethe–Kikuchi entropy and annealed calculations
      1. 3.1 Random sofic approximations
      2. 3.2 Formula for Kikuchi entropy
      3. 3.3 A brief history
    3. 4 Completely positive entropy, local convergence, and model mixing
      1. 4.1 Property M
    4. 5 Shattering
      1. 5.1 Consequences of shattering
      2. 5.2 Shattering and Bernoulli splittings
  3. II Parity check subshifts
    1. 6 LDPC codes and measures on microstate spaces
      1. 6.1 The use of LDPC codes
      2. 6.2 Outline of the rest of the paper
      3. 6.3 Random factor graphs
      4. 6.4 Parity-check matrices
    2. 7 Property M
      1. 7.1 Property M from few additional checks
      2. 7.2 Proof that there are few additional checks
    3. 8 Proof of local and empirical convergence
    4. 9 Proof of Theorem 1.3
      1. 9.1 Proof of the sofic entropy value
    5. 10 Proof of Theorems B and C
      1. 10.1 Expected number of low-density codewords
      2. 10.2 Proof of Theorem 6.1(3)
      3. 10.3 Proof of Theorem C
    6. 11 Directions for further study
      1. 11.1 Possible anti-Pinsker actions of other groups
      2. 11.2 Open problems for the parity-check subshift
    7. A A failure of contiguity

###  1 Introduction

This paper constructs explicit dynamical systems with unusual properties
related to recent work on the weak Pinsker property and shattering. The
construction is explained next; the background, motivation and precise
statements are developed afterwards.

Fix natural numbers $d,k$ and let $\Gamma=\Gamma_{d,k}$ be the $d$-fold free
product of order-$k$ cyclic groups:

$\Gamma:=\langle s_{1},\dots,s_{d}:\
s_{1}^{k}=\dots=s_{d}^{k}=e\rangle=\underbrace{\mathbb{Z}_{k}\ast\cdots\ast\mathbb{Z}_{k}}_{d},$

where $\mathbb{Z}_{k}$ means $\mathbb{Z}/k\mathbb{Z}$. The set of all
functions $x:\Gamma\to\mathbb{Z}_{2}$ is denoted $\mathbb{Z}_{2}^{\Gamma}$.
This is a compact Abelian group under pointwise addition with the pointwise
convergence topology. Let $X\leq\mathbb{Z}_{2}^{\Gamma}$ be the closed
subgroup defined by

$X=\left\\{x\in\mathbb{Z}_{2}^{\Gamma}:\
\sum_{j=0}^{k-1}x_{gs_{i}^{j}}=0\quad\forall g\in\Gamma,\
i=1,\dots,d\right\\},$

and let $\mu=m_{X}$ be the Haar probability measure on $X$.

For $g\in\Gamma$, let
$T^{g}:\mathbb{Z}_{2}^{\Gamma}\to\mathbb{Z}_{2}^{\Gamma}$ be the continuous
group automorphism given by permuting indices on the left:

$T^{g}((x_{h})_{h\in\Gamma})=(x_{g^{-1}h})_{h\in\Gamma}.$ (1)

The subgroup $X$ is invariant under this action, and hence so is its Haar
measure.

This state space is easily visualized in terms of the Cayley graph of $\Gamma$
with its generators $s_{1},\dots,s_{k}$. Through each group element $g$, each
$s_{i}$ generates a $k$-cycle. So each vertex of the Cayley graph lies in $d$
of these $k$-cycles, and there are no other relations in the group, so these
$k$-cycles are attached together into a hyper-tree. With this picture in mind,
a member of $X$ is simply an assignment of zeros and ones to the vertices of
the Cayley graph such that the sum around every $k$-cycle is even. For this
reason, and by analogy with similar constructions in coding theory, we call
$X$ a parity check subshift. Indeed, certain random finite parity check codes
play a crucial auxiliary role later in the paper: see Section 6.

Informally stated, our main results are these:

  * •

If $k>d\geq 3$ then the sofic entropy of the dynamical system $(X,m_{X},T)$ is
$(1-d/k)\log(2)$.

  * •

Every nontrivial factor of $(X,m_{X},T)$ has positive sofic entropy and
therefore positive Rokhlin entropy (this property is called ‘completely
positive entropy’ or ‘CPE’).

  * •

The system $(X,m_{X},T)$ is not isomorphic to a direct product of a nontrivial
Bernoulli shift with another system. Combined with the previous conclusion,
this is a strong negation of the weak Pinsker property.

  * •

The system $(X,m_{X},T)$ is not weakly contained in a Bernoulli shift. It is
one of the first examples that has completely positive entropy and also this
property.

Next we introduce background needed to state our main results precisely.

####  1.1 Background: classical entropy theory

Kolmogorov introduced entropy theory into dynamics for the purpose of
distinguishing Bernoulli shifts up to measure conjugacy. Given a standard
probability space $(\mathtt{K},\kappa)$, the Bernoulli shift over a countable
group $\Gamma$ with base space $(\mathtt{K},\kappa)$ consists of the
probability space $(\mathtt{K}^{\Gamma},\kappa^{\Gamma})$ together with the
action of $\Gamma$ by permuting indices as in 1. A sample of
$(\mathtt{K}^{\Gamma},\kappa^{\Gamma})$ is a random $\mathtt{K}$-valued
configuration $(x_{g})_{g\in\Gamma}$ whose coordinates are i.i.d. with law
$\kappa$.

Suppose we are given a standard probability space $(X,\mu)$ (where we have
left the sigma-algebra out of the notation for simplicity). Let
$\operatorname{Aut}(X,\mu)$ denote the group of all measure-preserving
automorphisms of $(X,\mu)$. A pmp (probability-measure-preserving) action of
$\Gamma$ is a homomorphism $T:\Gamma\to\operatorname{Aut}(X,\mu)$. The triple
$(X,\mu,T)$ is a $\Gamma$-system. We also refer to it as a system or action if
$\Gamma$ is understood.

If we are given two $\Gamma$-systems $(X_{i},\mu_{i},T_{i})$ then a measurable
map $\Phi:X_{1}\to X_{2}$ is a factor map if it is a.e. $\Gamma$-equivariant
(this means $\Phi(T_{1}^{g}x)=T_{2}^{g}\Phi(x)$ for all $g\in\Gamma$ and
$\mu_{1}$-a.e. $x\in X_{1}$) and the pushforward measure satisfies
$\Phi_{*}\mu_{1}=\mu_{2}$. More precisely, we allow that $\Phi$ be defined
only on a subset of full measure. If $\Phi$ is invertible (after ignoring a
some null set) then it is a measure-conjugacy or isomorphism.

If $\Gamma=\mathbb{Z}$ then an action of the integers is given by a single
transformation $T\in\operatorname{Aut}(X,\mu)$. Thus it makes sense to
consider whether two transformations are measurably conjugate.

A problem attributed to von Neumann asks whether there could be two Bernoulli
shifts over the group of integers which are not measurably conjugate. To
answer this, Kolmogorov defined the entropy rate of a dynamical system in the
special case in which $\Gamma=\mathbb{Z}$ [38, 39]. He proved entropy is
invariant under measure-conjugacy and computed entropy rates for Bernoulli
shifts, thereby answering the problem in the affirmative. In fact, the entropy
rate of a Bernoulli shift action is the same as the Shannon entropy of the
base space. When the base space is $(\mathtt{K},\kappa)$ and $\mathtt{K}$ is
countable, its Shannon entropy is

$H(\kappa)=-\sum_{k\in\mathtt{K}}\kappa(\\{k\\})\log(\kappa(\\{k\\})).$

If $\kappa$ is not supported on a countable set, then its Shannon entropy is
defined to be $+\infty$.

Kolmogorov’s theory extends fairly directly to the case when $\Gamma$ is
amenable. The first published work on entropy theory for general amenable
groups is due to Kieffer [36].

Since Kolmogorov’s pioneering work, entropy and Bernoulli shifts have played a
central role in classifying dynamical systems. For example, Sinai proved that
if an ergodic action of $\mathbb{Z}$ has positive entropy then it factors onto
a Bernoulli shift of the same entropy [62]. Because entropy cannot increase
under a factor map, this shows that Bernoulli factors witness entropy.
Inspired by Sinai’s theorem, Ornstein proved that Bernoulli shifts over the
integers are isomorphic if and only if they have the same entropy [47, 48].
These results were extended to the case of amenable acting groups in [53].

Shannon entropy is easily seen to be additive under direct products, and this
property is inherited by Kolmogorov’s entropy rate. Naively, one might guess
that any ergodic system is isomorphic to a direct product of a Bernoulli shift
with a zero entropy system. This turns out to be false; counterexamples to
weaker claims appear in [51, 50, 49]. If it were true for a system which was
not itself isomorphic to a Bernoulli shift, then additivity implies that the
system would have a nontrivial (direct) factor with zero entropy. A system is
said to have completely positive entropy (CPE) if every nontrivial factor has
positive entropy. Here a “trivial” factor is a measure-preserving system where
the measure is a delta mass at a single point. This system is a factor of
every other system, and it is easy to see that its entropy is zero. The paper
[52] shows that for any positive number $h>0$ there exist uncountably many
pairwise non-isomorphic transformations which are CPE and have entropy $h$.

A factor map $\pi:(X_{1},\mu_{1},T_{1})\to(X_{2},\mu_{2},T_{2})$ is said to be
direct or split if there is another factor map
$\xi:(X_{1},\mu_{1},T_{1})\to(X_{3},\mu_{3},T_{3})$ so that the pair
$(\pi,\xi)$ together forms an isomorphism

$(X_{1},\mu_{1},T_{1})\to(X_{2}\times X_{3},\mu_{2}\times\mu_{3},T_{2}\times
T_{3}).$

Note that the measure on the right-hand side is required to be the product, so
in particular the factor maps $\pi$ and $\xi$ must generate independent sigma-
subalgebras of subsets of $X_{1}$. While Sinai’s factor theorem shows the
existence of Bernoulli factors, it does not say anything about the existence
of direct Bernoulli factors.

In the 1970s, Thouvenot defined a system to have the weak Pinsker property
(WPP) if for every $\epsilon>0$ it is isomorphic to a direct product of a
Bernoulli shift with a system of entropy less than $\epsilon$ [64]. In other
words, a system has the WPP if its entropy is witnessed by direct Bernoulli
factors. Thouvenot asked whether every ergodic transformation has the WPP. The
first author recently proved that this is indeed the case [5]. Moreover, the
statement holds whenever the acting group $\Gamma$ is amenable.

####  1.2 Background: sofic entropy theory

The second author constructed a system without the WPP in the special case
when the group $\Gamma$ is a free group of sufficiently high rank [16]. To
explain, we need to pause for a moment to discuss entropy theory for when the
acting group is not amenable.

An example due to Ornstein and Weiss in [53] suggested it might not be
possible to extend entropy theory to non-amenable groups. However, this
changed with the introduction of sofic entropy theory [11]. The new theory
applies to all sofic groups, which is a class of groups containing amenable
and linear groups, for example. It is unknown whether all countable groups are
sofic. Sofic entropy theory is reviewed in §2.2.

A sofic approximation to a group $\Gamma$ is a sequence $\Sigma$ of partial
actions on finite sets which approximates the action of the group on itself by
left-translations. To be precise, $\Sigma=(\sigma_{n})_{n\in\mathbb{N}}$ where
$\sigma_{n}:\Gamma\to\operatorname{Sym}(V_{n})$, $V_{n}$ are finite sets,
$\operatorname{Sym}(V_{n})$ is the symmetric group on $V_{n}$ and the sequence
is required to satisfy for all $g,h,f\in\Gamma$ such that $f$ is not the
identity,

$\displaystyle 1$ $\displaystyle=$
$\displaystyle\lim_{n\to\infty}|V_{n}|^{-1}|\\{v\in
V_{n}:~{}\sigma_{n}(gh)v=\sigma_{n}(g)\sigma_{n}(h)v\\}|$ $\displaystyle 0$
$\displaystyle=$ $\displaystyle\lim_{n\to\infty}|V_{n}|^{-1}|\\{v\in
V_{n}:~{}\sigma_{n}(f)v=v\\}|.$

A group is called sofic if it admits a sofic approximation. The sofic entropy
of a system $(X,\mu,T)$ (defined in Section 2.2) depends a priori on a choice
of sofic approximation, although for many actions where it has been computed,
it has been shown not to.

Many classical results extend to the sofic setting. For example, the sofic
entropy of a Bernoulli shift action is equal to the Shannon entropy of the
base. Sofic entropy is a measure-conjugacy invariant and so two Bernoulli
shifts with different sofic entropy are not isomorphic. In recent work, Seward
completed the converse direction: for any countable group $\Gamma$, if two
Bernoulli shifts over $\Gamma$ have the same base space Shannon entropy then
they are measurably conjugate [63, 12, 61]. This converse does not depend on
sofic entropy, which might not even be defined.

In a series of works generalizing Krieger’s Theorem [58, 59], Seward
introduced Rokhlin entropy. To define it, suppose we are given an action
$T:\Gamma\to\operatorname{Aut}(X,\mu)$ and a countable measurable partition
$\mathcal{P}$ of $X$. We say the partition is generating if the smallest
sigma-algebra containing it which is also $T(\Gamma)$-invariant is the sigma-
algebra of all measurable sets (up to sets of measure zero). Then Rokhlin
entropy is defined to be the infimum of $H_{\mu}(\mathcal{P})$ over all
generating partitions, where

$H_{\mu}(\mathcal{P})=-\sum_{P\in\mathcal{P}}\mu(P)\log(\mu(P))$

is the Shannon entropy of $(\mathcal{P},\mu)$.

It is immediate that Rokhlin entropy is a measure-conjugacy invariant.
Moreover, it upper bounds sofic entropy. In fact, it is unknown whether
Rokhlin entropy equals sofic entropy whenever the latter is not minus infinity
(which can happen). On the other hand, the only known method for computing a
lower bound to Rokhlin entropy uses sofic entropy. For example, it is unknown
how to compute the Rokhlin entropy of Bernoulli shift actions, except in the
case when $\Gamma$ is assumed to be sofic.

In a different paper [60] Seward generalized Sinai’s factor theorem: every
ergodic system with positive Rokhlin entropy factors onto a Bernoulli shift
with the same entropy.

However, other structural results about classical Kolmogorov–Sinai entropy
break down outside the world of amenable groups. For example, Ornstein and
Weiss’ example shows that sofic entropy can increase under a factor map. In
fact recent work of the second author shows that if $\Gamma$ is an arbitrary
non-amenable group then every Bernoulli shift over $\Gamma$ factors onto every
Bernoulli shift over $\Gamma$ [14]. For example, Bernoulli shifts of small
entropy factor onto Bernoulli shifts of infinite entropy.

Although Bernoulli shifts themselves have been classified, there is no known
substitute for broader ‘Ornstein theory’, which provides necessary and
sufficient conditions for general ergodic processes to be isomorphic to
Bernoulli shifts. Moreover, some specific counterexamples show that the story
must change substantially for some non-amenable groups. For example, when $G$
has property (T), Popa and Sasyk [55] have given simple examples of factors of
Bernoulli shifts that are not isomorphic to Bernoulli shifts.

It is also known that the weak Pinsker property does not hold for all non-
amenable groups and for the main non-amenable notions of entropy. The first
counterexample appeared in [16]. While that counterexample does not have the
WPP, it might still admit some direct Bernoulli factors. In other words, the
system might be measurably conjugate to the direct product of a Bernoulli
shift with another system, but one cannot choose the other system to have
entropy less than $\epsilon$ if $\epsilon>0$ is chosen low enough. In this
work we present a new counterexample which does not admit _any_ nontrivial
Bernoulli factors. Here, a Bernoulli shift
$(\mathtt{K}^{\Gamma},\kappa^{\Gamma},T)$ is said to be trivial if $\kappa$ is
supported on a single point in $\mathtt{K}$. So a trivial Bernoulli shift is
measurably conjugate to the trivial system which consists of $\Gamma$ acting
on a single point.

####  1.3 Main results

Recall from the introduction that $\Gamma$ is the $d$-fold free power of
$\mathbb{Z}_{k}$, $X\subset(\mathbb{Z}_{2})^{\Gamma}$ is a certain closed
“parity check” subgroup and $T:\Gamma\to\operatorname{Aut}(X,m_{X})$ is the
canonical shift action by automorphisms.

######  Theorem A.

Let $k>d\geq 3$. Then there exists a sofic approximation
$\Sigma=(\sigma_{n})_{n}$ to $\Gamma$ such that

$\operatorname{h}_{\Sigma}(X,m_{X},T)=(1-d/k)\log 2$

and along which $(X,m_{X},T)$ has completely positive sofic entropy.

Since sofic entropy is always bounded above by Rokhlin entropy, the last part
of this theorem has the following immediate corollary:

######  Corollary 1.1.

The system $(X,m_{X},T)$ has completely positive Rokhlin entropy.

######  Theorem B.

If $k>d\geq 3$ then the system $(X,m_{X},T)$ has no non-trivial direct
Bernoulli factors.

######  Remark.

Theorems A and B should hold in the more general setting in which
$\Gamma=\Gamma_{1}\ast\cdots\ast\Gamma_{d}$ where each $\Gamma_{i}$ is a group
of order $k$. That is, we do not need to require that each $\Gamma_{i}$ is
cyclic. The proofs are essentially the same.

######  Remark.

The weak Pinsker entropy of a system $(X,\mu,T)$ is defined to be the supremum
of the Shannon entropies $H(\mathtt{K},\kappa)$ over all direct Bernoulli
factors of the form $\Gamma{\curvearrowright}(\mathtt{K},\kappa)^{\Gamma}$.
This concept was introduced in [17]. So Theorem B implies that $(X,m_{X},T)$
has zero weak Pinsker entropy.

Finally, our methods also give the following.

######  Theorem C.

If $k>d\geq 3$ then the system $(X,m_{X},T)$ is not weakly contained in a
Bernoulli system.

For a definition of weak containment of measure-preserving systems, see for
example [18].

Theorems B and C are consequences of the system having totally shattered
microstate spaces along some sofic approximation: see Corollary 5.5.

Together, Theorems A and C show that $(X,m_{X},T)$ has completely positive
sofic entropy along some sofic approximation, hence also completely positive
Rokhlin entropy, but is not weakly contained in a Bernoulli shift. The authors
are not aware of other systems for which both of these properties have been
verified previously.

####  1.4 Probabilistic versions of the main theorems

Both Theorem A and Theorem B will be derived as corollaries of probabilistic
theorems. To explain, we say that a permutation of a set $V$ is $k$-uniform if
it consists entirely of $k$-cycles: that is, its cycle type is $[k^{n/k}]$.
Recall that $\Gamma=\Gamma_{d,k}=\langle s_{1},\dots,s_{d}:\
s_{1}^{k}=\dots=s_{d}^{k}=e\rangle$. A homomorphism
$\sigma:\Gamma\to\operatorname{Sym}(V)$ is $k$-uniform if for each generator
$s_{i}$, the image $\sigma(s_{i})$ is $k$-uniform. Let $\mathbb{P}_{n}$ be the
uniform distribution on the set
$\operatorname{Hom}_{\mathrm{unif}}(\Gamma,\operatorname{Sym}(V_{n}))$ of
$k$-uniform homomorphisms. We will always assume $n$ is chosen so that $k$
divides $n$ (since otherwise there are no $k$-uniform permutations).

We infer the existence of sofic approximations with the desired properties
from the next proposition, which follows immediately from a more precise
estimate in [2, Lemma 3.1].

######  Proposition 1.2.

There are subsets $\Omega_{n}^{\mathrm{sofic}}$ of
$\operatorname{Hom}_{\mathrm{unif}}(\Gamma,\operatorname{Sym}(V_{n}))$ with
${\mathbb{P}_{n}(\Omega_{n}^{\mathrm{sofic}})\to 1}$ and such that
$(\sigma_{n})_{n}$ is a sofic approximation to $\Gamma$ whenever
$\sigma_{n}\in\Omega_{n}^{\mathrm{sofic}}$ for all $n$. ∎

With Proposition 1.2 in hand, Theorem A is a corollary of the following
probabilistic version.

######  Theorem 1.3.

There are subsets $\Omega_{n}^{\prime}\subseteq\Omega_{n}^{\mathrm{sofic}}$
with $\mathbb{P}_{n}(\Omega_{n}^{\prime})\to 1$ and such that, if
$\sigma_{n}\in\Omega_{n}^{\prime}$ for every $n$, then

  * a.

the sofic entropy of $(X,m_{X},T)$ along any subsequence of $(\sigma_{n})_{n}$
equals

$(1-d/k)\log 2;$

  * b.

every nontrivial factor of $(X,m_{X},T)$ has positive sofic entropy along
$(\sigma_{n})_{n}$.

######  Remark.

It is tempting to summarize part (b) of Theorem 1.3 as “$(X,m_{X},T)$ has
completely positive entropy with high probability according to
$\mathbb{P}_{n}$”. But we must be careful, because this summary hides an
important detail about the order of quantifiers. For part (b) of Theorem 1.3,
the high-probability subsets $\Omega_{n}^{\prime}$ are found a priori, and
then _any_ factor of $(X,m_{X},T)$ has positive sofic entropy along _any_
choice of $\sigma_{n}$ from those subsets. One could instead take “completely
positive entropy with high probability” to mean that for every factor of
$(X,m_{X},T)$ there is a sequence of high-probability sets
$\Omega^{\prime}_{n}$ (depending on the factor) within which one sees the
desired positive sofic entropy. The latter conclusion is formally weaker, and
we do not know whether there exist examples of one without the other. Since
the collection of all factors may be uncountable, one cannot use a simple
diagonal argument to prove that these two formulations are equivalent. (If one
identifies factors with their conditional expectation operators, then their
induced strong operator topology is separable, but the semi-continuity
properties of sofic entropy do not obviously combine with approximations in
this topology to enable a more complicated diagonal argument, either.)

Theorem B is also a corollary of a probabilistic assertion about randomly-
chosen $\sigma_{n}$ and the geometry of the space of microstates. We will
prove that the space of microstates shatters in a strong sense, which roughly
speaking means that it splits into a union of exponentially many well-
separated clusters, each of which has sub-exponential size. The precise
definition is given in §5, and the precise statement of the result for the
parity-check subshift is Theorem 6.1(3) formulated in §6.1 below. It was
essentially already known from [16] that this phenomenon is incompatible with
having a direct Bernoulli factor. We give a formal proof of this
incompatibility in §5.

Our focus on the geometry and on shattering is inspired by similar ideas from
statistical physics on random sparse graphs [1]. As far as we know, the term
‘shattering’ first appears in [21]. In other works, this phenomenon is called
dynamical replica symmetry breaking [28, 40].

####  1.5 Outline of the paper

This paper is divided into two parts. In Part I, we consider general symbolic
dynamical systems with a focus on the case in which $\Gamma$ is a free product
of finite cyclic groups.

  * •

Section 2 is a review of sofic group theory and sofic entropy.

  * •

Section 3 introduces Kikuchi entropy and annealed entropy for actions of
$\Gamma_{d,k}$. These entropies generalize the $F$-functional and the
$f$-invariant from [10] and are strongly related to the first moment method in
statistical physics. This is the main tool for proving Theorem 1.3 part (a).

  * •

Section 4 discusses completely positive entropy and a version of uniform
mixing for model spaces that we call ‘property M’. These general notions
provide the background and tools needed to prove Theorem 1.3 part (b).

  * •

Section 5 defines totally shattered microstate spaces and shows how this
property prevents both direct Bernoulli factors and weak containment in a
Bernoulli shift.

Part II focuses on the parity check sub-shifts which appear in the main
theorems:

  * •

Section 6 discusses random (finite) LDPC codes.

  * •

Section 7 proves that for a typical sequence of these codes, the sequence of
uniform measures on the codebooks has property M.

  * •

Section 8 proves that typically these uniform measures converge locally and
empirically to the Haar measure. Since the sequence also has property M, this
gives Theorem 1.3(b) as an application of Theorem 4.3.

  * •

Section 9 proves that the sofic entropy of the Haar measure is $(1-d/k)\log 2$
over most sofic approximations (Theorem 1.3(a)).

  * •

Section 10 proves that the Haar measure typically has totally shattered
microstate spaces (Theorem 6.1(3)). This implies Theorem B (the Haar measure
has no direct Bernoulli factors) via Corollary 5.5(2).

####  1.6 Notational conventions

We use the following standard notation for approximate comparison of
functions. Let $f$ and $g$ be real-valued functions on the same domain $S$,
and let $A$ be any set of additional parameters in specifying these functions.
Then:

  * •

In case $g$ is non-negative, we write $f=O_{A}(g)$ if there is a positive
constant $c$, depending possibly on $A$ but on nothing else, such that
$|f|\leq cg$.

  * •

In case $g$ is non-negative and $S=\mathbb{N}$, we write $f=o_{A}(g)$ if
$g(n)$ is strictly positive for all sufficiently large $n$ and $f(n)/g(n)\to
0$, where this convergence may be bounded by a function that tends to $0$ and
depends only on $A$.

  * •

For any $S$, we write $f\lesssim_{A}g$ or $g\gtrsim_{A}f$ if (i) both
functions are non-negative, and (ii) there is a positive constant $c$,
depending possibly on $A$ but on nothing else, such that $f\leq cg$. Note that
this is similar to writing ‘$f=O_{A}(g)$’, except here it is part of the
assertion that $f$ and $g$ are both non-negative, in case this is not obvious.

Finally, if $(\Omega_{n},\mathbb{P}_{n})$ is a sequence of probability spaces
indexed by $n\in\mathbb{N}$, we write ‘$o_{p}(1)$’ as a placeholder for any
sequence of random variables $X_{n}$ on these spaces such that

$\mathbb{P}_{n}(|X_{n}|>\varepsilon)\to 0\qquad\forall\varepsilon>0.$

So this is essentially an analog of $o(1)$ for convergence in probability.

####  1.7 Acknowledgements

The authors thank Brandon Seward for helpful discussions. The authors (ordered
alphabetically by last name) were supported by NSF grants DMS-1855694,
DMS-2154680 and DMS-1937215 respectively.

For the purpose of open access, the authors have applied a Creative Commons
Attribution (CC-BY) licence to any Author Accepted Manuscript version arising
from this submission.

##  Part I General systems

###  2 Preliminaries

####  2.1 Sofic groups

A sofic approximation to a countable group $\Gamma$ is a sequence
$\Sigma=\\{\sigma_{n}\\}_{n\in\mathbb{N}}$ of maps

$\sigma_{n}:\Gamma\to\operatorname{Sym}(V_{n})$

where $V_{n}$ are finite sets, $\operatorname{Sym}(V_{n})$ is the symmetric
group on $V_{n}$, and the sequence is required to be asymptotically
homomorphic and free in the following sense: For every $g,h\in\Gamma$ we
require that the homomorphism equation
$\sigma_{n}(gh)v=\sigma_{n}(g)\sigma_{n}(h)v$ holds for asymptotically all
$v\in V_{n}$:

$1=\lim_{n\to\infty}|V_{n}|^{-1}|\\{v\in
V_{n}:~{}\sigma_{n}(gh)v=\sigma_{n}(g)\sigma_{n}(h)v\\}|.$

For every non-identity element $g\in\Gamma\setminus\\{1_{\Gamma}\\}$, we
require that the percentage of points fixed by $\sigma_{n}(g)$ tends to zero:

$\displaystyle 0$ $\displaystyle=$
$\displaystyle\lim_{n\to\infty}|V_{n}|^{-1}|\\{v\in
V_{n}:~{}\sigma_{n}(g)v=v\\}|.$

A group $\Gamma$ is sofic if it admits a sofic approximation.

If $\Gamma$ admits a finite generating set $S$ then it is common to visualize
a map $\sigma_{n}$ as above in terms of the graph
$G(\sigma_{n})=(V_{n},E_{n})$ it induces. The edges of this graph are pairs of
the form $\\{v,\sigma_{n}(s)v\\}$ for $s\in S$ and $v\in V_{n}$. Then $\Sigma$
is a sofic approximation precisely when this sequence of graphs
$G(\sigma_{n})$ Benjamini-Schramm converges to the Cayley graph of $\Gamma$
with respect to $S$ [26].

It is an exercise to check that all amenable groups and all residually finite
groups are sofic. Because finitely generated linear groups are sofic and
direct unions of sofic groups are also sofic, it follows that all linear
groups are sofic. It is an open problem whether all countable groups are
sofic.

The class of sofic groups was introduced implicitly by Gromov [34] and
explicitly by Weiss [67]. For further background on sofic groups, see [54,
20].

####  2.2 Sofic entropy

This section defines sofic entropy for subshifts using the formulation from
[13]. See also [15] or [35] for more comprehensive references.

Let $\Gamma$ denote a countable group and let $\mathtt{A}$ be a finite set
(called the alphabet). Let $\mathtt{A}^{\Gamma}$ be the set of all functions
$x:\Gamma\to\mathtt{A}$. We write either $x_{g}$ or $x(g)$ for the value of
$x$ on $g\in\Gamma$, whichever is most convenient. We endow
$\mathtt{A}^{\Gamma}$ with the pointwise convergence topology, under which it
is compact and metrizable.

Let $\operatorname{Prob}(\mathtt{A}^{\Gamma})$ denote the space of all Borel
probability measures on $\mathtt{A}^{\Gamma}$, which we endow with the weak*
topology. In this topology, a sequence of Borel probability measures
$(\mu_{n})_{n\in\mathbb{N}}$ converges to a measure $\mu_{\infty}$ if and only
if for every continuous function $f:\mathtt{A}^{\Gamma}\to\mathbb{R}$,
$\lim_{n\to\infty}\int f~{}\textrm{d}\mu_{n}=\int f~{}\textrm{d}\mu_{\infty}$.
An equivalent characterization uses cylinder sets which are defined as
follows. Given a finite subset $F\subset\Gamma$ and $x:F\to\mathtt{A}$ let
$C(x,F)$ be the set of all functions $y:\Gamma\to\mathtt{A}$ such that
$y(f)=x(f)$ for all $f\in F$. Then $(\mu_{n})_{n\in\mathbb{N}}$ converges to
$\mu_{\infty}$ if and only if for every such $F$ and $x$,
$\lim_{n\to\infty}\mu_{n}(C(x,F))=\mu_{\infty}(C(x,F))$. This is because the
cylinder sets $C(x,F)$ form a sub-basis for the topology on
$\mathtt{A}^{\Gamma}$.

Let $T=(T^{g})_{g\in\Gamma}$ be the shift action on $\mathtt{A}^{\Gamma}$
defined by $T^{g}x(f)=x(g^{-1}f)$ for $x\in\mathtt{A}^{\Gamma}$. This induces
an action on $\operatorname{Prob}(\mathtt{A}^{\Gamma})$ by pushforwards. The
set of all shift-invariant Borel probability measures on $\mathtt{A}^{\Gamma}$
will be denoted $\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma})$. If $\mu$
is a shift-invariant Borel probability measure on $\mathtt{A}^{\Gamma}$ then
the system $(\mathtt{A}^{\Gamma},\mu,T)$ is called a shift $\Gamma$-system. We
define here the sofic entropy of such systems.

Given $\sigma:\Gamma\to\textrm{Sym}(V)$, $v\in V$ and $x:V\to\mathtt{A}$, the
pullback name of $x$ at $v$ is the labeling
$\Pi^{\sigma}_{v}(x)\in\mathtt{A}^{\Gamma}$ defined by

$\Pi^{\sigma}_{v}(x)(g)=x_{\sigma(g^{-1})v}\quad\forall g\in\Gamma.$

For the sake of building some intuition, note that when $\sigma$ is a
homomorphism, the map $v\mapsto\Pi^{\sigma}_{v}(x)$ is $\Gamma$-equivariant
(in the sense that $\Pi^{\sigma}_{\sigma(g)v}(x)=T^{g}\Pi^{\sigma}_{v}(x)$).
In particular $\Pi^{\sigma}_{v}(x)\in\mathtt{A}^{\Gamma}$ is periodic. In
general, we think of $\Pi^{\sigma}_{v}(x)$ as an approximate periodic point.

When $\Gamma$ is generated by a finite subset $S\subset\Gamma$ and we form the
graph $G=G(\sigma)$ as in the previous subsection, if $\sigma$ is a
homomorphism then there is a unique covering space map $\pi$ from the Cayley
graph of $\Gamma$ to the connected component of $G(\sigma)$ containing $v$
which maps the identity to $v$ and maps $s$-labeled edges to $s$-labeled edges
(for $s\in S$). In this case, $\Pi^{\sigma}_{v}(x):\Gamma\to\mathtt{A}$ is the
composition of the covering map with $x$.

The empirical measure of $x:V\to\mathtt{A}$ is

$P^{\sigma}_{x}=|V|^{-1}\sum_{v\in
V}\delta_{\Pi^{\sigma}_{v}(x)}\in\operatorname{Prob}(\mathtt{A}^{\Gamma})$

where, for $y\in\mathtt{A}^{\Gamma}$,
$\delta_{y}\in\operatorname{Prob}(\mathtt{A}^{\Gamma})$ is the Dirac measure
concentrated on $\\{y\\}$. For example, if $\sigma$ is a homomorphism then
$P^{\sigma}_{x}$ is a $\Gamma$-invariant measure supported on the
$\Gamma$-orbits of the pullback names $\Pi^{\sigma}_{v}(x)$.

Given an open set
$\mathcal{O}\subset\operatorname{Prob}(\mathtt{A}^{\Gamma})$, a map
$x:V\to\mathtt{A}$ is called an $(\mathcal{O},\sigma)$-microstate if
$P^{\sigma}_{x}\in\mathcal{O}$. Typically we take $\mathcal{O}$ to be a small
neighborhood of $\mu$, in which case we consider
$(\mathcal{O},\sigma)$-microstates to be ‘good microstates for $\mu$’. Let
$\Omega(\mathcal{O},\sigma)\subset\mathtt{A}^{V}$ denote the set of all
$(\mathcal{O},\sigma)$-microstates.

Let $\mu\in\operatorname{Prob}(\mathtt{A}^{\Gamma})$ be $\Gamma$-invariant and
let $\Sigma=(\sigma_{i}:\Gamma\to\textrm{Sym}(V_{i}))_{i\in\mathbb{N}}$ be a
sofic approximation to $\Gamma$. We say that the system
$(\mathtt{A}^{\Gamma},\mu,T)$ has microstates along $\Sigma$ if for every
neighbourhood $\mathcal{O}$ of $\mu$

$\Omega(\mathcal{O},\sigma_{n})\neq\emptyset\quad\hbox{for all sufficiently
large }n.$

The $\Sigma$-entropy of the action $(\mathtt{A}^{\Gamma},\mu,T)$ is defined by

$h_{\Sigma}(\mathtt{A}^{\Gamma},\mu,T):=\inf_{\mathcal{O}\ni\mu}\limsup_{i\to\infty}|V_{i}|^{-1}\log\lvert\Omega(\mathcal{O},\sigma_{i})\rvert$

where the infimum is over all open neighborhoods of $\mu$ in
$\operatorname{Prob}(\mathtt{A}^{\Gamma})$. This number depends on the action
$(\mathtt{A}^{\Gamma},\mu,T)$ only up to measure conjugacy. If the system does
not have microstates along any subsequence of $\Sigma$ then we declare that
the $\Sigma$-entropy is $-\infty$.

####  2.3 Almost-Lipschitz approximations

With the exception of Lemma 2.2, this section is a summary of relevant results
and definitions from [3].

Let $\phi\colon X^{\Gamma}\to Y$ be a Borel-measurable map, where $X,Y$ are
compact metric spaces. This induces an equivariant map $\phi^{\Gamma}\colon
X^{\Gamma}\to Y^{\Gamma}$ given by

$\phi^{\Gamma}(x)(\gamma)=\phi(\gamma^{-1}\cdot x).$

Given $\mu\in\operatorname{Prob}^{\Gamma}(X^{\Gamma})$, let
$\nu=(\phi^{\Gamma})_{*}\mu$; then $\phi^{\Gamma}$ is a factor map from
$(X^{\Gamma},\mu)$ to $(Y^{\Gamma},\nu)$. If $\mathbf{x}\in X^{V}$ is some
good microstate for $\mu$ over a map
$\sigma\colon\Gamma\to\operatorname{Sym}(V)$, we might attempt to send it to a
good microstate for $\nu$ using the map $\phi^{\sigma}\colon X^{V}\to Y^{V}$
defined by

$\phi^{\sigma}(\mathbf{x})(v)=\phi(\Pi_{v}^{\sigma}\mathbf{x}),$ (2)

since the empirical distribution of $\phi^{\sigma}(\mathbf{x})$ would then be
$\phi^{\Gamma}_{*}P_{\mathbf{x}}^{\sigma}$. Since $P_{\mathbf{x}}^{\sigma}$ is
close to $\mu$, one would hope this would be close to $\nu$. But in general
$\phi^{\Gamma}_{*}$ is not continuous. One way to deal with this is to use
regularizations introduced in [3] called almost-Lipschitz approximations.

If $X,Y$ are metric spaces, a map $\psi\colon X\to Y$ is called $\eta$-almost
$L$-Lipschitz if for every $x_{1},x_{2}\in X$ we have

$\textrm{d}_{Y}(\psi(x_{1}),\,\psi(x_{2}))\leq\eta+L\,\textrm{d}_{X}(x_{1},\,x_{2}).$

If we do not want to specify a particular $L$, we can call the map
$\eta$-almost Lipschitz.

If $\phi\colon X^{\Gamma}\to Y$ is a measurable map and
$\mu\in\operatorname{Prob}(\mathtt{A}^{\Gamma})$, then we call $\psi\colon
X^{\Gamma}\to Y$ an $\eta$-almost Lipschitz (or $\eta$-AL) approximation to
$\phi$ rel $\mu$ if it has the following three properties [3, Def 4.2]:

  1. (i)

The map $\psi$ approximates $\phi$ in the sense that
$\int_{X}\textrm{d}_{Y}(\psi(x),\phi(x))\,\mu(dx)<\eta$

  2. (ii)

there is some finite $D\subset\Gamma$ such that $\psi$ is $D$-local (that is,
$\psi(x_{1})=\psi(x_{2})$ whenever $x_{1}$ and $x_{2}$ agree on $D$)

  3. (iii)

There is some $D$-local open set $U\subset X^{\Gamma}$ such that
$\mu(U)>1-\eta$ and the restriction $\psi|U$ is $\eta$-almost Lipschitz, where
we consider the domain to be $X^{D}$ with the normalized Hamming metric

$\textrm{d}_{X}^{(D)}(x_{1},\,x_{2})=\frac{1}{\lvert D\rvert}\sum_{\gamma\in
D}\textrm{d}_{X}(x_{1}(\gamma),\,x_{2}(\gamma)).$

Here we say that $U$ is $D$-local if its characteristic function is $D$-local.

We often drop the phrase “rel $\mu$” if the measure is unambiguous.

One example of the induced maps on microstate spaces inheriting regularity is
given by the following lemma.

######  Lemma 2.1.

Suppose $\mathtt{A},\mathtt{B}$ are finite sets,
$\phi\colon\mathtt{A}^{\Gamma}\to\mathtt{B}$ is $D$-local, and
$\sigma\colon\Gamma\to\operatorname{Sym}(V)$. Then
$\phi^{\sigma}\colon\mathtt{A}^{V}\to\mathtt{B}^{V}$ is $\lvert
D\rvert$-Lipschitz with respect to the normalized Hamming metrics.

###### Proof.

Since $\phi$ is $D$-local, for every $\mathbf{x},\mathbf{y}\in\mathtt{A}^{V}$

$\displaystyle\textrm{d}^{(V)}(\phi^{\sigma}(\mathbf{x}),\phi^{\sigma}(\mathbf{y}))$
$\displaystyle=\frac{1}{\lvert V\rvert}\sum_{v\in
V}\mathbf{1}\\{\phi(\Pi_{v}^{\sigma}\mathbf{x})\neq\phi(\Pi_{v}^{\sigma}\mathbf{y})\\}$
$\displaystyle\leq\frac{1}{\lvert V\rvert}\sum_{v\in
V}\mathbf{1}\\{\exists\gamma\in
D\,:\,(\Pi_{v}^{\sigma}\mathbf{x})_{\gamma}\neq(\Pi_{v}^{\sigma}\mathbf{y})_{\gamma}\\}$
$\displaystyle=\frac{1}{\lvert V\rvert}\sum_{v\in
V}\mathbf{1}\\{\exists\gamma\in
D\,:\,\mathbf{x}(\sigma(\gamma)v)\neq\mathbf{y}(\sigma(\gamma)v)\\}$

We can then apply a union bound to the indicator function to get

$\displaystyle\textrm{d}^{(V)}(\phi^{\sigma}(\mathbf{x}),\,\phi^{\sigma}(\mathbf{y}))$
$\displaystyle\leq\frac{1}{\lvert V\rvert}\sum_{v\in V}\sum_{\gamma\in
D}\mathbf{1}\\{\mathbf{x}(\sigma(\gamma)v)\neq\mathbf{y}(\sigma(\gamma)v)\\}.$

Since each $\sigma(\gamma)$ is a permutation, the right-hand side is equal to
$\lvert D\rvert\cdot\textrm{d}^{(V)}(\mathbf{x},\mathbf{y})$. ∎

A sequence of maps $(\psi_{n})_{n}$ is called an AL approximation sequence to
$\phi$ if each $\psi_{n}$ is an $\eta_{n}$-AL approximation to $\phi$ for some
sequence $(\eta_{n})_{n}$ decreasing to zero.

The action of AL approximations on microstate spaces, defined as in Equation
(2), is well-behaved. Informally, if $\psi$ is an AL approximation to $\phi$
rel $\mu$, then

  1. 1.

The restriction of $\psi^{\sigma}$ to a set of good microstates for $\mu$ is
an almost-Lipschitz map [3, Lemma 4.9]; and

  2. 2.

$\psi^{\sigma}$ sends good microstates for $\mu$ to good microstates for
$\phi^{\Gamma}_{*}\mu$ [3, Lemma 4.10].

Below, we will also use the following lemma regarding compositions of AL
approximations:

######  Lemma 2.2.

Suppose $\phi_{1}\colon\mathtt{A}^{\Gamma}\to Y$ and $\phi_{2}\colon
Y^{\Gamma}\to Z$ are measurable maps, where $\mathtt{A}$ is a finite alphabet
(with the discrete metric) and $Y,Z$ are compact metric spaces. Let
$\mu\in\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma})$ and let
$\nu=(\phi_{1}^{\Gamma})_{*}\mu\in\operatorname{Prob}^{\Gamma}(Y^{\Gamma})$.

Suppose $\psi_{2}$ is an $\eta_{2}$-AL approximation to $\phi_{2}$ rel $\nu$
for some $\eta_{2}>0$. Then there is an $\eta_{1}>0$ such that if $\psi_{1}$
is an $\eta_{1}$-AL approximation to $\phi_{1}$ rel $\mu$ then
$\psi_{2}\circ\psi_{1}^{\Gamma}$ is a $(5\eta_{2})$-AL approximation to
$\phi_{2}\circ\phi_{1}^{\Gamma}$ rel $\mu$.

We use discreteness of $\mathtt{A}$ to ensure that a particular local set is
automatically open, as required by the definition of AL approximation. There
may be a way around this, or a suitable substitute for this result, if
$\mathtt{A}$ is an arbitrary compact set.

Lemma 5.4 of [16] is an analogous result for a similar kind of regularization
called a uniformly continuous approximation.

###### Proof.

Assume for convenience that metric spaces have diameter at most one.

We first note that the locality property (ii) is satisfied for the composition
of any pair $(\psi_{1},\psi_{2})$ of AL approximations.

For property (i), we bound the integral as follows:

$\int\textrm{d}_{Z}\big{(}\phi_{2}\circ\phi_{1}^{\Gamma}(x),\
\psi_{2}\circ\psi_{1}^{\Gamma}(x)\big{)}\
\mu(dx)\leq\int\textrm{d}_{Z}\big{(}\phi_{2}\circ\phi_{1}^{\Gamma}(x),\
\psi_{2}\circ\phi_{1}^{\Gamma}(x)\big{)}\ \mu(dx)\\\
+\int\textrm{d}_{Z}\big{(}\psi_{2}\circ\phi_{1}^{\Gamma}(x),\
\psi_{2}\circ\psi_{1}^{\Gamma}(x)\big{)}\ \mu(dx).$

The first integral on the right is bounded by

$\int\textrm{d}_{Z}\big{(}\phi_{2}\circ\phi_{1}^{\Gamma}(x),\
\psi_{2}\circ\phi_{1}^{\Gamma}(x)\big{)}\
\mu(dx)=\int\textrm{d}_{Z}\big{(}\phi_{2}(y),\ \psi_{2}(y)\big{)}\
\nu(dy)\leq\eta_{2}.$

The second integral we break further into pieces: let $U_{2}$ be a open
$D_{2}$-local set such that $\nu(U_{2})>1-\eta_{2}$ and the restriction of
$\psi_{2}$ to $Y^{D_{2}}$ is $\eta_{2}$-almost $L_{2}$-Lipschitz from
$(Y^{D_{2}},\textrm{d}_{Y}^{(D_{2})})$ to $(Z,\textrm{d}_{Z})$, where
$\textrm{d}_{Y}^{(D_{2})}$ is the normalized Hamming metric

$\textrm{d}_{Y}^{(D_{2})}(y_{1},y_{2})=\frac{1}{\lvert D_{2}\rvert}\sum_{g\in
D_{2}}\textrm{d}_{Y}(y_{1}(g),\,y_{2}(g)).$

Let $V=(\psi_{1}^{\Gamma})^{-1}U_{2}\cap(\phi_{1}^{\Gamma})^{-1}U_{2}$. Since
$U_{2}$ is open and $\nu(U_{2})>1-\eta_{2}$,

$\mathcal{N}=\\{\theta\in\operatorname{Prob}(Y^{\Gamma})\,:\,\theta(U_{2})>1-\eta_{2}\\}$

is an open neighborhood of $\nu$, and if $\eta_{1}$ is small enough then every
$\eta_{1}$-AL approximation $\psi_{1}$ to $\phi_{1}$ satisfies
$(\psi_{1}^{\Gamma})_{*}\mu\in\mathcal{N}$. So

$\displaystyle\mu(V^{c})$
$\displaystyle\leq(1-\mu((\psi_{1}^{\Gamma})^{-1}U_{2}))+(1-\mu((\phi_{1}^{\Gamma})^{-1}U_{2}))$
$\displaystyle=(1-(\psi_{1}^{\Gamma})_{*}\mu(U_{2}))+(1-(\phi_{1}^{\Gamma})_{*}\mu(U_{2}))$
$\displaystyle\leq 2\eta_{2},$

and therefore (using that $Z$ has diameter at most 1)

$\displaystyle\int\textrm{d}_{Z}\big{(}\psi_{2}\circ\phi_{1}^{\Gamma}(x),\
\psi_{2}\circ\psi_{1}^{\Gamma}(x)\big{)}\ \mu(dx)$
$\displaystyle\leq\int_{V}(\cdots)\,\mu(dx)+\int_{V^{c}}(\cdots)\,\mu(dx)$
$\displaystyle\leq\int_{V}\left(\eta_{2}+L_{2}\,\textrm{d}_{Y}^{(D_{2})}(\phi_{1}^{\Gamma}(x),\,\psi_{1}^{\Gamma}(x))\right)\mu(dx)+2\eta_{2}$
$\displaystyle\leq 3\eta_{2}+L_{2}\eta_{1}.$

So if we also require $\eta_{1}<\eta_{2}/L_{2}$ then we get the overall bound
$5\eta_{2}$.

Let $U_{2},D_{2},L_{2}$ be as above. In addition to the assumptions made above
on $\eta_{1}$, assume that $\eta_{1}<4\eta_{2}/\lvert D_{2}\rvert$. We will
show that property (iii) holds if $\psi_{1}$ is an $\eta_{1}$-AL
approximation. Analogous to $U_{2}$, let $U_{1}$ be an open $D_{1}$-local
subset of $\mathtt{A}^{\Gamma}$ such that $\mu(U_{1})>1-\eta_{1}$ and the
restriction of $\psi_{1}$ to $U_{1}$ is $\eta_{1}$-almost $L_{1}$-Lipschitz.

Let $U=(\psi_{1}^{\Gamma})^{-1}U_{2}\cap\bigcap_{g\in D_{2}}g\cdot U_{1}$.
Since $(\psi_{1}^{\Gamma})_{*}\mu\in\mathcal{N}$ as above,
$\mu\big{(}(\psi_{1}^{\Gamma})^{-1}U_{2}\big{)}>1-\eta_{2}$, and since $\mu$
is shift-invariant, $\mu(g\cdot U_{1})>1-\eta_{1}$. Hence

$\mu(U)>1-\eta_{2}-\lvert D_{2}\rvert\eta_{1}>1-5\eta_{2}.$

Now $U\subset\mathtt{A}^{\Gamma}$ is a local set, since $U_{1},U_{2},\psi_{1}$
are local. Since $\mathtt{A}$ is discrete this automatically implies $U$ is
open. It remains only to show that the restriction of
$\psi_{2}\circ\psi_{1}^{\Gamma}$ to $U$ is $(5\eta)$-almost Lipschitz. If
$x_{1},x_{2}\in U$ then first of all
$\psi_{1}^{\Gamma}(x_{1}),\psi_{1}^{\Gamma}(x_{2})\in U_{2}$, so

$\textrm{d}_{Z}(\psi_{2}\circ\psi_{1}^{\Gamma}(x_{1}),\,\psi_{2}\circ\psi_{1}^{\Gamma}(x_{2}))\leq\eta_{2}+L_{2}\,\textrm{d}_{Y}^{(D_{2})}\big{(}\psi_{1}^{\Gamma}(x_{1}),\,\psi_{1}^{\Gamma}(x_{2})\big{)},$

and moreover for every $g\in D_{2}$ we have $g^{-1}\cdot x_{1},g^{-1}\cdot
x_{2}\in U_{1}$, so

$\displaystyle\textrm{d}_{Y}^{(D_{2})}\big{(}\psi_{1}^{\Gamma}(x_{1}),\,\psi_{1}^{\Gamma}(x_{2})\big{)}$
$\displaystyle=\frac{1}{\lvert D_{2}\rvert}\sum_{g\in
D_{2}}\textrm{d}_{Y}(\psi_{1}(g^{-1}\cdot x_{1}),\,\psi_{1}(g^{-1}\cdot
x_{2}))$ $\displaystyle\leq\frac{1}{\lvert D_{2}\rvert}\sum_{g\in
D_{2}}(\eta_{1}+L_{1}\,\textrm{d}^{(D_{1})}_{X}(g^{-1}\cdot
x_{1},\,g^{-1}\cdot x_{2})).$

Expanding the definition of the normalized Hamming metric,

$\displaystyle\frac{1}{\lvert D_{2}\rvert}\sum_{g\in
D_{2}}\textrm{d}^{(D_{1})}_{X}(g^{-1}\cdot x_{1},\,g^{-1}\cdot x_{2})$
$\displaystyle=\frac{1}{\lvert D_{2}\rvert}\sum_{g_{2}\in
D_{2}}\frac{1}{\lvert D_{1}\rvert}\sum_{g_{1}\in
D_{1}}\textrm{d}_{X}([g_{2}^{-1}\cdot x_{1}](g_{1}),\,[g_{2}^{-1}\cdot
x_{2}](g_{1}))$ $\displaystyle=\frac{1}{\lvert D_{1}\rvert\lvert
D_{2}\rvert}\sum_{(g_{1},g_{2})\in D_{1}\times
D_{2}}\textrm{d}_{X}(x_{1}(g_{2}g_{1}),\,x_{2}(g_{2}g_{1}))$
$\displaystyle\leq\textrm{d}^{(D_{2}D_{1})}_{X}(x_{1},x_{2})\cdot C$

where $C=\max_{g\in D_{2}D_{1}}\left(\frac{\lvert D_{1}D_{2}\rvert}{\lvert
D_{1}\rvert\lvert D_{2}\rvert}\,\lvert\\{(g_{1},g_{2})\in D_{1}\times
D_{2}\,:\,g=g_{2}g_{1}\\}\rvert\right)$. So the composition restricted to $U$
is $(\eta_{2}+L_{2}\eta_{1})$-almost $(CL_{1}L_{2})$-Lipschitz, and in
particular $(5\eta_{2})$-almost Lipschitz as required. ∎

###  3 Bethe–Kikuchi entropy and annealed calculations

Throughout this section, we set
$\Gamma=\Gamma_{d,k}=\mathbb{Z}_{k}\ast\dots\ast\mathbb{Z}_{k}$ equal to the
free product of $d$ copies of $\mathbb{Z}_{k}=\mathbb{Z}/k\mathbb{Z}$.

The proof of Theorem A part (a) (and its probabilistic version Theorem 1.3)
relies on a first moment calculation. These kinds of computations have a long
and interesting history in statistical physics and more recently appeared in
the entropy theory of actions of the free group, where, for example, they were
used to answer a long-standing open problem on the classification of Bernoulli
shifts over free groups [10]. This history is reviewed in §3.3.

In the next section, we introduce the uniformly random sofic approximation to
$\Gamma$. This will be our main focus and we will only obtain results about
deterministic sofic approximations indirectly as a consequence of the analysis
of these random ones.

In Section 3.2, we introduce Kikuchi entropy, which has historical roots in
physics [37] and is a version of the functional $F$ of [10] adapted from the
free group to groups $\Gamma$ which are free products of finite groups. This
entropy is a first approximation to the annealed entropy which in recent
ergodic-theory research was called the $f$-invariant [10]. These entropies are
key ingredients for proving Theorem 1.3 part (a).

####  3.1 Random sofic approximations

Instead of directly constructing sofic approximation sequences
$\sigma_{n}:\Gamma\to\operatorname{Sym}(V_{n})$, we will construct probability
measures on the space of homomorphisms from $\Gamma$ to
$\operatorname{Sym}(kn)$. These measures were used for the same purpose in
[2].

Let $V$ be a finite set whose size is divisible by $k$. Let us say that a
permutation of $V$ is $k$-uniform if it consists entirely of $k$-cycles: that
is, its cycle type is $[k^{n/k}]$. Consider a $d$-tuple of $k$-uniform
permutations $(\sigma(s_{1}),\dots,\sigma(s_{d}))$. Then $\sigma(s_{i}^{k})$
equals the identity permutation for each $i$, and so the tuple
$(\sigma(s_{i}),\dots,\sigma(s_{d}))$ is the image of the generators
$(s_{1},\dots,s_{d})$ under a homomorphism
$\sigma:\Gamma\to\operatorname{Sym}(V)$. We call such a homomorphism
$k$-uniform if the images of these generators are all $k$-uniform
permutations. Denote the set of $k$-uniform homomorphisms into
$\operatorname{Sym}(V)$ by
$\operatorname{Hom}_{\mathrm{unif}}(\Gamma,\operatorname{Sym}(V))$. Note that
for arbitrary members of $\operatorname{Hom}(\Gamma,\operatorname{Sym}(V))$
the cycle sizes of the images of the generators of $\Gamma$ must be factors of
$k$.

Given a homomorphism
$\sigma\in\operatorname{Hom}_{\mathrm{unif}}(\Gamma,\operatorname{Sym}(V))$,
consider the collection of all the orbits of the individual maps
$\sigma_{i}=\sigma(s_{i})$: that is, all the subsets of the form

$\\{\sigma(s_{i}^{j})(v)\,:\,0\leq j<k\\}$ (3)

for $v\in V$ and $i\in[d]$. Taken together, these may be regarded as a hyper-
graph on $V$. Because we consider a $k$-uniform homomorphism, this hyper-graph
is $k$-uniform in the usual sense in combinatorics: this is the origin of the
terminology. However, it could happen that two $\sigma_{i}$ and $\sigma_{j}$
give some vertex the same orbit. In this eventuality it is better to think of
the family of sets (3) as a _multi-hyper-graph_ , in that we count each hyper-
edge with this multiplicity.

For each $n$, we set $V_{n}:=\\{1,2,\dots,n\\}$. If $k$ divides $n$, then we
let $\mathbb{P}_{n}$ be the uniform distribution on
$\operatorname{Hom}_{\mathrm{unif}}(\Gamma,\operatorname{Sym}(V_{n}))$. The
sofic approximations that appear in Theorem A are obtained at random from
these distributions, and shown to have all the desired properties with high
probability.

In order to take this approach, Proposition 1.2 above is a basic prerequisite.
It allows us to focus on typical properties of the microstate spaces, knowing
that random homomorphisms will be good sofic approximation maps with high
probability. It is implied by the more precise estimate in [2, Lemma 3.1],
where our $\mathbb{P}_{n}$ is called ‘$\mathbb{P}_{n}^{u}$’. Note that
attention is restricted to even $n$ in that reference, but that restriction is
unnecessary for the case of $\mathbb{P}_{n}^{u}$; it is included there only
for the sake of the other probability distribution $\mathbb{P}_{n}^{p}$ that
is covered by the same lemma.

####  3.2 Formula for Kikuchi entropy

Let $\mathtt{A}$ be a finite set and $\Gamma=(\mathbb{Z}_{k})^{\ast d}$ as
above. Given a $\Gamma$-invariant measure
$\mu\in\operatorname{Prob}(\mathtt{A}^{\Gamma})$, we define the edge weight
$W_{\mu}(\cdot;\cdot)\colon\mathtt{A}^{\mathbb{Z}_{k}}\times[d]\to[0,1]$ by

$W_{\mu}(\mathbf{a};i)=\mu\\{\mathbf{x}\in\mathtt{A}^{\Gamma}\,:\,\mathbf{x}(s_{i}^{j})=\mathbf{a}(j)\
\forall 0\leq j<k\\}.$

Each $W(\cdot;i)$ is a probability measure on $\mathtt{A}^{\mathbb{Z}_{k}}$
which records the statistics of $\mu$ on the hyper-edge
$\\{s_{i},s_{i}^{2},\ldots,s_{i}^{d-1}\\}$. Also define the vertex weight

$W_{\mu}(\mathtt{a})=\mu\\{\mathbf{x}\in\mathtt{A}^{\Gamma}\,:\,\mathbf{x}(e)=\mathtt{a}\\}$

for $\mathtt{a}\in\mathtt{A}$. This probability measure on $\mathtt{A}$
records the single-site statistics of $\mu$. It is determined by the edge
weight $W_{\mu}(\cdot;\cdot)$.

More generally, an abstract weight $W$ is a $d$-tuple of probability vectors
$W(\cdot;1),\ldots,W(\cdot;d)$ on $\mathtt{A}^{\mathbb{Z}_{k}}$ such that
there is a probability vector $W(\cdot)$ on $\mathtt{A}$ satisfying the
consistency condition

$W(\mathtt{a}_{0})=\sum_{\mathbf{a}\in\mathtt{A}^{\mathbb{Z}_{k}}\,:\,\mathbf{a}(j)=\mathtt{a}_{0}}W(\mathbf{a};i)$

for every $i\in[d]$, $j\in\mathbb{Z}_{k}$ and $\mathtt{a}_{0}\in\mathtt{A}$.

For any weight $W$, we define the Kikuchi entropy of $W$ by

$\mathrm{H_{K}}(W):=(1-d)\operatorname{H}(W(\cdot))+\frac{1}{k}\sum_{i\in[d]}\operatorname{H}(W(\cdot;i)),$

where $\operatorname{H}(\cdot)$ denotes Shannon entropy, and for a
$\Gamma$-invariant measure $\mu$ on $\mathtt{A}^{\Gamma}$ we abbreviate
$\mathrm{H_{K}}(W_{\mu})$ to $\mathrm{H_{K}}(\mu)$. The functional
$\mathrm{H_{K}}$ appears in our work because it gives the upper exponential
growth rate of the expected number of microstates whose averaged hyper-edge
marginals are approximately specified by $\mu$. This is an analog of [9,
Theorem 1.4]. Given a microstate $\mathbf{x}\in\mathtt{A}^{V}$ and
$\sigma\in\operatorname{Hom}(\Gamma,\operatorname{Sym}(V))$, let
$W_{\mathbf{x},\sigma}$ be the weight corresponding to
$P_{\mathbf{x}}^{\sigma}\in\operatorname{Prob}(\mathtt{A}^{\Gamma})$, the
empirical distribution of $\mathbf{x}$ over $\sigma$. Also, given two weights
$W,W^{\prime}$, let

$\|W-W^{\prime}\|:=\max_{1\leq i\leq
d}\max_{\mathbf{a}\in\mathtt{A}^{\mathbb{Z}_{k}}}|W(\mathbf{a};i)-W^{\prime}(\mathbf{a};i)|.$

######  Proposition 3.1.

We have

$\mathrm{H_{K}}(\mu)=\lim_{\varepsilon\to
0}\limsup_{n\to\infty}\frac{1}{nk}\log\operatorname*{\mathbb{E}}_{\sigma_{n}\sim\mathbb{P}_{nk}}\left\lvert\\{\mathbf{x}\in\mathtt{A}^{nk}\,:\,\|W_{\mathbf{x},\sigma_{n}}-W_{\mu}\|<\varepsilon\\}\right\rvert.$

The proof of this proposition shows that we also obtain $\mathrm{H_{K}}(\mu)$
if $\limsup$ is replaced with $\liminf$ on the right-hand side.

###### Proof.

Let $\mathbb{Z}_{k}$ act on $\mathtt{A}^{\mathbb{Z}_{k}}$ in the usual way:
$\pi\mathbf{a}(j)=\mathbf{a}(j-\pi)$ for $\pi\in\mathbb{Z}_{k}$,
$\mathbf{a}\in\mathtt{A}^{\mathbb{Z}_{k}}$ and $j\in\mathbb{Z}_{k}$. We will
say that two elements $\mathbf{a},\mathbf{b}\in\mathtt{A}^{\mathbb{Z}_{k}}$
are equivalent if they are in the same $\mathbb{Z}_{k}$-orbit. Let
$[\mathbf{a}]\subset\mathtt{A}^{\mathbb{Z}_{k}}$ denote the equivalence class
of $\mathbf{a}$. For a weight $W$ write

$W([\mathbf{a}];i)\coloneqq\sum_{\mathbf{b}\in[\mathbf{a}]}W(\mathbf{b};i).$

A weight $W$ is cyclically invariant if $W(\mathbf{a};i)=W(\mathbf{b};i)$ for
every equivalent pair $\mathbf{a},\mathbf{b}$ in
$\mathtt{A}^{\mathbb{Z}_{k}}$. For example, since $\mu$ is $\Gamma$-invariant,
for each $i\in[d]$ the probability measure
$W_{\mu}(\cdot;i)\in\operatorname{Prob}(\mathtt{A}^{\mathbb{Z}_{k}})$ is
cyclically invariant.

We first calculate
$\operatorname*{\mathbb{E}}\left\lvert\\{\mathbf{x}\in\mathtt{A}^{kn}\,:\,W_{\mathbf{x},\sigma_{n}}=W\\}\right\rvert$
for an arbitrary cyclically invariant weight $W$ with denominator $kn$, _i.e._
such that $kn\cdot W([\mathbf{a}];i)\in\mathbb{Z}$ for each $i,\mathbf{a}$.
Letting

$N_{n}=\left\lvert\operatorname{Hom}_{\mathrm{unif}}(\Gamma,\operatorname{Sym}(kn))\right\rvert=\left(\frac{(kn)!}{n!k^{n}}\right)^{d},$

we have

$\displaystyle\operatorname*{\mathbb{E}}\left\lvert\\{\mathbf{x}\in\mathtt{A}^{kn}\,:\,W_{\mathbf{x},\sigma_{n}}=W\\}\right\rvert$
$\displaystyle=\frac{1}{N_{n}}\sum_{\sigma\in\operatorname{Hom}_{\mathrm{unif}}(\Gamma,\operatorname{Sym}(kn))}\left\lvert\\{\mathbf{x}\in\mathtt{A}^{kn}\,:\,W_{\mathbf{x},\sigma}=W\\}\right\rvert$
$\displaystyle=\frac{1}{N_{n}}\sum_{\mathbf{x}\in\mathtt{A}^{kn}}\left\lvert\\{\sigma\in\operatorname{Hom}_{\mathrm{unif}}(\Gamma,\operatorname{Sym}(kn))\,:\,W_{\mathbf{x},\sigma}=W\\}\right\rvert.$

Now a labeling $\mathbf{x}\in\mathtt{A}^{kn}$ admits at least one $\sigma$
that gives the correct weight $W$ if and only if it has the correct “vertex
statistics,” that is,
$\frac{1}{kn}\left\lvert\\{i\in[kn]\,:\,\mathbf{x}(i)=\mathtt{a}\\}\right\rvert=W(\mathtt{a})$
for all $\mathtt{a}\in\mathtt{A}$. There are
$\exp\\{kn(\operatorname{H}(W(\cdot))+o(1))\\}$ such $\mathbf{x}$, and each
admits the same number of $\sigma$. From now on fix one such $\mathbf{x}$.

For $i\in[d]$, let $G_{i}$ be the set of $k$-uniform permutations
$\pi\in\operatorname{Sym}(kn)$ such that if $W(\cdot;\pi)$ is the probability
vector on $\mathtt{A}^{\mathbb{Z}_{k}}$ given by

$W(\mathbf{a};\pi)=(kn)^{-1}|\\{v\in[kn]:~{}\mathbf{a}(t)=\mathbf{x}(\pi^{t}(v))~{}\forall
0\leq t<k\\}|$

then $W(\cdot;\pi)\equiv W(\cdot;i)$. Any $k$-uniform homomorphism $\sigma$
with $W_{\mathbf{x},\sigma}=W$ is determined by the permutations
$\sigma(s_{i})$ which must be in $G_{i}$. So the number of such homomorphisms
is $\prod_{i=1}^{d}|G_{i}|$.

Let $G(\mathbf{x})$ be the set of permutations $g\in\operatorname{Sym}(kn)$
which fix $\mathbf{x}$ in the sense that $\mathbf{x}(v)=\mathbf{x}(gv)$ for
all $v\in[kn]$. Observe that $G(\mathbf{x})$ acts on $G_{i}$ by conjugation.
This means that if $\pi_{i}$ is a fixed permutation in $G_{i}$ and $g\in
G(\mathbf{x})$ then $g\pi_{i}g^{-1}\in G_{i}$. Moreover, this action is
transitive. So

$|G_{i}|=\frac{|G(\mathbf{x})|}{|\textrm{Stab}(\pi_{i})|}$

where $\textrm{Stab}(\pi_{i})$ is the set of $g\in G(\mathbf{x})$ with
$g\pi_{i}g^{-1}=\pi_{i}$. Observe

$|G(\mathbf{x})|=\prod_{\mathtt{a}\in\mathtt{A}}\left(kn\cdot
W(\mathtt{a})\right)!.$

There are two mechanisms by which a $g\in G(\mathbf{x})$ can stabilize
$\pi_{i}$. Either $g$ can permute $k$-cycles with the same labels or it can
rotate a given labeled $k$-cycle. Therefore,

$|\textrm{Stab}(\pi_{i})|=\prod_{[\mathbf{a}]\in\mathtt{A}^{\mathbb{Z}_{k}}/\mathbb{Z}_{k}}\left(n\cdot
W([\mathbf{a}];i)\right)!\left(\frac{k}{\lvert[\mathbf{a}]\rvert}\right)^{n\cdot
W([\mathbf{a}];i)}.$

Putting everything together, we get

$\operatorname*{\mathbb{E}}\left\lvert\\{\mathbf{x}\in\mathtt{A}^{kn}\,:\,W_{\mathbf{x},\sigma_{n}}=W\\}\right\rvert=\frac{e^{kn(\operatorname{H}(W(\cdot))+o(n))}\left(n!k^{n}\prod_{\mathtt{a}\in\mathtt{A}}\left(kn\cdot
W(\mathtt{a})\right)!\right)^{d}}{(kn)!^{d}\prod_{i\in[d]}\prod_{[\mathbf{a}]\in\mathtt{A}^{\mathbb{Z}_{k}}/\mathbb{Z}_{k}}\left(n\cdot
W([\mathbf{a}];i)\right)!\left(\frac{k}{\lvert[\mathbf{a}]\rvert}\right)^{n\cdot
W([\mathbf{a}];i)}}.$

Applying Stirling’s approximation $\log n!=n\log n-n+o(n)$, the logarithm of
this is

$kn\left(\operatorname{H}(W(\cdot))+d\sum_{\mathtt{a}\in\mathtt{A}}W(\mathtt{a})\log
W(\mathtt{a})-\frac{1}{k}\sum_{i\in[d]}\sum_{[\mathbf{a}]}W([\mathbf{a}];i)\log\frac{W([\mathbf{a}];i)}{\lvert[\mathbf{a}]\rvert}\right)+o(n).$

By cyclic invariance of each $W(\cdot;i)$, we have
$W(\mathbf{a};i)=\frac{W([\mathbf{a}];i)}{\lvert[\mathbf{a}]\rvert}$, so this
gives

$\operatorname*{\mathbb{E}}\left\lvert\\{\mathbf{x}\in\mathtt{A}^{kn}\,:\,W_{\mathbf{x},\sigma_{n}}=W\\}\right\rvert=e^{nkF(W)+o(n)}$

where

$F(W)\coloneqq(1-d)\operatorname{H}(W(\cdot))+\frac{1}{k}\sum_{i\in[d]}\operatorname{H}(W(\cdot;i)).$

Now, since the number of denominator-$n$ weights $W$ grows polynomially in
$n$, it follows that for any $\varepsilon>0$

$\lim_{n\to\infty}\frac{1}{kn}\log\operatorname*{\mathbb{E}}\left\lvert\\{\mathbf{x}\in\mathtt{A}^{kn}\,:\,\|W_{\mathbf{x},\sigma_{n}}-W_{\mu}\|<\varepsilon\\}\right\rvert=\sup\\{F(W)\,:\,\|W-W_{\mu}\|<\varepsilon\\}$

and taking $\varepsilon$ to 0 gives the claimed formula, by continuity of $F$.
∎

The annealed entropy of $\mu$ is defined by

$\mathrm{h_{ann}}(\mu)=\inf_{\mathcal{O}\ni\mu}\limsup_{n\to\infty}\frac{1}{nk}\log\operatorname*{\mathbb{E}}_{\sigma_{n}\sim\mathbb{P}_{nk}}\left\lvert\Omega(\sigma_{n},\mathcal{O})\right\rvert$

where the infimum is over all open neighborhoods of $\mu$.

To emphasize the relationship between $\mathrm{H_{K}}(\mu)$ and
$\mathrm{h_{ann}}(\mu)$, let

$\mathcal{O}_{\epsilon}(\mu)=\\{\nu\in\operatorname{Prob}(\mathtt{A}^{\Gamma}):~{}\|W_{\nu}-W_{\mu}\|<\epsilon\\}.$

Then $\mathcal{O}_{\epsilon}(\mu)$ is an open neighborhood of $\mu$ and
Proposition 3.1 becomes

$\mathrm{H_{K}}(\mu)=\inf_{\epsilon>0}\limsup_{n\to\infty}\frac{1}{nk}\log\operatorname*{\mathbb{E}}_{\sigma_{n}\sim\mathbb{P}_{nk}}\left\lvert\Omega(\sigma_{n},\mathcal{O}_{\epsilon}(\mu))\right\rvert.$

In particular $\mathrm{h_{ann}}(\mu)\leq\mathrm{H_{K}}(\mu)$.

The next proposition shows that $\mathrm{H_{K}}(\mu)$ is an upper bound for
sofic entropy with respect to “most” sofic approximations.

######  Proposition 3.2.

Let $\mu$ be a $\Gamma$-invariant Borel probability measure on
$\mathtt{A}^{\Gamma}$. Then there are subsets
$\Omega_{n}^{\prime}\subseteq\Omega_{n}^{\mathrm{sofic}}$ with

$\lim_{n\to\infty}\mathbb{P}_{n}(\Omega_{n}^{\prime})=1$

and such that, if $\Sigma=\\{\sigma_{n}\\}_{n=1}^{\infty}$ satisfies
$\sigma_{n}\in\Omega^{\prime}_{i_{n}}$ for some increasing sequence
$(i_{n})_{n}$ with $k\mid i_{n}$ for all $n$ then

$h_{\Sigma}(\mathtt{A}^{\Gamma},\mu,T)\leq\mathrm{H_{K}}(\mu).$

###### Proof.

Given a number $n$ divisible by $k$, $\varepsilon>0$, and
$\sigma:\Gamma\to\operatorname{Sym}(n)$, let $N_{n,\varepsilon}(\sigma)$ be
the number of microstates $\mathbf{x}\in\mathtt{A}^{\Gamma}$ such that

$\|W_{\mathbf{x},\sigma}-W_{\mu}\|<\varepsilon.$

We think of $N_{n,\varepsilon}$ as a random variable with respect to the
uniform measure on the space of $k$-uniform homomorphisms from $\Gamma$ to
$\operatorname{Sym}(n)$. By definition

$\displaystyle\mathrm{H_{K}}(\mu)$ $\displaystyle=$
$\displaystyle\lim_{\varepsilon\to
0}\limsup_{n\to\infty}\frac{1}{n}\log\operatorname*{\mathbb{E}}[N_{n,\varepsilon}]$

where here and below we assume $n$ is always a multiple of $k$. So there
exists a sequence $(\epsilon_{n})_{n}$ of positive numbers tending to zero
slowly enough so that

$\displaystyle\mathrm{H_{K}}(\mu)$ $\displaystyle=$
$\displaystyle\limsup_{n\to\infty}\frac{1}{n}\log\operatorname*{\mathbb{E}}[N_{n,\epsilon_{n}}].$

Let $(\delta_{n})_{n}$ be another sequence of positive numbers tending to
zero. We choose $\delta_{n}$ to converge to zero slowly enough so that

$\lim_{n\to\infty}\frac{\operatorname*{\mathbb{E}}[N_{n,\epsilon_{n}}]}{\exp(n(\mathrm{H_{K}}(\mu)+\delta_{n}))}=0.$

For example, we could choose $\delta_{n}$ by setting

$\mathrm{H_{K}}(\mu)+\delta_{n}/2=n^{-1}\log\operatorname*{\mathbb{E}}[N_{n,\epsilon_{n}}].$

It follows from Markov’s inequality that

$\mathbb{P}_{n}(N_{n,\epsilon_{n}}\geq\exp(n(\mathrm{H_{K}}(\mu)+\delta_{n})))\leq\frac{\operatorname*{\mathbb{E}}[N_{n,\epsilon_{n}}]}{\exp(n(\mathrm{H_{K}}(\mu)+\delta_{n}))}\to
0$

as $n\to\infty$. So we set $\Omega_{n}^{\prime}$ to be the set of
$\sigma\in\Omega_{n}^{\mathrm{sofic}}$ satisfying
$N_{n,\epsilon_{n}}(\sigma)<\exp(n(\mathrm{H_{K}}(\mu)+\delta_{n}))$. The
previous inequality shows
$\lim_{n\to\infty}\mathbb{P}_{n}(\Omega_{n}^{\prime})=1$.

Suppose $\Sigma=\\{\sigma_{n}\\}_{n=1}^{\infty}$ satisfies
$\sigma_{n}\in\Omega^{\prime}_{i_{n}}$ for some increasing sequence
$(i_{n})_{n}$ with $k\mid i_{n}$ for all $n$. Then the choice of
$\Omega^{\prime}_{n}$ implies

$\displaystyle\mathrm{H_{K}}(\mu)$ $\displaystyle\geq$
$\displaystyle\lim_{\varepsilon\to
0}\limsup_{n\to\infty}\frac{1}{i_{n}}\log\left\lvert\\{\mathbf{x}\in\mathtt{A}^{i_{n}}\,:\,\|W_{\mathbf{x},\sigma_{i_{n}}}-W_{\mu}\|<\varepsilon\\}\right\rvert$
$\displaystyle\geq$ $\displaystyle h_{\Sigma}(\mathtt{A}^{\Gamma},\mu,T).$

The second inequality follows from the fact that, for any $\varepsilon>0$, the
set

$\\{\nu\in\operatorname{Prob}(\mathtt{A}^{\Gamma}):~{}\|W_{\nu}-W_{\mu}\|<\varepsilon\\}$

is an open neighborhood of $\mu$. ∎

####  3.3 A brief history

The most basic method for analyzing the behaviour of a random sofic
approximation is the first moment method. Our first indication of the typical
number of microstates for $(X,m_{X},T)$ over $\sigma_{n}$ chosen from
$\mathbb{P}_{n}$ is given by the expectation of that number.

In the analogous setting of actions of free groups, such averages have been
studied intensely in recent years. In [9], the exponential growth rate of the
expected number of good microstates was shown to coincide with an invariant of
systems previously introduced by the second author in [10], where it was used
to solve the isomorphism problem for finite-state Bernoulli actions of free
groups. In those and several subsequent papers, this invariant was called the
‘f-invariant’. Here we propose a new term instead: we refer to this quantity
as ‘annealed entropy’.

In work of the second author, the f-invariant was obtained as a limit of
functionals referred to as $F$, which are annealed entropies of Markov
approximations. As explained further below, this quantity first appeared in
refinements of work of Kikuchi [37]. For this reason, we call it Kikuchi
entropy. In later sections, it is used to prove Theorem 1.3.

The reason for the name “annealed entropy” is a connection to statistics and
statistical physics. During the last forty years, very similar first-moment
calculations for various configurations over large sparse random graphs have
become a central feature of the analysis of ‘graphical models’ in those
disciplines. Often, the use of such averages can be seen as a first attempt to
find the value for a ‘typical’ random graph. In such settings, the first
moment is referred to as an annealed average: see, for instance, the usage in
[45, Section IV.1] or [44, Section 5.4]. Its use as a prediction of typical
behaviour is called the ‘Bethe ansatz’ (or sometimes the ‘replica symmetric’
approximation in reference to a phenomenology in the study of spin glasses
that we do not explain here: see, for instance, [45, Chapter I] or [44,
Chapter 8]444Indeed, the second author has previously also suggested the term
‘replica-symmetric entropy’ [13, Subsection 7.3], but we feel ‘annealed’
reflects the general nature of this quantity better.).

In fact, the origins of these quantities lie even further back in the
statistical physics literature. In the general setting for random graphical
models studied in statistics, the leading order exponents in first moment
calculations are given by quantities called ‘Bethe’ or ‘Kikuchi’ entropy.

The first of these terms refers to foundational work by Bethe [8]. He
estimated the free energy of a certain model of an alloy on a two-dimensional
lattice by a recursive expansion that retained nearest-neighbour interactions
but ignored the effect of loops in the lattice graph. A more mathematical
description is that the two-dimensional lattice is approximated by an infinite
regular tree, and this is why such trees are now often called ‘Bethe lattices’
in statistical physics.

In [37], Kikuchi expanded on Bethe’s ideas by proposing a more careful
expansion that respects slightly more of the lattice structure. In modern
terms, this can be understood as an approximation to the lattice by a hyper-
tree rather than a simple tree. While Bethe argued mostly in terms of free
energies, Kikuchi’s paper includes various explicit formulae for entropy
estimates, and these evolved over time into the quantities studied in
statistical inference today. See [37, Equations (A.7) and (C1.6)] for early
intimations of these modern formulae. Bethe’s and Kikuchi’s approximation
methods can also be found in physics surveys from closer to that time such as
Section III in Burley’s contribution [25, Chapter 9].

These formulae were brought explicitly into statistical theory around 2000 by
Yedidia and various co-authors in a series of technical reports: see, in
particular, [71, 72] and the further references given there. While these
references continued to emphasize free energy more than entropy, they do cover
both: the explicit formula for Bethe entropy is [71, Formula (1.32)], for
example.

The term ‘annealed entropy’ (instead of ‘f-invariant’) emphasizes the
connection between these two fields. To be more precise, the annealed entropy
of a measure-preserving action of a free group is defined as an infimum of the
values of a more elementary quantity over Markov approximations to the action.
This more elementary quantity, denoted by ‘$F$’ in [10, 9], has precisely the
same formula as Bethe entropy. Thus, the same formula for an entropy-like
quantity was discovered independently and then used for very similar first-
moment calculations in both fields.

Bethe entropy has by now become a textbook topic in statistical inference with
graphical models: see, for instance, [65, Section 4] or [44, Chapter 14,
especially Subsection 14.2.4]. Some of the theory of these models has also
been analyzed rigorously in the probability literature. For example, [23]
proves that a first-moment quantity asymptotically agrees with the typical
free energy for ferromagnetic Potts models over sparse graph sequences,
justifying the ‘Bethe ansatz’ for these models.

Whereas Bethe entropy can be understood as a functional of a probability
distribution over a tree, the extension to Kikuchi entropy allows an
underlying graph that is a hyper-tree, which is a hyper-graph $G=(V,E)$ such
that there is some tree with vertex set $V$ whose subgraphs induced by hyper-
edges of $G$ are all connected.

For the first-moment calculations we need below, the exponent is given by the
analogous annealed entropy for an action of $\Gamma$, the $d$-fold free power
of $\mathbb{Z}_{k}$, rather than a free group. It turns out that this could
again be defined as an infimum of a more elementary quantity over Markov
approximations, where now the more elementary quantity is the Kikuchi entropy
associated to the Cayley hyper-tree of $\Gamma$. We do not work this out
completely here. Instead, we give a more direct formula for the annealed
entropy and only show that it is bounded above by the Kikuchi entropy (see
discussion following Prop. 3.1).

###  4 Completely positive entropy, local convergence, and model mixing

In order to prove the completely positive entropy (CPE) statement in Theorem
1.3, we will use a variant of the main result of [7]. That paper proves that
if a model measure sequence locally and empirically converges to the target
measure and is uniformly model mixing then the system is CPE. The local and
empirical convergence result needed to prove CPE will also help us establish
the lower bound in Theorem 1.3, part (a). We review these concepts here.

As in previous sections, let $\mathtt{A}$ be a finite set, $\Gamma$ a
countable group and $\mu$ be a $\Gamma$-invariant Borel probability measure on
$\mathtt{A}^{\Gamma}$. We also let $\Sigma=(\sigma_{n})_{n}$ be a sofic
approximation, where $\sigma_{n}:\Gamma\to\operatorname{Sym}(V_{n})$ for each
$n$.

Given a probability measure $\kappa$ on $\mathtt{A}^{V_{n}}$ and a vertex
$v\in V_{n}$, the localization of $\kappa$ at $v$ is the probability measure

$\mathrm{Loc}(\kappa,v)=(\Pi_{v}^{\sigma_{n}})_{*}\kappa=\sum_{\mathbf{x}\in\mathtt{A}^{V_{n}}}\kappa(\mathbf{x})\delta_{\Pi^{\sigma_{n}}_{v}(\mathbf{x})}\in\operatorname{Prob}(\mathtt{A}^{\Gamma}).$

This is the law of the pull-back name of a $\kappa$-random sample, as viewed
from a fixed $v\in V_{n}$. This measure depends on the homomorphism
$\sigma_{n}$, but we will usually leave that dependence implicit. If we want
to specify $\sigma_{n}$, we use the notation
$\mathrm{Loc}_{\sigma_{n}}(\kappa,v)$.

A model measure sequence is a sequence $(\mu_{n})_{n}$ of probability measures
$\mu_{n}$ on $\mathtt{A}^{V_{n}}$. The sequence $(\mu_{n})_{n}$ is said to
converge to $\mu$ locally and empirically if for every open neighborhood
$\mathcal{O}$ of $\mu$ in $\operatorname{Prob}(\mathtt{A}^{\Gamma})$,

$\displaystyle 1$ $\displaystyle=$
$\displaystyle\lim_{n\to\infty}|V_{n}|^{-1}\,\lvert\\{v\in
V_{n}:~{}\mathrm{Loc}(\mu_{n},v)\in\mathcal{O}\\}\rvert$ $\displaystyle 1$
$\displaystyle=$
$\displaystyle\lim_{n\to\infty}\mu_{n}(\\{\mathbf{x}\in\mathtt{A}^{V_{n}}:~{}P_{\mathbf{x}}^{\sigma_{n}}\in\mathcal{O}\\}).$

Below, we will sometimes refer to the first equality holding for every
$\mathcal{O}$ as _local convergence_ and the second as _empirical convergence_
in order to be explicit about which property is relevant.

If the measures $\mu_{n}$ and/or the maps $\sigma_{n}$ are random with law
$\mathbb{P}_{n}$, then we say the sequence converges locally and empirically
in probability to $\mu$ if the same limits hold in probability. Explicitly,
for every open neighborhood $\mathcal{O}$ of $\mu$ and every $\varepsilon>0$,

$\displaystyle 1$ $\displaystyle=$
$\displaystyle\lim_{n\to\infty}\mathbb{P}_{n}\left\\{|V_{n}|^{-1}\,\lvert\\{v\in
V_{n}:~{}\mathrm{Loc}(\mu_{n},v)\in\mathcal{O}\\}\rvert>1-\varepsilon\right\\}$
$\displaystyle 1$ $\displaystyle=$
$\displaystyle\lim_{n\to\infty}\mathbb{P}_{n}\left\\{\mu_{n}(\\{\mathbf{x}\in\mathtt{A}^{V_{n}}:~{}P_{\mathbf{x}}^{\sigma_{n}}\in\mathcal{O}\\})>1-\varepsilon\right\\}.$

It will be convenient to reformulate local convergence in probability in terms
of total variation distance between marginals. To make this precise, we need
notation for the marginals.

Given a finite set $B\subset\Gamma$ and a probability measure $\nu$ on
$\mathtt{A}^{\Gamma}$, let $\nu_{B}$ be the probability measure on
$\mathtt{A}^{B}$ equal to the pushforward of $\nu$ under the projection map
$\mathtt{A}^{\Gamma}\to\mathtt{A}^{B}$. This is the marginal of $\nu$ on $B$.

Let $d_{\operatorname{TV}}$ denote total variation distance. Because the sets
of the form
$\mathcal{O}(B,\varepsilon,\mu)=\\{\nu\in\operatorname{Prob}(\mathtt{A}^{\Gamma}):~{}d_{\operatorname{TV}}(\nu_{B},\mu_{B})<\varepsilon\\}$
form a neighborhood basis for the topology at $\mu$, it follows that a
sequence of random measures
$\mu_{n}\in\operatorname{Prob}(\mathtt{A}^{V_{n}})$ converges locally in
probability to a measure $\mu\in\operatorname{Prob}(\mathtt{A}^{\Gamma})$ if
and only if for every finite $B\subset\Gamma$ and $\varepsilon>0$,

$\displaystyle\lim_{n\to\infty}\mathbb{P}_{n}\left\\{\frac{1}{\lvert
V_{n}\rvert}\left\lvert\left\\{v\in
V_{n}\,:\,d_{\operatorname{TV}}\big{(}\mathrm{Loc}(\mu_{n},v)_{B},\,\mu_{B}\big{)}>\varepsilon\right\\}\right\rvert>\varepsilon\right\\}=0.$
(4)

The following lemma is a version of [3, Corollary 5.7] for random measures.
The proof requires only minor modifications.

######  Lemma 4.1.

If a sequence of random measures $(\mu_{n})_{n}$ converges locally in
probability to an ergodic measure
$\mu\in\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma})$ over some random
sequence of homomorphisms, then it converges locally and empirically in
probability to $\mu$.

###### Proof.

For each $n$, let
$\theta_{n}\in\operatorname{Prob}(\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma}))$
denote the law of

$\frac{1}{\lvert V_{n}\rvert}\sum_{v\in
V_{n}}\mathrm{Loc}_{\sigma_{n}}(\mu_{n},v),$

where $(\sigma_{n},\mu_{n})$ are jointly distributed as given. As stated,
$\theta_{n}$ is supported on $\Gamma$-imvariant measures because each
$\sigma_{n}$ is a homomorphism and therefore the empirical measure
$P^{\sigma_{n}}_{\bf{x}}$ is invariant, for any ${\bf
x}\in\mathtt{A}^{V_{n}}$.

Passing to a subsequential limit if necessary, the sequence $(\theta_{n})_{n}$
converges weakly to some
$\theta\in\operatorname{Prob}(\operatorname{Prob}^{\Gamma}(\mathtt{A}^{\Gamma}))$.
We first show the barycenter of $\theta$ must be $\mu$: given a continuous
function $g\in C(\mathtt{A}^{\Gamma})$

$\displaystyle\iint g(\mathbf{z})\,\nu(d\mathbf{z})\,\theta(d\nu)$
$\displaystyle=\lim_{n\to\infty}\iint
g(\mathbf{z})\,\nu(d\mathbf{z})\,\theta_{n}(d\nu)$
$\displaystyle=\lim_{n\to\infty}\operatorname*{\mathbb{E}}\left[\frac{1}{|V_{n}|}\sum_{v\in
V_{n}}\int g(\Pi_{v}^{\sigma_{n}}\mathbf{x})\,\mu_{n}(d\mathbf{x})\right].$

Now given $\varepsilon>0$, let $\mathcal{O}\ni\mu$ be an open neighborhood
such that if $\nu\in\mathcal{O}$ then $\int g\,d\nu$ is within $\varepsilon$
of $\int g\,d\mu$. Then we control the expectation above by dividing up the
terms based on whether $\mu_{n}$ looks like $\mu$ near $v$:

$\displaystyle\operatorname*{\mathbb{E}}\left[\frac{1}{|V_{n}|}\sum_{v\in
V_{n}}\int g(\Pi_{v}^{\sigma_{n}}\mathbf{x})\,\mu_{n}(d\mathbf{x})\right]$
$\displaystyle=\frac{1}{|V_{n}|}\operatorname*{\mathbb{E}}\left[\sum_{\begin{subarray}{c}v\in
V_{n}\\\ \mathrm{Loc}(\mu_{n},v)\in\mathcal{O}\end{subarray}}\int
g(\Pi_{v}^{\sigma_{n}}\mathbf{x})\,\mu_{n}(d\mathbf{x})\right]$
$\displaystyle\qquad+\frac{1}{|V_{n}|}\operatorname*{\mathbb{E}}\left[\sum_{\begin{subarray}{c}v\in
V_{n}\\\ \mathrm{Loc}(\mu_{n},v)\not\in\mathcal{O}\end{subarray}}\int
g(\Pi_{v}^{\sigma_{n}}\mathbf{x})\,\mu_{n}(d\mathbf{x})\right].$

The magnitude of the second term is bounded by

$\max\lvert
g\rvert\cdot\operatorname*{\mathbb{E}}\left[\frac{1}{|V_{n}|}\lvert\\{v\in
V_{n}:\mathrm{Loc}(\mu_{n},v)\not\in\mathcal{O}\\}\rvert\right]$

which goes to 0 as $n$ goes to infinity by definition of local convergence in
probability. By choice of $\mathcal{O}$, the first term is within
$\varepsilon$ of $\int g\,d\mu$ for large $n$. Since $\varepsilon>0$ was
arbitrary, this proves that the (subsequential) limit must have barycenter
$\mu$.

Since $m$ is ergodic, the only possible subsequential limit with barycenter
$\mu$ is $\delta_{\mu}$, so this is the true limit. This implies that for any
$\varepsilon>0$ and open $\mathcal{O}\ni\mu$,

$\mathbb{P}\big{\\{}\mu_{n}(\Omega(\sigma_{n},\mathcal{O}))>1-\varepsilon\big{\\}}\to
1.$

This is because

$\mathbb{P}\big{\\{}1-\mu_{n}(\Omega(\sigma_{n},\mathcal{O}))>\varepsilon\big{\\}}\leq\frac{\operatorname*{\mathbb{E}}\big{[}1-\mu_{n}(\Omega(\sigma_{n},\mathcal{O}))]}{\varepsilon}=\frac{1-\operatorname*{\mathbb{E}}[\operatorname*{\mathbb{E}}_{\mathbf{x}\sim\mu_{n}}[\mathbf{1}_{P_{\mathbf{x}}^{\sigma_{n}}\in\mathcal{O}}]]}{\varepsilon}=\frac{1-\theta_{n}(\mathcal{O})}{\varepsilon}\to
0$

using Markov’s inequality, the tower law of expectation, and the portmanteau
theorem. ∎

####  4.1 Property M

To define notions of model mixing, we will impose distance functions on the
finite sets $V$ which form a given sofic approximation. For this purpose, we
will assume $\Gamma$ is finitely generated and let $E\subset\Gamma$ be a
finite symmetric generating subset. For $g\in\Gamma$, let $|g|$ be the word-
length of $g$, which is the length of the shortest word in $E$ representing
$g$. Given $\sigma:\Gamma\to\operatorname{Sym}(V)$, define distance in $V$ by

$d_{\sigma}(v,w)=\min\\{|g|:~{}g\in\Gamma,\sigma(g)v=w\\}.$

If there does not exist $g$ with $\sigma(g)v=w$ then we set
$d_{\sigma}(v,w)=+\infty$. If $\sigma$ is not a homomorphism then $d_{\sigma}$
may fail to satisfy the triangle inequality.

A subset $S\subset V$ is $r$-separated if $d_{\sigma}(v,w)>r$ for every pair
of distinct $v,w\in S$.

Suppose a model measure sequence $(\mu_{n})_{n}$ converges locally and
empirically to $\mu$. We say the sequence is uniformly model mixing (umm) if
for every finite $F\subset\Gamma$ and every $\epsilon>0$ there is some
$r<\infty$ and a sequence of finite subsets $W_{n}\subset V_{n}$ such that

$|W_{n}|=(1-o(1))|V_{n}|$

and if $S\subset W_{n}$ is $r$-separated then

$\operatorname{H}((\mu_{n})_{\sigma_{n}^{F}(S)})\geq|S|(\operatorname{H}(\mu_{F})-\epsilon)$

where

  * •

$\mu_{F}$ is the probability measure on $\mathtt{A}^{F}$ which is the
pushforward of $\mu$ under the projection map
$\mathtt{A}^{\Gamma}\to\mathtt{A}^{F}$;

  * •

$\sigma_{n}^{F}(S)=\\{\sigma_{n}(f)s:~{}f\in F,s\in S\\}$;

  * •

$(\mu_{n})_{\sigma_{n}^{F}(S)}$ is the probability measure on
$\mathtt{A}^{\sigma_{n}^{F}(S)}$ which is the pushforward of $\mu_{n}$ under
the projection map $\mathtt{A}^{V_{n}}\to\mathtt{A}^{\sigma_{n}^{F}(S)}$.

This is a microstates analog of uniform mixing, introduced by Rudolph and
Weiss in [57] for actions of an amenable group; see also [68, Definition 10],
where the name ‘uniform mixing’ appears for the first time. The main result of
[7] is that if $(\mu_{n})_{n}$ locally and empirically converges to $\mu$ and
is uniformly model mixing with respect to a fixed sofic approximation
$\Sigma$, then the system $(\mathtt{A}^{\Gamma},\mu,T)$ has completely
positive entropy with respect to $\Sigma$, in analogy with a corresponding
result of [57].

Unfortunately, we do not know whether the parity check sub-shifts of Theorem
1.3 are uniformly model mixing. Instead we define a weaker version of model
mixing which suffices.

######  Definition 4.2 (Property M).

Suppose $(\mu_{n})_{n}$ is a model measure sequence and
$\mu\in\operatorname{Prob}_{\Gamma}(\mathtt{A}^{\Gamma})$ is an invariant
measure. We say the sequence has property M if for every $\epsilon>0$ and
$0<r<\infty$ there is a sequence of subsets $S_{n}\subset V_{n}$ such that

$\liminf\frac{|S_{n}|}{|V_{n}|}>0$

and

$\operatorname{H}((\mu_{n})_{\sigma_{n}^{B_{r}}(S_{n})})\geq|S_{n}|(\operatorname{H}(\mu_{B_{r}})-\epsilon)$
(5)

for all $n$, where $B_{r}=\mathrm{B}(r,e)\subset\Gamma$ denotes the ball of
radius $r$ centered at the identity. In applications, $\mu$ will be a limit of
the sequence $(\mu_{n})_{n}$ but we do not impose any such requirement for the
definition.

In contrast with uniform model-mixing, we only require $S_{n}$ to have
asymptotically positive density in $V_{n}$, and there is no uniform lower
bound on this density across different choices of $\epsilon,r$. This density
could be much smaller than $|B_{r}|^{-1}$, for example. We also do not require
the sets $S_{n}$ to be separated, although the lower bound (5) does usually
imply a kind of approximate separation anyway.

We suspect that other variants of uniform model mixing could be used in a
similar way to prove completely positive entropy, so Definition 4.2 is not an
attempt at optimal generality. This is why we have chosen a rather bland name
for Property M, although it is convenient in our work below.

We will show below that every nontrivial factor has positive entropy, but so
far we have defined sofic entropy only for finite-alphabet shift systems.
Before stating and proving the main theorem of this section, we briefly recall
the definition of sofic entropy for shift systems with a compact base space.

If $X$ is a metric space and $Y\subseteq X$, then for every $\delta>0$ we
define the covering number

$\operatorname{cov}_{\delta}(Y)=\min\left\\{\lvert F\rvert\,:\,F\subset Y,\
Y\subseteq\bigcup_{x\in F}\mathrm{B}(\delta,x)\right\\}$

where $\mathrm{B}(\delta,x)$ is the closed ball centered at $x$ of radius
$\delta$. For every finite set $V$ we give $X^{V}$ the normalized Hamming
metric

$\textrm{d}_{X}^{(V)}(x_{1},\,x_{2})=\frac{1}{\lvert V\rvert}\sum_{v\in
V}\textrm{d}_{X}(x_{1}(v),\,x_{2}(v)).$

For a sofic approximation
$\Sigma=(\sigma_{n}\colon\Gamma\to\operatorname{Sym}(V_{n}))_{n}$ we define
the sofic entropy of $\mu\in\operatorname{Prob}^{\Gamma}(X^{\Gamma})$ by

$\operatorname{h}_{\Sigma}(X^{\Gamma},\mu)=\sup_{\delta>0}\inf_{\mathcal{O}\ni\mu}\limsup_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\operatorname{cov}_{\delta}\big{(}\Omega(\sigma_{n},\mathcal{O})\big{)},$

where $\mathcal{O}$ is a weak*-open neighborhood of $\mu$ and the set
$\Omega(\sigma_{n},\mathcal{O})\subset X^{V_{n}}$ of $\mathcal{O}$-microstates
is defined in the same way as the finite-alphabet case.

######  Theorem 4.3.

As above, let $\mu$ be a $\Gamma$-invariant probability measure on
$\mathtt{A}^{\Gamma}$,
$\Sigma=(\sigma_{n}:\Gamma\to\operatorname{Sym}(V_{n}))_{n}$ a sofic
approximation, and $(\mu_{n})_{n}$ a model measure sequence. Assume
$(\mu_{n})_{n}$ converges to $\mu$ locally and empirically along $\Sigma$ and
has property M. Then every nontrivial factor of $(\mathtt{A}^{\Gamma},\mu,T)$
has positive $\Sigma$-entropy.

###### Proof.

The proof of the case in which the factor has a finite generating partition is
based on the proof of Theorem 1.2 of [7].

For two or more jointly distributed random variables $X_{1},\ldots,X_{k}$,
define the total correlation

$\operatorname{TC}(X_{1};\cdots;X_{k})=\left(\sum_{i=1}^{k}\operatorname{H}(X_{i})\right)-\operatorname{H}(X_{1},\ldots,X_{k}).$

This is a generalization of mutual information to more than two random
variables, introduced in [66]. It can also be recursively defined by setting
$\operatorname{TC}(X_{1};X_{2})=\operatorname{I}(X_{1};X_{2})$ and for $k\geq
3$

$\operatorname{TC}(X_{1};\cdots;X_{k})=\operatorname{TC}(X_{1};\cdots;X_{k-1})+\operatorname{I}(X_{1},\ldots,X_{k-1};X_{k}).$

Using this recursion and the data-processing inequality [22, Theorem 2.8.1],
it can be shown by induction on $k$ that if $f$ is any function and
$Y_{i}=f(X_{i})$ for each $i$ then

$\operatorname{TC}(Y_{1};\cdots;Y_{k})\leq\operatorname{TC}(X_{1};\cdots;X_{k}).$
(6)

This inequality has also appeared in [6, Lemma 4.3]. Note that the total
correlation does not depend on the order in which the random variables are
listed. Below, we will refer to the total variation of a collection of random
variables $\\{X_{i}\,:\,i\in I\\}$ indexed by a finite set $I$ using the
notation $\operatorname{TC}(\\{X_{i}\,:\,i\in I\\})$, since fixing an ordering
would unnecessarily complicate notation.

The Rokhlin distance between random variables $\alpha,\beta$ which are defined
on the same probability space is defined by
$\textrm{d}^{\mathrm{Rok}}_{\mu}(\alpha,\beta)=\operatorname{H}_{\mu}(\alpha|\beta)+\operatorname{H}_{\mu}(\beta|\alpha)$.
This satisfies the triangle inequality, and it equals zero if and only if
$\alpha$ and $\beta$ generate the same partition up to null sets. This
distance can be used to control total correlation via the bound

$\displaystyle\left\lvert\operatorname{TC}(X_{1};\cdots;X_{k})-\operatorname{TC}(Y_{1};\cdots;Y_{k})\right\rvert$
$\displaystyle\leq\left\lvert\operatorname{H}(X_{1},\ldots,X_{k})-\operatorname{H}(Y_{1},\ldots,Y_{k})\right\rvert+\sum_{i=1}^{k}\left\lvert\operatorname{H}(X_{i})-\operatorname{H}(Y_{i})\right\rvert$
$\displaystyle\leq
2\sum_{i=1}^{k}\big{(}\operatorname{H}(X_{i}|Y_{i})+\operatorname{H}(Y_{i}|X_{i})\big{)}=2\sum_{i=1}^{k}\textrm{d}^{\mathrm{Rok}}(X_{i},Y_{i}).$

Since $(\mu_{n})_{n}$ locally and empirically converges to $\mu$, if
$S_{n}\subset V_{n}$ satisfies $\liminf\frac{\lvert S_{n}\rvert}{\lvert
V_{n}\rvert}>0$ then

$\frac{1}{\lvert S_{n}\rvert}\sum_{v\in
S_{n}}\operatorname{H}\big{(}(\mu_{n})_{\sigma_{n}^{B_{r}}(v)}\big{)}=\operatorname{H}(\mu_{B_{r}})+o(1).$

So property M implies that for every $r,\varepsilon>0$ there is a sequence of
subsets $S_{n}\subset V_{n}$ such that $\liminf\frac{\lvert
S_{n}\rvert}{\lvert V_{n}\rvert}>0$ and

$\frac{1}{\lvert
S_{n}\rvert}\operatorname{TC}\big{(}\\{(\mathbf{x}_{n})^{\sigma_{n}^{B_{r}}(v)}\,:\,v\in
S_{n}\\}\big{)}\leq\varepsilon$

for all large $n$, where $\mathbf{x}_{n}$ is a random sample of $\mu_{n}$ and
the projections $\\{(\mathbf{x}_{n})^{\sigma_{n}^{B_{r}}(v)}\,:\,v\in
S_{n}\\}$ are jointly distributed in the natural way (from a common sample of
$\mathbf{x}_{n}$).

We first consider the case where the factor has a finite generating partition:
suppose $\phi\colon\mathtt{A}^{\Gamma}\to\mathtt{B}$ is a measurable map into
a finite set $\mathtt{B}$ generating a factor map
$\phi^{\Gamma}\colon\mathtt{A}^{\Gamma}\to\mathtt{B}^{\Gamma}$ defined by

$\phi^{\Gamma}(x)(g)=\phi(g^{-1}x).$

If this factor is nontrivial then $\operatorname{H}_{\mu}(\phi)>0$. We want to
show that the property M assumption on $\mu_{n}\to\mu$ implies that
$\phi^{\Gamma}_{*}\mu$ has positive sofic entropy.

Fix $r\in\mathbb{N}$ and an $r$-local function
$\psi\colon\mathtt{A}^{\Gamma}\to\mathtt{B}$ such that
$\textrm{d}^{\mathrm{Rok}}_{\mu}(\psi,\phi)<\frac{1}{8}\operatorname{H}_{\mu}(\phi)$
(“$r$-local” means that if $x,y\in\mathtt{A}^{\Gamma}$ agree on the ball
$\mathrm{B}(r,e)$ then $\psi(x)=\psi(y)$).

Now with $\varepsilon=\frac{1}{8}\operatorname{H}_{\mu}(\phi)$ and this $r$,
let $(S_{n})_{n}$ be the sequence of subsets of $V_{n}$ given by property M.
Since $\psi$ is $r$-local, the data-processing inequality (6) above implies
that

$\operatorname{TC}\big{(}\\{{\psi^{\sigma_{n}}}(\mathbf{x}_{n})(v)\,:\,v\in
S_{n}\\}\big{)}\leq\operatorname{TC}\big{(}\\{(\mathbf{x}_{n})^{\sigma_{n}^{B_{r}}(v)}\,:\,v\in
S_{n}\\}\big{)}\leq\varepsilon\lvert S_{n}\rvert$

where ${\bf x}_{n}$ is a random sample of $\mu_{n}$ and
$\psi^{\sigma_{n}}\colon\mathtt{A}^{V_{n}}\to\mathtt{B}^{V_{n}}$ is defined by

$\psi^{\sigma_{n}}(\mathbf{x})(v)=\psi(\Pi_{v}^{\sigma_{n}}\mathbf{x}).$

Let $(\psi_{m})_{m}$ be an AL-approximating sequence to $\phi$ rel $\mu$ [3].
Then the Rokhlin distance $\textrm{d}^{\mathrm{Rok}}_{\mu}(\phi,\psi_{m})$
converges to 0. Since the Rokhlin distance satisfies the triangle inequality,
there is some $M\in\mathbb{N}$ such that if $m\geq M$ then
$\textrm{d}^{\mathrm{Rok}}_{\mu}(\psi,\psi_{m})<\frac{1}{8}\operatorname{H}_{\mu}(\phi)$.

Given an open neighborhood $\mathcal{O}\ni\phi^{\Gamma}_{*}\mu$, by [3, Prop.
4.10] there is some open neighborhood $\mathcal{U}\ni\mu$ and some $m\geq M$
such that, for all large enough $n$, the map $\psi_{m}^{\sigma_{n}}$ sends
$\mathcal{U}$-microstates to $\mathcal{O}$-microstates. Let us also assume $m$
is large enough that
$\operatorname{H}_{\mu}(\psi_{m})\geq\frac{1}{2}\operatorname{H}_{\mu}(\phi)$.

Now fix some $R$ such that $\psi$ and $\psi_{m}$ are both $R$-local. By local
convergence of $\mu_{n}$ to $\mu$, for any $\delta>0$, the fraction of $v\in
S_{n}$ for which the local marginal $\mathrm{Loc}(\mu_{n},v)_{B_{R}}$ is
within total variation distance $\delta$ of $\mu_{B_{R}}$ is $1-o(1)$. For the
rest of the $v\in S_{n}$, the term in the sum below has the upper bound
$2\log\lvert\mathtt{B}\rvert$:

$\displaystyle\tfrac{1}{\lvert
S_{n}\rvert}\left\lvert\operatorname{TC}\big{(}\\{{\psi^{\sigma_{n}}}(\mathbf{x}_{n})(v)\,:\,v\in
S_{n}\\}\big{)}-\operatorname{TC}\big{(}\\{{\psi_{m}^{\sigma_{n}}}(\mathbf{x}_{n})(v)\,:\,v\in
S_{n}\\}\big{)}\right\rvert$ $\displaystyle\leq\frac{2}{\lvert
S_{n}\rvert}\sum_{v\in
S_{n}}\left(\operatorname{H}_{\mathrm{Loc}(\mu_{n},v)}(\psi|\psi_{m})+\operatorname{H}_{\mathrm{Loc}(\mu_{n},v)}(\psi_{m}|\psi)\right)$
$\displaystyle\leq 2\textrm{d}^{\mathrm{Rok}}_{\mu}(\psi_{m},\psi)+o(1).$

Hence

$\tfrac{1}{\lvert
S_{n}\rvert}\operatorname{TC}\big{(}\\{{\psi_{m}^{\sigma_{n}}}(\mathbf{x}_{n})(v)\,:\,v\in
S_{n}\\}\big{)}\leq\frac{3}{8}\operatorname{H}_{\mu}(\phi)+o(1).$ (7)

By empirical convergence, for large $n$ the model measure $\mu_{n}$ is mostly
supported on $\mathcal{U}$-microstates. So
${\psi_{m}^{\sigma_{n}}}_{*}\mu_{n}$ is mostly supported on
$\mathcal{O}$-microstates, and using Fano’s inequality we see that

$\frac{1}{\lvert
V_{n}\rvert}\operatorname{H}({\psi_{m}^{\sigma_{n}}}_{*}\mu_{n})\leq\frac{1}{\lvert
V_{n}\rvert}\log\lvert\Omega(\sigma_{n},\mathcal{O})\rvert+o(1).$

The total correlation bound (7) gives

$\displaystyle\operatorname{H}({\psi_{m}^{\sigma_{n}}}_{*}\mu_{n})=\operatorname{H}(\psi_{m}^{\sigma_{n}}({\bf
x}_{n}))$ $\displaystyle\geq\operatorname{H}(\\{(\psi_{m}^{\sigma_{n}}({\bf
x}_{n})(v)\,:\,v\in S_{n}\\})$ $\displaystyle\geq\sum_{v\in
S_{n}}\operatorname{H}((\psi_{m}^{\sigma_{n}}({\bf x}_{n})(v)\\})-\lvert
S_{n}\rvert\big{(}\tfrac{3}{8}\operatorname{H}_{\mu}(\phi)+o(1)\big{)}.$

Since $(\mu_{n})_{n}$ converges locally to $\mu$ and $\psi_{m}$ is a local
function,

$\frac{1}{\lvert S_{n}\rvert}\sum_{v\in
S_{n}}\operatorname{H}((\psi_{m}^{\sigma_{n}}({\bf
x}_{n})(v))=\operatorname{H}_{\mu}(\psi_{m})+o(1)\geq\tfrac{1}{2}\operatorname{H}_{\mu}(\phi)+o(1).$

So

$\frac{1}{\lvert
V_{n}\rvert}\log\lvert\Omega(\sigma_{n},\mathcal{O})\rvert\geq\frac{\lvert
S_{n}\rvert}{\lvert
V_{n}\rvert}\left(\tfrac{1}{8}\operatorname{H}_{\mu}(\phi)+o(1)\right)+o(1),$

and for every $\mathcal{O}\ni\phi^{\Gamma}_{*}\mu$

$\liminf_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\lvert\Omega(\sigma_{n},\mathcal{O})\rvert\geq\left(\liminf_{n\to\infty}\frac{\lvert
S_{n}\rvert}{\lvert
V_{n}\rvert}\right)\tfrac{1}{8}\operatorname{H}_{\mu}(\phi).$

Since we chose $(S_{n})_{n}$ independently of $\mathcal{O}$, and
$\liminf_{n\to\infty}\frac{\lvert S_{n}\rvert}{\lvert V_{n}\rvert}>0$, taking
the infimum over $\mathcal{O}$ completes the proof in the case where the
factor has a finite generating partition.

To deal with the general case, note that above we have shown the following:
under the property M assumption, if
$\phi\colon\mathtt{A}^{\Gamma}\to\mathtt{B}$ is a measurable map into a finite
set such that $\operatorname{H}_{\mu}(\phi)>0$ then there is some $C>0$ such
that if $(\psi_{m})_{m}$ is an AL-approximation to $\phi$ then

$\liminf_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\operatorname{H}({\psi_{m}^{\sigma_{n}}}_{*}\mu_{n})\geq C$

for all large enough $m$.

Suppose $\phi_{1}\colon\mathtt{A}^{\Gamma}\to Y$ is a measurable map into a
compact metric space $Y$ which is not $\mu$-almost-surely constant, and let
$\nu=(\phi_{1}^{\Gamma})_{*}\mu$. We want to show that
$\operatorname{h}_{\Sigma}(Y^{\Gamma},\nu)>0$. Assume for the sake of
contradiction that $\operatorname{h}_{\Sigma}(Y^{\Gamma},\nu)=0$. Since
$\phi_{1}$ is not almost-surely constant, there is some measurable map
$\phi_{2}\colon Y^{\Gamma}\to\mathtt{B}$ into a finite set such that
$\phi\coloneqq\phi_{2}\circ\phi_{1}^{\Gamma}$ is not almost-surely constant;
for example we can take any measurable set $E$ in $Y^{\Gamma}$ such that
$\nu(E)\in(0,1)$ and let $\phi_{2}$ be its characteristic function.

As discussed above, there is some $C>0$ such that if $(\psi_{m})_{m}$ is an
AL-approximation to $\phi$ then

$\liminf_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\operatorname{H}({\psi_{m}^{\sigma_{n}}}_{*}\mu_{n})\geq C$ (8)

for all large enough $m$. We will show that $(Y^{\Gamma},\nu)$ having entropy
zero would form a “bottleneck” which prevents this from being true in general.
Fix $s>0$ such that
$\operatorname{H}(s)+s\log\lvert\mathtt{B}\rvert<\frac{C}{4}$.

Let $(\psi_{2,m})_{m}$ be an AL-approximation sequence to $\phi_{2}$. Suppose
each $\psi_{2,m}$ is an $\eta_{m}$-AL approximation, with $\eta_{m}\downarrow
0$.

For all $m$ large enough, $\psi_{2,m}$ is an $\frac{s}{6}$-AL approximation to
$\phi_{2}$. This means there are a finite set $D_{m}\subset\Gamma$, a
$D_{m}$-local open set $U_{m}$, and an $L_{m}$ such that $\nu(U_{m})>1-s/6$
and the restriction of $\phi_{2,m}$ to $U_{m}$ is $\frac{s}{6}$-almost
$L_{m}$-Lipschitz.

Using the assumption that $\operatorname{h}_{\Sigma}(Y^{\Gamma},\nu)=0$, pick
an open neighborhood $\mathcal{O}_{m}\ni\nu$ such that

$\limsup_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\left(\operatorname{cov}_{\frac{s}{2L_{m}\lvert
D_{m}\rvert}}\big{(}\Omega(\mathcal{O}_{m},\sigma_{n})\big{)}\right)<\frac{C}{4}.$

Making $\mathcal{O}_{m}$ smaller if necessary, we can also ensure that the
restriction of $\psi_{2,m}^{\sigma_{n}}$ to
$\Omega(\mathcal{O}_{m},\sigma_{n})$ is $3(\frac{s}{6})$-almost $L_{m}\lvert
D_{m}\rvert$-Lipschitz for all large $n$ [3, Lemma 4.9].

Now for each $m$ there is some $\eta_{1,m}>0$ such that if $\psi_{1,m}$ is an
$\eta_{1,m}$-AL approximation to $\phi_{1}$ then

  1. 1.

there is an open neighborhood $\mathcal{V}_{m}\ni\mu$ such that
$\psi_{1,m}^{\sigma_{n}}$ sends $\mathcal{V}_{m}$-microstates to
$\mathcal{O}_{m}$-microstates for all large enough $n$ [3, Prop. 4.10], and

  2. 2.

$\psi_{m}\coloneqq\psi_{2,m}\circ\psi_{1,m}^{\Gamma}$ is a $(5\eta_{m})$-AL
approximation to $\phi$ (Lemma 2.2).

So, for each fixed $m$, if $n$ is large enough then $\mu_{n}$ is mostly
supported on $\mathcal{V}_{m}$-microstates and hence
$(\psi_{1,m}^{\sigma_{n}})_{*}\mu_{n}$ is mostly supported on
$\mathcal{O}_{m}$-microstates. But, by choice of $\mathcal{O}_{m}$, for some
$k\leq\exp\big{(}\lvert V_{n}\rvert(\frac{C}{4}+o(1))\big{)}$ there are
$y_{1},\ldots,y_{k}\in\Omega(\mathcal{O}_{m},\sigma_{n})\subset Y^{V_{n}}$
such that

$\Omega(\mathcal{O}_{m},\sigma_{n})\subset\bigcup_{i=1}^{k}\mathrm{B}(\frac{s}{2L_{m}\lvert
D_{m}\rvert},y_{i}).$

So for every $y\in\Omega(\mathcal{O}_{m},\sigma_{n})$ there is some
$i\in\\{1,\ldots,k\\}$ such that
$\textrm{d}_{Y}^{(V_{n})}(y_{i},y)<\frac{s}{2L_{m}\lvert D_{m}\rvert}$. By the
almost-Lipschitz property of $\psi_{2,m}^{\sigma_{n}}$ restricted to
$\Omega(\mathcal{O}_{m},\sigma_{n})$, as long as $n$ is large enough we have

$\textrm{d}_{Y}^{(V_{n})}\big{(}\psi_{2,m}^{\sigma_{n}}(y_{i}),\,\psi_{2,m}^{\sigma_{n}}(y)\big{)}\leq\frac{s}{2}+L_{m}\lvert
D_{m}\rvert\,\textrm{d}_{Y}^{(V_{n})}(y_{i},y)\leq s.$

Hence

$\psi_{2,m}^{\sigma_{n}}\big{(}\Omega(\mathcal{O}_{m},\sigma_{n})\big{)}\subset\bigcup_{i=1}^{k}\mathrm{B}(s,\psi_{2,m}^{\sigma_{n}}(y_{i})),$

and using a standard bound on the size of a radius-$s$ Hamming ball we get

$\displaystyle\left\lvert\psi_{2,m}^{\sigma_{n}}\big{(}\Omega(\mathcal{O}_{m},\sigma_{n})\big{)}\right\rvert$
$\displaystyle\leq\exp\big{(}\lvert
V_{n}\rvert(\tfrac{C}{4}+\operatorname{H}(s)+s\log\lvert B\rvert+o(1))\big{)}$
$\displaystyle\leq\exp\big{(}\lvert V_{n}\rvert(\tfrac{C}{2}+o(1))\big{)}$

where in the second line we use our defining property of $s$. Now this set
$\psi_{2,m}^{\sigma_{n}}\big{(}\Omega(\mathcal{O}_{m},\sigma_{n})\big{)}$
contains $1-o(1)$ of the mass of
$(\psi_{2,m}^{\sigma_{n}}\circ\psi_{1,m}^{\sigma_{n}})_{*}\mu_{n}$. Since
$(\sigma_{n})_{n}$ is a sofic approximation and $\psi_{1,m},\psi_{2,m}$ are
local functions, we have

$\max\big{\\{}\textrm{d}^{(V_{n})}\big{(}\psi_{2,m}^{\sigma_{n}}\circ\psi_{1,m}^{\sigma_{n}}(x),\,(\psi_{2,m}\circ\psi_{1,m}^{\Gamma})^{\sigma_{n}}(x)\big{)}\,:\,x\in\mathtt{A}^{V_{n}}\big{\\}}=o(1).$

This means a radius-$o(1)$ neighborhood of
$\psi_{2,m}^{\sigma_{n}}\big{(}\Omega(\mathcal{O}_{m},\sigma_{n})\big{)}$
contains $1-o(1)$ of the mass of

$(\psi_{2,m}\circ\psi_{1,m}^{\Gamma})^{\sigma_{n}}_{*}\mu_{n}=(\psi_{m}^{\sigma_{n}})_{*}\mu_{n},$

which combined with the above estimate gives

$\limsup_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\operatorname{H}((\psi_{m}^{\sigma_{n}})_{*}\mu_{n})\leq\frac{C}{2}.$

But $(\psi_{m})_{m}$ is an AL approximation sequence to $\phi$, so must
satisfy (8) for all large $m$. This contradicts the above, so it must be that
$\operatorname{h}_{\Sigma}(Y^{\Gamma},\nu)>0$. ∎

###  5 Shattering

Let $(\mathtt{A}^{\Gamma},\mu,T)$ be a shift $\Gamma$-system and
$\Sigma=(\sigma_{n})_{n}$ a sofic approximation, where
${\sigma_{n}:\Gamma\to\operatorname{Sym}(V_{n})}$. On each model space
$\mathtt{A}^{V_{n}}$ we have the normalized Hamming distance defined by

$\textrm{d}^{(V_{n})}(\mathbf{x},\mathbf{y})=|V_{n}|^{-1}|\\{v\in
V_{n}:~{}\mathbf{x}(v)\neq\mathbf{y}(v)\\}|.$

In this section we derive ergodic-theoretic consequences from the following
phenomenon, which is at the heart of our study of parity check shifts.

######  Definition 5.1.

The shift system has totally shattered microstate spaces along $\Sigma$ if (i)
it has microstates along $\Sigma$, and (ii) there exists a $\delta>0$ for
which the following holds. For every $\varepsilon>0$ there exist a weak∗
neighbourhood $\mathcal{O}$ of $\mu$ and a positive integer $n_{0}$ such that,
for any $n\geq n_{0}$ and any two microstates
$\mathbf{x},\mathbf{y}\in\Omega(\sigma_{n},\mathcal{O})$, we have

$\hbox{either}\quad\textrm{d}^{(V_{n})}(\mathbf{x},\mathbf{y})\geq\delta\quad\hbox{or}\quad\textrm{d}^{(V_{n})}(\mathbf{x},\mathbf{y})<\varepsilon.$

We refer to any such $\delta$ as a shatter distance for the system along
$\Sigma$.

####  5.1 Consequences of shattering

In this section, fix a sofic approximation $\Sigma=(\sigma_{n})_{n}$ by
homomorphisms, and assume that $(\mathtt{A}^{\Gamma},\mu,T)$ has totally
shattered microstate spaces along $\Sigma$.

######  Theorem 5.2.

For every $\varepsilon>0$ there is a neighbourhood $\mathcal{O}$ of $\mu$ for
which the following holds. Let $(\mathtt{B}^{\Gamma},\nu,T)$ be another shift
system that has microstates along $\Sigma$, let
$(\mathtt{K}^{\Gamma},\kappa^{\Gamma},T)$ be a Bernoulli shift, and let

$\phi:\mathtt{B}^{\Gamma}\times\mathtt{K}^{\Gamma}\to\mathtt{A}$

be a measurable map. If

$\phi^{\Gamma}_{\ast}(\nu\times\kappa^{\Gamma})\in\mathcal{O}$ (9)

then

$(\nu\times\kappa^{\Gamma}\times\kappa^{\Gamma})\\{(y,z,z^{\prime}):\
\phi(y,z)\neq\phi(y,z^{\prime})\\}<\varepsilon.$ (10)

Intuitively, the conclusion is that if $\phi^{\Gamma}$ is approximately a
factor map onto $(\mathtt{A}^{\Gamma},\mu,T)$, then it must be approximately
independent from the second coordinate in
$\mathtt{B}^{\Gamma}\times\mathtt{K}^{\Gamma}$. There are many ways to capture
the latter assertion precisely, but (10) turns out to be convenient during the
proof.

The proof of Theorem 5.2 has much in common with the main proof in [32]. In
that paper, Gamarnik and Sudan used a relative of shattering to prove an
a.a.s. upper bound on the maximum size of an independent set on a random
regular graph that can be constructed using a local algorithm. The property
they use there is now called the ‘overlap gap property,’ and is actually a
little weaker than being totally shattered. See [31] for a recent survey. The
reference [41, Section 4] explains how the absence of an approximating local
algorithm for certain combinatorial problems implies that a resulting limit
process is not weakly contained in a Bernoulli shift.

Our proof of Theorem 5.2 needs a couple of known facts about microstate spaces
for a product in which one factor is Bernoulli. We recall these as separate
lemmas before starting the proof.

######  Lemma 5.3.

Let $(\mathtt{B}^{\Gamma},\nu,T)$ be a shift system and let
$(\mathtt{L}^{\Gamma},\lambda^{\Gamma},T)$ a Bernoulli shift. Assume that
$\mathbf{y}_{n}\in\mathtt{B}^{V_{n}}$ is a sequence such that
$P^{\sigma_{n}}_{\mathbf{y}_{n}}\to\nu$. Then

$\lambda^{V_{n}}\big{\\{}\mathbf{z}:\
P^{\sigma_{n}}_{(\mathbf{y}_{n},\mathbf{z})}\in\mathcal{O}\big{\\}}\to 1$

for every neighbourhood $\mathcal{O}$ of $\nu\times\lambda^{\Gamma}$. ∎

Lemma 5.3 is well-known as folklore in the study of sofic entropy, and a full
proof can be found inside the proofs of some of its consequences in the
literature. The earliest and perhaps easiest to extract is inside the proof of
the lower bound in [11, Theorem 8.1].

The next lemma is more specialized, but was also used in the second author’s
previous counterexample to the weak Pinsker conjecture for some sofic groups:
it is a special case of [16, Proposition 7.9]. It refers to ‘hereditary’
neighbourhoods of a shift-invariant measure. We do not repeat the definition
of these here; the only property we need is that they form a basis for the
weak∗ topology.

######  Lemma 5.4.

Let $\mathcal{U}\subset\mathcal{V}$ be open neighborhoods of
$\nu\times\kappa^{\Gamma}$ with $\mathcal{U}$ hereditary and $\mathcal{V}$
containing the closure of $\mathcal{U}$. For every $\delta>0$, if $n$ is large
enough, then for every $\mathbf{z},\mathbf{z}^{\prime}\in\mathtt{K}^{V_{n}}$
and $\mathbf{y}\in Y^{V_{n}}$, if
$(\mathbf{y},\mathbf{z}),\,(\mathbf{y},\mathbf{z}^{\prime})$ are in
$\Omega(\sigma_{n},\mathcal{U})$ then they are $\delta$-connected within
$\Omega(\sigma_{n},\mathcal{V})$ (this means there are
$\mathbf{w}_{1},\ldots,\mathbf{w}_{k}\in\Omega(\sigma_{n},\mathcal{V})$ with
$\mathbf{w}_{1}=(\mathbf{y},\mathbf{z})$,
$\mathbf{w}_{k}=(\mathbf{y},\mathbf{z}^{\prime})$ and
$d^{(V_{n})}(\mathbf{w}_{i},\mathbf{w}_{i+1})<\delta$ for all $i$). ∎

###### Proof of Theorem 5.2.

Let $\delta$ be a shatter distance for the system along $\Sigma$. Let
$\varepsilon>0$ be small enough that $2\varepsilon<\delta$, and now let
$\mathcal{O}_{1}$ and $n_{0}$ be a neighbourhood and positive integer as
promised by Definition 5.1 for this choice of $\varepsilon$. Lastly choose a
smaller neighbourhood $\mathcal{O}$ of $\mu$ whose closure is contained in
$\mathcal{O}_{1}$.

Let $\phi:\mathtt{B}^{\Gamma}\times\mathtt{K}^{\Gamma}\to\mathtt{A}$ be a
measurable map such that
$\phi_{\ast}^{\Gamma}(\nu\times\kappa^{\Gamma})\in\mathcal{O}$. In the rest of
the proof we show that (10) holds for this $\mathcal{O}$ and with
$3\varepsilon$ in place of $\varepsilon$.

_Step 1._ Since $\mathtt{A}$ is finite and $\phi$ is measurable, for any
$\eta>0$ there is an approximating map

$\psi:\mathtt{B}^{\Gamma}\times\mathtt{K}^{\Gamma}\to\mathtt{A}$

such that

$(\nu\times\kappa^{\Gamma})\\{\psi\neq\phi\\}<\eta$ (11)

and such that (i) $\psi$ is a local map and (ii) $\psi$ depends on the
coordinates in $\mathtt{K}^{\Gamma}$ only through some finite measurable
partition $\mathcal{P}$ of $\mathtt{K}$. If we choose $\eta$ sufficiently
small in terms of $\mathcal{O}\subset\mathcal{O}_{1}$ and $\varepsilon$, then
(9) and (11) imply that $\psi^{\Gamma}_{\ast}(\nu\times\kappa^{\Gamma})$ still
lies in $\mathcal{O}$, and also (11) implies that the desired conclusion (10)
holds for $\phi$ with error $3\varepsilon$ if it holds for $\psi$ with error
$2\varepsilon$.

By replacing $\mathtt{K}$ with the set of cells $\mathcal{P}$, we have
therefore reduced our work to the case when $\mathtt{K}$ is finite and $\phi$
is $F$-local for some finite subset $F$ of $\Gamma$. We assume this for the
rest of the proof, and do not refer to $\psi$ again.

Having made these assumptions, let us note that the set

$\Delta:=\\{(y,z,z^{\prime}):\ \phi(y,z)\neq\phi(y,z^{\prime})\\}$

is closed and open in
$\mathtt{B}^{\Gamma}\times\mathtt{K}^{\Gamma}\times\mathtt{K}^{\Gamma}$.

_Step 2._ Since $\phi$ is local, pushing forward by the equivariant map
$\phi^{\Gamma}$ acts continuously on probability measures. We may therefore
choose a neighbourhood $\mathcal{V}$ of $\nu\times\kappa^{\Gamma}$ such that
$\phi^{\Gamma}_{\ast}[\mathcal{V}]\subset\mathcal{O}$. Since $\sigma_{n}$ is a
homomorphism we have
$P_{\phi^{\sigma_{n}}(\mathbf{x})}^{\sigma_{n}}=\phi^{\Gamma}_{*}P_{\mathbf{x}}^{\sigma_{n}}$,
so this implies that

$\phi^{\sigma_{n}}[\Omega(\sigma_{n},\mathcal{V})]\subset\Omega(\sigma_{n},\mathcal{O})\quad\hbox{for
every}\ n.$ (12)

In addition, since hereditary neighbourhoods form a basis, we may let
$\mathcal{U}$ be a hereditary neighbourhood of $\nu\times\kappa^{\Gamma}$
whose closure is contained in $\mathcal{V}$.

_Step 3._ By assumption, there is a sequence
$\mathbf{y}_{n}\in\mathtt{B}^{V_{n}}$ such that
$P^{\sigma_{n}}_{\mathbf{y}_{n}}\to\nu$. Fix this for the rest of the proof.

For each $n$, consider $\mathbf{z}_{n}$ and
$\mathbf{z}_{n}^{\prime}\in\mathtt{K}^{V_{n}}$ drawn independently at random
according to $\kappa^{V_{n}}$, and consider the event

$E:=\big{\\{}(\mathbf{z}_{n},\mathbf{z}_{n}^{\prime})\in\mathtt{K}^{V_{n}}\times\mathtt{K}^{V_{n}}:\
(\mathbf{y}_{n},\mathbf{z}_{n}),(\mathbf{y}_{n},\mathbf{z}_{n}^{\prime})\in\Omega(\sigma_{n},\mathcal{U})\big{\\}}.$

By Lemma 5.3, we have

$(\kappa^{V_{n}}\times\kappa^{V_{n}})(E)\to 1.$ (13)

When $E$ occurs, we can draw the following additional conclusions:

  * •

The points $(\mathbf{y}_{n},\mathbf{z}_{n})$ and
$(\mathbf{y}_{n},\mathbf{z}_{n}^{\prime})$ are $(\delta/|F|)$-connected within
$\Omega(\sigma_{n},\mathcal{V})$ for all sufficiently large $n$ (not depending
on the specific values of $\mathbf{y}_{n}$, $\mathbf{z}_{n}$ or
$\mathbf{z}_{n}^{\prime}$), by Lemma 5.4.

  * •

Since $\phi$ is $F$-local, the map $\phi^{\sigma_{n}}$ is $|F|$-Lipschitz for
the normalized Hamming metrics (Lemma 2.1), so
$\phi^{\sigma_{n}}(\mathbf{y}_{n},\mathbf{z}_{n})$ and
$\phi^{\sigma_{n}}(\mathbf{y}_{n},\mathbf{z}_{n}^{\prime})$ both lie in
$\Omega(\sigma_{n},\mathcal{O})$ and are $\delta$-connected within that set,
by the previous conclusion and (12).

  * •

By total shattering and our choice of $\mathcal{O}$, we can now deduce that

$\textrm{d}^{(V_{n})}\big{(}\phi^{\sigma_{n}}(\mathbf{y}_{n},\mathbf{z}_{n}),\phi^{\sigma_{n}}(\mathbf{y}_{n},\mathbf{z}_{n}^{\prime})\big{)}<\varepsilon$
(14)

for all sufficiently large $n$. Indeed, if $n$ is large enough and

$\phi^{\sigma_{n}}(\mathbf{y}_{n},\mathbf{z}_{n})=\mathbf{w}_{1},\ \dots,\
\mathbf{w}_{l}=\phi^{\sigma_{n}}(\mathbf{y}_{n},\mathbf{z}_{n}^{\prime})$

is a sequence in $\Omega(\sigma_{n},\mathcal{O})$ with all consecutive
distances less than $\delta$, then total shattering implies that all of these
distances are actually less than $\varepsilon$. Then the triangle inequality
implies that
$\textrm{d}^{(V_{n})}(\mathbf{w}_{1},\mathbf{w}_{3})<2\varepsilon$, which is
still less than $\delta$. We may therefore invoke total shattering again to
conclude that in fact
$\textrm{d}^{(V_{n})}(\mathbf{w}_{1},\mathbf{w}_{3})<\varepsilon$. Now a
simple induction shows that in fact
$\textrm{d}^{(V_{n})}(\mathbf{w}_{1},\mathbf{w}_{i})<\varepsilon$ for every
$i$, giving (14) when $i=l$.

Unpacking the definitions of normalized Hamming metric and empirical
distribution, the left-hand side of (14) is equal to

$\frac{1}{|V_{n}|}\sum_{v\in
V_{n}}1_{\left\\{\phi(\Pi^{\sigma_{n}}_{v}\mathbf{y}_{n},\Pi^{\sigma_{n}}_{v}\mathbf{z}_{n})\neq\phi(\Pi^{\sigma_{n}}_{v}\mathbf{y}_{n},\Pi^{\sigma_{n}}_{v}\mathbf{z}_{n}^{\prime})\right\\}}=P^{\sigma_{n}}_{(\mathbf{y}_{n},\mathbf{z}_{n},\mathbf{z}_{n}^{\prime})}(\Delta).$

Therefore, in view of the conclusions above, (13) implies that

$(\kappa^{V_{n}}\times\kappa^{V_{n}})\big{\\{}P^{\sigma_{n}}_{(\mathbf{y}_{n},\mathbf{z}_{n},\mathbf{z}_{n}^{\prime})}(\Delta)<\varepsilon\big{\\}}\to
1.$ (15)

On the other hand, since $\Delta$ is a closed and open set, another appeal to
Lemma 5.3 (this time for the larger product
$\nu\times\kappa^{\Gamma}\times\kappa^{\Gamma}$) shows that

$(\kappa^{V_{n}}\times\kappa^{V_{n}})\big{\\{}P^{\sigma_{n}}_{(\mathbf{y}_{n},\mathbf{z}_{n},\mathbf{z}_{n}^{\prime})}(\Delta)>(\nu\times\kappa^{\Gamma}\times\kappa^{\Gamma})(\Delta)-\epsilon\big{\\}}\to
1.$ (16)

The limits (15) and (16) can hold simultaneously only if

$(\nu\times\kappa^{\Gamma}\times\kappa^{\Gamma})(\Delta)<2\varepsilon.$

Since $\varepsilon$ was arbitrary, this completes the proof. ∎

Theorem 5.2 has several more streamlined consequences.

######  Corollary 5.5.

Suppose that $(\mathtt{A}^{\Gamma},\mu,T)$ has totally shattered microstate
spaces along $\Sigma$.

  1. 1.

If $(\mathtt{B}^{\Gamma},\nu,T)$ is another shift system that has microstates
along $\Sigma$, and $(\mathtt{K}^{\Gamma},\kappa^{\Gamma},T)$ is a Bernoulli
shift, then any factor map

$(\mathtt{B}^{\Gamma}\times\mathtt{K}^{\Gamma},\nu\times\kappa^{\Gamma},T)\to(\mathtt{A}^{\Gamma},\mu,T)$

factorizes through the coordinate projection from
$\mathtt{B}^{\Gamma}\times\mathtt{K}^{\Gamma}$ to $\mathtt{B}^{\Gamma}$.

  2. 2.

The system $(\mathtt{A}^{\Gamma},\mu,T)$ has no non-trivial direct Bernoulli
factors.

  3. 3.

The system $(\mathtt{A}^{\Gamma},\mu,T)$ is not weakly contained in a
Bernoulli shift unless it is actually a trivial system, meaning that
$\mu=\delta_{(\dots,a,a,\dots)}$ for some $a\in\mathtt{A}$.

###### Proof.

_Part 1._ If $\phi^{\Gamma}$ is the factor map in question, then the identity-
coordinate map $\phi$ satisfies hypothesis (9) for every neighbourhood
$\mathcal{O}$. Therefore, by Theorem 5.2, it also satisfies (10) for every
$\varepsilon>0$, and so in fact

$\phi(y,z)=\phi(y,z^{\prime})\quad\hbox{for}\
(\nu\times\kappa^{\Gamma}\times\kappa^{\Gamma})\hbox{-a.e.}\
(y,z,z^{\prime}).$

This implies that, up to agreement a.e., $\phi$ depends only on the first
coordinate in $\mathtt{B}^{\Gamma}\times\mathtt{K}^{\Gamma}$.

_Part 2._ Assume that

$\phi^{\Gamma}:(\mathtt{B}^{\Gamma},\nu,T)\times(\mathtt{K}^{\Gamma},\kappa^{\Gamma},T)\to(\mathtt{A}^{\Gamma},\mu,T)$

is an isomorphism. Then $(\mathtt{B}^{\Gamma},\nu,T)$ is a factor of
$(\mathtt{A}^{\Gamma},\mu,T)$. Since $(\mathtt{A}^{\Gamma},\mu,T)$ has
microstates along $\Sigma$, so does $(\mathtt{B}^{\Gamma},\nu,T)$. Therefore
we may apply Part 1 to conclude that $\phi^{\Gamma}$ is actually independent
of the Bernoulli factor. Since $\phi^{\Gamma}$ is an isomorphism, this is
possible if and only if that Bernoulli factor is trivial.

_Part 3._ Towards a contradiction, suppose that
$(\mathtt{K}^{\Gamma},\kappa^{\Gamma},T)$ is a Bernoulli shift and that
$\phi_{m}:\mathtt{K}^{\Gamma}\to\mathtt{A}$ is a sequence of measurable maps
such that

$\phi^{\Gamma}_{m\ast}\kappa^{\Gamma}\to\mu.$ (17)

Apply Theorem 5.2 by inserting a trivial one-point system in the place of
$(\mathtt{B}^{\Gamma},\nu,T)$. The conclusion is that

$(\kappa^{\Gamma}\times\kappa^{\Gamma})\\{(z,z^{\prime}):\
\phi_{m}(z)\neq\phi_{m}(z^{\prime})\\}\to 0.$

However, this implies that the distribution of $\phi_{m}$ is converging to
$\delta_{a}$ for some $a\in\mathtt{A}$. Combined with (17), it follows that
$\mu=\delta_{(\dots,a,a,\dots)}$. ∎

####  5.2 Shattering and Bernoulli splittings

Suppose the shift system $(\mathtt{A}^{\Gamma},\mu,T)$ has totally shattered
microstate spaces along $\Sigma$. Note as soon as $\varepsilon<\delta/2$, if
$\mathcal{O}$ is the neighborhood of $\mu$ given by the definition then the
relation “$\textrm{d}^{(V_{n})}<\delta$” restricted to the microstate space
$\Omega(\sigma_{n},\mathcal{O})$ is an equivalence relation, so it partitions
the microstate space into small-diameter, well-separated clusters.

In this section, we give a second proof of Corollary 5.5(2) and sketch a
third. Both of these approaches are based on the clusters of microstates: one
uses the number of clusters, which is one of the sofic homological invariants
introduced in [16], and the other uses the sizes of clusters. Both can be
compared to the use of the “overlap gap property” introduced in [32] to prove
an a.a.s. upper bound on the size of an independent set on a random regular
graph, when the independent set is required to be constructed from a local
algorithm.

The size of clusters can be used as follows: if a direct Bernoulli factor
exists, it can be shown that its entropy rate is a uniform lower bound for the
exponential size of all microstate clusters, while if a system has totally
shattered microstate spaces then all its clusters are of subexponential size.
This implies Corollary 5.5(2).

In the rest of the section, we give a proof using the number of clusters.
First, we give relevant definitions.

If $\mathcal{O}$ is a subset of a metric space and $x,y\in\mathcal{O}$, we say
$x,y$ are $\delta$-connected within $\mathcal{O}$ if there is a sequence of
points $z_{1},\ldots,z_{l}\in\mathcal{O}$ with $z_{1}=x$, $z_{l}=y$, and
$\textrm{d}(z_{i},z_{i+1})<\delta$ for each $i$. This defines an equivalence
relation on $\mathcal{O}$, which we denote $\mathrm{cl}(\mathcal{O},\delta)$.

Given a map $\sigma\colon\Gamma\to\operatorname{Sym}(V)$, a labeling
$\mathbf{x}\in\mathtt{A}^{V}$, an open set
$\mathcal{O}\subset\operatorname{Prob}(\mathtt{A}^{\Gamma})$, and $\delta>0$,
let

$\mathrm{cl}(\sigma,\mathbf{x},\mathcal{O},\delta)=[x]_{\mathrm{cl}(\Omega(\sigma,\mathcal{O}),\delta)}=\\{\mathbf{z}\in\mathtt{A}^{V}\,:\,\mathbf{z}\text{
is $\delta$-connected to $\mathbf{x}$ within }\Omega(\sigma,\mathcal{O})\\}.$

where $\Omega(\sigma,\mathcal{O})\subset\mathtt{A}^{V}$ has the normalized
Hamming metric $\textrm{d}^{(V)}$. In particular,
$\mathrm{cl}(\sigma,\mathbf{x},\mathcal{O},\delta)\subset\Omega(\sigma,\mathcal{O})$.

Now if in addition to the above we have some
$\mathcal{O}^{\prime}\subset\mathcal{O}$, the quotient

${\left.\raisebox{1.99997pt}{$\Omega(\sigma_{n},\mathcal{O}^{\prime})$}\middle/\raisebox{-1.99997pt}{$\mathrm{cl}(\Omega(\sigma_{n},\mathcal{O}),\,\delta)$}\right.}$

is the set of clusters of $\mathcal{O}^{\prime}$-microstates that are
$\delta$-connected within $\Omega(\sigma_{n},\mathcal{O})$. We define

$b_{0,\Sigma}(\mu)=\sup_{\mathcal{O}\ni\mu}\sup_{\delta>0}\inf_{\mu\in\mathcal{O}^{\prime}\subset\mathcal{O}}\limsup_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert{\left.\raisebox{1.99997pt}{$\Omega(\sigma_{n},\mathcal{O}^{\prime})$}\middle/\raisebox{-1.99997pt}{$\mathrm{cl}(\Omega(\sigma_{n},\mathcal{O}),\,\delta)$}\right.}\right\rvert.$

Informally, we first set coarseness parameters $\mathcal{O},\delta$ which
divide microstate spaces into clusters. We consider the exponential growth
rate of the number of these clusters which contain $\mathcal{O}^{\prime}$-good
microstates for $\mu$. At first, it might seem more natural to consider
directly the growth rate of the number of $\delta$-connected clusters within a
single $\Omega(\sigma_{n},\mathcal{O})$:

$\limsup_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert{\left.\raisebox{1.99997pt}{$\Omega(\sigma_{n},\mathcal{O})$}\middle/\raisebox{-1.99997pt}{$\mathrm{cl}(\Omega(\sigma_{n},\mathcal{O}),\,\delta)$}\right.}\right\rvert,$

then take $\delta$ to $0$ and in some sense $\mathcal{O}$ to $\mu$. But there
is no monotonicity in $\mathcal{O}$: shrinking the neighborhood of $\mu$
removes some microstates from $\Omega(\sigma_{n},\mathcal{O})$, but this can
both remove some clusters and/or break a cluster into multiple pieces.
Considering pairs $\mathcal{O}^{\prime}\subset\mathcal{O}$ is one natural way
around this. See also the discussion of a related definition of connected
model spaces in [4, Section 2.2].

In [16], $b_{0,\Sigma}(\mu)$ is called the $0$th Betti number of $\mu$. If $X$
is totally disconnected and $\mu\in\operatorname{Prob}^{\Gamma}(X^{\Gamma})$
then $b_{0,\Sigma}(\mu)$ is a measure-conjugacy invariant [16, Corollary 4.2].

It follows directly from the definition that
$b_{0,\Sigma}(\mu)\leq\operatorname{h}_{\Sigma}(\mu)$ (a similar inequality
holds for higher-dimensional sofic homology theories [16, Lemma 7.13]).

######  Lemma 5.6.

If $(\mathtt{A}^{\Gamma},\mu)$ has totally shattered microstate spaces over
$\Sigma$, then $b_{0,\Sigma}(\mu)=\operatorname{h}_{\Sigma}(\mu)$.

###### Proof.

Recall that in general $b_{0,\Sigma}(\mu)\leq\operatorname{h}_{\Sigma}(\mu)$,
so we only have to prove that having totally shattered microstate spaces
implies the reverse inequality.

Let $\delta>0$ be as in the definition of totally shattered microstate spaces.
Given $\varepsilon<\delta/2$, there exists a neighborhood $U$ of $\mu$ such
that for all large $n$, every $\mathbf{x},\mathbf{y}\in\Omega(\sigma_{n},U)$
have
$\textrm{d}^{(V_{n})}(\mathbf{x},\mathbf{y})\in[0,\varepsilon)\cup[\delta,\infty)$.
In particular, for every $\mathbf{x}\in\Omega(\sigma_{n},U)$

$\mathrm{cl}(\sigma_{n},\mathbf{x},U,\varepsilon)\subseteq\mathrm{B}(\varepsilon,\mathbf{x}),$

where $\mathrm{B}(\varepsilon,\mathbf{x})$ is the radius-$\varepsilon$ ball
around $\mathbf{x}$. Thus

$\lvert\mathrm{cl}(\sigma_{n},\mathbf{x},U,\varepsilon)\rvert\leq\lvert\mathrm{B}(\varepsilon,\mathbf{x})\rvert\leq\exp\big{(}\lvert
V_{n}\rvert(\operatorname{H}(\varepsilon)+\varepsilon\log\lvert\mathtt{A}\rvert+o(1))\big{)}.$

This leads to a lower bound on the number of clusters for all
$\mathcal{O}^{\prime}\subset U$:

$\left\lvert{\left.\raisebox{1.99997pt}{$\Omega(\sigma_{n},\mathcal{O}^{\prime})$}\middle/\raisebox{-1.99997pt}{$\mathrm{cl}(\Omega(\sigma_{n},U),\,\varepsilon)$}\right.}\right\rvert\geq\lvert\Omega(\sigma_{n},\mathcal{O}^{\prime})\rvert\exp\big{(}-\lvert
V_{n}\rvert(\operatorname{H}(\varepsilon)+\varepsilon\log\lvert\mathtt{A}\rvert+o(1))\big{)}.$

Hence

$\inf_{\mu\in\mathcal{O}^{\prime}\subset U}\limsup_{n\to\infty}\frac{1}{\lvert
V_{n}\rvert}\log\left\lvert{\left.\raisebox{1.99997pt}{$\Omega(\sigma_{n},\mathcal{O}^{\prime})$}\middle/\raisebox{-1.99997pt}{$\mathrm{cl}(\Omega(\sigma_{n},U),\,\varepsilon)$}\right.}\right\rvert\geq\operatorname{h}_{\Sigma}(\mu)-\big{(}\operatorname{H}(\varepsilon)+\varepsilon\log\lvert\mathtt{A}\rvert\big{)},$

and taking the supremum over $\varepsilon>0$ and $U\ni\mu$ completes the
proof. ∎

###### Alternate proof of Cor. 5.5(2).

To obtain a contradiction suppose that $(\mathtt{A}^{\Gamma},\mu,T)$ is
measurably conjugate to the direct product of a nontrivial Bernoulli shift
$(\mathtt{K}^{\Gamma},\kappa^{\Gamma},T)$ with another shift system
$(\mathtt{B}^{\Gamma},\nu,S)$ where $\mathtt{B}$ is a compact metrizable
space. We may assume $\mathtt{B}$ is totally disconnected without loss of
generality because any dynamical system is measurably conjugate to a system of
this form; this assumption is used in results of [16] cited below.

It is well-known that sofic entropy is additive under taking direct products
with a Bernoulli shift [11, Theorem 8.1]. So

$\displaystyle\operatorname{h}_{\Sigma}(\mathtt{A}^{\Gamma},\mu,T)=\operatorname{H}(\mathtt{K},\kappa)+\operatorname{h}_{\Sigma}(\mathtt{B}^{\Gamma},\nu,S)>\operatorname{h}_{\Sigma}(\mathtt{B}^{\Gamma},\nu,S).$
(18)

Theorem 7.8 of [16] implies that the $0$-dimensional sofic homology theories
of $(\mathtt{A}^{\Gamma},\mu,T)$ and $(\mathtt{B}^{\Gamma},\nu,S)$ are
equivalent. In particular, this implies that the exponential rate of growth of
the number of clusters in the microstate spaces of the two actions are the
same. In the notation of [16], this means

$b_{0,\Sigma}(\mathtt{A}^{\Gamma},\mu,T)=b_{0,\Sigma}(\mathtt{B}^{\Gamma},\nu,S)\leq\operatorname{h}_{\Sigma}(\mathtt{B}^{\Gamma},\nu,S)$

where the last inequality holds by [16, Lemma 7.13].

Because $(\mathtt{A}^{\Gamma},\mu,T)$ has totally shattered microstate spaces,
by Lemma 5.6 we have
$b_{0,\Sigma}(\mathtt{A}^{\Gamma},\mu,T)=\operatorname{h}_{\Sigma}(\mathtt{A}^{\Gamma},\mu,T)$.
Combined with the previous inequality this implies

$\operatorname{h}_{\Sigma}(\mathtt{A}^{\Gamma},\mu,T)=b_{0,\Sigma}(\mathtt{A}^{\Gamma},\mu,T)\leq\operatorname{h}_{\Sigma}(\mathtt{B}^{\Gamma},\nu,S)$

which contradicts (18). This contradiction finishes the proof. ∎

##  Part II Parity check subshifts

In this part, we fix natural numbers $d,k$ with $k>d\geq 3$ and let
$\Gamma=\Gamma_{d,k}$ be the $d$-fold free product of order-$k$ cyclic groups:

$\Gamma:=\langle s_{1},\dots,s_{d}:\
s_{1}^{k}=\dots=s_{d}^{k}=e\rangle=\underbrace{\mathbb{Z}_{k}\ast\cdots\ast\mathbb{Z}_{k}}_{d}.$

Let $X\leq\mathbb{Z}_{2}^{\Gamma}$ be the closed subgroup defined by

$X=\left\\{x\in\mathbb{Z}_{2}^{\Gamma}:\ \sum_{j=0}^{k-1}x_{gs_{i}^{j}}=0\
\forall g\in\Gamma,\ i=1,\dots,d\right\\},$

and let $\mu=m_{X}$ be the Haar probability measure on $X$.

If $F$ is any subset of $\Gamma$, let $X_{F}$ be the image of $X$ under the
coordinate projection map $\mathbb{Z}_{2}^{\Gamma}\to\mathbb{Z}_{2}^{F}$, and
let $m_{F}$ be the pushforward of $m_{X}$ under this projection. We mostly use
these notations when $F$ is $B_{r}$, the ball of radius $r$ centered at the
identity in the Cayley graph of $\Gamma$, where we use $\\{s_{i}^{j}:~{}1\leq
i\leq d,1\leq j\leq k-1\\}$ for the generating set.

###  6 LDPC codes and measures on microstate spaces

####  6.1 The use of LDPC codes

Our proofs of the main theorems are considerably simplified by using the
special structure of the system as a subgroup of $\mathbb{Z}_{2}^{\Gamma}$. We
largely do so via the corresponding finitary codes constructed over the sofic
approximations. Given a $k$-uniform homomorphism
$\sigma:\Gamma_{d,k}\to\operatorname{Sym}(V)$, let

$X_{\sigma}:=\left\\{\mathbf{x}\in\mathbb{Z}_{2}^{V}:\
\sum_{j=0}^{k-1}x_{\sigma_{i}^{j}(v)}=0\ \forall v\in V,\
i=1,\dots,d\right\\}.$

Let $\mu_{\sigma}$ be the uniform distribution on $X_{\sigma}$.

These are the obvious finitary analogs of $X$ and $m_{X}$ themselves. It turns
out that these finitary constructs can be used as better and better
approximations to the infinitary system and measure, and their linear
structure makes them easier to analyze than the ‘looser’ sets
$\Omega(\sigma,U)$ that are used to define sofic entropy.

In fact, sets such as $X_{\sigma}$ are classical objects in coding theory.
They are linear codes over the field $\mathbb{Z}_{2}$, each defined by a
collection of parity-check constraints. Since each of those parity-checks
involves only $k$ vertices, and $k$ is fixed as $n$ grows, these are examples
of low-density parity-check (‘LDPC’) codes. Such codes were introduced in
Gallager’s PhD thesis [30, 29]. After many years of relative neglect, they
were re-discovered independently by MacKay in the late 1990s [42], and they
are now a textbook family of codes with desirable properties. A good basic
reference for their theory is [43, Chapter 47], and a more dedicated treatment
is [56]. In fact, the essence of the parity-check subshift $X$ itself already
appears in those sources too, playing the role of an ‘idealized limit code’ on
which to investigate the performance of local decoding algorithms: see, for
instance, [43, Figure 47.11] and the discussion around it.

####  6.2 Outline of the rest of the paper

Our use of the measures $\mu_{\sigma}$ to analyze the system $(X,m_{X},T)$
rests on the following main results. As before, we confine the index $n$ to
multiples of $k$. Abbreviate $X_{\sigma_{n}}$ to $X_{n}$ and
$\mu_{\sigma_{n}}$ to $\mu_{n}$.

Recall that $\mathbb{P}_{n}$ is the uniform probability measure on
$\operatorname{Hom}_{\mathrm{unif}}(\Gamma,\operatorname{Sym}(n))$ which is
the set of $k$-uniform homomorphisms $\sigma:\Gamma\to\operatorname{Sym}(n)$.

######  Theorem 6.1.

There are subsets

$\Omega^{\prime}_{n}\subseteq\operatorname{Hom}_{\mathrm{unif}}(\Gamma,\operatorname{Sym}(V_{n}))$

such that $\mathbb{P}_{n}(\Omega^{\prime}_{n})\to 1$ and the following holds.
If $\sigma_{n}\in\Omega_{n}^{\prime}$ for each $n$, then

  1. 1.

$(\mu_{n})_{n}$ has property M;

  2. 2.

$(\mu_{n})_{n}$ converges locally and empirically to $m_{X}$;

  3. 3.

$(X,m_{X},T)$ has totally shattered microstate spaces along
$\Sigma=(\sigma_{n})_{n}$.

Our proof of Theorem 6.1 relies on the linear structure of the codes
$X_{\sigma}$.

In the next few sections we introduce notation to formulate Proposition 7.1
which, roughly speaking, rules out near-cancellations among parity-check words
of a typical $\sigma_{n}\sim\mathbb{P}_{n}$. Section §7.1 proves Theorem
6.1(1) from Proposition 7.1. The rest of §7 proves Proposition 7.1.

Item (2) of Theorem 6.1 is proven in §8. Its proof relies on item (1). Item
(3) is proven in §10. Its proof does not refer to items (1) or (2). Theorem B
is an immediate consequence of item (3) and Corollary 5.5(2).

Theorem 1.3 is proven in §9. Part (b) of that theorem follows readily from
items (1) and (2) of Theorem 6.1 together with Theorem 4.3. Part (a) (which
computes the sofic entropy value) uses item (2) and the Bethe-Kikuchi entropy
theory of §3.

####  6.3 Random factor graphs

In this subsection, fix a size $n$ that is divisible by $k$ and suppress it
from the notation: thus, for instance, $\mathbb{P}$ stands for
$\mathbb{P}_{n}$. Most of our work towards Theorem 6.1 consists of estimates
of various probabilities under $\mathbb{P}$.

Several of these estimates involve a sum or union bound over possible
subfamilies of the set of all hyper-edges of the form (3). We need to be able
to move the sum outside an expectation, and for this purpose the sum must be
over a range which is fixed, not random. For this reason, it is convenient to
augment the information in $\sigma_{n}$ with a labeling of the family of
hyper-edges (3) by a fixed index set.

Let $E_{1}$, …, $E_{d}$ be disjoint sets, each of size $n/k$, and let
$E:=E_{1}\cup\cdots\cup E_{d}$. Taking some terminology from coding theory, we
refer to the elements of $E$ as check nodes: this is explained further in
Subsection 6.4 below. Let
$\sigma\in\operatorname{Hom}_{\mathrm{unif}}(\Gamma,\operatorname{Sym}(V))$
with $|V|=n$. Fix $i\in[d]$, and consider that $V$ is partitioned into the
orbits of the generator $\sigma(s_{i})$. Each orbit corresponds to a hyper-
edge as in (3). Since each hyper-edge has size $k$, there are $n/k$ of them,
and so there exists a bijection between $E_{i}$ and this family of hyper-
edges. Let us choose such a bijection uniformly and independently at randomly
for each $i$, and record the result as a subset $H\subseteq E\times V$: a pair
$(e,v)\in E_{i}\times V$ lies in $H$ if $e$ is attached by the
$i^{\mathrm{th}}$ bijection to the hyper-edge that contains $v$.

We regard $H$ as a bipartite graph on the disjoint union of $E$ and $V$. As
such, each check node in $E$ has exactly $k$ neighbours in $V$, and each
vertex in $V$ has exactly one neighbour in each of the subsets $E_{i}$ (and
thus $d$ neighbours in total). It follows that each intersection
$H\cap(E_{i}\times V)$ is equivalent to a partition of $V$ into parts labelled
by $E_{i}$. In the sequel, we borrow some more terminology from coding theory
and refer to any such bipartite graph $H$ on $E$ and $V$ as a factor graph:
see, for instance, [43, Sections 26.1 and 47.2]. Beware that this is actually
a slight deviation from standard usage, which would not insist that $H$ be a
union of the partitions $H\cap(E_{i}\times V)$, but here we do take this as
part of the definition of a ‘factor graph’.

More generally, if $F\subseteq E$, then a partial factor graph on $F$ and $V$
is a bipartite graph $M\subseteq F\times V$ such that every check node in $F$
has precisely $k$ neighbours in $V$ and every vertex in $V$ is joined to at
most one check node in each intersection $F\cap E_{i}$. Equivalently, there
exists a factor graph $H$ such that $M=H\cap(F\times V)$. In particular, if
$F=E_{i}$, then a partial factor graph is simply a partition of $V$ into
$k$-sets that are labelled by $E_{i}$.

If $H$ is a factor graph on $E$ and $V$ and $F\subseteq E$, then the vertex
neighbourhood of $F$ is the set

$\mathtt{Vert}(H;F):=\\{v\in V:\ (e,v)\in H\ \hbox{for some}\ e\in F\\}.$

We also use the notation $\mathtt{Vert}(M;F)$ for a partial factor graph $M$
in the same way.

Similarly, the check-node neighbourhood of $U\subseteq V$ is the set

$\mathtt{Check}(H;U):=\\{e\in E:\ (e,v)\in H\ \hbox{for some}\ v\in V\\}.$

We may iterate these definitions to define neighbourhoods with larger radii.
In general, for $F\subseteq E$ or $U\subseteq V$ we define

$\displaystyle\mathtt{Vert}_{1}(H;F)$ $\displaystyle:=$