/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Ben Green's Open Problem 92

References:

    [Gr24] Green, Ben. "100 open problems." (2024).

    [NP17] Nazarov, F. and Peres, Y., Trace reconstruction with $\exp(O(n^{1/3}))$ samples. Proceedings of STOC 2017, ACM, New York (2017), 1042--1046. arXiv:1612.03599

    [DOS19] De, A., O'Donnell, R. and Servedio, R., Optimal mean-based algorithms for trace reconstruction. Ann. Appl. Probab. 29 (2019), 851--874. arXiv:1612.03148

    [Ch20] Chase, Z., New upper bounds for trace reconstruction. arXiv:2009.03296 (2020).

    [Ch21] Chase, Z., New lower bounds for trace reconstruction. Ann. Inst. Henri Poincaré Probab. Stat. 57 (2021), 627--643. arXiv:1905.03031

@[expose] public sectionopen Filter Asymptoticsnamespace Green92

trace x S is the trace of the string x that keeps the bits in the positions of S and deletes the others, read in order.

def trace {n : ℕ} (x : Fin n → Bool) (S : Finset (Fin n)) : List Bool := ((List.finRange n).filter fun i ↦ decide (i ∈ S)).map xopen scoped Classical in

successProb R x is the probability that the decoder R returns x when it is applied to m independent traces of x. Each bit is kept independently with probability $1/2$, so the family S : Fin m → Finset (Fin n) of sets of kept positions is uniformly distributed.

noncomputable def successProb {n m : ℕ} (R : (Fin m → List Bool) → Fin n → Bool) (x : Fin n → Bool) : ℝ := (Finset.univ.filter fun (S : Fin m → Finset (Fin n)) ↦ R (fun j ↦ trace x (S j)) = x).card / (Fintype.card (Fin m → Finset (Fin n)) : ℝ)

numTraces n is the least number $m$ of traces such that some decoder recovers every string $x \in {0,1}^n$ from $m$ independent traces with probability at least $0.9$.

Such an $m$ exists: a single trace keeps all bits with probability $2^{-n}$, so a decoder that returns a trace of full length, if there is one, succeeds with probability at least $1 - (1 - 2^{-n})^m$. Hence the sInf is a minimum.

noncomputable def numTraces (n : ℕ) : ℕ := sInf {m | ∃ R : (Fin m → List Bool) → Fin n → Bool, ∀ x, (9 / 10 : ℝ) ≤ successProb R x}

The example of [Gr24]: deleting bits $2, 3, 5, 8$ (numbered from $1$) of $x = 00110110$ gives the trace $0111$. In Fin 8, numbered from $0$, the kept positions are $0, 3, 5, 6$.

@[category test, AMS 68] theorem trace_example : trace ![false, false, true, true, false, true, true, false] {0, 3, 5, 6} = [false, true, true, true] := ⊢ trace ![false, false, true, true, false, true, true, false] {0, 3, 5, 6} = [false, true, true, true] All goals completed! 🐙def green_92.answer : ℕ → ℝ := sorry

I have a string $x \in {0,1}^n$. Let $\tilde{x}$ be the random string obtained by deleting bits from $x$ independently at random with probability $\frac{1}{2}$ (thus, for example, if $n = 8$ and $x = 00110110$, it might be the case that $\tilde{x} = 0111$, generated by deleting bits $2, 3, 5, 8$.) An instance of $\tilde{x}$ is called a 'trace'. How many independent traces $\tilde{x}_1, \dots, \tilde{x}_m$ are needed before one can reconstruct $x$ with probability $0.9$?

This is the trace reconstruction problem. numTraces n is the least $m$ for which some decoder succeeds with probability at least $0.9$ for every $x$. Replacing $0.9$ by another constant in $(1/2, 1)$ changes $m$ by at most a constant factor (repeat and take a majority vote), so we ask for numTraces n up to constant factors.

@[category research open, question value, AMS 60 68] theorem green_92 : (fun n ↦ (numTraces n : ℝ)) =Θ[atTop] green_92.answer := ⊢ (fun n ↦ ↑(numTraces n)) =Θ[atTop] green_92.answer All goals completed! 🐙

Chase's upper bound. For every deletion probability $q \in (0, 1)$ and every $\delta > 0$ there is $C > 0$ such that every $x \in {0,1}^n$ can be reconstructed with probability at least $1 - \delta$ from $\exp(C n^{1/5} \log^5 n)$ independent traces of $x$ [Ch20, Theorem 1]. We state it for $q = 1/2$ and $\delta = 1/10$, with the number of traces rounded up, for large $n$. It improves the bound $\exp(C n^{1/3})$ of [NP17] and [DOS19].

@[category research solved, AMS 60 68] theorem green_92.variants.chase_upper : ∃ C : ℝ, 0 < C ∧ ∀ᶠ n : ℕ in atTop, numTraces n ≤ ⌈Real.exp (C * (n : ℝ) ^ (1 / 5 : ℝ) * Real.log n ^ 5)⌉₊ := ⊢ ∃ C, 0 < C ∧ ∀ᶠ (n : ℕ) in atTop, numTraces n ≤ ⌈Real.exp (C * ↑n ^ (1 / 5) * Real.log ↑n ^ 5)⌉₊ All goals completed! 🐙

Chase's lower bound. For every deletion probability $q \in (0, 1)$ and every $\delta \in (0, 1)$ there is $c > 0$ such that at least $c n^{3/2} / \log^7 n$ traces are required to distinguish between $x_n = (01)^k 1 (01)^{k+1}$ and $y_n = (01)^{k+1} 1 (01)^k$ with probability at least $1 - \delta$, where $n = 4k + 3$ [Ch21, Theorem 1]. A decoder that recovers every string distinguishes these two. We state it for $q = 1/2$ and $\delta = 1/10$, for large $n \equiv 3 \pmod 4$. [Gr24] quotes the bound $n^{3/2} (\log n)^{-16}$ of the first arXiv version of [Ch21]; the published version has $(\log n)^{-7}$.

@[category research solved, AMS 60 68] theorem green_92.variants.chase_lower : ∃ c : ℝ, 0 < c ∧ ∀ᶠ n : ℕ in atTop, n % 4 = 3 → c * (n : ℝ) ^ (3 / 2 : ℝ) / Real.log n ^ 7 ≤ numTraces n := ⊢ ∃ c, 0 < c ∧ ∀ᶠ (n : ℕ) in atTop, n % 4 = 3 → c * ↑n ^ (3 / 2) / Real.log ↑n ^ 7 ≤ ↑(numTraces n) All goals completed! 🐙end Green92