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

We introduce a deterministic two--parameter 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 parameter--rigidity theorem for the m=1 family: for every p0, the expelled sequence is Eₙ=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 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+ (-1) ⁿ, and (2, 1) is exhaustive via an explicit ``3x-1'' parity cascade. The remaining (2, p) cases reduce to a floor--dilation map gᵣ (W) =W+ W/r. We then extend the theory to all m 2 and establish two new universal results. A Universal Arithmetic Progression Theorem: for every (m, p) with m 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 Coverage Law: the asymptotic fraction of integers expelled up to the running maximum converges to T/\! (2 (T-1) ), interpolating between full exhaustivity at T=2 and the structural density~1/2 of the m=1 regime as T. This dichotomy---structural non--exhaustivity (only odd integers expelled) versus 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ᵣ is a Cantor--type fractal of Hausdorff dimension (r-1) / r, non--terminating integers have density~0, and stopping times are geometrically distributed under uniform base--r digits.