VibeMathedMath problems solved with AI
Sign in

An FPRAS for counting common bases of two matroids

Given independence oracles for two matroids M1,M2M_1,M_2 of the same rank rr on [n][n], estimate ∣B(M1)∩B(M2)∣|\mathcal B(M_1)\cap\mathcal B(M_2)|, the number of common bases. The problem contains counting bases of one matroid (FPRAS by Anari-Liu-Oveis Gharan-Vinzant) and counting perfect matchings of a bipartite graph (the Jerrum-Sinclair-Vigoda permanent FPRAS). For intersections only coarse or exponential-factor approximations were known, and Anari-Oveis Gharan-Vinzant's 2O(r)2^{O(r)}-factor method is fully polynomial only for r=O(log⁡n)r=O(\log n). Cryan, Guo and Mousa asked for a rapidly mixing chain sampling common bases. Is there a fully polynomial randomized approximation scheme for the number of common bases of two arbitrary matroids given by independence oracles?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Argument
Field
Approximate counting; matroids; Markov chains
Posed by
Cryan, Guo and Mousa (Ann. Probab. 2021) asked for a fast sampler; the FPRAS question is Problem 1 of Section 13.2 of Kuikui Liu's dissertation (2023)
Year posed
2021
Years open
5y
Solved
2026-09-23
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
40 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: one randomized oracle algorithm, given independence oracles for rank-rr matroids on [n][n] and rational ε,δ∈(0,1)\varepsilon,\delta\in(0,1), outputs Z^\widehat Z within relative error ε\varepsilon of the number of common bases with probability at least 1−δ1-\delta, outputs zero when there are none, and uses polynomially many oracle calls and bit operations on every execution. Corollaries give FPRASes and almost-uniform samplers for common independent sets of prescribed, unrestricted or maximum size, even for different ranks. The method is a Jerrum-Sinclair-Vigoda style annealed chain with defect states, using the homogeneous Tutte theorem of Branden-Huh (Lorentzian polynomials). It gives no exact counting and no deterministic algorithm, and does not treat three or more matroids. The October companion gives an FPRAS for common integer bases of two polymatroids with binary capacities.

What the AI did

The release README says the results were produced by an unreleased internal OpenAI model with one fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region, whose write-up was human-edited). The manuscript is authored 'OpenAI' and names no human author. A later manuscript in the family (5 October 2026) extends the method to common integer bases of two polymatroids with binary capacities and builds on this paper's transport and trace estimates.

Verification

No independent mathematician has checked this yet. Checked here: Theorem 1.1 of the principal manuscript was read against Liu's formulation. formalization.yaml lists ComparatorChallenges/CommonBasesFPRAS.json with declaration OAI.common_bases_fpras in OAI/Combinatorics/MatroidCounting/CommonBases.lean (file exists at the pinned commit). The challenge statement was read here: it fixes an explicit oracle register machine and asserts one program and polynomial BB in nn, the binary input length, ⌈ε−1⌉\lceil\varepsilon^{-1}\rceil and log⁡δ−1\log\delta^{-1} such that, for all equal-rank matroids on Fin n\mathrm{Fin}\,n with exact independence oracles, every run halts within BB oracle calls and bit operations, outputs zero when the count is zero, and at least a 1−δ1-\delta fraction of random tapes give relative error at most ε\varepsilon. That is the headline claim. Not rebuilt here. The polymatroid extension is not formalized.

Sources

Changelog1 change

Discussion