\section{Proofs of the consequences}\label{app:consequences}

\subsection{Producing a target order}

\begin{proof}[Proof of Corollary~\ref{cor:production}]
A successful output assigns each key to one slot of $R$. Every total
order satisfying the transcript must respect this assignment, so
$T_q\le e(R)$. For all sufficiently large $n$, apply
Theorem~\ref{thm:fixed-stage} with the parameter $k=k(n)$ selected in
Section~\ref{sec:parameter-selection}. It gives
\[
q\ge\frac{I(R)}{1+\delta_{k(n)}}=(1-o(1))I(R),
\]
since $k(n)\to\infty$ and $\delta_k=O(\log k/k)$. The $o(1)$ term
depends only on $n$, so the bound is uniform over all targets $R$.
\end{proof}

\subsection{A compatible partition into layers}

The reduction for an initial partial order needs an ordered partition
whose layers retain many permutations. Cardinal et al.'s construction gives such a partition.

\begin{lemma}[Weak-order extension]\label{lem:weak-order-extension}
Given a partial order $P$ on $n$ elements, one can deterministically
construct in polynomial time a weak order $W$ extending $P$ such that
\[
\log e(W)\ge\log e(P)-C_0 n\log\log n
\]
for an absolute constant $C_0$.
\end{lemma}
\begin{proof}
Cardinal et al.~\cite[Section~3, Lemmas~1 and~3]{cardinal-production}
construct $W$ in polynomial time with
\[
I(W)\le I(P)+2n\log\bigl(I(P)/n+1\bigr)+O(n).
\]
Since $I(P)\le\log(n!)\le n\log n$, the extra term is
$O(n\log\log n)$. Substitute
$I(W)-I(P)=\log e(P)-\log e(W)$.
For two elements, take $W=P$.
\end{proof}

An arbitrary partition into antichains need not admit a compatible layer
order. For example, the relations $a<b$ and $c<d$ permit the antichains
$\{a,d\}$ and $\{b,c\}$, but require opposite orders between them.
Lemma~\ref{lem:weak-order-extension} supplies both the partition and a
layer order respecting all initial relations.

\begin{proof}[Proof of Corollary~\ref{cor:initial-poset}]
Construct $W$ using Lemma~\ref{lem:weak-order-extension}, and let its
layers have sizes $m_1,\ldots,m_t$. Choose $k=k(n)$ once, using the full
input size. Within every layer of size at least two, run a copy of the
ordinary adversary with these parameters and its local horizon
$Q(m_i)=m_i\ceil{\log m_i}$. A singleton needs no comparisons. Answer
comparisons between layers from their fixed order.

Each local transcript has a consistent total order. Concatenating these
orders gives a linear extension of $W$ and hence of $P$, proving legality.
At termination, each layer must have a unique possible order: two possible
orders in one layer, combined with the same orders in the others, would
give two global orders consistent with the full transcript.

Let $q_i$ count comparisons within layer $i$. Theorem~\ref{thm:fixed-stage}
applies to the local transcript with $T_{q_i}=1$ and gives
\[
q_i\ge\frac{\log(m_i!)}{1+\delta_k}.
\]
The inequality also holds for a singleton. Since $\sum_i m_i=n$ and
$e(W)=\prod_i m_i!$, summing gives
\begin{align*}
q\ge\sum_i q_i
&\ge\frac{\log e(W)}{1+\delta_k}\\
&\ge\frac{\log e(P)-C_0 n\log\log n}{1+\delta_k}.
\end{align*}
As $k(n)\to\infty$, this implies the stated bound, uniformly over $P$.

The common choice of $k(n)$ is essential to this estimate: each layer
has the same $\delta_k$, even when its size stays small.
It also preserves polynomial time in $n$. Each finite calculation
enumerates at most $E_k\le n$ assignments. Across all layers, the horizons
sum to at most $n\ceil{\log n}$, and the refinement and precision bounds
of Section~\ref{sec:runtime} apply with the ambient size $n$.
The construction of $W$ is polynomial-time as well. For the finitely
many sizes at which no tuple qualifies, use a fixed topological order of
$P$.
\end{proof}

\subsection{Amplifying a constant-factor estimate}
\label{app:counting-amplification}

Suppose a deterministic polynomial-time algorithm estimates $V(D)>0$
within a fixed factor $C>1$. Let $D^{(k)}$ be the disjoint union of $k$
copies of the order-restriction DAG $D$, each with the same interval
bounds. Its feasible region is a Cartesian product, so
\[
V(D^{(k)})=V(D)^k.
\]
A factor-$C$ estimate for this volume, followed by a $k$th root, estimates
$V(D)$ within a factor $C^{1/k}$. Taking $k=O(1/\varepsilon)$ makes this
factor at most $1+\varepsilon/4$. Computing the root to relative error at
most $\varepsilon/4$ then gives relative error at most $\varepsilon$.
The expanded input and the required rational arithmetic have size
polynomial in the original input length and $1/\varepsilon$.
Disjoint union preserves both the maximum degree and the directed-path
bound, so the argument applies to each fixed-$d,h$ class.

For linear-extension counts, if $Q$ is the disjoint union of $k$ copies
of an $n$-element partial order $P$, then
\[
e(Q)=\frac{(kn)!}{(n!)^k}\,e(P)^k.
\]
Choose a linear extension within each copy and then interleave the
copies, giving the displayed multinomial factor. Divide a factor-$C$
estimate for $e(Q)$ by this explicitly computable factor before taking
the root. The factorials have $O(kn\log(kn))$ bits, so the same
polynomial-time conclusion holds. In particular, a deterministic PTAS,
run at any fixed sufficiently small error, would already yield an
FPTAS.

\subsection{From approximate counting to an adversary}
\label{app:counting-adversary}

Suppose a deterministic FPTAS for $e(P)$ is available. For an unresolved
comparison, let $a,b$ be the positive numbers of extensions consistent
with its two answers. Estimate both counts to relative error at most
$\eta=1/n$ and choose the larger estimate. If the chosen branch has
count $a$, then $(1+\eta)a\ge(1-\eta)b$, and hence
\[
a\ge\frac{1-\eta}{2}(a+b).
\]
Already determined comparisons lose no extensions. Starting from any
supplied $P$, after $q$ answers at least
$e(P)((1-\eta)/2)^q$ extensions remain. A correct sorter can terminate
only when this number is at most one, so
\[
q\ge\frac{\log e(P)}{1-\log(1-1/n)}
  =(1-O(1/n))\log e(P).
\]
The approximation calls use polynomial time, and every chosen answer
is legal. This proves the claimed implication uniformly over $P$.

\subsection{Sampling linear extensions}\label{app:exact-sampling}

\begin{proof}[Proof of Corollary~\ref{cor:exact-sampling}]
All asymptotic constants in this proof may depend on the fixed parameters
$d,h$.
Give every vertex the interval $(0,1)$, and choose $S,p$ as in
\eqref{eq:digit-alphabet}--\eqref{eq:moment-power}. We use coupling from
the past~\cite{propp-wilson}, stopping when all coordinate orders are
certified, as in Huber's sampler~\cite{huber-sampling}.

Fix a topological order. For each negative integer $s$, let $F_s$ be a
full sweep of \eqref{eq:digit-update}, using independent uniform digits
at every vertex. Retain each digit once generated. For a horizon $t$,
apply $F_{-t},\ldots,F_{-1}$ in that order to the all-zero and all-one
vectors, obtaining $A(t),B(t)$. A larger horizon prepends older sweeps
and replays the entire history, without changing any previously used
digit.

Each sweep is increasing and preserves the closed feasible region.
Consequently,
\[
A(t)\le A(t+1)\le B(t+1)\le B(t).
\]
Appendix~\ref{app:coupling} gives
$\E(B_x(t)-A_x(t))^p\le2^{-t}$ for every coordinate $x$.
Together with nesting, this implies that both vectors converge almost
surely to a common limit $Z$. To identify its law, take $U$ uniformly
distributed on $K(D)$, independently of the digit history. Applying the
same $t$ sweeps to $U$ gives a uniform point $Y(t)$, since each sweep
preserves the uniform law after averaging its digits
(Appendix~\ref{sec:oracle}). Monotonicity gives
$A(t)\le Y(t)\le B(t)$, so $Y(t)\to Z$ almost surely. Thus $Z$ is
uniform on $K(D)$; it is used only in the proof.

Start with $t_0=\ceil{\log(n+1)}$ and double the horizon until the
intervals $[A_x(t),B_x(t)]$ are pairwise disjoint. Sort their lower
endpoints and check that each upper endpoint is strictly below the next
lower endpoint. At termination, return this order. It equals the order
of $Z$, which is a uniform linear extension: every compatible
permutation occupies a simplex of volume $1/n!$. Since $Z$ has distinct
coordinates almost surely and the widths vanish, the algorithm
terminates almost surely. The stopping rule therefore introduces no
bias.

For the running time, the sorted coordinates of $Z$ have the
order-statistic distribution of $n$ independent uniform points on
$(0,1)$. Indeed, conditioning those points on their relative permutation
being a linear extension leaves their sorted values unchanged. A union
bound gives
\[
\Prb\bigl(\min_{x\ne y}|Z_x-Z_y|\le2\delta\bigr)
\le2n(n-1)\delta.
\]
If every width is at most $\delta$ and every coordinate gap exceeds
$2\delta$, the enclosing intervals are disjoint. Markov's inequality
and a union bound therefore give
\[
\Prb(\text{failure at horizon }t)
\le n2^{-t}\delta^{-p}+2n(n-1)\delta.
\]
Taking $\delta=2^{-t/(p+1)}$ yields
\begin{equation}\label{eq:exact-sampling-tail}
\Prb(\text{failure at horizon }t)
\le(2n^2-n)2^{-t/(p+1)}.
\end{equation}
Summing this tail over doubled horizons shows that the final horizon
$T$ satisfies $\E T=O(\log n)$ and
$\E T^2=O(\log^2 n)$.

A topological order and incoming and outgoing adjacency lists take
$O(n)$ operations to prepare. Each stage uses $O(nt)$
arithmetic operations, including the $O(n\log n)$ comparisons needed
to sort the intervals, since $t\ge t_0\ge\log n$. Summing over doubled
horizons gives $O(nT)$ operations. Each digit uses exactly
$\log S$ fair bits, and retaining the history uses only $nT\log S$
bits in total. This proves both expected bounds.

All computed endpoints are exact dyadic rationals. After $t$ sweeps they
have at most $ht\log S$ fractional bits: within one sweep a new value
can depend on earlier updates only along a predecessor path of at most
$h$ vertices, and each update adds at most $\log S$ bits. Thus the
expected bit cost of the arithmetic is $O(n\log^2 n)$ in a
random-access model, by summing $O(nt^2)$ over the stages and
using the bound on $\E T^2$.
\end{proof}