Satisfiability threshold for random regular NAE-SAT

Introduction

Given a Boolean formula in conjunctive normal form (i.e., expressed as an and of ors), a not-all-equal-sat (nae-sat) solution is an assignment $\underline{\smash{x}}$ of literals to variables such that both $\underline{\smash{x}}$ and its negation $\neg\underline{\smash{x}}$ evaluate to true. A $k$-nae-sat problem is one in which each clause involves exactly $k$ literals.

The $k$-nae-sat problem is a symmetrized version of $k$-sat. A major direction of research has concerned the large-system limit of random problem instances, seeking to establish typical behavior and phase transitions. In particular, much effort has been directed towards locating the satisfiability transition: the critical density $\alpha_{\star}$ where solutions cease to exist .

In this paper we consider random $d$-regular $k$-nae-sat, in which each variable is involved in exactly $d$ clauses, and clause literals are chosen uniformly at random. We establish the following sharp satisfiability threshold, the first of its kind among this class of csps:

For $k\geq k_{0}$ there is a threshold $d_{\star}\equiv d_{\star}(k)$, given by the largest zero of the explicit function (1), such that the probability for a random $d$-regular $k$-nae-sat instance to be solvable tends to one for $d<d_{\star}$, and tends to zero for $d>d_{\star}$.

The threshold $d_{\star}$ is given by the largest zero of the function

where $q=q(d)$ is the unique solution in the interval $[1-2^{-k},1]$ of

We will find (see Propn. 3.11) that ${}^{\star}\bm{\Phi}$ is decreasing with a unique zero on the interval $(2^{k-1}-2)k\log 2\leq d\leq 2^{k-1}k\log 2$.

As the threshold is given by the root of an equation, it is possible for $d_{\star}$ to be integer-valued, though we have no reason to believe that this ever occurs. Nevertheless, we also address this hypothetical possibility by showing that if $d=d_{\star}$ then the probability for the nae-sat instance to be solvable is asymptotically bounded away from both zero and one. This completes the characterization of the satisfiability transition.

The methods developed in this paper offer a new approach to tackling other problems in the same class and establishing exact thresholds. Indeed, in a companion paper we consider the maximum independent set problem on random regular graphs, where we determine the explicit threshold, and furthermore show tight concentration of the maximum independent set size about the threshold value.

Previous work on the satisfiability transition has identified sharp thresholds in models not exhibiting condensation, e.g. xor-sat . The $2$-sat satisfiability transition is also much simpler, and can be identified by a branching process argument . See also for detailed discussions of these problems. Previous work on nae-sat has centered on the Erdős–Rényi version in which variables are included in clauses independently at random, with a series of improving bounds on the satisfiability transition .

Shortly prior to the posting of this paper, A. Coja-Oghlan posted a paper on a different symmetrization of regular $k$-sat in which a $2$-clause joins each consecutive pair of variables, forcing them to take opposite literals. While not establishing a satisfiability threshold, his paper establishes a 1rsb-type formula for the existence of solutions that satisfy all but $o(n)$ clauses. His approach of modeling clusters of configurations is similar to our own.

We hereafter write $G\equiv\mathcal{G}_{n,d,k}$ to indicate that $G$ is chosen according to the configuration model for uniformly random $(d,k)$-regular bipartite (multi-)graphs with $n$ degree-$d$ vertices, with $\underline{\smash{L}}$ a uniformly random literal assignment.

2. Outline of proof

It is most natural to apply the moment method with the nae-sat partition function

For fixed $k$ the rate function $\Phi_{k}(d)$ is clearly decreasing in $d$, with unique zero at

In §2 we will see that a rather straightforward application of the second moment method on $Z$ gives the following

We establish this by the second moment method applied to the partition function $\bm{Z}$ of the frozen configurations. In §3-5 we prove

The proof of Thm. 2 comprises a large portion of the present paper. The first moment is addressed in §3, where we identify the exact local neighborhood profile that gives the maximal contribution to the expectation. This is done by a Bethe variational principle which relates stationary points of the rate function to fixed points of certain tree recursions. A major technical difficulty is the high dimensionality of the maximization problem, and the possibility of multiple stationary points which must be ruled out. This is done by delicate a priori estimates which allow us to reduce the dimensionality by certain symmetry conditions.

The second moment can be understood in the same framework by regarding it as the first moment of the pair model, but clearly the dimensionality is substantially increased. We show in §4 that the dominant contribution comes from two local maximizers: one corresponding to pairs whose overlap distribution looks like a product measure, and the other corresponding to pairs which are perfectly correlated — in each case, with both marginals given by the first moment maximizer. The results of §3 and 4 control the moments up to polynomial prefactors, which are determined in §5 by establishing negative-definiteness of the Hessians for the first- and second-moment rate functions at their maximizers.

Thm. 3 is proved in §6 by a variance reduction argument. This issue occurs commonly in applications of the second moment method, and is often dealt with by a somewhat standard machinery known as the subgraph conditioning method (see ) which “explains” the variance in terms of the short cycles in the graph. Applying this method is technically demanding, and seems to us intractable in our models due to the large number of variables.

We develop instead a novel approach of taking a certain log-transform of the partition function, and bounding the incremental fluctuations of its Doob martingale with respect to the edge-revealing filtration; each increment amounts to the effect of adding a clause. We control the variance by discrete Fourier analysis applied on the spins at the boundary of a large local neighborhood of the added clause, and we show that the main contribution comes from the degree-two Fourier coefficients which correspond to the formation of short cycles in the graph.

3. Notation

Acknowledgements

We thank Amir Dembo, Elchanan Mossel, Andrea Montanari, and David Wilson for helpful conversations.

Satisfying assignments

where $\gamma_{0}\equiv\gamma_{0}(\alpha)\equiv 1-\alpha^{k}-(1-\alpha)^{k}$. Thus we conclude

For fixed $\alpha$, $\mathbf{a}$ is strictly concave in $\gamma$ with second derivative $-[\gamma(1-\gamma)]^{-1}\leq-4$, and is uniquely maximized at $\gamma^{\star}(\alpha)=\gamma_{0}(1-\vartheta)/(1-\vartheta\gamma_{0})$ with optimal value

It is straightforward to calculate that for $k^{-1}(\log k)^{2}\leq\alpha\leq 1-k^{-1}(\log k)^{2}$,

so clearly $\alpha=\mathchoice{\nicefrac{{1}}{{2}}}{\smash{\nicefrac{{1}}{{2}}}}{\nicefrac{{1}}{{2}}}{\nicefrac{{1}}{{2}}}$ is the unique maximizer on this interval. For $0\leq\alpha\leq\mathchoice{\nicefrac{{1}}{{2}}}{\smash{\nicefrac{{1}}{{2}}}}{\nicefrac{{1}}{{2}}}{\nicefrac{{1}}{{2}}}$, $H(\alpha)$ is increasing while $\alpha^{k}+(1-\alpha)^{k}$ is decreasing, and we use this to bound

For $\alpha\leq k^{-3/2}$ we have $(1-\alpha)^{k}=1-k\alpha+O(k^{1/2}\alpha)$, therefore

Lastly, recalling $H(x)+x\log c\leq\log(1+c)\leq c$ gives

where the inner sum is taken over probability measures $\nu$ on $\{0,\ldots,k\}$ such that $m\nu$ is integer-valued. By Stirling’s approximation,

where $\mathbf{b}(\alpha,\nu)\equiv H(\alpha)-(d/k)\sum_{j}\nu_{j}\log[\nu_{j}/p_{j}(\alpha)]$ is strictly concave in $(\alpha,\nu)$, and the correction term $\mathscr{P}(\alpha,\nu)$ is $n^{O(1)}$ in general, and is $\asymp_{k}n^{(k+1)/2}$ for $\nu$ satisfying $\max_{j}1/\nu_{j}\lesssim_{k}1$. It is easily seen that this is indeed satisfied by $\operatorname{arg\,max}_{\nu}\mathbf{b}(\alpha,\nu)$ for $\mathchoice{\nicefrac{{1}}{{4}}}{\smash{\nicefrac{{1}}{{4}}}}{\nicefrac{{1}}{{4}}}{\nicefrac{{1}}{{4}}}\leq\alpha\leq\mathchoice{\nicefrac{{3}}{{4}}}{\smash{\nicefrac{{3}}{{4}}}}{\nicefrac{{3}}{{4}}}{\nicefrac{{3}}{{4}}}$, so it follows using the strict concavity of $\mathbf{b}$ that

2. Coarsening algorithm and frozen model

In view of Propn. 1.2 we hereafter assume unless indicated otherwise that $k\geq k_{0}$ large,

We simulate the coarsening algorithm as follows: of the $nd$ half-edges incident to variables, choose $e_{1},\ldots,e_{m}$ uniformly at random (with random ordering) to be potentially forcing. Edge $e_{a}$ corresponds to clause $a$, though here the clauses are not explicitly formed. Conditioned on $\underline{\smash{x}}$ being a valid solution, each clause independently has probability $\vartheta\equiv\mathchoice{\nicefrac{{2k}}{{(2^{k}-2)}}}{\smash{\nicefrac{{2k}}{{(2^{k}-2)}}}}{\nicefrac{{2k}}{{(2^{k}-2)}}}{\nicefrac{{2k}}{{(2^{k}-2)}}}$ to be $\underline{\smash{x}}$-forcing (cf. Defn. 2.1): therefore set each $e_{a}$ to be initially forcing with probability $\vartheta$, independently over $a$. Then, for each $t\geq 0$, if there exists $v\in V$ which is incident to no (remaining) initially forcing half-edge, then take the first such $v$ and

Delete all $d^{t}_{v}$ remaining potentially forcing half-edges incident to $v$; and

Delete the first $d-d^{t}_{v}$ potentially forcing half-edges among all those remaining.

The interpretation is that the coarsening algorithm sets $v$ to be a free variable at stage $t$. Thus the $d-d^{t}_{v}$ clauses incident to $v$ and potentially forcing to other variables can no longer be forcing, so we remove these clauses from consideration (step (ii)).Step (i) does not delete any initially forcing half-edges, but step (ii) can.

First moment of frozen model

We shall specify a Gibbs measure $\nu$ on $T_{d,k}$ by defining a consistent family of finite-dimensional distributions $\nu_{t}$ on the depth-$t$ subtrees $T_{d,k}(t)$. A typical manner of specifying $\nu_{t}$ is to specify a “boundary law” on the configuration on the depth-$t$ vertices, and then to define $\nu_{t}$ as an appropriate finite-volume Gibbs measure on $T_{d,k}(t)$ conditioned on the boundary configuration.

In our setting some difficulty is imposed by the fact that the frozen model is not a factor model (or Markov random field) in the conventional sense that $\underline{\smash{\eta}}|_{A}$ and $\underline{\smash{\eta}}|_{B}$ are conditionally independent given the configuration $\underline{\smash{\eta}}|_{C}$ on any subset $C$ separating $A$ from $B$ — in particular, given the variable spins at level $2t$ of $T_{d,k}$, whether a variable at level $2(t-1)$ is permitted to take spin f depends on whether its neighboring 0’s and 1’s in level $2t$ are forced by clauses in level $2t+1$.

The message-passing rules for our frozen model are as follows:

provided $\underline{\smash{\eta}}^{\uparrow}$ completes leads to a valid message configuration (no unsat messages) on $T_{d,k}(t)$ with respect to literals $\underline{\smash{L}}(t)$. The root marginal is then given by

If $1-q\lesssim 2^{-k}$ then $v_{k-1}(q)=1-\mathchoice{\nicefrac{{2}}{{2^{k}}}}{\smash{\nicefrac{{2}}{{2^{k}}}}}{\nicefrac{{2}}{{2^{k}}}}{\nicefrac{{2}}{{2^{k}}}}+O(\mathchoice{\nicefrac{{k}}{{4^{k}}}}{\smash{\nicefrac{{k}}{{4^{k}}}}}{\nicefrac{{k}}{{4^{k}}}}{\nicefrac{{k}}{{4^{k}}}})$, therefore $v_{k-1}(q)^{d-1}=2^{-k}+O(\mathchoice{\nicefrac{{k^{2}}}{{4^{k}}}}{\smash{\nicefrac{{k^{2}}}{{4^{k}}}}}{\nicefrac{{k^{2}}}{{4^{k}}}}{\nicefrac{{k^{2}}}{{4^{k}}}})$ and $q_{d-1}\circ v_{k-1}(q)=1-2^{-k-1}+O(\mathchoice{\nicefrac{{k^{2}}}{{4^{k}}}}{\smash{\nicefrac{{k^{2}}}{{4^{k}}}}}{\nicefrac{{k^{2}}}{{4^{k}}}}{\nicefrac{{k^{2}}}{{4^{k}}}})$. In this regime we also calculate

thus $(q_{d-1}\circ v_{k-1})^{\prime}\asymp\mathchoice{\nicefrac{{k^{2}}}{{2^{k}}}}{\smash{\nicefrac{{k^{2}}}{{2^{k}}}}}{\nicefrac{{k^{2}}}{{2^{k}}}}{\nicefrac{{k^{2}}}{{2^{k}}}}$ so in this regime (10) must have the unique solution as claimed. ∎

2. Auxiliary model

In the auxiliary model, each configuration ${\underline{\smash{\sigma}}}\in\mathscr{M}^{E}$ receives the factor model weight

3. Bethe variational principle

We regard $\bm{h}\equiv(\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}},\bm{\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}})$ as a vector indexed by $\operatorname{supp}\varphi\equiv(\operatorname{supp}\mathchoice{\dot{\varphi}}{\smash{\dot{\varphi}}}{\dot{\varphi}}{\dot{\varphi}},\operatorname{supp}\mathchoice{\hat{\varphi}}{\smash{\hat{\varphi}}}{\hat{\varphi}}{\hat{\varphi}})$. For $\sigma\in\mathscr{M}$ and $\underline{\smash{\mathchoice{\dot{\sigma}}{\smash{\dot{\sigma}}}{\dot{\sigma}}{\dot{\sigma}}}}\in\operatorname{supp}\mathchoice{\dot{\varphi}}{\smash{\dot{\varphi}}}{\dot{\varphi}}{\dot{\varphi}}$ let $\mathchoice{\dot{H}}{\smash{\dot{H}}}{\dot{H}}{\dot{H}}_{\sigma,\underline{\smash{\mathchoice{\dot{\sigma}}{\smash{\dot{\sigma}}}{\dot{\sigma}}{\dot{\sigma}}}}}$ denote the number of appearances of $\sigma$ in $\underline{\smash{\mathchoice{\dot{\sigma}}{\smash{\dot{\sigma}}}{\dot{\sigma}}{\dot{\sigma}}}}$, and similarly write $\mathchoice{\hat{H}}{\smash{\hat{H}}}{\hat{H}}{\hat{H}}_{\sigma,\underline{\smash{\mathchoice{\hat{\sigma}}{\smash{\hat{\sigma}}}{\hat{\sigma}}{\hat{\sigma}}}}}$ for the number of appearances of $\sigma$ in $\underline{\smash{\mathchoice{\hat{\sigma}}{\smash{\hat{\sigma}}}{\hat{\sigma}}{\hat{\sigma}}}}$. For $\bm{h}$ to correspond to a valid configuration ${\underline{\smash{\sigma}}}$, the variable and clause empirical measures must give rise to the same edge marginals

Given $\varphi\equiv(\mathchoice{\dot{\varphi}}{\smash{\dot{\varphi}}}{\dot{\varphi}}{\dot{\varphi}},\mathchoice{\hat{\varphi}}{\smash{\hat{\varphi}}}{\hat{\varphi}}{\hat{\varphi}})$ let $\bm{\Delta}$ denote the space of probability measures $\bm{h}\equiv(\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}},\bm{\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}})$ on $\operatorname{supp}\varphi$ (that is, $\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}}$ is a probability measure on $\operatorname{supp}\mathchoice{\dot{\varphi}}{\smash{\dot{\varphi}}}{\dot{\varphi}}{\dot{\varphi}}$ while $\bm{\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}}$ is a probability measure on $\operatorname{supp}\mathchoice{\hat{\varphi}}{\smash{\hat{\varphi}}}{\hat{\varphi}}{\hat{\varphi}}$) such that

$(\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}},\mathchoice{\tfrac{d}{k}}{\smash{\tfrac{d}{k}}}{\tfrac{d}{k}}{\tfrac{d}{k}}\bm{\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}})$ lies in the kernel of matrix $H_{\bm{\Delta}}\equiv\begin{pmatrix}\mathchoice{\dot{H}}{\smash{\dot{H}}}{\dot{H}}{\dot{H}}&-\mathchoice{\hat{H}}{\smash{\hat{H}}}{\hat{H}}{\hat{H}}\end{pmatrix}$, and

Let $\bm{\mathchoice{\dot{s}}{\smash{\dot{s}}}{\dot{s}}{\dot{s}}}\equiv|\operatorname{supp}\mathchoice{\dot{\varphi}}{\smash{\dot{\varphi}}}{\dot{\varphi}}{\dot{\varphi}}|$, $\bm{\mathchoice{\hat{s}}{\smash{\hat{s}}}{\hat{s}}{\hat{s}}}\equiv|\operatorname{supp}\mathchoice{\hat{\varphi}}{\smash{\hat{\varphi}}}{\hat{\varphi}}{\hat{\varphi}}|$, and $\bar{s}\equiv|\operatorname{supp}\mathchoice{\hat{\varphi}}{\smash{\hat{\varphi}}}{\hat{\varphi}}{\hat{\varphi}}|=|\mathscr{M}|$: we shall show (Lem. 6.4) that $H_{\bm{\Delta}}$ is surjective, therefore $\bm{\Delta}$ is an $(\bm{\mathchoice{\dot{s}}{\smash{\dot{s}}}{\dot{s}}{\dot{s}}}+\bm{\mathchoice{\hat{s}}{\smash{\hat{s}}}{\hat{s}}{\hat{s}}}-\bar{s}-1)$-dimensional space.

The expected number of auxiliary configurations on $\mathcal{G}_{n,d,k}$ with empirical measure $\bm{h}$ is

If further $\min\bm{h}\gtrsim_{k}1$ as $n\to\infty$, then

If ${}^{\star}\bm{h}$ lies in the interior $\bm{\Delta}^{\circ}$ of $\bm{\Delta}$ then it must be a stationary point for $\bm{\Phi}$. Such points correspond to a generalization of the tree Gibbs measures considered in §3.1, where the boundary conditions are specified by a law on incoming and outgoing messages, as follows: first sample uniformly random literals $\underline{\smash{L}}(t)$ on $T_{d,k}(t)$ as before. If ${\underline{\smash{\sigma}}}(t)$ is a message configuration on the edges of $T_{d,k}(t)$ — including the edges $E(t-1,t)$ joining levels $t-1$ and $t$ — then let $\Psi_{t}(\underline{\smash{L}}(t),{\underline{\smash{\sigma}}}(t))$ denote the product of the factor weights $\mathchoice{\dot{\varphi}}{\smash{\dot{\varphi}}}{\dot{\varphi}}{\dot{\varphi}}(\underline{\smash{\mathchoice{\dot{\sigma}}{\smash{\dot{\sigma}}}{\dot{\sigma}}{\dot{\sigma}}}}_{v})$, $\mathchoice{\hat{\varphi}}{\smash{\hat{\varphi}}}{\hat{\varphi}}{\hat{\varphi}}^{a}(\underline{\smash{\mathchoice{\hat{\sigma}}{\smash{\hat{\sigma}}}{\hat{\sigma}}{\hat{\sigma}}}}_{a})$ over all $v,a\in T_{d,k}(t-1)$. For probability measures $\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}},\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}$ on $\mathscr{M}$ we define the measures

with $Z_{t}$ the normalizing constant which makes $\bm{\nu}_{t}$ a probability measure. This generalizes the definition of $\nu_{t}$ in (8) by taking $\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}_{\eta\eta^{\prime}}$ proportional to $\mathchoice{\dot{q}}{\smash{\dot{q}}}{\dot{q}}{\dot{q}}_{\eta}$ and $\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}_{\eta\eta^{\prime}}$ proportional to $\mathchoice{\hat{q}}{\smash{\hat{q}}}{\hat{q}}{\hat{q}}_{\eta^{\prime}}$, i.e.

The family $(\bm{\nu}_{t})_{t}$ is consistent if and only if $h\equiv(\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}},\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}})$ satisfies the Bethe recursions

(with $\mathchoice{\dot{z}}{\smash{\dot{z}}}{\dot{z}}{\dot{z}}_{h},\mathchoice{\hat{z}}{\smash{\hat{z}}}{\hat{z}}{\hat{z}}_{h}$ the normalizing constants); these generalize the frozen model recursions (9), as we shall see explicitly below. Thus a solution $h$ of (18) specifies a Gibbs measure $\bm{\nu}$ for the auxiliary model on $T_{d,k}$ which generalizes the measures $\nu$ described in §3.1.

This proves our claim that the measures $\bm{\nu}$ generalize the measures $\nu$ of §3.1.

The connection between these Gibbs measures and the rate function $\bm{\Phi}$ is given by the following variational principle:

If $\varphi\equiv(\mathchoice{\dot{\varphi}}{\smash{\dot{\varphi}}}{\dot{\varphi}}{\dot{\varphi}},\mathchoice{\hat{\varphi}}{\smash{\hat{\varphi}}}{\hat{\varphi}}{\hat{\varphi}})$ is such that both $\mathchoice{\dot{H}}{\smash{\dot{H}}}{\dot{H}}{\dot{H}}$ and $\mathchoice{\hat{H}}{\smash{\hat{H}}}{\hat{H}}{\hat{H}}$ are surjective, then any stationary point $\bm{h}$ of $\bm{\Phi}$ belonging to $\bm{\Delta}^{\circ}$ corresponds to a Bethe fixed point solving (18) via

with $\bm{\mathchoice{\dot{z}}{\smash{\dot{z}}}{\dot{z}}{\dot{z}}}_{h},\bm{\mathchoice{\hat{z}}{\smash{\hat{z}}}{\hat{z}}{\hat{z}}}_{h},\mathchoice{\bar{z}}{\smash{\bar{z}}}{\bar{z}}{\bar{z}}_{h}$ normalizing constants satisfying $\mathchoice{\bar{z}}{\smash{\bar{z}}}{\bar{z}}{\bar{z}}_{h}=\bm{\mathchoice{\dot{z}}{\smash{\dot{z}}}{\dot{z}}{\dot{z}}}_{h}/\mathchoice{\dot{z}}{\smash{\dot{z}}}{\dot{z}}{\dot{z}}_{h}=\bm{\mathchoice{\hat{z}}{\smash{\hat{z}}}{\hat{z}}{\hat{z}}}_{h}/\mathchoice{\hat{z}}{\smash{\hat{z}}}{\hat{z}}{\hat{z}}_{h}$ for $\mathchoice{\dot{z}}{\smash{\dot{z}}}{\dot{z}}{\dot{z}}_{h},\mathchoice{\hat{z}}{\smash{\hat{z}}}{\hat{z}}{\hat{z}}_{h}$ as in (18).

At an interior stationary point $\bm{h}$, consider differentiating $\bm{\Phi}$ in direction $\bm{\delta}\equiv(\bm{\mathchoice{\dot{\delta}}{\smash{\dot{\delta}}}{\dot{\delta}}{\dot{\delta}}},0)$ with $\mathchoice{\dot{H}}{\smash{\dot{H}}}{\dot{H}}{\dot{H}}\bm{\mathchoice{\dot{\delta}}{\smash{\dot{\delta}}}{\dot{\delta}}{\dot{\delta}}}=0$, so that $\bm{h}+s\bm{\delta}\in\bm{\Delta}^{\circ}$ for $|s|$ small. Writing $\bm{\mathchoice{\dot{a}}{\smash{\dot{a}}}{\dot{a}}{\dot{a}}}\equiv\log[\mathchoice{\dot{\varphi}}{\smash{\dot{\varphi}}}{\dot{\varphi}}{\dot{\varphi}}(\underline{\smash{\mathchoice{\dot{\sigma}}{\smash{\dot{\sigma}}}{\dot{\sigma}}{\dot{\sigma}}}})/\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}}(\underline{\smash{\mathchoice{\dot{\sigma}}{\smash{\dot{\sigma}}}{\dot{\sigma}}{\dot{\sigma}}}})]$,

We claim it is possible to choose $\mathchoice{\dot{\lambda}}{\smash{\dot{\lambda}}}{\dot{\lambda}}{\dot{\lambda}}$ such that $\bm{\mathchoice{\dot{\varepsilon}}{\smash{\dot{\varepsilon}}}{\dot{\varepsilon}}{\dot{\varepsilon}}}$ has marginals $\bar{\varepsilon}\equiv 0$: in vector notation $\bm{\mathchoice{\dot{\varepsilon}}{\smash{\dot{\varepsilon}}}{\dot{\varepsilon}}{\dot{\varepsilon}}}=\bm{\mathchoice{\dot{a}}{\smash{\dot{a}}}{\dot{a}}{\dot{a}}}+\mathchoice{\dot{H}}{\smash{\dot{H}}}{\dot{H}}{\dot{H}}^{t}\mathchoice{\dot{\lambda}}{\smash{\dot{\lambda}}}{\dot{\lambda}}{\dot{\lambda}}$, so this amounts to solving $\mathchoice{\dot{H}}{\smash{\dot{H}}}{\dot{H}}{\dot{H}}\bm{\mathchoice{\dot{a}}{\smash{\dot{a}}}{\dot{a}}{\dot{a}}}+\mathchoice{\dot{H}}{\smash{\dot{H}}}{\dot{H}}{\dot{H}}\mathchoice{\dot{H}}{\smash{\dot{H}}}{\dot{H}}{\dot{H}}^{t}\mathchoice{\dot{\lambda}}{\smash{\dot{\lambda}}}{\dot{\lambda}}{\dot{\lambda}}=0$, which has a unique solution $\mathchoice{\dot{\lambda}}{\smash{\dot{\lambda}}}{\dot{\lambda}}{\dot{\lambda}}$ by surjectivity of $\mathchoice{\dot{H}}{\smash{\dot{H}}}{\dot{H}}{\dot{H}}$. Taking $\bm{\mathchoice{\dot{\delta}}{\smash{\dot{\delta}}}{\dot{\delta}}{\dot{\delta}}}=\bm{\mathchoice{\dot{\varepsilon}}{\smash{\dot{\varepsilon}}}{\dot{\varepsilon}}{\dot{\varepsilon}}}$ with this value of $\mathchoice{\dot{\lambda}}{\smash{\dot{\lambda}}}{\dot{\lambda}}{\dot{\lambda}}$ in the above derivative gives

Now differentiate in the direction of general $\bm{\delta}$ with $\mathchoice{\tfrac{1}{d}}{\smash{\tfrac{1}{d}}}{\tfrac{1}{d}}{\tfrac{1}{d}}\mathchoice{\dot{H}}{\smash{\dot{H}}}{\dot{H}}{\dot{H}}\bm{\mathchoice{\dot{\delta}}{\smash{\dot{\delta}}}{\dot{\delta}}{\dot{\delta}}}=\mathchoice{\bar{\delta}}{\smash{\bar{\delta}}}{\bar{\delta}}{\bar{\delta}}=\mathchoice{\tfrac{1}{k}}{\smash{\tfrac{1}{k}}}{\tfrac{1}{k}}{\tfrac{1}{k}}\mathchoice{\hat{H}}{\smash{\hat{H}}}{\hat{H}}{\hat{H}}\bm{\mathchoice{\hat{\delta}}{\smash{\hat{\delta}}}{\hat{\delta}}{\hat{\delta}}}$, so $\bm{h}+s\bm{\delta}\in\bm{\Delta}$ for small $|s|$. Applying (22) and simplifying gives

By surjectivity we may choose $\bm{\delta}$ with $\mathchoice{\bar{\delta}}{\smash{\bar{\delta}}}{\bar{\delta}}{\bar{\delta}}(\sigma)=\bar{\rho}(\sigma)-|\mathscr{M}|^{-1}\sum_{\sigma^{\prime}}\bar{\rho}(\sigma^{\prime})$, and then substituting into the above we find that $\log\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}}-\mathchoice{\dot{\lambda}}{\smash{\dot{\lambda}}}{\dot{\lambda}}{\dot{\lambda}}-{\mathchoice{\hat{\lambda}}{\smash{\hat{\lambda}}}{\hat{\lambda}}{\hat{\lambda}}}$ is a constant function of $\sigma$, that is,

On the other hand, the marginal of (22) reads

Comparing the expressions for $\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}}(\sigma)$ shows that the probability measures $\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}$ and $\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}$ on $\mathscr{M}$ obtained by normalizing respectively $\smash{e^{{\mathchoice{\hat{\lambda}}{\smash{\hat{\lambda}}}{\hat{\lambda}}{\hat{\lambda}}}(\sigma)}}$ and $\smash{e^{\mathchoice{\dot{\lambda}}{\smash{\dot{\lambda}}}{\dot{\lambda}}{\dot{\lambda}}(\sigma)}}$ must solve the Bethe recursions (18). Lastly (22) shows that $\bm{h}$ corresponds to $h\equiv(\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}},\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}})$ via (21), concluding the proof. ∎

In view of Lem. 3.6 and our preceding discussion of Gibbs measures, Thm. 3.7 will follow by showing

Any global maximizer $\bm{h}$ of $\bm{\Phi}$ on $\bm{\Delta}$ must lie in the interior $\bm{\Delta}^{\circ}$, and so corresponds via (21) to a solution $h$ of the Bethe recursions (18). (For the required surjectivity of $\mathchoice{\dot{H}}{\smash{\dot{H}}}{\dot{H}}{\dot{H}},\mathchoice{\hat{H}}{\smash{\hat{H}}}{\hat{H}}{\hat{H}}$ see Lem. 6.4.)

Any such Bethe solution $h$ satisfies the symmetries (18), therefore reduces to a solution $q$ of the frozen model recursions (9). Further $q$ is in the regime of Lem. 3.1, which uniquely identifies $\bm{h}={}^{\star}\bm{h}$.

4. Boundary maximizers

In this section we verify (by a priori estimates) that $\bm{\Phi}$ has no maximizers on the boundary of $\bm{\Delta}$. By Rmk. 3.3 we may work interchangeably with the frozen and auxiliary models.

Recall that $\bm{Z}_{n\beta}$ denotes the contribution to the frozen model partition function from configurations with $n\beta$ free variables.

The above is optimized at $\nu_{j}=p_{j}u^{j}/c$ where $c\equiv\sum_{j}p_{j}u^{j}$ and $u$ is chosen such that $k\beta$ matches $\smash{\sum_{j}j\nu_{j}=(\sum_{j}jp_{j}u^{j})/(\sum_{j}p_{j}u^{j})}$. The latter is increasing in $u$, and it is straightforward to check that it has a unique solution $u=1+\mathchoice{\nicefrac{{2}}{{2^{k}}}}{\smash{\nicefrac{{2}}{{2^{k}}}}}{\nicefrac{{2}}{{2^{k}}}}{\nicefrac{{2}}{{2^{k}}}}+O(\mathchoice{\nicefrac{{k}}{{4^{k}}}}{\smash{\nicefrac{{k}}{{4^{k}}}}}{\nicefrac{{k}}{{4^{k}}}}{\nicefrac{{k}}{{4^{k}}}})$. This implies $c=1-\mathchoice{\nicefrac{{2}}{{2^{k}}}}{\smash{\nicefrac{{2}}{{2^{k}}}}}{\nicefrac{{2}}{{2^{k}}}}{\nicefrac{{2}}{{2^{k}}}}+O(\mathchoice{\nicefrac{{k^{2}}}{{8^{k}}}}{\smash{\nicefrac{{k^{2}}}{{8^{k}}}}}{\nicefrac{{k^{2}}}{{8^{k}}}}{\nicefrac{{k^{2}}}{{8^{k}}}})$, thus

with $\Phi$ as in (2) (not depending on $\beta$).

Bounds with forcing constraints. Suppose we condition on an assignment of edges such that every clause is satisfied, and no f-variables are illegally forced. Each of the $m\nu_{0}$ fully rigid clauses is forcing with probability $\vartheta\equiv\mathchoice{\nicefrac{{2k}}{{(2^{k}-2)}}}{\smash{\nicefrac{{2k}}{{(2^{k}-2)}}}}{\nicefrac{{2k}}{{(2^{k}-2)}}}{\nicefrac{{2k}}{{(2^{k}-2)}}}$, and $m\nu_{0}$ is clearly sandwiched between $m$ and $\acute{m}\equiv m(1-k\beta)$, therefore

For $\alpha=[1+O(2^{-k/3})]\,\vartheta$ we have

the same estimate holds with $\acute{m},\acute{y}$ in place of $m,y$. Applying Lem. 3.8 then gives

This is clearly optimized with $2^{k+1}\beta\approx 1$, and estimating the second derivative of the exponent with respect to $\beta$ implies the result. ∎

Lem. 3.9 shows that the maximum cannot be obtained on the boundary $\beta=\beta_{\max}$, so it remains to show that the maximizer must be a strictly positive measure on $\operatorname{supp}\varphi$. For $\bm{\delta}\equiv(\bm{\mathchoice{\dot{\delta}}{\smash{\dot{\delta}}}{\dot{\delta}}{\dot{\delta}}},\bm{\mathchoice{\hat{\delta}}{\smash{\hat{\delta}}}{\hat{\delta}}{\hat{\delta}}})$ such that $\bm{h}+t\bm{\delta}$ lies in $\bm{\Delta}$ for $t\geq 0$ small, consider

To show that $\bm{h}\in\bm{\Delta}$ is not a maximizer it suffices to exhibit $\mathbf{T}\bm{\Phi}(\bm{h};\bm{\delta})>0$ for some $\bm{\delta}$. In particular, it follows by convexity that for any $\bm{h}\in\bm{\Delta}$, $\bm{h}+t({}^{\star}\bm{h}-\bm{h})\in\bm{\Delta}^{\circ}$ for $t>0$ small and ${}^{\star}\bm{h}$ as in the statement of Thm. 3.7. Therefore, if $\bm{h}$ is a maximizer such that the edge marginal has full support $\operatorname{supp}\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}}=\mathscr{M}$, then necessarily $\operatorname{supp}\bm{h}=\operatorname{supp}\varphi$, since otherwise $\mathbf{T}\bm{\Phi}(\bm{h};{}^{\star}\bm{h}-\bm{h})>0$.

Clearly the same argument applies replacing 0 with 1. In each case the conclusion contradicts the assumption that $\bm{h}$ is a maximizer, concluding the proof.In our setting we have checked $\operatorname{supp}\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}}=\mathscr{M}$ in a rather ad hoc manner. A simpler argument applies generally to any specification $\varphi$ which is everywhere positive on $\mathscr{M}^{d}$, $\mathscr{M}^{k}$: if $\sigma\notin\operatorname{supp}\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}}$ then take $\acute{\sigma}\in\operatorname{supp}\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}}$, and observe that $\mathbf{T}\bm{\Phi}(\bm{h};\bm{\delta})>0$ for $\bm{\delta}$ defined by $\bm{\mathchoice{\dot{\delta}}{\smash{\dot{\delta}}}{\dot{\delta}}{\dot{\delta}}}=\mathbf{1}_{(\sigma,\acute{\sigma}^{d-1})}-\mathbf{1}_{(\acute{\sigma}^{d})}$, $(\mathchoice{\nicefrac{{d}}{{k}}}{\smash{\nicefrac{{d}}{{k}}}}{\nicefrac{{d}}{{k}}}{\nicefrac{{d}}{{k}}})\bm{\mathchoice{\hat{\delta}}{\smash{\hat{\delta}}}{\hat{\delta}}{\hat{\delta}}}=\mathbf{1}_{(\sigma,\acute{\sigma}^{k-1})}-\mathbf{1}_{(\acute{\sigma}^{k})}$. ∎

5. Bethe recursion symmetries

Suppose $\bm{h}$ is an interior maximizer for $\bm{\Phi}$ on $\bm{\Delta}$, and so corresponds to a Bethe solution $h$. Let $\acute{T}_{d,k}$ denote $T_{d,k}$ with a subtree incident to the root removed, leaving an unmatched half-edge $\acute{e}$ incident to $o$ (Fig. 2). Consider defining a Gibbs measure on $\acute{T}_{d,k}$ in the manner of (16), with boundary law given by the Bethe solution $h$. Then the marginal law of $\sigma_{\acute{e}}$ will be $\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}$, and the marginal law of the tuple of spins incident to any given vertex will be $\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}}$ if the vertex is a variable, $\bm{\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}}$ if it is a clause. Further, the Gibbs measure on $\acute{T}_{d,k}$ can be generated in Markovian fashion, starting with spin $\sigma_{\acute{e}}$ distributed according to $\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}$, generating the messages on the other $d-1$ edges incident to $o$ according to the conditional measure $\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}}(\underline{\smash{\mathchoice{\dot{\sigma}}{\smash{\dot{\sigma}}}{\dot{\sigma}}{\dot{\sigma}}}}\,|\,\sigma_{1}=\sigma_{\acute{e}})$, and continuing iteratively down the tree.

The effect of changing $\smash{\acute{\bm{u}}}\smash{\grave{\bm{\upsilon}}}$ from ff to f0 can only propagate through clauses in which the parent variable and exactly one descendant variable send message f, and the evaluation of the remaining $k-2$ messages under the clause literals is identically 0 or 1. The vertex-preceding edges of $\acute{T}_{d,k}$ whose spins will be affected by changing $\smash{\grave{\bm{\upsilon}}}$ from f to 0 form a branching process with mean

where the intermediate step follows from (21). Similarly, the effect of changing $\smash{\acute{\bm{u}}}\smash{\grave{\bm{\upsilon}}}$ from f0 to ff can only propagate through clauses in which exactly one descendant variable sends message f, and the evaluation of the remaining $k-1$ messages under the clause literals is identically 0 or 1. This forms a branching process with mean

6. Explicit form of first moment exponent

We conclude this section by giving the explicit form of ${}^{\star}\bm{\Phi}\equiv{}^{\star}\bm{\Phi}_{k}(d)$.

with $d_{\square}$ the first moment threshold of the original nae-sat partition function (3).

Let us now see that ${}^{\star}\bm{\Phi}$ is strictly decreasing in $d$. Recalling (30) that $v=Q/(1-Q)$, we find

and rearranging gives (27). This can be expressed as a function of $q$ alone by taking $Q=Q(q)$ as in (30) and $d=d(q)$ as in (28). With $D_{q}$ denoting differentiation in $q$, we calculate

The total derivative of ${}^{\star}\bm{\Phi}\equiv{}^{\star}\bm{\Phi}(d(q))$ with respect to $q$ is then straightforward to calculate: the main contribution comes from

Second moment of auxiliary model

In this subsection we complete our analysis of the near-independent regime ${}^{\star}_{2}\bm{\Delta}$ to prove

The unique global maximizer of the restriction of ${}_{2}\bm{\Phi}$ to ${}^{\star}_{2}\bm{\Delta}$ is ${}^{\star}_{2}\bm{h}$.

Note that $H(\pi)$ is maximized at $\alpha=\mathchoice{\nicefrac{{1}}{{2}}}{\smash{\nicefrac{{1}}{{2}}}}{\nicefrac{{1}}{{2}}}{\nicefrac{{1}}{{2}}}$, therefore

From the above estimates on the $\overline{\nu}_{j}$ we find

Combining these estimates and recalling $\Phi=\log 2+(\mathchoice{\nicefrac{{d}}{{k}}}{\smash{\nicefrac{{d}}{{k}}}}{\nicefrac{{d}}{{k}}}{\nicefrac{{d}}{{k}}})\log(1-\mathchoice{\nicefrac{{2}}{{2^{k}}}}{\smash{\nicefrac{{2}}{{2^{k}}}}}{\nicefrac{{2}}{{2^{k}}}}{\nicefrac{{2}}{{2^{k}}}})$ from (2) gives

Recalling (23) gives the two upper bounds

Any global maximizer of ${}_{2}\bm{\Phi}$ on ${}^{\star}_{2}\bm{\Delta}$ must be an interior stationary point.

It follows by symmetry considerations that $\operatorname{supp}\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}}=\mathscr{M}^{2}$, hence any maximizer $\bm{h}$ of ${}_{2}\bm{\Phi}$ must be positive on $\operatorname{supp}\varphi$ since otherwise $\mathbf{T}_{2}\bm{\Phi}(\bm{h};{}^{\star}_{2}\bm{h}-\bm{h})$ would be positive. ∎

The variable recursions are (with $\mathchoice{\dot{c}}{\smash{\dot{c}}}{\dot{c}}{\dot{c}}$ the normalizing constant)

Writing $Q\equiv(q/2)^{k-1}$, $\acute{Q}\equiv(\acute{q}/2)^{k-1}$, and $Q^{\star}\equiv(\mathchoice{\dot{q}}{\smash{\dot{q}}}{\dot{q}}{\dot{q}}^{\star}/2)^{k-1}$, we have

By assumption, $x\equiv 2^{k}(|q-\mathchoice{\dot{q}}{\smash{\dot{q}}}{\dot{q}}{\dot{q}}^{\star}|+|\acute{q}-\mathchoice{\dot{q}}{\smash{\dot{q}}}{\dot{q}}{\dot{q}}^{\star}|)\lesssim 1$, so $Q+O(x\mathchoice{\tfrac{k}{4^{k}}}{\smash{\tfrac{k}{4^{k}}}}{\tfrac{k}{4^{k}}}{\tfrac{k}{4^{k}}})=Q^{\star}=\acute{Q}+O(x\mathchoice{\tfrac{k}{4^{k}}}{\smash{\tfrac{k}{4^{k}}}}{\tfrac{k}{4^{k}}}{\tfrac{k}{4^{k}}})$ and consequently $W^{d-1}[1+O(x\mathchoice{\tfrac{dk}{4^{k}}}{\smash{\tfrac{dk}{4^{k}}}}{\tfrac{dk}{4^{k}}}{\tfrac{dk}{4^{k}}})]=(W^{\star})^{d-1}$. It follows that

implying that the recursion contracts to $x=0$, $q=\acute{q}=\mathchoice{\dot{q}}{\smash{\dot{q}}}{\dot{q}}{\dot{q}}^{\star}$ as claimed. ∎

Estimates on messages. The number of clauses incident to any variable which are free in either coordinate is $\lesssim m\mathchoice{\tfrac{k}{2^{k}}}{\smash{\tfrac{k}{2^{k}}}}{\tfrac{k}{2^{k}}}{\tfrac{k}{2^{k}}}$, while an easy a priori estimate implies that the number of fully-rigid clauses which are non-forcing is $\asymp m$. Recalling (21) then gives

where the last inequality follows because all the $\mathchoice{\hat{\varphi}}{\smash{\hat{\varphi}}}{\hat{\varphi}}{\hat{\varphi}}_{2}$ factor weights involved in the application of (21) are $1-O(\mathchoice{\tfrac{k}{2^{k}}}{\smash{\tfrac{k}{2^{k}}}}{\tfrac{k}{2^{k}}}{\tfrac{k}{2^{k}}})$.

where the last step uses the assumption that $\bm{h}$ lies in ${}^{\star}_{2}\bm{\Delta}$.

2. A priori rigidity estimate

Recalling Lem. 4.2, let ${}^{\cdot\cdot}_{2}\bm{Z}$ denote the contribution to $\bm{Z}^{2}$ from the near-identical regime $\bm{h}\in{}^{\cdot\cdot}_{2}\bm{\Delta}$. In this subsection we prove

(where $0<\alpha<1$ may be arbitrarily chosen). We therefore bound

where we have used the trivial inequality $H(x)+x\log c\leq\log(1+c)\leq c$. Recall $\varepsilon\lesssim 2^{-k/2}$ by assumption, and $\gamma\leq k^{2}/2^{k/2}$ by the restriction to $\Omega_{B}$, therefore

Crudely bounding $\widetilde{\text{{a}}}_{v}\leq d$, there exists a uniform constant $C$ such that

Again recalling $H(x)+x\log c\leq\log(1+c)\leq c$ we bound

Follows by combining Propns. 4.3 and 4.7. ∎

Negative-definiteness of free energy Hessians

The Hessians $H\bm{\Phi}({}^{\star}\bm{h})$ and $H_{2}\bm{\Phi}({}^{\star}_{2}\bm{h})$ are negative-definite.

Let $\bm{h}\in\bm{\Delta}^{\circ}$ with $\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}}$ and $\bm{\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}}$ both symmetric, and let $\bm{\delta}$ be any signed measure on $\operatorname{supp}\varphi$ (not necessarily symmetric) with $\bm{h}+s\bm{\delta}\in\bm{\Delta}^{\circ}$ for sufficiently small $|s|$. Then

where $a/b$ denotes the vector given by coordinate-wise division of $a$ by $b$, and $\langle\cdot\rangle_{h}$ denotes integration with respect to measure $h$, e.g. $\langle(\mathchoice{\bar{\delta}}{\smash{\bar{\delta}}}{\bar{\delta}}{\bar{\delta}}/\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}})^{2}\rangle_{\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}}}=\sum_{\sigma}\bm{\delta}(\sigma)^{2}/\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}}(\sigma)$.

Given fixed marginals $\mathchoice{\bar{\delta}}{\smash{\bar{\delta}}}{\bar{\delta}}{\bar{\delta}}$, $\langle(\bm{\mathchoice{\dot{\delta}}{\smash{\dot{\delta}}}{\dot{\delta}}{\dot{\delta}}}/\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}})^{2}\rangle_{\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}}}$ is minimized by $\bm{\mathchoice{\dot{\delta}}{\smash{\dot{\delta}}}{\dot{\delta}}{\dot{\delta}}}(\underline{\smash{\mathchoice{\dot{\sigma}}{\smash{\dot{\sigma}}}{\dot{\sigma}}{\dot{\sigma}}}})=\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}}(\underline{\smash{\mathchoice{\dot{\sigma}}{\smash{\dot{\sigma}}}{\dot{\sigma}}{\dot{\sigma}}}})\mathchoice{\tfrac{1}{d}}{\smash{\tfrac{1}{d}}}{\tfrac{1}{d}}{\tfrac{1}{d}}\sum_{i=1}^{d}\mathchoice{\dot{\chi}}{\smash{\dot{\chi}}}{\dot{\chi}}{\dot{\chi}}_{\sigma_{i}}$ with $\mathchoice{\dot{\chi}}{\smash{\dot{\chi}}}{\dot{\chi}}{\dot{\chi}}$ chosen to satisfy the margin constraint — which, after a little algebra, becomes the vector equation $\mathchoice{\bar{H}}{\smash{\bar{H}}}{\bar{H}}{\bar{H}}^{-1}\mathchoice{\bar{\delta}}{\smash{\bar{\delta}}}{\bar{\delta}}{\bar{\delta}}=d^{-1}[I+(d-1)\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}]\mathchoice{\dot{\chi}}{\smash{\dot{\chi}}}{\dot{\chi}}{\dot{\chi}}$ where $\mathchoice{\bar{H}}{\smash{\bar{H}}}{\bar{H}}{\bar{H}}\equiv\operatorname{diag}(\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}})$ and $\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}$ denotes the stochastic matrix

If such $\mathchoice{\dot{\chi}}{\smash{\dot{\chi}}}{\dot{\chi}}{\dot{\chi}}$ exists, then the minimal value of $\langle(\bm{\mathchoice{\dot{\delta}}{\smash{\dot{\delta}}}{\dot{\delta}}{\dot{\delta}}}/\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}})^{2}\rangle_{\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}}}$ subject to marginals $\mathchoice{\bar{\delta}}{\smash{\bar{\delta}}}{\bar{\delta}}{\bar{\delta}}$ is $\langle\mathchoice{\bar{\delta}}{\smash{\bar{\delta}}}{\bar{\delta}}{\bar{\delta}},\mathchoice{\dot{\chi}}{\smash{\dot{\chi}}}{\dot{\chi}}{\dot{\chi}}\rangle$. Define analogously the stochastic matrix $\mathchoice{\hat{M}}{\smash{\hat{M}}}{\hat{M}}{\hat{M}}$ corresponding to $\bm{\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}}$: if both $\mathchoice{\dot{L}}{\smash{\dot{L}}}{\dot{L}}{\dot{L}}\equiv I+(d-1)\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}$ and $\mathchoice{\hat{L}}{\smash{\hat{L}}}{\hat{L}}{\hat{L}}\equiv I+(k-1)\mathchoice{\hat{M}}{\smash{\hat{M}}}{\hat{M}}{\hat{M}}$ are non-singular, then the maximum of $k\,\partial_{\eta}^{2}\bm{\Phi}(\bm{h}+\eta\bm{\delta})|_{\eta=0}$ over all $\bm{\delta}$ with marginal $\mathchoice{\bar{\delta}}{\smash{\bar{\delta}}}{\bar{\delta}}{\bar{\delta}}$ is given by

where $F\equiv(\mathchoice{\bar{H}}{\smash{\bar{H}}}{\bar{H}}{\bar{H}}^{1/2}\mathchoice{\dot{L}}{\smash{\dot{L}}}{\dot{L}}{\dot{L}}\mathchoice{\bar{H}}{\smash{\bar{H}}}{\bar{H}}{\bar{H}}^{-1/2})^{-1}+(\mathchoice{\bar{H}}{\smash{\bar{H}}}{\bar{H}}{\bar{H}}^{1/2}\mathchoice{\hat{L}}{\smash{\hat{L}}}{\hat{L}}{\hat{L}}\mathchoice{\bar{H}}{\smash{\bar{H}}}{\bar{H}}{\bar{H}}^{-1/2})^{-1}-I$. It is clear from (37) that $\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}$ and $\mathchoice{\hat{M}}{\smash{\hat{M}}}{\hat{M}}{\hat{M}}$ are $\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}}$-reversible, therefore $F$ is symmetric. Since $\sum_{\sigma}\mathchoice{\bar{\delta}}{\smash{\bar{\delta}}}{\bar{\delta}}{\bar{\delta}}(\sigma)=0$ we consider only the action $F^{\prime}$ of $F$ on the space of vectors orthogonal to $\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}}^{1/2}$. At a global maximizer we know $F^{\prime}$ to be negative-semidefinite, so if $\det F\neq 0$ then it is in fact negative-definite. Thus let $\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}$, $\mathchoice{\hat{M}}{\smash{\hat{M}}}{\hat{M}}{\hat{M}}$, $\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}_{2}$, $\mathchoice{\hat{M}}{\smash{\hat{M}}}{\hat{M}}{\hat{M}}_{2}$ denote the Markov transition matrices corresponding (via (37)) to ${}^{\star}\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}}$, ${}^{\star}\bm{\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}}$, ${}^{\star}_{2}\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}}$, ${}^{\star}_{2}\bm{\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}}$ respectively. In §5.2 we will prove that the matrices

are all non-singular. Propn. 5.1 then follows by noting that $F=\mathchoice{\bar{H}}{\smash{\bar{H}}}{\bar{H}}{\bar{H}}^{1/2}\mathchoice{\dot{L}}{\smash{\dot{L}}}{\dot{L}}{\dot{L}}^{-1}L\mathchoice{\hat{L}}{\smash{\hat{L}}}{\hat{L}}{\hat{L}}^{-1}\mathchoice{\bar{H}}{\smash{\bar{H}}}{\bar{H}}{\bar{H}}^{-1/2}$.

2. Calculation of transition matrices

The eigenvalues of $\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}$ counted with geometric multiplicity are

The matrix $\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}_{2}$ is given by $\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}\otimes\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}$; consequently both $\mathchoice{\dot{L}}{\smash{\dot{L}}}{\dot{L}}{\dot{L}}$ and $\mathchoice{\dot{L}}{\smash{\dot{L}}}{\dot{L}}{\dot{L}}_{2}$ are non-singular.

which has $\text{{{eigen}}}(\mathchoice{\dot{\mathfrak{m}}}{\smash{\dot{\mathfrak{m}}}}{\dot{\mathfrak{m}}}{\dot{\mathfrak{m}}})=(1,ab^{1/2},-ab^{1/2})$. Thus $\text{{{eigen}}}(\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}})=(1,\text{{{eigen}}}(\mathchoice{\dot{\mathfrak{m}}}{\smash{\dot{\mathfrak{m}}}}{\dot{\mathfrak{m}}}{\dot{\mathfrak{m}}}),\text{{{eigen}}}(\mathchoice{\dot{\mathfrak{m}}}{\smash{\dot{\mathfrak{m}}}}{\dot{\mathfrak{m}}}{\dot{\mathfrak{m}}}))$ is as stated above. Since ${}^{\star}_{2}\bm{h}={}^{\star}\bm{h}\otimes{}^{\star}\bm{h}$, clearly $\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}_{2}=\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}\otimes\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}$, so the lemma is proved. ∎

The matrices $L$ and $L_{2}$ are non-singular.

For $A\subseteq\mathscr{M}$ write $\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}}_{A}\equiv(\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}}\mathbf{1}_{A})/\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}}(A)$, the stationary distribution $\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}}$ conditioned on $A$. The vectors

therefore $\|w_{2}^{t}\mathchoice{\dot{S}}{\smash{\dot{S}}}{\dot{S}}{\dot{S}}\mathchoice{\hat{S}}{\smash{\hat{S}}}{\hat{S}}{\hat{S}}\|/\|w_{2}\|=\|(u_{2}^{t}\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}\mathchoice{\hat{M}}{\smash{\hat{M}}}{\hat{M}}{\hat{M}})/\mathchoice{\bar{h}}{\smash{\bar{h}}}{\bar{h}}{\bar{h}}^{1/2}\|/\|w_{2}\|\asymp 2^{-k/2}$. It follows that $\mathchoice{\dot{M}}{\smash{\dot{M}}}{\dot{M}}{\dot{M}}\mathchoice{\hat{M}}{\smash{\hat{M}}}{\hat{M}}{\hat{M}}$ (equivalently $\mathchoice{\dot{S}}{\smash{\dot{S}}}{\dot{S}}{\dot{S}}\mathchoice{\hat{S}}{\smash{\hat{S}}}{\hat{S}}{\hat{S}}$) can have no eigenvalue with absolute value $\asymp 1/(dk)$, hence $L$ is non-singular.

For $1\leq i,j\leq 3$ let $w_{ij}\equiv w_{i}\otimes w_{j}$, and note that if $w$ is orthogonal to the span of $(w_{11},w_{12},w_{21})$ then $\|w^{t}\mathchoice{\dot{S}}{\smash{\dot{S}}}{\dot{S}}{\dot{S}}_{2}\mathchoice{\hat{S}}{\smash{\hat{S}}}{\hat{S}}{\hat{S}}_{2}\|=O(2^{-3k/2})\|w\|$. Next note that

so $\|w_{12}^{t}\mathchoice{\dot{S}}{\smash{\dot{S}}}{\dot{S}}{\dot{S}}_{2}\mathchoice{\hat{S}}{\smash{\hat{S}}}{\hat{S}}{\hat{S}}_{2}\|/\|w_{12}\|=\|w_{2}^{t}\mathchoice{\hat{S}}{\smash{\hat{S}}}{\hat{S}}{\hat{S}}\|/\|w_{2}\|\asymp 2^{-k/2}$. Since $w_{12}\mathchoice{\dot{S}}{\smash{\dot{S}}}{\dot{S}}{\dot{S}}_{2}\mathchoice{\hat{S}}{\smash{\hat{S}}}{\hat{S}}{\hat{S}}_{2}$ and $w_{21}\mathchoice{\dot{S}}{\smash{\dot{S}}}{\dot{S}}{\dot{S}}_{2}\mathchoice{\hat{S}}{\smash{\hat{S}}}{\hat{S}}{\hat{S}}_{2}$ are orthogonal,

As shown in §5.1 the result follows by verifying that the matrices defined in (38) are non-singular, which is done by the lemmas of §5.2. ∎

In the pair partition function $\bm{Z}^{2}$, let ${}^{\star}_{2}\bm{Z}$ denote the contribution from (non-normalized) measures ${}_{2}\bm{g}$ within euclidean distance $\smash{n^{1/2}\log n}$ of the independent-copies local maximizer ${}^{\star}_{2}{\bm{g}}={}^{\star}{\bm{g}}\otimes{}^{\star}{\bm{g}}$. Recall from the statement of Lem. 4.2 that ${}^{\cdot\cdot}_{2}\bm{Z}$ denotes the contribution to $\bm{Z}^{2}$ from the near-identical measures ${}^{\cdot\cdot}_{2}\bm{\Delta}$. Decompose

From constant to high probability

As in the proof of Thm. 2, ${}^{\star}\bm{Z}$ denotes the contribution to the auxiliary model partition function on $(G,\underline{\smash{L}})$ from configurations whose non-normalized empirical measure ${\bm{g}}\equiv(n\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}},m\bm{\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}})$ lies within euclidean distance $n^{1/2}\log n$ of ${}^{\star}{\bm{g}}$. The main result of this section is the following

The proposition easily implies the following strengthened statement of Thm. 3a:

Taking $n\to\infty$ followed by $\varepsilon\downarrow 0$ proves the theorem. ∎

Consider forming the graph $G$ by beginning with $n$ vertices each incident to $d$ half-edges, and choosing, for $1\leq i\leq m$, a random set of $k$ unmatched half-edges to be joined into the $i$-th clause $a_{i}$ (every clause comes with literals). Let $\mathscr{F}\equiv(\mathscr{F}_{i})_{0\leq i\leq m}$ denote the associated filtration; to prove Propn. 6.1 we will control the increments of the Doob martingale of $\mathbf{L}^{\varepsilon}$ with respect to $\mathscr{F}$:

Note the term $i=m$ is zero, since there is no randomness left when only two unmatched half-edges remain. Since a maximum of $k$ clauses will use any subset of the half-edges of size $k$, the random graph $G\,|\,\mathscr{F}_{i}$ can be coupled with $G\,|\,\mathscr{F}_{i-1}$ such that the graphs differ only in the placement of clauses on $k^{2}$ half-edges. Therefore

Let $i$ be fixed, and note that since $(a-b)/a\leq\log(a/b)\leq(a-b)/b$ for any $a,b>0$,

Consider the graph $G^{\circ}$, with its unmatched half-edges partitioned into disjoint subsets $\mathscr{K}$ and $\mathscr{W}$. We shall define a certain local neighborhood $T$ of the half-edges in $\mathscr{K}$, such that $G^{\partial}\equiv G^{\circ}\backslash T$ is a graph with unmatched half-edges in disjoint sets $\mathscr{W}$ (as before) and $\mathscr{U}$ (leaves of $T$ without $\mathscr{W}$); see Fig. 3.Each unmatched half-edge is incident to a variable, and does not include a clause. Then, writing $\mathscr{Y}\equiv\mathscr{U}\cup\mathscr{W}$, we decompose

where $\Psi_{W}$ is the partition function on $W$, ${}^{\star}\bm{Z}^{\partial}[{\underline{\smash{\sigma}}}_{\mathscr{Y}}]$ is the partition function on $G^{\partial}$ given boundary conditions ${\underline{\smash{\sigma}}}_{\mathscr{Y}}$, $\kappa({\underline{\smash{\sigma}}}_{\mathscr{U}})\equiv\kappa_{T}({\underline{\smash{\sigma}}}_{\mathscr{U}}|{\underline{\smash{\sigma}}}_{\mathscr{W}})$ is the partition function on $T\cup A$ given boundary conditions ${\underline{\smash{\sigma}}}_{\mathscr{Y}}$, and $\smash{\acute{\kappa}({\underline{\smash{\sigma}}}_{\mathscr{U}})\equiv\acute{\kappa}_{T}({\underline{\smash{\sigma}}}_{\mathscr{U}}|{\underline{\smash{\sigma}}}_{\mathscr{W}})}$ is the partition function on $T\cup\acute{A}$ given boundary conditions ${\underline{\smash{\sigma}}}_{\mathscr{Y}}$. Averaging over $W$ and squaring gives

$\mathscr{W}$ can only intersect $T$ in its leaves; and we shall let $\mathscr{U}$ denote the leaves of $T$ without $\mathscr{W}$.

so we shall bound (45) by projection onto a Fourier basis for $L^{2}(\mathscr{M}^{2\mathscr{U}},\bm{p})$: take $(\bm{b}_{1},\ldots,\bm{b}_{|\mathscr{M}|})$ to be an orthonormal basis for $L^{2}(\mathscr{M},\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}})$ with $\bm{b}_{1}\equiv 1$. Then the functions $\bm{b}_{\underline{\smash{s}}}({\underline{\smash{\sigma}}}_{\mathscr{U}})\equiv\prod_{u\in\mathscr{U}}\bm{b}_{s(u)}(\sigma_{u})$ ($\underline{\smash{s}}\in[|\mathscr{M}|]^{\mathscr{U}}$) form an orthonormal basis for $L^{2}(\mathscr{M}^{\mathscr{U}},\bm{p})$, and the functions $\bm{b}_{\underline{\smash{s}}^{1},\underline{\smash{s}}^{2}}({\underline{\smash{\tau}}}_{\mathscr{U}})\equiv\bm{b}_{\underline{\smash{s}}^{1}}({\underline{\smash{\sigma}}}^{1}_{\mathscr{U}})\bm{b}_{\underline{\smash{s}}^{2}}({\underline{\smash{\sigma}}}^{1}_{\mathscr{U}})$ form an orthonormal basis for $L^{2}(\mathscr{M}^{2\mathscr{U}},\bm{p})$. By Plancherel’s identity,

where ∧ indicates the Fourier transform with respect to the basis $\bm{b}$, and

2. Expansion of partition function

On the graph $G^{\partial}$ we now analyze the partition function ${}^{\star}\bm{Z}^{\partial}[{\underline{\smash{\sigma}}}_{\mathscr{Y}}]$ and its marginals

It is more convenient here to work with the non-normalized tuple empirical measures ${\bm{g}}\equiv(\bm{\mathchoice{\dot{g}}{\smash{\dot{g}}}{\dot{g}}{\dot{g}}},\bm{\mathchoice{\hat{g}}{\smash{\hat{g}}}{\hat{g}}{\hat{g}}})\equiv(n\bm{\mathchoice{\dot{h}}{\smash{\dot{h}}}{\dot{h}}{\dot{h}}},m\bm{\mathchoice{\hat{h}}{\smash{\hat{h}}}{\hat{h}}{\hat{h}}})$. The associated non-normalized marginal edge counts are given by $\mathchoice{\dot{H}}{\smash{\dot{H}}}{\dot{H}}{\dot{H}}\bm{\mathchoice{\dot{g}}{\smash{\dot{g}}}{\dot{g}}{\dot{g}}}$ and $\mathchoice{\hat{H}}{\smash{\hat{H}}}{\hat{H}}{\hat{H}}\bm{\mathchoice{\hat{g}}{\smash{\hat{g}}}{\hat{g}}{\hat{g}}}$ where $\mathchoice{\dot{H}}{\smash{\dot{H}}}{\dot{H}}{\dot{H}}$, $\mathchoice{\hat{H}}{\smash{\hat{H}}}{\hat{H}}{\hat{H}}$ are the marginalization matrices corresponding to $\mathchoice{\dot{\varphi}}{\smash{\dot{\varphi}}}{\dot{\varphi}}{\dot{\varphi}}$, $\mathchoice{\hat{\varphi}}{\smash{\hat{\varphi}}}{\hat{\varphi}}{\hat{\varphi}}$ as defined in §3.3. The pair ${\bm{g}}\equiv(\bm{\mathchoice{\dot{g}}{\smash{\dot{g}}}{\dot{g}}{\dot{g}}},\bm{\mathchoice{\hat{g}}{\smash{\hat{g}}}{\hat{g}}{\hat{g}}})$ can contribute to ${}^{\star}\bm{Z}^{\partial}[{\underline{\smash{\sigma}}}_{\mathscr{Y}}]$ only if

where $\langle\bm{\mathchoice{\dot{g}}{\smash{\dot{g}}}{\dot{g}}{\dot{g}}},1\rangle$ indicates the total mass of $\bm{\mathchoice{\dot{g}}{\smash{\dot{g}}}{\dot{g}}{\dot{g}}}$, and $\mathchoice{\bar{H}}{\smash{\bar{H}}}{\bar{H}}{\bar{H}}_{{\underline{\smash{\sigma}}}_{\mathscr{Y}}}$ denotes the non-normalized edge empirical measure associated to ${\underline{\smash{\sigma}}}_{\mathscr{Y}}$. The contribution from such ${\bm{g}}$ is given by

where we adopt the shorthand $\mathchoice{\dot{\varphi}}{\smash{\dot{\varphi}}}{\dot{\varphi}}{\dot{\varphi}}^{\bm{\mathchoice{\dot{\delta}}{\smash{\dot{\delta}}}{\dot{\delta}}{\dot{\delta}}}}\equiv\prod_{\underline{\smash{\mathchoice{\dot{\sigma}}{\smash{\dot{\sigma}}}{\dot{\sigma}}{\dot{\sigma}}}}}\mathchoice{\dot{\varphi}}{\smash{\dot{\varphi}}}{\dot{\varphi}}{\dot{\varphi}}(\underline{\smash{\mathchoice{\dot{\sigma}}{\smash{\dot{\sigma}}}{\dot{\sigma}}{\dot{\sigma}}}})^{\bm{\mathchoice{\dot{\delta}}{\smash{\dot{\delta}}}{\dot{\delta}}{\dot{\delta}}}(\underline{\smash{\mathchoice{\dot{\sigma}}{\smash{\dot{\sigma}}}{\dot{\sigma}}{\dot{\sigma}}}})}$, $\bm{\mathchoice{\dot{g}}{\smash{\dot{g}}}{\dot{g}}{\dot{g}}}!\equiv\prod_{\underline{\smash{\mathchoice{\dot{\sigma}}{\smash{\dot{\sigma}}}{\dot{\sigma}}{\dot{\sigma}}}}}\bm{\mathchoice{\dot{g}}{\smash{\dot{g}}}{\dot{g}}{\dot{g}}}(\underline{\smash{\mathchoice{\dot{\sigma}}{\smash{\dot{\sigma}}}{\dot{\sigma}}{\dot{\sigma}}}})!$, etc.

The following lemma estimates the contribution in expectation from ${}^{\star}\bm{Z}^{\partial}[{\underline{\smash{\sigma}}}_{\mathscr{Y}}]$ to ${}^{\star}\bm{Z}^{\partial}$.

Suppose there exist measures $\bm{\delta}^{{\underline{\smash{\sigma}}}_{\mathscr{Y}}}$ (non-zero only on the support of $\varphi$) satisfying $\mathchoice{\hat{H}}{\smash{\hat{H}}}{\hat{H}}{\hat{H}}\bm{\mathchoice{\hat{\delta}}{\smash{\hat{\delta}}}{\hat{\delta}}{\hat{\delta}}}^{{\underline{\smash{\sigma}}}_{\mathscr{Y}}}=\mathchoice{\dot{H}}{\smash{\dot{H}}}{\dot{H}}{\dot{H}}\bm{\mathchoice{\dot{\delta}}{\smash{\dot{\delta}}}{\dot{\delta}}{\dot{\delta}}}^{{\underline{\smash{\sigma}}}_{\mathscr{Y}}}+\mathchoice{\bar{H}}{\smash{\bar{H}}}{\bar{H}}{\bar{H}}_{{\underline{\smash{\sigma}}}_{\mathscr{Y}}}$ for all ${\underline{\smash{\sigma}}}_{\mathscr{Y}}$, with $(\langle\bm{\mathchoice{\dot{\delta}}{\smash{\dot{\delta}}}{\dot{\delta}}{\dot{\delta}}}^{{\underline{\smash{\sigma}}}_{\mathscr{Y}}},1\rangle,\langle\bm{\mathchoice{\hat{\delta}}{\smash{\hat{\delta}}}{\hat{\delta}}{\hat{\delta}}}^{{\underline{\smash{\sigma}}}_{\mathscr{Y}}},1\rangle)=(\nu,\mu)$ constant in ${\underline{\smash{\sigma}}}_{\mathscr{Y}}$. Then

where $\|\bm{\delta}\|_{1}\equiv\sum_{\underline{\smash{\mathchoice{\dot{\sigma}}{\smash{\dot{\sigma}}}{\dot{\sigma}}{\dot{\sigma}}}}}|\bm{\mathchoice{\dot{\delta}}{\smash{\dot{\delta}}}{\dot{\delta}}{\dot{\delta}}}(\underline{\smash{\mathchoice{\dot{\sigma}}{\smash{\dot{\sigma}}}{\dot{\sigma}}{\dot{\sigma}}}})|+\sum_{\underline{\smash{\mathchoice{\hat{\sigma}}{\smash{\hat{\sigma}}}{\hat{\sigma}}{\hat{\sigma}}}}}|\bm{\mathchoice{\hat{\delta}}{\smash{\hat{\delta}}}{\hat{\delta}}{\hat{\delta}}}(\underline{\smash{\mathchoice{\hat{\sigma}}{\smash{\hat{\sigma}}}{\hat{\sigma}}{\hat{\sigma}}}})|$.

$G^{\partial}$ has $n^{\partial}$ variables, $m^{\partial}$ clauses, and $|\mathscr{Y}|$ unmatched edges incident to variables, so $n^{\partial}d=m^{\partial}k+|\mathscr{Y}|$. Fix ${\underline{\smash{\sigma}}}_{\mathscr{Y}}$ and abbreviate $\bm{\delta}\equiv\bm{\delta}^{{\underline{\smash{\sigma}}}_{\mathscr{Y}}}$; note from the assumptions that $\nu d=\mu k-|\mathscr{Y}|$. Thus $n^{\prime}d=m^{\prime}k$ for $n^{\prime}\equiv n^{\partial}+\nu$ and $m^{\prime}\equiv m^{\partial}+\mu$, so we may compare ${}^{\star}\bm{Z}^{\partial}$ with the partition function ${}^{\star}\bm{Z}^{\prime}$ on a full bipartite $(d,k)$-regular graph with $n^{\prime}$ variables and $m^{\prime}$ clauses. Away from the simplex boundary, empirical measures contributing to ${}^{\star}\bm{Z}^{\partial}[{\underline{\smash{\sigma}}}_{\mathscr{Y}}]$ can be parametrized as ${\bm{g}}-\bm{\delta}$ where ${\bm{g}}$ runs over the empirical measures contributing to ${}^{\star}\bm{Z}^{\prime}$. Writing $(a)_{b}$ for the falling factorial $a!/(a-b)!$, we have