An FPRAS for counting common bases of two matroids

Theorem 1.1: one randomized oracle algorithm, given independence oracles for rank- $r$ matroids on $[n]$ and rational $\varepsilon,\delta\in(0,1)$ , outputs $\widehat Z$ within relative error $\varepsilon$ of the number of common bases with probability at least $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.

Exact FrontierDelta

Prior state unknown→proved

Scope and record

Occurred: Sep 23, 2026

Delta type: SOURCE CLAIM

Assumptions: VibeMathed verification: lean-checked. Publication: announcement. AI contribution: ai-discovered. VibeMathed editorial classifications, scores, notes, relations, and dataset structure are CC BY 4.0. Source statements and linked content retain their own rights.

Canonical aliases: An FPRAS for counting common bases of two matroids · Counting common bases of two matroids

Confidence: Not scored

Registry verification: lean checked · announcement · candidate

Open the source record ↗

Attribution

VibeMathed
registry · event recorded by

Unreleased internal OpenAI model
model · ai model contributor · OpenAI

Evidence vector

SourceReplayReproducedFormal proofStatement auditExternal checkExpert reviewPeer review

Named evidence

VibeMathed record: An FPRAS for counting common bases of two matroids

specialist registry · passed

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 $B$ in $n$ , the binary input length, $\lceil\varepsilon^{-1}\rceil$ and $\log\delta^{-1}$ such that, for all equal-rank matroids on $\mathrm{Fin}\,n$ with exact independence oracles, every run halts within $B$ oracle calls and bit operations, outputs zero when the count is zero, and at least a $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.