OctoInformBeta

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

Proposition 5.3: For nonempty disjoint pairs covering Γ\Gamma, good multipliers and a positive ff with the slot signature property, Varπ(QH)≤2000n6ℰ(H)\mathrm{Var}_\pi(QH)\le 2000n^6\,\mathcal{E}(H)

An observable Poincaré bound on plain and defect states.

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

Take a finite set Γ\Gamma split into disjoint pairs and a positive function ff on its subsets. A Markov chain moves, by exchanging one element for another, among the plain states and the defect states. Averaging an observable over each class of defect states gives its projection. The question is whether the stationary variance of the projection is bounded by a polynomial multiple of the Dirichlet form of the observable itself, a Poincaré inequality in observable form. The two matroids of the counting problem enter only through one hypothesis on ff, the slot signature property.

Let 𝒫=(p1,…,pn)\mathcal P=(p_1,\dots,p_n) be a list of pairs pi=(xi,yi)p_i=(x_i,y_i) of elements of Γ\Gamma, of length nn. A list of pairs of elements of Γ\Gamma is fresh for a subset BB of Γ\Gamma when the entries of its pairs are pairwise distinct and none of them lies in BB.✦ The support of a list 𝒫\mathcal P of pairs of elements of Γ\Gamma is the set of elements of Γ\Gamma that are an entry of some pair of 𝒫\mathcal P, and 𝒫\mathcal P covers Γ\Gamma when its support is Γ\Gamma.✦ An observable HH is a real function on the subsets of Γ\Gamma.

Slot Totals and Good Multipliers

A real function ff on the subsets of Γ\Gamma is the coefficient function of the multiaffine polynomial ∑S⊆Γf(S)∏i∈Szi\sum_{S\subseteq\Gamma}f(S)\prod_{i\in S}z_i in the variables ziz_i, i∈Γi\in\Gamma. For a vector a∈ℝΓa\in\mathbb R^\Gamma, ∂af\partial_a f is the coefficient function of the derivative of this polynomial in the direction aa, and the iterated derivative along a list (a1,…,ak)(a_1,\dots,a_k) of vectors is ∂a1∂a2⋯∂akf\partial_{a_1}\partial_{a_2}\cdots\partial_{a_k}f, which is ff 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 ff along 𝒫\mathcal P is the iterated derivative along the directions of its pairs, ∂𝒫f=∂𝟏{x1,y1}∂𝟏{x2,y2}⋯∂𝟏{xn,yn}f,\partial_{\mathcal P}f=\partial_{\mathbf 1_{\{x_1,y_1\}}}\partial_{\mathbf 1_{\{x_2,y_2\}}}\cdots \partial_{\mathbf 1_{\{x_n,y_n\}}}f,(1)✦ and when the pairs are disjoint and avoid a set AA, its value ∂𝒫f(A)\partial_{\mathcal P}f(A) is the sum of ff over the sets obtained from AA by adding one element of each pair. We write c0=∂𝒫f(∅)c_0=\partial_{\mathcal P}f(\emptyset).

For pairs pp and r=(xr,yr)r=(x_r,y_r) of the list and a subset AA of Γ\Gamma, the slot defect of ff at AA is the slot total along the list with pp and rr removed, taken at AA with both entries of rr added: ∂𝒫prf(A)=∂𝒫\{p,r}f(A∪{xr,yr}),cpr=∂𝒫prf(∅).\partial^{pr}_{\mathcal P}f(A)=\partial_{\mathcal P\setminus\{p,r\}}f\bigl(A\cup\{x_r,y_r\}\bigr), \qquad c_{pr}=\partial^{pr}_{\mathcal P}f(\emptyset).(2)✦ When the pairs are disjoint and avoid AA, it is the sum of ff over the sets that add to AA both entries of rr, no entry of pp and one entry of each other pair.

The face Hessian of a real function gg on the subsets of Γ\Gamma at a subset AA is the symmetric matrix HessAg\mathrm{Hess}_A g with rows and columns indexed by Γ\A\Gamma\setminus A, zero diagonal, and entry g(A∪{i,j})g(A\cup\{i,j\}) for distinct ii and jj.✦ A bilinear form BB on a real vector space has one positive direction when, for every vector ee with B(e,e)>0B(e,e)>0, every vector vv with B(v,e)=0B(v,e)=0 satisfies B(v,v)≤0B(v,v)\le 0; for a symmetric form this is having at most one positive eigenvalue.✦ A real function ff on the subsets of Γ\Gamma has the slot signature property when, for every list ℒ\mathcal L of pairs of elements of Γ\Gamma and every subset AA of Γ\Gamma, the bilinear form of HessA(∂ℒf)\mathrm{Hess}_A(\partial_{\mathcal L}f) has one positive direction.✦

Multipliers are reals wprw_{pr}, one for each ordered pair (p,r)(p,r) of pairs of elements of Γ\Gamma. Multipliers ww are good for a function ff along a list 𝒫\mathcal P of pairs of elements of Γ\Gamma when, for all distinct pairs pp and rr of 𝒫\mathcal P, c04cpr≤wpr≤4c0cpr.\frac{c_0}{4c_{pr}}\le w_{pr}\le\frac{4c_0}{c_{pr}}.(3)

The Chain

A pair p=(x,y)p=(x,y) of elements of Γ\Gamma is empty in a subset SS of Γ\Gamma when neither xx nor yy lies in SS✦, full when both do✦, and single when exactly one does.✦ A subset SS of Γ\Gamma is a plain state of 𝒫\mathcal P when every pair of the list is single in SS.✦ For distinct pairs pp and rr of the list, a subset SS of Γ\Gamma is a defect state for (p,r)(p,r) when pp is empty in SS, rr is full in SS and every other pair of the list is single in SS.✦ A chain state of 𝒫\mathcal P is a subset of Γ\Gamma that is a plain state or a defect state for some (p,r)(p,r)✦, and Ω\Omega is the finite set of chain states.✦

The multiplier of a subset SS is m(S)=wprm(S)=w_{pr} when SS is a defect state for (p,r)(p,r), and m(S)=1m(S)=1 otherwise.✦ The weight of SS and the total weight are π(S)=m(S)f(S),W=∑S∈Ωπ(S),\pi(S)=m(S)\,f(S),\qquad W=\sum_{S\in\Omega}\pi(S),(4) and the mean and the variance of an observable HH are 𝔼πH=1W∑S∈Ωπ(S)H(S),Varπ(H)=1W∑S∈Ωπ(S)(H(S)−𝔼πH)2.\mathbb E_\pi H=\frac1W\sum_{S\in\Omega}\pi(S)H(S),\qquad \mathrm{Var}_\pi(H)=\frac1W\sum_{S\in\Omega}\pi(S)\bigl(H(S)-\mathbb E_\pi H\bigr)^2.(5)

Two subsets SS and TT of Γ\Gamma are exchange adjacent when S=A∪{a}S=A\cup\{a\} and T=A∪{b}T=A\cup\{b\} for a set AA and distinct elements a,b∉Aa,b\notin A.✦ The edge set E𝒫E_{\mathcal P} of the chain consists of the ordered pairs (S,T)(S,T) of exchange adjacent chain states✦, and the conductance of an edge is κ(S,T)=min⁡(π(S),π(T)).\kappa(S,T)=\min\bigl(\pi(S),\pi(T)\bigr).(6)✦

A subset SS of Γ\Gamma respects a pair (A,B)(A,B) of subsets of Γ\Gamma when A⊆SA\subseteq S and S∩B=∅S\cap B=\emptyset✦, and an edge respects (A,B)(A,B) when both of its endpoints do.✦ For a finite set EE of edges, ordered pairs of subsets of Γ\Gamma, with conductances qq, the energy of an observable HH restricted to (A,B)(A,B) is 𝒟A,B(H)=12∑(S,T)∈E(S,T) respects (A,B)q(S,T)(H(S)−H(T))2.\mathcal D_{A,B}(H)=\frac12\sum_{\substack{(S,T)\in E\\ (S,T)\text{ respects }(A,B)}} q(S,T)\bigl(H(S)-H(T)\bigr)^2.(7)✦ The energy 𝒟(H)\mathcal D(H) of an observable HH is the restricted energy 𝒟∅,∅(H)\mathcal D_{\emptyset,\emptyset}(H) taken over the edge set E𝒫E_{\mathcal P} with conductances κ\kappa. The Dirichlet form of the chain is ℰ(H)=𝒟(H)2n2W.\mathcal E(H)=\frac{\mathcal D(H)}{2n^2W}.(8)✦

The Projection

The plain mean and, for pairs pp and rr of the list, the defect mean of an observable HH are H‾0=∂𝒫(fH)(∅)c0,H‾pr=∂𝒫pr(fH)(∅)cpr,\bar H_0=\frac{\partial_{\mathcal P}(fH)(\emptyset)}{c_0},\qquad \bar H_{pr}=\frac{\partial^{pr}_{\mathcal P}(fH)(\emptyset)}{c_{pr}},(9) with fHfH the pointwise product. The observable projection of HH is the observable QHQH equal to the defect mean on the defect states and to HH elsewhere: QH(S)={H‾prif S is a defect state for (p,r),H(S)otherwise.QH(S)=\begin{cases}\bar H_{pr}&\text{if $S$ is a defect state for $(p,r)$,}\\ H(S)&\text{otherwise.}\end{cases}(10)✦ The defect types of 𝒫\mathcal P are the ordered pairs (p,r)(p,r) of distinct pairs of the list, and 𝒯\mathcal T is their set.✦

The Claim

Theorem 1. Let Γ\Gamma be a finite set, let 𝒫\mathcal P be a list of nn pairs of elements of Γ\Gamma that is fresh for ∅\emptyset and covers Γ\Gamma, let ff be a positive real function on the subsets of Γ\Gamma with the slot signature property, and let ww be positive multipliers that are good for ff along 𝒫\mathcal P. Then every observable HH satisfies ∑S∈Ωπ(S)(QH(S)−H‾0)2≤(n(1+8n)+4|𝒯|(8+32n))𝒟(H),\sum_{S\in\Omega}\pi(S)\bigl(QH(S)-\bar H_0\bigr)^2\le \bigl(n(1+8n)+4\,|\mathcal T|\,(8+32n)\bigr)\,\mathcal D(H),(11)✦ and if 𝒫\mathcal P is nonempty, then Varπ(QH)≤2000n6ℰ(H).\mathrm{Var}_\pi(QH)\le 2000\,n^6\,\mathcal E(H).(12)✦

In the paper, the result reads: for good multipliers and every function HH on Ω\Omega, Varπ(QH)≤Kobsℰ(H)\mathrm{Var}_\pi(QH)\le K_{\mathrm{obs}}\,\mathcal E(H) with Kobs=2000n6K_{\mathrm{obs}}=2000n^6.

What Is Checked

The bounds (11) and (12) are stated over the chain states Ω\Omega of a list of pairs fresh for ∅\emptyset and covering Γ\Gamma, the weights π\pi built from the multipliers mm and from ff, the exchange edges with conductances κ\kappa, the restricted energy 𝒟\mathcal D and the Dirichlet form ℰ\mathcal E, the variance Varπ\mathrm{Var}_\pi, the slot totals and slot defects behind c0c_0, cprc_{pr}, H‾0\bar H_0 and H‾pr\bar H_{pr}, the projection QHQH and the defect types 𝒯\mathcal T, under the slot signature property of ff and good multipliers.