$\displaystyle\mathtt{Vert}(H;F),$ $\displaystyle\mathtt{Check}_{1}(H;U)$
$\displaystyle:=$ $\displaystyle\mathtt{Check}(H;U),$
$\displaystyle\mathtt{Check}_{1}(H;F)$ $\displaystyle:=$
$\displaystyle\mathtt{Check}_{1}\big{(}\mathtt{Vert}_{1}(H;F)\big{)}$
$\displaystyle\hbox{and}\quad\mathtt{Vert}_{1}(H;U)$ $\displaystyle:=$
$\displaystyle\mathtt{Vert}_{1}\big{(}\mathtt{Check}_{1}(H;U)\big{)}.$

Then for integers $r>1$, we make the recursive definitions

$\mathtt{Vert}_{r}(H;F):=\mathtt{Vert}_{1}(H;\big{(}\mathtt{Vert}_{r-1}(H;F)\big{)},$

and the same with $U$ in place of $F$ or $\mathtt{Check}$ in place of
$\mathtt{Vert}$. In graph theoretic terms, if $F\subseteq E$, then
$\mathtt{Vert}_{r}(H;F)$ is the set of all vertices whose graph distance in
$H$ is at most $2r-1$ from $F$, $\mathtt{Check}_{r}(H;F)$ is the set of all
check nodes whose graph distance in $H$ is at most $2r$ from $F$, and
similarly for subsets of $V$.

These neighbourhoods are compatible with the Cayley graph neighbourhoods
$B_{r}=\mathrm{B}(e,r)$ induced by the word metric on $\Gamma$ (with respect
to the generating set $\\{s_{i}^{j}:~{}1\leq i\leq d,1\leq j\leq k-1\\})$.
Specifically, if $H$ arises from $\sigma$ through the construction above, and
$U\subseteq V$, then

$\sigma^{B_{r}}(U):=\\{\sigma^{g}(u):\ g\in B_{r},\ u\in
U\\}=\mathtt{Vert}_{r}(H;U).$

Now consider $\sigma\sim\mathbb{P}$ and generate $H$ from it as described
above. Then $H$ results from two random steps: the choice of $\sigma$, and
then the choice of a bijection for each $i$. Let $\tilde{\mathbb{P}}$ be the
joint distribution of $(\sigma,H)$ after this construction. This is a
probability measure on

$\tilde{\Omega}:=\operatorname{Hom}_{\mathrm{unif}}(\Gamma,\operatorname{Sym}(V))\times\\{0,1\\}^{E\times
V}.$

It is a coupling of $\mathbb{P}$ to the law of $H$ described above, and it has
the following simple properties:

  * •

Given $\sigma$, the conditional distribution of $H$ is uniform over
$((n/k)!)^{d}$ choices of bijections.

  * •

Given $H$, the conditional distribution of $\sigma$ is uniform over all
choices of cyclic orderings for each hyper-edge of the multi-hyper-graph:
there are ${((k-1)!)^{dn/k}}$ such choices for any $H$.

  * •

Under the marginal distribution of $H$, the intersections $H\cap(E_{i}\times
V)$ are independent as $i$ varies.

For $(\sigma,H)$ drawn from $\tilde{\mathbb{P}}$, the underlying multi-hyper-
graph may be read off from either coordinate: it is the multi-set of all
$\sigma(s_{i})$ orbits for $i\in[d]$, and it is also the collection of all
vertex neighbourhoods of the check nodes according to $H$. The labeling of
these hyper-edges by the fixed set $E$ that is given by $H$ is convenient for
union bounds and other forms of counting. Most of our probabilistic estimates
concerning these hyper-graphs later refer to $\tilde{\mathbb{P}}$ rather than
$\mathbb{P}.$

######  Remark.

The random hyper-graphs on $V$ that arise from $\sigma\sim\mathbb{P}$ are
$k$-uniform and $d$-regular.

Models of such random hyper-graphs already have an established place in the
literature on probabilistic combinatorics: see, for instance, [70, Subsection
3.5] and the references given there. However, most of that literature is
dedicated to a _uniform_ random choice of such a hyper-graph, and this is not
the same as the distribution that results from a random choice of $\sigma$.
The point is that if the hyper-graph is generated by a homomorphism $\sigma$,
then its hyper-edges can be classified according to which generator $s_{i}$
gave rise to them. For each single $i$, the corresponding hyper-edges form a
partition of $V$ into $k$ sets. In general, a $k$-uniform $d$-regular hyper-
graph need not be a union of partitions.

In case $k=2$, the difference here is between a uniformly random $d$-regular
graph and the sum of $d$ independent random matchings. In this case the
difference has been studied in some depth, with the outcome that these models
are ‘contiguous’: see, for instance, [33] or[70, Subsection 4.3]. The relation
of contiguity is strong enough to allow us to transfer most phenomena of
interest from one model to the other.

However, for $k>d\geq 3$, it turns out that contiguity fails. While we have
not found a reference for this fact in the literature, it follows fairly
easily from some other standard results, so we explain this in Appendix A.

For uniformly random $k$-uniform $d$-regular hyper-graphs, estimates on the
typical behaviour of the resulting LDPC codes are widely available in the
coding theory literature. For example, the typical rate of the resulting LDPC
code is known very exactly from [46] (we cite this in our proof of non-
contiguity in Appendix A). These known results would include most of the facts
we need here, were it not for the difference in the underlying random hyper-
graph model. However, we have not found the analogous estimates for our
distributions $\mathbb{P}$, so we must develop them here from scratch as
necessary. Nevertheless, the conclusions generally look the same as in those
previous works, and we have been guided by those throughout.

####  6.4 Parity-check matrices

To prove the desired properties of the random measures $\mu_{\sigma_{n}}$, we
make careful use of the linear structure of the codes $X_{n}$. As is standard
in coding theory, this structure is conveniently summarized by a parity-check
matrix.

To introduce this point of view, we start with some more notation. If a ground
set $A$ is understood and $B\subseteq A$, then $\mathbf{e}_{B}$ denotes the
mod-$2$ indicator function of $B$: this is the element of $\mathbb{Z}_{2}^{A}$
with entries equal to $\mathtt{1}$ precisely at the indices in $B$.

Now consider a vertex set $V$ of size $n$ which is a multiple of $k$, and let
$E=E_{1}\cup\cdots\cup E_{d}$ as in Subsection 3.1. Let $H$ be a factor graph
on $E$ and $V$, and turn it into the $(E\times V)$-matrix
$\mathbf{H}=\mathbf{e}_{H}$, which also takes values in $\mathbb{Z}_{2}$. If
this generates the same hyper-graph as
$\sigma\in\operatorname{Hom}_{\mathrm{unif}}(\Gamma,\operatorname{Sym}(V))$,
then our code is given by

$X_{\sigma}=\\{\mathbf{x}\in\mathbb{Z}_{2}^{V}:\
\mathbf{H}\mathbf{x}=\boldsymbol{0}\\}=\ker\mathbf{H}.$

In this role $\mathbf{H}$ is called the parity-check matrix (for an
introduction, see, for instance, [19, Chapter 9], [22, Section 7.11], or [43,
Chapter 1], especially the discussion of Exercise 1.9). This is why we refer
to the elements of $E$ as ‘check nodes’: each corresponds to a row of
$\mathbf{H}$, which every codeword $\mathbf{x}$ must be orthogonal to. The
representation of a code using a set of connections between vertices and check
nodes is a common example of a ‘factor graph representation’ [43, Section
47.2], hence our use of the term ‘factor graph’ for $H$.

Because $X_{\sigma}$ is a linear subspace of $\mathbb{Z}_{2}^{V}$, it may
equivalently be specified via its dual code

$X_{\sigma}^{\perp}:=\\{\mathbf{y}\in\mathbb{Z}_{2}^{V}:\
\langle\mathbf{y},\mathbf{x}\rangle=0\pmod{2}\ \forall\mathbf{x}\in
X_{\sigma}\\}.$

Below, we refer to elements of $X_{\sigma}^{\perp}$ as parity checks. By the
construction of $X_{\sigma}$, this $X_{\sigma}^{\perp}$ is precisely the
linear subspace of $\mathbb{Z}_{2}^{V}$ spanned by the rows of $\mathbf{H}$:
that is, by the vectors $\mathbf{e}_{\mathtt{Vert}(H;\\{e\\})}$ for $e\in E$.
More succinctly,

$X_{\sigma}^{\perp}=\mathrm{img}\,(\mathbf{H}^{\mathsf{T}}).$

Theorem 6.1 (1,2) are proved by counting relations or ‘near relations’ among
the rows of $\mathbf{H}$. The second of these theorems requires the more
complicated calculation. It is based on Proposition 7.1 below. With that
proposition in hand, we can also prove Theorem 6.1(2); see Section 8.

###  7 Property M

In this section we again suppress the subscript $n$ from our notation, as in
Subsection 6.3. As before this index will tend to $\infty$ along multiples of
$k$.

The main part of the proof of Theorem 6.1 parts (1) and (2) is another, more
technical proposition. Put roughly, it rules out most ‘near cancellations’
among the parity-check words of a typical $(\sigma,H)$ drawn at random.
However, for the application to Theorem 6.1, we need such a result not only
when $(\sigma,H)\sim\tilde{\mathbb{P}}$, but also after conditioning
$(\sigma,H)$ on a small fraction of the vertices and check nodes.

We formulate this technical proposition next. For each $i\in[d]$ let
$F_{i}\subseteq E_{i}$ and let $W_{i}:=\mathtt{Vert}(H;F_{i})$. Let
$w_{i}:=|W_{i}|=k|F_{i}|$. Let $F:=F_{1}\cup\cdots\cup F_{d}$,
$W:=W_{1}\cup\cdots\cup W_{d}$, and $w:=|W|$; see Figure 1. Then

$\max\\{w_{1},\dots,w_{d}\\}\leq w\leq w_{1}+\cdots+w_{d}.$

$E_{1}$
---
$E_{2}$
---
$E_{3}$
---

$F_{1}$
---
$F_{2}$
---
$F_{3}$
---
$W_{1}$
---
$W_{2}$
---
$W_{3}$
---

Figure 1: Diagrams showing full factor graph $H$ (left) and partial factor
graph $M$ (right). The square vertices on the right of each graph are the
check nodes, colored according to their membership in the sets
$E_{1},E_{2},E_{3}$. The distribution $\tilde{\mathbb{P}}^{M}$ draws a new
pair $(\sigma,H)$ conditioned on the edges on the right being present.

Let $M$ be a partial factor graph on $F$ and $V$, and let
$\tilde{\mathbb{P}}^{M}$ be the distribution obtained by conditioning
$\tilde{\mathbb{P}}$ on the event that $H\cap(F\times V)=M$. The key to
Theorem 6.1 is that, if the sets $F_{i}$ are small enough, then after this
conditioning, the rest of $H$ is very unlikely to create many new parity
checks that involve only vertices inside $W$. Roughly speaking, this means
that if ${\bf x}\in\mathbb{Z}^{W}_{2}$ satisfies all of the parity checks
arising from $F$ then, with high probability, it admits an extension
satisfying all of the parity checks.

Here and in the rest of the paper, if $F\subseteq E$ and $U\subseteq V$, then
$\mathbf{H}_{F\times U}$ denotes the submatrix of $\mathbf{H}$ indexed by
these sets, and we use analogous notation for the transpose
$\mathbf{H}^{\mathsf{T}}$ and for vectors indexed by either $E$ or $V$. We
identify $\mathbb{Z}_{2}^{E\setminus F}$ as a subspace of $\mathbb{Z}_{2}^{E}$
in the obvious way, and so any $\mathbf{y}\in\mathbb{Z}_{2}^{E\setminus F}$
may be written as a tuple $(\mathbf{y}_{1},\dots,\mathbf{y}_{d})^{\mathsf{T}}$
with $\mathbf{y}_{i}\in\mathbb{Z}_{2}^{E_{i}\setminus F_{i}}$.

######  Proposition 7.1 (‘Few additional checks inside $W$’).

For every $K>0$ and $\varepsilon>0$ the following holds for all sufficiently
small $\delta$ (depending on $d$, $k$, $\varepsilon$ and $K$). Let $F_{i}$,
$W_{i}$, $w_{i}$ and $M$ be as above. If

$\delta n\leq w_{1}+\dots+w_{d}\leq K\delta n,$ (19)

then

$\tilde{\mathbb{P}}^{M}\Big{(}\exists\mathbf{y}\in\mathbb{Z}_{2}^{E\setminus
F}\ \hbox{such that}\ \min\\{|\mathbf{y}_{i}|,|\mathbf{e}_{E_{i}\setminus
F_{i}}-\mathbf{y}_{i}|\\}\geq\varepsilon\delta\frac{n}{k}\ \hbox{for some
$i$}\\\ \hbox{ and}\ (\mathbf{H}^{\mathsf{T}}\mathbf{y})_{V\setminus
W}=\boldsymbol{0}\Big{)}\to 0$

as $n\to\infty$. The rate of convergence depends only on $d$, $k$ and
$\delta$, and is independent of $\delta$ provided $\delta$ is small enough and
also bounded away from zero.

We show how Proposition 7.1 implies Theorem 6.1 in the next subsection, and
then we prove Proposition 7.1 itself in Subsection 7.2.

######  Remark.

Proposition 7.1 has a similar flavor to the analysis of the satisfiability
threshold for the random combinatorial problem known as random XORSAT. But our
setting has the additional complication that we must analyse conditional
probabilities given the behaviour of the random factor graph $H$ on the small
sets $F_{i}$, which seems to make our situation less ‘homogeneous’. The random
XORSAT model is treated in [44, Chapter 18] using the paradigm of ‘belief
propagation’. It is possible that that approach could also be brought to bear
in the situation in Proposition 7.1, possibly leading to an alternative proof,
but we have not pursued this idea further.

####  7.1 Property M from few additional checks

To deduce Theorem 6.1 from Proposition 7.1, we also need two simpler
calculations that we present as separate lemmas.

The first concerns the following construction. Fix a subset $R$ of $V$ and let
$r>0$. For any factor graph $H\subset E\times V$, we can form the
neighbourhood $F:=\mathtt{Check}_{r}(H;R)$, and then the intersection
$M:=H\cap(F\times V)$ is a partial factor graph on $F$ and $V$. Let us call
the pair $(F,M)$ possible with respect to $(R,r)$ if they can arise from a
factor graph in this way.

######  Lemma 7.2.

Let $R$ and $r$ be as above, let $(F,M)$ be possible with respect to $(R,r)$,
and let $(\sigma,H)\sim\tilde{\mathbb{P}}$. If the event

$\\{H:\ H\cap(F\times V)=M\\}$

occurs, then so does the event

$\\{H:\ \mathtt{Check}_{r}(H;R)=F\\}.$

If we condition on the former event then the subsets $H\cap((E_{i}\setminus
F)\times V)$ are independent for different $i$, and each is a uniform random
labelled partition of $V\setminus\mathtt{Vert}(M;E_{i}\cap F)$ into $k$-sets.

###### Proof.

First, the definition of the neighbourhood $\mathtt{Check}_{r}(H;R)$ depends
only on those edges of the bipartite graph $H$ that connect this neighbourhood
to $V$. Since we are told that $(F,M)$ is possible with respect to $(R,r)$,
all those edges must already be visible in $M$, and so knowing that
$H\cap(F\times V)=M$ is enough to tell us that $\mathtt{Check}_{r}(H;R)=F$.

Now the conditional probability in question is $\tilde{\mathbb{P}}^{M}$, as
introduced previously. Since $\tilde{\mathbb{P}}$ is a uniform distribution,
$\tilde{\mathbb{P}}^{M}$ is the uniform distribution over all factor graphs
for which the event holds. However, if the event holds then (i) $H\cap(F\times
V)$ is uniquely determined, (ii) each $H\cap((E_{i}\setminus F)\times V)$ must
consist of a labelled partition of $V\setminus\mathtt{Vert}(M;E_{i}\cap F)$
into $k$-sets, and (iii) any tuple of such labelled partitions is still
possible. So this conditional distribution is simply the uniform distribution
over the Cartesian product set of tuples of such labelled partitions. This
implies the desired joint distribution for these sets. ∎

The next lemma may be well-known in coding theory, but we have not found a
convenient reference.

######  Lemma 7.3.

Let $A$ be any finite non-empty index set, $\delta<1/3$, and let $Y$ be a
linear subspace of $\mathbb{Z}_{2}^{A}$ such that

$\hbox{either}\quad|\mathbf{y}|\leq\delta|A|\quad\hbox{or}\quad|\mathbf{y}|\geq(1-\delta)|A|\quad\hbox{for
every}\quad\mathbf{y}\in Y.$ (20)

Then $\dim Y\leq 2\delta|A|+1$.

###### Proof.

Let $Z$ be the subset of all $\mathbf{y}\in Y$ for which
$|\mathbf{y}|\leq\delta|A|$. We prove that $Z$ is a linear subspace, $\dim
Y/Z\leq 1$, and $\dim Z\leq 2\delta|A|$.

First, $Z$ clearly contains $\boldsymbol{0}$, and if
$\mathbf{y},\mathbf{y}^{\prime}\in Z$ then $\mathbf{y}+\mathbf{y}^{\prime}\in
Y$ and

$|\mathbf{y}+\mathbf{y}^{\prime}|\leq 2\delta|A|.$

Since $2\delta<1-\delta$, by (20) this forces
$\mathbf{y}+\mathbf{y}^{\prime}\in Z$, so $Z$ is a subspace.

Next, if $\mathbf{y},\mathbf{y}^{\prime}\in Y\setminus Z$, then

$|\mathbf{y}-\mathbf{y}^{\prime}|\leq|(\mathtt{1},\dots,\mathtt{1})-\mathbf{y}|+|(\mathtt{1},\dots,\mathtt{1})-\mathbf{y}^{\prime}|\leq
2\delta|A|,$

so again we must in fact have $\mathbf{y}-\mathbf{y}^{\prime}\in Z$. Therefore
$\dim Y/Z\leq 1$.

Finally, call an index $i\in A$ proper if some member of $Z$ is non-zero in
this coordinate. Now choose $\mathbf{z}$ from $Z$ uniformly at random. If $i$
is proper, then the coordinate $z_{i}$ is equally likely to be $0$ or $1$, so
the expectation of $|\mathbf{z}|$ is half the number of proper coordinates.
Therefore the number of proper coordinates is at most $2\delta|A|$, and this
number is an upper bound on $\dim Z$. ∎

Property M (Theorem 6.1) follows from the following result, which is also used
to prove local and empirical convergence:

######  Theorem 7.4.

Given $r\in\mathbb{N}$ and $\eta>0$, for all small enough $\delta>0$ the
following holds: if for each $n$, $R_{n}\subset V_{n}$ is a subset of size
$\lceil\delta n\rceil$, then with high probability as $n\to\infty$

$\operatorname{H}\\!\big{(}(\mu_{n})_{\sigma_{n}^{B_{r}}(R_{n})}\big{)}\geq(1-\eta)\,\operatorname{H}\\!\big{(}m_{B_{r}}\big{)}|R_{n}|.$

###### Proof of Theorem 7.4 assuming Proposition 7.1.

Beware that we continue to suppress $n$ from subscripts where possible. It
should be understood that the following argument and construction are carried
out for each $n$ that is divisible by $k$.

Fix $\varepsilon>0$. For a small positive $\delta$ to be specified shortly,
let $R$ be any fixed choice of a subset of $V$ of size $\lceil\delta n\rceil$,
and now consider the following three subsets of $(\sigma,H)$ in
$\tilde{\Omega}$:

  * i.

(Few additional checks) $(\sigma,H)$ is in $\Omega^{1}$ if for

> any $\mathbf{y}\in\mathbb{Z}_{2}^{E\setminus\mathtt{Check}_{r}(H;R)}$ such
> that
> $(\mathbf{H}^{\mathsf{T}}\mathbf{y})_{V\setminus\mathtt{Vert}_{r}(H;R)}=\boldsymbol{0}$
> also has
>
> $\min\\{|\mathbf{y}_{i}|,|\mathbf{e}_{E_{i}\setminus
> F_{i}}-\mathbf{y}_{i}|\\}<\varepsilon\delta\frac{n}{k}\qquad\hbox{for
> every}\ i\in[d].$

where $F_{i}=E_{i}\cap\mathtt{Check}_{r}(H;R)$.

  * ii.

(Most vertices in $R$ well-separated) $(\sigma,H)$ is in $\Omega^{2}$ if the
set

$S_{1}:=\big{\\{}v\in R:\
\mathtt{Vert}_{r}(H;v)\cap\mathtt{Vert}_{r}(H;R\setminus
v)=\emptyset\big{\\}}.$

has $|S_{1}|>(1-\varepsilon)|R|$.

  * iii.

(Most vertices in $R$ not close to any short loops) $(\sigma,H)$ is in
$\Omega^{3}$ if the set

$S_{2}:=\big{\\{}v\in R:\ \hbox{the orbit map}\
B_{r}\to\mathtt{Vert}_{r}(H;v)\ \hbox{is injective}\big{\\}}.$

has $|S_{2}|>(1-\varepsilon)|R|$. (Here, the orbit map sends $\gamma\in
B_{r}\subset\Gamma$ to $\sigma(\gamma)v$.)

Let $S:=S_{1}\cap S_{2}$ and
$\Omega^{\prime}:=\Omega^{1}\cap\Omega^{2}\cap\Omega^{3}$. Think of $S$ as the
result of expurgating the ‘bad’ vertices from $R$, and $\Omega^{\prime}$ as
the event that there are only a few of these.

In the remainder of the proof we show that, provided $\delta$ was chosen small
enough, we have $\tilde{\mathbb{P}}(\Omega^{\prime})\to 1$ and the set $R$
satisfies the desired entropy bound.

_Step 1: $\tilde{\mathbb{P}}(\Omega^{\prime})\to 1$._ First, we have
$\tilde{\mathbb{P}}(\Omega^{2})\to 1$ as $n\to\infty$ for any sufficiently
small $\delta$ in terms of $d$, $k$, $r$ and $\varepsilon$. To see this,
observe that although we are fixing $R$ and choosing $(\sigma,H)$ at random,
we obtain the same distribution on $\lvert S_{1}\rvert$ if we choose $R$
uniformly at random among all subsets of $V$ of cardinality $\lceil\delta
n\rceil$, independently of $(\sigma,H)$. Thus it suffices to show that on any
$d$-regular $k$-uniform hyper-graph on $n$ vertices, if a subset $R\subset V$
of $\lceil\delta n\rceil$ vertices is chosen uniformly at random then the
probability that there are more than $\varepsilon\delta n$ vertices of $R$
which are $\leq 2r$ distance from another vertex in $R$ tends to zero as
$n\to\infty$.

If some number, say $x$, of vertices have already been chosen, then the
probability that the next vertex is not within distance $2r$ of the previously
selected vertices is at least

$1-\frac{(kd)^{2r}x}{n-x}\geq 1-\frac{(kd)^{2r}\lceil\delta
n\rceil}{n-\lceil\delta n\rceil}\geq 1-(kd)^{2r}\frac{\delta}{1-\delta}.$

This is because the number of vertices in the $(2r)$-neighbourhood of a given
vertex is at most $(kd)^{2r}$. Thus $\tilde{\mathbb{P}}(\Omega^{2})$ is at
least the probability that in $\lceil\delta n\rceil$ Bernoulli trials with
success probability $1-(kd)^{2r}\,\delta/(1-\delta)$, there are at least
$(1-\varepsilon)\lceil\delta n\rceil$ successes. This occurs with overwhelming
probability as $n\to\infty$ as long as
$\varepsilon>(kd)^{2r}\,\delta/(1-\delta)$, which we may assume by choosing
$\delta$ sufficiently small.

Second, for any $\delta>0$ we have $\tilde{\mathbb{P}}(\Omega^{3})\to 1$ as
$n\to\infty$ as an immediate corollary of Proposition 1.2.

So now let us show that $\tilde{\mathbb{P}}(\Omega^{1})\to 1$ as $n\to\infty$.
This is our application of Proposition 7.1. We make contact with that
proposition by conditioning on the partial factor graph
$H\cap(\mathtt{Check}_{r}(H;R)\times V)$ and using the law of total
probability.

Let $(F,M)$ be a possible pair with respect to $(R,r)$ as in Lemma 7.2, and
let $\tilde{\mathbb{P}}^{M}$ be the result of conditioning
$\tilde{\mathbb{P}}$ on the event $H\cap(F\times V)=M$, as previously. Let
$W_{i}:=\mathtt{Vert}(M;F_{i})$ and let $W:=W_{1}\cup\cdots\cup W_{d}$. By the
law of total probability,
$\tilde{\mathbb{P}}(\tilde{\Omega}\setminus\Omega^{1})$ is equal to the sum

$\sum_{\mathrm{possible}\,F,M}\tilde{\mathbb{P}}\big{(}H\cap(F\times
V)=M\big{)}\cdot\tilde{\mathbb{P}}^{M}\Big{(}\exists\mathbf{y}\in\mathbb{Z}_{2}^{E\setminus
F}\ \hbox{such that}\\\ \min\\{|\mathbf{y}_{i}|,|\mathbf{e}_{E_{i}\setminus
F_{i}}-\mathbf{y}_{i}|\\}\geq\varepsilon\delta\frac{n}{k}\ \ \hbox{for some
$i$}\ \hbox{and}\ (\mathbf{H}^{\mathsf{T}}\mathbf{y})_{V\setminus
W}=\boldsymbol{0}\Big{)}.$

Let $K:=(dk)^{r+1}+1$. Our construction of the possible pair $(F,M)$ gives
that

$\delta n\leq|R|\leq|W|\leq\sum_{i=1}^{d}|W_{i}|\leq(dk)^{r+1}|R|\leq K\delta
n,$

when $\delta n>1$ and so the condition (19) is satisfied for this value of $K$
by the second factor in every term of the sum above. Therefore, by Proposition
7.1, if $\delta$ is small enough in terms of $d$, $k$, $\varepsilon$ and $r$,
then this sum is a convex combination of quantities that converge to $0$ at a
rate depending only on $d$, $k$ and $\delta$, and hence so does the whole
expression.

This proves that $\tilde{\mathbb{P}}(\Omega^{\prime})\to 1$ for any
sufficiently small $\delta$. Fix such a $\delta$ for the rest of the proof.

_Step 2._ To finish the proof, we show that if $\sigma\in\Omega^{\prime}$ then
(i), (ii) and (iii) imply that $S$ has the properties required to witness
property M as in Definition 4.2.

First, $S_{1}$ is $(2r)$-separated by property (ii), and hence so is $S$.

Second, properties (ii) and (iii) together give

$\frac{|S|}{|V|}\geq(1-2\varepsilon)\frac{|R|}{|V|}\geq(1-2\varepsilon)\delta,$

which is uniformly positive in $n$ provided $\varepsilon<1/2$.

Finally, we must prove (5). Because $\mu_{\sigma}$ is the uniform distribution
on the linear subspace $X_{\sigma}$ of $\mathbb{Z}_{2}^{V}$, the image of
$\mu_{\sigma}$ on the subset of vertices
$\sigma^{B_{r}}(S)=\mathtt{Vert}_{r}(H;S)$ is the uniform distribution on an
image of $X$ under a linear projection. Therefore, after ignoring a factor of
$\log 2$, we need a lower bound on

$\dim\\{\mathbf{x}_{\mathtt{Vert}_{r}(H;S)}:\ \mathbf{x}\in X_{\sigma}\\}.$

By property (iii), each of the neighbourhoods $\mathtt{Vert}_{r}(H;v)$ for
$v\in S$ is a bijective copy of $B_{r}\subseteq\Gamma$, and by property (ii)
these neighbourhoods are disjoint. Therefore, by dimension counting, the
dimension above is at least

$|S|\cdot\dim X_{B_{r}}-\dim D_{1}-\dim D_{2},$

where

$D_{1}:=\mathbb{Z}_{2}^{\mathtt{Check}_{r}(H;R)\setminus\mathtt{Check}_{r}(H;S)}\quad\hbox{and}\quad
D_{2}:=\ker\mathbf{H}^{\mathsf{T}}_{(V\setminus\mathtt{Vert}_{r}(H;R))\times(E\setminus\mathtt{Check}_{r}(H;R))}.$

By properties (ii) and (iii), $|S|\geq(1-2\epsilon)|R|$. Since
$|\mathtt{Check}_{r}(H;R\setminus S)|\leq(dk)^{r-1}k|R\setminus S|$, this
implies

$\dim
D_{1}=|\mathtt{Check}_{r}(H;R)\setminus\mathtt{Check}_{r}(H;S)|\leq|\mathtt{Check}_{r}(H;R\setminus
S)|\leq Kk\varepsilon|S|.$

Finally, by property (i), if $\mathbf{y}\in D_{2}$ and we write
$\mathbf{y}=(\mathbf{y}_{1},\dots,\mathbf{y}_{d})^{\mathsf{T}}$, then for each
$i$ we have
$\mathbf{y}_{i}\in\mathbb{Z}_{2}^{E_{i}\setminus\mathtt{Check}_{r}(H;R)}$ and

$\hbox{either}\
|\mathbf{y}_{i}|<\varepsilon\delta\frac{n}{k}\quad\hbox{or}\quad|\mathbf{e}_{E_{i}\setminus\mathtt{Check}_{r}(H;R)}-\mathbf{y}_{i}|<\varepsilon\delta\frac{n}{k}.$

Therefore, provided $\varepsilon\delta<1/3$, Lemma 7.3 gives

$\dim\\{\mathbf{y}_{i}:\ \mathbf{y}\in D_{2}\\}\leq
2\varepsilon\delta\frac{n}{k}+1\quad\hbox{for each}\ i,$

and hence $\dim D_{2}\leq 2\varepsilon\delta nd/k+d$.

Inserting these bounds above, we finally arrive at

$\displaystyle\dim\\{\mathbf{x}_{\mathtt{Vert}_{r}(H;S)}:\ \mathbf{x}\in
X_{\sigma}\\}$ $\displaystyle\geq|S|\cdot\dim
X_{B_{r}}-Kk\varepsilon|S|-2\varepsilon\delta\frac{nd}{k}-d$
$\displaystyle\geq\left(\dim X_{B_{r}}-Kk\varepsilon-\frac{2\varepsilon
d}{k}-o(1)\right)\cdot|S|.$

This gives us a lower bound on the desired joint entropy:

$\displaystyle\operatorname{H}\\!\big{(}(\mu_{n})_{\sigma_{n}^{B_{r}}(R)}\big{)}$
$\displaystyle\geq\operatorname{H}\\!\big{(}(\mu_{n})_{\sigma_{n}^{B_{r}}(S)}\big{)}$
$\displaystyle=\log 2\cdot\dim\\{\mathbf{x}_{\mathtt{Vert}_{r}(H;S)}:\
\mathbf{x}\in X_{\sigma}\\}$ $\displaystyle\geq\left(\log 2\cdot\dim
X_{B_{r}}-\varepsilon\log
2\cdot\Big{(}Kk-\frac{2d}{k}-o(1)\Big{)}\right)\cdot(1-2\varepsilon)|R|$
$\displaystyle\geq\left(\operatorname{H}(m_{B_{r}})-\varepsilon C\right)|R|$

where $C=\log 2\cdot(Kk-\frac{2d}{k})+2\operatorname{H}(m_{B_{r}})$. Since $C$
depends only on $d,k$ and $r$, we could have taken at the beginning
$\varepsilon=\eta/C$, so this proves (5). ∎

######  Remark.

Proposition 7.1 shows that, with high conditional probability in the choice of
$\mathbf{H}$, the only parity checks among the bits in $W$ that are created by
$\mathbf{H}$ are (i) those created by the rows in $F$, and possibly (ii) a few
others that are generated by some vectors $\mathbf{y}$ whose support is either
extremely small or extremely close to the whole of $E\setminus F$. Since the
number of possible vectors of type (ii) is very small compared with those of
type (i), this implies that there are few enough ‘spurious’ parity checks
among the bits in $W$ to give Theorem 6.1. However, we do not expect that
there are _no_ extra parity checks of type (ii): just by chance, one should
typically find as many as a very small multiple of $n$ of these.

###### Proof of Theorem 6.1 item (1) from Theorem 7.4.

We have to prove 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 if
$\sigma_{n}\in\Omega_{n}^{\prime}$ for each $n$, then $(\mu_{n})_{n}$ has
property M with respect to $\Sigma=(\sigma_{n})_{n}$. This means that 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}(m_{B_{r}})-\epsilon)$
(21)

for all $n$.

Let $r,\varepsilon>0$. By Theorem 7.4, if $\delta>0$ is sufficiently small and
for each $n$, $S_{n}\subset[n]$ is an arbitrary set of size $\lceil\delta
n\rceil$, then there is some sequence $(\Omega^{\prime}_{n})_{n}$ with
$\mathbb{P}(\Omega^{\prime}_{n})\to 1$ such that the desired entropy
inequality holds when $\sigma_{n}\in\Omega^{\prime}_{n}$, and
$\liminf\frac{\lvert S_{n}\rvert}{n}=\liminf\frac{\lceil\delta
n\rceil}{n}=\delta>0$.

Then, by diagonalizing over the countably many choices of $r\in\mathbb{N}$ and
$\varepsilon\in\\{\frac{1}{2},\frac{1}{3},\frac{1}{4},\ldots\\}$, we can get a
single sequence of sets $(\Omega^{\prime}_{n})_{n}$ with
$\mathbb{P}(\Omega^{\prime}_{n})\to 1$ such that for any $r\in\mathbb{N}$ and
$\varepsilon>0$ there is a sequence $(S_{n})_{n}$ with the desired properties.
∎

####  7.2 Proof that there are few additional checks

This subsection proves Proposition 7.1. Let the sets $F_{i}$, $W_{i}$ and $M$
and parameters $K$, $\varepsilon$, $w_{i}$ and $w$ be as in that statement.
For $\mathbf{y}\in\mathbb{Z}_{2}^{E\setminus F}$, let

$G_{\mathbf{y}}:=\left\\{(\sigma,H)\,:\,(\mathbf{H}^{\mathsf{T}}\mathbf{y})_{V\setminus
W}=\boldsymbol{0}\right\\}\subset\tilde{\Omega}_{n}.$

Write $\mathbf{y}=(\mathbf{y}_{1},\ldots,\mathbf{y}_{d})^{\mathsf{T}}$ with
$\mathbf{y}_{i}\in\mathbb{Z}_{2}^{E_{i}\setminus F_{i}}$. We will focus on
those vectors $\mathbf{y}$ which satisfy restrictions on the cardinalities
$|\mathbf{y}_{i}|$ coming from Proposition 7.1. To be precise, let
$\mathcal{R}=\mathcal{R}(\varepsilon,\delta)$ be the set of all non-negative
integer tuples $\mathbf{\ell}=(\ell_{1},\dots,\ell_{d})$ that satisfy

$\ell_{i}\leq\frac{n-w_{i}}{k}\quad\hbox{for every}\
i\quad\hbox{and}\quad\min\left\\{\ell_{i},\frac{n-w_{i}}{k}-\ell_{i}\right\\}\geq\varepsilon\delta\frac{n}{k}\quad\hbox{for
some}\ i.$ (22)

The main conclusion of Proposition 7.1 is equivalent to:

$\tilde{\mathbb{P}}^{M}\left(\bigcup_{\mathbf{y}:\
(|\mathbf{y}_{1}|,\dots,|\mathbf{y}_{d}|)\in\mathcal{R}}G_{\mathbf{y}}\right)\to
0$

as $n\to\infty$. Our proof uses a simple union bound over $\mathbf{y}$. We
will derive estimates on $\tilde{\mathbb{P}}^{M}(G_{\mathbf{y}})$ that depend
on $\varepsilon$ and $\delta$ for
$\mathbf{y}\in\mathcal{R}(\varepsilon,\delta)$, and then use these to conclude
Proposition 7.1 provided $\delta$ is chosen correctly.

Fix a vector $\mathbf{y}\in\mathbb{Z}_{2}^{E\setminus F}$ with
$(|\mathbf{y}_{1}|,\dots,|\mathbf{y}_{d}|)\in\mathcal{R}$, and set
$r_{i}:=k|\mathbf{y}_{i}|$ and $\mathbf{r}:=(r_{1},\dots,r_{d})$. Let $Y_{i}$
be the support of the random vector $\mathbf{H}^{\mathsf{T}}\mathbf{y}_{i}$
for each $i$. This means
$\mathbf{H}^{\mathsf{T}}\mathbf{y}_{i}=\mathbf{e}_{Y_{i}}$. These random sets
are independent by the independence in Lemma 7.2. Each $Y_{i}$ is uniformly
random among all subsets of $V\setminus W_{i}$ of size $r_{i}$.

Each $Y_{i}$ may have non-empty intersection with $W\setminus W_{i}$. We bound
$\tilde{\mathbb{P}}^{M}(G_{\mathbf{y}})$ by breaking into a few further cases
depending on the sizes of these intersections. To this end, let
$Z_{i}:=Y_{i}\setminus W$. Under $\tilde{\mathbb{P}}^{M}$, the cardinality
$|Z_{i}|$ is a random quantity obtained by sampling $r_{i}$ points from
$V\setminus W_{i}$ without replacement and counting how many of them land in
$V\setminus W$. This random quantity has the hypergeometric distribution with
parameters $n-w_{i}$, $n-w$ and $r_{i}$: see, for instance, [27, Section
II.6]. Its possible values are the integers $s_{i}$ that satisfy

$\max(0,r_{i}-(w-w_{i}))\leq s_{i}\leq\min(r_{i},n-w),$ (23)

and for such values we have

$\tilde{\mathbb{P}}^{M}(|Z_{i}|=s_{i})=\frac{{n-w\choose s_{i}}{w-w_{i}\choose
r_{i}-s_{i}}}{{n-w_{i}\choose r_{i}}}.$

By the standard exponential estimate for binomial coefficients (see, for
instance, [22, Example 11.1.3]), this ratio is at most

$\exp\left(\operatorname{H}\left(\frac{s_{i}}{n-w}\right)(n-w)+\operatorname{H}\left(\frac{r_{i}-s_{i}}{w-w_{i}}\right)(w-w_{i})-\operatorname{H}\left(\frac{r_{i}}{n-w_{i}}\right)(n-w_{i})+o(n)\right),$
(24)

where quality of the error term does not depend on any other parameters.

Towards Proposition 7.1, we estimate the probability of $G_{\mathbf{y}}$ after
further conditioning on the tuple of cardinalities $|Z_{i}|$, and then combine
this estimate with (24) using the law of total probability. That refined
conditional probability estimate depends on the following lemma.

Let $\mathtt{Even}(d)$ be the subset of all strings in $\\{0,1\\}^{d}$ that
have even weight.

######  Lemma 7.5.

Let $q_{1}$, …, $q_{d}$ be probability distributions on $\\{0,1\\}$, and
assume that $q$ is a coupling of $q_{1}$, …, $q_{d}$ that is supported on
${\mathtt{Even}}(d)$. Then

$\operatorname{H}(q)\leq\left(1-\frac{1}{d}\right)\big{(}\operatorname{H}(q_{1})+\dots+\operatorname{H}(q_{d})\big{)}.$

###### Proof.

By permuting indices, we may assume without loss of generality that

$\operatorname{H}(q_{1})\geq\dots\geq\operatorname{H}(q_{d}).$

Let $\mathbf{z}=(z_{1},\dots,z_{d})$ be the identity map on $\\{0,1\\}^{d}$,
and regard it as a random binary string with distribution $q$. Then
$\mathbf{z}$ has even weight almost surely, and hence the coordinates $z_{2}$,
…, $z_{d}$ determine $z_{1}$ almost surely. Therefore

$\operatorname{H}(q)=\operatorname{H}_{q}(\mathbf{z})=\operatorname{H}_{q}(z_{2},\dots,z_{d})\leq\operatorname{H}_{q}(z_{2})+\cdots+\operatorname{H}_{q}(z_{d})=\operatorname{H}(q_{2})+\cdots+\operatorname{H}(q_{d}).$

Because of our ordering of the indices, this is at most the desired upper
bound. ∎

Now let $\mathcal{S}(\mathbf{r})$ be the set of all integer tuples
$\mathbf{s}=(s_{1},\dots,s_{d})$ that satisfy (23) for every $i$.

######  Lemma 7.6.

Fix a vector $\mathbf{y}\in\mathbb{Z}_{2}^{E\setminus F}$ with
$(|\mathbf{y}_{1}|,\dots,|\mathbf{y}_{d}|)\in\mathcal{R}$ as above. If
$\mathbf{s}\in\mathcal{S}(\mathbf{r})$, then

$\tilde{\mathbb{P}}^{M}\left(G_{\mathbf{y}}\ \big{|}\ |Z_{i}|=s_{i}\ \hbox{for
each}\
i\right)\leq\exp\left(-\frac{1}{d}\sum_{i=1}^{d}\operatorname{H}\left(\frac{s_{i}}{n-w}\right)\cdot(n-w)+o_{d}(n)\right).$

###### Proof.

To lighten notation, within this proof let

$\tilde{\mathbb{P}}^{M,\mathbf{s}}:=\tilde{\mathbb{P}}^{M}\big{(}\,\cdot\,\big{|}\
|Z_{i}|=s_{i}\ \hbox{for each}\ i\big{)}.$

Record the random sets $Z_{1}$, …, $Z_{d}$ into the random vector

$\boldsymbol{\eta}=(\eta_{v})_{v\in V\setminus
W}\in(\\{0,1\\}^{d})^{V\setminus W}\quad\hbox{where}\
\eta_{v}:=(1_{Z_{1}}(v),\dots,1_{Z_{d}}(v)).$

Let $P_{\boldsymbol{\eta}}=\frac{1}{\lvert V\setminus W\rvert}\sum_{v\in
V\setminus W}\delta_{\eta_{v}}$ be the empirical distribution of
$\boldsymbol{\eta}$. This is a probability distribution on $\\{0,1\\}^{d}$,
and the event $G_{\mathbf{y}}$ occurs if and only if this probability
distribution is supported on the subset $\mathtt{Even}(d)$. The marginals of
$P_{\boldsymbol{\eta}}$ are $(q_{i},1-q_{i})$ for $i=1,2,\dots,d$, where
$q_{i}:=s_{i}/(n-w)$. Moreover, $P_{\boldsymbol{\eta}}$ must take values that
are multiples of $1/(n-w)$, and the total number of such possible
distributions is at most

$(n-w+1)^{2^{d}}\leq n^{2^{d}}=e^{o_{d}(n)}$

(here and in some subsequent steps we generally loosen $o_{d}(n-w)$ to
$o_{d}(n)$). Therefore

$\tilde{\mathbb{P}}^{M,\mathbf{s}}(G_{\mathbf{y}})\leq
e^{o_{d}(n)}\max\big{\\{}\tilde{\mathbb{P}}^{M,\mathbf{s}}(P_{\boldsymbol{\eta}}=q):\
q\ \hbox{a coupling}\\\ \hbox{of}\ q_{1},\dots,q_{d}\ \hbox{such that}\
q(\mathtt{Even}(d))=1\big{\\}}.$ (25)

For a distribution $q$ as above, the set of vectors $\boldsymbol{\eta}$ that
give $P_{\boldsymbol{\eta}}=q$ are the ‘type class’ of $q$, and their number
is simply bounded using the entropy of $q$:

$|\\{\boldsymbol{\eta}\in(\\{0,1\\}^{d})^{V\setminus W}:\
P_{\boldsymbol{\eta}}=q\\}|\leq e^{\operatorname{H}(q)\cdot(n-w)}$

(see, for instance, [22, Theorem 11.1.3], except note that Cover and Thomas
use $\log_{2}$ rather than natural logarithms to define $\operatorname{H}$).
By Lemma 7.5, this upper bound is always at most

$\exp\left(\left(1-\frac{1}{d}\right)\cdot\big{(}\operatorname{H}(q_{1})+\cdots+\operatorname{H}(q_{d})\big{)}\cdot(n-w)\right).$
(26)

On the other hand, under the conditional probability measure
$\tilde{\mathbb{P}}^{M,\mathbf{s}}$, the set $Z_{i}$ is a uniform random
subset of $V\setminus W$ of size $s_{i}$, and these random sets are still
independent. Therefore the probability of any particular $d$-tuple of sets of
these sizes occurring is

$\prod_{i=1}^{d}{n-w\choose s_{i}}^{-1},$

and by another use of standard exponential estimates on binomial coefficients
[22, Example 11.1.3] this is at most

$\exp\left(-\big{(}\operatorname{H}(q_{1})+\cdots+\operatorname{H}(q_{d})\big{)}\cdot(n-w)+o_{d}(n)\right).$

Multiplying by the cardinality upper bound (26), we obtain

$\tilde{\mathbb{P}}^{M,\mathbf{s}}(P_{\boldsymbol{\eta}}=q)\leq\exp\left(-\frac{1}{d}\big{(}\operatorname{H}(q_{1})+\cdots+\operatorname{H}(q_{d})\big{)}\cdot(n-w)+o_{d}(n)\right)$

for any such coupling $q$. Since this upper bound is independent of the
particular coupling $q$, and the extra factor in (25) is sub-exponential, this
gives the result. ∎

######  Lemma 7.7.

Fix $k$ and $d$ as before, and define the function

$f(t,\alpha^{\prime},\alpha^{\prime\prime}):=(1-k^{-1})\operatorname{H}\big{(}(1-t)\alpha^{\prime}+t\alpha^{\prime\prime}\big{)}-(1-t)(1-d^{-1})\operatorname{H}(\alpha^{\prime})-t\operatorname{H}(\alpha^{\prime\prime})$

for $0\leq\alpha^{\prime},\alpha^{\prime\prime},t\leq 1$. Then

$\tilde{\mathbb{P}}^{M}\left(\bigcup_{\mathbf{y}:\
(|\mathbf{y}_{1}|,\dots,|\mathbf{y}_{d}|)\in\mathcal{R}}G_{\mathbf{y}}\right)\leq\sum_{\mathbf{r}\in
k\mathcal{R},\
\mathbf{s}\in\mathcal{S}(\mathbf{r})}\exp\left(-\sum_{i=1}^{d}f_{i}(r_{i},s_{i})\cdot(n-w_{i})+o_{d}(n)\right),$

where

$f_{i}(r_{i},s_{i})=f\left(\frac{w-w_{i}}{n-w_{i}},\frac{s_{i}}{n-w},\frac{r_{i}-s_{i}}{w-w_{i}}\right).$

###### Proof.

For each $\mathbf{y}$, we let $r_{i}:=k|\mathbf{y}_{i}|$ and bound
$\tilde{\mathbb{P}}^{M}(G_{\mathbf{y}})$ from above using (24), Lemma 7.6 and
the law of total probability. The resulting upper bound is

$\tilde{\mathbb{P}}^{M}\left(G_{\mathbf{y}}\right)\leq\sum_{\mathbf{s}\in\mathcal{S}(\mathbf{r})}\exp\Bigg{(}-\frac{1}{d}\sum_{i=1}^{d}\operatorname{H}\left(\frac{s_{i}}{n-w}\right)(n-w)+\sum_{i=1}^{d}\operatorname{H}\left(\frac{s_{i}}{n-w}\right)(n-w)\\\
+\sum_{i=1}^{d}\operatorname{H}\left(\frac{r_{i}-s_{i}}{w-w_{i}}\right)(w-w_{i})-\sum_{i=1}^{d}\operatorname{H}\left(\frac{r_{i}}{n-w_{i}}\right)(n-w_{i})+o_{d}(n)\Bigg{)}.$

On the other hand, the number of vectors
$\mathbf{y}\in\mathbb{Z}_{2}^{E\setminus F}$ with given weights
$|\mathbf{y}_{i}|=r_{i}/k$ is at most

$\exp\left(\sum_{i=1}^{d}\operatorname{H}\left(\frac{r_{i}}{n-w_{i}}\right)\frac{n-w_{i}}{k}\right).$

Therefore the sum of $\tilde{\mathbb{P}}^{M}(G_{\mathbf{y}})$ over all
$\mathbf{y}$ satisfying
$(|\mathbf{y}_{1}|,\dots,|\mathbf{y}_{d}|)\in\mathcal{R}$ is at most

$\sum_{\mathbf{r}\in k\mathcal{R},\
\mathbf{s}\in\mathcal{S}(\mathbf{r})}\exp\left(-\sum_{i=1}^{d}f_{i}(r_{i},s_{i})\cdot(n-w_{i})+o_{d}(n)\right),$
(27)

where

$\displaystyle f_{i}(r_{i},s_{i})$
$\displaystyle:=-\frac{1}{k}\operatorname{H}\left(\frac{r_{i}}{n-w_{i}}\right)+\frac{1}{d}\cdot\frac{n-w}{n-w_{i}}\cdot\operatorname{H}\left(\frac{s_{i}}{n-w}\right)$
$\displaystyle\qquad-\frac{n-w}{n-w_{i}}\cdot\operatorname{H}\left(\frac{s_{i}}{n-w}\right)-\frac{w-w_{i}}{n-w_{i}}\cdot\operatorname{H}\left(\frac{r_{i}-s_{i}}{w-w_{i}}\right)+\operatorname{H}\left(\frac{r_{i}}{n-w_{i}}\right)$
$\displaystyle=\left(1-\frac{1}{k}\right)\cdot\operatorname{H}\left(\frac{r_{i}}{n-w_{i}}\right)$
$\displaystyle\qquad-\left(1-\frac{1}{d}\right)\cdot\frac{n-w}{n-w_{i}}\cdot\operatorname{H}\left(\frac{s_{i}}{n-w}\right)-\frac{w-w_{i}}{n-w_{i}}\cdot\operatorname{H}\left(\frac{r_{i}-s_{i}}{w-w_{i}}\right)$
$\displaystyle=f\left(\frac{w-w_{i}}{n-w_{i}},\frac{s_{i}}{n-w},\frac{r_{i}-s_{i}}{w-w_{i}}\right).\qed$

We are nearly ready to prove Proposition 7.1. For that proof, we must combine
Lemma 7.7 with an elementary but rather fiddly estimate. That estimate refers
to the functions

$\gamma_{1}(t):=\frac{1}{(\log(1/t))^{1/3}}\quad\hbox{and}\quad\gamma_{2}(t):=\frac{1}{(\log(1/t))^{2/3}},$

both for $0<t<1$. The exponents $1/3$ and $2/3$ are not particularly special
here: all we really need is the ordering $0<1/3<2/3<1$. The next lemma gives a
collection of simple bounds on the quantity
$f(t,\alpha^{\prime},\alpha^{\prime\prime})$ for different ranges of the
arguments. Each part requires that $t$ is sufficiently small in terms of $d$
and $k$. The quantities $t_{0}^{\mathrm{(a)}},t_{0}^{\mathrm{(b)}}$,
$t_{0}^{\mathrm{(c)}}$ and $t_{0}^{\mathrm{(d)}}$ are unspecified positive
numbers that are sufficiently small in terms of only $d$ and $k$. Recall we
assume $k>d\geq 3$.

######  Lemma 7.8.

Write $\alpha:=(1-t)\alpha^{\prime}+t\alpha^{\prime\prime}$. The function $f$
from Lemma 7.7 satisfies the following.

  1. a.

If $t<t_{0}^{\mathrm{(a)}}$ and either
$\alpha^{\prime\prime}\leq\alpha^{\prime}\leq 1/2$ or
$\alpha^{\prime\prime}\geq\alpha^{\prime}>1/2$, then

$f(t,\alpha^{\prime},\alpha^{\prime\prime})\gtrsim_{d,k}\operatorname{H}(\alpha).$

(This includes the assertion that the left-hand side is non-negative; see
Section 1.6.)

  2. b.

If $t<t_{0}^{\mathrm{(b)}}$ and $t\gamma_{p}(t)\leq\alpha^{\prime}\leq
1-t\gamma_{p}(t)$, then

$f(t,\alpha^{\prime},\alpha^{\prime\prime})\gtrsim_{d,k}t\cdot(\log(1/t))^{1-p/3}.$

  3. c.

If $t<t_{0}^{\mathrm{(c)}}$ and $\gamma_{p}(t)\leq\alpha^{\prime\prime}\leq
1-\gamma_{p}(t)$, then

$f(t,\alpha^{\prime},\alpha^{\prime\prime})\gtrsim_{d,k}t\cdot(\log(1/t))^{1-p/3}.$

  4. d.

If $t<t_{0}^{\mathrm{(d)}}$ and

$[\ \alpha^{\prime}<t\gamma_{p}(t)\ \hbox{or}\
\alpha^{\prime}>1-t\gamma_{p}(t)]\ \hbox{and}\ [\
\alpha^{\prime\prime}<\gamma_{p}(t)\ \hbox{or}\
\alpha^{\prime\prime}>1-\gamma_{p}(t)\ ],$

then

$\max\\{0,-f(t,\alpha^{\prime},\alpha^{\prime\prime})\\}\lesssim_{d,k}t\cdot(\log(1/t))^{1-p/3}.$

(The maximum is used here to maintain the non-negativity convention for
$\lesssim$.)

Observe that at least one of the parts (b), (c) or (d) must hold whenever
$t<\min\\{t_{0}^{\mathrm{(b})},t_{0}^{\mathrm{(c)}},t_{0}^{\mathrm{(d)}}\\}$.

###### Proof.

Each part of this lemma is symmetric under replacing
$(\alpha^{\prime},\alpha^{\prime\prime})$ with
${(1-\alpha^{\prime},1-\alpha^{\prime\prime})}$, and so is the function $f$.
We therefore assume that $\alpha^{\prime}\leq 1/2$ throughout the proof.

_Part (a)._ By the concavity of $\operatorname{H}$, we have

$\displaystyle(1-t)(1-d^{-1})\operatorname{H}(\alpha^{\prime})+t\operatorname{H}(\alpha^{\prime\prime})$
$\displaystyle\leq\big{(}(1-t)(1-d^{-1})+t\big{)}\operatorname{H}\left(\frac{(1-t)(1-d^{-1})}{(1-t)(1-d^{-1})+t}\alpha^{\prime}+\frac{t}{(1-t)(1-d^{-1})+t}\alpha^{\prime\prime}\right).$

Since $1-d^{-1}<1$, the convex combination inside the argument of
$\operatorname{H}$ here skews more towards $\alpha^{\prime\prime}$ than does
the convex combination that gives $\alpha$. Therefore, since
$\alpha^{\prime\prime}\leq\alpha^{\prime}\leq 1/2$ and $\operatorname{H}$ is
increasing on $[0,1/2]$, the right-hand side above is bounded above by

$\big{(}(1-t)(1-d^{-1})+t\big{)}\operatorname{H}(\alpha)=(1-d^{-1}+td^{-1})\operatorname{H}(\alpha).$

Therefore

$f(t,\alpha^{\prime},\alpha^{\prime\prime})\geq\big{(}(1-k^{-1})-(1-d^{-1}+td^{-1})\big{)}\operatorname{H}(\alpha)=(d^{-1}-k^{-1}-td^{-1})\operatorname{H}(\alpha),$

which is $\gtrsim_{d,k}\operatorname{H}(\alpha)$ provided
$t<t_{0}^{\mathrm{(a)}}$.

_Part (b)._ For this part our assumptions are now $\alpha^{\prime}\leq 1/2$
and $\alpha^{\prime}\geq t\gamma_{p}(t)$. Let $c_{1}:=(d^{-1}-k^{-1})/2>0$.
Since $\alpha^{\prime}\leq 1/2$ and $\operatorname{H}$ is continuous on
$[0,1]$ and increasing on $[0,1/2]$, we have that

$\operatorname{H}((1-t)\alpha^{\prime}+t\alpha^{\prime\prime})\geq\frac{1-d^{-1}+c_{1}}{1-k^{-1}}\operatorname{H}(\alpha^{\prime})\quad\hbox{whenever}\
t<t_{0}^{\mathrm{(b)}}.$ (28)

If $\alpha^{\prime}\geq t\gamma_{p}(t)$ and $t<t_{0}^{\mathrm{(b)}}$, then

$\displaystyle\operatorname{H}(\alpha^{\prime})$ $\displaystyle\geq$
$\displaystyle\operatorname{H}(t\gamma_{p}(t))\geq
t\cdot\gamma_{p}(t)\cdot\big{(}\log(1/\gamma_{p}(t))+\log(1/t)\big{)}$
$\displaystyle\geq$ $\displaystyle
t\cdot\gamma_{p}(t)\cdot\log(1/t)=t\cdot(\log(1/t))^{1-p/3}.$

Combining (28) and (7.2), we obtain

$\displaystyle f(t,\alpha^{\prime},\alpha^{\prime\prime})$
$\displaystyle\geq(1-d^{-1}+c_{1})\operatorname{H}(\alpha^{\prime})-(1-t)(1-d^{-1})\operatorname{H}(\alpha^{\prime})-t\operatorname{H}(\alpha^{\prime\prime})$
$\displaystyle\geq
c_{1}\operatorname{H}(\alpha^{\prime})-t\operatorname{H}(\alpha^{\prime\prime})$
$\displaystyle\geq c_{1}\cdot t\cdot(\log(1/t))^{1-p/3}-\log 2\cdot t$
$\displaystyle\gtrsim_{d,k}t\cdot(\log(1/t))^{1-p/3}\qquad\qquad\qquad\hbox{if}\
t<t_{0}^{\mathrm{(b)}}.$

_Part (c)._ For this part our assumptions are now $\alpha^{\prime}\leq 1/2$
and $\alpha^{\prime\prime}\geq\gamma_{p}(t)$. We may also assume that
$\alpha^{\prime}<t\gamma_{p}(t)$, for otherwise part (b) already gives the
desired bound.

If, in addition, we have $\alpha^{\prime}\geq\alpha^{\prime\prime}$, then part
(a) gives

$f(t,\alpha^{\prime},\alpha^{\prime\prime})\gtrsim_{d,k}\operatorname{H}(\alpha),$

and this in turn satisfies

$\operatorname{H}(\alpha)\geq\operatorname{H}(t\alpha^{\prime\prime})\geq
t\cdot\alpha^{\prime\prime}\cdot\log(1/t)\geq
t\cdot\gamma_{p}(t)\cdot\log(1/t)=t\cdot(\log(1/t))^{1-p/3}.$ (30)

So for the rest of this part assume in addition that
$\alpha^{\prime}\leq\alpha^{\prime\prime}$. Then for sufficiently small $t$ we
must have the ordering $\alpha^{\prime}\leq\alpha<1/2$, and so

$\displaystyle(1-t)(1-d^{-1})\operatorname{H}(\alpha^{\prime})+t\operatorname{H}(\alpha^{\prime\prime})$
$\displaystyle\leq(1-d^{-1})\operatorname{H}(\alpha^{\prime})+t\operatorname{H}(\alpha^{\prime\prime})$
$\displaystyle\leq(1-d^{-1})\operatorname{H}(\alpha)+t\operatorname{H}(\alpha^{\prime\prime}).$

Therefore in this case it suffices to show that

$(d^{-1}-k^{-1})\operatorname{H}(\alpha)-t\operatorname{H}(\alpha^{\prime\prime})\gtrsim_{d,k}t\cdot(\log(1/t))^{1-p/3}.$

Since the second left-hand term here is $O(t)$, this follows by another use of
(30).

_Part (d)._ For this case we simply neglect the positive term in $f$ entirely.
If

$t<t_{0}^{\mathrm{(d)}},\quad\alpha^{\prime}<t\cdot\gamma_{p}(t)\quad\hbox{and}\quad\alpha^{\prime\prime}<\gamma_{p}(t),$

then

$\operatorname{H}(\alpha^{\prime})\lesssim_{d,k}t\cdot\gamma_{p}(t)\cdot\log\frac{1}{t}=t\cdot(\log(1/t))^{1-p/3}$

and

$t\operatorname{H}(\alpha^{\prime\prime})=O(t)\lesssim_{d,k}t\cdot(\log(1/t))^{1-p/3}.$

In the cases where $\alpha^{\prime}>1-t\cdot\gamma_{p}(t)$ or
$\alpha^{\prime\prime}>1-\gamma_{p}(t)$ the same estimates hold, by the
symmetry $\operatorname{H}(x)=\operatorname{H}(1-x)$. Adding these estimates
gives the conclusion. ∎

######  Corollary 7.9.

Fix $K\geq 1$ and $\delta>0$, and let the other notation be as for Lemma 7.8.
If $\delta$ is sufficiently small in terms of $d$, $k$ and $K$, and if

$t\leq K\delta\quad\hbox{and}\quad\delta\cdot\gamma_{1}(\delta)\leq\alpha\leq
1-\delta\cdot\gamma_{1}(\delta),$

then

$f(t,\alpha^{\prime},\alpha^{\prime\prime})\gtrsim_{d,k,K}\delta\cdot(\log(1/\delta))^{2/3}$

(irrespective of any further bounds on $\alpha^{\prime}$ and
$\alpha^{\prime\prime}$).

###### Proof.

By the same symmetry as for Lemma 7.8, we may assume that $\alpha^{\prime}\leq
1/2$.

Having done so, suppose first that $\alpha^{\prime\prime}\leq\alpha^{\prime}$.
Then part (a) of Lemma 7.8 gives

$f(t,\alpha^{\prime},\alpha^{\prime\prime})\gtrsim_{d,k}\operatorname{H}(\alpha),$

and our assumed range for $\alpha$ gives

$\operatorname{H}(\alpha)\geq\operatorname{H}(\delta\cdot\gamma_{1}(\delta))\geq\delta\cdot(\log(1/\delta))^{2/3},$
(31)

giving a lower bound of the desired form.

So now suppose that $\alpha^{\prime}\leq 1/2$ and
$\alpha^{\prime\prime}\geq\alpha^{\prime}$. Since $t\leq K\delta$, it follows
that

$\alpha^{\prime}\leq\alpha\leq(1-K\delta)\alpha^{\prime}+K\delta.$

Provided $\delta$ is sufficiently small in terms of $d$ and $k$, this range of
possible values for $\alpha^{\prime}$ and $\alpha$ implies that

$(1-d^{-1})\operatorname{H}(\alpha^{\prime})\leq\left(1-\frac{d^{-1}+k^{-1}}{2}\right)\operatorname{H}(\alpha)$

(noting that the constant in front of the entropy on the left is slightly
smaller than the constant in front of the entropy on the right). Re-arranging,
this implies that

$(1-k^{-1})\operatorname{H}(\alpha)-(1-d^{-1})\operatorname{H}(\alpha^{\prime})\geq\frac{d^{-1}-k^{-1}}{2}\operatorname{H}(\alpha)\geq\frac{d^{-1}-k^{-1}}{2}\cdot\delta\cdot(\log(1/\delta))^{2/3},$

using again the lower bound (31). This now gives

$\displaystyle f(t,\alpha^{\prime},\alpha^{\prime\prime})$
$\displaystyle\geq\frac{d^{-1}-k^{-1}}{2}\cdot\delta\cdot(\log(1/\delta))^{2/3}-t\big{(}\operatorname{H}(\alpha^{\prime\prime})-(1-d^{-1})\operatorname{H}(\alpha^{\prime})\big{)}$
$\displaystyle\geq\frac{d^{-1}-k^{-1}}{2}\cdot\delta\cdot(\log(1/\delta))^{2/3}-\log
2\cdot K\cdot\delta.$

This implies the desired lower bound on $f$ for all sufficiently small
$\delta$. ∎

###### Proof of Proposition 7.1.

Fix $K$ and $\varepsilon$ and also $F_{i}$, $W_{i}$, $w_{i}$ and $M$ as in the
statement of Proposition 7.1, and suppose that (19) holds. We prove the
convergence to zero of the required probabilities provided that $\delta$ is
small enough in terms of $d$, $k$, $\varepsilon$ and $K$.

First, assume $\delta$ is small enough that

$\gamma_{1}(\delta)\leq\varepsilon,$ (32)

and also small enough in terms of $d$, $k$ and $K$ that Corollary 7.9 applies.

By Lemma 7.7, and since a small choice of $\delta$ ensures that $n-w_{i}\geq
n/2$ for each $i$, it suffices to show that, if $\delta$ is sufficiently
small, then the negative exponent

$\sum_{i=1}^{d}f\left(\frac{w-w_{i}}{n-w_{i}},\frac{s_{i}}{n-w},\frac{r_{i}-s_{i}}{w-w_{i}}\right)$
(33)

is bounded below by a positive quantity that is independent of $\mathbf{r}\in
k\mathcal{R}$ and $\mathbf{s}\in\mathcal{S}(\mathbf{r})$.

So fix $\mathbf{r}$ and $\mathbf{s}$, and let

$(t_{i},\alpha^{\prime}_{i},\alpha^{\prime\prime}_{i}):=\left(\frac{w-w_{i}}{n-w_{i}},\frac{s_{i}}{n-w},\frac{r_{i}-s_{i}}{w-w_{i}}\right)$

and

$\alpha_{i}=(1-t_{i})\alpha^{\prime}_{i}+t_{i}\alpha^{\prime\prime}_{i}=\frac{r_{i}}{n-w_{i}}.$

For each $i$ this implies that

$t_{i}\leq\frac{w}{n}\leq K\delta.$

Assume $\delta$ is also small enough that
$K\delta<\min\\{t_{0}^{\mathrm{(a)}},t_{0}^{\mathrm{(b)}},t_{0}^{\mathrm{(c)}},t_{0}^{\mathrm{(d)}}\\}$,
so each $t_{i}$ is also less than this minimum.

Classify the indices $i\in[d]$ into two subsets:

$\displaystyle I_{1}$ $\displaystyle=\\{i\in[d]:\ \varepsilon\delta\leq
r_{i}/(n-w_{i})\leq 1-\varepsilon\delta\\}$ $\displaystyle I_{2}$
$\displaystyle=[d]\setminus I_{1}.$

The definition of $\mathcal{R}$ implies that $I_{1}\neq\emptyset$. Consider
the terms in (33) for indices in these subsets:

  * •

If $i\in I_{1}$, then, by our choice of $\delta$ in (32) and since $t_{i}\leq
K\delta$, Corollary 7.9 gives

$f\left(\frac{w-w_{i}}{n-w_{i}},\frac{s_{i}}{n-w},\frac{r_{i}-s_{i}}{w-w_{i}}\right)\geq
C_{1}\cdot\delta\cdot(\log(1/\delta))^{2/3}$

for some positive constant $C_{1}$ depending only on $d$, $k$ and $K$.

  * •

Next, for $i\in I_{2}$, we use that at least one of parts (b), (c), and (d) of
Lemma 7.8 must hold, which gives that

$\displaystyle\max\left\\{0,\,-f\left(\frac{w-w_{i}}{n-w_{i}},\frac{s_{i}}{n-w},\frac{r_{i}-s_{i}}{w-w_{i}}\right)\right\\}$
$\displaystyle\lesssim_{d,k}t_{i}\cdot(\log(1/t_{i}))^{1/3}$
$\displaystyle\lesssim_{K}\delta\cdot(\log(1/\delta))^{1/3}$

provided $\delta$ is sufficiently small, and so the left-hand side is bounded
above by $C_{2}\cdot\delta\cdot(\log(1/\delta))^{1/3}$ for some positive
$C_{2}$ depending only on $d$, $k$ and $K$.

We bound (33) from below by adding these estimates. At least one term has
$i\in I_{1}$, and there are at most $d-1$ terms with $i\in I_{2}$. This leaves
the lower bound

$C_{1}\cdot\delta\cdot(\log(1/\delta))^{2/3}-(d-1)\cdot
C_{2}\cdot\delta\cdot(\log(1/\delta))^{1/3}.$

This is positive for all sufficiently small $\delta$, uniformly over different
choices of $\mathbf{r}$ or $\mathbf{s}$, as required. ∎

###  8 Proof of local and empirical convergence

In this section we prove Theorem 6.1(2): we show that if
$(\Omega^{\prime}_{n})_{n}$ is the sequence given by Theorem 6.1(1) and
$\sigma_{n}\in\Omega^{\prime}_{n}$ for each $n$, then the measures $\mu_{n}$
converge locally and empirically in probability to the Haar measure $m$.

Recall $X_{n}=X_{\sigma_{n}}$ is the set of parity check codewords over
$\sigma_{n}\in\operatorname{Hom}_{\mathrm{unif}}(\Gamma,\operatorname{Sym}(V_{n}))$.
For $v\in V_{n}$ let

$X_{n,v}=\left\\{\Pi_{v}^{\sigma_{n}}\mathbf{x}\,:\,\mathbf{x}\in
X_{n}\right\\}$

be the set of pullback names at $v$ of all the codewords in $X_{n}$. As above,
let

$\mathrm{Loc}(\mu_{n},v)=\left(\Pi_{v}^{\sigma_{n}}\right)_{*}\mu_{n}\in\operatorname{Prob}(X).$

Let $X_{n,v,r}$ be the projection of $X_{n,v}$ onto $\mathbb{Z}_{2}^{B_{r}}$.
Call a vertex $v\in V_{n}$ $r$-proper if $X_{n,v,r}=X_{B_{r}}$. Otherwise,
call it $r$-improper.

The following lemma is a (stronger) version of [56, Lemma 3.47] for our random
factor graph model.

######  Lemma 8.1.

For any $r,\varepsilon>0$

$\mathbb{P}\left(\frac{1}{\lvert V_{n}\rvert}\lvert\\{v\in V_{n}\,:\,v\text{
is $r$-improper}\\}\rvert\geq\varepsilon\right)\to 0$

as $n\to\infty$.

###### Proof.

In general $X_{n,v,r}$ is a vector subspace of $X_{B_{r}}$. If $v$ is
$r$-improper, then it is a subspace of strictly smaller dimension, so

$\operatorname{H}(\mathrm{Loc}(\mu_{n},v)_{B_{r}})\leq\log\lvert
X_{n,v,r}\rvert=(\dim X_{n,v,r})\log 2\leq(\dim X_{B_{r}}-1)\log
2=\operatorname{H}(m_{B_{r}})-\log 2.$ (34)

With $\varepsilon,r$ as given, pick $\eta=\frac{\varepsilon\log 2}{4}$. By
Theorem 7.4, for small enough $\delta>0$, if for each $n$ we pick a subset
$R_{n}$ of $V_{n}$ of size $\lceil\delta n\rceil$, then with high probability
$\sigma_{n}$ satisfies

$\operatorname{H}((\mu_{n})_{\sigma_{n}^{B_{r}}\cdot
R_{n}})\geq\left(\operatorname{H}(m_{B_{r}})-\eta\right)\lvert R_{n}\rvert.$

Now for the sake of contradiction suppose that

$\limsup_{n\to\infty}\mathbb{P}\left(\frac{1}{\lvert V_{n}\rvert}\lvert\\{v\in
V_{n}\,:\,v\text{ is $r$-improper}\\}\rvert\geq\varepsilon\right)>0.$

Then, by symmetry of the law of $\sigma_{n}$, and using that $\lvert
R_{n}\rvert\geq\delta\lvert V_{n}\rvert$, the probability that the fraction of
$r$-improper vertices within $R_{n}$ is at least $\frac{\varepsilon}{2}$ is
uniformly bounded below for infinitely many $n$. But if an
$\frac{\varepsilon}{2}$ fraction of vertices of $R_{n}$ are $r$-improper, then
by Equation 34 and subadditivity of Shannon entropy

$\operatorname{H}((\mu_{n})_{\sigma_{n}^{B_{r}}\cdot
R_{n}})\leq\left(\operatorname{H}(m_{B_{r}})-\tfrac{\varepsilon}{2}\log
2\right)\lvert R_{n}\rvert$

Combining with the above, this implies that with nonvanishing probability

$\left(\operatorname{H}(m_{B_{r}})-\eta\right)\lvert
R_{n}\rvert\leq\left(\operatorname{H}(m_{B_{r}})-\tfrac{\varepsilon}{2}\log
2\right)\lvert R_{n}\rvert.$

But this is false by choice of $\eta$, so it must be that

$\limsup_{n\to\infty}\mathbb{P}\left(\frac{1}{\lvert V_{n}\rvert}\lvert\\{v\in
V_{n}\,:\,v\text{ is $r$-improper}\\}\rvert\geq\varepsilon\right)=0$

as desired. ∎

###### Proof of Theorem 6.1(2).

Let $\mathrm{Loc}(\mu_{n},v)_{B_{r}}$ denote the marginal of
$\mathrm{Loc}(\mu_{n},v)$ on $X_{n,v,r}$.

Since $\mathrm{Loc}(\mu_{n},v)_{B_{r}}$ is the uniform distribution on
$X_{n,v,r}$ and $m_{B_{r}}$ is the uniform distribution on $X_{B_{r}}$, local
convergence in probability to $\mu$ is implied by

$\lim_{n\to\infty}\mathbb{P}\left(\frac{1}{\lvert
V_{n}\rvert}\lvert\left\\{v\in V_{n}\,:\,X_{n,v,r}\neq
X_{B_{r}}\right\\}\rvert>\varepsilon\right)=0,$

which is true by Lemma 8.1.

Since $(\mu_{n})_{n}$ converges locally in probability to $m_{X}$, which is
ergodic, Lemma 4.1 completes the proof. ∎

###  9 Proof of Theorem 1.3

Next we prove the upper bound in Theorem 1.3, part (a). After this, part (b)
of the Theorem 1.3 is an immediate consequence of Theorems 6.1 (items 1,2) and
4.3.

####  9.1 Proof of the sofic entropy value

###### Proof of Theorem 1.3, part (a).

Let $\sigma_{n}\sim\mathbb{P}_{n}$ and let
$\Omega_{n}^{\prime}\subseteq\Omega_{n}^{\mathrm{sofic}}$ be as in Proposition
3.2. Let $\Sigma=\\{\sigma_{n}\\}_{n=1}^{\infty}$ satisfy
$\sigma_{n}\in\Omega^{\prime}_{i_{n}}$ for some increasing sequence
$(i_{n})_{n}$ with $k\mid i_{n}$ for all $n$. It suffices to prove

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

By Proposition 3.1,

$\mathrm{H_{K}}(m_{X})=(1-d)\operatorname{H}(W_{m_{X}}(\cdot))+\frac{1}{k}\sum_{i\in[d]}\operatorname{H}(W_{m_{X}}(\cdot;i)).$

The weight $W_{m_{X}}$ is uniform on $\mathbb{Z}_{2}$. So
$\operatorname{H}(W_{m_{X}}(\cdot))=\log(2)$. For each $i\in[d]$, the measure
$W_{m_{X}}(\cdot;i)$ is uniformly distributed on the subgroup of
$\mathbb{Z}_{2}^{k}$ which is the kernel of the homomorphism
$(x_{1},\ldots,x_{k})\mapsto\sum_{i}x_{i}\in\mathbb{Z}_{2}$. This group has
order $2^{k-1}$. So

$\operatorname{H}(W_{m_{X}}(\cdot;i))=(k-1)\log(2).$

Combined with the previous formula, we obtain

$\mathrm{H_{K}}(m_{X})=(1-d/k)\log(2).$

The conclusion of Proposition 3.2 now implies the upper bound

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

By Theorem 6.1(2), $\mu_{n}$ converges empirically to $m_{X}$. Therefore, if
$\mathcal{O}$ is any open neighborhood of $m_{X}$ then

$1=\lim_{n\to\infty}\mu_{n}(\Omega(\sigma_{n},\mathcal{O})).$

Since $\mu_{n}$ is the uniform measure on $X_{\sigma_{n}}$, this implies

$\operatorname{h}_{\Sigma}(X,m_{X},T)\geq\lim_{n\to\infty}\frac{1}{i_{n}}\log|X_{\sigma_{n}}|.$

We may estimate $|X_{\sigma_{n}}|$ by simple dimension-counting. In fact,
$X_{\sigma_{n}}$ is the kernel of a homomorphism from $\mathbb{Z}_{2}^{i_{n}}$
to $\mathbb{Z}_{2}^{di_{n}/k}$. So

$|X_{\sigma_{n}}|\geq 2^{(1-d/k)i_{n}}.$

This gives the lower bound

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

∎

###  10 Proof of Theorems B and C

Theorem B is an immediate consequence of Theorem 6.1(3) and Corollary 5.5(2).

####  10.1 Expected number of low-density codewords

In this section we derive an asymptotic formula for the expected number of
low-density codewords. Versions of this appear in [44, Formula (11.10)] and
[56, Lemma 3.163]. The authors of [44] and [56] use a configuration model
instead of a permutation model. As discussed above, these models are not
contiguous (see Appendix A). Moreover, we are able to show a stronger result
than contiguity alone would imply.

For $\eta>0$ and
$\sigma\in\operatorname{Hom}_{\mathrm{unif}}(\Gamma,\operatorname{Sym}(kn))$,
let $X_{\sigma}^{\eta}$ denote the set of $\mathbf{x}\in(\mathbb{Z}_{2})^{kn}$
for which the sum around all but at most a fraction $\eta$ of each of the $d$
hyper-edges types is even. More formally,

$X_{\sigma}^{\eta}=\bigcap_{i\in[d]}\left\\{\mathbf{x}\in(\mathbb{Z}_{2})^{kn}\,:\,\left\lvert\left\\{v\in[kn]\,:\,\sum_{j=0}^{k-1}\mathbf{x}(\sigma_{i}^{j}v)=0\pmod{2}\right\\}\right\rvert>kn(1-\eta)\right\\}.$

We can think of these as “approximate codewords.”

For $t\in[0,1]$ we define the upper exponential growth rate of the expected
number of approximate codewords of density $t$ by

$G_{\mathrm{cw}}(t)=\inf_{\varepsilon,\eta>0}\limsup_{n\to\infty}\frac{1}{kn}\log\operatorname*{\mathbb{E}}_{\sigma\sim\mathbb{P}_{kn}}\left\lvert\\{\mathbf{x}\in
X_{\sigma}^{\eta}\,:\,\tfrac{1}{kn}\lvert\mathbf{x}\rvert\in(t-\varepsilon,\,t+\varepsilon)\\}\right\rvert.$

######  Proposition 10.1.

For any $d,k$,

$G_{\mathrm{cw}}(t)=\frac{1}{2}t\big{(}d\log(k-1)-d+2+(d-2)\log(t)\big{)}+O(t^{2}).$

In particular, for $k\geq 2$ this is negative for small $t>0$ if and only if
$d>2$.

The “$O(t^{2})$” term here is a power series convergent on some neighborhood
of $t=0$ with lowest-order term $t^{2}$.

Figure 2 compares exact plots of $G_{\mathrm{cw}}(t)$ (created using
parametric plots in the parameter $s$ of Lemma 10.2) with plots of this
approximation.

Figure 2: Comparison of $G_{\mathrm{cw}}(t)$ (solid lines) with asymptotic in
Proposition 10.1 (dashed lines) for $k=6$ and several choices of $d$.

The proof of Proposition 10.1 is based on the following lemma.

######  Lemma 10.2.

For any $k,d$ and any $t\in[0,1]$

$G_{\mathrm{cw}}(t)=(1-d)\operatorname{H}(t)+\frac{k}{d}\left(-kt\log s+\log
Z\right),$

where $s$ and $Z$ are related to $t$ via

$t=s\frac{(1+s)^{k-1}-(1-s)^{k-1}}{(1+s)^{k}+(1-s)^{k}}\quad\text{and}\quad
Z=\frac{1}{2}\left((1+s)^{k}+(1-s)^{k}\right).$

###### Proof of Lemma 10.2.

Here, let $\mathtt{A}=\mathbb{Z}_{2}$. We also let $\mathcal{W}$ denote the
set of weights which have edge weights that are cyclically invariant and
supported on configurations with even parity. The terminology of weights was
defined in Section 3.2.

We first show that, for every $t\in[0,1]$,

$G_{\mathrm{cw}}(t)=\sup_{W\in\mathcal{W}\,:\,W(1)=t}\mathrm{H_{K}}(W).$ (35)

First suppose $W\in\mathcal{W}$ has $W(1)=t$. For every $\varepsilon,\eta>0$,
if $\delta>0$ is small enough then we always have

$\\{\mathbf{x}\in(\mathbb{Z}_{2})^{kn}\,:\,\|W_{\sigma,\mathbf{x}}-W\|<\delta\\}\subseteq\\{\mathbf{x}\in
X_{\sigma}^{\eta}\,:\,\tfrac{1}{kn}\lvert\mathbf{x}\rvert\in(t-\varepsilon,t+\varepsilon)\\}.$

By Proposition 3.1, this implies that $\mathrm{H_{K}}(W)\leq
G_{\mathrm{cw}}(t)$, which gives one half of Eqn. 35.

For the converse inequality: Given $\varepsilon,\eta>0$ let
$\mathcal{W}_{\varepsilon,\eta}$ be the set of cyclically-invariant weights
with $\lvert W(1)-t\rvert<\varepsilon$ and each $W(\cdot;i)$ giving mass at
least $1-\eta$ to even-parity configurations.

Given $\delta>0$, by Proposition 3.1 for each weight $W$ there is some
$r_{W}>0$ which satisfies

$\limsup_{n\to\infty}\frac{1}{kn}\log\operatorname*{\mathbb{E}}_{\sigma}\lvert\\{\mathbf{x}\in(\mathbb{Z}_{2})^{kn}\,:\,\|W_{\sigma,\mathbf{x}}-W\|<r_{W}\\}\rvert\leq\mathrm{H_{K}}(W)+\delta.$

By compactness, there is a finite set
$\mathcal{S}\subset\overline{\mathcal{W}_{\varepsilon,\eta}}$ such that the
balls centered at $W\in\mathcal{S}$ of radius $r_{W}$ cover
$\mathcal{W}_{\varepsilon,\eta}$. Then we have

$\\{\mathbf{x}\in
X_{\sigma}^{\eta}\,:\,\tfrac{1}{kn}\lvert\mathbf{x}\rvert\in(t-\varepsilon,t+\varepsilon)\\}\subseteq\bigcup_{W\in\mathcal{S}}\\{\mathbf{x}\in(\mathbb{Z}_{2})^{kn}\,:\,\|W_{\sigma,\mathbf{x}}-W\|<r_{W}\\}.$

Therefore,

$\displaystyle\limsup_{n\to\infty}$
$\displaystyle\frac{1}{kn}\log\operatorname*{\mathbb{E}}_{\sigma}\lvert\\{\mathbf{x}\in
X_{\sigma}^{\eta}\,:\,\tfrac{1}{kn}\lvert\mathbf{x}\rvert\in(t-\varepsilon,t+\varepsilon)\\}\rvert$
$\displaystyle\leq\max_{W\in\overline{\mathcal{W}_{\varepsilon,\eta}}}\limsup_{n\to\infty}\frac{1}{kn}\log\operatorname*{\mathbb{E}}_{\sigma}\lvert\\{\mathbf{x}\in(\mathbb{Z}_{2})^{kn}\,:\,\|W_{\sigma,\mathbf{x}}-W\|<r_{W}\\}\rvert$
$\displaystyle\leq\max_{W\in\overline{\mathcal{W}_{\varepsilon,\eta}}}\mathrm{H_{K}}(W)+\delta.$

Taking $\varepsilon,\eta$ and then $\delta$ to 0 gives the other half of Eqn.
35.

Now any weight achieving the supremum in 35 must have all edge weights equal:
to maximize $\mathrm{H_{K}}$ under the constraint $W(1)=t$, whichever
$W(\cdot;i)$ maximizes the edge term in the definition of $\mathrm{H_{K}}(W)$
should be used for all $i\in[d]$.

We can specify such a weight by a single probability vector
$\mathbf{p}\in\operatorname{Prob}(\mathtt{A}^{\mathbb{Z}_{k}}/\mathbb{Z}_{k})$
recording the edge weight. We use a probability measure on
$\mathtt{A}^{\mathbb{Z}_{k}}/\mathbb{Z}_{k}$ rather than
$\mathtt{A}^{\mathbb{Z}_{k}}$ because the edge weights must be invariant under
cyclic permutations. Let $W_{\mathbf{p}}$ be the weight with edge weights
specified by $\mathbf{p}$, and write $\alpha(\mathbf{p})=W_{\mathbf{p}}(1)$.
The Kikuchi entropy of $W_{\mathbf{p}}$ is

$\mathrm{H_{K}}(W_{\mathbf{p}})=(1-d)\operatorname{H}(\alpha(\mathbf{p}))+\frac{d}{k}\left(\operatorname{H}(\mathbf{p})+\sum_{[\mathbf{a}]\in\mathtt{A}^{\mathbb{Z}_{k}}/\mathbb{Z}_{k}}\mathbf{p}([\mathbf{a}])\log\lvert[\mathbf{a}]\rvert\right)$

where $\lvert[\mathbf{a}]\rvert$ is the number of elements of the equivalence
class $[\mathbf{a}]\in\mathtt{A}^{\mathbb{Z}_{k}}/\mathbb{Z}_{k}$.

Now, we are interested in estimating

$G_{\mathrm{cw}}(t)=\max_{\mathbf{p}\,:\,\alpha(\mathbf{p})=t}\mathrm{H_{K}}(W_{\mathbf{p}}),$

where the maximum is also constrained to $\mathbf{p}$ supported on equivalence
classes of even-parity configurations. Since $\alpha(\mathbf{p})$ is fixed to
be $t$, we really just need to maximize

$\operatorname{H}(\mathbf{p})+\sum_{[\mathbf{a}]\in\mathtt{A}^{\mathbb{Z}_{k}}/\mathbb{Z}_{k}}\mathbf{p}([\mathbf{a}])\log\lvert[\mathbf{a}]\rvert$

subject to the constraints

$\sum_{[\mathbf{a}]}\mathbf{p}([\mathbf{a}])\alpha([\mathbf{a}])=kt\quad\text{and}\quad\sum_{[\mathbf{a}]}\mathbf{p}([\mathbf{a}])=1$

where $\alpha([\mathbf{a}])$ is the number of $1$’s in any representative of
$[\mathbf{a}]$. So we get two Lagrange multipliers $\lambda_{1},\lambda_{2}$
so that a maximizer on the interior of the constraint region is given by

$\mathbf{p}([\mathbf{a}])=\lvert[\mathbf{a}]\rvert\cdot
e^{\lambda_{1}\alpha([\mathbf{a}])+\lambda_{2}+1}$

for $[\mathbf{a}]\in\mathtt{A}^{\mathbb{Z}_{k}}/\mathbb{Z}_{k}$ with even
parity and 0 otherwise. We rewrite this as

$\mathbf{p}([\mathbf{a}])=\lvert[\mathbf{a}]\rvert\cdot\frac{s^{\alpha([\mathbf{a}])}}{Z}$

where $Z$ is determined by the normalization constraint and $s$ is determined
by the density-$t$ constraint. Since the objective function is strictly
concave, the critical point given by these $Z,s$ is in fact the unique
maximum. The corresponding $\mathrm{H_{K}}$-maximizing weight $W$ therefore
satisfies

$W(\mathbf{a};i)=\frac{s^{\alpha(\mathbf{a})}}{Z}$

if $\alpha(\mathbf{a})$ (the number of $1$’s in $\mathbf{a}$) is even and
$W(\mathbf{a};i)=0$ otherwise.

Note that

$Z=\frac{1}{2}\left((1+s)^{k}+(1-s)^{k}\right)$ (36)

since

$Z=\sum_{\begin{subarray}{c}\mathbf{a}\in\mathtt{A}^{k}\\\
\alpha(\mathbf{a})\text{
even}\end{subarray}}s^{\alpha(\mathbf{a})}=\sum_{\begin{subarray}{c}m=0\\\
m\text{
even}\end{subarray}}^{k}s^{m}\binom{k}{m}=\frac{1}{2}\left(\sum_{m=0}^{k}s^{m}\binom{k}{m}+\sum_{m=0}^{k}(-s)^{m}\binom{k}{m}\right).$

The constraint
$\sum_{[\mathbf{a}]}\mathbf{p}([\mathbf{a}])\,\alpha([\mathbf{a}])=kt$ gives
the relation between $t$ and $s$:

$kt=\sum_{[\mathbf{a}]\text{
even}}\lvert[\mathbf{a}]\rvert\frac{s^{\alpha([\mathbf{a}])}}{Z}\cdot\alpha([\mathbf{a}])=s\frac{\frac{dZ}{ds}}{Z}=sk\frac{(1+s)^{k-1}-(1-s)^{k-1}}{(1+s)^{k}+(1-s)^{k}}.$

Finally, we can calculate

$\operatorname{H}(W(\cdot;i))=-\sum_{\mathbf{a}\text{
even}}\frac{s^{\alpha(\mathbf{a})}}{Z}\alpha(\mathbf{a})\log s+\log Z=-kt\log
s+\log Z$

which gives the claimed formula. ∎

This lemma does not give an explicit formula for $G_{\mathrm{cw}}(t)$: we have
$t$ as a function of $s$ but we do not have an explicit formula for the
inverse function. Still, we can use it to prove Proposition 10.1.

###### Proof of Proposition 10.1.

Expanding the formula for $t$ as a power series centered at $s=0$, we get
$t=(k-1)s^{2}+O(s^{4})$ so, by Lagrange inversion [69, §7.32], there is a
power series for $s^{2}$ on some interval around $0$ of the form

$s^{2}=\frac{t}{k-1}+O(t^{2}).$

Hence

$t\log s=\frac{1}{2}t\log\frac{t}{k-1}+O(t^{2})$

and

$\log Z=\frac{1}{2}k(k-1)s^{2}+O(s^{4})=\frac{1}{2}kt+O(t^{2}).$

The estimate for Shannon entropy

$\operatorname{H}(t)=-t\log t-t+O(t^{2})$

completes the proof. ∎

####  10.2 Proof of Theorem 6.1(3)

Recall that $\mu$ has totally shattered microstate spaces along
$(\sigma_{n})_{n}$ if there exists a $\delta>0$ for which the following holds:
For every $\varepsilon>0$ there exist a weak∗ neighbourhood $U$ 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},U)$ we have either
$\textrm{d}^{(V_{n})}(\mathbf{x},\mathbf{y})\geq\delta$ or
$\textrm{d}^{(V_{n})}(\mathbf{x},\mathbf{y})<\varepsilon$.

###### Proof of Theorem 6.1(3).

Given $k\geq 2$ and $d>2$ by Proposition 10.1 there is some $\delta>0$ such
that $G_{\mathrm{cw}}(t)<0$ for $t\in(0,\delta)$. We will use this $\delta$ to
establish totally shattered microstates.

For any fixed $\varepsilon>0$,

$\inf_{\eta>0}\limsup_{n\to\infty}\frac{1}{n}\log\operatorname*{\mathbb{E}}|\\{\mathbf{x}\in
X_{n}^{\eta}\,:\,\tfrac{1}{n}|\mathbf{x}|\in[\varepsilon,\delta]\\}|=\sup\\{G_{\mathrm{cw}}(t)\,:\,t\in(\varepsilon,\delta)\\}<0.$

Pick some $\eta$ such that the expression in the infimum is negative, and let
$U^{\eta}\subset\operatorname{Prob}(\mathbb{Z}_{2}^{\Gamma})$ be the set of
all probability measures whose marginal on every hyper-edge gives probability
greater than $1-\eta$ to labelings with even parity. Then $U^{\eta}$ is a
weak∗ neighborhood of $m_{X}$ and

$X_{n}^{\eta}=\Omega(\sigma_{n},U^{\eta}),$

so

$\limsup_{n\to\infty}\frac{1}{n}\log\operatorname*{\mathbb{E}}|\\{\mathbf{x}\in\Omega(\sigma_{n},U^{\eta})\,:\,\tfrac{1}{n}|\mathbf{x}|\in[\varepsilon,\delta]\\}|<0$

and there are subsets
$\Omega_{n}^{\varepsilon}\subset\Omega_{n}^{\mathrm{sofic}}$ with
$\mathbb{P}_{n}(\Omega_{n}^{\varepsilon})\to 1$ and such that for all large
enough $n$ if $\sigma_{n}\in\Omega_{n}^{\varepsilon}$ then
$\\{\mathbf{x}\in\Omega(\sigma_{n},U^{\eta})\,:\,\tfrac{1}{n}|\mathbf{x}|\in[\varepsilon,\delta]\\}=\varnothing$.
Now if $\mathbf{x},\mathbf{y}\in\Omega(\sigma_{n},U^{\eta/2})$, then
$\mathbf{x}+\mathbf{y}\in\Omega(\sigma_{n},U^{\eta})$ so

$\textrm{d}^{(V_{n})}(\mathbf{x},\mathbf{y})=\tfrac{1}{n}|\mathbf{x}+\mathbf{y}|\notin[\varepsilon,\delta].$

We can then get a single sequence $\Omega_{n}^{\prime}$ that works for every
$\varepsilon$ by picking one for each
$\varepsilon=\frac{1}{2},\frac{1}{3},\ldots$ and then using a diagonal
argument. ∎

####  10.3 Proof of Theorem C

Theorem C is an immediate consequence of Corollary 5.5(3) and Theorem 6.1(3).

###  11 Directions for further study

A probability measure-preserving action $\Gamma{\curvearrowright}(X,\mu)$ is
anti-Pinkser if it has positive entropy but does not have any nontrivial
direct Bernoulli factors. We are being deliberately vague here by not
specifying whether “positive entropy” refers to sofic, Rokhlin or some other
notion of entropy.

####  11.1 Possible anti-Pinsker actions of other groups

  1. 1.

Are there explicit anti-Pinsker actions of a free group? One candidate is the
frozen model associated to independent sets [24].

  2. 2.

Do all non-amenable groups admit anti-Pinsker actions? Here it might be
necessary to use Rokhlin rather than sofic entropy.

  3. 3.

Given a positive number $h$ and a non-amenable group $\Gamma$, does there
exist an uncountable family of pairwise non-measurably conjugate ergodic pmp
actions of $\Gamma$ which are anti-Pinsker, have completely positive sofic
entropy and have sofic entropy $h$ (with respect to some fixed sofic
approximation)? Starting from the example of the present paper, one place to
look might be among its ‘typical’ compact extensions.

####  11.2 Open problems for the parity-check subshift

Let $(X,m_{X},T)$ be the system in Theorem A.

  1. 1.

Does there exist a sofic approximation $\Sigma$ to $\Gamma$ with respect to
which $(X,m_{X},T)$ does not have completely positive sofic entropy?

  2. 2.

Is $(X,m_{X},T)$ finitely determined? This would mean that, if
$(\\{0,1\\}^{\Gamma},\mu,T)$ is another system for which $\mu$ is close to
$m_{X}$ both in sofic entropy and in the weak∗ topology, then there is a
joining of these two systems under which the identity coordinates agree with
high probability. This property characterizes those processes isomorphic to
Bernoulli shifts over amenable groups [53], but little is known about it for
non-amenable groups.

  3. 3.

Formally, the family of equations that defines our LDPC shift $X$ can be used
to define a system of algebraic origin inside $A^{\Gamma}$ for another compact
Abelian group $A$, such as a finite cyclic group or the continuous circle
$\mathbb{R}/\mathbb{Z}$. For which such $A$ (and which values of $d$ and $k$)
is the resulting system still anti-Pinsker? If there are such examples with
$A=\mathbb{R}/\mathbb{Z}$, do these have infinite sofic entropy?

###  Appendix A A failure of contiguity

Let $V$ be a vertex set of size $n$ divisible by $k$, let $E$ be a set of size
$dn/k$, and let $\tilde{\mathbb{P}}_{n}$ be the measure on $k$-uniform
$d$-regular factor graphs on $(V,E)$ that is constructed in Section 6.3. In
addition, let $\mathbb{P}_{n}^{\mathrm{unif}}$ be the uniform distribution on
all such $k$-uniform $d$-regular factor graphs on $(V,E)$ produced without
respect to a partition $E=\bigsqcup_{i\in[d]}E_{i}$.

######  Proposition A.1.

Let $k>d\geq 3$, and let

$U_{n}:=\left\\{H\subset V\times E:\ \exists E^{\prime}\subseteq E\ \hbox{with
every $v\in V$ adj.~{}to exactly two elements of }E^{\prime}\right\\}.$

Then $\tilde{\mathbb{P}}_{n}(U_{n})=1$ for all $n$, but
$\mathbb{P}_{n}^{\mathrm{unif}}(U_{n})\to 0$ as $n\to\infty$. As a result, the
models $\tilde{\mathbb{P}}_{n}$ and $\mathbb{P}_{n}^{\mathrm{unif}}$ are not
contiguous.

Note that the definition of $U_{n}$ ensures that the contiguity also fails for
the associated multi-hyper-graph models with unlabeled hyper-edges.

###### Proof.

If $H$ arises from $\tilde{\mathbb{P}}_{n}$, then let $i,j\in[d]$ be distinct
and let $E^{\prime}=E_{i}\cup E_{j}$. Then every vertex is adjacent to exactly
one check node in each of $E_{i},E_{j}$, and in particular to exactly two
check nodes in $E^{\prime}$.

On the other hand, the very precise calculations in [46] show that, with high
probability according to $\mathbb{P}_{n}^{\mathrm{unif}}$, the transposed
parity-check matrix associated to $H$ has kernel that is either trivial (if
$d$ is odd) or one-dimensional (if $d$ is even, in which case the all 1’s
vector is in the kernel). In either case, there can be no $E^{\prime}$ as
promised by the event $U_{n}$, since it would give an additional nontrivial
element of the kernel. ∎

### References

  * [1] Dimitris Achlioptas and Federico Ricci-Tersenghi.  On the solution-space geometry of random constraint satisfaction problems.  In STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 130–139. ACM, New York, 2006.
  * [2] Dylan Airey, Lewis Bowen, and Yuqing Lin.  A topological dynamical system with two different positive sofic entropies.  Transactions of the American Mathematical Society, Series B, 9(2):35–98, February 2022.
  * [3] Tim Austin.  Additivity Properties of Sofic Entropy and Measures on Model Spaces.  Forum of Mathematics, Sigma, 4, 2016.
  * [4] Tim Austin.  The Geometry of Model Spaces for Probability-Preserving Actions of Sofic Groups.  Analysis and Geometry in Metric Spaces, 4(1), August 2016.
  * [5] Tim Austin.  Measure concentration and the weak Pinsker property.  Publ. Math. Inst. Hautes Études Sci., 128:1–119, 2018.
  * [6] Tim Austin.  Multi-variate correlation and mixtures of product measures.  Kybernetika, pages 459–499, July 2020.
  * [7] Tim Austin and Peter Burton.  Uniform mixing and completely positive sofic entropy.  J. Anal. Math., 138(2):597–612, 2019.
  * [8] H.A. Bethe.  Statistical Theory of Superlattices.  Proc. Roy. Soc. London Ser. A, 152:552–575, 1935.
  * [9] Lewis Bowen.  The ergodic theory of free group actions: Entropy and the f-invariant.  Groups, Geometry, and Dynamics, pages 419–432, 2010.
  * [10] Lewis Bowen.  A measure-conjugacy invariant for free group actions.  Ann. of Math. (2), 171(2):1387–1400, 2010.
  * [11] Lewis Bowen.  Measure conjugacy invariants for actions of countable sofic groups.  J. Amer. Math. Soc., 23(1):217–245, 2010.
  * [12] Lewis Bowen.  Every countably infinite group is almost Ornstein.  In Dynamical systems and group actions, volume 567 of Contemp. Math., pages 67–78. Amer. Math. Soc., Providence, RI, 2012.
  * [13] Lewis Bowen.  A brief introduction of sofic entropy theory.  In Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. III. Invited lectures, pages 1847–1866. World Sci. Publ., Hackensack, NJ, 2018.
  * [14] Lewis Bowen.  Finitary random interlacements and the Gaboriau-Lyons problem.  Geom. Funct. Anal., 29(3):659–689, 2019.
  * [15] Lewis Bowen.  Examples in the entropy theory of countable group actions.  Ergodic Theory Dynam. Systems, 40(10):2593–2680, 2020.
  * [16] Lewis Bowen.  Sofic homological invariants and the Weak Pinsker Property.  American Journal of Mathematics, 144(1):169–226, 2022.
  * [17] Lewis Bowen and Robin D. Tucker-Drob.  Superrigidity, measure equivalence, and weak Pinsker entropy.  Groups Geom. Dyn., 16(1):247–286, 2022.
  * [18] Peter J. Burton and Alexander S. Kechris.  Weak containment of measure-preserving group actions.  Ergodic Theory and Dynamical Systems, 40(10):2681–2733, October 2020.
  * [19] P. J. Cameron and J. H. van Lint.  Designs, graphs, codes and their links, volume 22 of London Mathematical Society Student Texts.  Cambridge University Press, Cambridge, 1991.
  * [20] Valerio Capraro and Martino Lupini.  Introduction to Sofic and hyperlinear groups and Connes’ embedding conjecture, volume 2136 of Lecture Notes in Mathematics.  Springer, Cham, 2015.  With an appendix by Vladimir Pestov.
  * [21] Amin Coja-Oghlan and Charilaos Efthymiou.  On independent sets in random graphs.  Random Structures Algorithms, 47(3):436–486, 2015.
  * [22] Thomas M. Cover and Joy A. Thomas.  Elements of information theory.  Wiley-Interscience [John Wiley & Sons], Hoboken, NJ, second edition, 2006\.
  * [23] Amir Dembo, Andrea Montanari, Allan Sly, and Nike Sun.  The replica symmetric solution for Potts models on $d$-regular graphs.  Comm. Math. Phys., 327(2):551–575, 2014.
  * [24] Jian Ding, Allan Sly, and Nike Sun.  Maximum independent sets on random regular graphs.  Acta Mathematica, 217(2):263–340, 2016.
  * [25] C. Domb and M. S. Green, editors.  Phase transitions and critical phenomena. Vol. 2.  Academic Press, London-New York, 1972.
  * [26] Gábor Elek and Endre Szabó.  Sofic groups and direct finiteness.  J. Algebra, 280(2):426–434, 2004.
  * [27] William Feller.  An introduction to probability theory and its applications. Vol. I.  John Wiley & Sons, Inc., New York-London-Sydney, third edition, 1968\.
  * [28] Yaotian Fu and P. W. Anderson.  Application of statistical mechanics to ${\rm NP}$-complete problems in combinatorial optimisation.  J. Phys. A, 19(9):1605–1620, 1986.
  * [29] R. G. Gallager.  Low-density parity-check codes.  MIT PhD thesis, now available online at http://www.inference.org.uk/mackay/gallager/papers/ldpc.pdf.
  * [30] R. G. Gallager.  Low-density parity-check codes.  IRE Trans., IT-8:21–28, 1962.
  * [31] David Gamarnik.  The overlap gap property: A topological barrier to optimizing over random structures.  Proceedings of the National Academy of Sciences, 118(41), October 2021.  Available online at arXiv.org: 2109.14409.
  * [32] David Gamarnik and Madhu Sudan.  Limits of local algorithms over sparse random graphs.  Ann. Probab., 45(4):2353–2376, 2017.
  * [33] Catherine Greenhill, Svante Janson, Jeong Han Kim, and Nicholas C. Wormald.  Permutation pseudographs and contiguity.  Combinatorics, Probability and Computing, 11:273–298, 2002.
  * [34] M. Gromov.  Endomorphisms of symbolic algebraic varieties.  J. Eur. Math. Soc. (JEMS), 1(2):109–197, 1999.
  * [35] David Kerr and Hanfeng Li.  Ergodic theory.  Springer Monographs in Mathematics. Springer, Cham, 2016.  Independence and dichotomies.
  * [36] J. C. Kieffer.  A generalized Shannon-McMillan theorem for the action of an amenable group on a probability space.  Ann. Probability, 3(6):1031–1037, 1975.
  * [37] R. Kikuchi.  A Theory of Cooperative Phenomena.  Physical Review, 81:988–1003, 1951.
  * [38] A. N. Kolmogorov.  A new metric invariant of transient dynamical systems and automorphisms in Lebesgue spaces.  Dokl. Akad. Nauk SSSR (N.S.), 119:861–864, 1958.
  * [39] A. N. Kolmogorov.  Entropy per unit time as a metric invariant of automorphisms.  Dokl. Akad. Nauk SSSR, 124:754–755, 1959.
  * [40] Florent Krza̧kała, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborová.  Gibbs states and the set of solutions of random constraint satisfaction problems.  Proc. Natl. Acad. Sci. USA, 104(25):10318–10323, 2007.
  * [41] Russell Lyons.  Factors of IID on Trees.  Combinatorics, Probability and Computing, 26(2):285–300, March 2017\.
  * [42] David J. C. MacKay.  Good error-correcting codes based on very sparse matrices.  IEEE Trans. Inform. Theory, 45(2):399–431, 1999.
  * [43] David J. C. MacKay.  Information theory, inference and learning algorithms.  Cambridge University Press, New York, 2003.
  * [44] Marc Mézard and Andrea Montanari.  Information, Physics, and Computation.  Oxford University Press, January 2009.
  * [45] Marc Mézard, Giorgio Parisi, and Miguel Angel Virasoro.  Spin glass theory and beyond, volume 9 of World Scientific Lecture Notes in Physics.  World Scientific Publishing Co., Inc., Teaneck, NJ, 1987.
  * [46] Gadi Miller and Gérard Cohen.  The rate of regular LDPC codes.  IEEE Trans. Inform. Theory, 49(11):2989–2992, 2003.
  * [47] Donald Ornstein.  Bernoulli shifts with the same entropy are isomorphic.  Advances in Math., 4:337–352 (1970), 1970.
  * [48] Donald Ornstein.  Two Bernoulli shifts with infinite entropy are isomorphic.  Advances in Math., 5:339–348 (1970), 1970.
  * [49] Donald S. Ornstein.  An example of a Kolmogorov automorphism that is not a Bernoulli shift.  Advances in Math., 10:49–62, 1973.
  * [50] Donald S. Ornstein.  A $K$ automorphism with no square root and Pinsker’s conjecture.  Advances in Math., 10:89–102, 1973.
  * [51] Donald S. Ornstein.  A mixing transformation for which Pinsker’s conjecture fails.  Advances in Math., 10:103–123, 1973.
  * [52] Donald S. Ornstein and Paul C. Shields.  An uncountable family of $K$-automorphisms.  Advances in Math., 10:63–88, 1973.
  * [53] Donald S. Ornstein and Benjamin Weiss.  Entropy and isomorphism theorems for actions of amenable groups.  J. Analyse Math., 48:1–141, 1987.
  * [54] Vladimir G. Pestov.  Hyperlinear and sofic groups: a brief guide.  Bull. Symbolic Logic, 14(4):449–480, 2008.
  * [55] Sorin Popa and Roman Sasyk.  On the cohomology of Bernoulli actions.  Ergodic Theory Dynam. Systems, 27(1):241–251, 2007.
  * [56] Tom Richardson and Rüdiger Urbanke.  Modern Coding Theory.  Cambridge University Press, first edition, March 2008.
  * [57] Daniel J. Rudolph and Benjamin Weiss.  Entropy and mixing for amenable group actions.  Ann. of Math. (2), 151(3):1119–1150, 2000.
  * [58] Brandon Seward.  Krieger’s finite generator theorem for actions of countable groups I.  Invent. Math., 215(1):265–310, 2019.
  * [59] Brandon Seward.  Krieger’s finite generator theorem for actions of countable groups II.  J. Mod. Dyn., 15:1–39, 2019.
  * [60] Brandon Seward.  Positive entropy actions of countable groups factor onto Bernoulli shifts.  J. Amer. Math. Soc., 33(1):57–101, 2020.
  * [61] Brandon Seward.  Bernoulli shifts with bases of equal entropy are isomorphic.  J. Mod. Dyn., 18:345–362, 2022.
  * [62] Ja. G. Sinaĭ.  On a weak isomorphism of transformations with invariant measure.  Mat. Sb. (N.S.), 63 (105):23–42, 1964.
  * [63] A. M. Stepin.  Bernoulli shifts on groups.  Dokl. Akad. Nauk SSSR, 223(2):300–302, 1975.
  * [64] J.-P. Thouvenot.  On the stability of the weak Pinsker property.  Israel J. Math., 27(2):150–162, 1977.
  * [65] Martin J. Wainwright and Michael I. Jordan.  Graphical Models, Exponential Families, and Variational Inference.  Foundations and Trends in Machine Learning, 1(1-2):1–305, 2008\.
  * [66] Satosi Watanabe.  Information Theoretical Analysis of Multivariate Correlation.  IBM Journal of Research and Development, 4(1):66–82, January 1960\.
  * [67] Benjamin Weiss.  Sofic groups and dynamical systems.  Sankhyā Ser. A, 62(3):350–359, 2000.  Ergodic theory and harmonic analysis (Mumbai, 1999).
  * [68] Benjamin Weiss.  Actions of amenable groups.  In Topics in dynamics and ergodic theory, volume 310 of London Math. Soc. Lecture Note Ser., pages 226–262. Cambridge Univ. Press, Cambridge, 2003.
  * [69] E. T. Whittaker and G. N. Watson.  A course of modern analysis—an introduction to the general theory of infinite processes and of analytic functions with an account of the principal transcendental functions.  Cambridge University Press, Cambridge, fifth edition, 2021.  Edited by Victor H. Moll, With a foreword by S. J. Patterson, For an unaltered reprint of the fourth edition see [ 0178117].
  * [70] N. C. Wormald.  Models of random regular graphs.  In Surveys in combinatorics, 1999 (Canterbury), volume 267 of London Math. Soc. Lecture Note Ser., pages 239–298. Cambridge Univ. Press, Cambridge, 1999.
  * [71] Jonathan Yedidia.  An Idiosyncratic Journey Beyond Mean Field Theory.  Technical Report TR-2000-27, Mitsubishi Electric Res. Lab., June 2000\.
  * [72] Jonathan Yedidia, William Freeman, and Yair Weiss.  Bethe free energy, Kikuchi approximations, and belief propagation algorithms.  Technical Report TR-2001-16, Mitsubishi Electric Res. Lab., May 2001.