The Autocorrelation Formula

Take the repeating block of $1/7$ in base ten.

142857

Move the first digit to the end and put the two copies alongside each other.

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

No position agrees. Move two digits to the end, then three, four, five. Still nothing. Each digit occurs only once in the block, so no nontrivial rotation can bring a digit back onto itself.

Now try $1/17$.

0 5 8 8 2 3 5 2 9 4 1 1 7 6 4 7
5 8 8 2 3 5 2 9 4 1 1 7 6 4 7 0

The third positions agree. So do the eleventh. The same one-place shift now gives two matches.

The number of matches at shift $\ell$ is the autocorrelation $R(\ell)$. Here correlation means equal digits in equal positions. We are counting agreements, not multiplying the numerical digit values.

For seven, the complete list is $6,0,0,0,0,0$. The first entry counts the unshifted word against itself. For seventeen, the list has sixteen entries and several are nonzero.

Writing out the words gives the answers. I want to see those answers in the remainder arithmetic that produces the words.

Following the remainders

Long division carries a remainder from one position to the next. In base ten, multiply it by ten, emit the whole-number digit, and keep the new remainder.

At denominator seventeen, a remainder of $2$ gives

$$20=1\cdot17+3.$$

It emits $1$ and leaves remainder $3$. That remainder also emits $1$, because $30=1\cdot17+13$. These are the adjacent ones we just saw.

The adjacent eights have the same explanation. Remainder $15$ emits $8$ and leaves remainder $14$. Remainder $14$ also emits $8$.

A one-place shift compares each remainder with ten times that remainder, reduced modulo seventeen. A two-place shift compares it with a hundred times that remainder. Moving along a word has become multiplication in a finite table.

Make the table explicit. Label both its edges by the remainders. Fill a cell whenever its two remainders emit the same digit. Leave it empty otherwise.

The circles follow multiplication by ten. Two land on filled cells, at $(2,3)$ and $(15,14)$. The count is two again.

Call this equality table $K$. Its entries are just ones and zeros. Include a row and column labeled zero, but leave both empty. Zero is outside the repeating remainder orbit, and it contributes no match. The same construction works for any prime denominator $p$ and any base $b$ not divisible by $p$.

Keeping the positions

The Spectral Power of the Digit Function looked at the digit bins in frequency coordinates. Each bin contributed rotating arrows. Adding the arrows and squaring their total length gave its power at a frequency.

That calculation made the bin lengths visible. Squaring the length of an arrow, however, discards its direction. Move a bin along the remainder line and its Fourier arrows turn, even though their lengths stay the same.

Multiplication asks where a bin sits as well as how long it is. The equality table keeps that positional information. Take its Fourier transform in both directions, one for each remainder label. The resulting table is the cross-spectrum, $G(k,k')$. It describes the same relation as $K$, in frequency coordinates. Fourier inversion can recover every original cell.

The familiar spectral power is still there. It occupies the cells $G(k,-k)$, where the two frequency labels are opposites. The other cells preserve the relations between different frequencies.

There is a useful simplification. Replacing a remainder $r$ by $p-r$ replaces its digit by its complement. In decimal notation, the two digits add to nine. If two digits agreed before this reflection, their complements agree afterward. The filled cells of $K$ therefore come in reflected pairs.

In the Fourier calculation, those pairs cancel the imaginary parts. Every entry of $G$ is real. We can draw it as a table of ordinary signed numbers.

One line through the table

Return to the circles in the remainder grid. They follow a rule of the form $s=ar$, with multiplication reduced modulo the prime. Let $C(a)$ count how many filled cells that path visits.

There is an exact way to read the same count from the frequency table.

$$C(a)=\frac1p\sum_{k=0}^{p-1}G(k,-a^{-1}k).$$

For each first label $k$, the formula selects one second label, $-a^{-1}k$. Add those $p$ entries and divide by $p$. All labels are reduced modulo $p$. The inverse $a^{-1}$ is the number that undoes multiplication by $a$.

The reason a line survives is cancellation. Each Fourier term is a rotating arrow. Along the remainder path, its rotation is controlled by $k+ak'$. If that number is nonzero modulo $p$, the arrows complete a balanced circuit and sum to zero. If it is zero, they all point together. Only the frequency pairs satisfying $k+ak'=0$ survive, giving the line in the formula.

This works for every nonzero multiplier $a$. A cyclic shift chooses a particular one, $a=b^\ell$.

At seven and seventeen in base ten, the repeating word visits every nonzero remainder exactly once. The count over all remainders is therefore the count over all positions in that word,

$$R(\ell)=C(b^\ell).$$

This is where the full-period condition enters. The line formula itself does not need it.

Seven cells give zero

At seven, each occupied digit bin contains one remainder. Distinct remainders never emit the same digit. The table $G$ then has only two values. It is $6$ wherever $k+k'=0$ modulo seven, and $-1$ everywhere else.

At shift zero, the multiplier is one. The formula selects opposite frequency labels. All seven selected cells contain $6$. Divide their total, $42$, by seven and recover the six matches of the unshifted word.

At shift one, the multiplier is $10$, which is $3$ modulo seven. Its inverse is $5$, because $3\cdot5$ leaves remainder one. Negate that inverse and the line becomes $k'=2k$ modulo seven.

Its seven cells are $(0,0)$, $(1,2)$, $(2,4)$, $(3,6)$, $(4,1)$, $(5,3)$, and $(6,5)$. Only the first has labels whose sum is zero. It supplies $6$. Each of the other six supplies $-1$.

$$R(1)=\frac{6+6(-1)}7=0.$$

Every other nontrivial shift meets the bright line only at the origin as well. All five nonzero shifts give zero.

The digit argument at the opening was shorter. The reason to build this table is that the same construction also handles seventeen, where bins contain several remainders and some shifted digits agree. The frequency entries change. The line formula does not.

Eight cycles at forty-one

At denominator forty-one, the decimal word for $1/41$ is $02439$. It repeats after five places. Forty nonzero remainders are available, so this one word visits only an eighth of them.

The other remainders form seven more cycles. Their digit words need not have the same match counts.

Shift $02439$ by two places. None of its positions agrees. But the frequency line for multiplication by $10^2$ gives six matches. It has added the contributions from all eight cycles. Six is the correct total, while zero is the correct answer for the reference word.

The distinction is exact. One line through $G$ gives the aggregate over all cycles. To recover a chosen cycle, retain only its remainders in the Fourier calculation. The formula then uses a sum over that subgroup orbit instead of the simple cancellation over the whole field. It remains an exact formula, but generally involves the full frequency table rather than one line.

Back to the word

In the full-period case, the route to the matrix spectrum is now explicit. The digit bins give their Fourier coefficients. Those coefficients give $G$. A line through $G$ gives each shifted match count. Divide those counts by the period length and take their discrete Fourier transform to obtain the eigenvalues of the cross-alignment matrix.

At the start, we moved a digit from one end of $142857$ to the other and counted nothing. The frequency table gives that nothing a visible arithmetic form. One six is canceled by six minus ones. At seventeen, two matches remain. At forty-one, the answer depends on which cycles we have included. The same table construction accounts for all three, down to the individual match.