Episode 114, October 2026

Counting common bases?

A claimed fully polynomial randomized approximation scheme for the common bases of any two matroids, extended to common integer bases of two polymatroids

Covers result 114 in OpenAI’s catalog: all 2 papers. See its connections to other results and the work it cites.

Play Episode 114: Counting common bases? Two copies of a ground set in pairs, with one transversal circled.

5:52. English captions available. The video loads from YouTube when you press play.

Chapters

The claims, in plain words

Counting is harder. A fully polynomial randomized approximation scheme (FPRAS) gets within any relative error ε with probability at least 1 − δ, in time polynomial in the input size, 1/ε and log(1/δ). Anari, Liu, Oveis Gharan and Vinzant gave one for the bases of a single matroid, using log-concave polynomials; Jerrum, Sinclair and Vigoda’s permanent algorithm covers bipartite perfect matchings. For two arbitrary matroids given by independence oracles, Anari, Oveis Gharan and Vinzant gave a deterministic approximation within a factor 2^O(r), exponential in the rank r. An FPRAS for two oracle matroids was recorded as an open problem in Liu’s dissertation, and Cryan, Guo and Mousa asked for a rapidly mixing chain.

Result 114 is two OpenAI preprints. The first, 26 pages, dated September 23, 2026, claims an FPRAS for the number of common bases of any two matroids of the same rank, given by independence oracles: on every execution, the numbers of oracle calls and bit operations are polynomial in the ground-set size, the input length, 1/ε and log(1/δ), and a zero count gives zero. It also covers common independent sets of a prescribed size, of any size, or of maximum size, even when the ranks differ. The second, 42 pages, dated October 5, 2026, extends this, together with a companion contingency-table preprint, to common integer bases of two polymatroids of equal total rank given by rank-value oracles, with capacities written in binary and each integer vector counted once.

What it doesn’t claim

The count is approximate and randomized, not exact. The guarantee is in the oracle model: the matroids are accessed only through independence queries, and the bounds count both the queries and the bit operations around them. The polymatroid extension relies on a separate preprint and is not part of the Lean formalization.

Where it stands

Posted as preprints: OpenAI, 26 and 42 pages, dated September 23 and October 5, 2026
Peer reviewed: Not yet
Checked in Lean: OpenAI published a Lean proof of the matroid FPRAS, not of the polymatroid extension; we have not run the check

Last checked October 19, 2026. The preprints have not been revised. OpenAI published a Lean formalization of the matroid FPRAS with its oracle and bit bounds, a single file of 26,126 lines importing only Mathlib, matched against its comparator statement, with no unproved steps that we could find. The common-independent-set results and the polymatroid extension are not formalized. We have not run the check. Neither paper is among those OSVerify reviewed, and we have seen no expert review.

How the proof goes

Two copies of the ground set. Following Anari, Oveis Gharan and Vinzant, put the first matroid on one copy and the dual of the second on the other, K = M₁ ⊕ M₂^*. A transversal chooses one element from every pair; the transversal that takes the first copy on a set A and the second copy elsewhere is a basis of K exactly when A is a common basis.
Weights and a chain. Every transversal gets weight q^d, where d is its rank deficiency. At q = 1 the total is 2ⁿ; as q shrinks, it approaches the number of common bases. The algorithm lowers q in small steps and estimates each ratio by sampling. The chain also visits defective states, with one empty pair and one doubly occupied pair, whose total weights are balanced by learned multipliers, as in the permanent algorithm; it moves by one-element exchanges with Metropolis acceptance.
The algebraic engine. By a theorem of Brändén and Huh, for 0 < q ≤ 1 a matroid’s homogeneous multivariate Tutte polynomial is Lorentzian, so every quadratic obtained from it by derivatives and nonnegative substitutions has at most one positive eigenvalue. Applied to the paired matroid and its dual, this gives inequalities between defect totals, such as 4·c_ij·c_ji ≤ c₀², and a transport inequality comparing states that differ in which slot is missing.
From inequalities to an algorithm. The chain’s visits to transversals mix rapidly, and a separate variance bound covers the defect indicators and ratio observables. Fresh restarts along the schedule give warm starts, even though the multipliers are learned from earlier observations, and a bit-level implementation bounds the work on every execution.

The numbers in the video

A 3-by-3 bipartite graph had 3 common bases, matching its permanent; two random binary matroids of rank 4 on 9 elements shared 8 bases.
For the paired reduction, all 512 subsets of the 9-element example agreed.
The total transversal weight fell from 512 at q = 1 to 142.25, 22.24, 9.20 and 8.01 at q = 0.5, 0.1, 0.01 and 1/10,000, against 8 common bases.
The defect inequality held for every pair of the 9-element example, with largest ratios 4·c_ij·c_ji/c₀² of 0.25, 0.39 and 0.59 at q = 1, 0.3 and 0.05.
All 57 derivative Hessians for the graphic matroid of the complete graph K₄, at three values of q, had at most one positive eigenvalue.

Read the source

Approximate counting of common bases of two matroids (PDF), 26 pages.
An FPRAS for Common Integer Polymatroid Bases with Binary Capacities (PDF), 42 pages.
The Lean scope note.
The collection’s catalog, where this is result 114.

The 2 papers in this result

OpenAI groups related papers, such as alternative proofs, supporting results and consequences, into one result; we label the first paper it lists the main paper and the others companions.

An FPRAS for Common Integer Polymatroid Bases with Binary Capacities main paper
Approximate counting of common bases of two matroids companion

Transcript

Read the full script

0:00Common bases

A matroid captures the idea of independence, like forests in a graph or linearly independent vectors. Its maximal independent sets, the bases, all have the same size. Two matroids on the same ground set can share bases. When no vertex is isolated, the perfect matchings of a bipartite graph are exactly the common bases of two partition matroids, each allowing at most one edge at every vertex on one side. Edmonds showed how to find a largest common independent set in polynomial time, using only an oracle that answers whether a set is independent. In our check, a 3-by-3 bipartite graph had 3 common bases, matching its permanent, and two random binary matroids of rank 4 on 9 elements shared 8. Counting common bases is harder. For a single matroid, Anari, Liu, Oveis Gharan and Vinzant gave a fully polynomial randomized approximation scheme, or FPRAS, using log-concave polynomials. For bipartite perfect matchings, the permanent algorithm of Jerrum, Sinclair and Vigoda applies. For two arbitrary matroids given by independence oracles, Anari, Oveis Gharan and Vinzant gave a deterministic approximation within a factor exponential in the rank. An FPRAS for two matroids given by independence oracles was recorded as an open problem in Liu’s dissertation, and Cryan, Guo and Mousa asked for a rapidly mixing chain.

1:32The claims

Result 114 is two OpenAI preprints. The first, 26 pages, dated September 23, claims an FPRAS for the number of common bases of any two matroids of the same rank, given by independence oracles. With probability at least 1 − δ, the estimate is within a factor 1 ± ε, and on every execution the numbers of oracle calls and bit operations are polynomial in the ground-set size, the input length, 1/ε and log(1/δ). A zero count gives zero. It also covers common independent sets of a prescribed size, of any size, or of maximum size, even when the ranks differ. The second preprint, 42 pages, dated October 5, extends this, together with a companion contingency-table preprint, to common integer bases of two polymatroids of equal total rank given by rank oracles, with capacities written in binary and each integer vector counted once, without expanding capacities into labelled copies. OpenAI published a Lean formalization of the matroid theorem, a single file of about 26,000 lines; the polymatroid extension is not part of it. We have not run the Lean check ourselves.

2:52How the proof goes

The proof starts from a reduction of Anari, Oveis Gharan and Vinzant. Make two copies of the ground set, put the first matroid on one copy and the dual of the second on the other, and choose one element from every pair: a transversal. The transversal that takes the first copy on a set A and the second copy elsewhere is a basis of this direct sum exactly when A is a common basis. In our check, this held for all 512 subsets of a 9-element example. Every transversal gets weight q^(rank deficiency). At q = 1 the total is 2^n; as q shrinks, it approaches the number of common bases. The algorithm lowers q in small steps and estimates each ratio by sampling. The chain also visits defective states, with one empty pair and one doubly occupied pair, whose total weights are balanced by learned multipliers, as in the permanent algorithm, and it moves by one-element exchanges. In our check, the total fell from 512 to 8.01 as q went to 1/10,000, against 8 common bases. The algebraic engine is the theorem of Brändén and Huh that, for 0 < q ≤ 1, a matroid’s homogeneous multivariate Tutte polynomial is Lorentzian, so every quadratic obtained from it by derivatives and nonnegative substitutions has at most one positive eigenvalue. Applied to the paired matroid and its dual, this gives inequalities between defect totals, such as 4·c_ij·c_ji ≤ c_0², and a transport inequality comparing states that differ in which slot is missing. In our check, all 57 derivative Hessians for the graphic matroid of the complete graph K4, at 3 values of q, had at most one positive eigenvalue, and on the 9-element example the defect inequality held for every pair. These bounds control what the algorithm actually measures. The chain’s visits to transversals mix rapidly, and a separate variance bound covers the defect indicators and ratio observables. Fresh restarts along the schedule give warm starts, even though the multipliers are learned from earlier observations, and a bit-level implementation bounds the work on every execution.

5:15Where it stands

The preprints are not peer reviewed and have not been revised. The Lean formalization covers the matroid FPRAS with its oracle and bit bounds, but not the common-independent-set results or the polymatroid extension; we have not run it. Neither paper is among those OSVerify reviewed, and we have seen no expert review. If it holds, common bases of any two matroids can be counted approximately in randomized polynomial time, answering a problem left open after the single-matroid breakthrough.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.