Bounding the unsatisfiability threshold of random 3-SAT

Svante Janson

Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden. e-mail:svante.janson@math.uu.se

Yannis C. Stamatiou^{∗}

University of Patras, Department of Computer Engineering and Informatics, Rio 265 00, Patras, Greece and Computer Technology Institute, Kolokotroni 3, 263 21, Patras, Greece. e-mail: stamatiu@ceid.upatras.gr

Malvina Vamvakari

University of Patras, Department of Computer Engineering and Informatics, Rio 265 00, Patras, Greece and Computer Technology Institute, Kolokotroni 3, 263 21, Patras, Greece. e-mail: mvamv@ceid.upatras.gr

Keywords: Unsatisfiability threshold, Rogers–Szegö polynomials, Gaussian coefficients, Generating functions, Spin system, Entropy, Statistical physics

ABSTRACT

We lower the upper bound for the threshold for random 3-SAT from 4.6011 to 4.596 through two different approaches, both giving the same result. (Assuming the threshold exists, as is generally believed but still not rigorously shown.) In both approaches, we start with a sum over all truth assignments that appears in an upper bound by Kirousis et al. to the the probability that a random 3-SAT formula is satisfiable. In the first approach, this sum is reformulated as the partition function of a spin system consisting of n sites each of which may assume the values 0 or 1. We then obtain an asymptotic expression for this function that results from the application of an optimization technique from statistical

∗Research performed while this author was visiting the School of Computer Science of Carleton University in Ottawa, supported by the Greek Ministry of National Economy through a NATO scholarship for conducting postdoctoral studies (contract number 106384/ΔOO 1222/2-7-98).

Random Structures & Algorithms Vol. ???, (???) c_{◯} ??? John Wiley & Sons, Inc. CCC ???

physics. In the second approach, we use a connection of the same sum with the Rogers– Szegö polynomials. We apply a general technique that exploits a generating function of these polynomials and provides upper bounds for each one of them. c_{◯} ??? John Wiley

& Sons, Inc.

1. INTRODUCTION

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 Pr(φ_{n,m} is satisfiable) → 1, and if m/n ≥ γ + ε, then Pr(φ_{n,m} is satisfiable) → 0.

This is not yet proven, but Friedgut [4] has shown that there exists a sequence γ_{n} such that if m/n ≤ γ_{n} − ε, then Pr(φ_{n,m} is satisfiable) → 1, and if m/n ≥ γ_{n} + ε, then Pr(φ_{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 : Pr(φ_{n,⌊cn⌋} is satisfiable) → 1\} and γ^{∗} = \overline{lim}_{n→∞}γ_{n} = inf{c : Pr(φ_{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 been published so far to our knowledge are

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

where the lower bound is due to Frieze and Suen [5] and the upper to Kirousis, Kranakis, Krizanc and Stamatiou [8].

In this paper, we show that γ^{∗} < 4.596, drawing on the results presented in [8] where a technique is given that provides an improved upper bound for the probability that a random 3-SAT formula generated with clauses to variables ratio r is satisfiable (see next section for a more detailed exposition). Part of the argument is the estimation of a certain sum over all truth assignments (see (2.2) below). As indicated in [8], this sum can be expressed as a Rogers–Szegö polynomial. These polynomials are defined as follows:

F_{n,q}(z) = ∑_{k=0}^{n} \binom{n}{k}_{q}z^{k}, (1.1)

where \binom{n}{k}_{q} denotes the Gaussian or q-nomial coefficients [9], for 0 ≤ k ≤ n and q ≠ 1:

\binom{n}{k}_{q} = \frac{(q^{n} − 1)(q^{n} − q) ⋯ (q^{n} − q^{k−1})}{(q^{k} − 1)(q^{k} − q) ⋯ (q^{k} − q^{k−1})}.

An upper bound for Rogers–Szegö polynomials was given in [7], resulting in the conclusion of [8] that γ^{∗} < 4.6011. In this paper, we prove that γ^{∗} < 4.596, by providing better estimates for this sum through two different approaches.

In one approach (our second below), we derive a better estimate of the sum in (2.2) by first establishing an improved upper bound for the Rogers–Szegö polynomials.

In our first approach we instead rewrite the sum in (2.2) in the form

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

summing over the 2^{n} sequences ε_{1}, …, ε_{n} of 0’s and 1’s, and establish an asymptotic formula for S_{n}.

We will see that, interestingly, these two different ways of expressing the same quantity turn out to favor the application of different techniques that, however, lead to the same result.

The two approaches, which originally were developed independently by two subsets of the authors, are described separately in Sections 3 and 4, and then compared in Section 5, while Section 2 describes the links to the random 3-SAT problem.

Before presenting the technical details, we would like to comment on what, we believe, should be the focal point of our work, besides the minor improvement on the upper bound of the unsatisfiability threshold. Modelling a random formula as a physical spin system and then using various characteristics of the system, such as the energy function, in order to draw some conclusion for the unsatisfiability threshold, is in the spirit of a line of research that attracts a fast-growing number of scientists from both theoretical computer science and physics. This line of research attacks the problem of proving that the unsatisfiability threshold indeed exists, by reducing it, albeit not completely rigorously, to the study of threshold phenomena in spin systems and, in particular, spin glasses. Our proof, using the spin system analogy, is an example where this analogy leads to rigorous resuls revealing, at the same time, some interesting relationship between a mathematical idea (the local maxima technique proposed in [?]) and physics. Moreover, the spin system analogy helped us establish an asymptotic expression for an important and frequently appearing in applications expression, the Rogers-Szegö polynomials, that may prove useful in a broader class of problems, than the one considered in this paper.

Note. We have been informed that better bounds recently have been proved by other methods by Zito [14] (4.579) and by Dubois, Boufkhad and Mandler [3] (4.506).

2. THE TWO APPROACHES

In this section, we will sketch the argument in [8], omitting most details. At the same time we will provide the connection of this argument with our approaches for improving the upper bound.

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 Pr(φ_{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 [8] 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: (all logarithms in this paper are natural)

u = e^{−r/7},
x = 1 − u^{3} + o(1),  (2.1)
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}}),

where φ_{2}(t) is the smallest root of φ_{2}(t) = e^{tφ_{2}(t)}. (φ_{2} is defined on [0, e^{−1}] only, but it is easily verified that the argument to φ_{2} in (2.1) lies in this interval for any r ≥ 0.) This function comes from an application of a version of Suen’s inequality [6]. It is almost certainly not the best possible, but no better results are known at present.

A long probabilistic argument in [8], 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,

Pr(A ∈ A^{2♯}) ≤ 3m^{1/2}(\frac{7}{8})^{m}X^{sf(A)}Y^{df(A)},

where

X = x + o(1)
Y = 1 + z \frac{1}{n} + o (\frac{1}{n}) ,

and thus [8, equation (20)]

E|A^{2♯}| ≤ 3m^{1/2}(\frac{7}{8})^{m} ∑_{A} X^{sf(A)}Y^{df(A)}. (2.2)

Let us denote by Σ_{n} the sum over all truth assignments that appears in (2.2). We observe that if r is such that

r log \frac{7}{8} + lim sup_{n→∞} \frac{1}{n} log Σ_{n} < 0, (2.3)

then the right-hand side of Equation (2.2) tends to 0 (by taking the nth root and then the logarithm), and thus Pr(φ_{n,m} is satisfiable) ≤ E|A^{2♯}| → 0 and γ^{∗} ≤ r.

Therefore, in order to improve the estimate for γ^{∗}, it suffices to find an as good as possible closed form upper bound for Σ_{n} or, at best, an asymptotic expression. In [8], the following expression was used as an upper bound for Σ_{n} (for a proof see [7]):

Σ_{n} ≤ ∏_{k=0}^{n−1}(1 + XY^{i/2}), 0 ≤ X^{2} ≤ Y ≤ 1,

giving γ^{∗} < 4.6011.

In our first approach, coding the truth assignments A as sequences ε_{1}, …, ε_{n}, where (unconventionally) 0 represents TRUE and 1 FALSE, we see that the sum Σ_{n} in (2.2) equals S_{n} as defined in (1.2), with a = log(X) = log x + o(1) and b = n log(Y) = z + o(1). We then obtain an asymptotic expression for Σ_{n} using an optimization technique commonly employed in statistical physics.

In the second approach, we use the fact that, using the notation (1.1),

Σ_{n} = F_{n,Y} (X) (2.4)

(see [8]). We then derive an upper bound for the Rogers–Szegö polynomials using a generating functions technique described in [10].

The exact value and the upper bound to lim sup_{n→∞} \frac{1}{n} log Σ_{n} given by these two approaches are expressed by quite different formulas, but when inserted in (2.3), both formulas yield the same numerical result γ^{∗} < 4.596. We show in Section 5 that the two formulas indeed are equivalent.

3. THE FIRST APPROACH: AN ASYMPTOTIC FORMULA FOR Σ_{N} USING STATISTICAL PHYSICS METHODS

We will prove the following asymptotic formula for S_{n}.

Theorem 3.1. Let a and b be two fixed real numbers, and define S_{n} by (1.2). 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})),  (3.1)

with h = h(a, b) given by

h = log (e^{a} − 1 + \sqrt{(e^{a} − 1)^{2} + 4e^{a+b}}) − log 2 − b. (3.2)

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

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

Remark 3.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.

Proof. The theorem is proved by a fairly straightforward optimization of the type common in statistical physics. For later notational convenience we rewrite (1.2) 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}).  (3.3)

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.2) 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)  (3.4)

(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}). (3.5)

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 (3.5) 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} ). (3.6)

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.

The function 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}.  (3.7)

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}^{∗}, (3.8)

and obtain by (3.7)

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}} . (3.9)

Here h_{N} should be such that (3.8) 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 (3.8) 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). (3.10)

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, and (3.10) implies that h_{N} → h as N → ∞. Moreover, the definition of h is

h − log(1 + e^{h}) + log(1 + e^{h+b}) = a, (3.11)

which can be rewritten as e^{h}(1+e^{h+b}) = a(1+e^{h}). Solving this quadratic equation in e^{h}, we easily find (3.2).

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 (3.9), y_{k}^{∗} = g_{N}(k/N). Now let N → ∞; then g_{N} → g uniformly on [0, 1], and it follows from the definition (3.4) 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.  (3.12)

Denoting the right-hand side by ψ(a, b), this together with (3.6) 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.11), easily is shown to equal the expressions given in (3.1).

Remark 3.5. The proof demonstrates the usual conflict between energy and entropy; the largest term in (1.2) 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.

We have assumed in Theorem 3.1 that a and b are fixed, but it is easily seen that the result remains valid if S_{n} is defined using a_{n} and b_{n}, where a_{n} → a and b_{n} → b as n → ∞. (Cf. Remark 3.2.) In particular, with notation as in Section 2, taking a_{n} = log X → log x and b_{n} = n log Y → z, S_{n} = Σ_{n} = ∑_{A} X^{sf(A)}Y^{df(A)} as in (2.2), and it follows that

lim_{n→∞} \frac{1}{n} log Σ_{n} = ψ(log x, z). (3.13)

Consequently (see (2.3)), if r is such that

r log(7/8) + ψ(log x, z) < 0, (3.14) then Pr(φ_{n,m} is satisfiable) ≤ E|A^{2♯}| → 0 as n → ∞, and thus γ^{∗} ≤ r. (By continuity of the left-hand side of (3.14) in r, in fact γ^{∗} < r.) A numerical calculation (performed with a small Pascal progam) shows that (3.14) indeed holds for r = 4.596.

4. THE SECOND APPROACH: BOUNDING Σ_{N} USING AN UPPER BOUND FOR THE ROGERS–SZEGÖ POLYNOMIALS

In order to establish an upper bound for the Rogers–Szegö polynomials, we will make use of the following lemma, that appears as Lemma 8.1 in [10]:

Lemma 4.1. Let f(z) = ∑_{i=0}^{∞} f_{i}z^{i} be the generating function for the sequence f_{i}, i ≥ 0. Then if f(z) is analytic in |z| < R and if f_{i} ≥ 0 for all i ≥ 0, then for any t, 0 < t < R, and any n ≥ 0, it holds that

f_{n} ≤ t^{−n}f(t).

In the following theorem, we prove an upper bound for F_{n,q}(x) which improves upon the one used in [8].

Theorem 4.2. Let F_{n,q}(x) = ∑_{i=0}^{n} \binom{n}{i}_{q}x^{i} be the Rogers–Szegö polynomials. If 0 < x < ∞, 0 < q < 1 and n ≥ 0, then for any t, 0 < t < min(1, 1/x),

F_{n,q}(x) ≤ t^{−n} exp [−\frac{1}{log q} (Li_{2}(tx) + Li_{2}(t) + Li_{2}(q^{n}) − Li_{2}(q))] \frac{1}{(1 − t)(1 − tx)}

where

Li_{2}(y) = dilog(1 − y) = Polylog(2, y) = ∑_{k≥1} \frac{y^{k}}{k^{2}} ,

is the polylogarithm (or logarithmic integral) of index 2 at point y. Proof. Let

G(z, x) = ∑_{n=0}^{∞} F_{n,q}(x) ∏_{j=1}^{n}(1 − q^{j})^{−1}z^{n},

be the Eulerian generating function of F_{n,q}(x) (see [12]). Then (see [2])

G(z, x) = ∏_{j=0}^{∞}(1 − q^{j}zx)^{−1}(1 − q^{j}z)^{−1}.

For 0 < z < min(1, 1/x), the double generating function G(z, x) can be bounded from above as follows:

G(z, x) = exp [∑_{j=0}^{∞} − log(1 − q^{j}zx) + ∑_{j=0}^{∞} − log(1 − q^{j}z)]

= exp [∑_{j=1}^{∞} − log(1 − q^{j}zx) + ∑_{j=1}^{∞} − log(1 − q^{j}z)]
· exp[− log(1 − zx) − log(1 − z)]
≤ exp [− ∫_{0}^{∞} log(1 − q^{u}zx) du − ∫_{0}^{∞} log(1 − q^{u}z) du]
· \frac{1}{(1 − z)(1 − zx)}
= exp [−\frac{dilog(1 − zx)}{log(q)} − \frac{dilog(1 − z)}{log(q)}] \frac{1}{(1 − z)(1 − zx)}
= exp [−\frac{1}{log(q)}(Li_{2}(zx) + Li_{2}(z))]
· \frac{1}{(1 − z)(1 − zx)}.  (4.1)

Therefore, applying Lemma 4.1, we have that for any t, 0 < t < min(1, 1/x), and any n ≥ 0 it holds that

F_{n,q}(x) ≤ t^{−n} exp [−\frac{1}{log(q)}(Li_{2}(tx) + Li_{2}(t))] \frac{1}{(1 − t)(1 − tx)} ∏_{j=1}^{n}(1 − q^{j}).(4.2)

But

∏_{j=1}^{n}(1 − q^{j}) = exp (log (∏_{j=1}^{∞}(1 − q^{j}) / ∏_{j=n+1}^{∞}(1 − q^{j})))

= exp (∑_{j=1}^{∞} log(1 − q^{j}) − ∑_{j=n+1}^{∞} log(1 − q^{j}))

≤ exp (∫_{1}^{∞} log(1 − q^{j}) dj − ∫_{n}^{∞} log(1 − q^{j}) dj)
= exp [\frac{1}{log q} (Li_{2}(q) − Li_{2}(q^{n}))]

and, thus, Equation (4.2) completes the proof of the theorem.

Since the inequality of Theorem 4.2 holds for any t ∈ (0, 1), we may optimize it by choosing t so that the right-hand side attains its minimum value. Since it is rather difficult to minimize this expression, we will instead choose t such as to minimize the factor

G^{∗}(t) = t^{−n} exp [−\frac{1}{log(q)}(Li_{2}(tx) + Li_{2}(t))] .

We compute the first derivative of log G^{∗}(t) and set it equal to 0:

−\frac{n}{t} + \frac{1}{t log q} log [(1 − tx)(1 − t)] = 0.

Solving for t, and selecting the unique solution for which the second derivative of log G^{∗}(t) is positive, we obtain the optimal value t = t_{0}(x, q^{n}), where

t_{0}(x, y) = \frac{x + 1 − \sqrt{(x − 1)^{2} + 4xy}}{2x} . (4.3)

It is easily verified that 0 < t_{0}(x, q^{n}) < min(1, 1/x), so we may use t = t_{0} in Theorem 4.2. Notice, that then the factor 1/((1 − tx)(1 − x)) becomes q^{−n}.

In particular, this yields the following asymptotic result.

Corollary 4.3. If X = x + o(1) and q = 1 + z/n + o(1/n), where 0 < x < ∞ and z < 0, then,

lim sup_{n→∞} \frac{1}{n} log F_{n,q}(X) ≤ f(x, z), (4.4)

where, with t = t_{0}(x, e^{z}) given by (4.3),

f(x, z) = − log t − \frac{1}{z}(Li_{2}(tx) + Li_{2}(t) + Li_{2}(e^{z}) − Li_{2}(1)). (4.5)

Consequently, from (2.4) in Section 2 and if x and z are given by (2.1), we get that

lim sup_{n→∞} log Σ_{n} ≤ f(x, z), (4.6)

which together with (2.3) shows that if

r log \frac{7}{8} + f(x, z) < 0, (4.7)

then γ^{∗} < r. Solving the equation r log \frac{7}{8} + f(x, z) = 0 (e.g. using Maple [11]), the upper bound γ^{∗} < 4.596 for the unsatisfiability threshold follows.

Remark 4.4. It follows from Theorem 5.1 below that the inequality (4.4) can be sharpened to the equality lim_{n→∞} \frac{1}{n} log F_{n,q}(X) = f(x, z).

5. DISCUSSION

In this paper we have presented two different methods that lead to the same improvement on the upper bound for the unsatisfiablity threshold. Rather than focus on this minor improvement (4.596 versus 4.6011), we believe that it is more interesting and rewarding to concentrate on the techniques employed and the implications of the fact that they lead to exactly the same improvement.

The first interesting observation is that the two approaches consist of simply rewriting the same expression, Σ_{n}, in two different forms. Then it turned out that each of these forms facilitated the application of radically different techniques. In the first approach we considered, Σ_{n} was formulated as the partition function of a physical system of n spin sites, each assuming the values 0 or 1. Then an optimization technique commonly used in physics was applied that resulted in an asymptotic expression for the partition function and, thus, for Σ_{n}. On the other hand, in the second approach we used the fact that Σ_{n} is an expression for the Rogers–Szegö polynomials. We then used the Eulerian generating function of these polynomials that resulted in an upper bound for them and, therefore, for Σ_{n} for each finite n.

The fact that the two methods lead to the same numerical result is no coincidence. In fact, as it is shown in the following theorem, the upper bound given in (4.4) equals the limit given in Theorem 3.1. Hence (4.4) is, in fact, an equality, which shows that Theorem 4.2 is, in one sense, asymptotically sharp.

Theorem 5.1. Let ψ and f be given by (3.1) and (4.5). Then, for any real a and b with b < 0,

ψ(a, b) = f(e^{a}, b).

Proof. Although both ψ(a, b) and f(e^{a}, b) involve the dilogarithm, or logarithmic integral, the two expressions look quite different and we do not know any simple transformation of one into the other. Instead we proceed as follows.

We choose to parametrize by b and h, given by (3.2) or (3.11). Thus, for b < 0 and −∞ < h < ∞, define a by (3.11), x = e^{a} = e^{h}(1+e^{h+b})/(1+e^{h}) and t = t_{0}(x, e^{b}) by (4.3); it is easily seen, using (3.2) and (3.11), that t = 1−e^{h+b−a} = (1−e^{b})/(1+e^{h+b}) and thus tx = e^{h}(1 − e^{b})/(1 + e^{h}). Now express ψ(a, b) and f(x, b) as functions ψ̃(b, h) and f̃(b, h) of b and h.

First consider the case h = −b/2, which yields a = 0, x = 1, t = 1 − e^{b/2}. Then, by straightforward calculations which we omit,

\frac{d}{db}bψ̃(b, −b/2) = log(1 + e^{b/2}) = \frac{d}{db}bf̃(b, −b/2),

and thus bψ̃(b, −b/2) = bf̃(b, −b/2) + C for some constant C and all b < 0. Letting b → 0 yields C = 0, and thus ψ̃(b, −b/2) = f̃(b, −b/2) for all b < 0.

Next keep b < 0 fixed and vary h. Then, by further straightforward calculations which we omit,

\frac{∂}{∂h}ψ̃(b, h) = \frac{1}{b} (\frac{1}{1 + e^{h}} + \frac{e^{h+b}}{1 + e^{h+b}} ) log \frac{1 + e^{h+b}}{1 + e^{h}} = \frac{∂}{∂h}f̃(b, h),

and the identity follows.

The implications of the above discussion, can be summarized as follows:

• The fact that the first approach gave an asymptotic expression for S_{n} leads us to the conclusion that reducing the upper bound further using the double flips idea, will require the discovery of better correlation inequalities than the ones that resulted in the sum Σ_{n}. We believe that such a task is achievable.

• The fact that the upper bound for S_{n} that was obtained from the second approach using the very simple technique of Lemma 4.1 gives the same value as the asymptotic expression of the first approach, is an example that justifies the belief (see page 1122 in [10]) that such techniques, despite their simplicity, often give results close to the best possible.

• Using the observation that the sum S_{n} is equal to ∑_{k=0}^{n} \binom{n}{k}_{q}X^{k}, where X = e^{a} and q = e^{b/n}, we have, indirectly, also obtained an asymptotic expression for the Rogers–Szegö polynomials themselves.

We will close this paper by stating that the lower and the upper bound for the unsatisfiablitity threshold for random 3-SAT formulas are still far from the experimentally estimated threshold value. Reducing their distance is a challenging problem that may also lead to insights and implications not merely related to the threshold value itself, like the ones stated above.

ACKNOWLEDGEMENT

The first author thanks Anders Martin-Löf for helpful discussions. The second and the third authors, would like to thank Lefteris Kirousis whose concern, encouragement and help were crucial in the development and the clearer presentation of their thoughts. Also, without him, the three authors would have never worked together on this interesting problem. The authors would also like to thank the anonymous referees whose comments and suggestions helped to improve the presentation of the results in this paper.

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] L. Carlitz, Some polynomials related to theta functions. Ann. Mat. Pura Appl. 41 (1956), 359–373.

[3] O. Dubois, Y. Boufkhad & J. Mandler, Typical Random 3-SAT Formulae and the Satisfiability Threshold. SODA 2000.

[4] E. Friedgut, Sharp thresholds of graph properties, and the k-sat problem. J. Amer. Math. Soc. 12 (1999), 1017–1054.

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

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

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

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

[9] D.E. Knuth, Fundamental Algorithms, The Art of Computer Programming, Vol. 1. 3rd ed., Addison–Wesley, Reading, MA, 1997.

[10] A.M. Odlyzko, Handbook of Combinatorics, Chapter 22 Asymptotic Enumeration Methods. Eds. R.L. Graham, M. Grötschel, and L. Lovász, 1063-1229. Elsevier Science Publishers, Amsterdam, 1995.

[11] D. Redfern, The Maple Handbook: Maple V Release 3. Springer-Verlag, New York, 1994.

[12] V.N. Sachkov, Combinatorial Methods in Discrete Mathematics. Ed. G.-C. Rota, Encyclopedia of Mathematics and its Applications, vol. 55. Cambridge University Press, 1996.

[13] W.C. Suen, A correlation inequality and a Poisson limit theorem for nonoverlapping balanced subgraphs of a random graph. Random Struct. Alg. 1 (1990), 231–242.

[14] Ph.D. Thesis, University of Warwick.