Proof. We will use a two-to-four norm estimate to bound low-degree projections of the differences \(\Delta_i h\). Set \(\rho=\sigma/4\) and define the linear operator \(T\) by \(T\chi_A=\rho^{|A|}\chi_A\). We first prove \[ \|Tg\|_4\le\|g\|_2 \tag{4}\] for every real-valued function \(g\) on the product space. For one coordinate, \(|\chi_i|\le1/\sigma\) and \(\mathbb E\chi_i^2=1\) imply \(|\mathbb E\chi_i^3|\le1/\sigma\) and \(\mathbb E\chi_i^4\le1/\sigma^2\). For real \(a,b\), expansion and \(2|ab^3|\le a^2b^2+b^4\) give \[\begin{align*} \mathbb E(a+\rho b\chi_i)^4 &\le a^4+6\rho^2a^2b^2+ \frac{2\rho^3}{\sigma}(a^2b^2+b^4) +\frac{\rho^4}{\sigma^2}b^4\\ &=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\le1/2\).

To extend this estimate to the product, induct on \(|J|\), starting with the constant functions when \(J\) is empty. Write \(g=a+b\chi_i\), where \(a,b\) depend on the remaining coordinates, and use \(T\) for the operator on those coordinates as well. The one-coordinate estimate, applied pointwise, followed by the \(L^2\) triangle inequality gives \[\|Tg\|_4^2\le\|(Ta)^2+(Tb)^2\|_2 \le\|Ta\|_4^2+\|Tb\|_4^2 \le\|a\|_2^2+\|b\|_2^2=\|g\|_2^2.\] This proves (4).

Let \(P_{\le k}\) be the orthogonal projection onto the span of \(\chi_A\) with \(|A|\le k\). For every \(u\) in this span, \[\|u\|_4\le\|T^{-1}u\|_2\le\rho^{-k}\|u\|_2.\] Taking the supremum of \(|\mathbb E[gu]|\) over unit \(L^2\) vectors in this span, and applying Hölder’s inequality, therefore gives \[ \|P_{\le k}g\|_2\le\rho^{-k}\|g\|_{4/3}. \tag{5}\] These inequalities are valid for real \(k\ge0\), with no rounding required.

Each nonempty Fourier support is counted at least once when summed over its coordinates. Using the difference identity and enlarging the resulting degree cutoff from \(k-1\) to \(k\), we obtain \[\begin{align*} \sum_{1\le|S|\le k}\widehat h(S)^2 &\le\sigma^2\sum_{i\in J} \|P_{\le k}\Delta_i h\|_2^2 \\ &\le\sigma^2\rho^{-2k}\sum_{i\in J}I_i(h)^{3/2}. \tag{6}\end{align*}\] Here each projection acts on the coordinates other than \(i\), and \(\|\Delta_i h\|_{4/3}^2=I_i(h)^{3/2}\) because \(|\Delta_i h|\) is an indicator.

The function \(\sigma\log(4/\sigma)\) is increasing on \((0,1/2]\) and is at most \(2\). Hence \(\rho^{-2k}\le m^{1/16}\). If \(I(h)\le m^{1/4}\), then \(I_i(h)^{1/2}\le m^{-3/8}\), so (6) is at most \(\sigma^2m^{-5/16}I(h)\le m^{-1/4}I(h)\). If \(I(h)>m^{1/4}\), the right side of (3) exceeds \(1\), whereas its left side is at most \(\mathop{\mathrm{Var}}_p(h)\le1/4\). ◻

Proof. Fix \(B\) and an assignment \(y\) to the coordinates in \(E\setminus F_B\). Denote the resulting Boolean function on \(F_B\) by \(f_y\). Every permutation supported on \(B\) fixes each edge outside \(F_B\) individually, and consequently fixes \(y\). Thus \(f_y\) is invariant under all these permutations, regardless of the assignment.

An edge with \(j\) vertices in \(B\) has an orbit of size \(\binom mj\): its outside part is fixed and its inside part can be any \(j\)-subset of \(B\). Since \(1\le j\le r<m\), this size is at least \(m\). The free product measure is invariant under the same permutations, so influences are equal within each orbit. It follows that \[I_e(f_y)\le I(f_y)/m\qquad(e\in F_B).\] Lemma 2 therefore applies to every \(f_y\).

Average its conclusion over the product law of \(y\). For \(A\subseteq F_B\), the Fourier expansion of \(f\) gives \[\widehat{f_y}(A)= \sum_{D\subseteq E\setminus F_B}\widehat f(A\cup D)\chi_D(y).\] Orthonormality in the assigned coordinates yields \[\mathbb E_y\bigl[\widehat{f_y}(A)^2\bigr] =\sum_{D\subseteq E\setminus F_B}\widehat f(A\cup D)^2.\] Also \(\mathbb E_y I_e(f_y)=I_{e,p}(f)\) for every \(e\in F_B\), by conditioning the disagreement event. Consequently \[\sum_{S:\,1\le|S\cap F_B|\le k}\widehat f(S)^2 \le m^{-1/4}\sum_{e\in F_B}I_{e,p}(f).\] Finally average over \(B\). For each fixed edge \(e\), a union bound on its \(r\) vertices gives \(\Pr_B(e\in F_B)\le rm/n\), proving (7). ◻

Proof. Fix such an \(S\), write \(s=|S|\), and let \(V=\bigcup_{e\in S}e\) and \(v=|V|\). Because \(s\le\binom vr\le v^r\), the average degree of the hypergraph with edge set \(S\) is at most \[\frac{rs}{v}\le r s^{(r-1)/r}\le k.\] Choose a vertex \(u\in V\) of degree \(d_S(u)\) between \(1\) and \(k\). This choice depends only on \(S\), before \(B\) is sampled.

Conditional on \(u\in B\), each other vertex lies in \(B\) with probability \((m-1)/(n-1)\). The union bound and \(v\le rs\le rL\) therefore give \[\begin{align*} \Pr_B(B\cap V=\{u\}) &\ge\frac mn\left(1-(v-1)\frac{m-1}{n-1}\right)\\ &\ge\frac m{2n}. \end{align*}\] On this event, the edges of \(S\) meeting \(B\) are exactly those containing \(u\). Thus \(|S\cap F_B|=d_S(u)\in[1,k]\). ◻

Proof of Theorem 1. Fix \(r\ge3\) and write \(\alpha=r/(r-1)\). Choose an integer \(N_r>r\) such that, for every \(n\ge N_r\) and \(m=\lfloor\sqrt n\rfloor\), \[ \begin{gathered} m\ge r+1,\qquad \log m\ge\tfrac13\log n,\\ r(\log n)^\alpha n^{-1/2}\le\tfrac12,\qquad m^{-1/4}(\log n)^\alpha\le1. \end{gathered} \tag{11}\] Such an \(N_r\) exists: \(m\) is asymptotic to \(\sqrt n\), and any fixed power of \(\log n\) grows more slowly than a positive power of \(n\). In particular, the choice is independent of \(p\) and \(f\).

Assume first that \(n\ge N_r\), and set \[\sigma=\sqrt{p(1-p)},\qquad k=\frac{\sigma\log m}{64},\qquad L=(k/r)^\alpha.\] Both cutoffs are positive. Since \(k/r\le\log n\) and \[\frac{m-1}{n-1}\le\frac{\sqrt n-1}{n-1} =\frac1{\sqrt n+1}\le n^{-1/2},\] the third condition in (11) implies (8). Thus (10) and the fourth condition in (11) give \[ \sum_{1\le|S|\le L}\widehat f(S)^2 \le\frac{2r}{(\log n)^\alpha}I_p(f). \tag{12}\]

For the remaining degrees, (2) gives \[\sum_{|S|>L}\widehat f(S)^2 \le\frac1L\sum_S|S|\widehat f(S)^2 =\frac{\sigma^2}{L}I_p(f).\] The decisive bias dependence is \[ \frac{\sigma^2}{L} =\frac{(64r)^\alpha\sigma^{2-\alpha}}{(\log m)^\alpha} \le\frac{(192r)^\alpha}{(\log n)^\alpha}. \tag{13}\] Indeed \(2-\alpha=(r-2)/(r-1)>0\), \(\sigma\le1\), and \(\log m\ge(\log n)/3\). This estimate remains valid at arbitrarily small positive \(\sigma\). If \(L<1\), the low-degree sum is empty and the same tail estimate bounds the whole variance.

Adding the two parts proves (1) for \(n\ge N_r\) with constant \(2r+(192r)^\alpha\). For \(r\le n<N_r\), (2) gives \(\mathop{\mathrm{Var}}_p(f)\le\sigma^2 I_p(f)\le I_p(f)/4\). Therefore a valid choice for all \(n\) and \(p\) is \[C_r=\max\left\{2r+(192r)^\alpha,\, \frac{(\log N_r)^\alpha}{4}\right\}.\] ◻

Proof. The Margulis–Russo identity relates pivotal influences to the probability derivative; see [8], [10], and [5]. Here it follows directly by giving each coordinate its own bias: the expectation is affine in each bias separately, and its partial derivative in coordinate \(e\) is \(\mathbb E_p[f(x_{e\leftarrow1})-f(x_{e\leftarrow0})]\). Monotonicity identifies this with \(I_{e,p}(f)\). Differentiating along the common bias gives \(q'(p)=I_p(f)\).

Nontrivial monotonicity gives \(q(0)=0\) and \(q(1)=1\). Some pair of configurations differing in one coordinate has different values, so its pivotal event has positive probability for every \(0<p<1\). Hence \(q'(p)>0\) there, and the stated quantiles exist uniquely. Theorem 1 implies \[\frac{q'(p)}{q(p)(1-q(p))} \ge\frac{(\log n)^{r/(r-1)}}{C_r}.\] Integrating from \(p_\varepsilon\) to \(p_{1-\varepsilon}\), using the antiderivative \(\log(q/(1-q))\), proves the claim. ◻