OctoInformBeta

OpenAI preprint, September 2026 · §2. A low-degree estimate on biased products

Lemma 2.1: A bound at the cutoff p(1−p)log⁡m/64\sqrt{p(1-p)}\log m/64 for interior bias pp and real m≥1m\geq1

Small influences constrain low-degree Fourier mass.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

A Boolean function on a finite biased product has a Fourier spectrum indexed by coordinate sets. The question is how its mass on small nonempty sets depends on the distribution of its pivotal influences.

Let JJ be a finite coordinate set and let 0<p<10<p<1. The Bernoulli mass bpb_p on {0,1}\{0,1\} and its product probability mass wpw_p on {0,1}J\{0,1\}^J are defined by (1): bp(1)=p,bp(0)=1−p,wp(x)=∏i∈Jbp(xi).b_p(1)=p,\qquad b_p(0)=1-p,\qquad w_p(x)=\prod_{i\in J}b_p(x_i).(1) Write ℙp\mathbb P_p and 𝔼p\mathbb E_p for probability and expectation with this mass. The real indicator of a Boolean value is 11 for true and 00 for false; a Boolean function f:{0,1}J→{0,1}f:\{0,1\}^J\to\{0,1\} is also regarded as its real indicator.✦

For x∈{0,1}Jx\in\{0,1\}^J, let xi←ax^{i\gets a} denote xx with coordinate ii set to a∈{0,1}a\in\{0,1\}. The pivotal influence Ii,p(f)I_{i,p}(f) of coordinate ii is the probability that the two choices at ii give different values of ff, and the total influence Ip(f)I_p(f) is their sum, as in (2): Ii,p(f)=ℙp(f(xi←0)≠f(xi←1)),Ip(f)=∑i∈JIi,p(f).I_{i,p}(f)=\mathbb P_p\bigl(f(x^{i\gets0})\ne f(x^{i\gets1})\bigr), \qquad I_p(f)=\sum_{i\in J}I_{i,p}(f).(2)✦

Set σ=p(1−p)\sigma=\sqrt{p(1-p)}. The biased coordinate character χi\chi_i and the product character χS\chi_S for S⊆JS\subseteq J are the real functions in (3): χi(x)=xi−pσ,χS(x)=∏i∈Sχi(x).\chi_i(x)=\frac{x_i-p}{\sigma},\qquad \chi_S(x)=\prod_{i\in S}\chi_i(x).(3) The biased Fourier coefficient gˆ(S)\widehat g(S) of a real function g:{0,1}J→ℝg:\{0,1\}^J\to\mathbb R at S⊆JS\subseteq J is its expectation against χS\chi_S, as in (4): gˆ(S)=𝔼p[gχS].\widehat g(S)=\mathbb E_p[g\chi_S].(4)✦

The Claim

Theorem 1. Let f:{0,1}J→{0,1}f:\{0,1\}^J\to\{0,1\} be Boolean and let m≥1m\geq1 be real. Suppose that Ii,p(f)≤Ip(f)/mI_{i,p}(f)\leq I_p(f)/m for every i∈Ji\in J, and put k=σlog⁡m/64k=\sigma\log m/64. Then the full-sum estimate (5) holds: ∑S⊆J{fˆ(S)2,S≠⌀and|S|≤k,0,otherwise≤m−1/4Ip(f).\sum_{S\subseteq J} \begin{cases} \widehat f(S)^2,& S\ne\varnothing\ \text{and}\ |S|\leq k,\\ 0,&\text{otherwise} \end{cases} \ \leq\ m^{-1/4}I_p(f).(5)✦ The restricted-sum estimate is (6): ∑S⊆J1≤|S|≤kfˆ(S)2≤m−1/4Ip(f).\sum_{\substack{S\subseteq J\\1\leq |S|\leq k}} \widehat f(S)^2 \ \leq\ m^{-1/4}I_p(f).(6)✦

In the paper, the result reads: for finite JJ, 0<p<10<p<1, σ=p(1−p)\sigma=\sqrt{p(1-p)}, real m≥2m\geq2, and a Boolean function h:{0,1}J→{0,1}h:\{0,1\}^J\to\{0,1\} with Ii,p(h)≤Ip(h)/mI_{i,p}(h)\leq I_p(h)/m for every i∈Ji\in J, the cutoff k=σlog⁡m/64k=\sigma\log m/64 gives ∑S⊆J,1≤|S|≤khˆ(S)2≤m−1/4Ip(h)\sum_{S\subseteq J,\,1\leq|S|\leq k}\widehat h(S)^2\leq m^{-1/4}I_p(h), where the cutoff applies literally to integer cardinalities, so the sum is empty when k<1k<1.

What Is Checked

The claims (5) and (6) are stated over Boolean functions on finite Bernoulli products, with the pivotal influences of (2) and the Fourier coefficients of (4) taken at the same interior bias pp.