OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

Theorem 1.1: Given independence oracles, it halts within polynomially many steps and has relative error at most ε\varepsilon on at least a 1−δ1-\delta fraction of tapes

One machine program approximately counts common bases of two matroids.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Let M1M_1 and M2M_2 be matroids of the same rank rr on the ground set [n]={0,…,n−1}[n]=\{0,\dots,n-1\}, and let ZZ be the number of their common bases, the sets A⊆[n]A\subseteq[n] that are a base of both.✦ For a bipartite graph with edge set [n][n] and rr vertices on each side, none of them isolated, the partition matroids of the two sides have the perfect matchings as their common bases, and ZZ counts them. The matroids are known only through independence oracles. A fully polynomial randomized approximation scheme (FPRAS) for ZZ takes nn, rr and rationals ε,δ∈(0,1)\varepsilon,\delta\in(0,1) and returns an estimate within a factor 1±ε1\pm\varepsilon of ZZ with probability at least 1−δ1-\delta, at a cost polynomial in nn, the length of the input, ε−1\varepsilon^{-1} and log⁡δ−1\log\delta^{-1}.

The library states that one program of an explicit oracle machine, called the frozen machine below, is such a scheme, with its oracle calls and bit operations counted step by step and its success probability taken as a fraction of tapes of fair bits. The estimator it builds is an annealing product of ratios, each estimated with a Metropolis chain on a ground set of nn pairs of elements, defined below, amplified by the median trick.

Oracles, Machines and Tapes

An independence oracle on [n][n] is a map OO that takes a bit bb and the indicator vector of a set A⊆[n]A\subseteq[n] and returns a bit.✦ An independence oracle OO on [n][n] is exact for matroids M1M_1 and M2M_2 on [n][n] when, for every A⊆[n]A\subseteq[n], O(0,A)=1O(0,A)=1 exactly when AA is independent in M1M_1, and O(1,A)=1O(1,A)=1 exactly when AA is independent in M2M_2.✦

A rational zz is a relatively ε\varepsilon-accurate estimate of ZZ when (1−ε)Z≤z≤(1+ε)Z.(1-\varepsilon)Z\le z\le(1+\varepsilon)Z.(1)✦

A program with k+8k+8 registers and s+1s+1 states assigns an instruction to each state 0,…,s0,\dots,s.✦ An instruction pushes a given bit onto a register and moves to a given state; or pops a register and moves to one of three given states according as the register was empty or the popped bit was 00 or 11; or branches on a coin; or queries the oracle with a bit bb on the contents of a register and branches on the answer; or halts.✦ Registers hold finite words of bits. A configuration of a program is a record of the contents of the registers, the current state, an output, which is a rational number or absent, and the numbers of oracle calls and of bit operations made so far.✦

A tape is a sequence β=β0β1β2⋯\beta=\beta_0\beta_1\beta_2\cdots of bits. The run of a program PP with oracle OO on β\beta from a configuration c0c_0 is the sequence c0,c1,…c_0,c_1,\dots in which ct+1c_{t+1} comes from ctc_t by one step of PP that is handed βt\beta_t as its coin.✦ On the input (n,r,ε,δ)(n,r,\varepsilon,\delta) the initial configuration is in state 00, holds the binary expansions of nn, rr and the numerators and denominators of ε\varepsilon and δ\delta in registers 00 to 55, and has the other registers empty, no output and both counts at zero.✦ A tape of length BB is a word in {0,1}B\{0,1\}^B, continued by zeros.✦

With ℓ\ell, the input length, equal to 66 plus the total number of binary digits of these six numbers✦, the size of the input is μ=1+n+ℓ+⌈ε−1⌉+⌈log⁡2⌈δ−1⌉⌉,\mu=1+n+\ell+\lceil\varepsilon^{-1}\rceil+\bigl\lceil\log_2\lceil\delta^{-1}\rceil\bigr\rceil,(2)✦ and for constants CC and dd the resource bound is B=CμdB=C\mu^d✦.

The Estimator and the Frozen Machine

The estimator works on the paired ground set V=[n]⊔[n]V=[n]\sqcup[n], in which the two copies xix_i and yiy_i of each i∈[n]i\in[n] form the pair {xi,yi}\{x_i,y_i\}.✦ A plain state is a set S⊆VS\subseteq V that contains exactly one element of each pair.✦ A defect state of type (p,q)(p,q), for distinct pairs pp and qq, is a set S⊆VS\subseteq V that contains no element of pp, both elements of qq and exactly one element of every other pair.✦

With Sx={i:xi∈S}S_x=\{i:x_i\in S\} and Sy={i:yi∈S}S_y=\{i:y_i\in S\}, the deficiency of a set S⊆VS\subseteq V is def⁡(S)=n+r−(rk⁡1(Sx)+|Sy|+rk⁡2([n]\Sy)),\operatorname{def}(S)=n+r-\bigl(\operatorname{rk}_1(S_x)+|S_y| +\operatorname{rk}_2([n]\setminus S_y)\bigr),(3)✦ cut off at zero, where rk⁡1\operatorname{rk}_1 and rk⁡2\operatorname{rk}_2 are the ranks that the greedy algorithm computes from the oracle for M1M_1 and for M2M_2.

Let ρ=1−1/(2n)\rho=1-1/(2n)✦ and L=2n(n+κ)L=2n(n+\kappa)✦, where κ\kappa is five more than the number of binary digits of the denominator of ε\varepsilon. Phase jj, for j<Lj<L, weighs a set SS by fj(S)=ρjdef⁡(S)f_j(S)=\rho^{\,j\operatorname{def}(S)}✦, and, given multipliers wpqw_{pq}, by πj(S)=wpqfj(S)\pi_j(S)=w_{pq}f_j(S) when SS is a defect state of type (p,q)(p,q) and πj(S)=fj(S)\pi_j(S)=f_j(S) otherwise✦. The lazy Metropolis chain of phase jj moves on the plain and defect states. From SS it stays put with probability 1/21/2; otherwise it picks a∈Sa\in S and a′∈V\Sa'\in V\setminus S uniformly, and when T=(S\{a})∪{a′}T=(S\setminus\{a\})\cup\{a'\} is again a state it moves to TT with probability min⁡{1,πj(T)/πj(S)}\min\{1,\pi_j(T)/\pi_j(S)\}, staying at SS otherwise.✦

The multipliers start at wpq=4w_{pq}=4. After each phase, every wpqw_{pq} is multiplied by the fraction of plain states among the states visited in that phase divided by the fraction of defect states of type (p,q)(p,q) among them.✦ Phase jj goes ahead only when every multiplier learned so far is positive. It draws a start state by a restart procedure, which begins with a uniform plain state and may fail for lack of random bits from the fair bank defined below. It then runs its chain with the multipliers learned from the earlier phases for N−1N-1 steps and records as its sample the NN states visited, where N=1014(L+1)3n14⌈ε−1⌉2+1.N=10^{14}(L+1)^3n^{14}\lceil\varepsilon^{-1}\rceil^2+1.(4)✦ The restart procedure is cut off at a cap, equal to 2000(L+1)2n2⋅20n4(n(L+1)+2)2000(L+1)^2n^2\cdot 20n^4\bigl(n(L+1)+2\bigr).

After the LL phases, let RjR_j be the average of ρdef⁡(S)\rho^{\operatorname{def}(S)}, with def\operatorname{def} as in (3), over the plain states SS in the sample of phase jj.✦ The product estimate is Z̃=2n∏j<LRj.\tilde Z=2^n\prod_{j<L}R_j.(5)✦ A last restart draws one more plain state. The run outputs Z̃\tilde Z when that state has deficiency 00, and 00 when it does not✦, when a phase does not go ahead, or when a draw fails for lack of random bits.

The random bits come from a fair bank: an array of M×DM\times D words of HH bits each, where D=M+6D=M+6 and MM and HH are explicit polynomials in nn, LL and NN.✦ The iith uniform draw from {0,…,u}\{0,\dots,u\} uses row ii, by rejection sampling on the first ⌈log⁡2(u+1)⌉\lceil\log_2(u+1)\rceil bits of its words✦; a coin of bias a/ca/c in lowest terms is a uniform draw from {0,…,c−1}\{0,\dots,c-1\} that comes up heads when it is below aa✦. The output of one run is a function Y(γ)Y(\gamma) of the fair bank γ\gamma.

Let m=64(λ+1)m=64(\lambda+1), where λ\lambda is the number of binary digits of the denominator of δ\delta.✦ A full bank is an element β=(γ1,…,γm)\beta=(\gamma_1,\dots,\gamma_m) of the set ℬ\mathcal B of mm-tuples of fair banks✦, and F=mMDHF=mMDH is the number of its bits✦. The bounded output Z‾(β)\bar Z(\beta) is the median of Y(γ1),…,Y(γm)Y(\gamma_1),\dots,Y(\gamma_m), the entry of index ⌊m/2⌋\lfloor m/2\rfloor, counting from 00, in their sorted list, when n>0n>0, and 11 when n=0n=0.✦

The frozen machine is one fixed program. It runs a preamble that computes from (n,r,ε,δ)(n,r,\varepsilon,\delta) the parameters LL, NN, mm, MM, HH and FF; reads FF coin bits from the tape into a register, three steps per bit; and runs a postamble that cuts these bits into mm fair banks, runs the estimator on each and returns the bounded output. For a time t0t_0 and a tape β\beta, wt0(β)∈{0,1}Fw_{t_0}(\beta)\in\{0,1\}^F is the word whose bit ii is βt0+3(F−1−i)+1\beta_{t_0+3(F-1-i)+1}.

A computation of the preamble or of the postamble keeps within size SS when its input and every value computed along the way have size at most SS.✦ For polynomials fpf_p and fqf_q in one variable XX with natural coefficients, the resource polynomial is Tfp,fq=200(E+cpre(fp+X+1)epre+cpost(fq+X+1)epost+fq+1),T_{f_p,f_q}=200\bigl(E+c_{\mathrm{pre}}(f_p+X+1)^{e_{\mathrm{pre}}} +c_{\mathrm{post}}(f_q+X+1)^{e_{\mathrm{post}}}+f_q+1\bigr),(6)✦ where EE is a fixed polynomial and the constants cpre,eprec_{\mathrm{pre}},e_{\mathrm{pre}} and cpost,epostc_{\mathrm{post}},e_{\mathrm{post}} are determined by the preamble and the postamble.

A map v:{0,1}F→ℚv:\{0,1\}^F\to\mathbb Q is an output certificate when the postamble, run on each word ww together with the parameters, returns v(w)v(w); every v(w)v(w) is nonnegative and equals 00 when Z=0Z=0; and for every φ:ℚ→ℝ\varphi:\mathbb Q\to\mathbb R 12F∑w∈{0,1}Fφ(v(w))=1|ℬ|∑β∈ℬφ(Z‾(β)).\frac{1}{2^F}\sum_{w\in\{0,1\}^F}\varphi\bigl(v(w)\bigr) =\frac{1}{|\mathcal B|}\sum_{\beta\in\mathcal B}\varphi\bigl(\bar Z(\beta)\bigr).(7)✦

The Claim

Theorem 1. There are a program PP and constants C>0C>0 and dd with the following property.✦ Let M1M_1 and M2M_2 be matroids of rank rr on [n][n], let OO be an exact independence oracle for them, let ε\varepsilon and δ\delta be rationals in (0,1)(0,1), and let B=CμdB=C\mu^d, with μ\mu as in (2). Then on every tape, the run of PP with oracle OO from the initial configuration on (n,r,ε,δ)(n,r,\varepsilon,\delta) has, after BB steps, made at most BB oracle calls and at most BB bit operations and produced an output z≥0z\ge0, with z=0z=0 when Z=0Z=0. With z(β)z(\beta) the output on the tape β\beta, #{β∈{0,1}B:(1−ε)Z≤z(β)≤(1+ε)Z}≥(1−δ)2B.\#\bigl\{\beta\in\{0,1\}^B:(1-\varepsilon)Z\le z(\beta)\le(1+\varepsilon)Z\bigr\} \ge(1-\delta)\,2^B.(8)✦

In the paper, the result reads: there is a single randomized oracle algorithm that, given independence oracles for arbitrary matroids M1,M2M_1,M_2 of rank rr on [n][n] and rationals ε,δ∈(0,1)\varepsilon,\delta\in(0,1), outputs a nonnegative rational Zˆ\hat Z with Pr⁡[(1−ε)Z≤Zˆ≤(1+ε)Z]≥1−δ\Pr[(1-\varepsilon)Z\le\hat Z\le(1+\varepsilon)Z]\ge1-\delta, always outputs zero when Z=0Z=0, makes on every execution a number of oracle calls and of other bit operations bounded by a fixed polynomial in nn, ℓ\ell, ε−1\varepsilon^{-1} and log⁡δ−1\log\delta^{-1}, with ℓ\ell the encoding length of n,r,ε,δn,r,\varepsilon,\delta, and uses only independent unbiased random bits and no representation of either matroid. In the box, the probability is the fraction of the 2B2^B tapes of length BB and the polynomial is CμdC\mu^d.

What Is Checked

The claim (8) is stated over matroids of rank rr on [n][n], an exact independence oracle, the number ZZ of common bases, relative accuracy (1), programs with their configurations, initial configuration and runs on a tape, and the resource bound B=CμdB=C\mu^d.

For the estimator, take matroids M1M_1 and M2M_2 of rank rr on [n][n] with an exact independence oracle OO, and rationals 0<ε<10<\varepsilon<1 and δ>0\delta>0. The library proves that every full bank β\beta has Z‾(β)≥0\bar Z(\beta)\ge0, with Z‾(β)=0\bar Z(\beta)=0 when Z=0Z=0, and that 1|ℬ|#{β∈ℬ:(1−ε)Z≤Z‾(β)≤(1+ε)Z}≥1−δ.\frac{1}{|\mathcal B|}\, \#\bigl\{\beta\in\mathcal B:(1-\varepsilon)Z\le\bar Z(\beta)\le(1+\varepsilon)Z\bigr\} \ge1-\delta.(9)✦

The frozen machine reads a certificate off the tape. Let fpf_p and fqf_q be polynomials with natural coefficients, M1M_1, M2M_2 and OO as above, rationals ε>0\varepsilon>0 and δ\delta, and B≥Tfp,fq(μ)B\ge T_{f_p,f_q}(\mu), and suppose that the preamble keeps within size fp(μ)f_p(\mu) on (n,r,ε,δ)(n,r,\varepsilon,\delta) and the postamble keeps within size fq(μ)f_q(\mu) on every word w∈{0,1}Fw\in\{0,1\}^F with the parameters. Then there are an output certificate vv and a time t0t_0 with t0+3F+1≤Bt_0+3F+1\le B such that on every tape β\beta the run of the frozen machine for BB steps from the initial configuration makes at most BB oracle calls and at most BB bit operations and produces the output z(β)=v(wt0(β)).z(\beta)=v\bigl(w_{t_0}(\beta)\bigr).(10)✦

On tapes of length BB, a certificate is accurate on most tapes: for M1M_1, M2M_2 and OO as above, rationals 0<ε<10<\varepsilon<1 and δ>0\delta>0, an output certificate vv, and times t0t_0 and BB with t0+3F+1≤Bt_0+3F+1\le B, #{β∈{0,1}B:(1−ε)Z≤v(wt0(β))≤(1+ε)Z}≥(1−δ)2B.\#\bigl\{\beta\in\{0,1\}^B:(1-\varepsilon)Z\le v\bigl(w_{t_0}(\beta)\bigr) \le(1+\varepsilon)Z\bigr\}\ge(1-\delta)\,2^B.(11)✦