Approximate counting of common bases of two matroids
From OpenAI Aftermath
Approximate counting of common bases of two matroids asks for a fully polynomial randomized approximation scheme (FPRAS) for the number of common bases of two matroids on the same ground set when the matroids are given only by independence oracles. The manuscript discussed below cites the question as Problem 1 in Section 13.2 of K. Liu's 2023 dissertation. A manuscript in OpenAI's public mathematics collection (github.com/openai/math), dated 23 September 2026, claims such a scheme, and a companion manuscript dated 5 October 2026 claims the analogous scheme for common integer bases of two integral polymatroids with binary-encoded capacities. The collection includes a Lean formalization of the matroid theorem. This page summarizes the published claims and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper, code or a formal proof is not presented here as independent verification.
Background
- As recounted in the introduction of the September manuscript:
- Matroid intersection has a deterministic polynomial-time optimization algorithm in the independence-oracle model (Edmonds). Counting common bases includes counting the bases of one matroid and counting perfect matchings in bipartite graphs, for which Jerrum, Sinclair and Vigoda gave an FPRAS through the permanent of a nonnegative matrix.
- For a single matroid, Feder and Mihail treated balanced matroids, Anari, Oveis Gharan and Rezaei proved rapid mixing for homogeneous strongly Rayleigh distributions, and Anari, Liu, Oveis Gharan and Vinzant obtained an independence-oracle FPRAS for every matroid through log-concave polynomials.
- For intersections, earlier results gave coarser approximations or needed additional algebraic information: Barvinok and Samorodnitsky, Anari and Oveis Gharan, Straszak and Vishnoi, and a deterministic 2O(r)-factor approximation of Anari, Oveis Gharan and Vinzant, which becomes fully polynomial only when the rank r is O(log n). Cryan, Guo and Mousa asked for a rapidly mixing Markov chain for common bases or common independent sets.
The original results
- Claim. Theorem 1.1 of Approximate counting of common bases of two matroids states that a single randomized oracle algorithm, given independence oracles for arbitrary rank-r matroids M1 and M2 on {1, …, n} and rational ε, δ in (0, 1), outputs a nonnegative rational within relative error ε of the number of common bases with probability at least 1 − δ, always outputs zero when there is no common basis, and on every execution uses a number of oracle calls and other bit operations bounded by a fixed polynomial in n, the encoding length, 1/ε and log 1/δ. The manuscript derives an FPRAS and an almost-uniform sampler for common independent sets of prescribed, unrestricted or maximum cardinality, also when the two ranks differ. The companion An FPRAS for Common Integer Polymatroid Bases with Binary Capacities states such a scheme for the common integer bases of two integral polymatroids of equal total rank given by exact rank-value oracles, with the total rank and the capacities encoded in binary and without expanding the capacities into labelled copies.
- Method, as described: a common basis is encoded as a basis of a rank-n matroid on 2n elements that chooses one element from each of n prescribed pairs. Sets of rank deficiency d receive weight qd, with q decreasing from 1 to an exponentially small rational. The chain also visits states with one empty and one doubly occupied pair, whose total weights are balanced by learned multipliers, following the permanent algorithm of Jerrum, Sinclair and Vigoda. The algebraic input is the homogeneous Tutte theorem of Brändén and Huh, which gives inequalities between defect totals and a transport inequality between conditional distributions; rapid mixing is proved for the trace of the chain on transversals, together with a separate variance bound for the observables the algorithm averages.
- Sources. The manuscripts Approximate counting of common bases of two matroids and An FPRAS for Common Integer Polymatroid Bases with Binary Capacities at commit
1581d4c. - Formalization, as described by the repository. The scope note lists only the September manuscript. It states that the formalized result gives an FPRAS for the number of common bases of two equal-rank matroids on an enumerated finite ground set, using independence oracles, with a zero count producing zero on every execution and with polynomial bounds on oracle calls and bit operations on every random tape. The Comparator statement is
CommonBasesFPRAS.lean.
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 20 October 2026) |
|---|---|---|---|---|
| 2026-10-05 | X. Chen and K. Liu, An FPRAS for Counting Common Bases of Two Matroids, arXiv:2610.06724v1 | Parallel work | The abstract states the first polynomial-time algorithms for approximately counting and almost uniformly sampling common bases of two matroids given by independence oracles, and an extension to Hadamard products of two probability measures on the Boolean cube satisfying a nonnegative curvature condition. The method imposes an overlap penalty on the product measure, a "soft intersection" for which a Poincaré inequality uniform over all external fields is proved by an integrated Bochner-type method, and computes the external fields from a dual maximum-entropy convex program. Version 1 does not mention the OpenAI manuscripts. | arXiv preprint, version 1 of 5 October 2026. The paper states that GPT-5.6 Sol Ultra and GPT-6 Astra Ultra were heavily used to develop its ideas. |
| 2026-10-07 (manuscript date) | R. Gounder, Mathematical Frontiers in the OpenAI Research Release (GitHub) | Comparative review | Includes a case study of the September manuscript. It summarizes the paired reduction, the Brändén–Huh quadratic signatures, the transport lemma and the trace and warm-start control, and gives the four edges of K2,2 as an example: the generating polynomial x1x4 + x2x3 of the common bases of its two vertex-partition matroids has Hessian eigenvalues 1, 1, −1, −1, a structural obstruction to the single-matroid framework rather than a hardness result. It notes that the scope note covers the independence-oracle matroid theorem and not the polymatroid extension, and it compares the work with Chen and Liu's preprint, stating that manuscript dates alone do not establish priority. | A 25-page review. The README states that its checks "do not independently establish the underlying release theorems". |
| 2026-10-07 | R. Gounder, Kohze/counting-and-sampling-review, Approximate Counting and Uniform Sampling: A Critical Review of Matroid Intersections, Contingency Tables, and Graph Switch Chains | Review (narrative) | A narrative review of six counting and sampling manuscripts of the collection, including the two matroid and polymatroid manuscripts, relating their stated guarantees to the earlier literature through reductions, worked probability laws and accuracy and runtime models. | GitHub repository with a manuscript; its LaTeX source includes a dedicated AI disclosure. |
| 2026-10-08 | MathVet (GitHub; review of openai/math, tables at repository commit c76f1e4, 14 October 2026) |
Review (fidelity of the formal statements) | Rates this family "partial": the matroid special case, with independence oracles and equal ranks, is stated, while the integer-polymatroid scheme with binary capacities and rank-value oracles and the variants for common independent sets are not. Among the definitions it lists for checking is a hand-built oracle register machine. It records a sandboxed Comparator pass for CommonBasesFPRAS. |
MathVet states that it does not claim any theorem false and reports what was machine-checked as stated. |
| 2026-10-10 | cert-machine, openai/math lane K, run 38051470892 | Verification (two kernels) | Records that Lean's default kernel and the nanoda kernel accept the CommonBasesFPRAS solution (369 s). The project reports two-kernel certification of 398 of 416 challenges of the collection. |
Repository. |
| 2026-10-10 to 2026-10-14 | con-leche development journal (task #348) | Verification (second kernel) | In its run over all Comparator challenges of the collection at commit fd4aeeb, the journal's table of exceptions (time-outs, memory, errors) does not list CommonBasesFPRAS, so the challenge was accepted by con-leche and by Lean's official kernel. |
Development journal. |
| 2026-10-16 | J. Jardine, Lattice24, referee review of the polymatroid manuscript in JJardine919/openai-math-audit (archived at Zenodo 10.5281/zenodo.23422995) | Review (AI-assisted audit) | Reports no gap. The reviewer states that it read every section in full and checked the polyhedral, signature, scaling, port, evaluation and annealing estimates by hand. Its one minor note is that the transport, observable-variance and trace-mixing estimates are imported from a companion manuscript of the collection on contingency tables with cell bounds rather than reproved, so that the proof is correct only if that companion is; the interface hypotheses are verified in the paper and the constants match. | Part of an audit of the collection's manuscripts that the audit describes as complete. The reviews are published under CC BY 4.0. |
Notes
- K. Liu, whose dissertation records the question, is a coauthor of the parallel arXiv preprint listed above.
- The earlier counting and sampling results are due to the authors named in the Background section, as recounted by the manuscript.
- The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.
