OctoInformBeta

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

§3: Spectral tail and numerical assembly: Spectral identities and a numerical bound at every positive logarithmic scale

Fourier capture controls the variance.

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 variance estimate in terms of pivotal edge influences compares the fluctuations of a Boolean graph function with its sensitivity to individual edges. The spectral input here is a bound on the Fourier mass of small, nonempty sets of edges.

The set EnE_n of potential edges consists of the two-element subsets of the nn labelled vertices.✦ A labelled graph is a configuration x∈{0,1}Enx\in\{0,1\}^{E_n}, with xe=1x_e=1 when ee is present.✦ A Boolean value is identified with its real indicator, equal to 11 for true and 00 for false.✦

For a finite coordinate set AA and 0<p<10<p<1, the Bernoulli mass wpw_p of a bit and the product probability mass WpW_p of a configuration are defined by wp(b)={p,b=1,1−p,b=0,Wp(x)=∏i∈Awp(xi).w_p(b)= \begin{cases} p,&b=1,\\ 1-p,&b=0, \end{cases} \qquad W_p(x)=\prod_{i\in A}w_p(x_i).(1) For A=EnA=E_n, the weight in (1) is the random graph probability mass.✦ Write 𝔼p\mathbb E_p and ℙp\mathbb P_p for expectation and probability under these weights. For a Boolean graph function ff, its graph property probability μp(f)\mu_p(f) is its expectation, and its variance Var⁡p(f)\operatorname{Var}_p(f) is its mean squared deviation from that expectation, as in (2): μp(f)=𝔼pf,Var⁡p(f)=𝔼p[(f−μp(f))2].\mu_p(f)=\mathbb E_p f, \qquad \operatorname{Var}_p(f)=\mathbb E_p\bigl[(f-\mu_p(f))^2\bigr].(2) For e∈Ene\in E_n, let x⊕ex^{\oplus e} denote xx with the bit at ee toggled. For a Boolean graph function ff and an edge e∈Ene\in E_n, the pivotal edge influence Ie,p(f)I_{e,p}(f) is the probability that toggling the bit at ee changes ff, with all other edges chosen independently at bias pp.✦ The total influence Ip(f)I_p(f) of a Boolean graph function ff is the sum of its pivotal edge influences, as in (3): Ie,p(f)=ℙp(f(x)≠f(x⊕e)),Ip(f)=∑e∈EnIe,p(f).I_{e,p}(f)=\mathbb P_p\bigl(f(x)\ne f(x^{\oplus e})\bigr), \qquad I_p(f)=\sum_{e\in E_n}I_{e,p}(f).(3) Set σ=p(1−p)\sigma=\sqrt{p(1-p)}. For a finite coordinate set AA, an index i∈Ai\in A and a subset S⊆AS\subseteq A, the biased coordinate character χi\chi_i and the product character χS\chi_S are the functions on {0,1}A\{0,1\}^{A} given by χ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).(4) For a real function gg on {0,1}A\{0,1\}^{A} and a subset S⊆AS\subseteq A, the biased Fourier coefficient gˆ(S)\widehat g(S) is the expectation of the product of gg and χS\chi_S, as in (5): gˆ(S)=𝔼p[g(x)χS(x)].\widehat g(S)=\mathbb E_p\bigl[g(x)\chi_S(x)\bigr].(5) For graph functions, fˆ(S)\widehat f(S) in (5) uses A=EnA=E_n and the real indicator of ff.

Captured Fourier Mass

A real coefficient family cc on a finite set AA is an assignment of a real number c(S)c(S) to each subset S⊆AS\subseteq A. For a real coefficient family cc on a finite set AA and positive parameters σ,m\sigma,m, the captured squared mass Cσ(m)C_\sigma(m) is the sum of the squared coefficients over the nonempty subsets of AA below the degree cutoff in (6): Cσ(m)=∑⌀≠S⊆A|S|≤(σlog⁡m/64)2/2c(S)2.C_\sigma(m)= \sum_{\substack{\varnothing\ne S\subseteq A\\ |S|\le (\sigma\log m/64)^2/2}}c(S)^2.(6) All logarithms are natural.

The Claim

Theorem 1. Let ff be a Boolean function of labelled graphs on nn vertices, and let 0<p<10<p<1. With σ=p(1−p)\sigma=\sqrt{p(1-p)}, the variance Parseval identity is (7): Var⁡p(f)=∑⌀≠S⊆Enfˆ(S)2.\operatorname{Var}_p(f)= \sum_{\varnothing\ne S\subseteq E_n}\widehat f(S)^2.(7)✦ The Dirichlet influence identity is (8): ∑S⊆En|S|fˆ(S)2=σ2Ip(f).\sum_{S\subseteq E_n}|S|\widehat f(S)^2 =\sigma^2 I_p(f).(8)✦

More generally, let cc be a real coefficient family on a finite set AA. Let V∈ℝV\in\mathbb R, J≥0J\ge0, σ>0\sigma>0, and t>0t>0 satisfy the spectral identities in (9): V=∑⌀≠S⊆Ac(S)2,∑S⊆A|S|c(S)2=σ2J.V=\sum_{\varnothing\ne S\subseteq A}c(S)^2, \qquad \sum_{S\subseteq A}|S|c(S)^2=\sigma^2J.(9) Suppose m>0m>0 satisfies t/3≤log⁡mt/3\le\log m and the capture bound (10), with Cσ(m)C_\sigma(m) as in (6): Cσ(m)≤4m−1/4J.C_\sigma(m)\le 4m^{-1/4}J.(10) Then the variance bound from capture is (11): V≤217t2J.V\le\frac{2^{17}}{t^2}J.(11)✦

Alternatively, suppose σ2≤1/4\sigma^2\le1/4 and, whenever t≥16t\ge16, there exists m>0m>0 satisfying t/3≤log⁡mt/3\le\log m and (10). Under (9), the variance bound at all scales is (12): V≤217t2J.V\le\frac{2^{17}}{t^2}J.(12)✦

In the paper, the result reads: for t=log⁡n≥16t=\log n\ge16 and its choices of mm and the Fourier cutoff parameter kk, Parseval, captured mass, and ∑S⊆En|S|fˆ(S)2=σ2Ip(f)\sum_{S\subseteq E_n}|S|\widehat f(S)^2=\sigma^2I_p(f) give Var⁡p(f)≤[4m−1/4+2σ2/k2]Ip(f)≤(217/t2)Ip(f)\operatorname{Var}_p(f)\le[4m^{-1/4}+2\sigma^2/k^2]I_p(f) \le(2^{17}/t^2)I_p(f), while for 0<log⁡n<160<\log n<16, Poincaré gives Var⁡p(f)≤σ2Ip(f)≤Ip(f)/4\operatorname{Var}_p(f)\le\sigma^2I_p(f)\le I_p(f)/4, which suffices for the same final constant.

What Is Checked

The graph identities concern arbitrary Boolean functions on labelled graphs at interior biases; the numerical estimates concern arbitrary real coefficient families on a finite coordinate set satisfying (9) and the respective capture hypotheses.