\section{Counting the orders that remain}\label{sec:potential}

We prove Theorem~\ref{thm:fixed-stage} in two steps. First, we compare
the increases in $\log Z$ from moves requested by \texttt{Select} and from
path repairs with the losses from answers and degree repairs. This proves
the refinement count in Lemma~\ref{lem:rare-refinements}. We then count
orders consistent with the transcript using the volumes and the anchors
in the stored tree.

\subsection{Refinements are rare}\label{sec:rare-refinements}\label{sec:guarantees}

Write $\eta=1/(100k)$ for the error in the retained fraction in
Lemma~\ref{lem:local-routines}. Recording an answer between two anchors
leaves $Z$ unchanged.
Every other answer retains at least $1/2-\eta$ of its node's volume, so
its loss in $\log Z$ is at most
\begin{equation}\label{eq:comparison-loss}
a_\eta=-\log(1/2-\eta)=1+O(1/k).
\end{equation}
Let $G$ be the sum of the refinement gains through $q$ completed calls
to \texttt{Compare}.
Since $Z$ starts at one and never exceeds one,
\begin{equation}\label{eq:total-refinement-gain}
G\le\log Z+a_\eta q\le a_\eta q.
\end{equation}

\begin{proof}[Proof of Lemma~\ref{lem:rare-refinements}]
Let $D$ count degree repairs. Each removes $k$ arcs, and each call
inserts at most one arc. Thus $D\le q/k$. By \eqref{eq:tariff}, each such
move gains at least $-4$. A refinement requested by \texttt{Select} has
$f_x(c)>2^k$ by Lemma~\ref{lem:local-routines}, so its gain
$\log f_x(c)$ is greater than $k$, by \eqref{eq:refinement-gain}.

In a path repair, refining $x_i$ at $c_i$ changes the arc to $x_{i+1}$
into the bound $X_{x_{i+1}}>c_i$. The next anchor therefore satisfies
$c_{i+1}>c_i$. Thus these $H=2^k$ anchors are distinct. The anchors with
reduced denominator $2^{m+1}$ are $(2j+1)/2^{m+1}$ for $0\le j<2^m$.
Thus only $\sum_{m=0}^{k-2}2^m=2^{k-1}-1<H/2$ possible anchors have
$m<k-1$. At least $H/2$ of the selected anchors therefore have $m\ge k-1$.
By \eqref{eq:tariff}, every refinement contributes at least $-4$ to
$\log Z$, and each of these $H/2$ refinements contributes at least
$(1-1/k)(k-1)$ in addition. The total increase from the $H$ refinements
in this path repair is therefore at least
\[
\begin{aligned}
&\underbrace{(1-1/k)\frac H2(k-1)}_{
  \substack{\text{extra gain from }H/2\text{ anchors}\\
            \text{with }m\ge k-1}}
+\underbrace{(-4H)}_{
  \substack{-4\text{ from all }H\text{ anchors,}\\
            \text{including those with }m<k-1}}
\\[1ex]
&\qquad=H\left(\frac{k}{2}-5+\frac1{2k}\right)\ge\frac{kH}{4}.
\end{aligned}
\]
Every path repair in a completed call to \texttt{Compare} contributes
all $H$ refinements to $P$, the total number of refinements after $q$
completed calls. Path repairs contribute at least $k/4$ per refinement
on average. Refinements requested by \texttt{Select} gain more than $k$
(Lemma~\ref{lem:local-routines} and \eqref{eq:refinement-gain}), and
each of the $D$ degree repairs gains at least $-4$ by \eqref{eq:tariff}.
Summing these contributions and applying \eqref{eq:total-refinement-gain} gives
\[
\frac k4(P-D)-4D\le G\le a_\eta q,\qquad D\le q/k.
\]
Rearranging proves the claim, for example with
$C=8$ since $k\ge64$.
\end{proof}

The proof of Lemma~\ref{lem:rare-refinements} tells us that long paths
help pay for their own removal: their distinct anchors force
a large volume gain. Since $Z\le1$, these gains must be offset by losses
from comparisons and degree repairs. Both losses are bounded in terms
of the number of comparisons, so frequent simplification requires many
comparisons.

\subsection{Counting with the queried labels}\label{sec:movement-volume}

Recall that $T_q$ is the number of total orders consistent with the first
$q$ comparison answers. To lower-bound $T_q$, we consider all total orders
obtained by inserting the unqueried labels into orders of the queried labels
represented by the adversary's tree. This can include orders that the
tree itself excludes. For example, if $a<b$ lie in the same child subtree
and an unqueried label $z$ is stored at the root, the tree keeps $z$
outside that child block, while the transcript also permits $a<z<b$.

Let $s$ be the number of labels that have appeared in queries.
For the counting argument, we can omit the other labels without changing
the product volume $Z$. To see this, consider an unqueried item. Its
vertex has no incident arcs, since every arc records a comparison.
\texttt{Select} requests moves only for items in the current query.
\texttt{Repair} selects only vertices incident to arcs. Thus the item
stays at the root. Its interval remains $(0,1)$: no comparison involves
it, and no bound can propagate to it along an arc. Its coordinate
therefore contributes an independent factor of volume one. Omitting all
such coordinates leaves the volume $Z$ for the $s$ queried labels.

To count orders of these $s$ labels, we sample positions in the
adversary's tree. Assign each child at the reduced dyadic anchor
$c=(2i+1)/2^{m+1}$ the weight
\begin{equation}\label{eq:child-weight}
w(c)=\frac1{k^2}\left(\frac{1-1/k}{2}\right)^m.
\end{equation}
The sum over all possible anchors is $1/k$ because there are $2^m$
anchors for each $m$.

For each of the $s$ labels independently, start at the root. At each
node, enter a child with probability equal to its weight, or stop with
the remaining probability and draw a uniform coordinate in $(0,1)$
there. The stopping probability is at least $1-1/k$. Order the resulting
positions by the tree and its anchors.

For each label $x$, let $d_x$ be the depth of the
node storing it, and write $c_{x,1},\ldots,c_{x,d_x}$ for the child
anchors on the path from the root to that node.
The product of these weights over all labels is
\begin{equation}\label{eq:path-weight-product}
\mathcal W=\prod_x\prod_{j=1}^{d_x}w(c_{x,j}).
\end{equation}
A label stored at the root contributes one, so $\mathcal W$ is unchanged
if the product is taken over only the queried labels.

\begin{lemma}[Orders consistent with the transcript]\label{lem:packing}
After any of the first $Q(n)$ calls to \textnormal{\texttt{Compare}},
\[
T_q\ge n!(1-1/k)^s Z\mathcal W.
\]
The same inequality holds before the first call.
\end{lemma}
\begin{proof}
The rule above samples each queried label's position by following
children with probabilities $w(c)$ and choosing a uniform coordinate
at the node where it stops. These positions are independent and
identically distributed. Ties have probability zero, so each of their
$s!$ relative orders has probability $1/s!$.

The product $\mathcal W$ is the probability that all $s$ labels reach
the nodes where the adversary stores them. Once there, they all stop
with probability at least $(1-1/k)^s$. Conditional on these choices,
the independently uniform coordinates satisfy all node constraints with
probability equal to the product of the node volumes. Omitting unqueried
labels leaves that product equal to $Z$.

Multiplying these three factors gives probability at least
$(1-1/k)^s Z\mathcal W$ of obtaining an order consistent with the
transcript, by Proposition~\ref{prop:legality}. Since each relative order
has probability $1/s!$, there are at least $s!(1-1/k)^s Z\mathcal W$
such orders of the queried labels.

Each extends to $\binom ns(n-s)!=n!/s!$ full orders: choose the positions
of the queried labels and arrange the remaining labels. Every extension
respects the transcript, since no answer involves an unqueried label.
Therefore
\[
T_q\ge \bigl[s!(1-1/k)^s Z\mathcal W\bigr]\frac{n!}{s!}
    =n!(1-1/k)^s Z\mathcal W.
\]
\end{proof}

\subsection{Bounding the number of remaining orders}\label{sec:comparison-cost}

Each refinement multiplies the product volume $Z$ by $f_x(c)$ and the
sampling weight $\mathcal W$ by $w(c)$. The anchor guarantee relates
these two changes: the volume gain almost pays for the loss in sampling
weight. This is the cancellation behind Theorem~\ref{thm:fixed-stage}.

\begin{proof}[Proof of Theorem~\ref{thm:fixed-stage}]
For the first $Q(n)$ calls to \texttt{Compare}, legality and termination
follow from Proposition~\ref{prop:legality}. Later calls use fixed ranks
consistent with the recorded answers. All choices are deterministic.
We first prove the bound for $q<Q(n)$.

Let $s$ be the number of queried labels and put
$d_k=-\log(1-1/k)=O(1/k)$. Taking logarithms in
Lemma~\ref{lem:packing} gives
\[
\log T_q\ge\log(n!)-s d_k+\log Z+\log\mathcal W.
\]
Since $s\le2q$, the term $s d_k$ costs only $O(q/k)$.
It remains to control the loss $-\log\mathcal W$.

A refinement through anchor $c$ contributes $\ell(c)=-\log w(c)$ to
this loss. For $c=(2i+1)/2^{m+1}$ in reduced form,
\eqref{eq:child-weight} gives
\[
\ell(c)=2\log k+(1+d_k)m.
\]
\begin{samepage}
If $g=\log f_x(c)$ is the refinement's volume gain, the anchor
guarantee~\eqref{eq:tariff} implies $m\le(g+4)/(1-1/k)$. Hence
\[
\ell(c)\le 2\log k+\frac{1+d_k}{1-1/k}(g+4)=ag+b,
\]
where $a=(1+d_k)/(1-1/k)$ and $b=4a+2\log k$.
Thus $a\ge1$, $a=1+O(1/k)$, and $b=O(\log k)$.

\end{samepage}

Let $P$ be the number of refinements and $G$ their total volume gain.
Summing over their anchors $c_r$ gives
\[
-\log\mathcal W=\sum_r\ell(c_r)\le aG+bP.
\]
The volume accounting bound~\eqref{eq:total-refinement-gain} gives
$G\le\log Z+a_\eta q$. Substituting both inequalities into the counting
bound yields
\begin{align*}
\log T_q
&\ge \log(n!)-s d_k+\log Z-aG-bP\\
&\ge \log(n!)-s d_k+(1-a)\log Z-aa_\eta q-bP.
\end{align*}
The volume terms have combined into $(1-a)\log Z$, which is nonnegative
because $a\ge1$ and $Z\le1$. Discarding this term, using $s\le2q$, and
applying $P\le Cq/k$ from Lemma~\ref{lem:rare-refinements}, we obtain
\[
\log T_q\ge\log(n!)-\left(aa_\eta+2d_k+\frac{Cb}{k}\right)q.
\]
Since $a_\eta=1+O(1/k)$ by \eqref{eq:comparison-loss}, we may take
\[
\delta_k=aa_\eta-1+2d_k+\frac{Cb}{k}
        =O\!\left(\frac{\log k}{k}\right).
\]
This proves \eqref{eq:prefix-orders} for $q<Q(n)$.
For $q\ge Q(n)\ge\log(n!)$, its right-hand side is nonpositive and
$T_q\ge1$, so the bound holds for all $q$.
\end{proof}

Intuitively, the proof of Theorem~\ref{thm:fixed-stage} shows that the
volume gains almost pay for the losses in sampling weight. The remaining
$O(\log k)$ cost per refinement totals only $O(q\log k/k)$, because
Lemma~\ref{lem:rare-refinements} limits the number of refinements to
$O(q/k)$. This gives the error term $\delta_k=O(\log k/k)$ in the
theorem's bound on the number of remaining orders.

The bound on $T_q$ also applies to tasks where the algorithm may stop
with several total orders still possible (Section~\ref{sec:consequences}).