oai-math-revised beta

Browse › Theoretical computer science › 114 Approximate counting of common integer polymatroid bases

Approximate counting of common bases of two matroids

OpenAI · September 23, 2026

Lean

Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion

Edit NOTES.md · Existing issues · Source on GitHub

Abstract

We give a fully polynomial randomized approximation scheme for counting the common bases of two arbitrary matroids of the same rank, supplied by independence oracles. The algorithm requires no explicit representation of either matroid and has polynomial bounds on both oracle calls and bit operations on every execution.

If the PDF does not display here, open it directly: Open PDF.

Notes

No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.

Automatically collected notes (unreviewed)

work in progress

Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.

Follow-up works

  • gavenren (GitHub), Attempt: TOP-30007447 (We-Solve/research issue #129, 2026-10-18). A partial result giving an exact reduction and an FPRAS for two partition matroids whose nonloop blocks all have capacity one; it cites this paper's general claim as context and says the claim was not audited. [AI-generated per source]

Formalization

  • OpenAI math release, Lean scope notes for family 114 (lean/docs/114.md). Describes the formalized statement: an FPRAS for common bases of two equal-rank independence-oracle matroids, with polynomial bounds on every random tape and zero output for a zero count, with the comparator statement in CommonBasesFPRAS.lean. [family-level]
  • OpenAI, CommonBases.lean (openai/math, lean/OAI/Combinatorics/MatroidCounting). The release's Lean development for this theorem, about 26,000 lines.

Possibly relevant literature (found by the agent, not checked)

  • Xiaoyu Chen and Kuikui Liu, An FPRAS for Counting Common Bases of Two Matroids (arXiv:2610.06724, 2026-10-05). An independent paper claiming the same main result via a "soft intersection" with an overlap penalty, a Poincaré inequality and a dual maximum-entropy program, with stated running time $\widetilde O(n^{13}/\varepsilon^2)$. It does not cite the OpenAI release and says GPT models "were heavily used to develop the ideas in this paper."

Digests and expositions

News and blogs

Elsewhere

Independent sites; their content is not reviewed here.

Cite

@misc{OAI:Approximate-counting-of-common-bases-of-two-matroids-September-23-2026,
  author = {{OpenAI}},
  title = {{Approximate counting of common bases of two matroids}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Approximate-counting-of-common-bases-of-two-matroids-September-23-2026/main.pdf}{OAI:Approximate-counting-of-common-bases-of-two-matroids-September-23-2026}},
  year = {2026}
}

Lean formalization

OpenAI provides Lean files for this family: lean/docs/114.md. The Lean statements have not been checked by people against the paper's claims.

Family 114: Approximate counting of common integer polymatroid bases

Gives a fully polynomial randomized approximation scheme for counting common integer bases of two integral polymatroids of equal total rank, supplied by exact rank-value oracles. Capacities are binary-encoded, each integer vector counts once, and oracle calls and bit operations outside the oracles are polynomial on every execution. For matroids presented by independence oracles, the results also cover common independent sets of prescribed, unrestricted, or maximum cardinality, even when the ranks differ.

Other papers in this family: