$\mathbb{E}[\boldsymbol{k}^{2}]=O(1)$ and the first equality sign follows
because ${\boldsymbol{m}}_{\varepsilon}^{+}$ is independent of
$\boldsymbol{d}_{n+1}$ and the $\boldsymbol{k}_{i}$. Further, to obtain the
first inequality we consider the ${\boldsymbol{m}}_{\varepsilon}^{+}$ checks
one by one. The degree of the $i$th check is distributed as
$\boldsymbol{k}_{i}$. We discard it unless $\boldsymbol{k}_{i}\geq\log n$. But
if $\boldsymbol{k}_{i}\geq\log n$, then the probability that
$\boldsymbol{k}_{i}$ is adjacent to $x_{n+1}$ is bounded by
$O(\boldsymbol{k}_{i}\boldsymbol{d}_{n+1}/\sum_{h=1}^{n+1}\boldsymbol{d}_{h})$
and $\sum_{h=1}^{n+1}\boldsymbol{d}_{h}>n$. Thus, we obtain (3.43). Further,
we observe that (3.43) yields
${\mathbb{P}}\left[{\mathcal{Q}_{1}}\right]\leq\mathbb{E}\sum_{i\geq
3}i{\boldsymbol{\gamma}}_{i}\boldsymbol{1}\mathcal{Q}_{1}=O(\log^{-2}n).$
Hence, as $\mathbb{E}\sum_{i\geq 3}i{\boldsymbol{\Delta}}_{i}=O(1)$ we obtain

$\displaystyle\mathbb{E}\left[{\sum_{i\geq
3}i{\boldsymbol{\Delta}}_{i}\boldsymbol{1}\mathcal{Q}_{1}}\right]$
$\displaystyle\leq{\mathbb{P}}\left[{\mathcal{Q}_{1}}\right]\log
n+\mathbb{E}\left[{\sum_{i\geq
3}i{\boldsymbol{\Delta}}_{i}\boldsymbol{1}\left\\{{\sum_{i\geq
3}i{\boldsymbol{\Delta}}_{i}\geq\log n}\right\\}}\right]=o(1).$ (3.44)

Combining (3.41), (3.43) and (3.44), we conclude that

$\displaystyle\mathbb{E}\left[{\left|{\operatorname{nul}(\boldsymbol{A}_{n+1,\boldsymbol{M}^{+}})-\operatorname{nul}(\boldsymbol{A}^{\prime\prime\prime})}\right|\boldsymbol{1}\mathcal{Q}_{1}}\right]$
$\displaystyle=o(1).$ (3.45)

Regarding $\mathcal{Q}_{2}$, we deduce from the bound
$\mathbb{E}[\boldsymbol{d}_{n+1}^{r}]=O(1)$ for an $r>2$ that

$\displaystyle\mathbb{E}\left[{\sum_{i\geq
3}i{\boldsymbol{\gamma}}_{i}\boldsymbol{1}\mathcal{Q}_{2}}\right]$
$\displaystyle\leq O(\log
n)\mathbb{E}\left[{\boldsymbol{d}_{n+1}\boldsymbol{1}\\{\boldsymbol{d}_{n+1}>\log
n\\}}\right]=o(1).$

Moreover, since the ${\boldsymbol{\Delta}}_{i}$ are independent of
$\boldsymbol{d}_{n+1}$ and $\mathbb{E}\sum_{i\geq
3}i{\boldsymbol{\Delta}}_{i}=O(1)$, we obtain $\mathbb{E}\left[{\sum_{i\geq
3}i{\boldsymbol{\Delta}}_{i}\boldsymbol{1}\mathcal{Q}_{2}}\right]=o(1)$.
Hence, (3.41) yields

$\displaystyle\mathbb{E}\left[{\left|{\operatorname{nul}(\boldsymbol{A}_{n+1,\boldsymbol{M}^{+}})-\operatorname{nul}(\boldsymbol{A}^{\prime\prime\prime})}\right|\boldsymbol{1}\mathcal{Q}_{2}}\right]$
$\displaystyle=o(1).$ (3.46)

Moving on to $\mathcal{Q}_{3}$, we find

$\displaystyle{\mathbb{P}}\left[{\mathcal{Q}_{3}}\right]$
$\displaystyle\leq\mathbb{E}\left[{\sum_{i\geq
3}i{\boldsymbol{\Delta}}_{i}}\right]\ln^{-3}n=O(\mathbb{E}[\boldsymbol{k}^{2}]\ln^{-3}n)=o(\log^{-2}n).$

Moreover, on $\mathcal{Q}_{3}$ we have $\sum_{i\geq
3}i{\boldsymbol{\gamma}}_{i}\leq\log^{2}n$ because
$\boldsymbol{d}_{n+1}\leq\log n$ and ${\boldsymbol{\gamma}}_{i}=0$ for all
$i\geq\log n$. Consequently, since the ${\boldsymbol{\Delta}}_{i}$ are
mutually independent and $\sum_{i\geq
3}\mathbb{E}[i{\boldsymbol{\Delta}}_{i}]=O(1)$, (3.41) yields

$\displaystyle\mathbb{E}\left[{\left|{\operatorname{nul}(\boldsymbol{A}_{n+1,\boldsymbol{M}^{+}})-\operatorname{nul}(\boldsymbol{A}^{\prime\prime\prime})}\right|\boldsymbol{1}\mathcal{Q}_{3}}\right]$
$\displaystyle\leq o(1)+4\mathbb{E}\left[{\sum_{i\geq
3}i{\boldsymbol{\Delta}}_{i}\boldsymbol{1}\left\\{{\sum_{i\geq
3}i{\boldsymbol{\Delta}}_{i}\geq\ln^{3}n}\right\\}}\right]=o(1).$ (3.47)

Finally, the second assertion follows from (3.40), (3.42), (3.45), (3.46) and
(3.47).

##  4\. The interpolation argument

###  4.1. Proof of Lemma 2.7

Each component of $\boldsymbol{G}_{\varepsilon}(0)$ contains precisely one of
the variable nodes $x_{1},\ldots,x_{n}$. In effect,
$\boldsymbol{A}_{\varepsilon}(0)$ has a block diagonal structure, and the
overall nullity is nothing but the sum of the nullities of the blocks. It
therefore suffices to study the contribution $\boldsymbol{N}_{s}$ of the block
containing $x_{s}$ to $\mathcal{N}_{0}$, i.e.,

$\displaystyle\boldsymbol{N}_{s}$
$\displaystyle=\left({\log_{q}\sum_{\sigma\in\mathbb{F}_{q}^{\\{x_{s}\\}\cup\partial^{2}x_{s}}}\boldsymbol{1}\\{(s>\boldsymbol{\theta}\vee\sigma_{x_{s}}=0)\wedge\forall
y\in\partial^{2}x_{s}\cap\mathcal{F}_{0}:\sigma_{y}=0\\}\boldsymbol{1}\\{\sigma\models
a\\}}\right)-\left|{\partial^{2}x_{s}}\right|+\left|{\partial^{2}x_{s}\cap\mathcal{F}_{0}}\right|.$
(4.1)

Indeed, to see that $\mathcal{N}_{0}=\sum_{s=1}^{n}\boldsymbol{N}_{s}$, we
observe that
$\sum_{s=1}^{n}\left|{\partial^{2}x_{s}}\right|=\sum_{i\leq{\boldsymbol{m}}^{\prime}_{\varepsilon}(0)}\boldsymbol{k}_{i}^{\prime}(\boldsymbol{k}_{i}^{\prime}-1)$
and that
$\sum_{s=1}^{n}\left|{\partial^{2}x_{s}\cap\mathcal{F}_{0}}\right|=|\mathcal{F}_{0}|$.
Moreover, the logarithmic term in (4.1) is just the nullity of the block
containing $x_{s}$. Dragging the last two terms from (4.1) into the logarithm,
we obtain

$\displaystyle\boldsymbol{N}_{s}$
$\displaystyle=\log_{q}\sum_{\sigma\in\mathbb{F}_{q}^{\\{x_{s}\\}\cup\partial^{2}x_{s}}}\boldsymbol{1}\\{s>\boldsymbol{\theta}\vee\sigma_{x_{s}}=0\\}\left({\prod_{y\in\partial^{2}x_{s}\cap\mathcal{F}_{0}}q\boldsymbol{1}\\{\sigma_{y}=0\\}}\right)\left({\prod_{a\in\partial
x_{s}}\frac{\boldsymbol{1}\\{\sigma\models a\\}}{q^{|\partial a|-1}}}\right),$
(4.2)

and
$\mathbb{E}[\mathcal{N}_{0}]=\sum_{s=1}^{n}\mathbb{E}[\boldsymbol{N}_{s}]$.
Consequently, since $\boldsymbol{\theta}=O(1)$ it suffices to prove that

$\displaystyle\mathbb{E}[\boldsymbol{N}_{s}]=\begin{cases}dK^{\prime}(\beta)/k+D(1-K^{\prime}(\beta)/k)-d+o_{\varepsilon}(1)&\mbox{
if }s>\boldsymbol{\theta},\\\ O(1)&\mbox{ otherwise}.\end{cases}$ (4.3)

In fact, the second case in (4.3) simply follows from the bounds
$|\boldsymbol{N}_{s}|\leq\boldsymbol{d}_{s}$ and
$\mathbb{E}[\boldsymbol{d}_{s}]=O(1)$ for all $s$.

Hence, suppose that $s>\boldsymbol{\theta}$. As
$|\boldsymbol{N}_{s}|\leq\boldsymbol{d}_{s}$ and
$\mathbb{E}[\boldsymbol{d}_{s}^{r}]=O_{\varepsilon}(1)$ for an $r>2$ we find
$\xi>0$ such that

$\displaystyle\mathbb{E}[|\boldsymbol{N}_{s}|\boldsymbol{1}\\{\boldsymbol{d}_{s}>\varepsilon^{\xi-1/2}\\}]$
$\displaystyle=o_{\varepsilon}(1).$ (4.4)

Moreover, let
$\Xi=\sum_{i=1}^{{\boldsymbol{m}}_{\varepsilon}^{\prime}(0)}\boldsymbol{k}_{i}^{\prime}\boldsymbol{1}\left\\{{\boldsymbol{k}_{i}^{\prime}>\varepsilon^{-8}}\right\\}$,
$\boldsymbol{M}_{j}^{\prime}=\sum_{i=1}^{{\boldsymbol{m}}_{\varepsilon}^{\prime}(0)}\boldsymbol{1}\\{\boldsymbol{k}_{i}^{\prime}=j\\}.$
Because $\mathbb{E}[\boldsymbol{k}^{2}]=O_{\varepsilon}(1)$ we have

$\displaystyle\mathbb{E}\left[{\Xi}\right]$
$\displaystyle\leq\frac{dn}{k}\mathbb{E}\left[{\boldsymbol{k}\boldsymbol{1}\\{\boldsymbol{k}\geq\varepsilon^{-8}\\}}\right]=nO_{\varepsilon}(\varepsilon^{8}),$
(4.5)

while
$\boldsymbol{M}_{j}^{\prime}\sim(1-\varepsilon)dn{\mathbb{P}}\left[{\boldsymbol{k}=j}\right]/k$
for all $j\leq\varepsilon^{-8}$ w.h.p. by Chebyshev’s inequality. Hence,
introducing the event

$\displaystyle{\mathcal{E}}_{s}$
$\displaystyle=\left\\{{\boldsymbol{d}_{s}\leq\varepsilon^{\xi-1/2},\ \Xi\leq
n\varepsilon^{6},\ \forall
j\leq\varepsilon^{-8}:\boldsymbol{M}_{j}^{\prime}\sim(1-\varepsilon)dn{\mathbb{P}}\left[{\boldsymbol{k}=j}\right]/k,\,\sum_{i=1}^{n}\boldsymbol{d}_{i}\sim
dn,\,\sum_{i\geq
3}i\boldsymbol{M}_{i}^{\prime}\sim(1-\varepsilon)dn}\right\\},$

we obtain from (4.4) and (4.5) that

$\displaystyle\mathbb{E}[\boldsymbol{N}_{s}]$
$\displaystyle=\mathbb{E}\left[{\boldsymbol{N}_{s}\boldsymbol{1}{\mathcal{E}}_{s}}\right]+o_{\varepsilon}(1).$
(4.6)

With $\boldsymbol{d}_{s}^{\star}\leq\boldsymbol{d}_{s}$ the actual degree of
$x_{s}$ in $\boldsymbol{G}_{\varepsilon}(s)$, let
$\boldsymbol{\kappa}_{1},\ldots,\boldsymbol{\kappa}_{\boldsymbol{d}_{s}^{\star}}$
be the degrees of the checks adjacent to $x_{s}$. We claim that given
${\mathcal{E}}_{s}$ and $\boldsymbol{d}_{s}$,

$\displaystyle
d_{\mathrm{TV}}((\boldsymbol{\kappa}_{1},\ldots,\boldsymbol{\kappa}_{\boldsymbol{d}_{s}^{\star}}),(\hat{\boldsymbol{k}}_{1},\ldots,\hat{\boldsymbol{k}}_{\boldsymbol{d}_{s}}))$
$\displaystyle=o_{\varepsilon}(\varepsilon^{1/2}).$ (4.7)

Indeed, on ${\mathcal{E}}_{s}$ the probability that $x_{s}$ is adjacent to a
check of degree greater than $\varepsilon^{-8}$ is
$O_{\varepsilon}(\boldsymbol{d}_{s}\Xi/\sum_{j\geq
3}j\boldsymbol{M}_{j}^{\prime})=o_{\varepsilon}(\varepsilon)$. Further, given
${\mathcal{E}}_{s}$ we have $\sum_{j\geq
3}j\boldsymbol{M}_{j}^{\prime}\geq(1-2\varepsilon)dn$, and thus
${\mathbb{P}}[\boldsymbol{d}_{s}^{\star}<\boldsymbol{d}_{s}\mid{\mathcal{E}}_{s}]=o_{\varepsilon}(\varepsilon^{1/2})$.
Moreover, given $\boldsymbol{d}_{s}^{\star}=\boldsymbol{d}_{s}$, for each
$i\in[\boldsymbol{d}_{s}]$ the probability that the $i$th clone of $x_{s}$
gets matched to a check of degree $j\leq\varepsilon^{-8}$ is

$j\boldsymbol{M}_{j}^{\prime}/\sum_{h\geq
3}h\boldsymbol{M}_{h}^{\prime}=j{\mathbb{P}}\left[{\boldsymbol{k}=j}\right]/k+o(1)={\mathbb{P}}\left[{\hat{\boldsymbol{k}}=j}\right]+o(1).$

These events are asymptotically independent for the different clones. Thus, we
obtain (4.7).

Finally, we can easily compute $\boldsymbol{N}_{s}$ given the vector
$(\boldsymbol{\kappa}_{1},\ldots,\boldsymbol{\kappa}_{\boldsymbol{\gamma}})$.
There are two possible scenarios.

Case 1: there is $a^{*}\in\partial x_{s}$ such that $\partial a^{*}\setminus
x_{s}\subseteq\mathcal{F}_{0}$:

then only the summand $\sigma_{x_{s}}=0$ contributes to the r.h.s. of (4.2),
because setting $x_{s}$ to zero is the only way to satisfy the check $a^{*}$.
Hence, we can rewrite $\boldsymbol{N}_{s}$ as

$\displaystyle\boldsymbol{N}_{s}$ $\displaystyle=\sum_{a\in\partial
x_{s}}\log_{q}\left[{\sum_{\sigma\in\mathbb{F}_{q}^{\partial
a}}\boldsymbol{1}\\{\sigma\models a,\,\sigma_{x_{s}}=0,\,\forall y\in\partial
a\cap\mathcal{F}_{0}:\sigma_{y}=0\\}q^{1-|\partial
a|+|\mathcal{F}_{0}\cap\partial a|}}\right].$

For $a\in\partial x_{s}$ the sum inside the logarithm evaluates to one if
$\partial a\setminus\\{x_{s}\\}\subseteq\mathcal{F}_{0}$ and to $1/q$
otherwise. Hence,

$\displaystyle\boldsymbol{N}_{s}$ $\displaystyle=\sum_{a\in\partial
x_{s}}\left({\boldsymbol{1}\\{\partial
a\setminus\\{x_{s}\\}\subseteq\mathcal{F}_{0}\\}-1}\right).$ (4.8)

Case 2: for all $a^{*}\in\partial x_{s}$ we have $\partial
a^{*}\setminus(\\{x_{s}\\}\cup\mathcal{F}_{0})\neq\emptyset$:

we rewrite $\boldsymbol{N}_{s}$ as

$\displaystyle\boldsymbol{N}_{s}$
$\displaystyle=\log_{q}\sum_{\sigma\in\mathbb{F}_{q}}\prod_{a\in\partial
x_{s}}\sum_{\tau\in\mathbb{F}_{q}^{\partial a}}\boldsymbol{1}\\{\tau\models
a,\,\tau_{x_{s}}=\sigma,\,\forall y\in\partial
a\cap\mathcal{F}_{0}:\tau_{y}=0\\}q^{1-|\partial a|+|\partial
a\cap\mathcal{F}_{0}|}.$

Then for any $\sigma\in\mathbb{F}_{q}$ the factor corresponding to any $a$
above evaluates to $1/q$. Consequently,

$\displaystyle\boldsymbol{N}_{s}$ $\displaystyle=1-{\boldsymbol{\gamma}}.$
(4.9)

Since any $a\in\partial^{2}x_{s}$ belongs to the set $\mathbb{F}_{q}$ with
probability $\beta$ independently, (4.8) and (4.9) imply that

$\displaystyle\mathbb{E}\left[{\boldsymbol{N}_{s}\mid(\boldsymbol{\kappa}_{1},\ldots,\boldsymbol{\kappa}_{\boldsymbol{\gamma}})}\right]$
$\displaystyle=\underbrace{{\boldsymbol{\gamma}}\prod_{i=1}^{{\boldsymbol{\gamma}}}(1-\beta^{\boldsymbol{\kappa}_{i}-1})+\sum_{i=1}^{{\boldsymbol{\gamma}}}(\beta^{\boldsymbol{\kappa}_{i}-1}-1)}_{\text{Case
1}}+\underbrace{(1-{\boldsymbol{\gamma}})\prod_{i=1}^{{\boldsymbol{\gamma}}}(1-\beta^{\boldsymbol{\kappa}_{i}-1})}_{\text{Case
2}}=\prod_{i=1}^{{\boldsymbol{\gamma}}}(1-\beta^{\boldsymbol{\kappa}_{i}-1})+\sum_{i=1}^{{\boldsymbol{\gamma}}}(\beta^{\boldsymbol{\kappa}_{i}-1}-1).$
(4.10)

Combining (4.6), (4.7) and (4.10) completes the proof.

###  4.2. Proof of Proposition 2.8

The computation of the derivative $\frac{\partial}{\partial
t}\mathbb{E}[\mathcal{N}_{t}+\mathcal{Y}_{t}]$ is based on a coupling argument
and a study of the Boltzmann distribution
$\mu_{\boldsymbol{A}_{\varepsilon}(t)}$. Specifically, we need to investigate
the joint distribution of the cavities, i.e., the clones from
$\bigcup_{i=1}^{n}\left\\{{x_{i}}\right\\}\times[\boldsymbol{d}_{i}]$ that are
not incident to an edge of $\boldsymbol{\Gamma}_{\varepsilon}(t)$. Denote this
set by ${\mathcal{C}}(t)$. Then $\mu_{\boldsymbol{A}_{\varepsilon}(t)}$
induces a probability distribution $\mu_{{\mathcal{C}}(t)}$ via

$\displaystyle\mu_{{\mathcal{C}}(t)}(\sigma)=\mu_{\boldsymbol{A}_{\varepsilon}(t),x_{1},\ldots,x_{n}}\left({\left\\{{\tau\in\mathbb{F}_{q}^{\\{x_{1},\ldots,x_{n}\\}}:\forall(x_{i},h)\in{\mathcal{C}}(t):\tau_{x_{i}}=\sigma_{x_{i},h}}\right\\}}\right)\qquad(\sigma\in\mathbb{F}_{q}^{{\mathcal{C}}(t)}).$

######  Lemma 4.1.

For any $\delta>0$ there is $\Theta=\Theta(\delta)>0$ such that
${\mathbb{P}}\left[{\mu_{{\mathcal{C}}(t)}\mbox{ is
$\delta$-symmetric}}\right]>1-\delta.$

###### Proof.

The choice (2.5) of
${\boldsymbol{m}}_{\varepsilon}(t),{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)$
guarantees that $|{\mathcal{C}}(t)|\geq\varepsilon n/2$ w.h.p. Moreover, since
$\mathbb{E}[\boldsymbol{d}]=O_{\varepsilon}(1)$ we find
$L=L(\varepsilon,\delta)>0$ such that the event
$\mathcal{L}=\left\\{{\sum_{i=1}^{n}\boldsymbol{d}_{i}\boldsymbol{1}\\{\boldsymbol{d}_{i}>L\\}<\varepsilon\delta^{2}n/16}\right\\}$
has probability ${\mathbb{P}}[\mathcal{L}]\geq 1-\delta/8$. Therefore, we may
condition on
${\mathcal{E}}=\mathcal{L}\cap\\{|{\mathcal{C}}(t)|\geq\varepsilon n/2\\}$.

On ${\mathcal{E}}$ let $\boldsymbol{y}\in\\{x_{1},\ldots,x_{n}\\}$ be a random
variable node chosen from the distribution

${\mathbb{P}}[\boldsymbol{y}=x_{i}\mid\boldsymbol{A}_{\varepsilon}(t)]=|{\mathcal{C}}(t)\cap(\\{x_{i}\\}\times[\boldsymbol{d}_{i}])|/|{\mathcal{C}}(t)|.$

Further, let $\boldsymbol{y}^{\prime}$ be an independent copy of
$\boldsymbol{y}$. Since ${\mathbb{P}}[{\mathcal{E}}]\geq 1-\delta/8-o(1)$, it
suffices to prove that

$\displaystyle\mathbb{E}\left[{\left\|{\mu_{\boldsymbol{A}_{\varepsilon}(t),\boldsymbol{y},\boldsymbol{y}^{\prime}}-\mu_{\boldsymbol{A}_{\varepsilon}(t),\boldsymbol{y}}\otimes\mu_{\boldsymbol{A}_{\varepsilon}(t),\boldsymbol{y}^{\prime}}}\right\|_{\mathrm{TV}}\,\bigg{|}\,{\mathcal{E}}}\right]$
$\displaystyle\leq\delta^{2}/2.$ (4.11)

To verify (4.11), let $\boldsymbol{x},\boldsymbol{x}^{\prime}$ be two
variables chosen uniformly and independently among $x_{1},\ldots,x_{n}$. Then
on ${\mathcal{E}}$,

$\displaystyle{\mathbb{P}}\left[{(\boldsymbol{y},\boldsymbol{y}^{\prime})\in\mathcal{V}\mid\boldsymbol{A}_{\varepsilon}(t)}\right]$
$\displaystyle\leq
L^{2}\cdot{\mathbb{P}}\left[{(\boldsymbol{x},\boldsymbol{x}^{\prime})\in\mathcal{V}\mid\boldsymbol{A}_{\varepsilon}(t)}\right]+\delta^{2}/8$
$\displaystyle\mbox{for any
}\mathcal{V}\subseteq\\{x_{1},\ldots,x_{n}\\}^{2}.$ (4.12)

Further, because the distribution of
$\boldsymbol{G}_{\varepsilon}(t)-\\{p_{1},\ldots,p_{\boldsymbol{\theta}}\\}$
is invariant under permutations of $x_{1},\ldots,x_{n}$, Lemma 2.3 shows that
for large enough $\Theta$,

$\displaystyle\mathbb{E}\left[{\left\|{\mu_{\boldsymbol{A}_{\varepsilon}(t),\boldsymbol{x},\boldsymbol{x}^{\prime}}-\mu_{\boldsymbol{A}_{\varepsilon}(t),\boldsymbol{x}}\otimes\mu_{\boldsymbol{A}_{\varepsilon}(t),\boldsymbol{x}^{\prime}}}\right\|_{\mathrm{TV}}\,\bigg{|}\,{\mathcal{E}}}\right]$
$\displaystyle\leq\delta^{3}/(64L^{2}).$ (4.13)

Thus, (4.11) follows from (4.12) and (4.13). ∎

We proceed to derive Proposition 2.8 from Lemma 4.1 and a coupling argument.
Let us write $\mathcal{N}(m,m^{\prime})$ for the conditional random variable
$\mathcal{N}_{t}$ given
${\boldsymbol{m}}_{\varepsilon}(t)=m,{\boldsymbol{m}}_{\varepsilon}(t)^{\prime}=m^{\prime}$.

######  Lemma 4.2.

We have

$\displaystyle\frac{\partial}{\partial
t}\mathbb{E}[\mathcal{N}_{t}]=(1-\varepsilon)\frac{dn}{k}\big{(}$
$\displaystyle(\mathbb{E}[\mathcal{N}({\boldsymbol{m}}_{\varepsilon}(t)+1,{\boldsymbol{m}}_{\varepsilon}^{\prime}(t))]-\mathbb{E}[\mathcal{N}({\boldsymbol{m}}_{\varepsilon}(t),{\boldsymbol{m}}_{\varepsilon}^{\prime}(t))])$
$\displaystyle-(\mathbb{E}[\mathcal{N}({\boldsymbol{m}}_{\varepsilon}(t),{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1)]-\mathbb{E}[\mathcal{N}({\boldsymbol{m}}_{\varepsilon}(t),{\boldsymbol{m}}_{\varepsilon}^{\prime}(t))])\big{)}.$

###### Proof.

The parameter $t$ comes in via the Poisson variables
${\boldsymbol{m}}_{\varepsilon}(t),{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)$
from (2.5). Hence, the product rule gives

$\displaystyle\frac{\partial}{\partial t}\mathbb{E}[\mathcal{N}_{t}]$
$\displaystyle=\frac{\partial}{\partial t}\sum_{m,m^{\prime}\geq
0}{\mathbb{P}}\left[{{\boldsymbol{m}}_{\varepsilon}(t)=m}\right]{\mathbb{P}}\left[{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)=m^{\prime}}\right]\mathbb{E}[\mathcal{N}(m,m^{\prime})]=\sum_{m,m^{\prime}\geq
0}\mathbb{E}[\mathcal{N}(m,m^{\prime})]\frac{\partial}{\partial
t}{\mathbb{P}}\left[{{\boldsymbol{m}}_{\varepsilon}(t)=m}\right]{\mathbb{P}}\left[{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)=m^{\prime}}\right]$
$\displaystyle=\sum_{m,m^{\prime}\geq
0}\mathbb{E}[\mathcal{N}(m,m^{\prime})]\left({\frac{\partial}{\partial
t}{\mathbb{P}}\left[{{\boldsymbol{m}}_{\varepsilon}(t)=m}\right]}\right){\mathbb{P}}\left[{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)=m^{\prime}}\right]+\mathbb{E}[\mathcal{N}(m,m^{\prime})]{\mathbb{P}}\left[{{\boldsymbol{m}}_{\varepsilon}(t)=m}\right]{\frac{\partial}{\partial
t}{\mathbb{P}}\left[{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)=m^{\prime}}\right]}$
$\displaystyle=\sum_{m\geq
0}\mathbb{E}[\mathcal{N}(m,{\boldsymbol{m}}_{\varepsilon}^{\prime}(t))]\frac{\partial}{\partial
t}{\mathbb{P}}\left[{{\boldsymbol{m}}_{\varepsilon}(t)=m}\right]+\sum_{m^{\prime}\geq
0}\mathbb{E}[\mathcal{N}({\boldsymbol{m}}_{\varepsilon}(t),m^{\prime})]\frac{\partial}{\partial
t}{\mathbb{P}}\left[{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)=m^{\prime}}\right].$
(4.14)

The Poisson derivatives work out to be

$\displaystyle\frac{\partial}{\partial
t}{\mathbb{P}}\left[{{\boldsymbol{m}}_{\varepsilon}(t)=m}\right]$
$\displaystyle=\frac{\partial}{\partial
t}\frac{((1-\varepsilon)tdn/k)^{m}}{m!\exp((1-\varepsilon)tdn/k)}=\frac{(1-\varepsilon)dn}{k}\left({{\mathbb{P}}\left[{{\boldsymbol{m}}_{\varepsilon}(t)=m-1}\right]-{\mathbb{P}}\left[{{\boldsymbol{m}}_{\varepsilon}(t)=m}\right]}\right),$
(4.15) $\displaystyle\frac{\partial}{\partial
t}{\mathbb{P}}\left[{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)=m^{\prime}}\right]$
$\displaystyle=\frac{\partial}{\partial
t}\frac{((1-\varepsilon)(1-t)dn/k)^{m^{\prime}}}{m^{\prime}!\exp((1-\varepsilon)(1-t)dn/k)}=\frac{(1-\varepsilon)dn}{k}\left({{\mathbb{P}}\left[{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)=m}\right]-{\mathbb{P}}\left[{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)=m-1}\right]}\right).$
(4.16)

Combining (4.14)–(4.16) completes the proof. ∎

We will couple
$\mathcal{N}({\boldsymbol{m}}_{\varepsilon}(t)+1,{\boldsymbol{m}}_{\varepsilon}^{\prime}(t))$
and
$\mathcal{N}({\boldsymbol{m}}_{\varepsilon}(t),{\boldsymbol{m}}_{\varepsilon}^{\prime}(t))$
as well as
$\mathcal{N}({\boldsymbol{m}}_{\varepsilon}(t),{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1)$
and
$\mathcal{N}({\boldsymbol{m}}_{\varepsilon}(t),{\boldsymbol{m}}_{\varepsilon}^{\prime}(t))$.
With respect to the first pair of random variables, obtain
$\boldsymbol{G}^{\prime}(t)$ from $\boldsymbol{G}_{\varepsilon}(t)$ by adding
a check $a_{{\boldsymbol{m}}_{\varepsilon}(t)+1}$ of target degree
$\boldsymbol{k}_{{\boldsymbol{m}}_{\varepsilon}(t)+1}$. The new check is
maximally matched with random cavities from ${\mathcal{C}}(t)$. Obtain
$\boldsymbol{A}^{\prime}(t)$ by adding a new row to
$\boldsymbol{A}_{\varepsilon}(t)$ corresponding to
$a_{{\boldsymbol{m}}_{\varepsilon}(t)+1}$ and adding a matrix entry drawn
independently according to ${\boldsymbol{\chi}}$ for each edge of
$\boldsymbol{G}^{\prime}(t)$ incident with
$a_{{\boldsymbol{m}}_{\varepsilon}(t)+1}$.

######  Lemma 4.3.

We have
$\mathbb{E}[\mathcal{N}({\boldsymbol{m}}_{\varepsilon}(t)+1,{\boldsymbol{m}}_{\varepsilon}^{\prime}(t))]-\mathbb{E}[\mathcal{N}({\boldsymbol{m}}_{\varepsilon}(t),{\boldsymbol{m}}_{\varepsilon}^{\prime}(t))]=\mathbb{E}[\operatorname{nul}(\boldsymbol{A}^{\prime}(t))-\operatorname{nul}(\boldsymbol{A}_{\varepsilon}(t))]+o(1)$.

###### Proof.

Due to (2.5) and Lemma 1.10, with probability $1-o(n^{-1})$ we have
$|{\mathcal{C}}(t)|\geq\boldsymbol{k}_{{\boldsymbol{m}}_{\varepsilon}(t)+1}$.
Hence, the assertion follows from the principle of deferred decisions. ∎

Lemma 2.2 implies that each marginal $\mu_{{\mathcal{C}}(t),c}$,
$c\in{\mathcal{C}}(t)$ is either $\delta_{0}$ or the uniform distribution on
$\mathbb{F}_{q}$. Thus, let us call $c\in{\mathcal{C}}(t)$ frozen if
$\mu_{{\mathcal{C}}(t),c}=\delta_{0}$. Let $\boldsymbol{\alpha}\in[0,1]$ be
the fraction of frozen cavities in ${\mathcal{C}}(t)$ (with the convention
that $\boldsymbol{\alpha}=0$ if ${\mathcal{C}}(t)=\emptyset$).

######  Lemma 4.4.

We have
$\mathbb{E}\left|{\mathbb{E}[\operatorname{nul}(\boldsymbol{A}^{\prime}(t))-\operatorname{nul}(\boldsymbol{A}_{\varepsilon}(t))\mid\boldsymbol{A}_{\varepsilon}(t)]-(K(\boldsymbol{\alpha})-1)}\right|=o_{\varepsilon}(1)$.

###### Proof.

Pick $\zeta=\zeta(\varepsilon)>0$ small enough and $\delta=\delta(\zeta)>0$
smaller still. Since
$|\operatorname{nul}(\boldsymbol{A}^{\prime}(t))-\operatorname{nul}(\boldsymbol{A}_{\varepsilon}(t))|\leq
1$ and $\mathbb{E}[\boldsymbol{k}^{2}]=O_{\varepsilon}(1)$ we may condition on
the event that
$\boldsymbol{k}_{{\boldsymbol{m}}_{\varepsilon}(t)+1}\leq\varepsilon^{-1}$.
Similarly, because
$|\operatorname{nul}(\boldsymbol{A}^{\prime}(t))-\operatorname{nul}(\boldsymbol{A}_{\varepsilon}(t))|\leq
1$, Lemma 4.1 shows that we may assume that $\mu_{{\mathcal{C}}(t)}$ is
$\delta$-symmetric for a small $\delta=\delta(\varepsilon)>0$. Let
$\mathcal{X}$ be the set of cavities adjacent to
$a_{{\boldsymbol{m}}_{\varepsilon}(t)+1}$. We consider three cases.

Case 1: $\boldsymbol{\alpha}<\varepsilon^{2}$:

since
$\boldsymbol{k}_{{\boldsymbol{m}}_{\varepsilon}(t)+1}\leq\varepsilon^{-1}$ the
probability that $a_{{\boldsymbol{m}}_{\varepsilon}(t)+1}$ joins a frozen
cavity is $o_{\varepsilon}(1)$. Moreover, Lemma 1.8 shows that with
probability at least $1-\exp(-1/\varepsilon)$ the joint distribution
$\mu_{{\mathcal{C}}(t),\mathcal{X}}$ of the cavities that
$a_{{\boldsymbol{m}}_{\varepsilon}(t)+1}$ joins is within
$\exp(-1/\varepsilon)$ of the uniform distribution on
$\mathbb{F}_{q}^{\boldsymbol{k}_{{\boldsymbol{m}}_{\varepsilon}(t)+1}}$ in
total variation, provided that $\Theta$ is chosen sufficiently large. If so,
then a random vector from the kernel of $\boldsymbol{A}_{\varepsilon}(t)$
satisfies the new check $\boldsymbol{a}_{{\boldsymbol{m}}_{\varepsilon}(t)+1}$
with probability $1/q+o_{\varepsilon}(1)$. Consequently, with probability
$1-o_{\varepsilon}(1)$ we have

$\displaystyle\mathbb{E}[\operatorname{nul}(\boldsymbol{A}^{\prime}(t))-\operatorname{nul}(\boldsymbol{A}_{\varepsilon}(t))\mid\boldsymbol{A}_{\varepsilon}(t)]$
$\displaystyle=-1+o_{\varepsilon}(1)=K(\boldsymbol{\alpha})-1+o_{\varepsilon}(1).$
(4.17)

Case 2: $\boldsymbol{\alpha}>1-\varepsilon^{2}$:

since $\boldsymbol{k}\leq\varepsilon^{-1}$ the probability that
$a_{{\boldsymbol{m}}_{\varepsilon}(t)+1}$ joins an unfrozen cavity is
$o_{\varepsilon}(1)$. Hence, with probability $1-o_{\varepsilon}(1)$ we have

$\displaystyle\mathbb{E}[\operatorname{nul}(\boldsymbol{A}^{\prime}(t))-\operatorname{nul}(\boldsymbol{A}_{\varepsilon}(t))\mid\boldsymbol{A}_{\varepsilon}(t)]$
$\displaystyle=0=K(\boldsymbol{\alpha})-1+o_{\varepsilon}(1).$ (4.18)

Case 3: $\varepsilon^{2}\leq\boldsymbol{\alpha}\leq 1-\varepsilon^{2}$:

the distribution of the number $X$ of frozen cavities in $\mathcal{X}$ is
within $o(1)$ of a binomial distribution ${\rm
Bin}(\boldsymbol{k}_{{\boldsymbol{m}}_{\varepsilon}(t)+1},\boldsymbol{\alpha})$
in total variation. Moreover, Lemma 1.8 shows that given any outcome of $X$
the joint distribution $\mu_{\mathcal{X}}$ is within $o_{\varepsilon}(1)$ of a
product distribution with probability $1-o_{\varepsilon}(1)$, provided that
$\Theta$ is chosen big enough. If
$X=\boldsymbol{k}_{{\boldsymbol{m}}_{\varepsilon}(t)+1}$, i.e., if all
variables adjacent to the new check are frozen, then the new check will
certainly be satisfied. Otherwise, the probability of it being satisfied
equals $1/q$. Thus, with probability $1-o_{\varepsilon}(1)$ we have

$\displaystyle\mathbb{E}[\operatorname{nul}(\boldsymbol{A}^{\prime}(t))-\operatorname{nul}(\boldsymbol{A}_{\varepsilon}(t))\mid\boldsymbol{A}_{\varepsilon}(t)]$
$\displaystyle=\mathbb{E}\left[{\boldsymbol{\alpha}^{\boldsymbol{k}_{{\boldsymbol{m}}_{\varepsilon}(t)+1}-1}\mid\boldsymbol{A}_{\varepsilon}(t)}\right]+o_{\varepsilon}(1)=K(\boldsymbol{\alpha})-1+o_{\varepsilon}(1).$
(4.19)

Finally, the assertion follows from (4.17)–(4.19). ∎

To couple
$\mathcal{N}({\boldsymbol{m}}_{\varepsilon}(t),{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1)$
and
$\mathcal{N}({\boldsymbol{m}}_{\varepsilon}(t),{\boldsymbol{m}}_{\varepsilon}^{\prime}(t))$
obtain $\boldsymbol{G}^{\prime\prime}(t)$ from
$\boldsymbol{G}_{\varepsilon}(t)$ by adding checks

$b_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1,1},\ldots,b_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1,\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}}$

as well as variables

$x_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1,i,j},\qquad
i\in[\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}],\qquad
j\in[\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}-1].$

Check $b_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1,i}$ is adjacent to
$x_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1,i,j}^{\prime}$,
$j\in[\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}-1]$.
Additionally, we pick a random maximal matching that matches each new check
$b_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1,i}$ to (at most) one cavity
from ${\mathcal{C}}(t)$. Finally, for each new variable
$x_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1,i,j}$ we insert a check
$f_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1,i,j}$ that pegs the variable
to zero with probability $\beta$ independently. Let
$\mathcal{F}_{t}^{\prime\prime}$ be the set of pairs $(i,j)$ for which such a
check was inserted. Obtain the random matrix
$\boldsymbol{A}^{\prime\prime}(t)$ from $\boldsymbol{A}_{\varepsilon}(t)$ by
adding rows and columns corresponding to the additional checks and variables,
representing each new edge of the Tanner graph by an independent matrix entry
distributed as ${\boldsymbol{\chi}}$.

######  Lemma 4.5.

We have

$\mathbb{E}[\mathcal{N}({\boldsymbol{m}}_{\varepsilon}(t),{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1)]-\mathbb{E}[\mathcal{N}({\boldsymbol{m}}_{\varepsilon}(t),{\boldsymbol{m}}_{\varepsilon}^{\prime}(t))]=\mathbb{E}\left[{\operatorname{nul}(\boldsymbol{A}^{\prime\prime}(t))-\operatorname{nul}(\boldsymbol{A}_{\varepsilon}(t))-\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}(\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}-1)+|\mathcal{F}^{\prime\prime}|}\right]+o(1).$

###### Proof.

Due to (2.5) and Lemma 1.10, with probability $1-o(n^{-1})$ we have
$|{\mathcal{C}}(t)|\geq\boldsymbol{k}_{{\boldsymbol{m}}_{\varepsilon}(t)+1}^{\prime}$.
Hence, the assertion follows from the construction of $\boldsymbol{A}(t)$ and
the principle of deferred decisions. ∎

######  Lemma 4.6.

Let
$Q(\alpha,\beta)=\mathbb{E}\left[{\boldsymbol{k}(\alpha\beta^{\boldsymbol{k}-1}-1)}\right]$
for $\alpha\in[0,1]$. Then

$\mathbb{E}\left|{\mathbb{E}\left[{\operatorname{nul}(\boldsymbol{A}^{\prime\prime}(t))-\operatorname{nul}(\boldsymbol{A}(t))-\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}(\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}-1)+|\mathcal{F}_{t}^{\prime\prime}|\mid\boldsymbol{A}(t)}\right]-Q(\boldsymbol{\alpha},\beta)}\right|=o_{\varepsilon}(1).$

###### Proof.

Pick $\zeta=\zeta(\varepsilon)>0$ small enough and $\delta=\delta(\zeta)>0$
smaller still. As

$\operatorname{nul}(\boldsymbol{A}(t))-\operatorname{nul}(\boldsymbol{A}^{\prime\prime}(t))+\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}(\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}-1)-|\mathcal{F}_{t}^{\prime\prime}|\leq\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}(t)^{\prime}+1}$

and $\mathbb{E}[\boldsymbol{k}^{2}]=O_{\varepsilon}(1)$ we may condition on
the event that
$\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}(t)^{\prime}+1}\leq\varepsilon^{-1}$.
Moreover, Lemma 4.1 shows that we may assume that $\mu_{{\mathcal{C}}(t)}$ is
$\delta$-symmetric. Let $\mathcal{X}$ be the set of cavities adjacent to the
new checks $b_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1,i}$. Also let

$\mathcal{U}=\left\\{{x_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1,i,j}^{\prime}:i\in[\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}+1}],j\in[\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}+1}-1]}\right\\}\setminus\mathcal{F}^{\prime\prime}_{t}$

be the set of new unfrozen variables. We consider three cases.

Case 1: $\boldsymbol{\alpha}<\varepsilon^{4}$:

since
$\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}\leq\varepsilon^{-1}$
the probability that any $b_{{\boldsymbol{m}}_{\varepsilon}(t)^{\prime}+1,i}$
joins a frozen cavity is $o_{\varepsilon}(\varepsilon)$. Hence, Lemma 1.8
shows that with probability $1-o_{\varepsilon}(\varepsilon)$ the joint
distribution $\mu_{{\mathcal{C}}(t),\mathcal{X}}$ is within
$o_{\varepsilon}(\varepsilon)$ of the uniform distribution on
$\mathbb{F}_{q}^{\mathcal{X}}$. Therefore, with probability
$1-o_{\varepsilon}(\varepsilon)$ we have

$\displaystyle\mathbb{E}[\operatorname{nul}(\boldsymbol{A}^{\prime\prime}(t))-\operatorname{nul}(\boldsymbol{A}_{\varepsilon}(t))-\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}(\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}-1)+|\mathcal{F}^{\prime\prime}|\mid\boldsymbol{A}_{\varepsilon}(t)]$
$\displaystyle=-\mathbb{E}[\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}]+o_{\varepsilon}(1)=Q(\boldsymbol{\alpha},\beta)+o_{\varepsilon}(1).$
(4.20)

Case 2: $\boldsymbol{\alpha}>1-\varepsilon^{4}$:

since
$\boldsymbol{k}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}\leq\varepsilon^{-1}$
the probability that any $b_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1,i}$
joins an unfrozen cavity is $o_{\varepsilon}(\varepsilon)$. Hence, with
probability $1-o_{\varepsilon}(\varepsilon)$ we have

$\displaystyle\mathbb{E}[\operatorname{nul}(\boldsymbol{A}^{\prime\prime}(t))-\operatorname{nul}(\boldsymbol{A}_{\varepsilon}(t))-\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}(\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}-1)+|\mathcal{F}^{\prime\prime}|\mid\boldsymbol{A}_{\varepsilon}(t)]$
$\displaystyle=-\mathbb{E}[\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}(\beta^{\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}}-1)]+o_{\varepsilon}(1)$
$\displaystyle=Q(\boldsymbol{\alpha},\beta)+o_{\varepsilon}(1).$ (4.21)

Case 3: $\varepsilon^{4}\leq\boldsymbol{\alpha}\leq 1-\varepsilon^{4}$:

the distribution of the number $X$ of frozen cavities in $\mathcal{X}$ is
within $o(1)$ of a binomial distribution ${\rm
Bin}(\boldsymbol{k}_{{\boldsymbol{m}}_{\varepsilon}(t)+1}^{\prime},\boldsymbol{\alpha})$
in total variation. Moreover, Lemma 1.8 shows that given any outcome of $X$
the joint distribution $\mu_{\mathcal{X}}$ is within
$o_{\varepsilon}(\exp(-1/\varepsilon))$ of a product distribution with
probability $1-o_{\varepsilon}(\exp(-1/\varepsilon))$, provided that $\Theta$
is chosen large enough. Thus, with probability
$1-o_{\varepsilon}(\varepsilon)$ we obtain

$\displaystyle\mathbb{E}[\operatorname{nul}(\boldsymbol{A}^{\prime\prime}(t))-\operatorname{nul}(\boldsymbol{A}_{\varepsilon}(t))-\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}(\boldsymbol{k}^{\prime}_{{\boldsymbol{m}}_{\varepsilon}^{\prime}(t)+1}-1)+|\mathcal{F}^{\prime}|\mid\boldsymbol{A}_{\varepsilon}(t)]$
$\displaystyle=Q(\boldsymbol{\alpha},\beta)+o_{\varepsilon}(1).$ (4.22)

The assertion follows from (4.20)–(4.22). ∎

######  Lemma 4.7.

We have $\frac{\partial}{\partial
t}\mathbb{E}[\mathcal{Y}_{t}]=(1-\varepsilon)dn\mathbb{E}[(\boldsymbol{k}-1)(\beta^{\boldsymbol{k}}-1)]/k$.

###### Proof.

This is a straightforward calculation. ∎

###### Proof of Proposition 2.8.

Combining Claims 4.2–4.7, we obtain

$\displaystyle\frac{\partial}{\partial
t}\mathbb{E}[\mathcal{N}_{t}]+\mathbb{E}[\mathcal{Y}_{t}]$
$\displaystyle=\frac{(1-\varepsilon)dn}{k}\left[{\mathbb{E}\left[{\boldsymbol{\alpha}^{\boldsymbol{k}}-1-\boldsymbol{k}(\boldsymbol{\alpha}\beta^{\boldsymbol{k}-1}-1)+(\boldsymbol{k}-1)(\beta^{\boldsymbol{k}}-1)}\right]+o_{\varepsilon}(1)}\right].$
(4.23)

Since $x^{k}-kxy^{k-1}+(k-1)y^{k}\geq 0$ for all $k\geq 2$, $x,y\in[0,1]$, the
assertion follows from (4.23). ∎

##  5\. Concentration

At this point we have completed the proofs of Propositions 2.4 and 2.8. Thus,
we know the expected rank of the random matrix $\boldsymbol{A}_{\varepsilon}$
with about $\varepsilon dn$ cavities. The aim of this section is to argue that
the rank of the actual matrix $\boldsymbol{A}$ that does not have any cavities
and whose Tanner graph is simple is close to the expected rank of
$\boldsymbol{A}_{\varepsilon}$ w.h.p. In other words, we need to show that the
rank of a random matrix is sufficiently concentrated that forbidding multi-
edges is as inconsequential as conditioning on the event

$\mathcal{D}=\left\\{{\sum_{i=1}^{n}\boldsymbol{d}_{i}=\sum_{i=1}^{{\boldsymbol{m}}}\boldsymbol{k}_{i}}\right\\}.$

Our main tool will be the local limit theorem for sums of independent random
variables, which we use in Section 5.1 to calculate the probability of
$\mathcal{D}$. There we will also study the conditional distributions of
${\boldsymbol{m}}$, $\sum_{i=1}^{n}\boldsymbol{d}_{i}$ and
$\sum_{i=1}^{{\boldsymbol{m}}}\boldsymbol{k}_{i}$ given $\mathcal{D}$.
Further, in Section 5.2 we prove Proposition 1.9. In Section 5.3 we then
derive Proposition 2.4. Moreover, Section LABEL:Sec_Lemma_nulconc contains the
proof of Proposition LABEL:Lemma_nulconc. Finally, Section 5.4 contains the
proof of Theorem 1.2.

###  5.1. The local limit theorem

We recall the local limit theorem for sums of independent random variables.

######  Theorem 5.1 ([26, p. 130]).

Suppose that $(\boldsymbol{X}_{i})_{i\geq 1}$ is a sequence of i.i.d.
variables that take values in $\mathbb{Z}$ such that the greatest common
divisor of the support of $\boldsymbol{X}_{1}$ is one. Also assume that
$\mathbb{E}[\boldsymbol{X}_{1}^{2}]=\sigma^{2}\in(0,\infty)$. Then

$\displaystyle\lim_{n\to\infty}\sup_{z\in\mathbb{Z}}\left|{\sqrt{n}{\mathbb{P}}\left[{\sum_{i=1}^{n}\boldsymbol{X}_{i}=z}\right]-\frac{\exp(-(z-n\mathbb{E}[\boldsymbol{X}_{1}])^{2}/(2n\sigma^{2}))}{\sqrt{2\pi}\sigma}}\right|$
$\displaystyle=0.$

As an application of Theorem 5.1 we obtain the following estimate. Because
$\mathbb{E}[\boldsymbol{d}^{r}]+\mathbb{E}[\boldsymbol{k}^{r}]<\infty$ for an
$r>2$, the event

$\displaystyle\mathcal{M}=\left\\{{\max_{i\in[n]}\boldsymbol{d}_{i}+\max_{i\in[{\boldsymbol{m}}]}\boldsymbol{k}_{i}\leq\sqrt{n}/\log^{9}n}\right\\}\qquad\mbox{satisfies}\qquad{\mathbb{P}}\left[{\mathcal{M}}\right]=1-o(1).$
(5.1)

######  Corollary 5.2.

If $\gcd(\boldsymbol{k})$ divides $n$, then
${\mathbb{P}}\left[{\mathcal{D}}\right]=\Theta(n^{-1/2})$ and
${\mathbb{P}}\left[{\mathcal{D}\mid\mathcal{M}}\right]=\Theta(n^{-1/2})$.

###### Proof.

For ${\mathbb{P}}\left[{\mathcal{D}\mid\mathcal{M}}\right]$ there are several
cases to consider. First, that
$\mathrm{Var}(\boldsymbol{d})=\mathrm{Var}(\boldsymbol{k})=0$, i.e.,
$\boldsymbol{d},\boldsymbol{k}$ are both atoms. Since ${\boldsymbol{m}}$ is a
Poisson variable with mean $dn/k$ we find
${\mathbb{P}}\left[{\mathcal{D}\mid\mathcal{M}}\right]={\mathbb{P}}\left[{{\boldsymbol{m}}=dn/k}\right]=\Theta(n^{-1/2})$.

Second, suppose that $\mathrm{Var}(\boldsymbol{d})>0$ but
$\mathrm{Var}(\boldsymbol{k})=0$. Then Theorem 5.1 and (5.1) show that

$\displaystyle{\mathbb{P}}\left[{\left|{dn-\sum_{i=1}^{n}\boldsymbol{d}_{i}}\right|\leq\sqrt{n}\wedge
k\mbox{ divides }\sum_{i=1}^{n}\boldsymbol{d}_{i}\mid\mathcal{M}}\right]$
$\displaystyle=\Omega(1).$ (5.2)

Further, given
$\left|{dn-\sum_{i=1}^{n}\boldsymbol{d}_{i}}\right|\leq\sqrt{n}$ and
$k|\sum_{i=1}^{n}\boldsymbol{d}_{i}$, the event
$k{\boldsymbol{m}}=\sum_{i=1}^{n}\boldsymbol{d}_{i}$ has probability
$\Theta(n^{-1/2})$ by the local limit theorem for the Poisson distribution.

The case that $\mathrm{Var}(\boldsymbol{d})=0$ but
$\mathrm{Var}(\boldsymbol{k})>0$ can be dealt with similarly. Indeed, pick a
large enough number $L>0$ and let
$I=\left\\{{i\in[{\boldsymbol{m}}]:\boldsymbol{k}_{i}>L}\right\\}$,
${\boldsymbol{m}}^{\prime}=|I|$,
${\boldsymbol{m}}^{\prime\prime}={\boldsymbol{m}}-|I|$, $S^{\prime}=\sum_{i\in
I}\boldsymbol{k}_{i}$ and
$S^{\prime\prime}=\sum_{i\in[{\boldsymbol{m}}]\setminus I}\boldsymbol{k}_{i}$.
Then ${\boldsymbol{m}}^{\prime},{\boldsymbol{m}}^{\prime\prime}$ are
stochastically independent, and so are $S^{\prime},S^{\prime\prime}$.
Moreover, since $S^{\prime}$ satisfies the central limit theorem we have

$\displaystyle{\mathbb{P}}\left[{|S^{\prime}-\mathbb{E}[S^{\prime}\mid\mathcal{M}]|\leq\sqrt{n}\mid\mathcal{M}}\right]$
$\displaystyle=\Omega(1).$ (5.3)

Further, Theorem 5.1 applies to $S^{\prime\prime}$, which is distributed as
$\sum_{i=1}^{{\boldsymbol{m}}}\boldsymbol{k}_{i}\boldsymbol{1}\\{\boldsymbol{k}_{i}\leq
L\\}$. Hence, as $n$ is divisible by $\gcd(k)$,

$\displaystyle{\mathbb{P}}\left[{S^{\prime}+S^{\prime\prime}=dn\mid|S^{\prime}-\mathbb{E}[S^{\prime}\mid\mathcal{M}]|,\mathcal{M}}\right]$
$\displaystyle=\Omega(n^{-1/2}).$ (5.4)

Thus, (5.3) and (5.4) show that
${\mathbb{P}}\left[{\mathcal{D}\mid\mathcal{M}}\right]=\Omega(n^{-1/2})$. The
upper bound
${\mathbb{P}}\left[{\mathcal{D}\mid\mathcal{M}}\right]=O(n^{-1/2})$ follows
from the uniform upper bound from Theorem 5.1.

A similar argument applies in the final case $\mathrm{Var}(\boldsymbol{d})>0$,
$\mathrm{Var}(\boldsymbol{k})>0$. Indeed, Theorem 5.1 and (5.1) yield

$\displaystyle{\mathbb{P}}\left[{\gcd(\boldsymbol{k})\mbox{ divides
}\sum_{i=1}^{n}\boldsymbol{d}_{i}\mbox{ and
}\left|{dn-\sum_{i=1}^{n}\boldsymbol{d}_{i}}\right|\leq\sqrt{n}\mid\mathcal{M}}\right]$
$\displaystyle=\Omega(1).$ (5.5)

Moreover, (5.3) remains valid regardless the variance of $\boldsymbol{d}$.
Hence, applying Theorem 5.1 to $S^{\prime\prime}$, we obtain

$\displaystyle{\mathbb{P}}\left[{S^{\prime}+S^{\prime\prime}=\sum_{i=1}^{n}\boldsymbol{d}_{i}\,\bigg{|}\,\gcd(\boldsymbol{k})\mbox{
divides
}\sum_{i=1}^{n}\boldsymbol{d}_{i},\,\left|{dn-\sum_{i=1}^{n}\boldsymbol{d}_{i}}\right|\leq\sqrt{n},\,|S^{\prime}-\mathbb{E}[S^{\prime}\mid\mathcal{M}]|,\mathcal{M}}\right]$
$\displaystyle=\Omega(n^{-1/2}).$ (5.6)

Combining (5.5) and (5.6), we see that
${\mathbb{P}}\left[{\mathcal{D}\mid\mathcal{M}}\right]=\Omega(n^{-1/2})$. The
matching upper bound
${\mathbb{P}}\left[{\mathcal{D}\mid\mathcal{M}}\right]=O(n^{-1/2})$ follows
from the universal upper bound from Theorem 5.1 once more. The treatment for
${\mathbb{P}}\left[{\mathcal{D}}\right]$ is similar and simpler. ∎

###  5.2. Proof of Proposition 1.9

Proposition 1.9 is a consequence of Lemma 5.2 and the following statement.

######  Lemma 5.3.

We have
${\mathbb{P}}\left[{\boldsymbol{A}_{0}\in\mathcal{S}|\mathcal{D}}\right]=\Omega(1)$.

Thus, we are left to prove Lemma 5.3.

######  Lemma 5.4.

On the event $\mathcal{M}\cap\mathcal{D}$ we have
$\frac{1}{n}\sum_{i=1}^{n}\boldsymbol{d}_{i}^{2}\to\mathbb{E}[\boldsymbol{d}^{2}]$,
$\frac{1}{n}\sum_{i=1}^{{\boldsymbol{m}}}\boldsymbol{k}_{i}^{2}\to
d\mathbb{E}[\boldsymbol{k}^{2}]/k$ in probability.

###### Proof.

We will only prove the statement about the $\boldsymbol{k}_{i}$; the same
(actually slightly simplified) argument applies to the $\boldsymbol{d}_{i}$.
By tail bounds on the Poisson distribution we may condition on
$\\{{\boldsymbol{m}}=m\\}$ for some integer $m$ with $|m-dn/k|\leq\sqrt{n}\ln
n$. Fix a small $\delta>0$ and a large enough $L=L(\delta)>0$. Given
${\boldsymbol{m}}=m$ the variables
$Q_{j}=\sum_{i\in[{\boldsymbol{m}}]}\boldsymbol{1}\\{\boldsymbol{k}_{i}=j\\}$
have a bionomial distribution. Therefore, the Chernoff bound yields
${\mathbb{P}}\left[{|Q_{j}-dn{\mathbb{P}}\left[{\boldsymbol{k}=j}\right]/k|\leq\sqrt{n}\ln
n\mid{\boldsymbol{m}}=m}\right]=1-o(1/n)$ for any $j\leq L$. Hence, (5.1) and
Corollary 5.2 yield

$\displaystyle{\mathbb{P}}\left[{\forall j\leq
L:|Q_{j}-dn{\mathbb{P}}[\boldsymbol{k}=j]/k|\leq\sqrt{n}\ln
n\mid\mathcal{D}\cap\mathcal{M},\,{\boldsymbol{m}}=m}\right]=1-o(1).$ (5.7)

Further, let

$\displaystyle R_{h}$ $\displaystyle=\sum_{j\geq
3}\boldsymbol{1}\\{(1+\delta)^{h-1}L<j\leq(1+\delta)^{h}L\wedge\sqrt{n}/\ln^{9}n\\}Q_{j},$
$\displaystyle\bar{R}_{h}$ $\displaystyle=m\sum_{j\geq
3}\boldsymbol{1}\\{(1+\delta)^{h-1}L<j\leq(1+\delta)^{h}L\wedge\sqrt{n}/\ln^{9}n\\}{\mathbb{P}}\left[{\boldsymbol{k}=j}\right]$

and let ${\mathcal{H}}$ be the set of all integers $h\geq 1$ with
$(1+\delta)^{h-1}L\leq\sqrt{n}/\ln^{9}n$. Then the Chernoff bound implies that

$\displaystyle{\mathbb{P}}\left[{\forall
h\in{\mathcal{H}}:\left|{R_{h}-\bar{R}_{h}}\right|>\delta\bar{R}_{h}+\ln^{2}n\mid\mathcal{D}\cap\mathcal{M},{\boldsymbol{m}}=m}\right]$
$\displaystyle=o(n^{-1}).$ (5.8)

Finally, if
$|Q_{j}-dn{\mathbb{P}}\left[{\boldsymbol{k}=j}\right]/k|\leq\sqrt{n}\ln n$ for
all $j\leq L$ and
$\left|{R_{h}-\bar{R}_{h}}\right|\leq\delta\bar{R}_{h}+\ln^{2}n$ for all
$h\in{\mathcal{H}}$, then

$\displaystyle\frac{1}{n}\sum_{i=1}^{m}\boldsymbol{k}_{i}^{2}$
$\displaystyle\leq
o(1)+\frac{d}{k}\mathbb{E}\left[{\boldsymbol{k}^{2}\boldsymbol{1}\\{\boldsymbol{k}\leq
L\\}}\right]+\frac{d}{kn}\sum_{h\in{\mathcal{H}}}(1+\delta)^{2h}L^{2}R_{h}$
$\displaystyle=o(1)+\frac{d}{k}\mathbb{E}\left[{\boldsymbol{k}^{2}\boldsymbol{1}\\{\boldsymbol{k}\leq
L\\}}\right]+\frac{d}{kn}\sum_{h\in{\mathcal{H}}}(1+\delta)^{2h+1}L^{2}\bar{R}_{h}\leq\frac{(1+\delta)d}{k}\mathbb{E}[\boldsymbol{k}^{2}]+o(1),$
and analogously $\displaystyle\frac{1}{n}\sum_{i=1}^{m}\boldsymbol{k}_{i}^{2}$
$\displaystyle\geq\frac{(1-\delta)d}{k}\mathbb{E}[\boldsymbol{k}^{2}]+o(1).$

Since this holds true for any fixed $\delta>0$, the assertion follows from
(5.7) and (5.8). ∎

######  Lemma 5.5.

Let $Y$ be the number of multi-edges of the Tanner graph and let $\ell\geq 1$.
There is $\lambda>0$ such that on

$\mathcal{M}\cap\mathcal{D}\cap\left\\{{\sum_{i=1}^{n}\boldsymbol{d}_{i}=dn+o(n),\,\sum_{i=1}^{n}\boldsymbol{d}_{i}^{2}=n\mathbb{E}[\boldsymbol{d}^{2}]+o(n)}\right\\}\cap\left\\{{\sum_{i=1}^{{\boldsymbol{m}}}\boldsymbol{k}_{i}^{2}=dn\mathbb{E}[\boldsymbol{k}^{2}]/k+o(n)}\right\\}\cap\\{{\boldsymbol{m}}=dn/k+o(n)\\}$

we have
$\mathbb{E}\left[{\prod_{i=1}^{\ell}Y-i+1\,\bigg{|}\,(\boldsymbol{d}_{i})_{i\in[n]},(\boldsymbol{k}_{i})_{i\in{\boldsymbol{m}}}}\right]=\lambda^{\ell}+o(1).$

###### Proof.

To estimate the $\ell$th factorial moments of $Y$ for $\ell\geq 1$, we split
the random variable into a sum of indicator variables. Specifically, let
$U_{\ell}$ be the set of all families $(a_{i},y_{i},w_{i})_{i\in\ell}$ with
$a_{i}\in[{\boldsymbol{m}}]$, $y_{i}\in[{\boldsymbol{n}}]$ and $2\leq
w_{i}\leq\boldsymbol{k}_{a_{i}}\wedge\boldsymbol{d}_{x_{i}}$ such that the
pairs $(a_{i},y_{i})$ are pairwise distinct. Let
$Y((a_{i},x_{i},w_{i})_{i\in[\ell]})$ be the number of ordered $\ell$-tuples
of multi-edges comprising precisely $w_{i}$ edges between check $a_{i}$ and
variable $x_{i}$ for each $i$. Then

$\displaystyle\prod_{h=1}^{\ell}Y-h+1$
$\displaystyle=\sum_{(a_{i},y_{i},w_{i})_{i\in[\ell]}\in
U_{\ell}}Y((a_{i},y_{i},w_{i})_{i\in[\ell]}).$

Moreover, letting $w=\sum_{i}w_{i}$, we have

$\displaystyle\mathbb{E}[Y((a_{i},y_{i},w_{i})_{i\in[h]})\mid(\boldsymbol{d}_{i})_{i\in[n]},(\boldsymbol{k}_{i})_{i\in{\boldsymbol{m}}}]$
$\displaystyle\sim\frac{1}{(dn)^{w}}\prod_{i=1}^{\ell}{\binom{\boldsymbol{d}_{y_{i}}}{w_{i}}}{\binom{\boldsymbol{k}_{a_{i}}}{w_{i}}}w_{i}!\enspace.$
(5.9)

Now, for a sequence $\boldsymbol{w}=(w_{1},\ldots,w_{\ell})$ let
$Y_{\boldsymbol{w}}=\sum_{(a_{i},y_{i},w_{i})_{i\in[\ell]}\in
U_{\ell}}Y((a_{i},y_{i},w_{i})_{i\in[\ell]})$. Then (5.9) yields

$\displaystyle\mathbb{E}[Y_{\boldsymbol{w}}\mid(\boldsymbol{d}_{i})_{i\in[n]},(\boldsymbol{k}_{i})_{i\in{\boldsymbol{m}}}]$
$\displaystyle\leq
O(n^{-w})\prod_{i=1}^{\ell}\left({\sum_{j=1}^{n}\boldsymbol{d}_{j}^{w_{i}}}\right)\left({\sum_{j=1}^{{\boldsymbol{m}}}\boldsymbol{k}_{j}^{w_{i}}}\right)\leq
O(n^{-w})\max_{j\in[n]}\boldsymbol{d}_{j}^{w-2\ell}\max_{j\in[{\boldsymbol{m}}]}\boldsymbol{k}_{j}^{w-2\ell}\left({\sum_{j=1}^{n}\boldsymbol{d}_{j}^{2}}\right)^{\ell}\left({\sum_{j=1}^{{\boldsymbol{m}}}\boldsymbol{k}_{j}^{2}}\right)^{\ell}$
$\displaystyle\leq
O(n^{2\ell-w})\max_{j\in[n]}\boldsymbol{d}_{j}^{w-2\ell}\max_{j\in[{\boldsymbol{m}}]}\boldsymbol{k}_{j}^{w-2\ell}=O(\ln^{2\ell-w}n).$

As a consequence,

$\displaystyle\sum_{\boldsymbol{w}:w>2\ell}\mathbb{E}[Y_{\boldsymbol{w}}\mid(\boldsymbol{d}_{i})_{i\in[n]},(\boldsymbol{k}_{i})_{i\in{\boldsymbol{m}}}]$
$\displaystyle=o(1).$ (5.10)

Finally, invoking (5.9), we obtain

$\displaystyle\mathbb{E}[Y_{(2,\ldots,2)}\mid(\boldsymbol{d}_{i})_{i\in[n]},(\boldsymbol{k}_{i})_{i\in{\boldsymbol{m}}}]$
$\displaystyle\sim\lambda^{\ell},\qquad\mbox{where}$ $\displaystyle\lambda$
$\displaystyle\sim\frac{\left({\sum_{i=1}^{n}\boldsymbol{d}_{i}(\boldsymbol{d}_{i}-1)}\right)\left({\sum_{i=1}^{n}\boldsymbol{k}_{i}(\boldsymbol{k}_{i}-1)}\right)}{2(dn)^{2}}.$
(5.11)

Combining (5.9), (5.10) and (5.11) completes the proof. ∎

######  Corollary 5.6.

We have
${\mathbb{P}}\left[{\mathcal{S}\mid\mathcal{D}\cap\mathcal{M}}\right]=\Omega(1)$.

###### Proof.

Lemmas 5.4 and 5.5 show together with inclusion/exclusion that w.h.p. on the
event $\mathcal{M}\cap\mathcal{D}$,

${\mathbb{P}}\left[{Y=0\mid(\boldsymbol{d}_{i})_{i\in[n]},(\boldsymbol{k}_{i})_{i\in{\boldsymbol{m}}}}\right]=\exp(-\lambda)=\Omega(1).$

Since $\mathcal{S}=\\{Y=0\\}$, the assertion follows. ∎

###### Proof of Lemma 5.3.

The assertion follows immediately from (5.1), Corollary 5.2 and Corollary 5.6.
∎

###  5.3. Proof of Proposition 2.4

The random matrix $\boldsymbol{A}$ has $n$ columns and
${\boldsymbol{m}}\,\sim\,{\rm Po}(dn/k)$ rows, with the column and row degrees
drawn from the distributions $\boldsymbol{d}$ and $\boldsymbol{k}$. By
comparison, $\boldsymbol{A}_{\varepsilon}$ has slightly fewer, namely
${\boldsymbol{m}}_{\varepsilon}\,\sim\,{\rm Po}((1-\varepsilon)dn/k)$ rows.
One might therefore think that the proof of Lemma 2.4 is straightforward, as
it appears that $\boldsymbol{A}$ is obtained from
$\boldsymbol{A}_{\varepsilon}$ by simply adding another random ${\rm
Po}(\varepsilon dn/k)$ rows. Since adding $O(\varepsilon n)$ rows cannot
reduce the nullity by more than $O(\varepsilon n)$, the bound on
$\mathbb{E}[\operatorname{nul}(\boldsymbol{A})]-\mathbb{E}[\operatorname{nul}(\boldsymbol{A}_{\varepsilon})]$
appears to be immediate. But there is a catch. Namely, in constructing
$\boldsymbol{A}$ we condition on the event
$\mathcal{D}=\\{\sum_{i=1}^{n}\boldsymbol{d}_{i}=\sum_{i=1}^{{\boldsymbol{m}}}\boldsymbol{k}_{i}\\}$.
Thus, $\boldsymbol{A}_{\varepsilon}$ does not have the same distribution as
the top ${\rm Bin}({\boldsymbol{m}},1-\varepsilon)$ rows of $\boldsymbol{A}$
since the conditioning might distort the degree distribution. We need to show
that this distortion is insignificant. To this end, recall that
${\boldsymbol{m}}_{\varepsilon}\,\sim\,{\rm Po}((1-\varepsilon)dn/k)$.

######  Lemma 5.7.

W.h.p. we have

$\displaystyle{\mathbb{P}}\left[{\left|{\operatorname{nul}(\boldsymbol{A}_{\varepsilon})-\mathbb{E}[\operatorname{nul}(\boldsymbol{A}_{\varepsilon})\mid{\boldsymbol{m}}_{\varepsilon},(\boldsymbol{d}_{i})_{i\geq
1},\,(\boldsymbol{k}_{i})_{i\geq 1}]}\right|>\sqrt{n}\ln
n\mid{\boldsymbol{m}}_{\varepsilon},(\boldsymbol{d}_{i})_{i\geq
1},\,(\boldsymbol{k}_{i})_{i\geq 1}}\right]$ $\displaystyle=o(1),$

###### Proof.

Lemma 1.10 shows that
$\sum_{i=1}^{n}\boldsymbol{d}_{i},\sum_{i=1}^{{\boldsymbol{m}}_{\varepsilon}}\boldsymbol{k}_{i}=O(n)$
and
$\sum_{i=1}^{{\boldsymbol{m}}_{\varepsilon}}\boldsymbol{k}_{i}\leq\sum_{i=1}^{n}\boldsymbol{d}_{i}$
with probability $1-o(n^{-1})$. Assuming that this is so, consider a
filtration
$(\mathfrak{F}_{t})_{t\leq\sum_{i=1}^{{\boldsymbol{m}}_{\varepsilon}}\boldsymbol{k}_{i}}$
that reveals the random matching $\boldsymbol{\Gamma}_{\varepsilon}$ one clone
at a time. Then

$\left|{\mathbb{E}[\operatorname{nul}(\boldsymbol{A}_{\varepsilon})\mid\mathfrak{F}_{t+1},{\boldsymbol{m}}_{\varepsilon},(\boldsymbol{d}_{i})_{i\geq
1},\,(\boldsymbol{k}_{i})_{i\geq
1}-\mathbb{E}[\operatorname{nul}(\boldsymbol{A}_{\varepsilon})\mid\mathfrak{F}_{t},{\boldsymbol{m}}_{\varepsilon},(\boldsymbol{d}_{i})_{i\geq
1},\,(\boldsymbol{k}_{i})_{i\geq 1}}\right|]\leq O(1)$

for all $t$. Therefore, the assertion follows from Azuma’s inequality. ∎

###### Proof of Proposition 2.4.

We will couple $\boldsymbol{A}_{\varepsilon}$ and $\boldsymbol{A}$ so that
they differ by $O(\varepsilon n)$ rows with probability at least
$1-\varepsilon$. The proposition follows immediately, as altering one row can
affect the nullity of a matrix by $O(1)$.

To construct the coupling we first generate the following parameters for
$\boldsymbol{A}_{\varepsilon}$. Parameter $\Theta=\Theta(\varepsilon)$ is
given. Generate ${\boldsymbol{\theta}}\in[\Theta]$ uniformly at random.
Generate ${\boldsymbol{m}}_{\varepsilon}$ and then
${\boldsymbol{m}}_{\varepsilon}$ check nodes. Each check node $a_{i}$ is
associated with an integer $\boldsymbol{k}_{i}$ which is an independent copy
of $\boldsymbol{k}$. To distinguish rows for $\boldsymbol{A}_{\varepsilon}$
from $\boldsymbol{A}$, we colour these check nodes red. Add additional
${\boldsymbol{\theta}}$ red check nodes
$p_{1},\ldots,p_{{\boldsymbol{\theta}}}$.

Next, we generate $n$ variable nodes where variable node $x_{i}$ is associated
with ${\boldsymbol{d}}_{i}$, which is an independent copy of
${\boldsymbol{d}}$.

Next we generate parameters ${\boldsymbol{m}}$, and ${\boldsymbol{n}}_{j}$ for
$\boldsymbol{A}$, where ${\boldsymbol{n}}_{j}$ denotes the number of rows in
$\boldsymbol{A}$ that contains exactly $j$ non-zero entries. The following
claim follows straightforwardly by the Chernoff bounds and Corollary 5.2.

######  Claim 5.8.

For every $\varepsilon>0$ there is a sufficiently large $L=L(\varepsilon)>0$
such that

${\mathbb{P}}\left[{\sum_{j\geq L}{\boldsymbol{n}}_{j}>\varepsilon
n}\right]<\varepsilon,\quad{\mathbb{P}}\left[{\sum_{j\geq
L}\sum_{i=1}^{{\boldsymbol{m}}_{\varepsilon}}\boldsymbol{1}\\{\boldsymbol{k}_{i}=j\\}>\varepsilon
n}\right]<\varepsilon,\quad{\mathbb{P}}\left[{{\boldsymbol{n}}_{j}>\sum_{i=1}^{{\boldsymbol{m}}_{\varepsilon}}\boldsymbol{1}\\{\boldsymbol{k}_{i}=j\\}\
\mbox{for all $j\leq L$}}\right]=1-o(1).$

Assume events $\\{\sum_{j\geq L}{\boldsymbol{n}}_{j}\leq\varepsilon n\\}$,
$\\{\sum_{j\geq
L}\sum_{i=1}^{{\boldsymbol{m}}_{\varepsilon}}\boldsymbol{1}\\{\boldsymbol{k}_{i}=j\\}\leq\varepsilon
n\\}$, and
$\\{{\boldsymbol{n}}_{j}>\sum_{i=1}^{{\boldsymbol{m}}_{\varepsilon}}\boldsymbol{1}\\{\boldsymbol{k}_{i}=j\\}\
\mbox{for all $j\leq L$}\\}$ hold. Uncolour all check nodes $a_{i}$ where
$\boldsymbol{k}_{i}\leq L$. For each $j\leq L$, generate
${\boldsymbol{n}}_{j}-\sum_{i=1}^{{\boldsymbol{m}}_{\varepsilon}}\boldsymbol{1}\\{\boldsymbol{k}_{i}=j\\}$
check nodes, colour them blue, and associate $\boldsymbol{k}_{i}=j$ to each
such check node $a_{i}$. For each $j>L$, generate ${\boldsymbol{n}}_{j}$ blue
check nodes and similarly each such node $a_{i}$ is associated with integer
$j$.

Now the Tanner graph of $\boldsymbol{A}_{\varepsilon}$ is generated by taking
a random maximal matching from the clones of all uncoloured and red check
nodes $\\{a_{i}\\}\times[\boldsymbol{k}_{i}]$ (excluding check nodes
$p_{1},\ldots,p_{{\boldsymbol{\theta}}}$) to the set of variable clones
$\cup_{j=1}^{n}\\{x_{j}\\}\times[{\boldsymbol{d}}_{j}]$, and then adding an
edge between $p_{i}$ and $a_{i}$ for $1\leq i\leq{\boldsymbol{\theta}}$. The
Tanner graph of $\boldsymbol{A}$ is generated by removing all matching edges
from the clones of the red check nodes, and removing edges between $p_{i}$ and
$a_{i}$ for $1\leq i\leq{\boldsymbol{\theta}}$, and then matching all clones
of the blue check nodes to the remaining clones of the variable nodes.

By the construction, marginally, the induced random matrix of the first Tanner
graph is distributed as $\boldsymbol{A}_{\varepsilon}$, and that of the second
Tanner graph is distributed as $\boldsymbol{A}$. Moreover, Claim 5.8 and the
fact that ${\boldsymbol{\theta}}\leq\Theta=O(1)$ ensures that with probability
at least $1-\varepsilon$,
$|\operatorname{nul}{\boldsymbol{A}_{\varepsilon}}-\operatorname{nul}{\boldsymbol{A}}|=O(\varepsilon
n)$. The proposition follows by taking $\varepsilon\to 0$. ∎

###  5.4. Proof of Theorem 1.2

Suppose that $D,K$ are polynomials that $\gcd(\boldsymbol{k})$ divides $n$ and
that $m=dn/k$ is an integer divisible by $\gcd(\boldsymbol{d})$.

######  Lemma 5.9.

For any $\ell$ in the support of $\boldsymbol{d}$ and any $\ell^{\prime}$ in
the support of $\boldsymbol{k}$ we have

$\displaystyle{\mathbb{P}}\left[{\left|{n{\mathbb{P}}\left[{\boldsymbol{d}=\ell}\right]-\sum_{i=1}^{n}\boldsymbol{1}\\{\boldsymbol{d}_{i}=\ell\\}}\right|\leq\sqrt{n}\ln
n\mid\mathcal{D}}\right]$ $\displaystyle=1-o(1),$
$\displaystyle{\mathbb{P}}\left[{\left|{m{\mathbb{P}}\left[{\boldsymbol{k}=\ell}\right]-\sum_{i=1}^{m}\boldsymbol{1}\\{\boldsymbol{k}_{i}=\ell^{\prime}\\}}\right|\leq\sqrt{n}\ln
n\mid\mathcal{D}}\right]$ $\displaystyle=1-o(1).$

###### Proof.

Since $D,K$ are polynomials,
$\sum_{i=1}^{n}\boldsymbol{1}\\{\boldsymbol{d}_{i}=\ell\\}$ and
$\sum_{i=1}^{m}\boldsymbol{1}\\{\boldsymbol{k}_{i}=\ell^{\prime}\\}$ are
binomial variables with mean $\Omega(n)$. Therefore, the Chernoff bound shows
that the probability of a deviation of more than $\sqrt{n}\ln n$ is
$O(1/n^{2})$. As Corollary 5.2 shows that
${\mathbb{P}}\left[{\mathcal{D}}\right]=\Omega(1/n)$, the assertion follows
from Bayes’ rule. ∎

###### Proof of Theorem 1.2.

Let ${\mathcal{E}}$ be the event that for all $\ell,\ell^{\prime}$ in the
support of $\boldsymbol{d},\boldsymbol{k}$, respectively,

$\displaystyle\left|{n{\mathbb{P}}\left[{\boldsymbol{d}=\ell}\right]-\sum_{i=1}^{n}\boldsymbol{1}\\{\boldsymbol{d}_{i}=\ell\\}}\right|\leq\sqrt{n}\ln
n,\quad\left|{m{\mathbb{P}}\left[{\boldsymbol{k}=\ell^{\prime}}\right]-\sum_{i=1}^{m}\boldsymbol{1}\\{\boldsymbol{k}_{i}=\ell^{\prime}\\}}\right|\leq\sqrt{n}\ln
n.$

Then Lemma 5.9 and Theorem 1.1 yield ${\mathbb{P}}[{\mathcal{E}}]\sim 1$.
Moreover, let ${\mathcal{E}}^{\prime}$ be the event that
$n{\mathbb{P}}\left[{\boldsymbol{d}=\ell}\right]=\sum_{i=1}^{n}\boldsymbol{1}\\{\boldsymbol{d}_{i}=\ell\\}$
and
$m{\mathbb{P}}\left[{\boldsymbol{k}=\ell^{\prime}}\right]=\sum_{i=1}^{m}\boldsymbol{1}\\{\boldsymbol{k}_{i}=\ell^{\prime}\\}$
for all $\ell,\ell^{\prime}$. We are going to couple $\boldsymbol{A}_{0}$
given ${\mathcal{E}}$ with $\boldsymbol{A}_{0}$ given ${\mathcal{E}}^{\prime}$
such that

$\displaystyle\mathbb{E}\left|{\operatorname{rk}(\boldsymbol{A}_{0}\mid{\mathcal{E}})-\operatorname{rk}(\boldsymbol{A}_{0}\mid{\mathcal{E}}^{\prime})}\right|$
$\displaystyle=o(n).$ (5.12)

Since
$\operatorname{rate}_{n}(\boldsymbol{d},\boldsymbol{k})=\frac{1}{n}\mathbb{E}\left[{\operatorname{nul}(\boldsymbol{A})\mid\mathfrak{D}}\right]=\frac{1}{n}\mathbb{E}\left[{\operatorname{nul}(\boldsymbol{A}_{0})\mid{\mathcal{E}}^{\prime}\cap\mathcal{S}}\right]$
and ${\mathbb{P}}[\mathcal{S}\mid{\mathcal{E}}^{\prime}]=\Omega(1)$ by Lemma
5.5, the assertion follows from (5.12) and Theorem 1.1.

To construct the coupling first choose a random matrix
$\boldsymbol{A}^{\prime}$ from the distribution of $\boldsymbol{A}_{0}$ given
${\mathcal{E}}$. Let
$N_{\ell}^{\prime}=\sum_{i=1}^{n}\boldsymbol{1}\\{\boldsymbol{d}_{i}=\ell\\}$
and
$M_{\ell}^{\prime}=\sum_{i=1}^{m}\boldsymbol{1}\\{\boldsymbol{k}_{i}=\ell\\}$.
Further, let $\mathcal{V}_{\ell}^{\prime}$ comprise the first
$n{\mathbb{P}}\left[{\boldsymbol{d}=\ell}\right]\wedge N_{\ell}^{\prime}$
indices $i$ with $\boldsymbol{d}_{i}=\ell$. Analogously, let
$\mathcal{F}_{\ell}^{\prime}$ contain the first
$m{\mathbb{P}}\left[{\boldsymbol{k}=\ell}\right]\wedge M_{\ell}^{\prime}$
indices $i\in[m]$ with $\boldsymbol{k}_{i}=\ell$. Let $X$ be the number of
edges of the Tanner graph of $\boldsymbol{A}^{\prime}$ that run between
$\bigcup_{\ell}\mathcal{V}_{\ell}^{\prime}$ and
$\bigcup_{\ell}\mathcal{F}_{\ell}^{\prime}$.

Moreover, let $Y$ be a random variable distributed as follows. Draw
$\boldsymbol{A}^{\prime\prime}$ from the distribution of $\boldsymbol{A}_{0}$
given ${\mathcal{E}}^{\prime}$. Let $\mathcal{V}_{\ell}^{\prime\prime}$
contain the first $n{\mathbb{P}}\left[{\boldsymbol{d}=\ell}\right]\wedge
N_{\ell}^{\prime}$ variables of degree $\ell$, and similarly let
$\mathcal{F}_{\ell}^{\prime\prime}$ contain the first
$m{\mathbb{P}}\left[{\boldsymbol{k}=\ell}\right]\wedge M_{\ell}^{\prime}$
constraints of degree $\ell$. Then $Y$ is the number of edges of the Tanner
graph of $\boldsymbol{A}^{\prime\prime}$ linking
$\bigcup_{\ell}\mathcal{V}_{\ell}^{\prime\prime}$ and
$\bigcup_{\ell}\mathcal{F}_{\ell}^{\prime\prime}$.

Because $\boldsymbol{A}^{\prime}\in{\mathcal{E}}$ and
$\boldsymbol{d},\boldsymbol{k}$ are supported on finite sets of integers, we
clearly have

$\displaystyle\left|{X-Y}\right|\leq O(\sqrt{n}\ln n).$ (5.13)

Letting $W=X\wedge Y$, we couple $\boldsymbol{A}^{\prime}$ and
$\boldsymbol{A}^{\prime\prime}$ as follows. Obtain the Tanner graph of
$\boldsymbol{A}^{\prime\prime\prime}$ by creating a random matching of size
$W$ between the clones of the variables
$\bigcup_{\ell}\mathcal{V}_{\ell}^{\prime}$ and the checks
$\bigcup_{\ell}\mathcal{F}_{\ell}^{\prime}$. Then obtain
$\boldsymbol{A}^{\prime}$, $\boldsymbol{A}^{\prime\prime}$ from
$\boldsymbol{A}^{\prime\prime\prime}$ by randomly matching the remaining
clones as determined by the respective degree sequences. The matrix entries
corresponding to the edges of the Tanner graph are drawn independently from
${\boldsymbol{\chi}}$ in such a way that those associated with the Tanner
graph of $\boldsymbol{A}^{\prime\prime\prime}$ agree. By the principle of
deferred decisions the resulting matrices $\boldsymbol{A}^{\prime}$,
$\boldsymbol{A}^{\prime\prime}$ are distributed as $\boldsymbol{A}$ given
${\mathcal{E}}$ and $\boldsymbol{A}$ given $\mathfrak{D}$. Furthermore,
because (5.13) shows that $\boldsymbol{A}^{\prime}$ and
$\boldsymbol{A}^{\prime\prime}$ disagree in no more than $O(\sqrt{n}\ln n)$
entries, we obtain (5.12). ∎

##  6\. Proof of Theorem 1.4

Recall that

$\phi(\alpha)=1-\alpha-\frac{1}{d}D^{\prime}\left(1-\frac{K^{\prime}(\alpha)}{k}\right).$
(6.1)

It is sufficient to prove that if conditions (i) and (ii) are satisfied then
(a) $\max_{\alpha\in[0,1]}\Phi(\alpha)=\max\\{\Phi(0),\Phi(\rho)\\}$; and (b)
$\phi^{\prime}(\rho)<0$ unless

${\mathbb{P}}({\boldsymbol{d}}=1)=0\quad\mbox{and}\quad
2({\mathbb{E}}\boldsymbol{k}-1){\mathbb{P}}({\boldsymbol{d}}=2)>{\mathbb{E}}{\boldsymbol{d}}.$
(6.2)

Since $\Phi(\alpha)$ is continuous on $[0,1]$, the maximum occurs at either 0
or 1 or at a stable point.

Case A: $\mathrm{Var}(\boldsymbol{k})=0$. In this case, $\boldsymbol{k}=k$
always and thus $K(\alpha)=\alpha^{k}$. Then,

$\displaystyle\phi(\alpha)$
$\displaystyle=1-\alpha-\frac{1}{d}D^{\prime}(1-\alpha^{k-1})$
$\displaystyle\phi^{\prime}(\alpha)$
$\displaystyle=-1+\frac{(k-1)\alpha^{k-2}}{d}D^{\prime\prime}(1-\alpha^{k-1})$
$\displaystyle\phi^{\prime\prime}(\alpha)$
$\displaystyle=\frac{k-1}{d}\alpha^{k-3}\Big{(}(k-2)D^{\prime\prime}(1-\alpha^{k-1})-(k-1)D^{\prime\prime\prime}(1-\alpha^{k-1})\alpha^{k-1}\Big{)}$
$\displaystyle=\frac{k-1}{d}\alpha^{k-3}\Big{(}(k-2)D^{\prime\prime}(t)-(k-1)D^{\prime\prime\prime}(t)(1-t)\Big{)}\quad\mbox{where
$t=1-\alpha^{k-1}$}.$

Hence,

$\displaystyle\phi(0)=0$ $\displaystyle\phi(1)=-\frac{1}{d}D^{\prime}(0)\leq
0$ (6.3) $\displaystyle\phi^{\prime}(0)=-1$
$\displaystyle\phi^{\prime}(1)=-1+\frac{k-1}{d}D^{\prime\prime}(0).$ (6.4)

Recall that
$\Phi^{\prime}(\alpha)=\frac{d}{k}K^{\prime\prime}(\alpha)\phi(\alpha)$. We
have $K^{\prime\prime}(\alpha)>0$ for all $\alpha\in(0,1]$. By (6.3) we have
$\Phi^{\prime}(1)\leq 0$ and thus the supremum of $\Phi(\alpha)$ can only
occur at 0 or a stable point. In all of the following sub-cases, we will prove
that $\phi^{\prime\prime}(\alpha)$ has at most 1 root in $[0,1]$ (except for
some trivial cases that we discuss separately). It follows immediately that
$\phi$ can have at most three roots on $[0,1]$ including the trivial one at
$\alpha=0$. Now we prove that this implies claims (a) and (b).

If $\phi$ has only a trivial root, then so is $\Phi^{\prime}(\alpha)$. Thus,
$\alpha=0$ is the unique maxima of $\Phi(\alpha)$ and $\rho=0$. This verifies
(a). As $\phi^{\prime}(0)=-1$ we immediately have $\phi^{\prime}(\rho)<0$.

If $\phi$ has two roots, then the larger root is $\rho$. Since
$\phi^{\prime}(0)<0$, in this case, $\phi$ is negative in $(0,\rho)$ and
positive in $(\rho,1)$. This is only possible when $\phi(1)=0$, which requires
${\mathbb{P}}({\boldsymbol{d}}=1)=0$. In this case, $\rho=1$. Next we consider
two further cases: (i) $2(k-1){\mathbb{P}}({\boldsymbol{d}}=2)>d$
corresponding to $\phi^{\prime}(1)>0$; (ii)
$2(k-1){\mathbb{P}}({\boldsymbol{d}}=2)<d$ corresponding to
$\phi^{\prime}(1)<0$. As $\phi$ has only two roots, case (ii) obviously cannot
happen. Thus, it means that the only situation that $\phi$ has two roots would
be ${\mathbb{P}}({\boldsymbol{d}}=1)=0$ and
$2(k-1){\mathbb{P}}({\boldsymbol{d}}=2)>d$, as in (6.2). In this situation we
are only required to verify (a). Note that $\phi$ is negative in $(0,1)$ as
$\rho=1$. It follows then that $\Phi(\alpha)$ is a decreasing function in
$(0,1)$. Hence, $\alpha=0$ is the unique maxima, as desired.

If $\phi$ has three roots, then there is a root $\rho^{*}$ between $0$ and
$\rho$. Then $\phi$ is negative in $(0,\rho^{*})$ and positive in
$(\rho^{*},\rho)$. As $K^{\prime\prime}(\alpha)>0$ for all $\alpha\in(0,1]$,
the sign of $\phi$ implies that $\rho^{*}$ is a local minima and $\rho$ is a
local maxima. This verifies (a). Moreover, as $\phi$ is positive in
$(\rho^{*},\rho)$ and $\phi(\rho)=0$, $\phi^{\prime}(\rho)<0$ follows
immediately.

Case A1: $\mathrm{Var}(\boldsymbol{k})=0$ and
$\mathrm{Var}({\boldsymbol{d}})=0$. In this case ${\boldsymbol{d}}=d$. Then
$D(\alpha)=\alpha^{d}$. If $d\geq 3$ then

$\displaystyle\phi^{\prime\prime}(\alpha)$
$\displaystyle=\frac{k-1}{d}\alpha^{k-3}\Big{(}(k-2)d(d-1)t^{d-2}-(k-1)d(d-1)(d-2)t^{d-3}(1-t)\Big{)}$
$\displaystyle=(k-1)(d-1)t^{d-3}\alpha^{k-3}\Big{(}(k-2)t-(k-1)(d-2)(1-t)\Big{)}\quad\mbox{where
$t=1-\alpha^{k-1}$}.$

Obviously, $\phi^{\prime\prime}(\alpha)$ has a unique root in $[0,1]$.

If $d=1$ then $\phi^{\prime}(\alpha)=-1$ and so $\phi$ has only a trivial root
at $\alpha=0$; If $d=2$ then $\phi^{\prime\prime}(\alpha)>0$ in $(0,1)$ and so
$\phi$ is convex and thus has only a trivial root at $\alpha=0$ by (6.3).
Hence for $d\leq 2$, $\rho=0$ and is the unique maxima. Claims (a) and (b)
hold trivially.

Case A2: $\mathrm{Var}(\boldsymbol{k})=0$ and ${\boldsymbol{d}}\sim{\bf
Po}_{\geq r}(\lambda)$. In this case
$D(\alpha)=h_{r}(\lambda\alpha)/h_{r}(\lambda)$, where

$\displaystyle h_{r}(x)$ $\displaystyle=\sum_{j\geq
r}\frac{x^{j}}{j!}\quad\mbox{for all nonnegative integers $x$};$ (6.5)
$\displaystyle h_{r}(x)$ $\displaystyle=e^{x}\quad\mbox{for all negative
integers $x$}.$ (6.6)

Then, for all integers $t$,

$D^{\prime}(\alpha)=\frac{\lambda h_{r-1}(\lambda\alpha)}{h_{r}(\lambda)},\
D^{\prime\prime}(\alpha)=\frac{\lambda^{2}h_{r-2}(\lambda\alpha)}{h_{r}(\lambda)},\
D^{\prime\prime\prime}(\alpha)=\frac{\lambda^{3}h_{r-3}(\lambda\alpha)}{h_{r}(\lambda)}.$

Since ${\mathbb{E}}{\boldsymbol{d}}=d$, it requires that $\lambda$ satisfies

$D^{\prime}(1)=\frac{\lambda h_{r-1}(\lambda)}{h_{r}(\lambda)}=d.$ (6.7)

Thus,

$\phi^{\prime\prime}(\alpha)=\frac{(k-1)d\alpha^{k-3}}{h_{r}(\lambda)}\Big{(}(k-2)h_{r-2}(\lambda
t)-(k-1)(1-t)h_{r-3}(\lambda t)\Big{)}.$

Solving $\phi^{\prime\prime}(\alpha)=0$ yields

$\frac{k-1}{k-2}(1-t)=\frac{h_{r-2}(\lambda t)}{h_{r-3}(\lambda
t)}=1-\frac{h_{r-3}(\lambda t)-h_{r-2}(\lambda t)}{h_{r-3}(\lambda t)}.$ (6.8)

The right hand side above is obviously a constant function if $r\leq 2$. If
$r\geq 3$, then $h_{r-3}(\lambda t)-h_{r-2}(\lambda t)=(\lambda
t)^{r-3}/(r-3)!$, and $h_{r-3}(\lambda t)$ is a power series of $\lambda t$
with minimum degree $r-3$. Hence, by dividing $(\lambda t)^{r-3}/(r-3)!$ from
both the numerator and the denominator, we immediately get that the right hand
side of (6.8) is an increasing function. However the left hand side of (6.8)
is a decreasing function. Hence (6.8) has at most one solution, implying that
$\phi^{\prime\prime}(\alpha)$ has at most one root.

Case B: $\boldsymbol{k}\sim{\bf Po}_{\geq s}(\gamma)$ where $s\geq 3$. We must
have $\gamma$ satisfy

$\frac{\gamma h_{s-1}(\gamma)}{h_{s}(\gamma)}=k,$

so that ${\mathbb{E}}\boldsymbol{k}=k$. Now we have
$K(\alpha)=h_{s}(\gamma\alpha)/h_{s}(\gamma)$, where $h_{s}$ is defined as in
(6.5) and (6.6). Thus,

$\displaystyle\phi(\alpha)$
$\displaystyle=1-\alpha-\frac{1}{d}D^{\prime}\left(1-\frac{h_{s-1}(\gamma\alpha)}{h_{s-1}(\gamma)}\right)$
$\displaystyle\phi^{\prime}(\alpha)$ $\displaystyle=-1+\frac{\gamma
h_{s-2}(\gamma\alpha)}{dh_{s-1}(\gamma)}D^{\prime\prime}\left(1-\frac{h_{s-1}(\gamma\alpha)}{h_{s-1}(\gamma)}\right)$
$\displaystyle\phi^{\prime\prime}(\alpha)$
$\displaystyle=\frac{\gamma^{2}}{dh_{s-1}(\gamma)}\left(h_{s-3}(\gamma\alpha)D^{\prime\prime}\left(1-\frac{h_{s-1}(\gamma\alpha)}{h_{s-1}(\gamma)}\right)-\frac{h_{s-2}(\gamma\alpha)^{2}}{h_{s-1}(\gamma)}D^{\prime\prime\prime}\left(1-\frac{h_{s-1}(\gamma\alpha)}{h_{s-1}(\gamma)}\right)\right).$

Hence,

$\displaystyle\phi(0)=0$ $\displaystyle\phi(1)=-\frac{1}{d}D^{\prime}(0)\leq
0$ (6.9) $\displaystyle\phi^{\prime}(0)=-1$
$\displaystyle\phi^{\prime}(1)=-1+\frac{\gamma
h_{s-2}(\gamma)}{dh_{s-1}(\gamma)}D^{\prime\prime}(0).$ (6.10)

As before, we will prove that $\phi^{\prime\prime}(\alpha)$ has at most 1 root
in $[0,1]$ (except for some trivial cases that will be discussed separately),
which is sufficient to ensure (a) and (b).

Case B1: $\boldsymbol{k}\sim{\bf Po}_{\geq s}(\gamma)$ and
$\mathrm{Var}({\boldsymbol{d}})=0$. In this case ${\boldsymbol{d}}=d$. Then
$D(\alpha)=\alpha^{d}$. If $d\geq 3$ then solving
$\phi^{\prime\prime}(\alpha)=0$ yields

$\frac{d-2}{h_{s-1}(\gamma)}\cdot
h_{s-2}(\gamma\alpha)=\left(1-\frac{h_{s-1}(\gamma\alpha)}{h_{s-1}(\gamma)}\right)\frac{h_{s-3}(\gamma\alpha)}{h_{s-2}(\gamma\alpha)}.$
(6.11)

On the right hand side above, $1-h_{s-1}(\gamma\alpha)/h_{s-1}(\gamma)\geq 0$
and is a decreasing function of $\alpha$. We also have

$\frac{h_{s-3}(\gamma\alpha)}{h_{s-2}(\gamma\alpha)}=\frac{h_{s-3}(\gamma\alpha)}{h_{s-3}(\gamma\alpha)-(\gamma\alpha)^{s-3}/(s-3)!}=\left(1-\frac{(\gamma\alpha)^{s-3}/(s-3)!}{h_{s-3}(\gamma\alpha)}\right)^{-1},$

which is positive and a decreasing function of $\alpha$. Hence, the left hand
side of (6.11) is an increasing function whereas the right hand side is a
decreasing function. Hence $\phi^{\prime\prime}(\alpha)$ has at most one root.

If $d\leq 2$ the same argument as in Case A1 shows that claims (a) and (b)
hold.

Case B2: $\boldsymbol{k}\sim{\bf Po}_{\geq s}(\gamma)$ and
${\boldsymbol{d}}\sim{\bf Po}_{\geq r}(\lambda)$. In this case
$D(\alpha)=h_{r}(\lambda\alpha)/h_{r}(\lambda)$, and $\lambda$ necessarily
satisfies (7.3). Then solving $\phi^{\prime\prime}(\alpha)=0$ yields

$\frac{\lambda}{h_{s-1}(\gamma)}h_{s-2}(\gamma\alpha)=\frac{h_{s-3}(\gamma\alpha)}{h_{s-2}(\gamma\alpha)}\cdot\frac{h_{r-2}(\lambda(1-h_{s-1}(\gamma\alpha)/h_{s-1}(\gamma)))}{h_{r-3}(\lambda(1-h_{s-1}(\gamma\alpha)/h_{s-1}(\gamma)))}$

The left hand side is an increasing function whereas the right hand side is
the product of two positive decreasing functions. Thus,
$\phi^{\prime\prime}(\alpha)$ has at most one root.

##  7\. Proof of Theorem 1.3

Proof of Theorem 1.3.  We describe how to extend the proof of [56] to ${\bf
G}$. Using the terminology in [56], variable nodes in ${\bf G}$ are called
vertices, and each check node corresponds to a hyperedge in the following
sense: if $f_{a}$ is a check node adjacent with variable nodes
$\\{v_{a_{1}},\ldots,v_{a_{h}}\\}$ for some $h\geq 3$, then the set of
vertices $\\{v_{a_{1}},\ldots,v_{a_{h}}\\}$ is called a hyperedge. Consider
the parallel stripping process where all vertices of degree less than 2 are
deleted in each step, together with the hyperedge (if any) incident with it.
Take a random vertex $v\in[n]$. Let $\lambda_{t}$ be the probability that $v$
survives after $t$ iterations of the stripping process. It is easy to see that
$\lambda_{t}$ is monotonely non-increasing and thus
$\lambda=\lim_{t\to\infty}\lambda_{t}$ exists. For any vertex $u\in[n]$, let
${\mathcal{N}}_{j}(u)$ denote the set of vertices of distance $j$ from $u$. We
claim that

######  Claim 7.1.

With high probability, the maximum degree and the maximum size of hyperedges
in ${\bf G}$ is at most
$(n\log n)^{1/(2+r)}$, and for every $u\in[n]$ and for all fixed $r$,
$|\cup_{j\leq r}{\mathcal{N}}_{j}(u)|=O(n^{1/(2+r)}\log^{2}n)$.

Let $H_{t}$ be the subgraph of $G_{n}$ obtained after $t$ iterations of the
parallel stripping process. Consider Doob’s martingale
$({\mathbb{E}}(H_{t}\mid e_{1},\ldots,e_{j}))_{0\leq j\leq m}$ where random
hyperedges are added in order $e_{1},\ldots,e_{m}$ using the configuration
model. By Claim 7.1, swapping two clones in the configuration model would
affect $H_{t}$ by $O(n^{1/(2+r)}\log^{2}n)$, as each altered hyperedge can
only affect the vertices (if surviving the first $t$-th iteration or not)
within its $t$-neighbourhood. Standard concentration arguments of Azuma’s
inequality [Regular, Theorem 2.19] (with Lipschitz constant
$Cn^{1/(2+r)}\log^{2}n$ for some fixed $C>0$) produce that
$||H_{t}|-\lambda_{t}n|=O(n^{(4+r)/(4+2r)}\log^{3}n)=o(n)$. Next we deduce an
expression for $\lambda_{t}$. Consider a random hypertree $T$ iteratively
built as follows. The root of $T$ is $v$, which is incident to $d_{v}$
hyperedges of size $\boldsymbol{k}_{1},\ldots,\boldsymbol{k}_{d_{v}}$ where
the $\boldsymbol{k}_{i}$s are i.i.d. copies of $\hat{\boldsymbol{k}}$ where

${\mathbb{P}}(\hat{\boldsymbol{k}}=j)=\frac{j{\mathbb{P}}(\boldsymbol{k}=j)}{k}.$
(7.1)

Then the $i$-th hyperedge is incident to other $\boldsymbol{k}_{i}-1$ vertices
(other than $v$) whose degrees are i.i.d. copies of $\hat{\boldsymbol{d}}$,
where

${\mathbb{P}}(\hat{\boldsymbol{d}}=j)=\frac{j{\mathbb{P}}({\boldsymbol{d}}=j)}{d}.$
(7.2)

This builds the first neighbourhood of $v$ in $T$. Iteratively we can build
the $r$-neighbourhood of $v$ in $T$ for any fixed $r$. It follows from the
following claim that the $r$-neighbourhood of $v$ in ${\bf G}$ converges in
distribution to the $r$-neighbourhood of $T$, as $n\to\infty$, for any fixed
$r\geq 1$. This is because when uniformly picking a random variable clone (or
check clone), the degree of the corresponding variable node (or check node)
has the distribution in (7.2) (or (7.1)).

######  Claim 7.2.

With high probability, for all fixed $r\geq 1$, $\cup_{j\leq
r}{\mathcal{N}}_{j}(v)$ induces no cycles.

If $v$ survives $t$ iterations of the stripping process then at least 2
hyperedges incident with $v$ survives after $t$ iterations of the stripping
process. Let $\rho_{t}$ denote the probability that $v$ is incident with at
least 1 hyperedge surviving after $t$ iterations of the stripping process.
Then, ignoring an $o(1)$ error accounting for the probability of the
complement of the evens in Claims 7.1 and 7.2:

$\rho_{0}=1$

and

$\displaystyle\rho_{t+1}$ $\displaystyle=\sum_{j\geq
1}\frac{j{\mathbb{P}}({\boldsymbol{d}}=j)}{d}\sum_{S\subseteq[j-1],|S|\geq
1}\sum_{k_{1},\ldots,k_{j-1}}\prod_{i=1}^{j-1}{\mathbb{P}}(\hat{\boldsymbol{k}}_{i}=k_{1})\prod_{i\in
S}\rho_{t}^{k_{i}-1}\prod_{i\notin S}(1-\rho_{t})^{k_{i}-1}$
$\displaystyle=\sum_{j\geq
1}\frac{j{\mathbb{P}}({\boldsymbol{d}}=j)}{d}\sum_{h\geq
1}\binom{j-1}{h}\left(\sum_{k_{1}}{\mathbb{P}}(\hat{\boldsymbol{k}}_{i}=k_{1})\rho_{t}^{k_{1}-1}\right)^{h}\left(\sum_{k_{1}}{\mathbb{P}}(\hat{\boldsymbol{k}}_{i}=k_{1})(1-\rho_{t})^{k_{1}-1}\right)^{j-1-h}$
$\displaystyle=\sum_{j\geq
2}\frac{j{\mathbb{P}}({\boldsymbol{d}}=j)}{d}\sum_{h\geq
1}\binom{j-1}{h}\left(\frac{K^{\prime}(\rho_{t})}{k}\right)^{h}\left(1-\frac{K^{\prime}(\rho_{t})}{k}\right)^{j-1-h}$
$\displaystyle=\sum_{j\geq
2}\frac{j{\mathbb{P}}({\boldsymbol{d}}=j)}{d}\left(1-\left(1-\sum_{j\geq
2}\frac{j{\mathbb{P}}({\boldsymbol{d}}=j)}{d}\right)^{j-1}\right)=1-\frac{D^{\prime}(1-\frac{K^{\prime}(\rho_{t})}{k})}{d},$

noting that

${\mathbb{E}}\rho^{\hat{\boldsymbol{k}}-1}=\sum_{j}\frac{j{\mathbb{P}}(\boldsymbol{k}=j)}{k}\rho^{j-1}=\frac{K^{\prime}(\rho)}{k}.$

Similarly,

$\displaystyle\lambda_{t}$ $\displaystyle=\sum_{j\geq
2}{\mathbb{P}}({\boldsymbol{d}}=j)\sum_{h\geq
2}\binom{j}{h}\left(\sum_{k_{1}}{\mathbb{P}}(\hat{\boldsymbol{k}}_{i}=k_{1})\rho_{t}^{k_{1}-1}\right)^{h}\left(\sum_{k_{1}}{\mathbb{P}}(\hat{\boldsymbol{k}}_{i}=k_{1})(1-\rho_{t})^{k_{1}-1}\right)^{j-h}$
$\displaystyle=\sum_{j\geq 2}{\mathbb{P}}({\boldsymbol{d}}=j)\sum_{h\geq
2}\binom{j}{h}\left({\mathbb{E}}\rho_{t}^{\hat{\boldsymbol{k}}-1}\right)^{h}\left(1-{\mathbb{E}}\rho_{t}^{\hat{\boldsymbol{k}}-1}\right)^{j-h}$
$\displaystyle=\sum_{j\geq
2}{\mathbb{P}}({\mathcal{D}}=j)\left(1-\left(\frac{K^{\prime}(\rho_{t})}{k}\right)^{j}-j\frac{K^{\prime}(\rho_{t})}{k}\left(1-\frac{K^{\prime}(\rho_{t})}{k}\right)^{j-1}\right)$
$\displaystyle=1-D\left(1-\frac{K^{\prime}(\rho_{t})}{k}\right)-\frac{K^{\prime}(\rho_{t})}{k}D^{\prime}\left(\frac{K^{\prime}(\rho_{t})}{k}\right).$

Let $g(x)=1-\frac{1}{d}D^{\prime}(1-\frac{K^{\prime}(x)}{k})$. Then
$g^{\prime}(x)=\frac{1}{dk}D^{\prime\prime}(1-\frac{K^{\prime}(x)}{k})K^{\prime\prime}(x)$
which is non-negative over $[0,1]$. We also have $\phi(x)=g(x)-x$, where
$\phi$ is given in (6.1). Since $\phi(1)=-D^{\prime}(0)/d\leq 0$,
$\phi^{\prime}(\rho)<0$ by the hypothesis, and $g(x)$ is nondecreasing in
$[0,1]$, it follows that $\rho$ is an attractive fix point of $x=g(x)$. As
$\rho_{0}=1$. It follows that $\rho_{t}\to\rho$ as $t\to\infty$. Consequently,
for every $\hat{\varepsilon}>0$ there is sufficiently large $I$ such that
$|\rho_{t}-\rho|<\hat{\varepsilon}$. Hence, after $I$ iterations of the
parallel stripping process, the number of vertices remaining is
$(\lambda+o(1))n+O(\hat{\varepsilon}n)$ where

$\lambda=1-D\left(1-\frac{K^{\prime}(\rho)}{k}\right)-\frac{K^{\prime}(\rho)}{k}D^{\prime}\left(\frac{K^{\prime}(\rho)}{k}\right).$
(7.3)

If $\rho=0$ then $\lambda=0$. The case $\rho=0$ of our theorem follows by
letting $I\to\infty$.

Suppose $\rho>0$. It is sufficient to show that the 2-core is obtained after
removing further $O(\hat{\varepsilon}n)$ vertices, following the same approach
as [56, Lemma 4]. We briefly sketch it. Following the same argument as before,
the probability that a random vertex has degree $j\geq 2$ after $I$ iterations
of the stripping process is

$\sum_{i\geq
2}{\mathbb{P}}({\boldsymbol{d}}=i)\binom{i}{j}({\mathbb{E}}\rho_{I}^{\hat{\boldsymbol{k}}-1})^{j}(1-{\mathbb{E}}\rho_{I}^{\hat{\boldsymbol{k}}-1})^{i-j}=\sum_{i\geq
2}{\mathbb{P}}({\boldsymbol{d}}=i)\binom{i}{j}\left(\frac{K^{\prime}(\rho_{I})}{k}\right)^{j}\left(1-\frac{K^{\prime}(\rho_{I})}{k}\right)^{i-j}.$

Similarly, the probability of a uniformly random hyperedge in $G_{n}$ having
size $j\geq 3$ and surviving the first $I$ iterations of the stripping process
is

${\mathbb{P}}(\boldsymbol{k}=j)\rho_{I}^{j}.$

The number of vertices with degree less than 2 after $I$ iterations is bounded
by $(\lambda_{I}-\lambda_{I+1})n+o(n)$. Hence, by choosing $I$ sufficiently
large, we can make these quantities arbitrarily close to those with $\rho_{I}$
replaced by $\rho$. Now standard concentration arguments apply to show that
the number of degree $j\geq 2$ vertices is
$\gamma_{j}n+O(\hat{\varepsilon}n)$, where

$\gamma_{j}=\sum_{i=0}^{\infty}{\mathbb{P}}({\boldsymbol{d}}=i)\binom{i}{j}\left(\frac{K^{\prime}(\rho)}{k}\right)^{j}\left(1-\frac{K^{\prime}(\rho)}{k}\right)^{i-j},$

the number of vertices of degree less than 2 is $O(\hat{\varepsilon}n)$, and
the proportion of remaining hyperedges of size $j$ is

$\frac{{\mathbb{P}}(\boldsymbol{k}=j)\rho^{j}}{\sum_{i\geq
3}{\mathbb{P}}(\boldsymbol{k}=i)\rho^{i}}+O(\hat{\varepsilon})=\frac{{\mathbb{P}}(\boldsymbol{k}=j)\rho^{j}}{K(\rho)}+O(\hat{\varepsilon}),$

as the probability that a hyperedge survives is proportional to the
probability that all of the vertices it contains survive. Note that
$\hat{\varepsilon}$ can be made arbitrarily small by choosing sufficiently
large $I$.

Now we remove one hyperedge incident with a vertex with degree 1 at a time.
Call this process SLOWSTRIP. Let $G_{t}$ denote the hypergraph obtained after
$t$ steps of SLOWSTRIP and let $X_{t}$ denote the total degree of the vertices
of degree 1 in $G_{t}$. Then,

$\displaystyle{\mathbb{E}}(X_{t+1}-X_{t}\mid G_{t})$
$\displaystyle=-1+\sum_{j\geq
3}\frac{j{\mathbb{P}}(\boldsymbol{k}=j)\rho^{j}/K(\rho)}{\rho
K^{\prime}(\rho)/K(\rho)}\cdot(j-1)\cdot\frac{2\gamma_{2}}{\sum_{j\geq
2}j\gamma_{j}}+O(\hat{\varepsilon})$ $\displaystyle=-1+\frac{1}{\rho
K^{\prime}(\rho)}\left(\sum_{j\geq
3}j(j-1){\mathbb{P}}(\boldsymbol{k}=j)\rho^{j}\right)\frac{2\cdot\frac{1}{2}(K^{\prime}(\rho)/k)^{2}D^{\prime\prime}(1-K^{\prime}(\rho)/k)}{K^{\prime}(\rho)d\rho/k}+O(\hat{\varepsilon})$
$\displaystyle=-1+\frac{D^{\prime\prime}(1-K^{\prime}(\rho)/k)K^{\prime\prime}(\rho)}{kd}+O(\hat{\varepsilon}).$

Note that in the first equation above, $-1$ accounts for the removal of one
variable clone $x$ from the set of vertices of degree less than 2. The term
$j{\mathbb{P}}(\boldsymbol{k}=j)\rho^{j}/\rho K^{\prime}(\rho)$ approximates
the probability that $x$ is contained in a hyperedge of size $j$, up to an
$O(\hat{\varepsilon})$ error. In that case, $j-1$ variable clones that lie in
the same hyperedge as $x$ will be removed. For each of these $j-1$ deleted
variable clones, if it lies in a variable of degree 2, then it results in one
new variable node of degree 1. The probability for that to happen is
approximated by $2\gamma_{2}/\sum_{j\geq 2}j\gamma_{j}$, up to an
$O(\hat{\varepsilon})$ error. By the assumption that $f^{\prime}(\rho)<0$ we
have

$-1+\frac{D^{\prime\prime}(1-K^{\prime}(\rho)/k)K^{\prime\prime}(\rho)}{kd}<0.$

Hence, ${\mathbb{E}}(X_{t+1}-X_{t}\mid G_{t})<-\delta$ for some $\delta>0$, by
making $\hat{\varepsilon}$ sufficiently small (i.e. by choosing sufficiently
large $I$). Then standard Azuma inequality [32, Lemma 29] (with Lipschitz
constant $n^{1/5}\log n$ by Claim 7.1) will be sufficient to show that $X_{t}$
decreases to 0 after $O(\hat{\varepsilon}n)$ steps (See details in [56, Lemma
4]). The case $\rho>0$ of the theorem follows by (7.3) and

$\lim_{n\to\infty}\frac{{\boldsymbol{m}}^{*}}{n}=\lim_{n\to\infty}\frac{m}{n}\cdot\sum_{i\geq
3}{\mathbb{P}}(\boldsymbol{k}=i)\rho^{i}=\frac{d}{k}K(\rho).\qed$

Proof of Claim 7.1.  Since both ${\mathbb{E}}{\boldsymbol{d}}^{2+r}=O(1)$ and
${\mathbb{E}}\boldsymbol{k}^{2+r}=O(1)$, the probability that
${\boldsymbol{d}}>(n\log n)^{1/(2+r)}$ or $\boldsymbol{k}>(n\log n)^{1/(2+r)}$
is $O(1/n\log n)$. The bound on the maximum degree and maximum size of the
hyperedges in ${\bf G}$ follows by taking the union bound.

For any $u\in[n]$, let $N_{i}(u)=|{\mathcal{N}}_{i}(u)|$. We will prove that
with high probability for every $u$ and for every fixed $i$,
$N_{i}(u)=O(n^{1/(2+r)}\log^{2}n)$, which then completes the proof for Claim
7.1. We prove by induction. Let $d_{1},\ldots,d_{N_{i}(u)}$ denote the degrees
of the vertices in ${\mathcal{N}}_{i}(u)$. Then the number of hyperedges
incident with these vertices is bounded by $M:=\sum_{j=1}^{N_{i}(u)}d_{j}$. By
the construction of ${\bf G}$, each $M$ is stochastically dominated by
$\sum_{j=1}^{N_{i}(u)}(1+o(1))\hat{\boldsymbol{d}}_{j}$ where
$\hat{\boldsymbol{d}}_{j}$ are i.i.d. copies of $\hat{\boldsymbol{d}}$ whose
distribution is given in (7.2). The $o(1)$ error is caused by the exposure of
$\cup_{j\leq i}{\mathcal{N}}_{j}$ which contains $o(n)$ vertices by induction.
Since ${\mathbb{E}}{\boldsymbol{d}}^{2+r}=O(1)$, we have
$\hat{d}:={\mathbb{E}}\hat{\boldsymbol{d}}=O(1)$. Note that
${\mathbb{E}}M=\hat{d}N_{i}(u)$. Applying the Chernoff bound to the sum of
independent $[0,1]$-valued random variables we have

${\mathbb{P}}\left(M\geq
2\hat{d}N_{i}(u)+n^{1/(2+r)}\log^{2}n\right)={\mathbb{P}}\left(\sum_{j=1}^{N_{i}(u)}\frac{\hat{\boldsymbol{d}}_{i}}{(n\log
n)^{1/(2+r)}}\geq\frac{2\hat{d}N_{i}(u)}{(n\log n)^{1/(2+r)}}+(\log
n)^{(3+r)/(2+r)}\right)<n^{-2}.$

Similarly, $N_{i+1}(u)$ is bounded by $\sum_{j=1}^{M}k_{i}$, where $k_{i}$ are
the sizes of the hyperedges incident with the vertices in ${\mathcal{N}}_{i}$.
Similarly, $\sum_{j=1}^{M}k_{i}$ is stochastically dominated by
$(1+o(1))\sum_{j=1}^{M}\hat{\boldsymbol{k}}_{j}$ where
$\hat{\boldsymbol{k}}_{j}$ are i.i.d. copies of $\hat{\boldsymbol{k}}$ whose
distribution is defined in (7.1). Let
$\hat{k}={\mathbb{E}}\hat{\boldsymbol{k}}$. Applying the Chernoff bound again
we obtain that with probability at least $1-n^{-2}$,
$N_{i+1}(u)<2\hat{k}M+n^{1/(2+r)}\log^{2}n<4\hat{d}\hat{k}N_{i}(u)+(1+2\hat{k})n^{1/(2+r)}\log^{2}n$.
Apply this recursion inductively and the union bound on the failure
probability, we obtain $N_{i}(u)=O(n^{1/(2+r)}\log^{2}n)$, as desired. ∎

Proof of Claim 7.2.  Fix $\varepsilon>0$. Choose $L=L(\varepsilon,r)$
sufficiently large so that the probability that $d_{v}>L$ is smaller than
$\varepsilon$ (note that $v$ is a uniformly random vertex). Given $d_{v}\leq
L$. Let $k_{1},\ldots,k_{d_{v}}$ be the sizes of the hyperedges incident to
$v$. Similarly to the proof of Claim 7.1, $k_{j}$s are approximated by i.i.d.
copies of $\hat{\boldsymbol{k}}$ defined in (7.1), up to an $1+o(1)$
multiplicative error. We can assume $L$ is sufficiently large so that with
probability at least $1-\varepsilon$, $\sum_{i=1}^{d_{v}}k_{i}\leq L$.
Inductively, we can make $L$ sufficiently large so that
$|{\mathcal{N}}_{i}(v)|\leq L$ for all $i\leq r$. Let ${\mathcal{E}}_{i}$
denote the set of hyperedges incident with vertices in ${\mathcal{N}}_{i}(v)$,
but not incident with any in ${\mathcal{N}}_{i-1}$. Cycles in
${\mathcal{N}}_{i}(v)$ can appear in two ways: (a) two vertices in
${\mathcal{N}}_{i}(v)$ are incident with the same hyperedge in
${\mathcal{E}}_{i}$; (b) two hyperedges in ${\mathcal{E}}_{i-1}$ are incident
with the same vertex in ${\mathcal{N}}_{i}(v)$. We will prove that with high
probability, none of the two cases occurs for any fixed $i$. For (a), let
$(d_{j})_{j\in{\mathcal{N}}_{i}(v)}$ denote the degrees of the vertices in
${\mathcal{N}}_{i}(v)$. The expected number of occurrences of pairs of
vertices in (a) is

${\mathbb{E}}\left(\sum_{j,k\in{\mathcal{N}}_{i}(v)}\binom{d_{j}}{2}\binom{d_{k}}{2}\sum_{h\in[{\boldsymbol{m}}]}\binom{k_{h}}{2}O(n^{-2})\right)=O(n^{-1}){\mathbb{E}}\left(\sum_{j,k\in{\mathcal{N}}_{i}(v)}d_{j}^{2}d_{k}^{2}\right).$
(7.4)

Note that $|{\mathcal{N}}_{j}(v)|\leq L$ for each $j\leq r$. This immediately
implies that $d_{j}\leq L$ for all $j\in{\mathcal{N}}_{i}(v)$. Hence, the
above probability is $O(n^{-1})$. The probability that
$|{\mathcal{N}}_{i}(v)|\leq L$ fails is at most $r\varepsilon$ by our choice
of $L$. Hence, the probability that (a) fails is at most $r\varepsilon+o(1)$.
The treatment of (b) is analogous. Our claim now follows by letting
$\varepsilon\to 0$. ∎

### Acknowledgment

We thank David Saad for a helpful conversation and Guilhem Semerjian for
bringing [48] to our attention.

## References

  * [1] D. Achlioptas, M. Molloy: The solution space geometry of random linear equations. Random Structures and Algorithms 46 (2015) 197–231.
  * [2] M. Aizenman, R. Sims, S. Starr: An extended variational principle for the SK spin-glass model. Phys. Rev. B 68 (2003) 214403.
  * [3] R. Alamino, D. Saad: Typical kernel size and number of sparse random matrices over Galois fields: a statistical physics approach. Physical Review E 77 (2008) 061123.
  * [4] P. Ayre, A. Coja-Oghlan, P. Gao, N. Müller: The satisfiability threshold for random linear equations. arXiv:1710.07497 (2017).
  * [5] G. Balakin: On random matrices. Theory Probab. Appl. 12 (1967) 346–353.
  * [6] G. Balakin: The distribution of random matrices over a finite field. Theory Probab. Appl. 13 (1968) 631–641.
  * [7] V. Bapst, A. Coja-Oghlan: Harnessing the Bethe free energy. Random Structures and Algorithms 49 (2016) 694–741.
  * [8] M. Bayati, D. Gamarnik, P. Tetali: Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. Annals of Probability 41 (2013) 4080–4115.
  * [9] J. Blömer, R. Karp, E. Welzl: The rank of sparse random matrices over finite fields. Random Structures and Algorithms 10 (1997) 407–419.
  * [10] B. Bollobás: The evolution of sparse graphs. Graph theory and combinatorics (Cambridge) (1983) 35–57.
  * [11] J. Bourgain, V. Vu, P. Wood: On the singularity probability of discrete random matrices. Journal of Functional Analysis 258 (2010) 559–603.
  * [12] C. Bordenave, M. Lelarge, J. Salez: The rank of diluted random graphs Ann. Probab. 39 (2011) 1097–1121.
  * [13] C. Bordenave, M. Lelarge, J. Salez: Matchings on infinite graphs. Probability Theory and Related Fields 157 (2013) 183–208.
  * [14] D. Burshtein, M. Krivelevich, S. Litsyn, G. Miller: Upper bounds on the rate of LDPC codes. IEEE Transactions on Information Theory 48 (2002), 2437–2449.
  * [15] J. Cain, N. Wormald: Encores on cores. Electronic journal of combinatorics, 13(1), 81 (2006).
  * [16] V. Chvátal: Almost all graphs with $1.44n$ edges are 3-colorable. Random Structures Algorithms 2(1) (1991) 11–28.
  * [17] S. Cocco, O. Dubois, J. Mandler, R. Monasson: Rigorous decimation-based construction of ground pure states for spin glass models on random lattices. Phys. Rev. Lett. 90 (2003) 047205.
  * [18] A. Coja-Oghlan, F. Krzakala, W. Perkins and L. Zdeborova: Information-theoretic thresholds from the cavity method. Advances in Mathematics 333 (2018) 694–795.
  * [19] A. Coja-Oghlan, W. Perkins: Spin systems on Bethe lattices. arXiv:1808.03440 (2018).
  * [20] C. Cooper: The cores of random hypergraphs with a given degree sequence. Random Structures and Algorithms 25(4) (2004) 353–375.
  * [21] C. Cooper: On the rank of random matrices. Random Structures and Algorithms 16 (2000) 209–232.
  * [22] C. Cooper, A. Frieze, W. Pegden: On the rank of a random binary matrix. arXiv 1806.04988 (2018).
  * [23] A. Dembo, E. Lubetzky: Empirical spectral distributions of sparse random graphs. arXiv:1610.05186 (2016).
  * [24] M. Dietzfelbinger, A. Goerdt, M. Mitzenmacher, A. Montanari, R. Pagh, M. Rink: Tight thresholds for cuckoo hashing via XORSAT. Proc. 37th ICALP (2010) 213–225.
  * [25] O. Dubois, J. Mandler: The 3-XORSAT threshold. Proc. 43rd FOCS (2002) 769–778.
  * [26] R. Durrett: Probability theory and examples, 3rd edition (2005).
  * [27] P. Erdös, A. Rényi: On random matrices. Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 (1963) 455–461.
  * [28] D. Fernholz, V. Ramachandran: The giant $k$-core of a random graph with a specified degree sequence. Manuscript, 2003.
  * [29] D. Fernholz, V. Ramachandran: Cores and connectivity in sparse random graphs. The University of Texas at Austin, Department of Computer Sciences, technical report TR-04-13 (2004).
  * [30] S. Franz, M. Leone: Replica bounds for optimization problems and diluted spin systems. J. Stat. Phys. 111 (2003) 535–564.
  * [31] R. Gallager: Low-density parity check codes. IRE Trans. Inform. Theory 8 (1962) 21–28.
  * [32] P. Gao, M. Molloy: The stripping process can be slow: part I. arXiv:1501.02695 (2015).
  * [33] A. Giurgiu, N. Macris, R. Urbanke: Spatial coupling as a proof technique and three applications. IEEE Transactions on Information Theory 62 (2016) 5281–5295.
  * [34] A. Goerdt, L. Falke: Satisfiability thresholds beyond $k$-XORSAT. Proc. 7th International Computer Science Symposium in Russia (2012) 148–159.
  * [35] F. Guerra: Broken replica symmetry bounds in the mean field spin glass model. Communications in Mathematical Physics 233 (2003) 1–12.
  * [36] M. Ibrahimi, Y. Kanoria, M. Kraning, A. Montanari: The set of solutions of random XORSAT formulae. Annals of Applied Probability 25 (2015) 2743–2808.
  * [37] S. Janson, M. J. Luczak: A simple solution to the $k$-core problem. Random Structures Algorithms 30(1-2) (2007) 50–62.
  * [38] Y. Kabashima, D. Saad: Statistical mechanics of error correcting codes. Europhys. Lett. 45 (1999) 97–103.
  * [39] J. Kahn; J. Komloś, E. Szemerédi: On the probability that a random $\pm 1$-matrix is singular. Journal of the AMS 8 (1995) 223–240.
  * [40] J. H. Kim: Poisson cloning model for random graphs. International Congress of Mathematicians. Vol. III, Eur. Math. Soc., Zürich (2006) 873–897.
  * [41] V. Kolchin: Random graphs and systems of linear equations in finite fields. Random Structures and Algorithms 5 (1995) 425–436.
  * [42] V. Kolchin, V. Khokhlov: On the number of cycles in a random non-equiprobable graph. Discrete Math. Appl. 2 (1992) 109–118.
  * [43] V. Kolchin: Consistency of a system of random congruences. Discrete Math. Appl. 3 (1993) 103–113.
  * [44] J. Komlós: On the determinant of (0,1) matrices. Studia Sci. Math. Hungar. 2 (1967) 7–21.
  * [45] I. Kovalenko: On the limit distribution of the number of solutions of a random system of linear equations in the class of Boolean functions. Theory Probab. Appl. 12 (1967) 51–61.
  * [46] I. Kovalenko, A. Levitskaya, M. Savchuk: Selected problems of probabilistic combinatorics. Naukova Dumka, Kiev (1986).
  * [47] S. Kumar, A. Young, N. Macris, H. Pfister: Threshold saturation for spatially-coupled LDPC and LDGM Codes on BMS channels. IEEE Transactions on Information Theory 60 (2014) 7389–7415
  * [48] M. Lelarge: Bypassing correlation decay for matchings with an application to XORSAT. Proc. IEEE Information Theory Workshop (2013) 1–5.
  * [49] M. Lelarge, M. Oulamara: Replica bounds by combinatorial interpolation for diluted spin systems. Journal of Statistical Physics (2018) 1–24.
  * [50] T. Luczak: Size and connectivity of the k-core of a random graph. Discrete Math., 91(1) (1991) 61–68.
  * [51] T. Luczak: Sparse random graphs with a given degree sequence. Random graphs, Vol. 2 (Poznań, 1989), Wiley-Intersci. Publ. Wiley, New York, (1992) 165–182.
  * [52] C. Méasson, A. Montanari, R. Urbanke: Maxwell’s constructions: the hidden bridge between maximum-likelihood and iterative decoding. IEEE Transactions on Information Theory 54 (2008) 5277–5307.
  * [53] M. Mézard, A. Montanari: Information, physics and computation. Oxford University Press 2009.
  * [54] M. Mézard, F. Ricci-Tersenghi, R. Zecchina: Two solutions to diluted $p$-spin models and XORSAT problems. Journal of Statistical Physics 111 (2003) 505–533.
  * [55] G. Miller, G. Cohen: The rate of regular LDPC codes. IEEE Transactions on Information Theory 49 (2003) 2989–2992.
  * [56] M. Molloy: Cores in random hypergraphs and Boolean formulas. Random Structures and Algorithms 27 (2005) 124–135.
  * [57] A. Montanari: Tight bounds for LDPC and LDGM codes under MAP decoding. IEEE Transactions on Information Theory 51 (2005) 3221-3246.
  * [58] D. Panchenko: Spin glass models from the point of view of spin distributions. Annals of Probability 41 (2013) 1315–1361.
  * [59] B. Pittel, J. Spencer, N. Wormald: Sudden emergence of a giant $k$-core in a random graph. J. Combin. Theory Ser. B, 67(1) (1996) 111–151.
  * [60] B. Pittel, G. Sorkin: The satisfiability threshold for $k$-XORSAT. Combinatorics, Probability and Computing 25 (2016) 236–268.
  * [61] T. Richardson, R. Urbanke: Modern coding theory. Cambridge University Press (2008).
  * [62] O. Riordan: The $k$-core and branching processes. Combin. Probab. Comput.17(1) (2008) 111–136.
  * [63] T. Tao, V. Vu: On the singularity probability of random Bernoulli matrices. Journal of the AMS 20 (2007) 603–628.
  * [64] L. Zdeborová, F. Krzakala: Statistical physics of inference: thresholds and algorithms. Advances in Physics 65 (2016) 453–552.

##  Appendix A Proof of Lemma 1.10

Since $\mathbb{E}[\boldsymbol{\lambda}^{r}]<\infty$, the event
$\mathcal{M}=\left\\{{\max_{i\in[s]}\boldsymbol{\lambda}_{i}\leq
n/\ln^{9}n}\right\\}$ has probability

$\displaystyle{\mathbb{P}}\left[{\mathcal{M}}\right]=1-o(1/n).$ (A.1)

Moreover, fixing a small enough $\eta=\eta(\delta)>0$ and a large enough
$L=L(\eta)>0$ and setting
$Q_{j}=\sum_{i\in[s]}\boldsymbol{1}\\{\lambda_{i}=j\\}$, we obtain from the
Chernoff bound that ${\mathbb{P}}\left[{\forall j\leq
L:|Q_{j}-s{\mathbb{P}}\left[{\boldsymbol{\lambda}=j}\right]|>\sqrt{n}\ln
n}\right]=o(1/n)$. Hence, by Bayes’ rule,

$\displaystyle{\mathbb{P}}\left[{\exists j\leq
L:|Q_{j}-s{\mathbb{P}}\left[{\boldsymbol{\lambda}=j}\right]|>\sqrt{n}\ln
n\mid\mathcal{M}}\right]$ $\displaystyle=o(1/n).$ (A.2)

In addition, let ${\mathcal{H}}=\left\\{{h\in\mathbb{N}:(1+\eta)^{h-1}L\leq
n/\ln^{9}n}\right\\}$ and for $h\in{\mathcal{H}}$ let

$\displaystyle R_{h}$ $\displaystyle=\sum_{j\geq
1}Q_{j}\boldsymbol{1}\\{L(1+\eta)^{h-1}<j\leq L(1+\eta)^{h}\wedge
n/\ln^{9}n\\},$ $\displaystyle\bar{R}_{h}$ $\displaystyle=s\sum_{j\geq
1}{\mathbb{P}}\left[{\boldsymbol{\lambda}=j}\right]\boldsymbol{1}\\{L(1+\eta)^{h-1}<j\leq
L(1+\eta)^{h}\wedge n/\ln^{9}n\\}.$

Then the Chernoff bound and Bayes’ rule yield

$\displaystyle{\mathbb{P}}\left[{\exists
h\in{\mathcal{H}}:\left|{R_{h}-\bar{R}_{h}}\right|>\eta\bar{R}_{h}+\ln^{2}n\mid\mathcal{M}}\right]$
$\displaystyle=o(1/n).$ (A.3)

Finally, given $\mathcal{M}$ and
$|Q_{j}-s{\mathbb{P}}\left[{\boldsymbol{\lambda}=j}\right]|\leq\sqrt{n}\ln n$
for all $j\leq L$ and
$\left|{R_{h}-\bar{R}_{h}}\right|\leq\eta\bar{R}_{h}+\ln^{2}n$ for all
$h\in{\mathcal{H}}$, we obtain

$\displaystyle\frac{1}{s}\sum_{i=1}^{s}\boldsymbol{\lambda}_{i}$
$\displaystyle\leq\sum_{j=1}jQ_{j}/s+\sum_{h\in{\mathcal{H}}}(1+\eta)^{h}LR_{h}/s=o(1)+\mathbb{E}\left[{\boldsymbol{\lambda}\boldsymbol{1}\\{\boldsymbol{\lambda}\leq
L\\}}\right]+\sum_{h\in{\mathcal{H}}}(1+\eta)^{h+1}(\bar{R}_{h}+(\ln^{2}n))/s\leq\mathbb{E}\left[{\boldsymbol{\lambda}\boldsymbol{1}}\right]+\delta/2+o(1).$

Similarly,
$\frac{1}{s}\sum_{i=1}^{s}\boldsymbol{\lambda}_{i}\geq\mathbb{E}\left[{\boldsymbol{\lambda}\boldsymbol{1}}\right]-\delta/2+o(1)$.
Thus, the assertion follows from (A.1)–(A.3)

##  Appendix B Proof of Lemma 2.3

For $t=1,\ldots,\boldsymbol{\theta}$ let $S_{0}(t),\ldots,S_{\ell(t)}(t)$ be
the decomposition of $[n]$ obtained by applying Lemma 2.2 to the matrix
$A[\boldsymbol{i}_{1},\ldots,\boldsymbol{i}_{t}]$. Further, let
$R_{h}(t)=S_{h}(t)\cap U$ for all $t$. We proceed in two steps. First we
establish a deterministic statement:

if $\sum_{h\geq 1}|R_{h}(t)|^{2}<\varepsilon|U|^{2}$, then
$\mu_{\hat{A},U}\mbox{ is $\varepsilon$-symmetric}$. (B.1)

Indeed, using (i) and (iii) from Lemma 2.2, we obtain

$\displaystyle\sum_{u,v\in
U}d_{\mathrm{TV}}(\mu_{\hat{A},u,v},\mu_{\hat{A},u}\otimes\mu_{\hat{A},v})$
$\displaystyle=\sum_{h=1}^{\ell(t)}\sum_{u,v\in
R_{h}(t)}d_{\mathrm{TV}}(\mu_{\hat{A},u,v},\mu_{\hat{A},u}\otimes\mu_{\hat{A},v})\leq\sum_{h=1}^{\ell(t)}|R_{h}(t)|^{2},$

whence (B.1) follows.

Second, we claim that for large enough $\Theta=\Theta(\varepsilon)$,

$\displaystyle\mathbb{E}\sum_{h\geq
1}|R_{h}(\boldsymbol{\theta})|^{2}<\varepsilon^{3}|U|^{2}.$ (B.2)

To see this, consider the random variables
$\Delta_{t}=|R_{0}(t)|-|R_{0}(t-1)|$ for $t\in[\Theta]$. Since
$S_{0}(t-1)\subseteq S_{0}(t)$, these random variables are non-negative.
Moreover, we claim that

$\displaystyle\sum_{t\in[\Theta]}\Delta_{t}$ $\displaystyle\leq|U|,$
$\displaystyle\mathbb{E}[\Delta_{t}\mid\boldsymbol{i}_{1},\ldots,\boldsymbol{i}_{t-1}]$
$\displaystyle\geq\sum_{h\geq 1}|R_{h}(t-1)|^{2}/|U|.$ (B.3)

The first inequality is self-evident. To obtain the second, we deduce from
Lemma 2.2 (ii) that freezing any variable in class $R_{h}(t-1)$ freezes the
entire class. In other words, if $\boldsymbol{i}_{t}\in R_{h}(t-1)$, then
$R_{h}(t-1)\subseteq R_{0}(t)$. Since $\boldsymbol{i}_{t}$ is chosen uniformly
at random, we obtain the second inequality. Combining the two inequalities
from (B.3), we find

$\displaystyle\mathbb{E}\left[{\sum_{h\geq
1}|R_{h}(\boldsymbol{\theta})|^{2}}\right]$
$\displaystyle=\frac{1}{\Theta}\sum_{t=1}^{\Theta}\mathbb{E}\left[{\sum_{h\geq
1}|R_{h}(t)|^{2}}\right]\leq\frac{|U|^{2}}{\Theta}+\frac{1}{\Theta}\sum_{t=1}^{\Theta}\mathbb{E}\left[{\sum_{h\geq
2}|R_{h}(t-1)|^{2}}\right]\leq\frac{|U|^{2}}{\Theta}+\frac{|U|}{\Theta}\mathbb{E}\left[{\sum_{t=1}^{\Theta}\Delta_{t}}\right]\leq\frac{2|U|^{2}}{\Theta},$

whence (B.2) follows. Finally, the assertion follows from (B.1) and (B.2).