Catching the k-NAESAT Threshold

Introduction

Over the past decade, physicists have developed sophisticated but non-rigorous techniques for the study of random constraint satisfaction problems (‘CSPs’) such as random $k$-SAT or random graph $k$-coloring . This work has led to a remarkably detailed conjectured picture, according to which various phase transitions affect both the combinatorial and computational nature of random problems. By now, some of these predictions have been turned into rigorous theorems. Examples include results on the “shattering” of the solution space , work on (non-)reconstruction and sampling , and even new algorithms for random CSPs . Many of these contributions have led to the development of new rigorous techniques. Indeed, it seems fair to say that, combined, these results have advanced our understanding of random CSPs quite significantly.

However, thus far substantial bits of the statistical mechanics picture have eluded all rigorous attempts. Perhaps most importantly, apart from a very few special cases, the precise thresholds for the existence of solutions in random CSPs have not been pinned down exactly. While rigorous upper and lower bounds can be derived via the first and the second moment method , these bounds do not quite match in most examples, including prominent ones such as random $k$-SAT or random graph $k$-coloring. In fact, the statistical mechanics techniques suggest a striking explanation for this discrepancy, namely the existence of a condensation phase shortly before the threshold for the existence of solutions. In this phase, a crucial necessary condition for the success of the (standard) second moment method is violated. Indeed, in statistical mechanics a deep formalism called Survey Propagation (‘SP’) has been developed expressly to deal with condensation. While SP is primarily an analysis technique, an off-spin has been the SP guided decimation algorithm, which seems highly successful at solving random CSPs experimentally.

In this paper we propose a new SP-inspired second moment method that allows us to overcome the barrier posed by condensation. The specific problem that we work with is random $k$-NAESAT, one of the standard benchmark problems in the theory of random CSPs. Random $k$-NAESAT is technically a bit simpler than random $k$-SAT due to a certain symmetry property, but computationally and structurally both problems have strong similarities. We determine the threshold for the existence of solutions in random $k$-NAESAT up to an additive error that tends to zero exponentially with $k$. This is the first time that the threshold in any random CSP of this type can be calculated with such accuracy. While from a technical viewpoint $k$-NAESAT is perhaps the simplest example of a random CSP that exhibits condensation, our proof technique rests on a rather generic approach. Therefore, we believe that with additional technical work our approach can be extended to many other problems, including random $k$-SAT or random graph $k$-coloring.

To define random $k$-NAESAT formally, let $k\geq 3$ and $n>0$ be integers and let $V=\left\{{x_{1},\ldots,x_{n}}\right\}$ be a set of Boolean variables. For a fixed real $r>0$ we let $m=m(n)=\lceil rn\rceil$. Further, let \mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}=\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{k}(n,m) be a propositional formula obtained by choosing $m$ clauses of length $k$ over $V$ uniformly and independently at random among all $(2n)^{k}$ possible clauses. We say that an assignment $\sigma:V\rightarrow\left\{{0,1}\right\}$ is an NAE-solution (a “solution”) if each clause has both a literal that evaluates to ‘true’ under $\sigma$ and one that evaluates to ‘false’. In other words, both $\sigma$ and its inverse $\bar{\sigma}:x_{i}\mapsto 1-\sigma(x_{i})$ are satisfying assignments of the Boolean formula $\textstyle\Phi$. We say that an event occurs with high probability (“w.h.p.”) if its probability tends to one as $n\rightarrow\infty$.

where $o_{k}(1)$ hides a term that tends to $0$ for large $k$. This left an additive gap of $\frac{1}{2}\ln 2\approx 0.347$, which our main result closes.

There is a sequence $\varepsilon_{k}=2^{-(1-o_{k}(1))k}$ such that

While the numerical improvement obtained in Theorem 1.1 may seem modest, we are going to argue that the result is conceptually quite significant for two reasons. First, we obtain (virtually) matching upper and lower bounds for the first time in a random CSP of this type. Second, and perhaps even more importantly, we devise a rigorous method for taming the condensation phenomenon. Indeed, condensation has been the main obstacle to determining the precise thresholds in random CSPs for the past decade. To understand why, we need to discuss the statistical mechanics picture and its relation to the second moment method.

Condensation and the second moment method

The purpose of the physicists’ Survey Propagation technique is precisely to deal with this type of correlation. The basic idea is to work with a different, non-uniform probability distribution on \mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}). This SP distribution is induced by first choosing a cluster $S_{i}$ uniformly at random among S_{1},\ldots,S_{N(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}})}, and then selecting a solution in that cluster $S_{i}$ uniformly. Since the number N(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) of clusters is (thought to be) exponential in $n$ throughout the condensation phase, two solutions \mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}^{\prime},\mathchoice{\mbox{\boldmath\displaystyle\tau}}{\mbox{\boldmath\textstyle\tau}}{\mbox{\boldmath\scriptstyle\tau}}{\mbox{\boldmath\scriptscriptstyle\tau}}^{\prime} chosen independently from the SP distribution are expected to lie in distinct clusters and thus to decorrelate w.h.p.

The obvious choice of random variable is the number Z(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) of solutions. Since Z(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}})^{2} is just the number of pairs of NAE-solutions, the second moment can be written as

Indeed, Achlioptas and Moore proved that (2.1) is satisfied for Y=Z(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) if $r\leq 2^{k-1}\ln 2-\left({1+\ln 2}\right)/{2}$. Improving upon , Coja-Oghlan and Zdeborová obtained the best previous lower bound (1.1) by considering a slightly modified random variable Z^{\prime}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}). Namely, Z^{\prime}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}})=Z(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}})\cdot\mathchoice{\mbox{\boldmath\displaystyle 1}}{\mbox{\boldmath\textstyle 1}}{\mbox{\boldmath\scriptstyle 1}}{\mbox{\boldmath\scriptscriptstyle 1}}_{\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}\in\mathcal{A}}, where $\mathcal{A}$ is a certain event such that \mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}\in\mathcal{A} w.h.p. In other words, Z^{\prime}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) is equal to Z(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) for almost all formulas, but a small fraction of “bad” formulas (that would blow up the second moment) are excluded. Still, Z^{\prime}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) admits a similar decomposition as (2.3) (one just has to condition on $\mathcal{A}$).

The statistical mechanics prescription to overcome these correlations is to work with the Survey Propagation distribution (first select a cluster uniformly, then choose a random solution from that cluster) rather than the uniform distribution over \mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}). This is precisely the key idea behind our new SP-inspired second moment argument. Roughly speaking, we are going to develop a way to apply the second moment method to the number N(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) of clusters, rather than the number of solutions. More precisely, we introduce a parameter $\beta$ that allows us to work with clusters of a prescribed size. A specific choice of $\beta$ (namely, $\beta=1/2$) corresponds to the SP distribution and thus to working with Y(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}})=N(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}).

This new technique allows us to obtain various further results. For instance, we can pin down the typical values of both Z(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) and N(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) throughout the condensation phase (details omitted). Furthermore, our proof entails the following result that confirms the physics conjecture that pairs of solutions drawn from the SP distribution decorrelate throughout the condensation phase.

Suppose that $r_{cond}\leq r\leq 2^{k-1}\ln 2-\left({\frac{\ln 2}{2}+\frac{1}{4}}\right)-\varepsilon_{k}$. Let \mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}^{\prime},\mathchoice{\mbox{\boldmath\displaystyle\tau}}{\mbox{\boldmath\textstyle\tau}}{\mbox{\boldmath\scriptstyle\tau}}{\mbox{\boldmath\scriptscriptstyle\tau}}^{\prime} be drawn independently from the SP distribution. Then \mbox{dist}(\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}^{\prime},\mathchoice{\mbox{\boldmath\displaystyle\tau}}{\mbox{\boldmath\textstyle\tau}}{\mbox{\boldmath\scriptstyle\tau}}{\mbox{\boldmath\scriptscriptstyle\tau}}^{\prime})=(\frac{1}{2}+o_{k}(1))n w.h.p.

Related work

Rigorous work. The $k$-NAESAT problem is well-known to be NP-complete in the worst case for any $k\geq 3$. In fact, the NP-complete problem of $2$-coloring a $k$-uniform hypergraph (with $k\geq 3$) simply is the special case of $k$-NAESAT without negations. The results in are actually phrased in terms of hypergraph $2$-coloring but carry over to $k$-NAESAT directly.

From a statistical mechanics point of view, many random CSPs are similar to random $k$-NAESAT. In particular, the physics methods suggest the existence of a condensation phase in most random CSPs (e.g., random $k$-SAT/graph $k$-coloring). While provided the prototype for the second moment arguments in these and other problems, the technical details in random graph $k$-coloring or random $k$-SAT are quite a bit more intricate than in random $k$-NAESAT.

For instance, random $k$-NAESAT is simpler than random $k$-SAT because for any NAE-solution $\sigma$ the inverse $\bar{\sigma}:x\mapsto 1-\sigma(x)$ is a NAE-solution as well. This symmetry of the solution space under inversion simplifies the second moment calculations significantly. To cope with the absence of symmetry in random $k$-SAT, Achlioptas and Peres weighted satisfying assignments cleverly in order to recover the beneficial analytic properties that symmetry induces. Our new second moment method is quite different from this weighting approach, since the asymmetry that called for the weighting scheme in is absent in $k$-NAESAT.

None of the (few) random CSPs in which the threshold for the existence of solutions is known precisely has a condensation phase. The most prominent example is random $k$-XORSAT (random linear equations mod $2$) . In this case, the algebraic nature of the problem precludes condensation: all clusters are simply translations of the kernel. Similarly, the condensation phase is empty in the uniquely extendible problem from . Also in random $k$-SAT with $k=k(n)>\log_{2}n$ (i.e., the clause length grows as a function of $n$), where the precise threshold has been determined by Frieze and Wormald via the second moment method, condensation does not occur . Nor does it in random 2-SAT .

Parts of our proof require a precise analysis of geometry of the solution space \mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}). This analysis harnesses some of the ideas that were developed in previous work (e.g., arguments for proving the existence of clusters or of “rigid variables”). However, we need to go beyond these previous arguments significantly in two respects. First, we need to generalize them to accommodate the parameter $\beta$ that controls the cluster sizes. Second, we need rather precise quantitative information about the cluster structures.

Survey Propagation guided decimation. The SP formalism has given rise to an efficient message passing algorithm called Survey Propagation guided decimation (‘SPD’) . Experimentally, SPD seems spectacularly successful at solving, e.g., random $k$-SAT for small values of $k$. Unfortunately, no quantitative analysis of this algorithm is currently known (not even a non-rigorous one). The basic idea behind SPD is to approximate the marginals of the SP distribution (i.e., the probability that a given variable is ‘true’ in a solution drawn from the SP distribution) via a message passing heuristic. Then a variable $x$ is selected according to some rule and is assigned a value based on the (approximate) marginal. The entire procedure is repeated on the “decimated” problem instance where $x$ has been eliminated, until (hopefully) a solution is found.

The decorrelation of random solutions chosen from the SP distribution is a crucial assumption behind the message passing computation of the SP marginals. Corollary 2.1 establishes such a decorrelation property rigorously. However, in order to actually analyze SPD, one would have to generalize Corollary 2.1 to the situation of a “decimated” random formula in which a number of variables have already been eliminated by previous steps of the algorithm. Still, we believe that the techniques developed in this paper are a (necessary) first step towards a rigorous analysis of SPD.

Heavy solutions and the first moment

As we discussed earlier, the demise of the “standard” second moment method in the condensation phase is due to the dominance of few large clusters. The statistical mechanics prescription for circumventing this issue is to work with a non-uniform distribution over solutions that favors “small” clusters. To implement this strategy, we are going to exhibit a simple parameter that governs the size of the cluster that a solution belongs to. Formally, we define the cluster of \sigma\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) as

This definition is vindicated by the following observation from , which shows that any two solutions either have the same cluster or are well-separated.

To proceed, we need to get an idea of the “shape” of the clusters ${\mathcal{C}}(\sigma)$. According to the SP formalism, each cluster has a set ${\mathcal{R}}(\sigma)$ of $\Omega(n)$ rigid variables on which all assignments in ${\mathcal{C}}(\sigma)$ coincide, while the values of the non-rigid variables vary. Formally, we have $\tau(x)=\sigma(x)$ for all $x\in{\mathcal{R}}(\sigma)$ and all $\tau\in{\mathcal{C}}(\sigma)$, while for each $x\not\in{\mathcal{R}}(\sigma)$ there is $\tau\in{\mathcal{C}}(\sigma)$ such that $\tau(x)\neq\sigma(x)$. This implies an immediate bound on the size of ${\mathcal{C}}(\sigma)$, namely $\left|{{\mathcal{C}}(\sigma)}\right|\leq 2^{n-|{\mathcal{R}}(\sigma)|}.$ Indeed, we are going to prove that every cluster has a rigid set of size $\Omega(n)$ w.h.p., and that for all clusters w.h.p.

With $|{\mathcal{C}}(\sigma)|$ controlled by the number of rigid variables, it might seem promising to perform first/second moment arguments for the number of solutions with a suitably chosen number of rigid variables. The problem with this is that there is no simple way to tell whether a given variable is rigid: deciding this is NP-hard in the worst case. Intuitively, this is because rigidity emerges from the “global” interplay of variables and clauses. In effect, parametrizing by the number of rigid variables appears technically infeasible.

Instead, we are going to work with a simple “local” parameter that turns out to be a good substitute. Suppose that $x\in{\mathcal{R}}(\sigma)$. Then $x$ must occur in some clause \mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{i} that would be violated if $x$ was assigned the opposite value $1-\sigma(x)$ (with all other variables unchanged). By the definition of $k$-NAESAT, this means that the other $k-1$ literals of \mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{i} take the opposite value of the literal whose underlying variable $x$ is. In this case we say that $x$ supports \mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{i} under $\sigma$, and we call \mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{i} a critical clause. Moreover, we call a variable that supports a clause blocked, while all other variables are free. While every rigid variable is blocked, the converse is not generally true. Nonetheless, we will see that the number of variables that are blocked but not rigid is small enough so that we can control the cluster sizes in terms of blocked variables.

As a first step, we are going to estimate the expected number of solutions with a given number of blocked variables. Let $\lambda=\frac{kr}{2^{k-1}-1}=k\ln 2+O_{k}(k/2^{k})$ and let us say that \sigma\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) is $\beta$-heavy if exactly $(1-\beta)\exp(-\lambda)n$ variables are free. Let \mathcal{S}_{\beta}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) be the set of all $\beta$-heavy solutions and let Z_{\beta}=\left|{\mathcal{S}_{\beta}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}})}\right| denote their number.

In particular, $Z_{\beta}=0$ for all $\beta<-3/2$ w.h.p.

Clearly, $\textstyle 1$ is a solution iff each clause of $\textstyle\Phi$ contains both a positive and a negative literal. A random clause has this property with probability $1-2^{1-k}$. Since the $m\sim rn$ clauses are chosen independently, we get

Working out the conditional probability that $\textstyle 1$ is $\beta$-heavy is not so straightforward. Whether $\textstyle 1$ is $\beta$-heavy depends only on the critical clauses of $\textstyle\Phi$. Let $X$ be their number. Given that $\textstyle 1$ is a solution, each clause \mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{i} is critical with probability $k/(2^{k-1}-1)$ independently (as there are $2k$ ways to choose the literal signs to obtain a critical clause). Hence, $X$ has a binomial distribution ${\rm Bin}(m,k/(2^{k-1}-1))$ with mean

As a next step, we need to estimate the cluster size of a $\beta$-heavy solution.

W.h.p. for all $-3/2\leq\beta\leq 1$ all $\beta$-heavy \sigma\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) satisfy

The crucial thing to show is that all but a very few blocked variables are rigid. The proof of this builds upon arguments developed in to establish rigidity. Suppose that $x$ is blocked in \sigma\in\mathcal{S}_{\beta}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}), i.e., $x$ supports some clause, say \mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{1}. In any solution $\tau$ with $\tau(x)\neq\sigma(x)$ there must be another variable $x^{\prime}$ that occurs in \mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{1} such that $\tau(x^{\prime})\neq\sigma(x^{\prime})$. Given that $x$ supports \mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{1}, the other $k-1$ variables of \mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{1} are uniformly distributed. Since $\sigma$ has no more than $(1-\beta)\exp(-\lambda)n=(1-\beta+o_{k}(1))2^{-k}n$ free variables, the probability that $x^{\prime}$ is free is bounded by $(1-\beta+o_{k}(1))(k-1)/2^{k}$. In fact, since the expected number of clauses that each variable supports is $\lambda=(1+o_{k}(1))k\ln 2$, it is quite likely that $x^{\prime}$ supports several clauses and that therefore “flipping” $x^{\prime}$ necessitates several further flips. Continuing this argument, we see that the number of flips follows a branching process with (initial) successor rate $\lambda$. A detailed analysis shows that for all but $O_{k}(k4^{-k})n$ blocked initial variables $x$ this process will lead to an avalanche of more than $0.01n$ flips, whence $\tau\not\in{\mathcal{C}}(\sigma)$. This shows that all but $o_{k}(2^{-k})n$ blocked variables are rigid. ∎

W.h.p. we have $N_{\beta}\leq\exp\left[{\eta(\beta)\cdot n/2^{k}}\right]$ for all $\beta$, with

The exponent $\eta(\beta)$ attains its maximum at $\beta=\frac{1}{2}+o_{k}(1)$. Together with our second moment bound below, this implies that for $\beta=\frac{1}{2}+o_{k}(1)$ we have N(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}})=\exp(o_{k}(1)n)\cdot N_{\beta}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) w.h.p., i.e., setting $\beta=\frac{1}{2}+o_{k}(1)$ corresponds to the uniform distribution over clusters and thus to the SP distribution.

The second moment

Thus, the second moment condition (2.1) that we would like to establish for $Y=Z_{\beta}$ becomes

However, (5.1) turns out to be false for any $\beta>0$, for any density $r>0$. To understand why, let us define the degree $d_{x}$ of a variable $x\in V$ as the number of times that $x$ occurs in the formula $\textstyle\Phi$. Let \mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}=(d_{x})_{x\in V} be the degree sequence of $\textstyle\Phi$. It is well known that in the “plain” random formula $\textstyle\Phi$ (without conditioning on \sigma\in\mathcal{S}_{\beta}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}})), the degree of each variable is asymptotically Poisson with mean $km/n$. On the other hand, if we condition on \sigma\in\mathcal{S}_{\beta}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) for some $\beta>0$, then the degrees are not asymptotically Poisson anymore. Indeed, the degree $d_{x}$ is the sum of the number $s_{x}$ of clauses that $x$ supports, and the number $d_{x}^{\prime}$ of times that $x$ appears otherwise. While $d_{x}^{\prime}$ is asymptotically Poisson with mean $<km/n$ as the non-critical clauses do not affect the number of blocked variables at all, $s_{x}$ is not. More precisely, we saw in the proof of Proposition 4.2 that for $\beta>0$, $s_{x}$ is the number of “balls” that $x$ receives in an atypical outcome of the occupancy problem. The precise distribution of $s_{x}$ is quite non-trivial, but it is not difficult to verify that $s_{x}$ does not have a Poisson distribution. Fleshing this observation out leads to the sobering

In summary, conditioning on \sigma\in\mathcal{S}_{\beta}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) with $\beta>0$ imposes a skewed degree distribution that in turn boosts the expected number of $\beta$-heavy solutions beyond the unconditional expectation.

Making things work. We tackle the issue of degree fluctuations by separating the choice of the degree sequence from the choice of the actual formula. More precisely, for a sequence \mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}=(d_{x})_{x\in V} of non-negative integers such that $\sum_{x\in V}d_{x}=km$ we let \mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}} denote a $k$-CNF with degree sequence $\textstyle d$ chosen uniformly at random amongst all such formulas. Fixing a “typical” degree sequence $\textstyle d$, we are going to perform a second moment argument for \mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}, thereby preventing fluctuations of the degrees.

How do we define “typical”? Ideally, we would like $\textstyle d$ to enjoy all the properties that the degree sequence of the (unconditioned) random formula $\textstyle\Phi$ is likely to have. Formally, we let \mathchoice{\mbox{\boldmath\displaystyle D}}{\mbox{\boldmath\textstyle D}}{\mbox{\boldmath\scriptstyle D}}{\mbox{\boldmath\scriptscriptstyle D}}=\mathchoice{\mbox{\boldmath\displaystyle D}}{\mbox{\boldmath\textstyle D}}{\mbox{\boldmath\scriptstyle D}}{\mbox{\boldmath\scriptscriptstyle D}}_{k}(n,m) be the distribution of the degree sequence of $\textstyle\Phi$. What we are going to show is that our second moment argument succeeds for a random degree sequence chosen from the distribution $\textstyle D$ w.h.p.

A $\beta$-heavy solution \sigma\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}) is good if the following conditions are satisfied.

There does not exist \tau\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}) with $0.01n\leq\mbox{dist}(\sigma,\tau)\leq(\frac{1}{2}-2^{-k/3})n$.

No variable supports more than $3k$ clauses under $\sigma$.

The first two items mirror our analysis of the solution space from Section 4. The third one turns out to be useful for a purely technical reason.

Let \mathcal{S}_{g,\beta}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}) be the set of good $\beta$-heavy solutions and set Z_{g,\beta}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}})=\left|{\mathcal{S}_{g,\beta}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}})}\right|. We perform a second moment argument for Z_{g,\beta}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}), with $\textstyle d$ chosen randomly from the distribution $\textstyle D$. The result is

Proposition 5.1 shows that the second moment method for Z_{g,\beta}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}) succeeds for feasible $\beta$. As we observed in Section 4, a feasible $\beta>0$ exists so long as $r\leq 2^{k-1}\ln 2-(\frac{\ln 2}{2}+\frac{1}{4})-O_{k}(k^{4}/2^{k})$. Hence, Proposition 5.1 and the Paley-Zygmund inequality show that \mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}} is NAE-satisfiable for all such $r$ with a non-vanishing probability for $\textstyle d$ chosen randomly from $\textstyle D$. Consequently, the same is true of the unconditioned formula $\textstyle\Phi$ (because we could generate $\textstyle\Phi$ by first choosing $\textstyle d$ from $\textstyle D$ and then generating \mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}). Since the $k$-NAESAT threshold is sharp , we obtain the lower bound in Theorem 1.1.

W.h.p. the degree sequence $\textstyle d$ chosen from $\textstyle D$ is such that

Choose and fix a degree sequence $\textstyle d$. We need to compute the probability that some $\sigma\in\left\{{0,1}\right\}^{V}$ is a good $\beta$-heavy solution. By symmetry, we may assume that \sigma=\mathchoice{\mbox{\boldmath\displaystyle 1}}{\mbox{\boldmath\textstyle 1}}{\mbox{\boldmath\scriptstyle 1}}{\mbox{\boldmath\scriptscriptstyle 1}} is the all-true assignment. Then $\sigma$ is a solution iff every clause contains both a positive and a negative literal. Since the signs of the literals are chosen for all $m$ clauses independently, we see that

Given that $\sigma$ is a solution, the number $X$ of critical clauses has distribution ${\rm Bin}(m,k/(2^{k-1}-1))$, because whether a clause is critical depends on its signs only. As in the proof of Proposition 4.2, to determine the probability that $\sigma$ is $\beta$-heavy we need to solve an occupancy problem: $X$ balls representing the critical clauses are tossed randomly into $n$ bins representing the variables. However, this time the bins have capacities: the bin representing $x\in V$ can hold no more than $\min\left\{{3k,d_{x}}\right\}$ balls in total. Thus, we need to compute the probability that under these constraints, exactly $(1-\beta)2^{-k}n$ bins are empty. This amounts to a rather non-trivial counting problem, but for a random degree sequence $\textstyle d$ the probability differs from the formula obtained in Proposition 4.2 only by an error term that decays exponentially in $k$. More precisely,

Let us provide some intuition why this is. The bin capacities are such that w.h.p. most bins can hold about $kr=k2^{k-1}\ln 2+O_{k}(k)$ balls. By comparison, the total number of balls is $X\sim_{k}mk/(2^{k-1}-1)\sim_{k}n\,k\ln 2$ w.h.p. In effect, the expected number of balls that a typical bin receives is about $k\ln 2$, way smaller than the capacity of that bin. Indeed, since the number of balls that are received by a typical bin is approximately ${\rm Bin}(kr,\frac{nk\ln 2}{km})\approx{\rm Bin}(kr,2^{-k+1})$, the number of balls can be approximated well by a ${\rm Po}(\lambda)$ distribution (with $\lambda=kr/(2^{k-1}-1)\sim_{k}k\ln 2$). Thus, the probability that a bin remains empty is close to $\exp(-\lambda)$, which was the probability of the same event in the experiment without capacities. The technical details of this argument are quite delicate, as the fluctuations of the capacities need to be controlled very carefully.

We now turn to the second moment. Fix some $\sigma\in\left\{{0,1}\right\}^{V}$, say \sigma=\mathchoice{\mbox{\boldmath\displaystyle 1}}{\mbox{\boldmath\textstyle 1}}{\mbox{\boldmath\scriptstyle 1}}{\mbox{\boldmath\scriptscriptstyle 1}}. Let $Z_{g,\beta}(t,\sigma)$ denote the number of good \tau\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}) at distance $t$ from $\sigma$. Using the linearity of expectation and recalling that the set of NAE-solutions is symmetric with respect to inversion, we obtain

Let $I=\left\{{t\in\mathbf{Z}:(\frac{1}{2}-2^{-k/3})n\leq t\leq n/2}\right\}$. The first two conditions from Definition 1 ensure that given that $\sigma$ is good, with certainty we have

This reduces the proof to the analysis of the “central terms” with $t\in I$. The result of this is

There is a constant $C^{\prime}=C^{\prime}(k)\geq 1$ such that for a random $\textstyle d$ we have

This is technically the most challenging bit of this work. The argument boils down to estimating the probability that two random \mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}},\mathchoice{\mbox{\boldmath\displaystyle\tau}}{\mbox{\boldmath\textstyle\tau}}{\mbox{\boldmath\scriptstyle\tau}}{\mbox{\boldmath\scriptscriptstyle\tau}}\in\left\{{0,1}\right\}^{n} with \mbox{dist}(\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}},\mathchoice{\mbox{\boldmath\displaystyle\tau}}{\mbox{\boldmath\textstyle\tau}}{\mbox{\boldmath\scriptstyle\tau}}{\mbox{\boldmath\scriptscriptstyle\tau}})/n=\alpha\in[\frac{1}{2}-2^{-k/3},\frac{1}{2}] simultaneously are good $\beta$-heavy solutions. To compute this probability, we need to analyze the interplay of two occupancy problems as in the proof of Lemma 5.2 with respect to the same degree sequence $\textstyle d$.

More precisely, let $B=\bigcup_{x\in V}\left\{{x}\right\}\times\left\{{1,\ldots,d_{x}}\right\}$ be a set of $km$ “balls”. Generating \mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}} is equivalent to drawing a random bijection \mathchoice{\mbox{\boldmath\displaystyle\pi}}{\mbox{\boldmath\textstyle\pi}}{\mbox{\boldmath\scriptstyle\pi}}{\mbox{\boldmath\scriptscriptstyle\pi}}:\left[{m}\right]\times\left[{k}\right]\rightarrow B, with $\pi(i,j)=(x,l)$ indicating that $x$ is the underlying variable of the $j$th literal of clause $i$, and independently choosing a map \mathchoice{\mbox{\boldmath\displaystyle s}}{\mbox{\boldmath\textstyle s}}{\mbox{\boldmath\scriptstyle s}}{\mbox{\boldmath\scriptscriptstyle s}}:\left[{m}\right]\times\left[{k}\right]\rightarrow\left\{{\pm 1}\right\} indicating the signs. Further, we represent the occupancy problems for \mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}},\mathchoice{\mbox{\boldmath\displaystyle\tau}}{\mbox{\boldmath\textstyle\tau}}{\mbox{\boldmath\scriptstyle\tau}}{\mbox{\boldmath\scriptscriptstyle\tau}} by two “colorings” $g_{\sigma},g_{\tau}:B\rightarrow\left\{{\mathtt{red},\mathtt{blue}}\right\}$, with $g_{\sigma}(x,l)=\mathtt{red}$ indicating that the $l$th position in bin $x$ is occupied under $\sigma$ (and analogously for $\tau$). We compute the probability $p(\alpha,g_{\sigma},g_{\tau})$ that \mathchoice{\mbox{\boldmath\displaystyle\pi}}{\mbox{\boldmath\textstyle\pi}}{\mbox{\boldmath\scriptstyle\pi}}{\mbox{\boldmath\scriptscriptstyle\pi}},\mathchoice{\mbox{\boldmath\displaystyle s}}{\mbox{\boldmath\textstyle s}}{\mbox{\boldmath\scriptstyle s}}{\mbox{\boldmath\scriptscriptstyle s}} induce a formula in which

literal $(i,j)$ supports clause $i$ under $\textstyle\sigma$ iff $g_{\sigma}\circ\pi(i,j)=\mathtt{red}$, and similarly for $\textstyle\tau$.

both \mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}},\mathchoice{\mbox{\boldmath\displaystyle\tau}}{\mbox{\boldmath\textstyle\tau}}{\mbox{\boldmath\scriptstyle\tau}}{\mbox{\boldmath\scriptscriptstyle\tau}} are good $\beta$-heavy solutions.

The result is that for any $g_{\sigma},g_{\tau}$ the “success probability” is minimized at $\alpha=1/2$. Quantitatively,

On the other hand, the total number of assignment pairs satisfies

which is maximized at $\alpha=1/2$. Combining (5.7) and (5.8), we see that for any two colorings $g_{\sigma},g_{\tau}$ the dominant contribution to the second moment stems from $\alpha=\frac{1}{2}+O(1/\sqrt{n})$, i.e., from “perfectly decorrelated” \mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}},\mathchoice{\mbox{\boldmath\displaystyle\tau}}{\mbox{\boldmath\textstyle\tau}}{\mbox{\boldmath\scriptstyle\tau}}{\mbox{\boldmath\scriptscriptstyle\tau}}. The assertion follows by evaluating the contribution of such $\alpha$ explicitly and summing over $g_{\sigma},g_{\tau}$. ∎

Acknowledgment. The first author thanks Dimitris Achlioptas and Lenka Zdeborová for helpful discussions on the second moment method and the statistical mechanics work on random CSPs.

References

Appendix 0.A Preliminaries

The next lemma provides an asymptotically tight bound for the probability that a sum of independent and identically distributed random variables attains a specific value. It will be an important tool in our further analysis, since we will be often interested in the exact probabilities of rare events.

where $\zeta$ and $\xi$ are the solutions to the equations

The first statement follows immediately from Theorem VIII.8 and the remark after Example VIII.11 in . To see the second statement let us write $\zeta_{\delta}$ for the solution to the equation $\frac{\zeta_{\delta}P^{\prime}(\zeta_{\delta})}{P(\zeta_{\delta})}=\mu+\delta\sigma$. Since $P(1)=1$ and $P^{\prime}(1)=\mu$ we infer that if $\delta=0$, then $\zeta_{\delta}=1$. Moreover, a Taylor series expansion around $z=1$ guarantees for all $\delta$ in a bounded interval around 0 that

Since $\sigma^{2}=P^{\prime\prime}(1)+P^{\prime}(1)-P^{\prime}(1)^{2}$, for all $\delta$ in a bounded interval around 0 we have that $\zeta_{\delta}=1+{\delta}/\sigma+O(\delta^{2})$. In order to show (0.A.3) we evaluate the right-hand side of (0.A.1) at $\zeta=\zeta_{\delta}$. Again a Taylor series expansion around $z=1$ guarantees that

The exponential term in (0.A.3) is then obtained by using the fact $1-x=e^{-x-\Theta(x^{2})}$. Finally, note that

By applying again Taylor’s Theorem to this function we obtain after some elementary algebra (details omitted) that the value of this function at $\zeta=\zeta_{\delta}$ equals $\sigma+O(\delta)$, and the proof of (0.A.3) is completed. ∎

The next statement provides tight asymptotic bounds for binomial coefficients.

Let $0<\alpha\leq 1/2$ and $-1/2<\varepsilon<1/2$ be such that $0<\alpha+\varepsilon<1$. Then, as $N\to\infty$

where $H(x)=-x\ln x-(1-x)\ln(1-x)$ denotes the entropy function and $f(x)=x(1-x)$.

The first statement is well-known, see e.g. . To see the second statement, note first that that $H^{\prime}(x)=\ln(\frac{1-x}{x})$ and $H^{\prime\prime}(x)=(x(x-1))^{-1}$, both valid in $(0,1)$. Then, Taylor’s Theorem guarantees that

from which the second statement follows immediately. ∎

Let $X\sim{\rm Bin}(m,k/(2^{k-1}-1))$. We throw $X$ balls into $n$ bins uniformly at random. Let $B_{i}$ denote the number of bins that receive $i$ balls. Then, for any $-3/2\leq\beta\leq 1$

We shall estimate the desired probability by conditioning on any specific value $x$ of $X$. Let $F_{i}$ be the number of balls in the $i$th bin, and let $P_{1},\dots,P_{n}$ be independent Poisson distributed random variables with mean $\lambda$. It is well-known and easy to verify that the distribution of $(F_{1},\dots,F_{n})$ is the same as the distribution of $(P_{1},\dots,P_{n})$, conditioned on the event ${\cal A}(x)=\text{``}\sum_{1\leq i\leq n}P_{i}=x\text{''}$. So, if we denote by $N_{0}$ the number of $P_{i}$’s that are equal to 0, we infer that

By the law of total probability this equals

Note that $N_{0}\sim{\rm Bin}(n,e^{-\lambda})$. Furthermore, if we denote by $P_{1}^{\prime},\dots,P_{\xi n}^{\prime}$, where $\xi=1-(1-\beta)e^{-\lambda}$, independent Poisson variables that are conditioned on being at least $1$, then the above equation implies that

i.e., we require that the sum of the $P_{i}^{\prime}$’s deviates from the expected value by $O_{k}(k2^{-k}n)$. By applying Lemma 0.A.1, where we set $\delta=O_{k}(k^{1/2}2^{-k})$, we conclude that the right-hand side of (0.B.2) is at least $\exp\{-O_{k}(k4^{-k}n)\}$. This shows the lower bound in (0.B.1).

In the remainder of this proof we will show an upper bound for the right-hand side of (0.B.2). To this end, we will argue that the ratio $\Pr[{\rm Bin}(rn,{k}/({2^{k-1}-1}))=\gamma\lambda n]/\Pr[{\rm Po}(\lambda n)=\gamma\lambda n]$ is essentially bounded for all $x$ in the given range, from which the claim immediately follows. More specifically, let us write $x=\gamma\,\lambda n$, where $\xi/\lambda\leq\gamma\leq r/\lambda$. By applying Stirling’s Formula $N!=(1+o(1))\sqrt{2\pi N}(N/e)^{N}$ we infer that

Moreover, by abbreviating $p=k/(2^{k-1}-1)$ we get

Since $\binom{N}{\alpha N}\leq e^{H(\alpha)\,N}$, where $H$ denotes the entropy function, we obtain after some elementary algebra

By combining this with (0.B.3) we obtain the estimate

Recall that $0<\xi/\lambda\leq\gamma\leq r/\lambda=1/p$, and note that both $f(0)$ and $f(1/p)$ are $<0$. Moreover, $f$ has an extremal point at $\gamma=1$, where $f(1)=0$. Thus, for all $\gamma$ in the considered range we have that $f(\gamma)\leq 0$, which implies that the right-hand side of (0.B.2) is bounded from above by at most a polynomial in $n$. This completes the proof of the lemma. ∎

The proof of Proposition 4.2 then completes by applying the following statement.

There is a $k_{0}\geq 3$ such that the following is true. Let $Y\sim{\rm Bin}(n,e^{-\lambda})$. For any $-3/2\leq\beta\leq 1$

Let us abbreviate $\xi=(1-\beta)e^{-\lambda}$. We will assume that $\xi n=\lfloor\xi n\rfloor$, i.e., that $\beta=1-N(e^{-\lambda}n)^{-1}$ for some $N\in\mathbf{N}_{0}$. To see that this is sufficient, note that by Taylor’s Theorem, for any $\beta\geq 1$ and any $|\varepsilon_{n}|\leq(e^{-\lambda}n)^{-1}$ such that $\beta+\varepsilon_{n}\leq 1$ there is a $\delta\in[\beta,\beta+\varepsilon_{n}]$ such that

With the above assumption we proceed with the proof of the claim. The definition of the binomial distribution implies

If $\beta=1$, then $\xi=0$ the above expression simplifies to

Since $f(1)=e^{-\lambda}$ and $\lambda=k\ln 2+\Theta(k2^{-k})$, we infer that the statement is true for $\beta=1$. It remains to treat the case $\beta<1$. Standard bounds for the binomial coefficients imply

Using the estimate $\ln(1-x)=-x-\Theta(x^{2})$, which is valid for $|x|<1$, we infer after some elementary algebra that

Similarly, the second and the third term in (0.B.4) can be estimated with

By plugging this fact together with (0.B.5) into (0.B.4) we finally obtain the desired statement. ∎

We proceed with the proof of the upper bound in Theorem 1.1. Let $Z_{\beta,\gamma}$ denote the number of $\beta$-heavy solutions $\sigma$ such that $\frac{1}{n}\log_{2}\left|{{\mathcal{C}}(\sigma)}\right|\leq(1-\beta-\gamma)e^{-\lambda}$. The following statement provides an upper bound for the expected number of such solutions.

For any $-3/2\leq\beta\leq 1$ and $\gamma>k^{5/2}e^{-\lambda}$ we have for sufficiently large $k$

given that \sigma\in\mathcal{S}_{\beta}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}). Let $\mathcal{F}(\sigma)$ denote the set of free variables, and denote by $\mathcal{X}$ be the set of clauses that do not contain both a positive and a negative literal whose underlying variable is in $V\setminus\mathcal{F}(\sigma)$. Then only the clauses in $\mathcal{X}$ impose constraints on the free variables. We decompose $\mathcal{X}$ into $k-1$ subsets $\mathcal{X}_{2},\dots,\mathcal{X}_{k}$, where $\mathcal{X}_{i}$ the set of all clauses in $\mathcal{X}$ that contain $i$ variables from $\mathcal{F}(\sigma)$. Note that $\mathcal{X}=\cup_{i=2}^{k}\mathcal{X}_{i}$, as any clause with only one variable from $\mathcal{F}(\sigma)$ necessarily contains both positive and negative literals whose underlying variables are not free. Let $X_{i}=|X_{i}|$. Since only the clauses in $\mathcal{X}$ impose constraints on variables from $\mathcal{F}(\sigma)$ that occur in them, we infer that

from which the statement in the lemma follows immediately.

Note that the set $\mathcal{F}(\sigma)$ is determined by the critical clauses only. Therefore, given that \sigma\in\mathcal{S}_{\beta}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}), the variables that occur in the non-critical clauses are independent and uniformly distributed over the set of all variables. Similarly, given that \sigma\in\mathcal{S}_{\beta}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) the $k-1$ variables that contributed the “majority value” to each critical clause are independently uniformly distributed. Therefore, $X_{i}$ is stochastically dominated by a binomial random variable

Our assumption $-3/2\leq\beta\leq 1$ guarantees that $(1-\beta)e^{-\lambda}\leq 3e^{-\lambda}\leq 3\cdot 2^{-k}$. By using the estimate $\binom{k}{i}\leq k^{i}$ we infer that

Let us fix $\delta=\frac{1}{5}\ln k$. By the arithmetic-geometric mean inequality we obtain that the expression in the previous equation is at most

Since $t=\gamma e^{-\lambda}>k^{5/2}4^{-k}$, for sufficiently large $k$ we get (0.B.6), and the proof is completed. ∎

Let $r_{*}$ be the least density $r$ such that $g(\beta)<-k^{3}4^{-k+1}$ for all $\beta\geq-1$. Since $g$ is maximized for $\beta=1/2$, where $g(1/2)=\frac{2\rho-\ln 2}{2^{k}}-\frac{1}{2}e^{-\lambda}$, it is easily verified that

With $r=r^{*}$ the random formula $\textstyle\Phi$ does not have a NAE-solution w.h.p.

Let us assume for the induction step that $i$ is such that w.h.p. $Z_{\leq\beta_{i}}=0$. Let $\gamma_{0}=k^{3}e^{-\lambda}$, and let $Z^{\prime}$ be the number of solutions that are $\beta^{\prime}$-heavy for some $\beta^{\prime}>\beta_{i}$ and such that $\frac{1}{n}\log_{2}\left|{{\mathcal{C}}(\sigma)}\right|\geq(1-\beta_{i}-\gamma_{0})e^{-\lambda}$. Then, by applying Proposition 4.2 and using that $h(x)$ is monotone increasing for $x\leq 0$ and monotone decreasing for $x\geq 0$ we obtain

Let us first consider the case $\beta_{i}\leq 0$. The choice of $r^{*}$ guarantees that $g(0)=h(0)-e^{-\lambda}\ln 2<-k^{3}4^{-k+1}$. Since $Z^{\prime}>0$ implies $Z^{\prime}\geq\exp\{n(1-\beta_{i}-\gamma_{0})e^{-\lambda}\ln 2\}\geq\exp\{n(1-\gamma_{0})e^{-\lambda}\ln 2\}$ or otherwise $Z_{\leq\beta_{i}}>0$ we infer for sufficiently large $k$ that

On the other hand, if $\beta_{i}>0$, then again the choice of $r^{*}$ is such that $g(\beta_{i})=h(\beta_{i})-(1-\beta_{i})e^{-\lambda}\ln 2<-k^{3}4^{-k+1}$. Thus, for sufficiently large $k$

So, since $Z^{\prime}>0$ implies $Z^{\prime}\geq\exp\{n(1-\beta_{i}-\gamma_{0})e^{-\lambda}\ln 2\}$ or otherwise $Z_{\leq\beta_{i}}>0$ we infer that

Thus, in both cases we have that $\Pr[Z^{\prime}>0]=o(1)$. In remains to consider all satisfying assignments such that $\frac{1}{n}\log_{2}\left|{{\mathcal{C}}(\sigma)}\right|\leq(1-\beta_{i}-\gamma_{0})e^{-\lambda}$. More specifically, let $Z_{j}^{\prime}$ be the number of solutions that are $\beta^{\prime}$-heavy for some $\beta_{i}<\beta^{\prime}\leq\beta_{i+1}$ and such that

where $\gamma_{j+1}=2\gamma_{j}$. Choose $\beta^{\prime}$ be such that \mathcal{S}_{\beta^{\prime}}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}})\cap{\mathcal{C}}(\sigma) is maximized. Then

Since $Z_{\leq\beta_{i}}=0$ w.h.p., we may assume that $\beta^{\prime}>\beta_{i}$. There are two cases to consider.

Case 1: $1-\beta_{i}-\gamma_{j+1}>1-\beta^{\prime}$. We will show that in this case the number of $\beta^{\prime}$-heavy assignments is larger than the expected value by at least an exponential factor. Indeed, our assumption on $g$ implies for sufficiently large $k$ that

By Markov’s inequality, the probability of this event is $\exp(-\Omega(n))$.

Case 2: $1-\beta_{i}-\gamma_{j+1}\leq 1-\beta^{\prime}$. The assumption guarantees the existence of a $\gamma^{\prime}>0$ such that

In this case we will show that the number of solutions in $\mathcal{S}_{\beta^{\prime},\gamma^{\prime}}(\Phi)$ is larger than the expected value by at least an exponential factor. Equation (0.B.8) implies that

If $\gamma^{\prime}>k^{5/2}e^{-\lambda}$, then by Lemma 0.B.3 and our assumption on $g$

Since the probability that either case occurs is $\exp(-\Omega(n))$, we conclude that the same is true of the event “$Z_{j}^{\prime}>0$”. Taking the union bound over $j$ then completes the induction step, i.e., $Z_{\leq\beta_{i+1}}=0$ w.h.p.∎

Appendix 0.C Proof of the lower bound

Let \mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}},\mathchoice{\mbox{\boldmath\displaystyle D}}{\mbox{\boldmath\textstyle D}}{\mbox{\boldmath\scriptstyle D}}{\mbox{\boldmath\scriptscriptstyle D}} be as in Section 5. In the extended abstract, we presented a slightly streamlined definition of “good”. Technically it will be more convenient to work with the following definition. (It will emerge later that the two definitions are equivalent.) Recall that $\lambda=kr/(2^{k-1}-1)$.

We call a solution $\sigma\in\left\{{0,1}\right\}^{V}$ of \mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}} $\beta$-good if it satisfies the following conditions.

$\sigma$ is $\beta$-heavy and the total number of critical clauses is equal to $\lambda n$.

No variable supports more than $3k$ clauses.

Let $\mathcal{Z}_{\beta}$ be the number of $\beta$-good solutions. As a first step, we determine the expectation of $\mathcal{Z}_{\beta}$.

Suppose that $\textstyle d$ is chosen from the distribution $\textstyle D$. Then w.h.p.

Let us fix an assignment $\sigma\in\left\{{0,1}\right\}^{V}$, say \sigma=\mathchoice{\mbox{\boldmath\displaystyle 1}}{\mbox{\boldmath\textstyle 1}}{\mbox{\boldmath\scriptstyle 1}}{\mbox{\boldmath\scriptscriptstyle 1}}. Moreover, let $\Sigma$ be the event that $\sigma$ is a $\beta$-good solution. Let $\mathcal{Z}_{\beta}(t)$ be the number of $\beta$-good solutions \tau\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}) such that $\mbox{dist}(\sigma,\tau)=t$. Then the symmetry properties of \mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}} imply the following.

For any $r<r^{*}$ there exists $0<\beta\leq\frac{1}{2}$ such that for $\textstyle d$ chosen from $\textstyle D$ w.h.p.

This follows from Proposition 0.C.1 and a little bit of calculus. ∎

As a next step, we are going to bound the second summand in (0.C.1). This is technically the most demanding part of this work. In Appendix 0.D we are going to prove the following.

Let $\delta=2^{-k/3}$. There is a number $C=C(k)$ such that for a degree sequence $\textstyle d$ chosen from $\textstyle D$ we have w.h.p.

This follows directly from (0.C.1), Lemma 0.C.1, and Lemma 0.C.2. ∎

Proof of Theorem 1.1 (lower bound). By Corollary 0.C.1 and the Paley-Zygmund inequality, for any $r<r^{*}$ for a random $\textstyle d$ chosen from the distribution $\textstyle D$ we have w.h.p.

Since $\textstyle D$ is precisely the distribution of the degree sequence of the uniformly random formula $\textstyle\Phi$, we have

where the expectation on the left hand side ranges over $\textstyle d$ chosen from $\textstyle D$. Therefore, (0.C.2) implies that

C.2 Proof of Proposition 0.C.1

We begin with the following simple observation.

We may assume without loss that \sigma=\mathchoice{\mbox{\boldmath\displaystyle 1}}{\mbox{\boldmath\textstyle 1}}{\mbox{\boldmath\scriptstyle 1}}{\mbox{\boldmath\scriptscriptstyle 1}}. Then $\sigma$ is a solution iff each clause has both a positive and a negative literal. Since the signs of the literals are chosen uniformly and independently, the assertion follows. ∎

We defer the proof of the following result to Section 0.C.3.

Let $\textstyle d$ be a chosen from $\textstyle D$. Then w.h.p. we have

Let $\textstyle d$ be chosen from $\textstyle D$. Then w.h.p. the following is true.

Let us call $S\subset V$ dense if each variable in $S$ supports at least two clauses that each feature another variable from $S$.

Let $\textstyle d$ be chosen from $\textstyle D$ and let $\sigma\in\left\{{0,1}\right\}^{V}$. Let $\mathcal{A}$ be the event that \sigma\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}) and that $\sigma$ satisfies conditions 1.–2. in Definition 2. Then w.h.p.

We may assume that $\textstyle d$ satisfies (0.C.4). Let $\mathcal{D}(S)$ be the event that $S\subset V$ is dense. We claim that

Indeed, the factor $k^{2|S|}$ accounts for the number of ways to choose the two relevant clauses supported by each variable, and the second factor bounds the probability that each of these clauses contains another occurrence of a variable from $S$. Now, (0.C.4) yields

For $0<s\leq 1/k^{5}$ let $X_{s}$ be the number of sets $S$ of size $|S|=sn$ for which $\mathcal{D}(S)$ occurs. Then

Summing over all possible $s$ and using Markov’s inequality completes the proof. ∎

The expected number of solutions \sigma\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) in which more than $k^{4}2^{-k}n$ variables support at most four clauses is $\leq\exp(-nk^{3}/2^{k})$.

Fix an assignment $\sigma\in\left\{{0,1}\right\}^{V}$, say \sigma=\mathchoice{\mbox{\boldmath\displaystyle 1}}{\mbox{\boldmath\textstyle 1}}{\mbox{\boldmath\scriptstyle 1}}{\mbox{\boldmath\scriptscriptstyle 1}}. Then number of clauses supported by each $x\in V$ is asymptotically Poisson with mean $\lambda$. Let ${\cal E}_{x}$ be the event that $x$ supports no more than three clauses. Then

The events $({\cal E}_{x})_{x\in V}$ are negatively correlated. Therefore, the total number $X$ of variables $x\in V$ for which ${\cal E}_{x}$ occurs is stochastically dominated by a binomial variable ${\rm Bin}(n,k^{4}2^{-k-1})$. Hence, the assertion follows from Chernoff bounds. ∎

Let us call a set $S\subset V$ self-contained if each variable in $S$ supports at least two clauses that consist of variables in $S$ only. There is a simple process that yields a (possibly empty) self-contained set $S$.

For each variable $x$ that supports at least one clause, choose such a clause $C_{x}$ randomly.

Let $R$ be the set of all variables that support at least four clauses.

While there is a variable $x\in R$ that supports fewer than two clauses \mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{i}\neq C_{x} that consist of variables of $R$ only, remove $x$ from $R$.

The clauses $C_{x}$ will play a special role later.

The expected number of solutions \sigma\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) for which the above process yields a set $R$ of size $|R|\leq(1-k^{5}/2^{k})n$ is bounded by $\exp(-\Omega(n))$.

Let $\sigma\in\left\{{0,1}\right\}^{V}$ be an assignment, say \sigma=\mathchoice{\mbox{\boldmath\displaystyle 1}}{\mbox{\boldmath\textstyle 1}}{\mbox{\boldmath\scriptstyle 1}}{\mbox{\boldmath\scriptscriptstyle 1}}. Let $Q$ be the set of all variables that support fewer than three clauses. By Lemma 0.C.6 we may condition on $|Q|\leq k^{4}2^{-k}n$. Assume that its size is $|R|\leq(1-k^{5}/2^{k})n$. Then there exists a set $S\subset V\setminus(R\cup Q)$ of size $\frac{1}{2}k^{5}n/2^{k}\leq S\leq k^{5}n/2^{k}$ such that each variable in $S$ supports two clauses that contain another variable from $S\cup Q$. With $s=|S|/n$ the probability of this event is bounded by

Hence, the expected number of set $S$ for which the aforementioned event occurs is bounded by

Let $\textstyle d$ be chosen from $\textstyle D$. Then the expected number of solutions \sigma\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}) for which the above process yields a set $R$ of size $|R|\leq(1-k^{5}/2^{k})n$ is bounded by $\exp(-\Omega(n))$.

Since the random formula $\textstyle\Phi$ can be generated by first choosing $\textstyle d$ from $\textstyle D$ and then generating \mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}, the assertion follows from Lemma 0.C.7. ∎

Let us call a variable $x$ is attached if $x$ supports a clause whose other $k-1$ variables belong to $R$.

W.h.p. a degree sequence $\textstyle d$ chosen from $\textstyle D$ has the following property. Let $\sigma\in\left\{{0,1}\right\}^{V}$ and let $\mathcal{A}$ be the event that \sigma\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}) and that $\sigma$ satisfies Conditions 1. and 2. in Definition 2. Moreover, let $Y$ be the number variables that support a clause but that are not attached. Then

Let us call a variable $x\in V$ $\xi$-rigid in a solution \sigma\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}) if for any solution \tau\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}) with $\tau(x)\neq\sigma(x)$ we have $\mbox{dist}(\sigma,\tau)\geq\xi n$.

W.h.p. a degree sequence $\textstyle d$ chosen from $\textstyle D$ has the following property. Let $\sigma\in\left\{{0,1}\right\}^{V}$ and let $\mathcal{A}$ be the event that \sigma\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}) and that $\sigma$ satisfies Conditions 1. and 2. in Definition 2. Moreover, let $Y$ be the number of variables that support a clause but that are $k^{-5}$-rigid. Then

We condition on the event $\mathcal{A}$. By Corollary 0.C.2, we may assume that the self-contained set $R$ has size $|R|\geq(1-k^{5}/2^{k})n$. Assume that there is \tau\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}), $\mbox{dist}(\sigma,\tau)<n/k^{5}$, such that

is non-empty. Then $\Delta$ is dense. Indeed, every $x\in\Delta$ supports at least two clauses, and thus $\Delta$ must contain another variable from each of them. Thus, Lemma 0.C.5 shows that $\left|{\Delta}\right|\geq n/k^{5}$, which is a contradiction.

Hence, w.h.p. all variables $x\in R$ are $k^{-5}$-rigid. Furthermore, if a variable $y$ is attached, then for any solution $\tau$ with $\tau(y)\neq\sigma(y)$ there is $x\in R$ such that $\tau(x)\neq\sigma(x)$. Consequently, all attached variables are $k^{-5}$-rigid w.h.p. Therefore, the assertion follows from Corollary 0.C.3. ∎

To complete the proof, we need the following fairly simple lemma.

The expected number of pairs of solutions \sigma,\tau\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) such that $\frac{n}{k^{6}}\leq\mbox{dist}(\sigma,\tau)\leq(\frac{1}{2}-2^{-k/2})n$ is $\leq\exp(-\Omega(n))$.

For a given $0\leq\alpha\leq 1$ let $P_{\alpha}$ denote the number of pairs \sigma,\tau\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) with $\mbox{dist}(\sigma,\tau)=\alpha n$ As worked out in , we have

It is a mere exercise in calculus to verify that the r.h.s. is strictly negative for all $k^{-6}\leq\alpha\leq\frac{1}{2}-2^{-k/2}$. ∎

W.h.p. a degree sequence $\textstyle d$ chosen from $\textstyle D$ has the following property. The expected number of pairs of solutions \sigma,\tau\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}) such that $\frac{n}{k^{6}}\leq\mbox{dist}(\sigma,\tau)\leq(\frac{1}{2}-2^{-k/2})n$ is $\leq\exp(-\Omega(n))$.

Combining Lemma 0.C.3, Proposition 0.C.2, Corollary 0.C.4, and Corollary 0.C.5, we obtain

W.h.p. a degree sequence $\textstyle d$ chosen from $\textstyle D$ has the following property. Let $\sigma\in\left\{{0,1}\right\}^{V}$ and let $\mathcal{A}$ be the event that \sigma\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}) and that $\sigma$ satisfies Conditions 1. and 2. in Definition 2. Then

Finally, Proposition 0.C.1 is a direct consequence of Lemma 0.C.3, Proposition 0.C.2, and Corollary 0.C.6.

C.3 Proof of Proposition 0.C.2

Let us begin with establishing the probable properties of $\mathbf{d}$ that we will need.