\section{Completion of the proofs}
\label{sec:completion}

\begin{proof}[Proof of Theorem~\ref{thm:polynomial}]
Fix $0<\alpha<1$ and set
\begin{equation}
\label{eq:parameter-choice}
\beta=\alpha^{-1}-1,\qquad
\eta=\min\{\beta,1/6\},\qquad
k=\lfloor\eta^{-1}\rfloor+1,\qquad
M=4k,\qquad K=6M+1.
\end{equation}
Thus $\eta k>1$.
Choose $m_*$ above the thresholds in Lemma~\ref{lem:local} and Proposition~\ref{prop:safe-menu} for these fixed parameters and $B=4$.
Increase it, if necessary, so that $m_*\ge k$ and
\begin{equation*}
C_{k,4}m^{1-\eta k}\le c_K/2\qquad(m\ge m_*),
\end{equation*}
where $c_K$ is the lower bound in Lemma~\ref{lem:local} and $C_{k,4}$ is the constant in Proposition~\ref{prop:safe-menu}.
All choices depend only on $\alpha$ and the absolute constants in the cited theorems.
Take an integer $C_\alpha\ge\max\{4m_*,4\}$.

Suppose that $C_\alpha\le n=|A|\le p^\alpha$.
In particular $p$ is odd.
The construction of Lemma~\ref{lem:cells} gives $m\ge n/4\ge m_*$ and
\begin{equation*}
p\ge n^{1/\alpha}\ge m^{1/\alpha}=m^{1+\beta}.
\end{equation*}
In the original probability space, Lemma~\ref{lem:local} gives $\Pr(\mathcal L_K)\ge c_K$.
Condition on the nonvariable entries and the variable set $X$.
The decorations are fixed on each such fibre, and the variables remain a uniform permutation of $X$.
Proposition~\ref{prop:safe-menu} therefore bounds the conditional probability of $\mathcal R_{\mathrm{menu}}^c$ by $C_{k,4}m^{1-\eta k}$ on every nonempty fibre.
Averaging gives
\begin{align*}
\Pr(\mathcal L_K\cap\mathcal R_{\mathrm{menu}})
&\ge \Pr(\mathcal L_K)-\Pr(\mathcal R_{\mathrm{menu}}^c) \\
&\ge c_K/2>0.
\end{align*}
No independence of these events is required.
For an outcome in their intersection, apply the variable permutation $\sigma$ from Proposition~\ref{prop:repair} to the cell arrangement and read off the resulting word.
This is an ordering of $A$, since only its variable coordinates have been permuted.
Nonempty prefixes ending in the same cell are distinct by Lemma~\ref{lem:cells}.
If two equal prefixes end in distinct cells, Proposition~\ref{prop:repair} places them at distance at most $4M$, whereas Lemma~\ref{lem:replay} excludes such a collision because $|\sigma(j)-j|<M$ and $K=6M+1$.
Thus the ordering is valid.
\end{proof}

\begin{proof}[Proof of Corollary~\ref{cor:large-prime}]
The large-set theorem \citep[Theorem~1.4]{Bedert2025b} gives an absolute $c>0$ such that, for every finite group $G$, every $S\subseteq G\setminus\{e\}$ with $|S|\ge |G|^{1-c}$ has a valid ordering.
Put $c_0=\min\{c,1/2\}$ and $\alpha=1-c_0/2$.
Then
\begin{equation*}
\frac{p^\alpha}{(2p)^{1-c_0}}
=2^{c_0-1}p^{c_0/2}\longrightarrow\infty.
\end{equation*}
Thus the polynomial range of Theorem~\ref{thm:polynomial} eventually overlaps the large-set range for $D_{2p}$.

For the small-set range, the semidirect-product theorem \citep[Theorem~1.3]{Costa2025} applies to $\Z_p\rtimes H$ when the fixed finite abelian group $H$ is strongly sequenceable and acts by signs.
The group $H=\Z_2$ is strongly sequenceable, since its only nonempty identity-free subset is a singleton.
Taking its action by inversion gives an absolute $c_s>0$ such that every identity-free dihedral subset of size at most
\begin{equation*}
\exp\bigl(c_s(\log p)^{1/4}\bigr)
\end{equation*}
has a sequencing.
Their condition also excludes intermediate identity prefixes and hence implies the validity required here.
This endpoint eventually exceeds the fixed $C_\alpha$.
The small-set, polynomial and large-set intervals therefore cover every integer from $1$ to $2p-1$ for sufficiently large primes.
The empty set is immediate.
\end{proof}