1 Introduction
Fix an integer n\ge3. A proper 3-clause is a disjunction of three literals on distinct variables among x_1,\ldots,x_n. Let C_1,C_2,\ldots be independent clauses, each uniform among the 8\binom n3 proper 3-clauses. Thus the signs are fair and independent, and whole clauses may repeat. Write
where F_0 is the empty, satisfiable formula. The random variable H_n records the location of the satisfiability transition in the clause process.
Theorem 1.1. There is an absolute constant C<\infty such that
There are also absolute constants c>0 and n_0 such that \Var(H_n)\ge cn for n\ge n_0. In particular, \Var(H_n)=\Theta(n) as n\to\infty.
The new assertion is the upper bound. We give its proof in full. The lower bound follows from Wilson’s quantitative separation of satisfiability levels [7, Corollary 4]; Section 5 includes the short deduction, with the integer endpoints treated explicitly.
Context and contribution
Friedgut proved sharpness of the random k-SAT threshold for every fixed k\ge2 [5, Theorem 1.3]. Quantifying the width of that transition is a finer problem. Wilson showed that, for k\ge3, a fixed decrease in the satisfiability probability requires at least a constant times \sqrt n additional clauses [7]. More recently, Carenini obtained an O(n/\log n) central clause-window bound for fixed k\ge3, including independently sampled proper constraints [3, Corollaries 7.10–7.11]. Her subsequent paper [2, Theorems 1.1 and 1.3, Corollary 1.2], made public on October 5, 2026, proves for every fixed k\ge3 a central window bound O_{k,\eta}(n^{1/2+1/k}) at each fixed 0<\eta<1/2 and a hitting-time variance bound O_k(n^{1+2/k}). Together with the Abbe–Montanari criterion, her result establishes the limiting satisfiability threshold for every fixed k\ge3. We credit Carenini with priority for the resolution of the satisfiability conjecture. The present paper concerns the sharper fluctuation question for three-literal clauses.
A bound on a fixed central window alone does not control the variance, which also depends on the tails. In the other direction, Theorem 1.1 and Wilson’s lower bound show that the clause window over which satisfiability drops from 1-\eta to \eta has order \sqrt n for every fixed 0<\eta<1/2; see Corollary 5.2.
The companion preprint Variance of the Random k-SAT Hitting Time [6] develops a clause-omission and root-test framework. It proves variance \Theta_k(n) for every fixed k\ge4 and an upper bound O(n\log n) for k=3. Our argument uses that framework, which we reprove here, and replaces its critical occupation estimate in the three-literal case. The companion has broader general-k and capped formulations; the present paper concerns the uncapped proper 3-clause process defined above.
The new ingredient is a family of potentials for an arbitrary set S of Boolean assignments. Let q_j(S) be the probability that j independent random proper 2-clauses leave no assignment in S, and put
The potential increases when S shrinks and is bounded by d. Section 2 proves that q_d(S)^{3/2}, for nonempty S, is controlled by the expected increment of P_d under a random 3-clause, up to a small error. Summing those increments gives a direct bound on the accumulated values of q_d^{3/2}. This is the step that removes the logarithmic loss.
Here is how the potential enters the variance proof. For n\ge6, cap H_n at 10n and let D_i be the delay caused by omitting the clause at index i, without renumbering later clauses. The coordinate-omission form of the Efron–Stein inequality bounds the capped variance by \sum_i\E D_i^2 [4, 1]. Fixing the omitted clause singles out its three variables as roots. If that clause is pivotal, every remaining solution has the unique root assignment that falsifies it. Flipping each root gives an independent family of necessary tests on the nonroot solution set, except when another clause meets two or more roots. Section 3 constructs this exposure and proves the test bound.
Let d be the larger of 1 and the number of clauses other than C_i among the first 10n that meet a root. At a given index, let S be the nonroot solution set of the omitted-clause prefix with the roots fixed to their falsifying assignment, and write p=q_d(S). With no collisions, the three test families each have at most d clauses and give a pivotality bound p^3. For p>0, the potential gives a conditional remaining-duration bound O(d^{3/2}p^{-3/2}) and bounds the conditional expected sum of p^{3/2}, while S is nonempty, by O(d^{3/2}). The identity 3-3/2=3/2 thus yields a conditional squared-delay bound O(d^3). The root-incidence count d has bounded moments uniformly in n. Section 4 carries out this calculation and averages the rare collision cases, obtaining \E D_i^2=O(1) uniformly in i. Finally, Section 5 removes the cap using an elementary first-moment tail bound and proves the matching lower bound.
Throughout, a random proper a-clause on a specified variable set is uniform over the clauses using a distinct variables and independent fair signs. Independent collections are sampled with replacement. All unspecified constants are absolute.
2 A potential for killing assignment sets
We first work on u\ge3 variables, independently of the clause process. The aim is to bound a power of a short-clause killing probability by the drift of a bounded, monotone potential. For S\subseteq\{0,1\}^u and a clause C, let
For j\ge0, define q_j(S) as the probability that j independent random proper 2-clauses kill S, meaning that no member of S satisfies them all. In particular,
The quantity q_j(S) is nondecreasing both in j and when S shrinks. Set \beta=3/2 for the rest of the paper.
Lemma 2.1 (One-clause comparison). For a nonempty assignment set S, let h_a(S) be the probability that one random proper a-clause kills S, for a=2,3. Then
Proof. A coordinate is frozen if it is constant throughout S. Let b be the number of frozen coordinates. A clause kills all of S exactly when all its variables are frozen and each literal has the falsifying sign. Consequently,
where (t)_a=t(t-1)\cdots(t-a+1), with value zero for integers 0\le t<a. Since b\le u,
For b\ge3 we also have
which proves h_2(S)^{3/2}\le3h_3(S) in this case. For b\le1 the left side is zero. For b=2 it is [2u(u-1)]^{-3/2}\le u^{-3}, proving (2.1).
The error term accounts for sets with exactly two frozen coordinates: a 2-clause can kill such a set, whereas a proper 3-clause cannot. The following lemma turns the one-clause comparison into the potential estimate needed along a decreasing sequence of assignment sets.
Lemma 2.2 (Potential drift). For every integer d\ge1, put
Then 0\le P_d(S)\le d, and P_d is nondecreasing when S shrinks. If C is an independent random proper 3-clause on the u variables, then
Proof. Fix j\ge0, and let Y be the subset of S surviving j independent random proper 2-clauses. Adding one more such clause gives
Adding instead the independent 3-clause C gives
Indeed, in either order of adding the clauses, the increase in killing probability is precisely the probability that the old surviving set is nonempty and the final clause kills it. Products with the indicators in these formulas are defined to be zero when Y is empty. Jensen’s inequality and Lemma 2.1 imply
For nonempty S, the nonnegative successive differences telescope to q_d(S), because q_0(S)=0. Thus the power-sum inequality yields
and summing the preceding bound proves (2.2). For empty S, its left side is zero and its right side is nonnegative. The bounds and monotonicity of P_d follow directly from those of q_j.
3 Clause deletion and independent root tests
We now reduce the variance bound to a uniform squared-delay estimate. The root exposure and root-flip tests in this section follow the clause-omission framework of [6, Section 3]; all details needed here are included.
Assume n\ge6, set L=10n, and let T=\min(H_n,L). For 1\le i\le L, omit C_i while retaining the original indices:
Let T^{(i)} be the first index at which this omitted-clause process is unsatisfiable, capped at L, and set D_i=T^{(i)}-T\ge0. Both capped variables are functions of the first L clauses, and T^{(i)} does not depend on C_i.
Lemma 3.1 (Coordinate omission). The capped hitting time satisfies
Proof. This is the coordinate-omission form of the Efron–Stein inequality; see [1, Section 3.2, Equation (3.6)]. For completeness, write \mathcal F_i=\sigma(C_1,\ldots,C_i) and \Delta_i X=\E[X\mid\mathcal F_i]-\E[X\mid\mathcal F_{i-1}]. Independence and the omission of C_i give \Delta_i T^{(i)}=0, so \Delta_i T=-\Delta_i D_i. Orthogonality of conditional-expectation projections implies \E(\Delta_i D_i)^2\le\E D_i^2. Summing the orthogonal martingale differences of T proves (3.1).
3.1 The exposure and its two filtrations
Fix i and condition on the value of C_i until further notice. All probabilities and expectations in this section and in Section 4, until the final averaging step, are in this conditional law. Write B_m=B_m^{(i)}. Call the three variables of C_i the roots, denote their set by R, and let w\in\{0,1\}^R be the unique root assignment falsifying C_i. There are u=n-3\ge3 nonroot variables.
For i\le m<L, define
The processes agree before i, so
For i\le m\le L, let S_m\subseteq\{0,1\}^u consist of the nonroot assignments that, together with w, satisfy B_m. The sets S_m decrease with m. On A_m, the set S_m is nonempty, and every solution of B_m has root assignment w.
We will retain two independent sources of randomness: clauses driving the evolution of S_m, and clauses testing possible root flips. For every index j\le L other than i, first reveal the subset of R met by C_j and all signs on that subset. Classify the index as follows:
- •
An ordinary clause meets no root; leave all its contents hidden.
- •
A test clause meets exactly one root, whose literal is true under w; leave its two nonroot literals hidden.
- •
For every other clause, reveal all its remaining contents.
Let \cE be the sigma-field of this exposure, including the information at future indices. Let Z count the exposed indices meeting at least one root, and let V count those meeting at least two roots. The latter clauses are called collisions. Set d=\max\{1,Z\}. The counts Z,V,d and the complete schedule of clause types are \cE-measurable.
Conditional on \cE, the hidden ordinary clauses are independent uniform proper 3-clauses on the nonroots, and the hidden nonroot parts of the test clauses are independent uniform proper 2-clauses there. These two collections are also independent of each other. To see this, condition first on the root subset and its signs separately at each index. Every permitted signed nonroot part remains equiprobable, and the original product law across indices is preserved. Revealing the remaining contents at the other indices does not change the law of the hidden coordinates.
For i\le m\le L, define
The set S_m is \cG_m-measurable: all test clauses are already true under w, whatever their nonroot parts. The event A_m is \cH_m-measurable, because this larger sigma-field knows all clauses of B_m. Future ordinary contents remain fresh given \cH_m. Finally, put
The quantity p_m is \cG_m-measurable and nondecreasing in m. Keeping the tests out of \cG_m will allow us to estimate pivotality after using \cH_m to estimate the remaining duration.
3.2 Necessary tests for root flips
Lemma 3.2 (Root-test bound). For i\le m<L, conditional on \cG_m,
Proof. Call a root x available at time m if no collision through index m, excluding i, has its literal on x as the unique root literal true under w. A collision excludes at most one root, so at least 3-V roots are available. Availability is \cE-measurable.
For an available root x, the nonroot parts of its test clauses through m must kill S_m on A_m. Otherwise, take z\in S_m satisfying all these parts and flip only x in the assignment (w,z). Every clause of B_m remains satisfied. A clause with no true root literal under w already has a satisfied nonroot literal, which is unchanged. A clause with a true root literal other than the one on x keeps that literal. Finally, a clause whose unique true root literal is on x cannot be a collision, by availability; it is therefore a test clause for x, and z satisfies its nonroot part. The flipped assignment also satisfies C_i, contradicting A_m.
Given \cG_m, the test families for distinct roots remain independent collections of random proper 2-clauses, independent of S_m. Each family has at most Z\le d members, so its probability of killing S_m is at most q_d(S_m)=p_m. On V=0 all three roots are available; on V=1 at least two are. Taking these necessary independent events proves the two inequalities, including the cases p_m=0 or S_m=\varnothing.
4 Occupation and squared deletion delays
We continue with i and C_i fixed. Our goal is \E D_i^2=O(1), uniformly in the value of the fixed clause. The root tests bound the chance that a delay is present; the potential will bound how long that delay can continue.
Lemma 4.1 (Conditional occupation estimate). With K=7, for every i\le m<L,
Proof. Suppose s+1 is ordinary, a fact known under \cE. Then S_{s+1}=S_s[C_{s+1}], and C_{s+1} is still a uniform proper 3-clause on the nonroots given \cH_s. Lemma 2.2 gives
Condition on \cH_m and sum over such s. Every potential increment is nonnegative, even at nonordinary steps. Thus, pathwise,
The tower property therefore bounds the contribution of the ordinary steps by 3d^\beta+Ld^\beta u^{-3}. There are at most Z remaining steps: all indices s+1 in question exceed i, and every nonordinary index meets a root. Each remaining summand is at most one. Since Z\le d\le d^\beta, u=n-3\ge n/2, and n\ge6, the full sum is bounded by
Corollary 4.2 (Remaining duration). For i\le m<L,
In particular, W_m is measurable with respect to the smaller sigma-field \cG_m.
Proof. For s\ge m, we have p_s\ge p_m, and A_s implies S_s\ne\varnothing. If p_m>0, divide (4.1) by p_m^\beta. The count is always at most L, giving both the minimum and the case p_m=0. Measurability follows from that of d and p_m.
The two estimates now have the compatible conditioning we need: the duration estimate knows whether A_m has occurred, while its upper bound W_m does not reveal the test parts. We can therefore multiply it by the independent-test probability from Lemma 3.2.
Proposition 4.3 (Squared delay conditional on the exposure). For every 1\le i\le L,
Proof. For i=L we have D_i=0. Otherwise, (3.3) implies
First condition on \cH_m, where A_m is known, and apply Corollary 4.2. Then condition on \cG_m, where W_m is known. Conditioning both estimates down to \cE gives
On V=0, Lemma 3.2 bounds the product inside by
This remains valid for p_m=0, because the conditional probability then vanishes. Lemma 4.1 with m=i, conditioned further down to \cE, bounds the sum in (4.4) by 2K^2d^{2\beta}=2K^2d^3. On V=1, the same product is at most Kd^\beta p_m^{2-\beta}\le Kd^\beta when p_m>0, and is zero when p_m=0. There are at most L terms. Finally, on V\ge2 use D_i\le L. The cases are \cE-measurable, proving (4.3).
4.1 Averaging the collision costs
It remains to average the three terms of (4.3). Although one collision costs a factor L and two collisions cost L^2, their probabilities are correspondingly small.
Lemma 4.4 (Root-incidence moments). Uniformly in n\ge6, i, and the fixed value of C_i,
Proof. Each of the other L-1 independent clauses meets a specified root with probability 3/n, and contains a specified pair of roots with probability 6/[n(n-1)]. Union bounds over the three roots and their three pairs give incidence and collision probabilities satisfying
The incidence count Z is binomial, so
This uniformly bounded exponential moment gives \E d^3=O(1).
For each j\ne i with j\le L, let J_j be the event that C_j is a collision. Bound \ind_{\{V\ge1\}} by \sum_{j\ne i}\ind_{J_j}. Conditional on J_j, the count Z is one plus a binomial variable with L-2 trials and success probability p_{\rm hit}; all other clauses retain their original law. Its exponential moment, and hence \E[d^{3/2}\mid J_j], is bounded uniformly. Therefore
Finally, independence at different indices gives
Combining Proposition 4.3 and Lemma 4.4, and using L=10n, proves \E D_i^2=O(1) in the law conditional on C_i, with a constant independent of its value. We may now remove that conditioning. Lemma 3.1 gives
This completes the deletion argument. No information about the location of the satisfiability threshold was needed.
5 The uncapped hitting time and the lower bound
5.1 Removing the cap
For a fixed assignment, each independent clause is satisfied with probability 7/8. A union bound over the 2^n assignments gives, for every n\ge3 and integer m\ge0,
In particular H_n is finite almost surely and has a finite second moment. For n\ge6, write T=\min\{H_n,L\} as before. The integer-valued tail-sum formula yields
Here \sum_{j\ge0}(2j+1)r^j=(1+r)/(1-r)^2=120 for r=7/8, and 2(7/8)^{10}<1. Since
Equations (4.6) and (5.2) give the upper bound in Theorem 1.1 for n\ge6. For 3\le n<6, the same tail bound gives \E H_n^2\le120\cdot2^n, so enlarging the absolute constant covers these finitely many sizes.
5.2 Wilson’s separation theorem
Define the survival function and its integer level locations by
These locations are finite by (5.1) and positive because s_n(0)=1. We use the following consequence of Wilson’s theorem for the independent proper-clause model with replacement.
Theorem 5.1 (Wilson [7], Corollary 4). Fix 1>p_1>p_2>0. There is a constant a(p_1,p_2)>0 such that, for all sufficiently large n, if integers m_1,m_2 satisfy s_n(m_1)\ge p_1 and s_n(m_2)\le p_2, then
Take a_n=r_n(3/4) and b_n=r_n(1/4). Minimality gives s_n(a_n-1)>3/4, whereas s_n(b_n)\le1/4. Theorem 5.1, applied at a_n-1 and b_n, therefore implies b_n-a_n+1\ge a(3/4,1/4)\sqrt n. Thus
for an absolute c_0>0 and all sufficiently large n. Moreover,
Let H_n' be an independent copy of H_n. The two events \{H_n\le a_n,H_n'\ge b_n\} and \{H_n'\le a_n,H_n\ge b_n\} are disjoint for large n, each has probability at least 1/16, and on each |H_n-H_n'|\ge b_n-a_n. Consequently,
This completes the proof of Theorem 1.1.
Corollary 5.2 (Fixed central windows). For every fixed 0<\eta<1/2,
Proof. The lower bound follows from Theorem 5.1 at r_n(1-\eta)-1 and r_n(\eta), absorbing the additive one. For the upper bound, put \mu_n=\E H_n and choose t=(2Cn/\eta)^{1/2}, with C from Theorem 1.1. Chebyshev’s inequality gives \Prb(|H_n-\mu_n|\ge t)\le\eta/2. For every nonnegative integer m\le\mu_n-t this implies s_n(m)\ge1-\eta/2>1-\eta, whereas at m=\lceil\mu_n+t\rceil it implies s_n(m)\le\eta/2<\eta. Hence r_n(1-\eta)>\mu_n-t and r_n(\eta)\le\lceil\mu_n+t\rceil, proving the upper bound. If \mu_n-t<0, the first inequality follows instead from r_n(1-\eta)\ge0.
The variance bound controls fluctuations around the finite-size mean \E H_n. Neither the proof nor Corollary 5.2 requires a limiting value of \E H_n/n or a limiting distribution for the centered hitting time.
References
- [1]Stéphane Boucheron, Olivier Bousquet, Gábor Lugosi, and Pascal Massart. Moment inequalities for functions of independent random variables. The Annals of Probability, 33(2):514–560, 2005. doi:10.1214/009117904000000856, arXiv:math/0503651.
- [2]Gaia Carenini. A polynomial scaling window for random k-SAT and a proof of the satisfiability conjecture. Technical Report TR26-229, Electronic Colloquium on Computational Complexity, 2026. Published 5 October 2026. https://eccc.weizmann.ac.il/report/2026/229/. https://eccc.weizmann.ac.il/report/2026/229/.
- [3]Gaia Carenini. The Scaling Window of Random k-SAT. Technical Report TR26-145, Electronic Colloquium on Computational Complexity, 2026. arXiv:2609.26222, https://eccc.weizmann.ac.il/report/2026/145/.
- [4]Bradley Efron and Charles Stein. The Jackknife Estimate of Variance. The Annals of Statistics, 9(3):586–596, 1981. doi:10.1214/aos/1176345462.
- [5]Ehud Friedgut. Sharp thresholds of graph properties, and the k-SAT problem. Journal of the American Mathematical Society, 12(4):1017–1054, 1999. With an appendix by Jean Bourgain. doi:10.1090/S0894-0347-99-00305-7.
- [6]OpenAI. Variance of the Random k-SAT Hitting Time. OpenAI Math Release preprint PDF, 2026. Reading view on this site: Variance of the Random k-SAT Hitting Time.
- [7]David B. Wilson. On the critical exponents of random k-SAT. Random Structures & Algorithms, 21(2):182–195, 2002. doi:10.1002/rsa.10050, arXiv:math/0005136.