OctoInformBeta

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

§2: Biased Fourier coefficients and discrete derivatives: Normalized characters give inversion and Parseval on finite products, with Dirichlet identities for Boolean functions

Biased Fourier coefficients determine pivotal influences.

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

Consider a Boolean function of finitely many independent bits with a common bias.

Let JJ be a finite coordinate set, let Ω={0,1}J\Omega=\{0,1\}^J, and take 0<p<10<p<1. Write σ=p(1−p)\sigma=\sqrt{p(1-p)}. The Bernoulli probability mass bpb_p on {0,1}\{0,1\} is defined by (1). bp(t)={p,t=1,1−p,t=0.b_p(t)= \begin{cases} p,&t=1,\\ 1-p,&t=0. \end{cases}(1)✦ The product probability mass wpw_p on Ω\Omega, used for Fourier analysis and pivotal influence, and expectation 𝔼p\mathbb E_p of a real-valued function u:Ω→ℝu:\Omega\to\mathbb R are given by (2). wp(x)=∏j∈Jbp(xj),𝔼p[u]=∑x∈Ωwp(x)u(x).w_p(x)=\prod_{j\in J}b_p(x_j), \qquad \mathbb E_p[u]=\sum_{x\in\Omega}w_p(x)u(x).(2)

The Boolean indicator assigns the real value 00 to false\mathrm{false} and 11 to true\mathrm{true}; a Boolean function f:Ω→{0,1}f:\Omega\to\{0,1\} is regarded as real-valued under this identification.✦ For i∈Ji\in J and b∈{0,1}b\in\{0,1\}, let xi←bx^{i\leftarrow b} be the configuration obtained from xx by setting coordinate ii to bb. The pivotal influence Ii,p(f)I_{i,p}(f) is the probability that coordinate ii changes ff when set to 11 and 00, and the total influence Ip(f)I_p(f) is its sum over coordinates, as in (3). Ii,p(f)=∑x∈Ωwp(x)𝟏{f(xi←1)≠f(xi←0)},Ip(f)=∑i∈JIi,p(f).I_{i,p}(f)=\sum_{x\in\Omega}w_p(x) \mathbf 1_{\{f(x^{i\leftarrow1})\ne f(x^{i\leftarrow0})\}}, \qquad I_p(f)=\sum_{i\in J}I_{i,p}(f).(3)✦

The Claim

Theorem 1. Let JJ be finite and let 0<p<10<p<1, with Ω\Omega, σ\sigma, and 𝔼p\mathbb E_p as above. The normalized bit χp:{0,1}→ℝ\chi_p:\{0,1\}\to\mathbb R is defined by χp(b)=(b−p)/σ\chi_p(b)=(b-p)/\sigma. Its coordinate lift χi:Ω→ℝ\chi_i:\Omega\to\mathbb R is χi(x)=χp(xi)\chi_i(x)=\chi_p(x_i), as in (4). χi(x)=xi−pσ(i∈J).\chi_i(x)=\frac{x_i-p}{\sigma} \qquad(i\in J).(4)✦ The biased character χS:Ω→ℝ\chi_S:\Omega\to\mathbb R indexed by a subset S⊆JS\subseteq J is the product in (5). χS(x)=∏i∈Sχi(x).\chi_S(x)=\prod_{i\in S}\chi_i(x).(5)✦ For a function g:Ω→ℝg:\Omega\to\mathbb R, its biased Fourier coefficient gˆ(S)\widehat g(S) at S⊆JS\subseteq J is defined by (6). gˆ(S)=𝔼p[gχS].\widehat g(S)=\mathbb E_p[g\chi_S].(6)✦ The discrete derivative Δig:Ω→ℝ\Delta_i g:\Omega\to\mathbb R is the difference in (7). Δig(x)=g(xi←1)−g(xi←0).\Delta_i g(x)=g(x^{i\leftarrow1})-g(x^{i\leftarrow0}).(7)✦ Every g:Ω→ℝg:\Omega\to\mathbb R satisfies Fourier inversion (8) and Parseval’s identity (9). g(x)=∑S⊆Jgˆ(S)χS(x)(x∈Ω).g(x)=\sum_{S\subseteq J}\widehat g(S)\chi_S(x) \qquad(x\in\Omega).(8)✦ ∑S⊆Jgˆ(S)2=𝔼p[g2].\sum_{S\subseteq J}\widehat g(S)^2=\mathbb E_p[g^2].(9)✦ Every Boolean function f:Ω→{0,1}f:\Omega\to\{0,1\} satisfies the coordinate Dirichlet identity (10), for each i∈Ji\in J, and the total Dirichlet identity (11). ∑S⊆Ji∈Sfˆ(S)2=σ2Ii,p(f).\sum_{\substack{S\subseteq J\\i\in S}}\widehat f(S)^2 =\sigma^2 I_{i,p}(f).(10)✦ ∑S⊆J|S|fˆ(S)2=σ2Ip(f).\sum_{S\subseteq J}|S|\widehat f(S)^2=\sigma^2 I_p(f).(11)✦

In the paper, the result reads: for any finite coordinate set JJ and 0<p<10<p<1, put σ=p(1−p)\sigma=\sqrt{p(1-p)}, define χi(x)=(xi−p)/σ\chi_i(x)=(x_i-p)/\sigma, χS=∏i∈Sχi\chi_S=\prod_{i\in S}\chi_i, gˆ(S)=𝔼p[gχS]\widehat g(S)=\mathbb E_p[g\chi_S], and Δig(x)=g(xi←1)−g(xi←0)\Delta_i g(x)=g(x^{i\leftarrow1})-g(x^{i\leftarrow0}); the characters form an orthonormal basis, inversion and Parseval hold, and every Boolean function hh satisfies ∑S∋ihˆ(S)2=σ2Ii,p(h)\sum_{S\ni i}\widehat h(S)^2=\sigma^2 I_{i,p}(h) and ∑S⊆J|S|hˆ(S)2=σ2Ip(h)\sum_{S\subseteq J}|S|\widehat h(S)^2=\sigma^2 I_p(h).

What Is Checked

The statements concern the finite product probability mass in (2) at an interior bias, with real-valued functions for inversion and Parseval and Boolean functions for the Dirichlet identities.