Episode 115, October 2026

Any margins?

A claimed exact uniform sampler for contingency tables with arbitrary margins, and a fully polynomial randomized approximation scheme for tables with cell bounds

Covers result 115 in OpenAI’s catalog: all 2 papers. See its connections to other results and the work it cites.

Play Episode 115: Any margins? A 3 by 3 table of whole numbers with every row and column summing to 3.

6:46. English captions available. The video loads from YouTube when you press play.

Chapters

The claims, in plain words

Exact counting is #P-complete even with two rows (Dyer, Kannan and Mount). Approximation had partial answers: Dyer and Greenhill handled two rows, Cryan and Dyer any fixed number of rows, and geometric methods of Dyer, Kannan and Mount, and later Morris, handled large margins. For sparse margins, Arman, Gao and Wormald gave exact uniform generation, and in 2021 they reported that no polynomial-time approximately uniform sampler for arbitrary margins was known. A cap on every cell connects the problem to perfect matchings and network flows; Cryan, Dyer and Randall identified the unrestricted capped case as an open problem in 2010.

Result 115 is two OpenAI preprints dated September 24, 2026. The first, 31 pages, claims an exactly uniform sampler for tables with any margins, with no positivity, balance, sparsity or fixed-dimension assumption: it stops with probability one, and its expected number of bit operations is polynomial in both dimensions and the number of bits in the margins. A second algorithm has a polynomial time bound on every execution and outputs a table within 2^−k of uniform in total variation, for any requested k. The second, 47 pages, claims a fully polynomial randomized approximation scheme (FPRAS) for tables with an individual upper bound on every cell, where a zero bound forbids the cell: on every execution the bit operations are polynomial in the input length, 1/ε and log(1/δ), and an empty set of tables gives zero. It also yields approximate counting and sampling of bounded integer flows in networks.

What it doesn’t claim

The exact sampler is polynomial in expectation, not on every run: a rare correction branch does exhaustive work. Its guarantees are for tables without cell bounds; with cell bounds, the claim is approximate counting (and, through it, approximate sampling). The authors note that their exponents are deliberately large: these are complexity guarantees, not practical running times.

Where it stands

Posted as preprints: OpenAI, 31 and 47 pages, dated September 24, 2026
Peer reviewed: Not yet
Checked in Lean: OpenAI published a Lean proof of both samplers and the counting scheme; we have not run the check

Last checked October 19, 2026. The preprints have not been revised. OpenAI published a Lean formalization of the bounded sampler, the exact sampler and the counting scheme, each as a statement about one fixed randomized machine (the comparator statements), proved in files whose import closure has 1,297 files and 191,813 lines, not counting Mathlib, with no unproved steps that we could find. The network-flow consequences are not formalized. We have not run the check. Neither paper is among those OSVerify reviewed, and we have seen no expert review.

How the proofs go

Small cells and a padded rectangle. Cells in a row or column with a small margin become explicit coordinates; the remaining cells form a complete rectangle, padded so that filling it in is always a dense problem. Each small cell carries a row value x_s and a column value q_s; states where they agree are transversals, and the chain also allows a surplus of one at one cell and a deficit of one at another. Each state is weighted by its number of padded completions. Sampling a state and then a completion, and accepting only a transversal whose large entries are all at least the padding, gives a uniform table once the padding is subtracted.
Why the chain mixes. The proof reveals the small-cell values one at a time and compares neighboring fibers. Quadratic forms indexed by pairs of unit removals have at most one positive eigenvalue, a property central to the theory of Lorentzian polynomials, and the property survives summing out a balanced pair. A weighted transport between neighboring fibers gives a Poincaré inequality, which bounds the mixing time.
From approximate to exact. Completions of the dense rectangle are drawn approximately on a finite scaled grid; a log-concave density appears only in the analysis, and in an ordinary run large ranges are never enumerated. For exactness, the residual-mixture idea of Göbel, Liu, Manurangsi and Pappik: with probability δ the algorithm enters a correction branch, lists all tables, computes the bounded sampler’s exact output law p_k, and draws from r(z) = (1/M − (1 − δ)p_k(z))/δ, so that (1 − δ)p_k + δr is exactly uniform. The branch is exponentially expensive but exponentially rare.
Counting with caps. Each cell is tightened to the range it can actually take, and cells are split at a threshold. Large cells are handled through a maximum-capacity spanning forest and soft penalties, hardened along a schedule while ratios are estimated by sampling; the final softened count is within a factor 1 + ε/32 of the true count. Each small cell with bound b becomes b labelled pairs, giving transversals and defect states as in the common-bases result (episode 114), with learned multipliers as in the permanent algorithm.

The numbers in the video

The 3-by-3 tables with every margin 3 number 55; MacMahon’s formula, checked by direct counting up to margin 12, gives 125,000,750,001,875,002,250,001 when every margin is 1,000,000.
Padding every entry of a small example (rows 3, 2; columns 2, 2, 1; 5 tables) by 2 gave 33 tables, exactly 5 of which had every entry at least 2, matching the 5 originals.
A slightly biased law on the 55 tables, mixed with its residual at probability 2⁻¹², was exactly uniform in exact arithmetic.
Seven labelled pairs gave six transversals; weighting each by 1/∏C(b_s, x_s) gave a total of 2, exactly the number of tables. Separately, with 0/1 bounds and unit margins, direct counts equalled the permanents.

Read the source

Exact Uniform Sampling of Contingency Tables with Arbitrary Margins (PDF), 31 pages.
An FPRAS for Cell-Bounded Contingency Tables (PDF), 47 pages.
The Lean scope note.
The collection’s catalog, where this is result 115.

The 2 papers in this result

OpenAI groups related papers, such as alternative proofs, supporting results and consequences, into one result; we label the first paper it lists the main paper and the others companions.

Exact Uniform Sampling of Contingency Tables with Arbitrary Margins main paper
An FPRAS for Cell-Bounded Contingency Tables companion

Transcript

Read the full script

0:00Tables with fixed margins

A contingency table is a grid of nonnegative whole numbers with prescribed row sums and column sums. Statisticians use such tables to test whether two classifications are independent, which raises two basic questions: how many tables share the same margins, and how can one be drawn uniformly at random? The 2-by-2 tables with every margin equal to two already show the geometry: there are exactly 3, the integer points of a segment, and only the two ends are vertices. In our check, the 3-by-3 tables with every margin equal to 3 number 55. With margins written in binary the count can be enormous: for 3-by-3 tables with every margin 1,000,000, about 20 bits each, there are about 1.25 × 10^23. Exact counting is hard: Dyer, Kannan and Mount proved it #P-complete even with two rows. Approximation had partial answers. Dyer and Greenhill handled two rows, Cryan and Dyer any fixed number of rows, and geometric methods of Dyer, Kannan and Mount, and later Morris, handled large margins. For sparse margins, Arman, Gao and Wormald gave exact uniform generation, and in 2021 they reported that no polynomial-time approximately uniform sampler for arbitrary margins was known. Adding a cap on every cell connects the problem to perfect matchings and network flows, and Cryan, Dyer and Randall identified the unrestricted capped case as an open problem in 2010.

1:33The claims

Result 115 is two OpenAI preprints dated September 24. The first, 31 pages, claims an exact uniform sampler for tables with any margins, with no positivity, balance, sparsity or fixed-dimension assumption. It terminates with probability one, and its expected number of bit operations is polynomial in both dimensions and the number of bits in the margins. A second algorithm stops within a polynomial time bound on every execution, and its output is within 2^−k of uniform in total variation, for any requested k. The authors note that their exponents are deliberately large. The second preprint, 47 pages, claims an FPRAS for tables with an individual upper bound on every cell, where a zero bound forbids the cell. Margins and bounds are written in binary and both dimensions vary. On every execution the bit operations are polynomial in the input length, 1/ε and log(1/δ), and an empty set of tables gives zero. It also yields approximate counting and sampling for bounded integer flows in networks. OpenAI published a Lean formalization of the two samplers and the counting scheme, about 1,300 files and 190,000 lines with its imports, not counting Mathlib. We have not run the Lean check ourselves.

3:00How the proofs go

The sampler separates small numbers from large ones. Cells in a row or column with a small margin become explicit coordinates; the remaining cells form a complete rectangle, which is padded so that filling it in is always a dense problem. Each small cell carries two bounded values, one for its row and one for its column. States where they agree are called transversals, and the chain also allows a surplus of one at one cell and a deficit of one at another. Each state is weighted by its number of padded completions. Sampling a state and then a completion, and accepting only a transversal whose large entries are all at least the padding, gives a uniform table once the padding is subtracted. In our check, padding every entry of a small example by 2 gave 33 tables, and exactly 5 had every entry at least 2, matching the 5 original tables. To show that the chain mixes quickly, the proof reveals the small-cell values one at a time and compares neighboring fibers. Quadratic forms indexed by pairs of unit removals have at most one positive eigenvalue, a property central to the theory of Lorentzian polynomials and also used in the common-bases result, and the property survives summing out a balanced pair. A weighted transport between neighboring fibers then gives a Poincaré inequality, which bounds the mixing time. Completions of the dense rectangle are drawn approximately on a finite scaled grid; a log-concave density appears only in the analysis, and in an ordinary run large ranges are never enumerated. That gives the bounded sampler. For exactness, the algorithm uses the residual-mixture idea of Göbel, Liu, Manurangsi and Pappik. With tiny probability it enters a correction branch, enumerates all tables, computes the bounded sampler’s exact output law, and draws from the leftover mass. The branch is exponentially expensive but exponentially rare, so the expected cost stays polynomial. In our check, a slightly biased law on the 55 tables, mixed with its residual at probability 2^−12, came out exactly uniform. The counting paper first tightens every cell to the range it can actually take, and splits cells at a threshold. Large cells are handled through a maximum-capacity spanning forest and soft penalties, which are hardened along a schedule while ratios are estimated by sampling; the final softened count is within a factor 1 + ε/32 of the true count. Each small cell with bound b becomes b labelled pairs, giving transversals and defect states as in the common-bases result, with learned multipliers as in the permanent algorithm. In our check, 7 labelled pairs gave 6 transversals; weighting each by one over the number sharing its profile gave a total of 2, exactly the number of tables. Separately, with 0/1 bounds and unit margins, a direct count equalled the permanent.

6:01Where it stands

The preprints are not peer reviewed and have not been revised. OpenAI’s Lean formalization covers the bounded sampler, the exact sampler and the counting scheme, as statements about a fixed randomized machine, but not the network-flow consequences; we have not run it. Neither paper is among those OSVerify reviewed, and we have seen no expert review. If they hold, tables with any margins can be sampled exactly in polynomial expected time, and tables with caps on individual cells can be counted approximately in polynomial time, without the fixed number of rows, large margins or sparse margins that earlier methods needed.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.