% Hexagon source adaptation of the published Zenodo edition. % Changes are limited to packaging, bibliography rendering, navigation and archive links. % Mathematical formulas and their order are preserved; see the local integrity record. \PassOptionsToPackage{expansion=false,nopatch=footnote}{microtype} \documentclass[11pt]{article} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage{lmodern,microtype} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage[a4paper,margin=25mm,headheight=14pt]{geometry} \usepackage{booktabs,array,longtable} \usepackage{tikz,fancyhdr} \usepackage{xurl} \usepackage[colorlinks=true,allcolors=blue!45!black]{hyperref} \hypersetup{pdftitle={Certified rational-anchor filtering for exact GPU scans of power-residue runs},pdfauthor={Brice Pouly}} \pagestyle{fancy}\fancyhf{} \fancyhead[L]{\small Exact GPU scans of power-residue runs} \fancyhead[R]{}\fancyfoot[C]{\thepage} \renewcommand{\headrulewidth}{0.3pt} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \theoremstyle{definition}\newtheorem{remark}[theorem]{Remark} \newcommand{\Fp}{\mathbb F_p} \newcommand{\Z}{\mathbb Z} \newcommand{\cl}{c_r} \newcommand{\data}{\texttt{results/gpu-algorithms/2026-10-02/}} \newcolumntype{P}[1]{>{\raggedright\arraybackslash}p{#1}} \title{Certified rational-anchor filtering\\ for exact GPU scans of power-residue runs} \author{Brice Pouly\thanks{Prepared with artificial-intelligence assistance; see the declaration at the end.}} \date{12 October 2026} \hypersetup{pdfsubject={Publication edition v1.0; 12 October 2026}} \usepackage{bookmark} \begin{document}\maketitle \begin{abstract} We study exact longest monochromatic runs of power-residue colourings, including neutral prefixes and least canonical witnesses. A certified rational cover represents every relevant interval inside a short signed character table. A reflection-compatible schedule retains an anchor; conservative filters reject only known contradictions, bilateral completion recovers the full run, and tie-preserving reduction selects its least witness. We prove this exact-success contract and describe its CUDA realization with separate arithmetic domains below $2^{32}$ and $2^{33}$. On one RTX 5090, two reserved cohorts give ratios $24.00$ and $10.95$ of sums of hot per-prime medians against the identified historical dense engine. A separate batch study gives throughput factors $1.23$--$2.58$ against an already optimized reference. The experiments have different timing boundaries and their factors are reported separately. Short-table multiplicative extraction has close algorithmic antecedents in cryptanalysis; our contribution is its certified organization for exhaustive maxima and witnesses and its measured implementation. Square-root-sized cover parameters do not give a general $O(\sqrt p)$ running-time bound. \end{abstract} \noindent\textbf{Keywords.} Multiplicative characters; monochromatic runs; Rabung construction; rational approximation; CUDA; reproducible computation. \section{Problem and contribution} Rabung's construction uses power-residue colourings to produce lower bounds for van der Waerden numbers~\cite{rabung}. A prime and a colour count encode the colouring succinctly, but the finite conditions must still be checked. Computing an exact run profile is therefore useful both for searching for candidate certificates and for building an experimental census. Distributed searches by Monroe provide an important computational predecessor~\cite{monroe,monroecode}. The published certificates paper separates GPU discovery from pointwise certificate verification~\cite{bounds,boundsv2}. The present paper treats the scanner itself as the object of study. Its exactness theorem concerns ordinary maxima, prefixes and canonical witnesses. The coverage proof and controlled measurements establish this computational contract independently of any census classification or limiting probability law. \paragraph{Reading contract.} A successful scan returns $(M_r,L_r,K_r,w_r)$: the largest ordinary run, the neutral prefix, the Rabung boundary threshold and the least start of a maximizing run. Section~\ref{sec:contract} fixes these conventions. Sections~3--4 establish coverage and conservative selection; Sections~5--6 explain profile sharing and execution; Sections~7--8 distinguish timings from implementation checks. Capacity refusal is a reported failure, not a statement that long runs are absent. The central difficulty is to reduce expensive character evaluations without assuming that long runs behave randomly. A probabilistic estimate for a typical maximum can guide experiments, but cannot justify discarding a candidate in an exact scan. We instead construct a geometric hitting set: every relevant interval has a rational representation with bounded numerator and denominator; a short monochromatic anchor then identifies a candidate whose maximal extent is reconstructed exactly. The contributions developed here are an integer certificate for the cover, a reflection-compatible anchor schedule, conservative bit filters, and an implementation that retains exact maxima, prefixes and canonical witnesses. The implementation combines adaptive warp partitioning, character-profile sharing and concurrent streams, with explicit failures for resource or domain violations. The measured gains have two distinct baselines: the historical dense engine, and a later qualified sparse engine. This distinction is essential to assessing the scale of the improvement. Minkowski's theorem, multiplicativity, Montgomery reduction and CUDA streams are established tools. Our claims concern their explicit assembly for this finite scanning problem and the archived measurements. The article does not claim priority for rational approximation or for any general-purpose GPU technique. The related work below identifies close algorithmic precedents. We make no claim that the primitives or their use for extracting sequences were invented here, and no exhaustive priority claim for the complete assembly. \paragraph{Scope.} The experiments use every $r\in\{2,\ldots,9\}$ dividing $p-1$, rather than only a fixed intersection of congruence classes. The optimized workers accept prime inputs $1000\le p<2^{33}$, using distinct 32-bit and wider paths. Type bounds do not promise successful execution for every input: table, seed and queue guards may refuse a case. Small-prime handling belongs to a separate exact preparation path. All measurements discussed here predate the completed atlas campaign. The atlas and new numerical bounds retain their own evidence; dissemination and evidence limits are collected in Section~\ref{sec:reproducibility}. \subsection{Related work and the precise contribution} First occurrences of power-residue runs were studied by Lehmer and Lehmer and by Rabung and Jordan~\cite{lehmer,rabungjordan}. Buell and Hudson computed longest quadratic-residue and nonresidue runs for primes below 420\,000~\cite{buell}. Their publisher's abstract and bibliography establish that the observable and a census of maxima are older. Their full paper and LSU report 83-017 were not obtained; their internal algorithm is therefore not claimed to differ from ours in every respect. Beullens, Beyne, Udovenko and Vitto~\cite{beullens}, Sections 3.2, 3.4 and 7.2, already exploit multiplicativity, arithmetic subsequences, denominators and reversal to extract many normalized sequences from a short table, with extensions to power-residue symbols. Their Section 3.1 also gives a deterministic table-search variant. Kalu\dj erovi\'c, Kleinjung and Kosti\'c~\cite{kkk}, Sections 3--5 and Appendix A, develop multiplicative extraction, reuse, reversal and bit-matrix transposition. These are close algorithmic precedents, rather than merely the same elementary identity. Their key-recovery contract does not automatically supply exhaustive run maxima and their canonical ties. Conversely, this different output contract does not erase the precedent for the primitives. We cite the revised ePrint text for these details; the related ANTS XIV article has a different title~\cite{kkkants}. Small modular representatives also belong to classical Thue and Euclidean methods and rational reconstruction~\cite{shoup,wang}. Reconstruction seeks a small fraction, often unique if it exists in a regime $2BDp$ and ensures existence for every relevant interval. Neither the lattice principle nor rational normalization is new. The contribution claimed here is the cover--hitting-set--conservative-filter--completion composition with a stated output contract, not priority for its ingredients. \begin{table}[ht] \centering\small \begin{tabular}{P{.24\textwidth}P{.31\textwidth}P{.37\textwidth}} \toprule Predecessor & Work and output & Relation to this scanner\\\midrule Buell--Hudson & Quadratic run maxima and census & Same kind of observable; internal algorithm not inspected.\\ Monroe paper/code & Full power table, shared orders, maximum/prefix/boundary threshold & Dense precedent; no per-position exponentiation is required to fill the table; no canonical witness exposed by the inspected code.\\ Beullens et al.; Kalu\dj erovi\'c et al. & Short-table extraction, reversal, bit operations for key recovery & Direct precedent for primitives; different output and coverage obligations.\\ Thue/reconstruction & Bounded modular representatives; uniqueness/conditional reconstruction & Classical foundations; whole-window existence is the role of our explicit certificate.\\ This work & Certified window cover, complete folded anchor set, safe rejection, exact completion & Exact $M_r,L_r,K_r,w_r$ on successful execution under the stated hypotheses.\\ \bottomrule \end{tabular} \caption{Algorithmic comparison, not a common-machine timing comparison or an assertion of universal priority.} \end{table} \section{Exact output contract}\label{sec:contract} Fix an odd prime $p$ and an admissible $r\ge2$. Choose a surjective additive label for a multiplicative character of order $r$, \[ \cl:\Fp^{\times}\longrightarrow\Z/r\Z, \qquad \cl(xy)=\cl(x)+\cl(y). \] For a primitive root $g$, one choice is $\cl(g^j)=j\bmod r$. The kernel is the subgroup of $r$th powers; the choice of labels permutes the colours and has no effect on equality of colours. We scan the ordinary integer sequence $1,\ldots,p-1$. Zero is excluded, and an interval does not wrap cyclically through it. Let $M_r$ be the largest length of a constant-colour interval, and let $L_r$ be the longest initial interval with colour zero. Thus $L_r\ge1$, since $\cl(1)=0$. For a maximal run $[l,h]$, its reflected partner is $[p-h,p-l]$, because \begin{equation}\label{eq:reflection} \cl(p-x)=\cl(x)+\sigma_r,\qquad \sigma_r=\cl(-1)=\frac{p-1}{2}\bmod r. \end{equation} The canonical witness is the least start among all runs of length $M_r$; reflection allows each pair to contribute $\min(l,p-h)$. A tie is part of the output contract, not a dispensable side effect of finding the maximum. The scanner also reports \begin{equation}\label{eq:K} K_r=\max\{M_r+1,\, B_r\},\qquad B_r=\begin{cases} 2L_r+2,&r\mid(p-1)/2,\\ L_r+2,&r\nmid(p-1)/2. \end{cases} \end{equation} Here $B_r$ is a boundary threshold and is unrelated to the table radius $B$ used below. Criterion (a) for a requested length $k$ checks $p>k$ and $M_rk$ and $K_r\le k$. These conditions describe distinct outputs. A fast scan of criterion (a) alone is not automatically a certificate for the combined condition. We use colour-first notation $W(r,k)$, with $r$ colours and progression length $k$, as in the published certificates paper~\cite{boundsv2}. That paper proves the boundary-test equivalence and owns the numerical bound comparisons. The present output contract supports those applications; no new lower-bound theorem is announced here. \subsection{Dense reference} The historical CUDA engine evaluates the character across a half interval and uses~\eqref{eq:reflection} to recover the full profile. It fuses admissible character orders using their least common multiple. Consecutive segments retain their endpoint colours, prefix, suffix and internal maximum; an ordered associative merge reconstructs boundary-crossing runs. When the central colours match, the central junction is merged explicitly. The baseline therefore already exploits symmetry, parallelism and shared character evaluation. Comparing against it is more informative than comparing with a naive serial scan. Monroe's inspected \texttt{uc2.cpp} builds a common discrete-log table by successive multiplication of a primitive root, then scans its entries for several orders~\cite{monroecode}. Filling it takes $O(p)$ modular multiplications and $\Theta(p)$ stored labels after root preparation; the pass across a fixed set of orders is linear. Thus a dense method need not perform one exponentiation per position. The historical CUDA baseline here instead trades dense storage for character evaluation over the half interval. Its small root-image table has at most 2520 entries. Our sparse engine prepares $O(B)$ character values, visits scheduled words and completes survivors. These are different work/memory tradeoffs; no timing factor against Monroe is available. Sharing orders and the boundary formula are also present in that earlier software, not introduced here. \subsection{A root of the required order} Let $\mathcal R$ be the requested orders and $m=\operatorname{lcm}\mathcal R$. For the admissible subset of $2,\ldots,9$, $m\le2520$ and $m\mid p-1$. To tabulate the image of $x\mapsto x^{(p-1)/m}$, it suffices to find an element $z$ of order exactly $m$. Trial values $z=a^{(p-1)/m}$ are accepted if \[ z^{m/q}\ne1\quad\hbox{for each prime }q\mid m. \] Only the small integer $m$ must be factored; a primitive root of order $p-1$ is unnecessary. The case $m=2$ uses $z=-1$. Any two choices of $z$ differ by a power $u$ invertible modulo $m$. The resulting relabelling preserves colour equality, the zero prefix, subgroup refinements and~\eqref{eq:reflection}. This optimization does not compute an unrestricted discrete logarithm. \section{Certified rational covers}\label{sec:cover} Multiplicativity gives \begin{equation}\label{eq:quotient} \cl(a/d)=\cl(a)-\cl(d) \quad(a,d\ne0\bmod p). \end{equation} Consequently, if an interval admits representatives $a,a+d,\ldots,a+(Q-1)d$ in a short signed table, testing its colours requires table comparisons instead of one modular exponentiation per position. The following certificate guarantees such a representation. It is an application of the classical convex-body theorem~\cite{minkowski}. The short-table use of~\eqref{eq:quotient} has algorithmic precedents in cryptanalysis~\cite{beullens,kkk}; the certificate supplies the exhaustive window guarantee needed for our distinct output contract. \begin{theorem}[Integer coverage certificate]\label{thm:cover} Let $3\le Q\le p-1$, $H=Q-1$, and let positive integers $B,D$ satisfy \begin{equation}\label{eq:certificate} B4p. \end{equation} For every interval $x,x+1,\ldots,x+H$ in $\{1,\ldots,p-1\}$, there are integers $a,d$ with $1\le d\le D$, $\gcd(a,d)=1$ and \[ a\equiv dx\pmod p,\qquad |a+jd|\le B\quad(0\le j\le H). \] None of these numerators is zero. \end{theorem} \begin{proof} The lattice \[ \Lambda_x=\{(a,d)\in\Z^2:a\equiv dx\pmod p\} \] has basis $(p,0),(x,1)$ and determinant $p$. Apply the determinant-one shear $(a,d)\mapsto(A,d)=(a+Hd/2,d)$. In these coordinates the centrally symmetric convex body \[ \mathcal C=\{(A,d):|d|\le D,\ |A|+H|d|/2\le B\} \] has area \[ \int_{-D}^{D}(2B-H|d|)\,\mathrm d d=4BD-HD^2>4p. \] Minkowski's theorem supplies a nonzero lattice point. If $d=0$, then $a$ is a nonzero multiple of $p$ with $|a|\le B0$. The convex-body inequality bounds both endpoints $a$ and $a+Hd$ by $B$ in absolute value, hence every intermediate numerator. If $s=\gcd(a,d)>1$, divide both coordinates by $s$. Since $s\le d404=4p$. The window $19,\ldots,23$ has numerator row $-25,-21,-17,-13,-9$, since $-25+4j\equiv4(19+j)\pmod{101}$. Multiplicativity reads its colours in the signed table after subtracting the common label of $4$. With $t=3$, spacing $s=q-t+1=3$ and phase $\phi=1$, the folded anchor has $b=17=4\cdot4+1$: its quotient $n=4$ satisfies $n\equiv1\pmod3$. Completion uses $x=-17\cdot4^{-1}=21\pmod{101}$ and recovers $[19,25]$. Its reflected partner is $[76,82]$, so its canonical start is $19$. A literal character scan gives $(M_2,L_2,K_2,w_2)=(7,1,8,19)$. This arithmetic example illustrates the cover, selection and completion; it is below the optimized workers' accepted range and is not a GPU timing or an additional qualification input. \subsection{Choosing parameters without trusting floating point} On the branch $HD^2\le4p$, the least table radius satisfying the strict area inequality is \begin{equation}\label{eq:Bchoice} B=\left\lfloor\frac{4p+HD^2}{4D}\right\rfloor+1. \end{equation} The branch condition also ensures $HD\le2B$. The implementation checks all of~\eqref{eq:certificate} using integer arithmetic after choosing parameters; a rounded square root can propose a candidate, but cannot certify it. Table capacities and signed filter indices impose additional guards. Ignoring integer rounding, let $D_0=2\sqrt{p/H}$ and choose $D=D_0/n$. Then the area boundary gives \begin{equation}\label{eq:volume} B\simeq\sqrt{Hp}\left(\frac n2+\frac1{2n}\right),\qquad BD\simeq p(1+n^{-2}). \end{equation} Changing $n=2$ to $n=4$ reduces this rectangle proxy from $1.25p$ to $1.0625p$, while increasing the table radius. Larger tables put additional pressure on cache and shared memory. This is an architectural tradeoff, not a theorem that larger $n$ is always faster. \begin{figure}[ht] \centering \begin{tikzpicture}[scale=0.9] \fill[blue!8] (-2.5,-1.25)--(2.5,-1.25)--(3.8,0)--(2.5,1.25)--(-2.5,1.25)--(-3.8,0)--cycle; \draw[blue!65!black,thick] (-2.5,-1.25)--(2.5,-1.25)--(3.8,0)--(2.5,1.25)--(-2.5,1.25)--(-3.8,0)--cycle; \draw[->](-4.3,0)--(4.4,0) node[right]{$A$}; \draw[->](0,-1.7)--(0,1.8) node[above]{$d$}; \node[below right] at (3.8,0){$B$}; \node[above left] at (0,1.25){$D$}; \node[below left] at (0,-1.25){$-D$}; \node at (0.2,0.62){$|A|+H|d|/2\le B$}; \end{tikzpicture} \caption{The symmetric clipped cover in sheared coordinates. Its area is $4BD-HD^2$. The diagram illustrates the certificate, not a measured work count.} \label{fig:cover} \end{figure} \section{Anchors, conservative rejection and exact completion}\label{sec:anchors} The cover supplies a bounded arithmetic progression of numerators for any run worth retaining. The implementation enumerates short anchors from this representation, filters them in words of 32 candidate bits, and extends the survivors to their true boundaries in the original sequence. \subsection{A reflection-compatible hitting set} Suppose a run contains a $q$-window and $3\le t\le q$. There are $s=q-t+1$ possible starts for a $t$-anchor within that window. Along a rational row these starts have numerators differing by $d$. A periodic selection with period $s$ therefore hits at least one of them. The signed table is folded using reflection. It is useful to make the selection commute with that fold, rather than relying on a favourable location of the run. \begin{lemma}[Symmetric anchor schedule]\label{lem:schedule} For the increasing representation $a,a+d,\ldots,a+(t-1)d$, define $b=a+(t-1)d$. The same anchor, in descending order, is $(b,b-d,\ldots,b-(t-1)d)$. Negating and reversing it sends its first numerator to $(t-1)d-b$. For $d>2$ and a primitive pair $(b,d)$, write $b=nd+c$, $0d \end{cases}\pmod s. \end{equation} Selection is invariant under $b\mapsto(t-1)d-b$. Every $q$-window in a primitive rational row contains a selected $t$-anchor, whose orientation may be chosen to satisfy $b\ge(t-1)d/2$. For $d=1,2$, retaining all starts has the same hitting property. \end{lemma} \begin{proof} Reflection replaces $n$ by $t-2-n$ and $c$ by $d-c$, which exchanges the two branches of~\eqref{eq:schedule}. The cases $c=0$ and $2c=d$ cannot occur in a primitive pair with $d>2$. Within the $q$-window the $s$ possible starts have one fixed nonzero residue $c$ and $s$ consecutive quotients $n$, so exactly one satisfies the appropriate congruence. If its centre is negative, reflection makes it nonnegative and preserves selection. All reflected numerators retain their absolute table bounds. \end{proof} After the fold, the enumeration domain is \begin{equation}\label{eq:folded} 1\le d\le D,\qquad \left\lceil\frac{(t-1)d}{2}\right\rceil\le b\le B, \qquad\gcd(b,d)=1. \end{equation} The span $(t-1)d\le HD\le2B$ ensures that all anchor numerators lie in the signed table. Zero numerators are excluded. The right endpoint of the unreflected anchor is $bd^{-1}\bmod p$; the completion code uses the reflected increasing anchor beginning at $x=-bd^{-1}\bmod p$, with numerators $-b+jd$. It checks $x\ne0$ and $x+t\le p$, so it never treats a zero-crossing cyclic interval as a run. In \texttt{periodic\_bands.hpp}, a band has $b=nd+c$ with $1\le c32}, with a 33-element array for positions $0,\ldots,32$; this path does not shift a 32-bit word by 32. Neither filter assumes that the anchor starts at the head of a maximal run. \subsection{Thresholds and canonical ties} A pilot establishes a real monochromatic run and hence a lower bound for the maximum. Each denominator epoch takes a snapshot of this bound and caps its geometric threshold by $Q$. For a coupled pair of profiles, the shared search uses a threshold no larger than either current maximum. The threshold stays immutable throughout the generation and completion kernels of that epoch; it is updated only after ordered completion. To retain the least witness, the search must preserve anchors in runs whose length equals the current maximum. It may reject runs certified to be strictly shorter. At completion, each surviving anchor is mapped to a position of the original sequence using~\eqref{eq:quotient}, extended in both directions, and reduced by length and then by least canonical start. The prefix is checked directly using modular powers. If the pilot cannot establish the required threshold, or a queue overflows, the engine produces a failure rather than an approximate maximum. The geometric certificate, the hitting-set argument and conservative rejection explain why a relevant run is retained at the algorithmic level. Correctness of its CUDA realization additionally depends on the finite partition, synchronization, arithmetic and output checks described below. A test passing does not replace a proof of the cover, and a proof of the cover does not verify an arbitrary CUDA implementation. \subsection{Composition into an exact-success contract}\label{sec:global} Consider a true global maximum. Its covering denominator is assigned to one epoch. The verified maximum available at that epoch gives a threshold no larger than the true maximum, so a subwindow at that threshold contains a scheduled anchor. Known contradictions cannot eliminate that anchor. Exact completion recovers the run, and the tie rule keeps its least start. Later increases in the threshold do not require revisiting earlier epochs. The theorem states precisely the implementation hypotheses for this argument. \begin{theorem}[Exactness on successful termination]\label{thm:global} For each profile $r$, fix $(B,D,Q)$ satisfying Theorem~\ref{thm:cover}, with $3\le Q\le p-1$. Suppose disjoint denominator epochs exhaust $\{1,\ldots,D\}$. In epoch $e$, use a fixed threshold \[ 3\le q_e\le\min(Q,m_{r,e})\le\min(Q,M_r), \] where $m_{r,e}$ is the length of a run verified before that epoch, and use $3\le t_e\le q_e$. Suppose enumeration preserves the complete scheduled primitive anchor set, modulo reflection; rejection is conservative for each profile; completion and colour arithmetic are exact; and each surviving obligation is completed to its true boundaries without passing zero. Assume no lost task, capacity overflow, failed arithmetic guard or unfinished epoch is accepted as success. Then reduction by length and least canonical start returns $M_r,w_r$. An exact prefix check returns $L_r$, and~\eqref{eq:K} returns $K_r$. For coupled profiles these assumptions apply to each profile separately; candidate routing must preserve their union of obligations. \end{theorem} \begin{proof} Verified seed and completed runs have length at most $M_r$. Fix any maximum run and a subwindow $J$ of length $\min(M_r,Q)$. Extend $J$ to a $Q$-window within $1,\ldots,p-1$ if necessary. The cover gives a primitive representation with some $d\le D$; restriction preserves its primitivity and table bounds. That denominator belongs to an epoch $e$. Because $q_e\le |J|$, a $q_e$-subwindow contains a scheduled $t_e$-anchor. Reflection may place it in the reflected run of the same length. An actual monochromatic window has no observed contradiction, so a conservative profile filter retains its obligation. Exact completion finds the maximum run or its partner. This holds for every maximum run, so the reduction also finds the least start among ties. Completion produces only real runs, excluding an overestimate. Direct prefix verification and the integer formula give the remaining outputs. \end{proof} \noindent\textbf{Algorithm 1 (logical specification; each failure is visible).} \begin{enumerate} \setlength{\itemsep}{1pt} \item Validate input, arithmetic and capacities; certify fixed group covers; prepare signed character planes and inverses. \item Establish real seed runs and their canonicalized witnesses. Refuse if the required threshold cannot be established. \item For each denominator epoch, snapshot per-profile maxima, choose $q_e,t_e$, and build whole-row folded plans. \item Generate primitive anchor words; test coarse anchors and maintain separate profile obligations. Reject only under the appropriate profile's known contradictions. Queue a word if any obligation remains. \item Complete queued obligations and reduce maxima/ties; check queue counts, errors, dependencies and epoch completion before advancing. \item Verify witnesses and prefixes, form $K_r$, and report success only after all epochs for all requested groups have completed. \end{enumerate} The theorem specifies the algorithm's mathematical contract. It is not a formal verification of CUDA instructions, binary identity or the absence of every software defect. Evidence for those implementation bridges is recorded separately in Section~\ref{sec:verification} and Appendix~\ref{app:bridge}. \section{Sharing character profiles}\label{sec:sharing} Subgroup refinements provide opportunities to reuse table bits and plans. For orders $2\mid4$, an ordinary binary encoding of the order-four label has its low bit equal to the order-two label. Only one residual plane is needed. For orders $3\mid6$, encode an order-six label $c$ as \[ (c\bmod2)+2(c\bmod3). \] Its two high planes are the order-three representation and its low plane is the residual parity. Signed-table access must also apply the appropriate reflection shifts and strides. Reusing an equal-looking array without these transformations would not preserve the character contract. The encoding is a bijective storage representation, not an additive character label in $\Z/6\Z$. Colour equalities and the documented reflection transformations, rather than integer addition of these codes, are used. For a coarse/fine pair, a fine-constant anchor is coarse-constant, but the reverse need not hold: $(0,3,0)$ is constant modulo three and not modulo six. Thus accepting only the fine equality would lose coarse maxima. \texttt{profile\_masks.hpp::split} first tests the coarse anchor and keeps two masks. Coarse-kept anchors are completed as entire coarse runs and their interior fine subruns are scanned by \texttt{coupled\_device.hpp::complete}. Fine-only bits refine the residual planes and are completed directly. A word is queued if either mask is nonzero. Fine work already covered by a coarse completion is not queued twice. The logical obligation is the union, not the intersection, of the profiles' relevant candidates. A shared low threshold alone would not suffice without this routing rule. Table preparation, plan preparation and candidate completion have different costs. It can be faster to share the table while scanning profiles separately, because the coarser character then has a stronger threshold. The retained 32-bit path separates order two from order four, but leaves orders three and six coupled. Each group retains its own $B,D,Q$ and epochs. This policy follows measurements, not an assertion that every subgroup pair should be coupled. The later wider worker also shares two planes of the order-eight encoding with order four, retaining one residual plane when $p\equiv1\pmod8$. It improved the measured natural batch throughput by a further $3.70$--$4.16\%$ relative to streams alone in the two late wide validation windows. The same specialization was not retained in the 32-bit worker, where exploratory gains were too small. Generic couplings and the order-three/order-nine pairing were tried and not retained. \section{Arithmetic and CUDA execution}\label{sec:implementation} \subsection{A separate wider arithmetic path} The 32-bit and wider workers have different type requirements. For $1000\le p<2^{33}$ and $r\ge2$, every colour class has $(p-1)/r$ elements, so \[ M_r\le(p-1)/r<2^{32}. \] Reflection gives a canonical witness no larger than $(p-1)/2<2^{32}$. Length and witness can therefore still be packed into a 64-bit reduction key with 32 bits each. A key of the form \[ (\text{length}\ll32)\;|\;(2^{32}-1-\text{witness}) \] implements the desired lexicographic order by maximization. However, $p$, positions and intermediate endpoints must be 64-bit, and $K_r$ must be formed in 64-bit arithmetic. In particular, a witness above $2^{31}-1$ is valid and must not become a negative signed integer. The wider path uses Montgomery multiplication~\cite{montgomery} with $R=2^{64}$ and $n'=-p^{-1}\bmod R$. For reduced operands $a,b