# Upper bounds on the $2$-colorability threshold of random $d$-regular
$k$-uniform hypergraphs for $k\geq 3$

Evan Chang , Neel Kolhe , Youngtak Sohn High Technology High School. Email:
<EMAIL_ADDRESS>High School. Email<EMAIL_ADDRESS>of
Mathematics, Massachusetts Institute of Technology. Email<EMAIL_ADDRESS>
(July 13, 2023)

###### Abstract

For a large class of random constraint satisfaction problems (csp), deep but
non-rigorous theory from statistical physics predict the location of the sharp
satisfiability transition. The works of Ding, Sly, Sun (2014, 2016) and Coja-
Oghlan, Panagiotou (2014) established the satisfiability threshold for random
regular $k$-nae-sat, random $k$-sat, and random regular $k$-sat for large
enough $k\geq k_{0}$ where $k_{0}$ is a large non-explicit constant.
Establishing the same for small values of $k\geq 3$ remains an important open
problem in the study of random csps.

In this work, we study two closely related models of random csps, namely the
$2$-coloring on random $d$-regular $k$-uniform hypergraphs and the random
$d$-regular $k$-nae-sat model. For every $k\geq 3$, we prove that there is an
explicit $d_{\star}(k)$ which gives a satisfiability upper bound for both of
the models. Our upper bound $d_{\star}(k)$ for $k\geq 3$ matches the
prediction from statistical physics for the hypergraph $2$-coloring by
Dall’Asta, Ramezanpour, Zecchina (2008), thus conjectured to be sharp.
Moreover, $d_{\star}(k)$ coincides with the satisfiability threshold of random
regular $k$-nae-sat for large enough $k\geq k_{0}$ by Ding, Sly, Sun (2014).

##  1 Introduction

In this work, we study the $2$-coloring on random $d$-regular $k$-uniform
hypergraphs and the random $d$-regular $k$-nae-sat model for $k\geq 3$. We
establish an explicit well-defined upper bound on the
satisfiability/colorability threshold that holds for every $k\geq 3$, which is
conjectured to be sharp in statistical physics [DRZ08] for hypergraph
$2$-coloring, and matches the previous rigorous results for random regular
$k$-nae-sat model for $k$ large enough [DSS14].

Given a $k$-uniform hypergraph with $n$ nodes and $m$ hyperedges, where every
edge consists of $k$ nodes, a hypergraph $2$-coloring is an assignment of
colors from $\\{\sf{red},\sf{blue}\\}\equiv\\{0,1\\}$ to the nodes such that
there is no monochromatic hyperedge. If there is such a $2$-coloring, the
hypergraph is said to be colorable or satisfiable. It is a typical example of
a constraint satisfaction problem (csp) that has been studied extensively in
combinatorics and computer science literature [Sey74, AB88, AM02, COZ12,
DFG15, HY13, HY18].

A $k$-nae-sat problem is another closely related csp studied in computer
science [COP12, DSS14, SSZ16, NSS22, SS23], which can be viewed as a variant
of the infamous $k$-sat problem [Kar72]. A $k$-sat formula is a boolean cnf
formula with $n$ variables formed by taking the and of $m$ clauses, which is
the or of $k$ variables or their negations. Then, a nae-sat solution
$\underline{x}\in\\{0,1\\}^{n}$ is an assignment such that $\underline{x}$ and
its negation $\neg\underline{x}$ evaluates $\sf{true}$ in the formula. Thus,
viewing each clause as an hyperedge, if no variable is negated in every
clauses, then a nae-sat solution is equivalent to a hypergraph $2$-coloring.

A significant direction of research on satisfiability has involved examining
the large-system limit of randomly generated problem instances. The study of
random constraint satisfaction problems (rcsps) aims to discern typical
behaviors and phase transitions in these systems as the number of variables
$n$ and the number of constraints $m$ tends to infinity with a fixed ratio
$\alpha\equiv\frac{m}{n}$. In this sparse regime, there has been considerable
effort into identifying the satisfiability transition, or the critical
density, denoted by $\alpha_{\sf sat}$, beyond which solutions cease to exist
[AP04, ANP05, AM06, COV13].

Many of the sparse rcsps belong to a broad universality class called the one-
step-replica-symmetry-breaking (1rsb) class from statistical physics [KMRT+07]
(see Chapter 19 of [MM09] for a survey) - including $2$-coloring on random
regular $k$-uniform hypergraphs, random regular $k$-nae-sat, and random
$k$-sat for $k\geq 3$. The 1rsb class refers to rcsp which is predicted to
possess a single layer of hierarchy of well-separated clusters, where a
cluster roughly refers to a dense region of the solution space. A shared
characteristic of these problems is that in a non-trivial regime below
$\alpha_{\sf sat}\equiv\alpha_{\sf sat}(k)$, the number of solutions fails to
concentrate about its mean due to the clustering effect. This effect thus
prevents standard first and second moment methods from locating the exact
transition, presenting a significant mathematical challenge.

Despite such difficulties, breakthroughs were made to successfully locate the
satisfiability threshold of the random regular $k$-nae-sat [DSS16b], the
random $k$-SAT [DSS22], and random regular $k$-SAT [COP16] for large enough
$k\geq k_{0}$, where $k_{0}$ is a non-explicit large absolute constant. These
works carried out a demanding second moment method to the number of clusters
instead of the number of solutions based on intuitions from statistical
physics [MPZ02] and previous mathematical works [AP04, COP13, COP16]. See
Section 1.1 for further literature.

However, for small values of $k\geq 3$, locating the satisfiability threshold
for rcsps in the 1rsb class remains an important open problem. Indeed, for all
the aforementioned models in 1rsb class, the physicists conjecture an explicit
value $\alpha_{\star}(k)$ for $\alpha_{\sf sat}(k)$, the 1rsb threshold, which
is expected to be correct for all $k\geq 3$ [MMZ06, MPZ02, DRZ08]. The methods
of [DSS16b, DSS22, COP16] crucially uses the fact that $k$ is large enough for
their second moment method to succeed.

In this work, we consider $2$-coloring on random $d$-regular $k$-uniform
hypergraphs, where the random hypergraph is generated uniformly at random from
the set of $k$-uniform hypergraphs such that every variable participates in
exactly $d$ hyperedges. We also consider random $d$-regular nae-sat, where
$k$-sat formula is generated uniformly at random with the condition that every
variable participates in exactly $d$ clauses. We establish an upper bound
$d_{\star}(k)$ on the satisfiability thresholds for these problems for every
$k\geq 3$, which is sharp [DSS14] for random regular $k$-nae-sat for large
$k\geq k_{0}$ and conjectured to be sharp [DRZ08] for $k\geq 3$ for hypergraph
$2$-coloring.

######  Theorem 1.1.

For $k\geq 3$ and $d_{\textnormal{lbd}}(k)\leq d\leq d_{\textnormal{ubd}}(k)$,
where $d_{\textnormal{lbd}}(k),d_{\textnormal{ubd}}(k)$ are defined in (1.4)
below, there exists a unique solution $x\equiv x(k,d)$ to the equation

$d=1+\left(\log\frac{1-2x}{1-x}\right)/\log\left(\frac{1-2x^{k-1}}{1-x^{k-1}}\right)\quad\textnormal{on
the interval}\quad\frac{1}{2}-\frac{1}{2^{k}}\leq x\leq\frac{1}{2}.$ (1.1)

Define $d_{\star}(k)$ by the largest zero of the explicit function

$\boldsymbol{\prescript{\star}{}{\Phi}}(d):=-\log(1-x)-d(1-k^{-1}-d^{-1})\log(1-2x^{k})+(d-1)\log(1-x^{k-1})\,,$
(1.2)

where the existence of the root of $\boldsymbol{\prescript{\star}{}{\Phi}}(d)$
is guaranteed in the interval
$[d_{\textnormal{lbd}}(k),d_{\textnormal{ubd}}(k)]$.

Then, for $k\geq 3$, and $d>d_{\star}(k)$, the random $d$-regular $k$-uniform
hypergraph is not $2$-colorable with probability tending to one as the graph
size $n\to\infty$. Similarly for $k\geq 3$ and $d>d_{\star}(k)$, then the
random $d$-regular $k$-nae-sat instance is not satisfiable with probability
tending to one as $n\to\infty$.

A matching lower bound was obtained in [DSS14] for large enough $k\geq k_{0}$
in random $d$-regular nae-sat by a demanding second moment method. Our proof
is based on an interpolation method from statistical physics [FL03, Gue03,
PT04]. We give a proof outline in Section 1.2.

We emphasize that for any $k\geq 3$, determining the colorability threshold
for $2$-coloring on random $d$-regular $k$-uniform hyprgraphs was previously
open, thus Theorem 1.1 for $2$-coloring is novel even for large $k$. Although
it is expected that the colorability threshold for the model matches the
satisfiability threshold for random regular $k$-nae-sat, it is highly non-
trivial to modify the proof techniques for random regular nae-sat [DSS16b] to
the $2$-coloring model since many of the arguments in [DSS16b] crucially takes
advantage of the randomness of clauses. For example, any
$\underline{x}\in\\{0,1\\}^{n}$ has the same probability of being a nae-sat
solution by the randomness of the clauses while this is obviously not true for
the $2$-coloring model. As we see below, even the calculation of the first
moment of the solutions is substantially more involved for the $2$-coloring
model. Let $Z_{\textsc{nae}}$ be the number of solutions of random $d$-regular
$k$-nae-sat, then it is trivial to calculate $\mathbb{E}Z_{\textsc{nae}}$
exactly by taking advantage of the randomness of the clauses:

$\mathbb{E}Z_{\textsc{nae}}=2^{n}(1-2^{-k+1})^{m}=\exp\Big{(}n\Big{(}\log
2+\alpha\log\big{(}1-2^{-k+1}\big{)}\Big{)}\Big{)}=:\exp\big{(}n\Phi_{k}(\alpha)\big{)}\,.$
(1.3)

On the other hand, if we denote $Z_{\textsc{col}}$ by the number of
$2$-colorings on random $d$-regular $k$-uniform graphs, then estimating
$\mathbb{E}Z_{\textsc{col}}$ is more delicate: we appeal to the idea of
exponential tilting from large deviations theory [DZ10] and local central
limit theorem [Bor17] to prove that $\mathbb{E}Z_{\textsc{col}}$ is of the
same order as $\exp\big{(}n\Phi_{k}(\alpha)\big{)}$ in Lemma 1.8 below. Using
the interpolation bound which is simpler than moment calculations, we clarify
a simple mechanism (cf. Lemma 2.3) behind the identical satisfiability upper
bounds for both models.

The solution $x(k,d)$ to the equation (1.1) has a mathematical interpretation.
Namely, $2x(k,d)$ is the fraction of the so-called frozen variables in the
cluster model. The solution $x(k,d)$ is called the Belief Propagation(bp)
fixed point for the cluster model in statistical physics. We emphasize that
addressing the uniqueness of the bp fixed point is a well-known major obstacle
for many combinatorial optimization and statistical inference problems that
exhibit sharp phase transitions (e.g. for spherical perceptron model [ST03];
see [Tal10, Chapter 3] for a further discussion). We establish the uniqueness
of the bp fixed point by showing that the Belief Propagation recursion (cf.
(1.12)) is a contraction for $k\geq 3$ and
$[d_{\textnormal{lbd}}(k),d_{\textnormal{ubd}}(k)]$, which might be also
useful in obtaining a matching lower bound to Theorem 1.1.

k | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15
---|---|---|---|---|---|---|---|---|---|---|---|---|---
$\lceil d_{\star}(k)\rceil$ | 7 | 20 | 53 | 130 | 307 | 705 | 1592 | 3543 | 7802 | 17028 | 36902 | 79488 | 170340
$\lceil d_{1}(k)\rceil$ | 8 | 21 | 54 | 131 | 309 | 708 | 1594 | 3546 | 7804 | 17031 | 36905 | 79491 | 170343
Table 1:  A comparison with the upper bound $d_{\star}(k)$ in Theorem 1.1 with
the first moment threshold $d_{1}(k):=\frac{k\log
2}{-\log\left(1-2^{-k+1}\right)}$ for small values of $k$. For $3\leq k\leq
10$, the values also appear in Table 1 of [DRZ08].

Since $\mathbb{E}Z_{\textsc{nae}}$ and $\mathbb{E}Z_{\textsc{col}}$ are given
by $\exp\big{(}n\Phi_{k}(\alpha)\big{)}$ up to a constant (cf. (1.3) and Lemma
1.8), the first moment thresholds for both of the models are given by
$d_{1}(k):=\frac{k\log 2}{-\log\left(1-2^{-k+1}\right)}$. In Table 1, we
report $\lceil d_{\star}(k)\rceil$ and $\lceil d_{1}(k)\rceil$ for $3\leq
k\leq 15$. For every $3\leq k\leq 15$, the upper bound $\lceil
d_{\star}(k)\rceil$ in Theorem 1.1 improves over the first moment threshold.
For large values of $k$, $d_{\star}(k)$ improves over $d_{1}(k)$ by
$\Omega(k)$ (see (1.5) below). The quantities $d_{\textnormal{lbd}}(k),$ and
$d_{\textnormal{ubd}}(k)$ are defined by

$d_{\textnormal{lbd}}(k)=\begin{cases}6.74&k=3\,,\\\ 16.7&k=4\,,\\\
(2^{k-1}-2)k\log 2&k\geq 5\,.\end{cases}\quad\quad\quad
d_{\textnormal{ubd}}(k)=\begin{cases}7.5&k=3\,,\\\ 2^{k-1}k\log 2&k\geq
4\,.\end{cases}$ (1.4)

######  Remark 1.2.

For $d\leq d_{\textnormal{lbd}}(k)$ and large $k\geq k_{0}$, the second moment
method applied to $Z_{\textsc{nae}}$ succeeds in showing the satisfiability
for the random $d$-regular $k$-nae-sat model (see [DSS14, Section 2.1]). For
$k\in\\{3,4\\}$, $d_{\textnormal{lbd}}(k)$ must be adjusted to be higher to
guarantee that $\boldsymbol{\prescript{\star}{}{\Phi}}(d)$ is well-defined,
i.e. there exists a unique solution to (1.1). The value
$d_{\textnormal{ubd}}(k)\equiv 2^{k-1}k\log 2>d_{1}(k)$ for $k\geq 4$ is a
convenient upper bound for satisfiability. For $k=3$, we take
$d_{\textnormal{ubd}}(3)$ to be $7.5>\frac{3\log 2}{-\log(3/4)}=d_{1}(3)$,
which does not change $d_{\star}(3)$, but is more convenient for the proof.

Finally, we note that the large $k$ asymptotics of $d_{\star}(k)$ was proven
in [SSZ22, Appendix B]:

$\alpha_{\star}(k)\equiv\frac{d_{\star}(k)}{k}=\left(2^{k-1}-\frac{1}{2}-\frac{1}{4\log
2}\right)\log 2+o_{k}(1)\,,$ (1.5)

where $o_{k}(1)$ denotes an error tending to zero as $k\to\infty$. Since
$d_{1}(k)=(2^{k-1}-1/2)k\log 2+o_{k}(1)$, we have that $d_{\star}(k)\leq
d_{1}(k)-\Omega(k)$.

###  1.1 Related work

Many of the earlier mathematical works on rcsps focused on determining their
satisfiability thresholds and verifying the sharpness of sat-unsat
transitions. For models that are known not to exhibit rsb, such goals were
established. These models include random 2-sat [CR92, BBC+01], random
1-in-$k$-sat [ACIM01], $k$-xor-sat [DM02, DGM+10, PS16], and random linear
equations [ACOGM20]. On the other hand, for the models which are predicted to
belong to 1rsb class, intensive studies have been conducted to estimate their
satisfiability threshold, as shown in [KKKS98, AP04, COP16] (random $k$-sat),
[AM06, COZ12, COP12] (random $k$-nae-sat), and [AN05, CO13, COV13, COEH16]
(random graph coloring).

More recently, the satisfiability thresholds for rcsps that exhibits rsb have
been rigorously determined for several models, namely the random regular
$k$-nae-sat [DSS16b], maximum independent set on $d$-regular graphs [DSS16a],
random regular $k$-sat [COP16] and random $k$-sat [DSS22] for large $k$ and
$d$. Although determining the location of $q$-colorability threshold for the
sparse Erdos Renyi graph is left open, the condensation threshold $\alpha_{\sf
cond}$ for random graph coloring, where the free energy becomes non-analytic,
was settled in [BCOH+16]. They carried out a technically challenging analysis
based on a clever “planting” technique, where the results were further
generalized to other models in [COKPZ18]. Similarly, [BCO16] identified the
condensation threshold for random regular $k$-sat, where each variable appears
$d/2$-times positive and $d/2$-times negative. Further, in the condensation
regime $\alpha\in(\alpha_{\sf cond},\alpha_{\sf sat})$, many quantities of
interest was established for random regular $k$-nae-sat with large enough $k$,
matching the statistical physics prediction. Namely, the number of solutions
at exponential scale (free energy) [SSZ22], the concentration of the overlap
[NSS20, NSS21], and the local weak limit [SS23] were established. Establishing
the same quantities for other models in the condensation regime is left open.

The closest result to ours in the literature is by Ayre, Coja-Oghlan, and
Greenhill [ACOG22], where they lower bound the chromatic number (or
equivalently, upper bound the colorability threshold) of the random regular
graph of any degree, which is conjectured to be tight. [ACOG22] also considers
the sparse Erdos Renyi graph, which is more complicated since the conjectured
chromatic number is defined in terms of a distributional (rather than real-
valued) optimization due to the randomness of the local neighborhoods. In this
work, we do not consider Erdos Renyi type problems, but we additionally
address the question of the uniqueness of the bp fixed point for any $k\geq 3$
(unique solution to the equation (1.1)). As in [ACOG22], we use an
interpolation bound, which gives an upper bound of the satisfiability
threshold also for the (non-regular) random $k$-nae-sat model. It would be
interesting to address the uniqueness of the bp fixed point for random
$k$-nae-sat and random $k$-sat for small $k\geq 3$. We refer to [ST03, MRSY19,
YP22, GP23] which addresses the uniqueness of bp fixed point for various
models.

###  1.2 Proof methods

We aim to rigorously establish the upper bound the satisfiability threshold
predicted by the so-called ‘1rsb cavity method’ from statistical physics
[DRZ08]. To do so, instead of using moment methods, we use a technique called
‘interpolation method’ from the theory of spin glasses developed by [FL03,
Gue03, PT04]. The interpolation method has been successful in upperbounding
the satisfiability threshold for random $k$-sat [DSS15] for large $k$, the
free energy for random regular $k$-nae-sat [SSZ16], and the colorability
threshold for random graphs [ACOG22].

We first introduce the notations and mathematical framework that we use
throughout the paper. For both the $d$-regular $k$-uniform hypergraphs and the
$k$-nae-sat formula, we can represent them as (labelled) $(d,k)$-regular
bipartite graph. Let $V=\\{v_{1},\ldots,v_{n}\\}$ be the set of variables or
nodes and $F=\\{a_{1},\ldots,a_{m}\\}$ be the set of clauses or hyperedges. An
edge is formed if the variable or node $v_{i}$ is included in the clause or
hyperedge $a_{j}$. For an edge $e$, we denote $v(e)$ (resp. $a(e)$) by the
variable (resp. clause) adjacent to it.

Denote $G=(V,F,E)$ by the resulting bipartite graph. We denote the
neighborhood of $v\in V$ (resp. $a\in F$) by $\delta v:=\\{a\in F:(av)\in
E\\}$ (resp. $\delta a:=\\{v\in V:(av)\in E\\}$). Throughout, we denote
$\alpha\equiv\frac{m}{n}=\frac{d}{k}$. For the nae-sat formula, there is an
extra label for each edge $e\in E$, namely the literal
$\texttt{L}_{e}\in\\{0,1\\}$, which specifies how the variable $v(e)$
participates in the clause $a(e)$. Then, the labelled graph
$\mathcal{G}=(V,F,E,\underline{\texttt{L}})\equiv(V,F,E,(\texttt{L}_{e})_{e\in
E})$ represents a nae-sat instance.

######  Definition 1.3.

Given a nae-sat instance $\mathcal{G}=(V,F,E,\underline{\texttt{L}})$,
$\underline{x}\in\\{0,1\\}^{V}$ is a (nae-sat) solution if

$\prod_{a\in F}\varphi((x_{v(e)}\oplus\texttt{L}_{e})_{e\in\delta a})=1\,,$

where for $\underline{z}=(z_{i})_{i\leq k}\in\\{0,1\\}^{k}$,
$\varphi(\underline{z})\equiv\mathds{1}(z_{1}=\ldots=z_{k})$, and $\oplus$
denotes addition mod $2$. Given a graph $G=(V,F,E)$,
$\underline{x}\in\\{0,1\\}^{V}$ is a (hypergraph $2$-) coloring if
$\underline{x}$ is a nae-sat solution on $G$ with literals identically zero
$(G,\underline{0})$.

The configuration model can be described as follows. Add $d$ (resp. $k$) half-
edges adjacent to each variable (resp. each clause) so that there are total
$nd=mk$ number of half-edges adjacent to variables (resp. clauses). Thus, $E$
can be regarded as the perfect matching between to the set of half-edges
adjacent to variables to those adjacent to clauses, and hence a permutation in
$S_{nd}$. Then, the configuration model $\boldsymbol{G}=(V,F,\boldsymbol{E})$
is defined by taking $\boldsymbol{E}\sim\textnormal{Unif}(S_{nd})$. For a
random $d$-regular $k$-nae-sat instance
$\boldsymbol{\mathcal{G}}=(\boldsymbol{G},\underline{\textbf{L}})$, we take
the literals $\underline{\textbf{L}}\equiv(\textbf{L}_{e})_{e\in
E}\stackrel{{\scriptstyle i.i.d.}}{{\sim}}\textnormal{Unif}(\\{0,1\\})$.

Note that the configuration model $\boldsymbol{G}$ may induce multi-edges.
However, if we denote $\mathscr{S}$ to be the event that $\boldsymbol{G}$ is
simple, then it is well-known that
$\mathbb{P}(\boldsymbol{G}\in\mathscr{S})=\Omega(1)$ (see e.g. Chapter 9 of
[JLR00]). Thus, the configuration model is mutually contiguous with respect to
the uniform distribution among all $(d,k)$-regular graphs, so to prove Theorem
1.1, it suffices to work with the configuration model.

In order to use the interpolation method, we consider the positive temperature
analogs of the $2$-coloring or the nae-sat model, which have more desirable
properties due to the softness of the constraints - e.g. the concentration of
the free energy as seen in Lemma 1.4 below. We introduce notations that allow
us to set up the positive temperature models. Let $S$ be a finite set and
$\underline{b}\equiv(b_{s})_{s\in S}$ be a vector with $b_{s}\geq 0$. Also,
let $\mathcal{X}$ be a finite set encoding the spins and denote
$\mathfrak{F}(\mathcal{X})$ by the set of functions
$\mathcal{X}\to\mathbb{R}_{\geq 0}$. Let $f:S\to\mathfrak{F}(\mathcal{X})$ be
a random function, i.e. $f(\cdot;s)\in\mathfrak{F}(\mathcal{X})$ is random for
$s\in S$, and $f_{1},\ldots,f_{k}$ be i.i.d. copies of $f$. Then, define the
random function $\theta:\mathcal{X}^{k}\to\mathbb{R}$ by letting for
$\underline{x}=(x_{1},\ldots,x_{k})\in\mathcal{X}^{k}$,

$\theta(\underline{x})=\sum_{s\in S}b_{s}\prod_{i=1}^{k}f_{j}(x_{j};s)\,.$
(1.6)

We assume that there exists a constant $\varepsilon\in(0,1)$ such that for any
$\underline{x}\in\mathcal{X}^{k}$,

$\varepsilon\leq
1-\theta(\underline{x})\leq\varepsilon^{-1}\quad\textnormal{almost surely.}$
(1.7)

On a $(d,k)$-regular bipartite graph $G=(V,F,E)$, let $(\theta_{a})_{a\in F}$
be i.i.d. copies of the random function $\theta$, and define the (random)
Gibbs measure on $\mathcal{X}^{V}$ by

$\mu_{G}(\underline{x})\equiv\frac{1}{Z(G)}\prod_{a\in
F}\Big{(}1-\theta_{a}(\underline{x}_{\delta a})\Big{)}\,,$

where $Z(G)$ is the normalizing constant explicitly given by

$Z(G)\equiv\sum_{\underline{x}\in\mathcal{X}^{V}}\prod_{a\in
F}\Big{(}1-\theta_{a}(\underline{x}_{\delta a})\Big{)}\,.$ (1.8)

We note that the condition (1.7) on $\theta$ guarantees that the Gibbs measure
$\mu_{G}$ is ‘finite temperature’. In particular, if we define the free energy

$F_{n}\equiv\frac{1}{n}\mathbb{E}\log Z(\boldsymbol{G})\,,$ (1.9)

where $\boldsymbol{G}$ is drawn from the configuration model and $\mathbb{E}$
above is over the randomness of $\boldsymbol{G}$ and randomness of
$(\theta_{a})_{a\in F}$, we have the following concentration of the free
energy.

######  Lemma 1.4.

Assume that $\theta$ satisfies (1.7) with some constant $\varepsilon\in(0,1)$.
Then, for any $\delta>0$, there exists a constant which only depends on
$\varepsilon,\delta>0$ such that

$\mathbb{P}\left(\bigg{|}\frac{1}{n}\log
Z(\boldsymbol{G})-F_{n}\bigg{|}\geq\delta\right)\leq e^{-cn}\,.$

The concentration of free energy in Lemma 1.4 is standard in literature
[BCOH+16, COP19, ACOG22], and we provide the proof in Section 2 for
completeness.

######  Definition 1.5.

(Positive temperature models) For $\beta>0$, called the inverse temperature,
the positive temperature nae-sat model
$\theta_{\textsc{nae}}(\cdot)\equiv\theta_{\textsc{nae}}(\cdot\,;\,\beta)$ is
defined as follows. Let $\underline{\texttt{L}}\equiv(\texttt{L}_{i})_{i\leq
k}\stackrel{{\scriptstyle i.i.d.}}{{\sim}}\textnormal{Unif}(\\{0,1\\})$ be a
sequence of i.i.d. Bernoulli(1/2) random variables. Then for
$\underline{x}=(x_{i})_{i\leq k}\in\\{0,1\\}^{k}$, define

$\theta_{\textsc{nae}}(\underline{x})\equiv\theta_{\textsc{nae}}(\underline{x};\beta)\equiv(1-e^{-\beta})\cdot\left(\prod_{i=1}^{k}(\texttt{L}_{i}\oplus
x_{i})+\prod_{i=1}^{k}(\texttt{L}_{i}\oplus x_{i}\oplus 1)\right)\,.$ (1.10)

That is, in the general form (1.6), we take $S=\mathcal{X}=\\{0,1\\}$,
$b_{i}\equiv 1-e^{-\beta}$, and $f(x;0)\equiv
1-f(x;1)\equiv\mathds{1}(x\oplus\texttt{L})$ for
$\texttt{L}\sim\textnormal{Unif}(\\{0,1\\})$. Moreover, the positive
temperature hypergraph $2$-coloring model
$\theta_{\textsc{col}}(\cdot)\equiv\theta_{\textsc{col}}(\cdot\,;\,\beta)$ is
defined by taking $\texttt{L}_{i}\equiv 0$ above:

$\theta_{\textsc{col}}(\underline{x})\equiv\theta_{\textsc{col}}(\underline{x};\beta)\equiv(1-e^{-\beta})\cdot\sum_{s\in\\{0,1\\}}\prod_{i=1}^{k}\mathds{1}(x_{i}=s)\,,$
(1.11)

which is taking $f(x;s)=\mathds{1}(x=s)$ in (1.6).

We note that formally taking $\beta=\infty$ and
$\theta=\theta_{\textsc{col}}(\underline{x};\beta)$, the corresponding
partition function $Z(G)$ equals the number of $2$-coloring on $G$. A similar
statement holds for the nae-sat model.

By constructing a certain sequential coupling of the given factor graph
$(\boldsymbol{G},(\theta)_{a\in F})$ to a set of disjoint trees so that the
free energy is monotone at every step, the interpolation method [FL03, Gue03,
PT04] gives an upper bound on the free energy $F_{n}$ as follows: for
$\zeta\in\mathscr{P}\big{(}\mathscr{P}(\mathscr{P}(\mathcal{X}))\big{)}$,
where $\mathscr{P}(A)$ denotes the set of probability measures on $A$, and
$\lambda\in(0,1)$, there exists an explicit functional
$\mathcal{P}(\zeta,\lambda)\equiv\mathcal{P}_{d,k,\theta}(\zeta,\lambda)$ such
that we have
$F_{n}\leq\inf_{\zeta,\lambda}\mathcal{P}(\zeta,\lambda)+o_{n}(1)$. By taking
advantage of the interpolation method applied to positive temperature models
in Definition 1.5 and the concentration of the free energy in Lemma 1.4, we
prove the proposition below in Section 2.

######  Proposition 1.6.

For a given $k\geq 3$ and $d$, suppose that there is a solution
$x\in[1/2-1/2^{k},1/2]$ to the bp equation (1.1). Further, suppose that
$\boldsymbol{\prescript{\star}{}{\Phi}}(d)$ in (1.2) defined with such $x$
satisfies $\boldsymbol{\prescript{\star}{}{\Phi}}(d)<0$. Then, with
probability tending to one, no nae-sat solution exists on
$\boldsymbol{\mathcal{G}}$. Also, with probability tending to one, no
$2$-coloring exists on $\boldsymbol{G}$.

Moreover, we show that $d_{\star}(k)$ in Theorem 1.1 is well-defined and that
the assumptions of Proposition 1.6 are meaningful. Note that the bp equation
(1.1) is equivalent to $\Psi_{d}(x)=x$, where
$\Psi_{d}\equiv\Psi_{k,d}:[0,1]\to[0,1]$ is defined by
$\Psi_{d}\equiv\dot{\Psi}\circ\hat{\Psi}$ with

$\dot{\Psi}(x)\equiv\dot{\Psi}_{d}(x)\equiv\frac{1-x^{d-1}}{2-x^{d-1}}\,,\quad\quad\hat{\Psi}(x)\equiv\hat{\Psi}_{k}(x)\equiv\frac{1-2x^{k-1}}{1-x^{k-1}}\,.$
(1.12)

The function $\dot{\Psi}(\cdot)$ is variable bp recursion and
$\hat{\Psi}(\cdot)$ is clause bp recursion (see [DSS16b, Section 3.1] for the
motivation).

######  Proposition 1.7.

For $k\geq 3$ and $d\in[d_{\textnormal{lbd}}(k),d_{\textnormal{ubd}}(k)]$,
there exists a unique root to
$\Psi_{d}(x)\equiv(\dot{\Psi}\circ\hat{\Psi})(x)=x$ in the interval
$x\in[1/2-1/2^{k},1/2]$. Thus, $\boldsymbol{\prescript{\star}{}{\Phi}}(d)$ in
equation (1.2) is well-defined. Furthermore,
$d\to\boldsymbol{\prescript{\star}{}{\Phi}}(d)$ is continuous in the interval
$d\in[d_{\textnormal{lbd}}(k),d_{\textnormal{ubd}}(k)]$ with
$\boldsymbol{\prescript{\star}{}{\Phi}}(d_{\textnormal{lbd}}(k))>0$ and
$\boldsymbol{\prescript{\star}{}{\Phi}}(d_{\textnormal{ubd}}(k))<0$.

The proof of Proposition 1.7 is given in Section 3 for $k\geq 4$ and in
Section 4 for $k=3$, which requires extra numerical estimates. Finally, we
show that the first moment $\mathbb{E}Z_{\textsc{col}}$ of the number of
$2$-colorings on random $d$-regular $k$-uniform hypergraphs is the same with
$\mathbb{E}Z_{\textsc{nae}}$ up to a constant.

######  Lemma 1.8.

For $k\geq 3$, there exist constants $C_{k,d,i}$ for $i=1,2,$, which only
depends on $k,d$ such that
$\mathbb{E}Z_{\textsc{col}}/\mathbb{E}Z_{\textsc{nae}}\in[C_{k,d,1},C_{k,d,2}]$

###### Proof of Theorem 1.1.

By Proposition 1.7, the function $\boldsymbol{\prescript{\star}{}{\Phi}}(d)$
is well-defined and has a root in the interval
$[d_{\textnormal{lbd}}(k),d_{\textnormal{ubd}}(k)]$. Moreover, since
$\boldsymbol{\prescript{\star}{}{\Phi}}(d_{\textnormal{ubd}}(k))<0$ holds and
$\boldsymbol{\prescript{\star}{}{\Phi}}(\cdot)$ is continuous, we have
$\boldsymbol{\prescript{\star}{}{\Phi}}(d)<0$ for
$d\in(d_{\star}(k),d_{\textnormal{ubd}}(k)]$. Hence, Proposition 1.6 shows
that if $d\in(d_{\star}(k),d_{\textnormal{ubd}}(k)]$, then the $2$-coloring of
random $d$-regular $k$-uniform hypergraph and random $d$-regular $k$-nae-sat
is not satisfiable, both with probability tending to one as $n\to\infty$.
Further, since
$\mathbb{E}Z_{\textsc{col}}\asymp_{k,d}\mathbb{E}Z_{\textsc{nae}}=\exp\big{(}n\big{(}\log
2+\alpha\log\big{(}1-2^{-k+1}\big{)}\big{)}\big{)}$ by Lemma 1.8 and $\log
2+\alpha\log\big{(}1-2^{-k+1}\big{)}<0$ holds for $d>d_{\textnormal{ubd}}(k)$,
the same is true for $d>d_{\textnormal{ubd}}(k)$ by Markov’s inequality. ∎

##  2 Satisfiability upper bound by interpolation

In this section, we prove Lemma 1.4, Proposition 1.6, and Lemma 1.8. We prove
Proposition 1.6 in Section 2.1 based on the interpolation bound from
statistical physics [FL03, Gue03]. In Section 2.2, we prove Lemma 1.4 based on
Azuma Hoeffding’s inequality applied to the Doob martingale with respect to
clause revealing filtration. In Section 2.3, we prove Lemma 1.8 based on the
local central limit theorem.

###  2.1 Proof of Proposition 1.6

Throughout, we assume that we are given $k\geq 3$ and $d$ such that there is a
solution $x\in[1/2-1/2^{k},1/2]$ to the equation (1.1). We use the following
one-step-replica-symmetry-breaking bound proven in [SSZ22, Theorem E.3] for
random regular graphs, which is the analog of [PT04, Theorem 3] for Erdos
Renyi graphs.

######  Theorem 2.1.

(Theorem E.3 in [SSZ22]) Let $\mathcal{X}$ and $S$ be finite sets and consider
the partition function $Z(G)$ (cf. Eq. (1.8)), where $\theta$ in (1.6)
satisfies the condition (1.7) for some $\varepsilon>0$ and $b_{s}\geq 0$ holds
for $s\in S$. Let $\mathcal{M}_{0}\equiv\mathscr{P}(\mathcal{X})$ be the space
of probability measures over $\mathcal{X}$,
$\mathcal{M}_{1}\equiv\mathscr{P}(\mathcal{M}_{0})$ be the space of
probability measures over $\mathcal{M}_{0}$, and
$\mathcal{M}_{2}\equiv\mathscr{P}(\mathcal{M}_{1})$ be the space of
probability measures over $\mathcal{M}_{1}$. For $\zeta\in\mathcal{M}_{2}$,
let $\underline{\eta}=(\eta_{a,j})_{a\geq 0,j\geq 0}$ be an array of i.i.d.
samples from $\zeta$. For each index $(a,j)$ let
$\rho_{a,j}\in\mathscr{P}(\mathcal{X})$ be a conditionally independent sample
from $\eta_{a,j}$, and denote $\underline{\rho}=(\rho_{a,j})_{a\geq 0,j\geq
0}.$ For $x\in\mathcal{X}$ define random variables

$\begin{split}u_{a}(x)\equiv\sum_{\underline{x}\in\mathcal{X}^{k}}\mathds{1}\\{x_{1}=x\\}\big{(}1-\theta_{a}(\underline{x})\big{)}\prod_{j=2}^{k}\rho_{a,j}(x_{j})\,,\quad\quad
u_{a}\equiv\sum_{\underline{x}\in\mathcal{X}^{k}}\big{(}1-\theta_{a}(\underline{x})\big{)}\prod_{j=1}^{k}\rho_{a,j}(x_{j})\,,\end{split}$

where we recall that $(\theta_{a})_{a\geq 0}$ are i.i.d. copies of the random
function $\theta$. For any $\lambda\in(0,1)$ and any
$\zeta\in\mathcal{M}_{2}$,

$\begin{split}&F_{n}\leq\mathcal{P}(\zeta,\lambda)+O_{\varepsilon}(n^{-1/3})\,,\quad\textnormal{where}\\\
&\mathcal{P}(\zeta,\lambda)\equiv\mathcal{P}_{\theta}(\zeta,\lambda):=\lambda^{-1}\mathbb{E}\log\mathbb{E^{\prime}}\bigg{[}\Big{(}\sum_{x\in\mathcal{X}}\prod_{a=1}^{d}u_{a}(x)\Big{)}^{\lambda}\bigg{]}-(k-1)\alpha\lambda^{-1}\mathbb{E}\log\mathbb{E^{\prime}}\Big{[}\left(u_{0}\right)^{\lambda}\Big{]}\,.\end{split}$
(2.1)

Here, $F_{n}$ is the free energy for the configuration model defined in (1.9),
$\mathbb{E}^{\prime}$ denotes the expectation over $\underline{\rho}$
conditioned on all else, and $\mathbb{E}$ denotes the overall expectation.

######  Remark 2.2.

[SSZ22, Theorem E.3] is stated more general than Theorem 2.1 by considering
independent external field $\\{h_{v}\\}_{v\in V}$ and random $(b_{s})_{s\in
S}$. For our purposes, it suffices to consider non-random $b_{s}\geq 0$ and
$h_{v}\equiv 1$.

We use Theorem 2.1 for the positive temperature models in Definition 1.5. Note
that $\theta_{\textsc{nae}}(\cdot\,;\,\beta)$ and
$\theta_{\textsc{col}}(\cdot\,;\,\beta)$ satisfies the condition (1.7) with
$\varepsilon=e^{-\beta}$. Furthermore, in the bound (2.1), we take
$\lambda=\beta^{-1/2}$ and
$\zeta\equiv\zeta_{k,d,\beta}\in\mathscr{P}\Big{(}\mathscr{P}\big{(}\mathscr{P}(\\{0,1\\})\big{)}\Big{)}$
given by a point mass at $\eta_{k,d,\beta}$:

$\zeta_{k,d,\beta}\equiv\delta_{\eta_{k,d,\beta}}\,,$ (2.2)

where $\eta_{k,d,\beta}\in\mathscr{P}(\mathscr{P}(\\{0,1\\}))$ is defined as
follows. Identify $\mathscr{P}(\\{0,1\\})$ with $[0,1]$ by the map

$\rho\in\mathscr{P}(\\{0,1\\})\leftrightarrow\rho(1)\in[0,1]\,.$

Thus, viewing $\eta\equiv\eta_{k,d,\beta}\in\mathscr{P}([0,1])$, define

$\eta\left(\frac{e^{\beta}}{e^{\beta}+e^{-\beta}}\right)=\eta\left(\frac{e^{-\beta}}{e^{\beta}+e^{-\beta}}\right)=x\,,\quad\eta\left(\frac{1}{2}\right)=1-2x\,,$
(2.3)

where $x\equiv x(k,d)$ is the bp fixed point, i.e. the solution to the
equation (1.1). Such choice $\zeta_{k,d,\beta}$ is motivated from physics
[KMRT+07] and previous mathematical works [DSS16b, Section 3] and [DSS22,
Section 4].

Before proceeding further, we show that if $\zeta$ is given as in (2.2),
(2.3), then $\mathcal{P}(\zeta,\lambda)$ does not depend on literals. More
precisely, suppose that $\zeta=\delta_{\eta_{0}}$, where
$\eta_{0}\in\mathscr{P}([0,1])$ is such that
$\eta_{0}(\mathrm{d}x)=\eta_{0}(\mathrm{d}(1-x))$, i.e.
$\rho\stackrel{{\scriptstyle d}}{{=}}1-\rho$ holds for $\rho\sim\eta_{0}$. For
a fixed $\underline{\texttt{L}}=(\texttt{L}_{i})_{i\leq k}\in\\{0,1\\}^{k}$,
let

$\theta_{\underline{\texttt{L}}}(\underline{x})=(1-e^{-\beta})\cdot\left(\prod_{i=1}^{k}(\texttt{L}_{i}\oplus
x_{i})+\prod_{i=1}^{k}(\texttt{L}_{i}\oplus x_{i}\oplus 1)\right)\,.$

With abuse of notation, for $x\in\\{0,1\\}$ and independent samples
$\rho_{a,j}\in\mathscr{P}(\\{0,1\\})$ from $\eta_{0}$, let

$u_{a,\underline{\texttt{L}}}(x)\equiv\sum_{\underline{x}\in\\{0,1\\}^{k}}\mathds{1}\\{x_{1}=x\\}\big{(}1-\theta_{\underline{\texttt{L}}}(\underline{x})\big{)}\prod_{j=2}^{k}\rho_{a,j}(x_{j})\,,\quad\quad
u_{\underline{\texttt{L}}}\equiv\sum_{\underline{x}\in\\{0,1\\}^{k}}\big{(}1-\theta_{\underline{\texttt{L}}}(\underline{x})\big{)}\prod_{j=1}^{k}\rho_{a,j}(x_{j})\,,$

where we consider $\underline{\texttt{L}}\in\\{0,1\\}^{k}$ to be fixed. Then,
for a given sequence of literals $\underline{\texttt{L}}_{a}\in\\{0,1\\}^{k}$
for $0\leq a\leq d$, let

$\mathcal{P}\big{(}\delta_{\eta_{0}},\lambda;(\underline{\texttt{L}}_{a})_{0\leq
a\leq
d}\big{)}:=\lambda^{-1}\log\mathbb{E^{\prime}}\Big{(}\sum_{x\in\\{0,1\\}}\prod_{a=1}^{d}u_{a,\underline{\texttt{L}}_{a}}(x)\Big{)}^{\lambda}-(k-1)\alpha\lambda^{-1}\mathbb{E}\log\mathbb{E^{\prime}}\left(u_{\underline{\texttt{L}}_{0}}\right)^{\lambda}\,,$
(2.4)

where $\mathbb{E}^{\prime}$ is the expectation with respect to the independent
samples $\rho_{a,j}\in\mathscr{P}(\\{0,1\\})$ from $\eta_{0}$. Note that if
$\underline{\texttt{L}}_{a}\stackrel{{\scriptstyle
i.i.d}}{{\sim}}\textnormal{Unif}(\\{0,1\\}^{k})$, then
$\mathcal{P}_{\theta_{\textsc{nae}}}(\delta_{\eta_{0}},\lambda)=\mathbb{E}_{\underline{\texttt{L}}}\mathcal{P}\big{(}\delta_{\eta_{0}},\lambda;(\underline{\texttt{L}}_{a})_{0\leq
a\leq d}\big{)}$ holds, and if $\underline{\texttt{L}}_{a}\equiv\underline{0}$
for $0\leq a\leq d$, then
$\mathcal{P}_{\theta_{\textsc{col}}}(\delta_{\eta_{0}},\lambda)=\mathcal{P}\big{(}\delta_{\eta_{0}},\lambda;\underline{0}\big{)}$
holds. The following lemma then clarifies the mechanism behind the identical
satisfiability upper bound in Theorem 1.1.

######  Lemma 2.3.

Consider $\zeta=\delta_{\eta_{0}}$ for some $\eta_{0}\in\mathscr{P}([0,1])$
such that $\eta_{0}(\mathrm{d}x)=\eta_{0}(\mathrm{d}(1-x))$. Then, for any
literals $\underline{\texttt{L}}_{a}\in\\{0,1\\}^{k}$ for $0\leq a\leq d$, the
value
$\mathcal{P}\big{(}\delta_{\eta_{0}},\lambda;(\underline{\texttt{L}}_{a})_{0\leq
a\leq d}\big{)}$ does not depend on $(\underline{\texttt{L}}_{a})_{0\leq a\leq
d}$. Thus,
$\mathcal{P}_{\theta_{\textsc{nae}}}(\delta_{\eta_{0}},\lambda)=\mathcal{P}_{\theta_{\textsc{col}}}(\delta_{\eta_{0}},\lambda)$
holds.

###### Proof.

For fixed $\underline{\texttt{L}}_{a}\in\\{0,1\\}^{k}$ for $0\leq a\leq d$,
note that the vectors
$\big{(}u_{a,\underline{\texttt{L}}_{a}}(0),u_{a,\underline{\texttt{L}}_{a}}(1)\big{)}$
are independent for $0\leq a\leq d$. Thus, it suffices to show that for given
$\underline{\texttt{L}},\underline{\texttt{L}}^{\prime}\in\\{0,1\\}^{k}$ and
$1\leq a\leq d$,

$u_{\underline{\texttt{L}}}\stackrel{{\scriptstyle
d}}{{=}}u_{\underline{\texttt{L}}^{\prime}}\quad\textnormal{and}\quad\big{(}u_{a,\underline{\texttt{L}}}(0),u_{a,\underline{\texttt{L}}}(1)\big{)}\stackrel{{\scriptstyle
d}}{{=}}\big{(}u_{a,\underline{\texttt{L}}^{\prime}}(0),u_{a,\underline{\texttt{L}}^{\prime}}(1)\big{)}\,.$
(2.5)

To this end, let $\underline{\texttt{L}}^{\prime}=\underline{0}$ and we first
prove that $u_{\underline{\texttt{L}}}\stackrel{{\scriptstyle
d}}{{=}}u_{\underline{0}}$ holds. Since
$\theta_{\underline{\texttt{L}}}(\underline{x})=\theta_{\underline{0}}(\underline{x}\oplus\underline{\texttt{L}})$,

$u_{\underline{\texttt{L}}}\equiv\sum_{\underline{x}\in\\{0,1\\}^{k}}\big{(}1-\theta_{\underline{\texttt{L}}}(\underline{x})\big{)}\prod_{j=1}^{k}\rho_{0,j}(x_{j})=\sum_{\underline{x}\in\\{0,1\\}^{k}}\big{(}1-\theta_{\underline{0}}(\underline{x})\big{)}\prod_{j=1}^{k}\rho_{0,j}(x_{j}\oplus\texttt{L}_{j})\,.$

Note that since $(\rho_{0,j})_{1\leq j\leq k}$ are i.i.d. samples from
$\eta_{0}$ and $\eta_{0}(\mathrm{d}x)=\eta_{0}(\mathrm{d}(1-x))$ holds, the
sequence $\big{(}\rho_{0,j}(\cdot\oplus\texttt{L}_{j})\big{)}_{1\leq j\leq k}$
are also i.i.d. from $\eta_{0}$. Hence, the equation above shows that
$u_{\underline{\texttt{L}}}\stackrel{{\scriptstyle d}}{{=}}u_{\underline{0}}$
holds.

Next, we prove that
$\big{(}u_{a,\underline{\texttt{L}}}(0),u_{a,\underline{\texttt{L}}}(1)\big{)}\stackrel{{\scriptstyle
d}}{{=}}\big{(}u_{a,\underline{0}}(0),u_{a,\underline{0}}(1)\big{)}$ holds.
Without loss of generality, let $a=1$. Again since
$\theta_{\underline{\texttt{L}}}(\underline{x})=\theta_{\underline{0}}(\underline{x}\oplus\underline{\texttt{L}})$,

$\displaystyle u_{1,\underline{\texttt{L}}}(x)$
$\displaystyle\equiv\sum_{\underline{x}\in\\{0,1\\}^{k}}\mathds{1}\\{x_{1}=x\\}\big{(}1-\theta_{\underline{\texttt{L}}}(\underline{x})\big{)}\prod_{j=2}^{k}\rho_{1,j}(x_{j})=\sum_{\underline{x}\in\\{0,1\\}^{k}}\mathds{1}\\{x_{1}\oplus\texttt{L}_{1}=x\\}\big{(}1-\theta_{\underline{0}}(\underline{x})\big{)}\prod_{j=2}^{k}\rho_{1,j}(x_{j}\oplus\texttt{L}_{j})$

Now, observe that $\theta_{\underline{0}}(\cdot)$ is invariant under global
flip, i.e. $\theta_{\underline{0}}(x)=\theta_{\underline{0}}(x\oplus 1)$.
Thus, it follows that

$\displaystyle u_{1,\underline{\texttt{L}}}(x)$
$\displaystyle=\sum_{\underline{x}\in\\{0,1\\}^{k}}\mathds{1}\\{x_{1}=x\\}[1-\theta_{\underline{0}}(\underline{x})]\prod_{j=2}^{k}\rho_{1,j}(x_{j}\oplus\texttt{L}_{1}\oplus\texttt{L}_{j})\,.$

By the same reasons as above,
$\big{(}\rho_{1,j}(\cdot\oplus\texttt{L}_{1}\oplus\texttt{L}_{j})\big{)}_{2\leq
j\leq k}$ have the same distribution as $\big{(}\rho_{1,j}\big{)}_{2\leq j\leq
k}$, which are i.i.d. from $\eta_{0}$. Thus, we have that
$\big{(}u_{1,\underline{\texttt{L}}}(0),u_{1,\underline{\texttt{L}}}(1)\big{)}\stackrel{{\scriptstyle
d}}{{=}}\big{(}u_{1,\underline{0}}(0),u_{1,\underline{0}}(1)\big{)}$.
Therefore, (2.5) holds, which concludes the proof. ∎

The following lemma relates
$\mathcal{P}_{\theta_{\textsc{col}}}(\zeta_{k,d,\beta},\beta^{-1/2})=\mathcal{P}_{\theta_{\textsc{nae}}}(\zeta_{k,d,\beta},\beta^{-1/2}),$
and $\boldsymbol{\prescript{\star}{}{\Phi}}(d)$, which plays a crucial role in
proving Proposition 1.6. Recall the definition of $\zeta_{k,d,\beta}$ in (2.2)
and (2.3).

######  Lemma 2.4.

$\mathcal{P}_{\theta_{\textsc{col}}}(\zeta_{k,d,\beta},\beta^{-1/2})\leq
C+\beta^{1/2}\cdot\boldsymbol{\prescript{\star}{}{\Phi}}(d)$ holds for some
constant $C\in\mathbb{R}$, which does not depend on $\beta>0$.

###### Proof.

Throughout, let $(\rho_{a,j})_{a\geq 0,j\geq 0}$ denote i.i.d. samples from
$\eta_{k,d,\beta}$ defined in (2.3), and let $\mathbb{E}^{\prime}$ (resp.
$\mathbb{P}^{\prime}$) denote the expectation (resp. probability) with respect
to $(\rho_{a,j})_{a\geq 0,j\geq 0}$. Also, we use the generic notation $C$ by
a constant that does not depend on $\beta>0$. Note that since
$\theta_{\textsc{col}}$ and $\eta_{k,d,\beta}$ are non-random, the outer
expectation $\mathbb{E}$ in the definition of $\mathcal{P}(\zeta,\lambda)$ in
(2.1) is redundant.

First, we bound the second term of the definition of
$\mathcal{P}_{\theta_{\textsc{col}}}(\zeta_{k,d,\beta},\beta^{-1/2})$ in
(2.1):

$\displaystyle(k-1)\alpha\beta^{1/2}\log\mathbb{E^{\prime}}\Big{[}\left(u_{0}\right)^{\beta^{-1/2}}\Big{]}$
$\displaystyle=(k-1)\alpha\beta^{1/2}\log\mathbb{E^{\prime}}\Bigg{[}\bigg{(}1-(1-e^{-\beta})\bigg{(}\prod_{j=1}^{k}\rho_{0,j}(0)+\prod_{j=1}^{k}\rho_{0,j}(1)\bigg{)}\bigg{)}^{\beta^{-1/2}}\Bigg{]}$

Note that the expectation inside the log in the right hand side above is
bounded below by

$2^{-\beta^{-1/2}}\cdot\mathbb{P^{\prime}}\bigg{(}1-(1-e^{-\beta})\bigg{(}\prod_{j=1}^{k}\rho_{0,j}(0)+\prod_{j=1}^{k}\rho_{0,j}(1)\bigg{)}\geq\frac{1}{2}\bigg{)}=2^{-\beta^{-1/2}}(1-2x^{k})\,,$

where $x$ is the solution to the bp equation (1.1) and the equality holds for
large enough $\beta\geq\beta_{0}$ since for large $\beta$ and $k\geq 3,$
$(1-e^{-\beta})\left(\prod_{j=1}^{k}\rho_{0,j}(0)+\prod_{j=1}^{k}\rho_{0,j}(1)\right)\geq\frac{1}{2}$
holds if and only if either
$\rho_{0,j}(1)=\frac{e^{\beta}}{e^{\beta}+e^{-\beta}}$ holds for all $1\leq
j\leq k$, or $\rho_{0,j}(1)=\frac{e^{-\beta}}{e^{\beta}+e^{-\beta}}$ holds for
all $1\leq j\leq k$. Thus, it follows that

$-(k-1)\alpha\lambda^{-1}\mathbb{E}\log\mathbb{E^{\prime}}\left[\left(u_{0}\right)^{\lambda}\right]\leq
C-\beta^{1/2}(k-1)\alpha\log\big{(}1-2x^{k}\big{)}\,.$ (2.6)

Next, we estimate the first term of the definition of
$\mathcal{P}_{\theta_{\textsc{col}}}(\zeta_{k,d,\beta},\beta^{-1/2})$ in
(2.1), which equals

$\begin{split}&\beta^{1/2}\log\mathbb{E^{\prime}}\bigg{[}\Big{(}\sum_{x\in\\{0,1\\}}\prod_{a=1}^{d}u_{a}(x)\Big{)}^{\beta^{-1/2}}\bigg{]}\\\
&=\beta^{1/2}\log\mathbb{E^{\prime}}\left[\Bigg{(}\prod_{a=1}^{d}\bigg{(}1-(1-e^{-\beta})\prod_{j=2}^{k}\rho_{a,j}(0)\bigg{)}+\prod_{a=1}^{d}\bigg{(}1-(1-e^{-\beta})\prod_{j=2}^{k}\rho_{a,j}(1)\bigg{)}\Bigg{)}^{\beta^{-1/2}}\right]\end{split}$
(2.7)

We upper bound the expectation inside the log in the above expression by

$\begin{split}2^{\beta^{-1/2}}\cdot\mathbb{P^{\prime}}\big{(}\mathcal{A}\big{)}+\left(3e^{-\beta}\right)^{\beta^{-1/2}}\,,\end{split}$

where

$\mathcal{A}:=\left\\{\prod_{a=1}^{d}\bigg{(}1-(1-e^{-\beta})\prod_{j=2}^{k}\rho_{a,j}(0)\bigg{)}+\prod_{a=1}^{d}\bigg{(}1-(1-e^{-\beta})\prod_{j=2}^{k}\rho_{a,j}(1)\bigg{)}\geq
3e^{-\beta}\right\\}\,.$

Define the events $\mathcal{E}_{0}$ and $\mathcal{E}_{1}$ involving
$(\rho_{a,j})_{1\leq a\leq d,2\leq j\leq k}$ as follows.

  * •

$\mathcal{E}_{0}$ is the event such that for any $1\leq a\leq d$, there exists
$j\in\\{2,\ldots,k\\}$ such that
$\rho_{a,j}(0)\neq\frac{e^{\beta}}{e^{\beta}+e^{-\beta}}$.

  * •

$\mathcal{E}_{1}$ is the event such that for any $1\leq a\leq d$, there exists
$j\in\\{2,\ldots,k\\}$ such that
$\rho_{a,j}(1)\neq\frac{e^{\beta}}{e^{\beta}+e^{-\beta}}$.

We now claim that for large enough $\beta$, the event $\mathcal{A}$ is
included in $\mathcal{E}_{0}\cup\mathcal{E}_{1}$. To this end, suppose that
the event $(\mathcal{E}_{0}\cup\mathcal{E}_{1})^{\sf c}=\mathcal{E}_{0}^{\sf
c}\cap\mathcal{E}_{1}^{\sf c}$ holds. Then, for each $x\in\\{0,1\\}$, for some
$a\equiv a(x)\in\\{1,\ldots,d\\}$ such that
$\rho_{a,j}(x)=\frac{e^{\beta}}{e^{\beta}+e^{-\beta}}$ holds for all $2\leq
j\leq k$. Thus, for $x\in\\{0,1\\}$, we have

$\prod_{a=1}^{d}\bigg{(}1-(1-e^{-\beta})\prod_{j=2}^{k}\rho_{a,j}(x)\bigg{)}\leq
1-(1-e^{-\beta})\left(\frac{e^{\beta}}{e^{\beta}+e^{-\beta}}\right)^{k-1}\leq
e^{-\beta}+e^{-2\beta}\,,$

where the last inequality holds for large enough $\beta\geq\beta_{k}$. Hence,
summing over $x\in\\{0,1\\}$ gives that the event $\mathcal{A}$ cannot hold,
which proves our claim that
$\mathcal{A}\subset\mathcal{E}_{0}\cup\mathcal{E}_{1}$. Consequently, the term
(2.7) is bounded above by

$\displaystyle\beta^{1/2}\log\left(2^{\beta^{-1/2}}\cdot\mathbb{P}^{\prime}\big{(}\mathcal{E}_{0}\cup\mathcal{E}_{1}\big{)}+(3e^{-\beta})^{\beta^{-1/2}}\right)\leq\beta^{1/2}\log\mathbb{P}^{\prime}\big{(}\mathcal{E}_{0}\cup\mathcal{E}_{1}\big{)}+C\,.$

Note that
$\mathbb{P}^{\prime}\big{(}\mathcal{E}_{0}\cup\mathcal{E}_{1}\big{)}$ can be
calculated explicitly by

$\mathbb{P}^{\prime}(\mathcal{E}_{0}\cup\mathcal{E}_{1})=2(1-x^{k-1})^{d}-(1-2x^{k-1})^{d}=\frac{(1-x^{k-1})^{d-1}(1-2x^{k})}{1-x}\,,$

where in the final equality, we used the fact that $x$ is the solution to the
equation (1.1). Therefore, we have proven that

$\beta^{1/2}\log\mathbb{E^{\prime}}\bigg{[}\Big{(}\sum_{x\in\\{0,1\\}}\prod_{a=1}^{d}u_{a}(x)\Big{)}^{\beta^{-1/2}}\bigg{]}\leq
C+\beta^{1/2}\left(-\log(1-x)+(d-1)\log(1-x^{k-1})+\log(1-2x^{k})\right)\,.$
(2.8)

In conclusion, combining (2.6) and (2.8), and recalling the definition of
$\boldsymbol{\prescript{\star}{}{\Phi}}(d)$ in (1.2), we have

$\displaystyle\mathcal{P}_{\theta_{\textsc{col}}}(\zeta_{k,d,\beta},\beta^{-1/2})$
$\displaystyle\leq C+\beta^{1/2}\boldsymbol{\prescript{\star}{}{\Phi}}(d)\,,$

which concludes the proof. ∎

###### Proof of Proposition 1.6.

Given a nae-sat instance $\boldsymbol{\mathcal{G}}$, let
$\textsf{SOL}(\boldsymbol{\mathcal{G}})\subset\\{0,1\\}^{V}$ denotes the set
of nae-sat solutions. Also, let
$Z_{\beta,\textsc{nae}}(\boldsymbol{\mathcal{G}})$ denotes the partition
function (1.8) for $\theta=\theta_{\textsc{nae}}(\cdot\,;\,\beta)$. Note that
if $\underline{x}\in\textsf{SOL}(\boldsymbol{\mathcal{G}})$, then
$\theta_{\textsc{nae}}(\underline{x}_{\delta a})=0$ for any $a\in F$, thus we
have for any $\beta>0$ that

$Z_{\beta,\textsc{nae}}(\boldsymbol{\mathcal{G}})\equiv\sum_{\underline{x}\in\\{0,1\\}^{V}}\prod_{a\in
F}\big{(}1-\theta_{\textsc{nae}}(\underline{x}_{\delta
a};\beta)\big{)}\geq\left|\textsf{SOL}(\boldsymbol{\mathcal{G}})\right|\,.$
(2.9)

On the other hand, since $\theta_{\textsc{nae}}(\cdot\,;\,\beta)$ satisfies
the condition (1.7) with $\varepsilon=e^{-\beta}$, we have by Theorem 2.1 that

$\frac{1}{n}\mathbb{E}\Big{[}\log
Z_{\beta,\textsc{nae}}(\boldsymbol{\mathcal{G}})\Big{]}\leq\mathcal{P}_{\theta_{\textsc{nae}}}(\zeta_{k,d,\beta},\beta^{-1/2})+o_{n}(1)=\mathcal{P}_{\theta_{\textsc{col}}}(\zeta_{k,d,\beta},\beta^{-1/2})+o_{n}(1)\,,$

where the last equality is due to Lemma 2.3. By Lemma 2.4, the right hand side
is further bounded by

$\frac{1}{n}\mathbb{E}\Big{[}\log
Z_{\beta,\textsc{nae}}(\boldsymbol{\mathcal{G}})\Big{]}\leq\beta^{1/2}\cdot\boldsymbol{\prescript{\star}{}{\Phi}}(d)+C+o_{n}(1)\,,$

for some constant $C$ that does not depend on $n$ nor $\beta$. If
$\boldsymbol{\prescript{\star}{}{\Phi}}(d)<0$, then for large enough
$\beta>0$, $\beta^{1/2}\cdot\boldsymbol{\prescript{\star}{}{\Phi}}(d)+C<-1$
holds, thus $n^{-1}\mathbb{E}\big{[}\log
Z_{\beta,\textsc{nae}}(\boldsymbol{\mathcal{G}})\big{]}<-1$ holds for large
enough $n$. For such $\beta=\beta_{0}(k,d)>0$, we have by (2.9) and Lemma 1.4
that for large enough $n$,

$\mathbb{P}\Big{(}\left|\textsf{SOL}(\boldsymbol{\mathcal{G}})\right|\geq
1\Big{)}\leq\mathbb{P}\bigg{(}\bigg{|}\frac{1}{n}\log
Z_{\beta_{0},\textsc{nae}}(\boldsymbol{\mathcal{G}})-\frac{1}{n}\mathbb{E}\Big{[}\log
Z_{\beta_{0},\textsc{nae}}(\boldsymbol{\mathcal{G}})\Big{]}\bigg{|}\geq
1\bigg{)}\leq e^{-cn}\,,$

for some constant $c$ that depends only on $\beta_{0}>0$, which finishes the
proof for the nae-sat model.

Given a configuration model $\boldsymbol{G}$, let
$Z_{\beta,\textsc{col}}(\boldsymbol{G})$ denote the partition function (1.8)
for $\theta=\theta_{\textsc{col}}(\cdot\,;\,\beta)$. Then, by the same
reasoning, Theorem 2.1 and Lemma 2.4 shows that if
$\boldsymbol{\prescript{\star}{}{\Phi}}(d)<0$ then
$\frac{1}{n}\mathbb{E}\big{[}\log
Z_{\beta,\textsc{col}}(\boldsymbol{G})\big{]}<-1$ holds for large enough
$\beta=\beta_{0}(k,d)>0$ and $n$ large enough. On the event that there exists
a $2$-coloring on $\boldsymbol{G}$,
$Z_{\beta,\textsc{col}}(\boldsymbol{G})\geq 1$ holds, so Lemma 1.4 again
concludes the proof. ∎

###  2.2 Proof of Lemma 1.4

Recall that $\boldsymbol{G}=(V,F,\boldsymbol{E})$ is generated from the
configuration model, where the $\boldsymbol{E}$ is drawn uniformly from
$S_{nd}$. Thus, $\boldsymbol{E}$ has the same law as sequentially drawing
random clauses $\boldsymbol{a}_{1},\ldots,\boldsymbol{a}_{m}$ as follows. At
times $t\in\\{1,\ldots,k\\}$, clause $\boldsymbol{a}_{t}$ is drawn by
connecting the $k$ adjacent half-edges to previously unmatched half-edges
adjacent to variables. For $1\leq t\leq m$, let $\mathscr{F}_{t}$ be the
$\sigma$-algebra generated by $\boldsymbol{a}_{1},\ldots,\boldsymbol{a}_{t}$,
and $\mathscr{F}_{0}\equiv\emptyset$. Denote $M_{t}\equiv\mathbb{E}\big{[}\log
Z(\boldsymbol{G})\mid\mathscr{F}_{t}\big{]}$ by the associated Doob
martingale. Note that if $\boldsymbol{G}=(V,F,E)$ and
$\boldsymbol{G}^{\prime}=(V,F,E^{\prime})$ has the the same set of edges
except for those adjacent to two clauses $a_{1}\neq a_{2}\in F$, then by our
assumption of $\theta$ in (1.7) and the definition of $Z(G)$ in (1.8), it
follows that $\varepsilon^{2}\leq Z(G)/Z(G^{\prime})\leq\varepsilon^{-2}$
holds. Thus, we have for every $t\in\\{0,1,\ldots,m-1\\}$ that

$\Big{|}M_{t+1}-M_{t}\Big{|}\equiv\Big{|}\mathbb{E}\big{[}\log
Z(\boldsymbol{G})\mid\mathscr{F}_{t+1}\big{]}-\mathbb{E}\big{[}\log
Z(\boldsymbol{G})\mid\mathscr{F}_{t}\big{]}\Big{|}\leq
2\log\big{(}1/\varepsilon\big{)}\,,$ (2.10)

from which Lemma 1.4 follows.

###### Proof of Lemma 1.4.

Note that $M_{m}=\log Z(\boldsymbol{G})$ and $M_{0}=\mathbb{E}\big{[}\log
Z(\boldsymbol{G})\big{]}$ holds and $(M_{t})_{0\leq t\leq m}$ is a martingale
with bounded difference by (2.10). Therefore, the conclusion follows from
Azuma Hoeffding’s inequality. ∎

###  2.3 Proof of Lemma 1.8

The following notations are convenient for the proof of Lemma 1.8. For non-
negative quantities $f=f_{d,k,n}$ and $g=g_{d,k,n}$, we use any of the
equivalent notations $f=O_{k,d}(g),g=\Omega_{k,d}(f),f\lesssim_{k,d}g$ and
$g\gtrsim_{k,d}f$ to indicate that there exists a constant $C_{k,d}$, which
only depends on $k,d$ such that $f\leq C_{k,d}\cdot g$. We drop the subscripts
$d$ (resp. $k,d$) if the constant $C_{k,d}$ does not depend on $d$ (resp.
$k,d$). When $f\lesssim_{k,d}g$ and $g\lesssim_{k,d}f$, we write
$f\asymp_{k,d}g$. Similarly when $f\lesssim g$ and $g\lesssim f$, we write
$f\asymp g$.

Note that $\mathbb{E}Z_{\textsc{col}}$ is the sum over
$\underline{x}\in\\{0,1\\}^{V}$ of the probabilities that $\underline{x}$ is a
$2$-coloring on $\boldsymbol{G}$. By symmetry, the probability of
$\underline{x}\in\\{0,1\\}^{V}$ being a $2$-coloring depends only on the
number $n\gamma$ of nodes having color $1$, which we denote by
$\boldsymbol{p}_{\gamma}$. Thus,
$\mathbb{E}Z_{\textsc{col}}=\sum_{\gamma}\binom{n}{n\gamma}\boldsymbol{p}_{\gamma}$,
where the sum is over $\gamma\in(0,1)$ such that $n\gamma\in\mathbb{Z}$.
Moreover, we can express $\boldsymbol{p}_{\gamma}$ as follows. Let
$X_{1},\ldots,X_{m}$ be i.i.d. $\textnormal{Binom}(k,\gamma)$ random variables
and denote $\mathbb{P}_{\gamma}$ by the probability with repect to
$(X_{i})_{i\leq m}$. Then, we have

$\begin{split}\boldsymbol{p}_{\gamma}&=\mathbb{P}_{\gamma}\Big{(}X_{i}\notin\\{0,k\\}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \textnormal{for
all}\leavevmode\nobreak\ 1\leq i\leq
m\,\Big{|}\,\sum_{i=1}^{m}X_{i}=km\gamma\Big{)}\\\
&\leq\frac{\mathbb{P}_{\gamma}\big{(}X_{i}\notin\\{0,k\\}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \textnormal{for
all}\leavevmode\nobreak\ 1\leq i\leq
m\big{)}}{\mathbb{P}_{\gamma}\big{(}\sum_{i=1}^{m}X_{i}=km\gamma\big{)}}\lesssim_{k}\sqrt{m}(1-\gamma^{k}-(1-\gamma)^{k})^{m}\,,\end{split}$
(2.11)

where the last inequality is due to a Stirling’s approximation. It follows
that

$\begin{split}&\mathbb{E}Z_{\textsc{col}}\leq
n^{O(1)}\sum_{\gamma}\exp\Big{(}nF_{\alpha}(\gamma)\Big{)}\,,\quad\textnormal{where}\\\
&F_{\alpha}(\gamma):=H(\gamma)+\alpha\log\big{(}1-\gamma^{k}-(1-\gamma)^{k}\big{)}\,.\end{split}$
(2.12)

Here, $H(\gamma)\equiv-\gamma\log\gamma-(1-\gamma)\log(1-\gamma)$ is the
entropy of $\gamma$. Note that $\gamma\to\gamma^{k}+(1-\gamma)^{k}$ is
uniquely minimized at $\gamma=1/2$. Further, the entropy $H(\gamma)$ is
strictly concave and is maximized at $\gamma=1/2$. Thus, $\gamma\to
F_{\alpha}(\gamma)$ is uniquely maximized at $\gamma=1/2$ with
$\frac{\partial^{2}F_{\alpha}}{\partial\gamma^{2}}(1/2)<0$. Since
$\mathbb{E}Z_{\textsc{nae}}=\exp\big{(}nF_{\alpha}(1/2)\big{)}$, it follows
from (2.12) that

$\mathbb{E}Z_{\textsc{col}}\leq
n^{O(1)}\exp\big{(}nF_{\alpha}(1/2)\big{)}=n^{O(1)}\cdot\mathbb{E}Z_{\textsc{nae}}\,.$
(2.13)

We now show that the polynomial factor $n^{O(1)}$ can actually be removed with
a matching lower bound.

First, by (2.11) and the fact that $\gamma\to F_{\alpha}(\gamma)$ is uniquely
maximized at $\gamma=1/2$ with strictly negative second derivative, the
contribution to $\mathbb{E}Z_{\textsc{col}}$ from $\gamma$ such that
$|\gamma-1/2|\geq n^{-1/3}$ is negligible:

$\sum_{|\gamma-1/2|\geq
n^{-1/3}}\binom{n}{n\gamma}\boldsymbol{p}_{\gamma}\lesssim_{k,d}\exp\big{(}-\Omega_{k,d}\big{(}n^{1/3}\big{)}\big{)}\cdot\mathbb{E}Z_{\textsc{nae}}\,.$
(2.14)

Thus, we focus on the regime $|\gamma-1/2|\leq n^{-1/3}$. Note that we can
calculate $\boldsymbol{p}_{\gamma}$ by summing over the empirical distribution
$\nu$ of $(X_{i})_{i\leq m}$. Consider $\nu\in\mathscr{P}(\\{1,\ldots,k-1\\})$
and let $p_{\gamma}(j):=\binom{k}{j}\gamma^{j}(1-\gamma)^{k-j}$. Then,

$\begin{split}\boldsymbol{p}_{\gamma}=\frac{\sum_{\nu}\mathds{1}\Big{(}\sum_{j}j\nu_{j}=km\gamma\Big{)}\binom{m}{m\nu}\prod_{j}p_{\gamma}(j)^{m\nu_{j}}}{\mathbb{P}_{\gamma}\big{(}\sum_{i=1}^{m}X_{i}=km\gamma\big{)}}=\frac{\sum_{\nu}\mathds{1}\Big{(}\sum_{j}j\nu_{j}=km\gamma\Big{)}e^{-km\gamma\lambda}\binom{m}{m\nu}\prod_{j}(p_{\gamma}(j)e^{\lambda
j})^{m\nu_{j}}}{\mathbb{P}_{\gamma}\big{(}\sum_{i=1}^{m}X_{i}=km\gamma\big{)}}\,,\end{split}$

where $\binom{m}{m\nu}\equiv\frac{m!}{\prod_{j}(m\nu_{j})!}$ and we introduced
a lagrange parameter $\lambda\in\mathbb{R}$ in the last equality. Let

$\nu_{\gamma,\lambda}(x):=\frac{p_{\gamma}(x)e^{\lambda
x}}{\sum_{j=1}^{k-1}p_{\gamma}(j)e^{\lambda j}}\leavevmode\nobreak\
\leavevmode\nobreak\ \textnormal{for}\leavevmode\nobreak\ \leavevmode\nobreak\
1\leq x\leq k-1\,,$

and denote $\mathbb{P}_{\gamma,\lambda}$ by the probability with respect to
$\widetilde{X}_{1},\ldots,\widetilde{X}_{m}\stackrel{{\scriptstyle
i.i.d.}}{{\sim}}\nu_{\gamma,\lambda}$. Then, it follows that

$\boldsymbol{p}_{\gamma}=\frac{\mathbb{P}_{\gamma,\lambda}\big{(}\sum_{i=1}^{m}\widetilde{X}_{i}=km\gamma\big{)}}{\mathbb{P}_{\gamma}\big{(}\sum_{i=1}^{m}X_{i}=km\gamma\big{)}}\exp\big{(}-m\cdot\Xi(\gamma,\lambda)\big{)}\,,\leavevmode\nobreak\
\leavevmode\nobreak\ \textnormal{where}\leavevmode\nobreak\
\leavevmode\nobreak\
\Xi(\gamma,\lambda):=k\gamma\lambda-\log\bigg{(}\sum_{j=1}^{k-1}p_{\gamma}(j)e^{\lambda
j}\bigg{)}\,.$ (2.15)

In order to use the local central limit theorem, we take
$\lambda=\lambda(\gamma)$ such that
$\mathbb{E}_{\gamma,\lambda}\widetilde{X}=k\gamma$, where
$\widetilde{X}\sim\nu_{\gamma,\lambda}$. The existence of such
$\lambda(\gamma)$ is guaranteed by the lemma below.

######  Lemma 2.5.

For large enough $n$ and all $\gamma$ such that $|\gamma-1/2|\leq n^{-1/3}$,
there exists a unique $\lambda=\lambda(\gamma)$ such that
$\mathbb{E}_{\gamma,\lambda}\widetilde{X}=k\gamma$ holds. Furthermore, we have
$\lambda(1/2)=0$ and $\big{|}\lambda(\gamma)\big{|}\lesssim_{k}n^{-1/3}$ holds
uniformly over $|\gamma-1/2|\leq n^{-1/3}$.

###### Proof.

Note that we have
$\frac{\partial\Xi}{\partial\lambda}(\gamma,\lambda)=k\gamma-\mathbb{E}_{\gamma,\lambda}\widetilde{X}$
by definition of $\nu_{\gamma,\lambda}$ and $\Xi(\gamma,\lambda)$. Further, we
have that

$\frac{\partial\Xi}{\partial\lambda}\Big{(}\frac{1}{2}\,,\,0\Big{)}=\frac{k}{2}-\mathbb{E}_{\frac{1}{2},0}\widetilde{X}=\frac{k}{2}-\mathbb{E}_{\frac{1}{2}}\big{[}X\,\big{|}\,X\notin\\{0,k\\}\big{]}=0\,,$

where $\mathbb{E}_{\frac{1}{2}}$ is with respect to
$X\sim\textnormal{Binom}(1/2)$. Since
$\lambda\to\log\big{(}\sum_{j=1}^{k-1}p_{\gamma}(j)e^{\lambda j}\big{)}$ is
strongly convex, we have
$\frac{\partial^{2}\Xi}{\partial\lambda^{2}}\big{(}\frac{1}{2},0\big{)}<0$.
Thus, implicit function theorem shows that for
$\gamma\in(1/2-\varepsilon,1/2+\varepsilon)$, where
$\varepsilon=\varepsilon(k)>0$ depends only on $k$, there exists
$\lambda=\lambda(\gamma)$ such that
$\frac{\partial\Xi}{\partial\lambda}\big{(}\gamma,\lambda(\gamma)\big{)}=0$
holds, and that $\gamma\to\lambda(\gamma)$ is continuously differentiable.
Therefore, for large enough $n$ and $\gamma\in(1/2-n^{-1/3},1/2+n^{1/3})$,
there exists a unique $\lambda=\lambda(\gamma)$ such that
$\mathbb{E}_{\gamma,\lambda(\gamma)}\widetilde{X}=k\gamma$, and
$|\lambda(\gamma)|\lesssim_{k}n^{-1/3}$ holds uniformly over
$\gamma\in(1/2-n^{-1/3},1/2+n^{1/3})$. ∎

Having Lemma 2.5 in hand, we prove Lemma 1.8 by appealing to the local central
limit theorem.

###### Proof of Lemma 1.8.

The contribution to $\mathbb{E}Z_{\textsc{col}}$ from $\gamma$ such that
$|\gamma-1/2|\geq n^{-1/3}$ is negligible by (2.14), thus we consider $\gamma$
such that $|\gamma-1/2|\leq n^{-1/3}$ holds. To this end, we take
$\lambda=\lambda(\gamma)$ from Lemma 2.5 in equation (2.15). Then, by the
local central limit theorem [Bor17],

$\boldsymbol{p}_{\gamma}\asymp\bigg{(}\frac{\operatorname{Var}_{\gamma}\big{(}X\big{)}}{\operatorname{Var}_{\gamma,\lambda(\gamma)}\big{(}\widetilde{X}\big{)}}\bigg{)}^{1/2}\cdot\exp\Big{(}-m\cdot\Xi\big{(}\gamma,\lambda(\gamma)\big{)}\Big{)}\,,$
(2.16)

where $X\sim\textnormal{Binom}(k,\gamma)$ and
$\widetilde{X}\sim\nu_{\gamma,\lambda(\gamma)}$. Lemma 2.5 further shows that
$\big{|}\lambda(\gamma)\big{|}\lesssim_{k}n^{-1/3}$, thus we have

$\operatorname{Var}_{\gamma,\lambda(\gamma)}\big{(}\widetilde{X}\big{)}\asymp_{k}\operatorname{Var}_{\gamma}\big{(}X\,\big{|}\,1\leq
X\leq k-1\big{)}\asymp_{k}\operatorname{Var}_{\gamma}(X)\,,$ (2.17)

where the final estimate holds because $|\gamma-1/2|\leq n^{-1/3}$. Combining
with (2.14), it follows that

$\mathbb{E}Z_{\textsc{col}}=\big{(}1+o_{n}(1)\big{)}\sum_{|\gamma-1/2|\leq
n^{-1/3}}\binom{n}{n\gamma}\boldsymbol{p}_{\gamma}\asymp_{k,d}n^{-1/2}\sum_{|\gamma-1/2|\leq
n^{-1/3}}\exp\big{(}nG_{\alpha}(\gamma)\big{)}\,,$ (2.18)

where

$G_{\alpha}(\gamma):=H(\gamma)-\alpha\cdot\Xi\big{(}\gamma,\lambda(\gamma)\big{)}\,.$

Note that by comparing (2.16) and (2.17) with (2.11), we have
$G_{\alpha}(\gamma)\leq F_{\alpha}(\gamma)$ for $|\gamma-1/2|\leq n^{-1/3}$.
Also, note that for $\gamma=1/2$, $G_{\alpha}(1/2)=F_{\alpha}(1/2)$ holds
since

$G_{\alpha}(1/2)=H(1/2)-\alpha\cdot\Xi(1/2,0)=H(1/2)+\alpha\log\big{(}1-\gamma^{k}-(1-\gamma)^{k}\big{)}\,,$

where we used $\lambda(1/2)=0$ by Lemma 2.5. Recalling that $\gamma\to
F_{\alpha}(\gamma)$ is uniquely maximized at $\gamma=1/2$ with strictly
negative second derivative at the maximizer, it follows that the same holds
for $\gamma\to G_{\alpha}(\gamma)$. Therefore, combining with (2.18), we have

$\mathbb{E}Z_{\textsc{col}}\asymp_{k,d}\exp\big{(}nG_{\alpha}(1/2)\big{)}=\mathbb{E}Z_{\textsc{nae}}\,,$

which concludes the proof. ∎

##  3 Proof of Proposition 1.7 for $k\geq 4$

In this section, we prove Proposition 1.7 for $k\geq 4$, which can be split
into the following two lemmas. In Section 3.1, we prove Lemma 3.1 which
guarantees the existence and the uniqueness of the bp fixed point for $k\geq
4$.

######  Lemma 3.1.

For $k\geq 4$ and $d\in[d_{\textnormal{lbd}}(k),d_{\textnormal{ubd}}(k)]$,
there exists a unique solution to $\Psi_{d}(x)=x$ in the range
$x\in[\frac{1}{2}-\frac{1}{2^{k}},\frac{1}{2}]$.

By Lemma 3.1, the function $d\to\boldsymbol{\prescript{\star}{}{\Phi}}(d)$ is
well-defined. In Section 3.2, we prove Lemma 3.2 which guarantees that
$d_{\star}(k)$ is well-defined for $k\geq 4$.

######  Lemma 3.2.

For $k\geq 4$, the function $d\to\boldsymbol{\prescript{\star}{}{\Phi}}(d)$ is
continuous for $d\in[d_{\textnormal{lbd}}(k),d_{\textnormal{ubd}}(k)]$.
Further, $\boldsymbol{\prescript{\star}{}{\Phi}}(d_{\textnormal{lbd}}(k))>0$
and $\boldsymbol{\prescript{\star}{}{\Phi}}(d_{\textnormal{ubd}}(k))<0$ hold.

###### Proof of Proposition 1.7 for $k\geq 4$.

This is immediate from Lemma 3.1 and Lemma 3.2. ∎

###  3.1 Proof of Lemma 3.1

Recall the variable bp recursion $\dot{\Psi}$ and the clause bp recursion
$\hat{\Psi}$ defined in (1.12). To prove the uniqueness of the bp fixed point,
we show that the bp recursion $\Psi_{d}\equiv\dot{\Psi}\circ\hat{\Psi}$ is a
contraction for $k\geq 4$.

######  Lemma 3.3.

For $k\geq 4$ and $d\in[d_{\textnormal{lbd}}(k),d_{\textnormal{ubd}}(k)]$,
$\big{|}(\Psi_{d})^{\prime}(x)\big{|}<1$ holds uniformly over
$x\in[\frac{1}{2}-\frac{1}{2^{k}},\frac{1}{2}]$.

###### Proof.

Throughout, we let $x\in[1/2-1/2^{k},1/2]$ and denote $v=\hat{\Psi}(x)$. We
first consider $k\geq 5$. Observe that the derivative of the clause bp
recursion can simply be bounded in absolute value by

$\big{|}(\hat{\Psi})^{\prime}(x)\big{|}=\frac{(k-1)x^{k-2}}{(1-x^{k-1})^{2}}\leq\frac{(k-1)\cdot
2^{-k+2}}{(1-2^{-k+1})^{2}}=\frac{4(k-1)}{2^{k}(1-2^{-k+1})^{2}}\,,$ (3.1)

where the inequality holds since $x\to\frac{x^{k-2}}{(1-x^{k-1})^{2}}$ is
increasing. Similarly, we bound the derivative of the variable bp recursion:

$\big{|}(\dot{\Psi})^{\prime}(v)\big{|}=\frac{(d-1)v^{d-2}}{(2-v^{d-1})^{2}}\leq\frac{(d-1)v_{0}^{d-2}}{(2-v_{0}^{d-1})^{2}}\leq\frac{(d-1)v_{0}^{d-2}}{(2-v_{0}^{d-2})^{2}}\,,$
(3.2)

where we denoted $v_{0}:=\hat{\Psi}(x_{0})$ for $x_{0}=1/2-1/2^{k}$. The first
inequality holds because $x\to\hat{\Psi}(\cdot)$ is decreasing on
$[1/2-1/2^{k},1/2]$, and the last inequality holds since $v_{0}<1$. To this
end, we upper bound $v_{0}^{d-2}$ by

$v_{0}^{d-2}=\left(1-\frac{x_{0}^{k-1}}{1-x_{0}^{k-1}}\right)^{d-2}\leq(1-x_{0}^{k-1})^{d-2}\leq
e^{-(d-2)x_{0}^{k-1}}\,.$ (3.3)

Note that
$x_{0}^{k-1}=\left(\frac{1}{2}\right)^{k-1}\left(1-\frac{2}{2^{k}}\right)^{k-1}\geq\left(\frac{1}{2}\right)^{k-1}\left(1-\frac{2(k-1)}{2^{k}}\right)$
and $d\geq(2^{k-1}-2)k\log 2$ hold, thus we can lower bound $(d-2)x_{0}^{k-1}$
by

$(d-2)x_{0}^{k-1}\geq\left(k\log 2-\frac{4k\log
2+4}{2^{k}}\right)\cdot\left(1-\frac{2(k-1)}{2^{k}}\right)\,.$

Thus, combining with (3.3) shows that

$v_{0}^{d-2}\leq
2^{-k}e^{\varepsilon_{k}}\,,\quad\textnormal{where}\quad\varepsilon_{k}:=\frac{2(k-1)k\log
2}{2^{k}}+\frac{4k\log 2+4}{2^{k}}\left(1-\frac{2(k-1)}{2^{k}}\right)\,.$
(3.4)

Plugging this bound into (3.2), we have

$|(\dot{\Psi})^{\prime}(v)|<(d-1)\frac{v_{0}^{d-2}}{(2-v_{0}^{d-2})^{2}}\leq(2^{k-1}k\log
2-1)\cdot\frac{2^{-k}\cdot
e^{\varepsilon_{k}}}{(2-2^{-k}e^{\varepsilon_{k}})^{2}}\,.$

Combining with the contraction of clause bp recursion in (3.1), we have

$|(\Psi_{d})^{\prime}(x)|\leq\alpha_{k}:=\frac{2k(k-1)\log
2}{2^{k}}\cdot\left(1-\frac{1}{2^{k-1}k\log
2}\right)\cdot\frac{e^{\varepsilon_{k}}}{(1-2^{-k+1})^{2}(2-2^{-k}e^{\varepsilon_{k}})^{2}}\,.$

By comparing $\varepsilon_{k}$ and $\varepsilon_{k+1}$ for $k\geq 5$, it can
be easily checked that $k\to\varepsilon_{k}$ is decreasing, and the same holds
for $k\to\frac{2k(k-1)\log 2}{2^{k}}\cdot\left(1-\frac{1}{2^{k-1}k\log
2}\right)$. Thus, $k\to\alpha_{k}$ is decreasing for $k\geq 5$. Furthermore,
$\alpha_{5}$ can be calculated up to arbitrary precision (e.g. by
Mathematica), which satisfies $\alpha_{5}<0.99<1$. Consequently,
$|(\Psi_{d})^{\prime}(x)|<1$ holds for $k\geq 5$.

The case where $k=4$ is more delicate, and the previous strategy of bounding
the derivative of clause and variable bp recursions separately no longer is
successful. To this end, we bound $(\Psi_{d})^{\prime}(x)$ directly. If we
denote $v=\hat{\Psi}_{k}(x)$, then

$\displaystyle\big{|}(\Psi_{d})^{\prime}(x)\big{|}=\big{|}(\hat{\Psi})^{\prime}(x)|\cdot|(\dot{\Psi})^{\prime}(v)\big{|}$
$\displaystyle=\frac{(k-1)(d-1)v^{d-2}}{(2-v^{d-1})^{2}}\cdot\frac{x^{k-1}}{(1-x^{k-1})^{2}}\cdot\frac{1}{x}\,.$

Since $v\equiv\hat{\Psi}_{k}(x)\equiv\frac{1-2x^{k-1}}{1-x^{k-1}}$,
rearranging gives $x^{k-1}=\frac{1-v}{2-v}$. Substituting this in for
$x^{k-1}$, we have that

$\big{|}(\Psi_{d})^{\prime}(x)\big{|}=(k-1)(d-1)\cdot\frac{v^{d-2}(2-v)(1-v)}{(2-v^{d-1})^{2}}\cdot\frac{1}{x}\,.$
(3.5)

We now claim that $v\to\frac{v^{d-2}(2-v)(1-v)}{(2-v^{d-1})^{2}}$ is
increasing for $v\in[\hat{\Psi}_{4}(1/2),\hat{\Psi}_{4}(1/2-1/2^{4})]$ and
$d\in[24\log 2,32\log 2]$ (recall that $24\log 2>16.7\equiv
d_{\textnormal{lbd}}(4)$ holds). Since $v\to(2-v^{d-1})^{2}$ is decreasing, it
suffices to show that $v\to v^{d-2}(2-v)(1-v)$ is increasing. Note that

$\frac{\mathrm{d}}{\mathrm{d}v}\Big{(}v^{d-2}(2-v)(1-v)\Big{)}=(dv^{2}-3(d-1)v+2(d-2))v^{d-3}>0\iff
d>\frac{4-3v}{(2-v)(1-v)}\,.$

Note that $v\to\frac{4-3v}{(2-v)(1-v)}$ is increasing since its derivative is
given by $\frac{3v^{2}-8v+6}{(2-v)^{2}(1-v)^{2}}>0$. Thus, to prove our claim,
it suffices to check that for $d_{0}:=24\log 2$ and
$v_{0}=\hat{\Psi}_{4}(1/2-1/2^{4})$ that
$d_{0}>\frac{4-3v_{0}}{(2-v_{0})(1-v_{0})}$ holds. By a direct calculation,
$v_{0}=3410/3753<0.91$ and $24\log 2>16>\frac{4-3\cdot
0.91}{(2-0.91)(1-0.91)}$ holds, thus the claim that
$v\to\frac{v^{d-2}(2-v)(1-v)}{(2-v^{d-1})^{2}}$ is increasing is proven for
$d,v$ in the regime of interest.

Note that $x\to v=\hat{\Psi}_{4}(x)$ is decreasing, thus (3.5) and our
previous claim shows that for all $x_{0}\leq x\leq 1/2$, where
$x_{0}=1/2-1/2^{4}$, we have

$\big{|}(\Psi_{d})^{\prime}(x)\big{|}\leq(d-1)(k-1)\frac{v_{0}^{d-2}(2-v_{0})(1-v_{0})}{(2-v_{0}^{d-1})^{2}}\cdot\frac{1}{x_{0}}\,,$

where $v_{0}=\hat{\Psi}_{4}(x_{0})=3410/3753$. We next show that the right
hand side as a function of $d\in[24\log 2,32\log 2]$ is decreasing: since
$d\to(2-v_{0}^{d-1})^{2}$ is increasing, it suffices to show that
$d\to(d-1)v_{0}^{d-2}$ is decreasing. Note that

$\frac{\mathrm{d}}{\mathrm{d}d}\Big{(}(d-1)v_{0}^{d-2}\Big{)}=v_{0}^{d-2}\Big{(}1-(d-1)\log\big{(}1/v_{0}\big{)}\Big{)}<0\iff
d>\frac{1}{\log(1/v_{0})}+1\,,$

and it can be verified that $24\log 2>16>1/\log(3753/3410)+1$ holds.
Therefore, for $k=4$, it follows that for $d_{0}=24\log 2$,

$\big{|}(\Psi_{d})^{\prime}(x)\big{|}\leq
3(d_{0}-1)\frac{v_{0}^{d_{0}-2}(2-v_{0})(1-v_{0})}{(2-v_{0}^{d_{0}-1})^{2}}\cdot\frac{1}{x_{0}}\,.$

The right hand side can be computed to arbitrary precision (e.g. by
Mathematica), it can be verified that
$3(d_{0}-1)\frac{v_{0}^{d_{0}-2}(2-v_{0})(1-v_{0})}{(2-v_{0}^{d_{0}-1})^{2}}\cdot\frac{1}{x_{0}}<0.9<1$.
This concludes the proof for the case $k=4$. ∎

In the proof of Lemma 3.3, we did not use the adjustment for
$d_{\textnormal{lbd}}(4)\equiv 16.7>24\log 2$. That is,
$\max_{\frac{1}{2}-\frac{1}{2^{4}}\leq
x\leq\frac{1}{2}}\big{|}(\Psi_{d})^{\prime}(x)\big{|}<1$ holds for
$d\in[24\log 2,32\log 2]$. The adjustment $d_{\textnormal{lbd}}(4)\equiv 16.7$
is needed for the following lemma, which guarantees the existence of the
solution to $\Psi_{d}(x)=x$.

######  Lemma 3.4.

$\Psi_{d}(\frac{1}{2}-\frac{1}{2^{k}})>\frac{1}{2}-\frac{1}{2^{k}}$ holds for
$k\geq 4$ for $d\in[d_{\textnormal{lbd}}(k),d_{\textnormal{ubd}}(k)]$.

###### Proof.

Let $v_{0}\equiv v_{0}(k)=\hat{\Psi}\left(\frac{1}{2}-\frac{1}{2^{k}}\right)$
as before. Then, from the definition of $\dot{\Psi},\hat{\Psi}$ in (1.12),
$\Psi_{d}(\frac{1}{2}-\frac{1}{2^{k}})>\frac{1}{2}-\frac{1}{2^{k}}$ is
equivalent to $v_{0}^{d-1}<\frac{4}{2^{k}+2}$, which we aim to show for $k\geq
4$. We start with the case $k\geq 5$. We have shown in (3.4) that
$v_{0}^{d-2}\leq 2^{-k}e^{\varepsilon_{k}}$, holds, and by an analogous proof,
$v_{0}^{d-1}\leq 2^{-k}e^{\beta_{k}}$ holds, where
$\beta_{k}\equiv\varepsilon_{k}-\frac{1}{2^{k-1}}\big{(}1-\frac{2(k-1)}{2^{k}}\big{)}$.
Thus, it suffices to show that

$e^{\beta_{k}}\left(1+\frac{1}{2^{k-1}}\right)<4\,,\quad\textnormal{where}\quad\beta_{k}\equiv\frac{2(k-1)k\log
2}{2^{k}}+\frac{4k\log 2+2}{2^{k}}\left(1-\frac{2(k-1)}{2^{k}}\right)\,.$

For $k=5$, $e^{\beta_{5}}(1+1/2^{4})$ can be computed to arbitrary precision
(e.g. by Mathematica), and it can be numerically verified that
$e^{\beta_{5}}(1+1/2^{4})<3.7$. Further, $k\to\beta_{k}$ is decreasing by
comparing $\beta_{k}$ and $\beta_{k+1}$, thus this concludes the proof for
$k\geq 5$.

Next, we consider the case $k=4$. Since $d\to v_{0}^{d-1}$ is maximized at
$d=d_{\textnormal{lbd}}(4)\equiv 16.7$, it suffices to show that
$v_{0}^{15.7}\leq\frac{2}{9}$ holds, where
$v_{0}\equiv\hat{\Psi}_{4}(1/2-1/2^{4})=3410/3753$. Since
$v_{0}^{15.7}=(3410/3753)^{15.7}$ can be computed to arbitrary precision (e.g.
by Mathematica), it can be checked that
$v_{0}^{15.7}=(3410/3753)^{15.7}<0.2221<\frac{2}{9}$ holds, so this concludes
the proof. ∎

###### Proof of Lemma 3.1.

By Lemma 3.4,
$\Psi_{d}(\frac{1}{2}-\frac{1}{2^{k}})>\frac{1}{2}-\frac{1}{2^{k}}$ holds for
$k\geq 4$. Note that $\Psi_{d}(1/2)<1/2$ holds since $\dot{\Psi}(x)<1/2$ holds
for any $x\geq 0$. Thus, since $x\to\Psi_{d}(x)$ is continuous and
differentiable, intermediate value theorem guarantees the existence of the
solution to $\Psi_{d}(x)=x$ for
$x\in[\frac{1}{2}-\frac{1}{2^{k}},\frac{1}{2}]$. Moreover,
$\big{|}(\Psi_{d})^{\prime}(x)\big{|}<1$ holds uniformly over
$x\in[\frac{1}{2}-\frac{1}{2^{k}},\frac{1}{2}]$ by Lemma 3.3, thus mean value
theorem guarantees the uniqueness of the solution to $\Psi_{d}(x)=x$ for
$x\in[\frac{1}{2}-\frac{1}{2^{k}},\frac{1}{2}]$. ∎

###  3.2 Proof of Lemma 3.2

Recall that $\boldsymbol{\prescript{\star}{}{\Phi}}(d)$ is defined in (1.2) as
$\boldsymbol{\prescript{\star}{}{\Phi}}(d)\equiv\Phi\big{(}d,x(k,d)\big{)}$,
where $x(k,d)\in[\frac{1}{2}-\frac{1}{2^{k}},\frac{1}{2}]$ is the solution to
$\Psi_{d}(x)=x$, and we defined the function $\Phi(d,x)$ by

$\Phi(d,x)\equiv\Phi_{k}(d,x):=-\log(1-x)-d(1-k^{-1}-d^{-1})\log(1-2x^{k})+(d-1)\log(1-x^{k-1})\,.$
(3.6)

To prove
$\boldsymbol{\prescript{\star}{}{\Phi}}\big{(}d_{\textnormal{lbd}}(k)\big{)}>0$
and
$\boldsymbol{\prescript{\star}{}{\Phi}}\big{(}d_{\textnormal{ubd}}(k)\big{)}<0$,
we show respectively in Lemmas 3.5 and 3.6 that
$\Phi\big{(}d_{\textnormal{lbd}}(k),x\big{)}>0$ and
$\Phi\big{(}d_{\textnormal{ubd}}(k),x\big{)}<0$ hold uniformly over
$x\in[\frac{1}{2}-\frac{1}{2^{k}},\frac{1}{2}]$.

######  Lemma 3.5.

For $k\geq 4$, $\Phi(d_{\textnormal{lbd}}(k),x)>0$ holds uniformly over
$x\in[\frac{1}{2}-\frac{1}{2^{k}},\frac{1}{2}]$.

###### Proof.

Note that rearranging $\Phi(d,x)$ gives

$\begin{split}\Phi(d,x)&=-\log(1-x)-d\big{(}(1-k^{-1})\log(1-2x^{k})-\log(1-x^{k-1})\big{)}+\log(1-2x^{k})-\log(1-x^{k-1})\\\
&\geq-\log(1-x)-d\big{(}(1-k^{-1})\log(1-2x^{k})-\log(1-x^{k-1})\big{)}\,,\end{split}$
(3.7)

where the inequality holds since $\log(1-2x^{k})\geq\log(1-x^{k-1})$ holds for
$x\in[0,1/2]$. Note that the first term in the right hand side
$x\to-\log(1-x)$ is convex, so the linear approximation at $x=1/2$ shows that
$-\log(1-x)\geq\log 2+2(x-1/2)$ holds. Further, the function
$x\to(1-k^{-1})\log(1-2x^{k})-\log(1-x^{k-1})$ is increasing since

$\frac{\mathrm{d}}{\mathrm{d}x}\Big{(}(1-k^{-1})\log(1-2x^{k})-\log(1-x^{k-1})\Big{)}=\frac{(k-1)x^{k-2}(1-2x)}{(1-2x^{k})(1-x^{k-1})}\geq
0\,.$

Thus, the right hand side in (3.7) for $d=d_{\textnormal{lbd}}(k)$ can further
lower bounded by

$\begin{split}\Phi\big{(}d_{\textnormal{lbd}}(k),x\big{)}&\geq\log
2+2\big{(}x-1/2\big{)}+\frac{d_{\textnormal{lbd}}(k)}{k}\cdot\log\big{(}1-2^{-k+1}\big{)}\\\
&\geq\log
2-2^{-k+1}+\frac{d_{\textnormal{lbd}}(k)}{k}\cdot\log\big{(}1-2^{-k+1}\big{)}=:F(k)\,,\end{split}$
(3.8)

where we used $x\geq 1/2-1/2^{k}$ in the last inequality. Using the inequality
$\log(1-a)\geq-a-\frac{a^{2}}{2}-\frac{a^{3}}{2}$ for
$a=2^{-k+1}\leq\frac{1}{8}$, we have that for $k\geq 5$ that

$F(k)=\log 2-2^{-k+1}+(2^{k-1}-2)\log
2\cdot\log(1-2^{-k+1})\geq\frac{1}{2^{k}}\left(3\log 2-2-\frac{6\log
2}{2^{k}}+\frac{8\log 2}{2^{2k}}\right).$

For $k\geq 6$, the right hand side above is positive since $3\log
2-2-\frac{3\log 2}{32}>0.01$, thus (3.8) shows that
$\Phi\big{(}d_{\textnormal{lbd}}(k),x\big{)}>0$ holds for $k\geq 6$ and
$x\in[\frac{1}{2}-\frac{1}{2^{k}},\frac{1}{2}]$. For $k\in\\{4,5\\}$, we can
explicitly calculate $F(k)$ by $F(4)\equiv\log
2-1/8+(16.7/4)\log\left(7/8\right)>0.01>0$, and $F(5)\equiv\log 2-1/16+14\log
2\cdot\log\left(15/16\right)>0.004>0$, thus (3.8) again concludes the proof
for $k\in\\{4,5\\}$.

∎

######  Lemma 3.6.

For $k\geq 4$, $\Phi\big{(}d_{\textnormal{ubd}}(k),x\big{)}<0$ holds uniformly
over $x\in[\frac{1}{2}-\frac{1}{2^{k}},\frac{1}{2}]$.

###### Proof.

We first claim that for $k\geq 5$, the function
$x\to\Phi\big{(}d_{\textnormal{ubd}}(k),x\big{)}$ is increasing for
$x\in[\frac{1}{2}-\frac{1}{2^{k}},\frac{1}{2}]$ and
$d_{\textnormal{ubd}}(k)\equiv 2^{k-1}k\log 2$. A direct calculation shows
that

$\begin{split}\frac{\partial\Phi}{\partial
x}\big{(}d_{\textnormal{ubd}}(k),x\big{)}&=\frac{1}{1-x}-(2^{k-1}k\log
2-1)(k-1)\cdot\frac{x^{k-2}(1-2x)}{(1-x^{k-1})(1-2x^{k})}-\frac{2x^{k-1}}{1-2x^{k}}\\\
&\geq\frac{1}{\frac{1}{2}+\frac{1}{2^{k}}}-(2^{k-1}k\log
2-1)(k-1)\cdot\frac{x^{k-2}(1-2x)}{(1-x^{k-1})(1-2x^{k})}-\frac{4}{2^{k}-2}\,,\end{split}$
(3.9)

where the inequality holds since $x\to(1-x)^{-1}$ increasing, so it is
minimized at $x=1/2+1/2^{k}$, and $x\to 2x^{k-1}/(1-2x^{k})$ is increasing, so
it is maximized at $x=1/2$. Further, it is straightforward to check that $x\to
x^{k-2}(1-2x)$ is decreasing for
$x\in[\frac{1}{2}-\frac{1}{2^{k}},\frac{1}{2}]$, thus it is maximized at
$x=1/2-1/2^{k}$. Also, $x\to(1-x^{k-1})(1-2x^{k})$ is minimized at $x=1/2$.
Thus, by plugging in these bounds, we can further bound

$\begin{split}\frac{\partial\Phi}{\partial
x}\big{(}d_{\textnormal{ubd}}(k),x\big{)}&\geq
2-\left(\frac{2}{2^{k-1}+1}+\frac{4}{2^{k}-2}+\frac{(2^{k-1}k\log
2-1)(k-1)}{2^{2k-3}}\cdot\left(1-\frac{1}{2^{k-1}}\right)^{k-4}\right)\\\
&\geq 2-\left(\frac{2}{2^{k-1}+1}+\frac{4}{2^{k}-2}+\frac{(2^{k-1}k\log
2-1)(k-1)}{2^{2k-3}}\right)=:2-G(k)\,.\end{split}$ (3.10)

Note that the function $k\to G(k)$ is increasing for $k\geq 5$. Furthermore,
using the bound $\log 2<0.7$, we can bound
$G(5)=\frac{2}{17}+\frac{2}{15}+\frac{80\log 2-1}{32}<1.97<2$. Therefore,
$\frac{\partial\Phi}{\partial x}\big{(}d_{\textnormal{ubd}}(k),x\big{)}>0$
holds for $k\geq 5$ and $x\in[\frac{1}{2}-\frac{1}{2^{k}},\frac{1}{2}]$, which
proves our first claim.

Consequently, for the case $k\geq 5$, it suffices to show that
$\Phi(2^{k-1}k\log 2,x)<0$ holds for $x=1/2$. A direct calculation gives

$\displaystyle\Phi\Big{(}2^{k-1}k\log 2,\frac{1}{2}\Big{)}=\log 2+2^{k-1}\log
2\cdot\log\Big{(}1-\frac{1}{2^{k-1}}\Big{)}<0\,,$ (3.11)

where the inequality holds since $\log(1-a)<-a$ holds for $a\in(0,1)$. This
concludes the proof for $k\geq 5$.

It remains to consider the case $k=4$. For $k=4$, we claim that
$x\to\Phi_{4}\big{(}d_{\textnormal{ubd}}(4),x)$ is convex in the interval
$x\in[\frac{7}{16},\frac{1}{2}]$. From the computation of
$\frac{\partial\Phi}{\partial x}\big{(}d_{\textnormal{ubd}}(k),x\big{)}$ in
(3.9), we can calculate the second derivative by

$\frac{\partial^{2}\Phi}{\partial
x^{2}}\big{(}d_{\textnormal{ubd}}(4),x)=\frac{\mathrm{d}}{\mathrm{d}x}\left(\frac{1}{1-x}-\frac{2x^{3}}{1-2x^{4}}\right)+3(32\log
2-1)\cdot\frac{\mathrm{d}}{\mathrm{d}x}\left(\frac{x^{2}(2x-1)}{(1-x^{3})(1-2x^{4})}\right)\,.$
(3.12)

The first term in the right hand side can be bounded by

$\frac{\mathrm{d}}{\mathrm{d}x}\left(\frac{1}{1-x}-\frac{2x^{3}}{1-2x^{4}}\right)=\frac{1}{(1-x)^{2}}-\frac{6x^{2}+4x^{6}}{(1-2x^{4})^{2}}>\frac{1}{(1-\frac{7}{16})^{2}}-\frac{6\left(\frac{1}{2}\right)^{2}+4\left(\frac{1}{2}\right)^{6}}{(1-2\left(\frac{1}{2}\right)^{4})^{2}}>0\,,$
(3.13)

where the final inequality is equivalent to $\frac{256}{81}-\frac{100}{49}>0$.
The second term can be calculated as

$\frac{\mathrm{d}}{\mathrm{d}x}\left(\frac{x^{2}(2x-1)}{(1-x^{3})(1-2x^{4})}\right)=\frac{x(-16x^{8}+10x^{7}+4x^{5}-4x^{4}-x^{3}+6x-2)}{(1-x^{3})^{2}(1-2x^{4})^{2}}\,.$

Note that by neglecting the terms $10x^{7}+4x^{5}$ above, we can lower bound

$-16x^{8}+10x^{7}+4x^{5}-4x^{4}-x^{3}+6x-2>6\cdot\frac{7}{16}-2-\left(\frac{1}{2}\right)^{3}-4\left(\frac{1}{2}\right)^{4}-16\left(\frac{1}{2}\right)^{8}>0\,,$

thus
$\frac{\mathrm{d}}{\mathrm{d}x}\left(\frac{x^{2}(2x-1)}{(1-x^{3})(1-2x^{4})}\right)>0$
holds for $x\in[\frac{7}{16},\frac{1}{2}]$ as well. Therefore, combining with
(3.12) and (3.13) finishes the proof of our claim that
$x\to\Phi_{4}\big{(}d_{\textnormal{ubd}}(4),x)$ is convex in the interval
$x\in[\frac{7}{16},\frac{1}{2}]$.

Thus, by convexity, $x\to\Phi_{4}\big{(}d_{\textnormal{ubd}}(4),x)$ is
maximized at the end points $x\in\\{7/16,1/2\\}$, and it suffices to show that
$\Phi_{4}\big{(}d_{\textnormal{ubd}}(4),7/16)<0$ and
$\Phi_{4}\big{(}d_{\textnormal{ubd}}(4),1/2)<0$. For $x=7/16$,
$\Phi_{4}\big{(}d_{\textnormal{ubd}}(4),7/16)$ can be computed to arbitrary
precision (e.g. by Mathematica), and it can be checked that
$\Phi_{4}\big{(}d_{\textnormal{ubd}}(4),7/16)<-0.08<0$. For $x=1/2$, (3.11)
shows that $\Phi_{4}\big{(}d_{\textnormal{ubd}}(4),1/2)<0$ holds. This
concludes the proof for the case $k=4$. ∎

###### Proof of Lemma 3.2.

By definition,
$\boldsymbol{\prescript{\star}{}{\Phi}}(d)=\Phi\big{(}d,x(k,d)\big{)}$ holds,
and $(d,x)\to\Phi(d,x)$ is clearly continuous. Thus, in order to show the
continuity of $\boldsymbol{\prescript{\star}{}{\Phi}}(\cdot)$, it suffices to
show that $d\to x(k,d)$ is continuous for any fixed $k\geq 4$. To that end,
note that the function $\psi(d,x):=\Psi_{d}(x)-x$ satisfies
$\frac{\partial\psi}{\partial x}<0$ by Lemma 3.3. Since $x(k,d)$ is defined to
be the root of $\psi(d,\cdot)$, this implies that $d\to x(k,d)$ is continuous
by the implicit function theorem. As a consequence, we conclude that
$d\to\boldsymbol{\prescript{\star}{}{\Phi}}(d)$ is continuous. Since
$\boldsymbol{\prescript{\star}{}{\Phi}}(d_{\textnormal{lbd}}(k))>0$ holds by
Lemma 3.5 and
$\boldsymbol{\prescript{\star}{}{\Phi}}(d_{\textnormal{ubd}}(k))<0$ holds by
Lemma 3.6, we conclude the proof. ∎

##  4 Proof of Proposition 1.7 for $k=3$

In this section, we prove Proposition 1.7 for $k=3$. Previous arguments for
$k\geq 4$ in Section 3 do not work because
$\boldsymbol{\prescript{\star}{}{\Phi}}$ is in fact, not well defined for all
$d$ in the interval $[6\log 2,12\log 2]$. To resolve this, we instead restrict
our attention to
$d\in[d_{\textnormal{lbd}}(3),d_{\textnormal{ubd}}(3)]\equiv[6.74,7.5]\subset[6\log
2,12\log 2]$. In Section 4.1 we show the following lemma which guarantees the
existence and the uniqueness of the bp fixed point for $k=3$.

######  Lemma 4.1.

For $k=3$,
$d\in[d_{\textnormal{lbd}}(3),d_{\textnormal{ubd}}(3)]\equiv[6.74,7.5]$, there
exists a unique solution to $\Psi_{d}(x)=x$ in the range
$x\in[\frac{1}{2}-\frac{1}{2^{3}},\frac{1}{2}]$.

By Lemma 4.1, the function $d\to\boldsymbol{\prescript{\star}{}{\Phi}}(d)$ is
well-defined. In Section 4.2, we prove Lemma 4.2 which guarantees that
$d_{\star}(3)$ is well-defined.

######  Lemma 4.2.

For $k=3$, the function $d\to\boldsymbol{\prescript{\star}{}{\Phi}}(d)$ is
continuous for
$d\in[d_{\textnormal{lbd}}(3),d_{\textnormal{ubd}}(3)]\equiv[6.74,7.5]$.
Further, $\boldsymbol{\prescript{\star}{}{\Phi}}(d_{\textnormal{lbd}}(3))>0$
and $\boldsymbol{\prescript{\star}{}{\Phi}}(d_{\textnormal{ubd}}(3))<0$ hold.

###### Proof of Proposition 1.7 for $k=3$.

This is immediate from Lemma 4.1 and Lemma 4.2. ∎

###  4.1 Proof of Lemma 4.1

Recall the variable bp recursion $\dot{\Psi}$ and the clause bp recursion
$\hat{\Psi}$ defined in (1.12). To prove the uniqueness of the bp fixed point,
we show that the bp recursion $\Psi_{d}\equiv\dot{\Psi}\circ\hat{\Psi}$ is a
contraction for $k=3.$

######  Lemma 4.3.

For $d\in[d_{\textnormal{lbd}}(3),d_{\textnormal{ubd}}(3)]\equiv[6.74,7.5]$,
$\big{|}(\Psi_{d})^{\prime}(x)\big{|}<1$ holds uniformly over
$x\in[\frac{1}{2}-\frac{1}{2^{3}},\frac{1}{2}]$.

###### Proof.

For $k=3$, a direct calculation gives

$(\Psi_{d})^{\prime}(x)=\frac{2(d-1)\left(\frac{1-2x^{2}}{1-x^{2}}\right)^{d-2}}{\left(2-\left(\frac{1-2x^{2}}{1-x^{2}}\right)^{d-1}\right)^{2}}\cdot\frac{x}{(1-x^{2})^{2}}\,.$

Using the inequality $\frac{1-2x^{2}}{1-x^{2}}<1-x^{2}$ in the denominator
above, to prove our goal $\big{|}(\Psi_{d})^{\prime}(x)\big{|}<1$, it suffices
to prove that for $d\in[6.74,7.5]$ and $x\in[7/8,1/2]$,

$2(d-1)\left(\frac{1-2x^{2}}{1-x^{2}}\right)^{d-2}x<\left(2-(1-x^{2})^{d-1}\right)^{2}\cdot(1-x^{2})^{2}\,,$

which rearranges to

$L(d,x):=\frac{\left(1-x^{2}\right)^{d}\left(\left(1-x^{2}\right)^{d-1}-2\right)^{2}}{\left(1-2x^{2}\right)^{d-2}}-2(d-1)x>0\,\quad\textnormal{for}\quad
d\in[6.74,7.5]\leavevmode\nobreak\ \leavevmode\nobreak\
\textnormal{and}\leavevmode\nobreak\ \leavevmode\nobreak\ x\in[7/8,1/2]\,.$
(4.1)

For the rest of the proof, we aim to show (4.1). We first claim that $x\to
L(d,x)$ is increasing in the regime of interest. The following observation is
useful to prove our claim: suppose we are given differentiable functions
$f(x),g(x)$, such that $f(x)\geq 0$, $g(x)\leq 1$, and $g(\cdot)$ is
decreasing, i.e. $g^{\prime}(x)\leq 0$. Then,

$\big{(}f(x)g(x)\big{)}^{\prime}=f^{\prime}(x)g(x)+f(x)g^{\prime}(x)\leq
f^{\prime}(x)\,.$ (4.2)

That is, if we multiply $f(\cdot)$ by a non-negative function by a decreasing
function that is less than $1$, denoted by $g(\cdot)$, then $(f\cdot
g)^{\prime}\leq f^{\prime}$. Using this observation for
$f(x)=\frac{\left(1-x^{2}\right)^{d}\left(\left(1-x^{2}\right)^{d-1}-2\right)^{2}}{\left(1-2x^{2}\right)^{d-2}}$
and $g(x)=\frac{(1-2x^{2})^{d-2}}{((1-x^{2})^{2})^{d-2}}$, which is less than
$1$ and decreasing, we have that

$\begin{split}\frac{\partial L}{\partial
x}(d,x)&\geq\frac{\mathrm{d}}{\mathrm{d}x}\Bigg{(}\frac{\left(\left(1-x^{2}\right)^{d-1}-2\right)^{2}}{\left(1-x^{2}\right)^{d-4}}\Bigg{)}-2(d-1)\\\
&=x\cdot\left(\frac{8(d-4)}{(1-x^{2})^{d-3}}+24(1-x^{2})^{2}-2(d+2)(1-x^{2})^{d+1}-\frac{2(d-1)}{x}\right)\,.\end{split}$
(4.3)

Abbreviating $d_{\textnormal{lbd}}\equiv 6.74,d_{\textnormal{ubd}}\equiv 7.5$,
and $x_{\textnormal{lbd}}\equiv 3/8,x_{\textnormal{ubd}}\equiv 1/2$, we
crudely bound

$\begin{split}&\frac{8(d-4)}{(1-x^{2})^{d-3}}+24(1-x^{2})^{2}-2(d+2)(1-x^{2})^{d+1}-\frac{2(d-1)}{x}\\\
&\geq\frac{8(d_{\textnormal{lbd}}-4)}{(1-x_{\textnormal{lbd}}^{2})^{d_{\textnormal{lbd}}-3}}+24(1-x_{\textnormal{ubd}}^{2})^{2}-2(d_{\textnormal{ubd}}+2)(1-x_{\textnormal{lbd}}^{2})^{d_{\textnormal{lbd}}+1}-\frac{2(d_{\textnormal{ubd}}-1)}{x_{\textnormal{lbd}}}\,.\end{split}$

The right hand side above is a combination of fractions and powers of the
numbers $6.74,7.5,3/8,1/2$, thus can be computed up to arbitrary precision
(e.g. by Mathematica), and it can be checked that the right hand side above is
greater than $10$. Therefore, combining with (4.3), this finishes the proof of
our claim that $x\to L(d,x)$ is increasing in the regime of interest.

Since $L(d,\cdot)$ is increasing, to prove our goal (4.1), it remains to prove
that $L(d,3/8)>0$ for $d\in[6.74,7.5]$. By a direct calculation, we have

$L\Big{(}d\,,\,\frac{3}{8}\Big{)}=\frac{\left(55/64\right)^{3d-2}}{\left(23/32\right)^{d-2}}-\frac{4\left(55/64\right)^{2d-1}}{\left(23/32\right)^{d-2}}+\frac{4(55/64)^{d}}{(23/32)^{d-2}}-\frac{3(d-1)}{4}\,.$
(4.4)

We next claim that the $d\to L(d,3/8)$ is convex for any $d>0$. Recalling that
$\frac{\mathrm{d}^{2}\gamma^{d}}{\mathrm{d}d^{2}}=\gamma^{d}(\log\gamma)^{2}$
for $\gamma>0$, we can lower bound the second derivative by neglecting the
first term in the right hand side:

$\frac{\mathrm{d}^{2}L}{\mathrm{d}d^{2}}\Big{(}d\,,\,\frac{3}{8}\Big{)}\geq
4\left(\frac{32}{23}\right)^{2}\left(\frac{(55/64)^{d}}{(23/32)^{d}}\left(\log\left(\frac{55/64}{23/32}\right)\right)^{2}-\frac{\left(55/64\right)^{2d}}{\left(23/32\right)^{d}}\left(\log\left(\frac{(55/64)^{2}}{23/32}\right)\right)^{2}\cdot\frac{64}{55}\right)$

It can be numerically verified (e.g. by Mathematica) that
$\left(\log\left(\frac{55/64}{23/32}\right)\right)^{2}>0.01>\left(\log\left(\frac{(55/64)^{2}}{23/32}\right)\right)^{2}\cdot\frac{64}{55}$.
Further, we have
$\frac{(55/64)^{d}}{(23/32)^{d}}>\frac{\left(55/64\right)^{2d}}{\left(23/32\right)^{d}}$.
Thus, the inequality above proves our claim that $d\to L(d,3/8)$ is convex for
any $d>0$.

Now, since $L(d,3/8)$ in (4.4) can be computed to arbitrary precision (e.g. by
Mathematica), it can be numerically verified that $L(6.74,3/8)>0.001>0$ while
$L(6,3/8)<-0.2<0$ holds. Therefore, $L(d,3/8)>0$ holds for $d>6.74$ since
$L(\cdot,3/8)$ is convex. Since we have shown that $L(d,\cdot)$ is increasing,
this concludes the proof our goal (4.1). ∎

######  Lemma 4.4.

For $k=3$ and
$d\in[d_{\textnormal{lbd}}(3),d_{\textnormal{ubd}}(3)]\equiv[6.74,7.5]$,
$\Psi_{d}(\frac{1}{2}-\frac{1}{2^{3}})>\frac{1}{2}-\frac{1}{2^{3}}$ holds.

###### Proof.

By a direct calculation, we have
$\Psi_{d}(3/8)=\big{(}1-(46/55)^{d-1}\big{)}/\big{(}2-(46/55)^{d-1}\big{)}$,
thus $\Psi_{d}(3/8)>3/8$ is equivalent to
$\left(\frac{55}{46}\right)^{d-1}>\frac{5}{2}$. Since
$d\to\left(\frac{55}{46}\right)^{d-1}$ is increasing, it suffices to check
this for $d=6.74$. It can be checked numerically (e.g. by Mathematica) that
$\left(\frac{55}{46}\right)^{5.74}>2.7$, thus $\Psi_{d}(3/8)>3/8$ holds for
any $d\in[6.74,7.5]$. ∎

###### Proof of Lemma 4.1.

By Lemma 4.4,
$\Psi_{d}(\frac{1}{2}-\frac{1}{2^{3}})>\frac{1}{2}-\frac{1}{2^{3}}$ holds.
Note that $\Psi_{d}(1/2)<1/2$ holds since $\dot{\Psi}(x)<1/2$ holds for any
$x\geq 0$. Thus, since $x\to\Psi_{d}(x)$ is continuous and differentiable,
intermediate value theorem guarantees the existence of the solution to
$\Psi_{d}(x)=x$ for $x\in[\frac{1}{2}-\frac{1}{2^{3}},\frac{1}{2}]$. Moreover,
$\big{|}(\Psi_{d})^{\prime}(x)\big{|}<1$ holds uniformly over
$x\in[\frac{1}{2}-\frac{1}{2^{3}},\frac{1}{2}]$ by Lemma 4.3, thus mean value
theorem guarantees the uniqueness of the solution to $\Psi_{d}(x)=x$ for
$x\in[\frac{1}{2}-\frac{1}{2^{3}},\frac{1}{2}]$. ∎

###  4.2 Proof of Lemma 4.2

For $k\geq 4$, we have proven
$\boldsymbol{\prescript{\star}{}{\Phi}}\big{(}d_{\textnormal{lbd}}(k)\big{)}>0$
by showing that $\Phi\big{(}d_{\textnormal{lbd}}(k),x\big{)}$, defined in
(3.6), is uniformly positive for
$x\in[\frac{1}{2}-\frac{1}{2^{k}},\frac{1}{2}]$ in Lemma 3.4. Unfortunately,
the same does not hold for $k=3$. That is, it is not true for $k=3$ that
$\Phi(d_{\textnormal{lbd}}(3),x)$ is uniformly positive for
$x\in[\frac{1}{2}-\frac{1}{2^{3}},\frac{1}{2}]$. Instead, we prove
$\boldsymbol{\prescript{\star}{}{\Phi}}(6.74)>0$ by proving a refined
estimates for $x\equiv x(3,6.74)$, the solution to (1.1).

######  Lemma 4.5.

For $k=3$, we have $\boldsymbol{\prescript{\star}{}{\Phi}}(6.74)>0$.

###### Proof.

By Lemma 4.1, there exists a unique solution $x_{\circ}=x(3,6.74)$ to
$\Psi_{d}(x)=x$ for $k=3$ and $d=6.74$. By the uniqueness guaranteed by Lemma
4.3, if there exists $a,b\in[3/8,1/2],a<b$ such that $\Psi_{d}(a)>a$ and
$\Psi_{d}(b)<b$, then $x_{\circ}\in[a,b]$ holds. By taking $a=0.4464$ and
$b=0.45$, it can be numerically verified that $\Psi_{6.74}(0.4464)>0.44645$
and $\Psi_{6.74}(0.45)<0.449$ holds, thus we have $x_{\circ}\in[0.4464,0.45]$.

We now prove that for $k=3$ and $d=6.74$, the function $x\to\Phi(6.74,x)$ is
increasing for $x\in[0.44,0.45]$, where $\Phi$ is defined in (3.6). By a
direct calculation,

$\displaystyle\Phi(6.74,x)=-\log(1-x)-\frac{262}{75}\log(1-2x^{3})+\frac{287}{50}\log(1-x^{2})\,.$

Differentiating in $x$ gives that for $x\in[0.44,0.45]$

$\begin{split}\frac{\partial\Phi}{\partial
x}(6.74,x)&=\frac{1}{1-x}+\frac{524}{25}\cdot\frac{x^{2}}{1-2x^{3}}-\frac{287}{25}\cdot\frac{x}{1-x^{2}}\\\
&\geq\frac{1}{1-0.44}+\frac{524}{25}\cdot\frac{(0.44)^{2}}{1-2(0.44)^{3}}-\frac{287}{25}\cdot\frac{0.45}{1-(0.45)^{2}}>0.1\,,\end{split}$

thus $x\to\Phi(6.74,x)$ is increasing for $x\in[0.44,0.45]$.

As a consequence, it follows that
$\boldsymbol{\prescript{\star}{}{\Phi}}(6.74)\geq\inf_{x\in[0.4464,0.45]}\Phi(6.74,x)=\Phi(6.74,0.4464)$
holds. Further, $\Phi(6.74,0.4464)$ can be calculated up to arbitrary
precision (e.g. by Mathematica), and it can be checked that
$\Phi(6.74,0.4464)>4\cdot 10^{-5}>0$, which concludes the proof. ∎

To show that $\boldsymbol{\prescript{\star}{}{\Phi}}(7.5)>0$ holds for $k=3$,
we use a similar strategy as in the proof of Lemma 4.5.

######  Lemma 4.6.

For $k=3$, we have $\boldsymbol{\prescript{\star}{}{\Phi}}(7.5)<0$ holds.

###### Proof.

Let $x_{\circ}^{\prime}\equiv x(3,7.5)$ be the unique solution to
$\Psi_{d}(x)=x$ for $k=3$ and $d=7.5$ (cf. Lemma 4.1). By taking $a=0.46$ and
$b=0.48$, it can be numerically verified that $\Psi_{7.5}(a)<a$ and
$\Psi_{7.5}(b)>b$ holds, thus by uniqueness, we have
$x_{\circ}^{\prime}\in[0.46,0.48]$.

We now prove that for $k=3$ and $d=7.5$, the function $x\to\Phi(7.5,x)$ is
increasing for $x\in[0.46,0.48]$. By definition of $\Phi$ in (3.6), we have

$\displaystyle\boldsymbol{\prescript{\star}{}{\Phi}}(7.5)=-\log(1-x)-4\log(1-2x^{3})+6.5\log(1-x^{2})\,.$

Differentiating in $x$ gives that for $x\in[0.46,0.48]$

$\begin{split}\frac{\partial\Phi}{\partial
x}(6.74,x)&=\frac{1}{1-x}+\frac{24x^{2}}{1-2x^{3}}-\frac{13x}{1-x^{2}}=-\frac{2x^{3}-24x^{2}+12x-1}{(x-1)(x+1)(2x^{3}-1)}\\\
&\geq\frac{1}{1-0.46}+\frac{24\cdot(0.46)^{2}}{1-2(0.46)^{3}}-\frac{13\cdot
0.48}{1-(0.48)^{2}}>0.04>0\,,\end{split}$

thus $x\to\Phi(7.5,x)$ is increasing for $x\in[0.46,0.48]$.

Consequently, it follows that
$\boldsymbol{\prescript{\star}{}{\Phi}}(7.5)\leq\sup_{x\in[0.46,0.48]}\Phi(7.5,x)=\Phi(7.5,0.48)$.
Further, $\Phi(7.5,0.48)$ can be calculated up to arbitrary precision (e.g. by
Mathematica), and the inequality $\Phi(7.5,0.48)<-0.04<0$ can be checked,
which concludes the proof. ∎

###### Proof of Lemma 4.2.

By definition,
$\boldsymbol{\prescript{\star}{}{\Phi}}(d)=\Phi\big{(}d,x(3,d)\big{)}$ holds,
where $x(3,d)$ is solution to (1.1). Since $(d,x)\to\Phi(d,x)$ is continuous,
to prove the continuity of $\boldsymbol{\prescript{\star}{}{\Phi}}(\cdot)$, it
suffices to show that $d\to x(3,d)$ is continuous. Note that the function
$\psi(d,x):=\Psi_{d}(x)-x$ satisfies $\frac{\partial\psi}{\partial x}<0$ by
Lemma 4.3. Since $x(3,d)$ is defined to be the root of $\psi(d,\cdot)$, this
implies that $d\to x(3,d)$ is continuous by the implicit function theorem.
Hence, we conclude that $d\to\boldsymbol{\prescript{\star}{}{\Phi}}(d)$ is
continuous. Since
$\boldsymbol{\prescript{\star}{}{\Phi}}(d_{\textnormal{lbd}}(3))>0$ holds by
Lemma 4.5 and
$\boldsymbol{\prescript{\star}{}{\Phi}}(d_{\textnormal{ubd}}(3))<0$ holds by
Lemma 4.6, we conclude the proof. ∎

## Acknowledgements

We thank the MIT PRIMES program and its organizers Pavel Etingof, Slava
Gerovitch, and Tanya Khovanova for making this possible. Y.S. thanks Elchanan
Mossel, Allan Sly, and Nike Sun for encouraging feedbacks. Y.S. is supported
by Simons-NSF Collaboration on Deep Learning NSF DMS-2031883 and Vannevar Bush
Faculty Fellowship award ONR-N00014-20-1-2826.

## References

  * [AB88] N. Alon and Z. Bregman, _Every 8-uniform 8-regular hypergraph is 2-colorable_ , Graphs and Combinatorics 4 (1988), no. 1, 303–306.
  * [ACIM01] Dimitris Achlioptas, Arthur Chtcherba, Gabriel Istrate, and Cristopher Moore, _The phase transition in 1-in- $k$ SAT and NAE 3-sat_, Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Philadelphia, PA, USA), SODA ’01, Society for Industrial and Applied Mathematics, 2001, pp. 721–722.
  * [ACOG22] Peter Ayre, Amin Coja-Oghlan, and Catherine Greenhill, _Lower bounds on the chromatic number of random graphs_ , Combinatorica 42 (2022), no. 5, 617–658.
  * [ACOGM20] Peter Ayre, Amin Coja-Oghlan, Pu Gao, and Noëla Müller, _The satisfiability threshold for random linear equations_ , Combinatorica 40 (2020), no. 2, 179–235.
  * [AM02] Dimitris Achlioptas and Cristopher Moore, _On the 2-colorability of random hypergraphs_ , Randomization and Approximation Techniques in Computer Science (Berlin, Heidelberg) (José D. P. Rolim and Salil Vadhan, eds.), Springer Berlin Heidelberg, 2002, pp. 78–90.
  * [AM06] , _Random $k$-SAT: two moments suffice to cross a sharp threshold_, SIAM J. Comput. 36 (2006), no. 3, 740–762. MR 2263010
  * [AN05] Dimitris Achlioptas and Assaf Naor, _The two possible values of the chromatic number of a random graph_ , Ann. of Math. (2) 162 (2005), no. 3, 1335–1351. MR 2179732
  * [ANP05] Dimitris Achlioptas, Assaf Naor, and Yuval Peres, _Rigorous location of phase transitions in hard optimization problems_ , Nature 435 (2005), no. 7043, 759–764.
  * [AP04] Dimitris Achlioptas and Yuval Peres, _The threshold for random $k$-SAT is $2^{k}\log 2-O(k)$_, J. Amer. Math. Soc. 17 (2004), no. 4, 947–973. MR 2083472
  * [BBC+01] Béla Bollobás, Christian Borgs, Jennifer T. Chayes, Jeong Han Kim, and David B. Wilson, _The scaling window of the 2-SAT transition_ , Random Structures Algorithms 18 (2001), no. 3, 201–256. MR 1824274
  * [BCO16] Victor Bapst and Amin Coja-Oghlan, _The condensation phase transition in the regular $k$-SAT model_, Approximation, randomization, and combinatorial optimization. Algorithms and techniques, LIPIcs. Leibniz Int. Proc. Inform., vol. 60, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016, pp. Art. No. 22, 18. MR 3566764
  * [BCOH+16] Victor Bapst, Amin Coja-Oghlan, Samuel Hetterich, Felicia Raß mann, and Dan Vilenchik, _The condensation phase transition in random graph coloring_ , Comm. Math. Phys. 341 (2016), no. 2, 543–606. MR 3440196
  * [Bor17] A. A. Borovkov, _Generalization and refinement of the integro-local stone theorem for sums of random vectors_ , Theory of Probability & Its Applications 61 (2017), no. 4, 590–612.
  * [CO13] Amin Coja-Oghlan, _Upper-bounding the $k$-colorability threshold by counting covers_, Electron. J. Combin. 20 (2013), no. 3, Paper 32, 28\. MR 3104530
  * [COEH16] Amin Coja-Oghlan, Charilaos Efthymiou, and Samuel Hetterich, _On the chromatic number of random regular graphs_ , J. Combin. Theory Ser. B 116 (2016), 367–439. MR 3425250
  * [COKPZ18] Amin Coja-Oghlan, Florent Krz̧akała, Will Perkins, and Lenka Zdeborová, _Information-theoretic thresholds from the cavity method_ , Adv. Math. 333 (2018), 694–795. MR 3818090
  * [COP12] Amin Coja-Oghlan and Konstantinos Panagiotou, _Catching the $k$-NAESAT threshold [extended abstract]_, STOC’12—Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 899–907. MR 2961553
  * [COP13] , _Going after the k-sat threshold_ , Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC ’13, Association for Computing Machinery, 2013, p. 705–714.
  * [COP16] , _The asymptotic $k$-SAT threshold_, Adv. Math. 288 (2016), 985–1068. MR 3436404
  * [COP19] Amin Coja-Oghlan and Will Perkins, _Spin systems on Bethe lattices_ , Communications in Mathematical Physics 372 (2019), no. 2, 441–523.
  * [COV13] Amin Coja-Oghlan and Dan Vilenchik, _Chasing the $k$-colorability threshold_, 2013 IEEE 54th Annual Symposium on Foundations of Computer Science—FOCS ’13, IEEE Computer Soc., Los Alamitos, CA, 2013, pp. 380–389. MR 3246240
  * [COZ12] Amin Coja-Oghlan and Lenka Zdeborová, _The condensation transition in random hypergraph 2-coloring_ , Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’12, ACM, New York, 2012, pp. 241–250. MR 3205212
  * [CR92] V. Chvatal and B. Reed, _Mick gets some (the odds are on his side) (satisfiability)_ , Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (Washington, DC, USA), SFCS ’92, IEEE Computer Society, 1992, pp. 620–627.
  * [DFG15] Martin Dyer, Alan Frieze, and Catherine Greenhill, _On the chromatic number of a random hypergraph_ , Journal of Combinatorial Theory, Series B 113 (2015), 68–122.
  * [DGM+10] Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, and Michael Rink, _Tight thresholds for cuckoo hashing via XORSAT_ , Automata, Languages and Programming (Berlin, Heidelberg) (Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis, eds.), Springer Berlin Heidelberg, 2010, pp. 213–225.
  * [DM02] Olivier Dubois and Jacques Mandler, _The 3-XORSAT threshold_ , Proceedings of the 43rd Symposium on Foundations of Computer Science (Washington, DC, USA), FOCS ’02, IEEE Computer Society, 2002, pp. 769–778.
  * [DRZ08] L. Dall’Asta, A. Ramezanpour, and R. Zecchina, _Entropy landscape and non-gibbs solutions in constraint satisfaction problems_ , Physical Review E 77 (2008), no. 3.
  * [DSS14] Jian Ding, Allan Sly, and Nike Sun, _Satisfiability threshold for random regular nae-sat_ , Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC ’14, Association for Computing Machinery, 2014, p. 814–822.
  * [DSS15] , _Proof of the satisfiability conjecture for large k_ , Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC ’15, ACM, 2015, pp. 59–68.
  * [DSS16a] , _Maximum independent sets on random regular graphs_ , Acta Math. 217 (2016), no. 2, 263–340. MR 3689942
  * [DSS16b] , _Satisfiability threshold for random regular NAE-SAT_ , Commun. Math. Phys. 341 (2016), no. 2, 435–489.
  * [DSS22] Jian Ding, Allan Sly, and Nike Sun, _Proof of the satisfiability conjecture for large $k$_, Annals of Mathematics 196 (2022), no. 1, 1 – 388.
  * [DZ10] Amir Dembo and Ofer Zeitouni, _Large deviations techniques and applications_ , Stochastic Modelling and Applied Probability, vol. 38, Springer-Verlag, Berlin, 2010. MR 2571413
  * [FL03] Silvio Franz and Michele Leone, _Replica bounds for optimization problems and diluted spin systems_ , Journal of Statistical Physics 111 (2003), no. 3, 535–564.
  * [GP23] Yuzhou Gu and Yury Polyanskiy, _Uniqueness of bp fixed point for the potts model and applications to community detection_ , arXiv preprint, arXiv:2303.14688 (2023).
  * [Gue03] Francesco Guerra, _Broken replica symmetry bounds in the mean field spin glass model_ , Communications in Mathematical Physics 233 (2003), no. 1, 1–12.
  * [HY13] Michael A. Henning and Anders Yeo, _2-colorings in k-regular k-uniform hypergraphs_ , European Journal of Combinatorics 34 (2013), no. 7, 1192–1202.
  * [HY18] , _Not-all-equal 3-sat and 2-colorings of 4-regular 4-uniform hypergraphs_ , Discrete Mathematics 341 (2018), no. 8, 2285–2292.
  * [JLR00] Svante Janson, Tomasz Luczak, and Andrzej Rucinski, _Random graphs_ , Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1782847
  * [Kar72] Richard M. Karp, _Reducibility among combinatorial problems_ , pp. 85–103, Springer US, Boston, MA, 1972.
  * [KKKS98] Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, and Yannis C. Stamatiou, _Approximating the unsatisfiability threshold of random formulas_ , Random Structures Algorithms 12 (1998), no. 3, 253–269. MR 1635256
  * [KMRT+07] Florent Krz̧akała, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborová, _Gibbs states and the set of solutions of random constraint satisfaction problems_ , Proceedings of the National Academy of Sciences 104 (2007), no. 25, 10318–10323.
  * [MM09] Marc Mézard and Andrea Montanari, _Information, physics, and computation_ , Oxford Graduate Texts, Oxford University Press, Oxford, 2009. MR 2518205
  * [MMZ06] Stephan Mertens, Marc Mézard, and Riccardo Zecchina, _Threshold values of random k-sat from the cavity method_ , Random Structures & Algorithms 28 (2006), no. 3, 340–373.
  * [MPZ02] M. Mézard, G. Parisi, and R. Zecchina, _Analytic and algorithmic solution of random satisfiability problems_ , Science 297 (2002), no. 5582, 812–815.
  * [MRSY19] Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan, _The generalization error of max-margin linear classifiers: Benign overfitting and high-dimensional asymptotics in the overparametrized regime_ , arXiv:1911.01544 (2019).
  * [NSS20] Danny Nam, Allan Sly, and Youngtak Sohn, _One-step replica symmetry breaking of random regular NAE-SAT I_ , arXiv preprint, arXiv:2011.14270 (2020).
  * [NSS21] , _One-step replica symmetry breaking of random regular NAE-SAT II_ , arXiv preprint, arXiv:2112.00152 (2021).
  * [NSS22] , _One-step replica symmetry breaking of random regular nae-sat_ , 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 2022, pp. 310–318.
  * [PS16] Boris Pittel and Gregory B. Sorkin, _The satisfiability threshold for $k$-XORSAT_, Combin. Probab. Comput. 25 (2016), no. 2, 236–268. MR 3455676
  * [PT04] Dmitry Panchenko and Michel Talagrand, _Bounds for diluted mean-fields spin glass models_ , Probability Theory and Related Fields 130 (2004), no. 3, 319–336.
  * [Sey74] P. D. Seymour, _On the two-coloring of hypergraphs_ , The Quarterly Journal of Mathematics 25 (1974), no. 1, 303–311.
  * [SS23] Allan Sly and Youngtak Sohn, _Local geometry of NAE-SAT solutions in the condensation regime_ , arXiv preprint, arXiv:2305.17334 (2023).
  * [SSZ16] Allan Sly, Nike Sun, and Yumeng Zhang, _The number of solutions for random regular NAE-SAT_ , Proceedings of the 57th Symposium on Foundations of Computer Science, FOCS ’16, 2016, pp. 724–731.
  * [SSZ22] , _The number of solutions for random regular NAE-SAT_ , Probability Theory and Related Fields 182 (2022), no. 1-2, 1–109.
  * [ST03] Mariya Shcherbina and Brunello Tirozzi, _Rigorous solution of the Gardner problem_ , Communications in Mathematical Physics 234 (2003), no. 3, 383–422.
  * [Tal10] Michel Talagrand, _Mean field models for spin glasses: Volume i_ , Springer-Verlag, Berlin, 2010.
  * [YP22] Qian Yu and Yury Polyanskiy, _Ising model on locally tree-like graphs: Uniqueness of solutions to cavity equations_ , arXiv preprint, arXiv:2211.15242 (2022).