betaFeedback

WorksMathematics

The satisfiability conjecture for random k-SAT formulas. Human-friendly exposition of the recent OpenAI resolution

Abstract

The satisfiability conjecture was one of the most important open problems in discrete probability. It was resolved recently first by Carenini~\cite{GCarenini}, and shortly after by OpenAI~\cite{k-sat-OpenAI}, among other 370 problems solved by its internal model. The conjecture concerned the satisfiability property of random instances of the k-SAT problem. It posits the existence of a fixed value for the clause-to-variables ratio around which the probability that the formula is satisfiable drops sharply from nearly one to nearly zero as the ratio increases. While the case of large constant kk was resolved a decade ago by Ding, Sly and Sun~\cite{ding2015proof,ding2022proof} using the heavy machinery of the second moment method, the case of general kk eluded proof until ~\cite{GCarenini} and~\cite{k-sat-OpenAI}. In this short note we provide a ''human-friendly'' and detailed exposition of the OpenAI's resolution of the conjecture.

Introduction

The satisfiability conjecture was one of the most important open problems in discrete probability and theoretical computer science areas in the last several decades. It concerns random instances of a particular class of constraint satisfaction problems known as k-SAT problem. The k-SAT problem concerns the satisfiability property of a k-SAT Boolean formula with mm clauses of size kk and nn variables, see the next section for the formal description of the model and the statement of the conjecture. The conjecture posits that for each kk there exists a fixed value λ∗=λk∗\lambda^{*} = \lambda^{*}_{k} with the following property: the probability that the formula is satisfiable (not-satisfiable) is asymptotically one (asymptotically zero) when m/nm/n is uniformly smaller (uniformly larger) than λ∗\lambda^{*} and nn diverges to infinity. Namely, the probability of satisfiability exhibits a sharp phase transition around some constant value λ∗\lambda^{*}. The conjecture was positively resolved recently, first by Carenini [5], and shortly after by OpenAI [17]. The paper produced by OpenAI was one among 721 papers produced by the organization devoted to resolving some 372 open problems. The present paper is devoted to producing a reader-friendly exposition of the OpenAI paper. While the manuscript [17] is fairly short and readable on a purely technical level, in a fashion typical for the works produced by AI only, it is not optimized for the readership, contains unnecessary redundancies, applies an uncommon jargon and obscures key ideas. The present manuscript is devoted to fix this. Part of my motivation to write this manuscript was to understand and internalize the proof myself.

A brief history of the conjecture

The conjecture was formulated in Chvátal and Reed [7] who also resolved the conjecture positively for the case k=2k = 2. In particular, they proved λ2∗=1\lambda^*_{2} = 1. The progress beyond k=3k = 3 stalled however for several decades, despite many papers devoted to the subject and dramatic progress, particularly in narrowing the potential values of λk∗\lambda^*_{k}, assuming its validity, see for example [3, 2, 8]. Furthermore, sharp phase transition property was established for the satisfiability property for all kk by Friedgut in his landmark paper [13]. This work produced necessary and sufficient conditions for the existence of sharp transition for general random graph and random hypergraph properties, of which satisfiability of a random kk-SAT formula is a special case. Unfortunately, however, it did not resolve the conjecture itself. The import from Friedgut’s main result was existence of a potentially nn-dependent sequence λn,k∗\lambda^*_{n,k} such that the probability of satisfiability is asymptotically one (asymptotically zero) when m/nm/n is asymptotically smaller (asymptotically larger) than λn,k∗\lambda^*_{n,k} and n→∞n \to\infty. In other words, while the sharpness of the transition was established, the convergence of its location was not, and as such the location could potentially fluctuate as a function of nn.

A dramatic progress towards resolving the conjecture was initiated in the field of statistical mechanics, specifically the field of spin glasses. Specifically, Guerra and Toninelli [11] invented an important interpolation technique, using which they proved the existence of the ground state energy limit for the so-called Sherrington-Kirkpatrick model. This approach was instrumental for validating the ground state energy value for this model, computed earlier by Parisi [19, 20] using non-rigorous replica symmetry breaking method. Specifically, the interpolation technique was used by Guerra [14] to prove that the value computed by Parisi is a correct upper bound on the limiting ground state energy value. The matching lower bound was established in a breakthrough work of Talagrand [21] and further developed in many follow up papers, see Panchenko [18].

Next, closer to the random kk-SAT setting, Franz and Leone [12] adapted the interpolation technique to the setting of diluted spin glass models, which includes random kk-SAT model as a special case. A corollary of their main result is the existence of the limiting value for the largest number of satisfiable clauses normalized by nn for the random kk-SAT formula. The largest number of satisfiable clauses is called the ground state energy in the statistical physics parlance. The interpolation technique employed in [11] and [12] implied superadditivity property of the expectation of the ground state energy: the expected ground state energy on the nn-variable model is at least the sum of the expected ground state energies of the n1n_1 and n2n_2-variable models when n=n1+n2n = n_1 + n_2. The existence of the limit was then a simple application of Fekete’s Lemma. Both papers relied on introducing positive temperature parameter in the respective models and then taking the temperature value to zero in the limit.

The next development came from Bayati, Gamarnik and Tetali [4] who adapted Franz and Leone’s interpolation technique directly to the zero-temperature optimization problems. The results in this paper had implications for the satisfiability property of random kk-SAT formulas per se. Specifically, log-superadditivity of the satisfiability property was established there, see Theorem 3.7 below. This result is at the core of the main approach developed by OpenAI in [17], as is explained in the main body of the present paper. Shortly after and independently, Abbe and Montanari [1] adapted Franz and Leone’s technique for establishing a concentration property for the number of satisfying assignments when conditioned on the satisfiability of the formula. They also proved in the same paper that a concentration property stronger than one they managed to obtain would imply the validity of the kk-SAT conjecture. This is the approach successfully pursued by Carenini in [5]. A useful technical part of [1] was a variant of the superadditivity property which was also adapted by the OpenAI solution, see Proposition 3.10 below. A key novelty of the Carenini’s approach was obtaining a sharp bound on width of the Friedgut’s phase transition window.

The next major progress towards the full resolution of the conjecture was achieved in Ding, Sly and Sun [9, 10] who proved the validity of the conjecture for all sufficiently large values of kk. Their approach was based on very refined version of the second moment method and is technically quite involved. The upshot of this work was not only a positive resolution of the conjecture for large kk but also the validation of the phase transition values λk∗\lambda_k^*. These values were produced earlier in the statistical physics literature by Mertens, Mézard and Zecchina [16] also using the replica symmetry breaking method. It is worth mentioning that while the values produced by the replica symmetry breaking method have been confirmed in many papers such as [21] and [9, 10], the method itself remains a heuristic lacking a rigorous mathematical justification. The progress in [9, 10] which took place a decade ago was the last progress until the full resolution of the conjecture this year in [5] and [17].

Next we provide a brief outline of the proof. As in [4] a key technical object employed by the OpenAI proof is the concept of a frozen variable. A Boolean variable xix_i in the kk-SAT formula is defined to be frozen when the formula is satisfiable, but every satisfying solution fixes it as the same Boolean value, for example always at 0 or always at 1. The first technical step is then an upper bound on the number of frozen variables. As shown in Proposition 3.2, it is O(n1/k)O(n^{1/k}) in expectation. This bound on the expected number of frozen variables is used next to obtain a bound on the variance of the hitting time HnH_n associated with random formulas. The hitting time HnH_n is a random variable defined by considering the random kk-SAT formula as a discrete time process indexed by mm, and constructed by adding one clause at a time. HnH_n is then defined as largest value of mm for which the formula remains satisfiable, see Subsection 3.1. A bound O(n1/k)O(n^{1/k}) on the expected number of frozen variables is used for obtaining an upper bound O(n1+2/k)O(n^{1+2/k}) on the variance of HnH_n, as stated in Proposition 3.5. The well-known Efron-Stein-SteeIe inequality Theorem 3.3 is used towards the proof of this bound. A direct application of Chebyshev’s inequality also implies concentration property of the hitting time HnH_n, as stated in (7). The concentration of the hitting time property allows one to relate the expected value E[Hn]\mathbb{E}[H_n] of the hitting time to its median value, namely the largest value of mm for which the likelihood of satisfiability is at least 1/21/2. This is the subject of Lemma 3.6. The log-superadditivity property established in [4] is then used for establishing superadditivity of the median times as articulated in Corollary 3.8. The final step in the proof is adaptation of the variant of the superadditivity property developed in [1]. This is the subject of Proposition 3.10 and this completes the description of the proof. Remarkably, as in the proof by Carenini in [5], the approach does not assume the validity of the Friedgut’s sharp transition property and instead obtains it as an immediate corollary. One should stress, however, that the scope of the applicability of Friedgut’s theorem is much broader than the random kk-SAT formula setting.

The remainder of the paper is organized as follows. The model description and the main theorem are stated in the next section. The proof of the main theorem is the subject of § 3, where the concepts of frozen variables and hitting times are introduced in the beginning. § 4 presents some remaining open questions.

Definitions and the main result

Consider nn Boolean variables xix_i, i∈[n]i \in[n] taking values 0 and 1. We fix kk which is clause size. A formula ϕ\phi is a conjunction of some mm kk-clauses: ϕ=⋀1≤j≤mCj\phi= \bigwedge_{1 \le j \le m} C_j where each clause CjC_j is disjunction of kk of the nn variables x1,…,xnx_1,\ldots,x_n or their negations x‾1,…,x‾n\overline{x}_1,\ldots,\overline{x}_n. Thus for each jj there exists a subset Ij+⊂[n]I_j^+ \subset[n] (corresponding to variables without negation), and a subset Ij−⊂[n]I_j^- \subset[n] (corresponding to negated variables), such that ∣Ij+∣+∣Ij−∣=k\lvert I_j^+\rvert+ \lvert I_j^-\rvert= k, Ij+∩Ij−=∅I_j^+ \cap I_j^- = \varnothing and

Cj=(⋁i∈Ij+xi)∨(⋁i∈Ij−x‾i)C_j = \left(\bigvee_{i \in I_j^+} x_i\right) \vee\left(\bigvee_{i \in I_j^-} \overline{x}_i\right)

We call Ij=Ij+∪Ij−⊂[n]I_j = I_j^+ \cup I_j^- \subset[n] the support of the clause CjC_j. A formula ϕ\phi is satisfiable if there exists a setting of the variables xix_i which satisfies the formula. Namely, if there exists a vector x=(x1,…,xn)∈{0,1}nx = (x_1,\ldots,x_n) \in\{0,1\}^n such that all clauses CjC_j evaluate to 1 at this xx. Such a setting, when it exists, is called a satisfying assignment or a satisfying solution. We note that for each clause there exists only a single assignment of variables to kk values which do not satisfy the clause. When the formula is satisfiable we write ϕ∈SAT\phi\in\mathrm{SAT}. When it is not satisfiable we write ϕ∉SAT\phi\notin\mathrm{SAT}.

A random formula with nn variables and mm clauses, denoted by Φ(n,m)\Phi(n,m), is obtained by generating the supports IjI_j uniformly at random from all (nk)\binom{n}{k} choices, and letting Ij+I_j^+ (and thus Ij−I_j^-) be chosen uniformly at random from 2k2^k choices as well, also independently from everything else. We denote by p(n,m)p(n,m) the probability that Φ(n,m)\Phi(n,m) is sat: p(n,m)=P(Φ(n,m)∈SAT)p(n,m) = \mathbb{P}(\Phi(n,m) \in\mathrm{SAT}). The Satisfiability Conjecture asserted existence of a fixed threshold λ∗>0\lambda^* > 0 such that p(n,m)p(n,m) approaches 1 when m/nm/n stays uniformly smaller than λ∗\lambda^*, and approaches 0 when this ratio stays uniformly larger than λ∗\lambda^*, as nn diverges to infinity. The OpenAI paper [17] established precisely this which we now state as a formal theorem.

Theorem 2.1 (Theorem 1.1, [17]). For every k≥3k \ge3 there exists λk∗>0\lambda_k^* > 0 such that for every 0≤λ<λk∗0 \le\lambda< \lambda_k^*, lim⁡n→∞p(n,⌈λn⌉)=1\lim_{n \to\infty} p(n,\lceil\lambda n\rceil) = 1 and for every λ>λk∗\lambda> \lambda_k^*, lim⁡n→∞p(n,⌈λn⌉)=0\lim_{n \to\infty} p(n,\lceil\lambda n\rceil) = 0.

As stated in the introduction, the sharp transition result of Friedgut [13] will not be used in the proof of Theorem 2.1. Conversely, it is an immediate implication of Theorem 2.1.

Proof of Theorem 2.1

Preliminaries

We begin by reducing the problem to the case of clauses generated with replacement. Specifically, consider a modified model of the random formula Φ(n,m)\Phi(n,m) where replacement of variables is now allowed. Here a random clause CC is formed by selecting kk variables from the list x1,…,xn,x‾1,…,x‾nx_1,\ldots,x_n,\overline{x}_1,\ldots,\overline{x}_n independently and uniformly at random with replacement. The modified formula, denoted by Φwr(n,m)\Phi_{\mathrm{wr}}(n,m) (where wr stands for ”with replacement”), is then obtained by generating mm clauses with replacement independently, as in the original version. Let pwr(n,m)=P(Φwr(n,m)∈SAT)p_{\mathrm{wr}}(n,m)=\mathbb{P}(\Phi_{\mathrm{wr}}(n,m)\in\mathrm{SAT}). We claim that it suffices to establish Theorem 2.1 with pwr(n,m)p_{\mathrm{wr}}(n,m) replacing p(n,m)p(n,m). Specifically, suppose for every k≥3k\ge3 there exists λk,wr∗\lambda^{*}_{k,\mathrm{wr}} such that for every λ<λk,wr∗\lambda<\lambda^{*}_{k,\mathrm{wr}}, lim⁡n→∞pwr(n,⌈λn⌉)=1\lim_{n\to\infty}p_{\mathrm{wr}}(n,\lceil\lambda n\rceil)=1 and for every λ>λk,wr∗\lambda>\lambda^{*}_{k,\mathrm{wr}}, lim⁡n→∞pwr(n,⌈λn⌉)=0\lim_{n\to\infty}p_{\mathrm{wr}}(n,\lceil\lambda n\rceil)=0. Based on this assumption we now show the validity of Theorem 2.1 for the same limiting threshold λk∗=λk,wr∗\lambda^{*}_{k}=\lambda^{*}_{k,\mathrm{wr}}. The validity of this claim follows from a standard fact from the theory of random graphs that the collisions stemming from possible replacements occur with probability bounded away from zero across the entire formula. Specifically, let NC\mathcal{N}C (No-Collision) be the event that no single clause out of the mm clauses of the random formula Φwr(n,m)\Phi_{\mathrm{wr}}(n,m) contains repeated variables (with or without negation). For example, no clause can contain a variable xix_i twice or variables xix_i and xˉi\bar{x}_i simultaneously. It is straightforward to check that for every constant C>0C>0 there exist a>0a>0 such that lim inf⁡nmin⁡m≤CnP(NC)≥a\liminf_{n}\min_{m\le Cn}\mathbb{P}(\mathcal{N}C)\ge a. Furthermore, conditioned on the event NC\mathcal{N}C, the formula Φwr(n,m)\Phi_{\mathrm{wr}}(n,m) is distributed as Φ(n,m)\Phi(n,m).

Now, fix any λ<λk,wr∗\lambda<\lambda^{*}_{k,\mathrm{wr}}. Then

p(n,⌈λn⌉)=P(Φ(n,⌈λn⌉)∈SAT)=P(Φwr(n,⌈λn⌉)∈SAT∣NC)=P(Φwr(n,⌈λn⌉)∈SAT,NC)P(NC)=P(NC)−P(Φwr(n,⌈λn⌉)∉SAT,NC)P(NC).\begin{aligned} p(n,\lceil\lambda n\rceil)&=\mathbb{P}(\Phi(n,\lceil\lambda n\rceil)\in\mathrm{SAT})\\ &=\mathbb{P}(\Phi_{\mathrm{wr}}(n,\lceil\lambda n\rceil)\in\mathrm{SAT}\mid\mathcal{N}C)\\ &=\frac{\mathbb{P}(\Phi_{\mathrm{wr}}(n,\lceil\lambda n\rceil)\in\mathrm{SAT},\mathcal{N}C)}{\mathbb{P}(\mathcal{N}C)}\\ &=\frac{\mathbb{P}(\mathcal{N}C)-\mathbb{P}(\Phi_{\mathrm{wr}}(n,\lceil\lambda n\rceil)\notin\mathrm{SAT},\mathcal{N}C)}{\mathbb{P}(\mathcal{N}C)}. \end{aligned}

We have

P(Φwr(n,⌈λn⌉)∉SAT,NC)≤P(Φwr(n,⌈λn⌉)∉SAT)=1−pwr(n,⌈λn⌉).\mathbb{P}(\Phi_{\mathrm{wr}}(n,\lceil\lambda n\rceil)\notin\mathrm{SAT},\mathcal{N}C)\le\mathbb{P}(\Phi_{\mathrm{wr}}(n,\lceil\lambda n\rceil)\notin\mathrm{SAT})=1-p_{\mathrm{wr}}(n,\lceil\lambda n\rceil).

By our assumption, the right-hand side converges to zero as n→∞n\to\infty. Since P(NC)≥a>0\mathbb{P}(\mathcal{N}C)\ge a>0, we conclude lim⁡np(n,⌈λn⌉)=1\lim_{n}p(n,\lceil\lambda n\rceil)=1.

Similarly, assume λ>λk,wr∗\lambda>\lambda^{*}_{k,\mathrm{wr}}. Then

p(n,⌈λn⌉)=P(Φ(n,⌈λn⌉)∈SAT)=P(Φwr(n,⌈λn⌉)∈SAT∣NC)=P(Φwr(n,⌈λn⌉)∈SAT,NC)P(NC)≤P(Φwr(n,⌈λn⌉)∈SAT)P(NC)≤pwr(n,⌈λn⌉)a.\begin{aligned} p(n,\lceil\lambda n\rceil)&=\mathbb{P}(\Phi(n,\lceil\lambda n\rceil)\in\mathrm{SAT})\\ &=\mathbb{P}(\Phi_{\mathrm{wr}}(n,\lceil\lambda n\rceil)\in\mathrm{SAT}\mid\mathcal{N}C)\\ &=\frac{\mathbb{P}(\Phi_{\mathrm{wr}}(n,\lceil\lambda n\rceil)\in\mathrm{SAT},\mathcal{N}C)}{\mathbb{P}(\mathcal{N}C)}\\ &\le\frac{\mathbb{P}(\Phi_{\mathrm{wr}}(n,\lceil\lambda n\rceil)\in\mathrm{SAT})}{\mathbb{P}(\mathcal{N}C)}\\ &\le\frac{p_{\mathrm{wr}}(n,\lceil\lambda n\rceil)}{a}. \end{aligned}

By our assumption lim⁡npwr(n,⌈λn⌉)=0\lim_{n}p_{\mathrm{wr}}(n,\lceil\lambda n\rceil)=0. We conclude lim⁡n→∞p(n,⌈λn⌉)=0\lim_{n\to\infty}p(n,\lceil\lambda n\rceil)=0. This completes the proof of the claim.

The remainder of the paper is thus devoted to establishing Theorem 2.1 for pwr(n,m)p_{\mathrm{wr}}(n,m) replacing p(n,m)p(n,m). For simplicity, we denote Φwr(n,m)\Phi_{\mathrm{wr}}(n,m) and pwr(n,m)p_{\mathrm{wr}}(n,m) by Φ(n,m)\Phi(n,m) and p(n,m)p(n,m), respectively, throughout the rest of the paper.

Next we introduce the concepts of hitting times and frozen variables. We begin by defining hitting times. Given nn and mm let ZZ denote the (random) number of solutions satisfying the formula Φ(n,m)\Phi(n,m). A straightforward computation shows E[Z]=2n(1−1/2k)m\mathbb{E}[Z] = 2^n(1 - 1/2^k)^m. By Markov inequality p(n,m)≤E[Z]p(n,m) \le\mathbb{E}[Z]. When m≥2knm \ge2^k n, we obtain

p(n,m)≤2n(1−1/2k)m≤(2e−1)n<1/2p(n,m) \le2^n(1 - 1/2^k)^m \le(2e^{-1})^n < 1/2

for all sufficiently large nn. Define m(n)m(n) as the largest mm such that p(n,m)≥1/2p(n,m) \ge1/2. Then p(n,m(n)+1)<1/2p(n,m(n) + 1) < 1/2. By the above m(n)<2knm(n) < 2^k n for all nn. Let λn=m(n)/n\lambda_n = m(n)/n. Then for all nn, λn<2k\lambda_n < 2^k. In particular, λn=O(1)\lambda_n = O(1). It is well known that for all ϵ>0\epsilon> 0, lim inf⁡nλn≥1−ϵ\liminf_n \lambda_n \ge1 - \epsilon and thus for some n0n_0 and all n≥n0n \ge n_0

1/2≤λn≤2k.(1)1/2 \le\lambda_n \le2^k. \tag*{(1)}

See for example [6] which shows that for k=2k = 2, λn→1\lambda_n \to1 with high concentration around λn\lambda_n for the version without replacement. By the equivalence property above the same applies to the model with replacement. Finally, we use λn,k≤λn,k+1\lambda_{n,k} \le\lambda_{n,k+1} to assert (1).

Let HnH_n be the hitting time defined as follows. Consider the random formula Φ(n,2k+1n)\Phi(n,2^{k+1}n) and the associated stochastic process (Φ(n,m),0≤m≤2k+1n)(\Phi(n,m), 0 \le m \le2^{k+1}n). Define

Hn=max⁡{m≤2k+1n:Φ(n,m)∈SAT}.H_n = \max\{m \le2^{k+1}n : \Phi(n,m) \in\mathrm{SAT}\}.

Namely HnH_n is the largest index of a clause which maintains the satisfiability property, capped at 2k+1n2^{k+1}n. Then for all m≤2k+1nm \le2^{k+1}n we have p(n,m)=P(Hn≥m)p(n,m) = \mathbb{P}(H_n \ge m). Thus m(n)m(n) is the median of the random variable HnH_n and λn\lambda_n is median normalized by nn.

Next we define frozen variables. Given a formula ϕ\phi defined on variables x1,…,xnx_1,\ldots,x_n, a variable xix_i is called frozen if it takes the same value for all satisfying assignments. Namely xix_i, i∈[n]i \in[n] is frozen if either xi=0x_i = 0 for all satisfying solutions (x1,…,xn)∈{0,1}n(x_1,\ldots,x_n) \in\{0,1\}^n, or xi=1x_i = 1 for all satisfying solutions (x1,…,xn)∈{0,1}n(x_1,\ldots,x_n) \in\{0,1\}^n. If the formula is not satisfiable, (and thus the number of satisfying assignments is empty), the set of frozen variables is empty. Given a satisfiable formula ϕ\phi and a clause CC note that the modified formula ϕ∧C\phi\wedge C is not satisfiable if and only if every variable in the support of CC is frozen and its parity agrees with the value of the frozen variable. For example, if C=(x3∨x‾7∨x‾8)C = (x_3 \vee\overline{x}_7 \vee\overline{x}_8) then ϕ∧C\phi\wedge C is not satisfiable if and only if variables x3,x7,x8x_3,x_7,x_8 are frozen to values 0,1,10,1,1 respectively.

Let 0≤f(ϕ)≤n0 \le f(\phi) \le n denote the number of frozen variables in formula ϕ\phi. We adopt the convention that f(ϕ)=0f(\phi) = 0 when ϕ\phi is not satisfiable. Note that for every formula ϕ\phi, (f(ϕ)/(2n))k(f(\phi)/(2n))^k is precisely the probability that the modified formula ϕ∧C\phi\wedge C is not satisfiable when CC is a kk-clause chosen uniformly at random. We write qk(ϕ)=(f(ϕ)/(2n))kq_k(\phi) = (f(\phi)/(2n))^k for short.

Controlling frozen variables

The goal of this subsection is to obtain an upper bound on the number of frozen variables in a random formula Φ(n,m)\Phi(n,m). In particular, we will establish in Proposition 3.2 below that the expected number of the frozen variables in formula Φ(n,m)\Phi(n,m) is order n1/kn^{1/k} on average when we average over the number of clauses mm in the range [0,2k+1n][0,2^{k+1}n].

We begin with a preliminary lemma. It shows that, modulo order n−(k−1)/kn^{-(k-1)/k} correction term, for every satisfiable formula ϕ\phi, appending this formula with a k−1k-1 clause chosen uniformly at random leads to a higher chance of maintaining satisfiability vs appending it with order n1/kn^{1/k} many kk-clauses also chosen uniformly at random and independently.

Lemma 3.1. Let ϕ\phi be any fixed formula on nn variables. Let C0C_0 be a k−1k-1-clause chosen uniformly at random and let C1,…,CRC_1,\ldots,C_R be kk-clauses chosen independently uniformly at random. Suppose R≥2n1kR \ge2n^{\frac{1}{k}}. There exists sufficiently large n0n_0 such that for all n≥n0n \ge n_0

P(ϕ∧C0∈SAT)≥P(ϕ∧(⋀1≤j≤RCj)∈SAT)−n−k−1k.(2)\mathbb{P}(\phi\wedge C_0 \in\mathrm{SAT}) \ge\mathbb{P}\left(\phi\wedge\left(\bigwedge_{1\le j\le R} C_j\right) \in\mathrm{SAT}\right) - n^{-\frac{k-1}{k}}. \tag*{(2)}

Proof. The claim holds trivially when ϕ\phi is not satisfiable. Thus assume ϕ\phi is satisfiable. Suppose first f(ϕ)/(2n)≤n−1kf(\phi)/(2n) \le n^{-\frac{1}{k}}. Then P(ϕ∧C0∈SAT)=1−(f(ϕ)/(2n))k−1≥1−n−k−1k\mathbb{P}(\phi\wedge C_0 \in\mathrm{SAT}) = 1 - (f(\phi)/(2n))^{k-1} \ge1 - n^{-\frac{k-1}{k}}, and the claim holds trivially.

Thus suppose f(ϕ)/(2n)≥n−1kf(\phi)/(2n) \ge n^{-\frac{1}{k}}. Then

R(f(ϕ)/(2n))k≥2n1k(f(ϕ)/(2n))k=2n1k(f(ϕ)/(2n))(f(ϕ)/(2n))k−1≥2(f(ϕ)/(2n))k−1.\begin{aligned} R(f(\phi)/(2n))^k &\ge2n^{\frac{1}{k}}(f(\phi)/(2n))^k \\ &= 2n^{\frac{1}{k}}(f(\phi)/(2n))(f(\phi)/(2n))^{k-1} \\ &\ge2(f(\phi)/(2n))^{k-1}. \end{aligned}

Then

P(ϕ∧(⋀1≤j≤RCj)∈SAT)≤P(⋂1≤j≤R(ϕ∧Cj∈SAT))=(1−(f(ϕ)2n)k)R≤e−R(f(ϕ)/(2n))k≤e−2(f(ϕ)/(2n))k−1≤1−(f(ϕ)/(2n))k−1=P(ϕ∧C0∈SAT),\begin{aligned} \mathbb{P}\left(\phi\wedge\left(\bigwedge_{1\le j\le R} C_j\right) \in\mathrm{SAT}\right) &\le\mathbb{P}\left(\bigcap_{1\le j\le R}(\phi\wedge C_j \in\mathrm{SAT})\right) \\ &= \left(1-\left(\frac{f(\phi)}{2n}\right)^k\right)^R \\ &\le e^{-R(f(\phi)/(2n))^k} \\ &\le e^{-2(f(\phi)/(2n))^{k-1}} \\ &\le1-(f(\phi)/(2n))^{k-1} \\ &= \mathbb{P}(\phi\wedge C_0 \in\mathrm{SAT}), \end{aligned}

where we use (f(ϕ)/(2n))k≤1/2k−1≤1/2(f(\phi)/(2n))^k \le1/2^{k-1} \le1/2 and e−2x≤1−xe^{-2x} \le1-x for x∈[0,1/2]x \in[0,1/2].

The following bound shows that for random formulas on nn variables the number of frozen variables is at most order n1kn^{\frac{1}{k}} “on average” when we average over mm in the range [0,2k+1n][0,2^{k+1}n].

Proposition 3.2. For every kk there exists a constant ckc_k and n0n_0 such that for all n≥n0n \ge n_0

∑0≤m≤2k+1nE[f(Φ(n,m))]n≤ckn1k.\sum_{0\le m\le2^{k+1}n}\frac{\mathbb{E}[f(\Phi(n,m))]}{n} \le c_k n^{\frac{1}{k}}.

Proof. Fix m≤2k+1nm \le2^{k+1}n. By symmetry E[f(Φ(n,m))]/n\mathbb{E}[f(\Phi(n,m))]/n equals the probability that Φ(n,m)\Phi(n,m) is satisfiable and the variable xnx_n is frozen, since when Φ(n,m)\Phi(n,m) is not satisfiable, f(Φ(n,m))=0f(\Phi(n,m))=0 by assumption. Let Φ−n\Phi_{-n} be the part of this formula spanned by the first n−1n-1 variables x1,…,xn−1x_1,\ldots,x_{n-1}. Consider the clauses C1,…,CDC_1,\ldots,C_D containing the variable xnx_n (where DD is random), so that Φ(n,m)=Φ−n∧(⋀1≤j≤DCj)\Phi(n,m)=\Phi_{-n}\wedge\left(\bigwedge_{1\le j\le D}C_j\right). Consider the clauses C^j\widehat{C}_j, 1≤j≤D1\le j\le D obtained from CjC_j, 1≤j≤D1\le j\le D by deleting variable xnx_n. Each clause has at most k−1k-1 variables. Specifically, the clause size C^j\widehat{C}_j is strictly less than k−1k-1 if variable xnx_n appears in CjC_j more than once. Let Ck−1C_{k-1} be the event that all clauses C^j\widehat{C}_j, 1≤j≤D1\le j\le D have size k−1k-1. We can find constant c>0c>0 such that P(Ck−1)≥1−c/n\mathbb{P}(C_{k-1})\ge1-c/n uniformly in m≤2k+1nm\le2^{k+1}n.

::: Next, we make the following observation: if xnx_n is a frozen variable in Φ(n,m)\Phi(n,m) then Φ−n\Phi_{-n} is satisfiable (since Φ(n,m)\Phi(n,m) is), but the formula obtained by appending C^j,1≤j≤D\hat{C}_j, 1 \le j \le D is not satisfiable. That is Φ−n∈SAT\Phi_{-n} \in\mathrm{SAT}, but Φ^−n≜Φ−n∧(⋀1≤j≤DC^j)∉SAT\hat{\Phi}_{-n} \triangleq\Phi_{-n} \wedge\left(\bigwedge_{1\le j\le D}\hat{C}_j\right) \notin\mathrm{SAT}. Indeed, otherwise a satisfying assignment of Φ^(n,m)\hat{\Phi}(n,m) can be extended to a satisfying assignment of Φ(n,m)\Phi(n,m) with either choice xn=0x_n=0 or xn=1x_n=1, contradicting the assumption that xnx_n is frozen. Thus

E[f(Φ(n,m))]n=P(xn frozen)≤P(Φ−n∈SAT,Φ^−n∉SAT).(3)\frac{\mathbb{E}[f(\Phi(n,m))]}{n}=\mathbb{P}(x_n\text{ frozen})\le\mathbb{P}(\Phi_{-n}\in\mathrm{SAT},\hat{\Phi}_{-n}\notin\mathrm{SAT}). \tag*{(3)}

By earlier observation,

P(Φ−n∈SAT,Φ^−n∉SAT)≤P(Φ−n∈SAT,Φ^−n∉SAT∣Ck−1)+O(1/n).(4)\mathbb{P}(\Phi_{-n}\in\mathrm{SAT},\hat{\Phi}_{-n}\notin\mathrm{SAT})\le\mathbb{P}(\Phi_{-n}\in\mathrm{SAT},\hat{\Phi}_{-n}\notin\mathrm{SAT}\mid C_{k-1})+O(1/n). \tag*{(4)}

We now construct a sequence of modified formulas Φ^j\hat{\Phi}_j, 0≤j≤D0\le j\le D starting with Φ^0=Φ^−n\hat{\Phi}_0=\hat{\Phi}_{-n} as follows. For j=1,2,…,Dj=1,2,\ldots,D, the formula Φ^j\hat{\Phi}_j is obtained from Φ^j−1\hat{\Phi}_{j-1} by removing clause C^j\hat{C}_j and replacing it with R≜⌈2n1/k⌉R\triangleq\lceil2n^{1/k}\rceil kk-clauses Cj,1,…,Cj,RC_{j,1},\ldots,C_{j,R} on variables x1,…,xn−1x_1,\ldots,x_{n-1} and their negations. These clauses are generated uniformly at random independently and also independently from the all the other clauses.

Fix $0\le d\le m$. We note that conditionally on D=dD=d, Φ^D\hat{\Phi}_D is distributed as Φ(n−1,m−d+Rd)\Phi(n-1,m-d+Rd). Applying Lemma 3.1 we have for some constant n0n_0 for all n≥n0n\ge n_0 and for all $j=0,\ldots,d-1

P(Φ^j∈SAT∣D=d,Ck−1)≥P(Φ^j+1∈SAT∣D=d,Ck−1)−(n−1)−k−1k.\mathbb{P}(\hat{\Phi}_j\in\mathrm{SAT}\mid D=d,C_{k-1})\ge\mathbb{P}(\hat{\Phi}_{j+1}\in\mathrm{SAT}\mid D=d,C_{k-1})-(n-1)^{-\frac{k-1}{k}}.

Summing over jj we obtain that conditional on D=dD=d

P(Φ^−n∈SAT∣D=d,Ck−1)≥p(n−1,m−d+Rd)−d(n−1)−k−1k.\mathbb{P}(\hat{\Phi}_{-n}\in\mathrm{SAT}\mid D=d,C_{k-1})\ge p(n-1,m-d+Rd)-d(n-1)^{-\frac{k-1}{k}}.

On the other hand

P(Φ^−n∈SAT∣D=d,Ck−1)=P(Φ−n∈SAT∣D=d,Ck−1)−P(Φ−n∈SAT,Φ^−n∉SAT∣D=d,Ck−1).\mathbb{P}(\hat{\Phi}_{-n}\in\mathrm{SAT}\mid D=d,C_{k-1})=\mathbb{P}(\Phi_{-n}\in\mathrm{SAT}\mid D=d,C_{k-1})-\mathbb{P}(\Phi_{-n}\in\mathrm{SAT},\hat{\Phi}_{-n}\notin\mathrm{SAT}\mid D=d,C_{k-1}).

We obtain

P(Φ−n∈SAT,Φ^−n∉SAT∣D=d,Ck−1)≤P(Φ−n∈SAT∣D=d,Ck−1)−p(n−1,m−d+Rd)+d(n−1)−k−1k.\begin{aligned} \mathbb{P}(\Phi_{-n}\in\mathrm{SAT},\hat{\Phi}_{-n}\notin\mathrm{SAT}\mid D=d,C_{k-1}) &\le\mathbb{P}(\Phi_{-n}\in\mathrm{SAT}\mid D=d,C_{k-1})\\ &\quad-p(n-1,m-d+Rd)+d(n-1)^{-\frac{k-1}{k}}. \end{aligned}

We note

P(Φ−n∈SAT∣D=d,Ck−1)=p(n−1,m−d).\mathbb{P}(\Phi_{-n}\in\mathrm{SAT}\mid D=d,C_{k-1})=p(n-1,m-d).

We conclude

P(Φ−n∈SAT,Φ^−n∉SAT∣D=d,Ck−1)≤p(n−1,m−d)−p(n−1,m−d+Rd)+d(n−1)−k−1k.\mathbb{P}(\Phi_{-n}\in\mathrm{SAT},\hat{\Phi}_{-n}\notin\mathrm{SAT}\mid D=d,C_{k-1})\le p(n-1,m-d)-p(n-1,m-d+Rd)+d(n-1)^{-\frac{k-1}{k}}.

Summing over m=0,1,…,2k+1nm=0,1,\ldots,2^{k+1}n we obtain

∑d≤m≤2k+1nP(Φ−n∈SAT,Φ^−n∉SAT∣D=d,Ck−1)≤∑0≤m≤Rd−1p(n−1,m)+2k+1nd(n−1)−k−1k≤Rd+2k+1dn1k≤ck,1dn1k,\begin{aligned} \sum_{d\le m\le2^{k+1}n}\mathbb{P}(\Phi_{-n}\in\mathrm{SAT},\hat{\Phi}_{-n}\notin\mathrm{SAT}\mid D=d,C_{k-1}) &\le\sum_{0\le m\le Rd-1}p(n-1,m)+2^{k+1}nd(n-1)^{-\frac{k-1}{k}}\\ &\le Rd+2^{k+1}dn^{\frac{1}{k}}\\ &\le c_{k,1}dn^{\frac{1}{k}}, \end{aligned}

for some kk dependent constant ck,1c_{k,1}. Multiplying throughout by likelihood that D=dD=d we obtain

∑d≤m≤2k+1nP(Φ−n∈SAT,Φ^−n∉SAT,D=d∣Ck−1)≤ck,1n1kdmax⁡d≤m≤2k+1nPm(D=d∣Ck−1),\sum_{d\le m\le2^{k+1}n}\mathbb{P}(\Phi_{-n}\in\mathrm{SAT},\widehat{\Phi}_{-n}\notin\mathrm{SAT},D=d\mid\mathcal{C}_{k-1})\le c_{k,1}n^{\frac{1}{k}}d\max_{d\le m\le2^{k+1}n}\mathbb{P}_m(D=d\mid\mathcal{C}_{k-1}),

where subscript in Pm\mathbb{P}_m emphasizes that the probability depends on mm. For fixed mm the random variable DD has Binomial distribution with m=O(n)m=O(n) trials and success probability O(1/n)O(1/n). It is easy to see that ∑d≥0dmax⁡d≤m≤2k+1nPm(D=d∣Ck−1)≤ck,2<∞\sum_{d\ge0}d\max_{d\le m\le2^{k+1}n}\mathbb{P}_m(D=d\mid\mathcal{C}_{k-1})\le c_{k,2}<\infty. for some constant ck,2c_{k,2}. Summing over dd, we obtain

∑0≤m≤2k+1nP(Φ−n∈SAT,Φ^−n∉SAT∣Ck−1)≤ck,3n1k,\sum_{0\le m\le2^{k+1}n}\mathbb{P}(\Phi_{-n}\in\mathrm{SAT},\widehat{\Phi}_{-n}\notin\mathrm{SAT}\mid\mathcal{C}_{k-1})\le c_{k,3}n^{\frac{1}{k}},

and further using (4) we obtain

∑0≤m≤2k+1nP(Φ−n∈SAT,Φ^−n∉SAT)≤ck,3n1k+ck,4\sum_{0\le m\le2^{k+1}n}\mathbb{P}(\Phi_{-n}\in\mathrm{SAT},\widehat{\Phi}_{-n}\notin\mathrm{SAT})\le c_{k,3}n^{\frac{1}{k}}+c_{k,4}

for some constant ck,4c_{k,4}. Combining with (3) and (4) we complete the proof by increasing ckc_k to absorb the additive constant ck,4c_{k,4}.

Concentration of the hitting times HnH_n

The goal of this subsection is to establish a very important technical result: the hitting time HnH_n is concentrated around its expectation. Specifically, in Proposition 3.5 below we will show that the variance of HnH_n is at most order n1+2kn^{1+\frac{2}{k}}. The concentration then will follow directly by applying Chebyshev’s inequality.

Given formula Φ(n,2k+1n)\Phi(n,2^{k+1}n) and index 1≤j≤2k+1n1\le j\le2^{k+1}n let Φ−j\Phi_{-j} denote the formula Φ(n,2k+1n)\Phi(n,2^{k+1}n) with clause CjC_j omitted. Let H−jH_{-j} be the corresponding hitting time. To be precise, let C1,…,C2k+1nC_1,\ldots,C_{2^{k+1}n} be the clauses of Φ(n,2k+1n)\Phi(n,2^{k+1}n). Denote by Φm,−j\Phi_{m,-j} the formula ⋀1≤ℓ≤m,ℓ≠jCℓ\bigwedge_{1\le\ell\le m,\ell\ne j}C_\ell. Then

H−j=max⁡{m≤2k+1n:Φm,−j∈SAT}.H_{-j}=\max\{m\le2^{k+1}n:\Phi_{m,-j}\in\mathrm{SAT}\}.

We omit index nn for brevity. Also we write HH for HnH_n. Trivially H≤H−jH\le H_{-j} for all j≥1j\ge1. The following bound on the variance of HH is based on standard inequality known as Efron-Stein and Steele’s application of it to non-symmetric cases. We include the proof for completeness.

Theorem 3.3 (Efron-Stein-Steele bound). The following holds for all nn:

Var⁡(H)≤∑1≤j≤2k+1nE[(H−H−j)2].\operatorname{Var}(H)\le\sum_{1\le j\le2^{k+1}n}\mathbb{E}\left[(H-H_{-j})^2\right].

Proof. For j=0,1,…,2k+1nj=0,1,\ldots,2^{k+1}n denote by Fj\mathcal{F}_j the σ\sigma-field generated by randomness of C1,…,CjC_1,\ldots,C_j, where F0\mathcal{F}_0 is assumed to be the trivial σ\sigma-field. Note that HH is measurable with respect to F2k+1n\mathcal{F}_{2^{k+1}n}, since the realizations of CjC_j, 1≤j≤2k+1n1\le j\le2^{k+1}n uniquely determine the formula and the value of HH as a result. Introduce martingale differences for 1≤j≤2k+1n1\le j\le2^{k+1}n

Dj=E[H∣Fj]−E[H∣Fj−1]D_j=\mathbb{E}[H\mid\mathcal{F}_j]-\mathbb{E}[H\mid\mathcal{F}_{j-1}]

so that H−E[H]=∑1≤j≤2k+1nDjH-\mathbb{E}[H]=\sum_{1\le j\le2^{k+1}n}D_j. A standard property satisfied by martingale differences is the orthogonality: for all j≠ℓj\ne\ell E[DjDℓ]=0\mathbb{E}[D_jD_\ell]=0. It is a simple consequence of the tower property E[E[H∣Fj]∣Fℓ]=E[H∣Fℓ]\mathbb{E}[\mathbb{E}[H\mid\mathcal{F}_j]\mid\mathcal{F}_\ell]=\mathbb{E}[H\mid\mathcal{F}_\ell] for all j≥ℓj\ge\ell. Orthogonality implies

Var⁡(H)=∑1≤j≤2k+1nE[Dj2].(5)\operatorname{Var}(H)=\sum_{1\le j\le2^{k+1}n}\mathbb{E}[D_j^2]. \tag*{(5)}

Next, as H−jH_{-j} does not depend on CjC_j we have E[H−j∣Fj]=E[H−j∣Fj−1]\mathbb{E}[H_{-j}\mid\mathcal{F}_j]=\mathbb{E}[H_{-j}\mid\mathcal{F}_{j-1}], j≥1j\ge1 which means

Dj=E[H−H−j∣Fj]−E[H−H−j∣Fj−1].D_j=\mathbb{E}[H-H_{-j}\mid\mathcal{F}_j]-\mathbb{E}[H-H_{-j}\mid\mathcal{F}_{j-1}].

Applying the tower property we obtain

E[Dj2]=E[(E[H−H−j∣Fj])2]−E[(E[H−H−j∣Fj−1])2]≤E[(E[H−H−j∣Fj])2].\mathbb{E}[D_j^2]=\mathbb{E}\left[(\mathbb{E}[H-H_{-j}\mid\mathcal{F}_j])^2\right]-\mathbb{E}\left[(\mathbb{E}[H-H_{-j}\mid\mathcal{F}_{j-1}])^2\right]\le\mathbb{E}\left[(\mathbb{E}[H-H_{-j}\mid\mathcal{F}_j])^2\right].

Applying conditional Jensen’s inequality E[Dj2]≤E[(H−H−j)2]\mathbb{E}[D_j^2]\le\mathbb{E}[(H-H_{-j})^2]. Combining with (5) we complete the proof.

The next lemma relates the variance of the hitting time to the expectation of the number of frozen variables.

Lemma 3.4. The following holds for every j=1,2,…,2k+1nj=1,2,\ldots,2^{k+1}n

E[(H−H−j)2]≤2∑j≤m≤2k+1nE[min⁡(2k+1nqk(Φ(n,m−1)),1)].\mathbb{E}[(H-H_{-j})^2]\le2\sum_{j\le m\le2^{k+1}n}\mathbb{E}\left[\min(2^{k+1}nq_k(\Phi(n,m-1)),1)\right].

Proof. Fix 1≤j≤2k+1n1\le j\le2^{k+1}n. Recall our earlier notation Φm,−j\Phi_{m,-j} for m≥jm\ge j. This is the formula obtained from the first mm clauses of the clauses C1,…,C2k+1nC_1,\ldots,C_{2^{k+1}n} of Φ(n,2k+1n)\Phi(n,2^{k+1}n) with clause CjC_j omitted. Let Φm\Phi_m be the same formula without omitting CjC_j, so that Φm\Phi_m is Φ(n,m)\Phi(n,m) in distribution. Introduce the events

Am={Φm,−j∈SAT,Φm∉SAT}.A_m=\{\Phi_{m,-j}\in\mathrm{SAT},\Phi_m\notin\mathrm{SAT}\}.

This is precisely the event H<m≤H−jH<m\le H_{-j}. Then

H−j−H=∣{m:H<m≤H−j}∣=∑j≤m≤2k+1n1(Am).H_{-j}-H=\lvert\{m:H<m\le H_{-j}\}\rvert=\sum_{j\le m\le2^{k+1}n}1(A_m).

We obtain

E[(H−j−H)2]=E[(∑j≤m≤2k+1n1(Am))2]=∑j≤m≤2k+1nP(Am)+2∑j≤m<ℓ≤2k+1nP(Am∩Aℓ)≤2∑j≤m≤ℓ≤2k+1nP(Am∩Aℓ).(6)\begin{aligned} \mathbb{E}[(H_{-j}-H)^2] &=\mathbb{E}\left[\left(\sum_{j\le m\le2^{k+1}n}1(A_m)\right)^2\right]\\ &=\sum_{j\le m\le2^{k+1}n}\mathbb{P}(A_m)+2\sum_{j\le m<\ell\le2^{k+1}n}\mathbb{P}(A_m\cap A_\ell)\\ &\le2\sum_{j\le m\le\ell\le2^{k+1}n}\mathbb{P}(A_m\cap A_\ell). \tag*{(6)} \end{aligned}

Next we claim that for every ℓ≥m\ell\ge m

Am∩Aℓ=Am∩{Φℓ,−j∈SAT}.\mathcal{A}_m \cap\mathcal{A}_\ell= \mathcal{A}_m \cap\{\Phi_{\ell,-j} \in\mathrm{SAT}\}.

Indeed, since Aℓ⊂{Φℓ,−j∈SAT}\mathcal{A}_\ell\subset\{\Phi_{\ell,-j} \in\mathrm{SAT}\} then

Am∩Aℓ⊂Am∩{Φℓ,−j∈SAT}.\mathcal{A}_m \cap\mathcal{A}_\ell\subset\mathcal{A}_m \cap\{\Phi_{\ell,-j} \in\mathrm{SAT}\}.

On the other hand Am⊂{Φm∉SAT}⊂{Φℓ∉SAT}\mathcal{A}_m \subset\{\Phi_m \notin\mathrm{SAT}\} \subset\{\Phi_\ell\notin\mathrm{SAT}\}, the latter following from ℓ≥m\ell\ge m. This furnishes the other inclusion.

Consider the σ\sigma-field Fm,−j\mathcal{F}_{m,-j} generated by clauses CrC_r, 1≤r≤m1 \le r \le m, r≠jr \ne j. The randomness of clauses CjC_j as well as clauses Cm+1,…,C2k+1nC_{m+1},\ldots,C_{2^{k+1}n} is independent from this σ\sigma-field. Recall our notation qk(ϕ)=(f(ϕ)/(2n))kq_k(\phi) = (f(\phi)/(2n))^k. Then P(Am∣Fm,−j)=qk(Φm,−j)\mathbb{P}(\mathcal{A}_m \mid\mathcal{F}_{m,-j}) = q_k(\Phi_{m,-j}). Also Φℓ,−j∈SAT\Phi_{\ell,-j} \in\mathrm{SAT} implies Φm,−j∧Cr∈SAT\Phi_{m,-j} \land C_r \in\mathrm{SAT} for all m+1≤r≤ℓm+1 \le r \le\ell. Similarly, we have P(Φm,−j∧Cr∈SAT∣Fm,−j)=1−qk(Φm,−j)\mathbb{P}(\Phi_{m,-j} \land C_r \in\mathrm{SAT} \mid\mathcal{F}_{m,-j}) = 1 - q_k(\Phi_{m,-j}) for r≥m+1r \ge m+1. The events Am\mathcal{A}_m and Φm,−j∧Cr∈SAT\Phi_{m,-j} \land C_r \in\mathrm{SAT}, r=m+1,…,ℓr=m+1,\ldots,\ell are independent conditionally on Fm,−j\mathcal{F}_{m,-j}, since they depend on randomness of disjoint clauses, namely CjC_j and CrC_r, m+1,…,ℓm+1,\ldots,\ell. Thus

P(Am∩Aℓ∣Fm,−j)=P(Am∩{Φℓ,−j∈SAT}∣Fm,−j)≤qk(Φm,−j)(1−qk(Φm,−j))ℓ−m.\begin{aligned} \mathbb{P}(\mathcal{A}_m \cap\mathcal{A}_\ell\mid\mathcal{F}_{m,-j}) &= \mathbb{P}(\mathcal{A}_m \cap\{\Phi_{\ell,-j} \in\mathrm{SAT}\} \mid\mathcal{F}_{m,-j}) \\ &\le q_k(\Phi_{m,-j})(1-q_k(\Phi_{m,-j}))^{\ell-m}. \end{aligned}

Then

∑ℓ:m≤ℓ≤2k+1nP(Am∩Aℓ∣Fm,−j)≤∑ℓ:m≤ℓ≤2k+1nqk(Φm,−j)(1−qk(Φm,−j))ℓ−m≤min⁡(2k+1nqk(Φm,−j),1).\sum_{\ell:m\le\ell\le2^{k+1}n}\mathbb{P}(\mathcal{A}_m \cap\mathcal{A}_\ell\mid\mathcal{F}_{m,-j}) \le \sum_{\ell:m\le\ell\le2^{k+1}n}q_k(\Phi_{m,-j})(1-q_k(\Phi_{m,-j}))^{\ell-m} \le\min(2^{k+1}nq_k(\Phi_{m,-j}),1).

Taking the outer expectation with respect to Fm,−j\mathcal{F}_{m,-j} we obtain

∑ℓ:m≤ℓ≤2k+1nP(Am∩Aℓ)≤E[min⁡(2k+1nqk(Φm,−j),1)].\sum_{\ell:m\le\ell\le2^{k+1}n}\mathbb{P}(\mathcal{A}_m \cap\mathcal{A}_\ell) \le\mathbb{E}\left[\min(2^{k+1}nq_k(\Phi_{m,-j}),1)\right].

Summing over m=j,j+1,…,2k+1nm=j,j+1,\ldots,2^{k+1}n and using (6) we conclude the proof.

We are ready to state and prove the concentration of hitting times property.

Proposition 3.5. For every kk there exists large enough constant CkC_k such that Var⁡(Hn)≤Ckn1+2k\operatorname{Var}(H_n) \le C_k n^{1+\frac{2}{k}} for all nn. As a result for δ≜(k−2)/(4k)\delta\triangleq(k-2)/(4k) and η=(k−2)/(2k)\eta=(k-2)/(2k)

P(∣Hn−E[Hn]∣≥n1−δ)≤Ckn−η.(7)\mathbb{P}\left(\left|H_n-\mathbb{E}[H_n]\right| \ge n^{1-\delta}\right) \le C_k n^{-\eta}. \tag*{(7)}

While δ\delta and η\eta were simple to express in terms of kk, their detailed values are not of importance to the remainder of the proof. As we will see, it suffices to have 0<δ<10<\delta<1 and η>0\eta>0. The only adjustment is that the exponent δ\delta appearing in Corollary 3.8 in the next subsection would need to be reduced to a smaller positive value.

Proof. The tail bound (7) follows from the bound on variance Var⁡(Hn)\operatorname{Var}(H_n) immediately by Chebyshev’s inequality. Thus we focus on bounding the variance Var⁡(Hn)\operatorname{Var}(H_n). Using min⁡(z,1)≤z1/k\min(z,1) \le z^{1/k} for all z≥0z \ge0, we have

min⁡(2k+1nqk(Φ(n,m)),1)≤21+1/kn1/k(qk(Φ(n,m)))1/k=21+1/kn1/k(f(Φ(n,m))/n).\min\left(2^{k+1}nq_k(\Phi(n,m)),1\right) \le2^{1+1/k}n^{1/k}\left(q_k(\Phi(n,m))\right)^{1/k}=2^{1+1/k}n^{1/k}\left(f(\Phi(n,m))/n\right).

Applying Lemma 3.4 we obtain

E[(H−H−j)2]≤4n1/k∑j≤m≤2k+1nn−1E[f(Φ(n,m−1))].\mathbb{E}\left[(H-H_{-j})^2\right]\le4n^{1/k}\sum_{j\le m\le2^{k+1}n}n^{-1}\mathbb{E}\left[f(\Phi(n,m-1))\right].

Applying Proposition 3.2 we obtain

E[(H−H−j)2]≤4ckn2/k.\mathbb{E}\left[(H-H_{-j})^2\right]\le4c_kn^{2/k}.

Finally, using Efron-Stein-Steele bound Theorem 3.3 we obtain

Var⁡(H)≤4ck2k+1n1+2/k.\operatorname{Var}(H)\le4c_k2^{k+1}n^{1+2/k}.

This completes the proof by setting Ck=4ck2k+1C_k=4c_k2^{k+1}.

From concentration of HnH_n to superadditivity of the normalized medians

The main technical result for this section is establishing the superadditivity type property for the normalized median times λn\lambda_n which is subject of Corollary 3.8, as well as continuity of the median times in nn. Specifically, in Lemma 3.9 we establish that λn+1\lambda_{n+1} is close to λn\lambda_n. We begin by showing the proximity of mean and median of the hitting times.

Lemma 3.6. Let δ=(k−2)/(4k)\delta=(k-2)/(4k) be as in Proposition 3.5. There exists n0n_0 such that for all n≥n0n\ge n_0

∣E[Hn]−λnn∣≤2n1−δ.\left|\mathbb{E}[H_n]-\lambda_n n\right|\le2n^{1-\delta}.

As we will see in the proof, the choice of multiplier 2 is somewhat arbitrary and any constant strictly larger than 1 suffices.

Proof. Suppose first E[Hn]≥λnn+2n1−δ\mathbb{E}[H_n]\ge\lambda_n n+2n^{1-\delta}. Then by Proposition 3.5 P(Hn≤λnn+n1−δ)≤n−η\mathbb{P}(H_n\le\lambda_n n+n^{1-\delta})\le n^{-\eta}. On the other hand

12>p(n,λnn+1)=P(Hn≥λnn+1),\frac{1}{2}>p(n,\lambda_n n+1)=\mathbb{P}(H_n\ge\lambda_n n+1),

implying

P(Hn≤λnn+n1−δ)≥P(Hn≤λnn+1)>12>n−η,\mathbb{P}(H_n\le\lambda_n n+n^{1-\delta})\ge\mathbb{P}(H_n\le\lambda_n n+1)>\frac{1}{2}>n^{-\eta},

for large enough nn which is a contradiction. We conclude E[Hn]≤λnn+2n1−δ\mathbb{E}[H_n]\le\lambda_n n+2n^{1-\delta}.

Conversely, suppose E[Hn]≤λnn−2n1−δ\mathbb{E}[H_n]\le\lambda_n n-2n^{1-\delta}. Then P(Hn≥λnn−n1−δ)≤n−η\mathbb{P}(H_n\ge\lambda_n n-n^{1-\delta})\le n^{-\eta}. On the other hand

12≤p(n,λnn)=P(Hn≥λnn)≤P(Hn≥λnn−n1−δ),\frac{1}{2}\le p(n,\lambda_n n)=\mathbb{P}(H_n\ge\lambda_n n)\le\mathbb{P}(H_n\ge\lambda_n n-n^{1-\delta}),

which is again a contradiction when n−η<1/2n^{-\eta}<1/2. We conclude E[Hn]≥λnn−2n1−δ\mathbb{E}[H_n]\ge\lambda_n n-2n^{1-\delta}.

Next we import the following superadditivity result from [4] based on the combinatorial interpolation technique. We reproduce the proof for completeness. This result is at the core of establishing the satisfiability limit as stated in our main result, Theorem 2.1.

Theorem 3.7. Given n,n1,n2n,n_1,n_2 such that n=n1+n2n=n_1+n_2 and given mm, let random variables M,M1,M2M,M_1,M_2 have Poisson distributions with means m,(n1/n)m,(n2/n)mm,(n_1/n)m,(n_2/n)m, respectively. Then

E[p(n,M)]≥E[p(n1,M1)]E[p(n2,M2)],\mathbb{E}[p(n,M)] \ge\mathbb{E}[p(n_1,M_1)]\mathbb{E}[p(n_2,M_2)],

where the expectations of p(n,M)p(n,M) and p(nj,Mj)p(n_j,M_j), j=1,2j=1,2 are with respect to the randomness of M,MjM,M_j, j=1,2j=1,2.

Proof. Consider the random formula Φ(n,M)\Phi(n,M). On the event M>0M>0 we consider the following process indexed by time t=1,…,Mt=1,\ldots,M. We order MM clauses uniformly at random and independently from any other randomness of the formula. For each tt we delete the tt-th clause CtC_t. We then generate a new kk-clause C^t\widehat{C}_t as follows. With probability n1/nn_1/n this clause is generated uniformly at random with replacement from the set of variables x1,…,xn1x_1,\ldots,x_{n_1} and their negations. With the remaining probability n2/nn_2/n the clause is generated uniformly at random with replacement from the set of variables xn1+1,…,xnx_{n_1+1},\ldots,x_n and their negations. If M=0M=0 we do nothing. Let Φt\Phi_t, t=0,1,…,Mt=0,1,\ldots,M be the random formula obtained at time tt, after clause CtC_t is deleted and C^t\widehat{C}_t is created. In particular, Φ0=Φ(n,M)\Phi_0=\Phi(n,M). Also by the Poisson splitting theorem, the formula ΦM\Phi_M at the end of the process is a disjoint union of independent formulas Φj\Phi_j, j=1,2j=1,2 on the two sets of nodes 1,…,n11,\ldots,n_1 and n1+1,…,nn_1+1,\ldots,n, respectively, where Φj\Phi_j is distributed as Φ(nj,Mj)\Phi(n_j,M_j) for j=1,2j=1,2.

Fix T>0T>0 and condition on M=TM=T. We claim that for every 1≤t≤T1\le t\le T

P(Φt−1∈SAT∣M=T)≥P(Φt∈SAT∣M=T),(8)\mathbb{P}(\Phi_{t-1}\in\mathrm{SAT}\mid M=T)\ge\mathbb{P}(\Phi_t\in\mathrm{SAT}\mid M=T), \tag*{(8)}

from which the assertion of the theorem follows.

Let ΔΦt\Delta\Phi_t be the random formula obtained after deleting clause CtC_t but before adding the clause C^t\widehat{C}_t. Then Φt−1=ΔΦt∧Ct\Phi_{t-1}=\Delta\Phi_t\wedge C_t and Φt=ΔΦt∧C^t\Phi_t=\Delta\Phi_t\wedge\widehat{C}_t. We condition on the realization ϕ\phi of ΔΦt\Delta\Phi_t. Note that CtC_t and C^t\widehat{C}_t are independent from ϕ\phi. Assume first ϕ\phi is satisfiable formula. Then

P(ϕ∧Ct∉SAT)=(f(ϕ)2n)k.\mathbb{P}(\phi\wedge C_t\notin\mathrm{SAT})=\left(\frac{f(\phi)}{2n}\right)^k.

For j=1,2j=1,2, let fj(ϕ)f_j(\phi) be the number of frozen variables of the formula ϕ\phi in subsets 1,…,n11,\ldots,n_1 and n1+1,…,nn_1+1,\ldots,n, respectively. Then

P(ϕ∧C^t∉SAT)=n1n(f1(ϕ)2n1)k+n2n(f2(ϕ)2n2)k.(9)\mathbb{P}(\phi\wedge\widehat{C}_t\notin\mathrm{SAT})= \frac{n_1}{n}\left(\frac{f_1(\phi)}{2n_1}\right)^k+ \frac{n_2}{n}\left(\frac{f_2(\phi)}{2n_2}\right)^k. \tag*{(9)}

Using the convexity of the function xkx^k when restricted to the domain x≥0x\ge0, the right-hand side is at least

(n1nf1(ϕ)2n1+n2nf2(ϕ)2n2)k=(f1(ϕ)+f2(ϕ)2n)k=P(ϕ∧Ct∉SAT).(10)\left(\frac{n_1}{n}\frac{f_1(\phi)}{2n_1}+\frac{n_2}{n}\frac{f_2(\phi)}{2n_2}\right)^k = \left(\frac{f_1(\phi)+f_2(\phi)}{2n}\right)^k =\mathbb{P}(\phi\wedge C_t\notin\mathrm{SAT}). \tag*{(10)}

We conclude P(ϕ∧C^t∉SAT)≥P(ϕ∧Ct∉SAT)\mathbb{P}(\phi\wedge\widehat{C}_t\notin\mathrm{SAT})\ge\mathbb{P}(\phi\wedge C_t\notin\mathrm{SAT}). On the other hand, when formula ϕ\phi is not satisfiable, we have P(ϕ∧C^t∈SAT)=P(ϕ∧Ct∈SAT)=0\mathbb{P}(\phi\wedge\widehat{C}_t\in\mathrm{SAT})=\mathbb{P}(\phi\wedge C_t\in\mathrm{SAT})=0. We conclude that for every realization of ϕ\phi, P(ϕ∧Ct∈SAT)≥P(ϕ∧C^t∈SAT)\mathbb{P}(\phi\wedge C_t\in\mathrm{SAT})\ge\mathbb{P}(\phi\wedge\widehat{C}_t\in\mathrm{SAT}). Thus (8) is verified. Removing the conditioning on ϕ\phi and M=TM=T we complete the proof. ∎

The key implication of Theorem 3.7 is the following property of the normalized median times.

Corollary 3.8. There exists n0n_0 such that for all n1,n2≥n0n_1,n_2 \ge n_0

λn1+n2≥min⁡(λn1,λn2)−5(n1+n2)−δ.\lambda_{n_1+n_2} \ge\min(\lambda_{n_1},\lambda_{n_2}) - 5(n_1+n_2)^{-\delta}.

Proof. Fix n1,n2>1n_1,n_2 > 1 and let n=n1+n2n=n_1+n_2. Let λ=min⁡j=1,2λnj\lambda=\min_{j=1,2}\lambda_{n_j}. Set r=λnr=\lambda n. Then rj≜(nj/n)r≤λnjnjr_j \triangleq(n_j/n)r \le\lambda_{n_j}n_j. (We note that r,rjr,r_j are not necessarily integers, unlike λnn,λnjnj\lambda_n n,\lambda_{n_j}n_j, j=1,2j=1,2,) Let M,MjM,M_j, j=1,2j=1,2 be Poisson random variables with means r,rjr,r_j, j=1,2j=1,2 respectively. We use the following universal lower bound for a Poisson random variable XX with mean μ\mu: P(X≤μ)≥1/e\mathbb{P}(X\le\mu)\ge1/e. This implies for j=1,2j=1,2

E[p(nj,Mj)]≥P(Φ(nj,Mj)∈SAT∣Mj≤rj)P(Mj≤rj)≥p(nj,λnjnj)(1/e)≥1/(2e).\mathbb{E}[p(n_j,M_j)] \ge\mathbb{P}(\Phi(n_j,M_j)\in\mathrm{SAT}\mid M_j\le r_j)\mathbb{P}(M_j\le r_j) \ge p(n_j,\lambda_{n_j}n_j)(1/e) \ge1/(2e).

Applying Theorem 3.7, we obtain E[p(n,M)]≥1/(2e)2\mathbb{E}[p(n,M)]\ge1/(2e)^2. Fix γ∈(1/2,1−δ)\gamma\in(1/2,1-\delta). This is possible since δ=(k−2)/(4k)<1/2\delta=(k-2)/(4k)<1/2 for all kk. Since Var⁡(M)=λn\operatorname{Var}(M)=\lambda n, by Chebyshev’s inequality we have

P(M−r<−nγ)≤λnn2γ=λn2γ−1.\mathbb{P}(M-r<-n^\gamma)\le\frac{\lambda n}{n^{2\gamma}}=\frac{\lambda}{n^{2\gamma-1}}.

Thus

P(Φ(n,M)∈SAT∣M≥r−nγ)P(M≥r−nγ)≥1/(2e)2−λn2γ−1,\mathbb{P}(\Phi(n,M)\in\mathrm{SAT}\mid M\ge r-n^\gamma)\mathbb{P}(M\ge r-n^\gamma)\ge1/(2e)^2-\frac{\lambda}{n^{2\gamma-1}},

namely

p(n,⌈r−nγ⌉)≥1/(2e)2−λn2γ−1.p(n,\lceil r-n^\gamma\rceil)\ge1/(2e)^2-\frac{\lambda}{n^{2\gamma-1}}.

Since n≥n1+n2≥2n0n\ge n_1+n_2\ge2n_0, applying the bound (1) on λ\lambda, this is at least 1/(3e)21/(3e)^2 for n0n_0 large enough. Then applying the concentration bound (7), for n0n_0 large enough E[Hn]≥r−nγ−2n1−δ≥r−3n1−δ\mathbb{E}[H_n]\ge r-n^\gamma-2n^{1-\delta}\ge r-3n^{1-\delta}. Applying Lemma 3.6 we conclude λnn≥r−5n1−δ\lambda_n n\ge r-5n^{1-\delta} provided n0n_0 is large enough. Dividing by nn we obtain for sufficiently large n0n_0

λn≥λ−5n−δ=min⁡(λn1,λn2)−5n−δ,\lambda_n\ge\lambda-5n^{-\delta}=\min(\lambda_{n_1},\lambda_{n_2})-5n^{-\delta},

concluding the proof.

Next we lower bound λn+1\lambda_{n+1} in terms of λn\lambda_n.

Lemma 3.9. There exists n0n_0 such that for all n≥n0n\ge n_0

λn+1≥λn−4(n+1)−δ.\lambda_{n+1}\ge\lambda_n-4(n+1)^{-\delta}.

Proof. Let Dn+1D_{n+1} be the number of clauses containing variable xn+1x_{n+1} in Φ(n+1,m)\Phi(n+1,m). For m≤2k+1nm\le2^{k+1}n we have inf⁡nP(Dn+1=0)≜α>0\inf_n\mathbb{P}(D_{n+1}=0)\triangleq\alpha>0. In fact Dn+1D_{n+1} has a Poisson distribution in the limit with nn independent parameter, but this will not be explicitly needed. We have P(Φ(n+1,m)∈SAT∣Dn+1=0)=P(Φ(n,m)∈SAT)\mathbb{P}(\Phi(n+1,m) \in\mathrm{SAT}\mid D_{n+1}=0)=\mathbb{P}(\Phi(n,m) \in\mathrm{SAT}). Thus for every m≤2k+1nm\le2^{k+1}n

P(Hn+1≥m)=P(Φ(n+1,m)∈SAT)≥P(Φ(n+1,m)∈SAT∣Dn+1=0)α=P(Φ(n,m)∈SAT)α≥P(Hn≥m)α.\begin{aligned} \mathbb{P}(H_{n+1}\ge m)&=\mathbb{P}(\Phi(n+1,m)\in\mathrm{SAT})\\ &\ge\mathbb{P}(\Phi(n+1,m)\in\mathrm{SAT}\mid D_{n+1}=0)\alpha\\ &=\mathbb{P}(\Phi(n,m)\in\mathrm{SAT})\alpha\\ &\ge\mathbb{P}(H_n\ge m)\alpha. \end{aligned}

Applying this to m=λnnm=\lambda_n n

P(Hn+1≥λnn)≥P(Hn≥λnn)α=α/2.\begin{aligned} \mathbb{P}(H_{n+1}\ge\lambda_n n)&\ge\mathbb{P}(H_n\ge\lambda_n n)\alpha\\ &=\alpha/2. \end{aligned}

We claim that for n0n_0 sufficiently large and all n≥n0n\ge n_0, E[Hn+1]≥λnn−(n+1)1−δ\mathbb{E}[H_{n+1}]\ge\lambda_n n-(n+1)^{1-\delta}. Indeed, otherwise

α/2≤P(Hn+1≥λnn)≤P(Hn+1≥E[Hn+1]+(n+1)1−δ)≤1(n+1)η,\alpha/2\le\mathbb{P}(H_{n+1}\ge\lambda_n n)\le\mathbb{P}(H_{n+1}\ge\mathbb{E}[H_{n+1}]+(n+1)^{1-\delta})\le\frac{1}{(n+1)^\eta},

which is violated when n≥n0n\ge n_0 and n0n_0 is large enough. Combining with Lemma 3.6 we obtain

λn+1(n+1)≥λnn−3(n+1)1−δ.\lambda_{n+1}(n+1)\ge\lambda_n n-3(n+1)^{1-\delta}.

Dividing by n+1n+1 and using λn/(n+1)≤(n+1)−δ\lambda_n/(n+1)\le(n+1)^{-\delta}, which holds for sufficiently large n0n_0 and by (1), we obtain the result.

From superadditivity to the existence of a limit of normalized medians λn\lambda_n. Proof of the main theorem

We complete the proof of the main theorem in this section by establishing the existence of a limit lim⁡n→∞λn\lim_{n\to\infty}\lambda_n of normalized medians using the near superadditivity property. The following variant of the superadditivity property is adopted from Abbe and Montanari [1].

Proposition 3.10. Suppose ana_n, n≥1n\ge1 is a non-negative bounded sequence of real values satisfying the following properties. There exists n0n_0 and δ>0\delta>0 such that for all n1,n2≥n0n_1,n_2\ge n_0

an1+n2≥min⁡(an1,an2)−5(n1+n2)−δ.(11)a_{n_1+n_2}\ge\min(a_{n_1},a_{n_2})-5(n_1+n_2)^{-\delta}. \tag*{(11)}

and for all n≥n0n\ge n_0

an+1≥an−4(n+1)−δ.(12)a_{n+1}\ge a_n-4(n+1)^{-\delta}. \tag*{(12)}

Then for all r≥n0r\ge n_0 and all n≥r2n\ge r^2

an≥ar−14r−δ1−(2/3)δ.(13)a_n\ge a_r-\frac{14r^{-\delta}}{1-(2/3)^\delta}. \tag*{(13)}

As a result the limit a∗≜lim⁡n→∞ana^*\triangleq\lim_{n\to\infty}a_n exists.

We first show how this claim implies the main theorem.

Proof of Theorem 2.1. Corollary 3.8 and Lemma 3.9 imply that our sequence λn\lambda_n satisfies the assumptions of the Proposition 3.10 with δ=(k−2)/(4k)\delta=(k-2)/(4k) chosen as in Proposition 3.5. Thus the limit λ∗=lim⁡nλn\lambda^*=\lim_n\lambda_n exists. By (1) we have 0<λ∗≤2k0<\lambda^*\leq2^k. Fix any ϵ>0\epsilon>0 such that λ∗(1+ϵ)<2k+1\lambda^*(1+\epsilon)<2^{k+1}. By Lemma 3.6 we can find large enough n0n_0 such that for all n≥n0n\geq n_0 E[Hn]≤λnn+2n1−δ\mathbb{E}[H_n]\leq\lambda_n n+2n^{1-\delta}. Again taking n0n_0 sufficiently large we obtain for all n≥n0n\geq n_0

E[Hn]≤λ∗(1+ϵ/2)n.\mathbb{E}[H_n]\leq\lambda^*(1+\epsilon/2)n.

Take m=⌈λ∗(1+ϵ)n⌉≤2k+1nm=\lceil\lambda^*(1+\epsilon)n\rceil\leq2^{k+1}n. Then applying the concentration bound Proposition 3.5 for large enough n0n_0 and all n≥n0n\geq n_0

P(Φ(n,m)∈SAT)=P(Hn≥m)≤P(Hn−E[Hn]≥λ∗(ϵ/2)n)≤Cn−η.\begin{aligned} \mathbb{P}(\Phi(n,m)\in\mathrm{SAT})=\mathbb{P}(H_n\geq m) \\ &\leq\mathbb{P}(H_n-\mathbb{E}[H_n]\geq\lambda^*(\epsilon/2)n)\leq Cn^{-\eta}. \end{aligned}

Here we used the uniform bound (1) on λn\lambda_n. Thus lim⁡n→∞P(Φ(n,m)∈SAT)=0\lim_{n\to\infty}\mathbb{P}(\Phi(n,m)\in\mathrm{SAT})=0 and the one side of the assertion of the theorem is established.

The other side is established similarly. Taking n0n_0 sufficiently large we obtain for all n≥n0n\geq n_0

E[Hn]≥λ∗(1−ϵ/2)n.\mathbb{E}[H_n]\geq\lambda^*(1-\epsilon/2)n.

We set m=⌈λ∗(1−ϵ)n⌉m=\lceil\lambda^*(1-\epsilon)n\rceil. Then

P(Φ(n,m)∉SAT)=P(Hn<m)≤P(Hn−E[Hn]≤−λ∗(ϵ/2)n)≤Cn−η.\begin{aligned} \mathbb{P}(\Phi(n,m)\notin\mathrm{SAT})=\mathbb{P}(H_n<m) \\ &\leq\mathbb{P}(H_n-\mathbb{E}[H_n]\leq-\lambda^*(\epsilon/2)n)\leq Cn^{-\eta}. \end{aligned}

Thus lim⁡n→∞P(Φ(n,m)∈SAT)=1\lim_{n\to\infty}\mathbb{P}(\Phi(n,m)\in\mathrm{SAT})=1, and the other side of the assertion of the theorem is established. □

Thus it remains to prove Proposition 3.10.

Proof of Proposition 3.10. The existence of the limit lim⁡nan\lim_n a_n is immediate from (13). Thus we focus on proving (13).

Given any positive integer RR consider a binary tree T(R)\mathcal{T}(R) constructed recursively as follows. Every node uu of this tree is marked with a positive integer denoted by RuR_u. The root oo of the tree T(R)\mathcal{T}(R) is marked with value RR itself. When R=1R=1 the associated tree is a single node uu, with Ru=R=1R_u=R=1. Assuming the tree is defined for all 1≤R′<R1\leq R'<R, we construct it for RR recursively as follows. The root of the tree T(R)\mathcal{T}(R) has two children o1,o2o_1,o_2. Suppose R=2R^R=2\widehat{R} is even. Then the subtrees emanating from both ojo_j, j=1,2j=1,2 are T(R′)\mathcal{T}(R'). In particular, Roj=R′R_{o_j}=R'. On the other hand, when R=2R′+1R=2R'+1 is odd, the two children ojo_j, j=1,2j=1,2 of the root oo of T(R)\mathcal{T}(R) are roots of subtrees T(R′)\mathcal{T}(R') and T(R′+1)\mathcal{T}(R'+1), respectively. In particular, the two children o1o_1 and o2o_2 are marked with R′R' and R′+1R'+1, respectively. As a result, the leaves of every tree T(R)\mathcal{T}(R) are marked with value 11. Since in either even or odd case we have (1/3)R≤R′≤(2/3)R(1/3)R\leq R'\leq(2/3)R, the depth TT of the tree is logarithmic in RR, though this fact will not be required for the remainder of the proof.

Now, fix any r≥n0r\geq n_0 and n≥r2n\geq r^2. Finding q≥rq\geq r, 0≤t≤r−10\leq t\leq r-1 such that n=qr+tn=qr+t, we can write n=(q−t)r+t(r+1)n=(q-t)r+t(r+1). Note q−t>0q-t>0. We assume t>0t>0. The case t=0t=0 is treated similarly, and the proof is omitted. Applying (11) with n1=(q−t)rn_1=(q-t)r and n2=t(r+1)n_2=t(r+1) we have

an≥min⁡(a(q−t)r,at(r+1))−5n−δ.(14)a_n\geq\min(a_{(q-t)r},a_{t(r+1)})-5n^{-\delta}. \tag*{(14)}

Now consider the two binary trees T(q−t)\mathcal{T}(q-t) and T(t)\mathcal{T}(t) defined as above. Starting from the left tree T(q−t)\mathcal{T}(q-t) with the root marked with q−tq-t, apply (11) recursively down the tree until the leaves of the left tree are reached. For example, in the first step, assuming q−tq-t is even we obtain

a(q−t)r≥aq−t2r−5((q−t)r)−δ.a_{(q-t)r} \ge a_{\frac{q-t}{2}r} - 5((q-t)r)^{-\delta}.

Assuming, on the other hand, q−tq-t is odd, in the first step we obtain instead

a(q−t)r≥min⁡(aq−t−12r,aq−t+12r)−5((q−t)r)−δ.(15)a_{(q-t)r} \ge\min\left(a_{\frac{q-t-1}{2}r}, a_{\frac{q-t+1}{2}r}\right) - 5((q-t)r)^{-\delta}. \tag*{(15)}

Iterating we obtain

a(q−t)r≥ar−max⁡PEPa_{(q-t)r} \ge a_r - \max_P E_P

where EPE_P is the additive correction accumulated across a path PP from the root to a leaf. From the relation R′/R≤2/3R'/R \le2/3 between a mark of a node and the mark of any of its child, that we observed above, every next correction term up the path is at most (2/3)δ(2/3)^\delta times the previous correction term. The largest correction is associated with leaves and is 5r−δ5r^{-\delta}. Thus we obtain

EP≤5r−δ∑ℓ≥0(2/3)δℓ=5r−δ1−(2/3)δ.E_P \le5r^{-\delta}\sum_{\ell\ge0}(2/3)^{\delta\ell} = \frac{5r^{-\delta}}{1-(2/3)^\delta}.

We obtain

a(q−t)r≥ar−5r−δ1−(2/3)δ.a_{(q-t)r} \ge a_r - \frac{5r^{-\delta}}{1-(2/3)^\delta}.

Similarly, we obtain

at(r+1)≥ar+1−5(r+1)−δ1−(2/3)δ.a_{t(r+1)} \ge a_{r+1} - \frac{5(r+1)^{-\delta}}{1-(2/3)^\delta}.

Applying (12) we obtain

at(r+1)≥ar−5(r+1)−δ1−(2/3)δ−4(r+1)−δ.a_{t(r+1)} \ge a_r - \frac{5(r+1)^{-\delta}}{1-(2/3)^\delta} - 4(r+1)^{-\delta}.

Applying this to (14) we obtain

an≥ar−5r−δ1−(2/3)δ−4(r+1)−δ−5n−δ.(16)a_n \ge a_r - \frac{5r^{-\delta}}{1-(2/3)^\delta} - 4(r+1)^{-\delta} - 5n^{-\delta}. \tag*{(16)}
≥ar−14r−δ1−(2/3)δ.(17)\ge a_r - \frac{14r^{-\delta}}{1-(2/3)^\delta}. \tag*{(17)}

completing the proof.

Some open questions

Several questions appear to be within the reach of the current techniques, in particular ones developed in [5] and [17]. In particular, it seems very plausible that the approach extends to other models of random constraint satisfaction problems such as proper coloring of a graph.

Furthermore, while the validity of the limiting satisfiability threshold λk∗\lambda_k^* is now established, it is not known whether it coincides with ground state energy limit, the existence of which was established in [4]. Specifically, it is shown in [4] that for every fixed value dd, the minimum number of violated clauses in the random formula Φ(n,⌈dn⌉)\Phi(n,\lceil dn\rceil) converges to some limit γk(d)\gamma_k(d) when normalized by nn. Define dk∗d_k^* as sup⁡{d:γk(d)=0}\sup\{d:\gamma_k(d)=0\}. dk∗d_k^* is strictly positive since γk(d)\gamma_k(d) is zero with high probability when d<λk∗d<\lambda_k^*. What remains unclear, though is extremely plausible, is whether dk∗=λk∗d_k^*=\lambda_k^*. Specifically, at the present stage, we cannot rule out a range of values dd above λk∗\lambda_k^* for which on the one hand the formula is not satisfiable with high probability, but on the other hand solutions exist which violate only sublinearly in nn many clauses also with high probability. Provided an exponential concentration of the hitting time HnH_n around its expectation holds, such a conclusion would be an immediate corollary of Theorem 2.1 and the log-superadditivity property Theorem 3.7 from [4]. Unfortunately, the current concentration bound from Proposition 3.5 is too weak for this purpose.

Finally, unfortunately not all random constraint satisfaction problems such as random kk-SAT and spin glasses are amenable to the interpolation technique. The key challenge is that the convexity property such as one in (9) and (10) does not always hold. A notable counter-example is the Minimum Bisection problem in sparse random graph, see [15] for the definition and some partial results. Specifically, given a sparse Erdős-Rényi graph G(n,d/n)\mathbb{G}(n,d/n) let MB(n,d)\mathrm{MB}(n,d) be its minimum bisection value. The expectation of this value is O(n)O(n) trivially and it is natural to conjecture that the limit lim⁡nE[MB(n,d)]/n\lim_n\mathbb{E}[\mathrm{MB}(n,d)]/n exists. Unfortunately, the counterparts of the expressions (9) and (10) for the Minimum Bisection problem do not exhibit the convexity property. As a result the validity of the conjecture remains open.

References

  1. [1]Emmanuel Abbe and Andrea Montanari, On the concentration of the number of solutions of random satisfiability formulas, Random Structures & Algorithms 45 (2014), no. 3, 362–382.arxiv.org/abs/1006.3786
  2. [2]D. Achlioptas and Y. Peres, The threshold for random k-SAT is 2ᵏ ln 2 − O(k), Proc. 45th Ann. Symposium on the Theory of Computing (2003).
  3. [3]D. Achlioptas and G. Sorkin, Optimal myopic algorithms for random 3-SAT, Proc. 41st IEEE Symposium on Foundations of Computer Science (2000).
  4. [4]M. Bayati, D. Gamarnik, and P. Tetali, Combinatorial approach to the interpolation method and scaling limits in sparse random graphs, Annals of Probability. (Conference version in Proc. 42nd Ann. Symposium on the Theory of Computing (STOC) 2010) 41 (2013), 4080–4115.
  5. [5]G. Carenini, A polynomial scaling window for random k-sat and a proof of the satisfiability conjecture, Electronic Colloquium on Computational Complexity, Report No. 229. https://eccc.weizmann.ac.il/report/2026/229/ (2026).
  6. [6]V. Chvatal and B. Reed, Mick gets some (the odds are on his side), Proc. 33d Symposium on Foundations of Computer Science (1992).
  7. [7]Vašek Chvátal and Bruce Reed, Mick gets some (the odds are on his side)(satisfiability), Proceedings., 33rd Annual Symposium on Foundations of Computer Science, IEEE, 1992, pp. 620–627.DOI
  8. [8]Amin Coja-Oghlan and Konstantinos Panagiotou, The asymptotic k-SAT threshold, Advances in Mathematics 288 (2016), 985–1068.
  9. [9]Jian Ding, Allan Sly, and Nike Sun, Proof of the satisfiability conjecture for large k, Proceedings of the forty-seventh annual ACM symposium on Theory of computing, 2015, pp. 59–68.
  10. [10]———, Proof of the satisfiability conjecture for large k, Annals of Mathematics 196 (2022), no. 1, 1–388.
  11. [11]F.Guerra and F.L.Toninelli, The thermodynamic limit in mean field spin glass models, Commun. Math. Phys. 230 (2002), 71–79.
  12. [12]S. Franz and M. Leone, Replica bounds for optimization problems and diluted spin systems, Journal of Statistical Physics 111 (2003), no. 3/4, 535–564.arxiv.org/abs/cond-mat/0208280
  13. [13]E. Friedgut, Sharp thresholds of graph properties, and the k-SAT problem, J. Amer. Math. Soc. 4 (1999), 1017–1054.DOI
  14. [14]Francesco Guerra, Broken replica symmetry bounds in the mean field spin glass model, Communications in mathematical physics 233 (2003), 1–12.DOI
  15. [15]Brice Huang, Convergence of maximum bisection ratio of sparse random graphs, Electronic Communications in Probability 23 (2018), 1–10.DOI
  16. [16]Stephan Mertens, Marc Mézard, and Riccardo Zecchina, Threshold values of random k-sat from the cavity method, Random Structures & Algorithms 28 (2006), no. 3, 340–373.
  17. [17]OpenAI, A limiting satisfiability threshold for every fixed clause size, https://github.com/openai/math/blob/main/preprints/ (2026).
  18. [18]Dmitry Panchenko, The Sherrington-Kirkpatrick model, Springer Science & Business Media, 2013.DOI
  19. [19]Giorgio Parisi, Infinite number of order parameters for spin-glasses, Physical Review Letters 43 (1979), no. 23, 1754.
  20. [20]———, A sequence of approximated solutions to the SK model for spin glasses, Journal of Physics A: Mathematical and General 13 (1980), no. 4, L115.
  21. [21]Michel Talagrand, The Parisi formula, Annals of mathematics (2006), 221–263.

Paper details

vlnc:W_d8dm8zfc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents