Limiting random SAT thresholds, sharp variance and computability

1 · The essentials

Imagine adding randomly chosen requirements to a collection of yes-or-no choices until no choice can satisfy them all. These manuscripts study where that breakdown occurs as the number of choices grows. Each requirement involves a fixed number $k$ of distinct choices, with positive and negative forms chosen uniformly and requirements sampled independently with possible repeats. For every fixed $k \geq 3$ , the main result establishes a finite, positive limiting boundary for the number of requirements per choice. The companion manuscripts show that the variance of the breakdown point grows in proportion to the number of choices, with constants allowed to depend on $k$ . For requirements involving three choices, another companion shows that a single deterministic machine can approximate the limiting boundary to any requested accuracy. The main result has a Lean formalization, although the supplied description does not specify its detailed scope or whether it covers the companion results.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine adding randomly selected rules to a yes-or-no questionnaire until no completed questionnaire can obey every rule. The threshold describes the limiting number of rules per question at which this happens, while the variance describes how much the stopping point differs between randomly generated questionnaires.

Why it matters

Existence of a limiting threshold gives a definite large-system boundary rather than only a sequence of finite-system transitions. The variance results quantify the fluctuations of the first failure point and remove a logarithmic loss for random 3-SAT. The computability result adds a different guarantee: for 3-SAT, the boundary can be approximated to prescribed accuracy without requiring a computable rate of finite-size convergence.

2 · Going further

The model is random $k$ -SAT on $n$ Boolean variables: clauses are independent, uniformly signed, use $k$ distinct variables, and are sampled with replacement. Let $H_{n}$ be the index of the first unsatisfiable prefix of the clause sequence. The main question is whether the satisfiability transition has a finite positive limiting clause density for every fixed integer $k \geq 3$ . The main manuscript establishes this limiting threshold and credits Gaia Carenini with priority for resolving the threshold-existence conjecture in the concurrent ECCC TR26-229, made public October 5, 2026.

The alternative argument described in the main abstract combines concentration of a capped last satisfiable index with a comparison between different system sizes. Capping limits the index being studied; concentration controls its fluctuations, while the size comparison connects systems with different numbers of variables. The supplied abstract does not give the detailed estimates. The main result has a Lean formalization, but its precise coverage is not specified in the supplied material.

The variance companions study $Var (H_{n})$ . For every fixed $k \geq 4$ , Manuscript 3 shows in the manuscript that $Var (H_{n}) = Θ_{k} (n)$ , meaning upper and lower bounds proportional to $n$ , with constants that may depend on $k$ . For $k = 3$ , that manuscript gives a linear lower bound and an $O (n lo g n)$ upper bound; Manuscript 2 sharpens the upper bound to obtain $Θ (n)$ . Its abstract attributes the matching lower bound to Wilson's transition-width theorem. Manuscript 3 also states that its upper bounds remain valid after clipping the hitting time at any fixed positive multiple of $n$ .

Manuscript 4 shows in the manuscript that the limiting random 3-SAT threshold is a computable real. A deletion estimate supplies explicit lower certificates, and a finite hierarchical approximation of the soft pressure supplies upper certificates at every rational density above the threshold. A fair search through these certificates halts and yields an approximation to any prescribed accuracy, without requiring a computable rate of finite-size convergence. This computability statement concerns 3-SAT, whereas the threshold-existence and combined linear-variance results concern every fixed $k \geq 3$ .

Useful notions

Boolean variables and satisfying assignments
Clauses and clause density
Independent random sampling
Variance and concentration
Limits and computable real numbers

What was known before / what is new

Before

The source credits Gaia Carenini with priority for resolving the threshold-existence conjecture in her concurrent ECCC TR26-229, made public October 5, 2026. It also describes an earlier 3-SAT variance estimate with a logarithmic loss. The 3-SAT variance abstract identifies Wilson's transition-width theorem as the basis for the matching lower bound.

New

This family supplies an alternative threshold-existence argument based on concentration and comparison across system sizes. Together, its variance manuscripts show in the manuscripts linear hitting-time variance for every fixed clause size $k \geq 3$ , including the sharper 3-SAT upper bound. The computability manuscript additionally gives a certificate-search method for approximating the random 3-SAT threshold to arbitrary prescribed accuracy.

Limits and assumptions

The conclusions concern independent, uniformly signed clauses using distinct variables within each clause, sampled with replacement, with clause size fixed at $k \geq 3$ . The variance constants may depend on that fixed clause size; the statements do not assert uniform bounds as $k$ grows. Computability is stated only for the 3-SAT threshold, and the supplied text gives neither a numerical threshold value nor an efficiency guarantee for the approximation machine. The main result has a Lean formalization, but the supplied description does not identify its exact scope or establish formal verification of the companion claims. The source does not specify further open problems, and it does not claim computability for larger clause sizes.

Mini glossary

Random k-SAT: A random collection of clauses, each requiring at least one of k signed Boolean variables to be satisfied, with distinct variables within each clause in the model considered here.
Clause density: The number of clauses divided by the number of variables.
Limiting satisfiability threshold: A limiting clause-density boundary separating the satisfiable and unsatisfiable regimes as the number of variables grows.
Hitting time: The index of the first prefix of the growing clause sequence that has no satisfying assignment.
Variance: The expected squared deviation of a random quantity from its mean.
Computable real: A real number that one finite deterministic machine can approximate to any prescribed accuracy.

Keywords : Random k-SAT · Hitting-time variance · Threshold computability

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

For random k-SAT with independent uniformly signed proper clauses sampled with replacement, proves finite positive limiting thresholds and hitting-time variance $Θ_{k} (n)$ for every fixed k ≥ 3, and computability of the 3-SAT threshold. We credit Gaia Carenini with priority for resolving the threshold-existence conjecture in her concurrent [ECCC TR26-229](https://eccc.weizmann.ac.il/report/2026/229/), made public October 5, 2026; this family supplies another proof and the sharper variance and computability results.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/235.md

Manuscripts in this family

★

A Limiting Satisfiability Threshold for Every Fixed Clause Size

25/09/2026

To be verified

For every fixed integer k ≥ 3, 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 [[5]](https://eccc.weizmann.ac.il/report/2026/229/) 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.

PDF GitHub folder

Linear Variance of the Random 3-SAT Hitting Time

05/10/2026

To be verified

For random 3-SAT on n Boolean variables, with independent uniformly signed clauses on three distinct variables sampled with replacement, we prove that the first unsatisfiable prefix has variance $Θ (n)$ . The upper bound removes the logarithmic loss in the earlier variance estimate; the matching lower bound follows from Wilson's transition-width theorem.

PDF GitHub folder

Variance of the Random k-SAT Hitting Time

27/09/2026

To be verified

Let H_n be the index of the first unsatisfiable prefix in random k-SAT on n variables, with independent uniformly signed clauses using k distinct variables and sampled with replacement. For every fixed k ≥ 4, we prove $Var (H_{n}) = Θ_{k} (n)$ . For k = 3, the variance is bounded below by a positive multiple of n and above by a constant multiple of $n lo g n$ ; the companion paper on random 3-SAT sharpens this to $Θ (n)$ . The same upper bounds proved here hold after clipping at any fixed positive multiple of n.

PDF GitHub folder

Computing the Random 3-SAT Threshold

27/09/2026

To be verified

The limiting satisfiability threshold of uniform random 3-SAT is a computable real. We credit Gaia Carenini [[4]](https://eccc.weizmann.ac.il/report/2026/229/) with priority for resolving the satisfiability conjecture, which establishes the threshold's existence. We prove that one finite deterministic machine can approximate it to any prescribed accuracy. A deletion estimate gives explicit lower certificates, while a finite hierarchical approximation of the soft pressure gives upper certificates at every larger rational density. A fair search through these certificates halts without requiring a computable rate of finite-size convergence.

PDF GitHub folder