Still preparing the reader…Long documents can take a little longer to load and typeset.
Still preparing the reader…Long documents can take a little longer to load and typeset.
Still preparing the reader…Long documents can take a little longer to load and typeset.
Cyclic digit autocorrelation counts the positions at which a repetend agrees with a shifted copy. An exact Fourier slice computes this count from the digit partition and separates the contribution of one remainder orbit from the aggregate over all orbits. 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). In this full-period case, R(\ell) is the cyclic Hamming match count of the reciprocal digit sequence. 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.
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.
Coordinatewise equality under a cyclic shift is Hamming correlation. Lempel and Greenberger place that statistic in the general theory of finite sequence families [1]. Kak and Chatterjee study Hamming distance between prime-reciprocal digit sequences and their cyclic shifts, together with numerical digit-product autocorrelation [2]. The statistic used below counts equal digits. It is unchanged by relabeling the digit alphabet, whereas a numerical digit-product correlation need not be. Repetend multiplication and its orbit structure are classical [3]. Those results establish the observable and its reciprocal-sequence setting. The result here is the exact two-dimensional transform of the complete digit-bin equality relation, its multiplier-line slice for every nonzero residue, and the separation between the all-orbit aggregate and an individual coset when the base is not primitive.
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 sum of the squared Fourier magnitudes of the digit bins, the function studied in The Spectral Power of the Digit Function [7]. 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 obtained from character orthogonality [6].
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 [6].
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. ◻
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.
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.
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 [4]. 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. ◻
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 [5]. The individual-orbit formula is still exact, but the clean collapse to one line is no longer automatic.
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 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 classical Hamming count sees those six comparisons. The two-dimensional transform sees every multiplier at once. One line recovers each count, all cosets remain present before any primitive-root assumption is made, and a subgroup exponential sum can separate them again. For 142857, every nonidentity line sums to zero.
[1]A. Lempel and H. Greenberger, Families of sequences with optimal Hamming-correlation properties, IEEE Trans. Inform. Theory 20 (1974), no. 1, 90–94. https://doi.org/10.1109/TIT.1974.1055169.
[2]S. C. Kak and A. Chatterjee, On decimal sequences, IEEE Trans. Inform. Theory 27 (1981), no. 5, 647–652. https://doi.org/10.1109/TIT.1981.1056394.
[3]N. J. Armstrong and R. J. Armstrong, Some properties of repetends, Math. Gaz. 87 (2003), no. 510, 437–443. https://doi.org/10.1017/S0025557200173619.
[4]P. J. Davis, Circulant Matrices, second edition, Chelsea, 1994.
[5]H. Iwaniec and E. Kowalski, Analytic Number Theory, American Mathematical Society, 2004.
[6]A. Terras, Fourier Analysis on Finite Groups and Applications, Cambridge University Press, 1999.
[7]A. S. Petty, The Spectral Power of the Digit Function, research note, October 2021. https://doi.org/10.5281/zenodo.21845198.
Discussion
Sign in to join the discussion.