The Autocorrelation Formula

One quantity in the spectral chain resisted a closed form longer than the others.

Take the repeating block of $1/7$ in base $10$:

142857

Shift it by one place and compare the shifted copy with the original:

1 4 2 8 5 7
4 2 8 5 7 1

No matches. Shift by two, three, four, or five places, and the answer is still zero. For $p = 7$, the repeating block never agrees with any nontrivial cyclic shift of itself.

That behavior is not typical. At $p = 29$, some shifts produce matches. At $p = 97$, the profile is much richer.

The number of matches at shift $\ell$ is the autocorrelation $R(\ell)$. It governs the spectral side of the program because the eigenvalues of the cross-alignment matrix are the discrete Fourier transform of this profile.

The problem was simple to state and awkward to compute. Computing $R(\ell)$ directly meant writing out the full repetend and checking every shift by brute force. I had been doing exactly that, for every prime, since the beginning. The quantity was always computable. It was never expressed in terms of anything deeper.

The missing phase

The Spectral Power of the Digit Function gave a closed formula for the magnitude profile of the digit partition. That recovered the bin-sum and characterized digit-partitioning primes, but it did not recover $R(\ell)$.

The reason is the same as in ordinary wave interference. Magnitude tells you how large a frequency component is. It does not tell you how two components line up when added. Two frequencies can have the same magnitude and still reinforce or cancel depending on how they are aligned. Autocorrelation depends on exactly that.

A one-variable magnitude function is not enough. A two-variable object is needed.

The cross-spectral table

For each pair of frequencies $(k, k')$, define a table entry $G(k,k')$ built from the Fourier coefficients of the digit bins. The diagonal of this table recovers the spectral power. The off-diagonal entries carry the phase relations the spectral power discards.

One fact about this table drives the whole argument.

$$\sum_{k,k'} G(k,k') = 0.$$

At first sight this looks incidental. It is not. It is the cancellation identity that turns a long expansion into a usable formula.

The formula

Count the residues whose leading digit agrees with the leading digit of their shifted partner. That is $R(\ell)$ by definition.

The agreement test can be written in terms of the digit bins. Each bin indicator expands in additive characters on $\mathbf{Z}/p\mathbf{Z}$. After that substitution, the residue sum collapses into a sum over pairs of frequencies weighted by the cross-spectral table $G$.

Two classes of terms appear. Those where the combined frequency is zero, and those where it is not. The standard character sum over nonzero residues takes two values in those two cases, so the expression splits into two pieces. The cancellation identity

$$\sum_{k,k'} G(k,k') = 0$$

forces those two pieces to collapse into one.

$$R(\ell) = \frac{1}{p}\sum_{k=0}^{p-1} G!\left(k,,-k,b^{-\ell}!!!\pmod p\right).$$

$R(\ell)$ is no longer a digit comparison run in a loop. It is a walk through the table $G$ along a path determined by $\ell$, summing whatever lies on that path.

The path at $p = 7$

At $p = 7$, every occupied digit bin has size one. The table $G$ takes only two values: $6$ on the diagonal and $-1$ everywhere else. A $7 \times 7$ grid, bright along the diagonal, dark everywhere else.

The gold circles mark the path for shift 1. The formula sends frequency $k$ to $k \cdot b^{-1} \bmod p$. Since $10 \equiv 3 \pmod 7$, shift 1 maps $k$ to $3k \bmod 7$, and the path visits cells $(0,0)$, $(1,3)$, $(2,6)$, $(3,2)$, $(4,5)$, $(5,1)$, $(6,4)$. Seven cells. One lands on the diagonal and picks up $6$. Six land off the diagonal and each picks up $-1$.

$$6 + 6(-1) = 0. \qquad R(1) = 0/7 = 0.$$

Shifts 2 through 5 trace different paths through the same table. Each one also hits the diagonal exactly once. Every path sums to zero. The formula reproduces the full row of zeros from the opening without writing down a single digit of 142857.

The digit bins determine the Fourier coefficients. The Fourier coefficients determine the table $G$. The table $G$ determines $R(\ell)$. The discrete Fourier transform of $R(\ell)$ gives the eigenvalues. Everything is now explicit.

The primitive-root boundary

The clean formula belongs to the primitive-root case, where the base runs through the full multiplicative orbit modulo $p$. The path through $G$ has the right shape and the cancellation identity finishes the job.

At multi-coset primes, the same expansion can be written down, but the collapse is no longer so direct. The table is there, the paths are there, but the orbit structure is smaller and the neat one-step reduction does not follow from the same argument.

Before this paper, autocorrelation was the one place in the spectral chain where brute-force digit comparison was still doing essential work. After this paper, that is gone in the primitive-root case. What remains outside that regime is now precisely identified.

A note from 2026

April 2026

The same cancellation identity appeared again in The Collision Spectrum: a one-variable invariant on the diagonal of a richer two-variable object, with the off-diagonal data carrying what the diagonal alone cannot see. Variance-type quantities on the diagonal. Correlations off it.

Once the autocorrelation formula was written down, the path from digit bins to eigenvalues was explicit from end to end. The collision papers kept that standard. The quantities under study are always built from finite arithmetic data, checkable directly in small cases. That discipline did not come from nowhere.

.:.

Try it yourself

$ ./nfield autocorrelation 7
  R(0) = 6
  R(1) = R(2) = R(3) = R(4) = R(5) = 0

$ ./nfield autocorrelation 29
  R(0) = 28
  nonzero values appear at several shifts

$ ./nfield autocorrelation 97
  R(0) = 96
  the self-match profile is visibly structured

At $p = 7$, every nontrivial shift vanishes. At $p = 29$, the profile is sparse but no longer trivial. At $p = 97$, the pattern across shifts is dense and structured.

For any of these primes, the formula computes each $R(\ell)$ by walking a path through the table $G$ and summing. No repetend written out. No digits compared by hand. Arithmetic tells you where to walk.

Code: github.com/alexspetty/nfield
Paper: The Autocorrelation Formula

Alexander S. Petty
January 2022 (updated April 2026)
.:.