OctoInformBeta

OpenAI preprint, September 2026 · §5. A chain and its observable Poincaré bound · §5

The projection Q: The defect class means of HH are ratios of slot totals and QQ puts each on its class; class observables are constant there

Averaging over defect classes and under the chain’s law.

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

The Markov chain behind the approximate count of common bases of two matroids on [n][n] moves on subsets of the paired ground set V=[n]⊔[n]V = [n] \sqcup [n], where the two copies of each i∈[n]i \in [n] form a pair. The library works with any finite set Γ\Gamma and a list 𝒫=(p1,…,pn)\mathcal{P} = (p_1, \dots, p_n) of disjoint pairs pi={xi,yi}p_i = \{x_i, y_i\} of its elements. These notes define, for a real function HH on the subsets of Γ\Gamma, its averages over classes of chain states, the projection QQ built from them, and its mean and variance over the chain states under the chain weight π\pi defined below.

A pair pp of elements of Γ\Gamma is empty in a subset SS of Γ\Gamma when SS contains neither of its elements✦, single when SS contains exactly one✦, and full when SS contains both.✦ A plain state, or transversal, of 𝒫\mathcal{P} is a subset of Γ\Gamma in which every pair of 𝒫\mathcal{P} is single; Ω0\Omega_0 is the set of them.✦ For distinct pairs pp and rr of 𝒫\mathcal{P}, a defect state of class (p,r)(p, r) is a subset of Γ\Gamma in which pp is empty, rr is full and every other pair of 𝒫\mathcal{P} is single; the defect class Ωpr\Omega_{pr} is the set of them.✦ A chain state is a plain state or a defect state of some class✦, and the chain states form the finite set Ω=Ω0∪⋃p≠rΩpr.\Omega = \Omega_0 \cup \bigcup_{p \neq r} \Omega_{pr}.(1)✦

Weights and Slot Totals

Let ff be a real function on the subsets of Γ\Gamma, and let wprw_{pr} be real multipliers, one for each ordered pair (p,r)(p, r) of pairs of 𝒫\mathcal{P}. The multiplier m(S)m(S) of a subset SS of Γ\Gamma is wprw_{pr} when S∈ΩprS \in \Omega_{pr} and 11 otherwise.✦ The chain weight π(S)\pi(S) of SS and the total chain weight π(Ω)\pi(\Omega) are π(S)=m(S)f(S),π(Ω)=∑S∈Ωπ(S).\pi(S) = m(S)\, f(S), \qquad \pi(\Omega) = \sum_{S \in \Omega} \pi(S).(2)

Read a real function gg on the subsets of Γ\Gamma as the multiaffine polynomial ∑S⊆Γg(S)zS\sum_{S \subseteq \Gamma} g(S)\, z^S in the variables zγz_\gamma for γ∈Γ\gamma \in \Gamma, where zSz^S is the product of the zγz_\gamma with γ∈S\gamma \in S. For a vector aa of ℝΓ\mathbb{R}^\Gamma, DagD_a g is the coefficient function of the derivative of this polynomial along aa, and the iterated derivative along a list of vectors is D(a1,…,ak)g=Da1Da2⋯DakgD_{(a_1, \dots, a_k)} g = D_{a_1} D_{a_2} \cdots D_{a_k} g, which is gg itself for the empty list.✦ The indicator vector 𝟏E\mathbf{1}_E of a finite set E⊆ΓE \subseteq \Gamma has entry 11 on EE and 00 elsewhere✦, and the direction of a pair {x,y}\{x, y\} is 𝟏{x,y}\mathbf{1}_{\{x, y\}}.✦ The slot total of gg along 𝒫\mathcal{P} is the iterated derivative along the directions of its pairs, ∂𝒫g=D(𝟏{x1,y1},…,𝟏{xn,yn})g,\partial_{\mathcal{P}}\, g = D_{(\mathbf{1}_{\{x_1, y_1\}}, \dots, \mathbf{1}_{\{x_n, y_n\}})}\, g,(3)✦ and at a set AA that no pair of 𝒫\mathcal{P} meets, ∂𝒫g(A)\partial_{\mathcal{P}} g(A) is the sum of gg over the sets obtained from AA by adding one element of each pair.

For distinct pairs pp and rr of 𝒫\mathcal{P}, the defect total of gg at a set AA is the slot total along the list 𝒫\{p,r}\mathcal{P} \setminus \{p, r\} obtained by removing pp and rr, taken at AA with both elements of rr added: cpr(g;A)=∂𝒫\{p,r}g(A∪r).c_{pr}(g; A) = \partial_{\mathcal{P} \setminus \{p, r\}}\, g\,(A \cup r).(4)✦ At a set AA that no pair meets, it is the sum of gg over the sets that add to AA both elements of rr, no element of pp and one element of each other pair. Write c0(g)=∂𝒫g(∅)c_0(g) = \partial_{\mathcal{P}} g(\emptyset) and cpr(g)=cpr(g;∅)c_{pr}(g) = c_{pr}(g; \emptyset).

The Definition

Definition 1. A class observable of 𝒫\mathcal{P} is a real function HH on the subsets of Γ\Gamma that is constant on each defect class: H(S)=H(T)for all distinct p,r∈𝒫 and all S,T∈Ωpr.H(S) = H(T) \quad \text{for all distinct } p, r \in \mathcal{P} \text{ and all } S, T \in \Omega_{pr}.(5)✦

Let HH be any real function on the subsets of Γ\Gamma, and let fHfH be the function S↦f(S)H(S)S \mapsto f(S)\, H(S). The transversal mean H‾0\bar{H}_0 of HH is its mean, weighted by ff, over the sets made of one element of each pair of 𝒫\mathcal{P}: H‾0=c0(fH)c0(f).\bar{H}_0 = \frac{c_0(fH)}{c_0(f)}.(6)✦ For distinct pairs pp and rr of 𝒫\mathcal{P}, the defect class mean H‾pr\bar{H}_{pr} of HH is its mean, weighted by ff, over the sets made of both elements of rr and one element of each pair other than pp and rr: H‾pr=cpr(fH)cpr(f).\bar{H}_{pr} = \frac{c_{pr}(fH)}{c_{pr}(f)}.(7)✦ The projection QHQH of HH is the real function on the subsets of Γ\Gamma given by (QH)(S)={H‾prif S∈Ωpr for distinct pairs p,r of 𝒫,H(S)otherwise.(QH)(S) = \begin{cases} \bar{H}_{pr} & \text{if } S \in \Omega_{pr} \text{ for distinct pairs } p, r \text{ of } \mathcal{P},\\ H(S) & \text{otherwise.} \end{cases}(8)✦

For a real function HH on the subsets of Γ\Gamma, the chain mean 𝔼π[H]\mathbb{E}_\pi[H] and the chain variance Var⁡π(H)\operatorname{Var}_\pi(H) are its mean and variance over the chain states, weighted by the chain weight π\pi of (2): 𝔼π[H]=1π(Ω)∑S∈Ωπ(S)H(S),\mathbb{E}_\pi[H] = \frac{1}{\pi(\Omega)} \sum_{S \in \Omega} \pi(S)\, H(S),(9)✦ Var⁡π(H)=1π(Ω)∑S∈Ωπ(S)(H(S)−𝔼π[H])2.\operatorname{Var}_\pi(H) = \frac{1}{\pi(\Omega)} \sum_{S \in \Omega} \pi(S) \bigl(H(S) - \mathbb{E}_\pi[H]\bigr)^2.(10)✦

In the paper, the result reads: QQ keeps every value of HH on Ω0\Omega_0 and replaces the values of HH on each defect class Ωpr\Omega_{pr} by the conditional mean of HH on that class.

What Is Checked

The definitions (8) to (10) are stated over a finite set Γ\Gamma, the list 𝒫\mathcal{P} of pairs of its elements with its transversals and defect classes, a real function ff on the subsets of Γ\Gamma with its slot totals (3) and defect totals (4), and the multipliers wprw_{pr} with the chain weight (2) on the chain states Ω\Omega of (1).