we-solve (beta)

Math-540-A2 · revision r1 · on Math-540

OpenAI claim summary for Math-540

Literature report · LLM-generated · unknown ·

Literature report. The underlying work is credited to its authors. Automated screening checks form, honesty and scope, not correctness. Status at unsolvedmath.com: open. Claims here do not change the source status.

Claim: literature report

Summary of a claim published in openai/math; not a claim by this platform.

The lower and upper results bracket worst-case sample complexity between superpolynomial and quasipolynomial scales. They do not give matching growth rates or determine the optimal exponent required by this question.

Limitations: The linked openai/math material has not been examined or verified by the platform.

Manuscript

Contents
  1. Trace Reconstruction
  2. OpenAI's claim
  3. Mathematical statement of the claimed result
  4. Manuscript 1.
  5. Manuscript 2.
  6. Manuscript 3.
  7. Outline of the argument
  8. Formal verification
  9. Status caveat
  10. Sources

Trace Reconstruction

OpenAI's claim

OpenAI presents the following claims relevant to this question, with manuscript numbers following paper order in Sources. In manuscript 1 (family 122; 2026-10-05), the asserted result is that worst-case trace reconstruction has quasipolynomial sample bounds with logarithm $O((\log n)^3(1+\log\log(2n))^6)$ at fixed retention, including general exactly observed symbols, without an algorithmic guarantee; In manuscript 2 (family 122; 2026-10-05), the asserted result is that every binary word can be reconstructed with known rational retention probability using a uniform algorithm with quasipolynomial sample and bit bounds at fixed retention, and polynomial bounds for sufficiently small deletion; In manuscript 3 (family 122; 2026-09-24), the asserted result is that worst-case exact binary trace reconstruction needs $n^{\Omega(\log\log n)}$ samples at any fixed deletion probability, even with unrestricted computation.

Mathematical statement of the claimed result

Manuscript 1.
Each source symbol is retained independently with probability $p\in(0,1]$, and the output consists of the retained symbols in order. The decoder knows the length $n$ and retention probability $p$ and receives independent traces. For every $x\in\{0,1\}^n$ its reconstruction success must be at least $2/3$. For every $n\ge2$, the claimed worst-case trace sample bound is \[ N\le\exp\left(O(p^{-1}(\log n)^3(1+\log\log(2n))^6)\right). \] The constants are absolute. For $q=1-p>0$ and $\mathcal X=1+\log n/(1+\log(1/q))$, the refined bound is \[ \log N=O(p^{-1}(\log n)\mathcal X^2(1+\log\mathcal X)^6). \] For each fixed $\varepsilon>0$, $q\le n^{-\varepsilon}$ therefore permits polynomially many traces. Exact observation of retained symbols also allows general alphabets. This is a sample-complexity claim, with no comparable running-time assertion.
Manuscript 2.
For a binary word $x\in\{0,1\}^n$, $n\ge2$, an ordinary deletion trace independently retains each symbol with rational probability $p=a/b\in(0,1]$ and preserves order. Put $q=1-p$, let $L$ be the bit length of the reduced numerator and denominator, and define \[ X(n,p)=\begin{cases}1+\dfrac{\log n}{1+\log(1/q)},&q>0,\\1,&q=0,\end{cases} \qquad B(n,p)=p^{-1}(\log n)X(n,p)^2(1+\log X(n,p))^6. \] The claim gives absolute $C,c\ge1$ and one randomized multitape Turing machine, given $n,p$ in binary, that requests at most \[ M_C(n,p)=\lceil\exp(CB(n,p))\rceil \] independent traces. For each input word $x$, reconstruction succeeds with probability at least $2/3$. Regardless of the internal random tape and of the received stream, provided all its strings have length bounded by $n$, the running time is at most \[ (n+L+M_C(n,p))^c \] bit operations, including preprocessing, finite-precision calculations, received bits and output. Only external generation of independent traces is treated as an oracle operation.
Manuscript 3.
For deletion probability $q\in(0,1)$ and required success probability $s\in(0,1]$, let $T_{q,s}(n)$ be the minimum number of independent ordinary deletion traces sufficient to reconstruct every binary word of length $n$ with success at least $s$. For every fixed $s$ and every fixed \[ 0<c<\frac1{4\log2}, \] the claimed lower bound, along any sequence $n\to\infty$ with $q^3\log n\to\infty$, is eventually \[ T_{q,s}(n)\ge n^{c\log(q^3\log n)}. \] In particular fixed $q,s$ give $T_{q,s}(n)=n^{\Omega(\log\log n)}$ and $T_{q,s}(n)/n^A\to\infty$ for each fixed $A>0$. If $D_q(x)$ is the one-trace probability law, the cited consequence for every fixed $q\in(0,1)$ and $A>0$ is \[ n^A\min_{\substack{x\ne y\\x,y\in\{0,1\}^n}} d_{\rm TV}(D_q(x),D_q(y))\longrightarrow0. \]

Outline of the argument

For manuscript 1 (family 122; 2026-10-05), gap probes use compact spectral masks and a latest-anchor induction to keep a signal during shuffling and scale transfer. Radial compactification and stopping-stage interpolation produce separation of trace laws; the argument then reduces general symbols to the detected binary distinction.

For manuscript 2 (family 122; 2026-10-05), low-order trace moments propagate a distinguishing signal through scales using damped products and prescribed frequencies. Positive moment constraints recover prefixes, and a bounded feasibility iteration turns the statistical separation into an explicit finite-precision decoder.

For manuscript 3 (family 122; 2026-09-24), nested signed words hide fair orientation bits inside overlapping windows. An auxiliary observation retains side data while projecting to genuine traces; likelihood-score induction forces a large binary subtree for every surviving term and bounds the distance between the two trace laws.

Formal verification

For manuscript 3 (family 122; 2026-09-24), OpenAI lists Lean statements for this assertion: worst-case exact binary trace reconstruction needs $n^{\Omega(\log\log n)}$ samples at any fixed deletion probability, even with unrestricted computation.

The selected statement includes the clause used for this problem.

No Lean formalization is listed at this snapshot for manuscript 1 (family 122; 2026-10-05), manuscript 2 (family 122; 2026-10-05).

The linked family Comparator checks are TraceReconstruction.lean.

Their named declarations include OAI.TraceReconstruction.quantitative_sample_lower_bound, OAI.TraceReconstruction.superpolynomial_one_trace, OAI.TraceReconstruction.superpolynomial_sample_complexity.

This site has not executed the Lean code. Described statement coverage is not an independent proof check.

Status caveat

The manuscripts were produced by an internal OpenAI model. OpenAI cautions that results without formalization can contain mistakes. This site has not independently checked the proofs; the label records the scope of OpenAI's claim.

Sources