1 · The essentials
The task is to count how many whole-number choices satisfy two sets of mathematical constraints at once. The main manuscript considers choices that reach the same required total under both sets of constraints. It describes a randomized algorithm that estimates the count, with a chosen relative-error tolerance and a chosen bound on the chance of failure. Large limits are written in binary and handled directly, rather than expanded into individually labelled copies. Each distinct whole-number choice counts once. On every run, the number of requests for constraint information and the computation outside those requests have polynomial bounds in the stated input and accuracy parameters. A companion result for counting common bases of two equal-rank matroids has a Lean formalization; the supplied source does not identify the broader polymatroid result as formalized.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine counting whole-number packing lists that must satisfy two different rulebooks and reach the same required total. A list specifying several identical items is counted once, rather than separately for every way of labelling those items. This captures the counting convention, but arbitrary packing rulebooks need not satisfy the mathematical assumptions of the result.
Why it matters
The result addresses approximate counting when capacities may be large but have compact binary descriptions. Handling those capacities without expanding them into labelled copies preserves both the intended counting convention and the stated polynomial resource bounds. The oracle model also makes explicit which information the algorithm needs and which computational costs are bounded.
2 · Going further
The main problem is to count common integer bases of two integral polymatroids on a ground set, assuming that both have the same total rank. The polymatroids are supplied through exact rank-value oracles. Total rank and capacities are binary-encoded, and the objects being counted are distinct integer vectors, each with weight one—not labelled realizations of those vectors.
The main manuscript describes a fully polynomial randomized approximation scheme, or FPRAS. Its oracle-call count and bit work outside the oracles are bounded on every execution by a fixed polynomial in the ground-set size, binary input length, inverse relative-error tolerance , and logarithm of inverse failure probability . The abstracts identify direct treatment of binary capacities, without expansion into labelled copies, as an important feature. They do not describe the internal sampling method or the argument establishing its guarantees, so no more detailed mechanism can be extracted from this source.
The Lean-formalized companion addresses common bases of two arbitrary matroids of equal rank, supplied by independence oracles. It requires no explicit representation of either matroid and gives polynomial bounds on oracle calls and bit operations on every execution. The repository summary additionally reports results for common independent sets of prescribed, unrestricted, or maximum cardinality, including matroids with unequal ranks; the supplied formalization description does not explicitly cover these extensions.
Useful notions
- Whole-number vectors and counting
- Binary encoding and input length
- Randomized approximation and relative error
- Matroids and polymatroids
- Oracle access and polynomial resource bounds
What was known before / what is new
Before
The supplied source gives no account of earlier algorithms, historical milestones, or previously open problems. It presents two related manuscripts, distinguishing the broader integer-polymatroid setting from the equal-rank matroid setting.
New
The main manuscript reports an FPRAS for common integer polymatroid bases with binary capacities and exact rank-value oracle access. It handles capacities directly and counts each integer vector once, with polynomial bounds on oracle calls and external bit work on every execution. The companion supplies a Lean-formalized result for common bases of equal-rank matroids accessed through independence oracles.
Limits and assumptions
The polymatroid result assumes integrality, equal total rank, and exact rank-value oracles; rank and capacities are binary-encoded. Its computation bound covers oracle calls and bit operations outside the oracles, not the internal cost of answering an oracle query. Polynomial bounds hold on every execution, while the approximation guarantee allows a specified failure probability. The identified Lean formalization concerns the equal-rank matroid common-base result, not explicitly the full polymatroid statement or the independent-set extensions. The source states no remaining open problem and provides no details of the internal argument.
Mini glossary
- Common integer base —
- An integer vector that is a base of each of the two polymatroids and is counted once.
- FPRAS —
- A fully polynomial randomized approximation scheme estimates a count with a specified relative-error tolerance and failure-probability bound under polynomial resource guarantees.
- Exact rank-value oracle —
- An information interface that returns exact rank values for the polymatroid.
- Independence oracle —
- An information interface through which an algorithm tests independence in a matroid.
- Binary encoding —
- Representation of numerical quantities in binary, whose description length is a parameter in the stated resource bounds.
Keywords : Approximate counting · Integer polymatroids · Matroid common bases
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
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.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
An FPRAS for Common Integer Polymatroid Bases with Binary Capacities
05/10/2026We 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/09/2026We 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.