\section{Introduction}

The trace reconstruction problem asks one to recover an unknown string $x$ of length $n$ from independent noisy samples of the string. In the original setting, $x$ is a binary string in $\{0, 1\}^n,$ and a random subsequence $\tilde{x}$ of $x$, called a \emph{trace}, is generated by sending $x$ through a deletion channel with deletion probability $q$, which removes each bit of $x$ independently with some fixed probability $q$. The main question is to determine how many independent traces are needed to recover the original string with high probability. This question has become very well studied over the past two decades \cite{Levenshtein01a, Levenshtein01b, BatuKKM04, KannanM05, HolensteinMPW08, ViswanathanS08, McGregorPV14, DeOS17, NazarovP17, PeresZ17, HartungHP18, HoldenL18, HoldenPP18, Chase19, ChenDLSS20}, with many results over various settings. For instance, people have studied the case where we wish to reconstruct $x$ for any arbitrarily chosen $x \in \{0, 1\}^n$ (worst-case) or the case where we just wish to reconstruct a randomly chosen string $x$ (average-case). People have also studied the trace reconstruction problem for various values of the deletion probability $q$, such as if $q$ is a fixed constant between $0$ and $1$ or decays as some function of $n$. People have also studied variants where the traces allow for insertions of random bits, rather than just deletion of bits, and variants where the string is no longer binary but from a larger alphabet.

Finally, various generalizations or variants of the trace reconstruction problem have also been developed. These include error-correcting codes over the deletion channel (i.e., ``coded'' trace reconstruction) \cite{CheraghchiGMR19, BrakensiekLS19}, reconstructing matrices \cite{KrishnamurthyMMP19} and trees \cite{DaviesRR19} from traces, and reconstructing mixtures of strings from traces \cite{BanCFSS19, BanCSS19, Narayanan20}.

In this paper, we develop and study a new variant of trace reconstruction that we call \emph{Circular Trace Reconstruction}. In this variant, there is again an unknown string $x \in \{0, 1\}^n$ that we can sample traces from, but this time, the string $x$ is a cyclic string, meaning that there is no beginning or end to the string. Equivalently, one can imagine a linear string that undergoes a random cyclic shift before a trace is returned. See Figure \ref{Example} for an example. Our goal, like in the normal trace reconstruction, is to reconstruct the original circular string using as few random traces as possible.

\begin{figure} \label{Example}
\centering
\begin{tikzpicture}
\tikzstyle{bead}=[shape=circle, draw, inner sep=1,fill=white]

\draw (0, 0)
-- ++(75:0.6) node[bead] {\color{red} 1}
-- ++(45:0.6) node[bead] {\color{red} 0}
-- ++(15:0.6) node[bead] {\color{red} 0}
-- ++(-15:0.6) node[bead] {0}
-- ++(-45:0.6) node[bead] {\color{red} 1}
-- ++(-75:0.6) node[bead] {0}
-- ++(-105:0.6) node[bead] {1}
-- ++(-135:0.6) node[bead] {\color{red} 1}
-- ++(-165:0.6) node[bead] {0}
-- ++(-195:0.6) node[bead] {1}
-- ++(-225:0.6) node[bead] {\color{red}1}
-- ++(-255:0.6) node[bead] {0};

\draw[->, thick] (2.6, 0) -- (5.7, 0);

\draw (6,0)
-- ++(60:1) node[bead] {0}
-- ++(0:1) node[bead] {0}
-- ++(-60:1) node[bead] {1}
-- ++(-120:1) node[bead] {0}
-- ++(-180:1) node[bead] {1}
-- ++(-240:1) node[bead] {0};

\draw[->, thick] (8.3, 0) -- (11.2, 0);

\node[draw,text width=1.1cm] at (12,0) {010001};
\end{tikzpicture}
\caption{An example of a circular trace. We start with an unknown circular string (top left). Each bit of the string is randomly deleted (red bits are deleted, black bits are retained) and the order of the retained bits is preserved, so we are left with the smaller circular string. However, since there is no beginning or end of the circular string, we assume the string is seen in clockwise order starting from a randomly chosen bit.}
\end{figure}

\subsection{Main Results and Comparison to Linear Trace Reconstruction}

Perhaps the first natural question about circular trace reconstruction is the following: how does the sample complexity of circular trace reconstruction compare to the sample complexity of standard (linear) trace reconstruction? Intuitively, one should expect circular trace reconstruction to be at least as difficult as standard trace reconstruction, since given any trace of a linear string, we can randomly rotate it to get a trace of the corresponding circular string. 
This reasoning, however, is slightly flawed. For instance, if we wish to distinguish between two strings $x$ and $y$ which are different as linear strings but equivalent up to a cyclic shift, then one cannot distinguish between traces of random rotations of $x$ and traces of random rotations of $y$. However, by padding the trace with extra bits before randomly rotating, one can show that circular trace reconstruction is at least as hard as linear trace reconstruction in both the worst-case and average-case. Indeed, we have the following proposition -- as its proof is quite simple, we defer it to Appendix \ref{Omitted}.

\begin{proposition} \label{CircularHarderThanLinear}
    Suppose that we can solve worst-case circular trace reconstruction over length $m$ strings with deletion probability $q$ using $T_1(m, q)$ traces. Then, we can solve worst-case linear trace reconstruction over length $n$ strings with deletion probability $q$ using $\min_{m \ge 2n} T_1(m, q)$ traces.
    
    Likewise, suppose that we can solve average-case circular trace reconstruction over length $m$ strings with deletion probability $q$ using $T_2(m, q)$ traces. Then, we can solve average-case linear trace reconstruction over length $n$ strings with deletion probability $q$ using $\min_{m \ge 2n} T_2(m, q)$ traces.
\end{proposition}

Given Proposition \ref{CircularHarderThanLinear}, any upper bounds for circular trace reconstruction imply nearly equivalent upper bounds for the linear trace reconstruction, and any lower bounds for linear trace reconstruction imply nearly equivalent lower bounds for circular trace reconstruction. This raises two natural questions. First, can we match or nearly match the best linear trace reconstruction upper bounds for circular trace reconstruction? Second, can we beat the best linear trace reconstruction lower bounds for circular trace reconstruction?

\medskip


The first main result we prove is for worst-case circular strings. The best known upper bound for worst-case linear trace reconstruction with deletion probability $q$, where $q$ is a fixed constant between $0$ and $1$, is $\exp\left(O(n^{1/3})\right),$ where the unknown string has length $n$ \cite{DeOS17, NazarovP17}. Our first main result, proven in Section \ref{WorstCase}, provides a nearly matching upper bound for the circular trace reconstruction problem, but only if the length $n$ has at most $2$ prime factors.

\begin{theorem} \label{WorstCaseThm}
    Let $x$ be an unknown, arbitrary circular string of length $n$, let $q$ be the deletion probability of each element in the string, and let $p = 1-q$ be the retention probability. Then, if $n$ is either a prime or a product of two (possibly equal) primes, using $\exp\left(O\left(n^{1/3} (\log n)^{2/3} p^{-2/3}\right)\right)$ random traces, we can determine $x$ with failure probability at most $2^{-n}.$
\end{theorem}

The primary reason why our theorem fails for $n$ having $3$ or more prime factors is that we prove the following number theoretic result which is crucial in our algorithm.

\begin{theorem} \label{NT:Main}
    For any fixed integer $n \ge 2,$ the following statement is true \textbf{if and only if} $n$ has at most $2$ prime factors, counting multiplicity. 
    
    Define $\omega := e^{2 \pi i/n}$, and suppose that $a_0, \dots, a_{n-1}, b_0, \dots, b_{n-1}$ are all integers in $\{0, 1\}.$ Also, suppose that for all $0 \le k \le n-1,$ there is some integer $c_k$ such that $\sum a_i \omega^{i \cdot k} = \omega^{c_k} \cdot \sum b_i \omega^{i \cdot k}.$ Then, the sequences $\{a_i\}$ and $\{b_i\}$ are cyclic shifts of each other.
\end{theorem}

   

The next main result we prove is for average-case circular strings: we show that a random circular string can be recovered using a polynomial number of traces. Formally, we prove the following theorem, done in section \ref{AverageCase}.

\begin{theorem}\label{AverageCaseThm}
Let $x$ be an unknown but randomly chosen circular string of length $n$ and let $0 < q < 1$ be the deletion probability of each element. Then, there exists a constant $C_q$ depending only on $q$ such that we can determine $x$ with failure probability at most $n^{-10}$ using $O(n^{C_q})$ traces.
\end{theorem}

The main lemma we need to prove Theorem \ref{AverageCaseThm} is actually a result that is true for worst-case strings. Specifically, we show how to recover the multiset of all consecutive substrings of length $O(\log n)$ using a polynomial number of strings. While this does not guarantee that we can recover an arbitrary circular string, it does allow us to recover what we will call \emph{regular strings}, which we show comprise the majority of circular strings. The following lemma may be of independent interest for studying worst-case strings as well, as it allows one to gain information about all ``consecutive chunks'' of the unknown string using only a polynomial number of queries.

\begin{lemma} \label{Contiguous}
    Let $x = x_1 \cdots x_n$ be an arbitrary circular string of length $n$ and let $0 < q < 1$ be the deletion probability of each element. Then, for $k = 100 \log n,$ we can recover the multiset of all substrings $\{x_i x_{i+1} \cdots x_{i+k-1}\}_{i = 1}^{n}$, where indices are modulo $n$, using $O(n^{C_q})$ traces with failure probability $n^{-10}$, where $C_q$ is a constant that only depends on $q$.
\end{lemma}

The best known upper bound for average-case linear trace reconstruction is only $\exp\left(O((\log n)^{1/3})\right)$ \cite{HoldenPP18}. Unfortunately, we were not able to adapt their argument to circular strings. One major reason why we are unable to do so is that in the argument of \cite{HoldenPP18} (as well as \cite{PeresZ17}, which provides an $\exp\left(O((\log n)^{1/2})\right)$ sample algorithm), the authors recover the $(k+1)^{\text{st}}$ bit of the string assuming the first $k$ bits are known using a small number of traces, and by reusing traces, they inductively recover the full string. However, since we are dealing with circular strings, even recovering the ``first'' bit does not make much sense. However, we note that even a polynomial-sample algorithm is quite nontrivial. In the linear case, a polynomial-sample algorithm for average-case strings was first proven by \cite{HolensteinMPW08}, and their algorithm only worked as long as the deletion probability $q$ was at most some small constant, which when optimized is only about $0.07$ \cite{PeresZ17}.

\medskip

Our final main result regards lower bounds for worst-case strings. For linear worst-case strings, the best known lower bound for trace reconstruction is $\tilde{\Omega}(n^{3/2})$ \cite{Chase19}. For circular trace reconstruction, we show an improved lower bound of $\Omega(n^3)$, although the proof of our lower bound is actually much simpler and cleaner than those of the known lower bounds for standard trace reconstruction \cite{Chase19, HoldenL18}. Specifically, we prove the following theorem, done in Section \ref{LowerBound}:

\begin{theorem} \label{LowerThm}
    Let $n \ge 1,$ $2 \le k \le 4$, and let $x$ be the string $10^{n}10^{n+1}10^{n+k} = 1 \underbrace{0 \dots 0}_{n \text{ times}} 1 \underbrace{0 \dots 0}_{n+1 \text{ times}} 1 \underbrace{0 \dots 0}_{n+k \text{ times}}.$ Likewise, let $y$ be the string $y = 10^{n}10^{n+k}10^{n+1}.$ Then, the strings $x, y$ are not equivalent up to cyclic rotations, but for any constant deletion probability $q$, one requires $\Omega(n^3/\log^3n)$ random traces to distinguish between the original string being $x$ or $y$. Thus, for all integers $n$, worst-case circular trace reconstruction requires at least $\tilde{\Omega}(n^3)$ random traces.
\end{theorem}

\subsubsection{Concurrent Work}

We note that a very similar statement to Lemma \ref{Contiguous}, but for linear strings, was proven in independent concurrent work by Chen et. al. \cite[Theorem 2]{ChenDLSS20}, which provides a polynomial-sample algorithm for a ``smoothed'' variant of worst-case linear trace reconstruction. Many ideas in our proof of Lemma \ref{Contiguous} and their proof appear to overlap, though our proof is substantially shorter.

\subsection{Motivation and Relation to Other Work}

From a theoretical perspective, circular trace reconstruction can bring many novel insights to the theory of reconstruction algorithms, some of which may be useful even in the standard trace reconstruction problem. For instance, the proof of Theorem \ref{WorstCaseThm} combines analytic, statistical, and combinatorial approaches as in previous trace reconstruction papers, but now also uses ideas from number theory and results about cyclotomic integers. To the best of our knowledge, this paper is the first paper on trace reconstruction that utilizes number theoretic ideas, though there is work on other problems about cyclic strings that uses ideas from number theory. Also, Lemma \ref{Contiguous} shows a way to recover all contiguous sequences in the original string of length $O(\log n)$ for arbitrary circular strings, which is a new result even in the linear case (concurrent with \cite{ChenDLSS20}) and has applications to problems in linear trace reconstruction (as done in \cite{ChenDLSS20}).

From an applications perspective, trace reconstruction is closely related to the multiple sequence alignment problem in computational biology. In the multiple sequence alignment problem, one is given DNA sequences from several related organisms, and the goal is to align the sequences to determine what mutations each descendant underwent from their common ancestor: the trace reconstruction problem is analogous to actually recovering the common ancestor. See \cite{BatuKKM04} for more about the relation between multiple sequence alignment and trace reconstruction.

The multiple sequence alignment problem is also a key motivation for studying circular trace reconstruction. Many important types of DNA, such as mitochondrial DNA in humans and other eukaryotes, chloroplast DNA, bacterial DNA, and DNA in plasmids, are predominantly circular (see, e.g., \cite[pp. 313, 397, 516-517]{Campbell}, or \cite{Wikipedia}). Therefore, understanding circular trace reconstruction could prove useful in reconstructing ancestral sequences for mitochondrial or bacterial DNA. Another problem in computational biology that trace reconstruction may be applicable to is the DNA Data Storage problem, where data is stored in DNA and can be recovered through sequencing, though the stored DNA may mutate over time \cite{ChurchGK12, OrganickAC18}. Recently, long-term DNA data storage in plasmids has been successfully researched \cite{NguyenPP18}, which further motivates the study of circular trace reconstruction.

\medskip

Besides the linear trace reconstruction problem, circular trace reconstruction is also closely related to the problem of population recovery from the deletion channel \cite{BanCFSS19, BanCSS19, Narayanan20}, where the goal is to recover an unknown mixture of $\ell$ strings from random traces. Indeed, receiving traces from a circular string is equivalent to receiving traces from a uniform mixture of a linear string along with all of its cyclic shifts, so circular trace reconstruction can be thought of as an instance of population recovery from the deletion channel with mixture size $\ell = n$.

Unfortunately, the best known algorithm for population recovery over worst-case strings requires $\exp\left(\tilde{O}(n^{1/3}) \cdot \ell^2\right)$ traces \cite{Narayanan20}, which is not useful if $\ell = n$. However, to prove our worst-case upper bound, we will use ideas based on \cite{DeOS17, NazarovP17, Narayanan20} to estimate certain polynomials that depend on the unknown circular string $x$. For the average case problem, i.e. if given a mixture over $\ell$ random strings, population recovery can be done with $\text{poly}\left(\ell, \exp\left((\log n)^{1/3})\right)\right)$ random traces. While this seemingly implies a $\text{poly}(n)$-sample algorithm for average-case circular trace reconstruction, the $n$ cyclic shifts of the circular string are quite similar to each other and thus do not behave like a collection of $n$ independent random strings. Indeed, our techniques for average-case circular trace reconstruction are very different from those developed in \cite{BanCSS19}.

While circular strings have not been studied before in the context of trace reconstruction, people have studied circular strings and cyclic shifts in the context of edit distance \cite{Maes90, AndoniGMP13}, multi-reference alignment \cite{BandeiraCSZ14, BandeiraWR19, PerryWBRS19}, and other pattern matching problems \cite{CKPRRSWZ21}. We note that \cite{AndoniGMP13} also applies results from number theory and about cyclotomic polynomials, though the techniques overall are not very similar to ours.

\subsection{Proof Overview}

In this subsection, we highlight some of the ideas used in Theorems \ref{WorstCaseThm}, \ref{AverageCaseThm}, and \ref{LowerThm}.

The proof of Theorem \ref{WorstCaseThm} is partially based on ideas from \cite{DeOS17, NazarovP17, Narayanan20}. In \cite{DeOS17, NazarovP17}, the authors consider two strings $x, y \in \{0, 1\}^n$ and show how to distinguish between random traces of $x$ and random traces of $y$. To do so, they construct an unbiased estimator for $P(z; x) := \sum x_i z^i$ (or $P(z; y) = \sum y_i z^i$) solely based on the random trace of either $x$ or $y$, for some $z \in \mathbb C$. By showing that the unbiased estimator is never ``too'' large and that $P(z; x)$ and $P(z; y)$ differ enough for an appropriate choice of $z$, they can estimate this quantity using many random traces to distinguish between $x$ and $y$. Unfortunately, in our case, applying the same estimator will give us an unbiased estimator for $P'(z; x) := \mathbb E_i[P(z; x^{(i)})],$ where $x^{(i)}$ is the $i$th cyclic shift of $x$: it turns out that $P(z; x) = P(z; y)$ as polynomials in $z$ even if $x, y$ have the same number of $1$'s. Our goal will then be to establish some other polynomial $Q(z; x)$ such that we can construct a good unbiased estimator, but at the same time $Q'(z; x) := \mathbb E_i[Q(z; x^{(i)})]$ and $Q'(z; y) := \mathbb E_i[Q(z; y^{(i)})]$ are distinct polynomials for any distinct cyclic strings $x, y$. We show that the polynomial $Q(z; x) := z^{kn} P(z; x)^k P(z^{-k}; x)$ will do the job, for some some small integer $k$. We provide a (significantly more complicated) unbiased estimator of $Q(z; x)$ using a random trace: the construction is similar to that of \cite{Narayanan20}, which shows how to estimate $P(z; x)^k$ for some integer $k$. To show that $Q(z; x) \neq Q(z; y)$ as polynomials, we first show that $P(z; x)^k P(z^{-k}; x)$ has the special property that if $z$ is a cyclotomic $n$th root of unity, this polynomial is in fact invariant under cyclic shifts! Thus, it just suffices to show that if $x, y \in \{0, 1\}^n$ are not cyclic shifts of each other, there is some $n$th root of unity $\omega$ such that $P(\omega; x)^k P(\omega^{-k}; x) \neq P(\omega; y)^k P(\omega^{-k}; y).$ This will require significant number theoretic computation, and will be true as long as $n$ is a prime or a product of two primes.

The bulk of the proof of Theorem \ref{AverageCaseThm} will be proving Lemma \ref{Contiguous}, which reconstructs all consecutive substrings of length $100 \log n$ in the unknown circular string $x$. For a random string $x$, these substrings will all be sufficiently different, so once we know the substrings, we can reconstruct the full string because there is only one way to ``glue'' together the substrings. Therefore, we focus on explaining the ideas for Lemma \ref{Contiguous}. Our goal will be to determine how many times a string $s$ appears consecutively in $x$ for each string $s$ of length $100 \log n$. For an unknown string $x$ and $i$ between $0$ and $n- 100 \log n,$ we let $c_i$ be the number of times $s$ appears in some contiguous block of length $i + 100 \log n$ in $x$. Then, a basic enumerative argument shows that for a random (cyclically shifted) trace $\tilde{x} = \tilde{x}_1 \tilde{x}_2 \cdots \tilde{x}_m,$ the probability that $\tilde{x}_1 \cdots \tilde{x}_{100 \log n}$ can be written as $\sum_{i \ge 0} c_i (1-q)^{100 \log n} q^i,$ and we wish to recover $c_0$. The $(1-q)^{100 \log n}$ term is a constant that equals $1/\text{poly}(n),$ so it is easy to recover an approximation to $\sum_{i \ge 0} c_i q^i$. We truncating this polynomial at an appropriate degree (approximately $C \log n$ for some large $C$) and show that the truncated polynomial $\sum_{i = 0}^{C \log n} c_i x^i$ is very close to the original polynomial, but differs from $\sum_{i = 0}^{C \log n} c_i' x^i$ for some $x \in [q, (1-q)/2]$ by a significant amount, if $c_0' \neq c_0,$ using ideas based on \cite{BorweinEK99}. We can also simulate a trace with deletion probability $x > q$ by taking a ``trace of the trace.'' This will be sufficient in determining $c_0$, and therefore, the (multi)-set of all consecutive substrings of length $100 \log n$.

The proof of Theorem \ref{LowerThm} proceeds by showing that the laws of the traces of $x=10^n10^{n+1}10^{n+k}$ and $y=10^n10^{n+k}10^{n+1}$ are close to each other in the sense of Hellinger distance and concluding by a lemma in \cite{HoldenL18} that was used in a similar fashion to show a lower bound for linear trace reconstruction. It is first shown that conditioned on a $1$ being deleted, a trace from $x$ is equidistributed as a trace from $y$. Then explicit expressions for the probabilities that the trace is $10^a10^b10^c$ are computed and compared, yielding an upper bound on the Hellinger distance. The difference between the probabilities for $x$ and $y$ is proportional to the product of $(a-b)(b-c)(a-c)$ and a symmetric polynomial in $a,b,c$. Both $x$ and $y$ consist of three $1$'s separated by runs of $0$'s of approximate length $n$, so with high probability we have that $a,b,c$ are approximately $np$, with square root fluctuations. The contribution of the $(a-b)(b-c)(a-c)$ term allows us to recover a $\tilde\Omega(n^3)$ bound.

\section{Preliminaries}


First, we explain a basic definition we will use involving complex numbers.

\begin{defn}
    For $z \in \mathbb C,$ let $|z|$ be the \emph{magnitude} of $z$, and if $z \neq 0$, let $\arg z$ be the \emph{argument} of $z$, which is the value of $\theta \in (-\pi, \pi]$ such that $\frac{z}{|z|} = e^{i \theta}$.
\end{defn}

Next, we state a Littlewood-type result about bounding polynomials on arcs of the unit circle.

\begin{theorem} \textup{\cite{BorweinE97}} \label{Littlewood}
    Let $f(z) = \sum_{j = 0}^{n} a_j z^j$ be a nonzero polynomial of degree $n$ with complex coefficients. Suppose there is some positive integer $M$ such that $|a_0| \ge 1$ and $|a_j| \le M$ for all $0 \le j \le n$. Then, if $A$ is an arc of the unit circle $\{z \in \mathbb C: |z| = 1\}$ with length $0 < a < 2 \pi$, there exists some absolute constant $c_1 > 0$ such that
\[\sup\limits_{z \in A} |f(z)| \ge \exp\left(\frac{-c_1 (1 + \log M)}{a}\right).\]
\end{theorem}


   

Next, we state two well known results about roots of unity in cyclotomic fields.

\begin{lemma} \label{GaloisConjugate} \cite{Marcus}
    Let $\omega = e^{2 \pi i/n}$. Then, the set of $\{\omega^k\}$ for $k \in \mathbb Z, \gcd(k, n) = 1$ are all \emph{Galois conjugates}. This means that if $P(x)$ is an integer polynomial, then $P(\omega^k) = 0$ if and only if $P(\omega) = 0$ for any $k \in \mathbb Z$ with $\gcd(k, n) = 1.$ Moreover, $P(\omega) = 0$ if and only if $P$ is a multiple of the $n$th \emph{Cyclotomic polynomial}.
\end{lemma}

\begin{lemma} \label{RootsOfUnity} \cite{Marcus}
    Let $\omega = e^{2 \pi i/n}$ be an $n$th root of unity, and let $\mathbb Q[\omega]$ be the $n$th degree cyclotomic field. Then, if $z \in \mathbb Q[\omega]$ such that $z^r = 1$ for some integer $r \ge 1,$ $z$ must equal $\omega^k$ or $-\omega^k$ for some integer $k$.
\end{lemma}

Finally, we define the Hellinger distance between two probability measures and state a folklore bound on distinguishing between distributions based on samples in terms of the Hellinger distance.

\begin{defn}
    Let $\mu$ and $\nu$ be discrete probability measures over some set $\Omega.$ In other words, for $x \in \Omega$, $\mu(x)$ is the probability of selecting $x $ when drawing from the measure $\mu.$ Then, the Hellinger distance is defined as 
\[d_H(\mu, \nu) = \left(\sum_{x \in \Omega} \left(\sqrt{\mu(x)}-\sqrt{\nu(x)}\right)^2\right)^{1/2}.\]
\end{defn}

The following proposition is quite well-known (see for instance, \cite[Lemma A.5]{HoldenL18}).

\begin{proposition}
    If $\mu, \nu$ are discrete probability measures, then if given i.i.d. samples from either $\mu$ or $\nu$, one must see at least $\Omega(d_H(\mu, \nu)^{-2})$ i.i.d. samples to determine whether the distribution is $\mu$ or $\nu$ with at least $2/3$ success probability.
\end{proposition}

\section{Worst Case: Upper Bound} \label{WorstCase}



In this section, we prove Theorem \ref{WorstCaseThm}, i.e., we provide an $\exp\left(\tilde{O}(n^{1/3})\right)$-sample algorithm for circular trace reconstruction when the length $n$ is a prime or product of two primes.

For a (linear) string $x \in \{0, 1\}^n$ and $z \in \mathbb C,$ we define $P(z; x) := \sum_{i = 1}^{n} x_i z^i.$ The first lemma we require creates an unbiased estimator for $\prod_{i = 1}^{m} P(z_i; x)$ for some complex numbers $z_1, \dots, z_m,$ using only random traces of $x$. The proof of the following lemma greatly resembles the proof of \cite[Lemma 4.1]{Narayanan20}, so we defer the proof to Appendix \ref{Omitted}.

\begin{lemma} \label{CreatingG}
    Let $x$ be a linear string of length $n$. Fix $q$ as the deletion probability and $p = 1-q$ as the retention probability. Then, for any integer $m \ge 1$ and any $Z = (z_1, \dots, z_m)$ for $z_1, \dots, z_m \in \mathbb C,$ there exists some function $g_m(\tilde{x}, Z)$ such that
\[\mathbb E_{\tilde{x}}[g_m(\tilde{x}, Z)] = \prod_{k = 1}^{m} \left(\sum_{i = 1}^{n} x_i z_k^i\right),\]
    where the expectation is over traces drawn from $x$. Moreover, for any $L \ge 1,$ and for all $\tilde{x} \in \{0, 1\}^n$ and all $Z$ such that $|z_1|, \dots, |z_m| = 1$ and $|\arg z_i| \le \frac{1}{L}$ for all $1 \le i \le m,$ 
\[|g_m(\tilde{x}, Z)| \le (p^{-1} m n)^{O(m)} \cdot e^{O(m^2n/(p^2L^2))}.\]
\end{lemma}

For $x \in \{0, 1\}^n$ and $z \in \mathbb C,$ let $P(z; x) := \sum_{i = 1}^{n} x_i z^i.$ Our main goal will be to determine the value of $f_t(z; x) := P(z; x)^t \cdot P(z^{-t}; x)$ for some integer $t$, where $z$ is an $n$th root of unity. Importantly, we note that $f_t(z; x)$ is invariant under rotations of $x$, since for $z = e^{2 \pi i k/n},$
\[\sum_{i = 1}^{n} x_{(i+1) \Mod n} z^i = \sum x_i z^{i-1} = P(z; x) \cdot z^{-1}\]
whereas
\[\sum_{i = 1}^{n} x_{(i+1) \Mod n} z^{-t \cdot i} = \sum x_i z^{-t(i-1)} = P(z^{-t}; x) \cdot z^{t}\]
Therefore, if we define $x^{(j)}$ as the string $x$ rotated by $j$ places (so $x^{(j)}_i = x_{(i+j) \Mod n}$), then $f(z; x) = f(z; x^{(j)})$ for all $z = e^{2 \pi i k/n}$ and $0 \le j \le n-1.$

Now, choose some $z$ with $|z| = 1$ and $|\arg z| \le \frac{1}{L}$. Also, fix some integer $t$, let $m = t+1,$ and let $Z = ( \underbrace{z, \dots, z}_{t \text{ times}}, z^{-t}).$ Then, if $j$ is randomly chosen in $\{0, 1, \dots, n-1\}$ and $\tilde{x}$ is a random trace,
\[\mathbb E_{\tilde{x}}[n z^{tn} \cdot g_m(\tilde{x}, Z)] = (n \cdot z^{tn}) \cdot \left(\frac{1}{n} \cdot \sum_{j = 0}^{n-1} P(z; x^{(j)})^t \cdot P(z^{-t}; x^{(j)})\right) = \sum_{j = 0}^{n-1} z^{tn} \cdot P(z; x^{(j)})^t \cdot P(z^{-t}; x^{(j)}).\]
Note that $\sum_{j = 0}^{n-1} z^{t n} \cdot P(z; x^{(j)})^t \cdot P(z^{-t}; x^{(j)})$ is a polynomial of $z$ of degree at most $(t+1)n$ and all coefficients bounded by $n^{t+1}$. We write this polynomial as $Q_t(z; x).$ Thus, if we define $h_t(\tilde{x}, z) := n z^{tn} g_{m}(\tilde{x}, Z),$ we have that $\mathbb E_{\tilde{x}}[h_t(\tilde{x}, z)] = Q(z; x)$ for $\tilde{x}$ a trace of a randomly shifted $x$, and that $|h_t(\tilde{x}; z)| \le (p^{-1} t n)^{O(t)} \cdot e^{O(t^2n/(p^2L^2))}$ whenever $|z| = 1$ and $|\arg z| \le \frac{1}{L}$ for $L \ge 2,$ since $m = t+1.$

Now, we will state two important results that will lead to the proof of the main result.

\begin{lemma} \label{Arc}
    Let $n \ge 2,$ and suppose that $x, x'$ are strings in $\{0, 1\}^n$ such that $Q_t(z; x) \neq Q_t(z; x')$ as polynomials in $z.$ Then, there is a uniform constant $c_2$ such that for any $L \ge 2,$ there exists $z$ such that $|z| = 1,$ $|\arg z| \le \frac{1}{L},$ and
\[|Q_t(z; x) - Q_t(z; x')| \ge n^{-c_2 t L}.\]
\end{lemma}

\begin{proof}
    Note that $Q_t(z; x) - Q_t(z; x')$ is a nonzero polynomial in $z$ of degree at most $(t+1)n$ and with all coefficients bounded by $2n^{t+1}.$ Therefore, by Theorem \ref{Littlewood},
\[\sup_{|z| = 1, |\arg z| \le 1/L} |Q_t(z; x) - Q_t(z; x')| \ge \exp\left(-\frac{c_1 (1 + \log (2n^{t+1}))}{2/L}\right) \ge \exp\left(-c_2 \cdot L \cdot t \cdot \log n\right) = n^{-c_2 t L},\]
    where we note that the arc $\{z: |z| = 1, |\arg z| \le \frac{1}{L}\}$ has length $\frac{2}{L}.$
\end{proof}

The next important result we need will be Theorem \ref{NT:Main}. We defer the full proof of Theorem \ref{NT:Main} to Subsection \ref{NT:Subsection}, but as the proof of the case where $n$ is prime is simpler, we prove this special case here. Using this, we can get an $\exp\left(\tilde{O}(n^{1/3})\right)$ sample upper bound at least for $n$ prime.

\begin{proposition} \label{NT:Prime}
    Suppose that $n = p$ is prime, and $a_0, \dots, a_{n-1}, b_0, \dots, b_{n-1} \in \{0, 1\}$ such that for all $0 \le k < p,$ there is some integer $c_k$ such that $\sum_{i = 0}^{p-1} a_i = \omega^{c_k} \cdot \sum_{i = 0}^{p-1} b_i.$ Then, the sequences $\{a_1, \dots, a_n\}$ and $\{b_1, \dots, b_n\}$ are equivalent up to a cyclic permutation.
\end{proposition}

\begin{proof}
    First, $\sum_{i = 0}^{p-1} a_i = \omega^{c_0} \cdot \sum_{i = 0}^{p} b_i$. Since $\sum_{i = 0}^{p-1} a_i$ and $\sum_{i = 0}^{p-1} b_i \ge 0$ are both positive real numbers, and since $\omega^{c_0}$ is a root of unity, we must have that $\sum_{i = 0}^{p-1} a_i = \sum_{i = 0}^{p-1} b_i$. In the case $p = 2,$ this alone proves the proposition, so we now assume $p$ is odd.
    
        Now, we have that $\sum_{i = 0}^{p-1} a_i \omega^i = \omega^{c_1} \cdot \sum_{i = 0}^{p-1} b_i \omega^i$. Letting $b'_i = b_{(i-c_1) \Mod p}$, we have that $b'$ is a cyclic shift of $b$, and $\sum_{i = 0}^{p-1} a_i = \sum_{i = 0}^{p-1} b'_i$ and $\sum_{i = 0}^{p-1} a_i \omega^i = \sum_{i = 0}^{p-1} b'_i \omega^i.$ Letting $Q(x) = \sum_{i = 0}^{p-1} (a_i-b'_i) x^i,$ we have that $\omega$ and $1$ are both roots of $Q(x)$. Since $Q(x)$ is an integer-valued polynomial, this implies that all Galois conjugates of $\omega$ are roots, so $1, \omega, \omega^2, \dots, \omega^{p-1}$ are roots of $Q(x).$ Thus, $x^p-1$ divides $Q(x).$ But since $Q(x)$ has degree at most $p-1,$ $Q(x)$ must equal $0$, so $a_i = b'_i$ for all $i$. Since the sequence $b'$ is just a shift of $b$, we are done.
\end{proof}

Finally, we are ready to Prove Theorem \ref{WorstCaseThm}.

\begin{proof}[Proof of Theorem \ref{WorstCaseThm}]
    Let $L = \Theta(n^{1/3} (\log n)^{-1/3} p^{-2/3}),$ and suppose that we are trying to distinguish between the original circular string being $a = a_1 a_2 \cdots a_n$ or $b = b_1 b_2 \cdots b_n,$ where $a, b$ are distinct, even up to cyclic shifts. First, we claim that for some $0 \le \ell \le n-1$, some $2 \le t \le 5,$ and $z = \omega^{\ell}$, we have that $P(z; a)^t P(z^{-t}; a) \neq P(z; b)^t P(z^{-t}; b),$ where we recall that $\omega := e^{2 \pi i/n}.$
    
    To prove this, first choose $k$ such that $\sum_{i = 1}^{n} a_i \omega^{i \cdot k} \neq \omega^{c_k} \cdot \sum_{i = 1}^{n} b_i \omega^{i \cdot k}$ for all integers $c_k,$ which exists by Theorem \ref{NT:Main}. If $k = 0,$ then $P(\omega^k; a) = P(1; a)$ and $P(\omega^k; b) = P(1; b)$ are distinct nonnegative integers, so we trivially have $P(1; a)^t P(1; a) \neq P(1; b)^t P(1; b).$ Otherwise, let $t$ be the smallest prime that doesn't divide $\frac{n}{\gcd(n, k)}$ (so $t \le 5$ as $n$ has at most $2$ prime factors). If $\sum_{i = 1}^{n} a_i \omega^{i \cdot k} = 0,$ then $\sum_{i = 1}^{n} b_i \omega^{i \cdot k} \neq 0.$ Now, since $\omega^{-tk}$ is a Galois conjugate of $\omega^k$ (since $t \nmid n$), we also have that $\sum_{i = 1}^{n} b_i \omega^{-ti \cdot k} \neq 0.$ This means that $P(\omega^k; a) = 0$ so $P(\omega^k; a)^t P((\omega^k)^{-t}; a) = 0,$ but $P(\omega^k; b)^t P((\omega^k)^{-t}; b) \neq 0$. Likewise, if $\sum_{i = 1}^{n} b_i \omega^{i \cdot k} = 0,$ we'll have $P(\omega^k; a)^t P((\omega^k)^{-t}; a) \neq 0,$ but $P(\omega^k; b)^t P((\omega^k)^{-t}; b) = 0$.
    
    Otherwise, $P(\omega^k; a) = \sum_{i = 1}^{n} a_i \omega^{i \cdot k}$ and $P(\omega^k; b) = \sum_{i = 1}^{n} b_i \omega^{i \cdot k}$ are both nonzero. This means that for all $r \ge 0,$ $P(\omega^{(-t)^r \cdot k}; a)$ and $P(\omega^{(-t)^r \cdot k}; b)$ are both nonzero, since $\omega^{(-t)^r \cdot k}$ and $\omega^k$ are Galois conjugates. This means that if $P(z; a)^t P(z^{-t}; a) = P(t; b)^2 P(z^{-t}; b)$ for all $z = \omega^{(-t)^r \cdot k},$ then 
\[\frac{P(\omega^{(-t)^{r+1} \cdot k}; a)}{P(\omega^{(-t)^r \cdot k}; a)^{-t}} = \frac{P(z^{-t}; a)}{P(z; a)^{-t}} = \frac{P(z^{-t}; b)}{P(z; b)^{-t}} = \frac{P(\omega^{(-t)^{r+1} \cdot k}; b)}{P(\omega^{(-t)^r \cdot k}; b)^{-t}}\]
    for all $r \ge 0,$ so we inductively have that
\[\frac{P(\omega^{(-t)^r \cdot k}; a)}{P(\omega^k; a)^{(-t)^r}} = \frac{P(\omega^{(-t)^r \cdot k}; b)}{P(\omega^k; b)^{(-t)^r}}.\]
    Now, letting $r = \varphi\left(\frac{n}{\gcd(n, k)}\right),$ we know that $k \cdot (-t)^r \equiv k \Mod n$ by Euler's theorem, which means that $\omega^{(-t)^r \cdot k} = \omega^k.$ Thus,
\[P(\omega^k; a)^{1 - (-t)^r} = P(\omega^k; b)^{1 - (-t)^r}.\]
    Since $k \neq 0,$ we have that $\frac{n}{\gcd(n, k)} > 1$ so $r \ge 1.$ Thus, since $t \ge 2,$ $1-(-t)^r \neq 0.$ Now, since $P(\omega^k; a), P(\omega^k; b)$ are nonzero, we have that $\frac{P(\omega^k; a)}{P(\omega^k; b)}$ is a $|1-(-t)^r|^{\text{th}}$ root of unity. Also, $P(\omega^k; a), P(\omega^k; b) \in \mathbb Q[\omega],$ which means $\frac{P(\omega^k; a)}{P(\omega^k; b)} \in \mathbb Q[\omega]$. However, all roots of unity in $\mathbb Q[\omega]$ are of the form $\pm \omega^i$ for some $i$, and since $(-t)^{r}-1$ is odd if $n$ is odd (since $t = 2$), we must have that $\frac{P(\omega^k; a)}{P(\omega^k; b)} = \omega^{c_k}$ for some integer $c_k.$ This is a contradiction, so we must have that $P(z; a)^t P(z^{-t}; a) \neq P(z; b)^t P(z^{-t}; b),$ for some $z = \omega^{(-t)^r \cdot k}$, $r \ge 0$.
    
    Next, as we have already noted, $P(z; a)^t P(z^{-t}; a)$ is invariant under rotation of $a$, and $P(z; b)^t P(z^{-t}; b)$ is invariant under rotation of $b.$ Thus, by our definition of $Q_t(z; x),$ we have that $Q_t(z; a) \neq Q_t(z; b).$ Thus, by Lemma \ref{Arc}, there is some $z$ such that $|z| = 1, |\arg z| \le \frac{1}{L}$, and
\[|Q_t(z; a) - Q_t(z; b)| \ge n^{-c_2 t L} \ge n^{-5 c_2 L}.\]
    Therefore, for $L = \Theta(n^{1/3} (\log n)^{-1/3} p^{-2/3}),$ there exists some $z$ with $|z| = 1$ and $|\arg z| \le \frac{1}{L}$ and some $2 \le t \le 5$ such that
\[|Q_t(z; a) - Q_t(z; b)| \ge n^{-5 c_2 L} \ge \exp\left(-c_3 \cdot n^{1/3} (\log n)^{2/3} p^{-2/3}\right)\]
    but
\[|h_t(\tilde{x}, z)| \le (p^{-1} n)^{O(1)} \cdot \exp\left(O\left(\frac{n}{p^2 L^2}\right)\right) \le \exp\left(c_4 \cdot n^{1/3} (\log n)^{2/3} p^{-2/3}\right).\]
    Therefore, by choosing $z$ and $t$ appropriately, taking $R = \exp\left(O\left(n^{1/3} (\log n)^{2/3} p^{-2/3}\right)\right)$ traces $\tilde{x}^{(1)}, \dots, \tilde{x}^{(R)}$, and letting $h_t(z)$ denote the average of $h_t(\tilde{x}^{(i)}, z)$ for all $i$, the Chernoff bound tells us that with probability at least $1-10^{n},$ $|h_t(z) - Q_t(z; a)| \le \frac{1}{3} \cdot \exp\left(c_4 \cdot n^{1/3} (\log n)^{2/3} p^{-2/3}\right)$ if the original string were $a,$ and $|h(z) - Q_t(z; b)| \le \frac{1}{3} \cdot \exp\left(c_4 \cdot n^{1/3} (\log n)^{2/3} p^{-2/3}\right)$ if the original string were $b.$ Thus, by returning $a$ if $h(z)$ is closer to $Q_t(z; a)$ and returning $b$ otherwise, we can distinguish between the original string being $a$ or $b$ using $\exp\left(O\left(n^{1/3} (\log n)^{2/3} p^{-2/3}\right)\right)$ traces, with $1-10^n$ failure probability.
    
    Thus, to reconstruct the original string $x$, we simply run the distinguishing algorithm for all pairs $a, b \in \{0, 1\}^n$ such that $a \neq b,$ using the same $R$ traces $\tilde{x}^1, \dots, \tilde{x}^R.$ With probability at least $1 - (4/10)^n \ge 1 - 2^{-n},$ the true string $x$ will be the only string such that the distinguishing algorithm will successfully choose $x$ over all other strings. Thus, for $n$ a prime or a product of two primes, the circular trace reconstruction problem can be solved using $\exp\left(O\left(n^{1/3} (\log n)^{2/3} p^{-2/3}\right)\right)$ traces.
\end{proof}

\iffalse
\subsection{Proof of Theorem \ref{Main2}}

We adopt a similar approach to the proof of Theorem \ref{WorstCaseThm}, but now look at $Z = (z_1, z_2, z_1^{-1} z_2^{-1}).$ This time, if $j$ is randomly chosen in $\{0, 1, \dots, n-1\}$ and $\tilde{x}$ is a random trace,
\[\mathbb E_{\tilde{x}}[n z_1^nz_2^n \cdot g_3(\tilde{x}, Z)] = z_1^n z_2^n \sum_{j = 0}^{n-1} P(z_1; x^{(j)}) \cdot P(z_2; x^{(j)}) \cdot P(z_1^{-1} z_2^{-1}; x^{(j)}).\]
This is a multivariate polynomial with maximum degree $O(n)$ and all coefficients integers bounded by $O(n^2).$ Now, if $z_1, z_2$ are $n$th roots of unity, then as we saw in the prevoius section, $P(z_1; x^{(j)}) = z_1^{-j} P(z_1; x),$ $P(z_2; x^{(j)}) = z_2^{-j} P(z_2; x),$ and $P(z_1^{-1} z_2^{-1}; x^{(j)}) = (z_1z_2)^j P(z_1^{-1} z_2^{-1}; x).$ Therefore, if we define $Q(z_1, z_2; x) := z_1^n z_2^n P(z_1; x) P(z_2; x) P(z_1^{-1} z_2^{-1}; x),$ we have that $Q(z_1, z_2; x)$ is invariant under cyclic rotations of $x$ if $z_1, z_2$ are $n$th roots of unity.

Now, we prove the following lemma.

\begin{lemma}
    For any strings $x, y$ which are not the same up to cyclic rotation, $Q(z_1, z_2; x) \neq Q(z_1, z_2; y)$ for some $z_1, z_2$ that are $n$th roots of unity.
\end{lemma}

\begin{proof}
    Let $\omega = e^{-2 \pi i/n}.$ Then, for all $0 \le k \le n-1,$ we have that
\[P(\omega^k; x) P(\omega; x) P(\omega^{-(k+1)}; x) = Q(\omega^k, \omega; x) = Q(\omega^k, \omega; y) = P(\omega^k; y) P(\omega; y) P(\omega^{-(k+1)}; y).\]
\end{proof}
\fi

\section{Average Case: Upper Bound} \label{AverageCase}
We now consider the situation in which the unknown circular string $x$ is random. We will suppose that $x$ is equidistributed as a random circular string in which each bit is $0$ or $1$ with $\frac12$ probability. Note that this distribution is not uniform over all possible circular strings. However, our arguments can easily be modified to handle such a situation. We use the randomness to rule out certain problematic strings with high probability, and this can be done for uniform random circular strings as well as other distributions, for example if independently each bit is biased towards $0$ or $1$.

\begin{theorem}\label{AverageCasePoly}
Let $x$ be a random (in the sense described above) unknown circular string of length $n$ and let $q$ be the deletion probability of each element. Then there exists a constant $C_q$ depending only on $q$ such that we can determine $x$ with failure probability at most $n^{-10}$ using $O(n^{C_q})$ traces.
\end{theorem}

In what follows, we will let $x=x_1\cdots x_n$ and take indices of bits in $x$ modulo $n$. Let $k=100\log n$. We first note that with high probability, all of the consecutive substrings of $x$ of length $k$ and $k-1$ are pairwise distinct. We will refer to such strings as \emph{regular} strings. Indeed, the probability that $x_i\cdots x_{i+k-1}=x_j\cdots x_{j+k-1}$ for $i\ne j$ is $2^{-k}$ (where indices are taken modulo $n$), and union bounding over all $i,j$ as well as both $k$ and $k-1$ gives a failure probability of at most $O(n^2 2^{-k}) \ll n^{-10}$. 

If we assume that $x$ is regular,
the length $k$ consecutive substrings of $x$ uniquely determine $x$. Indeed, given $x_i\cdots x_{i+k-1}$, we can uniquely determine $x_{i+k}$ as there is a unique length $k$ consecutive substring of $x$ that begins with $x_{i+1}\cdots x_{i+k-1}$. Iteratively applying this allows us to recover the entire string $x$.
Thus, to prove Theorem \ref{AverageCasePoly}, it suffices to prove Lemma \ref{Contiguous}, i.e., to determine how many times each length $k$ substring appears consecutively in $x$ using $O(n^{C_q})$ traces, which will allow us to recover $x$ if $x$ is regular.

We will show the existence of $C_q$ so that for any string $s$ of length $k$, we can distinguish between
strings $x$ and $y$ correctly using $O(n^{C_q})$ samples with failure probability $10^{-n}$, if the number of consecutive occurrences of $s$ in $x$ and in $y$ differ, from which a union bound over all strings $s$ of length $k$ and all pairs of strings $x, y$ of length $n$ shows the result. 
Let $\alpha$ denote a sufficiently large constant only depending on $q$ that we will determine later.
For $0\le i\le n-k$, let $c_i$ denote the number of (not necessarily consecutive) occurrences of $s$ in $x$ contained in a consecutive substring of $x$ of length at most $i+k$. Similarly, let $d_i$ denote the number of (not necessarily consecutive) occurrences of $s$ in $y$ contained in a consecutive substring of $y$ of length at most $i+k$. By assumption, we have that $c_0 \neq d_0$. By casework on the last bit of the occurrence of $s$, we have that $c_i,d_i\le n\binom{i+k}k$. Let $P(t)=\sum_{i=0}^{\alpha k}c_it^i$ and $Q(t)=\sum_{i=0}^{\alpha k}d_it^i$. Moreover, the following is true:

\begin{lemma}\label{ProbStartWa}
The probability that a trace of $x$ starts with $s$ (where a random bit in the string is chosen as the beginning before bits are deleted) is $\frac1n(1-q)^kP(q)+O(q^{\alpha k}(\alpha+1)^ke^k)$. Similarly, the probability that a trace of $y$ starts with $s$ is $\frac1n(1-q)^kQ(q)+O(q^{\alpha k}(\alpha+1)^ke^k)$.
\end{lemma}

\begin{proof}
To compute the probability that a trace of $x$ starts with $s$, we do casework on how many bits are deleted before the last bit in the occurrence of $s$. If $i$ bits are deleted, then note that there are $c_i$ ways for it to be done by definition. Each such way has a probability of $\frac1n(1-q)^kq^i$ to occur. Indeed, for each way there is a $\frac1n$ probability that the correct starting bit is chosen, and the probability that only the bits corresponding to the specific instance of $s$ are kept is $(1-q)^kq^i$. It follows that the probability is exactly $\frac1n(1-q)^k\sum_{i=0}^{n-k}c_iq^i$.

It remains to show that $\frac1n(1-q)^k\sum_{\alpha k+1}^{n-k}c_iq^i=O(q^{\alpha k}(\alpha+1)^ke^k)$. As mentioned before, we have that $c_i\le n\binom{i+k}k$. Thus, this term is at most $\sum_{i>\alpha k}\binom{i+k}kq^i\le\binom{\alpha k+k}kq^{\alpha k}\sum_{i\ge0}\left(\frac{q(\alpha+1)}\alpha\right)^i$. Indeed, the ratio of consecutive terms in the sequence $\binom{i+k}kq^i$ is equal to $q\frac{i+k}i\le\frac{q(\alpha+1)}\alpha$. For a sufficiently large choice of $\alpha$, $\frac{q(\alpha+1)}\alpha<1$, so $\sum_{i>\alpha k}\binom{i+k}kq^i=O(\binom{\alpha k+k}kq^{\alpha k})=O(q^{\alpha k}(\alpha+1)^ke^k)$ by Stirling's approximation.

The argument for $y$ is analogous.
\end{proof}

Lemma \ref{ProbStartWa} allows us to estimate $P(q)$ and $Q(q)$ up to an $O(n(1-q)^{-k}q^{\alpha k}(\alpha+1)^ke^k)$ error by looking at how often traces of $x$ or $y$ begin with $s$, and then dividing by $\frac{1}{n}(1-q)^k$. So long as $P(q)$ and $Q(q)$ are sufficiently far apart, a Chernoff bound allows us to determine with high probability if the traces came from $x$ or $y$. However, it may be the case that $P(q)$ and $Q(q)$ are quite close. To remedy this, we observe that it is possible to \emph{simulate higher deletion probabilities $q'>q$}. Indeed, this can be achieved by deleting each bit in traces received independently with probability $\frac{q'-q}{1-q}$. Thus, it suffices to find $q'\in[q,r]$ with $P(q')$ and $Q(q')$ far apart for some $q<r<1$. 
The existence of such a $q'$ is proven by the following Littlewood-type result of Borwein, Erdélyi, and Kós.

\begin{theorem}[\cite{BorweinEK99}, Theorem 5.1]\label{BEKLittlewood}
There exist absolute constants $c_1>0$ and $c_2>0$ such that if $f$ is a polynomial with coefficients in $[-1,1]$ and $a\in(0,1]$, then \[|f(0)|^{c_1/a}\le\exp\left(\frac{c_2}a\right)\sup_{z\in[1-a,1]}|f(z)|.\]
\end{theorem}

\begin{proof}[Proof of Theorem \ref{AverageCasePoly}]
Let $r=\frac{q+1}2$. We first apply Theorem \ref{BEKLittlewood} to $\binom{\alpha k+k}k^{-1}(P(rx)-Q(rx))$ and $a=1-q/r$. Here, we are using the fact that the coefficients of $P$ and $Q$ are bounded in magnitude by $\binom{\alpha k+k}k$ by previous observations, and that $|P(0)-Q(0)| \ge 1$. Theorem \ref{BEKLittlewood} tells us that 
\begin{align*}
    \binom{\alpha k+k}k^{-c_1/a} &\le\exp\left(\frac{c_2}a\right)\binom{\alpha k+k}k^{-1}\sup_{z\in[1-a,1]}|P(rz)-Q(rz)| \\
    &=\exp\left(\frac{c_2}a\right)\binom{\alpha k+k}k^{-1}\sup_{q'\in[q,r]}|P(q')-Q(q')|,
\end{align*} or \[\sup_{q'\in[q,r]}|P(q')-Q(q')|\ge c_3\binom{\alpha k+k}k^{-c_4}\] for some constants $c_3$ and $c_4$ that only depend on $q$.

In particular, this is much larger than $10^kn(1-r)^{-k}r^{\alpha k}(\alpha+1)^ke^k$ for sufficiently large values of $\alpha$ ($\alpha$ may depend on $q$). Indeed, after taking $k$th roots and using Stirling's approximation this reduces to showing that $(e(\alpha+1))^{-c_5}>10 n^{1/k} (1-r)^{-1} r^\alpha(\alpha+1)e$ for sufficiently large $\alpha$ where $c_5$ is some constant that only depends on $q$, which is clear (since $0 < r < 1$ is fixed and $n^{1/k} < 2$). Thus, for any $q' \in [q, r],$ the error term $\frac1n(1-q')^k\sum_{\alpha k+1}^{n-k}c_i(q')^i=O((q')^{\alpha k}(\alpha+1)^ke^k)$ is at most $10^{-k}$ times $\frac{1}{n} (1-q')^{k} \cdot \sup_{q' \in [q, r]} |P(q')-Q(q')|.$

Hence, for some $q'\in[q,r]$, the probability that a trace begins with $s$ under bit deletion with probability $q'$ differs between $x$ and $y$ by $\Omega(10^kn(1-r)^{-k}r^{\alpha k}(\alpha+1)^ke^k)=\Omega(n^{-c_6})$ for some constant $c_6$ that only depends on $q$. By a standard Chernoff bound, for some constant $C_q$ only depending on $q$, we can distinguish between $x$ and $y$ using $O(n^{C_q})$ traces with failure probability at most $\exp(-\Omega(n))$, so the theorem follows.
\end{proof}

\section{Worst Case: Lower Bound}
\label{LowerBound}
In this section, we prove Theorem \ref{LowerThm} and demonstrate that worst-case circular trace reconstruction requires $\tilde\Omega(n^3)$ traces. We first record the following lemma from \cite{HoldenL18} expressing the number of independent samples required to distinguish between two probability measures $\mu$ and $\nu$ in terms of their Hellinger distance $d_H(\mu,\nu)$, defined to be $\left(\sum_{x\in X}(\mu(\{x\})-\nu(\{x\}))^2\right)^{1/2}$ where the sum is over all events in some discrete sample space $X$. Let $d_{TV}(\mu,\nu)$ denote the total variation distance between $\mu$ and $\nu$ and $\mu^n$ denote the law of $n$ independent samples from $\mu$.

\begin{lemma}[\cite{HoldenL18}, Lemma A.5] \label{HLLemma}
If $\mu$ and $\nu$ are probability measures satisfying $d_H(\mu,\nu)\le1/2$, then for $m\ge1/(4d_H^2(\mu,\nu))$, we have that $1-d_{TV}(\mu^m,\nu^m)\ge\epsilon$ if $m\le\frac{\log(1/\epsilon)}{9d_H^2(\mu,\nu)}$.
\end{lemma}

Note that the number of samples $m$ required to distinguish between $\mu$ and $\nu$ is given by the total variation distance between $\mu^m$ and $\nu^m$. Thus, it requires $\Omega(d_H^{-2}(\mu,\nu))$ samples to distinguish between two probability measures $\mu$ and $\nu$.

\begin{proof}[Proof of Theorem \ref{LowerThm}]
We now specialize to the case of distinguishing between $x=10^n10^{n+1}10^{n+k}$ and $y=10^n10^{n+k}10^{n+1}$ from independent traces. Let $\mu$ and $\nu$ respectively denote the laws of traces from $x$ and $y$. We will show that $d_H^2(\mu,\nu)=O((n\log n)^{3/2})$, which establishes the result by Lemma \ref{HLLemma}.

First, we note that conditional on the first $1$ in $x$ being deleted, the resulting trace is equidistributed as a trace from $y$ conditioned on the second $1$ being deleted, as in both cases we obtain a trace from the circular string $10^{n+1}10^{2n+k}$. Similar arguments for other cases show that conditioned on any $1$ being deleted, traces from $x$ and $y$ are equal in law. Thus, the resulting string must have three $1$'s to contribute to the Hellinger distance. We will henceforth assume that the resulting trace is of the form $10^a10^b10^c$ for some nonnegative integers $a,b,c$.

We now compute the ratio $\frac{\mu(\{10^a10^b10^c\})}{\nu(\{10^a10^b10^c\})}$ and show that it is typically $1+O((n/\log n)^{3/2})$. We have that \[\frac{\mu(\{10^a10^b10^c\})}{q^{3n+k+1-a-b-c}(1-q)^{a+b+c}}=\binom na\binom{n+1}b\binom{n+k}c+\binom nb\binom{n+1}c\binom{n+k}a+\binom nc\binom{n+1}a\binom{n+k}b,\]
\[\frac{\nu(\{10^a10^b10^c\})}{q^{3n+k+1-a-b-c}(1-q)^{a+b+c}}=\binom na\binom{n+k}b\binom{n+1}c+\binom nb\binom{n+k}c\binom{n+1}a+\binom nc\binom{n+k}a\binom{n+1}b.\]
It follows that \[\frac{\mu(\{10^a10^b10^c\})}{\nu(\{10^a10^b10^c\})}=\frac{\frac1{(n+1-b)(n+1-c)\cdots(n+k-c)}+\frac1{(n+1-c)(n+1-a)\cdots(n+k-a)}+\frac1{(n+1-a)(n+1-b)\cdots(n+k-b)}}{\frac1{(n+1-c)(n+1-b)\cdots(n+k-b)}+\frac1{(n+1-a)(n+1-c)\cdots(n+k-c)}+\frac1{(n+1-b)(n+1-a)\cdots(n+k-a)}}.\]
Multiplying the numerator and denominator by $\prod_{i=1}^k(n+i-a)(n+i-b)(n+i-c)$ results in \[S_1=\prod_{i=1}^k(n+i-a)\prod_{i=2}^k(n+i-b)+\prod_{i=1}^k(n+i-b)\prod_{i=2}^k(n+i-c)+\prod_{i=1}^k(n+i-c)\prod_{i=2}^k(n+i-a)\] and \[S_2=\prod_{i=1}^k(n+i-b)\prod_{i=2}^k(n+i-a)+\prod_{i=1}^k(n+i-c)\prod_{i=2}^k(n+i-b)+\prod_{i=1}^k(n+i-a)\prod_{i=2}^k(n+i-c),\] respectively. We have that $S_1-S_2=(a-b)\prod_{i=2}^k(n+i-a)(n+i-b)+(b-c)\prod_{i=2}^k(n+i-b)(n+i-c)+(c-a)\prod_{i=2}^k(n+i-c)(n+i-a)$. This is an alternating polynomial in $a,b,c$, i.e. applying a permutation $\sigma$ to $a,b,c$ changes the sign of the polynomial by the sign of $\sigma$. Hence, it can be written in the form $(a-b)(b-c)(a-c)P_k(n,a,b,c)$, where $P_k$ is a polynomial in $n,a,b,c$ of degree $2k-4$ since $S_1$ and $S_2$ have degree $2k-1$.

By a standard Chernoff bound, there exists a constant $C$ such that with probability at least $1-n^{-100}$, $a,b,c\in[np-C\sqrt{n\log n},np+C\sqrt{n\log n}]$. When this occurs, we have that $S_2=\Omega(n^{2k-1})$ and $|S_1-S_2|=O((n\log n)^{3/2}n^{2k-4})$, so $\frac{\mu(\{10^a10^b10^c\})}{\nu(\{10^a10^b10^c\})}\in[1-(c\log n/n)^{3/2},1+(c\log n/n)^{3/2}]$ for some constant $c$. We thus have that \[d_H^2(\mu,\nu)=\sum_{a,b,c\ge0}(\mu(\{10^a10^b10^c\})-\nu(\{10^a10^b10^c\}))^2\le 2n^{-100}\]\[+\sum_{a,b,c\in[np-C\sqrt{n\log n},np+C\sqrt{n\log n}]}\nu(\{10^a10^b10^c\})^2\left(1-\frac{\mu(\{10^a10^b10^c\})}{\nu(\{10^a10^b10^c\})}\right)^2=O((\log n/n)^3).\]

It follows by Lemma \ref{HLLemma} that it requires $\Omega(n^3/\log^3n)$ samples to distinguish between traces from $x$ and $y$, as desired.
\end{proof}

\section*{Acknowledgments}

This research was partially supported by the MIT Akamai Fellowship, the NSF Graduate Fellowship, and by NSF-DMS grant 1949884 and NSA grant H98230-20-1-0009. The first author thanks Piotr Indyk for many helpful discussions and feedback, as well as Mehtaab Sawhney for pointers to some references. The second author thanks Professor Joe Gallian for running the Duluth REU at which part of this research was conducted, as well as program advisors Amanda Burcroff, Colin Defant, and Yelena Mandelshtam for providing a supportive environment.

\newcommand{\etalchar}[1]{$^{#1}$}
