OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction · §1

Matroids, independence oracles and the common-basis count: An exact independence oracle OO for matroids M1,M2M_1, M_2, their number ZZ of common bases, and an estimate zz of relative accuracy ε\varepsilon

The input and the target of counting common bases.

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 two matroids M1M_1 and M2M_2 on the same ground set [n][n] of nn elements, and ask how many subsets of [n][n] are a basis of both. The perfect matchings of a bipartite graph with no isolated vertex are an instance: they are the common bases of two partition matroids on its edges, in the first of which a set of edges is independent when it meets each left vertex at most once, in the second when it meets each right vertex at most once.

The matroids are not listed. An algorithm sees them only through independence queries, and from the answers it is to estimate the number of common bases within a prescribed relative error ε\varepsilon, as a fully polynomial randomized approximation scheme for the count does. The definitions below fix that input and that target.

The Definition

Subsets of [n][n] are queried as bit vectors: with 𝔹={𝖿𝖺𝗅𝗌𝖾,𝗍𝗋𝗎𝖾}\mathbb{B} = \{\mathsf{false}, \mathsf{true}\}, a vector A∈𝔹nA \in \mathbb{B}^n marks the set SA={i∈[n]:Ai=𝗍𝗋𝗎𝖾}S_A = \{i \in [n] : A_i = \mathsf{true}\}. For a matroid MM with ground set [n][n], ℐ(M)\mathcal{I}(M) is its family of independent sets.

Definition 1. Let M1M_1 and M2M_2 be matroids with ground set [n][n].

An independence oracle on [n][n] is a function that assigns a bit to each pair of a selector b∈𝔹b \in \mathbb{B} and a bit vector A∈𝔹nA \in \mathbb{B}^n: O:𝔹×𝔹n→𝔹.O \colon \mathbb{B} \times \mathbb{B}^n \to \mathbb{B}.(1)✦

An independence oracle OO on [n][n] is exact for M1M_1 and M2M_2 when, for every A∈𝔹nA \in \mathbb{B}^n, O(𝖿𝖺𝗅𝗌𝖾,A)=𝗍𝗋𝗎𝖾⇔SA∈ℐ(M1)andO(𝗍𝗋𝗎𝖾,A)=𝗍𝗋𝗎𝖾⇔SA∈ℐ(M2).O(\mathsf{false}, A) = \mathsf{true} \iff S_A \in \mathcal{I}(M_1) \qquad\text{and}\qquad O(\mathsf{true}, A) = \mathsf{true} \iff S_A \in \mathcal{I}(M_2).(2)✦

The number Z(M1,M2)Z(M_1, M_2) of common bases of M1M_1 and M2M_2 is Z(M1,M2)=|{X⊆[n]:X is a basis of M1 and a basis of M2}|.Z(M_1, M_2) = \bigl|\{X \subseteq [n] : X \text{ is a basis of } M_1 \text{ and a basis of } M_2\}\bigr|.(3)✦

For rational numbers ε\varepsilon and zz and a natural number ZZ, the estimate zz has relative accuracy ε\varepsilon for ZZ when (1−ε)Z≤z≤(1+ε)Z.(1-\varepsilon)\, Z \le z \le (1+\varepsilon)\, Z.(4)✦

In the paper, the result reads: M1M_1 and M2M_2 are matroids of the same rank rr on [n][n], given by exact independence oracles that answer nn-bit subset queries, and Z(M1,M2)=|ℬ(M1)∩ℬ(M2)|Z(M_1, M_2) = |\mathcal{B}(M_1) \cap \mathcal{B}(M_2)|, where ℬ(M)\mathcal{B}(M) is the set of bases of MM.

What Is Checked

The definitions are stated over two matroids M1M_1 and M2M_2 with ground set [n][n], an independence oracle OO on [n][n] as in (1), and, in (4), rational numbers ε\varepsilon and zz with a natural number ZZ.