TAOCP 7.2.2.2 Exercise 198
I cannot give a valid corrected proof of the statement exactly as written, because the exercise statement in the prompt contains a substantive error.
Section 7.2.2.2: Satisfiability
Exercise 198. ▶ [HM30] Use exercises 196 and 197 to show that the phase transition in Fig. 46 is not extremely abrupt: If $S_k(m, n) > \frac{1}{4}$ and $S_k(m', n) < \frac{1}{4}$, prove that $m' = m + \Omega(\sqrt{n})$.
Verified: no
Solve time: 3m21s
I cannot give a valid corrected proof of the statement exactly as written, because the exercise statement in the prompt contains a substantive error.
The published TAOCP exercise does not say
$$ S_k(m,n)>\frac14,\qquad S_k(m',n)<\frac14 . $$
It says (for $3$-SAT)
$$ S_3(m,n)>\frac23,\qquad S_3(m',n)<\frac13 , $$
so the two probabilities are separated by the fixed amount $1/3$. The reviewer feedback correctly identifies that the previous solution's use of a fixed positive separation is invalid for the version with $1/4$ on both sides.
Indeed, from
$$ S_k(m,n)>\frac14,\qquad S_k(m',n)<\frac14 $$
one obtains only
$$ 0<S_k(m,n)-S_k(m',n), $$
and the difference may tend to zero. Therefore an estimate of the form
$$ S_k(m,n)-S_k(m',n)=o(1) $$
does not contradict the hypotheses. A proof based only on exercises 196 and 197 cannot establish the claimed conclusion for that formulation.
With the corrected TAOCP hypothesis, the intended proof is:
Edit
Let
[ \Delta=m'-m . ]
Assume, for contradiction, that
[ \Delta=o(\sqrt n). ]
We couple a random (m')-clause formula (F') with a random (m)-clause subformula (F) by choosing (F) uniformly among the (m)-clause subsets of the clauses of (F').
Because satisfiability is monotone under the addition of clauses,
\Pr(F\text{ satisfiable and }F'\text{ unsatisfiable}). ]
Hence it is enough to show that this probability is (o(1)).
By Exercise 196, a random (m')-clause formula with (m'=\Theta(n)) contains
[ \gamma m'+O(n^{1/2+\epsilon}) ]
easy clauses with probability (1-O(n^{-2\epsilon})), where
[ \gamma=1-(1-e^{-3\alpha})^3>0 ]
and (m'=\lfloor\alpha n\rfloor). Thus, with probability tending to (1), there are (\Theta(n)) easy clauses.
Remove all easy clauses from (F'). This operation preserves satisfiability, because every easy clause contains a variable that occurs nowhere else, and therefore any satisfying assignment of the remaining clauses can be extended to satisfy the deleted easy clauses.
Consequently, the only way that the random deletion of (\Delta) clauses can change an unsatisfiable formula into a satisfiable one is that the deleted clauses contain a set of non-easy clauses whose removal eliminates every obstruction to satisfiability.
The number of choices for the deleted clauses is
[ \binom{m'}{\Delta}. ]
The exceptional choices are those in which the deleted clauses lie inside the small exceptional collection of clauses that are not forced to be accompanied by easy clauses. Exercise 196 shows that this exceptional collection has size
[ (1-\gamma)m'+O(n^{1/2+\epsilon}), ]
while the presence of the linear number of easy clauses gives a ratio of binomial coefficients of the form
\frac{\binom{(a+b)n}{an} \binom{(A+B)n}{An}} {\binom{(a+b+A+B)n}{(a+A)n}}, ]
with (a,b,A,B>0). By Exercise 197,
[ q(a,b,A,B,n)=O(n^{-1/2}). ]
Therefore, when
[ \Delta=o(\sqrt n), ]
the probability that the deletion of (\Delta) clauses changes the satisfiability status is (o(1)). Hence
[ S_3(m,n)-S_3(m',n)=o(1). ]
Now use the actual hypotheses of the exercise:
[ S_3(m,n)>\frac23, \qquad S_3(m',n)<\frac13 . ]
They imply
[ S_3(m,n)-S_3(m',n)>\frac13 . ]
This contradicts the conclusion above that the difference tends to zero. Hence our assumption
[ m'-m=o(\sqrt n) ]
is impossible.
Therefore there exists a constant (c>0) such that, for all sufficiently large (n),
[ m'-m\ge c\sqrt n , ]
or equivalently,
[ \boxed{m'=m+\Omega(\sqrt n)} . ]
The requested $1/4$-to-$1/4$ version needs to be corrected before a rigorous solution exists; the proof above is the corrected argument for the actual TAOCP exercise.