ON RANDOM 3-SAT

SVANTE JANSON

Abstract. We prove that a random Boolean 3-SAT formula on n variables with 4.596n clauses is almost certainly unsatisfiable, in the sense that the probability of it being satisfiable tends to 0 as n → ∞.

1. Introduction and results

The random 3-SAT problem is the following: Let x_{1}, …, x_{n} be n Boolean variables and consider the 8\binom{n}{3} clauses consisting of the disjunction of three literals x_{i} or ¬x_{i} using three different variables. Construct a random formula φ_{n,m} as the conjunction of m of these clauses, selected at random (with replacement, for definiteness; this does not matter asymptotically). Now let n, m → ∞. Experiments suggest strongly that there is a threshold γ ≈ 4.2 such that if m/n ≤ γ − ε for any ε > 0, then ℙ(φ_{n,m} is satisfiable) → 1, and if m/n ≥ γ + ε, then ℙ(φ_{n,m} is satisfiable) → 0.

This is not yet proven, but Friedgut [2] has shown that there exists a sequence γ_{n} such that if m/n ≤ γ_{n} − ε, then ℙ(φ_{n,m} is satisfiable) → 1, and if m/n ≥ γ_{n} + ε, then ℙ(φ_{n,m} is satisfiable) → 0. It is still not known, however, if these γ_{n} converge (or, equivalently, can be taken as a constant γ). We therefore define γ_{∗} = \underline{lim}_{n→∞}γ_{n} = sup\{c : ℙ(φ_{n,⌊cn⌋} is satisfiable) → 1\} and γ^{∗} = \overline{lim}_{n→∞}γ_{n} = inf\{c : ℙ(φ_{n,⌊cn⌋} is satisfiable) → 0\}. Hence γ_{∗} ≤ γ^{∗} (and presumably equality holds).

Many authors have given numerical bounds for γ_{∗} or γ^{∗} using various techniques. The best bounds that have appeared so far to our knowledge are

3.003 < γ_{∗} ≤ γ^{∗} < 4.601+,

where the lower bound is due to Frieze and Suen [6] and the upper to Kirousis, Kranakis, Krizanc and Stamatiou [5]. The purpose of the present paper is to present a small improvement in the upper bound.

Theorem 1. γ^{∗} < 4.596.

The proof is based on the proof in [5], improving one estimate only.

The improvement concerns the sum

S_{n} = ∑_{ε_{1},...,ε_{n}∈\{0,1\}} exp(a ∑_{i=1}^{n} ε_{i} + \frac{b}{n} ∑ ∑_{1≤i<j≤n} ε_{i}(1 − ε_{j})),  (1)

summing over the 2^{n} sequences ε_{1}, …, ε_{n} of 0’s and 1’s. We will prove the following asymptotic formula for S_{n}. (All logarithms in this paper are natural.)

Date: March 2, 1999; revised March 8, 1999.

Theorem 2. Let a and b be two fixed real numbers, and define S_{n} by (1). Then, as n → ∞,

\frac{1}{n} log S_{n} → ψ(a, b),

where ψ(a, 0) = log(1 + e^{a}) and for b ≠ 0

ψ(a, b) = \frac{(h − a)^{2}}{2b} + \frac{1}{b} ∫_{h}^{h+b} log(1 + e^{x}) dx
= \frac{(h − a)^{2}}{2b} + \frac{1}{b}(dilog(1 + e^{h}) − dilog(1 + e^{h+b})),

(2)

with h = h(a, b) denoting the unique root of

h − log(1 + e^{h}) + log(1 + e^{h+b}) = a.  (3)

Remark 1. The dilogarithm is defined by dilog(x) = − ∫_{1}^{x} \frac{log t}{t−1} dt [1], and the second equality in (2) follows by a simple change of variables.

Remark 2. It is easily shown that ψ is continuous, also at b = 0.

Remark 3. The sum S_{n} equals ∑_{k=0}^{n} \binom{n}{k}_{q}X^{k}, where X = e^{a}, q = e^{b/n} and the q-binomial coefficient \binom{n}{k}_{q} = ∏_{i=0}^{k−1}(1 − q^{n−i})/(1 − q^{k−i}), see [4, 5], but we will not use this representation.

Remark 4. In statistical physics terminology, S_{n} is the partition function for a system with n sites, each of which has a spin ε_{i} which may take the values 0 and 1, and with an energy function H = −a ∑_{i=1}^{n} ε_{i} − \frac{b}{n} ∑ ∑_{1≤i<j≤n} ε_{i}(1−ε_{j}). The first term in H corresponds to an external field acting on all spins, and the second to a peculiar interaction which acts only between pairs of sites (of arbitrary distance) where the left site has spin 1 and the right site has spin 0.

This energy function can easily be rewritten into a more conventional form. In fact, H = ∑_{i=1}^{n}( − a − b + b\frac{i}{n})ε_{i} + \frac{b}{n} ∑ ∑_{i<j} ε_{i}ε_{j}, or, substituting ε_{i} = (1 + s_{i})/2 to have more traditional (and symmetrical) spins with values ±1, H = −\frac{a}{2}n − \frac{b}{8}(n − 1) + ∑_{i=1}^{n}(−\frac{a}{2} + b\frac{i−(n+1)/2}{2n})s_{i} + \frac{b}{4n} ∑ ∑_{i<j} s_{i}s_{j}, which shows that the system can be interpreted as a mean-field Ising model with an inhomogeneous (linear) external field.

Remark 5. Theorem 1 has independently been proved by Stamatiou and Vamvakari [7], using another estimate of the sum S_{n}.

Acknowledgement

I thank Anders Martin-Löf for helpful discussions.

2. Proof of Theorem 2

Theorem 2 is proved by a fairly straightforward optimization of the type common in statistical physics. For later notational convenience we rewrite (1) in the equivalent form (reversing the order of ε_{1}, …, ε_{n})

S_{n} = ∑_{ε_{1},...,ε_{n}∈\{0,1\}} exp(a ∑_{i=1}^{n} ε_{i} + \frac{b}{n} ∑ ∑_{1≤i<j≤n}(1 − ε_{i})ε_{j}),  (4)

We begin by discretizing in order to obtain a finite-dimensional optimization problem also asymptotically. Fix a large integer N and partition {1, …, n} into N intervals I_{1}, …, I_{N} of lengths ⌊n/N⌋ or ⌈n/N⌉; let n_{k} = |I_{k}| = n/N + O(1). We group the terms in (1) according to m_{k} = ∑_{i∈I_{k}} ε_{i}, k = 1, …, N, and obtain, observing that the sum of all (1 − ε_{i})ε_{j} with i and j in the same interval I_{k} is less than N(n/N)^{2},

S_{n} = ∑_{m_{1},...,m_{k}} ∏_{k=1}^{N} \binom{n_{k}}{m_{k}} exp(a ∑_{k=1}^{N} m_{k} + \frac{b}{n} ∑ ∑_{1≤k<l≤N}(n_{k} − m_{k})n_{l} + O(n/N)).

(The implicit constants in the O terms here and below may depend on a and b but not on n or N.) By Stirling’s formula,

log \binom{M}{m} = M log M − m log m − (M − m) log(M − m) + O(log M)

= M(−\frac{m}{M} log \frac{m}{M} − (1 − \frac{m}{M} ) log(1 − \frac{m}{M} )) + O(log M)

and thus, with y_{k} = m_{k}/n_{k} and summing over the grid Λ_{Nn} = {(y_{1}, …, y_{N}) ∈ [0, 1]^{N} : n_{k}y_{k} is an integer for every k}

S_{n} = ∑_{Λ_{Nn}} exp(∑_{k=1}^{N} \frac{n}{N} (−y_{k} log y_{k} − (1 − y_{k}) log(1 − y_{k})) + O(N log n)

+ a ∑_{k=1}^{N} \frac{n}{N} y_{k} + \frac{bn}{N^{2}} ∑ ∑_{1≤k<l≤N}(1 − y_{k})y_{l} + O(N) + O(n/N)).

Define, for y = (y_{1}, …, y_{N}) ∈ [0, 1]^{N},

F_{N}(y) = \frac{1}{N} ∑_{k=1}^{N}(−y_{k} log y_{k} − (1 − y_{k}) log(1 − y_{k}) + ay_{k})

+ \frac{b}{N^{2}} ∑ ∑_{1≤k<l≤N}(1 − y_{k})y_{l} + \frac{b}{N^{2}} ∑_{k=1}^{N}(y_{k} − y_{k}^{2}/2) (5)

(the last term, which is O(1/N), will be convenient below). Then,

S_{n} = ∑_{y∈Λ_{Nn}} exp(nF_{N}(y) + O(\frac{n}{N} + N log n)).

The number of terms in this sum is ∏_{1}^{N}(1 + n_{k}) ≤ n^{N}, and thus

S_{n} = max_{y∈Λ_{Nn}} exp(nF_{N}(y) + O(\frac{n}{N} + N log n))

and

\frac{1}{n} log S_{n} = max_{y∈Λ_{Nn}} F_{N}(y) + O(\frac{1}{N} + N \frac{log n}{n}).  (6)

Since F_{N} is continuous on [0, 1]^{N}, max_{y∈Λ_{Nn}} F_{N}(y) tends to the global maximum of F_{N} on [0, 1]^{N} as n → ∞, and (6) implies

lim inf_{n→∞} \frac{1}{n} log S_{n}, lim sup_{n→∞} \frac{1}{n} log S_{n} = max_{y} F_{N}(y) + O(\frac{1}{N} ).  (7)

It follows easily that both lim_{n→∞} \frac{1}{n} log S_{n} and lim_{N→∞} max_{y} F_{N}(y) exist and are equal, but it remains to find this limit.

F_{N} is continuous on the closed cube [0, 1]^{N} and differentiable in its interior with

N \frac{∂F_{N}}{∂y_{k}} = − log y_{k} + log(1 − y_{k}) + a + \frac{b}{N} (− ∑_{l>k} y_{l} + ∑_{j<k}(1 − y_{j}) + 1 − y_{k})

= − log y_{k} + log(1 − y_{k}) + a + \frac{b}{N} k − \frac{b}{N} ∑_{l=1}^{N} y_{l}. (8)

Since this derivative tends to +∞ as y_{k} ↓ 0, and to −∞ as y_{k} ↑ 1, the maximum of F_{N} cannot be attained for y_{k} = 0 or y_{k} = 1; thus the maximum is attained at an interior point y^{∗} where all ∂F_{N}/∂y_{k} = 0.

We define

h_{N} = a − \frac{b}{N} ∑_{k=1}^{N} y_{k}^{∗},  (9)

and obtain by (8)

log \frac{y_{k}^{∗}}{1 − y_{k}^{∗}} = h_{N} + b\frac{k}{N} .

Hence,

y_{k}^{∗} = \frac{e^{h_{N} +bk/N}}{1 + e^{h_{N} +bk/N}} .  (10)

Here h_{N} should be such that (9) holds. We observe that \frac{b}{N} ∑ y_{k}^{∗} is a Riemann sum of

∫_{0}^{1} b\frac{e^{h_{N} +bt}}{1 + e^{h_{N} +bt}} = [log(1 + e^{h_{N} +bt})]_{0}^{1} = log(1 + e^{h_{N} +b}) − log(1 + e^{h_{N}}).

Since (9) implies |h_{N}| ≤ |a|+|b| and the Riemann sums of this integral converge uniformly for h_{N} in a compact set,

h_{N} = a − log(1 + e^{h_{N} +b}) + log(1 + e^{h_{N}}) + o(1).  (11)

The function φ(h) = h−log(1+e^{h})+log(1+e^{h+b}) = log(1+e^{h+b})−log(1+e^{−h}) is strictly increasing on (−∞, +∞), and lim_{h→±∞} φ(h) = ±∞. Consequently, there exists a unique h = h(a, b) such that φ(h) = a, i.e. (3) holds, and (11) implies that h_{N} → h(a, b) as N → ∞.

Let g_{N}(t) = e^{h_{N} +bt}/(1 + e^{h_{N} +bt}) and g(t) = e^{h+bt}/(1 + e^{h+bt}). Thus, by (10), y_{k}^{∗} = g_{N}(k/N). Now let N → ∞; then g_{N} → g uniformly on [0, 1], and it follows from the definition (5) of F_{N} that

max F_{N} = F_{N}(y^{∗}) → ∫_{0}^{1}(−g(t) log g(t) − (1 − g(t)) log(1 − g(t)) + ag(t)) dt

+ b ∫∫ _{0≤s<t≤1}(1 − g(s))g(t) ds dt. (12)

Denoting the right hand side by ψ(a, b), this together with (7) shows that lim inf \frac{1}{n} log S_{n} = lim sup \frac{1}{n} log S_{n} = ψ(a, b), as asserted.

It remains to derive the more explicit expressions given for ψ(a, b). The case b = 0 is trivial, with S_{n} = (1 + e^{a})^{n}, so we assume b ≠ 0. Integrating first over s, we obtain

ψ(a, b) = ∫_{0}^{1}(−g(t)(h + bt) + log(1 + e^{h+bt}) + ag(t)
+ (bt − log(1 + e^{h+bt}) + log(1 + e^{h}))g(t)) dt
= \frac{1}{b}[(a − h) log(1 + e^{h+bt}) − \frac{1}{2}(log(1 + e^{h+bt}) − log(1 + e^{h}))^{2}]_{0}^{1}
+ ∫_{0}^{1} log(1 + e^{h+bt}) dt,

which, using log(1 + e^{h+b}) − log(1 + e^{h}) = a − h from (3), easily is shown to equal the expressions given in (2).

Remark 6. The proof demonstrates the usual conflict between energy and entropy; the largest term in (1) is obtained for a sequence of 0’s followed by 1’s or conversely (depending on the sign of b), while most terms have about n/2 0’s and 1’s rather uniformly distributed; neither of these cases contribute significantly to the sum (unless a = b = 0). The proof shows that the main contribution comes from terms where the density of 1’s among the ε_{i} with i/n ≈ t is about g(1 − t); these are thus the typical states in the statistical physics interpretation.

3. Proof of Theorem 1

We sketch the argument of Kirousis, Kranakis, Krizanc and Stamatiou [5], omitting most details.

First, an old observation is that a given truth assignment A to x_{1}, …, x_{n} satisfies 7\binom{n}{3} of the 8\binom{n}{3} considered clauses with three literals, and hence the probability that φ_{n,m} is satisfied by A equals (7/8)^{m}. Since there are 2^{n} different truth assignments, the expected number of truth assignments that satisfy φ_{n,m} is 2^{n}(7/8)^{m}, and if m/n ≥ log 2/ log(8/7) + ε (with ε > 0), this tends to 0 and thus ℙ(φ_{n,m} is satisfiable) → 0. Consequently γ^{∗} ≤ log 2/ log(8/7) ≈ 5.191.

This bound is not sharp, and the reason is that a satisfiable formula usually has many satisfying truth assignments, and thus it is possible that the expected number tends to infinity even when the probability of having any satisfying truth assignment tends to 0. The method used in [5] to obtain better estimates is to count only a subset of all satisfying truth assignments; they choose the set A^{2♯} defined as follows.

A change of a truth assignment to another is called a single flip if the value of exactly one variable x_{i} is changed and this change is from FALSE to TRUE; a change is called a double flip if the values of exactly two variables x_{i} and x_{j} (with i < j) are changed and further x_{i} is changed from FALSE to TRUE and x_{j} from TRUE to FALSE. Then A^{2♯} is defined as the set of all truth assignments A such that A satisfies φ_{n,m} but no single or double flip of A does. (It is easily seen that A^{2♯} is non-empty if φ_{n,m} is satisfiable.)

Let r > 0 and define the following functions of r:

u = e^{−r/7},
X = 1 − u^{3},
Z = −\frac{6u^{6} log(1/u)}{1 − u^{3}} + \frac{18u^{9} log^{2}(1/u)}{(1 − u^{3})^{2}}φ_{2}(\frac{6u^{6} log(1/u)}{1 − u^{3}}),

(13)

where φ_{2}(x) is the smallest root of φ_{2}(x) = e^{xφ_{2}(x)}. (φ_{2} is defined on [0, e^{−1}] only, but it is easily verified that the argument to φ_{2} in (13) lies in this interval for any r ≥ 0.) A long probabilistic argument [5] shows that if r > 0 is fixed and m, n → ∞ with m/n → r, then for any truth assignment A with sf(A) possible single flips and df(A) possible double flips,

ℙ(A ∈ A^{2♯}) ≤ 3m^{1/2}(\frac{7}{8})^{m}(X + o(1))^{sf(A)}(1 + \frac{1}{n}Z + o(\frac{1}{n}))^{df(A)}

and thus [5, equation (20) (with slightly different notation)]

𝔼 |A^{2♯}| ≤ 3m^{1/2}(\frac{7}{8})^{m} ∑_{A}(X + o(1))^{sf(A)}(1 + \frac{1}{n}Z + o(\frac{1}{n}))^{df(A)}. (14)

Coding the truth assignments A as sequences ε_{1}, …, ε_{n}, where (unconventionally) 0 represents TRUE and 1 FALSE, we see that the sum in (14) is S_{n} as defined in (1), with a = log(X + o(1)) = log X + o(1) and b = n log(1 + \frac{1}{n}Z + o(\frac{1}{n})) = Z + o(1), and it follows from Theorem 2 (and Remark 2) that

𝔼 |A^{2♯}| ≤ exp(n(r log(7/8) + ψ(log X, Z) + o(1))).

In particular, if r is such that

r log(7/8) + ψ(log X, Z) < 0,  (15)

then ℙ(φ_{n,m} is satisfiable) ≤ 𝔼 |A^{2♯}| → 0 as n → ∞, and thus γ^{∗} ≤ r. (By continuity of the left hand side of (15) in r, in fact γ^{∗} < r.)

A numerical calculation (performed with a small Pascal progam) shows that (15) indeed holds for r = 4.596.

Remark 7. The proof in [5] uses instead of Theorem 2 the estimate, proved in [4], that if 2a ≤ b/n ≤ 0, then S_{n} ≤ ∏_{k=0}^{n−1}(1 + e^{a+ib/2n}), and thus

\overline{lim} \frac{1}{n} log S_{n} ≤ \frac{2}{b} ∫_{a}^{a+b/2} log(1 + e^{x}) dx = \frac{2}{b}(dilog(1 + e^{a}) − dilog(1 + e^{a+b/2})).

Remark 8. The function φ_{2} in (13) comes from an application of a version of Suen’s inequality [3]. It is almost certainly not the best possible, but no better results are known at present.

References

[1] M. Abramowitz & I.E. Stegun, Eds., Handbook of Mathematical Functions. U.S. Department of Commerce, National Bureau of Standards, Washington, DC, 1972.

[2] E. Friedgut, Necessary and sufficient conditions for sharp thresholds of graph properties, and the k-sat problem. J. Amer. Math. Soc., to appear.

[3] S. Janson, New versions of Suen’s correlation inequality. Random Struct. Alg. 13 (1998), 467–483.

[4] L. Kirousis, E. Kranakis & D. Krizanc, An upper bound for a basic hypergeometric series. Tech. Report TR-96-07, Computer Technology Institute, Carleton University, Canada, 1996.

[5] L.M. Kirousis, E. Kranakis, D. Krizanc & Y.C. Stamatiou, Approximating the unsatisfiability threshold of random formulas. Random Struct. Alg. 12 (1998), 253–269.

[6] A. Frieze & S. Suen, Analysis of two simple heuristics on a random instance of k-SAT. J. Algorithms 20 (1996), 312–355.

[7] Y.C. Stamatiou and M. Vamvakari, A bound for the Rogers–Szegö polynomials with an application to the threshold conjecture of random SAT problems. Preprint, 1999.

Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden

E-mail address: svante.janson@math.uu.se