OctoInformBeta

OpenAI preprint, September 2026 · §3. Restricting to the edges incident with a vertex block

Lemma 3.1: Degrees count only free coordinates, and restricted total influence averages to the sum of their original influences

Restriction averages select 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 graph restriction fixes some edges and leaves a Boolean function on the remaining edges. Take a finite coordinate set II; for graphs on nn vertices, take I=En=({1,…,n}2)I=E_n=\binom{\{1,\ldots,n\}}{2}. Let F⊆IF\subseteq I be the free coordinates and H=I\FH=I\setminus F the fixed coordinates. The degree of a Fourier support S⊆IS\subseteq I among the free coordinates is |S∩F||S\cap F|.

For a real parameter pp, the scalar Bernoulli weight bp(b)b_p(b) of a bit b∈{0,1}b\in\{0,1\} and the product weight wp,J(x)w_{p,J}(x) of a configuration x∈{0,1}Jx\in\{0,1\}^J, on any finite coordinate set JJ, are given in (1); for a real-valued function uu on this cube, 𝔼p,J\mathbb E_{p,J} denotes the corresponding finite weighted sum. bp(b)={p,b=1,1−p,b=0,wp,J(x)=∏i∈Jbp(xi),𝔼p,J[u]=∑x∈{0,1}Jwp,J(x)u(x).\begin{aligned} b_p(b)&=\begin{cases}p,&b=1,\\1-p,&b=0,\end{cases} & w_{p,J}(x)&=\prod_{i\in J}b_p(x_i),\\ \mathbb E_{p,J}[u]&=\sum_{x\in\{0,1\}^J}w_{p,J}(x)u(x). \end{aligned}(1) For 0≤p≤10\le p\le1, these are the Bernoulli product weights and expectation.

For any value set DD, the gluing x⊕y∈DIx\oplus y\in D^I of x∈DFx\in D^F and y∈DHy\in D^H is the configuration in (2).✦ For value sets DD and CC, a function g:DI→Cg:D^I\to C, and a fixed configuration y∈DHy\in D^H, the coordinate restriction gy:DF→Cg_y:D^F\to C is the function given by (2).✦ (x⊕y)i={xi,i∈F,yi,i∈H,gy(x)=g(x⊕y).(x\oplus y)_i= \begin{cases} x_i,&i\in F,\\ y_i,&i\in H, \end{cases} \qquad g_y(x)=g(x\oplus y).(2)

Fourier Coefficients and Influence

At bias 0<p<10<p<1, the biased coordinate character χi\chi_i on {0,1}J\{0,1\}^J, the product character χS\chi_S for S⊆JS\subseteq J, and the biased Fourier coefficient gˆ(S)\widehat g(S) of a real-valued function gg are defined by (3). σ=p(1−p),χi(x)=xi−pσ,χS(x)=∏i∈Sχi(x),gˆ(S)=𝔼p,J[gχS].\begin{aligned} \sigma&=\sqrt{p(1-p)}, &\chi_i(x)&=\frac{x_i-p}{\sigma},\\ \chi_S(x)&=\prod_{i\in S}\chi_i(x), &\widehat g(S)&=\mathbb E_{p,J}[g\chi_S]. \end{aligned}(3)

For a Boolean function f:{0,1}J→{0,1}f:\{0,1\}^J\to\{0,1\}, the pivotal influence Ii,p(f)I_{i,p}(f) of coordinate i∈Ji\in J is the weighted sum in (4), where x(i)x^{(i)} is xx with bit ii toggled; the total influence Ip(f)I_p(f) is the sum of the coordinate influences.✦ Ii,p(f)=∑x∈{0,1}Jwp,J(x)𝟏{f(x)≠f(x(i))},Ip(f)=∑i∈JIi,p(f).I_{i,p}(f)=\sum_{x\in\{0,1\}^J}w_{p,J}(x) \mathbf 1_{\{f(x)\ne f(x^{(i)})\}}, \qquad I_p(f)=\sum_{i\in J}I_{i,p}(f).(4)

The Claim

Theorem 1. Let II be a finite coordinate set, let F⊆IF\subseteq I, and put H=I\FH=I\setminus F. Let g:{0,1}I→ℝg:\{0,1\}^I\to\mathbb R and 0<p<10<p<1. For any set Q⊆{0,1,2,…}Q\subseteq\{0,1,2,\ldots\} of degrees, the selected-degree identity is (5): 𝔼p,H[∑A⊆F|A|∈Qgyˆ(A)2]=∑S⊆I|S∩F|∈Qgˆ(S)2.\mathbb E_{p,H}\!\left[ \sum_{\substack{A\subseteq F\\|A|\in Q}}\widehat{g_y}(A)^2 \right] = \sum_{\substack{S\subseteq I\\|S\cap F|\in Q}}\widehat g(S)^2.(5)✦ For every real cutoff kk, the low-degree identity is (6): ∑S⊆I1≤|S∩F|≤kgˆ(S)2=𝔼p,H[∑A⊆F1≤|A|≤kgyˆ(A)2].\sum_{\substack{S\subseteq I\\1\le |S\cap F|\le k}}\widehat g(S)^2 = \mathbb E_{p,H}\!\left[ \sum_{\substack{A\subseteq F\\1\le |A|\le k}}\widehat{g_y}(A)^2 \right].(6)✦ For a Boolean function f:{0,1}I→{0,1}f:\{0,1\}^I\to\{0,1\} and every real pp, the influence identity is (7): 𝔼p,H[Ip(fy)]=∑i∈FIi,p(f).\mathbb E_{p,H}[I_p(f_y)]=\sum_{i\in F}I_{i,p}(f).(7)✦

In the paper, the result reads: for a Boolean function ff on {0,1}En\{0,1\}^{E_n}, 0<p<10<p<1, F⊆EnF\subseteq E_n, H=En\FH=E_n\setminus F, and fy(x)=f(x⊕y)f_y(x)=f(x\oplus y), with yy distributed according to the Bernoulli-pp product law on HH, every real k>0k>0 satisfies (8) and (9): 𝔼p,H[∑A⊆F1≤|A|≤kfyˆ(A)2]=∑S⊆En1≤|S∩F|≤kfˆ(S)2,\mathbb E_{p,H}\!\left[ \sum_{\substack{A\subseteq F\\1\le |A|\le k}}\widehat{f_y}(A)^2 \right] = \sum_{\substack{S\subseteq E_n\\1\le |S\cap F|\le k}}\widehat f(S)^2,(8) 𝔼p,H[Ip(fy)]=∑e∈FIe,p(f).\mathbb E_{p,H}[I_p(f_y)]=\sum_{e\in F}I_{e,p}(f).(9)

What Is Checked

The Fourier identities concern real-valued functions on finite Boolean cubes at 0<p<10<p<1 with an arbitrary set of free coordinates, and the influence identity concerns Boolean functions with the product weights of (1) for every real pp.