OAI.RandomKSAT.variance_main

The theorem states that, for every integer k ≥ 3, three assertions hold about random k-SAT clause streams. A clause on n variables is a choice of k distinct variables together with a Boolean sign for each; an assignment satisfies it if it agrees with the clause's sign on at least one of its variables. A stream is an infinite sequence of independent clauses, each drawn uniformly from all such clauses (the product law streamLaw n k). The first failure time of a stream is the least m such that the first m clauses have no common satisfying assignment (infinite if none exists). H is this first-failure time converted to a real number, with an infinite value read as 0, and T B is the first-failure time truncated at cap ⌊B n⌋, likewise converted to a real number. Let ell(k,n) be log(e n) when k = 3 and 1 otherwise, and let U(k) = log 2 / (−log(1 − 2^(−k))). First, there is a constant C ≥ 0 such that for all n ≥ k the variance of H under streamLaw n k is at most C n ell(k,n). Second, for every B > 0 there is a constant C ≥ 0 (depending on B) such that for all n ≥ k the variance of T B is at most C n ell(k,n). Third, there is a constant c > 0 such that, for all sufficiently large n, the variance of H is at least c n, and for every B > U(k), for all sufficiently large n, the variance of T B is also at least c n; the threshold in n may depend on B, while c does not. The proof is admitted, not verified.