\section{Introduction}
\label{sec:intro}

An ordering $a_1,\ldots,a_n$ of a finite subset $A$ of a group is \emph{valid} if its nonempty partial products
\begin{equation*}
P_1=a_1,\quad P_2=a_1a_2,\quad\ldots,\quad P_n=a_1\cdots a_n
\end{equation*}
are pairwise distinct.
The empty product $P_0=e$ is excluded from this condition.
\citet[Problem~10, p.~36]{Graham1971} asked whether every subset of $\Z_p\setminus\{0\}$ has a valid ordering, for every prime $p$; the question was repeated by \citet[p.~95]{ErdosGraham1980}.
The corresponding nonabelian problem asks for distinct partial products.
We consider the dihedral group $D_{2p}$ of order $2p$.

\begin{theorem}
\label{thm:polynomial}
For every $0<\alpha<1$ there is an integer $C_\alpha$ such that, for every prime $p$, every subset $A\subseteq D_{2p}\setminus\{e\}$ satisfying
\begin{equation*}
C_\alpha\le |A|\le p^\alpha
\end{equation*}
has a valid ordering.
\end{theorem}

\begin{corollary}
\label{cor:large-prime}
For all sufficiently large primes $p$, every subset of $D_{2p}\setminus\{e\}$ has a valid ordering.
\end{corollary}

The proof of Corollary~\ref{cor:large-prime} uses the eventual overlap of three size ranges and leaves a finite set of primes untreated.
The assertion for every prime is unresolved.
The constants in Theorem~\ref{thm:polynomial} are not optimised.

The size range in Theorem~\ref{thm:polynomial} lies between two existing results.
The small-set theorem \citep[Theorem~1.3]{Costa2025} gives a stronger sequencing property for dihedral subsets of size at most $\exp(c_s(\log p)^{1/4})$, with an absolute $c_s>0$.
It extends the small-set method of \citet{Bedert2025a} to suitable semidirect products.
The general large-set theorem \citep[Theorem~1.4]{Bedert2025b} guarantees that, for an absolute $c>0$, every subset $S\subseteq G\setminus\{e\}$ of any finite group $G$ with $|S|\ge |G|^{1-c}$ has a valid ordering.
These ranges overlap the range of Theorem~\ref{thm:polynomial} for a suitable fixed $\alpha<1$, giving Corollary~\ref{cor:large-prime}.

\citet{Ollis2019} studied distinct partial products in dihedral groups.
For prime cyclic groups, \citet[Theorem~1.2]{Pham2026} proved the intermediate range $C_\alpha\le |A|\le p^\alpha$, and hence Graham's conjecture for sufficiently large primes.
Their exponent is written $1-\alpha$; we have reparametrised it.
Their proof combines subset-sum anticoncentration with local changes to a random ordering.
The dihedral intermediate range is explicitly identified as a further problem after extensions to cyclic groups \citep[Section~7]{Costa2026a}.
Theorem~\ref{thm:polynomial} supplies that range by an additive reduction which retains the signs caused by reflections.

There is also a graph formulation.
In the directed Cayley graph, give the edge $g\longrightarrow ga$ colour $a$.
For nonempty $A$, a valid ordering exists if and only if some $a\in A$ can be omitted so that the remaining colours form a simple directed rainbow path.
Indeed, left multiplication of $P_1,\ldots,P_n$ by $a_1^{-1}$ gives the distinct prefixes, including the empty prefix, of $a_2,\ldots,a_n$.
Conversely, prepending the omitted element to such an ordering translates its entire prefix list.
This equivalence explains the endpoint convention: a simple path using all colours would impose the additional requirement that $P_0$ be distinct from every $P_j$.

\subsection{The proof}
\label{subsec:proof-outline}

Write $D_{2p}=\Fp\rtimes\Z_2$, with
\begin{equation*}
(x,\epsilon)(y,\delta)
=\bigl(x+(-1)^\epsilon y,\epsilon+\delta\bigr).
\end{equation*}
A reflection reverses every subsequent sign until the next reflection.
Pairing reflections into cells of length at most four produces $m\ge |A|/4$ variable positions, all with coefficient $+1$.
After the other entries have been fixed, the variables $x_1,\ldots,x_m$ form a uniform permutation of a fixed subset of $\Fp$.
Every partial product in cell $j$ then belongs to
\begin{equation*}
s_j+\D_j,\qquad s_j=\sum_{h\le j}x_h,
\qquad \D_j\subseteq\Fp\times\Z_2,\quad |\D_j|\le4,
\end{equation*}
where the sets $\D_j$ remain attached to their positions when variables are permuted.
Parity-preserving permutations in semidirect products already appear in \citep[Section~2]{Costa2025}.

For each fixed $K$, the permutation local lemma gives a probability $c_K>0$ that every short identity subword is absent, even after arbitrary variable permutations in any window of at most $K$ cells.
The lower bound is uniform in the ratio of the rotation and reflection counts.
For a small reflection pool, a pattern count proportional to its size cancels the corresponding probability denominator; see Appendix~\ref{app:local}.
Separately, with probability tending to one on every fixed-decoration fibre, each member of a predetermined linear-size family of blocks has a cyclic rotation avoiding all distant target sets.
Two staggered passes of these rotations preserve selected cut sums and move every variable by a bounded distance.
Any remaining collision can therefore be reproduced by a permutation inside an original bounded window, contradicting the local condition.

The distant-avoidance estimate uses the sharp subset-sum theorem \citep[Theorem~1.3]{Pham2026}.
If all $\ell$ cyclic rotations of one block fail, one collision per rotation gives an affine system $Hx=z$.
Suppose its target anchors form $q$ clusters separated from the source cluster.
The affine dimension of the columns of $H$ is at least $(\ell+q)/2$; long gaps also supply $q$ independent differences of repeated columns.
Conditioning on disjoint position pools then yields
\begin{equation*}
\Pr(Hx=z)=O\bigl(m^{-(\ell+q)/2-\eta q}\bigr),
\qquad \eta=\min\{\beta,1/6\},\quad p\ge m^{1+\beta}.
\end{equation*}
With gap scale $m^{1/3}$, there are $O(m^qm^{(\ell-q)/3})$ anchor tuples, giving a total of $O(m^{-\eta\ell})$.
Clustered targets have fewer possible locations; separated targets give stronger anticoncentration.
This balance permits a union bound over the entire repair family.

The reservoir exposure is related to the chain estimate \citep[Corollary~4.2]{Pham2026} and to the standard rank-exposure argument \citep{Odlyzko1988}; see also \citep[Lemma~3.7]{Kwan2025}.
The boundary constraints \citep[Section~6]{Bedert2025a} and transposition repairs \citep[Section~5]{Pham2026} are antecedents of the random-ordering and local-repair approach.
The fixed-offset calculation, the repeated-column estimate and the two-pass rotation argument are proved below.