The Fraction of Satisfiable Clauses in a Typical Formula

Dimitris Achlioptas^{∗} Microsoft Research, Redmond, Washington

                        optas@microsoft.com

Assaf Naor Microsoft Research, Redmond, Washington

                        anaor@microsoft.com

Yuval Peres^{†}

Departments of Statistics and Mathematics, University of California, Berkeley

                      peres@stat.berkeley.edu

Abstract

Given n Boolean variables x_{1}, …, x_{n}, a k-clause is a disjunction of k literals, where a literal is a variable or its negation. A k-CNF formula is a conjunction of a finite number of k-clauses. Call such a formula p-satisfiable if there exists a truth assignment satisfying a fraction 1−2^{−k}+p 2^{−k} of all clauses and observe that every k-CNF formula is 0-satisfiable. Our goal is to determine for which ratios of clauses to variables, a typical k-CNF formula is p-satisfiable. Let F_{k}(n, m) denote a formula on n variables formed by selecting uniformly and independently m out of all (2n)^{k} possible k-clauses on x_{1}, …, x_{n}. Given p ∈ (0, 1], let r_{k}(p) be the supremum of all r such that the probability that F_{k}(n, rn) is p-satisfiable tends to 1 as n → ∞. Similarly, let r_{k}^{∗}(p) be the infimum of all r such that the probability that F_{k}(n, rn) is p-satisfiable tends to 0 as n → ∞. It is widely believed that r_{k}(p) = r_{k}^{∗}(p) for every p ∈ (0, 1] and k ≥ 2. We prove that this is true asymptotically in k. More precisely, we prove that for every p ∈ (0, 1], both r_{k}(p) and r_{k}^{∗}(p), when divided by 2^{k}, tend exponentially fast to log 2/[p + (1 − p) log(1 − p)] as k → ∞. As a corollary, for every k ≥ 2 and r > 2^{k} log 2 we give p = p(k, r) such that with probability tending to 1 as n → ∞, F_{k}(n, rn) is p-satisfiable but not (p + δ)-satisfiable, where δ = δ(k) = O(k2^{−k/2}). The proof is based on a delicate asymptotic analysis of a random bivariate generating function.

1 Introduction

This work is devoted to the asymptotic resolution of the maximum satisfiability threshold problem, a problem which originated in theoretical computer science in the early 1970s and has since been studied by mathematicians and statistical physicists due to its connections to spin glasses. Our solution is based on delicate analytic and probabilistic techniques, whereas previous rigorous results on the problem were algorithmic.

Definition 1. Given n Boolean variables x_{1}, …, x_{n}, a clause is a disjunction of literals, where a literal is a variable or its negation. A CNF formula F (CNF stands for conjunctive normal form) is the conjunction of finitely many clauses. When all clauses have k literals F is called a k-CNF formula.

Given a CNF formula F, the Satisfiability problem asks whether there exists a truth assignment under which F evaluates to true. In his seminal 1971 paper [7], Cook proved that Satisfiability is complete for the complexity class NP, i.e., that it is at least as hard as any decision problem for which positive answers can be verified in polynomial time. Cook also proved that Satisfiability remains NP-complete when the input is restricted to be a k-CNF formula, where k ≥ 3, and this version of the problem (known as k-SAT) has since been the canonical problem of computational complexity.

∗Part of this work was done while visiting UC Berkeley.

†Research supported by NSF Grant DMS-0104073 and a Miller Professorship at UC Berkeley.

Given a k-CNF formula F, a natural generalization of k-SAT is to ask whether there exists a truth assignment satisfying at least a certain number of clauses of F (rather than all of them). This problem is known as Max k-SAT and it is NP-complete for k ≥ 2 (see [13]). Observe that if a k-CNF formula has m clauses, the average over all 2^{n} truth assignments of the number of satisfied clauses is precisely (1 − 2^{−k})m. In particular, one can always produce a truth assignment satisfying all but 2^{−k}m clauses, e.g. by iteratively satisfying any literal that appears in the largest number of yet unsatisfied clauses. We will say that F is p-satisfiable, where p ∈ [0, 1], if there exists a truth assignment satisfying 1 − 2^{−k} + p 2^{−k} of all clauses.

A recent deep theorem of Håstad [14] states that, in general, the above algorithm is best possible: any polynomial-time algorithm that can distinguish between ε-satisfiable formulas and 1-satisfiable formulas, can be used to solve the original satisfiability problem in polynomial time. This suggests that in the worst case (over the choice of formulas), even approximating the maximum fraction of satisfiable clauses in a k-CNF formula is an extremely hard problem.

In this paper we study the maximum fraction of satisfiable clauses in typical k-CNF formulas, i.e., formulas chosen uniformly at random among all k-CNF formulas with a given number of variables and clauses. Our main result establishes that for such formulas the maximum fraction of satisfiable clauses can be determined with very high accuracy. The study of optimization problems with random inputs is pervasive in operations research (e.g., the travelling salesman problem and variants – see the recent special issue of TCS [11] and the references therein), in statistical physics (determining ground states of spin glasses – see for example Talagrand’s recent book [19]) and in computer science.

Let F_{k}(n, m) denote a random formula on n variables formed by selecting uniformly and independently m out of all (2n)^{k} possible k-clauses on x_{1}, …, x_{n}. When dealing with random k-CNF formulas^{1} we say that a sequence of random events E_{n} occurs with high probability (w.h.p.) if lim_{n→∞} P[E_{n}] = 1 and with uniformly positive probability if lim inf_{n→∞} P[E_{n}] > 0. We emphasize that throughout the paper k is arbitrarily large but fixed, while n → ∞. We introduce the following parameters for every k ≥ 2 and p ∈ (0, 1]:

r_{k}(p) ≡ sup{r : F_{k}(n, rn) is p-satisfiable w.h.p.}
≤ inf{r : F_{k}(n, rn) is not p-satisfiable w.h.p.} ≡ r_{k}^{∗}(p) .

One of the most intriguing aspects of random formulas is the Satisfiability Threshold Conjecture asserting that r_{k}(1) = r_{k}^{∗}(1) for every k ≥ 3. Much work has been done to bound r_{k}(1) and r_{k}^{∗}(1). Currently, the best rigorous bounds for general k ≥ 3, from [2, 10] respectively, are: 2^{k} log 2 − O(k) < r_{k} ≤ r_{k}^{∗} < 2^{k} log 2 − O(1). For all p < 1, though, the ratio of the previously known upper bound for r_{k}^{∗}(p) and the lower bound for r_{k}(p) tended to infinity with k.

The state of the art for general k was presented in an important recent paper by Coppersmith, Gamarnik, Hajiaghayi, and Sorkin [6], where it was proved that there exists an absolute constant c > 0 such that for all k and all p ∈ (0, p_{0}(k)],

\frac{2^{k+1} log 2}{ckp^{2}} < r_{k}(p) ≤ r_{k}^{∗}(p) < \frac{2^{k+1} log 2}{p^{2}} .  (1)

For small k the two bounds in (1) are reasonably close, but the ratio between them grows linearly in k; this naturally raises the question which bound is closer to the truth. Our main result resolves this question by pinpointing the values of r_{k}(p) and r_{k}^{∗}(p) with relative error that tends to zero exponentially fast in k. For every p ∈ (0, 1) denote

T_{k}(p) = \frac{2^{k} log 2}{p + (1 − p) log(1 − p)} ,  (2)

and let T_{k}(1) = 2^{k} log 2 so that T_{k}(·) is continuous on (0, 1].

Theorem 1. There exists a sequence δ_{k} = O(k2^{−k/2}), such that for all k ≥ 2 and p ∈ (0, 1],

(1 − δ_{k}) T_{k}(p) < r_{k}(p) ≤ r_{k}^{∗}(p) < T_{k}(p) .  (3)

Theorem 1 readily implies the following.

1Our results hold in all common models for random k-CNF, e.g. when literal replacement is not allowed; see Section 3.

Corollary 1. For k ≥ 2 and r > 2^{k} log 2, let p_{c}(k, r) be the supremum over all p such that w.h.p. F_{k}(n, rn) is p-satisfiable. Let Ψ be the inverse of the function f(p) = p + (1 − p) log(1 − p). Then

Ψ (\frac{2^{k} log 2}{r}) (1 − δ_{k}) ≤ p_{c}(k, r) ≤ Ψ (\frac{2^{k} log 2}{r}) ,

where δ_{k} = O(k2^{−k/2}) is the same as in Theorem 1.

Proof. Denote s = Ψ (\frac{2^{k} log 2}{r}). We have r = T_{k}(s) > r_{k}^{∗}(s) and, therefore, w.h.p. F_{k}(n, rn) is not s-

satisfiable. If p ≤ s(1 − δ_{k}), then \frac{2^{k} log 2}{r} = f(s) ≥ f(p/(1 − δ_{k})) > f(p)/(1 − δ_{k}), where the second inequality follows from the convexity of f. Thus, r < T_{k}(p)(1 − δ_{k}) < r_{k}(p), implying that w.h.p. F_{k}(n, rn) is p-satisfiable.

The upper bound in (3) follows from well-known tail estimates. Taylor expansion gives that as p → 0,

T_{k}(p) = \frac{2^{k} log 2}{p^{2}/2 + O(p^{3})} ,

so for p → 0 we can sharpen (1) to

(1 − δ_{k})\frac{2^{k+1} log 2}{p^{2} + O(p^{3})} ≤ r_{k}(p) ≤ r_{k}^{∗}(p) ≤ \frac{2^{k+1} log 2}{p^{2} + O(p^{3})} .  (4)

Our proof of Theorem 1 actually yields an explicit lower bound for r_{k}(p) for each k ≥ 2. For k = 2, i.e., Max 2-SAT, the algorithm presented in [6] dominates our lower bound uniformly, i.e., for every value of p, it yields a better lower bound for r_{2}(p). Already for k ≥ 3, though, our methods yield a better bound. The following plots indicate that even for relatively small k, our bounds are quite tight:

k = 3  k = 4

k = 7  k = 10

Figure 1. Bounds for r_{k}^{∗} and r_{k} as functions of q = 1 − p.

The proof of Theorem 1 is based on a delicate application of the second moment method. The second moment method is a natural approach to many probabilistic and combinatorial problems, and we refer to Janson’s survey article [16] for a presentation of this method and a useful conditional variant. For certain problems, a direct application of the second moment method fails due to high correlations, yet once the source of correlations is recognized, a suitable truncation or weighting can control it. Multiscale truncation was used in the solution of the Erdős-Taylor (1960) conjecture on simple random walk in the planar square lattice (see [12], [9]) and a weighting scheme motivated by entropy maximization was the key to the work of the first and third authors on random k-SAT [2].

In the present paper, in order to deal with correlations we study a random bivariate generating function that weights truth assignments according to the fraction of satisfied clauses and the fraction of satisfied literal occurrences. This approach builds upon insights from both [9] and [2], yet obtaining tight bounds in the presence of an additional parameter (the fraction of satisfied clauses) presents new analytic challenges. The crucial new ingredient is a truncation that allows us to adapt the weight assigned to each pair of assignments to their overlap. We emphasize that for Max k-SAT this adaptation is necessary even for determining the first order asymptotics (see Section 2.2). In general, it is notoriously difficult to obtain precise asymptotics from such random multivariate generating functions; for random Max k-SAT this is possible due to the surprising cancellation of four terms of equal magnitude in our analysis. This cancellation hints at the existence of some unexpected hidden structure in random Max k-SAT.

2 Locating the p-satisfiability threshold via moment estimates

The upper bound in Theorem 1 follows readily by applying Markov’s inequality to the number of p-satisfying truth assignments (see Section 3.1). While for any fixed value of k one can get a slightly better upper bound for r_{k}^{∗}(p) by employing a more refined counting argument, such as that of Janson, Stamatiou and Vamvakari [15], it is remarkable that the naive first moment bound is asymptotically tight.

For a random formula F_{k}(n, m), denote by s_{k}(n, m) the random variable equal to the maximum (over all truth assignments σ) of the number of clauses satisfied by σ. The first rigorous study of random Max k-SAT appeared in the work of Broder, Frieze and Upfal [4] where it was shown that s_{k}(n, m) is sharply concentrated around its mean. Specifically,

Theorem 2 ([4]). P[|s_{k}(n, m) − 𝔼[s_{k}(n, m)]| > t] < 2 exp (−\frac{2t^{2}}{m} ).

In proving the lower bound of Theorem 1, we will use the following corollary of Theorem 2:

Corollary 2. Assume that there exists c = c(k, p, r) such that for n large enough F_{k}(n, rn) is p-satisfiable with probability greater that n^{−c}. Then F_{k}(n, rn) is p′-satisfiable w.h.p. for every constant p′ < p.

Proof. Let S ≡ (1 − 2^{−k} + p2^{−k})rn. Then 𝔼[s_{k}(n, rn)] > S − n^{2/3}, since otherwise Theorem 2 would imply that the probability of p-satisfiability is less than 2e^{−2r^{−1}n^{1/3}}, contradicting our assumption. By the same token, P[s_{k}(n, rn) < S − 2n^{2/3}] = o(1).

Thus to establish the lower bound in (3) we will find for every p ∈ (0, 1] a value r = r(p) such that F_{k}(n, rn) is p-satisfiable with probability Ω(1/n) and rely on Corollary 2 to get a corresponding high probability result. A natural way of bounding probabilities from below is the second moment method, which is based on the following easy consequence of the Cauchy-Schwartz inequality:

Lemma 1. For any non-negative random variable X,

P[X > 0] ≥ \frac{𝔼[X]^{2}}{𝔼[X^{2}]} .  (5)

2.1 Why the standard second moment method fails

A natural way to apply Corollary 2 and Lemma 1 is the following: for any fixed p ∈ (0, 1] one can let X denote the number of p-satisfying assignments and apply (5) to bound P[X > 0] from below. Unfortunately, it turns out that for all k, p, r > 0 there exists a constant β = β(k, p, r) > 0 such that 𝔼[X^{2}] > (1 + β)^{n}𝔼[X]^{2}. As a result, this straightforward approach only gives a trivial lower bound on the probability of p-satisfiability. As shown in [2] for the case p = 1, a major factor in the excessive correlations behind the above failure is that p-satisfying truth assignments tend to lean toward the majority vote truth assignment. To see this, first observe that truth assignments that satisfy more literal occurrences than the average number km/2, have higher probability of being p-satisfying. Yet, in order to satisfy many literal occurrences, such assignments tend to agree with each other (and the majority truth assignment) on more than half the variables. As a result, the successes of such assignments tend to be highly correlated and dominate 𝔼[X^{2}].

2.2 A bivariate weighting scheme

An attractive feature of the second moment method is that we are free to apply it to any random variable X such that X > 0 implies p-satisfiability. Hence, in order to avoid the above pitfall, we would like to apply the second moment method to truth assignments that satisfy, approximately, half of all literal occurrences; we call such truth assignments “balanced”.

In what follows we fix p ∈ (0, 1] and k ≥ 2. We will denote by F = F_{k}(n, m) a random k-CNF formula on n variables with m = rn clauses. For any truth assignment σ ∈ {0, 1}^{n} let

1. H = H(σ, F) be the number of satisfied literal occurrences in F under σ, minus the number of unsatisfied literal occurrences in F under σ.

2. U = U(σ, F) be the number of unsatisfied clauses in F under σ.

We would like to focus on truth assignments that are balanced and p-satisfying, up to fluctuations one would expect from the central limit theorem, i.e., truth assignments σ such that for some constant A > 0,

|H(σ, F)| ≤ A\sqrt{m}  (6)
|U(σ, F) − (1 − p)2^{−k}m| ≤ A\sqrt{m} .  (7)

To do this let us fix 0 < γ, η < 1 and define X(γ, η) as

X(γ, η) = ∑_{σ} γ^{H(σ,F)}η^{U(σ,F)−u_{0}m} ,  (8)

where, and this is a hard-coded definition with inconsistent but convenient notation.

u_{0} = \frac{1 − p}{2^{k}} .  (9)

Since γ, η < 1 we see that in X(γ, η) the truth assignments σ for which H(σ, F) > 0 or U(σ, F) > u_{0}m are suppressed exponentially, while the rest are rewarded exponentially. Decreasing γ, η ∈ [0, 1) makes this phenomenon more and more acute, with the limiting case γ, η = 0 corresponding to a 0-1 weighting scheme (we adopt the convention 0^{0} ≡ 1). Indeed, applying the second moment method to X(γ, η) with η = 0 corresponds to the approach of [2] for the random k-SAT threshold, where only satisfying assignments receive non-zero weight γ^{H(σ,F)}. Unfortunately, when attempting to apply the second moment method to X(γ, η) with η > 0 we immediately encounter two problems.

The first, less serious, problem is that while X(γ, η) > 0 implies satisfiability when η = 0, having X(γ, η) > 0 does not imply p-satisfiability when η > 0: in principle, X(γ, η) could be positive due to the contribution of assignments falsifying many more clauses than u_{0}m. This necessitates restricting the sum defining X(γ, η) to truth assignments falsifying at most u_{0}m + O(\sqrt{m}) clauses, i.e., truncating X(γ, η). Specifically, for some fixed A > 0 let

S^{∗} = \{σ ∈ \{0, 1\}^{n} : H(σ, F) ≥ 0 and U(σ, F) ∈ [u_{0}m, u_{0}m + A\sqrt{m}]\} .

Correspondingly, we define a truncated version of X(γ, η) as

X_{∗}(γ, η) = ∑_{σ∈S^{∗}} γ^{H(σ,F)}η^{U(σ,F)−u_{0}m} .  (10)

By definition, when X_{∗}(γ, η) > 0 at least one truth assignment must falsify at most u_{0}m + A\sqrt{m} clauses. Thus, if we prove that there exists a constant D > 0 (which may depend on k, p but not on n) such that

𝔼X_{∗}(γ, η)^{2} < Dn · [𝔼X_{∗}(γ, η)]^{2}  (11)

then Corollary 2 will imply that F_{k}(n, m) is w.h.p. p′-satisfiable for all p′ < p.

The second, more severe, problem is that 𝔼X_{∗}(γ, η)^{2} becomes exponentially greater than [𝔼X_{∗}(γ, η)]^{2} when r is only, roughly, half the lower bound of Theorem 1. To overcome this difficulty we proceed as follows. Fix γ, η > 0 and note that

𝔼[X_{∗}(γ, η)]^{2} = 𝔼 [(∑_{σ} γ^{H(σ,F)}η^{U(σ,F)−u_{0}m} 1_{{σ∈S^{∗}}})^{2}]

= ∑_{σ,τ} 𝔼 [γ^{H(σ,F)+H(τ,F)}η^{U(σ,F)+U(τ,F)−2u_{0}m} 1_{{σ,τ∈S^{∗}}}] .  (12)

Now, since σ ∈ S^{∗} implies H(σ, F) ≥ 0 and U(σ, F) ≥ u_{0}m, we get that for every pair σ, τ and any γ̃ ≥ γ and η̃ ≥ η,

𝔼 [γ^{H(σ,F)+H(τ,F)}η^{U(σ,F)+U(τ,F)−2u_{0}m} 1_{{σ,τ∈S^{∗}}}] ≤ 𝔼 [γ̃^{H(σ,F)+H(τ,F)}η̃^{U(σ,F)+U(τ,F)−2u_{0}m} 1_{{σ,τ∈S^{∗}}}]
≤ 𝔼 [γ̃^{H(σ,F)+H(τ,F)}η̃^{U(σ,F)+U(τ,F)−2u_{0}m}] .  (13)

In other words, when using the right hand side of (13) to bound each term of the sum in (12), we are allowed to adapt the value of γ̃ and η̃ to the pair σ, τ, the only restrictions being γ̃ ≥ γ and η̃ ≥ η. This is a crucial point and we will exploit it heavily when bounding the contribution of pairs σ, τ which agree on many variables. The resulting adaptive weighting scheme leads to an extremely delicate asymptotic analysis in the proof of (11).

3 Probabilistic Preliminaries

Relationship to other k-CNF models: Recall that the m clauses of F_{k}(n, m) are chosen independently with replacement among all (2n)^{k} possibilities. Thus, the m clauses {c_{i}}_{i=1}^{m} are i.i.d. random variables, each c_{i} being the conjunction of k i.i.d. random variables {ℓ_{ij}}_{j=1}^{k}, each ℓ_{ij} being a uniformly random literal. This viewpoint of the formula as a sequence of km i.i.d. random literals will be very handy for our calculations.

Clearly, in this model some clauses might be improper, i.e., they might contain repeated and/or contradictory literals. Nevertheless, observe that the probability that any given clause is improper is smaller than k^{2}/n and, moreover, that the proper clauses are uniformly selected among all such clauses. Therefore, w.h.p. the number of improper clauses is o(n) implying that if for a given r, F_{k}(n, m = rn) is p-satisfiable w.h.p. then for m = rn − o(n), the same is true in the model where we only select among proper clauses. The issue of selecting clauses without replacement is completely analogous as w.h.p. there are o(n) clauses that contain the same k variables as some other clause.

3.1 The upper bound

As remarked in the Introduction, the upper bound in (3) can be readily derived from the entropic-form Chernoff bound for the binomial distribution (see Lemma A.10 in [3] or Lemma 3.8 in [8]). Nevertheless, in deriving the lower bound of Theorem 1 it will be informative to have a self-contained proof of the upper bound.

Define for α, γ, η ∈ [0, 1],

f(α, γ, η)

= η^{−2u_{0}} [(α (\frac{γ^{2} + γ^{−2}}{2} ) + 1 − α)^{k} − 2(1 − η) (\frac{αγ^{−2} + (1 − α)}{2})^{k} + (1 − η)^{2} (\frac{αγ^{−2}}{2} )^{k}] , (14)

where u_{0} is as in (9). Additionally, let

g_{r}(α, γ, η) = \frac{f(α, γ, η)^{r}}{α^{α}(1 − α)^{1−α}} .  (15)

Lemma 2. For X(γ, η) as in (8) with m = rn, for every 0 < γ, η < 1,

𝔼X(γ, η) = \frac{2^{n}}{η^{u_{0}m}} [(\frac{γ + γ^{−1}}{2} )^{k} − \frac{1 − η}{(2γ)^{k}} ]^{m} = [2g_{r} (\frac{1}{2}, γ, η)]^{n/2} .  (16)

Proof. The second equality in (16) follows directly from the definitions of f, g_{r}. Write F = c_{1} ∧ ⋯ ∧ c_{m}, where the c_{i}’s are k-clauses. Observe that for every truth assignment σ, H(σ, F) = ∑_{i=1}^{rn} H(σ, c_{i}), and similarly for U(σ, F). Since c_{1}, ..., c_{rn} are i.i.d. it follows that if c denotes a random clause

η^{u_{0}m}𝔼X(γ, η) = 2^{n} [𝔼 (γ^{H(σ,c)}η^{U(σ,c)})]^{m} .

Observe that U(σ, c) = 1 when c is violated by σ, i.e., with probability 2^{−k}; otherwise U(σ, c) = 0. Writing c = ℓ_{1} ∨ ⋯ ∨ ℓ_{k}, where ℓ_{1}, …, ℓ_{k} are i.i.d. uniformly distributed literals, it follows that:

𝔼 [γ^{H(σ,c)}η^{U(σ,c)}] = 𝔼γ^{H(σ,c)} − 𝔼 [γ^{H(σ,c)} (1 − η^{U(σ,c)})]
= [𝔼γ^{H(σ,ℓ_{1})}]^{k} − \frac{1 − η}{2^{k}γ^{k}}

= (\frac{γ + γ^{−1}}{2} )^{k} − \frac{1 − η}{2^{k}γ^{k}}
= f(1/2, γ, η) .  (17)

Lemma 3. For all k ≥ 2 and p ∈ (0, 1], if q = 1 − p then

r_{k}^{∗}(p) ≤ \frac{2^{k} log 2}{q log q − (2^{k} − q) log (\frac{2^{k}−1}{2^{k}−q})} < T_{k}(p) ,  (18)

where T_{k}(·) was defined in (2).

Proof. The right hand inequality of (18) follows from the inequality log t ≤ t − 1 applied to t = \frac{2^{k}−1}{2^{k}−q}, so we just need to verify the left hand inequality. Recall that u_{0} = 2^{−k}q. Let η ∈ (0, 1), and observe that if F is p-satisfiable, then U(σ, F) ≤ u_{0}m for some σ, whence

X(1, η) = ∑_{σ} η^{U(σ,F)−u_{0}m} ≥ 1 .

By Lemma 2 we have

P[X(1, η) ≥ 1] ≤ 𝔼[X(1, η)] = 2^{n}η^{−qrn2^{−k}}(1 − (1 − η)2^{−k})^{rn} .  (19)

Thus, the probability of p-satisfiability decays exponentially in n if the the n-th root of the RHS of (19) is strictly smaller than 1. Taking η = q(2^{k} − 1)/(2^{k} − q) yields the lemma.

3.2 The Lower Bound: Groundwork

Our first order of business is to show that for an appropriate choice of γ and η, the truncation replacing X(γ, η) by X_{∗}(γ, η) does not reduce the expectation by more than a constant factor. The idea behind the proof below is motivated by Cramer’s classical “change of measure” technique in large deviation theory.

Lemma 4. Given u_{0} ∈ (0, 2^{−k}), let γ_{0}, η_{0} satisfy

1 − η_{0} = (1 − γ_{0}^{2})(1 + γ_{0}^{2})^{k−1}  and  u_{0} = \frac{η_{0}}{(1 + γ_{0}^{2})^{k} − (1 − η_{0})} .  (20)

There exists θ = θ(k, γ_{0}, A) > 0 such that as n → ∞,

\frac{𝔼X_{∗}(γ_{0}, η_{0})}{𝔼X(γ_{0}, η_{0})} → θ .

Remark. Since the function γ ↦ \frac{1−(1−γ^{2})(1+γ^{2})^{k−1}}{(1+γ^{2})^{k}−(1−γ^{2})(1+γ^{2})^{k−1}} maps (0, 1) onto (0, 2^{−k}), the existence of γ_{0}, η_{0} ∈ (0, 1) satisfying (20) is guaranteed. Moreover, η_{0}, γ_{0} are uniquely defined, but this fact will not be used.

Proof. It suffices to prove that there exists some θ = θ(k, γ_{0}, A) > 0 such that for the values of γ_{0}, η_{0} satisfying (20) and every truth assignment σ, we have

\frac{𝔼 [γ_{0}^{H(σ,F)}η_{0}^{U(σ,F)}1_{\{σ∈S^{∗}(F)\}}]}{𝔼 [γ_{0}^{H(σ,F)}η_{0}^{U(σ,F)}]} → θ .  (21)

Fix a truth assignment σ and consider an auxiliary distribution P_{σ} on k-CNF formulas where the clauses c_{1}, …, c_{m} are again i.i.d. among all (2n)^{k} possible k-clauses, but where now for any fixed clause ω

P_{σ}(c_{i} = ω) = \frac{1}{(2n)^{k}} · \frac{γ_{0}^{H(σ,ω)}η_{0}^{U(σ,ω)}}{Z(γ_{0}, η_{0})} ,  (22)

where

Z(γ_{0}, η_{0}) = \frac{1}{(2n)^{k}} ∑_{c} γ_{0}^{H(σ,c)}η_{0}^{U(σ,c)} = 𝔼 [γ_{0}^{H(σ,c)}η_{0}^{U(σ,c)}] = f(1/2, γ_{0}, η_{0}) .  (23)

Let 𝔼_{σ} be the expectation operator corresponding to P_{σ}. A calculation similar to that leading to (17), adding the equal contributions from the k literals, gives that for a single random clause c

Z(γ_{0}, η_{0})𝔼_{σ}[H(σ, c)] = k \frac{γ_{0} − γ_{0}^{−1}}{2} (\frac{γ_{0} + γ_{0}^{−1}}{2} )^{k−1} + \frac{k(1 − η_{0})}{(2γ_{0})^{k}} .  (24)

Moreover,

Z(γ_{0}, η_{0})𝔼_{σ}[U(σ, c)] = (2γ_{0})^{−k}η_{0} .  (25)

Thus, the first equation in (20) along with (24) ensure that 𝔼_{σ}[H(σ, c)] = 0, while the second equation in (20) along with (23),(25) ensure that 𝔼_{σ}[U(σ, c)] = u_{0}.

Next, we apply the multivariate central limit theorem (see, e.g. [17], page 182) to the i.i.d. mean-zero random vectors (H(σ, c_{i}), U(σ, c_{i}) − u_{0}) for i = 1, …, m. Observe that, since k ≥ 2, the common law of these random vectors is not supported on a line. We deduce that as n → ∞,

P_{σ}[σ ∈ S^{∗}(F)] = P_{σ}[H(σ, F) ≥ 0 and U(σ, F) ∈ [mu_{0}, mu_{0} + A\sqrt{m}]] → θ(k, γ_{0}, A) > 0 .

Here, the right hand side is the probability that a certain non-degenerate bivariate normal law assigns to a certain open set. Its exact value is unimportant for our purpose. By (22), this is equivalent to (21).

The next lemma bounds the second moment of X_{∗}(γ_{0}, η_{0}) from above:

Lemma 5. Let γ(z), η(z) be arbitrary sequences such that γ(z) ≥ γ_{0} and η(z) ≥ η_{0} for every 0 ≤ z ≤ n. Then, for every u_{0},

𝔼[X_{∗}(γ_{0}, η_{0})]^{2} ≤ 2^{n} ∑_{z=0}^{n} \binom{n}{z}f (\frac{z}{n}, γ(z), η(z))^{rn} ≤ (n + 1) · [2 · max_{0≤z≤n} g_{r} (\frac{z}{n}, γ(z), η(z))]^{n} ,  (26)

where g_{r} is as in (15).

Proof. Fix γ, η > 0. For any pair of truth assignments σ, τ we first observe that since the m clauses c_{1}, c_{2}, …, c_{m} are i.i.d., letting c be a single random clause we have

𝔼 [γ^{H(σ,F)+H(τ,F)}η^{U(σ,F)+U(τ,F)}] = 𝔼 [∏_{i=1}^{m} γ^{H(σ,c_{i})+H(τ,c_{i})}η^{U(σ,c_{i})+U(τ,c_{i})}]

= ∏_{i=1}^{m} 𝔼 [γ^{H(σ,c_{i})+H(τ,c_{i})}η^{U(σ,c_{i})+U(τ,c_{i})}]

= (𝔼 [γ^{H(σ,c)+H(τ,c)}η^{U(σ,c)+U(τ,c)}])^{m} .  (27)

Next, we observe that for every pair σ, τ, by symmetry, the expectation in (27) depends only on the number of variables to which σ, τ assign the same value. So, let σ, τ be any pair of truth assignments that agree on exactly z = αn variables, i.e., have overlap z. By first rewriting γ^{H}η^{U} as γ^{H} + γ^{H}(η^{U} − 1) and then observing that η^{U(τ,c)} is distributed identically with η^{U(σ,c)} we get

𝔼[γ^{H(σ,c)}η^{H(σ,c)}γ^{H(τ,c)}η^{H(τ,c)}]

= 𝔼[(γ^{H(σ,c)} − γ^{H(σ,c)} (1 − η^{U(σ,c)}))(γ^{H(τ,c)} − γ^{H(τ,c)} (1 − η^{U(τ,c)}))]

= 𝔼[γ^{H(σ,c)+H(τ,c)}] − 2 𝔼[γ^{H(σ,c)+H(τ,c)} (1 − η^{U(σ,c)})] + 𝔼[γ^{H(σ,c)+H(τ,c)} (1 − η^{U(σ,c)}) (1 − η^{U(τ,c)})]

= 𝔼 [γ^{H(σ,c)+H(τ,c)}] − 2(1 − η)𝔼 [γ^{H(σ,c)+H(τ,c)}1_{\{σ violates c\}}] + \frac{α^{k}(1 − η)^{2}}{2^{k}γ^{2k}} .  (28)

To evaluate (28) we note that since the literals ℓ_{1}, ℓ_{2}, … ℓ_{k} comprising c are i.i.d. we have

𝔼 [γ^{H(σ,c)+H(τ,c)}] = 𝔼 [∏_{i} γ^{H(σ,ℓ_{i})+H(τ,ℓ_{i})}] = ∏_{i} 𝔼 [γ^{H(σ,ℓ_{i})+H(τ,ℓ_{i})}] = (α (\frac{γ^{2} + γ^{−2}}{2} ) + 1 − α)^{k} (29)

and, similarly,

𝔼 [γ^{H(σ,c)+H(τ,c)}1_{\{σ violates c\}}] = 𝔼 [∏_{i} γ^{H(σ,ℓ_{i})+H(τ,ℓ_{i})}1_{\{σ violates ℓ_{i}\}}] = (\frac{αγ^{−2} + (1 − α)}{2})^{k} . (30)

Substituting (29), (30) into (28) we get

η^{−2u_{0}} 𝔼 [γ^{H(σ,c)}η^{H(σ,c)}γ^{H(τ,c)}η^{H(τ,c)}]

= η^{−2u_{0}} [(α (\frac{γ^{2} + γ^{−2}}{2} ) + 1 − α)^{k} − 2(1 − η) (\frac{αγ^{−2} + (1 − α)}{2})^{k} + (1 − η)^{2} (\frac{αγ^{−2}}{2} )^{k}]

= f(α, γ, η) .  (31)

Since the number of ordered pairs with overlap z is 2^{n} \binom{n}{z}, using the reasoning in (12) and (13), we get

𝔼 X_{∗}(γ_{0}, η_{0})^{2} ≤ 2^{n} ∑_{z=0}^{n} \binom{n}{z}f (\frac{z}{n}, γ(z), η(z))^{m} ,  (32)

for any set of choices for γ(z), η(z) such that γ(z) ≥ γ_{0} and η(z) ≥ η_{0} for all 0 ≤ z ≤ n.

The final inequality in (26) follows from the fact that for all n > 1 and z = 0, 1, …, n Stirling’s formula implies that \binom{n}{z} ≤ [τ(z/n)]^{n}, where τ(α) = α^{−α}(1 − α)^{α−1} (see e.g. [1], eq. (18)) .

The following corollary is a direct consequence of Lemmata 2, 4 and 5.

Corollary 3. Let χ : [0, 1] → [γ_{0}, 1) and ω : [0, 1] → [η_{0}, 1) be arbitrary functions satisfying χ(1/2) = γ_{0}, ω(1/2) = η_{0}, and let g_{r}(α) = g_{r}(α, χ(α), ω(α)). Assume that g_{r}(α) ≤ g_{r}(1/2) for all α ∈ [0, 1]. Then there exists a constant D = D_{χ,ω}(k, r, p) > 0 such that for all sufficiently large n

𝔼[X_{∗}(γ_{0}, η_{0})^{2}] ≤ Dn · [𝔼X_{∗}(γ_{0}, η_{0})]^{2}.

Therefore, in order to prove Theorem 1 it is enough to show that for every p ∈ (0, 1] and r = (1−δ_{k})T_{k}(p), there exist functions χ, ω for which the conditions of Corollary 3 hold. To simplify the analysis, we use the crudest possible such functions, paying the price of this simplicity in the value of the constant C in Proposition 6 below. We note that by choosing a more refined (and more cumbersome) adaptation of γ, η to α this value can be improved greatly. Moreover, we emphasize that for any fixed value of k, one can get a sharper lower bound for r_{k}(p) by partitioning [0, 1] to a large number of intervals and numerically finding a good value of γ, η for each one. Indeed, the bounds reported in the plots in the Introduction are the result of such optimization. (We discuss this point further in Section 5).

Recall that q = 1 − p = u_{0}2^{k}. We define φ : [0, 1) → [1/2, 1) as

φ(q) = \frac{(1 − \sqrt{q})^{2}}{1 − q + q log q} .  (33)

Theorem 1 will follow from the following proposition.

Proposition 6. Let g_{r}(α, γ, η) be as in (15) and define

G_{r}(α) = \{ \begin{matrix}g_{r}(α, γ_{0}, η_{0}) & if α ∈ [\frac{3 log k}{k} , 1 − \frac{3 log k}{k} ] \\ g_{r}(α, \sqrt{γ_{0}}, \sqrt{η_{0}}) & otherwise. \end{matrix}  (34)

There exists a universal constant C > 0 such that if r ≤ \frac{2^{k} log 2}{1−q+q log q} (1 − Ck2^{−kφ(q)}), then for all α ∈ [0, 1], G_{r}(α) ≤ G_{r}(1/2).

The proof of Proposition 6 is presented in the following section. We remark that using the Laplace method from asymptotic analysis (see [5, §4.2] or Lemma 2 in [1]), a slight modification of the arguments below shows that the factor of n in Corollary 3 can be removed. However, this is immaterial for our purpose.

4 Asymptotic Analysis

We begin by observing that to prove Proposition 6 it suffices to consider α ∈ (1/2, 1].

Lemma 7. For every 0 < x ≤ \frac{1}{2}, G_{r}(1/2 + x) > G_{r}(1/2 − x).

Proof. Since the function α ↦ α^{α}(1−α)^{1−α} is symmetric around 1/2, it suffices to prove that for x ∈ (0, 1/2]

f (\frac{1}{2} + x, γ, η) > f (\frac{1}{2} − x, γ, η) .  (35)

Substituting α = 1/2 + x in (14) and denoting ε = 1 − γ^{2} we get that for all x ∈ [−1/2, 1/2]

η^{y/2^{k−1}}2^{2k}γ^{2k}f (\frac{1}{2} + x, γ, η) = [2xε^{2} + (2 − ε)^{2}]^{k} − 2 [2xε + (2 − ε)]^{k}(1 − η) + (1 − η)^{2}(1 + 2x)^{k}

= ∑_{j=0}^{k} \binom{k}{j}2^{j}x^{j}[ε^{2j}(2 − ε)^{2(k−j)} − 2(1 − η)ε^{j}(2 − ε)^{k−j} + (1 − η)^{2}]

= ∑_{j=0}^{k} \binom{k}{j}2^{j}x^{j}[ε^{j}(2 − ε)^{k−j} − (1 − η)]^{2}.  (36)

Thus, f(1/2 + x, γ, η) − f(1/2 − x, γ, η) = ∑_{j=1}^{⌈k/2⌉} a_{j}x^{2j−1}, where at most one of the a_{j}’s is zero.

Before proceeding with the rest of the proof, we introduce some notation, and prove some elementary estimates that will be used throughout the remainder of this section.

Recalling the definition of η_{0} from (20) and substituting into the definition of f from (14) we get

f(α, γ_{0}, η_{0}) = η_{0}^{−q/2^{k−1}}

· [(1 − α + α\frac{γ_{0}^{2} + γ_{0}^{−2}}{2} )^{k} − 2 (1 − γ_{0}^{2})(1 + γ_{0}^{2})^{k−1} (\frac{αγ_{0}^{−2} + 1 − α}{2})^{k} + \frac{α^{k}(1 − γ_{0}^{2})^{2}(1 + γ_{0}^{2})^{2k−2}}{2^{k}γ_{0}^{2k}} ] .

For some parts of the ensuing calculations, it will be convenient to use the following normalizations of f(α, γ_{0}, η_{0}) and g_{r}(α, γ_{0}, η_{0}) denoted as f_{0} and g_{0}, respectively,

f_{0}(α) = 2^{2k}γ_{0}^{2k}η_{0}^{q/2^{k−1}}f(α, γ_{0}, η_{0}) and g_{0}(α) = 2^{2kr}γ_{0}^{2kr}η_{0}^{qr/2^{k−1}}g_{r}(α, γ_{0}, η_{0}).  (37)

We will also write ε_{0} = 1−γ_{0}^{2}. With this notation, we have the following formula valid for all x ∈ [−1/2, 1/2]

f_{0} (\frac{1}{2} + x) = [2xε_{0}^{2} + (2 − ε_{0})^{2}]^{k} − 2ε_{0}(2 − ε_{0})^{k−1}[2 − ε_{0} + 2xε_{0}]^{k} + ε_{0}^{2}(2 − ε_{0})^{2k−2}(1 + 2x)^{k} . (38)

In particular,

f_{0} (\frac{1}{2}) = (2 − ε_{0})^{2k} − 2ε_{0}(2 − ε_{0})^{2k−1} + ε_{0}^{2}(2 − ε_{0})^{2k−2} = 4(1 − ε_{0})^{2}(2 − ε_{0})^{2k−2} .  (39)

The function y ↦ 1 − y + y log y, defined on [0, 1], appears throughout our analysis. The following elementary inequalities, valid for all y ∈ [0, 1], will be used

\frac{(1 − y)^{2}}{2} ≤ 1 − y + y log y ≤ (1 − y)^{2} .  (40)

Recalling that q = 1 − p and Equations (9), (20) we claim that

ε_{0} = \frac{2(1 − q)}{2^{k} − k − 1} + O (\frac{k(1 − q)^{2}}{2^{2k}} ) ,  (41)

and

η_{0} = q − \frac{(k + 1)(1 − q)}{2^{k} − k − 1} + O (\frac{k(1 − q)^{2}}{2^{k}} ) .  (42)

By the first equation in (20) we have that η_{0} = 1 − ε_{0}(2 − ε_{0})^{k−1}. Therefore, (42) is a consequence on (41). To prove (41) let

ψ(t) = ∑_{j=1}^{k−1} \frac{1}{(2 − t)^{j}} = \frac{(2 − t)^{k−1} − 1}{(1 − t)(2 − t)^{k−1}} .  (43)

Evidently, ψ is increasing, and for 0 ≤ t ≤ 1/k,

ψ(t) = 1 − \frac{1}{2^{k−1}} + t − \frac{(k + 1)t}{2^{k}} + O(t^{2}) .  (44)

Additionally, using the second equation in (20) we find that ψ(ε_{0}) = 1 − \frac{q}{2^{k−1}} . Since ψ is increasing, (41) will be proved once we show that for some constants c_{1}, c_{2},

ψ (\frac{2(1 − q)}{2^{k} − k − 1} + \frac{c_{1}(1 − q)^{2}}{2^{2k}} ) ≤ 1 − \frac{q}{2^{k−1}} ≤ ψ (\frac{2(1 − q)}{2^{k} − k − 1} + \frac{c_{2}(1 − q)^{2}}{2^{2k}} ) ,  (45)

and (45) is a straightforward consequence of (44).

The following lemma proves Proposition 6 in the first range of the definition of G_{r}.

Lemma 8. For all k ≥ k_{0}, if r ≤ \frac{2^{k} log 2}{1−q+q log q} then for α ∈ [\frac{1}{2}, 1 − \frac{3 log k}{k} ] we have G_{r}(α) ≤ G_{r}(1/2).

Proof. In this proof we use the normalization (37). It is enough to prove that g′_{0}(α) < 0 for \frac{1}{2} < α ≤ 1− \frac{3 log k}{k}. Now,

g′_{0}(α) = \frac{f_{0}(α)^{r−1}\{rf′_{0}(α) + f_{0}(α)[ log(1 − α) − log α]\}}{α^{α}(1 − α)^{1−α}} .  (46)

Differentiating (38) at x = 0 we find that

f′_{0} (\frac{1}{2}) = 2kε_{0}^{2}(2 − ε_{0})^{2k−2} − 4ε_{0}^{2}(2 − ε_{0})^{2k−2} + 2ε_{0}^{2}(2 − ε_{0})^{2k−2} = 0 .

Since, by (36), f_{0}(α) > 0 it is enough to show that the following function is decreasing on [\frac{1}{2}, 1 − \frac{3 log k}{k} ]

ζ(α) = rf′_{0}(α) + f_{0}(α)[log(1 − α) − log α] .

Now,

ζ′(α) = rf′′_{0}(α) + f′_{0}(α)[log(1 − α) − log α] − f_{0}(α) (\frac{1}{α} + \frac{1}{1 − α}) .

Since for 1/2 < α ≤ 1, log(1 − α) < log α and, by (36), f′_{0} > 0 on (1/2, 1], it is thus enough to prove that

rf′′_{0}(α) ≤ f_{0}(α) (\frac{1}{α} + \frac{1}{1 − α}) .

Now, \frac{1}{α} + \frac{1}{1−α} ≥ 4 and, using (39), we get that for α ≥ 1/2,

f_{0}(α) ≥ f_{0} (\frac{1}{2}) = 4(1 − ε_{0})^{2}(2 − ε_{0})^{2k−2} ≥ (2 − ε_{0})^{2k−2} ,

where for the last inequality we used that ε_{0} ≤ 1/2 for k large enough (by (41)). Thus, it suffices to prove that for all x ≤ 1/2 − \frac{3 log k}{k}

rf′′_{0} (\frac{1}{2} + x) ≤ 4(2 − ε_{0})^{2k−2} .  (47)

Now, using that x ≤ \frac{1}{2} − \frac{3 log k}{k}, we differentiate (38) twice to get

f′′_{0} (\frac{1}{2} + x)

= 4k(k − 1) {ε_{0}^{4}[2xε_{0}^{2} + (2 − ε_{0})^{2}]^{k−2} − 2ε_{0}^{3}(2 − ε_{0})^{k−1}[2 − ε_{0} + 2xε_{0}]^{k−2} + ε_{0}^{2}(2 − ε_{0})^{2k−2}(1 + 2x)^{k−2}}

≤ 4k^{2} \{ε_{0}^{4}(2 − ε_{0})^{2k−4} (1 + \frac{2xε_{0}^{2}}{(2 − ε_{0})^{2}} )^{k−2} + ε_{0}^{2}(2 − ε_{0})^{2k−2}(1 + 2x)^{k−2}\}

≤ 4k^{2} {ε_{0}^{4}(2 − ε_{0})^{2k−4} (1 + 2x)^{k−2} + ε_{0}^{2}(2 − ε_{0})^{2k−2}(1 + 2x)^{k−2}} ≤ 8k^{2}ε_{0}^{2}(2 − ε_{0})^{2k−2}(1 + 2x)^{k}

≤ 8k^{2}ε_{0}^{2}(2 − ε_{0})^{2k−2} [2 − \frac{6 log k}{k} ]^{k}

≤ 8k^{2}ε_{0}^{2}(2 − ε_{0})^{2k−2} \frac{2^{k}}{k^{3}}

≤ \frac{2^{k+3}}{k} (\frac{4(1 − q)}{2^{k}})^{2} (2 − ε_{0})^{2k−2} ,

where in the last line we used the fact that for k large enough (41) implies ε_{0} ≤ 4(1 − q)/2^{k}.

Combining this estimate with (47), we see that we must show that for sufficiently large k

\frac{128 log 2}{1 − q + q log q} · \frac{(1 − q)^{2}}{k} ≤ 4 ,

and this is indeed the case by (40).

It remains to prove that G_{r}(α) < G_{r}(1/2) for 1 − \frac{3 log k}{k} ≤ α ≤ 1. This inequality simplifies to:

[\frac{f(α, \sqrt{γ_{0}}, \sqrt{η_{0}})}{f(1/2, γ_{0}, η_{0})}]^{r} < 2α^{α}(1 − α)^{1−α} .  (48)

The following lemma gives an upper bound for the left-hand side of (48). Lemma 9. There exists a constant c > 0 such that for all sufficiently large k and α ∈ [1/2, 1],

\frac{f(α, \sqrt{γ_{0}}, \sqrt{η_{0}})}{f(1/2, γ_{0}, η_{0})} < q^{q/2^{k}} [1 + \frac{2\sqrt{q} − 2q + (1 − \sqrt{q})^{2}α^{k}}{2^{k}} + \frac{ck(1 − q)^{2}}{2^{2k}} ] .  (49)

Proof. Denote ε_{1} = 1 − (\sqrt{γ_{0}})^{2} = 1 − \sqrt{1 − ε_{0}} = \frac{ε_{0}}{2} + O(ε_{0}^{2}). Now,

η_{0}^{q/2^{k}}γ_{0}^{k}f (α, \sqrt{γ_{0}}, \sqrt{η_{0}}) = (1 − ε_{1} + \frac{αε_{1}^{2}}{2} )^{k} − \frac{2(1 − \sqrt{η_{0}})(1 − ε_{1}(1 − α))^{k} + (1 − \sqrt{η_{0}})^{2}α^{k}}{2^{k}}
= 1 − \frac{kε_{0}}{2} + \frac{k^{2}ε_{0}^{2}}{8} + O(kε_{0}^{2}) − \frac{2(1 − \sqrt{η_{0}}) + (1 − \sqrt{η_{0}})^{2}α^{k}}{2^{k}} + O (\frac{k(1 − \sqrt{η_{0}})ε_{0}}{2^{k}} )
= 1 − \frac{kε_{0}}{2} + \frac{k^{2}ε_{0}^{2}}{8} − \frac{2(1 − \sqrt{η_{0}}) + (1 − \sqrt{η_{0}})^{2}α^{k}}{2^{k}} + O (\frac{k(1 − q)^{2}}{2^{2k}} ) ,  (50)

where in (50) we have used (41) and (42). Observe now that q > η_{0} since

\frac{q}{2^{k}} = u_{0} = \frac{η_{0}}{(1 + γ_{0}^{2})^{k} − (1 − η_{0})} = \frac{η_{0}}{2^{k}(1 − ε_{0})(1 − ε_{0}/2)^{k−1}} > \frac{η_{0}}{2^{k}} ,

where for the second and third equalities we used, respectively, the definitions of u_{0} and η_{0} from (20). The fact q > η_{0} implies that for every α ∈ [0, 1],

(1 − \sqrt{η_{0}})^{2}α^{k} − 2(1 − \sqrt{η_{0}}) ≤ (1 − \sqrt{q})^{2}α^{k} − 2(1 − \sqrt{q}) + η_{0} − q ,  (51)

since the right-hand side minus the left-hand side of (51) equals (1 − α^{k}) ((2\sqrt{q} − q) − (2\sqrt{η_{0}} − η_{0})) > 0. Using (42) to bound η_{0} in the right hand side of (51) we conclude that

(1 − \sqrt{η_{0}})^{2}α^{k} − 2(1 − \sqrt{η_{0}}) ≤ (1 − \sqrt{q})^{2}α^{k} − 2(1 − \sqrt{q}) − \frac{(k + 1)(1 − q)}{2^{k} − k − 1} + O (\frac{k(1 − q)^{2}}{2^{k}} ) .

Substituting this estimate into (50), we get

η_{0}^{q/2^{k}}γ_{0}^{k}f (α, \sqrt{γ_{0}}, \sqrt{η_{0}})
= 1 − \frac{kε_{0}}{2} + \frac{k^{2}ε_{0}^{2}}{8} − \frac{2(1 − \sqrt{q}) − (1 − \sqrt{q})^{2}α^{k}}{2^{k}} − \frac{(k + 1)(1 − q)}{2^{k}(2^{k} − k − 1)} + O (\frac{k(1 − q)^{2}}{2^{2k}} ) .  (52)

Using the identity (39) we can rewrite the ratio in (48) as

\frac{f(α, \sqrt{γ_{0}}, \sqrt{η_{0}})}{f(1/2, γ_{0}, η_{0})} = \frac{η_{0}^{q/2^{k}}(1 − ε_{0})^{\frac{k}{2} −2}}{(1 − ε_{0}/2)^{2k−2}} · η_{0}^{q/2^{k}}γ_{0}^{k}f (α, \sqrt{γ_{0}}, \sqrt{η_{0}}) .  (53)

By (42)

η_{0}^{q/2^{k}} = q^{q/2^{k}} [1 − \frac{(k + 1)(1 − q)}{2^{k}(2^{k} − k − 1)} + O (\frac{k(1 − q)^{2}}{2^{2k}} )] .  (54)

Expanding around ε_{0} and using (41) we get

\frac{(1 − ε_{0})^{\frac{k}{2} −2}}{(1 − ε_{0}/2)^{2k−2}} =1 + (\frac{k}{2} + 1) ε_{0} + \frac{k^{2}}{8} ε_{0}^{2} + O(kε_{0}^{2}) = 1 + (\frac{k}{2} + 1) ε_{0} + \frac{k^{2}}{8} ε_{0}^{2} + O (\frac{k(1 − q)^{2}}{2^{2k}} ) . (55)

Direct substitution of (52),(54),(55) into (53) gives (56). Collecting terms, noting two cancellations and using (41) to bound the remaining terms involving ε_{0} gives (57)

\frac{f(α, \sqrt{γ_{0}}, \sqrt{η_{0}})}{f(1/2, γ_{0}, η_{0})} = q^{q/2^{k}} [1 − \frac{(k + 1)(1 − q)}{2^{k}(2^{k} − k − 1)} + O (\frac{k(1 − q)^{2}}{2^{2k}} )] ·
[1 + (\frac{k}{2} + 1) ε_{0} + \frac{k^{2}}{8} ε_{0}^{2} + O (\frac{k(1 − q)^{2}}{2^{2k}} )] ·  (56)

[1 − \frac{kε_{0}}{2} + \frac{k^{2}ε_{0}^{2}}{8} − \frac{2(1 − \sqrt{q}) − (1 − \sqrt{q})^{2}α^{k}}{2^{k}} − \frac{(k + 1)(1 − q)}{2^{k}(2^{k} − k − 1)} + O (\frac{k(1 − q)^{2}}{2^{2k}} )]

= q^{q/2^{k}} [1 + ε_{0} − \frac{2(k + 1)(1 − q)}{2^{k}(2^{k} − k − 1)} − \frac{2(1 − \sqrt{q}) − (1 − \sqrt{q})^{2}α^{k}}{2^{k}} + O (\frac{k(1 − q)^{2}}{2^{2k}} )] .(57)

Using (41) once more, (57) becomes

q^{q/2^{k}} [1 + \frac{2(1 − q)}{2^{k} − k − 1} − \frac{2(k + 1)(1 − q)}{2^{k}(2^{k} − k − 1)} − \frac{2(1 − \sqrt{q}) − (1 − \sqrt{q})^{2}α^{k}}{2^{k}} + O (\frac{k(1 − q)^{2}}{2^{2k}} )] .  (58)

Observe now that

\frac{2(1 − q)}{2^{k} − k − 1} − \frac{2(k + 1)(1 − q)}{2^{k}(2^{k} − k − 1)} − \frac{2(1 − \sqrt{q}) − (1 − \sqrt{q})^{2}α^{k}}{2^{k}} = \frac{2\sqrt{q} − 2q + (1 − \sqrt{q})^{2}α^{k}}{2^{k}}

which concludes the proof.

We are now in position to conclude the proof of Proposition 6.

Proof of Proposition 6. By (49), there is a constant c > 0 such that for α ∈ [1/2, 1]

\frac{f(α, \sqrt{γ_{0}}, \sqrt{η_{0}})}{f(1/2, γ_{0}, η_{0})} < q^{q/2^{k}} [1 + \frac{2\sqrt{q} − 2q + (1 − \sqrt{q})^{2}α^{k}}{2^{k}} + \frac{c k(1 − q)^{2}}{2^{2k}} ] .

Hence, to prove (48) it is enough to show that

\{q^{q/2^{k}} [1 + \frac{2\sqrt{q} − 2q + (1 − \sqrt{q})^{2}α^{k}}{2^{k}} + \frac{ck(1 − q)^{2}}{2^{2k}} ]\}^{r} < 2α^{α}(1 − α)^{1−α} .

Taking logarithms and using the inequality log(1 + x) ≤ x, this amounts to showing

\frac{r}{2^{k}} [q log q + 2\sqrt{q} − 2q + (1 − \sqrt{q})^{2}α^{k} + \frac{ck(1 − q)^{2}}{2^{k}} ] ≤ log 2 − h(α) ,  (59)

where h(α) = −α log α − (1 − α) log(1 − α).

To simplify notation let us define

A = (1 − \sqrt{q})^{2} and B = q log q + 2\sqrt{q} − 2q + \frac{ck(1 − q)^{2}}{2^{k}}  (60)

and observe that

\frac{A}{A + B} = φ(q)(1 + O(k2^{−k})) .  (61)

With this notation (59) becomes

\frac{r}{2^{k}} ≤ \frac{log 2 − h(α)}{Aα^{k} + B} ≡ M(α) ,  (62)

and this should hold for all α ≥ 1 − \frac{3 log k}{k}.

We need to determine the minimal value of M on the interval [1 − \frac{3 log k}{k} , 1]. The derivative of M is

M′(α) = \frac{(Aα^{k} + B) · [log α − log(1 − α)] − kAα^{k−1}[log 2 − h(α)]}{(Aα^{k} + B)^{2}} .  (63)

In particular, M′(1) = ∞, so M cannot be minimized at α = 1. Moreover, we claim that M(α) > M(1) for α ∈ [1 − \frac{3 log k}{k} , 2^{−1/k}]. To prove this observe that h(α) = o(1) since α ≥ 1 − \frac{3 log k}{k}. Since, also, α ≤ 2^{−1/k}

M (α) ≥ \frac{log 2 − o(1)}{A (2^{−1/k})^{k} + B} ≥ \frac{log 2 (1 − o(1))}{\frac{A}{2} + B} .

On the other hand, M(1) = log 2/(A + B). Thus, by (61), we have M(1)/M(α) → 1 − φ(q)/2. It remains to bound M(α) from below when α > 2^{−1/k} and M′(α) = 0. For such α, by (63), we have

− log(1 − α) = − log α + \frac{kAα^{k−1}}{Aα^{k} + B} [log 2 − h(α)] .  (64)

Since α > 2^{−1/k}, h(α) = o(1). Hence (64) implies that α ≥ 1 − e^{−k/8} since for k large enough we must have

− log(1 − α) ≥ \frac{kA}{2(A + B)} (log 2 − o(1)) > \frac{kφ(q)}{4} ≥ \frac{k}{8} .  (65)

Invoking (64) again, now starting with the premise α > 1 − e^{−k/8}, we get that for all sufficiently large k,

− log(1 − α) > kφ(q) log 2 (1 − e^{−k/9})  (66)

and, thus, α > 1 − exp(−kφ(q) log 2 (1 − e^{−k/9})). Since h(1 − e^{−z}) ≤ e^{−z}(1 + z) for all z ≥ 0 we get

h(α) ≤ k2^{−kφ(q)(1−e^{−k/9})} = O(k2^{−kφ(q)}) ,  (67)

where for the equality above we used that φ(q) ∈ [1/2, 1). Therefore,

M(α) = \frac{log 2 − h(α)}{Aα^{k} + B} ≥ \frac{log 2}{A + B} (1 − O (k2^{−kφ(q)})) ≥ \frac{log 2}{1 − q + q log q} (1 − O (k2^{−kφ(q)})) .

Hence the restriction on r in (62) becomes r ≤ \frac{2^{k} log 2}{1−q+q log q} (1 − O (k2^{−kφ(q)})), proving Proposition 6.

5 Bounds for Small values of k

As mentioned in Section 3, for small values of k the simple adaptation scheme of Proposition 6 does not yield the best possible lower bound for p-satisfiability afforded by our method. For that, one has to use a significantly more refined adaptation of γ, η with respect to α. Our lower bounds reported in Figure 1 are, indeed, the result of performing such optimization of γ, η numerically (For both the upper bound plots and the plots of the lower bound from [6] we used the explicit formulas.)

Specifically, to create the plots of the lower bounds we computed a lower bound for 100 equally spaced values of p on the horizontal axis and then had Maple’s [18] plotting function “connect the dots”. For each of these values of p, to prove the corresponding lower bound for r we had to establish that there exist a choice of functions χ, ω as in Lemma 3 such that for all α ∈ (1/2, 1] we have g_{r}(1/2, γ_{0}, η_{0}) > g_{r}(α, χ(α), ω(α)). To that end, we partitioned (1/2, 1] to 10,000 points and for each such point we searched for values of γ ≥ γ_{0} and η ≥ η_{0} such that this condition holds with a bit of room. (For k > 4 we solved (20), defining γ_{0} and η_{0}, numerically to 10 digits of accuracy. For the optimization we exploited convexity to speed up the search.) Having determined such values, we (implicitly) extended the functions χ, ω to all (1/2, 1] by assigning to every not-chosen point the value at the nearest chosen point. Finally, we computed a (crude) upper bound on the derivative of g_{r} with respect to α in (1/2, 1]. This bound on the derivative, along with our room factor, then implied that for every point that we did not check, the value of g_{r} was sufficiently close to its value at the corresponding chosen point to also be dominated by g_{r}(1/2, γ_{0}, η_{0}).

Acknowledgement

We thank Cris Moore for helpful conversations in the early stages of this work.

References

[1] Dimitris Achlioptas and Cristopher Moore, The asymptotic order of the random k-SAT threshold, 43th Annual Symposium on Foundations of Computer Science (Vancouver, BC, 2002), pp. 779–788.

[2] Dimitris Achlioptas and Yuval Peres, The random k-SAT threshold is 2^{k} log 2 − O(k), 35th Annual Symposium on Theory of Computing (San Diego, CA, 2003), pp. 223–231.

[3] Noga Alon and Joel H. Spencer, The Probabilistic Method, Wiley 1991.

[4] Andrei Z. Broder, Alan M. Frieze, and Eli Upfal, On the satisfiability and maximum satisfiability of random 3-CNF formulas, Proc. 4th Annual Symposium on Discrete Algorithms, 1993, pp. 322–330.

[5] N. G. de Bruijn. Asymptotic methods in analysis. Dover Publications Inc., New York, 1981.

[6] Don Coppersmith, David Gamarnik, Mohammad T. Hajiaghayi, and Gregory B. Sorkin, Random MAX 2-SAT and MAX CUT, 14th Annual Symposium on Discrete Algorithms (Baltimore, MD, 2003), New York, 2003.

[7] Stephen A. Cook, The complexity of theorem-proving procedures, 3rd Annual Symposium on Theory of Computing (Shaker Heights, OH, 1971), New York, 1971, pp. 151–158.

[8] Paul Deheuvels and David M. Mason On the Fractal Nature of Empirical Increments, The Annals of Probability 23 (1995), 355–387.

[9] A. Dembo, Y. Peres, J. Rosen and O. Zeitouni. Thick points for planar Brownian motion and the Erdős-Taylor conjecture on random walk. Acta Math., 186:239–270, 2001.

[10] Olivier Dubois and Yacine Boufkhad, A general upper bound for the satisfiability threshold of random r-SAT formulae, J. Algorithms 24 (1997), no. 2, 395–420.

[11] Olivier Dubois, Rémi Monasson, Bart Selman and Riccardo Z. Zecchina editors, Phase Transitions in Combinatorial Problems, Theoretical Computer Science, volume 265, numbers 1-2 (2001).

[12] P. Erdős and S. J. Taylor. Some problems concerning the structure of random walk paths. Acta Sci. Hung. 11:137–162, 1960.

[13] Michael R. Garey and David S. Johnson, Computers and intractability, Freeman, San Francisco, CA, 1979.

[14] Johan Håstad, Some optimal inapproximability results, Journal of ACM 48 (2001), 798–859.

[15] Svante Janson, Yannis C. Stamatiou and Malvina Vamvakari, Bounding the unsatisfiability threshold of random 3-SAT, Random Structures and Algorithms 17 (2000), no. 2, 103-116.

[16] Svante Janson, The second moment method, conditioning and approximation, Random discrete structures (Minneapolis, MN, 1993), 175–183, IMA Vol. Math. Appl., 76, Springer, New York, 1996.

[17] David Pollard, A user’s guide to measure theoretic probability, Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge, 2002. MR 2002k:60003

[18] Darren Redfern, The Maple Handbook: Maple V Release 3, third ed., Springer Verlag, New York, 1994.

[19] Michel Talagrand, Spin Glasses: A Challenge for Mathematicians: Cavity and Mean Field Models, Ergebnisse Der Mathematik Und Ihrer Grenzgebiete, 3. Folge, Bd. 46. (2003).