we-solve (beta)

Math-540 · mathematics · Combinatorics

Trace Reconstruction

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Shared notation.
Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

A trace of $x\in\{0,1\}^n$ is the subsequence left after independently deleting each coordinate with probability $1/2$, retaining the order but not the deleted positions. Let $m(n)$ be the least sample size for which one reconstruction rule, knowing $n$, returns every possible $x$ correctly with probability at least $0.9$ from independent traces. This is a sample-complexity question, without an additional running-time bound. [S1] [S2]

Statement recorded in the supplied source.
Given a string $x \in \{0, 1\}^n$, let $\tilde{x}$ be obtained by deleting bits independently at random with probability $\frac{1}{2}$. How many independent traces $\tilde{x}_1, \dots, \tilde{x}_m$ are needed to reconstruct $x$ with probability 0.9? [S1]
Residual task reported by the archive.

The embedded review (2026-08-17) records: Determine matching lower and upper bounds, including the optimal exponent at deletion probability 1/2. [S1]

Short English statement

How many independent deletion-corrupted copies suffice to recover an arbitrary binary string reliably, even when computation time is unrestricted?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 2

Math-540-A2 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-540

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.

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

Go to contribution →

Math-540-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on Math-540

Worst-Case Binary Trace Reconstruction

Definitions and mathematical statement

Shared notation.
Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

A trace of $x\in\{0,1\}^n$ is the subsequence left after independently deleting each coordinate with probability $1/2$, retaining the order but not the deleted positions. Let $m(n)$ be the least sample size for which one reconstruction rule, knowing $n$, returns every possible $x$ correctly with probability at least $0.9$ from independent traces. This is a sample-complexity question, without an additional running-time bound. [S1] [S2]

Statement recorded in the supplied source.
Given a string $x \in \{0, 1\}^n$, let $\tilde{x}$ be obtained by deleting bits independently at random with probability $\frac{1}{2}$. How many independent traces $\tilde{x}_1, \dots, \tilde{x}_m$ are needed to reconstruct $x$ with probability 0.9? [S1]
Residual task reported by the archive.

The embedded review $2026-08-17$ records: Determine matching lower and upper bounds, including the optimal exponent at deletion probability 1/2. [S1]

Short English statement

How many independent deletion-corrupted copies suffice to recover an arbitrary binary string reliably, even when computation time is unrestricted?

Research attempt

Provenance and scope.
This individual attempt was generated by GPT-6 Astra Ultra on 1 October 2026. The method was to derive explicit partial results and test the first proposed extension adversarially. The original statement and sources below are retained. No claim of mathematical novelty or complete solution is made.
Formal target and context.
The unknown binary string has known length $n$, deletion probability is one half, and the same algorithm must succeed with probability at least $0.9$ for every input. Computation time is unrestricted. The inspected Nazarov--Peres paper concerns a much stronger upper bound than the elementary one below and distinguishes the restricted model based only on coordinate means. We derive a simple information-theoretic lower bound from neighbouring isolated-one strings and an exact generating-function identity, keeping general reconstruction separate from mean-based reconstruction.
An elementary upper bound uses an intact trace.
A trace equals the complete input with probability $2^{-n}$. Whenever a trace of length $n$ appears, it must be the original string. With $m$ independent traces, the probability of seeing none is $(1-2^{-n})^m\leq e^{-m2^{-n}}$. Thus $m\geq2^n\log10$ suffices. This is deliberately a weak baseline, not a claim about the best known rate. Its merit is that it is uniform in the string and gives a direct check on the success-probability convention.
Two nearby isolated-one inputs are hard to distinguish.
Take $x=0^k1 0^\ell$ and $y=0^{k+1}1 0^{\ell-1}$, where $k+\ell+1=n$ and both $k,\ell$ are order $n$. Conditional on deletion of the one, both inputs produce the same distribution: a zero string of length $\operatorname{Bin}(n-1,1/2)$. Conditional on retention, the numbers of zeros before and after the one are independent, distributed as \[ (\operatorname{Bin}(k,1/2),\operatorname{Bin}(\ell,1/2)) \quad\hbox{and}\quad (\operatorname{Bin}(k+1,1/2),\operatorname{Bin}(\ell-1,1/2)). \] Let $P_m$ denote the law of $\operatorname{Bin}(m,1/2)$. Since $P_{m+1}$ is the average of $P_m$ and its translate by one, \[ d_{\rm TV}(P_m,P_{m+1}) \leq\tfrac12d_{\rm TV}(P_m,P_m+1) =\tfrac12\max_j P_m(j)\ll m^{-1/2}. \] For completeness, the equality follows by summing successive absolute differences of the unimodal binomial mass function: the total rise and fall is twice its maximum, and total variation divides by two. The final estimate is the central-binomial bound from Stirling's formula.

Total variation between product measures is at most the sum of the coordinate distances, by independent maximal couplings. Mixing with the common deleted-one component multiplies the remaining difference by one half. Therefore the single-trace laws $P_x,P_y$ satisfy $d_{\rm TV}(P_x,P_y)\leq C/\sqrt n$. For $m$ independent traces, the same coupling argument gives distance at most $Cm/\sqrt n$.

If a reconstruction rule succeeds with probability $0.9$ on both inputs, its output distinguishes them with average error at most $0.1$. Binary testing requires total variation at least $0.8$: for equal priors, optimal average success is $(1+d_{\rm TV})/2$. Hence $m\geq c\sqrt n$. This is a complete but nonoptimal lower bound; it does not use computational restrictions.

The mean polynomial and its limitation.
Index the input bits by $0,\ldots,n-1$, and write a trace's bit at position $j$ as $\widetilde x_j$, padded by zeros beyond its length. Conditional on retaining bit $i$, its output position is binomial with parameters $i,1/2$. Consequently \[ {\mathbb{E}}\sum_{j\geq0}\widetilde x_jz^j =\frac12\sum_{i=0}^{n-1}x_i\left(\frac{1+z}{2}\right)^i. \] The affine change of variable is invertible, so exact knowledge of all means identifies the input polynomial uniquely. However finite samples only estimate means approximately. Inverting a polynomial transformation can amplify tiny errors, and injectivity alone gives no good sample bound. This is the exact point where a purely algebraic identification argument stops being a quantitative reconstruction theorem.
Verification and remaining gap.
The two test strings have the same length and the one is internal, so no boundary convention is hidden in the binomial laws. The common all-zero mixture is treated explicitly rather than discarded. The lower bound concerns every reconstruction algorithm, whereas the generating identity describes only means. The established bounds are $c\sqrt n\leq m(n)\leq2^n\log10$ by elementary arguments, together with exact identifiability from means. They are not literature records. Determining the sharp sample growth still requires substantially stronger indistinguishability examples or reconstruction estimates beyond these calculations.

Sources

Go to contribution →