we-solve (beta)

CS-124 · computer science · mathematics · Algorithms and data structures · Graph theory and combinatorics

FPRAS for common matroid bases

Status OpenLLM status Open unverified

Statement

Definitions and mathematical statement

Statement recorded in the supplied source.
Given only independence oracles for any two equal-rank matroids on n labeled elements, can one estimate their number of common bases to relative error $\varepsilon $ with failure $\delta $ using polynomially many oracle calls and other bit operations in n, parameter encoding length, $\varepsilon ^{-1}$ and $\log (\delta ^{-1})$, with certain zero output when none exist?

Short English statement

Given only independence oracles for any two equal-rank matroids on n labeled elements, can one estimate their number of common bases to relative error $\varepsilon $ with failure $\delta $ using polynomially many oracle calls and other bit operations in n, parameter encoding length, $\varepsilon ^{-1}$ and $\log (\delta ^{-1})$, with certain zero output when none exist?

Sources

Statement licence: CC-BY-4.0 · Source file

Contributions 1

CS-124-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for CS-124

The result supplies the conclusion in this problem with its displayed hypotheses and quantifiers. The broader statements and applications in the manuscript are kept separate from the particular question above. The supporting result is manuscript 1 (family 114; 2026-09-23).

FPRAS for common matroid bases

OpenAI's claim

OpenAI presents the following claims relevant to this question, with manuscript numbers following paper order in Sources. In manuscript 1 (family 114; 2026-09-23), the asserted result is that two arbitrary equal-rank matroids supplied by independence oracles admit an FPRAS for their common bases, with polynomial work on every execution.

Mathematical statement of the claimed result

Manuscript 1.
For arbitrary rank-$r$ matroids $M_1,M_2$ on $[n]$, supplied only by independence oracles, let $Z$ count subsets that are bases of both. Given rational $\varepsilon,\delta\in(0,1)$, the claimed uniform oracle algorithm returns $\widehat Z\in\mathbb Q_{\ge0}$ with \[ \Pr[(1-\varepsilon)Z\le\widehat Z\le(1+\varepsilon)Z]\ge1-\delta. \] When there is no common base it always outputs zero. One polynomial bounds both the number of oracle queries and the bit time, on all executions, as a function of $n$, encoding length $\ell$ of $n,r,\varepsilon,\delta$, $\varepsilon^{-1}$ and $\log\delta^{-1}$. No linear representation or special matroid class is assumed.

Outline of the argument

For manuscript 1 (family 114; 2026-09-23), a paired-ground-set construction represents common bases as transversals of an auxiliary matroid. Quadratic signature inequalities compare defect classes and yield a transport bound, after which annealing learns multipliers and warm restarts estimate the partition ratios.

Formal verification

For manuscript 1 (family 114; 2026-09-23), OpenAI lists Lean statements for this assertion: two arbitrary equal-rank matroids supplied by independence oracles admit an FPRAS for their common bases, with polynomial work on every execution.

The selected statement includes the clause used for this problem.

The linked family Comparator checks are CommonBasesFPRAS.lean.

Their named declarations include OAI.common_bases_fpras.

This site has not executed the Lean code. Described statement coverage is not an independent proof check.

Status caveat

The manuscripts were produced by an internal OpenAI model. OpenAI cautions that results without formalization can contain mistakes. This site has not independently checked the proofs; the label records the scope of OpenAI's claim.

Sources

Go to contribution →