OctoInformBeta

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

Lemma 5.2: For a positive weight with the slot signature property and multipliers wpr≥c0/(4cpr)w_{pr} \ge c_0/(4c_{pr}): c0(H‾pr−H‾0)2≤(8+32n)𝒟(H)c_0(\bar H_{pr}-\bar H_0)^2 \le (8+32n)\,\mathcal{D}(H)

Dirichlet energy ties defect class means to the transversal mean.

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 Γ\Gamma be a finite set, PP a list of nn pairs {xi,yi}\{x_i, y_i\} of elements of Γ\Gamma whose 2n2n entries are pairwise distinct, and ff a positive weight on the subsets of Γ\Gamma, in the role of the paper’s weight fqf_q. A transversal takes one element from each pair.✦ The chain studied here walks on the transversals and on defect states, in which a pair pp is left empty and another pair rr is taken whole, so that the state has type (p,r)(p,r); it moves by exchanging one element for another, and at a defect state of type (p,r)(p,r) it scales the weight by a multiplier wprw_{pr}. For an observable HH, a real function on the subsets of Γ\Gamma, the lemma bounds how far the mean of HH over the defect states of one type can lie from its mean over the transversals, against the Dirichlet energy of HH, the quantity with which a Poincaré inequality bounds the variance.

States and Moves

A pair q={x,y}q = \{x, y\} of elements of Γ\Gamma is empty in a subset SS of Γ\Gamma when neither xx nor yy lies in SS✦, full in SS when both do✦, and single in SS when exactly one does.✦

A plain state, or transversal, of PP is a subset of Γ\Gamma in which every pair of PP is single; Ω0\Omega_0 is the set of transversals.✦ For two distinct pairs pp and rr of PP, a defect state of type (p,r)(p,r) is a subset of Γ\Gamma in which pp is empty, rr is full and every other pair of PP is single; these states form the defect class Ωpr\Omega_{pr}.✦ A chain state is a subset of Γ\Gamma that is a plain state or a defect state of some type, and Ω\Omega is the set of chain states.✦

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 subset AA of Γ\Gamma and distinct elements a,b∉Aa, b \notin A.✦ The edge set EE of the chain is the set of ordered pairs (S,T)(S,T) of chain states that are exchange adjacent.✦

Slot Totals and Means

A real function gg on the subsets of Γ\Gamma is the coefficient function of the multiaffine polynomial ∑S⊆Γg(S)∏i∈Sti\sum_{S \subseteq \Gamma} g(S) \prod_{i \in S} t_i in the variables tit_i, i∈Γi \in \Gamma, and for a vector a∈ℝΓa \in \mathbb{R}^\Gamma the derivative ∂ag\partial_a g is the coefficient function of the directional derivative ∑i∈Γai∂/∂ti\sum_{i \in \Gamma} a_i\, \partial/\partial t_i of that polynomial. The indicator vector 𝟏F\mathbf{1}_F of a set F⊆ΓF \subseteq \Gamma has entry 11 on FF and 00 elsewhere✦, and a pair q={x,y}q = \{x, y\} has direction 𝟏q=𝟏{x,y}\mathbf{1}_q = \mathbf{1}_{\{x,y\}}.✦ The slot total of gg along a list L=(q1,…,qk)L = (q_1, \dots, q_k) of pairs is the iterated derivative ∂Lg=∂𝟏q1∂𝟏q2⋯∂𝟏qkg;\partial_L g = \partial_{\mathbf{1}_{q_1}} \partial_{\mathbf{1}_{q_2}} \cdots \partial_{\mathbf{1}_{q_k}}\, g;(1)✦ when the pairs of LL are disjoint and avoid a set AA, ∂Lg(A)\partial_L g(A) is the sum of gg over the sets obtained from AA by adding one element of each pair.

For two pairs pp and rr of PP and a subset AA of Γ\Gamma, the defect total of gg at AA is cpr(g;A)=∂P\{p,r}g(A∪r)c_{pr}(g; A) = \partial_{P \setminus \{p,r\}}\, g(A \cup r).✦ The masses of the transversals and of a defect class are c0=∂Pf(∅)=∑S∈Ω0f(S),cpr=cpr(f;∅)=∑S∈Ωprf(S),c_0 = \partial_P f(\emptyset) = \sum_{S \in \Omega_0} f(S), \qquad c_{pr} = c_{pr}(f; \emptyset) = \sum_{S \in \Omega_{pr}} f(S),(2) and, with fHfH the pointwise product S↦f(S)H(S)S \mapsto f(S)H(S), the means of HH over them are H‾0=∂P(fH)(∅)c0,H‾pr=cpr(fH;∅)cpr.\bar H_0 = \frac{\partial_P (fH)(\emptyset)}{c_0}, \qquad \bar H_{pr} = \frac{c_{pr}(fH; \emptyset)}{c_{pr}}.(3)

For an element aa of a pair pp of PP and an element bb of another pair rr of PP, the transversal event TabT_{ab} is the set of transversals that contain aa and bb. Its mass and the mean of HH over it are zab=∂P\{p,r}f({a,b})=∑S∈Tabf(S),H‾ab=∂P\{p,r}(fH)({a,b})zab.z_{ab} = \partial_{P \setminus \{p,r\}} f(\{a,b\}) = \sum_{S \in T_{ab}} f(S), \qquad \bar H_{ab} = \frac{\partial_{P \setminus \{p,r\}} (fH)(\{a,b\})}{z_{ab}}.(4)

The Slot Signature

The face Hessian ∇A2g\nabla^2_A g of gg at a subset AA of Γ\Gamma is the symmetric matrix with rows and columns indexed by Γ\A\Gamma \setminus A, zero diagonal, and entry g(A∪{i,j})g(A \cup \{i,j\}) at distinct ii and jj.✦

A bilinear form BB on a real vector space WW has one positive direction when, for every e∈We \in W with B(e,e)>0B(e,e) > 0, every v∈Wv \in W with B(v,e)=0B(v,e) = 0 satisfies B(v,v)≤0B(v,v) \le 0; for a symmetric form this is the condition of at most one positive eigenvalue.✦

A real function ff on the subsets of Γ\Gamma has the slot signature property when, for every list LL of pairs of elements of Γ\Gamma and every subset AA of Γ\Gamma, the bilinear form of the face Hessian ∇A2(∂Lf)\nabla^2_A(\partial_L f) has one positive direction.✦

Multipliers and Energy

A family of multipliers w=(wpr)w = (w_{pr}) for PP is a family of positive reals wprw_{pr}, one for each ordered pair (p,r)(p,r) of pairs of PP. The multipliers ww are good when c04cpr≤wpr≤4c0cprfor all distinct pairs p and r of P,\frac{c_0}{4c_{pr}} \le w_{pr} \le \frac{4c_0}{c_{pr}} \quad \text{for all distinct pairs $p$ and $r$ of $P$},(5) and the left inequality is the lower half of (5). The multiplier m(S)m(S) of a subset SS of Γ\Gamma is wprw_{pr} when SS is a defect state of type (p,r)(p,r), and 11 otherwise.✦ The conductance of an edge (S,T)(S,T) is Q(S,T)=min⁡{m(S)f(S),m(T)f(T)}.Q(S,T) = \min\{\, m(S) f(S),\ m(T) f(T) \,\}.(6)✦

For subsets AA and BB of Γ\Gamma, a subset of Γ\Gamma respects (A,B)(A,B) when it contains AA and is disjoint from BB✦, and an edge respects (A,B)(A,B) when both of its endpoints do.✦ Over a finite set of edges with conductances cc, the energy of a function HH on the subsets of Γ\Gamma restricted to (A,B)(A,B) is half the sum of c(S,T)(H(S)−H(T))2c(S,T)\,(H(S) - H(T))^2 over the edges (S,T)(S,T) that respect (A,B)(A,B).✦ The Dirichlet energy 𝒟(H)\mathcal{D}(H) of a function HH on the subsets of Γ\Gamma for the chain is the energy of HH over the edge set EE with conductances QQ, restricted to (∅,∅)(\emptyset, \emptyset): 𝒟(H)=12∑(S,T)∈EQ(S,T)(H(S)−H(T))2.\mathcal{D}(H) = \frac{1}{2} \sum_{(S,T) \in E} Q(S,T)\, \bigl(H(S) - H(T)\bigr)^2.(7)

The Claim

Theorem 1. Let PP be a list of nn pairs of elements of a finite set Γ\Gamma whose 2n2n entries are pairwise distinct, and let pp and rr be two distinct pairs of PP. Let ff be a positive weight on the subsets of Γ\Gamma with the slot signature property, let ww be positive multipliers that satisfy the lower half of (5), and let HH be a real function on the subsets of Γ\Gamma. Then there is a constant CnC_n, depending on nn alone, such that for every element aa of pp and every element bb of rr zab(H‾pr−H‾ab)2≤Cn𝒟(H),z_{ab}\,\bigl(\bar H_{pr} - \bar H_{ab}\bigr)^2 \le C_n\, \mathcal{D}(H),(8)✦ and the mean of HH over the defect class of type (p,r)(p,r) satisfies c0(H‾pr−H‾0)2≤(8+32n)𝒟(H).c_0\,\bigl(\bar H_{pr} - \bar H_0\bigr)^2 \le (8 + 32n)\, \mathcal{D}(H).(9)✦

In the paper, the result reads: for good multipliers, every function HH on Ω\Omega and every defect type (p,r)(p,r), the paper’s type ijij, there is an event 𝒜⊆Ω0\mathcal{A} \subseteq \Omega_0 prescribing the selected elements of pp and rr with μ(𝒜)≥1/4\mu(\mathcal{A}) \ge 1/4 such that (H‾pr−H‾′)2≤Cd𝒟(H)/c0(\bar H_{pr} - \bar H')^2 \le C_d\, \mathcal{D}(H)/c_0 with Cd=8+32nC_d = 8 + 32n and (H‾′−H‾0)2≤4Var⁡μH(\bar H' - \bar H_0)^2 \le 4 \operatorname{Var}_\mu H, where H‾′=𝔼μ[H∣𝒜]\bar H' = \mathbb{E}_\mu[H \mid \mathcal{A}] and μ\mu is the paper’s probability measure on Ω\Omega.

What Is Checked

Both bounds are stated over a finite set Γ\Gamma with a list PP of nn pairs whose 2n2n entries are pairwise distinct, two distinct pairs pp and rr of PP, a positive weight ff with the slot signature property, positive multipliers satisfying the lower half of (5), and an arbitrary real function HH on the subsets of Γ\Gamma, with 𝒟\mathcal{D} the Dirichlet energy (7) of the chain on plain and defect states with exchange edges and conductances (6). The bound (8) is stated in addition over a choice of one element of pp and one element of rr, which fixes the transversal event TabT_{ab}.