The Autocorrelation Formula

Long division runs on two kinds of arithmetic at once. Which digit a remainder writes depends only on its size, so the digits sort the remainders into bins by order. Which remainder comes next depends on multiplying by the base, and multiplication scrambles size completely. Every repeating decimal lives where those two meet, and the simplest question you can ask there is how often a repeating block agrees with itself slid along by a few places. Writing the block out answers it one shift at a time. Here the answer comes from the bins alone, through one frequency table per prime in which every possible shift is a single line. The table also answers a slightly different question than the one you might think you asked. At forty-one it reports six matches for a word that, rotated two places, matches itself nowhere, and both numbers are right.

Start small, with 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 and five, and there is still nothing, because each digit occurs only once in the block and no rotation short of a full turn can bring a digit back onto itself.

Now try $1/17$, whose block is $0588235294117647$. Shift it one place and the adjacent eights leave one match and the adjacent ones leave another.

The number of matches at shift $\ell$ is the autocorrelation $R(\ell)$. We count equal digits, not products of their numerical values. At seven the complete list is $6,0,0,0,0,0$, and at seventeen it starts with sixteen self-matches and then two.

Writing out the words gives these answers directly. What I want is to see them 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 two gives

It emits one and leaves remainder three, and that remainder also emits one, because $30=1\cdot17+13$. Those are the adjacent ones in the word. The adjacent eights have the same explanation, since remainder fifteen emits eight and leaves fourteen, and fourteen also emits eight.

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

Label both edges of a square table by the remainders. Put a one in a cell when its two remainders emit the same digit, and zero otherwise. Call the table $K$.

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

This is a table of remainder states and the single digits they emit. The Cross-Alignment Matrix compares whole repeating rows. The two tables are related, but their entries answer different questions.

Include a row and column labeled zero in $K$ and leave both empty, since remainder zero contributes no match. The digit zero can still occur, as it does at the start of $1/17$. The construction works for a prime denominator $p$ and any base $b\ge2$ not divisible by $p$.

Two frequency labels

The Spectral Power of the Digit Function added rotating arrows within each digit bin and squared the length of each sum to get its power. That kept the length and threw away the direction, or phase. Multiplication needs to know where the bins sit, and the full equality table keeps that information.

To give it frequency coordinates, choose two labels, $k$ and $k'$. Every filled cell $(r,s)$ supplies a unit arrow whose turn depends on both labels, through $kr+k's$, and the sum of those arrows is one entry $G(k,k')$ in the cross-spectrum.

Repeat for every pair of frequency labels and a second square table appears. This is the Fourier transform of $K$ in both directions, and unlike the one-variable power, it keeps enough information to recover every cell of $K$.

The old power curve has not disappeared. It occupies the opposite-label cells,

The rest of the table records the other frequency pairings.

The arrows and the two-dimensional transform

Let $f_d(r)$ indicate the bin for digit $d$, with $f_d(0)=0$. Use the unnormalized additive transform

$$\widehat f_d(k)=\sum_{r=0}^{p-1}f_d(r)e^{-2\pi i kr/p}.$$

The equality table and cross-spectrum are

$$K(r,s)=\sum_{d=0}^{b-1}f_d(r)f_d(s),$$ $$G(k,k')=\sum_{d=0}^{b-1}\widehat f_d(k)\widehat f_d(k').$$

There is no conjugate in the second product. Expanding it gives one arrow for each filled cell,

$$G(k,k')=\sum_{r,s=0}^{p-1}K(r,s)e^{-2\pi i(kr+k's)/p}.$$

Inversion divides by $p^2$,

$$K(r,s)=\frac1{p^2}\sum_{k,k'=0}^{p-1}G(k,k')e^{2\pi i(kr+k's)/p}.$$

When $k'=-k$, the two bin coefficients become conjugates. Their product is a squared magnitude, giving $\Phi(k)$.

These are additive frequencies of the remainder labels. They are not the frequencies around a repeating word, and the entries of $G$ are not eigenvalues of the cross-alignment matrix. Equality of symbols under a shift is the classical Hamming correlation. The Autocorrelation Formula gives the finite Fourier proofs and references.

The vertical parts cancel

Reflect a nonzero remainder $r$ to $p-r$ and its digit changes to its complement, so in decimal the two digits add to nine. Reflect both labels of a filled cell and it stays filled, because equal digits have equal complements.

We already have an example. The cell $(2,3)$ pairs with $(15,14)$ modulo seventeen, and the first pair emits two ones while the reflected pair emits two eights. In the Fourier sum, reflection changes the sign of the arrow’s angle, so the two arrows have equal horizontal parts and opposite vertical parts.

The up-and-down parts cancel, and the same pairing works throughout the table, so every entry of $G$ is real. It can be negative, though. The power cells $G(k,-k)$ are never negative, but the rest of the cross-spectrum can be.

One line through the table

The circles in the remainder grid follow $s=ar$ modulo $p$. Let $C(a)$ count the filled cells they visit. The same count can be read from $G$,

For each first label $k$, select the second label $-a^{-1}k$, add those $p$ entries and divide by $p$. All labels are reduced modulo $p$, and the inverse $a^{-1}$ undoes multiplication by $a$.

The line comes from cancellation. Insert $s=ar$ into a Fourier arrow’s angle and the coefficient of $r$ becomes $k+ak'$. If that coefficient is nonzero modulo $p$, summing over $r=0,\ldots,p-1$ takes the arrows once around a balanced circuit and they sum to zero. If $k+ak'=0$, all $p$ arrows point together.

So only the line $k'=-a^{-1}k$ survives. The $p$ aligned arrows cancel one of the two factors of $p$ in Fourier inversion, which leaves the $1/p$ in the formula.

The identity works for every nonzero multiplier $a$. A cyclic shift chooses $a=b^\ell$. At seven and seventeen in decimal, one repeating word visits every nonzero remainder, so

That equality needs the full-period condition, but the line formula does not.

Seven cells give zero

At seven every occupied bin is a singleton, so the equality table has ones only at $(r,r)$ for nonzero $r$. Its transform has just two values, six when $k+k'=0$ modulo seven and minus one otherwise.

At shift zero $a=1$, and the selected cells have opposite frequency labels. All seven contain six, their sum is 42, and $42/7=6$ recovers the unshifted word’s six matches.

At shift one, $a=10\equiv3\pmod7$, whose inverse is five. Negate the inverse and the line becomes $k'=2k$ modulo seven. The selected cells are $(0,0)$, $(1,2)$, $(2,4)$, $(3,6)$, $(4,1)$, $(5,3)$ and $(6,5)$, and only the first has labels whose sum is zero, so the line holds one six and six minus ones.

Every other nontrivial shift meets the sixes only at the origin as well. All five shifted counts vanish.

The digit argument with $142857$ was shorter. The table earns its space at seventeen, where bins contain several remainders. For a one-place shift, ten has inverse twelve, the frequency line is $k'=5k$ modulo seventeen, and its seventeen entries sum to 34.

Divide by seventeen and you get two matches, the adjacent ones and the adjacent eights. The entries have changed, but the rule for reading them hasn’t.

From the match counts to the matrix eigenvalues

At seven the count vector and its normalized version are

$$R=(6,0,0,0,0,0),$$ $$R/6=(1,0,0,0,0,0).$$

Every Fourier sum of the second vector is one, since only its first entry contributes and that entry receives no turn. The six eigenvalues are therefore

$$(1,1,1,1,1,1).$$

These are the eigenvalues of the identity matrix in The Cross-Alignment Matrix.

For a word of period $L$, its rotations have pairwise scores $A_{u,v}=R(v-u)/L$. The resulting circulant has eigenvalues

$$\lambda_j=\frac1L\sum_{\ell=0}^{L-1}R(\ell)e^{2\pi i j\ell/L}.$$

This transform runs around the word, with $L$ positions. The transform defining $G$ runs over remainder labels, with $p$ positions in each direction. In the full-period case the rotations exhaust the denominator’s fractional rows. With several cycles, this calculation describes the within-cycle block, not the full cross-alignment matrix.

Eight cycles at forty-one

The decimal word for $1/41$ is $02439$, and it repeats after five places. Forty nonzero remainders are available, so this word visits only an eighth of them, and the others form seven more cycles. Shift each word by two places and count.

The reference word contributes zero, six other cycles contribute one each, and the last cycle contributes zero, so the line formula adds them all and gives six. Six is the correct count for the whole field and zero is the correct count for the reference word. A line through $G$ does not pick out a cycle just because we began with $1/41$.

To pick one out, keep only its remainders when summing the Fourier arrows. The full-field cancellation no longer applies, and although an exact formula remains, it generally uses the entire frequency table instead of a single line.

The formula for a chosen cycle

Let $H=\langle b\rangle$ be the remainder cycle containing one. A cycle beginning at $c$ is the coset $cH$. Define

$$S_{cH}(m)=\sum_{r\in cH}e^{2\pi i mr/p}.$$

Its shifted match count is

$$R_c(\ell)=\frac1{p^2}\sum_{k,k'=0}^{p-1}G(k,k')S_{cH}(k+b^\ell k').$$

At forty-one this isolates five remainders from forty. Summing the eight orbit answers recovers $C(10^\ell)$.

If the base is primitive, $H$ contains every nonzero residue. Then $S_H(0)=p-1$ and $S_H(m)=-1$ for nonzero $m$. Together with $\sum_{k,k'}G(k,k')=p^2K(0,0)=0$, these values reduce the double sum to the one-line formula. For a proper subgroup, that reduction is not automatic.

Six cross-spectra, from seven to 509

The two-valued table at seven is the smallest one below. Each panel uses decimal digit bins and shows every frequency pair, with colors separating positive and negative entries. The period $L$ and number of cycles are listed separately, because the table contains the whole field in every case.

Values are divided by $p-1$, the number of nonzero remainders. The shared color scale is linear between $-0.02$ and $0.02$ and logarithmic outside that interval, and it does not clip any entry. This is a signed cross-spectrum, not a power plot, and the logarithm changes only the display.

Each table is computed from exact digit equalities, and every nonzero multiplier’s frequency slice is checked against a direct integer count. The largest panel contains $509^2=259{,}081$ cells, so open the plate to inspect them at full size.

The words and their two kinds of table

These wider plates keep the shifted words, remainder grid, frequency lines, and eight-cycle comparison together. Follow the two matches at seventeen from their positions in the word to their cells in the remainder table.

Rotate $02439$ twice and every digit misses. The six matches the line reports are out in the field, in six of the seven other cycles, and not one of them belongs to the word we started with.