Counting common matroid and integer polymatroid bases

Source and verification

This article explains family 114 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Common bases and oracle access

A matroid on a finite set $E$ specifies independent subsets closed under taking subsets and satisfying augmentation. Its rank $r(A)$ is the maximum independent-set size in $A$. Every maximal independent subset of $E$, called a basis, has the same size.

Given two rank-$r$ matroids on an explicitly enumerated ground set $[n]$, the common-base count is

$$Z=|\mathcal{B}(M_1)\cap \mathcal{B}(M_2)|.$$

An independence oracle answers whether one queried subset is independent. It does not supply a generating polynomial, a sampler, or the count. Oracle calls are charged separately from the bit operations used to write the $n$-bit queries and process their answers.

An FPRAS returns a nonnegative rational $\hat{Z}$ with relative error at most $\epsilon$ and failure probability at most $\delta$, using polynomial work in encoded input size, ${\epsilon }^{-1}$, and $\log ({\delta }^{-1})$.

Matroid companion statement

One uniform randomized independence-oracle algorithm gives an FPRAS for common bases of two arbitrary equal-rank matroids. It returns zero on every execution if the count is zero. Both oracle calls and other bit operations have fixed polynomial bounds on every random tape. (OpenAI, 2026)

🏷️ Why intersection changes the sampling problem

For a bipartite graph, use its edges as the ground set. One partition matroid permits at most one edge at each left vertex; another imposes the corresponding right-vertex constraint. Their common full-size bases are perfect matchings, after handling isolated vertices.

The common bases need not themselves be the bases of a matroid. In a four-cycle with edges $a,b,c,d$ in cyclic order, the two perfect matchings are $\{a,c\}$ and $\{b,d\}$. Replacing one edge of the first by either edge of the second never gives another perfect matching. The matroid basis-exchange axiom fails for this two-element family.

Thus a sampler for one matroid cannot simply be applied to its intersection with another. A direct chain on common bases may also require large changes to move between them.

🏷️ Paired labels and controlled defects

The companion encodes a common basis as a basis of a rank-$n$ matroid on $2n$ elements, choosing one element from each prescribed pair. Such a selection is a transversal. An arbitrary $n$-set of rank deficiency $d$ receives positive weight $q^d$, with $q$ gradually decreased from one to an exponentially small rational.

Positivity alone does not imply useful mixing. The chain enlarges the transversal states by allowing one empty pair and one doubly occupied pair. Their ordered indices define a defect type. Type-dependent multipliers balance the mass of those classes against the transversal mass, and one-element exchanges use the resulting Metropolis probabilities.

The analytic inputs are complementary quadratic inequalities obtained from a matroid and its dual. One compares defect masses; another transports conditional laws with different missing slots. The source constructs signed flows and bounds their energy. These inequalities are used as stated interfaces here, without developing the excluded algebraic theory behind them.

The resulting variance estimate controls individual transversal values and defect-type means, not arbitrary variation inside each defect class. The algorithm therefore uses the trace chain, which records successive visits to transversals, together with separate variance bounds for the type frequencies and adjacent partition ratios it actually estimates.

A warm start is a law pointwise bounded by a controlled multiple of stationarity. Fresh restarts along the annealing schedule provide such starts despite adaptive estimates of the multipliers. State weights are evaluated by rank queries; the partition sums and transport flows in the proof are not additional input oracles.

🏷️ Integer polymatroids and binary capacities

The October companion extends the object being counted. Let $r_1,r_2:2^E\to {\mathbb{Z}}_{\ge 0}$ be normalized, nondecreasing, and submodular. The last property is

$$\begin{array}{rl}& r_i(A)+r_i(B)\\ & \ge r_i(A\cup B)+r_i(A\cap B).\end{array}$$

Assume their total ranks equal $R$. A common integer base is a nonnegative integer vector $x$ satisfying

$$\begin{array}{c}x(E)=R,\\ x(A)\le r_i(A)(A\subseteq E,i=1,2),\end{array}$$

where $x(A)={\sum }_{e\in A}{x}_e$. Each vector is counted once. Unlike matroid incidence vectors, its coordinates may exceed one.

Polymatroid manuscript statement

Given exact rank-value oracles and binary-encoded $R$, there is a uniform FPRAS for this count, with polynomial bounds on oracle calls and other bit operations in $n$, the encoded data length, ${\epsilon }^{-1}$, and $\log ({\delta }^{-1})$, on every execution. Empty feasible sets return zero with certainty. If $R=0$, the unique base is the zero vector, including when $E$ is empty. (OpenAI, 2026a)

The internal computation of the rank-value oracles is excluded from the bit count, but writing queries and reading binary answers are included. No explicit list of exponentially many subset inequalities is supplied.

🏷️ Label expansion changes both size and probability

Replacing each unit of capacity by a labeled copy creates a ground set of size proportional to the numerical capacities, which can be exponential in their bit lengths. Even if expansion were affordable, an occupancy vector $x$ has multiplicity ${\prod }_e\left(\genfrac{}{}{0ex}{}{b_e}{x_e}\right)$ for groups of capacities $b_e$.

For two coordinates of capacity two and total occupancy two, the vectors are $(0,2),(1,1),(2,0)$. They should have equal mass. Labeled expansion gives multiplicities $1,4,1$, so a uniform labeled choice assigns probabilities $1/6,2/3,1/6$ instead of $1/3$ each.

The bars show the exact probabilities in this three-vector example. They are calculated from binomial coefficients, not a simulation of the research algorithm.

This discrepancy is a counting issue, not just a running-time issue. An FPRAS for labeled common bases would approximate a different weighted sum unless the multiplicities were corrected.

🏷️ Keeping small totals discrete and integrating large ranges

The polymatroid proof first tests feasibility exactly and finds a rational center of the common base polytope. Nearly tight rank inequalities define partitions of the ground set. Their part totals become discrete variables with polynomially many possible values; a coarser partition identifies the remaining directions for comparison.

An incidence graph joins overlapping parts of the two partitions. Spanning trees express dependent coordinates in terms of free variables and part totals. The proof integrates over large free ranges, with soft penalties for violated constraints, rather than listing every possible large integer coordinate.

Directional log concavity and a controlled enlargement of fixed-total slices show that the resulting weighted count is close to the original lattice count. The distinction between this comparison and the actual algorithm is essential: large expansions and subdivisions may be used in the proof, but the sampled discrete instance has polynomial size.

Integration preserves ordinary log concavity. It does not automatically imply the discrete quadratic inequalities required by the paired counting method. The source smooths the integrated weights and adds a small strictly concave quadratic correction. Bounds comparing discrete second differences with the continuous Hessian ensure the needed signatures at every annealing power.

🏷️ Two corrected weights with different roles

Each retained small variable is represented by polynomially many paired labels. Two factorially corrected weight extensions agree on transversals, where labeled multiplicities cancel exactly, but differ on defect states. One provides the omission-type quadratic inequality used for transport; the other provides the addition-type inequality used to compare defect masses. Polynomial comparison between their defect weights transfers the required estimates.

The relevant signature statement says that a symmetric matrix has at most one positive eigenvalue, counted with multiplicity. This is stronger information than ordinary log concavity of a scalar marginal. Establishing it after smoothing, integration, and extension is a main part of the new proof, rather than a closure property being assumed.

A separate convex-volume routine approximates the weights using rational computation. The annealing algorithm couples fresh approximate evaluations to its ideal transitions and caps all subroutines. Thus the running-time guarantee survives inaccurate estimates; their probability is charged to the failure budget.

The family scope page covers the earlier independence-oracle matroid FPRAS. It does not list the binary-capacity polymatroid extension as a selected comparator result. The latter also imports specific transport and factorial-lift inputs from the common-base and cell-bounded-table companions, so its proof dependencies cross family boundaries.

🏷️ Key steps and proof outlines

A trace chain uses exactly the variance estimate available

The matroid proof obtains good control on transversal observables but does not claim a full Poincaré inequality for arbitrary fluctuations within defect classes. The subsection “The trace on transversals” shows how to use that limited information correctly. Let $P$ be the enlarged reversible chain, $A$ its transversal states, $\pi$ its stationary law, and $\mu =\pi (\cdot \mid A)$. The trace transition $P_A$ records the next positive-time return to $A$. (OpenAI, 2026b)

Given $h:A\to \mathbb{R}$, extend it harmonically off $A$ by $H(x)={\mathbb{E}}_{x}h(X_{{\tau }_A})$, where ${\tau }_A$ is the first hit of $A$. Conditioning on the first transition gives $(I-P)H=0$ off $A$ and $(I-P)H=(I-P_A)h$ on $A$. Hence the Dirichlet energies satisfy

$$⟨H,(I-P)H{⟩}_{\pi }=\pi (A)⟨h,(I-P_A)h{⟩}_{\mu }.$$

Applying the established transversal variance bound to this extension gives the trace’s spectral gap. The source obtains inverse gap at most $18n^4$ with good multipliers. This method requires no control of arbitrary defect fluctuations, because harmonic extension chooses the particular defect values appropriate to each transversal observable.

Return time and warm starts are separate requirements

One trace step may involve many underlying transitions. Starting with $\mu$, expected occupation counts before the next return form a stationary measure: shifting the occupation sum by one transition replaces its initial law by its identical final law. Normalization on $A$ therefore gives expected return time $1/\pi (A)$. If the starting law is dominated by $U\mu$, the expected time is at most $U/\pi (A)$, bounded in the source by $5U{n}^2$.

This explains why both a trace gap and a warm-start condition are needed. The trace can mix quickly in its own step count while excursions are expensive from an arbitrary chosen state. Moreover, conditioning on the entire history used to estimate multipliers can concentrate the current endpoint. The algorithm therefore restarts with fresh randomness from the known initial transversal law and walks through stored annealing levels. It does not assume that a history-dependent endpoint remains warm.

For $\rho =1-1/(2n)$ and rank deficiency $d(S)\le n$, neighboring state weights obey

$$\frac{1}{2}\le {\rho }^{d(S)}\le 1.$$

Thus target laws and ideal multipliers drift by only constant factors per level. Accurate estimates preserve balance inductively. The positive weights at the final level make nonbases contribute a controlled small residual; the final product of estimated ratios approximates the desired zero-deficiency count.

Binary capacities require multiplicity correction before mixing

The polymatroid extension has an additional issue. If coordinate $x_e$ is represented by choosing $x_e$ among $b_e$ labels, its multiplicity is $\left(\genfrac{}{}{0ex}{}{b_e}{x_e}\right)$. To count occupancy vectors equally, the weight per labeled representation must be divided by the product of these multiplicities. On transversal states this correction is exact. Off transversals, there is no unique forced extension, so the source constructs two extensions suited to different quadratic inequalities. (OpenAI, 2026a)

Large coordinate ranges are integrated out before a polynomial-size paired system is formed. The resulting continuous log-concavity controls first-order shape but does not by itself imply the discrete signature needed for transport. Smoothing and a strictly concave correction supply quantitative second-derivative bounds; finite-difference estimates then transfer them to the small discrete variables. The order is therefore: geometric reduction, weight correction, signature estimates, transport, trace sampling and annealing. Merely applying the earlier matroid sampler to an exponentially expanded ground set would fail both the bit-time requirement and the intended counting measure.

See Also

• Contingency tables gives the paired factorial corrections and illustrates why binary bounds cannot be expanded directly.
• Perfect matchings separates relative approximation from coarse entropy-based counting and discusses a different enlarged sampling space for nonbipartite graphs.
• Matroid prophets uses matroid rank and contraction for feasible online selection rather than counting.

🏷️ Manuscripts and verification scope

• An FPRAS for Common Integer Polymatroid Bases with Binary Capacities — pinned manuscript and companion source.
• Approximate counting of common bases of two matroids — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The comparator covers the independence-oracle common-matroid-base FPRAS. The October binary-capacity polymatroid extension is not included in the page’s manuscript list or selected comparator statement. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. An FPRAS for Common Integer Polymatroid Bases with Binary Capacities.

🐻  OpenAI 2026b. Approximate counting of common bases of two matroids.