A Limiting Satisfiability Threshold for Every Fixed Clause Size

The limiting-threshold problem

As independent clauses are added to a random Boolean formula, satisfiability changes from likely to unlikely. A narrow transition window answers only part of the threshold question: its location might still drift as the number of variables grows. We prove that the location converges for every fixed clause size at least three.

A Boolean assignment gives each variable $x_i$ a value in $\{0,1\}$. A literal is a variable or its negation; a clause is a disjunction of literals, and a conjunctive normal form formula is a conjunction of clauses. A formula is satisfiable if some assignment makes every clause true. Random $k$-SAT asks how this event changes as independent clauses are added to a formula on $n$ variables.

Fix an integer $k \ge3$. For $n \ge k$, a proper $k$-clause uses $k$ distinct variables chosen uniformly from $x_1,\ldots,x_n$, with independent fair signs. Thus each of the $2^k\binom{n}{k}$ possible clauses has the same probability. Let $C_1,C_2,\ldots$ be independent clauses with this law, and define

Here SAT denotes satisfiability, and the empty conjunction is true. Whole clauses are sampled with replacement: two positions may contain the same clause, although a variable cannot occur twice within one proper clause. The prefix coupling makes $P_n$ nonincreasing and gives $P_n(0)=1$. The ratio $c=m/n$ is the clause density.

Theorem 1.1. For every fixed integer $k \ge3$, there is a constant $\alpha_k \in(0,\infty)$ such that, for independent proper uniformly signed $k$-clauses sampled with replacement,

The conclusion is a strict-side threshold statement; it makes no assertion at $c=\alpha_k$. All estimates below may depend on the fixed integer $k$. The proof does not require the centers of the transition windows to be known in advance. It constructs a finite-size center, controls the fluctuations about it, and then proves that these centers converge.

Prior work and the role of the present argument

Carenini [5], Theorem 1.1 and Corollary 1.2 proves an $O_{k,\eta}(n^{1/2+1/k})$ clause window between probability levels $\eta$ and $1-\eta$, for each fixed $0<\eta<1/2$, and, using the Abbe–Montanari criterion, establishes the satisfiability conjecture for every fixed $k\ge3$. We credit Carenini with priority for the resolution of the satisfiability conjecture. The present paper gives an alternative proof of the limiting-threshold conclusion.

Chvátal and Reed [7] explicitly formulated the conjecture that each fixed clause size greater than one has a limiting satisfiability density. Friedgut’s sharp-threshold theorem, with Bourgain’s appendix [14], Theorem 1.3, established that random $k$-SAT has a sharp transition around a sequence of densities. It left open whether that sequence converges for each fixed $k$. The classical two-clause problem had already been settled by Chvátal and Reed [7], Theorems 3–4, who also credit independent proofs by Goerdt and Fernandez de la Vega. Goerdt’s journal treatment is [15]. The implication-graph mechanism is separate from the proof given here.

For larger arities, Achlioptas and Peres [2] obtained leading-order bounds $2^k\log2-O(k)$, using weighted second moments. The statistical-physics work of Mézard, Parisi, and Zecchina [19] and of Mertens, Mézard, and Zecchina [18] developed threshold predictions through the cavity method and one-step replica symmetry breaking. In particular, the latter work predicted the large-$k$ expansion

Coja-Oghlan and Panagiotou [8], Theorem 1.1 proved that the liminf and limsup of the sharp-threshold sequence both lie within an additive error tending to zero as $k\to\infty$ of $2^k\log2-(1+\log2)/2$. These asymptotic-in-arity estimates are distinct from convergence in $n$ at a fixed arity. Ding, Sly, and Sun [9] proved existence and identified the threshold with the one-step replica symmetry breaking prediction for all sufficiently large fixed $k$. Theorem 1.1 establishes existence for every fixed $k\ge3$, without identifying the value of $\alpha_k$.

The first ingredient is a comparison between shorter clauses and blocks of ordinary clauses. Friedgut’s half-cube replacement lemma [14], Lemma 5.7 gives a qualitative antecedent based on frozen coordinates and sequential replacement. Carenini [6], Lemma 6.1 and Corollaries 6.2, 7.10–7.11 developed an averaged clause-replacement method. The cited version proves an $O_k(n/\log n)$ window between any two fixed central probability levels, with constants also depending on those levels, and distinguishes window width from convergence of the location in Section 10.1. Here the replacement is applied after erasing one variable. Summing the resulting changes in satisfiability probabilities bounds the forced fraction along the clause process. A deletion argument then converts this integrated bound into polynomial concentration. We give the replacement, forcing, and deletion proofs in full.

The second ingredient compares a whole system with independent subsystems. Guerra and Toninelli [16] used interpolation to establish thermodynamic limits for mean-field spin glasses. Franz and Leone [12], and Franz, Leone, and Toninelli [13], developed interpolation for diluted systems. Their pressure and free-energy arguments, with the stated even-arity restrictions, do not supply the hard satisfiability-threshold conclusion used here. Bayati, Gamarnik, and Tetali [3], Section 4, Proposition 2 established a frozen-variable satisfiability interpolation between clauses on a whole variable set and clauses confined to its parts. Our Poisson comparison is a continuous-parameter form of that method. Its sign follows from convexity of $x \mapsto x^k$, applied to the proportions of globally forced variables in the parts. The comparison is exact for an auxiliary clause model that permits repeated variables; we prove the transfer back to proper clauses, including the constant loss caused by repetitions.

Finally, errors that are summable over geometrically increasing sizes cannot produce macroscopic drift. This principle parallels the approximate-superadditivity analysis of Abbe and Montanari [1], arXiv version, Section 4.3, Lemma 8 and Remark 3, developed in their study of solution counts. Our comparison uses the minimum of two normalized centers. We prove the corresponding deterministic convergence lemma, in a form that requires the comparison only when the two sizes are comparable.

How the proof reaches the threshold

We cap the last satisfiable index at a fixed multiple of $n$, and take its expectation divided by $n$ as the finite-size center. The first task is to show that this capped index has sublinear fluctuations. In a satisfiable formula, a variable is forced if every satisfying assignment gives it the same value. The clauses that avoid the variable form the untouched background. If the variable is forced, deleting its literal from each incident clause produces shorter clauses that eliminate every solution of this background. Replacing each shortened clause by a block of ordinary clauses turns this event into a decrease of the satisfiability probability. Summing over prefix lengths telescopes the decreases. Section 2 thereby controls the total expected forced fraction along the process.

Section 3 omits a single clause while keeping the other time indices. The delay in losing satisfiability counts the prefixes where that clause is pivotal. Its square counts pairs of such prefixes. If the punctured formula survives from the earlier prefix to the later one, every intervening clause must avoid killing the earlier solution set. This bounds the pair probability in terms of the variables already forced at the earlier time. The integrated forcing estimate then yields the required variance bound. Section 4 places the normalized means in a fixed positive bounded interval, using a clause-to-variable matching at low density and an assignment first moment at high density.

Concentration alone still permits the centers to drift. In the auxiliary Poisson model, interpolation says that satisfiability at a combined size is at least the product of the probabilities in two independent parts. Below either finite-size center, transfer from the proper model gives a fixed positive probability; above the combined center, it gives a probability tending to zero. These facts prevent the combined center from lying much below both smaller centers. A comparison with one extra variable handles adjacent sizes. Section 5 makes these steps precise and sums the errors along a balanced tree of nearly equal blocks. Its concentration-to-convergence theorem is then applied to the local variance and center bounds.

Section 6 uses a first moment at density six to bound the means of the three-clause indices, and gives exact relations between their cap conventions. It then specializes the forcing estimate and deduces concentration at the smaller cap. The improved mean bound permits a smaller transfer interval for either cap, sharpening the numerical constants while keeping the roles of the cap and the interval distinct. Section 7 explains the lower-arity cases and the finite-size information supplied by the proof.

Replacement and integrated forcing

We begin the local concentration proof by controlling how many variables are forced along the clause process. The estimate is integrated over prefix lengths: erasing one variable turns forcing into a difference of satisfiability probabilities, and those differences can be summed by telescoping.

For the fixed $k \ge3$, write

The value $+\infty$ is allowed in this definition, although $P_n(m) \le2^n(1-2^{-k})^m$ implies that $H_n$ is finite almost surely. Put

Thus $V_n$ is the last satisfiable index up to the cap $M_n$, and

This identity includes $m = M_n$. Later, when a clause is omitted, the same endpoint convention will count every additional satisfiable prefix.

Killing a solution set with one clause

A variable of a satisfiable formula $H$ is forced if all satisfying assignments of $H$ give it the same value. Let $b(H)$ be the number of forced variables, and set $b(H) = 0$ if $H$ is unsatisfiable. This definition uses all solutions of the entire formula, even when the formula contains clauses of different lengths.

For a formula $H$ on $v$ variables and $1 \le r \le v$, define

where $(u)_r = 0$ for nonnegative integers $u < r$. Here a random $r$-clause uses $r$ distinct uniform variables and independent fair signs.

If $H$ is satisfiable, $q_r(H)$ is exactly the probability that adding one independent random $r$-clause makes it unsatisfiable. Indeed, every solution of $H$ must falsify every literal in such a clause. Each chosen variable must therefore be forced, and its sign must oppose the forced value. Conversely those conditions make the clause false in every solution. For unsatisfiable $H$, the convention $q_r(H) = 0$ records that there is no transition to count.

Replacing a shorter clause

The next estimate is uniform in the background formula. This uniformity will allow successive replacements after conditioning on all other clauses.

Lemma 2.1 (Replacing a $(k-1)$-clause). Let $k \ge3$ and $n \ge k+1$ be integers, and put

For any formula $H$ on these $v$ variables, let $Q$ be an independent random $(k-1)$-clause and let $R_1,\ldots,R_g$ be independent random $k$-clauses, also independent of $H,Q$. Then

The power comparison below is the Boolean forced-variable instance of the codimension comparison in Carenini [6], Lemma 6.1. The proof records the block size and error needed for the present summation.

Proof. If $H$ is unsatisfiable, both unsatisfiability probabilities are one. Suppose it is satisfiable, and set $x=q_{k-1}(H)$ and $b=b(H)$. When $x \le\varepsilon$, the right side after subtracting $\varepsilon$ is nonpositive. Assume $x > \varepsilon$.

First $b \ge k$. Otherwise

The middle inequality follows from $\binom{n-1}{k-1}\ge n-1$, valid for $1\le k-1\le n-2$, and $2^{k-1}(n-1)\ge n$. For $b\ge k$, the exact killing probabilities give

Here $b-k+1\ge b/k$ and $v-k+1\le v$. For the last inequality, each factor $(b-j)/(v-j)$ is at most $b/v$, so $x\le(b/(2v))^{k-1}$. Consequently,

because $x>n^{-(k-1)/k}$.

The block makes $H$ unsatisfiable whenever at least one of its clauses does so individually. These individual events are independent conditional on $H$. Hence

For the last inequality, $0\le x\le2^{-(k-1)}\le1/4$, and $1-e^{-2x}-x$ vanishes at zero and has positive derivative on that interval.

Erasing one variable and summing over time

The following estimate is the input to the omission argument in Section 3. Unsatisfiable formulas contribute zero, and the sum includes the empty prefix and the cap.

Proposition 2.2 (Integrated forcing). For every fixed integer $k \ge3$,

Proof. It is enough to consider $n \ge k+1$. We first prove an explicit bound for every integer cap $M \ge0$, and then take $M=M_n$. The case $M=0$ is immediate, so assume $M \ge1$. By symmetry, the $j$-th summand is the probability that $F_{n,j}$ is satisfiable and $x_n$ is forced. Delete the clauses containing $x_n$, and let $d$ be their number. Then $d \sim\operatorname{Bin}(j,k/n)$. Conditional on their positions, the untouched formula $B$ is an independent proper $k$-SAT formula on $v=n-1$ variables with $j-d$ clauses. Erasing the literal on $x_n$ from each deleted clause leaves independent uniform $(k-1)$-clauses $Q_1,\ldots,Q_d$ on those $v$ variables, independent of $B$.

If $F_{n,j}$ is satisfiable and $x_n$ is forced, then

Indeed, any solution of the latter formula would extend to a solution of $F_{n,j}$ with either value of $x_n$.

Keep the incidence positions fixed. Replace each $Q_\ell$ in turn by $g$ fresh random $k$-clauses, with $g,\varepsilon$ as in Lemma 2.1. At a replacement step, condition on $B$, all other remaining shortened clauses, and all previously inserted blocks. The clause being replaced is still uniform and independent of this background, so the lemma bounds the loss in unsatisfiability probability by $\varepsilon$. Averaging at each step yields

The formula after all replacements has $j-d+dg$ independent proper $k$-clauses on $v$ variables. Since $B \notin\operatorname{SAT}$ is contained in the event on the left and has conditional probability $1-P_v(j-d)$, the conditional probability of (5) is at most

To sum this estimate, let $p_{j,d}=\mathbb{P}(\operatorname{Bin}(j,k/n)=d)$. For $0\le d\le j\le M$,

For fixed $d$, monotonicity of $P_v$ and telescoping give

For example, after shifting the second sum by $dg$, only the first $dg$ nonnegative terms can remain; if the shift exceeds the number of terms, that number is already at most $dg$. Use the envelope $(kM/n)^d/d!$ only for the nonnegative $\Delta_{j,d}$ term. The error $d\varepsilon$ is averaged with its original binomial weight, whose mean is $kj/n$. Therefore

At $M=M_n=L_kn$, the exponential factor depends only on $k$. The last expression is therefore $O_k(g+n\varepsilon)=O_k(n^{1/k})$, because $g=O_k(n^{1/k})$ and $n\varepsilon=n^{1/k}$.

Clause omission and polynomial concentration

We now turn the integrated forcing estimate into a bound on the fluctuations of the last satisfiable prefix. Omitting one clause can delay the loss of satisfiability. The delay counts the prefixes where that clause is pivotal, and its square counts pairs of pivotal times. The key observation is that a future punctured prefix can survive only if every intervening clause avoids killing the present solution set.

Omitting a clause without changing time indices

Fix an integer $M\ge1$ and the independent clauses $C_1,\ldots,C_M$. For the next two lemmas, let

be the last satisfiable index capped at $M$. For $1\le i\le M$, set

The time index $i$ is skipped; the remaining positions are not renumbered. Thus $V^{-i}\ge V$, and $V^{-i}$ is independent of $C_i$.

The following coordinate-omission inequality belongs to the martingale variance method associated with Efron and Stein [10] and Steele’s treatment of nonsymmetric statistics [20]. Boucheron, Bousquet, Lugosi, and Massart [4], Section 3.2, equation (3.6) state the arbitrary-omission form. The short proof fixes the deletion convention and constant.

Lemma 3.1 (Deletion variance bound). For the capped indices just defined,

Proof. Let $\mathcal{F}_i=\sigma(C_1,\ldots,C_i)$, with $\mathcal{F}_0$ trivial, and put

Independence of the clauses and the fact that $V^{-i}$ does not use $C_i$ give

For $Z_i=V-V^{-i}$, it follows that

The tower property and conditional Jensen inequality yield

The martingale differences are orthogonal and sum to $V-\mathbb{E}V$. Summing the displayed inequalities proves the lemma. □

Pairs of pivotal times

Fix $i$. For $i\leq m\leq M$, the punctured prefix and its killing probability are

The function $q_k$ was defined in (3); in particular, $q_m=0$ when $G_m$ is unsatisfiable.

Lemma 3.2 (Pivotal pairs). For every $1\leq i\leq M$,

Proof. Let

This event is exactly $\{V<m\leq V^{-i}\}$: prefix $m$ is satisfiable after omission and unsatisfiable before it. Hence, including the endpoint $m=M$,

For $\ell\geq m$, on $A_m$ the original prefix remains unsatisfiable, so

Condition on $\mathcal{F}^{(-i)}_m=\sigma(C_j:1\leq j\leq m,\ j\ne i)$. The clause $C_i$ and the future clauses $C_{m+1},\ldots,C_\ell$ are conditionally independent. The conditional probability of $A_m$ is $q_m$. If $G_m$ is satisfiable, then $G_\ell$ can be satisfiable only if none of these future clauses individually makes $G_m$ unsatisfiable. Each does so with probability $q_m$, independently. Thus

If $G_m$ is unsatisfiable, the relevant event and the right side are both zero.

Expand the square of the indicator sum and bound its double sum by twice the sum over $m \le\ell$. For $q > 0$,

because $m \ge1$. Multiplication by $q$, followed by expectation and summation over $m$, gives (8). When $q = 0$, every term in the corresponding product is zero, so no division by zero is needed.

The variance bound

The pivotal-pair estimate has reduced the squared omission delay to a truncated killing probability. Taking a $k$-th root converts that quantity into the forced fraction controlled by Proposition 2.2.

Proposition 3.3 (Polynomial concentration). For every fixed integer $k \ge3$, the statistic $V_n = \min(H_n - 1, L_kn)$ from (1) satisfies

In particular, with $\mu_n = \mathbb{E}V_n/n,$

Proof. Set $M = L_kn$, $V = V_n$, and fix $i$. With the notation of Lemma 3.2, let $\rho_m = b(G_m)/n$. The falling-factorial ratios in (3) give $q_m \le\rho_m^k$. Since $\min\{z,1\} \le z^{1/k}$ for $z \ge0$,

Unconditionally, $G_m$ has the law of $F_{n,m-1}$. Lemma 3.2 and Proposition 2.2 therefore give, uniformly in $1 \le i \le M$,

Summing over $M = L_kn$ indices in Lemma 3.1 proves (10). Chebyshev’s inequality proves (11), because

The exponent $\delta_k$ is positive for $k \ge3$, so the window $n^{1-\delta_k}$ is sublinear. The estimate is centered at the finite-size mean $n\mu_n$; comparing those means across sizes is a separate task.

Positive and finite center bounds

Before comparing different sizes, we place the centers in a fixed positive interval below the cap. At high density, an assignment first moment makes satisfiability unlikely. At a sufficiently small positive density, a matching from clauses to variables supplies a satisfying assignment regardless of the signs.

The matching criterion is Hall’s theorem [17]. Its application to satisfiability and the associated deficiency counting appear in Franco and Van Gelder [11], Section 8. We include the alternating-path argument and the probability estimate.

Lemma 4.1 (Bounds on the centers). For each fixed $k \ge3$, there is $a_0 > 0$ such that, for all sufficiently large $n$,

Proof. For any fixed assignment, each proper uniformly signed $k$-clause is satisfied with probability $1 - 2^{-k}$. The clauses are independent, so at $m = 2^k n$ the expected number of satisfying assignments is

Consequently $P_n(2^k n) = o(1)$. Since $V_n \le L_k n$,

For the lower bound, fix $c_0 > 0$ with $e^2c_0 < 1$ and put $m = \lfloor c_0n \rfloor< n$. A matching assigning each clause position a distinct variable occurring in that clause guarantees satisfiability: give each matched variable the value that satisfies its literal in the matched clause. These choices are compatible because the matched variables are distinct.

If no such matching exists, some $t$ clause positions use fewer than $t$ variables. To see this directly, take a maximum matching and start an alternating-path search from an unmatched clause. Every reached variable must be matched, or an augmenting path would exist. Its matched clause is then reached as well. The starting unmatched clause gives more reached clauses than reached variables, which is the asserted obstruction.

Enlarge a deficient variable set to a set of exactly $t$ variables. A union bound gives

Indeed, the probability that a proper clause lies in a specified $t$-set is $(t)_k/(n)_k \le(t/n)^k$, and it is zero for $t < k$. Bounding the two binomial coefficients by $(em/t)^t$ and $(en/t)^t$ first gives $[e^2c_0(t/n)^{k-2}]^t$. Since $k \ge3$ and $t < n$, this is at most the displayed summand. For the last limit, every fixed summand tends to zero, whereas the tail is bounded by the tail of the convergent geometric series $\sum_{t \ge1}(e^2c_0)^t$.

Thus $P_n(m) = 1 - o(1)$. Because $m \le M_n$, the survival identity (2) gives

An eventual lower bound $a_0 > 0$ and the asserted upper bound follow.

From concentration to a limiting location

The preceding estimates control fluctuations at one size. We now rule out drift of the centers as the number of variables grows. The argument has two steps. An auxiliary Poisson formula compares the satisfiability probabilities at a combined size and at two smaller sizes. Concentration turns this probability comparison into inequalities between centers, whose errors can then be summed along a balanced tree.

Recall that $H_n=\inf\{m\ge1:F_{n,m}\notin\mathrm{SAT}\}$ is the first unsatisfiable index in the proper-clause process. To state the comparison argument independently of the cap used above, fix $\lambda>0$ and define

Thus, for every integer $0\le m\le M_n^{(\lambda)}$,

This identity includes $m=M_n^{(\lambda)}$. The superscript keeps these statistics distinct from the particular $V_n$ and $\mu_n$ used in the preceding sections.

Theorem 5.1 (Concentration implies convergence). Fix an integer $k\ge3$ and $\lambda>0$. Suppose that the proper independent uniformly signed $k$-clause process has constants

such that, for all sufficiently large $n$,

Then $x_n^{(\lambda)}$ converges to some $\alpha\in[a,b]$, and

Moreover, for all sufficiently large $r,s$,

The first comparison holds without a restriction on $r/s$.

The input is a tail estimate about a finite-size mean. The conclusion gives convergence of that mean, while the quantitative comparison is one-sided. We begin with the probability inequality that supplies it.

An auxiliary product inequality

For every positive integer $n$ and $c \ge0$, let $s_n(c)$ be the satisfiability probability of the following auxiliary formula. Its number of clauses is $\operatorname{Pois}(cn)$. Within each clause, the $k$ variable indices are chosen independently and uniformly from $\{1,\ldots,n\}$, and their signs are independent and fair. The clauses are independent. The resulting literals are disjoined in the usual Boolean sense, so repeated variables and tautologies are allowed. This definition applies at every positive size, including $n=1$.

The following calculation is a Poisson form of the frozen-variable interpolation of Bayati, Gamarnik, and Tetali [3], Section 4, Proposition 2. Independence of the endpoint Poisson families gives the product that we need.

Lemma 5.2 (Auxiliary product inequality). For every pair of positive integers $r,s$ and every $c \ge0$,

Proof. Let $N=r+s$, and partition the variables into parts of sizes $n_1=r$ and $n_2=s$. For $0 \le t \le c$, take three independent Poisson families: a mean $Nt$ family of auxiliary clauses on all $N$ variables and, for $i=1,2$, a mean $n_i(c-t)$ family of auxiliary clauses confined to part $i$. Write $G_t$ for their conjunction and $f(t)=\mathbb{P}(G_t \in\mathrm{SAT})$.

We use the elementary add-one formula for a marked Poisson family. If a bounded observable has conditional expectations $a_j$ given exactly $j$ independent marks, then its expectation at mean $v$ is $\sum_{j\ge0}e^{-v}v^j a_j/j!$, whose derivative is $\sum_{j\ge0}e^{-v}v^j(a_{j+1}-a_j)/j!$. Both series converge uniformly on compact intervals of $v$, so the formula also applies after conditioning on the other two Poisson families.

For a satisfiable background $G_t$, let $b_i$ be the number of variables in part $i$ that are forced by the entire background: every satisfying assignment gives each such variable the same value. Set $b_i=0$ on unsatisfiable backgrounds. For a satisfiable background, a new auxiliary clause destroys satisfiability exactly when each of its literals is false in every satisfying assignment. Each literal must therefore oppose the value of a forced variable. Conversely, that condition makes the whole new clause false in every solution. The independent signed draws give killing probabilities

for a global clause and a clause confined to part $i$, respectively. This remains exact when an index is repeated: each independent signed draw must still be one of the literals false in every solution.

An unsatisfiable background remains unsatisfiable after any clause is added. The add-one formula, applied to the three means, therefore gives for $0<t<c$

The last inequality is convexity of $z\mapsto z^k$ on $[0,\infty)$, since $(b_1+b_2)/(2N)$ is the weighted average of $b_i/(2n_i)$ with weights $n_i/N$. At $t=0$ the two restricted formulas are independent, so $f(0)=s_r(c)s_s(c)$; at $t=c$, only the global formula remains, so $f(c)=s_N(c)$. Continuity at the endpoints proves the assertion for $c>0$, and $c=0$ is immediate. □

Transfer to proper clauses

For the rest of the proof of Theorem 5.1, assume its hypotheses and keep $k,\lambda,a,b,\delta,\eta,K$ fixed. Choose any density ceiling $D>b$. The elementary sandwich below does not use the concentration hypothesis; its tail consequences also use (15). The ceiling is independent of the cap parameter $\lambda$: the cap locates the survival events in (14), whereas $D$ bounds the expected number of clauses with internal repetitions in the auxiliary formula. Put

Lemma 5.3 (Proper-clause transfer). For $n \ge k$ set $\theta_n=(n)_k/n^k$, where $(n)_k=n(n-1)\cdots(n-k+1)$. If $0\le c\le D$ and $J\sim\operatorname{Pois}(cn\theta_n)$, then

If (15) holds, then there are constants $0\le K'<\infty$ and an integer $n_1\ge k$ such that for every $n\ge n_1$ and every $c\in[0,D]$,

The constants $K'$ and $n_1$ may depend on the fixed parameters, but not on $c$ or $n$.

Proof. An auxiliary clause has distinct indices with probability $\theta_n$. Poisson thinning separates the clauses into a family of $J$ clauses with distinct indices and a family of $Q$ clauses with an internal repetition, where

These counts are independent. Indeed, their joint probability-generating function is

The same independent-mark construction shows that, conditional on these counts, the marks in the two families are independent with their respective conditional laws. In the first family, every unordered set of $k$ distinct variables has $k!$ equally likely orders and the signs remain independent and fair. Conditional on $J$, this family therefore has exactly the law $F_{n,J}$.

A union bound over the $\binom{k}{2}$ pairs of variable positions gives

Consequently $cn-R\le\mathbb{E}J\le cn$ and $\operatorname{Var}(J)=\mathbb{E}J\le Dn$. Deleting the repeated-variable clauses can only help satisfiability. Requiring $Q=0$, which is independent of the proper family and has probability $e^{-cn(1-\theta_n)}\ge e^{-R}$, gives the lower bound. This proves (20). Write $h = n^{1-\delta}$. The concentration input and the survival identity give, for all sufficiently large $n$ and integer $j$,

For the first estimate the indicated counts are below the cap because $x_n^{(\lambda)} \le b < \lambda$. For the second, first use (14) up to the cap and then use monotonicity beyond it at $j_0=\lceil nx_n^{(\lambda)}+h\rceil$. The inequality $j_0 \le M_n^{(\lambda)}$ holds for all sufficiently large $n$: the gap $(\lambda-b)n$ dominates $h+2$. This also accounts for both integer roundings.

If $c \le x_n^{(\lambda)}-2n^{-\delta}$, then $\mathbb{E}J \le nx_n^{(\lambda)}-2h$. Chebyshev’s inequality yields

The lower bound in (20) is thus at least

which is at least $\kappa$ for every sufficiently large $n$.

If $c \ge x_n^{(\lambda)}+2n^{-\delta}$, then $\mathbb{E}J \ge nx_n^{(\lambda)}+2h-R$. For large $n$, $h>R$, and

The upper bound in (20) is at most this probability plus $Kn^{-\eta}$, proving (22) with $\gamma=\min\{\eta,1-2\delta\}$. All estimates used the common bounds $R$ and $Dn$, so they are uniform on $[0,D]$.

Comparing centers at different sizes

The lower transfer bound (21) stays positive, whereas the upper bound (22) tends to zero uniformly. We use this separation with the product inequality (18) to compare the centers.

Let $u=\min\{r,s\}$, $N=r+s$, and set

For all sufficiently large $u$, the center bounds in (5.3) put $c$ in $[0,D]$. Since $u^{-\delta}\ge r^{-\delta},s^{-\delta}$, the lower estimate in Lemma 5.3 applies at both sizes. Hence Lemma 5.2 gives $s_N(c)\ge\kappa^2$. For all sufficiently large $N$, the upper estimate in Lemma 5.3 is smaller than $\kappa^2$; it rules out $c\ge x_N^{(\lambda)}+2N^{-\delta}$. Therefore

This proves (16) for every pair of sufficiently large sizes. No ratio between them was used.

To reach every sufficiently large size from a fixed block size, we will use blocks of sizes $s$ and $s+1$. We therefore also need a neighboring-size comparison. Take $c=x_s^{(\lambda)}-2s^{-\delta}$, which again lies in $[0,D]$ for large $s$. In the size-one auxiliary model, the empty-formula event gives $s_1(c) \ge e^{-c} \ge e^{-D}$. Consequently

For large $s$, the upper transfer estimate at size $s+1$ is smaller than this fixed positive constant. It follows that

which proves (5.5).

The tree argument below uses the sum comparison only when its child sizes are comparable.

Summing the errors along a balanced tree

The principle that errors summable over geometrically increasing sizes cannot sustain macroscopic drift parallels the approximate-superadditivity argument of Abbe and Montanari [1] (arXiv version, Lemma 8). Here the operation is a minimum of normalized quantities; the following lemma proves the required form directly.

Lemma 5.4 (Balanced comparisons). Let $n_0 \ge1$ be an integer and let $(u_n)_{n\ge n_0}$ be a bounded real sequence. Suppose that $0 \le A < \infty$, $\beta> 0$, and that, for all $r,s \ge n_0$ with $1/3 \le r/s \le3,$

Suppose also that, for every $s \ge n_0$,

Then $u_n$ converges. More precisely, put

For every integer $s \ge\max\{n_0,2\}$ and every integer $n \ge s^2$,

Proof. Fix an integer $s \ge\max\{n_0,2\}$. For $n \ge s^2$, write $n=qs+t$, where $q=\lfloor n/s\rfloor\ge s$ and $0 \le t<s$. Thus $n$ is a sum of $q-t$ blocks of size $s$ and $t$ blocks of size $s+1$. Both block counts are nonnegative, and the neighbor inequality puts the value of every block at least $u_s-As^{-\beta}$.

Arrange these $q$ blocks in a binary tree by dividing each group of $a \ge2$ blocks into groups of $\lfloor a/2\rfloor$ and $\lceil a/2\rceil$ blocks. Each child contains at least $a/3$ blocks, so its total size is at least $sa/3$. Moreover, the ratio of the larger child’s total size to the smaller child’s is at most

The sum inequality is therefore valid at every internal node, with error at most $A(sa/3)^{-\beta}$. Iterating the minimum inequality from the leaves to the root gives a lower bound by the least leaf value minus the largest sum of errors on a leaf-to-root path. If $a_1,a_2,\ldots$ are the block counts at the successive internal nodes of such a path, then $a_1 \ge2$ and $a_{j+1} \ge(3/2)a_j$, because a child contains at most two thirds of its parent’s blocks. Every path error is consequently at most

This proves (5.11). First let $n \to\infty$ with $s$ fixed to obtain

Taking the limsup as $s \to\infty$ gives $\liminf_n u_n \ge\limsup_n u_n$. Boundedness makes both quantities finite, and hence $u_n$ converges. □

Completion of Theorem 5.1. Apply Lemma 5.4 to (5.4)–(5.5), with $A=4$ and $\beta=\delta$. It gives convergence, and the center bounds place the limit $\alpha$ in $[a,b]$.

Fix $0 \le c < \alpha$. Since $x_n^{(\lambda)} \to\alpha$ and $n^{-\delta} \to0$, for all sufficiently large $n$, $\lfloor cn\rfloor\le nx_n^{(\lambda)}-n^{1-\delta}$. This count lies below the cap, and (5.3) together with (5.2) gives $P_n(\lfloor cn\rfloor) \ge1-Kn^{-\eta} \to1$.

Now fix $c>\alpha$, and choose a real $d$ with $\alpha<d<\min\{c,\lambda\}$, which is possible because $\alpha\le b<\lambda$. For large $n$, the integer $\lfloor dn\rfloor$ lies below the cap and is at least $nx_n^{(\lambda)}+n^{1-\delta}$. The same two estimates give $P_n(\lfloor dn\rfloor)\le Kn^{-\eta}\to0$. Monotonicity then yields $P_n(\lfloor cn\rfloor)\le P_n(\lfloor dn\rfloor)\to0$. □

Application to every fixed clause size

We finish by checking the inputs for the statistic used in this paper. This also identifies the repetition constant furnished by the general transfer lemma.

Proof of Theorem 1.1. Fix $k\ge3$. Recall $L_k=2^{k+1}$, $V_n=\min\{H_n-1,L_kn\}$, and $\mu_n=\mathbb{E}V_n/n$. Since $L_k$ is an integer, the definitions in (5.1) with $\lambda=L_k$ give exactly $V_n^{(L_k)}=V_n$ and $x_n^{(L_k)}=\mu_n$.

Proposition 3.3 supplies the tail estimate in (5.3) with

and some $K=K_k<\infty$. These exponents satisfy $0<\delta<1/2$ and $\eta>0$. Lemma 4.1 supplies the center bounds with $a=a_0$ and $b=2^k+1<L_k$.

For the transfer in this application choose $D=L_k>b$. Then

Thus all hypotheses of Theorem 5.1 hold with the stated cap, center bounds, and exponents. It follows that $\mu_n\to\alpha_k\in[a_0,2^k+1]$ and that the proper-clause satisfiability probabilities tend to one for $0\le c<\alpha_k$ and to zero for $c>\alpha_k$, as claimed. □

Three-clause refinements

For three literals per clause, a first moment at density six improves the center bound enough to use the comparison interval $[0,8]$, including for the main cap $16n$. We also compare that statistic with last-satisfiable and first-unsatisfiable indices capped at $10n$. Changing the cap of the last-satisfiable index has an exponentially small effect on its normalized mean. Comparison with the first unsatisfiable index also includes a one-step shift.

Throughout this section the clauses are independent uniformly signed proper triples, sampled with replacement, and $n \ge3$. Recall the first unsatisfiable index $H_n$, and write

Thus $V_n$ is the statistic of the main proof at $k=3$. Put $\nu_n = \mathbb{E}W_n/n$, while $\mu_n = \mathbb{E}V_n/n$ as before. For integer $m$,

Only the last-satisfiable identity includes its capped endpoint.

The density-six bound and changes of cap

Each fixed assignment satisfies a proper triple with probability $7/8$, so $P_n(m) \le2^n(7/8)^m$. Set

The survival-sum identity for the positive integer $H_n$ gives the cap-independent bound

In particular, the normalized means of $W_n$, $T_n$, $V_n$ are all at most seven for large $n$. Splitting at $6n$ also gives the direct estimate

The matching argument in Lemma 4.1 gives $P_n(\lfloor c_0n\rfloor) = 1 - o(1)$ whenever $c_0 > 0$ and $e^2c_0 < 1$. These clause counts lie below both caps, so there is $a_0 > 0$ such that

The improved upper bound therefore applies to either cap.

The exact relations explain the distinction between first and last indices at the capped endpoint. With the common cap $10n$,

If $H_n \le10n$, the indices differ by one; otherwise both equal $10n$. To compare $V_n$ with $T_n - 1$, count the extra satisfiable prefixes:

The first term is necessary: $H_n = 10n + 1$ gives $E_n = 1$. Since $P_n(10n) \le\rho^n$, these identities imply

For the second estimate, center the identity $V_n=T_n-1+E_n$ and apply the reverse triangle inequality in $L^2$, using $\operatorname{sd}(E_n)\leq(\mathbb{E}E_n^2)^{1/2}$. Similarly,

Thus $\nu_n\to\alpha_3$, since the main proof already gives $\mu_n\to\alpha_3$.

Numerical forcing bound and concentration

The replacement parameters of Lemma 2.1 become $v=n-1$, $\varepsilon=n^{-2/3}$, and $g=\lceil6n^{1/3}\rceil$, for $n\geq4$. For a satisfiable background $B$, put $b=b(B)$ and $x=q_2(B)=b(b-1)/(4v(v-1))$. When $x>\varepsilon$, the proof of that lemma gives $b\geq3$, and the exact killing probabilities read

Here $b-2\geq b/3$, $\sqrt{b(b-1)}\leq b$, and $\sqrt{v(v-1)}\geq v-2$. Thus $gq_3(B)>2x$, and the lemma’s independent-block estimate is $1-(1-q_3(B))^g\geq1-e^{-2x}\geq x$. Together with the case $x\leq\varepsilon$, this recovers the uniform replacement loss $\varepsilon$.

The numerical forcing bound follows directly from (2.8) with $k=3$ and $M=10n$:

The constant 30 is the maximum mean incidence count $3M/n$. The general proof supplies the conditioning and telescoping needed for this estimate, including the prefix $j=10n$.

Concentration at the smaller cap follows even more directly from the main variance bound: $W_n=\min\{V_n,10n\}$. If $V'_n$ is an independent copy of $V_n$ and $W'_n=\min\{V'_n,10n\}$, truncation is 1-Lipschitz, so

Proposition 3.3 and Chebyshev’s inequality give

The same powers hold for $V_n$, with its own finite-size mean.

The comparison range is independent of the cap

In the auxiliary model, an ordered triple has distinct variable indices with probability

At density $c$, Poisson thinning separates a proper-clause count $J\sim\operatorname{Pois}(cn\vartheta_n)$ from an independent repeated-variable family with mean count $c(3-2/n)$. Therefore Lemma 5.3 gives, for every fixed $D\geq0$ and $0\leq c\leq D$,

The parameter $D$ controls the density at which probabilities are compared. The proof of Theorem 5.1 requires $D>b$; it need not equal the cap.

By (6.5) and (33), both $(\lambda,x_n^{(\lambda)})=(10,\nu_n)$ and $(\lambda,x_n^{(\lambda)})=(16,\mu_n)$ satisfy that theorem’s inputs with

Here $b<\lambda$ for either cap, $D>b$, and $\gamma=\min\{\eta,1-2\delta\}=1/6$. On $[0,8]$, the repetition mean is at most 24, so the sandwich is

For either choice $z_n=\nu_n$ or $z_n=\mu_n$, there is an absolute constant $K_8<\infty$ such that, uniformly on $0\le c\le8$ for all sufficiently large $n$,

The theorem also gives the corresponding size comparisons for either choice of center:

for all sufficiently large relevant sizes, without a restriction on $r/s$ in the first inequality.

If probabilities are instead compared over the wider interval $[0,16]$, the same calculation gives $R=48$, lower sandwich factor $e^{-48}$, and lower-transfer constant $e^{-48}/2$. These are the constants obtained from the generic choices $\lambda=16$, $b=9$, and $D=16$ in the main proof. The sharper mean bound permits $D=8$ for that same cap, while the $D=16$ calculation covers a larger range of densities.

Lower arities and finite-size information

The balanced comparison gives a one-sided quantitative bound on the finite-size centers. In (23), take $u_n=\mu_n$, $A=4$, and $\beta=\delta_k$, then let the larger size tend to infinity. For every sufficiently large integer $s$,

Thus the center cannot exceed its limit by more than the stated error. The proof gives no corresponding bound on $\alpha_k-\mu_s$, and hence no effective two-sided rate for approximating $\alpha_k$. Proposition 3.3 controls fluctuations about $\mathop{\mathrm{E}}V_n$; it does not place a two-sided window of width $n^{1-\delta_k}$ around $\alpha_kn$. All constants concern a fixed $k$, and are not uniform when $k$ grows with $n$.

Remark 7.1 (The two-clause boundary). Chvátal and Reed [7], Theorems 3–4 proved that independent uniform clauses on two distinct variables, sampled with replacement, are satisfiable with probability tending to one below density 1 and unsatisfiable with probability tending to one above density 1. Goerdt [15] obtained the threshold independently. Thus $\alpha_2=1$ in the same proper-clause convention. This is a separate theorem: the bound $O_k(n^{1+2/k})$ is only $O(n^2)$ at $k=2$ and gives no sublinear concentration window there.

Remark 7.2 (The unit-clause boundary). For $k = 1$, the threshold on the linear-density scale is zero. Fix $c > 0$, choose $0 < c' < c$, and Poissonize the number of independent uniform unit clauses at mean $c'n$. For each variable, the positive and negative occurrence counts are independent $\operatorname{Pois}(c'/2)$ variables, independently across variables. The formula is satisfiable exactly when no variable receives both signs, an event of probability

The Poisson clause count is at most $\lfloor cn\rfloor$ with probability tending to one. Monotonicity in the clause count therefore implies that the fixed-count unit-clause formula is unsatisfiable with probability tending to one at every $c > 0$. At density zero it is empty and satisfiable.