OctoInformBeta

OpenAI preprint, September 2026 · §2. The paired-ground-set reduction · §2, (2.2) to (2.4)

Rank weights and defect types (2.2) to (2.4): The weight qn−rk(S)q^{n-\mathrm{rk}(S)}; for disjoint pairs covering a finite set Γ\Gamma, c0c_0 and cprc_{pr} sum ff over plain and over defect states

Rank weights and slot totals over 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

Let M1M_1 and M2M_2 be matroids on [n][n], each with ground set all of [n][n], and let ZZ be the number of their common bases. The goal is a fully polynomial randomized approximation scheme (FPRAS) for ZZ, given an independence oracle for each matroid. The paired-ground-set reduction works on V=[n]⊔[n]V = [n] \sqcup [n], two copies of [n][n], in which the copies xix_i and yiy_i of each i∈[n]i \in [n] form a pair.

A transversal of the pairs is a set containing exactly one element of each pair. Exchanging one element of a transversal for another, as an exchange walk does, gives a transversal again or a set in which one pair has neither of its elements and another has both. Sets of VV are weighted by a power of a real parameter qq set by their rank in a matroid on VV.

The library states the item for any finite set Γ\Gamma and list PP of pairs p=(xp,yp)p = (x_p, y_p) of its elements, and for any real function ff on the subsets of Γ\Gamma in place of the weights.

Pairs and Slot Totals

A pair pp of PP is empty in a set S⊆ΓS \subseteq \Gamma if neither xpx_p nor ypy_p lies in SS✦, full in SS if both do✦, and single in SS if one of them lies in SS and the other does not.✦

The multiaffine polynomial FfF_f of a real function ff on the subsets of Γ\Gamma is the polynomial Ff(t)=∑S⊆Γf(S)∏i∈StiF_f(t) = \sum_{S \subseteq \Gamma} f(S) \prod_{i \in S} t_i(1) in variables tit_i, i∈Γi \in \Gamma, whose coefficient function is ff. For a vector a∈ℝΓa \in \mathbb{R}^\Gamma, the derivative in direction aa is Da=∑i∈Γai∂/∂tiD_a = \sum_{i \in \Gamma} a_i \, \partial / \partial t_i, and the direction of a pair pp is the indicator vector ep∈ℝΓe_p \in \mathbb{R}^\Gamma of {xp,yp}\{x_p, y_p\}.✦ For A⊆ΓA \subseteq \Gamma and a polynomial GG, [tA]G[t^A]\, G is the coefficient of ∏i∈Ati\prod_{i \in A} t_i in GG.

The slot total of ff over a list QQ of pairs at a set A⊆ΓA \subseteq \Gamma is the coefficient of tAt^A in the derivative of FfF_f along the directions of all pairs of QQ: zAQ(f)=[tA]∏p∈QDepFf.z^Q_A(f) = [t^A] \prod_{p \in Q} D_{e_p} F_f .(2)✦ The slot total of ff over all of PP at the empty set is c0=z∅P(f)c_0 = z^P_\emptyset(f).

For pairs pp and rr of PP, the defect total of type (p,r)(p,r) at AA is the slot total over the list PP with pp and rr removed, taken at AA with both elements of rr added; its value at the empty set is cprc_{pr}: cpr(A)=zA∪{xr,yr}P\{p,r}(f),cpr=cpr(∅).c_{pr}(A) = z^{P \setminus \{p, r\}}_{A \cup \{x_r, y_r\}}(f), \qquad c_{pr} = c_{pr}(\emptyset).(3)✦

The Claim

Definition 1. Let MM be a matroid with rank function rk\mathrm{rk}, let nn be a natural number and let qq be a real number. The rank weight of a set SS is the real number fq(S)=qmax⁡{n−rk(S),0}.f_q(S) = q^{\max\{n - \mathrm{rk}(S),\, 0\}}.(4)✦ A plain state of PP is a set S⊆ΓS \subseteq \Gamma in which every pair of PP is single; Ω0\Omega_0 is the set of plain states.✦ For distinct pairs pp and rr of PP, a defect state of type (p,r)(p,r) is a set S⊆ΓS \subseteq \Gamma in which pp is empty, rr is full and every other pair of PP is single; Ωpr\Omega_{pr} is the set of defect states of type (p,r)(p,r).✦ A chain state of PP is a plain state or a defect state of some type, and the set of chain states is Ω=Ω0∪⋃p≠rΩpr,\Omega = \Omega_0 \cup \bigcup_{p \neq r} \Omega_{pr},(5)✦ the union running over all ordered choices of distinct pp and rr in PP. If the pairs of PP are disjoint two-element sets whose union is Γ\Gamma, then for every real function ff on the subsets of Γ\Gamma and all distinct pairs pp and rr of PP, c0=∑S∈Ω0f(S),c_0 = \sum_{S \in \Omega_0} f(S),(6)✦ cpr=∑S∈Ωprf(S).c_{pr} = \sum_{S \in \Omega_{pr}} f(S).(7)✦

In the paper, the result reads: fq(S)=qd(S)f_q(S) = q^{d(S)} with d(S)=n−rkK(S)d(S) = n - \mathrm{rk}_K(S), Ω0\Omega_0 is the set of transversals of the pairs, Ωij\Omega_{ij} is the set of nn-element sets with pair ii empty, pair jj full and every other pair single, and cT(q)=∑S∈ΩTfq(S)c_T(q) = \sum_{S \in \Omega_T} f_q(S) for each of these sets ΩT\Omega_T, where KK is the page’s MM and Ωij\Omega_{ij} its Ωpr\Omega_{pr}.

What Is Checked

The definitions (4) and (5) and the identities (6) and (7) are stated over the rank function of a matroid, a list of pairs of elements of a finite set Γ\Gamma, the ways a pair can be empty, single or full in a set, the derivatives of the multiaffine polynomial (1) along the indicator vectors of pairs, and the hypothesis that the pairs are disjoint two-element sets whose union is Γ\Gamma.