Going after the k-SAT Threshold

Introduction

Since the early 2000s physicists have developed a sophisticated but highly non-rigorous technique called the “cavity method” for the study of random constraint satisfaction problems. This method allowed them to put forward a very detailed conjectured picture according to which various phase transitions affect both computational and structural properties of random CSPs. In addition, the cavity method has inspired new message passing algorithms called Belief/Survey Propagation guided decimation. Over the past few years there has been significant progress in turning bits and pieces of the physics picture into rigorous theorems. Examples include results on the interpolation method or the geometry of the solution space and their algorithmic implications .

In spite of this progress, substantial gaps remain. Perhaps most importantly, in most random CSPs the threshold for the existence of solutions is not known precisely. In the relatively simple case of the random $k$-NAESAT (“Not-All-Equal-Satisfiability”) problem the difference between the best current lower and upper bounds is as tiny as $2^{-\Omega(k)}$ . By contrast, in random graph $k$-coloring, a problem already studied by Erdős and Rényi in the 1960s, the best current bounds differ by $\Theta(\ln k)$ . Hence, the difference is unbounded in terms of the number of colors. Even worse, in random $k$-SAT the gap is as big as $\Theta(k)$ . Yet random $k$-SAT is probably the single most important example of a random CSP, not least due to the great amount of experimental and algorithmic work conducted on it (e.g., ).

The reason for the large gap in random $k$-SAT is that the satisfiability problem lacks a certain symmetry property. This property is vital to the current rigorous proof methods, particularly the second moment method, on which most of the previous work is based (e.g., ). More precisely, in random graph coloring the different colors all play the exact same role: for any proper coloring of a graph, another proper coloring can be obtained by simply permuting the color classes (e.g., color all red vertices blue and vice versa). Similarly, in $k$-NAESAT, where the requirement is that in each clause at least one literal must be true and at least one false, the binary inverse of any NAE-solution is a NAE-solution as well. By contrast, in $k$-SAT there is an inherent asymmetry between the Boolean values ‘true’ and ‘false’.

As has been noticed in prior work , the second moment method is fundamentally ill-posed to deal with such asymmetries. Roughly speaking, the second moment method is based on the assumption that in a random CSP instance, two randomly chosen solutions are perfectly uncorrelated. But in random $k$-SAT, this is simply not the case. Indeed, suppose that a variable $x$ appears much more often positively than negatively throughout the formula. Then it seems reasonable to expect that most satisfying assignments set $x$ to ‘true’, thereby satisfying all clauses where $x$ appears positively. More generally, define the majority vote $\sigma_{maj}$ to be the assignment that sets variable $x$ to true if it appears more often positively than negatively, and to false otherwise. Then we expect that the satisfying assignments of a random formula “gravitate toward” $\sigma_{maj}$. Unfortunately, the correlations among satisfying assignments induced by this drift toward $\sigma_{maj}$ doom the second moment method. Previously this issue was sidestepped by symmetrizing the problem artificially . But this inevitably leaves a $\Theta(k)$ gap.

The main contribution of the present work is a new asymmetric second moment method that enables us to tackle this problem head on. A key feature of this method is that we harness the Belief Propagation calculation from physics, called the “replica symmetric case” of the cavity method in physics jargon. We are going to employ Belief Propagation directly as an “educated guess” in the design the random variable upon which our proof is based in order to quantify how much a typical satisfying assignment leans toward $\sigma_{maj}$.

This is in contrast to most prior work on the subject, where individual statements hypothesized on the basis of physics arguments were proved via completely different methods (with the notable exception of the interpolation technique ). Hence, we view the present work as a pivotal step in the long-term effort of providing a rigorous foundation for the physicists’ cavity method. In fact, the general approach developed here does not hinge on particular properties of the $k$-SAT problem, and thus we expect that the technique will extend to other asymmetric problems as well. Examples include not only other random CSPs that are asymmetric per se, but also instances of random problems that arise at intermediate steps of message passing algorithms such as Belief/Survey Propagation guided decimation, even if the initial problem is symmetric. In particular, we believe that getting a handle on asymmetric problems is a necessary step to analyze such message passing algorithms accurately.

To state our results precisely, we let $k\geq 3,n>0$ be integers and we let $V=\left\{{x_{1},\ldots,x_{n}}\right\}$ be a set of $n$ Boolean variables. 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) denote a Boolean formula with $m$ clauses of length $k$ over the variables $V$ chosen uniformly at random among all $(2n)^{km}$ such formulas. Let $r=m/n$ denote the density. We say that an event occurs with high probability (‘w.h.p.’) if its probability tends to $1$ as $n\rightarrow\infty$.

where $o_{k}(1)$ hides a term that tends to $0$ for large $k$. The best prior lower bound is due to Achlioptas and Peres , who used a “symmetric” second moment argument to show

The bounds (1) and (2) leave an additive gap of $k\cdot\frac{\ln 2}{2}+\frac{1}{2}+o_{k}(1)$, i.e., the gap is unbounded in terms of $k$.

There is $\varepsilon_{k}=o_{k}(1)$ such that

Apart from the quantitative improvement, the main point of this paper is that we manage to solve the problem of asymmetry in random CSPs for the first time. To explain this point, we start by discussing what we mean by asymmetry and how it derails the second moment method. That this is so was already intuited in . In the next section, we are going to verify and elaborate on those discussions.

Asymmetry and the second moment method

The second moment method. In general, the second moment method works as follows. Suppose that Z=Z(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) is a non-negative random variable such that $Z>0$ only if $\textstyle\Phi$ is satisfiable. Moreover, suppose that for some density $r>0$ there is a number $C=C(k)>0$ that may depend on $k$ but not on $n$ such that

Hence, we “just” need to find a random variable that satisfies (5). Let \mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) denote the set of satisfying assignments; then certainly Z=\left|{\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}})}\right| is the most obvious choice. However, this “vanilla” second moment argument turns out to fail spectacularly. We need to understand why.

Asymmetry and the majority vote. The origin of the problem is that $k$-SAT is asymmetric in the following sense. Suppose that all we know about the random formula $\textstyle\Phi$ is for each variable $x$ the number $d_{x}$ of times that $x$ appears as a positive literal in the formula, and the number $d_{\neg x}$ of negative occurrences. Then our best stab at constructing a satisfying assignment seems to be the “majority vote” assigment $\sigma_{maj}$ where we set $x$ to true if $d_{x}>d_{\neg x}$ and to false otherwise. Indeed, by maximizing the total number of true literal occurrences, of which a satisfying assignment must put one in every clause, $\sigma_{maj}$ also maximizes the probability of being satisfiable.

Our proof of Theorem 1.1 allows us to formalize this observation, thereby verifying a conjecture from . Let $\mbox{dist}(\cdot,\cdot)$ denote the Hamming distance.

Hence, the average Hamming distance of \sigma\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) from $\sigma_{maj}$ is strictly smaller than $n/2$, i.e., the set \mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) is “skewed toward” $\sigma_{maj}$ w.h.p.

This asymmetry dooms the second moment method. To see why, let

Let us highlight this tradeoff, as it is characteristic of the kind of trouble that asymmetry causes. For $\xi>0$ independent of $n$ but sufficiently small it turns out that for a certain constant $c>0$,

That is, the probability is exponentially small but, like in the Chernoff bound, the exponent is a quadratic function of $\xi$. By comparison, increasing the majority weight by $\xi$ boosts the expected number of satisfying assignments by a linear exponential factor: there is $c^{\prime}>0$ such that

For any $k\geq 3$ and $r>2^{k}/k$ we have

In summary, the drift toward $\sigma_{maj}$ and the resulting fluctuations of the majority weight induce a tremendous source of variance, derailing the “vanilla” second moment argument.

A quick fix? We saw that to make an asymmetric second moment argument work, we need to rule out fluctuations of the majority weight. A sensible way of implementing this is by actually fixing the entire vector \mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}=(d_{x},d_{\neg x})_{x\in V} that counts the positively/negatively occurrences of each variable. More precisely, given a non-negative integer vector \mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}=(d_{x},d_{\neg x})_{x\in V} with $\sum_{x\in V}d_{x}+d_{\neg x}=km$ 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 uniformly random $k$-CNF in which each variable $x$ appears $d_{x}$ times positively and $d_{\neg x}$ times negatively. Then we can split the generation of a random formula $\textstyle\Phi$ into two steps:

First, choose the occurrence vector $\textstyle d$ randomly from the “correct” distribution $\textstyle D$.

Then, choose a random formula \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 “correct” $\textstyle D$ is as follows. Let {\mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}}=(e_{x},e_{\neg x})_{x\in V} be a family of independent Poisson variables with mean $kr/2$ each. Moreover, let ${\cal E}$ be the event that $\sum_{x\in V}e_{x}+e_{\neg x}=km$. Let $\textstyle D$ be the conditional distribution of $\textstyle e$ given ${\cal E}$. Then standard arguments show that the outcome of first choosing $\textstyle d$ and then \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 exactly the uniformly random $\textstyle\Phi$.

The point of generating $\textstyle\Phi$ in two steps as above is that given the outcome $\textstyle d$ of the first step, the majority weight is fixed. Hence, if we could show that given a “typical” $\textstyle d$, the second moment succeeds for |\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}}})| we would obtain a lower bound on $r_{k-SAT}$. Unfortunately, matters are not so simple.

The explanation for this is that even if we fix $\textstyle d$, various other types of fluctuations remain, turning \left|{\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}}})}\right| into a “lottery”. For instance, even given $\textstyle d$ the number of clauses that are unsatisfied under $\sigma_{maj}$ fluctuates. Hence, the inherent asymmetry of $k$-SAT puts not only the majority weight but also various other parameters on a slippery slope. What we need is a way of controlling all these fluctuations simultaneously. We will present our solution in Section 5.

Catching the $k$-SAT threshold? Before we come to that, let us discuss what it would take to eliminate the (small but non-zero) gap left by Theorem 1.1, i.e., how far we are from “catching” the $k$-SAT threshold. The physicists’ cavity method comes in two installments. The (relatively speaking) simpler “replica symmetric” version is based on Belief Propagation. Theorem 1.1 provides a rigorous proof of the best possible bound on the $k$-SAT threshold that can be obtained from this version of the cavity method (up to possibly the precise error term $\varepsilon_{k}$) .

In we managed to prove rigorously that the 1RSB prediction for the random $k$-NAESAT threshold is correct (up to an additive $2^{-\Omega(k)}$). However, depends heavily on the fact that $k$-NAESAT is symmetric. While it would be very interesting to combine the merits of the present paper with those of , this appears to be quite challenging. Thus, putting the 1RSB calculation for random $k$-SAT on a rigorous foundation remains an important open problem. That said, we believe that any such attempt would need to build upon the techniques developed in this paper.

Related work

Also in random $k$-XORSAT (random linear equations mod 2) the threshold for the existence of solutions is known precisely . The proof relies on computing the second moment of the number of solutions (after the instance has been stripped down to a suitable core). In contrast to random $k$-SAT, the random $k$-XORSAT problem is symmetric (cf. Remark 5.5 below), albeit in a more subtle way than $k$-NAESAT.

Other problems where the second moment method succeeds are symmetric as well. Pioneering the use of the second moment method in random CSPs, Achlioptas and Moore computed the random $k$-NAESAT threshold within an additive $1/2$. By enhancing this argument with insights from physics this gap can be narrowed to a mere $2^{-\Omega(k)}$ . Moreover, the best current bounds on the random (hyper)graph $k$-colorability thresholds are based on “vanilla” second moment arguments as well . In summary, in all the previous second moment arguments, the issue of asymmetry either did not appear at all by the nature of the problem , or it was sidestepped .

The best current algorithms for random $k$-SAT find satisfying assignments w.h.p. for densities up to $1.817\cdot 2^{k}/k$ (better for small $k$) resp. $2^{k}\ln(k)/k$ (better for large $k$) , a factor of $\Theta(k/\ln k)$ below the satisfiability threshold. By comparison, the Lovász Local Lemma and its algorithmic version succeed up to $r=\Theta(2^{k}/k^{2})$ .

Apart from experimental work , very little is known about the physics-inspired message passing algorithms (“Belief/Survey Propagation guided decimation”) . The most basic variant of Belief Propagation guided decimation is known to fail w.h.p. on random formulas if $r>c\cdot 2^{k}/k$ for some constant $c>0$ . However, it is conceivable that Survey Propagation and/or other variants of Belief Propagation perform better.

Preliminaries

We shall make repeated use of the following local limit theorem for the sums of independent random variables, see and .

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

From this we can rather easily derive the following well-known statement about the rate function of the binomial distribution.

If $p,q$ remain fixed as $n\rightarrow\infty$, then

The following form of the chain rule will prove useful.

Let $g:\mathbf{R}^{a}\rightarrow\mathbf{R}^{b}$ and $f:\mathbf{R}^{b}\rightarrow\mathbf{R}$ be of class $C^{2}$, i.e, with continuous second derivatives. Then for any $x_{0}\in\mathbf{R}^{a}$ and with $y_{0}=g(x_{0})$ we have for any $i,j\in\left[{a}\right]$

Finally, we need the following version of the inverse function theorem that states under which conditions a given system of equations can be solved around a specific point $u$. A detailed exposition can be found in .

Let $U\subset\mathbf{R}^{h}$ be open and let $f\in C^{1}(U)$. Assume that $u\in U$ and $\lambda>0$ are such that

Then for each $y\in\mathbf{R}^{h}$ such that $\left\|{y-f(u)}\right\|\leq\lambda/2$ there is precisely one $x\in\mathbf{R}^{h}$ such that $\left\|{x-u}\right\|\leq r$ and $f(x)=y$. Furthermore, the inverse map $f^{-1}$ is $C^{1}$ on $\left\{{x\in\mathbf{R}^{h}:\left\|{x-u}\right\|_{2}<\lambda}\right\}$, and $Df^{-1}(x)=(Df(x))^{-1}$ on this set.

to denote the fact that $\left\|{\xi-\eta}\right\|_{\infty}\leq O(1/n)$.

for some sequence $\varepsilon_{k}=o_{k}(1)$ that tends to $0$ sufficiently slowly.

The random variable

Our goal is to make the second moment method work for a random variable that counts “asymmetric” satisfying assignments. In this section, we develop this random variable. The starting point, and the key ingredient, is simply a map $p:\mathbf{Z}\rightarrow\left[{0,1}\right]$. For the sake of clarity, we start by setting up the framework for generic maps $p$; below we will use the Belief Propagation formalism to pick the “optimal” $p$.

The idea is that $p$ prescribes how strongly the assignments that we work with lean toward the majority vote. Informally speaking, we are going to work with assignments such that a variable $x$ that occurs $d_{x}$ times positively and $d_{\neg x}$ times negatively has a $p(d_{x}-d_{\neg x})$ chance of being set to ‘true’. Before we give a formal definition, we need to fix the number of times that each variable appears positively or negatively.

Fixing the majority weight. As we saw in Section 2, in order to make the second moment argument work, we need to rule out fluctuations of the majority weight. To achieve this, we follow the strategy outlined in Section 2. That is, we are going to work with formulas \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 a given vector \mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}=(d_{x},d_{\neg x})_{x\in V} of occurrence counts, where each variable $x$ appears precisely $d_{x}$ times positively and $d_{\neg x}$ times negatively. As in Section 2, we let $\textstyle D$ denote the (conditional Poisson) distribution over sequences $\textstyle d$ such that 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}}} is equivalent to choosing a $k$-CNF $\textstyle\Phi$ uniformly at random.

Fixing the marginals. Now, fix one such vector $\textstyle d$. Then the map $p:\mathbf{Z}\rightarrow\left[{0,1}\right]$ induces a map p_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}} from the set $L=\left\{{x,\neg x:x\in V}\right\}$ of literals to $\left[{0,1}\right]$ in the natural way: we let

The idea is that, given $\textstyle d$, we should set variable $x$ to ‘true’ with probability p_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}(x).

To formalize this, we call p_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}(l) the p_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}-type of the literal $l$. Let \mathcal{T}=\mathcal{T}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}=\left\{{p_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}(l):l\in L}\right\} be the set of all possible p_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}-types. We say that $\sigma:V\rightarrow\left\{{0,1}\right\}$ has p_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}-marginals if for any type t\in\mathcal{T}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}} we have

i.e., among all occurrences of literals of type $t$, a $t$ fraction is true under $\sigma$. This definition captures the above idea that variable $x$ has a p_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}(x) chance of being ‘true’.

Given \mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}} there is a simple way of generating the random formula \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}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}}}. Namely, create $d_{l}$ clones of each literal $l$, and put all the clones of a given p_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}-type on a pile. Then the formula \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}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}}} is simply the result of matching the clones on the type $t$ pile randomly to all the clauses where a literal of type $t$ is required.

As in those papers, the problem admits a remarkably simple solution: let us call an assignment $\sigma$ good in \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}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}}} if

Together with Paley-Zygmund (5), Theorem 5.1 shows that with $\textstyle d$ chosen from $\textstyle D$ and $\textstyle m$ chosen from \mathchoice{\mbox{\boldmath\displaystyle M}}{\mbox{\boldmath\textstyle M}}{\mbox{\boldmath\scriptstyle M}}{\mbox{\boldmath\scriptscriptstyle M}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}} w.h.p.

Guessing the marginals. For a set $\emptyset\neq S\subset\left\{{0,1}\right\}^{V}$ and a variable $x$ we define the $S$-marginal of $x$ as

The definition of ‘p_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}-judicious’ is guided by the idea that p_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}(x) should prescribe the marginal of $x$ in the set of all p_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}-judicious satisfying assignments. Hence, in order to make the set of p_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}-judicious assignments as good an approximation of the entire set of satisfying assignments as possible, we better pick $p$ so that p_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}(x) is a good approximation to the actual marginal \mu_{\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}}})}(x) of $x$ in the set of all satisfying assignments. The problem is that, because of the asymmetry of the $k$-SAT problem, these marginals are highly non-trivial quantities. Indeed, on general formulas $\Phi$ the marginals $\mu_{\mathcal{S}(\Phi)}(x)$ are $\#P$-hard to compute.

We observe that (20) is in line with the notion that \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 “skewed toward” $\sigma_{maj}$. Indeed, the conjecture quantifies how much so. Motivated by Conjecture 5.2, we define

Under the distribution $\textstyle D$, the random variables $d_{x},d_{\neg x}$ are asymptotically independent Poisson with mean $kr/2$ (cf. Section 2). Therefore,

Belief Propagation actually leads to a stronger prediction than Conjecture 5.2. Namely, it yields a conjecture for \mu_{\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}}})}(x) up to an additive error then tends to $0$ as $n\rightarrow\infty$. However, (a) this stronger conjecture is not in explicit form, and (b) it does not only depend on $d_{x},d_{\neg x}$, but also on various other parameters. In any case, even a more accurate prediction would not yield a better constant than $\frac{3}{2}\ln 2$ in Theorem 1.1.

2 Typical degree sequences

We need to collect a few basic properties of the sequence $\textstyle d$ chosen from $\textstyle D$. Let us call a sequence \mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}=(d_{l})_{l\in L} of non-negative integers such that $\sum_{l\in L}d_{l}=km$ a signed degree sequence. For a $k$-CNF $\Phi$ let \mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}\left({\Phi}\right)=(d_{l}\left({\Phi}\right))_{l\in L} denote the vector whose entry $d_{l}\left({\Phi}\right)$ is equal to the number of times that literal $l$ occurrs in $\Phi$. Then \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) is just the distribution of the signed degree sequence \mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}).

Let $\textstyle d$ be a signed degree sequence. A $k$-CNF $\Phi$ over $V$ is $\textstyle d$-compatible if \mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}(\Phi)=\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}. Thus,

is a uniformly random $\textstyle d$-compatible $k$-CNF.

For $\textstyle d$ chosen from $\textstyle D$ the following statements hold w.h.p.

$\sum_{x\in V}(d_{x}-d_{\neg x})^{2}\sim km.$

Proof. We use the following description of the distribution $\textstyle D$. Let \mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}=(e_{l})_{l\in L} be a family of indepedent ${\rm Po}(kr/2)$ variables. Moreover, let ${\cal E}$ be the event that $\sum_{l\in L}e_{l}=km$. It is well known that $\textstyle e$ given ${\cal E}$ has distribution $\textstyle D$. Furthermore, a simple calculation based on Stirling’s formula yields

Furthermore, as $e_{x},e_{\neg x}$ are independent for any $x\in V$, we have

Because $\hat{e}_{l}\leq\ln^{2}n$ and the random variables $\left\{{(\hat{e}_{x}-\hat{e}_{\neg x})^{2}}\right\}_{x\in V}$ are mutually independent, Azuma’s inequality yields

thereby proving the first claim. The second claim follows from the first by means of the Cauchy-Schwarz inequality: w.h.p.

Finally, the third assertion is immediate from the second. $\Box$

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

Proof. We use the alternative description of $\textstyle D$ from the proof of Lemma 5.7. That is, \mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}=(e_{l})_{l\in L} is a family of indepedent ${\rm Po}(kr/2)$ variables, and ${\cal E}$ is the event that $\sum_{l\in L}e_{l}=km$. Let $\lambda=kr/2$. For any fixed set $S\subset L$ the random variable $X_{S}=\sum_{l\in S}e_{l}$ has distribution ${\rm Po}(|S|\lambda)$ (because the sum of two independent Poisson variables is Poisson). Therefore, letting $\mu=10|S|\max\left\{{kr,\ln(n/|S|)}\right\}$, we obtain from Stirling’s formula

For $1\leq s\leq 2n$ let X_{s}=\sum_{S:\left|{S}\right|=s}\mathchoice{\mbox{\boldmath\displaystyle 1}}{\mbox{\boldmath\textstyle 1}}{\mbox{\boldmath\scriptstyle 1}}{\mbox{\boldmath\scriptscriptstyle 1}}_{X_{S}>\mu}. Then (27) yields

because $\mu\geq 10s\ln(n/s)$. Thus, the first claim follows from (22) and the union bound.

To prove the second claim, we use Lemma 5.6. For $S\subset L$ we let $Y_{S}$ be the total number of occurrences of literals from $S$ in $\textstyle\Phi$. Then $Y_{S}$ has distribution ${\rm Bin}(km,|S|/2n)$ with mean $|S|kr/2$. By the Chernoff bound,

Hence, letting Y_{s}=\sum_{S:|S|=s}\mathchoice{\mbox{\boldmath\displaystyle 1}}{\mbox{\boldmath\textstyle 1}}{\mbox{\boldmath\scriptstyle 1}}{\mbox{\boldmath\scriptscriptstyle 1}}_{Y_{S}<kr|S|/3}, we get from (28) for $s\geq n2^{-0.8k}$

For any $t\in\mathcal{T}$ we let $n(t)$ be the number of variables $x\in V$ such that p_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}(x)=t.

Let $\textstyle d$ be chosen from $\textstyle D$. Then w.h.p. for any type $t\in\mathcal{T}$ we have

Thus, the assertion follows by combining (22), (29) and (30). $\Box$

For each $t\in\mathcal{T}$ we let $\pi(t)$ denote the fraction of literal occurrences of $p$-type $t$, i.e.,

Since $\left|{\mathcal{L}}\right|=O(1)$ as $n\rightarrow\infty$ by the construction of $p$, the assertion follows from (31) and the union bound. $\Box$

The first moment

Let $\rho>\frac{3}{2}\ln 2$ be such that $r=2^{k}\ln 2-\rho$.

W.h.p. \mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}} are such that

Let $\chi(z)=-z\ln z-(1-z)\ln(1-z)$ denote the entropy function. Then w.h.p. $\textstyle d$ is such that

Taylor expanding $\chi(z)$ around $z=1/2$ and plugging in the definition (21) of $p$, we obtain that w.h.p. $\textstyle d$ is such that

As a next step, we compute the probability of \sigma\in\mathcal{S}_{p}(\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}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}}}) for \sigma\in\mathcal{H}_{p}(\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}).

W.h.p. $\textstyle d$, $\textstyle m$ are such that for any \sigma\in\mathcal{H}_{p}(\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}),

Let us defer the proof of Lemma 6.3, which is the core of the first moment computation, for a little while. Combining (32)–(34), we see that w.h.p. over the choice of \mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}} we have

W.h.p. over the choice of \mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}} we have

The proof of Lemma 6.4 is based on arguments developed in for analyzing the geometry of the set of satisfying assignments. Combining (35) and Lemma 6.4 yields Proposition 6.1.

2 Proof of Lemma 6.3

For any $\sigma\in\left\{{0,1}\right\}^{V}$ with $p$-marginals we have

The proof of Proposition 6.5 consists of two steps. We defer the proof of the following lemma to Section 6.3.

With the assumptions of Proposition 6.5 and with $\delta,\delta^{\prime}$ defined by

Proof of Proposition 6.5. Let $\Delta=100k2^{k}\ln k$ and let $\delta,\delta^{\prime}$ be as in Lemma 6.6. Using the alternative description of the distribution $\textstyle D$ from the proof of Lemma 5.7 and applying Azuma’s inequality, one can easily verify that w.h.p.

Similarly, invoking (36) once more, we see that w.h.p.

w.h.p. Thus, Proposition 6.5 is a direct consequence of Lemmas 5.9 and 6.6 and (37), (38). $\Box$

3 Proof of Lemma 6.6

We begin by determining the number $\sigma\in\left\{{0,1}\right\}^{V}$ with $p$-marginals. The following is an easy consequence of Lemma 6.2.

W.h.p. for $\textstyle d$ chosen from $\textstyle D$ we have

Proof. This follows from Lemma 6.2 by Taylor expanding $\chi(\cdot)$ around $\frac{1}{2}$. $\Box$

For any $\textstyle d$-compatible formula \Phi\in\Gamma_{\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}}} we can define a map

Proof. Since the total number $\left|{\mathcal{L}}\right|$ of clause types is bounded, the assertion follows from a repeated application of Lemma 4.1 (the local limit theorem). $\Box$

From this point on we fix $\textstyle q$ as in Lemma 6.12.

where we used the approximation $\ln(1+x)=x-\frac{1}{2}x^{2}+O(x^{3})$. Thus, Lemma 5.10 yields

In the second moment calculation we will need to know that

Let $\delta,\delta^{\prime}>0$ be such that

Proof of Lemma 6.6. Lemma 6.6 is a direct consequence of Corollaries 6.7, 6.9, 6.11 and 6.15. $\Box$

4 Proof of Lemma 6.4

Assume that $\textstyle m$ is feasible. Let $\mathcal{Z}$ denote the number of good $p$-satisfying assignments.

The proof of Proposition 6.16 is based on three lemmas.

Let $\textstyle d$ be chosen from $\textstyle D$ and let $\textstyle m$ be chosen from \mathchoice{\mbox{\boldmath\displaystyle M}}{\mbox{\boldmath\textstyle M}}{\mbox{\boldmath\scriptstyle M}}{\mbox{\boldmath\scriptscriptstyle M}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}.

Proof. This follows from a similar application of Markov’s inequality as in the proof of Lemma 5.6. $\Box$

With the assumptions of Proposition 6.16 the random variable

The proof of Lemma 6.18 can be found in Section 6.5. Moreover, in Section 6.6 we prove the following.

Suppose that $r\leq 2^{k}\ln 2$. Let $\xi=k2^{-k/2}$. Let $Z^{\prime\prime}$ be 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}})^{2} such that

Finally, Proposition 6.16 follows immediately from Lemmas 6.17, 6.18 and 6.19.

5 Proof of Lemma 6.18

Let $\Phi$ be a $k$-CNF and $\sigma\in\mathcal{S}(\Phi)$. We say that a variable $x$ is $\xi$-rigid in $(\Phi,\sigma)$ if for any $\tau\in\mathcal{S}(\Phi)$ with $\tau(x)\neq\sigma(x)$ we have $\mbox{dist}(\sigma,\tau)\geq\xi n$. Let $\lambda=kr/(2^{k}-1)$.

Proof. 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 the 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 12 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,\frac{1}{2}k^{12}2^{-k})$. Hence, the first assertion follows from Chernoff bounds.

Let us call a set $S\subset V$ self-contained if each variable in $S$ supports at least ten 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 12 clauses.

While there is a variable $x\in R$ that supports fewer than ten 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.

Proof. 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 12 clauses. By Lemma 6.20 we may condition on $|Q|\leq k^{12}2^{-k}n$. Assume that $|R|\leq(1-k^{15}/2^{k})n$. Then there exists a set $S\subset V\setminus(R\cup Q)$ of size $\frac{1}{2}k^{15}n/2^{k}\leq S\leq k^{15}n/2^{k}$ such that each variable in $S$ supports ten 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 us call a variable $x$ is attached if $x$ supports a clause whose other $k-1$ variables belong to $R$.

Proof. Let $F=V\setminus R$. By Proposition 6.21 we may assume that $|F|\leq nk^{15}/2^{k}$. Therefore, for each of the “special” clause $C_{x}$ that we reserved for each $x$ that supports at least one clause the probability of containing a variable from $F\setminus\left\{{x}\right\}$ is bounded by

Furthermore, these events are independent (because the clauses $C_{x}$ were disregarded in the construction of $R$). Hence, the number of variables $x\not\in R$ that support at least one clause but that are not attached is dominated by ${\rm Bin}(|F|,\frac{3k^{16}}{2^{k}})$. The assertion thus follows from Chernoff bounds. $\Box$

Let us call $S\subset V$ dense if each variable in $S$ supports at least ten clauses and at most $2k$ clauses such that at least ten of them feature another variable from $S$.

For $\textstyle d$ chosen from $\textstyle D$, $\textstyle m$ chosen from \mathchoice{\mbox{\boldmath\displaystyle M}}{\mbox{\boldmath\textstyle M}}{\mbox{\boldmath\scriptstyle M}}{\mbox{\boldmath\scriptscriptstyle M}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}} and any $\sigma\in\left\{{0,1}\right\}^{V}$ the following holds w.h.p. Let $\mathcal{A}$ be the event that $\sigma$ is a $p$-satisfying assignment 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}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}}}. Then

Due to negative correlation, in total we obtain

(The factor ${{2k}\choose{10}}^{|S|}$ accounts for the number of ways to choose $10$ out of the at most $2k$ clauses that each variable in $S$ supports.)

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

There are two cases to consider. First, if $s\leq\ln(n)/n$, then the term in the brackets is clearly $o(1)$. Second, if $s\geq\ln(n)/n$, then we have the following bound. Since $s\leq s_{\max}=2^{-0.99k}$ and as $x\mapsto x^{9}\ln^{10}x$ is monotonically increasing for $x<0.1$, we have

Hence, the entire bracket is bounded by $2^{-k/2}$. Summing over all possible $s$ and using Markov’s inequality completes the proof. $\Box$

Let us call a variable $x\in V$ $\xi$-rigid in $\sigma\in\mathcal{S}(\Phi)$ if for any $\tau\in\mathcal{S}(\Phi)$ with $\tau(x)\neq\sigma(x)$ we have $\mbox{dist}(\sigma,\tau)\geq\xi n$.

W.h.p. for $\textstyle d$ chosen from $\textstyle D$ and for $\textstyle m$ chosen from \mathchoice{\mbox{\boldmath\displaystyle M}}{\mbox{\boldmath\textstyle M}}{\mbox{\boldmath\scriptstyle M}}{\mbox{\boldmath\scriptscriptstyle M}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}} the following is true. Let $\sigma\in\left\{{0,1}\right\}^{V}$ and let $\mathcal{A}$ be the event that $\sigma$ is a $p$-satisfying assignment 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}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}}}. Moreover, let $Y$ be the number of variables that are not $2^{-0.99k}$-rigid. Then

Proof. Let $\xi=2^{-0.99k}$. We condition on the event $\mathcal{A}$. Consider a variable $z$ that is either attached or in $R$. Let \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}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}}}) be such that $\tau(z)\neq\sigma(x)$ and $\mbox{dist}(\sigma,\tau)<n/2^{0.99k}$. Because $z$ is attached or in $R$, the set

is non-empty. Moreover, $\Delta$ is dense by the construction of $R$. Thus, Lemma 6.23 shows that $\mbox{dist}(\sigma,\tau)\geq\left|{\Delta}\right|\geq n/2^{0.99k}$ w.h.p. Hence, w.h.p. all $z$ that are either attached or in $R$ are $\xi$-rigid.

Further, let ${\mathcal{R}}$ be the event that

no more than $(1+1/k^{2})2^{-k}n$ variables support no clause at all and

at most $n/(k^{2}2^{k})$ variables $x\not\in R$ that support at least one clause are not attached

Then Lemma 6.20 and Corollary 6.22 imply together with Proposition 6.5 that

Hence, the total number of vertices that either do not support a clause or that are not attached is bounded by $(1+2/k^{2})2^{-k}n$ $\Box$

Proof of Lemma 6.18. Suppose that $r=2^{k}\ln 2-c$. By Proposition 6.5 we have

w.h.p. Now, assume that in \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}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}}}) all but at most $(1+2k^{-2})2^{-k}n$ variables are $\xi$-rigid with $\xi=2^{-0.99k}$. If \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}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}}}) is such that $\mbox{dist}(\sigma,\tau)\leq\xi n$, then $\sigma,\tau$ agree on all $\xi$-rigid variables of $\sigma$. Hence,

As $c-\frac{\ln 2}{2}+o_{k}(1)>(1+o_{k}(1))\ln 2$ for $c>\frac{3}{2}\ln 2+\varepsilon$ and $k$ large enough, the assertion follows. $\Box$

6 Proof of Lemma 6.19

By Markov’s inequality, it suffices to bound the expected number of paris (\sigma,\tau)\in\mathcal{S}(\mathchoice{\mbox{\boldmath\displaystyle\Phi}}{\mbox{\boldmath\textstyle\Phi}}{\mbox{\boldmath\scriptstyle\Phi}}{\mbox{\boldmath\scriptscriptstyle\Phi}}) at the given Hamming distances. More precisely, let $\mathcal{Z}_{x}$ be 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}}) such that $\mbox{dist}(\sigma,\tau)/n=x$. Let $h(x)=-x\ln x-(1-x)\ln(1-x)$ and set

If $k2^{-k}\leq x\leq k^{-2}$, then $1-\ln x-k+k^{2}x\leq 1-\ln k+1<0$. Moreover, if $k^{-2}\leq x\leq(2k)^{-1}$, then $1-\ln x-k+k^{2}x\leq 1+2\ln k-\frac{3}{4}k<0$.

The last expression is negative for $x<0.05$ (and $k$ not too small).

Hence, for $0.01\leq x<\frac{1}{2}-k^{-2}$ we have $h^{\prime}(x)+q^{\prime}(x)>0$. Thus, $h(x)+q(x)+\ln 2$ is monotonically increasing in this interval. Now, let $x=\frac{1}{2}-\varepsilon$ for $k^{-2}\leq\varepsilon\leq k2^{-k/2}$. Then

The function $h(x)$ satisfies $h(1-y)=h(y)$ for $0<y<1/2$. Furthermore, $q(x)$ is monotonically decreasing. Therefore, for any $x\geq\frac{1}{2}+k2^{-k/2}$ we have

In each case we have $\ln 2+h(x)+q(x)<0$. Thus, the assertion follows from (47) and Markov’s inequality.

The second moment

The overlap of two assignments $\sigma,\tau\in\left\{{0,1}\right\}^{V}$ is the vector

In words, $\mathcal{O}(\sigma,\tau)$ captures the fraction of occurrences of literals of each type $t$ that are true under both $\sigma,\tau$. Since \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 independent and have $p$-marginals, we have

Set $\mathcal{O}^{*}=\left[{t^{2}}\right]_{t\in\mathcal{T}}$.

Let $Z^{\prime\prime}$ be the number of pairs $(\sigma,\tau)$ of p_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}-judicious satisfying assignments 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}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}}} such that

Moreover, let $Z^{\prime}$ be the number of pairs $(\sigma,\tau)$ of p_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}}-judicious satisfying assignments 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}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}}} such that

The proof of Proposition 7.1 can be found in Section 7.2. Let $Z$ denote the number of $p$-satisfying assignments 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}}}. Furthermore, let $\mathcal{Z}$ signify the number of good $p$-satisfying assignments 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}}}. In Section 8 we are going to establish the following.

Proof. Let $Y$ be the number of pairs $(\sigma,\tau)$ of good $p$-satisfying assignments 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}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}}} such that

Combining (50) with Proposition 7.1 and 7.2, we obtain for $\textstyle d$ chosen from $\textstyle D$ w.h.p.

The second part of Theorem 5.1 follows directly from Corollary 7.3.

2 Proof of Proposition 7.1

We begin by relating the overlap to the Hamming distance.

W.h.p. \mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}} are such that for all pairs $\sigma,\tau\in\left\{{0,1}\right\}^{V}$ satisfying (48) we have

W.h.p. \mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}} are such that for any $\sigma,\tau\in\left\{{0,1}\right\}^{V}$ that satisfy (48) and that have $p$-marginals we have

Let (\hat{\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}},\hat{\mathchoice{\mbox{\boldmath\displaystyle\tau}}{\mbox{\boldmath\textstyle\tau}}{\mbox{\boldmath\scriptstyle\tau}}{\mbox{\boldmath\scriptscriptstyle\tau}}}) denote a random pair chosen from this distribution.

Proposition 6.5 and Lemma 7.4 ensure that w.h.p. $\textstyle d$ is such that

In addition, let $S$ be the event that \max_{j\in\left[{k}\right]}\hat{\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}}_{ij}=\max_{j\in\left[{k}\right]}\hat{\mathchoice{\mbox{\boldmath\displaystyle\tau}}{\mbox{\boldmath\textstyle\tau}}{\mbox{\boldmath\scriptstyle\tau}}{\mbox{\boldmath\scriptscriptstyle\tau}}}_{ij} for all $i\in\left[{m}\right]$. We claim that

Indeed, any $d$-compatible formula $\Phi$ induces a pair $(\hat{\sigma}|_{\Phi},\hat{\tau}|_{\Phi})\in\hat{\Omega}$ defined by $\hat{\sigma}_{ij}|_{\Phi}=\sigma(\Phi_{ij})$, $\hat{\tau}_{ij}|_{\Phi}=\tau(\Phi_{ij})$. Clearly, the distribution of the random pair (\hat{\sigma}|_{\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}}}},\hat{\tau}|_{\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 identical to the distribution of (\hat{\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}},\hat{\mathchoice{\mbox{\boldmath\displaystyle\tau}}{\mbox{\boldmath\textstyle\tau}}{\mbox{\boldmath\scriptstyle\tau}}{\mbox{\boldmath\scriptscriptstyle\tau}}}) given $B$.

Due to independence, the probability of the event $S$ is easy to compute. Indeed, with $q=q^{10}+q^{11}$ inclusion/exclusion yields

Using (52) and simplifying completes the proof. $\Box$

Let $\lambda>2^{-k}$ and $t\in\mathcal{T}$. For $\textstyle d$ chosen from $\textstyle D$ the following is true w.h.p. Let $\mathcal{H}^{\prime\prime}$ be the set of all pairs $\sigma,\tau\in\left\{{0,1}\right\}^{V}$ such that $|\mathcal{O}_{t}(\sigma,\tau)-1/4|>\lambda.$ Then

If $\sigma^{\prime},\tau^{\prime\prime},\sigma^{\prime\prime},\tau^{\prime\prime}\in\left\{{0,1}\right\}^{V}$ are such that there is a literal $l_{0}$ with $\mathcal{T}(l_{0})=t$ such that $\sigma^{\prime\prime}(l)=\sigma^{\prime}(l),\tau^{\prime\prime}(l)=\tau^{\prime}(l)$ for all $l\not\in\left\{{l_{0},\neg l_{0}}\right\}$, then

Therefore, by Azuma’s inequality for any $\lambda>0$ we have

where the last step follows from part 2 of Proposition 6.5. $\Box$

Proof of Proposition 7.1. Let $H^{\prime\prime}$ be the set of pairs $(\sigma,\tau)$ such that

$\sigma,\tau$ satisfy (48) and have $p$-marginals, and

$\left\|{\mathcal{O}(\sigma,\tau)-\mathcal{O}^{*}}\right\|_{\infty}>\xi$.

Then by Lemma 7.6 and the second part of Proposition 6.5 w.h.p. (over the choice of $\textstyle d$) we have

Furthermore, by Lemma 7.5 w.h.p. (again over the choice of $\textstyle d$) we have

Combining (54) and (55), we obtain that w.h.p. $\textstyle d$ is such that

Therefore, the definition of the distribution \mathchoice{\mbox{\boldmath\displaystyle M}}{\mbox{\boldmath\textstyle M}}{\mbox{\boldmath\scriptstyle M}}{\mbox{\boldmath\scriptscriptstyle M}}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}} entails that w.h.p. $\textstyle d$ is such that

Thus, the assertion follows from Markov’s inequality. $\Box$

Proof of Proposition 7.2

We keep the notation and the assumptions of Section 7.

For two assignments $\sigma,\tau$ and a formula $\Phi$ with signed degree distribution $\textstyle d$ we define a matrix

In Section 9 we are going to prove the following.

For any assignment $\sigma$ with $p$-marginals we have

Recall that $\mathcal{O}^{*}=(t^{2})_{t\in\mathcal{T}}$. In Section 8.3 we will prove the following.

W.h.p. \mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}} are such that the following holds. For any $\mathcal{O}=(\mathcal{O}_{t})_{t\in\mathcal{T}}$ such that \left\|{\mathcal{O}-\frac{1}{4}\mathchoice{\mbox{\boldmath\displaystyle 1}}{\mbox{\boldmath\textstyle 1}}{\mbox{\boldmath\scriptstyle 1}}{\mbox{\boldmath\scriptscriptstyle 1}}}\right\|_{\infty}\leq 2\xi we have

In Section 8.4 we will show the following.

There exists a constant $\eta>0$ such that w.h.p. \mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}} are such that the following holds. For all $\mathcal{O}$ with \left\|{\mathcal{O}-\frac{1}{4}\mathchoice{\mbox{\boldmath\displaystyle 1}}{\mbox{\boldmath\textstyle 1}}{\mbox{\boldmath\scriptstyle 1}}{\mbox{\boldmath\scriptscriptstyle 1}}}\right\|_{\infty}\leq 2\xi we have

Recall that $n(t)$ is the number of variables of type $t\in\mathcal{T}$. In Section 10 we are going to prove the following.

W.h.p. \mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}},\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}} are such that the following holds. For all vectors $\lambda=(\lambda_{t})_{t\in\mathcal{T}}$ with $\left\|{\lambda}\right\|_{\infty}\leq 1/8$ we have

Proof of Proposition 7.2. Suppose that $\mathcal{O}\in\left[{0,1}\right]^{\mathcal{T}}$ satisfies $\left\|{\mathcal{O}-\mathcal{O}^{*}}\right\|_{\infty}\leq\xi$. By Proposition 8.4 w.h.p.

For an assignment $\sigma$ with $p$-marginals let

Then by part 3 of Proposition 8.1, Corollary 8.4 and Corollary 6.9 we have

For a vector $\lambda=(\lambda_{t})_{t\in\mathcal{T}}$ let

Moreover, for $c=c(k)>0$ a sufficiently large number let $\Lambda=\frac{c}{\sqrt{n}}\mathbf{Z}_{\geq 0}^{\mathcal{T}}$ be the positive $\mathcal{T}$-dimensional grid scaled by a factor of $c/\sqrt{n}$. In addition, let $h$ be the number of assignments $\sigma$ with $p$-marginals. Then by Proposition 8.5 and (59) there is a number $\zeta=\zeta(k)>0$ such that

It will be convenient to work with a different probability space. Namely, let $\hat{\Omega}$ be the set of all pairs $(\hat{\sigma},\hat{\tau})$ of $0/1$ vectors

2 Proof of Proposition 8.2

the remaining entries of $\textstyle q$ are determined by (60)–(62). Then the following is immediate from the construction.

The last step follows from the local limit theorem for the multinomial distribution because

3 Proof of Corollary 8.3

observe that $\bar{P}$ depends on $\mathcal{O}$ but not on the specific choice of $\omega$. Then by Propositions 8.1 and 8.2

Summing over all possible overlap matrices $\omega$ of assignments with $p$-marginals, we get

4 Proof of Proposition 8.4

We claim that there exist numbers $0<c_{k}<c_{k}^{\prime}$ (independent of $\omega$) such that w.h.p. $\textstyle d$ is such that

Once more, the conditional probability that this random variable equals its expectation lies in $\left[{c_{k,3}n^{-1/2},c_{k,4}n^{-1/2}}\right]$ for certain $c_{k,4}>c_{k,3}>0$. Hence, setting $c_{k}=c_{k,1}c_{k,3}$ and $c_{k}^{\prime}=c_{k,2}c_{k,4}$, we obtain (63).

Proof of Proposition 8.1

We keep the notation and the assumptions of Section 7.

In Section 9.2 we will establish the following.

For any $\omega$ in the domain of $\mathcal{P}$ we have

Proof. This follows directly from Propositions 9.2 and 9.3 and Taylor’s formula. $\Box$

Finally, in Section 9.6 we will show of Proposition 8.1 follows from Proposition 9.1 and Corollary 9.4.

2 Proof of Proposition 9.1

There exists a vector $\textstyle q$ such that

Proof. This follows from applying the inverse function theorem in a similar way as in the proof of Lemma 6.10. $\Box$

In the rest of this section, we fix $\textstyle q$ as in Lemma 9.9.

By inclusion/exclusion, we obtain from (70) and (71) that

Due to (70) and (72), a repeated application of Lemma 4.1 (the local limit theorem) yields

Invoking Lemma 9.8 and using the large deviations principle for the binomial distribution (Lemma 4.2), we can easily determine the unconditional probability of $B^{\prime}\cap C^{\prime}$: we have

Finally, Proposition 9.1 follows from Fact 9.6 and Lemma 9.10.

3 Proof of Proposition 9.2

Proof. Equation (73) from the proof of Lemma 9.10 shows that

Furthermore, applying Azuma’s inequality just as in the previous paragraph, we find that

Let $H(\omega)$ be the number of pairs $(\hat{\sigma},\hat{\tau})\in\hat{\Omega}$ such $(\hat{\sigma},\hat{\tau})\in B^{\prime}$ and \hat{\mathchoice{\mbox{\boldmath\displaystyle\omega}}{\mbox{\boldmath\textstyle\omega}}{\mbox{\boldmath\scriptstyle\omega}}{\mbox{\boldmath\scriptscriptstyle\omega}}}(\hat{\sigma},\hat{\tau})=\omega. We claim that

This can be verified either by representing $H(\omega)$ as a product of binomial coefficients and applying Stirlings formula or, alternatively, by using (75). Indeed, assume that (81) is false. Then for small enough $\varepsilon>0$ there is $\delta>0$ such that for some $\omega^{\prime}$ with $\left\|{\omega^{\prime}-\omega^{*}}\right\|_{\infty}\sim\varepsilon$ we have

(with both $\varepsilon,\delta$ possibly dependent on $k$ but not on $n$). Letting

which is a contradiction. Hence, (81) follows.

with $\varepsilon,\delta$ independent of $n$. Let

4 Proof of Proposition 9.3

for all $i,j,h\in\left[{k}\right]$. Therefore, the assertion follows from Lemma 4.3 (the chain rule) and Lemma 9.12. $\Box$

Let $\varepsilon>0$. We say that $\Psi\in C^{2}((0,1)^{2},\mathbf{R})$ is $\varepsilon$-tame on $\mathcal{Y}\subset(0,1)^{2}$ if the following conditions hold:

For all $y\in(0,1)$ we have $\Psi(y,y)=0$.

On $\mathcal{Y}$ we have $\left|{\sum_{i=1}^{2}\frac{\partial^{2}\Psi}{\partial z_{i}\partial z_{j}}}\right|\leq\varepsilon$ for any $j=1,2$.

On $\mathcal{Y}$ we have $\left|{\sum_{i,j=1}^{2}\frac{\partial^{2}\Psi}{\partial z_{i}\partial z_{j}}}\right|\leq\varepsilon^{2}$.

On $\mathcal{Y}$ we have $|\frac{\partial^{2}\Psi}{\partial z_{i}\partial z_{j}}|\leq 100$ for any $i,j=1,2$.

Let $f:(0,1)^{k}\rightarrow\mathbf{R}^{2}$, $(z_{1},\ldots,z_{k})\mapsto(f_{1}(z_{1},\ldots,z_{k}),f_{2}(z_{1},\ldots,z_{k}))$ be a $C^{2}$-function. We say that $f$ is $\varepsilon$-benign on $\mathcal{W}$ if the following statements are true on $\mathcal{W}$:

$\left|{\frac{\partial f_{1}}{\partial z_{1}}-\frac{\partial f_{2}}{\partial z_{1}}}\right|<\varepsilon$.

$\left|{\frac{\partial f_{i}}{\partial z_{j}}}\right|<\varepsilon$ for any $1<j\leq k$ and $i=1,2$ and $\left|{\frac{\partial f_{i}}{\partial z_{1}}}\right|\leq 100$.

$\left|{\frac{\partial^{2}f_{i}}{\partial z_{h}\partial z_{j}}}\right|<\varepsilon$ for any $i$ and $(h,j)\neq(1,1)$.

$\left|{\frac{\partial^{2}f_{1}}{\partial z_{1}^{2}}-\frac{\partial^{2}f_{2}}{\partial z_{1}^{2}}}\right|<\varepsilon$ and $|\frac{\partial^{2}f_{1}}{\partial z_{1}^{2}}|\leq 100$.

There is an absolute constant $C>0$ such that the following is true. Assume that $f$ is $\varepsilon$-benign on $\mathcal{W}$ and that $\Psi$ is $\varepsilon$-tame on $f(\mathcal{W})$. Then on $\mathcal{W}$ we have