Can worst-case trace reconstruction be done with polynomially many traces?

An unknown binary string $x\in\{0,1\}^n$ is passed repeatedly through a deletion channel that removes each bit independently with known probability $q\in(0,1)$ and concatenates the survivors; each output is a trace. Worst-case trace reconstruction asks how many independent traces $T_q(n)$ suffice to recover every $x$ with probability at least $2/3$ . The problem was formulated by Batu, Kannan, Khanna and McGregor (2004). For fixed $q$ the best upper bounds fell from $\exp(\widetilde O(\sqrt n))$ (Holenstein et al. 2008) to $\exp(O(n^{1/3}))$ (De-O'Donnell-Servedio; Nazarov-Peres 2017), $\exp(O(n^{1/5}\log^5 n))$ (Chase 2021) and a quasipolynomial bound (Burudgunte-Valiant-Wang 2026), while the best lower bound was $\Omega(n^{3/2}/\log^7 n)$ (Chase 2021). For a fixed deletion probability, is $T_q(n)$ bounded by a polynomial in $n$ ?

Result: Disproved(see note)
Status: Candidate (review pending)
AI contribution: AI-discovered
Method: Argument
Field: Trace reconstruction; deletion channels
Posed by: Open since Batu, Kannan, Khanna and McGregor formulated worst-case trace reconstruction (SODA 2004); the manuscript calls it the polynomial-sample question without naming who first asked it
Year posed: 2004
Years open: 22y
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

Theorem 1.1: for fixed $s\in(0,1]$ and $0<c<1/(4\log 2)$ , $T_{q,s}(n)\ge n^{c\log(q^3\log n)}$ eventually whenever $q^3\log n\to\infty$ ; so $T_q(n)=n^{\Omega(\log\log n)}$ at every fixed $q$ , a negative answer to the polynomial question. Theorem 1.2: the minimum total variation between one-trace laws of distinct length- $n$ words is $o(n^{-A})$ for all $A$ . The companions give a matching-type upper side: quasipolynomial samples and bit complexity with a uniform decoder for known rational retention, and polynomial bounds when $q\le n^{-\varepsilon}$ . A gap remains between $\log T$ of order $\log n\log\log n$ (lower) and a power of $\log n$ (upper); the exact complexity is not determined.

What the AI did

The release README says every result in openai/math was produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result. This result is not one of the README's two exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored 'OpenAI' and names no human author. The family has two later companions (October 5, 2026): a uniform quasipolynomial-time reconstruction algorithm for known rational retention probability, and an improved quasipolynomial sample upper bound. They give upper bounds and are links here.

Verification

No independent mathematician has checked this yet. Checked here: Theorems 1.1 and 1.2 of the lower-bound manuscript were read against the question. They give $T_{q,s}(n)\ge n^{c\log(q^3\log n)}$ along any sequence with $q^3\log n\to\infty$ , and $T_{q,s}(n)/n^A\to\infty$ for every fixed $q,s,A$ , with unrestricted computation and randomized estimators. The challenge is not in lean/formalization.yaml; lean/ComparatorChallenges/TraceReconstruction.json exists with solution_module OAI.Probability.TraceReconstruction, whose file exists at the pinned commit. The statement TraceReconstruction.lean was read here; not rebuilt here. Its three theorems define the sample complexity as an infimum over budgets admitting an estimator (a probability kernel on complete traces) and state: superpolynomial growth of sample complexity for every fixed $q\in(0,1)$ and $s\in(0,1]$ , superpolynomially small minimum one-trace total variation, and the quantitative bound. This states the headline negative answer. Permitted axioms: propext, Quot.sound, Classical.choice.

Can worst-case trace reconstruction be done with polynomially many traces?

What was actually shown

What the AI did

Verification

Sources

Discussion