= Solution
We prove the following precise form of the <Friedgut-Kalai sharp threshold theorem>. There is an absolute $C$ such that, for a nontrivial <transitive increasing event> $A\subseteq\{0,1\}^n$, $n\geq2$, and $0<\varepsilon<1/2$, its success <probability> increases from $\varepsilon$ to $1-\varepsilon$ over an interval of length at most
$$
\boxed{\frac{C\log((1-\varepsilon)/\varepsilon)}{\log n}.}
$$
In particular, $\mu_p(A)>\varepsilon$ and $q-p\geq C\log((1-\varepsilon)/\varepsilon)/\log n$, with $p<q<1$, imply $\mu_q(A)>1-\varepsilon$. Here $\mu_p$ denotes independent bits equal to one with <probability> $p$. Symmetry means invariance under a permutation group acting transitively on the $n$ coordinates, not necessarily invariance under all coordinate permutations.
Use the allowed weighted-cube influence theorem in this exact form: an absolute $c>0$ exists such that, for every $n\geq2$, $0<p<1$, and zero-one <Boolean function> of mean $u$ under $\mu_p$, some coordinate has pivotal probability at least $cu(1-u)\log n/n$. A coordinate's pivotal event is determined by the other coordinates and means that the two possible values of that coordinate give different outputs. This uniform form is a consequence of the weighted <Kahn-Kalai-Linial theorem>; it applies to nonsymmetric functions as well.
Write $u(p)=\mu_p(A)$. Differentiating the finite product expression for $u(p)$, one coordinate at a time, gives
$$
u'(p)=\sum_{i=1}^n\mathbb E_p[f(x^{i\to1})-f(x^{i\to0})]=\sum_{i=1}^n I_i^{(p)}(f).
$$
The last equality uses monotonicity, so each summand is the pivotal probability. This derives the <Margulis–Russo formula> in the normalization being used. Transitivity makes all the <influences> equal; applying the weighted influence theorem therefore yields
$$
u'(p)\geq c\,u(p)(1-u(p))\log n.
$$
Nontriviality ensures $0<u(p)<1$ throughout $(0,1)$. Dividing and integrating the derivative of the log odds gives
$$
\log\frac{u(q)}{1-u(q)}-\log\frac{u(p)}{1-u(p)}\geq c(q-p)\log n.
$$
At the two specified quantiles the left side is $2\log((1-\varepsilon)/\varepsilon)$. Taking $C=2/c$ proves the window bound and, with a strict starting inequality, the asserted strict final inequality. This is the <sharp threshold> conclusion, rather than an assumption about a discontinuous finite-$n$ probability curve.
Back to article page
