Plectis Atlas
Search

↑ and ↓ move, Enter opens, Esc closes.

Show on the map

Approximate counting of common integer polymatroid bases

OpenAI groups related papers into a “family”. OpenAI’s catalogue describes this one:

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. (OpenAI’s Lean note)

Lean is a language for mathematical statements and proofs that a computer can verify. The assessments below ask whether those statements express the result OpenAI describes here.

The independent assessments find that the Lean statements express only part of the result described above, or a narrower statement. Read the assessments

What the papers state

Theorem 1.1

In Approximate counting of common bases of two matroids, 23 September 2026

Possible match to OpenAI’s description, selected from the papers’ main statements because it shares the most wording. No review confirming the selection is recorded.

There is a single randomized oracle algorithm with the following guarantee. Given independence oracles for arbitrary rank-r matroids M_1,M_2 on [n], and rational \epsilon,\delta\in(0,1), it outputs a nonnegative rational \widehat Z such that

\Prob\bigl[(1-\epsilon)Z(M_1,M_2)\le\widehat Z \le(1+\epsilon)Z(M_1,M_2)\bigr]\ge1-\delta.

If Z(M_1,M_2)=0, its output is always zero. On every execution, the number of oracle calls and the number of other bit operations are bounded by a fixed polynomial in

n,\qquad \ell,\qquad \epsilon^{-1},\qquad \log\delta^{-1},

where \ell is the binary encoding length of n,r,\epsilon,\delta. The algorithm uses only independent unbiased random bits and does not require a representation of either matroid.

Theorem 1.1

In An FPRAS for Common Integer Polymatroid Bases with Binary Capacities, 5 October 2026

The paper’s main theorem is shown as a possible match to OpenAI’s description. No review confirming the selection is recorded.

There is a single uniform randomized algorithm which, for every input described above, outputs a nonnegative rational \widehat Z satisfying

\PP\bigl((1-\eps)Z\le\widehat Z\le(1+\eps)Z\bigr) \ge1-\delta.

If Z=0, the algorithm outputs zero on every execution. On every execution, both its number of oracle calls and its number of other bit operations are bounded by one fixed polynomial in

n,\qquad \ell,\qquad \eps^{-1},\qquad \log(\delta^{-1}).

The bit-operation bound includes rational arithmetic, generation of independent unbiased random bits, and the encoding of the output.

No Lean statement in the release is paired with this theorem.

The release does not say which paper theorem its catalogue describes. Both statements above are shown whole, the closer match to the description’s wording first. The atlas has not reviewed either choice.

Reported proof verification
One Lean statement in the release; three independent groups report that Comparator accepted runs for this file at the version shown here.
Papers and explanations
Two current papers, each readable here as a page beside its PDF.

Papers

Each paper opens as a reading page in the browser, with the PDF beside it. The statements each paper opens with are on its reading page.

An FPRAS for Common Integer Polymatroid Bases with Binary Capacities

5 October 2026, current edition.

Read it herePDF

We give a fully polynomial randomized approximation scheme for counting common integer bases of two polymatroids with the same total rank, supplied by exact rank-value oracles. The total rank and capacities are encoded in binary, and each integer vector is counted once. On every execution, the number of oracle calls and the bit work outside the oracles are bounded by a fixed polynomial in the ground-set size, the binary input length, the inverse relative-error tolerance, and the logarithm of the inverse failure probability. The algorithm handles binary capacities directly, without expanding them into labelled copies.

Approximate counting of common bases of two matroids

23 September 2026, current edition.

Read it herePDF

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.

One Lean statement in this family

Lean is a language for mathematical statements and proofs that a computer can verify. The Lean statement below is shown beside its possible paper counterpart, with the reason they were linked.

For a configured theorem, the Comparator program tests whether OpenAI’s separate proof proves the exact Lean statement using only the allowed axioms. Some statement files instead configure definitions for comparison by name and type. Acceptance does not establish that a formal statement means the same thing as the paper’s theorem.

CommonBasesFPRAS

The paper states

Theorem 1.1

In Approximate counting of common bases of two matroids, 23 September 2026

There is a single randomized oracle algorithm with the following guarantee. Given independence oracles for arbitrary rank-r matroids M_1,M_2 on [n], and rational \epsilon,\delta\in(0,1), it outputs a nonnegative rational \widehat Z such that

\Prob\bigl[(1-\epsilon)Z(M_1,M_2)\le\widehat Z \le(1+\epsilon)Z(M_1,M_2)\bigr]\ge1-\delta.

If Z(M_1,M_2)=0, its output is always zero. On every execution, the number of oracle calls and the number of other bit operations are bounded by a fixed polynomial in

n,\qquad \ell,\qquad \epsilon^{-1},\qquad \log\delta^{-1},

where \ell is the binary encoding length of n,r,\epsilon,\delta. The algorithm uses only independent unbiased random bits and does not require a representation of either matroid.

The words they share: independence, zero, calls, matroid, oracle, random, output, binary, rank, execution, length, rational, bits, operations, bounded, bases, counting, common, prob, delta, randomized, number, nonnegative, polynomial.

Possible Lean counterpart

Selected from shared wording. No review of whether the statements mean the same thing is recorded.

FPRAS for common matroid bases

CommonBasesFPRAS.lean, the release lists it as a main result.

def MainTheorem : Prop :=  ∃ (k s : ℕ) (P : Program k s) (C d : ℕ), 0 < C ∧    ∀ (n r : ℕ) (M₁ M₂ : Matroid (Fin n)) (O : IndependenceOracle n)      (ε δ : ℚ),      M₁.E = Set.univ → M₂.E = Set.univ →      M₁.eRank = (r : ℕ∞) → M₂.eRank = (r : ℕ∞) →      ExactOracles M₁ M₂ O → 0 < ε → ε < 1 → 0 < δ → δ < 1 →      let B := resourceBound C d n r ε δ      let Z := commonBaseCount M₁ M₂      (∀ bits : ℕ → Bool,        let out := execution P O (initialConfig k s n r ε δ) bits B        out.output.isSome ∧ out.oracleCalls ≤ B ∧ out.bitOperations ≤ B ∧        ∀ z, out.output = some z → 0 ≤ z ∧ (Z = 0 → z = 0)) ∧      (1 - δ) * (2 : ℚ) ^ B ≤        (Nat.card {bits : Fin B → Bool //          ∃ z, (execution P O (initialConfig k s n r ε δ) (finiteBits bits) B).output

This file states the theorem with sorry, a placeholder, in place of its proof. OpenAI supplies a separate proof file. Comparator tests whether that proof proves the statement here.

three independent groups report that Comparator accepted runs for this Lean statement file: cert-machine; MathVet; Neal McBurnett, openai-math-lean-tooling. Who ran the proof-verification program

  • cert-machine records it as “CERTIFIED”.
  • MathVet records it as “comparator-sandboxed-pass”.
  • Neal McBurnett, openai-math-lean-tooling records it as “accepted”.

Read the complete Lean statement

Independent comparisons and proof-verification reports

Does the Lean express the advertised result?

Neither group finds that the Lean statements express or imply the whole advertised result. They describe what the statements express in different terms.

MathVet and Carlos Toledo’s cert-machine independently assessed whether this family’s Lean statements express the whole result OpenAI describes in its catalogue. These are assessments of the family as a whole, not of each paper theorem separately.

MathVet finds that the Lean statements express part of the advertised result (their term: “partial”).

Their note: Matroid special case only (independence oracles, equal ranks); the integer-polymatroid FPRAS with binary capacities and rank-value oracles, and the variants for common independent sets of other cardinalities/unequal ranks, are not stated.

Definitions the group asks readers to compare with the paper: Hand-rolled oracle register machine: Instruction = push/pop/coin/query/halt over Fin (k+8) bit-list registers with counters oracleCalls/bitOperations; a query on a register of length ≠ n silently outputs 0 and stops; ExactOracles says the oracle answers independence of the characteristic vector exactly; inputLength counts n and r in binary while the resource bound is polynomial in n itself

“partial”, in their words: Only a special case is stated, or a co-equal headline claim has no challenge statement.

Their method: An independent, model-assisted, pre-referee reading of each family’s challenge statements against its headline claim under a published rubric (PROTOCOL.md), with its own Comparator runs per challenge.

Read the original assessment Read MathVet’s method

cert-machine finds that the Lean statements express a narrower statement than the advertised result (their term: “NARROWER — UNDECLARED”).

The gap they name: The headline object (common integer bases of integral polymatroids with binary capacities and rank-value oracles) and the independent-set variants are not stated. Only the matroid common-bases FPRAS is stated (the September 23 paper; the October 5 polymatroid paper is not formalized).

“NARROWER — UNDECLARED”, in their words: The challenge statements state less than the headline, and OpenAI’s Lean note does not say so.

Their method: Every Comparator challenge re-run on Linux with nanoda switched on, decided by a preregistered rule.

Read the original assessment Read cert-machine’s method

OpenAI’s own note on what its Lean covers

The formalized result gives a fully polynomial randomized approximation scheme for the number of common bases of two equal-rank matroids on an enumerated finite ground set, using independence oracles. For rational $0<\varepsilon,\delta<1$, the nonnegative rational output has relative error at most $\varepsilon$ with probability at least $1-\delta$. A zero count produces zero on every execution. Oracle calls and bit operations have polynomial bounds on every random tape in the input size, $\varepsilon^{-1}$, and $\log(\delta^{-1})$.

AI-drafted comparisons, with no recorded human review

  • FPRAS for common matroid bases CommonBasesFPRAS

    Unreviewed AI draft: states a paper’s theorem as the paper does. States the main theorem: an FPRAS, using independence oracles, for the number of common bases of two equal-rank matroids. The integer-polymatroid version of the family’s later paper is not part of the statement.

Who ran the proof-verification program?

These groups report running Comparator with the release’s Lean statement files. For a configured theorem, it verifies OpenAI’s separate proof against the exact statement; some files instead configure definitions for comparison by name and type. Each row is the named group’s report. Atlas has not repeated the runs.

These reports do not list the software versions, proof-verification programs, axioms, time or memory in separate fields. Any such details in a report’s prose are reproduced below.

FPRAS for common matroid bases CommonBasesFPRAS

Three reports, all at the release’s recorded version.

Reported byTheir wordTheir accountDateOriginal report
cert-machine“CERTIFIED”Re-run through Comparator with the independent nanoda kernel switched on: Lean’s kernel and nanoda both accept OpenAI’s solution.10 October 2026Original report
MathVet“comparator-sandboxed-pass”Re-run through Comparator in a sandboxed virtual machine: accepted.8 October 2026Original report
Neal McBurnett, openai-math-lean-tooling“accepted”Re-run through Comparator with Lean’s kernel: accepted (the check took 79 s).10 October 2026Original report

Missing or incomplete source records

The program that collects Atlas’s source records, Statement Map, could not obtain or interpret some source material. These notes describe those limits; they do not identify mathematical errors.

  • CommonBasesFPRAS: Source contains alias/export or metaprogrammed declaration syntax; lexical absence is inconclusive.

What these papers cite in the release, and what cites them

These links come from the papers’ bibliographies. A citation records that one paper cites another; how each cited result is used has not been examined here.

Within this family

Papers elsewhere in the release that this family’s papers cite

Papers elsewhere in the release that cite this family’s papers

References outside the release

Each paper’s outside references are listed with it on its reading page, where each citation is placed. Every outside work cited in the release: References outside the release

Explain a result, compare statements or propose a correction

Atlas has no contributed explanation for this family yet. You can offer one with a GitHub account. You receive named credit and disclose any AI assistance.

Each button opens a GitHub form with this page and its source version filled in. Opening the form does not reserve the work.

Offer to write an explanationCompare the Lean statement with the paperSuggest a source attributionSuggest a change

What people have said

Commentary on this family by others, dated and credited. It is commentary, not a finding.

  • An unsigned public tier list, the OpenAI Math Tier List, classes it as a algorithm and rates its significance, if it holds up, as “Solid publication, could lead to tenure”. The page says that nothing on it is verified.

    Author not stated. Source

Questions awaiting review

Each item identifies a statement, definition or report that needs further review. Its link opens a GitHub form with the source version already recorded.

Read the Lean statement against the paper

  • An AI agent drafted an assessment of which part of the paper this Lean statement expresses. No named human review is recorded. Open the form

Identify the theorem the catalogue describes

  • Family 114 The theorem shown was selected from shared wording with OpenAI’s description. Atlas records no review confirming that it is the theorem the description means. Open the form

Address a question raised in an independent assessment

Compare the proposed paper and Lean matches

  • Family 114 Atlas records no review of whether each linked Lean statement and paper theorem mean the same thing. Open the form