\subsection{Answering a comparison}\label{sec:comparison}\label{sec:legal}

Algorithm~\ref{alg:compare} gives the comparison procedure. Its main
choice is delegated to \texttt{Select}, which encapsulates the key
algorithmic result of this paper.

\begin{algorithm}[H]
\caption{\texttt{Compare}$(A,B)$: answer a comparison query.}
\label{alg:overview-compare}\label{alg:compare}
\DontPrintSemicolon
\KwIn{Distinct item labels $A,B$ and the current adversary state.}
\KwOut{An answer $A<B$ or $B<A$, with the state updated.}
\If{fixed ranks have been chosen}{\Return their order of $A,B$\;}
\If{$|\mathcal T|=n\ceil{\log n}$}{
  Form the DAG of answers in $\mathcal T$ and choose a topological order, breaking ties by label\;
  Store its ranks and \Return their order of $A,B$\;
}
\While{true}{
  $v\gets$ the root\;
  \While{$A$ and $B$ lie in the same child subtree of $v$}{
    $v\gets$ that child\;
  }
  \If{$A$ and $B$ lie in different child subtrees of $v$}{
    $\mathit{answer}\gets$ the left-to-right order of their child anchors\;
    \textbf{break}\;
  }
  $\alpha,\beta\gets$ the coordinates or child anchors representing $A,B$ at $v$\;
  $r\gets$ \texttt{Select}$(D_v,\alpha,\beta)$\;
  \If{$r$ is an answer}{
    $\mathit{answer}\gets$ the corresponding order of $A,B$\;
    \textbf{break}\;
  }
  $(x,c)\gets r$\;
  \texttt{RefineAt}$(x,c)$\;
}
\If{at least one queried item is stored at $v$}{
  Store $\mathit{answer}$ as an arc in the graph at $v$ or as an interval bound\;
  \texttt{Normalize}$(D_v)$\;
}
Append $\mathit{answer}$ to $\mathcal T$\;
\texttt{Repair}$(v)$\;
\Return $\mathit{answer}$\;
\end{algorithm}

\subsubsection{Choosing an answer}\label{sec:selection}

\texttt{Select} uses deterministic estimates of the fractions of $K(D)$
retained by the two answers. It obtains these estimates by examining
bounded neighborhoods of the queried vertices in the DAG. The size of
each neighborhood depends on vertex degree (the sum of its in-degree and out-degree) and
the length of the longest directed path in the DAG. We use one integer
$k$ to specify these bounds in Lemma~\ref{lem:local-routines}. Larger $k$ allows higher degrees
and longer paths, while the guaranteed retained fraction approaches
one half.

Algorithm~\ref{alg:select} gives the \texttt{Select} algorithm.
It calls \texttt{Enclose}, given in Algorithm~\ref{alg:finite-digits}.
\texttt{Enclose} returns a list whose entries give one interval $I_x$
for each queried coordinate $x$.

\begin{algorithm}[H]
\caption{\texttt{Select}$(D,\alpha,\beta)$: choose an answer or a position for refinement.}
\label{alg:select}
\DontPrintSemicolon
\KwIn{A canonical order-restriction DAG $D$ and a query between two distinct coordinates or between a coordinate and a dyadic constant.}
\KwOut{An answer $\alpha<\beta$ or $\beta<\alpha$, or a pair $(x,c)$.}
$T\gets$ the queried coordinates\;
$\mathcal L\gets$ \texttt{Enclose}$(D,T)$\;
In every entry, use $[t,t]$ for a queried constant $t$\;
$p\gets$ the fraction of entries with $\max I_\alpha<\min I_\beta$\;
$q\gets$ the fraction of entries with $\max I_\beta<\min I_\alpha$\;
\If{$\max(p,q)\ge 1/2-1/(100k)$}{
  \lIf{$p\ge q$}{\Return $\alpha<\beta$}
  \Return $\beta<\alpha$\;
}
$x\gets$ the smallest label in $T$\;
$W_x\gets r_x-\ell_x$\;
$h\gets$ the largest power of two at most $W_x/2$\;
$c\gets h\left\lceil(\ell_x+W_x/4)/h\right\rceil$\;
\Return $(x,c)$\;
\end{algorithm}

To state the guarantee provided by \texttt{Select}, let $f_x$ be the
density of $X_x$ under a uniform feasible assignment in $K(D)$. Explicitly,
\begin{equation}\label{eq:coordinate-density}
f_x(c)=\frac{\vol_{|V|-1}\bigl(K(D)\cap\{X_x=c\}\bigr)}{V(D)}.
\end{equation}
The numerator is the volume of the section $X_x=c$, measured in the
remaining $|V|-1$ coordinates.

The following lemma expresses the key idea: either we answer while retaining nearly
half the feasible volume, mirroring the ideal adversary, or we identify a
refinement that greatly increases the product of the node volumes
(Lemma~\ref{lem:section-volume}).

\begin{lemma}[Local selection]\label{lem:local-routines}
Let $k\ge64$ be an integer and $D$ an order-restriction DAG with canonical dyadic intervals,
$V(D)>0$, degree at most $k$, and directed paths of at most $2^{k+1}$
vertices. Algorithm~\ref{alg:select} returns one of the following:
\begin{enumerate}
\item An answer retaining at least $1/2-1/(100k)$ of $V(D)$.
\item A queried coordinate $x$ and a dyadic $c\in(\ell_x,r_x)$ with
$f_x(c)>2^k$.
\end{enumerate}
The calculation is deterministic and uses only the graph and interval
bounds within a distance of the queried coordinates depending only on $k$.
\end{lemma}
\begin{proof}
See Appendices~\ref{sec:oracle} and~\ref{app:execution}.
\end{proof}

\begin{proof}[Proof idea for Lemma~\ref{lem:local-routines}]
We sketch the enclosing-interval construction behind \texttt{Select}'s
probability estimates. Pass through the vertices in topological order,
changing one position at a time. Its permitted range is determined by
the stored interval and the neighbors' positions. Split this range into
$S$ equal pieces, choose one, and move the position to the same relative
point in that piece.
For example, choosing the second quarter of $(0,1)$ sends a position
$u$ to $(1+u)/4$.

Run this procedure on two copies of the position vector, starting one
at all lower interval endpoints and the other at all upper endpoints.
At each step, use the same piece number in both copies, each within its
own permitted range.

For the proof, also consider a position vector $X$, initially uniform
in $K(D)$. At each update, choose a piece number
independently and uniformly, and use it in all three vectors.
The update preserves coordinatewise order, so $X$ stays between the two
endpoint copies (Figure~\ref{fig:local-enclosure}). It also preserves
the uniform distribution on $K(D)$: conditional on the other positions,
it sends a uniform position into a uniformly chosen equal piece.
This use of enclosing copies is related to sampling algorithms for
linear extensions~\cite[Section~4.2]{talvitie-counting}.

\begin{center}
\begin{minipage}{\linewidth}
\captionsetup{hypcap=false}
\centering
\begin{tikzpicture}[>=Latex,font=\small,
  enclosure/.style={accent,very thick},
  position/.style={circle,fill=ink,inner sep=1.7pt}]
\begin{scope}
\node at (2.4,1.1) {Before updates};
\foreach \name/\row/\point in {x/.4/3.36,y/-.45/1.2}{
  \node[left] at (-.15,\row) {$\name$};
  \draw[enclosure] (0,\row)--(4.8,\row);
  \draw[enclosure] (0,\row-.09)--(0,\row+.09);
  \draw[enclosure] (4.8,\row-.09)--(4.8,\row+.09);
  \node[position] at (\point,\row) {};
}
\draw[ink!45] (0,-1.05)--(4.8,-1.05);
\node[below] at (0,-1.05) {$0$};
\node[below] at (4.8,-1.05) {$1$};
\end{scope}
\draw[->,thick] (5.3,0)--(6.7,0);
\node[align=center,font=\footnotesize] at (6,.5) {Shared\\updates};
\begin{scope}[shift={(7.4,0)}]
\node at (2.4,1.1) {After updates};
\foreach \name/\row/\lo/\hi/\point in {x/.4/1.2/2.4/2.04,y/-.45/3.6/4.8/3.9}{
  \node[left] at (-.15,\row) {$\name$};
  \draw[ink!20] (0,\row)--(4.8,\row);
  \draw[enclosure] (\lo,\row)--(\hi,\row);
  \draw[enclosure] (\lo,\row-.09)--(\lo,\row+.09);
  \draw[enclosure] (\hi,\row-.09)--(\hi,\row+.09);
  \node[position] at (\point,\row) {};
}
\draw[ink!45] (0,-1.05)--(4.8,-1.05);
\node[below] at (0,-1.05) {$0$};
\node[below] at (4.8,-1.05) {$1$};
\node at (2.4,-1.8) {The intervals certify $X_x<X_y$.};
\end{scope}
\end{tikzpicture}
\captionof{figure}{Updating two unconstrained coordinates using four
pieces. All three copies choose the second piece for $x$ and the fourth
for $y$. The blue interval endpoints show the two enclosing positions
for each coordinate. The dots show one feasible assignment between them.
The resulting disjoint intervals certify $X_x<X_y$.}
\label{fig:local-enclosure}
\end{minipage}
\end{center}

Disjoint enclosing intervals determine the queried order, so narrow
intervals make the probability estimates useful. At a vertex with no
incoming arcs, choosing the first piece moves both endpoint copies
towards their common lower bound and reduces their separation.
The proof tracks how this shrinking passes through neighboring vertices.
The degree and path bounds control how many passes are needed to make
the queried intervals narrow for most choice sequences.

Within one pass, dependence on newly updated positions follows directed
paths. After a bounded number of passes, only a bounded neighborhood can
affect a queried interval. \texttt{Enclose} enumerates the update choices
there, and \texttt{Select} counts the entries that certify each comparison
answer. The density argument for the refinement alternative is left to
the full proof.
\end{proof}

Keeping nearly half the volume at each answer is the geometric counterpart
of keeping at least half the possible total orders.
Section~\ref{sec:potential} relates the node volumes to the number of
orders still possible. We use this count to prove that every correct
sorter must make at least $(1-o(1))n\log n$ comparisons.

\begin{algorithm}[H]
\caption{\texttt{Enclose}$(D,T)$: compute enclosing intervals for the queried coordinates.}
\label{alg:finite-digits}
\DontPrintSemicolon
\KwIn{An order-restriction DAG $D$ and a set $T$ of one or two queried coordinates.}
\KwData{Fixed neighborhood radius $\rho$, number of repetitions $t$, and power of two $S$ giving the number of update choices, chosen in Appendix~\ref{app:certificates}.}
\KwOut{A list of interval families $(I_x)_{x\in T}$.}
$R\gets$ vertices within distance $\rho$ of $T$, ignoring arc directions\;
$F\gets$ vertices at distance strictly less than $\rho$ from $T$\;
$\pi\gets$ a topological order of the DAG induced by $R$, breaking ties by label\;
$\mathcal L\gets$ the empty list\;
\ForEach{assignment $j_{z,s}\in\{0,\ldots,S-1\}$ for $z\in F$ and $1\le s\le t$}{
  $A_z\gets\ell_z$, $B_z\gets r_z$ for every $z\in R$\;
  \For{$s=1,\ldots,t$}{
    \ForEach{$z\in F$ in the order $\pi$}{
      \ForEach{$Y\in\{A,B\}$}{
        $L\gets\max(\{\ell_z\}\cup\{Y_u:u\to z\})$\;
        $U\gets\min(\{r_z\}\cup\{Y_u:z\to u\})$\;
        $Y_z\gets\bigl(Y_z+(S-1-j_{z,s})L+j_{z,s}U\bigr)/S$\;
      }
    }
  }
  Append $([A_x,B_x])_{x\in T}$ to $\mathcal L$\;
}
\Return $\mathcal L$\;
\end{algorithm}

\subsubsection{Moving an item into a child}\label{sec:overview-refine}

Instead of answering the query, \texttt{Select} may return a pair $(x,c)$
directing \texttt{Compare} to move item $x$ into the child anchored at $c$,
creating that child if necessary. We now describe this move and its effect
on feasible volume.

Algorithm~\ref{alg:restrict} fixes $X_x=c$ in the parent's order-restriction
DAG. Its call to \texttt{Normalize} (Algorithm~\ref{alg:normalize}) makes
the remaining intervals canonical without changing their feasible region
(Lemma~\ref{lem:normalization}).

\begin{algorithm}[H]
\caption{\texttt{Restrict}$(D,x,c)$: fix and remove a coordinate.}
\label{alg:restrict}
\DontPrintSemicolon
\KwIn{A canonical order-restriction DAG $D$ with $V(D)>0$, a vertex $x$, and $c\in(\ell_x,r_x)$.}
\ForEach{arc $y\to x$}{
  $r_y\gets\min(r_y,c)$\;
}
\ForEach{arc $x\to z$}{
  $\ell_z\gets\max(\ell_z,c)$\;
}
Delete $x$ and its incident arcs\;
\texttt{Normalize}$(D)$\;
\Return $D$\;
\end{algorithm}

\begin{algorithm}[H]
\caption{\texttt{Normalize}$(D)$: propagate the interval bounds.}
\label{alg:normalize}
\DontPrintSemicolon
\KwIn{An order-restriction DAG $D$.}
\ForEach{vertex $x$ in topological order}{
  $\ell_x\gets\max(\{\ell_x\}\cup\{\ell_y:y\to x\})$\;
}
\ForEach{vertex $x$ in reverse topological order}{
  $r_x\gets\min(\{r_x\}\cup\{r_y:x\to y\})$\;
}
\end{algorithm}

\Needspace{6\baselineskip}
\begin{lemma}[Coordinate restriction]\label{lem:interior}
Let $D$ be canonical with $V(D)>0$ and $c\in(\ell_x,r_x)$.
Then \textnormal{\texttt{Restrict}}$(D,x,c)$ represents the section
$X_x=c$ of $K(D)$, and
\begin{equation}\label{eq:restriction-volume}
V(\operatorname{Restrict}(D,x,c))=V(D)f_x(c)>0.
\end{equation}
\end{lemma}
\begin{proof}
See Appendix~\ref{app:geometry}.
\end{proof}

Algorithm~\ref{alg:refine} uses this operation in the tree.
Figure~\ref{fig:overview-refine} illustrates a move into an existing child.

\begin{algorithm}[H]
\caption{\texttt{RefineAt}$(x,c)$: move an item into a child.}
\label{alg:refine}
\DontPrintSemicolon
\KwIn{A free item $x$, an interior anchor $c$, and the current adversary state.}
\KwOut{The updated state, with $x$ stored in a child of its former node.}
$v\gets$ the node storing $x$\;
$D_v\gets$ \texttt{Restrict}$(D_v,x,c)$\;
\If{$v$ has no child anchored at $c$}{
  Create a child of $v$ at $c$, with an empty order-restriction DAG\;
}
$u\gets$ the child of $v$ anchored at $c$\;
Insert $x$ into $D_u$ as an isolated vertex with record $(x,0,1)$\;
\end{algorithm}

\begin{center}
\begin{minipage}{\linewidth}
\captionsetup{hypcap=false}
\centering
\begin{tikzpicture}[>=Latex,font=\small,
  group/.style={draw=ink!65,rounded corners=2pt,fill=pale},
  item/.style={circle,draw=ink,fill=white,minimum size=6mm,inner sep=1pt}]
\begin{scope}[shift={(-3.2,0)}]
\node at (0,1.55) {Before refinement};
\draw[group] (-2.4,-.45) rectangle (2.4,1.2);
\node[item] (ra) at (-1.5,.65) {$a$};
\node[item] (rx) at (0,.65) {$x$};
\node[item] (rb) at (1.5,.65) {$b$};
\draw[->,thick,accent] (ra)--(rx);
\draw[->,thick,accent] (rx)--(rb);
\fill (0,-.15) circle (2pt) node[right=4pt] {anchor $c$};
\draw[thick,ink!55] (0,-.15)--(0,-1);
\draw[group] (-1.8,-2) rectangle (1.8,-1);
\node at (0,-1.3) {Existing child at $c$};
\node at (0,-1.7) {$z$ free};
\end{scope}
\draw[->,thick] (-.55,-.2)--(.55,-.2);
\begin{scope}[shift={(3.2,0)}]
\node at (0,1.55) {After fixing $X_x=c$};
\draw[group] (-2.4,-.45) rectangle (2.4,1.2);
\node[item] at (-1.5,.65) {$a$};
\node[item] at (1.5,.65) {$b$};
\node at (0,.65) {$X_a<c<X_b$};
\fill (0,-.15) circle (2pt) node[right=4pt] {anchor $c$};
\draw[thick,ink!55] (0,-.15)--(0,-1);
\draw[group] (-1.8,-2) rectangle (1.8,-1);
\node at (0,-1.3) {Same child at $c$};
\node at (0,-1.7) {$x,z$ free (no arc)};
\end{scope}
\end{tikzpicture}
\captionof{figure}{The two arc inequalities become bounds on the remaining parent
coordinates. The new coordinate of $x$ orders it within the child, where
both $x<z$ and $z<x$ remain possible. The anchor $c$ determines where
the child block lies among the parent items. The child's constraints
determine the possible orders within that block.}
\label{fig:overview-refine}
\end{minipage}
\end{center}


At an interior anchor, the old constraints allow $x$ immediately before
or after the existing child block. Both placements satisfy the transcript,
so no earlier answer compares $x$ with an item in that block. Thus $x$
can enter the child without contradicting any earlier answer
(Appendix~\ref{app:execution}). This move can allow orders previously
excluded by the tree, while preserving every answer in the transcript.

When \texttt{Select} returns $(x,c)$, \texttt{RefineAt} moves $x$ into
the child anchored at $c$. To measure the resulting change in volume
across the tree, write
$K_v=K(D_v)$, $V_v=V(D_v)$, and define
\begin{equation}\label{eq:Z}
Z=\prod_v V_v.
\end{equation}
Initially $Z=1$, and positive node volumes give $0<Z\le1$.
Each item has one coordinate, so the product region always has dimension
$n$. This volume is not by itself the fraction of total orders consistent
with the transcript, as we will see in Section~\ref{sec:potential}.
The following identity expresses the change in $Z$ using the density
$f_x$ of $X_x$ at the parent before refinement.

\begin{samepage}
\begin{lemma}[Refinement identity]\label{lem:section-volume}
Suppose every node region has positive volume. Let $Z_{\rm before}$ and
$Z_{\rm after}$ be the product volumes before and after refining $x$ at an
interior anchor $c$. Then
\begin{equation}\label{eq:refine}
\frac{Z_{\rm after}}{Z_{\rm before}}=f_x(c).
\end{equation}
\end{lemma}
\begin{proof}
See Appendix~\ref{app:execution}.
\end{proof}
\end{samepage}

\begin{samepage}
Fixing $X_x=c$ leaves a cross-section of the parent's feasible region
with volume $V(D)f_x(c)$. The item $x$ then leaves the parent and receives
a fresh coordinate in the child. This coordinate ranges independently
over $(0,1)$, contributing a factor of one to the child's volume.
All other node volumes are unchanged, so the product volume is
multiplied by $f_x(c)$.

\end{samepage}

\begin{samepage}
Figure~\ref{fig:section-volume} provides an example of the refinement operation.
The parent region $0<X_A<X_B<1$ has area $1/2$. Fixing
$X_A=1/4$ leaves the interval $X_B\in(1/4,1)$ of length $3/4$. The new
child coordinate $U_A\in(0,1)$ turns this interval into a rectangle of
area $3/4$. Refinement therefore multiplies $Z$ by $3/2$.
Both regions represent the order $A<B$. Replacing the fixed parent
coordinate by a fresh child coordinate gives the larger area.

\end{samepage}

\begin{figure}[tb]
\centering
\begin{tikzpicture}[x=3.25cm,y=3.25cm,>=Latex,font=\small]
\begin{scope}
\node at (.5,1.38) {Before refinement};
\fill[pale] (0,0)--(0,1)--(1,1)--cycle;
\draw[ink!55] (0,0)--(1,1)--(0,1);
\draw[->] (0,0)--(1.12,0) node[right] {$X_A$};
\draw[->] (0,0)--(0,1.12) node[above] {$X_B$};
\draw[dashed,ink!60] (.25,0)--(.25,.25);
\draw[accent,very thick] (.25,.25)--(.25,1);
\node[below] at (.25,0) {$\frac14$};
\node[below left] at (0,0) {$0$};
\node[below] at (1,0) {$1$};
\node[left] at (0,1) {$1$};
\node at (.55,.83) {area $\frac12$};
\end{scope}
\draw[->,thick] (1.2,.53)--(1.63,.53);
\node[above] at (1.415,.56) {refine $A$};
\begin{scope}[shift={(1.9,0)}]
\node at (.5,1.38) {After refinement};
\fill[pale] (0,.25) rectangle (1,1);
\draw[ink!55] (0,.25)--(1,.25)--(1,1)--(0,1);
\draw[->] (0,0)--(1.12,0) node[right] {$U_A$};
\draw[->] (0,0)--(0,1.12) node[above] {$X_B$};
\node[below left] at (0,0) {$0$};
\node[left] at (0,.25) {$\frac14$};
\node[below] at (1,0) {$1$};
\node[left] at (0,1) {$1$};
\node at (.5,.65) {area $\frac34$};
\end{scope}
\end{tikzpicture}
\caption{The highlighted section of the triangle has length $3/4$.
Replacing the fixed parent coordinate by a fresh unit coordinate in the
child gives the rectangle on the right. Its area is $3/2$ times the
original area.}
\label{fig:section-volume}
\end{figure}

We call the change
\begin{equation}\label{eq:refinement-gain}
 g=\log\frac{Z_{\rm after}}{Z_{\rm before}}=\log f_x(c)
\end{equation}
the refinement's \emph{volume gain}. Lemma~\ref{lem:local-routines}
guarantees that a refinement requested by
\texttt{Select} gains more than $k$ in $\log Z$, whereas an answer
loses at most $-\log(1/2-1/(100k))=1+O(1/k)$.
Thus an inconclusive call to \texttt{Select} actually restores volume as it moves
an item. Since $Z\le1$, these increases must be offset by losses from
answers and repairs.
\label{sec:refinement-volume}

\subsubsection{Keeping the in-node DAGs small}\label{sec:repairs}

To keep the DAGs within the bounds of Lemma~\ref{lem:local-routines},
Algorithm~\ref{alg:repair} maintains degree below $k$ and directed paths
with fewer than
\begin{equation}\label{eq:path-threshold}
H=2^k
\end{equation}
vertices between comparisons. After one arc is inserted, the degree is
at most $k$ and every directed path has fewer than $2H=2^{k+1}$ vertices.
Further insertions could exceed these bounds, so \texttt{Repair} restores
the stricter bounds before the next comparison.

A repair selects items to move into children so that the parent's DAG
again satisfies the degree and path-length bounds. Its routine
\texttt{ChooseAnchor}$(D,x)$ chooses an interior position for the
specified item $x$. Lemma~\ref{lem:anchor-selection} gives the guarantee
needed for these choices.

\begin{algorithm}[H]
\caption{\texttt{Repair}$(v)$: restore the graph bounds after an answer.}
\label{alg:repair}
\DontPrintSemicolon
\KwIn{The node $v$ at which the answer was determined.}
\If{the graph at $v$ has a directed path on $H$ vertices}{
  $L\gets$ the lexicographically first $H$-vertex path, in path order\;
  \ForEach{$x\in L$ in path order}{
    $c\gets$ \texttt{ChooseAnchor}$(D_v,x)$\;
    \texttt{RefineAt}$(x,c)$\;
  }
}
\ElseIf{a vertex at $v$ has degree $k$}{
  $x\gets$ the smallest label of degree $k$\;
  $c\gets$ \texttt{ChooseAnchor}$(D_v,x)$\;
  \texttt{RefineAt}$(x,c)$\;
}
\end{algorithm}

One repair suffices: every new path on $H$ vertices contains the inserted
arc, and only its endpoints can newly reach degree $k$. Either repair
removes an endpoint of that arc, leaving a subgraph of the graph before
the answer.

\begin{lemma}[Anchor selection]\label{lem:anchor-selection}
Under the assumptions on $D$ in Lemma~\ref{lem:local-routines},
for any vertex $x$, \textnormal{\texttt{ChooseAnchor}}$(D,x)$ returns a dyadic
$c\in(\ell_x,r_x)$. The routine is deterministic and uses only a
neighborhood of $x$ whose radius depends on $k$.

Every position $c$ returned by \textnormal{\texttt{Select}} or
\textnormal{\texttt{ChooseAnchor}}, written in reduced form as
$c=(2i+1)/2^{m+1}$ with $m\ge0$, satisfies
\begin{equation}\label{eq:tariff}
\log f_x(c)\ge(1-1/k)m-4.
\end{equation}
\end{lemma}
\begin{proof}
See Appendices~\ref{sec:oracle} and~\ref{app:execution}.
\end{proof}

Since $m\ge0$, each repair move loses at most four in $\log Z$.
For a path repair, the dependence on $m$ yields a stronger lower bound
on the total change in $\log Z$. Section~\ref{sec:rare-refinements} uses
this bound to limit the number of refinements.