OAI.RandomKSAT.sharpness

The theorem states the following for every integer k ≥ 3, in a model where an assignment on u variables is a Boolean vector, a width-s clause picks s distinct variables together with a required Boolean value for each, and is satisfied by an assignment that matches at least one of those values. Clauses are drawn independently and uniformly, and blockKill(u,s,S,g) is the probability that no assignment in a finite set S of assignments satisfies all of the first g random width-s clauses. The lifetime of S for width-s clauses is the sum over m ≥ 0 of the probability that S still has a surviving (nonempty) subset after m successive random clauses, each step keeping only the assignments that satisfy the new clause; it is the expected number of clauses until S is emptied. The conclusion is a conjunction of three claims. First, for every real γ < k/(k−1) and all positive reals D and A, and every N, there exist u ≥ max(N,k) and a nonempty set S of assignments such that the one-clause kill probability of width k−1, blockKill(u,k−1,S,1), is at least A·u^{−(k−1)}, while the width-k lifetime of S strictly exceeds D·blockKill(u,k−1,S,1)^{−γ}. Second, there are sizes u(g) ≥ k and nonempty sets S(g), for each g ≥ 2, such that blockKill(u(g),k−1,S(g),1) − blockKill(u(g),k,S(g),g) is asymptotically equivalent as g tends to infinity to 2^{−k}·g^{−(k−1)}. Third, there is no function e with e(g) = o(g^{−(k−1)}) such that for all u ≥ k, all nonempty S and all g ≥ 2 one has blockKill(u,k−1,S,1) − e(g) ≤ blockKill(u,k,S,g). The source states this as an admitted theorem with no proof supplied.