The Autocorrelation Formula
Abstract
Let b\ge2 and let p\nmid b be prime. The digit function \delta(r)=\left\lfloor\frac{br}{p}\right\rfloor partitions the nonzero residues modulo p into digit bins. Let K(r,s) be the same-bin kernel. Let G(k,k') be its additive Fourier transform in both variables.
For every nonzero multiplier a modulo p, the multiplicative collision count satisfies the exact slice formula C(a)=\frac1p\sum_{k=0}^{p-1}G(k,-a^{-1}k). When b is a primitive root modulo p, the remainder orbit of 1/p contains every nonzero residue. Its cyclic digit autocorrelation is therefore R(\ell)=\frac1p\sum_{k=0}^{p-1} G(k,-b^{-\ell}k). The formula retains the phase information lost by spectral power alone.
The complement law \delta(p-r)=b-1-\delta(r) forces G to be real and symmetric. When the base has several multiplicative orbits, the same line sum gives their aggregate autocorrelation. An individual orbit has an exact formula involving the corresponding subgroup exponential sum. Outside the primitive-root case, reduction of an individual orbit to the same one-line slice is no longer automatic.
Where Addition Meets Multiplication
The decimal repetend 142857 of 1/7 agrees with itself in all six positions at lag zero and in none under any nontrivial cyclic shift. What forces this complete vanishing without comparing the shifted words?
The repetend of 1/p is generated by one arithmetic motion. A remainder r emits the digit \lfloor br/p\rfloor and moves to br\bmod p. The emitted digits form consecutive bins in the additive ordering of the residues. The remainders move through the multiplicative group. Autocorrelation lies where these two structures meet.
The squared magnitude of a bin Fourier coefficient records power at one additive frequency. It does not retain the starting phase of the bin. Autocorrelation needs that phase because multiplication moves one interval of residues against another. The natural object is therefore not a one-variable power function. It is the two-dimensional Fourier transform of the relation “these two residues emit the same digit.”
Denote that transform by G(k,k'). Its antidiagonal is the spectral power developed in The Spectral Power of the Digit Function [4]. Its other entries retain the phase data. A multiplier a selects the line k'=-a^{-1}k. The sum of G along this line is exactly p times the number of same-digit matches under multiplication by a. This is a finite Fourier slice identity.
The primitive-root condition has one precise role. It makes the remainder orbit of 1/p equal to the full multiplicative group. The slice identity itself needs no primitive-root hypothesis. When there are several orbits, it computes their aggregate, while a subgroup sum isolates any chosen orbit.
The Fourier transform is the standard unnormalized transform on the finite cyclic group [3].
The digit partition
Fix an integer b\ge2 and a prime p with p\nmid b. Write \mathbb{F}_p=\mathbb Z/p\mathbb Z, \qquad \mathbb{F}_p^{\times}=\mathbb{F}_p\setminus\{0\}. Represent the nonzero residues by 1,2,\ldots,p-1.
Definition 1. For r\in\{1,\ldots,p-1\}, define \delta(r)=\left\lfloor\frac{br}{p}\right\rfloor. For 0\le d<b, the dth digit bin is B_d=\{r\in\mathbb{F}_p^{\times}\mid \delta(r)=d\}. Let f_d=\mathbf 1_{B_d} on \mathbb{F}_p^{\times} and extend it to \mathbb{F}_p by setting f_d(0)=0.
The floor function is nondecreasing, so the nonempty bins are consecutive intervals and occur in digit order. If n_d=|B_d| and a_d=1+\sum_{e<d}n_e, then a nonempty bin has the form B_d=\{a_d,a_d+1,\ldots,a_d+n_d-1\}. The ordered vector (n_0,\ldots,n_{b-1}) therefore determines the bins and their starting positions.
Definition 2. The same-bin kernel is K(r,s)=\sum_{d=0}^{b-1}f_d(r)f_d(s), \qquad r,s\in\mathbb{F}_p.
If r and s are nonzero, then K(r,s) is one when they emit the same digit and zero otherwise. It is also zero when either argument is zero. Thus K records the equality relation of the digit partition without retaining the numerical digit labels.
Lemma 3 (Complement reflection). For every r\in\mathbb{F}_p^{\times}, \delta(p-r)=b-1-\delta(r). Consequently, -B_d=B_{b-1-d} \qquad\text{and}\qquad K(-r,-s)=K(r,s).
Proof. The number br/p is not an integer. Hence \delta(p-r) =\left\lfloor b-\frac{br}{p}\right\rfloor =b-1-\left\lfloor\frac{br}{p}\right\rfloor. The bin identity follows immediately. Replacing both arguments of K by their negatives only replaces digit d by digit b-1-d, so the equality relation is unchanged. ◻
The cross-spectrum
Put \mathrm{e}_p(x)=e^{2\pi i x/p}. For a function f on \mathbb{F}_p, use the Fourier conventions \widehat f(k)=\sum_{r\in\mathbb{F}_p}f(r)\mathrm{e}_p(-kr), \qquad f(r)=\frac1p\sum_{k\in\mathbb{F}_p}\widehat f(k)\mathrm{e}_p(kr).
Definition 4. The cross-spectrum of the digit partition is G(k,k')=\sum_{d=0}^{b-1} \widehat f_d(k)\widehat f_d(k'), \qquad k,k'\in\mathbb{F}_p.
No conjugate is missing from this definition. Conjugation appears on the antidiagonal because \widehat f_d(-k)=\overline{\widehat f_d(k)}.
Theorem 5 (Two-dimensional transform). The cross-spectrum is the two-dimensional Fourier transform of the same-bin kernel. More precisely, G(k,k') =\sum_{r,s\in\mathbb{F}_p}K(r,s)\mathrm{e}_p(-kr-k's). Fourier inversion recovers the kernel through K(r,s)=\frac1{p^2}\sum_{k,k'\in\mathbb{F}_p} G(k,k')\mathrm{e}_p(kr+k's).
Proof. Expanding the definition gives \begin{aligned} G(k,k') &=\sum_d \left(\sum_r f_d(r)\mathrm{e}_p(-kr)\right) \left(\sum_s f_d(s)\mathrm{e}_p(-k's)\right)\\ &=\sum_{r,s} \left(\sum_d f_d(r)f_d(s)\right) \mathrm{e}_p(-kr-k's)\\ &=\sum_{r,s}K(r,s)\mathrm{e}_p(-kr-k's). \end{aligned} The second identity is two-dimensional Fourier inversion. ◻
Thus G is the same-bin relation written in frequency coordinates.
Corollary 6 (Spectral power). On the antidiagonal, G(k,-k)=\sum_{d=0}^{b-1}|\widehat f_d(k)|^2. Thus the one-variable spectral power is the antidiagonal of G.
Proposition 7 (Reality and symmetry). For all k,k'\in\mathbb{F}_p, G(k,k')=G(k',k)=G(-k,-k') \qquad\text{and}\qquad \overline{G(k,k')}=G(k,k'). In particular, the matrix (G(k,k'))_{k,k'\in\mathbb{F}_p} is real, symmetric, and Hermitian.
Proof. Symmetry in k and k' follows from the definition. Lemma 3 gives f_{b-1-d}(r)=f_d(-r), and therefore \widehat f_{b-1-d}(k) =\widehat f_d(-k) =\overline{\widehat f_d(k)}. Reindexing the digit sum by d\mapsto b-1-d yields \overline{G(k,k')} =\sum_d\widehat f_{b-1-d}(k) \widehat f_{b-1-d}(k') =G(k,k'). The identity under simultaneous negation follows in the same way. ◻
Corollary 8 (Vanishing total). \sum_{k,k'\in\mathbb{F}_p}G(k,k')=0.
Proof. By Theorem 5, the left side is p^2K(0,0), which is zero. ◻
The interval structure also gives a direct finite expression for every entry of G. Define D_n(k)=\sum_{u=0}^{n-1}\mathrm{e}_p(-ku), \qquad D_0(k)=0. Then \widehat f_d(k)=\mathrm{e}_p(-ka_d)D_{n_d}(k), and hence G(k,k')=\sum_{d=0}^{b-1} \mathrm{e}_p\bigl(-(k+k')a_d\bigr) D_{n_d}(k)D_{n_d}(k'). This shows directly why the ordered bin lengths determine G. The lengths determine the finite geometric factors, while their cumulative sums determine the phases.
The multiplicative slice
Definition 9. For a\in\mathbb{F}_p^{\times}, define the multiplicative collision count C(a)=\sum_{r\in\mathbb{F}_p}K(r,ar).
The term at r=0 is zero. Thus C(a) counts the nonzero residues whose digit is unchanged by multiplication by a.
Theorem 10 (Multiplicative slice formula). For every a\in\mathbb{F}_p^{\times}, \boxed{ C(a)=\frac1p\sum_{k\in\mathbb{F}_p}G(k,-a^{-1}k). }
Proof. Insert the inversion formula from Theorem 5. Then \begin{aligned} C(a) &=\sum_{r\in\mathbb{F}_p}K(r,ar)\\ &=\frac1{p^2}\sum_{k,k'\in\mathbb{F}_p}G(k,k') \sum_{r\in\mathbb{F}_p}\mathrm{e}_p\bigl((k+ak')r\bigr). \end{aligned} Character orthogonality makes the inner sum equal to p when k+ak'=0 and zero otherwise. The surviving line is k'=-a^{-1}k, which proves the formula. ◻
The selected frequency line is perpendicular to the graph r\mapsto ar in residue space.
Corollary 11. For every a\in\mathbb{F}_p^{\times}, C(1)=p-1 \qquad\text{and}\qquad C(a^{-1})=C(a).
Proof. The first identity follows from K(r,r)=1 for every nonzero r. For the second, change variables r=as and use the symmetry of K. Then C(a^{-1}) =\sum_r K(r,a^{-1}r) =\sum_s K(as,s) =\sum_s K(s,as) =C(a). ◻
Although the right side of the slice formula is written in Fourier coordinates, it is therefore a nonnegative integer and is unchanged when the multiplier is inverted.
Repetend autocorrelation
Let L=\operatorname{ord}_p(b). The remainders in the base-b expansion of 1/p are 1,b,b^2,\ldots,b^{L-1}\pmod p. Write d_j=\delta(b^j\bmod p), \qquad j\in\mathbb Z/L\mathbb Z.
Definition 12. The cyclic digit autocorrelation at lag \ell is R(\ell) =\sum_{j=0}^{L-1} \mathbf 1[d_j=d_{j+\ell}].
Theorem 13 (Autocorrelation formula). Suppose that b is a primitive root modulo p. Then L=p-1, and for every \ell\in\mathbb Z/(p-1)\mathbb Z, \boxed{ R(\ell)=\frac1p\sum_{k\in\mathbb{F}_p} G(k,-b^{-\ell}k). }
Proof. When b is primitive, the remainders b^j run through \mathbb{F}_p^{\times} exactly once. Multiplication by b^\ell moves the remainder at position j to the remainder at position j+\ell. Therefore R(\ell) =\sum_{r\in\mathbb{F}_p}K(r,b^\ell r) =C(b^\ell). The result follows from Theorem 10 with a=b^\ell. ◻
The formula explains why phase is necessary. Spectral power sees only G(k,-k), which corresponds to the identity multiplier. A nonzero lag samples a different line, and that line generally passes through off-antidiagonal values of G.
The autocorrelation also has a harmonic readout. Define the normalized circulant matrix A_{u,v}=\frac1L R(v-u), \qquad u,v\in\mathbb Z/L\mathbb Z.
Proposition 14 (Harmonic energies). The Fourier characters of \mathbb Z/L\mathbb Z diagonalize A. Its eigenvalues are \lambda_j=\frac1L\sum_{\ell=0}^{L-1} R(\ell)e^{2\pi i j\ell/L}, \qquad 0\le j<L. They are real and nonnegative. If b is primitive, then \lambda_j=\frac1{pL} \sum_{\ell=0}^{L-1}\sum_{k\in\mathbb{F}_p} G(k,-b^{-\ell}k)e^{2\pi i j\ell/L}.
Proof. The eigenvalue formula is the standard diagonalization of a circulant matrix [1]. To see nonnegativity directly, put x_d(t)=\mathbf 1[d_t=d] \qquad\text{and}\qquad X_d(j)=\sum_{t=0}^{L-1}x_d(t)e^{-2\pi i jt/L}. Then \sum_{\ell=0}^{L-1}R(\ell)e^{2\pi i j\ell/L} =\sum_{d=0}^{b-1}|X_d(j)|^2. The final formula follows by inserting Theorem 13. ◻
When the base has several orbits
The slice theorem remains valid when L<p-1, but one repetend no longer visits the full nonzero field. Put H=\langle b\rangle\subset\mathbb{F}_p^{\times}. For a coset cH, define R_c(\ell)=\sum_{r\in cH}K(r,b^\ell r). This is the autocorrelation of the digit word obtained by following the orbit cH.
Proposition 15 (Orbit aggregation). For every lag \ell, C(b^\ell)=\sum_{cH\in\mathbb{F}_p^{\times}/H}R_c(\ell). Thus the single-line slice formula computes the sum of the autocorrelations of all multiplicative orbits.
Proof. The cosets of H partition \mathbb{F}_p^{\times}. Splitting the defining sum for C(b^\ell) over those cosets gives the identity. ◻
There is also an exact formula for one chosen orbit. Define S_{cH}(m)=\sum_{r\in cH}\mathrm{e}_p(mr).
Theorem 16 (Individual orbit formula). For every coset cH and every lag \ell, R_c(\ell)=\frac1{p^2} \sum_{k,k'\in\mathbb{F}_p}G(k,k') S_{cH}(k+b^\ell k').
Proof. Insert the two-dimensional inversion formula for K(r,b^\ell r) and sum over r\in cH. The remaining inner sum is exactly S_{cH}(k+b^\ell k'). ◻
When H=\mathbb{F}_p^{\times}, its exponential sum is S_H(m)= \begin{cases} p-1 & m=0,\\ -1 & m\ne0. \end{cases} The vanishing total in Corollary 8 then reduces the double sum to the one-line formula. For a proper subgroup, the values of S_{cH} are subgroup exponential sums rather than a two-valued delta [2]. The individual-orbit formula is still exact, but the clean collapse to one line is no longer automatic.
These finite digit-bin, cross-spectrum, and autocorrelation constructions can be explored in the nfield repository [5].
A Repetend With No Nontrivial Self-Match
Let p=7 and b=10. The base has order six modulo seven, so it is a primitive root. The nonempty bins are \begin{aligned} B_1&=\{1\}, & B_2&=\{2\}, & B_4&=\{3\},\\ B_5&=\{4\}, & B_7&=\{5\}, & B_8&=\{6\}. \end{aligned} Every occupied bin is a singleton. Therefore G(k,k') =\sum_{r=1}^{6}e^{-2\pi i(k+k')r/7} = \begin{cases} 6 & k+k'=0,\\ -1 & k+k'\ne0. \end{cases}
At lag zero, the selected line is k'=-k. All seven terms equal six, so R(0)=\frac{42}{7}=6. For a nonzero lag, put a=10^\ell\bmod7. Then a\ne1. Along the selected line k'=-a^{-1}k, the condition k+k'=0 becomes k(1-a^{-1})=0. Only k=0 satisfies it. The line sum is therefore 6+6(-1)=0, and R(\ell)=0 \qquad (1\le\ell\le5). The same-bin kernel and cross-spectrum form one exact chain. Complement reflection makes G real and Hermitian. Its antidiagonal is spectral power, while every nonzero multiplier selects an exact collision line.
For a primitive-root base, those lines give cyclic autocorrelation and nonnegative harmonic energies. With several multiplicative orbits, the line sum gives their aggregate and subgroup exponential sums isolate each orbit.
The repetend is 142857. Its six cyclic shifts agree with it in all six positions at lag zero and in no position at any nonzero lag. The frequency lines recover that complete self-match profile without comparing the shifted words.
References
[1]P. J. Davis, Circulant Matrices, second edition, AMS Chelsea Publishing, 1994.
[2]H. Iwaniec and E. Kowalski, Analytic Number Theory, American Mathematical Society, 2004.
[3]A. Terras, Fourier Analysis on Finite Groups and Applications, Cambridge University Press, 1999.
[4]A. S. Petty, The Spectral Power of the Digit Function, research paper, October 2021, revised August 2026. doi:10.5281/zenodo.21845198.
[5]A. S. Petty, nfield, software repository. https://github.com/alexspetty/nfield.