Documentary state: DRAFT_UNACCEPTED. This draft has NOT been editorially admitted. Mathematical claims require independent checking.
OAI-26 family 114: approximate counting of common polymatroid bases
Editorial status: DRAFT_UNACCEPTED. NO_CERTIFICATION. This article documents source-pinned publisher claims, not independently verified proofs of randomized approximation schemes.
The question in plain language
A matroid describes which subsets of a finite ground set count as independent, generalizing independence in vector spaces and forests in graphs. Two matroids on the same ground set may impose different independence constraints. Counting the subsets satisfying both can be much harder than finding just one.
An integral polymatroid is a related structure with nonnegative integer vectors instead of only zero-or-one subsets. Family 114 claims efficient randomized approximation schemes for counting vectors that are bases of two integral polymatroids, even when their capacities are written in binary.
A small example
Suppose three kinds of resource can be selected in integer quantities \(x_1,x_2,x_3\). One polymatroid limits the aggregate amount available to each subset of resources; a second represents independent constraints. A common integer base satisfies both families of upper bounds and reaches each total-rank equality.
Counting means counting each admissible integer vector once, regardless of how many exchanges or descriptions produce it. A binary-encoded capacity such as \(2^{100}\) uses only about a hundred input bits; an algorithm that takes time polynomial in the numerical value of that capacity is therefore not polynomial in the encoded input length.
What is known
The protected Family 114 catalogue lists two manuscripts: An FPRAS for Common Integer Polymatroid Bases with Binary Capacities and Approximate counting of common bases of two matroids.
The pinned publisher overview claims a fully polynomial randomized approximation scheme (FPRAS) for the number of common integer bases of two integral polymatroids with equal total rank, accessed through exact rank-value oracles. The capacities are binary-encoded. The overview further specifies that both oracle-call counts and bit operations outside the oracles are polynomial on every execution, rather than only in expectation.
An FPRAS for a nonzero counting quantity \(Z\) normally returns an estimate within multiplicative factors \(1\pm\varepsilon\), with success probability at least a fixed constant that can be amplified; running time must be polynomial in the encoded instance size and \(1/\varepsilon\). The exact zero-instance handling must be checked in the manuscript rather than inferred from this general definition.
For matroids accessed through independence oracles, the publisher overview also claims approximate counts of common independent sets of specified size, unrestricted size, and maximum possible size, even if the two matroid ranks differ. This is a distinct input and oracle model from integer polymatroid bases; the equal-total-rank condition must not be accidentally imposed on the matroid corollaries.
GCL verification state
Source lock: openai/math@1581d4cbdd69a0faf34b2089614fe2a814316a6a. Both manuscript paths are present in the protected catalogue. The pinned overview identifies the claimed oracle models, capacity encoding, rank constraints, counting units, and worst-case per-execution computational guarantees.
This editorial pass has not checked the sampling or counting reductions, total-rank equalization, polynomial oracle simulation, handling of zero counts, success probability, or bit-complexity accounting. No Family 114-specific independent proof audit, reproducible randomized experiment, Comparator result, or MATHCERT certificate is asserted.
What remains
Read both pinned PDFs and extract the exact approximation, success-probability and running-time statements. Verify that the ground set, capacities and rank values are encoded as specified, that oracle responses are exact and that the algorithm's costs exclude no unreported expensive subroutines. Check polynomial bounds on every execution and determine how oracle call and non-oracle bit costs are counted.
Audit the reduction from common integer polymatroid bases to common matroid independent-set counts, particularly the prescribed/unrestricted/maximum-cardinality cases and unequal matroid ranks. Establish whether the algorithm handles zero-count instances, and check that multiplicities from auxiliary encodings do not violate the “each integer vector once” requirement.
Complete mathematical Markdown and MkDocs regression, source-critical review, and protected merge/readback. Documentary admission does not certify the claimed FPRAS.
Sources and claim boundaries
- Pinned integer polymatroid FPRAS manuscript.
- Pinned common matroid bases manuscript.
- Pinned OAI-26 overview, Family 114.
- GCL editorial assignment.
Boundary: NO_CERTIFICATION. These approximation claims remain publisher-reported pending independent mathematical verification.
Indexed primary manuscript paths:
- An FPRAS for Common Integer Polymatroid Bases with Binary Capacities —
preprints/An-FPRAS-for-Common-Integer-Polymatroid-Bases-with-Binary-Capacities-October-5-2026/polymatroid-fpras.pdf - Approximate counting of common bases of two matroids —
preprints/Approximate-counting-of-common-bases-of-two-matroids-September-23-2026/main.pdf