VibeMathedMath problems solved with AI
Sign in

Polynomial-time approximate counting and uniform sampling of contingency tables with arbitrary margins

For margins r∈Z≥0mr\in\mathbb{Z}_{\ge0}^m, c∈Z≥0nc\in\mathbb{Z}_{\ge0}^n with equal totals, let Ω(r,c)\Omega(r,c) be the nonnegative integer m×nm\times n matrices with these row and column sums (optionally with individual cell bounds bijb_{ij}, zero bounds allowed). Exact counting is #P-complete even for two rows (Dyer-Kannan-Mount 1997). Polynomial approximate counting and sampling were known for two rows, for a fixed number of rows, for sufficiently large or dense margins, and for sparse margins, but not jointly polynomial in both dimensions and the binary length of the margins; Cryan, Dyer and Randall (2010) named unrestricted cell-bounded counting as open. Is there a fully polynomial randomized approximation scheme for ∣Ω∣|\Omega|, and a polynomial-time almost-uniform sampler, for arbitrary binary-encoded margins (and cell bounds) with both dimensions part of the input?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Construction
Field
Approximate counting and sampling (FPRAS, Markov chains)
Posed by
Dyer, Kannan and Mount (1997) and the subsequent literature; the unrestricted cell-bounded case named open by M. Cryan, M. Dyer and D. Randall, SIAM J. Comput. (2010)
Year posed
1997
Years open
29y
Solved
2026-09-24
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
42 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

FPRAS manuscript: one randomized algorithm counts nonnegative integer matrices with prescribed row sums, column sums and entry bounds bijb_{ij} (zeros allowed) within relative error ε\varepsilon with probability 1−δ1-\delta, using unbiased bits and a polynomial bound in the input length, ε−1\varepsilon^{-1} and log⁡δ−1\log\delta^{-1} on every execution. Sampling manuscript: for ordinary tables, an almost-uniform sampler (TV error 2−k2^{-k}) in worst-case polynomial bit time and an exactly uniform sampler in expected polynomial bit time in m,n,log⁡(N+1)m,n,\log(N+1). Exponents are deliberately large; the results are complexity classifications, not practical algorithms, and the exact sampler is polynomial only in expectation.

What the AI did

The OpenAI math release (github.com/openai/math, commit adc7f12) states that its results were produced by an unreleased internal OpenAI model under one fixed procedure, averaging about three hours of ChatGPT Pro thinking compute per result. This result is not among the README's stated exceptions (the Re(s) > 11/12 zero-free region write-up and the Hodge conjecture for CM abelian varieties). The manuscript is credited to OpenAI alone and names no human author. The family has two manuscripts, both dated 24 September 2026: an FPRAS for cell-bounded tables and exact and almost-uniform samplers for ordinary tables.

Verification

No independent mathematician has checked this yet. Checked here: the abstracts, introductions and main theorems of both TeX sources, read against the open problem as described in their history sections (Dyer-Kannan-Mount, Cryan-Dyer-Randall, Arman-Gao-Wormald); the proofs were not refereed. Lean: the Comparator challenge ContingencyTables (OAI.ContingencyTables.counting, exactSampling, boundedSampling; solution module OAI/Combinatorics/ContingencyTables/UnconditionalMain.lean) is not in the release's formalization catalogue, but its JSON and solution file exist at the pinned commit. Its statement was read here: it fixes a randomized Post-Turing machine model with binary encodings and asserts (i) a cell-bounded counter whose every execution halts within a fixed polynomial in input length, 1/eps and log(1/delta), outputs zero on infeasible inputs, and is within relative error eps with probability at least 1 - delta; (ii) a bounded-time sampler with total-variation error at most 2^-k; (iii) an exact sampler with uniform limiting law and polynomial expected running time. This states the headline claims. Not rebuilt here.

Sources

Changelog1 change

Discussion