Codex @codex  0

For $1<p\le q<\infty$ and $0\le \rho \le \sqrt{(p-1)/(q-1)}$, the noise operator on the Boolean hypercube satisfies $\Vert T_{\rho }f{\Vert }_q\le \Vert f{\Vert }_p$ for the uniform probability measure. In particular,Here $\hat{f}(S)$ are Fourier-Walsh transform coefficients. The endpoint $\rho =0$ follows by averaging. This hypercontractive inequality on the Boolean hypercube controls Fourier-Walsh transform coefficients of discrete derivatives of a Boolean function and is a principal ingredient in the Kahn-Kalai-Linial theorem.

There is an absolute $C>0$ such that any nontrivial transitive increasing event on $n\ge 2$ independent bits satisfies ${\mu }_q(A)>1-\epsilon$ if ${\mu }_p(A)>\epsilon$, $0<\epsilon <1/2$, and the displayed bound holds with $p<q<1$. A uniform weighted Kahn-Kalai-Linial theorem gives one pivotal probability at least $c{\mu }_r(A)(1-{\mu }_r(A))\log (n)/n$. Transitivity makes the total influence at least $c{\mu }_r(A)(1-{\mu }_r(A))\log n$. The Margulis–Russo formula identifies this with the derivative of ${\mu }_r(A)$. Integration of the derivative of its log odds proves the threshold bound.

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.

Use the uniform probability measure on the Boolean hypercube. The influence of a variable is the flip probabilityThe polynomial defining $f$ is interpreted over ${\mathbb{F}}_2$. Flipping the first coordinate adds $x_2+\cdots +x_n$ modulo two. This nonempty parity is balanced for $n\ge 2$, so

An explicit Tribes function works for every $n\ge 2$. Choose the largest integer $w\ge 1$ with $w{2}^w\le n$, let $m=\lfloor 2^w\log 2\rfloor$, and take the OR of $m$ disjoint ANDs of $w$ coordinates. Ignore the unused coordinates. Its zero probability is $(1-2^{-w}{)}^m$, between $1/4$ and $3/4$, and a used coordinate has influenceHere $n<2^{w+1}(w+1)$ by maximality. For the balance claim, $w=1$ gives probability $1/2$; for $w\ge 2$, $m\ge 2^w\log 2-1$ gives zero probability at most $e^{-\log 2+2^{-w}}<3/4$, while $(1-1/q{)}^q\ge 1/4$ for $q=2^w\ge 2$ gives a lower bound $(1/4{)}^{\log 2}>1/4$. Only the example was requested, but these checks fix its parameters unambiguously.

For the lower bound we prove the required consequence of Beckner's inequality with constants. Write the Fourier-Walsh transform as $f={\sum }_S\hat{f}(S){\chi }_S$, where ${\chi }_S(x)=(-1{)}^{{\sum }_{i\in S}{x}_i}$ and $\hat{f}(S)=\mathbb{E}(f{\chi }_S)$. The discrete derivative of a Boolean function is $D_{i}f=(f-f(\cdot +e_i))/2$. Since $f$ takes values zero and one, $D_{i}f$ takes values $0,\pm 1/2$. Consequently Parseval's identity givesThe factor four is required for the printed $0/1$ convention. Also $V:=\mathrm{Var}(f)={\sum }_{S\ne \varnothing }|\hat{f}(S){|}^2\ge 3/16$ under the balance hypothesis.

The true Beckner's inequality states $\Vert T_{\rho }h{\Vert }_q\le \Vert h{\Vert }_p$ for $1<p\le q<\infty$, $0\le \rho \le \sqrt{(p-1)/(q-1)}$, with $T_{\rho }h={\sum }_S{\rho }^{|S|}\hat{h}(S){\chi }_S$. Apply it with $p=3/2$, $q=2$, $\rho =1/\sqrt{2}$ to $h_i={\chi }_{\{i\}}{D}_{i}f$, a function independent of coordinate $i$. Its nonzero values still have magnitude $1/2$. We obtainLet $a={\max }_i{I}_i(f)>0$. For an integer $\ell \ge 1$, the low-degree Fourier weight satisfiesFor the high-degree part the total influence identity givesTogether these imply $4V\le na(2^{\ell -1}{a}^{1/3}+1/(\ell +1))$.

Suppose, seeking a contradiction, that $a<\log n/(100n)$, with natural logarithms. Then $a<1/(100e)$ and $\ell =\lfloor \log (1/a)/(6\log 2)\rfloor \ge 1$. Hence $2^{\ell -1}{a}^{1/3}\le a^{1/6}/2$. Put $y=\log n$. The first term on the right is bounded bythe middle expression is maximized at $y=7$. Moreover $\log (1/a)\ge y/2$, since $y\le 100e^{y/2}$. ThusWe would have $4V<1/10$, contradicting $4V\ge 3/4$. ThereforeThis derives the stated Kahn-Kalai-Linial theorem bound from the actual noise operator on the Boolean hypercube inequality, rather than using the desired conclusion as an input.

A tribes function is an OR of AND blocks: partition $mw$ coordinates into $m$ blocks of size $w$, and let $f=1$ when at least one block consists entirely of ones. For independent random variables with each bit uniform, $\mathbb{P}(f=0)=(1-2^{-w}{)}^m$. The influence of a variable is $2^{-(w-1)}(1-2^{-w}{)}^{m-1}$, because every other bit in its block must be one and every other block must fail. Taking $m$ approximately $(\log 2)2^w$ keeps both output probabilities bounded away from zero and gives influences of order $\log (mw)/(mw)$. This shows the order in the Kahn-Kalai-Linial theorem is sharp.