we-solve (beta)

CS-104 · computer science · mathematics · Information and coding theory

10 Lectures and 42 Open Problems — The Deletion Channel

Status Partially solved · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

A trace of $x\in\{0,1\}^n$ is obtained by independently deleting each bit with probability $1/2$ and retaining the order of the remaining bits. Deleted positions are not reported. Repeated traces of the same input use independent deletions.

For $0<\varepsilon<1/2$, let $D_{\rm av}(n,\varepsilon)$ be the least $m$ for which a decoder, knowing $n$, reconstructs a uniformly random $X\in\{0,1\}^n$ from $m$ traces with error probability at most $\varepsilon$. Probability averages over $X$, deletions, and any decoder randomness. This makes explicit the source's random-input wording. Define $D_{\rm worst}$ separately by requiring the error bound for every fixed input string.

Determine the asymptotic trace complexity, specifying the convention used; the high-probability average-case target can be fixed as $D_{\rm av}(n,n^{-1})$ for $n\ge3$. Bounds proved only for $D_{\rm worst}$ must be identified as such rather than silently equating the two quantities.

The second question concerns two known distinct strings $x,y$. Let $d(x,y)$ be the least number of traces permitting a test whose error is at most $1/3$ under each of the two hypotheses. Determine \[ \max_{x\ne y\in\{0,1\}^n}d(x,y) \] and identify pairs realizing the hardest order of growth. These questions concern information from repeated noisy observations, not the capacity of a code used for one transmission. Computation time is unrestricted in these sample-complexity definitions.

Short English statement

Determine trace-reconstruction sample complexity and the hardest pairs of strings to distinguish after independent deletions.

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

CS-104-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for CS-104

These results concern worst-case input words and hard-pair separation. They do not determine the typical random-word complexity or the exact extremal pair growth, so those additional clauses of the deletion-channel problem remain unanswered.

10 Lectures and 42 Open Problems — The Deletion Channel

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

Go to contribution →