Orientation-Sensitive Return Traces in a Four-State Graph Dynamics with Invertible Local Updates

We study a finite-state Markov dynamics on an oriented, weighted, finite simple graph in which each vertex carries one of four local states. After a binary change of coordinates, an active edge update exchanges two occupation variables together with their internal bits and flips one of the transported bits; reversing the edge orientation replaces the local update by its inverse. The occupation number is conserved. Although edge reversal does not change reachability, it can change return traces and hence the spectrum of the transition operator. Our first results locate the earliest possible orientation dependence in terms of the girth. All return traces of order below the girth are orientation-independent. At odd girth the trace at the girth is still independent, whereas at even girth the first possible difference is an explicit weighted sum over shortest cycles with Eulerian-number coefficients. We also derive a closed formula for the next trace order at every even girth, separating repeated-cycle-edge, boundary-edge, and disjoint-edge contributions. In a six-vertex example we determine analytically the first difference of the total trace and obtain an exact coefficient of 7680. A Walsh–Fourier transform in the internal bits gives a complete block decomposition of each fixed-occupation sector. This yields blockwise refinements of the trace formulas and, on even cycles, an arithmetic classification of every fine Fourier block: each block is either orientation-blind for all powers or has an explicitly determined first orientation-sensitive trace order. Exact finite computations are supplied as reproducibility checks, while the stated main results are proved analytically. Preprint. This manuscript has not undergone peer review.