Arithmetic Growth Controls Recurrence Complexity in Uniform GNNs

We study how the arithmetic gate basis inside a shared recurrent GNN cell affects the recurrence cost of graph-level color refinement. One-round graph colors form $2^{\Theta (n)}$ classes, while every fixed round $k\ge 2$ refines $2^{\Theta (n^2)}$ classes. For a fixed rational ReLU-MLP (continuous piecewise-affine, CPWA), output-coordinate numerator and denominator bit lengths grow by only $O(\log n)$ per recurrence. This gives an $\Omega (n^2/\log n)$ lower bound for fixed $k\ge 2$, even with a recurrent global sum. More generally, consider a fixed-dimensional cell and readout with a polynomial-growth envelope, polynomial-magnitude initialization, and inverse-polynomial separation between distinct class outputs. For fixed $k\ge 2$, such a model needs $\Omega (\log n)$ recurrences. We meet this bound with one fixed rational arithmetic cell over affine maps, scalar ReLU, and exact binary multiplication gates. Given $n$ and $k$, it computes graph-level ${\mathrm{CR}}_k$ in $2(k+1)\lceil {\log }_2(2n)\rceil +4k+4$ recurrences using only neighbor sums. Its integer outputs are unit-separated, and its states have $n^{O(k+1)}$ bits. For output radius $M(n)$ and separation $\delta (n)$, every fixed-dimensional representation still satisfies $\log (M(n)+1)+\log (1/\delta (n))=\Omega (n^2)$. Thus adding exact multiplication reduces fixed-$k$ recurrence complexity to $\Theta (\log n)$ without removing this output cost. The same cell computes stable color refinement in $O(n\log n)$ recurrences, while locality gives an $\Omega (n)$ lower bound. Exact circuit certificates and independent color-refinement implementations check the construction. The results do not address trainability or fixed-word execution.