Proof. Fix a coordinate, and write \(f_-,f_+\) for its two sections. Replace them pointwise by \(\min(f_-,f_+),\max(f_-,f_+)\), respectively. Let \(T\) denote noise in the remaining coordinates and put \[a=T\bigl((f_-+f_+)/2\bigr),\qquad c=T\bigl((f_+-f_-)/2\bigr).\] Sorting preserves \(a\) and replaces \(c\) by \[c'=T\bigl(|f_+-f_-|/2\bigr)\ge |c|,\] since \(T\) has a nonnegative kernel. The two fully noised values are \(a\pm\rho c\) before sorting and \(a\pm\rho c'\) afterwards. For fixed \(a\), the function \(u\mapsto H(a+u)+H(a-u)\) is even and concave on its domain, and hence nonincreasing for \(u\ge0\). Thus sorting weakly decreases the pair average of \(H\). It preserves the mean.

Perform this operation once in each coordinate. If the function is already increasing in a different coordinate, both its sections are increasing in that coordinate; their pointwise minimum and maximum remain increasing. The resulting function is therefore increasing in every coordinate. ◻

Proof. For an increasing Boolean function, the coefficient of coordinate \(i\) is \[x_i=\mathbb E\bigl[(f_+-f_-)/2\bigr].\] The integrand takes values in \(\{0,1\}\), so \(x_i>0\) precisely when the coordinate is active. Choose a coordinate with the least active coefficient \(x\). For any four distinct active coordinates, \[x\le\frac{x_{i_1}+x_{i_2}+x_{i_3}+x_{i_4}}4 =\mathbb E[f(X)Z],\qquad Z=\frac{X_{i_1}+X_{i_2}+X_{i_3}+X_{i_4}}4.\] The distribution of \(Z\), in decreasing order, is \[\begin{array}{c|rrrrr} z&1&1/2&0&-1/2&-1\\ \hline \Pr(Z=z)&1/16&4/16&6/16&4/16&1/16. \end{array}\] At fixed mean \(m\), the largest possible \(\mathbb E[fZ]\) is obtained by placing the positive values of \(f\) at the largest values of \(Z\), allowing a fraction of the threshold level. Indeed, transfer of positive mass from a smaller value of \(Z\) to a larger one can only increase the objective; allowing fractional values is a relaxation and therefore gives an upper bound for Boolean \(f\). Since \(\mathbb EZ=0\) and the law of \(Z\) is symmetric, this maximum is twice the integral over its top fraction \(q=(1-|m|)/2\). For \(q\in[0,1/2]\) that quantity is \[\begin{cases} 2q,&0\le q\le1/16,\\ q+1/16,&1/16\le q\le5/16,\\ 3/8,&5/16\le q\le1/2. \end{cases}\] These are exactly the three pieces of \(b(m)\). Finally, the section means have average \(m\) and half-difference \(x\), proving the last claim. ◻

Proof. Induct on the number of active coordinates. Lemma 5(4) provides the cases with at most three. Otherwise choose the coordinate in Lemma 4, and denote its increasing sections by \(f_-\) and \(f_+\), with means \(m-x\) and \(m+x\). On the smaller cube let \[p_0=\frac{1+T_\rho f_-}{2},\qquad p_1=\frac{1+T_\rho f_+}{2}.\] In these expressions, \(T_\rho\) acts only on the remaining coordinates. Positivity of its kernel gives \(p_0\le p_1\), and \(\mathbb E(p_1-p_0)=x\). At the two values of the chosen coordinate the parent noise probabilities are \(p_\delta\) and \(p_{1-\delta}\).

Apply Equation (7) pointwise, allowing \(p_0=p_1\), in which case both \(D\) and the expression on the right vanish. Set \[y=\frac{\mathbb EG(p_1)}s,\qquad t=\frac{\mathbb EG(p_0)}s,\qquad e=\frac{\mathbb ED}s,\qquad k=\frac{s}{2L},\qquad Q=\alpha y+(1-\alpha)t.\] All of \(y,t,e,Q\) are nonnegative. To average the pair inequality, write \(w=p_1-p_0-(G(p_1)-G(p_0))/(4L)\). Cauchy–Schwarz yields \[\begin{split} (\mathbb ED)\,\mathbb E(S+\Lambda D) &\ge\left(\mathbb E\sqrt{D(S+\Lambda D)}\right)^2\\ &\ge\mu s^2(\mathbb E|w|)^2 \ge\mu s^2(\mathbb Ew)^2. \end{split}\] No fixed sign of \(w\) is required. Since \(\mathbb Ew=x-k(y-t)/2\), division by \(s^2\) gives \[ e(Q+\Lambda e)\ge\mu\left[x-\frac{k}{2}(y-t)\right]^2. \tag{12}\] The parent expectation divided by \(s\) equals \((y+t)/2+e\). Solving Equation (12) for the nonnegative variable \(e\) therefore gives the lower bound \[ R_x(y,t)=\frac{y+t}{2}+ \frac{\sqrt{Q^2+4\Lambda\mu v^2}-Q}{2\Lambda}, \qquad v=x-\frac{k}{2}(y-t). \tag{13}\]

We next justify substitution of the induction bounds into this root. Put \(\Delta=\sqrt{Q^2+4\Lambda\mu v^2}\). For \(y,t>0\), \[\begin{split} \partial_yR_x &=\frac12-\frac{\alpha}{2\Lambda} +\frac{\alpha Q-2\Lambda\mu kv}{2\Lambda\Delta},\\ \partial_tR_x &=\frac12-\frac{1-\alpha}{2\Lambda} +\frac{(1-\alpha)Q+2\Lambda\mu kv}{2\Lambda\Delta}. \end{split}\] Using \(Q\ge0\) and \(|v|/\Delta\le1/(2\sqrt{\Lambda\mu})\), each derivative is at least \[ \frac12\left(1-\frac{\max(\alpha,1-\alpha)}{\Lambda} -k\sqrt{\frac\mu\Lambda}\right)>0. \tag{14}\] For completeness, the strict sign follows by rational arithmetic from Table 1. If \(a=1-\max(\alpha,1-\alpha)/\Lambda\), every row has \(a>0\) and \[a^2-\left(\frac{s_{\rm hi}}{2L}\right)^2\frac\mu\Lambda \ge\frac{12133}{44180000}>0.\] Since \(s\le s_{\rm hi}\), this proves the sign in Equation (14). Continuity extends coordinatewise monotonicity of \(R_x\) to the whole nonnegative quadrant.

Each section has fewer active coordinates, so the induction hypothesis implies \(y\ge B_+\) and \(t\ge B_-\). We have consequently obtained the lower bound \(R_x(B_+,B_-)\) for the normalized parent expectation. In the notation of Lemma 5(3), at these arguments \[\frac{B_++B_-}{2}=B(m)-x^2A,\qquad Q=B(m)-x^2A+(2\alpha-1)xC,\qquad v=x(1-kC).\] If \(A\le0\), the first of these terms is already at least \(B(m)\), and the root correction in Equation (13) is nonnegative. Suppose \(A>0\). The correction is the nonnegative solution \(u\) of \(u(Q+\Lambda u)=\mu x^2(1-kC)^2\). Because \(Q\ge0\) and \(\Lambda>0\), the left side is increasing for \(u\ge0\). Equation (9), multiplied by \(x^2\), states that \[\begin{split} (x^2A)(Q+\Lambda x^2A) &=x^2A\bigl[B(m)+(2\alpha-1)xC+(\Lambda-1)x^2A\bigr]\\ &\le\mu x^2(1-kC)^2. \end{split}\] Thus the correction is at least \(x^2A\), and again \(R_x(B_+,B_-)\ge B(m)\). This completes the induction. ◻

Proof of Theorem 2. By Lemma 3, it suffices to consider increasing \(f\). Its dual \(f^*(x)=-f(-x)\) is also increasing and has mean \(-m\). Noise commutes with input reversal, so \(T_\rho f^*(x)=-T_\rho f(-x)\). Apply Proposition 6 to \(f\) and \(f^*\), average the two inequalities, and change variables \(x\mapsto-x\) in the second expectation. Equation (5) gives \[\mathbb EH(T_\rho f) \ge\frac{s}{2}\bigl(B(m)+B(-m)\bigr) \ge H(m)-1+s,\] where the last inequality is Equation (8). ◻

Proof. Put \(G=F(x)\) and \(\ell(G)=\log F'(x)\). Direct differentiation gives \[ \ell'(G)=\frac{3x}{2\sqrt{H(x)}},\qquad \ell''(G)=\frac34\left(H(x)+\frac1{H(x)}\right),\qquad \ell'''(G)=\frac{3x^3}{4H(x)^{3/2}}. \tag{29}\] Thus \(\ell\) is even and convex, and \(\ell''\) is increasing on the nonnegative half of its domain.

Consider an edge with distinct \(g\)-values \(G_-<G_+\), and let \(I=[G_-,G_+]\). Changing variables from \(x\) to \(G\) in the two differences shows that the ratio of its energy to \((D_i g)^2\) is \[\left(\frac1{|I|}\int_I e^{\ell(G)}\,dG\right) \left(\frac1{|I|}\int_I e^{-\ell(G)}\,dG\right) =\mathbb E\cosh\bigl(\ell(U)-\ell(V)\bigr),\] where \(U,V\) are independent uniform points of \(I\). For a fixed separation \(\delta=|U-V|\), the midpoint is uniform on the interval of length \(|I|-\delta\) with the same center as \(I\). The function \[A_\delta(c)=\ell(c+\delta/2)-\ell(c-\delta/2)\] is odd, and is increasing because \(A_\delta'(c)=\ell'(c+\delta/2)-\ell'(c-\delta/2)\ge0\). Consequently \(\cosh A_\delta(c)\) is even and increasing in \(|c|\). The integral of any such function over an interval of fixed length is minimized by centering that interval at zero: for positive center \(c\), the derivative of the integral is the value at the right endpoint minus the value at the left endpoint, which is nonnegative. The domain of \(\ell\) is the symmetric interval \((-F(1),F(1))\). Moving the center of \(I\) toward zero while keeping its length fixed keeps \(I\), and hence every conditional midpoint interval, in this domain. Applying the preceding fixed-length integral comparison conditionally on \(\delta\) proves that the displayed product of averages is minimized when \(I\) is centered at zero.

If that centered interval has endpoints \(\pm a\), its corresponding \(d\)-values are \(\pm x\), where \(F(x)=a\). Its energy is exactly \(x^2/H(x)=a^2+\Phi(a^2)\). Since \(a^2=(D_i g)^2\), this proves (28). A zero difference gives the same statement directly.

The symmetric-interval computation also gives, for \(v>0\), \[ j(v)=\frac14\int_{-1}^1\int_{-1}^1 \left[\cosh\bigl(\ell(\sqrt v\,a)-\ell(\sqrt v\,c)\bigr)-1\right] \,da\,dc. \tag{30}\] To prove convexity of the integrand in \(v\), use evenness of \(\ell\) and \(\cosh\) to replace \((a,c)\) by numbers \(A\ge C\ge0\). For \(B(v)=\ell(A\sqrt v)-\ell(C\sqrt v)\), differentiation gives \[B'(v)=\frac{z_A\ell'(z_A)-z_C\ell'(z_C)}{2v},\qquad B''(v)=\frac{Q(z_A)-Q(z_C)}{4v^2}, \quad z_A=A\sqrt v,\ z_C=C\sqrt v,\] where \(Q(z)=z(z\ell''(z)-\ell'(z))\). The function \(z\ell'(z)\) is increasing on \(z\ge0\), and \[Q'(z)=z\ell''(z)-\ell'(z)+z^2\ell'''(z)\ge0.\] Indeed, \(\ell'(0)=0\) and increasing \(\ell''\) imply \(\ell'(z)\le z\ell''(z)\), and (29) gives \(\ell'''(z)\ge0\). Thus \(B\) is nonnegative, increasing, and convex. Its composition with \(\cosh-1\) has the same properties. Averaging proves these properties for \(j\), including its continuous extension \(j(0)=0\). Now \(\Phi(v)=vj(v)\) gives \(\Phi'=j+vj'\ge0\) and \(\Phi''=2j'+vj''\ge0\). Finally, convexity and \(j(0)=0\) imply that \(j(v)/v\) is increasing, while \(j'\) is increasing. Therefore \[\frac{\Phi'(v)}v=\frac{j(v)}v+j'(v)\] is increasing as claimed. ◻

Proof. As \(b\) decreases, \(M\) increases. Lemma 11 therefore reduces the first three upper bounds to \(b_0=.839\). Set \(\alpha_0=F(\sqrt{1-b_0^2})/\sqrt{1-b_0^2}\). At this endpoint the positive binomial series, integrated term by term, gives \[\alpha_0\ge\sum_{j=0}^{5} \frac{(3/4)_j(1-b_0^2)^j}{j!(2j+1)}>a_0:=1.08834, \qquad \sqrt{b_0}>y_0:=.91595,\] where \((3/4)_0=1\) and \((3/4)_j=(3/4)(7/4)\cdots(3/4+j-1)\). Using \(\Phi(M)/M=1/(b\alpha^2)-1\) and (31), exact rational comparisons give \[\begin{align*} \frac1{b_0a_0^2}-1&<.006257<.0063,\\ P_0:=\frac{1+b_0^2}{2a_0b_0y_0}-1&<.018641<.019,\\ \frac{P_0}{(1-b_0^2)a_0^2}&<.053154<.0532. \end{align*}\] For the last bound, (26) and \(m^2\le r^4/4\) give \[\frac\Delta M\le \frac{r^3}{4(1+h)}\left(1+\frac1{bs}\right) <\frac{R_0^3}{4(1.999)} \left(1+\frac1{(.839)(.84)}\right)<.007720<.008.\] The numerical comparisons above are exact rational inequalities. The four bounds in (32) are also verified by the central-band certificate described in Appendix 9. ◻

Proof. For \(P_c(t)=2-t+c(1-t)^2\), define the differential residual \[E_c(t)=-(1-t^4)P_c'(t)-2(1-t^3P_c(t)).\] Expansion yields \[\begin{align*} \frac{E_{1/2}(t)}{(1-t)^2}&=t(2t^2-2t-1)\le0,\\ \frac{E_{3/4}(t)}{(1-t)^2} &=\tfrac12(2t+1)(3t^2-3t+1)>0. \end{align*}\] The first sign uses \(2t^2-2t-1\le-1\); for the second, \(3t^2-3t+1=3(t-1/2)^2+1/4\). To justify backward comparison despite the singular endpoint, fix \(t<v<1\). The error \(e=k-P_c\) satisfies \(e'-2t^3e/(1-t^4)=E_c/(1-t^4)\), whence \[e(t)=\sqrt{\frac{1-v^4}{1-t^4}}\,e(v) -\int_t^v\sqrt{\frac{1-z^4}{1-t^4}} \frac{E_c(z)}{1-z^4}\,dz.\] Both \(k(v)\) and \(P_c(v)\) tend to \(1\). The first term therefore vanishes as \(v\uparrow1\), and the integral converges. Its sign proves the two polynomial comparisons in (38).

Substitute these comparisons into (37). The sufficient numerators for the three derivative inequalities are, respectively, \[\begin{align*} 2(1-t^3P_{3/4})-(1-t^4) &=\tfrac12(1-t)^2(-3t^3+6t^2+4t+2),\\ 2(1-t^4)-2(1-t^3P_{1/2}) &=t^3(t-5)(t-1),\\ \tfrac{5-3t}{2}(1-t^4)-2(1-t^3P_{1/2}) &=\tfrac12(1-t)^2(5t^3-3t^2-t+1). \end{align*}\] The first two are nonnegative on \([0,1]\). For the last cubic, on \([0,.6]\) use \(5t^3-3t^2+.16=(5t+1)(5t-2)^2/25\ge0\), leaving at least \(.24\). On \([.6,1]\) write the cubic as \(t^2(5t-3)+(1-t)\ge0\). This proves the derivative bounds for \(t<1\). The Taylor expansion \(F(x)/x=1+x^2/4+O(x^4)\) at \(x=0\) shows that \(k'(1)=-1\). ◻

Proof. The integral identity in (37) gives exactly \[ D(u)=\frac{2\alpha}{y}(u-y)^2 +4\int_u^y(k(t)-\alpha)\,dt -(1-u^4)(k(u)-\alpha)^2. \tag{42}\] Let \(L=|u-y|\) and \(\lambda=|k(u)-k(y)|\). Monotonicity of \(k\) makes the integral nonnegative. A function with slope of magnitude at most \(2\) needs length at least \(\lambda/2\) to rise from \(0\) to \(\lambda\); the triangle of that base and height is a lower bound for its integral. Thus \[4\int_u^y(k(t)-\alpha)\,dt\ge\lambda^2.\] The lower derivative bound in Lemma 13 gives \(\lambda\ge L\), so (42) implies \[ D(u)\ge\left(\frac{2\alpha}{y}+u^4\right)L^2. \tag{43}\]

For explicit estimates, put \(a=1-u\), \(c=1-y\), and \[\begin{align*} A_-&=1+c+\tfrac12c^2,& A_+&=1+c+\tfrac34c^2,\\ B&=1+\tfrac12(a+c)+\tfrac14(a^2+ac+c^2),& J&=1+\tfrac34(a+c). \end{align*}\] Lemma 13, and its averages over the interval joining \(u\) and \(y\), give \[ A_-\le\alpha\le A_+,\qquad |g^2-M|\le4BL,\qquad |R|\le J L\sqrt{1-u^4}. \tag{44}\] In fact \(B\) is the average of the upper quadratic bound for \(k\), and \(J\) is the average of the upper linear bound for \(-k'\). Define \[ S(u,y)=2A_-+y\bigl(u^4-16C_0B^2-.20(u+y)^2\bigr). \tag{45}\] By (43)–(44), the left side minus the right side of (41) is at least \[ \frac{L^2}{y}S -2A_+JmL\sqrt{1-u^4}+.88m^2. \tag{46}\] If \(u\le .8\), then \(L=y-u>0\). Since \(b\le s\) and \(2m\le r^2\), \[2m\le r^2\le(1-b^2)^2=(1-y^4)^2.\] Dropping \(.88m^2\) and bounding \(\sqrt{1-u^4}\le1\) makes (46) at least \(LP_1/y\), where \[ P_1(u,y)=(y-u)S-A_+J(1-y^4)^2y. \tag{47}\] If \(u\ge .8\) and \(L>0\), the elementary inequality \[2A_+JmL\sqrt{1-u^4} \le .88m^2+\frac{(A_+J)^2L^2(1-u^4)}{.88}\] makes the same expression at least \(L^2P_2/(.88y)\), where \[ P_2(u,y)=.88S-(A_+J)^2(1-u^4)y. \tag{48}\] It therefore suffices, when \(L>0\), to prove the polynomial signs \[ \begin{aligned} P_1(u,y)&>0 &&(0\le u\le .8,\ .915\le y\le1),\\ P_2(u,y)&>0 &&(.8\le u\le1,\ .915\le y\le1). \end{aligned} \tag{49}\] Here is a finite rational certificate for these signs, using the Bernstein coefficient formula of Appendix 9. Map each stated rectangle affinely to \([0,1]^2\), with the \(u\) coordinate first. If the resulting power coefficients are \(c_{ab}\), its Bernstein coefficient of index \((i,j)\) and order \((N_1,N_2)\) is \[ \beta_{ij}=\sum_{a\le i,\,b\le j}c_{ab} \frac{\binom ia}{\binom{N_1}a} \frac{\binom jb}{\binom{N_2}b}. \tag{50}\] The orders and row minima are as follows; the final column records \(\lfloor1000\min_j\beta_{ij}\rfloor\) for successive \(i\).

Thus every coefficient is strictly positive. Bernstein basis functions are nonnegative and sum to one on the unit square, proving (49) on the closed rectangles. The formula and the explicit polynomials specify all arithmetic in the table; the executable certificate is verification/central_band.py. Appendix 9 gives the general certificate convention.

The two lower bounds above are therefore strictly positive whenever \(L>0\). Finally, when \(u=y\), all terms in (41) vanish except \(.88m^2\), which is nonnegative. This also proves the asserted strictness. ◻

Proof. Write \(T=\mathbb E(u^2-y^2)^2=\mathbb E(H(d)-b)^2\). Since \(\mathbb Ed=m\) and \(H(d)^2=1-d^2\), \(T=h^2-b^2-\operatorname{Var}d\). Lemma 9, using \(w\le1-m\), therefore gives \[T\ge(1-r^2)h^2-b^2-rs^2(1-m).\] The crossing identity implies \(sh-b=(1-s)(1-h)\ge0\). Substituting \(b^2\le s^2h^2\) proves \[ T\ge rs^2(m-m^2). \tag{52}\] For \(m>0\) this yields \[ \frac T{m^2}\ge s^2\left(\frac2r-r\right) \ge(1-R_0)\left(\frac2{R_0}-R_0\right)>4.5. \tag{53}\] Both positive factors in the middle expression decrease with \(r\) on \(0<r\le R_0\), and the final inequality is rational.

We also need to compare the calibration loss with \(\alpha^2m^2\). The upper bound for \(k(y)\) gives \(\alpha<1.1\) and \[\alpha y\le(1-c)(1+c+\tfrac34c^2) =1-\tfrac14c^2-\tfrac34c^3\le1, \qquad c=1-y\in[0,.085].\] Using (31) and \(s-b=m^2/(1+h)\), for \(m>0\) we obtain \[\begin{align*} \frac\Delta{(1+p_*)m^2} &=\frac\alpha y\,\frac2{1+h} \left(1-\frac{s-b}{s(1+b^2)}\right)\tag{54}\\ &>\alpha^2-\frac{(1.1)^2(.001)}{.84} >\alpha^2-.004. \end{align*}\] In the first factor of (54), \(\alpha/y\ge\alpha^2\); also \(2/(1+h)\ge1\). The subtracted relative loss is less than \(.001/.84\), by (26), which proves the next line.

Averaging (41) and applying (40) now gives \[\operatorname{Var}g-M\ge C_0V_0+.20T-(\alpha^2+.88)m^2.\] For \(m>0\), insert (53) and (54). The remaining strict margin is \(.20(4.5)-.88-.004=.016\), proving (51). For \(m=0\) one has \(b=s\) and \(\Delta=0\); the same averaged inequality proves (36). If any cube point has \(u\ne y\), Lemma 14 makes the averaged inequality strict. Since \(k>0\) in (37), the condition \(u=y\) is equivalent to \(g^2=M\), completing the strictness statement. ◻

Proof of Proposition 10. Recall that \(q\) is the total degree-one Fourier weight of \(g\), \(l\) is its largest coordinate weight, and \(H_0=\operatorname{Var}g-q\) is its weight above degree one.

The resources available to control \(q-l\) follow without losing the \(\Delta\) term. Namely, (24), (33), and (36) imply \[ H_0+C_0V_0\le\Phi(M)-\frac{p_*\Delta}{1+p_*}\le\Phi(M), \qquad q\ge M-\Phi(M)-\Delta>.985M>0. \tag{55}\] Indeed, substituting the variance gain into the first energy bound gives \[H_0+C_0V_0\le K-M+\frac{\Delta}{1+p_*}-\Phi(l) =\Phi(M)-\frac{p_*\Delta}{1+p_*}-\Phi(l).\] Since \(\Phi(l)\ge0\), this proves the first resource bound. Combining it with the variance gain once more yields \[q\ge M-\Phi(M)+2C_0V_0+\frac{p_*-1}{1+p_*}\Delta \ge M-\Phi(M)-\Delta.\] Thus the second inequality retains the full calibration loss; Lemma 12 gives \(1-.0063-.008=.9857>.985\).

Let \[L_1(x)=\sum_i a_i x_i,\qquad P=L_1^2-q,\qquad W=\mathbb EP^2=2\left(q^2-\sum_i a_i^4\right).\] Since \(\sum_i a_i^4\le lq\), \[ q-l\le\frac W{2q}. \tag{56}\] Write \(g=\mu+L_1+Z\), with \(\mu=\mathbb Eg\) and \(Z\) containing only Fourier degrees at least two; thus \(\mathbb EZ^2=H_0\). The degree-three part of \(L_1P\) has coefficient \(6a_i a_j a_k\) on \(x_ix_jx_k\), so its squared norm is \[36\sum_{i<j<k}a_i^2a_j^2a_k^2\le3qW.\] To see the last inequality, write \(W=4\sum_{i<j}a_i^2a_j^2\): in \(qW\) each distinct triple occurs three times, with total coefficient \(12\), and all remaining terms are nonnegative. Only that degree-three part of \(L_1P\) pairs with \(Z\). Also \(P\ge-q\), \(\mathbb EP=\mathbb EL_1P=0\), and \(\mathbb EL_1^2P=W\). Expanding \(g^2P\) and applying Cauchy–Schwarz therefore gives \[ \sqrt{V_0W}\ge\mathbb E[g^2P] \ge W-(2\sqrt{3q}+2|\mu|)\sqrt{WH_0}-qH_0. \tag{57}\] The first inequality uses \(\mathbb E[g^2P]=\mathbb E[(g^2-M)P]\). For the last inequality the three error terms are \(2\mathbb E(L_1PZ)\), \(2\mu\mathbb E(PZ)\), and \(\mathbb E(Z^2P)\), bounded below by \(-2\sqrt{3qWH_0}\), \(-2|\mu|\sqrt{WH_0}\), and \(-qH_0\) respectively.

The mean term is small. Lemma 13 and (37) give \[|g-\alpha d|\le2|u-y|\le\tfrac12|g^2-M|.\] Together with (55) this proves \[ \frac{|\mu|}{\sqrt q} \le\frac{m/x_0+\tfrac12\sqrt{.0063/C_0}}{\sqrt{.985}} \le\frac{R_0(.543)/2+.431/2}{.9924}<.298<.31. \tag{58}\] Here \(m/x_0\le r^{3/2}/2\), and the rational comparisons \((.543)^2>R_0\), \((.431)^2>.0063/.034\), and \((.9924)^2<.985\) justify all square-root bounds.

Set \(A=\sqrt{V_0}\), \(B_0=\sqrt{qH_0}\), and \(z=\sqrt W\). Equations (57) and (58) imply \[z^2\le Az+(2\sqrt3+.62)B_0z+B_0^2.\] Writing \(c_0=2\sqrt3+.62\), the positive root of this quadratic is at most \(A+4.32B_0\). Indeed, substituting that value in the polynomial \(z^2-(A+c_0B_0)z-B_0^2\) gives \[(4.32-c_0)AB_0+(4.32^2-4.32c_0-1)B_0^2\ge0,\] and the substituted value is beyond its vertex. Both coefficients are positive: \(\sqrt3<1.73206\) gives \(4.32>c_0\) and \(4.32^2>1+4.32c_0\) by rational comparison. The degenerate cases \(B_0=0\) or \(W=0\) obey the same bound. Thus \[ \sqrt W\le\sqrt{V_0}+4.32\sqrt{qH_0}. \tag{59}\]

The constants leave a strict margin for absorbing this spread: \[\begin{align*} \frac{p_*}{(1+p_*)qC_0} +\frac{p_*(4.32)^2}{1-p_*} &<\frac{.0532}{(.985)(.034)} +\frac{.019(4.32)^2}{.981}\tag{60}\\ &<1.95<2. \end{align*}\] For clarity, the middle rational number is \(444890776/228150625\), which is strictly less than \(39/20\). Weighted Cauchy–Schwarz, applied to (59), now gives \[\begin{align*} \frac{p_*W}{2q} &\le\frac12\left( \frac{p_*}{(1+p_*)qC_0} +\frac{p_*(4.32)^2}{1-p_*}\right) \bigl((1+p_*)C_0V_0+(1-p_*)H_0\bigr)\\ &\le(1+p_*)C_0V_0+(1-p_*)H_0. \tag{61}\end{align*}\] All denominators are positive by (55) and \(0\le p_*<.019\).

If (36) is strict, substitute it into (34), then use (56) and (61). The result is \[\mathcal E(d)>K+(1+p_*)C_0V_0+(1-p_*)H_0-p_*(q-l)\ge K,\] contradicting (24). Lemma 15 therefore leaves only \(m=0\) and \(g^2=M\) everywhere.

In this exceptional case \(b=s\), so \(x_0=\sqrt{1-s^2}=\rho\). Because \(F\) is odd and strictly increasing, \(g^2=M\) implies \(|d|=\rho\) everywhere. If \(W_k(f)\) denotes the Fourier weight of \(f\) at degree \(k\), Parseval and \(m=0\) give \[\sum_{k\ge1}W_k(f)=1,\qquad \sum_{k\ge1}r^kW_k(f)=\mathbb Ed^2=r.\] Subtracting the second identity from \(r\) times the first gives \(\sum_{k\ge2}(r-r^k)W_k(f)=0\). Every coefficient \(r-r^k\) is positive for \(0<r<1\), so all weights above degree one vanish. Hence \(f=\sum_i c_i x_i\), with \(\sum_i c_i^2=1\). The identity \(f^2=1\) has degree-two coefficients \(2c_ic_j=0\) for every \(i\ne j\). At most one \(c_i\) is nonzero, and its square is \(1\). Thus \(f\) is a signed coordinate, proving Proposition 10. ◻

Proof of Proposition 16. Assume \(b=h-1+s\). Since \(s\ge21/25\), \[ r^2\le(184/625)^2<87/1000. \tag{71}\] The first term of the bound on \(w\), namely \(w\le1-m\), gives \[ Q\le Q_0:=\frac{1+r^2m}{h(1+m)}. \tag{72}\]

First suppose \(r^2/2\le m\le1/5\). In particular \(m>0\). On this interval, \[h\ge1-\frac{51}{100}m^2,\] as follows by squaring: the difference of the squares is \(m^2(1/50-2601m^2/10000)\ge0\). Consequently \[\begin{align*} \frac{1-Q_0}{m} &=\frac1h\left[\frac{1-r^2}{1+m}-\frac{1-h}{m}\right] \ge L(m):=\frac{913}{1000(1+m)}-\frac{51m}{100}. \tag{73}\end{align*}\] Here the bracket is positive, since it is at least \(L(m)\ge L(1/5)=3953/6000>0\); thus the factor \(1/h\ge1\) has been removed in the correct direction.

We compare \(L(m)\) with \[ R(m,s):=\frac{2v}{1+s}\left(\frac{v}{sm}+2m\right). \tag{74}\] For \(m\le3/50\), the hypothesis \(m\ge r^2/2\) gives \[R(m,s)\le\frac4{s(1+s)^3}+\frac{4vm}{1+s} \le\frac4{(21/25)(46/25)^3} +\frac{4(4/25)(3/50)}{46/25}.\] For \(3/50\le m\le1/5\), use instead \[R(m,s)\le \frac{2(4/25)^2}{(21/25)(46/25)(3/50)} +\frac{4(4/25)(1/5)}{46/25}.\] Since \(L\) decreases, the exact comparisons are \[\begin{array}{c|c|c} \text{range of }m & \text{lower bound for }L(m) &\text{upper bound for }R(m,s)\\ \hline \rule{0pt}{22pt}(0,3/50] & \dfrac{220141}{265000}>\dfrac45 & \dfrac{10032241}{12775350}<\dfrac45\\[7pt] [3/50,1/5]&\dfrac{3953}{6000}>\dfrac{16}{25} &\dfrac{4504}{7245}<\dfrac{16}{25}. \end{array}\] Equations (73)–(74) therefore give \((1-Q)/m>R(m,s)\). Since \[1-Q_* =\frac{v(2-s)}{s(1+s)},\] rearranging this strict inequality yields \[ \frac{1+s}{2v}(Q-Q_*)<\frac12-2m^2. \tag{75}\] The first line of Lemma 17, Jensen’s inequality, and (65) give \[\mathbb E\Psi\ge(\tfrac12-2m^2)\mathbb EV^2 \ge(\tfrac12-2m^2)v^2 >\frac r2(Q-Q_*),\] where the last step uses \(r=v(1+s)\) and (75).

Next suppose \(1/5\le m\le2/3\). For fixed \(a_0=r^2\le87/1000\), \[(\log Q_0)'=\frac{a_0}{1+a_0m}+\frac{2m-1}{1-m^2},\qquad (\log Q_0)''=-\frac{a_0^2}{(1+a_0m)^2} +\frac{2(m^2-m+1)}{(1-m^2)^2}>0.\] For the last sign, the positive term is at least \(3/2\), and \(a_0^2<1\). Convexity bounds \(Q_0\) by its endpoint maximum; it also increases with \(a_0\). At \(a_0=87/1000\), the two endpoint values are \[Q_0(1/5)=\frac{5087}{2400\sqrt6}<\frac{433}{500}=.866, \qquad Q_0(2/3)=\frac{4761}{2500\sqrt5}<\frac{213}{250}=.852.\] The strict comparisons follow respectively from \[25435^2<6\cdot10392^2,\qquad 4761^2<5\cdot2130^2.\] Thus \(Q<.866\) throughout this range.

Finally suppose \(2/3\le m\le37/50\). The second term of the bound on \(w\) gives \[ Q\le R_0(m,a_0):= (1-a_0)\frac{\sqrt3}{(1+m)^{3/2}}+\frac{a_0}{\sqrt{1-m^2}}, \qquad a_0=r^2\le87/1000. \tag{76}\] The coefficient of \(a_0\) is positive, because \((1+m)^2>3(1-m)\) on this interval. Hence it suffices to take \(a_0=87/1000\). Moreover, \[\frac{\partial R_0}{\partial m} =-\frac{3(1-a_0)\sqrt3}{2(1+m)^{5/2}} +\frac{a_0m}{(1-m^2)^{3/2}}<0.\] Here is a rational comparison proving the last sign on the entire interval. Since \(h>2/3\), the positive term is less than \((87/1000)(37/50)(27/8)<1/4\). Since \(\sqrt3>5/3\), \((1+m)^{5/2}<6\), and \(1-a_0\ge913/1000\), the magnitude of the negative term is greater than \(4565/12000>1/3\). At the left endpoint, \[R_0(2/3,87/1000)=\frac{4761}{2500\sqrt5}<.852,\] so \(Q<.852\) in the final range.

To finish both remaining ranges, observe that \[Q_*'(s)=\frac{2+4s(1-s)}{s^2(1+s)^2}>0, \qquad Q_*(21/25)=\frac{425}{483}>.879, \qquad \frac{1+s}{2}\ge\frac{23}{25}=.92.\] The exact positive margins after the respective pointwise losses are \[\begin{align*} \frac{1+s}{2}(Q_*-Q)-\frac1{100} &>.92(.879-.866)-.01=\frac{49}{25000}>0, &&1/5\le m\le2/3,\\ \frac{1+s}{2}(Q_*-Q)-\frac1{50} &>.92(.879-.852)-.02=\frac{121}{25000}>0, &&2/3\le m\le37/50. \end{align*}\] By the appropriate line of Lemma 17, \(\mathbb E\Psi\ge-\varepsilon\mathbb EV=-\varepsilon v\); the last inequalities and \(r=v(1+s)\) therefore imply (69). All three ranges give \(\mathcal E(d)>r/s\) by (67), completing the proof. ◻

Proof of Lemma 17. Introduce the midpoint and signed half-difference of the two angles: \[\beta=\arcsin m,\qquad t=\frac{\arcsin d-\beta}{2},\qquad c=t+\beta.\] Then \(|c|+|t|=\max\{|\arcsin d|,|\beta|\}<\pi/2\). The case \(t=0\) gives \(d=m\) and \(V=\Psi=0\); hence assume \(t\ne0\). Elementary angle identities give \[d-m=2\cos c\sin t,\qquad md+hH(d)=\cos(2t).\] Changing variables \(z=\sin\theta\) in the integral defining \(F\) gives, with the orientation of the integral retained if \(t<0\), \[g-F(m)=\int_{c-t}^{c+t}\frac{d\theta}{\sqrt{\cos\theta}}.\] Normalize this integral by setting \[T=\frac mh,\qquad q=\frac{\cos c}{h}=\cos t-T\sin t>0, \qquad G=\tan c.\] It follows that \[ V=\frac{2\sin^2t}{h},\qquad \frac{\Psi}{V}=4\sqrt q\,A-q^2-3, \qquad A=\frac{t}{\sin t}\frac12\int_{-1}^1 (\cos(tu)-G\sin(tu))^{-1/2}\,du. \tag{77}\]

To bound \(A\) from below, we keep the first three terms of a positive expansion. If \(y=\sin^2(tu)\), symmetry in \(u\) expresses the averaged integrand as \[\sum_{j\ge0}\frac{\binom{4j}{2j}}{16^j} G^{2j}y^j(1-y)^{-j-1/4}.\] This expansion is convergent because \(|G\tan(tu)|<1\), and its power coefficients in \(y\) are nonnegative. Keeping the terms through degree two therefore gives the lower bound \[1+\left(\frac14+\frac{3G^2}{8}\right)y +\left(\frac5{32}+\frac{15G^2}{32} +\frac{35G^4}{128}\right)y^2.\] Concavity of sine on \([0,\pi/2]\) implies \(\sin^2(tu)\ge u^2\sin^2t\). Averaging and writing \(Y=\sin^2t\), we obtain \[\frac12\int_{-1}^1(\cos(tu)-G\sin(tu))^{-1/2}\,du \ge1+\left(\frac1{12}+\frac{G^2}{8}\right)Y +\left(\frac1{32}+\frac{3G^2}{32} +\frac{7G^4}{128}\right)Y^2.\] Multiply by the positive-series bound \(t/\sin t\ge1+Y/6+3Y^2/40\), and discard terms of degree at least three. The result is \[ \frac{4(A-1)}{\sin^2t}\ge P_0, \qquad P_0=1+\frac{G^2}{2} +\sin^2t\left(\frac{173}{360}+\frac{11G^2}{24} +\frac{7G^4}{32}\right). \tag{78}\] To express the remaining terms rationally, put \(x=\tan(t/2)\). Then \[q-1=-\sin t(T+x),\qquad 4\sqrt q-q^2-3 =-(q-1)^2\left(1+\frac2{(1+\sqrt q)^2}\right).\] Equations (77) and (78) therefore imply \[ \frac{\Psi}{V}\ge\sin^2t \left[\sqrt q\,P_0 -(T+x)^2\left(1+\frac2{(1+\sqrt q)^2}\right)\right]. \tag{79}\]

We now bound these square-root coefficients on the required angular domains.

For \(m\le1/5\), \(T\le1/\sqrt{24}<21/100\) and \(\beta<21/100\). For \(m\le37/50\), \(\beta<21/25\). These bounds on \(\beta\) follow from \(\sin u\ge u-u^3/6\) at the respective rational values. Moreover, \[-\frac{\pi/2+\beta}{4}<\frac t2 <\frac{\pi}{8},\qquad \tan(\pi/8)=\sqrt2-1<\frac{21}{50}.\] Using \(\pi<22/7\), the lower angle in absolute value is less than \(9/20\) in the first range, and less than \(603/1000\) in the second. The bounds \[\tan(9/20)<1/2,\qquad \tan(603/1000)<7/10\] follow by dividing \(\sin u\le u-u^3/6+u^5/120\) by \(\cos u\ge1-u^2/2>0\); the resulting comparisons are rational. Thus \(m\le1/5\) gives \(0\le T\le21/100\) and \(|x|\le1/2\), whereas the two larger ranges have \(-7/10\le x\le21/50\). The corresponding bounds on \(T\) are \[T\le2/\sqrt5<9/10\quad(m\le2/3),\qquad T\le37/\sqrt{1131}<111/100\quad(m\le37/50).\]

On the small rectangle, \(q=(1-x^2-2Tx)/(1+x^2)\ge(27/50)/(5/4)=54/125=.432\), so \(\sqrt q>13/20\). The exact identity \[ \sqrt q=1+\frac{q-1}{2} -\frac{(q-1)^2}{2(1+\sqrt q)^2} \tag{80}\] and the rational comparisons \[\frac{200}{1089}<\frac{19}{100},\qquad \frac{1889}{1089}<\frac74\] give \[\sqrt q\ge1+\frac{q-1}{2}-\frac{19}{100}(q-1)^2, \qquad 1+\frac2{(1+\sqrt q)^2}<\frac74.\]

For the two larger ranges we use a bound on the actual angular domain: \[q\ge\frac{\cos((\pi/2+\beta)/2)}h =\frac1{\sqrt{2(1+m)}} \ge\frac5{\sqrt{87}}>\frac{53}{100}.\] In particular \(\sqrt q>18/25\), and \[\frac{625}{3698}<\frac{17}{100},\qquad \frac{3099}{1849}<\frac{42}{25}.\] Equation (80) therefore gives \[\sqrt q\ge1+\frac{q-1}{2}-\frac{17}{100}(q-1)^2, \qquad 1+\frac2{(1+\sqrt q)^2}<\frac{42}{25}.\]

These quadratic lower bounds for \(\sqrt q\) make the bracket in (79) rational in \(T,x\). We clear its positive denominators using the polynomials \[\begin{align*} &D=1+x^2,\qquad N=1-x^2-2Tx,\qquad z=2x,\qquad k=2x+T(1-x^2), \tag{81}\\ &P=D^2\left(N^4+\frac{k^2N^2}{2}\right) +z^2\left(\frac{173N^4}{360}+\frac{11k^2N^2}{24} +\frac{7k^4}{32}\right), \tag{82}\\ &R_e=D^2+\frac{(N-D)D}{2}-e(N-D)^2. \tag{83}\end{align*}\] At the angular parameters, \[ \begin{gathered} q=\frac ND,\qquad G=\frac kN,\qquad \sin t=\frac zD,\qquad P_0=\frac{P}{D^2N^4},\\ D>0,\qquad N>0,\qquad P>0. \end{gathered} \tag{84}\] The needed polynomial signs are \[\begin{align*} \mathcal S(T,x) &:=R_{19/100}P-D^4N^4 \left[1-\frac{33}{10}T^2+\frac74(T+x)^2\right]\ge0 \tag{85}\\[-3pt] &\hspace{35mm}(0\le T\le21/100,\ |x|\le1/2),\\ \mathcal L_{\varepsilon}(T,x) &:=z^2\left[R_{17/100}P-\frac{42}{25}D^4N^4(T+x)^2\right] +\varepsilon D^6N^4>0 \tag{86}\\[-3pt] &\hspace{10mm}(0\le T\le T_0,\ -7/10\le x\le21/50), \end{align*}\] where \((T_0,\varepsilon)=(9/10,1/100)\) or \((111/100,1/50)\). Their exact finite verification is given below.

For \(m\le1/5\), the lower bound for \(\sqrt q\) is \(R_{19/100}/D^2\). Hence (85) makes the bracket in (79) at least \(1-(33/10)T^2\). To compare this with the claimed bound, put \(y=T^2\le441/10000\). Both sides in the following squared comparison are nonnegative, and \[\left(1-\frac{33}{10}y\right)^2(1+y)-(1-3y)^2 =y\left(\frac25-\frac{471}{100}y+\frac{1089}{100}y^2\right)\ge0.\] Indeed \(2/5-(471/100)(441/10000)>0\). Consequently \[1-\frac{33}{10}T^2 \ge\frac{1-3T^2}{\sqrt{1+T^2}} =\frac{1-4m^2}{h}.\] Together with \(V=2\sin^2t/h\), this proves the first line of (70).

For the two larger ranges the lower bound for \(\sqrt q\) is \(R_{17/100}/D^2\), and the coefficient of \((T+x)^2\) is at most \(42/25\). Since \(\sin^2t=z^2/D^2\), Equation (86) implies \(\Psi/V>-\varepsilon\). This proves the other two lines for \(t\ne0\), and their nonstrict form also holds at \(t=0\). Notice that division by \(N\) has only been used at actual angular points, where (84) holds. A larger certification rectangle may contain \(N\le0\); its polynomial sign assertion remains valid and is more than is needed here. ◻

Proof. First consider one bit. Both sides are homogeneous of degree two in \(a\). After dividing by \(\mathbb Ea^2\) and exchanging the two endpoints if necessary, we may suppose that \(a_\pm^2=1\pm x\), where \(0\le x<1\). The entropy then equals \[J(x)=\frac{(1+x)\log(1+x)+(1-x)\log(1-x)}2,\] whereas the right side of (95) equals \[\frac{(a_+-a_-)^2}{2}=1-\sqrt{1-x^2}.\] Both expressions vanish at zero. Their derivatives satisfy \[J'(x)=\operatorname{arctanh}x\le\frac{x}{\sqrt{1-x^2}}.\] Indeed, the difference on the right minus the left vanishes at zero and has derivative \((1-x^2)^{-3/2}-(1-x^2)^{-1}\ge0\). Integration proves the one-bit inequality, including its constant \(2\).

For completeness, entropy is convex in its positive input. Its second variation in the direction \(w\) is \[\mathbb E\frac{w^2}{z}-\frac{(\mathbb Ew)^2}{\mathbb Ez}\ge0\] by Cauchy–Schwarz. Let \(\operatorname{Ent}_i\) denote entropy on bit \(i\) with the other bits fixed. The exact decomposition \[\operatorname{Ent}(z) =\mathbb E\operatorname{Ent}_1(z)+\operatorname{Ent}(\mathbb E_1z)\] and induction on the remaining coordinates imply \[ \operatorname{Ent}(z)\le\sum_i\mathbb E\operatorname{Ent}_i(z). \tag{96}\] To see the induction step explicitly, for \(i\ne1\) convexity gives \(\operatorname{Ent}_i(\mathbb E_1z)\le\mathbb E_1\operatorname{Ent}_i(z)\): conditional averaging in coordinate \(1\) is a convex combination of the two positive vectors indexed by coordinate \(i\). Apply the one-bit inequality to \(z=a^2\) in every summand of (96), and then sum the edge energies using (94). ◻

Proof. We begin with strictly positive \(u_0\). The noise semigroup is \(T_{e^{-t}}=e^{-t\mathcal N}\), so \(u(t)=T_{e^{-t}}u_0\) satisfies \(u'=-\mathcal Nu\). This identity follows, for example, because \(\mathcal N\) multiplies a character of degree \(j\) by \(j\), while noise multiplies it by \(e^{-tj}\).

For positive edge values \(A>B\) and any \(q>0\), \(q\ne1\), Cauchy–Schwarz in the interval \([B,A]\) gives \[\begin{align*} \frac4{q^2}(A^{q/2}-B^{q/2})^2 &=\left(\int_B^A t^{q/2-1}\,dt\right)^2\\ &\le(A-B)\int_B^A t^{q-2}\,dt =\frac{(A-B)(A^{q-1}-B^{q-1})}{q-1}. \end{align*}\] The last quotient is positive also when \(0<q<1\). The inequality is symmetric in \(A,B\) and holds by continuity when they coincide. Summing it with the edge factor \(1/4\) yields \[ \frac{\mathbb Eu^{q-1}\mathcal Nu}{q-1} \ge\frac4{q^2}\mathbb Eu^{q/2}\mathcal N(u^{q/2}). \tag{98}\]

To reach a prescribed final exponent \(q\), vary the exponent along \[\theta(t)=1+(q-1)e^{2(t-\tau)},\qquad 0\le t\le\tau.\] This path is positive, stays on the same side of \(1\) as \(q\), and satisfies \(\theta'=2(\theta-1)\), \(\theta(0)=p_q\), and \(\theta(\tau)=q\). For \(M(t)=\mathbb Eu(t)^{\theta(t)}\), direct differentiation gives \[M'=\theta'\mathbb E(u^\theta\log u) -\theta\mathbb Eu^{\theta-1}\mathcal Nu.\] Consequently, with \(\|u\|_\theta=(\mathbb Eu^\theta)^{1/\theta}\) also for \(0<\theta<1\), \[\begin{align*} \frac{d}{dt}\log\|u\|_\theta &=\frac{\theta'}{\theta^2} \frac{\operatorname{Ent}(u^\theta)}{M} -\frac{\mathbb Eu^{\theta-1}\mathcal Nu}{M}\\ &=\frac{\theta-1}{M} \left[ \frac2{\theta^2}\operatorname{Ent}(u^\theta) -\frac{\mathbb Eu^{\theta-1}\mathcal Nu}{\theta-1} \right]. \tag{99}\end{align*}\] Lemma 19, applied to \(u^{\theta/2}\), and (98) show that the bracket is nonpositive. Thus the derivative is nonpositive when \(q>1\) and nonnegative when \(0<q<1\). Integrating, and raising the resulting norm inequality to the positive power \(q\), proves (97). For general \(u_0\ge0\), apply the result to \(u_0+\varepsilon\) and let \(\varepsilon\downarrow0\). The cube is finite, and all exponents involved are positive, so both sides converge continuously. ◻

Proof of Proposition 18. We first use the norm inequalities to bound a positive series of moments. We then bound its terms and tail uniformly on four intervals of \(r\). Finally, exact rational estimates make the resulting bound smaller than \(1-s\) on each interval.

The case \(s=1\) has \(\rho=0\) and \(d=m\), hence \(h-b=0\). We may therefore assume \(0.84\le s<1\), so \(0<r\le0.2944\). Write \[p=\Pr(f=-1)=\frac{1-m}{2}\in(0,0.13],\qquad U=T_\rho\mathbf1_{\{f=-1\}}=\frac{1-d}{2}.\] The preceding approximation argument applies to this indicator input. After taking its limit, \(0\le U\le1\) and \(H(d)=2\sqrt U\sqrt{1-U}\).

For \(0\le z\le1\), the binomial expansion has positive coefficients: \[ 1-\sqrt{1-z}=\sum_{k\ge1}c_kz^k,\qquad c_k=\frac{\binom{2k}{k}}{(2k-1)4^k},\qquad c_1=\frac12,\quad c_{k+1}=c_k\frac{k-1/2}{k+1}. \tag{100}\] The usual Taylor expansion gives this identity for \(z<1\); positivity and monotone convergence as \(z\uparrow1\) give \(\sum_{k\ge1}c_k=1\) and the identity at \(z=1\). It follows that \[ h-b =2(\sqrt p-\mathbb E\sqrt U) +2\sum_{k\ge1}c_k\bigl(\mathbb EU^{k+1/2}-p^{k+1/2}\bigr). \tag{101}\] The interchange with expectation is justified by the nonnegative series for each of the two terms; both series are bounded by \(\sum_kc_k=1\). Lemma 20 with \(q=1/2\) bounds the first expectation from below, and with \(q_k=k+1/2\) bounds the other moments from above. Thus \[ h-b\le 2\bigl[p^{1/2}-p^{1/(2-r)}\bigr] +2\sum_{k\ge1}c_k \left[p^{q_k/(1+r(q_k-1))}-p^{q_k}\right]. \tag{102}\]

Every bracket on the right increases with \(p\) on \([0,0.13]\). Indeed, if \(1/2\le a<b\) and \(p>0\), then \[\frac{d}{dp}(p^a-p^b)\ge0 \quad\Longleftrightarrow\quad p\le(a/b)^{1/(b-a)}.\] Since \(\log(b/a)\le(b-a)/a\), this threshold is at least \(e^{-1/a}\ge e^{-2}>0.13\); the last strict inequality follows also from the logarithm bounds established in (104) below. The exponents in (102) have this ordering, since \(0<r<1\). We can therefore replace \(p\) by \(p_*=13/100\) throughout its right side.

Proof. Put \(\rho=1-2\varepsilon\), \(d=T_\rho f\), \(m=\mathbb Ef\), \(h=H(m)\), \(b=\mathbb EH(d)\), and \(s=H(\rho)\). Define \[\varphi(t)=h_2\left(\frac{1-\sqrt{1-t^2}}2\right),\qquad 0\le t\le1.\] This function is increasing and convex. In fact, for \(0<t<1\), writing \(v=\sqrt{1-t^2}\) gives \[\varphi'(t)=\frac{t}{2v\log 2}\log\frac{1+v}{1-v}\ge0, \qquad \varphi''(t)=\frac{\log((1+v)/(1-v))-2v}{2v^3\log 2}\ge0.\] The last numerator is nonnegative because its derivative with respect to \(v\) is \(2v^2/(1-v^2)\ge0\) and its value at zero is zero. Continuity extends monotonicity and convexity to \([0,1]\).

The symmetric noise kernel gives \(\Pr(f(X)=1\mid Y)=(1+d(Y))/2\). The identity \(h_2((1+u)/2)=\varphi(H(u))\), valid for every \(u\in[-1,1]\), and Jensen’s inequality therefore imply \[I(f(X);Y)=\varphi(h)-\mathbb E\varphi(H(d)) \le\varphi(h)-\varphi(b).\] Concavity of \(H\) gives \(b\le h\), and Theorem 1 gives \(\delta:=h-b\le1-s\). For a convex function its increments over intervals of fixed length are increasing with the left endpoint. Since \(h\le1\), \[\varphi(h)-\varphi(b) \le\varphi(1)-\varphi(1-\delta) \le\varphi(1)-\varphi(s) =1-h_2(\varepsilon).\] The same reasoning includes \(\delta=0\) and the noise endpoints by continuity. A signed coordinate is a uniform bit observed through a binary symmetric channel, whose mutual information is \(1-h_2(\varepsilon)\). ◻