diff fd6d571..03d45f2 uniform_trace_reconstruction_v2.txt
diff --git a/uniform_trace_reconstruction_v2.txt b/uniform_trace_reconstruction_v2.txt
index ea40795..521b377 100644
--- a/uniform_trace_reconstruction_v2.txt
+++ b/uniform_trace_reconstruction_v2.txt
@@ -9,6 +9,8 @@
\usepackage{lmodern}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype,enumitem,xcolor}
+\usepackage{tikz}
+\usetikzlibrary{arrows.meta,positioning,calc,decorations.pathreplacing}
\usepackage[colorlinks=true,linkcolor=blue!45!black,citecolor=blue!45!black,urlcolor=blue!45!black]{hyperref}
\setlist{itemsep=3pt,topsep=5pt}
\numberwithin{equation}{section}
@@ -59,7 +61,9 @@ Fix a binary string $x=x_1\cdots x_n\in\{0,1\}^n$. A \emph{deletion trace}
is the random string produced by the following experiment: walk through
the positions $1,2,\ldots,n$; keep position $i$ with probability $p$
and drop it with probability $q=1-p$, independently at each $i$; the
-kept bits, in their original order, form the trace. The trace reports
+kept bits, in their original order, form the trace. For example, if
+$x=1011$ and the deletion removes positions $2$ and $4$, the resulting
+trace is $11$. The trace reports
its own length and its bits, but nothing about which original positions
survived. An algorithm is handed $n$, the value $p$ (as a rational
number), and a stream of independent traces of $x$, and must output
@@ -1004,13 +1008,43 @@ its rows and columns through entries equal to one; that pairing is the
required assignment.
\end{proof}
-To see why distinctness matters: one edge may contribute to several new
-parameters, but it need pay for only one of their upper bounds. Concretely,
-take two old tuples $(i_1,i_3,i_5)$ and $(i_2,i_4,i_6)$ joined by one
-dashed endpoint link-edge, with gaps $g_a=(i_a,i_{a+1})$ for
-$1\le a\le5$. The assignment $g_a\mapsto e_a$, $1\le a\le5$, gives every
-gap a distinct crossing edge: $e_1$ crosses both $g_1$ and $g_2$ but is
-charged only to $g_1$, and $e_2$ supplies the bound for $g_2$.
+To see why distinctness matters, look at Figure~\ref{fig:edge-gap-assignment}:
+one edge may contribute to several new parameters, but it need pay for
+only one of their upper bounds. Concretely, take two old tuples
+$(i_1,i_3,i_5)$ and $(i_2,i_4,i_6)$ joined by one dashed endpoint
+link-edge, with gaps $g_a=(i_a,i_{a+1})$ for $1\le a\le5$. The assignment
+$g_a\mapsto e_a$, $1\le a\le5$, gives every gap a distinct crossing edge:
+$e_1$ crosses both $g_1$ and $g_2$ but is charged only to $g_1$, and $e_2$
+supplies the bound for $g_2$.
+
+\begin{figure}[htbp]
+\centering
+\begin{tikzpicture}[x=1.28cm,y=0.9cm,>=stealth,
+ olda/.style={draw=blue!70!black,thick},
+ oldb/.style={draw=orange!85!black,thick},
+ added/.style={draw=black,thick,dashed}]
+ \draw[gray] (0,0)--(5,0);
+ \foreach \a in {1,...,6} {
+ \fill (\a-1,0) circle (1.8pt);
+ \node[below=3pt] at (\a-1,0) {$i_{\a}$};
+ }
+ \draw[olda] (0,0) to[bend left=30] node[above,pos=.5] {$e_1$} (2,0);
+ \draw[olda] (2,0) to[bend left=30] node[above,pos=.5] {$e_3$} (4,0);
+ \draw[oldb] (1,0) to[bend left=65] node[above,pos=.5] {$e_2$} (3,0);
+ \draw[oldb] (3,0) to[bend left=65] node[above,pos=.5] {$e_4$} (5,0);
+ \draw[added] (4,0) to[bend right=60] node[below=2pt,pos=.5] {$e_5$} (5,0);
+ \foreach \a in {1,...,5} {
+ \node at (\a-.5,-1.05) {$g_{\a}$};
+ }
+\end{tikzpicture}
+\caption{A schematic interleaving of the two old tuples $(i_1,i_3,i_5)$
+and $(i_2,i_4,i_6)$, joined by the dashed endpoint link $e_5$. Here
+$g_a$ is the gap $(i_a,i_{a+1})$. The assignment $g_a\mapsto e_a$ for
+$1\le a\le5$ uses a distinct crossing edge for every gap: $e_1$ crosses
+both $g_1$ and $g_2$ but is charged only to $g_1$, while $e_2$ supplies
+the bound for $g_2$.}
+\label{fig:edge-gap-assignment}
+\end{figure}
Give each edge occurrence $e$ its damping $a_e>0$. A merged gap's damping
is the sum of $a_e$ over edges crossing it, hence at least that of its
@@ -1111,7 +1145,7 @@ The linear regime of this recurrence pushes $D_*S_j$ below one; its
quadratic regime then makes $S_j$ shrink fast. Both regimes also control
the arguments of the final gap parameters.
-Choose a integer $J_*$ with $\alpha J_*\ge3$ and set $H=J_*+3$. To check
+Choose an integer $J_*$ with $\alpha J_*\ge3$ and set $H=J_*+3$. To check
the decrease, write $\vartheta=\eta q_*Y^{-\alpha}$ and $t_j=D_*S_j$, so
$t_j=\vartheta\,t_{j-1}\min\{1,t_{j-1}\}$. Then, whenever the quadratic
regime begins,
@@ -1373,7 +1407,60 @@ $w_r(v)=(1+v)\re w_r+\ii\,{\rm Im}\,w_r$ is a horizontal segment starting
at $w_r$ and ending at $w_r(R)$ with $\re w_r(R)=(1+R)\xi_r\ge q/p$. All
coordinates use the same parameter $0\le v\le R$; the proof interpolates
$F(Z_0(v),\ldots,Z_{k-1}(v))$ on one complex strip, simultaneously for
-every coordinate.
+every coordinate (Figure~\ref{fig:simultaneous-cayley}).
+
+\suppressfloats[t]
+\begin{figure}[htbp]
+\centering
+\begin{tikzpicture}[x=1.2cm,y=1.2cm,>=Stealth,font=\small]
+ \begin{scope}
+ \fill[blue!4] (0,0) circle (1);
+ \fill[teal!17] (0.4,0) circle (0.6);
+ \draw[black!35,->] (-1.2,0)--(1.32,0) node[right] {$\re Z$};
+ \draw[black!35,->] (0,-1.16)--(0,1.2);
+ \draw[black!65] (0,0) circle (1);
+ \draw[teal!65!black] (0.4,0) circle (0.6);
+ \fill (0.4,0) circle (0.022) node[below right] {$q$};
+ \node[below right] at (1,0) {$1$};
+ \fill[blue!70!black] (-0.2027,0.5791) circle (0.027)
+ node[above left] {$Z_0^*$};
+ \fill[orange!80!black] (-0.1753,-0.4310) circle (0.027)
+ node[below left] {$Z_1^*$};
+ \node at (0,1.5) {The $Z$-plane};
+ \node at (0,-1.42) {$\abs{Z-q}\le p$ is shaded};
+ \end{scope}
+ \draw[->,thick] (1.68,0.22)--(3.78,0.22)
+ node[midway,above=5pt] {$w=\dfrac{1+Z}{1-Z}$};
+ \begin{scope}[xshift=6cm]
+ \fill[blue!4] (0,-1.1) rectangle (2.85,1.1);
+ \fill[teal!17] (0.6667,-1.1) rectangle (2.85,1.1);
+ \draw[black!35,->] (-0.15,0)--(3,0) node[right] {$\re w$};
+ \draw[black!65,->] (0,-1.16)--(0,1.22);
+ \draw[dashed,teal!65!black] (0.6667,-1.1)--(0.6667,1.1);
+ \node[below right] at (0.6667,0) {$q/p$};
+ \draw[->,thick,blue!70!black] (0.35,0.65)--(1.6333,0.65);
+ \fill[blue!70!black] (0.35,0.65) circle (0.027)
+ node[above left] {$w_0$};
+ \fill[blue!70!black] (1.6333,0.65) circle (0.027)
+ node[above] {$w_0(R)$};
+ \draw[->,thick,orange!80!black] (0.5,-0.55)--(2.3333,-0.55);
+ \fill[orange!80!black] (0.5,-0.55) circle (0.027)
+ node[below left] {$w_1$};
+ \fill[orange!80!black] (2.3333,-0.55) circle (0.027)
+ node[below] {$w_1(R)$};
+ \node at (1.4,1.5) {The $w$-plane};
+ \node at (1.4,-1.42) {Both paths use the same $0\le v\le R$};
+ \end{scope}
+\end{tikzpicture}
+\caption{Geometry of the simultaneous continuation. The Cayley map turns
+the deletion disk into $\re w\ge q/p$. Two possible starting coordinates
+are shown; the horizontal arrows have different lengths but share the
+same parameter: $w_r(v)=(1+v)\re w_r+\ii\operatorname{Im}w_r$ for
+$0\le v\le R$. The proof interpolates
+$F(Z_0(v),\ldots,Z_{k-1}(v))$ on one complex strip, simultaneously for
+every coordinate.}
+\label{fig:simultaneous-cayley}
+\end{figure}
On the closed strip $-1/2\le\re v\le R$ we have
$\re w_r(v)=(1+\re v)\xi_r>0$, so all $Z_r(v)$ lie in the unit disk and