OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

Theorem 1.2: At every interior bias, total edge influence controls variance through a squared logarithm of the vertex count

Vertex symmetry gives a variance bound.

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

Let nn be the number of labelled vertices, and write [n]={1,…,n}[n]=\{1,\ldots,n\}. A potential edge ee on [n][n] is a two-element subset of [n][n]✦; a labelled graph xx on [n][n] is an assignment of an edge indicator xex_e to each potential edge ee, with 11 indicating presence.✦ The edge set and graph space are En={e⊆[n]:|e|=2},𝒳n={0,1}En.E_n=\{e\subseteq[n]:|e|=2\}, \qquad \mathcal X_n=\{0,1\}^{E_n}.(1) A Boolean graph function f:𝒳n→{0,1}f:\mathcal X_n\to\{0,1\} specifies a property of the graphs in (1), with f(x)=1f(x)=1 indicating membership. The Boolean indicator sends false\mathrm{false} to the real number 00 and true\mathrm{true} to the real number 11; expectations use these real values.✦

For a vertex permutation π\pi, the permuted edge πe\pi e is the image of ee under π\pi✦, and the relabelled graph πx\pi x is given by πe={π(v):v∈e},(πx)e=xπ−1e.\pi e=\{\pi(v):v\in e\}, \qquad (\pi x)_e=x_{\pi^{-1}e}.(2) A vertex-invariant Boolean graph function f:𝒳n→{0,1}f:\mathcal X_n\to\{0,1\} is a function whose value is preserved by every vertex relabelling in (2): f(πx)=f(x)for every vertex permutation π and every x∈𝒳n.f(\pi x)=f(x) \qquad\text{for every vertex permutation $\pi$ and every $x\in\mathcal X_n$.}(3)✦

Fix an edge bias 0<p<10<p<1. The random graph probability mass wp(x)w_p(x) of a labelled graph xx is the product of the probabilities of its edge indicators: wp(x)=∏e∈Enpxe(1−p)1−xe.w_p(x)=\prod_{e\in E_n}p^{x_e}(1-p)^{1-x_e}.(4)✦ The distribution in (4) is denoted by G(n,p)G(n,p). For a Boolean graph function f:𝒳n→{0,1}f:\mathcal X_n\to\{0,1\}, the graph property probability μp(f)\mu_p(f) is the probability that f(x)=1f(x)=1 under G(n,p)G(n,p)✦, and the graph variance Var⁡p(f)\operatorname{Var}_p(f) is the expected squared deviation of its Boolean indicator from its mean: μp(f)=∑x∈𝒳nwp(x)f(x),Var⁡p(f)=∑x∈𝒳nwp(x)(f(x)−μp(f))2.\begin{aligned} \mu_p(f)&=\sum_{x\in\mathcal X_n}w_p(x)f(x),\\ \operatorname{Var}_p(f)&= \sum_{x\in\mathcal X_n}w_p(x)\bigl(f(x)-\mu_p(f)\bigr)^2. \end{aligned}(5)

For a graph x∈𝒳nx\in\mathcal X_n, an edge e∈Ene\in E_n, and an indicator b∈{0,1}b\in\{0,1\}, let xe←bx^{e\leftarrow b} be the graph obtained from xx by setting its edge indicator at ee to bb. The pivotal edge influence Ie,p(f)I_{e,p}(f) of a Boolean graph function f:𝒳n→{0,1}f:\mathcal X_n\to\{0,1\} at an edge e∈Ene\in E_n is the probability that changing edge ee changes ff, with every other edge present independently with probability pp.✦ The total influence Ip(f)I_p(f) of a Boolean graph function f:𝒳n→{0,1}f:\mathcal X_n\to\{0,1\} is the sum of its pivotal edge influences Ie,p(f)I_{e,p}(f) over all edges e∈Ene\in E_n: Ie,p(f)=ℙx∼G(n,p)(f(xe←0)≠f(xe←1)),Ip(f)=∑e∈EnIe,p(f).I_{e,p}(f)=\mathbb P_{x\sim G(n,p)} \bigl(f(x^{e\leftarrow0})\ne f(x^{e\leftarrow1})\bigr), \qquad I_p(f)=\sum_{e\in E_n}I_{e,p}(f).(6) All logarithms are natural logarithms.

The Claim

Theorem 1. Let n≥2n\ge2 be an integer, let f:𝒳n→{0,1}f:\mathcal X_n\to\{0,1\} be vertex-invariant in the sense of (3), and let 0<p<10<p<1. For the variance in (5) and total influence in (6), the uniform variance influence bound is (7): Var⁡p(f)≤217(log⁡n)2Ip(f).\operatorname{Var}_p(f) \le \frac{2^{17}}{(\log n)^2}\,I_p(f).(7)✦ The pointwise variance bound is the specialization of (7) to fixed nn, ff and pp. For fixed n≥2n\ge2, vertex-invariant f:𝒳n→{0,1}f:\mathcal X_n\to\{0,1\}, and 0<p<10<p<1: Var⁡p(f)≤217(log⁡n)2Ip(f).\operatorname{Var}_p(f) \le \frac{2^{17}}{(\log n)^2}\,I_p(f).(8)✦

What Is Checked

Both bounds are stated over Boolean functions on the labelled graphs in (1), with vertex permutation invariance, n≥2n\ge2 and 0<p<10<p<1, using the independent edge probability mass in (4) and the variance and pivotal edge influences in (5) and (6).