Front–Concatenation Shuffles on N: Tail Rigidity, Universal Coverage Laws, and a Deterministic Priority–Queue Framework

We introduce a deterministic two--parameter \emph{front--concatenation shuffle} on the positive integers, equivalently a priority--queue service discipline in which at step~$n$ the element in position~$n$ is expelled, the next $m$ elements are promoted to the front, and the preceding $p$ elements are demoted behind them. Exhaustivity---whether every integer is eventually expelled---is the combinatorial analogue of queue stability. Our first main result is a \textbf{parameter--rigidity theorem} for the $m=1$ family: for \emph{every} $p\ge0$, the expelled sequence is $E_n=2n-1$ and precisely the odd integers are expelled, despite the $p$--dependent reorganization of the internal queue state. An infinite family of combinatorial operators, parameterized by an arbitrary non--negative integer, thus produce identical output. We prove a \emph{tail rigidity theorem} reducing the infinite dynamics to a finite core of length $n+m-2$ for all $(m,p)$, and for $m=2$ we give complete classifications: $(2,0)$ is exhaustive with $E_n=n+(-1)^n$, and $(2,1)$ is exhaustive via an explicit ``$3x-1$'' parity cascade. The remaining $(2,p)$ cases reduce to a floor--dilation map $g_r(W)=W+\lfloor W/r\rfloor$. We then extend the theory to all $m\ge 2$ and establish two new universal results.A \textbf{Universal Arithmetic Progression Theorem}: for every $(m,p)$ with $m\ge 2$ and $T:=m+p$, the expelled sequence contains two deterministic APs of stride~$T$ and common difference~$2(T-1)$, proved via the core recursion by tracking the entry--to--expulsion path of each new label.A \textbf{Coverage Law}: the asymptotic fraction of integers expelled up to the running maximum converges to $T/\!\bigl(2(T-1)\bigr)$, interpolating between full exhaustivity at $T=2$ and the structural density~$1/2$ of the $m=1$ regime as $T\to\infty$. This dichotomy---\emph{structural} non--exhaustivity (only odd integers expelled) versus \emph{dynamical} near--non--exhaustivity (all integers eventually expelled, but with growing backlog)---is the paper's central conceptual contribution. Finally, the $r$--adic avoidance set for $g_r$ is a Cantor--type fractal of Hausdorff dimension $\log(r-1)/\log r$, non--terminating integers have density~$0$, and stopping times are geometrically distributed under uniform base--$r$ digits.