Proof. We first prove a product norm bound. Put \(\rho=\sigma/4\), so \(0<\rho\le1/8\), and define the linear operator \(T_\rho\) by \(T_\rho\chi_S=\rho^{|S|}\chi_S\). For one coordinate, the bound \(|\chi_i|\le\sigma^{-1}\) and the second moment identity imply \[|\mathbb E\chi_i^3|\le\sigma^{-1},\qquad \mathbb E\chi_i^4\le\sigma^{-2}.\] For real \(a,b\), expansion and \(2|ab^3|\le a^2b^2+b^4\) yield \[\begin{align*} \mathbb E(a+\rho b\chi_i)^4 &\le a^4+6\rho^2a^2b^2 +\frac{4\rho^3}{\sigma}|ab^3| +\frac{\rho^4}{\sigma^2}b^4\\ &\le a^4+\frac{13\sigma^2}{32}a^2b^2 +\frac{9\sigma^2}{256}b^4 \le(a^2+b^2)^2, \end{align*}\] where the last inequality uses \(\sigma^2\le1/4\).

To tensorize this inequality, induct on \(|J|\), the empty product being immediate. Write \(g=a+b\chi_i\) with \(a,b\) functions of the other coordinates, and set \(A=T_\rho a\), \(B=T_\rho b\), using the operator on those coordinates. Apply the scalar inequality pointwise and then the triangle inequality in \(L^2\) to obtain \[\|T_\rho g\|_4^2 \le \|A^2+B^2\|_2 \le \|A\|_4^2+\|B\|_4^2 \le \|a\|_2^2+\|b\|_2^2 =\|g\|_2^2.\] The penultimate inequality is the induction hypothesis. We have proved \[ \|T_\rho g\|_4\le\|g\|_2 \tag{6}\] on every finite product.

For any real \(d\ge0\), let \(P_{\le d}\) be the orthogonal projection onto the span of the characters of degree at most \(d\). If \(u=P_{\le d}u\), the operator \(T_\rho\) is invertible and Parseval gives \[\|T_\rho^{-1}u\|_2^2 =\sum_{|S|\le d}\rho^{-2|S|}\widehat u(S)^2 \le\rho^{-2d}\|u\|_2^2.\] Applying (6) to \(T_\rho^{-1}u\) proves \(\|u\|_4\le\rho^{-d}\|u\|_2\). Duality in this finite-dimensional subspace, followed by Hölder’s inequality, now gives for every real function \(v\) \[ \|P_{\le d}v\|_2 =\sup_{\substack{u=P_{\le d}u\\\|u\|_2=1}}|\mathbb E[vu]| \le\rho^{-d}\|v\|_{4/3}. \tag{7}\]

If \(k<1\), (5) is immediate, so assume \(k\ge1\). Since \(|\Delta_i h|\) is the indicator of a pivotal event, \(\|\Delta_i h\|_{4/3}=I_i(h)^{3/4}\). Every nonempty Fourier set is counted at least once when summing over its coordinates. The derivative coefficient identity and (7), applied on \(J\setminus\{i\}\) with \(d=k\), therefore show \[\begin{align*} \sum_{1\le |S|\le k}\widehat h(S)^2 &\le\sum_{i\in J}\sum_{\substack{S\ni i\\|S|\le k}} \widehat h(S)^2\\ &=\sigma^2\sum_{i\in J} \sum_{\substack{A\subseteq J\setminus\{i\}\\|A|\le k-1}} \widehat{\Delta_i h}(A)^2\\ &\le\sigma^2\rho^{-2k}\sum_{i\in J}I_i(h)^{3/2}. \end{align*}\] The function \(s\mapsto s\log(4/s)\) is increasing on \((0,1/2]\), since its derivative is \(\log(4/s)-1>0\). Hence \(\sigma\log(4/\sigma)\le\tfrac12\log8<2\), and \[\rho^{-2k} =m^{\sigma\log(4/\sigma)/32}\le m^{1/16}.\] If \(I(h)\le m^{1/4}\), the hypothesis implies \[\sum_i I_i(h)^{3/2} \le\sqrt{\frac{I(h)}m}\,I(h) \le m^{-3/8}I(h).\] The preceding estimates bound the desired sum by \(\sigma^2m^{-5/16}I(h)\le m^{-1/4}I(h)\), including when \(I(h)=0\). If \(I(h)>m^{1/4}\), Parseval and Booleanity instead give \[\sum_{1\le |S|\le k}\widehat h(S)^2 \le\mathbb Eh^2\le1<m^{-1/4}I(h).\] This proves the estimate for every \(0<p<1\), without a lower bound on \(\sigma\). ◻

Proof. Expand \(f\) in the product Fourier basis and integrate over \(x\). For each \(A\subseteq F\) this gives the exact finite identity \[\widehat{f_y}(A) =\sum_{D\subseteq H}\widehat f(A\cup D)\chi_D(y).\] Orthonormality on the exterior coordinates therefore gives \(\mathbb E_y\widehat{f_y}(A)^2 =\sum_{D\subseteq H}\widehat f(A\cup D)^2\). Summing over \(A\) proves (8). In particular, there is no constraint on the exterior Fourier degree \(|D|\).

For \(e\in F\), the pivotal event for \(f_y\) at \(e\) is the pivotal event for \(f\) at \(e\) with the exterior coordinates fixed to \(y\). Averaging over \(y\) and the remaining free coordinates gives \(\mathbb E_y I_e(f_y)=I_e(f)\); summation proves (9). ◻

Proof. Fix \(B\), and fix an arbitrary assignment \(y\) to \(H_B=E_n\setminus F_B\). The free set \(F_B\) contains all edges with at least one endpoint in \(B\): both edges within \(B\) and edges from \(B\) to its complement. Every permutation supported on \(B\) fixes each edge of \(H_B\) individually, and hence fixes \(y\). The restricted function \(f_y\) is consequently invariant under this permutation group even if the graph encoded by \(y\) has no symmetry.

The free-edge orbits are precisely the \(\binom m2\) edges within \(B\) and, for each fixed \(w\in[n]\setminus B\), the \(m\) edges \(\{\{u,w\}:u\in B\}\). Every orbit has size at least \(m\), since \(m\ge3\). The product law and the pivotal events are preserved by these permutations, so influences agree within each orbit. It follows that \[I_e(f_y)\le\frac{I(f_y)}m\qquad(e\in F_B).\] Lemma 3 applies separately to every \(y\). Its right-hand side is linear in \(I(f_y)\), so averaging and using Lemma 4 gives \[\sum_{\substack{S\subseteq E_n\\1\le |S\cap F_B|\le k}} \widehat f(S)^2 \le m^{-1/4}\sum_{e\in F_B}I_e(f).\] Finally average over \(B\). Each endpoint of a fixed edge belongs to \(B\) with probability \(m/n\), whence \(\Pr_B(e\in F_B)\le2m/n\). This proves (10). ◻

Proof. Fix a nonempty \(S\subseteq E_n\) with \(s=|S|\le k^2/2\), viewed as the edge set of a simple graph. Let \(V(S)\) be its set of nonisolated vertices and write \(v=|V(S)|\). Since \(s\le\binom v2<v^2/2\), its average degree over these vertices satisfies \[\frac{2s}{v}<\sqrt{2s}.\] Choose a vertex \(u\in V(S)\) whose degree \(d_S(u)\) is at most this average. Then \[ 1\le d_S(u)\le\sqrt{2s}\le k, \qquad v\le2s\le k^2. \tag{12}\]

Choose \(B\) uniformly among the \(m\)-element vertex sets. Conditioned on \(u\in B\), each other specified vertex belongs to \(B\) with probability \((m-1)/(n-1)\). A union bound gives \[ \Pr_B\{B\cap V(S)=\{u\}\} \ge \frac mn \left(1-(v-1)\frac{m-1}{n-1}\right). \tag{13}\] On this event, \(S\cap F_B\) consists of every support edge incident with \(u\), and contains no other support edge. Its size is therefore \(d_S(u)\), between \(1\) and \(k\); it need not be \(1\). Figure 1 illustrates this distinction.

To bound the probability uniformly in \(p\), note that \(k\le t\) and \[\frac{m-1}{n-1}\le\frac1{\sqrt n}, \qquad (v-1)\frac{m-1}{n-1} \le t^2e^{-t/2}\le256e^{-8}<\frac12.\] Here \(t^2e^{-t/2}\) is decreasing for \(t\ge16\). Consequently, for every support under consideration, \[ \Pr_B\{1\le|S\cap F_B|\le k\}\ge\frac{m}{2n}. \tag{14}\] The choice of \(u\) may depend on \(S\). The lower bound (14) is applied to each nonnegative summand \(\widehat f(S)^2\) separately; no block must capture all supports simultaneously. Comparing with (10) and cancelling \(m/(2n)\) proves (11). If \(k^2/2<1\), the sum in (11) is empty and the conclusion holds without choosing a support. ◻

Proof of Theorem 2. First suppose \(t=\log n\ge16\), and choose \(m\) and \(k\) as in Lemma 6; in particular \(m\ge3\) and \(k>0\). For the remaining Fourier degrees, the Dirichlet identity (4) gives \[ \sum_{|S|>k^2/2}\widehat f(S)^2 \le\frac2{k^2}\sum_S|S|\widehat f(S)^2 =\frac{2\sigma^2}{k^2}I(f). \tag{15}\] This remains valid for \(k^2/2<1\), when the left side includes all nonconstant coefficients. Combining (3), (11), and (15) yields \[ \mathop{\mathrm{Var}}(f)\le \left(4m^{-1/4}+\frac{2\sigma^2}{k^2}\right)I(f). \tag{16}\]

For completeness, all constants can be bounded independently of \(p\) and \(n\). Since \(m\ge\sqrt n/2\) and \(t\ge16\), \(\log m\ge t/2-\log2\ge t/3\). Thus \[\frac{2\sigma^2}{k^2} =\frac{8192}{(\log m)^2}\le\frac{73728}{t^2}.\] The cancellation of \(\sigma^2\) is exact, even when \(p\) is arbitrarily close to \(0\) or \(1\). Also, \(t^2e^{-t/8}\) is nonincreasing for \(t\ge16\), so \[4m^{-1/4}t^2 \le4\,2^{1/4}t^2e^{-t/8} \le4\,2^{1/4}\,256e^{-2}<256.\] Thus the right-hand side of (16) is at most \((73728+256)I(f)/t^2\), which is at most \(2^{17}I(f)/t^2\).

If instead \(2\le n<e^{16}\), the same Fourier identities immediately give \[\mathop{\mathrm{Var}}(f)\le\sigma^2I(f)\le\frac14 I(f) \le\frac{64}{(\log n)^2}I(f).\] Hence the single choice \(C_0=2^{17}\) works for every integer \(n\ge2\) and every \(p\in(0,1)\), as asserted. ◻

Proof of Theorem 1. Put \(f=\mathbf 1_{\mathcal P}\), \(\mu(p)=\mathbb E_p f\), and \(C_0=2^{17}\). We first verify the probability-derivative identity with the influence convention used here. If the edge probabilities are allowed to vary separately, \(\mathbb Ef\) is a multilinear polynomial in those probabilities. Its partial derivative in the probability at \(e\) is the expectation of \[\Delta_e f=f(x_{e\leftarrow1})-f(x_{e\leftarrow0}).\] For increasing \(f\), this difference takes values in \(\{0,1\}\), so its expectation is \(I_{e,p}(f)\) when all other biases are \(p\). Differentiating along the diagonal therefore gives \[ \mu'(p)=I_p(f). \tag{17}\] This is the usual probability-derivative formula underlying the sharp-threshold method; the calculation above proves it directly in the present finite setting.

Since \(f\) is Boolean, \(\mathop{\mathrm{Var}}_p(f)=\mu(p)(1-\mu(p))\). Theorem 2 and (17) imply \[ \mu'(p)\ge \frac{(\log n)^2}{C_0}\mu(p)(1-\mu(p)) \qquad(0<p<1). \tag{18}\] Nontriviality and monotonicity give \(f(\varnothing)=0\) and \(f(E_n)=1\). Both configurations have positive probability for every interior bias, hence \(0<\mu(p)<1\) there, while \(\mu(0)=0\) and \(\mu(1)=1\). Equation (18) now gives \(\mu'(p)>0\) throughout \((0,1)\). Thus, by continuity, every quantile \(p_a\) is the unique interior point satisfying \(\mu(p_a)=a\).

On the interval \([p_\varepsilon,p_{1-\varepsilon}]\), division in (18) is legitimate and gives \[\frac{d}{dp}\log\frac{\mu(p)}{1-\mu(p)} =\frac{\mu'(p)}{\mu(p)(1-\mu(p))} \ge\frac{(\log n)^2}{C_0}.\] Integration yields \[p_{1-\varepsilon}-p_\varepsilon \le\frac{2C_0}{(\log n)^2} \log\frac{1-\varepsilon}{\varepsilon}.\] Finally, \(4\varepsilon(1-\varepsilon)\le1\) implies \[\log\frac{1-\varepsilon}{\varepsilon} \le 2\log\frac1{2\varepsilon}.\] This proves (1) with \(4C_0=2^{19}\) for the entire range \(0<\varepsilon<1/2\). ◻