OctoInformBeta

OpenAI preprint, September 2026 · §5. A chain and its observable Poincaré bound · §5, (5.1) to (5.3)

Chain weights, good multipliers and type masses (5.1) to (5.3): Weights ff on transversals and wprfw_{pr}f on defect states; under good multipliers, Λ≤5n2c0\Lambda \le 5n^2c_0 and the transversals keep mass at least 1/(5n2)1/(5n^2)

Good multipliers give each state type mass at least 1/(20n2)1/(20n^2)..

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

For two matroids on [n][n], the counting of common bases works on the doubled ground set [n]⊔[n][n] \sqcup [n], whose elements come in nn pairs, the two copies of each ii. Here Γ\Gamma is any finite set, P=(p1,…,pn)P = (p_1, \dots, p_n) any list of pairs p=(xp,yp)p = (x_p, y_p) of elements of Γ\Gamma, and ff any real function on the subsets of Γ\Gamma, read as the multiaffine polynomial ∑Sf(S)∏i∈Szi\sum_{S} f(S) \prod_{i \in S} z_i in the variables ziz_i, one for each element ii of Γ\Gamma.

A pair pp of elements of Γ\Gamma is empty, single or full in a subset SS of Γ\Gamma when SS contains none, exactly one or both of its entries xpx_p and ypy_p. A transversal, or plain state, of PP is a subset of Γ\Gamma in which every pair of PP is single.✦ For 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.✦ We write Ω0\Omega_0 for the set of transversals and Ωpr\Omega_{pr} for the set of defect states of type (p,r)(p, r).

A Markov chain on the transversals and all the defect states reweights each type of defect state by its own multiplier wprw_{pr}. The question is how large the multipliers may be, and how small, if neither the transversals nor any type of defect state is to be rare under the chain’s stationary distribution.

Slot Totals

For a pair qq of elements of Γ\Gamma, the pair direction 𝟏q\mathbf{1}_q is the indicator vector of {xq,yq}\{x_q, y_q\}, the vector of ℝΓ\mathbb{R}^\Gamma with entry 11 at xqx_q and at yqy_q and 00 elsewhere.✦ For a list Q=(q1,…,qk)Q = (q_1, \dots, q_k) of pairs, the slot total ∂Qf\partial_Q f is the iterated derivative of ff along their pair directions, ∂Qf=D𝟏q1D𝟏q2⋯D𝟏qkf,\partial_Q f = D_{\mathbf{1}_{q_1}} D_{\mathbf{1}_{q_2}} \cdots D_{\mathbf{1}_{q_k}} f,(1)✦ where DaD_a is the derivative along a vector aa of ℝΓ\mathbb{R}^\Gamma, and ∂Qf(A)\partial_Q f(A) is its coefficient at a set AA.

Two slot totals enter the claim below: the plain total c0c_0 and, for distinct pairs pp and rr of PP, the defect total cprc_{pr}, defined by c0=∂Pf(∅),cpr=∂P\{p,r}f({xr,yr}),c_0 = \partial_P f(\emptyset), \qquad c_{pr} = \partial_{P \setminus \{p, r\}} f(\{x_r, y_r\}),(2) where P\{p,r}P \setminus \{p, r\} is the list PP with pp and rr removed. When the 2n2n entries of PP are distinct and cover Γ\Gamma, c0c_0 is the sum of ff over Ω0\Omega_0 and cprc_{pr} the sum of ff over Ωpr\Omega_{pr}.

The Claim

Definition 1. Let w=(wpr)w = (w_{pr}) be a family of real multipliers, one for every two pairs pp and rr of elements of Γ\Gamma. The chain states of PP form the set Ω=Ω0∪⋃p,r∈P,p≠rΩpr.\Omega = \Omega_0 \cup \bigcup_{p, r \in P,\ p \neq r} \Omega_{pr}.(3)✦ The chain multiplier and the chain weight of a subset SS of Γ\Gamma are m(S)={wprif S∈Ωpr,1otherwise,m(S) = \begin{cases} w_{pr} & \text{if } S \in \Omega_{pr}, \\ 1 & \text{otherwise}, \end{cases}(4)✦ λ(S)=m(S)f(S),\lambda(S) = m(S)\, f(S),(5)✦ the chain total Λ\Lambda of ww and ff is Λ=∑S∈Ωλ(S),\Lambda = \sum_{S \in \Omega} \lambda(S),(6) and the mean of a real function HH on the subsets of Γ\Gamma under π=λ/Λ\pi = \lambda / \Lambda is 𝔼πH=Λ−1∑S∈Ωλ(S)H(S)\mathbb{E}_\pi H = \Lambda^{-1} \sum_{S \in \Omega} \lambda(S) H(S)✦, with π(Ωpr)=𝔼π𝟏Ωpr\pi(\Omega_{pr}) = \mathbb{E}_\pi \mathbf{1}_{\Omega_{pr}} the mass of the defect states of type (p,r)(p, r). The family ww of multipliers is good for ff when every wprw_{pr} is positive and, for all distinct pairs pp and rr of PP, c04cpr≤wpr≤4c0cpr,\frac{c_0}{4 c_{pr}} \le w_{pr} \le \frac{4 c_0}{c_{pr}},(7)✦ whose left inequality is the lower half and whose right inequality is the upper half. Here 𝟏Ωpr\mathbf{1}_{\Omega_{pr}} is the indicator function of the set Ωpr\Omega_{pr} on the subsets of Γ\Gamma: it equals 11 at a defect state of type (p,r)(p, r) and 00 at every other subset.

Theorem 1. Let PP be a list of n≥1n \ge 1 pairs of elements of a finite set Γ\Gamma whose 2n2n entries are distinct and cover Γ\Gamma, let ff be a positive function on the subsets of Γ\Gamma, and let ww be a family of multipliers. If ww satisfies the upper half of (7), then Λ≤5n2c0.\Lambda \le 5 n^2 c_0.(8)✦ If moreover every wprw_{pr} is positive, then c0Λ≥15n2.\frac{c_0}{\Lambda} \ge \frac{1}{5 n^2}.(9)✦ If ww is good for ff, then for all distinct pairs pp and rr of PP, π(Ωpr)≥120n2.\pi(\Omega_{pr}) \ge \frac{1}{20 n^2}.(10)✦

In the paper, the result reads: with λ(S)=f(S)\lambda(S) = f(S) on Ω0\Omega_0 and λ(S)=wprf(S)\lambda(S) = w_{pr} f(S) on Ωpr\Omega_{pr}, π=λ/Λ\pi = \lambda / \Lambda and μ=f/c0\mu = f / c_0 on Ω0\Omega_0, the multipliers are good when wpr*/4≤wpr≤4wpr*w^*_{pr}/4 \le w_{pr} \le 4 w^*_{pr} for wpr*=c0/cprw^*_{pr} = c_0 / c_{pr}, and then Λ≤5n2c0\Lambda \le 5n^2 c_0, π(Ω0)≥1/(5n2)\pi(\Omega_0) \ge 1/(5n^2) and π(Ωpr)≥1/(20n2)\pi(\Omega_{pr}) \ge 1/(20n^2); the paper writes fqf_q for ff and indexes the pairs by ii and jj in place of pp and rr. The ratio c0/Λc_0 / \Lambda in (9) is the mass π(Ω0)\pi(\Omega_0) of the transversals.

What Is Checked

The definitions (3) to (7) are stated over a list PP of pairs of elements of a finite set Γ\Gamma, a real function ff on the subsets of Γ\Gamma with its plain and defect totals c0c_0 and cprc_{pr}, and a family ww of real multipliers; the bounds (8) to (10) are stated over the same objects with n≥1n \ge 1, the entries of PP distinct and covering Γ\Gamma, ff positive, and only those conditions of goodness that each bound uses.