==== TABLE OF CONTENTS ====
A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//anchors.tex
A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//boundaries.tex
A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//concentration.tex
A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//convergence.tex
A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//forcing.tex
A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//introduction.tex
A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//paper.tex
A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//preamble.tex
A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//references.tex
A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//three-clause.tex
===========================
==== BEGIN A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//anchors.tex ====
\section{Positive and finite center bounds}\label{sec:anchors}
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~\cite{Hall}. Its application
to satisfiability and the associated deficiency counting appear in
Franco and Van Gelder~\cite[Section~8]{FV}. We include the
alternating-path argument and the probability estimate.
\begin{lemma}[Bounds on the centers]\label{lem:center-bounds}
For each fixed \(k\ge3\), there is \(a_0>0\) such that, for all
sufficiently large \(n\),
\[
a_0\le\mu_n\le2^k+1.
\]
\end{lemma}
\begin{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^kn\) the expected number of satisfying assignments is
\[
2^n(1-2^{-k})^{2^kn}\le(2/e)^n=o(1).
\]
Consequently \(P_n(2^kn)=o(1)\). Since \(V_n\le L_kn\),
\[
\mu_n\le2^k+(L_k-2^k)P_n(2^kn)=2^k+o(1).
\]
For the lower bound, fix \(c_0>0\) with \(e^2c_0<1\) and put
\(m=\lfloor c_0n\rfloor0\) and the asserted upper bound follow.
\end{proof}
==== END A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//anchors.tex ====
==== BEGIN A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//boundaries.tex ====
\section{Lower arities and finite-size information}\label{sec:boundaries}
The balanced comparison gives a one-sided quantitative bound on the
finite-size centers. In \eqref{eq:balanced-comparison-bound}, 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\),
\begin{equation}\label{eq:one-sided-center-rate}
\mu_s\le\alpha_k+C_k s^{-\delta_k},\qquad
C_k=4\left(1+\frac{(3/2)^{\delta_k}}
{1-(2/3)^{\delta_k}}\right).
\end{equation}
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~\ref{prop:concentration} controls fluctuations about
\(\EE 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\).
\begin{remark}[The two-clause boundary]\label{rem:two}
Chv\'atal and Reed~\cite[Theorems~3--4]{CR} 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~\cite{Goerdt} 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.
\end{remark}
\begin{remark}[The unit-clause boundary]\label{rem:unit}
For \(k=1\), the threshold on the linear-density scale is zero.
Fix \(c>0\), choose \(00\). At density zero it is
empty and satisfiable.
\end{remark}
==== END A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//boundaries.tex ====
==== BEGIN A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//concentration.tex ====
\section{Clause omission and polynomial concentration}\label{sec: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.
\subsection{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
\[
V=\max\{0\le m\le M:F_{n,m}\in\sat\}
\]
be the last satisfiable index capped at \(M\). For \(1\le i\le M\), set
\[
V^{-i}=\max\left\{0\le m\le M:
\bigwedge_{\substack{1\le j\le m\\j\ne i}}C_j\in\sat\right\}.
\]
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~\cite{EfronStein} and
Steele's treatment of nonsymmetric statistics~\cite{Steele}.
Boucheron, Bousquet, Lugosi, and Massart
\cite[Section~3.2, equation~(3.6)]{BBLM} state the arbitrary-omission
form. The short proof fixes the deletion convention and constant.
\begin{lemma}[Deletion variance bound]\label{lem:variance-deletion}
For the capped indices just defined,
\[
\Var(V)\le\sum_{i=1}^{M}\EE(V^{-i}-V)^2.
\]
\end{lemma}
\begin{proof}
Let \(\F_i=\sigma(C_1,\ldots,C_i)\), with \(\F_0\) trivial, and put
\[
D_i=\EE[V\mid\F_i]-\EE[V\mid\F_{i-1}].
\]
Independence of the clauses and the fact that \(V^{-i}\) does not use
\(C_i\) give
\[
\EE[V^{-i}\mid\F_i]=\EE[V^{-i}\mid\F_{i-1}].
\]
For \(Z_i=V-V^{-i}\), it follows that
\[
D_i=\EE[Z_i\mid\F_i]-\EE[Z_i\mid\F_{i-1}].
\]
The tower property and conditional Jensen inequality yield
\[
\EE D_i^2
=\EE\bigl(\EE[Z_i\mid\F_i]\bigr)^2
-\EE\bigl(\EE[Z_i\mid\F_{i-1}]\bigr)^2
\le\EE Z_i^2.
\]
The martingale differences are orthogonal and sum to \(V-\EE V\).
Summing the displayed inequalities proves the lemma.
\end{proof}
\subsection{Pairs of pivotal times}
Fix \(i\). For \(i\le m\le M\), the punctured prefix and its killing
probability are
\[
G_m=\bigwedge_{\substack{1\le j\le m\\j\ne i}}C_j,\qquad
q_m=q_k(G_m).
\]
The function \(q_k\) was defined in \eqref{eq:kill}; in particular,
\(q_m=0\) when \(G_m\) is unsatisfiable.
\begin{lemma}[Pivotal pairs]\label{lem:pivotal}
For every \(1\le i\le M\),
\begin{equation}\label{eq:pivotal}
\EE(V^{-i}-V)^2
\le2\sum_{m=i}^{M}\EE\min\{Mq_m,1\}.
\end{equation}
\end{lemma}
\begin{proof}
Let
\[
A_m=\{G_m\in\sat,\ G_m\wedge C_i\notin\sat\}.
\]
This event is exactly \(\{V0\),
\[
\sum_{\ell=m}^{M}(1-q)^{\ell-m}\le\min\{M,1/q\},
\]
because \(m\ge1\). Multiplication by \(q\), followed by expectation
and summation over \(m\), gives \eqref{eq:pivotal}. When \(q=0\), every
term in the corresponding product is zero, so no division by zero is
needed.
\end{proof}
\subsection{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~\ref{prop:forcing}.
\begin{proposition}[Polynomial concentration]\label{prop:concentration}
For every fixed integer \(k\ge3\), the statistic
\(V_n=\min(H_n-1,L_kn)\) from \eqref{eq:statistic} satisfies
\begin{equation}\label{eq:variance}
\Var(V_n)=O_k(n^{1+2/k}).
\end{equation}
In particular, with \(\mu_n=\EE V_n/n\),
\begin{equation}\label{eq:concentration}
\PP\bigl(|V_n-n\mu_n|\ge n^{1-\delta_k}\bigr)
=O_k(n^{-\eta_k}),\qquad
\delta_k=\frac{k-2}{4k},\quad \eta_k=\frac{k-2}{2k}.
\end{equation}
\end{proposition}
\begin{proof}
Set \(M=L_kn\), \(V=V_n\), and fix \(i\). With the notation of
Lemma~\ref{lem:pivotal}, let \(\rho_m=b(G_m)/n\).
The falling-factorial ratios in \eqref{eq:kill} give
\(q_m\le\rho_m^k\). Since \(\min\{z,1\}\le z^{1/k}\) for \(z\ge0\),
\[
\min\{Mq_m,1\}\le(Mq_m)^{1/k}\le M^{1/k}\rho_m.
\]
Unconditionally, \(G_m\) has the law of \(F_{n,m-1}\).
Lemma~\ref{lem:pivotal} and Proposition~\ref{prop:forcing} therefore
give, uniformly in \(1\le i\le M\),
\[
\EE(V^{-i}-V)^2
\le2M^{1/k}\sum_{m=i}^{M}\EE\rho_m
\le2M^{1/k}\sum_{j=0}^{M-1}\EE\frac{b(F_{n,j})}{n}
=O_k(n^{2/k}).
\]
Summing over \(M=L_kn\) indices in
Lemma~\ref{lem:variance-deletion} proves \eqref{eq:variance}.
Chebyshev's inequality proves \eqref{eq:concentration}, because
\[
1+\frac2k-2(1-\delta_k)
=-\left(1-\frac2k-2\delta_k\right)=-\eta_k.
\]
\end{proof}
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.
==== END A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//concentration.tex ====
==== BEGIN A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//convergence.tex ====
\section{From concentration to a limiting location}\label{sec:convergence}
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\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
\begin{equation}\label{eq:general-capped-center}
\begin{gathered}
M_n^{(\lambda)}=\lfloor\lambda n\rfloor,\qquad
V_n^{(\lambda)}=\min\{H_n-1,M_n^{(\lambda)}\},\\
x_n^{(\lambda)}=\frac{\EE V_n^{(\lambda)}}{n}.
\end{gathered}
\end{equation}
Thus, for every integer \(0\le m\le M_n^{(\lambda)}\),
\begin{equation}\label{eq:general-cap-survival}
P_n(m)=\PP\bigl(V_n^{(\lambda)}\ge m\bigr).
\end{equation}
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.
\Needspace{24\baselineskip}
\begin{samepage}
\begin{theorem}[Concentration implies convergence]
\label{thm:concentration-to-convergence}
Fix an integer \(k\ge3\) and \(\lambda>0\). Suppose that the proper
independent uniformly signed \(k\)-clause process has constants
\[
00,\qquad 0\le K<\infty
\]
such that, for all sufficiently large \(n\),
\begin{equation}\label{eq:convergence-input}
\begin{gathered}
a\le x_n^{(\lambda)}\le b,\\
\PP\left(\left|V_n^{(\lambda)}-nx_n^{(\lambda)}\right|
\ge n^{1-\delta}\right)\le K n^{-\eta}.
\end{gathered}
\end{equation}
Then \(x_n^{(\lambda)}\) converges to some \(\alpha\in[a,b]\), and
\[
\lim_{n\to\infty}P_n(\lfloor cn\rfloor)=
\begin{cases}
1,&0\le c<\alpha,\\
0,&c>\alpha.
\end{cases}
\]
Moreover, for all sufficiently large \(r,s\),
\begin{align}
x_{r+s}^{(\lambda)}
&\ge\min\{x_r^{(\lambda)},x_s^{(\lambda)}\}
-4\min\{r,s\}^{-\delta},\label{eq:convergence-sum}\\
x_{s+1}^{(\lambda)}
&\ge x_s^{(\lambda)}-4s^{-\delta}.
\label{eq:convergence-neighbor}
\end{align}
The first comparison holds without a restriction on \(r/s\).
\end{theorem}
\end{samepage}
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.
\subsection{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 \(\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
\cite[Section~4, Proposition~2]{BGT}. Independence of the endpoint
Poisson families gives the product that we need.
\begin{lemma}[Auxiliary product inequality]\label{lem:auxiliary-product}
For every pair of positive integers \(r,s\) and every \(c\ge0\),
\begin{equation}\label{eq:auxiliary-product}
s_{r+s}(c)\ge s_r(c)s_s(c).
\end{equation}
\end{lemma}
\begin{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)=\PP(G_t\in\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^ja_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
\[
\left(\frac{b_1+b_2}{2N}\right)^k
\quad\text{and}\quad
\left(\frac{b_i}{2n_i}\right)^k
\]
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 \(00\), and \(c=0\) is immediate.
\end{proof}
\subsection{Transfer to proper clauses}
For the rest of the proof of
Theorem~\ref{thm:concentration-to-convergence}, 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
\eqref{eq:convergence-input}. The ceiling is independent of the cap
parameter \(\lambda\): the cap locates the survival events in
\eqref{eq:general-cap-survival}, whereas \(D\) bounds the expected number
of clauses with internal repetitions in the auxiliary formula. Put
\begin{equation}\label{eq:transfer-parameters}
R=D\binom{k}{2},\qquad
\gamma=\min\{\eta,1-2\delta\}>0,\qquad
\kappa=\frac{e^{-R}}2.
\end{equation}
\begin{samepage}
\begin{lemma}[Proper-clause transfer]\label{lem:proper-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\Pois(cn\theta_n)\), then
\begin{equation}\label{eq:proper-sandwich}
\begin{gathered}
e^{-R}\EE P_n(J)\le s_n(c)\le\EE P_n(J),\\
cn-R\le\EE J\le cn,\qquad \Var(J)\le Dn.
\end{gathered}
\end{equation}
If \eqref{eq:convergence-input} 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]\),
\begin{align}
c\le x_n^{(\lambda)}-2n^{-\delta}
&\quad\Longrightarrow\quad s_n(c)\ge\kappa,
\label{eq:proper-transfer-low}\\
c\ge x_n^{(\lambda)}+2n^{-\delta}
&\quad\Longrightarrow\quad s_n(c)\le K'n^{-\gamma}.
\label{eq:proper-transfer-high}
\end{align}
The constants \(K'\) and \(n_1\) may depend on the fixed parameters,
but not on \(c\) or \(n\).
\end{lemma}
\end{samepage}
\begin{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
\[
J\sim\Pois(cn\theta_n),\qquad Q\sim\Pois(cn(1-\theta_n)).
\]
These counts are independent. Indeed, their joint probability-generating
function is
\[
\EE[z^Jw^Q]
=\exp\bigl(cn[\theta_n z+(1-\theta_n)w-1]\bigr)
=e^{cn\theta_n(z-1)}e^{cn(1-\theta_n)(w-1)}.
\]
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
\[
cn(1-\theta_n)\le c\binom{k}{2}\le R.
\]
Consequently \(cn-R\le\EE J\le cn\) and \(\Var(J)=\EE 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 \eqref{eq:proper-sandwich}.
Write \(h=n^{1-\delta}\). The concentration input and the survival
identity give, for all sufficiently large \(n\) and integer \(j\),
\begin{align*}
P_n(j)&\ge1-Kn^{-\eta}
&&\text{if }0\le j\le nx_n^{(\lambda)}-h,\\
P_n(j)&\le Kn^{-\eta}
&&\text{if }j\ge nx_n^{(\lambda)}+h.
\end{align*}
For the first estimate the indicated counts are below the cap because
\(x_n^{(\lambda)}\le b<\lambda\). For the second, first use
\eqref{eq:general-cap-survival} 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
\(\EE J\le nx_n^{(\lambda)}-2h\). Chebyshev's inequality yields
\[
\PP\bigl(J>nx_n^{(\lambda)}-h\bigr)
\le\frac{Dn}{h^2}=D n^{-(1-2\delta)}.
\]
\begin{samepage}
The lower bound in \eqref{eq:proper-sandwich} is thus at least
\[
e^{-R}\bigl(1-Kn^{-\eta}-D n^{-(1-2\delta)}\bigr),
\]
which is at least \(\kappa\) for every sufficiently large \(n\).
\end{samepage}
If \(c\ge x_n^{(\lambda)}+2n^{-\delta}\), then
\(\EE J\ge nx_n^{(\lambda)}+2h-R\). For large \(n\), \(h>R\), and
\[
\PP\bigl(Jc-2N^{-\delta}
\ge\min\{x_r^{(\lambda)},x_s^{(\lambda)}\}-4u^{-\delta}.
\]
This proves \eqref{eq:convergence-sum} 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
\[
s_{s+1}(c)\ge s_s(c)s_1(c)\ge\kappa e^{-D}.
\]
For large \(s\), the upper transfer estimate at size \(s+1\) is smaller
than this fixed positive constant. It follows that
\[
x_{s+1}^{(\lambda)}>c-2(s+1)^{-\delta}
\ge x_s^{(\lambda)}-4s^{-\delta},
\]
which proves \eqref{eq:convergence-neighbor}.
The tree argument below uses the sum comparison only when its child
sizes are comparable.
\subsection{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 \cite[arXiv version, Lemma~8]{AM}.
Here the operation is a minimum of normalized quantities; the following
lemma proves the required form directly.
\begin{samepage}
\begin{lemma}[Balanced comparisons]\label{lem:balanced-comparison}
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\),
\[
u_{r+s}\ge\min\{u_r,u_s\}-A\min\{r,s\}^{-\beta}.
\]
Suppose also that, for every \(s\ge n_0\),
\[
u_{s+1}\ge u_s-As^{-\beta}.
\]
Then \(u_n\) converges. More precisely, put
\[
B_\beta=\frac{(3/2)^\beta}{1-(2/3)^\beta}.
\]
For every integer \(s\ge\max\{n_0,2\}\) and every integer \(n\ge s^2\),
\begin{equation}\label{eq:balanced-comparison-bound}
u_n\ge u_s-A(1+B_\beta)s^{-\beta}.
\end{equation}
\end{lemma}
\end{samepage}
\begin{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\alpha\), and choose a real \(d\) with
\(\alpha0\). Lemma~\ref{lem:center-bounds}
supplies the center bounds with
\(a=a_0\) and \(b=2^k+1b\). Then
\[
R=L_k\binom{k}{2},\qquad
1-2\delta=\frac{k+2}{2k}>\eta,
\qquad \gamma=\eta,\qquad \kappa=\frac{e^{-R}}2.
\]
Thus all hypotheses of Theorem~\ref{thm:concentration-to-convergence}
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.
\end{proof}
==== END A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//convergence.tex ====
==== BEGIN A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//forcing.tex ====
\section{Replacement and integrated forcing}\label{sec: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.
\begin{samepage}
For the fixed \(k\ge3\), write
\[
H_n=\inf\{m\ge1:F_{n,m}\notin\sat\}.
\]
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
\begin{equation}\label{eq:statistic}
L_k=2^{k+1},\qquad M_n=L_kn,\qquad
V_n=\min\{H_n-1,M_n\},\qquad \mu_n=\frac{\EE V_n}{n}.
\end{equation}
Thus \(V_n\) is the last satisfiable index up to the cap \(M_n\), and
\begin{equation}\label{eq:survival}
P_n(m)=\PP(V_n\ge m)\qquad(0\le m\le M_n).
\end{equation}
This identity includes \(m=M_n\). Later, when a clause is omitted, the
same endpoint convention will count every additional satisfiable prefix.
\end{samepage}
\subsection{Killing a solution set with one clause}
A variable of a satisfiable formula \(H\) is \emph{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
\begin{equation}\label{eq:kill}
q_r(H)=\frac{\fall{b(H)}r}{2^r\fall vr},
\qquad
\fall ur=u(u-1)\cdots(u-r+1),
\end{equation}
where \(\fall ur=0\) for nonnegative integers \(u\eps\).
First \(b\ge k\). Otherwise
\[
x\le\frac{1}{2^{k-1}\binom{n-1}{k-1}}
\le\frac1n\le n^{-(k-1)/k}=\eps.
\]
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
\[
q_k(H)
=x\frac{b-k+1}{2(v-k+1)}
\ge \frac{x}{k}\frac{b}{2v}
\ge \frac1k x^{k/(k-1)}.
\]
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,
\[
gq_k(H)\ge2n^{1/k}x^{k/(k-1)}\ge2x,
\]
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
\[
\PP(H\wedge R_1\wedge\cdots\wedge R_g\notin\sat)
\ge1-(1-q_k(H))^g
\ge1-e^{-2x}
\ge x.
\]
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.
\end{proof}
\subsection{Erasing one variable and summing over time}
The following estimate is the input to the omission argument in
Section~\ref{sec:concentration}. Unsatisfiable formulas contribute zero,
and the sum includes the empty prefix and the cap.
\begin{proposition}[Integrated forcing]\label{prop:forcing}
For every fixed integer \(k\ge3\),
\begin{equation}\label{eq:integrated}
\sum_{j=0}^{M_n}\EE\frac{b(F_{n,j})}{n}=O_k(n^{1/k}),
\qquad M_n=2^{k+1}n.
\end{equation}
\end{proposition}
\begin{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\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
\begin{equation}\label{eq:forced-reduction}
B\in\sat,\qquad B\wedge Q_1\wedge\cdots\wedge Q_d\notin\sat.
\end{equation}
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,\eps\) as in
Lemma~\ref{lem:replacement}. 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 \(\eps\). Averaging at each step yields
\[
\PP(B\wedge Q_1\wedge\cdots\wedge Q_d\notin\sat
\mid\text{incidence positions})
\le1-P_v(j-d+dg)+d\eps.
\]
The formula after all replacements has \(j-d+dg\) independent proper
\(k\)-clauses on \(v\) variables. Since \(B\notin\sat\) is contained in
the event on the left and has conditional probability \(1-P_v(j-d)\),
the conditional probability of \eqref{eq:forced-reduction} is at most
\begin{equation}\label{eq:replacement-difference}
\Delta_{j,d}+d\eps,\qquad
\Delta_{j,d}=P_v(j-d)-P_v(j-d+dg)\ge0.
\end{equation}
To sum this estimate, let
\(p_{j,d}=\PP(\Bin(j,k/n)=d)\). For \(0\le d\le j\le M\),
\[
p_{j,d}\le\binom jd(k/n)^d\le\frac{(kM/n)^d}{d!}.
\]
For fixed \(d\), monotonicity of \(P_v\) and telescoping give
\begin{equation}\label{eq:telescoping}
\sum_{j=d}^{M}\Delta_{j,d}
=\sum_{t=0}^{M-d}\bigl[P_v(t)-P_v(t+dg)\bigr]\le dg.
\end{equation}
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\eps\) is averaged with its original
binomial weight, whose mean is \(kj/n\). Therefore
\begin{align}
\sum_{j=0}^{M}\EE\frac{b(F_{n,j})}{n}
&\le
\sum_{d=0}^{M}\frac{(kM/n)^d}{d!}
\sum_{j=d}^{M}\Delta_{j,d}
+\eps\sum_{j=0}^{M}\frac{kj}{n}\notag\\
&\le
g\sum_{d=0}^{\infty}\frac{d(kM/n)^d}{d!}
+\frac{kM(M+1)}{2n}\eps\notag\\
&=\frac{kM}{n}e^{kM/n}g+\frac{kM(M+1)}{2n}\eps.
\label{eq:forcing-general-cap}
\end{align}
At \(M=M_n=L_kn\), the exponential factor depends only on \(k\).
The last expression is therefore \(O_k(g+n\eps)=O_k(n^{1/k})\),
because \(g=O_k(n^{1/k})\) and \(n\eps=n^{1/k}\).
\end{proof}
==== END A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//forcing.tex ====
==== BEGIN A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//introduction.tex ====
\section{The limiting-threshold problem}\label{sec:intro}
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 \emph{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 nk\) possible
clauses has the same probability. Let \(C_1,C_2,\ldots\) be independent
clauses with this law, and define
\[
F_{n,m}=\bigwedge_{i=1}^{m}C_i,
\qquad P_n(m)=\PP(F_{n,m}\in\sat),\qquad m=0,1,2,\ldots.
\]
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.
\begin{theorem}\label{thm:main}
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,
\[
\lim_{n\to\infty}P_n(\lfloor cn\rfloor)
=
\begin{cases}
1,&0\le c<\alpha_k,\\
0,&c>\alpha_k.
\end{cases}
\]
\end{theorem}
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.
\subsection{Prior work and the role of the present argument}
Carenini~\cite[Theorem~1.1 and Corollary~1.2]{Carenini2026Polynomial}
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\'atal and Reed~\cite{CR} 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
\cite[Theorem~1.3]{Friedgut}, 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\'atal and Reed
\cite[Theorems~3--4]{CR}, who also credit independent proofs by Goerdt
and Fernandez de la Vega. Goerdt's journal treatment is~\cite{Goerdt}.
The implication-graph mechanism is separate from the proof given here.
For larger arities, Achlioptas and Peres~\cite{AP} obtained leading-order
bounds \(2^k\log2-O(k)\), using weighted second moments. The
statistical-physics work of M\'ezard, Parisi, and Zecchina~\cite{MPZ}
and of Mertens, M\'ezard, and Zecchina~\cite{MMZ} developed threshold
predictions through the cavity method and one-step replica symmetry
breaking. In particular, the latter work predicted the large-\(k\)
expansion
\[
2^k\log2-\frac{1+\log2}{2}+o_k(1),
\qquad o_k(1)\longrightarrow0\quad(k\longrightarrow\infty).
\]
Coja-Oghlan and Panagiotou~\cite[Theorem~1.1]{COP} 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~\cite{DSS} proved existence and identified the threshold with the
one-step replica symmetry breaking prediction for all sufficiently
large fixed \(k\). Theorem~\ref{thm:main} 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
\cite[Lemma~5.7]{Friedgut} gives a qualitative antecedent based on frozen
coordinates and sequential replacement. Carenini
\cite[Lemma~6.1 and Corollaries~6.2, 7.10--7.11]{Carenini} 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~\cite{GT} used interpolation to
establish thermodynamic limits for mean-field spin glasses.
Franz and Leone~\cite{FL}, and Franz, Leone, and Toninelli~\cite{FLT},
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~\cite[Section~4, Proposition~2]{BGT}
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
\cite[arXiv version, Section~4.3, Lemma~8 and Remark~3]{AM}, 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.
\subsection{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 \emph{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~\ref{sec:forcing} thereby
controls the total expected forced fraction along the process.
Section~\ref{sec:concentration} 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~\ref{sec:anchors}
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~\ref{sec:convergence} 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~\ref{sec:three-clause} 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~\ref{sec:boundaries} explains the lower-arity cases and the
finite-size information supplied by the proof.
==== END A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//introduction.tex ====
==== BEGIN A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//paper.tex ====
\documentclass[11pt]{article}
\input{preamble}
\title{A Limiting Satisfiability Threshold\\for Every Fixed Clause Size}
\author{OpenAI}
\date{September 25, 2026}
\begin{document}
\maketitle
\begin{abstract}
For every fixed integer \(k\ge3\), random \(k\)-SAT with independent
uniformly signed clauses on distinct variables, sampled with replacement,
has a finite positive limiting satisfiability threshold.
We credit Gaia Carenini~\cite{Carenini2026Polynomial} with priority for
resolving the satisfiability conjecture. This paper gives an alternative
proof, using concentration of a capped last satisfiable index and a
comparison between different system sizes.
\end{abstract}
\input{sections/introduction}
\input{sections/forcing}
\input{sections/concentration}
\input{sections/anchors}
\input{sections/convergence}
\input{sections/three-clause}
\input{sections/boundaries}
\input{references}
\end{document}
==== END A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//paper.tex ====
==== BEGIN A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//preamble.tex ====
\pdftrailerid{}
\pdfinfoomitdate=1
\pdfsuppressptexinfo=-1
\usepackage[T1]{fontenc}
\usepackage{mathpazo}
\usepackage[margin=1.12in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage[dvipsnames]{xcolor}
\usepackage{needspace}
\usepackage{hyperref}
\hypersetup{
colorlinks=true,
linkcolor=MidnightBlue,
citecolor=MidnightBlue,
urlcolor=MidnightBlue,
pdfauthor={OpenAI},
pdftitle={A Limiting Satisfiability Threshold for Every Fixed Clause Size},
pdfsubject={Convergence of the random k-SAT satisfiability threshold for every fixed k at least three}
}
\urlstyle{same}
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\PP}{\mathbb P}
\newcommand{\EE}{\mathbb E}
\newcommand{\Var}{\operatorname{Var}}
\newcommand{\Pois}{\operatorname{Pois}}
\newcommand{\Bin}{\operatorname{Bin}}
\newcommand{\ind}{\mathbf 1}
\newcommand{\sat}{\mathrm{SAT}}
\newcommand{\fall}[2]{(#1)_{#2}}
\newcommand{\eps}{\varepsilon}
\newcommand{\F}{\mathcal F}
\newcommand{\sd}{\operatorname{sd}}
\setlength{\emergencystretch}{2em}
\clubpenalty=10000
\widowpenalty=10000
\displaywidowpenalty=10000
==== END A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//preamble.tex ====
==== BEGIN A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//references.tex ====
\begingroup\small
\begin{thebibliography}{99}
\setlength{\itemsep}{0pt}
\bibitem{AM}
E.~Abbe and A.~Montanari,
\emph{On the concentration of the number of solutions of random
satisfiability formulas},
Random Structures Algorithms \textbf{45} (2014), no.~3, 362--382.
\href{https://doi.org/10.1002/rsa.20501}{doi:10.1002/rsa.20501};
\href{https://arxiv.org/abs/1006.3786v1}{arXiv:1006.3786v1}.
\bibitem{AP}
D.~Achlioptas and Y.~Peres,
\emph{The threshold for random \(k\)-SAT is \(2^k\log2-O(k)\)},
J. Amer. Math. Soc. \textbf{17} (2004), no.~4, 947--973.
\href{https://doi.org/10.1090/S0894-0347-04-00464-3}
{doi:10.1090/S0894-0347-04-00464-3}.
\bibitem{BGT}
M.~Bayati, D.~Gamarnik, and P.~Tetali,
\emph{Combinatorial approach to the interpolation method and scaling
limits in sparse random graphs},
Ann. Probab. \textbf{41} (2013), no.~6, 4080--4115.
\href{https://doi.org/10.1214/12-AOP816}{doi:10.1214/12-AOP816};
\href{https://arxiv.org/abs/0912.2444v3}{arXiv:0912.2444v3}.
\bibitem{BBLM}
S.~Boucheron, O.~Bousquet, G.~Lugosi, and P.~Massart,
\emph{Moment inequalities for functions of independent random variables},
Ann. Probab. \textbf{33} (2005), no.~2, 514--560.
\href{https://doi.org/10.1214/009117904000000856}
{doi:10.1214/009117904000000856};
\href{https://arxiv.org/abs/math/0503651v1}{arXiv:math/0503651v1}
(electronic reprint).
\bibitem{Carenini2026Polynomial}
G.~Carenini,
\emph{A polynomial scaling window for random \(k\)-SAT and a proof of
the satisfiability conjecture},
Electronic Colloquium on Computational Complexity,
Report TR26-229 (2026), published 5 October 2026.
\href{https://eccc.weizmann.ac.il/report/2026/229/}{ECCC Report TR26-229}.
\bibitem{Carenini}
G.~Carenini,
\emph{The Scaling Window of Random \(k\)-SAT},
Electronic Colloquium on Computational Complexity,
Report TR26-145 (2026), preprint;
\href{https://arxiv.org/abs/2609.26222v1}{arXiv:2609.26222v1}.
\href{https://eccc.weizmann.ac.il/report/2026/145/}{ECCC Report TR26-145}.
\bibitem{CR}
V.~Chv\'atal and B.~Reed,
\emph{Mick Gets Some (the Odds Are on His Side)},
Proc. 33rd Annual Symposium on Foundations of Computer Science (1992),
620--627.
\href{https://doi.org/10.1109/SFCS.1992.267789}{doi:10.1109/SFCS.1992.267789}.
\href{https://www.diochnos.com/teaching/CS5970/2020F/project-papers/ChvatalReed.pdf}{conference paper PDF}.
\bibitem{COP}
A.~Coja-Oghlan and K.~Panagiotou,
\emph{The asymptotic \(k\)-SAT threshold},
Adv. Math. \textbf{288} (2016), 985--1068.
\href{https://doi.org/10.1016/j.aim.2015.11.007}
{doi:10.1016/j.aim.2015.11.007};
\href{https://arxiv.org/abs/1310.2728v6}{arXiv:1310.2728v6}.
\bibitem{DSS}
J.~Ding, A.~Sly, and N.~Sun,
\emph{Proof of the satisfiability conjecture for large \(k\)},
Ann. of Math. (2) \textbf{196} (2022), no.~1, 1--388.
\href{https://doi.org/10.4007/annals.2022.196.1.1}
{doi:10.4007/annals.2022.196.1.1};
\href{https://arxiv.org/abs/1411.0650v3}{arXiv:1411.0650v3}.
\bibitem{EfronStein}
B.~Efron and C.~Stein,
\emph{The jackknife estimate of variance},
Ann. Statist. \textbf{9} (1981), no.~3, 586--596.
\href{https://doi.org/10.1214/aos/1176345462}{doi:10.1214/aos/1176345462}.
\bibitem{FV}
J.~Franco and A.~Van Gelder,
\emph{A perspective on certain polynomial-time solvable classes of
satisfiability},
Discrete Appl. Math. \textbf{125} (2003), nos.~2--3, 177--214.
\href{https://doi.org/10.1016/S0166-218X(01)00358-4}
{doi:10.1016/S0166-218X(01)00358-4}.
See also the \href{https://citeseerx.ist.psu.edu/document?doi=a79e4c87237fc557de1acc74371bc986f575a571&repid=rep1&type=pdf}{author manuscript dated 7 August 1998}, Section~8.
\bibitem{FL}
S.~Franz and M.~Leone,
\emph{Replica bounds for optimization problems and diluted spin systems},
J. Statist. Phys. \textbf{111} (2003), 535--564.
\href{https://doi.org/10.1023/A:1022885828956}{doi:10.1023/A:1022885828956};
\href{https://arxiv.org/abs/cond-mat/0208280v1}{arXiv:cond-mat/0208280v1}.
\bibitem{FLT}
S.~Franz, M.~Leone, and F.~L.~Toninelli,
\emph{Replica bounds for diluted non-Poissonian spin systems},
J. Phys. A \textbf{36} (2003), no.~43, 10967--10985.
\href{https://doi.org/10.1088/0305-4470/36/43/021}
{doi:10.1088/0305-4470/36/43/021};
\href{https://arxiv.org/abs/cond-mat/0307367v2}{arXiv:cond-mat/0307367v2}.
\bibitem{Friedgut}
E.~Friedgut, with an appendix by J.~Bourgain,
\emph{Sharp thresholds of graph properties, and the \(k\)-SAT problem},
J. Amer. Math. Soc. \textbf{12} (1999), no.~4, 1017--1054.
\href{https://doi.org/10.1090/S0894-0347-99-00305-7}
{doi:10.1090/S0894-0347-99-00305-7}.
\bibitem{Goerdt}
A.~Goerdt,
\emph{A threshold for unsatisfiability},
J. Comput. System Sci. \textbf{53} (1996), no.~3, 469--486.
\href{https://doi.org/10.1006/jcss.1996.0081}{doi:10.1006/jcss.1996.0081}.
\bibitem{GT}
F.~Guerra and F.~L.~Toninelli,
\emph{The thermodynamic limit in mean field spin glass models},
Comm. Math. Phys. \textbf{230} (2002), no.~1, 71--79.
\href{https://doi.org/10.1007/s00220-002-0699-y}
{doi:10.1007/s00220-002-0699-y};
\href{https://arxiv.org/abs/cond-mat/0204280v1}{arXiv:cond-mat/0204280v1}.
\bibitem{Hall}
P.~Hall,
\emph{On representatives of subsets},
J. London Math. Soc. \textbf{10} (1935), no.~1, 26--30.
\href{https://doi.org/10.1112/jlms/s1-10.37.26}{doi:10.1112/jlms/s1-10.37.26}.
\bibitem{MMZ}
S.~Mertens, M.~M\'ezard, and R.~Zecchina,
\emph{Threshold values of random \(K\)-SAT from the cavity method},
Random Structures Algorithms \textbf{28} (2006), no.~3, 340--373.
\href{https://doi.org/10.1002/rsa.20090}{doi:10.1002/rsa.20090};
\href{https://arxiv.org/abs/cs/0309020v2}{arXiv:cs/0309020v2}.
\bibitem{MPZ}
M.~M\'ezard, G.~Parisi, and R.~Zecchina,
\emph{Analytic and algorithmic solution of random satisfiability problems},
Science \textbf{297} (2002), no.~5582, 812--815.
\href{https://doi.org/10.1126/science.1073287}
{doi:10.1126/science.1073287}.
\bibitem{Steele}
J.~M.~Steele,
\emph{An Efron--Stein inequality for nonsymmetric statistics},
Ann. Statist. \textbf{14} (1986), no.~2, 753--758.
\href{https://doi.org/10.1214/aos/1176349952}{doi:10.1214/aos/1176349952}.
\end{thebibliography}
\endgroup
==== END A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//references.tex ====
==== BEGIN A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//three-clause.tex ====
\section{Three-clause refinements}\label{sec:three-clause}
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
\begin{equation}\label{eq:three-statistics}
W_n=\min\{H_n-1,10n\},\qquad
T_n=\min\{H_n,10n\},\qquad
V_n=\min\{H_n-1,16n\}.
\end{equation}
Thus \(V_n\) is the statistic of the main proof at \(k=3\). Put
\(\nu_n=\EE W_n/n\), while \(\mu_n=\EE V_n/n\) as before.
For integer \(m\),
\begin{equation}\label{eq:three-survival}
\begin{aligned}
P_n(m)&=\PP(W_n\ge m)&&\quad(0\le m\le10n),\\
P_n(m)&=\PP(T_n>m)&&\quad(0\le m<10n).
\end{aligned}
\end{equation}
Only the last-satisfiable identity includes its capped endpoint.
\subsection{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
\[
\sigma=2(7/8)^6<1,\qquad \rho=2(7/8)^{10}<1.
\]
The survival-sum identity for the positive integer \(H_n\) gives the
cap-independent bound
\begin{equation}\label{eq:three-h-mean}
\EE H_n=\sum_{m\ge0}P_n(m)
\le6n+\sum_{m\ge6n}2^n(7/8)^m
=6n+8\sigma^n.
\end{equation}
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
\begin{equation}\label{eq:three-center}
\nu_n\le6+4P_n(6n)\le6+4\sigma^n.
\end{equation}
The matching argument in Lemma~\ref{lem:center-bounds} 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
\begin{equation}\label{eq:three-anchors}
a_0\le\nu_n\le\mu_n\le7
\qquad\text{for all sufficiently large }n.
\end{equation}
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\),
\begin{equation}\label{eq:three-same-cap}
W_n=T_n-1+\ind_{\{H_n>10n\}}
=T_n-1+\ind_{\{F_{n,10n}\in\sat\}}.
\end{equation}
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:
\begin{equation}\label{eq:three-cross-cap}
\begin{gathered}
V_n=T_n-1+E_n,\qquad
E_n=\sum_{m=10n}^{16n}\ind_{\{H_n>m\}},\\
0\le E_n\le(6n+1)\ind_{\{H_n>10n\}}.
\end{gathered}
\end{equation}
The first term is necessary: \(H_n=10n+1\) gives \(E_n=1\).
Since \(P_n(10n)\le\rho^n\), these identities imply
\begin{align}
0\le\EE V_n-(\EE T_n-1)&\le(6n+1)\rho^n,
\label{eq:three-mean-bridge}\\
|\sd(V_n)-\sd(T_n)|&\le(6n+1)\rho^{n/2}.
\label{eq:three-sd-bridge}
\end{align}
For the second estimate, center the identity \(V_n=T_n-1+E_n\) and
apply the reverse triangle inequality in \(L^2\), using
\(\sd(E_n)\le(\EE E_n^2)^{1/2}\). Similarly,
\begin{equation}\label{eq:three-last-cap-bridge}
0\le V_n-W_n\le6n\ind_{\{H_n>10n\}},\qquad
0\le\mu_n-\nu_n\le6\rho^n.
\end{equation}
Thus \(\nu_n\to\alpha_3\), since the main proof already gives
\(\mu_n\to\alpha_3\).
\subsection{Numerical forcing bound and concentration}
The replacement parameters of Lemma~\ref{lem:replacement} become
\(v=n-1\), \(\varepsilon=n^{-2/3}\), and
\(g=\lceil6n^{1/3}\rceil\), for \(n\ge4\).
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\ge3\), and the exact killing probabilities read
\begin{equation}\label{eq:three-killing}
q_3(B)=x^{3/2}
\frac{b-2}{\sqrt{b(b-1)}}
\frac{\sqrt{v(v-1)}}{v-2}
\ge\frac13x^{3/2}.
\end{equation}
Here \(b-2\ge b/3\), \(\sqrt{b(b-1)}\le b\), and
\(\sqrt{v(v-1)}\ge v-2\). Thus \(gq_3(B)>2x\), and the lemma's
independent-block estimate is
\(1-(1-q_3(B))^g\ge1-e^{-2x}\ge x\).
Together with the case \(x\le\varepsilon\), this recovers the uniform
replacement loss \(\varepsilon\).
The numerical forcing bound follows directly from
\eqref{eq:forcing-general-cap} with \(k=3\) and \(M=10n\):
\begin{equation}\label{eq:three-forcing}
\sum_{j=0}^{10n}\EE\frac{b(F_{n,j})}{n}
\le30e^{30}\lceil6n^{1/3}\rceil
+(150n+15)n^{-2/3}
=O(n^{1/3}).
\end{equation}
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
\[
\Var(W_n)=\tfrac12\EE(W_n-W_n')^2
\le\tfrac12\EE(V_n-V_n')^2=\Var(V_n).
\]
Proposition~\ref{prop:concentration} and Chebyshev's inequality give
\begin{equation}\label{eq:three-concentration}
\Var(W_n)=O(n^{5/3}),\qquad
\PP\bigl(|W_n-n\nu_n|\ge n^{11/12}\bigr)=O(n^{-1/6}).
\end{equation}
The same powers hold for \(V_n\), with its own finite-size mean.
\subsection{The comparison range is independent of the cap}
In the auxiliary model, an ordered triple has distinct variable indices
with probability
\[
\vartheta_n=\frac{(n)_3}{n^3}=1-\frac3n+\frac2{n^2}.
\]
At density \(c\), Poisson thinning separates a proper-clause count
\(J\sim\Pois(cn\vartheta_n)\) from an independent repeated-variable
family with mean count \(c(3-2/n)\). Therefore
Lemma~\ref{lem:proper-transfer} gives, for every fixed \(D\ge0\) and
\(0\le c\le D\),
\begin{equation}\label{eq:three-density-sandwich}
e^{-3D}\EE P_n(J)\le s_n(c)\le\EE P_n(J),\qquad
cn-3D\le\EE J\le cn,\qquad \Var(J)\le Dn.
\end{equation}
The parameter \(D\) controls the density at which probabilities are
compared. The proof of Theorem~\ref{thm:concentration-to-convergence}
requires \(D>b\); it need not equal the cap.
By \eqref{eq:three-anchors} and \eqref{eq:three-concentration}, both
\((\lambda,x_n^{(\lambda)})=(10,\nu_n)\) and
\((\lambda,x_n^{(\lambda)})=(16,\mu_n)\) satisfy that theorem's inputs
with
\begin{equation}\label{eq:three-engine-parameters}
(a,b,\delta,\eta)=\left(a_0,7,\frac1{12},\frac16\right),\qquad
(D,R,\gamma,\kappa)=\left(8,24,\frac16,\frac{e^{-24}}2\right).
\end{equation}
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
\begin{equation}\label{eq:three-poisson-sandwich}
e^{-24}\EE P_n(J)\le s_n(c)\le\EE P_n(J),\qquad
cn-24\le\EE J\le cn,\qquad \Var(J)\le8n.
\end{equation}
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\),
\begin{align}
c\le z_n-2n^{-1/12}&\Longrightarrow s_n(c)\ge e^{-24}/2,
\label{eq:three-transfer-low}\\
c\ge z_n+2n^{-1/12}&\Longrightarrow s_n(c)\le K_8n^{-1/6}.
\label{eq:three-transfer-high}
\end{align}
The theorem also gives the corresponding size comparisons for either
choice of center:
\begin{align}
z_{r+s}&\ge\min\{z_r,z_s\}-4\min\{r,s\}^{-1/12},
\label{eq:three-center-sum}\\
z_{s+1}&\ge z_s-4s^{-1/12},
\label{eq:three-neighbor}
\end{align}
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.
==== END A-Limiting-Satisfiability-Threshold-for-Every-Fixed-Clause-Size//three-clause.tex ====