Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 13 / 4

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\ge 2$, and $0<\epsilon <1/2$, its success probability increases from $\epsilon$ to $1-\epsilon$ over an interval of length at mostIn particular, ${\mu }_p(A)>\epsilon$ and $q-p\ge C\log ((1-\epsilon )/\epsilon )/\log n$, with $p<q<1$, imply ${\mu }_q(A)>1-\epsilon$. 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\ge 2$, $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, givesThe 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 yieldsNontriviality ensures $0<u(p)<1$ throughout $(0,1)$. Dividing and integrating the derivative of the log odds givesAt the two specified quantiles the left side is $2\log ((1-\epsilon )/\epsilon )$. 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.

Partition $N=mw$ bits into $m$ tribes of size $w$, and let the tribes function be one when some tribe consists entirely of ones. Permuting tribes and permuting bits within a tribe acts transitively on the $N$ coordinates, so this is a transitive increasing event. Under independent bits of density $p$, its exact success probability isChoose $m=\lfloor (\log 2)2^w\rfloor$. Then $u(1/2)\to 1/2$, while $\log N=w\log 2+O(\log w)$. For fixed $0<x<1$, its unique $x$-quantile isPut $a_x=-\log (1-x)$. Expanding $1-e^{-a_x/m}=a_x/m+O_x(m^{-2})$ givesThus, for fixed $0<\epsilon <1/2$,This positive window prevents an improvement to $o(1/\log N)$ in the Friedgut-Kalai sharp threshold theorem. Moreover, as the fixed error parameter tends to zero, the displayed logarithmic coefficient is $\log (1/\epsilon )+\log \log (1/\epsilon )+o(1)$, so the theorem's logarithmic error dependence is also optimal up to constants. This last comparison takes $w\to \infty$ for each fixed $\epsilon$; the expansion is not being claimed uniformly for arbitrarily tiny $w$-dependent errors.