2.1 Existence of the fixed point and upper bound

As a first step towards the proof of Theorem 1.1 we prove that the limit (1.6) exists for $d\lt d_{\mathrm{uniq}}(k)$ . More precisely, we will establish the following statement.

Proposition 2.1. For every $k \ge 3$ and every $d \lt d_{\mathrm{uniq}}(k)$ , the $W_1$ -limit $\pi _{d,k}=\lim _{\ell \to \infty }\mathrm{BP}_{d,k}^{\ell }(\delta _{1/2})$ exists and

(2.1) \begin{align} {\mathbb E}\left [ {\log ^2\boldsymbol{\mu }_{\pi _{d,k},1,1}}\right ] +{\mathbb E}\left |{\log \left ({\prod _{i=1}^{\boldsymbol{d}^-}\boldsymbol{\mu }_{\pi _{d,k},2i}+\prod _{i=1}^{\boldsymbol{d}^+}\boldsymbol{\mu }_{\pi _{d,k},2i-1}}\right )}\right |+{\mathbb E}\left |{\log \left ({1-\prod _{j=1}^k\boldsymbol{\mu }_{\pi _{d,k},1,j}}\right )}\right | & \lt \infty . \end{align}

In addition, $\boldsymbol{\mu }_{\pi _{d,k},1,1}$ and $1-\boldsymbol{\mu }_{\pi _{d,k},1,1}$ are identically distributed.

The existence of the limit $\pi _{d,k}$ is an easy consequence of the Gibbs uniqueness property. As an aside, the limit $\pi _{d,k}=\lim _{\ell \to \infty }\mathrm{BP}_{d,k}^{\ell }(\delta _{1/2})$ is a fixed point of the Belief Propagation operator, i.e.,

(2.2) \begin{align} \pi _{d,k} & =\mathrm{BP}_{d,k}(\pi _{d,k}). \end{align}

The proof of the bound (2.1) is a bit more subtle and requires a few preparations, but we will come to that. The upshot of (2.1) is that the Bethe free entropy $\mathfrak B_{d,k}(\pi _{d,k})$ is well defined.

With the fixed point $\pi _{d,k}$ in hand we can bring to bear the ‘interpolation method’ to the upper bound the likely value of $\log Z(\boldsymbol{\Phi })$ .

The interpolation method is a mainstay of the study of disordered systems in mathematical physics and has also been used to investigate random constraint satisfaction problems. In particular, the variant of the interpolation method from [Reference Panchenko and Talagrand61] (in combination with Proposition 2.1) easily implies that

\begin{align*} \limsup _{n\to \infty }\frac 1n{\mathbb E}\left [ {\log (Z(\boldsymbol{\Phi })\vee 1)}\right ] & \leq \mathfrak B_{d,k}(\pi _{d,k}) ; \end{align*}

taking the logarithm of $Z(\boldsymbol{\Phi })\vee 1$ ensures that the expectation is well defined, as it is possible (albeit unlikely for $d\lt d_{\mathrm{uniq}}(k)$ ) that $\boldsymbol{\Phi }$ is unsatisfiable. The added value of Corollary 2.2 is that we obtain a bound that holds with high probability, rather than just a bound on the expectation. The interpolation method was used in [Reference Achlioptas, Coja-Oghlan and Hahn-Klimroth3] in a similar fashion to prove a ‘with high probability’ bound on the number of satisfying assignments of random 2-CNFs. The proof of Corollary 2.2 is an adaptation of that argument to $k\geq 3$ .

2.2 A matching lower bound

The key step towards Theorem 1.1 is to establish a lower bound on $\log Z(\boldsymbol{\Phi })$ that matches the upper bound from Corollary 2.2. To accomplish this task we employ a coupling argument known as the ‘Aizenman-Sims-Starr scheme’ in mathematical physics. Its original version was intended to estimate the partition function of the Sherrington-Kirkpatrick model, a spin glass model [Reference Aizenman, Sims and Starr8]. But the technique has since been employed in probabilistic combinatorics (e.g., [Reference Coja-Oghlan, Kapetanopoulos and Müller24, Reference Coja-Oghlan, Krzakala, Perkins and Zdeborová25, Reference Coja-Oghlan and Perkins29]). By comparison to the mathematical physics context, the crucial difference is that here our objective is to count actual satisfying assignments where every single clause imposes a hard constraint, whereas in spin glass theory constraints are soft. The same issue occurred in previous work on the random 2-SAT problem [Reference Achlioptas, Coja-Oghlan and Hahn-Klimroth3]. However, in that case a relatively simple percolation argument was sufficient to deal with the ensuing complications. As we will see, for $k\geq 3$ considerably more care is needed.

But first things first. The basic idea behind the Aizenman-Sims-Starr argument is to perform a kind of induction. Translated to random $k$ -SAT this means that we couple the random $k$ -CNF $\boldsymbol{\Phi }_{d,k}(n)$ with $n$ variables with the random $k$ -CNF $\boldsymbol{\Phi }_{d,k}(n+1)$ with $n+1$ variables. Recall that $\boldsymbol{\Phi }_{d,k}(n)$ comprises $\boldsymbol{m}_n\sim \textrm {Po}(dn/k)$ independent random clauses. Ultimately Theorem 1.1 is going to be a consequence of Corollary 2.2 and the following statement.

Once again we work with $Z(\boldsymbol{\Phi }_{d,k}(n))\vee 1$ and $Z(\boldsymbol{\Phi }_{d,k}(n+1))\vee 1$ to ensure that the expectations are well defined.

To prove Proposition 2.3 we couple the random formulas $\boldsymbol{\Phi }_{d,k}(n+1)$ and $\boldsymbol{\Phi }_{d,k}(n)$ as follows.

1. CPL1: Let $\boldsymbol{\Phi }'$ be a random $k$ -CNF with variables $x_1,\ldots ,x_n$ and $\boldsymbol{m}'\sim \textrm {Po}(d(n-k+1)/k)$ clauses.

2. CPL2: Obtain $\boldsymbol{\Phi }''$ from $\boldsymbol{\Phi }'$ by adding another $\boldsymbol{\Delta }''\sim \textrm {Po}(d(k-1)/k)$ independent random clauses.

3. CPL3: Obtain $\boldsymbol{\Phi }'''$ from $\boldsymbol{\Phi }'$ by adding one new variable $x_{n+1}$ and $\boldsymbol{\Delta }'''\sim \textrm {Po}(d)$ independent random clauses that each contain $x_{n+1}$ and $k-1$ other variables from $\{x_1,\ldots ,x_n\}$ .

Observe that $\boldsymbol{\Phi }''$ ultimately has variables $x_1,\ldots ,x_n$ and a total of $\boldsymbol{m}_n\sim \textrm {Po}(dn/k)$ random clauses. Thus, $\boldsymbol{\Phi }''$ is identical to the random formula $\boldsymbol{\Phi }_{d,k}(n)$ . Similarly, $\boldsymbol{\Phi }'''$ has the same distribution as $\boldsymbol{\Phi }_{d,k}(n+1)$ . Consequently, we obtain the following.

The coupling CPL1–CPL3 reduces the proof of Proposition 2.3 to getting a handle on the differences $\log (Z(\boldsymbol{\Phi }'')\vee 1)-\log (Z(\boldsymbol{\Phi }')\vee 1)$ and $\log (Z(\boldsymbol{\Phi }''')\vee 1)-\log (Z(\boldsymbol{\Phi }')\vee 1)$ . More precisely, recalling (1.4)–(1.5), we see that Proposition 2.3 is a consequence of the following two statements.

Proposition 2.5. If $d\lt d_{\mathrm{uniq}}(k)$ then

(2.3) \begin{align} {\mathbb E}\left [ {\log \frac {Z(\boldsymbol{\Phi }'')\vee 1}{Z(\boldsymbol{\Phi }')\vee 1}}\right ] & =\frac {d(k-1)}{k}{\mathbb E}\left [ {\log \left ({1-\prod _{j=1}^k\boldsymbol{\mu }_{\pi _{d,k},1,j}}\right )}\right ] +o(1). \end{align}

Proposition 2.6. If $d\lt d_{\mathrm{uniq}}(k)$ then

(2.4) \begin{align} {\mathbb E}\left [ {\log \frac {Z(\boldsymbol{\Phi }''')\vee 1}{Z(\boldsymbol{\Phi }')\vee 1}}\right ] & ={\mathbb E}\left [ {\log \left ({\prod _{i=1}^{\boldsymbol{d}^-}\boldsymbol{\mu }_{\pi _{d,k},2i}+\prod _{i=1}^{\boldsymbol{d}^+}\boldsymbol{\mu }_{\pi _{d,k},2i-1}}\right )}\right ] +o(1). \end{align}

To prove Propositions 2.5– 2.6 we effectively need to trace the impact that local changes have on the number of satisfying assignments. Indeed, under the coupling CPL1–CPL3, the formula $\boldsymbol{\Phi }''$ is obtained from the ‘base formula’ $\boldsymbol{\Phi }'$ by adding just a bounded expected number of random clauses. Thus, if we imagine that, as both the first moment upper bound (1.13) and the balanced second moment lower bound (1.14) suggest, each additional random clause typically reduces the number of satisfying assignments by a constant factor, then the quantity $|\log (Z(\boldsymbol{\Phi }'')/Z(\boldsymbol{\Phi }'))|$ should be bounded with probability close to one. Similar reasoning applies to $\boldsymbol{\Phi }'''$ .

Yet while with high probability the local changes that turn $\boldsymbol{\Phi }'$ into $\boldsymbol{\Phi }''$ or $\boldsymbol{\Phi }'''$ are indeed benign, because we are dealing with hard constraints there is a non-negligible probability that $\log (Z(\boldsymbol{\Phi }'')/Z(\boldsymbol{\Phi }'))$ and $\log (Z(\boldsymbol{\Phi }''')/Z(\boldsymbol{\Phi }'))$ could be large. Indeed, a single extra clause might wipe out all satisfying assignments of $\boldsymbol{\Phi }'$ , in which case

\begin{align*} \log \frac {Z(\boldsymbol{\Phi }'')\vee 1}{Z(\boldsymbol{\Phi }') \vee 1}=-\log Z(\boldsymbol{\Phi }')=-\Omega (n). \end{align*}

Hence, we need to argue that such drastic changes are sufficiently rare. The following statement furnishes the necessary tail bound.

Proposition 2.7. For $d\lt d_{\mathrm{uniq}}(k)$ we have

(2.5) \begin{align} {\mathbb E}\left [ {\left |\log \frac {Z(\boldsymbol{\Phi }'')\vee 1}{Z(\boldsymbol{\Phi }')\vee 1}\right |^{3/2}+\left |\log \frac {Z(\boldsymbol{\Phi }''')\vee 1}{Z(\boldsymbol{\Phi }')\vee 1}\right |^{3/2}}\right ] =O(1). \end{align}

2.3 Pure literal pursuit

The proof of Proposition 2.7 constitutes the main technical challenge towards the proof of Theorem 1.1. The linchpin of the proof is an algorithm that we call Pure Literal Pursuit (‘ $\texttt {PULP}$ ’). Its purpose is to trace the repercussions of setting a relatively small number of variables to specific truth values. More precisely, $\texttt {PULP}$ will allow us to compare the number of satisfying assignments that set a few chosen variables to specific values to the total number of satisfying assignments.

To this end $\texttt {PULP}$ attempts to solve the following optimisation task. Suppose we are given a $k$ -CNF $\Phi$ and a set $\mathscr{L}$ of literals of $\Phi$ that we deem to be set to ‘true’. We would like to identify a superset $\skew9\bar{\mathscr{L}}\supseteq \mathscr{L}$ of literals with the following properties; think of $\skew9\bar{\mathscr{L}}$ as a ‘closure’ of $\mathscr{L}$ .

1. PULP1: every clause $a$ of $\Phi$ that contains a literal from $\neg \skew9\bar{\mathscr{L}}=\{\neg l\,:\,l\in \skew9\bar{\mathscr{L}}\}$ also contains a literal from $\skew9\bar{\mathscr{L}}$ .

2. PULP2: there is no literal $l$ such that $l,\neg l\in \skew9\bar{\mathscr{L}}$ .

Of course, it may be impossible to satisfy PULP1 and PULP2 simultaneously. In this case we ask $\texttt {PULP}$ to report a ‘contradiction’. But if PULP1–PULP2 can be satisfied, we aim to find a closure $\skew9\bar{\mathscr{L}}$ of as small size $|\skew9\bar{\mathscr{L}}|$ as possible.

The combinatorial idea behind PULP1–PULP2 is as follows. Deeming the literals from the initial set $\mathscr{L}$ ‘true’, our goal is to reconcile this assumption with the formula $\Phi$ . To this end we enhance the set $\mathscr{L}$ . Clearly, any clause that contains the negation $\neg l$ of a literal $l$ that we deem true also needs to contain another literal $l'$ that is set to true. This is what PULP1 asks. Furthermore, it would be contradictory to deem both $l$ and its negation $\neg l$ true; this is PULP2.

The size of the closure $\skew9\bar{\mathscr{L}}$ yields a bound on the reduction in the number of satisfying assignments if we indeed insist on all literals $l\in \mathscr{L}$ being set to true. Formally, let $S(\Phi ,\mathscr{L})$ be the set of all satisfying assignments $\sigma \in S(\Phi )$ under which all literals $l\in \mathscr{L}$ evaluate to ‘true’. Also set $Z(\Phi ,\mathscr{L})=|S(\Phi ,\mathscr{L})|$ .

In order to identify a ‘small’ closure $\skew9\bar{\mathscr{L}}$ the $\texttt {PULP}$ algorithm resorts to pure literal elimination, a simple trick commonplace to satisfiability algorithms. A variable $x$ is pure in a CNF formula $\Phi$ if $\mathrm{sign}(x,a)=\mathrm{sign}(x,b)$ for any two clauses $a,b\in \partial x$ . Clearly, if our objective is to construct a satisfying assignment, we might as well set all pure variables $x$ to the value that satisfies all clauses $a\in \partial x$ and disregard these clauses henceforth. In light of this observation, pure literal elimination repeatedly removes all clauses that contain a pure variable. Naturally, every round of clause removals may create new pure variables, and thus more clauses may be ripe for removal in the next round. For a clause $a$ of the original formula $\Phi$ let $\mathfrak{h}_a(\Phi )\geq 1$ be the number of the round at which pure literal elimination removes $a$ . If $a$ is never removed then we set $\mathfrak{h}_a(\Phi )=\infty$ .

The $\texttt {PULP}$ algorithm invokes a slightly modified version of pure literal elimination to accommodate the initial set $\mathscr{L}$ of literals. Specifically, for a variable $x$ of a CNF $\Phi$ and $s\in \{\pm 1\}$ let $\Phi [x\mapsto s]$ be the CNF obtained by removing all clauses $a\in \partial x$ with $\mathrm{sign}(x,a)=s$ and removing the literal $-s\cdot x$ from all $a\in \partial x$ with $\mathrm{sign}(x,a)=-s$ . The definition reflects that if we set $x$ to value $s$ , all $a\in \partial ^s x$ will be satisfied, while all $a\in \partial ^{-s} x$ will have to be satisfied by one of their other constituent literals. Further, let

(2.6) \begin{align} \mathfrak{h}_x(s,\Phi ) & = \begin{cases} 0 & \mbox{ if }\partial _\Phi ^{-s} x=\emptyset ,\\ \max \left \{{\mathfrak{h}_a(\Phi [x\mapsto s])\,:\,a\in \partial _\Phi ^{-s} x}\right \} & \mbox{ otherwise.} \end{cases} \qquad \in [0,\infty ]. \end{align}

We refer to $\mathfrak{h}_x(s,\Phi )$ as the height of literal $s\cdot x$ in $\Phi$ .

The $\texttt {PULP}$ algorithm, displayed as Algorithm 1, harnesses the heights as follows. In its attempt to precipitate PULP1 and PULP2 the algorithm iteratively enhances the set $\mathscr{L}$ of literals deemed to be ‘true’. For any clause $a$ that violates PULP1 and that contains a literal $l\not \in \neg \mathscr{L}$ the algorithm adds one such literal $l$ of minimum height to $\mathscr{L}$ . This choice is intended to keep the ultimate size of the closure small; one could say that $\texttt {PULP}$ uses height as a proxy of ‘size’. If at any point the algorithm encounters a clause $a$ that consists of literals from $\neg \mathscr{L}$ only, the algorithm reports a contradiction and aborts.

Algorithm 1.

The $\texttt {PULP}$ algorithm

Algorithm 1 Long description

An algorithm for enhancing a set of literals. The algorithm starts by initializing a set of literals. It then enters a loop where it checks for clauses that contain a literal not in the set of negated literals but no literal from the set of literals. If such a clause is found, it picks the clause that minimizes the distance from the initial set of literals. If the clause consists of literals only from the set of negated literals, the algorithm returns a contradiction and halts. Otherwise, it chooses a literal from the clause that minimizes a certain function and adds the sign of that literal multiplied by the literal itself to the set of literals. The algorithm then returns the enhanced set of literals.

From here on we write $\skew9\bar{\mathscr{L}}$ for the set of literals returned by $\texttt {PULP}$ if the algorithm does not encounter a contradiction; in the event of a a contradiction we let $\skew9\bar{\mathscr{L}}=\{x,\neg x\,:\,x\in V(\Phi )\}$ be the set of all literals. Where the reference to the formula $\Phi$ is not entirely obvious, we write $\skew9\bar{\mathscr{L}}_{\Phi }$ . The analysis of $\texttt {PULP}$ on the random formula $\boldsymbol{\Phi }'$ furnishes the following bound on $|\skew9\bar{\mathscr{L}}|$ in terms of the size of the initial set $\mathscr{L}$ . This bound is the key ingredient towards the proof of Proposition 2.7.

The proof of Lemma 2.10 is one of the main technical challenges of the present work. The difficulty stems from the stochastic dependencies that are inherent to the $\texttt {PULP}$ algorithm. Specifically, in order to decide which literals to add to the set $\mathscr{L}$ , $\texttt {PULP}$ requires knowledge of the heights $\mathfrak{h}_{x}(\pm 1,\boldsymbol{\Phi }')$ . But these heights depend on the other variables $y\in \partial a\setminus \left \{{x}\right \}$ , the clauses that these variables $y$ appear in, etc. Furthermore, in its subsequent iterations the algorithm is apt to revisit some of these variables and clauses at a point when their heights have already been revealed. These repetitions rule out an analysis of $\texttt {PULP}$ by way of routine techniques such as the principle of deferred decisions or the differential equations method. The reason why we manage to cope with these complicated dependencies at all is that, remarkably, the heights $\mathfrak{h}_{x}(\pm 1,\boldsymbol{\Phi }')$ have only a tiny upper tail. More precisely, as we will see the tails of these random variables decay at a doubly exponential rate.

Proposition 2.7 follows from the analysis of $\texttt {PULP}$ . The basic idea is to apply the algorithm to an initial set $\mathscr{L}$ of literals that contain one literal from each of the extra clauses that are present in $\boldsymbol{\Phi }''$ or $\boldsymbol{\Phi }'''$ but not in $\boldsymbol{\Phi }'$ . With a bit of care the bounds from Lemmas 2.8 and 2.10 then imply (2.5). Finally, the analysis of $\texttt {PULP}$ that leads up to the proof of Lemma 2.10 also implies the necessary tail bounds to verify the bounds from (2.1). Specifically, the proof of Lemma 2.10 proceeds by way of analysing $\texttt {PULP}$ on the Galton-Watson tree $\mathbb{T}_{d,k}$ , and the bounds (2.1) come out as a byproduct of that analysis.

2.4 Completing the Aizenman-Sims-Starr scheme

To obtain Propositions 2.5– 2.6 we combine Proposition 2.7 with an analysis of the quotients $Z(\boldsymbol{\Phi }'')/Z(\boldsymbol{\Phi }')$ and $Z(\boldsymbol{\Phi }''')/Z(\boldsymbol{\Phi }')$ on a likely ‘good’ event. On this good event the empirical distribution of the marginal probabilities $({\mathbb P}[\boldsymbol{\sigma }_{\boldsymbol{\Phi }'}(x_i)=1\mid \boldsymbol{\Phi }'])_{1\leq i\leq n}$ of the different variables $x_i$ receiving the value ‘true’ under a random satisfying assignment is ‘close’ to the limiting distribution $\pi _{d,k}$ from Proposition 2.1. Additionally, on the good event the joint distribution of the truth values assigned to a moderate number of variables is well approximated by a product measure. Of course, to make this precise we need to investigate the empirical distribution

(2.7) \begin{align} \boldsymbol{\pi }_n' & =\frac 1n\sum _{i=1}^n\delta _{{\mathbb P}[\boldsymbol{\sigma }_{\boldsymbol{\Phi }'}(x_i)=1\mid \boldsymbol{\Phi }']}\in \mathscr{P}(0,1) \end{align}

of the marginals $({\mathbb P}[\boldsymbol{\sigma }_{\boldsymbol{\Phi }'}(x_i)=1\mid \boldsymbol{\Phi }'])_{1\leq i\leq n}$ .

Proposition 2.11. Assume that $d\lt d_{\mathrm{uniq}}(k)$ . Then ${\mathbb E}\left [ {W_1(\boldsymbol{\pi }_n',\pi _{d,k})}\right ] =o(1)$ and for any $\ell = O(1)$ we have

\begin{align*} \sum _{\sigma \in \{\pm 1\}^\ell }{\mathbb E}\left |{{\mathbb P}\left [ {\forall 1\leq i\leq \ell \,:\,\boldsymbol{\sigma }_{\boldsymbol{\Phi }'}(x_i)=\sigma _i\mid \boldsymbol{\Phi }'}\right ] -\prod _{i=1}^\ell {\mathbb P}\left [ {\boldsymbol{\sigma }_{\boldsymbol{\Phi }'}(x_i)=\sigma _i\mid \boldsymbol{\Phi }'}\right ] }\right | & =o(1). \end{align*}

The proof of Proposition 2.11 hinges on the Gibbs uniqueness property and the convergence of the local topology of the random formula $\boldsymbol{\Phi }'$ to the Galton-Watson tree $\mathbb{T}_{d,k}$ . Together with careful coupling arguments Propositions 2.7– 2.11 imply Propositions 2.5– 2.6. Moreover, in combination with Fact 2.4 these two propositions yield Proposition 2.3. We complete this paragraph by showing how Theorem 1.1 follows from Corollary 2.2 and Proposition 2.3.

Proof of Theorem 1.1. The existence of the limit (1.6) follows from Proposition 2.1. With respect to (1.7), we apply Proposition 2.3 to obtain

(2.8) \begin{align} \nonumber \frac {1}{n}\mathbb{E}\left [ {\log (1 \vee Z(\boldsymbol{\Phi }_{d,k}(n)))}\right ] & =\frac {1}{n}\sum _{N=0}^{n-1} \left (\mathbb{E}\left [ {\log (1 \vee Z(\boldsymbol{\Phi }_{d,k}(N+1))}\right ] - \mathbb{E}\left [ {\log (1 \vee Z(\boldsymbol{\Phi }_{d,k}(N))}\right ] \right )\\ & = \mathfrak B_{d,k}(\pi _{d,k}) + o(1). \end{align}

Since, conversely, Corollary 2.2 shows that $\frac 1n\log Z(\boldsymbol{\Phi })\leq \mathfrak B_{d,k}(\pi _{d,k})+o(1)$ w.h.p. and since $\log Z(\boldsymbol{\Phi })\leq n\log 2$ deterministically, the assertion follows from (2.8).

2.5 Lower-bounding the uniqueness threshold

The proof of Theorem 1.2 combines three ingredients. From the work [Reference Achlioptas, Coja-Oghlan and Hahn-Klimroth3] on random 2-SAT we borrow the idea of constructing an explicit extremal boundary configuration. In effect, in order to prove Gibbs uniqueness we just have to consider one single boundary configuration, instead of an enormous number of possible configurations $\tau$ that grows quickly with the height $\ell$ as in the original definition (1.1). Second, from the work [Reference Montanari and Shah57] of Montanari and Shah we borrow the idea of expressly considering the effect of pure literals. As it turns out, without explicit consideration of pure literals it seems difficult to even recover the correct asymptotic order (1.8) of the Gibbs uniqueness threshold. Third, and most importantly, the improvement over the bound from [Reference Montanari and Shah57] stems from a new subtle coupling argument that we will explain in due course.

2.5.1 The extremal boundary condition

An obvious challenge associated with establishing the Gibbs uniqueness property (1.1) seems to be that we need to estimate the marginal of the root variable given any possible boundary condition, i.e., given any assignment of the variables at distance $2\ell$ from $\mathfrak{x}$ . As we expect to see $(d (k-1))^\ell$ variables at distance $2\ell$ from $\mathfrak{x}$ , we thus face a doubly exponential number $2^{(d (k-1))^\ell }$ of possible boundary conditions. But fortunately, following [Reference Achlioptas, Coja-Oghlan and Hahn-Klimroth3] we may confine ourselves to just a single, explicit boundary configuration $\boldsymbol{\tau }^+$ that satisfies

(2.9) \begin{align} & {\mathbb P}\big [ {\boldsymbol{\tau }^{(\ell )}(r)=1\mid \mathbb{T},\,\forall x\in \partial ^{2\ell }r\,:\,\boldsymbol{\tau }^{(\ell )}(x)=\boldsymbol{\tau }^+(x)}\big]\nonumber\\ & \qquad \qquad \!\!= \max _{\tau \in S(\mathbb{T}^{(\ell )})} {\mathbb P}\big[ {\boldsymbol{\tau }^{(\ell )}(r)=1\mid \mathbb{T},\,\forall x\in \partial ^{2\ell }r\,:\,\boldsymbol{\tau }^{(\ell )}(x)=\tau (x)}\big] . \end{align}

Due to the inherent symmetry of the distribution of $\mathbb{T}$ with respect to the signs of the clauses, towards the proof of (1.1) it is sufficient to show that the difference (2.9) vanishes as $\ell \to \infty$ .

The extremal boundary condition can be constructed explicitly. Specifically, given ${\mathbb{T}}^{(\ell )}$ we construct a satisfying assignment $\boldsymbol{\tau }^+\in S(\mathbb{T}^{(\ell )})$ by working our way down the tree ${\mathbb{T}}^{(\ell )}$ . We begin by setting $\boldsymbol{\tau }^+(\mathfrak{x}) = 1$ . Now suppose that for $q \ge 1$ , the values of the variables at distance $2(q-1)$ from $\mathfrak{x}$ have been already determined. Let $w$ be a variable at distance $2q$ from $\mathfrak{x}$ with parent clause $a$ and grandparent variable $u$ . Then we define

(2.10) \begin{align} \boldsymbol{\tau }^+(w) = \mathrm{sign}(w,a)\cdot \unicode {x1D7D9} \{\mathrm{sign}(u,a)\neq \boldsymbol{\tau }^+(u)\} -\mathrm{sign}(w,a)\cdot \unicode {x1D7D9} \{\mathrm{sign}(u,a)=\boldsymbol{\tau }^+(u)\}. \end{align}

The idea behind (2.10) is for $\boldsymbol{\tau }^+(w)$ to ‘nudge’ $u$ towards $\boldsymbol{\tau }^+(u)$ by making sure that $w$ satisfies clause $a$ if setting $u$ to $\boldsymbol{\tau }^+(u)$ does not, and conversely making sure that $w$ fails to satisfy clause $a$ if setting $u$ to $\boldsymbol{\tau }^+(u)$ does. A simple induction on $\ell$ shows that $\boldsymbol{\tau }^+$ is a satisfying assignment for which (2.9) holds.

Lemma 2.12. For any integer $\ell \geq 0$ the assignment $\boldsymbol{\tau }^+$ defined via (2.10) satisfies (2.9).

Hence, proving Theorem 1.2 reduces to establishing the following.

Proposition 2.13. For $d \lt {{{d_{\mathrm{con}}}}}(k)$ we have that

(2.11) \begin{align} \lim _{\ell \to \infty }\mathbb{E}\big [ {{\mathbb P}\big [ {\boldsymbol{\tau }^{(\ell )}(\mathfrak{x})=1\mid \mathbb{T},\,\forall x\in \partial ^{2\ell }\mathfrak{x}\,:\,\boldsymbol{\tau }^{(\ell )}(x)=\boldsymbol{\tau }^+(x)}\big ] -{\mathbb P}\big [ {\boldsymbol{\tau }^{(\ell )}(\mathfrak{x})=1\mid \mathbb{T}}\big ] }\big ] =0. \end{align}

The proof of Proposition 2.13 may seem delicate because the boundary condition $\boldsymbol{\tau }^+$ depends on the tree ${\mathbb{T}}^{(\ell )}$ . To sidestep this problem, we generalise another idea from the work [Reference Achlioptas, Coja-Oghlan and Hahn-Klimroth3] on random $2$ -SAT to $k\geq 3$ by introducing a quantity that allows us to prove (2.13) but that behaves ‘Markovian’ as we pass up and down the tree. Specifically, for a variable $x$ of ${\mathbb{T}}^{(\ell )}$ let $\mathbb{T}_x^{(\ell )}$ be the sub-formula of ${\mathbb{T}}^{(\ell )}$ comprising $x$ and its progeny. Moreover, for a satisfying assignment $\tau \in S({\mathbb{T}}^{(\ell )})$ let

\begin{align*} S\big({\mathbb{T}}_x^{(\ell )},\tau \big) & = \big \{{\chi \in S\big({\mathbb{T}}_x^{(\ell )}\big)\,:\, \forall y\in V\big({\mathbb{T}}_x^{(\ell )}\big)\cap \partial ^{2\ell }_{\mathbb{T}}\mathfrak{x} \,:\, \chi _y=\tau _y }\big \}, & Z\big({\mathbb{T}}_x^{(\ell )},\tau \big) & =\big |{S\big({\mathbb{T}}_x^{(\ell )},\tau \big)}\big |. \end{align*}

In words, $S({\mathbb{T}}_x^{(\ell )},\tau )$ contains all satisfying assignments of ${\mathbb{T}}_x^{(\ell )}$ that comply with the boundary condition induced by $\tau$ . Additionally, for $t=\pm 1$ let

\begin{align*} S\big({\mathbb{T}}_x^{(\ell )},\tau ,t\big) & =\big \{{\chi \in S\big({\mathbb{T}}_x^{(\ell )},\tau \big)\,:\,\chi _x=t}\big \}, & Z\big({\mathbb{T}}_x^{(\ell )},\tau ,t\big) & =\big|{S\big({\mathbb{T}}_x^{(\ell )},\tau ,t\big) }\big | \end{align*}

be the set and number of satisfying assignments of ${\mathbb{T}}_x^{(\ell )}$ that agree with $\tau$ on the boundary and assign value $t$ to $x$ . Finally, let

(2.12) \begin{align} {\boldsymbol{\eta }}_{x}^{(\ell )} & = \log \frac {Z\big({\mathbb{T}}_x^{(\ell )},\boldsymbol{\tau }^+,\boldsymbol{\tau }^+(x)\big)} {Z\big({\mathbb{T}}_x^{(\ell )},\boldsymbol{\tau }^+,-\boldsymbol{\tau }^+(x)\big)} \in \mathbb{R}\cup \{\pm \infty \} \end{align}

be the log-likelihood ratio that gauges how likely a random satisfying assignment $\boldsymbol{\tau }$ of ${\mathbb{T}}_x^{(\ell )}$ subject to the $\boldsymbol{\tau }^+$ -boundary condition is to set $x$ to its designated value $\boldsymbol{\tau }^+(x)$ from (2.10). In terms of (2.12), the proof of Proposition 2.13 comes down to showing that for $d\lt {{{d_{\mathrm{con}}}}}(k)$ ,

(2.13) \begin{align} \lim _{\ell \to \infty }{\boldsymbol{\eta }}_{\mathfrak{x}}^{(\ell )} & =\log \left (\frac {\boldsymbol{\mu }_{\pi _{d,k},1,1}}{1-\boldsymbol{\mu }_{\pi _{d,k},1,1}}\right )\quad \mbox{in distribution}. \end{align}

For a start, the following lemma bounds the tails of ${\boldsymbol{\eta }}_{x}^{(\ell )}$ for large enough $\ell$ and $x$ reasonably close to the root variable $\mathfrak{x}$ .

Lemma 2.14. For every $0\lt d\lt {{{d_{\mathrm{con}}}}}(k)$ there exist $c=c(d,k)$ and a sequence $(\varepsilon _t)_t$ with $\lim _{t \to \infty }\varepsilon _t = 0$ such that for any $t\gt 0$ , $\ell \gt ct^c$ we have

(2.14) \begin{align} {\mathbb P} \left [\max _{x \in \partial ^{2t}\mathfrak{x}} \;\left |{\boldsymbol{\eta }}_x^{(\ell )}\right | \le 2t^c\right ] \gt 1 - \varepsilon _t. \end{align}

The proof of Lemma 2.14 rests on combinatorial arguments reminiscent of the analysis of $\texttt {PULP}$ .

A key feature of the definition (2.12) is that the random variables $\boldsymbol{\eta }_x^{(\ell )}$ exhibit a ‘reverse Markovian’ behaviour. This is because $\boldsymbol{\eta }_x^{(\ell )}$ depends only on $\boldsymbol{\tau }^+(x)$ and the part $\mathbb{T}_x^{(\ell )}$ of the tree pending on $x$ . Furthermore, because the distribution of the random tree $\mathbb{T}_x^{(\ell )}$ is symmetric with respect to sign flips, even the dependence on the value $\boldsymbol{\tau }^+(x)$ can be eliminated. All we need to keep in mind is that the values $\boldsymbol{\tau }^+(y)$ for $y\in V(\mathbb{T}_x^{(\ell )})$ are constructed from the value $\boldsymbol{\tau }^+(x)$ in accordance with the recurrence (2.10). Thus, by flipping all signs in the tree $\mathbb{T}_x^{(\ell )}$ if necessary, we could assume without loss that $\boldsymbol{\tau }^+(x)=1$ without changing the distribution of $\boldsymbol{\eta }_x^{(\ell )}$ with respect to the randomness of $\mathbb{T}_x^{(\ell )}$ . As a consequence, it is possible to set up a recurrence that expresses the log-likelihood ratios $\boldsymbol{\eta }_x^{(\ell )}$ of variables $x$ at distance $q$ from $\mathfrak{x}$ in terms of the $\boldsymbol{\eta }_y^{(\ell )}$ for $y$ at distance $q+2$ from $\mathfrak{x}$ .

Due to the recursive nature of the random tree $\mathbb{T}$ , it suffices to set up this recurrence for the root $\mathfrak{x}$ of the tree. In other words, to prove (2.13) we just need a recurrence that expresses the distribution of the random variable $\boldsymbol{\eta }_{\mathfrak{x}}^{(\ell +1)}$ in terms of the law of $\boldsymbol{\eta }_{\mathfrak{x}}^{(\ell )}$ for $\ell \geq 0$ . A bit of reflection (see Claim 7.1), reveals that the corresponding distributional operator

\begin{align*} \mathrm{LL}^+_{d,k}\,:\,\mathscr{P}((\!-\infty , \infty ])\to \mathscr{P}((\!-\infty , \infty ]) ,\quad \rho \mapsto \hat {\rho }=\mathrm{LL}^+_{d,k}(\rho ) \end{align*}

has the following shape. For a distribution $\rho \in \mathscr{P}((\!-\infty , \infty ])$ let $(\boldsymbol{\eta }_{\rho ,i,j})_{i,j\geq 1}$ be a family of random variables with distribution $\rho$ . Moreover, let $(\boldsymbol{s}_i)_{i\geq 1}$ be a sequence of uniformly random $\pm 1$ -valued random variables and let ${\boldsymbol{d}}\sim \textrm {Po}(d)$ . All of these random variables are mutually independent. Additionally, for $q\geq 0$ and $z_1,\ldots ,z_q\in \mathbb{R}\cup \{\pm \infty \}$ define

(2.15) \begin{align} \Gamma (z_1,\ldots ,z_q) & = \prod _{i=1}^{q} \frac {1 +\tan\, h (z_i/2)} {2}. \end{align}

Then $\hat {\rho }=\mathrm{LL}^+_{d,k}(\rho )$ is the distribution of the random variable

(2.16) \begin{align} -\sum _{i=1}^{\boldsymbol{d}} & \boldsymbol{s}_i \cdot \log \left ( 1- {\Gamma \left (\boldsymbol{s}_i\cdot \bigl ( {{\boldsymbol{\eta }}_{\rho , i, 1}}, \ldots , {{\boldsymbol{\eta }}_{\rho , i, k-1}} \bigr ) \right )} \right ) . \end{align}

Ultimately we will derive (2.13), and thereby Proposition 2.13, from Lemma 2.14 and a contraction argument. However, this is not quite as straightforward as one might be inclined to expect. Indeed, at first glance, a natural approach to proving (2.13) from Lemma 2.14 seems to be to show that $\mathrm{LL}^+_{d,k}$ is a contraction, say, with respect to the $W_1$ -metric. This is indeed carried out in [Reference Achlioptas, Coja-Oghlan and Hahn-Klimroth3] for $k=2$ , where it is shown that $\mathrm{LL}^+_{d,2}$ contracts for all $0\lt d\lt 2$ , i.e., right up to the random 2-SAT satisfiability threshold. However, for $k\geq 3$ we can only show that $\mathrm{LL}^+_{d,k}$ contracts for $d\lt 2/(k-1)$ , a value well below ${{{d_{\mathrm{con}}}}}(k)$ and short of the correct asymptotic order (1.10).

2.5.2 Pure and mixed literals

To cover a larger range of $d$ we borrow from [Reference Montanari and Shah57] the idea of expressly taking into account pure literals. To elaborate, while $\mathrm{LL}^+_{d,k}$ describes how the law of $\boldsymbol{\eta }_{\mathfrak{x}}^{(\ell +1)}$ results from that of $\boldsymbol{\eta }_{\mathfrak{x}}^{(\ell )}$ , the operator fails to take into account that $\mathfrak{x}$ itself as well as some of the grandchildren of $\mathfrak{x}$ in $\mathbb{T}$ may be pure literals. However, the pure literal property has a marked effect on the log-likelihood ratios. For if, say, $\mathfrak{x}$ only appears positively, then a simple double counting argument shows that $\boldsymbol{\eta }_{\mathfrak{x}}^{(\ell )}\geq 0$ for all $\ell$ . By extension, pure literals among the grandchildren of $\mathfrak{x}$ have a ‘dampening’ effect and may thus improve the range of $d$ for which we can establish contraction.

For a variable node $x$ of $\mathbb{T}$ , let us denote by $\mathbb{T}_x$ the subtree of $\mathbb{T}$ rooted at $x$ and containing its progeny. Leveraging the above observation, we classify a variable $x$ of $\mathbb{T}$ as , $\oplus$ , $\ominus$ , or $\mathrel {{\Large\unicode{x25EF}}}$ , depending on whether $x$ appears both positively and negatively in $\mathbb{T}_x$ , only positively, only negatively, or whether $x$ has no children at all, respectively. Furthermore, instead of just tracing the law of $\boldsymbol{\eta }_{\mathfrak{x}}^{(\ell )}$ for $\ell \geq 0$ , we study the four separate conditional distributions given the type or $\mathrel {{\Large\unicode{x25EF}}}$ of $\mathfrak{x}$ . Of course, the distribution of $\boldsymbol{\eta }_{\mathfrak{x}}^{(\ell )}$ given type $\mathrel {{\Large\unicode{x25EF}}}$ (i.e., $\mathfrak{x}$ has no children) is just the atom at zero for all  $\ell$ .

To describe the evolution of the other distributions we introduce the operator

(2.17)

defined as follows. Let $\boldsymbol{d}_{+}^{\star }, {\boldsymbol{d}_{+}^{\star }}^{\prime }, \boldsymbol{d}_{-}^{\star }, {\boldsymbol{d}_{-}^{\star }}^{\prime }$ be Poisson variables with parameter $d/2$ , conditioned on being positive. Moreover, let be multinomial variables with $k-1$ trials and probabilities

(2.18)

For $i,j \ge 1$ let , ${\boldsymbol{\eta }}_{\oplus ,i,j}$ , ${\boldsymbol{\eta }}_{\ominus ,i,j}$ be random variables with law , $\rho _{\oplus }$ , $\rho _{\ominus }$ , respectively. All of the aforementioned random variables are mutually independent. Further, for a sign $\varepsilon \in \{\pm 1\}$ and a vector $r=(r_{\raise-1pt\hbox{$\bullet$}}, r_{\oplus }, r_{\ominus }, r_{\unicode{x25EF}})$ of non-negative integers with $r_{\raise-1pt\hbox{$\bullet$}} + r_{\oplus } + r_{\ominus } + r_{\unicode{x25EF}} = {k-1}$ and $i\geq 0$ , $1\leq j\leq 4$ we let

(2.19) \begin{align} \boldsymbol{\Xi }_{i,j}(\varepsilon ,r) & = 1 - \frac {1}{2^{{r}_{\unicode{x25EF}}}} \cdot \Gamma (\varepsilon ( {{\boldsymbol{\eta }}_{\raise-1pt\hbox{$\bullet$},4i+j,1}},\ldots ,{{\boldsymbol{\eta }}_{\raise-1pt\hbox{$\bullet$},4i+j,r_{\raise-0.5pt\hbox{$\bullet$}}}} ) ) \Gamma (\varepsilon ( {{\boldsymbol{\eta }}_{\oplus ,4i+j,1}},\ldots ,{{\boldsymbol{\eta }}_{\oplus ,4i+j,r_{\oplus }}} ) )\\ & \quad \Gamma (\varepsilon ( {{\boldsymbol{\eta }}_{\ominus ,4i+j,1}},\ldots ,{{\boldsymbol{\eta }}_{\ominus ,4i+j,r_{\ominus }}}) ).\nonumber \end{align}

The r.h.s. of (2.19) amounts to rewriting the argument of the logarithm in (2.16) when the number of variables of each type is distributed according to $r$ . Finally, let

(2.20) \begin{align} \boldsymbol{\Xi }_{i,j}=\boldsymbol{\Xi }_{i,j}\left ({(-1)^{j+1},\boldsymbol{r}_{4i+j}}\right )\!. \end{align}

Then the operator (2.17) maps $\rho _{\raise-1pt\hbox{$\bullet$}}, \rho _{\oplus }, \rho _{\ominus }$ to the distributions $\hat {\rho }_{\raise-1pt\hbox{$\bullet$}}, \hat {\rho }_{\oplus }, \hat {\rho }_{\ominus }$ of the random variables

(2.21) \begin{align} \hat {\rho }_{\raise-1pt\hbox{$\bullet$}} & \sim -\sum _{i =1}^{\boldsymbol{d}_{+}^{\star }} \log \,\boldsymbol{\Xi }_{i,1}+\sum _{i =1}^{\boldsymbol{d}_{-}^{\star }} \log \,\boldsymbol{\Xi }_{i,2}, & \hat {\rho }_{\oplus } & \sim -\sum _{i =1}^{{\boldsymbol{d}_{+}^{\star }}'} \log \, \boldsymbol{\Xi }_{i,3}, & \hat {\rho }_{\ominus } & \sim +\sum _{i =1}^{{\boldsymbol{d}_{-}^{\star }}'} \log \, \boldsymbol{\Xi }_{i,4}. \end{align}

2.5.3 Coupling and contraction

While Montanari and Shah [Reference Montanari and Shah57] do not write their proof of the lower bound $d_{\mathrm{MS}}(k)\leq d_{\mathrm{uniq}}(k)$ in the language of distributional recurrences, translating their argument to the current formalism evinces two key differences by comparison to the approach that we are going to take. First, Montanari and Shah establish contraction with respect to messages from clauses to variables, instead of messages from variables to clauses as considered here.

While this change of perspective may seem innocuous at first, working with respect to variables provides us with greater control over how the change in log-likelihood ratios propagates. In particular, working with variable-to-clause messages and taking into account the four variable types $\raise-1pt\hbox{$\bullet$},\oplus ,\ominus ,\mathrel {{\Large\unicode{x25EF}}}$ allows us to optimise the metric with respect to which we establish contraction. Hence, for $t\gt 0$ we endow the space $\mathscr{P} (\!-\infty ,\infty ] \times \mathscr{P} (0, +\infty ] \times \mathscr{P}(\!-\infty , 0]$ with the metric

(2.22) \begin{align} \mathrm{dist}_{t}\left ( \left (\rho _{\raise-1pt\hbox{$\bullet$}}, \rho _{\oplus }, \rho _{\ominus }\right ), \left ({\rho }_{\raise-1pt\hbox{$\bullet$}}', {\rho }_{\oplus }', {\rho }_{\ominus }'\right ) \right ) & = \left (1-e^{-t/2}\right ) \cdot W_1\left (\rho _{\raise-1pt\hbox{$\bullet$}}, {\rho }_{\raise-1pt\hbox{$\bullet$}}'\right ) + e^{-t/2}\cdot W_1\left (\rho _{\oplus }, {\rho }_{\oplus }'\right )\\ & \qquad + e^{-t/2}\cdot W_1\left (\rho _{\ominus }, {\rho }_{\ominus }'\right ). \nonumber \end{align}

The following proposition summarises the main step towards the proof of Theorem 1.2.

Proposition 2.15. For every $d\lt {{{d_{\mathrm{con}}}}}(k)$ , the operator ${\mathrm{LL}}^{\star }_{d,k}$ is a contraction with respect to the metric $\mathrm{dist}_{d}$ .

The second key difference between [Reference Montanari and Shah57] and the present approach will emerge in the proof of Proposition 2.15 itself. As we are about to see, leveraging the four variable types enables us to carry out a sharper bound on the derivative of our operator ${\mathrm{LL}}^{\star }_{d,k}$ . This comes in the form of a subtle combinatorial coupling between variable types among clauses with opposite signs. To explain this, we recall that ${\mathrm{LL}}^{\star }_{d,k}$ describes how the laws of the log-likelihood ratios $\rho _{\raise-1pt\hbox{$\bullet$}}, \rho _{\oplus }$ , and $\rho _{\ominus }$ , evolve given the corresponding laws of the variables in one generation below. Recall also that we are always considering the positive boundary condition, i.e., the one maximising the value of each log-likelihood ratio.

Let us write $\rho = (\rho _{\raise-1pt\hbox{$\bullet$}}, \rho _{\oplus }, \rho _{\ominus })$ , $\rho ' = (\rho '_{\raise-1pt\hbox{$\bullet$}}, \rho '_{\oplus }, \rho '_{\ominus })$ , and $\hat {\rho }, \hat {\rho }'$ for their corresponding images under the operator ${\mathrm{LL}}^{\star }_{d,k}$ . We wish to establish that $\mathrm{dist}_d(\hat {\rho }, \hat {\rho }') \lt c\cdot \mathrm{dist}_d(\rho , \rho ')$ , for some constant $c=c(d,k) \lt 1$ . We call a clause $a$ positive if it contains its parent variable as a direct literal; otherwise, we call $a$ negative. The change between the output distributions $\hat {\rho }, \hat {\rho }'$ describing the log-likelihood law of, say, variable $\mathfrak{x}$ , comes from two sources: the positive and the negative children of $\mathfrak{x}$ . Observe that there is no obvious symmetry between the two, as we have imposed the positive boundary condition, and therefore, the influence of positive clauses is typically more pronounced. In turn, the change caused by each clause can be further attributed to that of the $k-1$ grandchildren variables it features. To be more precise, let us consider the contribution of a single positive clause $a$ . Let us write $\boldsymbol{r}=(\boldsymbol{r}_{\raise-1pt\hbox{$\bullet$}}, \boldsymbol{r}_{\oplus }, \boldsymbol{r}_{\ominus }, \boldsymbol{r}_{\unicode{x25EF}})$ for the type-distribution of the children variables of $a$ , where $\boldsymbol{r}$ follows the law described in (2.18). Consider also an arbitrary enumeration of the variables of each type $t \in \{\raise-1pt\hbox{$\bullet$}, \oplus , \ominus \}$ , and write $\mathscr{D}_i^{t}(z, \boldsymbol{r}; +1)$ for the magnitude of the partial derivative of the message clause $a$ sends to $\mathfrak{x}$ , with respect to the message clause $a$ receives from its $i$ -th variable of type $t$ . Then, the expected contribution of clause $a$ to the distance $\mathrm{dist}(\hat {\rho }, \hat {\rho }')$ is bounded in terms of $\mathscr{D}_i^{t}(z, \boldsymbol{r}; +)$ ’s as follows

(2.23) \begin{align} \mathbb{E}\left [ { \sum _{i=1}^{\boldsymbol{r}_{\raise-1pt\hbox{$\bullet$}}} \left |\int _{{{\boldsymbol{\eta }}}_{\raise-1pt\hbox{$\bullet$}, i}}^{{{\boldsymbol{\eta }}}'_{\raise-1pt\hbox{$\bullet$}, i}}\! \mathscr{D}^{\raise-1pt\hbox{$\bullet$}}_{i}(w_i, \boldsymbol{r};+\!1) {\mathrm d} w_i \right | + \sum _{j=1}^{\boldsymbol{r}_{\oplus }} \!\left | \int _{{{\boldsymbol{\eta }}}_{\oplus , j}}^{{{\boldsymbol{\eta }}}'_{\oplus , j}}\! \mathscr{D}^{\oplus }_{j}(y_j, \boldsymbol{r};+\!1) {\mathrm d} y_j\right | + \sum _{\ell =1}^{\boldsymbol{r}_{\ominus }} \left | \int _{{{\boldsymbol{\eta }}}_{\ominus , \ell }}^{{{\boldsymbol{\eta }}}'_{\ominus , \ell }} \! \mathscr{D}^{\ominus }_{\ell }(z_\ell , \boldsymbol{r};+\!1) {\mathrm d} z_\ell \right | }\right ], \end{align}

where ${\boldsymbol{\eta }}_{t,i},{\boldsymbol{\eta }}'_{t,i}$ follow the law of $\rho _t, \rho '_t$ , respectively. Expanding the expectation with respect to the type-distribution $\boldsymbol{r}$ , and writing $P(r)={\mathbb P}[\boldsymbol{r}=r]$ , for the probability of a vector $r=(r_{\raise-1pt\hbox{$\bullet$}}, r_{\oplus }, r_{\ominus }, r_{\unicode{x25EF}})$ , we rewrite (2.23) as

(2.24) \begin{align} & \sum _{r}P(r) \left ( {r}_{\raise-1pt\hbox{$\bullet$}} \cdot {\mathbb E}\left |\int _{{{\boldsymbol{\eta }}}_{\raise-1pt\hbox{$\bullet$}, 1}}^{{{\boldsymbol{\eta }}}'_{\raise-1pt\hbox{$\bullet$}, 1}}\! \mathscr{D}^{\raise-1pt\hbox{$\bullet$}}_{1}(z, r; +1) {\mathrm d} z \right | + {r}_{\oplus } \cdot {\mathbb E} \!\left | \int _{{{\boldsymbol{\eta }}}_{\oplus , 1}}^{{{\boldsymbol{\eta }}}'_{\oplus , 1}}\! \mathscr{D}^{\oplus }_{1}(z, r; +1) {\mathrm d} z\right |\right.\nonumber\\ & \qquad \qquad \left. + {{r}_{\ominus }} \cdot {\mathbb E} \left | \int _{{{\boldsymbol{\eta }}}_{\ominus , 1}}^{{{\boldsymbol{\eta }}}'_{\ominus , 1}} \! \mathscr{D}^{\ominus }_{1}(z, r; +1) {\mathrm d} z \right | \right ). \end{align}

The expected contribution of a negative clause is given by an expression similar to (2.24), albeit in terms of $\mathscr{D}_1^{t}(z, \boldsymbol{r}; -)$ , i.e., the partial derivative of the message $a \to \mathfrak{x}$ , with respect to the message from a variable of type $t$ to clause $a$ . Specifically, the expected contribution of a negative clause reads:

(2.25) \begin{align} & \sum _{r'}P(r') \left ( {r}'_{\raise-1pt\hbox{$\bullet$}} \cdot {\mathbb E}\left |\int _{{{\boldsymbol{\eta }}}_{\raise-1pt\hbox{$\bullet$}, 1}}^{{{\boldsymbol{\eta }}}'_{\raise-1pt\hbox{$\bullet$}, 1}}\! \mathscr{D}^{\raise-1pt\hbox{$\bullet$}}_{1}(z, r'; -1) {\mathrm d} z \right | + {r}'_{\oplus } \cdot {\mathbb E} \!\left | \int _{{{\boldsymbol{\eta }}}_{\oplus , 1}}^{{{\boldsymbol{\eta }}}'_{\oplus , 1}}\! \mathscr{D}^{\oplus }_{1}(z, r'; -1) {\mathrm d} z\right |\right.\nonumber\\ & \qquad \qquad \left. + {{r}'_{\ominus }} \cdot {\mathbb E} \left | \int _{{{\boldsymbol{\eta }}}_{\ominus , 1}}^{{{\boldsymbol{\eta }}}'_{\ominus , 1}} \! \mathscr{D}^{\ominus }_{1}(z, r'; -1) {\mathrm d} z \right | \right). \end{align}

It is not hard to see that pure literals have a ‘dampening’ effect on each partial derivative $\mathscr{D}^{t}_1(z, r; \pm )$ . Consider a clause $a$ whose children variables are distributed among the different types according to $r$ . Then each derivative in (2.24)–(2.25), can be bounded in terms of the number of pure literals featured in $a$ , excluding the variable of type $t$ with respect to which the derivative is taken. Notice that the operator ${\mathrm{LL}}^{\star }_{d,k}$ effectively incorporates the positive boundary condition by imposing the sign of each variable with respect to its parent clause, $a$ , to be $+$ if $a$ is positive, and $-$ if $a$ is negative. With that in mind, we see that if $a$ is a positive clause, the total number of pure literals it contains is just $r_{\ominus } + r_{\unicode{x25EF}}$ . On the other hand, if $a$ is negative, then the total number of pure literals it contains is $r_{\oplus } + r_{\unicode{x25EF}}$ . Bounding separately each derivative $\mathscr{D}^{t}_i(z, r; \pm 1 )$ in (2.24)–(2.25), and invoking the mean value theorem, yields an upper bound on for the contraction constant $c$ .

However, we can do better by partitioning the derivatives in (2.24)–(2.25) into groups, and optimising them jointly. Indeed, a careful examination of the expression (2.19), reveals that, for example, any sum of the form $\mathscr{D}^{\oplus }(z, (*, *, r_{\ominus },r_{\unicode{x25EF}}); +1)+\mathscr{D}^{\oplus }(z, (*,r_{\ominus }+1, *,r_{\unicode{x25EF}}); -1)$ can be explicitly maximised, and the resulting maximum is smaller than the sum of maxima of the parts. At first sight, this seems to be of little use, if any, as in order to implement such a coupling between terms (2.24)–(2.25), we should also match their coefficients, that is, the quantity $P(r)\cdot r_{\oplus }$ , must remain invariant under the coupling. Somewhat unexpectedly, it turns out that the coupling $r \mapsto r'$ with $r' = (r_{\raise-1pt\hbox{$\bullet$}}, r_{\ominus }+1, r_{\oplus }-1, r_{\unicode{x25EF}})$ , enjoys both features. Similar couplings strategies (depicted in Figure 2) facilitate the maximisation of $\oplus , \ominus$ -terms. The full proof of Proposition 2.15 can be found in Section 7.

We conclude the section explaining how Theorem 1.2 follows from the above.

Figure 2.

Example of a coupling between derivative terms in (2.24)–(2.25). For vector $r$ and type $t\in \{\raise-1pt\hbox{$\bullet$}, \oplus , \ominus \}$ , we pair the term $\mathscr{D}^{t}(z, r; +1)$ in (2.24) with the term $\mathscr{D}^{t}(z, \mathfrak{p}_t(r); -1)$ in (2.25).

Proof of Theorem 1.2. From the triangle inequality, and Lemma 2.12, it is immediate to obtain Theorem 1.2 from Proposition 2.13.

2.6 Discussion

The location of the random 2-SAT satisfiability threshold was pinpointed already in the 1990s [Reference Chvátal and Reed21, Reference Goerdt41] essentially because the threshold coincides with the giant component phase transition of a directed random graph whose edges correspond to the clauses. This argument also implies that both the pure literal algorithm and another efficient algorithm called unit clause propagation find satisfying assignments up to the satisfiability threshold w.h.p. By contrast, in the case of random $k$ -SAT with $k\geq 3$ the satisfiability threshold is known only for $k$ exceeding an undetermined (but large) constant $k_0$ [Reference Ding, Sly and Sun34]. The proof is based on a sophisticated, physics-inspired second moment argument that significantly extends ideas from earlier work [Reference Achlioptas and Moore5, Reference Achlioptas and Peres7, Reference Coja-Oghlan and Panagiotou27]. Asymptotically in the limit of large $k$ the satisfiability threshold reads

(2.26) \begin{align} d_{\mathrm{sat}}(k) & =k\left [ {2^k\log 2-\frac {1+\log 2}2}\right ] +\varepsilon _k,\quad \mbox{where }\lim _{k\to \infty }\varepsilon _k=0. \end{align}

Even though [Reference Achlioptas and Moore5, Reference Achlioptas and Peres7, Reference Coja-Oghlan and Panagiotou27, Reference Ding, Sly and Sun34] rely on the second moment method, they do not yield asymptotically tight estimates of the number of satisfying assignments for any regime of $d$ . This is because the second moment method is applied not to the number of satisfying assignments, but to another, exponentially smaller random variable. The assumption that $k$ exceeds a large constant is used critically in [Reference Coja-Oghlan and Panagiotou27, Reference Ding, Sly and Sun34] to ensure certain concentration and expansion properties.

For $3\leq k\lt k_0$ even the existence of a uniform satisfiability threshold remains an open problem, although a sharp threshold sequence that may vary with $n$ is known to exist [Reference Friedgut37]. That said, an upper bound on the satisfiability threshold (sequence) that matches the so-called ‘1-step replica symmetry breaking’ prediction from statistical physics can be verified using the interpolation method from mathematical physics [Reference Franz and Leone36, Reference Mertens, Mézard and Zecchina50, Reference Mézard, Parisi and Zecchina52, Reference Panchenko and Talagrand61]. However, the currently known lower bounds for small $k$ (say, $k=3,4,5$ ) fall short of this upper bound [Reference Achlioptas and Peres7, Reference Hajiaghayi and Sorkin43, Reference Kaporis, Kirousis and Lalas47]. For example, in the case $k=3$ the best current lower bound is $d_{\mathrm{sat}}(3)\geq 10.56$ , while $d_{\mathrm{sat}}(3)\approx 12.801$ according to physics predictions [Reference Mertens, Mézard and Zecchina50, Reference Mézard, Parisi and Zecchina52].

Thus, the satisfiability of random formulas continues to pose a substantial challenge for ‘small’ $3\leq k\lt k_0$ . In light of this, a particularly satisfactory aspect of the present results is that they apply and are meaningful for all $k\geq 3$ . In fact, comparing the asymptotic bounds (1.10) and (2.26), we see that the Gibbs uniqueness threshold $d_{\mathrm{uniq}}(k)$ is much smaller than $d_{\mathrm{sat}}(k)$ for large $k$ . Thus, Theorems 1.1 and 1.2 cover larger shares of the satisfiable regime of $d$ for smaller values of $k$ ; cf. Table 1.

The best current lower bounds on the satisfiability thresholds for $k\geq 4$ are non-constructive. With respect to the algorithmic problem of finding a satisfying assignment of a random $k$ -CNF the best current results for ‘small’ $k$ are based on simple combinatorial algorithms, analysed via the method of differential equations [Reference Frieze and Suen38, Reference Hajiaghayi and Sorkin43, Reference Kaporis, Kirousis and Lalas47]. Asymptotically for large $k$ the best known efficient algorithm [Reference Coja-Oghlan22] succeeds up to

(2.27) \begin{align} d_{\mathrm{alg}}(k) & =(1-\varepsilon _k)2^k\log k \quad \mbox{where }\lim _{k\to \infty }\varepsilon _k=0, \end{align}

about a factor of $\log (k)/k$ below (2.26). There is evidence that certain types of algorithms do not succeed for much larger values of $d$ , at least for enough large $k$ [Reference Achlioptas and Coja-Oghlan2, Reference Bresler and Huang15, Reference Coja-Oghlan23, Reference Hetterich45]. Apart from the task of finding a satisfying assignment, an important line of work deals with the problem of counting and sampling satisfying assignments of random $k$ -CNFs for large $k$ [Reference Chen, Galanis and Goldberg19, Reference Chen, Lonkar, Wang, Yang and Yin20, Reference He, Wu and Yang44]. The best current result [Reference Chen, Lonkar, Wang, Yang and Yin20] covers the regime $d\leq 2^k/k^c$ for an undetermined (large enough) constant $c\gt 0$ . Since for large $k$ the bound $2^k/k^c$ significantly exceeds the pure literal threshold (1.10), it might be an interesting question whether ideas from [Reference Chen, Galanis and Goldberg19, Reference Chen, Lonkar, Wang, Yang and Yin20, Reference He, Wu and Yang44] can be used to verify the replica symmetric solution (1.7) for $d$ beyond the Gibbs uniqueness threshold for large $k$ .

Most of the prior work on the rigorous verification of the replica symmetric solution focuses on a soft version of random $k$ -SAT, the so-called random $k$ -SAT model at inverse temperature $\beta \gt 0$ [Reference Panchenko58]. The partition function $Z_\beta (\boldsymbol{\Phi })$ of this model, its the key quantity of interest, is defined as follows. For a clause $a$ of the random formula $\boldsymbol{\Phi }$ and a truth assignment $\sigma$ write $\sigma \models a$ if $\sigma$ satisfies clause $a$ . Then

(2.28) \begin{align} Z_\beta (\boldsymbol{\Phi }) & =\sum _{\sigma \in \{\pm 1\}^n}\exp \left ({-\beta \sum _{i=1}^{\boldsymbol{m}}\unicode {x1D7D9}\{\sigma \not \models a_i\}}\right ). \end{align}

Thus, each assignment $\sigma$ contributes a summand equal to $\exp (-\beta )$ raised to the power of the number of clauses that $\sigma$ fails to satisfy. In effect,

(2.29) \begin{align} Z(\boldsymbol{\Phi }) & =\lim _{\beta \to \infty }Z_\beta (\boldsymbol{\Phi }). \end{align}

A line of prior work [Reference Biswas, Chen and Sen13, Reference Panchenko60, Reference Talagrand63] deals with the derivation of the ‘thermodynamic limit’

(2.30) \begin{align} \lim _{n\to \infty }\frac 1n{\mathbb E}\left [ {\log Z_\beta (\boldsymbol{\Phi })}\right ] \end{align}

for small $d$ and/or small $\beta$ . Specifically, these works verify that (2.30) is given by the replica symmetric solution at inverse temperature $\beta$ from [Reference Monasson and Zecchina55, Reference Monasson and Zecchina56] under the assumption

(2.31) \begin{align} d(k-1)\min \left \{{1,6\beta \exp (4\beta )}\right \} & \lt 1. \end{align}

We observe that for large $\beta$ the bound (2.31) holds only up to the giant component threshold $d=1/(k-1)$ , where the replica symmetric solution trivially follows from the fact that Belief Propagation is exact on acyclic graphical models [Reference Mézard and Montanari51, Theorem 4.1]. That said, a technique called the interpolation method shows that the replica symmetric solution yields an upper bound on (2.30) for all $d,\beta \gt 0$ [Reference Franz and Leone36, Reference Panchenko and Talagrand61]. In particular, we will combine the interpolation method with a concentration argument in order to prove Corollary 2.2.

According to physics predictions the ‘replica symmetric solution’ from [Reference Monasson and Zecchina55, Reference Monasson and Zecchina56] yields the correct value of both $\lim _{n\to \infty }n^{-1}\log Z_\beta (\boldsymbol{\Phi })$ for all $\beta \gt 0$ and of $\lim _{n\to \infty }n^{-1}\log Z(\boldsymbol{\Phi })$ for all $d$ up to a threshold $d_{\mathrm{rsb}}(k)$ close to but strictly below the satisfiability threshold $d_{\mathrm{sat}}(k)$ for all $k\geq 3$ [Reference Krzakala, Montanari, Ricci-Tersenghi, Semerjian and Zdeborová48]. The threshold $d_{\mathrm{rsb}}(k)$ is known as the ‘1-step replica symmetry breaking phase transition’ in physics jargon; its asymptotic value is predicted as

(2.32) \begin{align} d_{\mathrm{rsb}}(k)=k\big [ {2^k\log 2-2\log 2}\big ] +\varepsilon _k,\quad \mbox{where }\lim _{k\to \infty }\varepsilon _k=0. \end{align}

Indeed, the interpolation method can be used to verify that the replica symmetric solution ceases to be correct for $d_{\mathrm{rsb}}(k)+\varepsilon _k\lt d\lt d_{\mathrm{sat}}(k)$ with $\varepsilon _k\to 0$ . Conversely, the replica symmetric solution is known to be correct for all $d$ and $\beta \gt 0$ where a certain correlation decay condition is satisfied [Reference Coja-Oghlan, Müller and Ravelomanana26], provided that $k$ is large enough. Physics methods predict that this condition holds for all $\beta \gt 0$ and all $d\lt d_{\mathrm{rsb}}(k)$ [Reference Krzakala, Montanari, Ricci-Tersenghi, Semerjian and Zdeborová48].

The aforementioned work of Montanari and Shah [Reference Montanari and Shah57] also deals with the soft variant of random $k$ -SAT (2.28), but allows for an inverse temperature $\beta =\beta (n)$ that tends to infinity slowly as $n\to \infty$ . Specifically, considering a small power $\beta =n^\delta$ enables Montanari and Shah to estimate the number of assignments that satisfy all but $o(n)$ clauses. The proof combines an interpolation on $0\leq \beta \leq n^\delta$ with a contraction argument that improves over the previous contraction estimates from [Reference Biswas, Chen and Sen13, Reference Panchenko60, Reference Talagrand63]. Instead of the interpolation on $\beta$ , in order to prove Theorem 1.1 we use the Aizenman-Sims-Starr scheme. Because we count actual satisfying assignments, this requires the careful combinatorial analysis of tail events, which is where the $\texttt {PULP}$ algorithm and its analysis come in. Additionally, towards the proof of Theorem 1.2 we devise an improved version of the contraction argument from [Reference Montanari and Shah57]. Following Montanari and Shah, we also take advantage of the impact of pure literals on the Belief Propagation operator. But we develop an improved coupling scheme that yields a better range of $d$ for which contraction occurs. Additionally, once again because we deal with actual satisfying assignments, the proof of the Gibbs uniqueness property involves the analysis of the $\texttt {PULP}$ algorithm on a Galton-Watson tree in order to cope with unlikely events.

By comparison to the ‘soft’ random $k$ -SAT model (2.28), few prior contributions deal with the actual number $Z(\boldsymbol{\Phi })$ of satisfying assignments. A result of Abbe and Montanari [Reference Abbe and Montanari1] implies that a deterministic limit (in probability)

(2.33) \begin{align} \lim _{n\to \infty }\frac 1n\log Z(\boldsymbol{\Phi }) \end{align}

exists for Lesbegue-almost all $0\lt d\lt d_{\mathrm{pure}}(k)$ for all $k\geq 2$ . However, the proof, which is based on the interpolation method, does not reveal the value of (2.33). In fact, prior to the present work the limit (2.33) was known only in two cases. First, in the trivial regime $d\lt 1/(k-1)$ below the giant component threshold. Second, in the case $k=2$ for $0\lt d\lt d_{\mathrm{sat}}(2)=2$ [Reference Achlioptas, Coja-Oghlan and Hahn-Klimroth3]. In both cases the limit (2.33) coincides with the replica symmetric solution from [Reference Monasson and Zecchina55]. Beyond the convergence in probability, $\log Z(\boldsymbol{\Phi })$ is known to satisfy a central limit theorem in the case $k=2$ [Reference Chatterjee, Coja-Oghlan and Müller17].

To compute the limit (2.33) in the case $k=2$ the contribution [Reference Achlioptas, Coja-Oghlan and Hahn-Klimroth3] employs the Aizenman-Sims-Starr scheme. The couplings that we use towards the proofs of Propositions 2.5– 2.6 generalise the argument from [Reference Achlioptas, Coja-Oghlan and Hahn-Klimroth3] to $k\geq 3$ . The main technical novelty lies in the way that moderately unlikely events are treated. Specifically, in the case $k=2$ the simple Unit Clause propagation algorithm, which essentially boils down to directed reachability, was sufficient to derive a tail bound similar to (and actually stronger than) (2.5). By contrast, since in the case $k\geq 3$ the clauses ‘branch out’, the analysis of tail events and, accordingly, the derivation of (2.5) is far more delicate. The core of this derivation is the detailed analysis of the $\texttt {PULP}$ algorithm right up to $d_{\mathrm{pure}}(k)$ .

Finally, by contrast to random $k$ -SAT the validity of the replica symmetric solution is known for the optimal parameter range for several other random constraint satisfaction problems that enjoy certain symmetry properties. Examples include random graph colouring or random $k$ -NAESAT [Reference Bapst, Coja-Oghlan, Hetterich, Raßmann and Vilenchik11, Reference Coja-Oghlan, Krzakala, Perkins and Zdeborová25]. Due to the symmetry propertyFootnote 7 the replica symmetric solution simply coincides with the first moment of the number of solutions. In effect, in many symmetric problems it is even possible to precisely determine the limiting distribution of the number of solutions, which superconcentrates on the first moment [Reference Coja-Oghlan, Kapetanopoulos and Müller24]. By contrast, in random $k$ -SAT the first moment overshoots the typical number of satisfying assignments by an exponential factor [Reference Achlioptas and Moore5], which is why random $k$ -SAT is so much more delicate than symmetric problems. That said, there is a regular variant of random $k$ -SAT (where every variable appears an equal number of times positively and negatively) where symmetry and superconcentration are recovered [Reference Coja-Oghlan and Wormald30].

2.7 Organisation

In the remaining sections we work our way through the proofs of Theorems 1.1 and 1.2. Specifically, in Section 3 we analyse the $\texttt {PULP}$ algorithm introduced in Section 2.3, proving Lemmas 2.8-2.10, which facilitates many of the subsequent results.

In Section 4 we establish Proposition 2.1, verifying that the quantities appearing in Theorem 1.1 are well-defined. The proof of Corollary 2.2 follows in Section 5. Section 6 is devoted to the Aizenman-Sims-Starr scheme, and in particular the proof of Proposition 2.3. There we also complete the proof of Theorem 1.1.

Our final Section 7, deals with the remaining proofs toward establishing Theorem 1.2. We begin by proving Lemma 2.14, showing that the log-likelihood ratios of the random Galton-Watson formula close to the root are bounded w.h.p. This enables us to compare the output distribution of the non-random operator introduced in Section 2.5 with that of actual ratios on the random tree. We then proceed with the proof of Proposition 2.15, and conclude with the proof of (2.13), completing the proof of Theorem 1.2.

3.1 Proof of Lemma 2.8

Suppose that $\skew9\bar{\mathscr{L}} \supseteq \mathscr{L}$ satisfies PULP1–PULP2. Let $U=\{|l|\,:\,l\in \skew9\bar{\mathscr{L}}\}$ be the set of variables underlying the literals $\skew9\bar{\mathscr{L}}$ . Moreover, let $\chi : U \to \{\pm 1\}$ be the truth assignments under which all literals of $l\in \skew9\bar{\mathscr{L}}$ evaluate to ‘true’. Due to PULP2, the assignment $\chi$ is well defined. Moreover, since $\mathscr{L}\subseteq \skew9\bar{\mathscr{L}}$ , under $\chi$ all literals $l\in \mathscr{L}$ evaluate to ‘true’. Hence, for a satisfying assignment $\sigma \in S(\Phi )$ define an assignment $\sigma '$ by letting

\begin{align*} \sigma '(x)=\unicode {x1D7D9}\{x\in U\}\chi (x)+\unicode {x1D7D9}\{x\not \in U\}\sigma (x). \end{align*}

Because $\skew9\bar{\mathscr{L}}$ satisfies condition PULP1, we have $\sigma '\in S(\Phi ,\mathscr{L})$ . Finally, because for a satisfying assignment $\tau '\in S(\Phi ,\mathscr{L})$ there are no more than $2^{|U|}=2^{|\skew9\bar{\mathscr{L}}|}$ satisfying assignments $\tau \in S(\Phi )$ such that $\tau (x)=\tau '(x)$ for all $x \not \in U$ , we obtain the desired bound $Z(\Phi )\leq 2^{|\skew9\bar{\mathscr{L}}|}Z(\Phi ,\mathscr{L})$ .

3.2 Turning a tree to $\texttt {PULP}$

While the ultimate goal of this section is to study the $\texttt {PULP}$ algorithm on the random formula $\boldsymbol{\Phi }'$ to prove Lemma 2.10, a necessary preparation is to investigate the algorithm on the random Galton-Watson tree $\mathbb{T}=\mathbb{T}_{d,k}$ . Of course, since $\mathbb{T}$ may be infinite we should formally confine ourselves to the finite trees $\mathbb{T}^{(\ell )}$ truncated at the $2\ell$ -th level from the root $\mathfrak{x}$ . Hence, recalling (2.6), we aim to estimate the height $\mathfrak{h}_{\mathfrak{x}}(s,\mathbb{T}^{(\ell )})$ for finite $\ell$ . That said, since these random variables are monotonically increasing in $\ell$ , it makes sense to define

(3.1) \begin{align} \mathfrak{h}_{\mathfrak{x}}(s,\mathbb{T}) & =\lim _{\ell \to \infty }\mathfrak{h}_{\mathfrak{x}}(s,\mathbb{T}^{(\ell )})\in [0,\infty ]. \end{align}

We point out that for $d\lt d_{\mathrm{pure}}(k)$ the tails of $\mathfrak{h}_{\mathfrak{x}}(s,\mathbb{T})$ decay at a doubly exponential rate.

Lemma 3.1. For any $d\lt d_{\mathrm{pure}}(k)$ there exist $c_1=c_1(d,k),c_2=c_2(d,k)\gt 0$ such that

\begin{align*} {\mathbb P} \left [ { \mathfrak{h}_{\mathfrak{x}}(\pm 1,\mathbb{T}) \geq h }\right ] & \leq c_1 \cdot \exp ({-\exp ({c_2 \cdot h})}) \quad \text{ for every } h \ge 1. \end{align*}

Proof. By symmetry it suffices to consider $\mathfrak{h}_{\mathfrak{x}}(1,\mathbb{T})$ . Thus, let $p_{h, \ell } = {\mathbb P} \left [ { \mathfrak{h}_{\mathfrak{x}} (1,\mathbb{T}^{(\ell )})\geq h}\right ]$ . All variables at distance $2\ell$ from $\mathfrak{x}$ are leaves and therefore pure in the tree $\mathbb{T}^{(\ell )}$ . Consequently, pure literal elimination removes all clauses of $\mathbb{T}^{(\ell )}$ within at most $\ell$ rounds. Hence, $p_{h,\ell }=0$ for $h\gt \ell$ . Furthermore, we claim that

(3.2) \begin{align} p_{h,\ell } & =\varphi _{d,k}(p_{h-1,\ell -1}),\quad \mbox{where}\quad \varphi _{d,k}(z)=1-\exp \left ({-\frac d2z^{k-1}}\right ) & & (1\leq h\leq \ell ). \end{align}

Indeed, if $\mathfrak{h}_{\mathfrak{x}} (1,\mathbb{T}^{(\ell )})\geq h\geq 1$ then by (2.6) there exists a clause $a\in \partial _{\mathbb{T}} r$ with $\mathrm{sign}(\mathfrak{x},a)=-1$ such that $\mathfrak{h}_a(\mathbb{T}^{(\ell )}[\mathfrak{x}\mapsto 1])\geq h-1$ . In other words, pure literal elimination on the sub-tree $\mathbb{T}^{(\ell )}[a]$ of $\mathbb{T}^{(\ell )}$ rooted at clause $a$ and with variable $\mathfrak{x}$ removed takes at least $h-1$ rounds to remove clause $a$ . Consequently, pure literal elimination on $\mathbb{T}^{(\ell )}[a]$ takes at least $h-1$ rounds to remove one of the variables $x\in \partial _{\mathbb{T}} a\setminus \{\mathfrak{x}\}$ . In other words, the sub-tree $\mathbb{T}^{(\ell )}[x]$ comprising $x$ and its successors satisfies

(3.3) \begin{align} \mathfrak{h}_x(\mathrm{sign}(x,a),\mathbb{T}^{(\ell )}[x])\geq h-1\quad \mbox{for every }x\in \partial _{\mathbb{T}} a\setminus \{\mathfrak{x}\}. \end{align}

But since $\mathbb{T}$ is a Galton-Watson tree, the sub-tree $\mathbb{T}^{(\ell )}[x]$ has the same distribution as the random tree $\mathbb{T}^{(\ell -1)}$ . Hence, (3.3) implies that for every $a\in \partial _{\mathbb{T}}\mathfrak{x}$ with $\mathrm{sign}(x,a)=-1$ ,

(3.4) \begin{align} {\mathbb P}\big [ {\mathfrak{h}_a(\mathbb{T}^{(\ell )}[\mathfrak{x}\mapsto 1])\geq h-1\mid \mathbb{T}^{(1)}}\big ] & =p_{h-1,\ell -1}^{k-1}. \end{align}

Finally, the construction of $\mathbb{T}$ ensures that the number of $a\in \partial _{\mathbb{T}}\mathfrak{x}$ with $\mathrm{sign}(x,a)=-1$ has distribution $\textrm {Po}(d/2)$ . Therefore, (3.4) shows that

\begin{align*} p_{h,\ell } & =\sum _{i=0}^{\infty }{\mathbb P}\left [ {\textrm {Po}(d/2)=i}\right ] \left ({1-\left ({1-p_{h-1,\ell -1}^{k-1}}\right )^i}\right )=1-\exp \left ({-\frac d2p_{h-1,\ell -1}^{k-1}}\right ), \end{align*}

which completes the proof of (3.2).

Since the sequences $(p_{h,\ell })_{\ell }$ are non-decreasing, the limits $p_h=\lim _{\ell \to \infty }p_{h,\ell }$ exist. Moreover, (3.2) shows that

(3.5) \begin{align} p_h=\varphi _{d,k}(p_{h-1})\quad (h\geq 1). \end{align}

Hence, recalling the definition (1.8) of $d_{\mathrm{pure}}(k)$ , we find

\begin{align*} \left (\frac {p_{h+1}}{p_{h}}\right )^{k-1} = \left (\frac {\varphi _{d,k}(p_h)} {p_h} \right )^{k-1} = d\cdot \frac {\left ( 1 - \exp \left (-dp_h^{k-1}/2\right )\right )^{k-1}} {d p^{k-1}_h} \le \frac {d}{d_{\mathrm{pure}}}\lt 1. \end{align*}

Consequently,

(3.6) \begin{align} \lim _{h\to \infty }p_h & =0. \end{align}

To complete the proof we expand $\varphi _{d,k}(z)$ around $z=0$ :

(3.7) \begin{align} \varphi _{d,k}(z) = \frac {d}{2}z^{k-1} +O(z^{2k-2})\quad\mbox{ as }z\to 0. \end{align}

Thus, the function $\varphi _{d,k}(z)$ is well approximated by a $(k-1)$ -th power. Since $k\geq 3$ , combining (3.5)–(3.7), we conclude that for sufficiently large $h$ we have $p_h\leq (d/2+1)p_{h-1}^{k-1}$ . Consequently, $p_h\leq c_1 \cdot \exp \left ({-\exp \left ({c_2 \cdot h}\right )}\right )$ for suitable $c_1=c_1(d,k)$ and $c_2=c_2(d,k)$ .

We remind ourselves that $\overline {\{\pm 1\cdot \mathfrak{x}\}}_{\mathbb{T}^{(\ell )}}$ signifies the output of $\texttt {PULP}$ run on the formula $\mathbb{T}^{(\ell )}$ with initial literal set $\{\pm 1\cdot \mathfrak{x}\}$ . We extend the definition of the closure to the (possibly infinite) tree $\mathbb{T}$ by letting

\begin{align*} \overline {\{\pm 1\cdot \mathfrak{x}\}}_{\mathbb{T}} & =\bigcap _{\ell _0\geq 1}\bigcup _{\ell \geq \ell _0}\overline {\{\pm 1\cdot \mathfrak{x}\}}_{\mathbb{T}^{(\ell )}}. \end{align*}

This definition ensures that if the height $\mathfrak{h}_{\mathfrak{x}}(\pm 1,\mathbb{T})$ from (3.1) is finite, then

\begin{align*} \overline {\{\pm 1\cdot \mathfrak{x}\}}_{\mathbb{T}}=\overline {\{\pm 1\cdot \mathfrak{x}\}}_{\mathbb{T}^{(\ell )}}\quad \mbox{ for all }\ell \geq \mathfrak{h}_{\mathfrak{x}}(\pm 1,\mathbb{T}). \end{align*}

In order to estimate the size of this set, we combine Lemma 3.1 with a crude bound on the total number of variable nodes of the Galton-Watson tree $\mathbb{T}^{(\ell )}$ . Recall that $V(\mathbb{T}^{(\ell )})$ signifies the set of variable nodes of $\mathbb{T}^{(\ell )}$ .

Lemma 3.2. Let $d\gt 0$ . For any $\ell \geq 1$ and any $t\gt 100(1+d(k-1))^2$ we have

\begin{align*} {\mathbb P}\left [ {|V(\mathbb{T}^{(\ell )})|\gt t^\ell }\right ] & \leq \ell \exp (-t^{\ell /2}/4). \end{align*}

Proof. Let $\boldsymbol{N}_\ell =|V(\mathbb{T}^{(\ell )})|$ for brevity, set $g=10(1+d(k-1))$ and notice that $t\gt g^2$ . The construction of the Galton-Watson tree $\mathbb{T}$ ensures that $\boldsymbol{N}_0=1$ and that for $\ell \geq 1$ given $\boldsymbol{N}_{\ell -1}$ we have $\boldsymbol{N}_\ell \sim (k-1)\cdot \textrm {Po}(d\boldsymbol{N}_{\ell -1}).$ Therefore, Bennett’s inequality shows that

(3.8) \begin{align} {\mathbb P}\left [ {\boldsymbol{N}_h\gt g^{h-\ell }t^\ell \mid \boldsymbol{N}_{h-1}\leq g^{h-1-\ell }t^\ell }\right ] & \leq \exp \left ({-\frac {t^\ell }{4g^{\ell -h}}}\right )\leq \exp (-t^{\ell /2}/4) & & (1\leq h\leq \ell ). \end{align}

Furthermore, if $\boldsymbol{N}_\ell \gt t^\ell$ then there exists $1\leq h\leq \ell$ such that $\boldsymbol{N}_h\gt g^{h-\ell }t^\ell$ while $\boldsymbol{N}_{h-1}\leq g^{h-1-\ell }t^\ell$ . Hence, combining (3.8) with the union bound completes the proof.

Corollary 3.3. For any $d\lt d_{\mathrm{pure}}(k)$ there exists $c_3=c_3(d,k)\gt 0$ such that

\begin{align*} {\mathbb P}[|\overline {\{\pm 1\cdot \mathfrak{x}\}}_{\mathbb{T}}|\gt t]\leq c_3\exp (-t^{1/c_3})\quad\mbox{ for all }t\gt 0. \end{align*}

Proof. By symmetry it suffices to consider $\boldsymbol{N}=|\overline {\{\mathfrak{x}\}}_{\mathbb{T}}|$ . Since Lemma 3.1 shows that ${\mathbb P}[\mathfrak{h}_{\mathfrak{x}}(1,\mathbb{T})\lt \infty ]=1$ , we may assume from now on that indeed $\mathfrak{h}_{\mathfrak{x}}(1,\mathbb{T})\lt \infty$ . Moreover, picking $c_3=c_3(d,k)\gt 0$ large enough, we may assume that $t\gt t_0$ for a large $t_0=t_0(d,k)$ . Let $\boldsymbol{N}_\ell =|V(\mathbb{T}^{(\ell )})|$ , $p_h={\mathbb P}\left [ {\mathfrak{h}_{\mathfrak{x}}(1,\mathbb{T})=h}\right ]$ and $g=10(1+d(k-1))$ . It is an immediate consequence of the way that $\texttt {PULP}$ proceeds that for all $l\in \overline {\{\mathfrak{x}\}}_{\mathbb{T}}$ we have $|l|\in V(\mathbb{T}^{(\mathfrak{h}_{\mathfrak{x}}(1,\mathbb{T}))})$ . Hence, $\boldsymbol{N}\leq \boldsymbol{N}_{\mathfrak{h}_{\mathfrak{x}}(1,\mathbb{T})}$ . Therefore, by the law of total probability,

(3.9) \begin{align} {\mathbb P}\left [ {\boldsymbol{N}\gt t}\right ] \leq \sum _{h\geq 0}S_h,\quad\mbox{where }S_h={\mathbb P}\left [ {\mathfrak{h}_{\mathfrak{x}}(1,\mathbb{T})=h}\right ] {\mathbb P}\left [ {\boldsymbol{N}_h\gt t\mid \mathfrak{h}_{\mathfrak{x}}(1,\mathbb{T})=h}\right ] . \end{align}

Depending on the value of $t$ in relation to $h$ , we use either Lemma 3.1 or Lemma 3.2 to bound $S_h$ .

1. Case 1: $t_0\lt t\leq g^{2h}$ : Lemma 3.1 shows that for certain $c_1,c_2\gt 0$ we have

   (3.10) \begin{align} S_h & \leq {\mathbb P}\left [ {\mathfrak{h}_{\mathfrak{x}}(1,\mathbb{T})=h}\right ] \leq c_1\exp (-\exp (c_2h))\leq c_12^{-h}\exp (-t^{1/c_3}), \end{align}
   provided $c_3$ is chosen large enough.

2. Case 2: $t\gt g^{2h}$ : we apply Lemma 3.2 to obtain

   (3.11) \begin{align} S_h & \leq {\mathbb P}\left [ {\boldsymbol{N}_h\gt t}\right ] \leq h\exp (-\sqrt t/4)\leq h2^{-h}\exp (-t^{1/3}), \end{align}
   provided that $t\gt t_0$ is sufficiently large.

Combining the bounds (3.9)–(3.11) completes the proof.

3.3 Proof of Lemma 2.10

Because the distribution of $\boldsymbol{\Phi }'$ is invariant under variable permutations and inversions, we may assume the initial set $\mathscr{L}$ of literals passed to $\texttt {PULP}$ is just $\mathscr{L}=\{x_1,\ldots ,x_L\}$ for an integer $L=\tilde O(1)$ . For an integer $\ell \geq 1$ let $\boldsymbol{\phi }_{\ell ,L}'$ be the sub-formula of $\boldsymbol{\Phi }'$ comprising all clauses and variables at distance at most $2\ell$ from $\mathscr{L}$ . We recall that this formula has a bipartite graph representation $G(\boldsymbol{\phi }_{\ell ,L}')$ with variable nodes $V(\boldsymbol{\phi }_{\ell ,L}')$ , clause nodes $F(\boldsymbol{\phi }_{\ell ,L}')$ and edges $E(\boldsymbol{\phi }_{\ell ,L}')$ . The excess of $\boldsymbol{\phi }_{\ell ,L}'$ is defined as

\begin{align*} \boldsymbol{X}_{\ell ,L} & =|E(\boldsymbol{\phi }_{\ell ,L}')|-|V(\boldsymbol{\phi }_{\ell ,L}')|-|F(\boldsymbol{\phi }_{\ell ,L}')|. \end{align*}

Thus, $\boldsymbol{X}_{\ell ,L}=-L$ iff $G(\boldsymbol{\phi }'_{\ell ,L})$ consists of $L$ acyclic components.

Lemma 3.5. Let $d\gt 0$ , $c\gt 0$ and assume that $L\leq \log ^cn$ and $\ell \leq c\log \log n$ . Then

(3.12) \begin{align} {\mathbb P}\left [ {\boldsymbol{X}_{\ell ,L}\gt -L}\right ] & = \tilde O(n^{-1}), & {\mathbb P}\left [ {\boldsymbol{X}_{\ell ,L}\gt 1-L}\right ] & = \tilde O(n^{-2}). \end{align}

Furthermore, there exists $c_4=c_4(c,d,k)\gt 0$ such that

(3.13) \begin{align} {\mathbb P}\left [ {|V(\boldsymbol{\phi }'_{\ell ,L})|+|F(\boldsymbol{\phi }'_{\ell ,L})|\gt \log ^{c_4}n}\right ] & = O(n^{-2}). \end{align}

Proof. We study breadth first search (‘BFS’) on the graph $G(\boldsymbol{\Phi }')$ from the start vertices $\mathscr{L}$ by means of a routine deferred decisions argument. Throughout the execution of BFS each variable node is in one of three possible states: unexplored, active, or finished.

Towards the proof of (3.13) we study a ‘parallel’ version of BFS. More precisely, let $\mathscr{A}_0=\mathscr{L}$ be the set of initially active variables, let $\mathscr{U}_0=\{x_1,\ldots ,x_n\}\setminus \mathscr{L}$ comprise the initially unexplored variables and let $\mathscr{F}_0=\emptyset$ . Further, for $t\geq 0$ define $\mathscr{A}_{t+1},\mathscr{U}_{t+1},\mathscr{F}_{t+1}$ as follows. If $\mathscr{A}_t=\emptyset$ then the process has stopped and we let $\mathscr{A}_{t+1}=\mathscr{A}_t=\emptyset ,\mathscr{U}_{t+1}=\mathscr{U}_t,\mathscr{F}_{t+1}=\mathscr{F}_t$ . Otherwise let $\mathscr{A}_{t+1}$ be the set of all variable nodes $y\in \mathscr{U}_{t}$ such that there exist an active variable node $x\in \mathscr{A}_t$ and a clause $a$ that contains $x$ and $y$ ; in symbols, $x,y\in \partial _{\boldsymbol{\Phi }'}a$ . Further, let $\mathscr{F}_{t+1}=\mathscr{F}_t\cup \mathscr{A}_t$ and $\mathscr{U}_{t+1}=\mathscr{U}_t\setminus \mathscr{A}_{t+1}$ . The BFS exploration occurs ‘in parallel’ in the sense that all active vertices activate their previously unexplored second neighbours simultaneously.

Let $\mathfrak{F}_t$ be the $\sigma$ -algebra generated by the first $t$ rounds of parallel exploring. Then the distribution of $|\mathscr{A}_{t+1}|$ given $\mathfrak{F}_t$ is stochastically dominated by a random variable with distribution $(k-1)\textrm {Po}(d|\mathscr{A}_t|)$ . This is because by the construction of the formula $\boldsymbol{\Phi }'$ the total number of clauses containing a given variable node has distribution $\textrm {Po}(d(1-(k-1)/n))$ . Hence, for any $u\gt 0$ we have

(3.14) \begin{align} {\mathbb P}\left [ {|\mathscr{A}_{t+1}|\gt u\mid \mathfrak{F}_t}\right ] & \leq {\mathbb P}\left [ {(k-1)\textrm {Po}(d|\mathscr{A}_t|)\gt u}\right ] . \end{align}

To complete the proof of (3.13) we mimic the argument from the proof of Lemma 3.2. Thus, let $u=\log ^{c_4-3}n$ for a large enough $c_4=c_4(c,d,k)$ and set $g=10(1+d(k-1))$ . Since $\ell \leq c\log \log n$ , the bound (3.14) and Bennett’s inequality show that

\begin{align*} {\mathbb P}\left [ {|\mathscr{A}_{t+1}|\gt g^{t+1-\ell }u\mid |\mathscr{A}_t|\leq g^{t-\ell }u}\right ] & \leq \exp \left ({-\frac {u}{4g^{\ell -t+1}}}\right )\leq \exp (-\sqrt u/4)=O(n^{-3}) & & (0\leq t\lt \ell ). \end{align*}

Hence, taking a union bound on $0\leq t\lt \ell$ and observing that $|V(\boldsymbol{\phi }'_{\ell ,L})|\subseteq \mathscr{A}_0\cup \cdots \cup \mathscr{A}_\ell$ , we obtain

(3.15) \begin{align} {\mathbb P}\left [ {|V(\boldsymbol{\phi }'_{\ell ,L})|\gt u\log n}\right ] & =\tilde O(n^{-3}). \end{align}

Finally, another application of Bennett’s inequality demonstrates that with probability $1-O(n^{-2})$ no variable of $\boldsymbol{\Phi }'$ appears in more than $\log n$ clauses. Thus, $|F(\boldsymbol{\phi }'_{\ell ,L})|\leq |V(\boldsymbol{\phi }'_{\ell ,L})|\log n$ . Hence, (3.15) implies (3.13).

We are left to establish (3.12). The way we set up the BFS process implies that there are only two ways in which excess edges can come about. First, there may be clauses $a$ with $\partial _{\boldsymbol{\Phi }'}a\subseteq \mathscr{A}_t\cup \mathscr{A}_{t+1}$ such that $|\partial _{\boldsymbol{\Phi }'}a\cap \mathscr{A}_t|\geq 2$ . Given that $|\mathscr{A}_t\cup \mathscr{A}_{t+1}|\leq \log ^{c_4}n$ , the number of such $a$ with $|\partial _{\boldsymbol{\Phi }'}a\cap \mathscr{A}_t|=2$ has distribution $\textrm {Po}(\tilde O(1/n))$ , and the number of $a$ with $|\partial _{\boldsymbol{\Phi }'}a\cap \mathscr{A}_t|\gt 2$ has distribution $\textrm {Po}(\tilde O(1/n^2))$ . The second possibility is that for a variable $x\in \mathscr{A}_{t+1}$ there exist clauses $a,b\in \partial _{\boldsymbol{\Phi }'}x$ with $\partial _{\boldsymbol{\Phi }'}a,\partial _{\boldsymbol{\Phi }'}b\subseteq \mathscr{A}_t\cup \mathscr{A}_{t+1}$ . Once again the number of such clauses has distribution $\textrm {Po}(\tilde O(1/n))$ given $|\mathscr{A}_t\cup \mathscr{A}_{t+1}|\leq \log ^{c_4}n$ . Furthermore, excess inducing clauses occur independently at different rounds $t$ of the BFS process. Thus, (3.12) follows from (3.13).

We proceed to derive bounds on $|\skew9\bar{\mathscr{L}}|=|\skew9\bar{\mathscr{L}}_{\boldsymbol{\Phi }'}|$ depending on the value of the excess. To deal with the case of excess $-L$ , let $\Lambda =\Theta (\log \log n)$ and let $(\mathbb{T}[i])_{i\geq 1}$ be a sequence of independent copies of the random tree $\mathbb{T}$ . In the case that the excess $\boldsymbol{X}_{\Lambda ,L}$ equals $-L$ , the bound on $|\skew9\bar{\mathscr{L}}|$ follows from the fact that the Galton-Watson tree $\mathbb{T}$ captures the local structure of the graph $G(\boldsymbol{\Phi }')$ in combination with the bound from Corollary 3.3. More precisely, the following is true.

Lemma 3.6. For any $0\lt d\lt d_{\mathrm{uniq}}(k)$ and $c\gt 0$ there exists $\zeta =\zeta (c,d,k)\gt 0$ such that with $\Lambda =\lceil \zeta \log \log n\rceil$ uniformly for all $1\leq L\leq \log ^cn$ and all $u\gt 0$ we have

\begin{align*} {\mathbb P}\left [ {\unicode {x1D7D9}\{\boldsymbol{X}_{\Lambda ,L}=-L\}|\skew9\bar{\mathscr{L}}|\gt u}\right ] & \leq {\mathbb P}\left [ {\sum _{i=1}^L|\overline {\{\mathfrak{x}\}}_{\mathbb{T}[i]}|\gt u}\right ] +O(n^{-2}). \end{align*}

Proof. We begin by coupling the random formula $\boldsymbol{\phi }'_{\ell ,1}$ with the Galton-Watson tree $\mathbb{T}^{(\ell )}[1]$ for $0\leq \ell \leq \Lambda$ . The coupling operates in accordance with the iterations of the BFS process from the proof of Lemma 3.5. Under the coupling some of the variable and clause nodes of $\boldsymbol{\phi }'_{\ell ,1}$ and of the tree $\mathbb{T}^{(\ell )}[1]$ are identical, but both $\mathbb{T}^{(\ell )}[1]$ and $\boldsymbol{\phi }'_{\ell ,1}$ may contain additional clauses or variables. These additional clauses/variables result from excess edges of $G(\boldsymbol{\phi }_{\ell ,1}')$ , i.e., edges that close cycles or merge different components in the course of the BFS process.

For $\ell =0$ we just identify the start variable $x_1$ with the root $\mathfrak{x}$ of the Galton-Watson tree $\mathbb{T}[1]$ . Going from $\ell$ to $\ell +1$ , we remember the sets $\mathscr{A}_\ell ,\mathscr{A}_{\ell +1}$ from the proof of Lemma 3.5. For each variable $x\in \mathscr{A}_\ell$ let $\mathscr{C}_x$ be the set of clauses $a\in \partial _{\boldsymbol{\Phi }'}x$ such that $|\partial _{\boldsymbol{\Phi }'}a\cap \mathscr{A}_{\ell +1}|=k-1$ and also such that none of the variables $y\in \mathscr{A}_{\ell +1}\cap \partial _{\boldsymbol{\Phi }'}a$ appear in another clause $b\neq a$ with $\partial _{\boldsymbol{\Phi }'}b\subseteq \mathscr{A}_\ell \cup \mathscr{A}_{\ell +1}$ . In other words, $\mathscr{C}_x$ contains all clauses $a\in \partial _{\boldsymbol{\Phi }'}x$ that do not induce excess edges. Let $\boldsymbol{d}_x=|\mathscr{C}_x|$ be the number of such clauses. As we pointed out in the proof of Lemma 3.5, $\boldsymbol{d}_x$ is stochastically dominated by a $\textrm {Po}(d)$ variable. Hence, there is a random variable $\boldsymbol{d}_x'$ such that $\boldsymbol{d}_x+\boldsymbol{d}_x'\sim \textrm {Po}(d)$ .

For any variable $x\in \mathscr{A}_\ell$ that is also a variable node of $\mathbb{T}^{(\ell )}[1]$ we add all clauses $a\in \mathscr{C}_x$ and the $k-1$ variables $y\in \partial _{\boldsymbol{\Phi }'}a\cap \mathscr{A}_{\ell +1}$ to $\mathbb{T}^{(\ell +1)}[1]$ . Additionally, $\mathbb{T}^{(\ell +1)}[1]$ contains $\boldsymbol{d}_x'$ independent random clauses that contain $x$ and $k-1$ new variable nodes without a counterpart in $\boldsymbol{\phi }'_{\ell +1,1}$ . Finally, to complete $\mathbb{T}^{(\ell +1)}[1]$ every variable $y$ of $\mathbb{T}^{(\ell )}[1]$ at distance precisely $2\ell$ from $r$ such that $y\not \in V(\boldsymbol{\phi }_{\ell ,1}')$ independently begets $\textrm {Po}(d)$ offspring clause nodes, each containing $k-1$ new variable nodes that do not belong to $V(\boldsymbol{\phi }_{\ell +1,1}')$ .

The coupling ensures that $\boldsymbol{\phi }_{\Lambda ,1}'$ is a sub-formula of $\mathbb{T}^{(\Lambda )}[1]$ unless $\boldsymbol{X}_{\Lambda ,1}\gt -L$ . The extension of this coupling to $\mathscr{L}=\{x_1,\ldots ,x_L\}$ is straightforward. We simply perform BFS exploration from the start variables $x_1,\ldots ,x_L$ one after the other. Given that $\boldsymbol{X}_{\Lambda ,L}=-L$ , we thus couple the sub-formula of $\boldsymbol{\Phi }'$ explored from each $x_i$ with $\mathbb{T}^{(\Lambda )}[i]$ for $1\leq i\leq L$ such that $\boldsymbol{\phi }'_{\Lambda ,L}$ is contained in the union of $\mathbb{T}^{(\Lambda )}[1],\ldots ,\mathbb{T}^{(\Lambda )}[L]$ . Finally, we obtain independent copies $\mathbb{T}[1],\ldots ,\mathbb{T}[L]$ of the (possibly infinite) tree $\mathbb{T}$ by continuing the Galton-Watson processes $\mathbb{T}^{(\Lambda )}[i]$ independently for depths $\ell \gt \Lambda$ .

The remaining task is to compare $|\skew9\bar{\mathscr{L}}|$ with $\sum _{i=1}^L|\overline {\{\mathfrak{x}\}}_{\mathbb{T}[i]}|$ . If $\boldsymbol{X}_{\Lambda ,L}=-L$ and if $\mathfrak{h}_{\mathfrak{x}}(1,\mathbb{T}[i])\lt \Lambda$ for all $1\leq i\leq L$ , then the coupling ensures that all clauses and variables of $\boldsymbol{\phi }_{\Lambda ,L}'$ are contained in the disjoint union of the trees $\mathbb{T}[1],\ldots ,\mathbb{T}[L]$ , and thus $|\skew9\bar{\mathscr{L}}|\leq \sum _{i=1}^L|\overline {\{\mathfrak{x}\}}_{\mathbb{T}[i]}|$ . Therefore, for any $u\gt 0$ we have

(3.16) \begin{align} {\mathbb P}\left [ {\unicode {x1D7D9}\left \{{\boldsymbol{X}_{\Lambda ,L}=-L,\,\max _{1\leq i\leq L}\mathfrak{h}_{\mathfrak{x}}(1,\mathbb{T}[i])\lt \Lambda }\right \}|\skew9\bar{\mathscr{L}}|\gt u}\right ] & \leq {\mathbb P}\left [ {\sum _{i=1}^L|\overline {\{\mathfrak{x}\}}_{\mathbb{T}[i]}|\gt u}\right ] . \end{align}

Furthermore, since $\Lambda \geq \zeta \log \log n$ for a large $\zeta \gt 0$ , Lemma 3.1 ensures that

(3.17) \begin{align} {\mathbb P}\left [ {\max _{1\leq i\leq L}\mathfrak{h}_{\mathfrak{x}}(1,\mathbb{T}[i])\geq \Lambda }\right ] & \leq O(n^{-2}). \end{align}

Combining (3.16) and (3.17) completes the proof.

For later reference we make a note of the following immediate consequence of the coupling from the proof of Lemma 3.6. For two rooted Boolean formulas $\phi ,\phi '$ we write $\phi \cong \phi '$ if there is an isomorphism of $\phi$ and $\phi '$ that preserves the root variable. We consider the random formula $\boldsymbol{\phi }'_{\ell ,1}$ rooted at $x_1$ .

From here on, we set $\Lambda =\lceil c_5\log \log n\rceil$ for a large enough $c_5=c_5(d,k)\gt 0$ . We obtain the following bound on the second moment of $|\skew9\bar{\mathscr{L}}|$ on the event that the excess equals $-L$ .

As a next step we deal with the case that the excess equals $1-L$ . More precisely, with $c_6=c_6(d,k)\gg c_5$ a large enough constant let $\Lambda ^+=\lceil c_6\log \log n\rceil$ . We are going to bound $|\skew9\bar{\mathscr{L}}|$ on the event that $\boldsymbol{X}_{\Lambda ,L}=\boldsymbol{X}_{\Lambda ^+,L}=1-L$ . The proof combines the bound on the probability of this event from Lemma 3.5 with a crude bound on $|\skew9\bar{\mathscr{L}}|$ . To elaborate, since Lemma 3.5 shows that the event $\boldsymbol{X}_{\Lambda ,L}=\boldsymbol{X}_{\Lambda ^+,L}=1-L$ has probability $\tilde O(n^{-1})$ , we can essentially get away with simply bounding $|\skew9\bar{\mathscr{L}}|$ by the total number of variables within a $2\Lambda ^+$ radius around the start variables $\mathscr{L}$ . Indeed, as Lemma 3.5 shows, this number of variables is very likely polylogarithmic in $n$ . Working out the details, we obtain the following.

Figure 3.

A sketch depicting the subformulas $\boldsymbol{\psi }^+, \boldsymbol{\psi }^-, \boldsymbol{\phi }'_{\Lambda ,L}$ , and $\boldsymbol{\phi }'_{\Lambda ^+,L}$ of $\boldsymbol{\Phi }'$ constructed above.

Proof. Let $\mathscr{V}^{\,\,+}=V(\boldsymbol{\phi }'_{\Lambda ,L})\setminus V(\boldsymbol{\phi }'_{\Lambda -1,L})$ and obtain $\boldsymbol{\psi }^-$ from $\boldsymbol{\Phi }'$ by deleting all variables from $V(\boldsymbol{\phi }'_{\Lambda -1,L})$ and all clauses from $F(\boldsymbol{\phi }'_{\Lambda ,L})$ . Further, let $\Lambda ^-=\Lambda ^+-\Lambda$ and let $\boldsymbol{\psi }^+$ be the sub-formula of $\boldsymbol{\psi }^-$ comprising all clauses and variables of $\boldsymbol{\psi }^-$ with distance at most $2\Lambda ^-$ from $\mathscr{V}^{\,\,+}$ (see Figure 3 below). If $\boldsymbol{X}_{\Lambda ,L}=\boldsymbol{X}_{\Lambda ^+,L}=1-L$ then

(3.18) \begin{align} |V(\boldsymbol{\phi }'_{\Lambda ,L})|+|F(\boldsymbol{\phi }'_{\Lambda ,L})|-|E(\boldsymbol{\phi }'_{\Lambda ,L})| & =L-1, \end{align}

(3.19) \begin{align} |V(\boldsymbol{\psi }^+)|+|F(\boldsymbol{\psi }^+)|-|E(\boldsymbol{\psi }^+)| & =|\mathscr{V}^{\,\,+}|. \end{align}

Moreover, Lemma 3.5 shows that for suitable $c_5'=c_5'(d,k,c_5),c_6'=c_6'(d,k,c_6)\gt 0$ we have

(3.20) \begin{align} {\mathbb P}\left [ {|V(\boldsymbol{\phi }'_{\Lambda ,L})|+|F(\boldsymbol{\phi }'_{\Lambda ,L})|\gt \log ^{c_5'}n}\right ] & = O(n^{-2}), \end{align}

(3.21) \begin{align} {\mathbb P}\left [ {|V(\boldsymbol{\phi }'_{\Lambda ^+,L})|+|F(\boldsymbol{\phi }'_{\Lambda ^+,L})|\gt \log ^{c_6'}n}\right ] & = O(n^{-2}). \end{align}

Let $\hat {\mathscr{L}}\subseteq \skew9\bar{\mathscr{L}}$ be the set of literals $l$ that were added to the output set $\skew9\bar{\mathscr{L}}$ by Step 7 of $\texttt {PULP}$ by way of clauses $a\in F(\boldsymbol{\phi }'_{\Lambda ,L})$ , i.e., at distance less than $2\Lambda$ from the initial set $\mathscr{L}$ . Let $\mathscr{V}^-=\{|l|:l\in \hat {\mathscr{L}}\}\cap \mathscr{V}^{\,\,+}$ be the set of all variables at distance $2\Lambda$ from $\mathscr{L}$ in $\boldsymbol{\Phi }'$ that underlie a literal from $\hat {\mathscr{L}}$ . If $\boldsymbol{X}_{\Lambda ,L}=1-L$ , the variables and clauses at distance at most $2\Lambda$ from $\mathscr{L}$ do not cause $\texttt {PULP}$ to run into a contradiction, because each clause contains $k\geq 3$ literals. Therefore, there does not exist a variable $x$ such that both $x$ and $\neg x$ belong to $\hat {\mathscr{L}}$ . Hence, because the signs of $\boldsymbol{\Phi }'$ are uniformly random and $\texttt {PULP}$ proceeds in a BFS order, we may assume without loss of generality that $\hat {\mathscr{L}}$ contains positive literals only. Thus,

(3.22) \begin{align} \mathscr{V}^{\,\,-}=\hat {\mathscr{L}}\cap \mathscr{V}^{\,\,+}\subseteq \mathscr{V}^{\,\,+}. \end{align}

We now apply Lemma 3.6 to the random formula $\boldsymbol{\psi }^-$ . Specifically, let $\skew9\bar{\mathscr{L}}^+$ be the output of $\texttt {PULP}$ on the formula $\boldsymbol{\psi }^-$ with the start set $\mathscr{L}^+$ comprised by the positive literals of $\mathscr{V}^{\,\,+}$ . Further, let $\mathfrak{E}$ be the event that $|V(\boldsymbol{\phi }'_{\Lambda ,L})|+|F(\boldsymbol{\phi }'_{\Lambda ,L})|\leq \log ^{c_5'}n$ . Let

\begin{equation*}\boldsymbol{X}^+=|E(\boldsymbol{\psi }^+)|-|V(\boldsymbol{\psi }^+)|-|F(\boldsymbol{\psi }^+)|\end{equation*}

be the excess of $\boldsymbol{\psi }^+$ . Since $0\lt d\lt d_{\mathrm{uniq}}(k)$ , given $\mathfrak{E}$ the formula $\boldsymbol{\psi }^-$ has the same distribution as a random $k$ -CNF with $n^-=n-O(\log ^cn)$ variables and $\boldsymbol{m}^-\sim \textrm {Po}(d^-n^-/k)$ random clauses, with $0\lt d^-=d+o(1)\lt d_{\mathrm{uniq}}(k)$ . Hence, assuming that $c_6=c_6(d,k)\gt c_5'$ is sufficiently large, Lemma 3.6 shows that

(3.23) \begin{align} {\mathbb P}\left [ {\unicode {x1D7D9}\mathfrak{E}\cap \{\boldsymbol{X}^+=-|\mathscr{V}^{\,\,+}|\}\cdot |\skew9\bar{\mathscr{L}}^+|\gt u}\right ] & \leq {\mathbb P}\left [ {\sum _{1\leq i\leq \log ^{c_5'}n}|\overline {\{\mathfrak{x}\}}_{\mathbb{T}[i]}|\gt u}\right ] +O(n^{-2}) & & (u\gt 0). \end{align}

Combining (3.23) with Corollary 3.3, we conclude that for a large enough $c_7=c_7(d,k) \gt c_6'$ ,

(3.24) \begin{align} {\mathbb P} \big[ {\unicode {x1D7D9}\mathfrak{E}\cap \{\boldsymbol{X}^+=-|\mathscr{V}^{\,\,+}|\}\cdot |\skew9\bar{\mathscr{L}}^+|\gt \log ^{c_7}n}\big ] & =O(n^{-2}). \end{align}

In light of above, we see that

\begin{align*} & {\mathbb E}\big[ {\unicode {x1D7D9}\{\boldsymbol{X}_{\Lambda ,L} =\boldsymbol{X}_{\Lambda ^+,L}=1-L\}|\skew9\bar{\mathscr{L}}|^{3/2}}\big ]\nonumber\\ & \qquad \le {\mathbb E}\big [ {\unicode {x1D7D9}\mathfrak{E}\cap \{\boldsymbol{X}_{\Lambda ,L}=\boldsymbol{X}_{\Lambda ^+,L}=1-L\}|\skew9\bar{\mathscr{L}}|^{3/2}}\big ] + (2n)^{3/2}(1-{\mathbb P}\left [ {\mathfrak{E}}\right ] ) , & & \mbox [ \text{since } |\skew9\bar{\mathscr{L}}|\le 2n]\\ & \qquad \le {\mathbb E}\big [ {\unicode {x1D7D9}\mathfrak{E}\cap \{\boldsymbol{X}_{\Lambda ,L}=\boldsymbol{X}_{\Lambda ^+,L}=1-L\}(|\skew9\bar{\mathscr{L}}^+| + \log ^{c'_5}n)^{3/2}}\big] + o(1) , & & \mbox [ \text{from (3.20)} ]\\ & \qquad \le {\mathbb E}\big [ {\unicode {x1D7D9}\mathfrak{E}\cap \{\boldsymbol{X}^+=-|\mathscr{V}^{\,\,+}|\}(|\skew9\bar{\mathscr{L}}^+| + \log ^{c'_5}n)^{3/2}}\big ] + o(1) , & & \mbox [ \text{from (3.18), (3.19)} ]\\ & \qquad \le {\mathbb P}\big [ {\unicode {x1D7D9}\mathfrak{E}\cap \{\boldsymbol{X}^+=-|\mathscr{V}^{\,\,+}|\}\cdot |\skew9\bar{\mathscr{L}}^+|\gt \log ^{c_7}n}\big] (2n)^{3/2} \\ & \qquad \quad + {\mathbb P}\big[ {\{\boldsymbol{X}_{\Lambda ,L}=1-L\}}\big] (2\log ^{c_7}n)^{3/2} +o(1) & & \mbox [ \text{total probability} ] \\ & \qquad = o(1) & & \mbox [ \text{from }(3.24), \text{Lemma}\,3.5] \end{align*}

completing the proof.