Digit Collisions and the Cubic Law

Divide one by a prime and the digits that come out look like noise, though long division is a machine with no freedom in it at all. Its digits imitate randomness so well that in 1981 Kak and Chatterjee proposed using the digits of prime reciprocals as communication codes.

A code lives or dies by one test. Slide the sequence against a copy of itself and count the places where the digits agree. A good code agrees with its own shifts about as often as chance would allow, and no more. Too much agreement and two signals blur into each other.

So there is a fair question sitting inside ordinary arithmetic. When digits agree, how far do they stray from fair, and is there any law to the straying? Deterministic digits could wander in any pattern at all. The totals could wobble forever as the base changes.

Add up the squared strays over every shuffle a prime base allows, though, and the wobble settles into a law. The total grows exactly like the cube of the base, with coefficient one, and the one comes from an identity Euler knew about the reciprocal cubes. The same total is also, exactly, a weighted sum of Dirichlet $L$-values, the functions that govern how primes spread through arithmetic progressions. A count of agreeing digits and those functions are two readings of one number.

A clock with nine hours

Take a clock with nine hours, numbered zero through eight. Put a mark at zero, at four and at eight. Written in base three, those are 00, 11 and 22, the two-digit words whose digits agree. A collision, in the language of this work, is exactly that. The leading digit and the trailing digit land on the same value.

Now shuffle the clock. Multiply every mark by two and read the answer on the dial. Zero stays at zero. Four goes to eight. Eight goes to sixteen, which on a nine-hour clock is seven. Then push each mark forward two more hours, and watch midnight.

The mark at zero moves to two. It stays in the same day. The mark at eight passes midnight and comes out at one. The mark at seven lands exactly on midnight, and that counts as a crossing too. Two of the three marks cross.

Do the same thing with the multiplier one. The marks stay at zero, four and eight, each moves forward one hour, and only the mark at eight reaches midnight. One crossing.

Everything below grows out of that little count.

A fair share of midnight

A larger push should catch more marks. With a push of two hours, a mark crosses if it starts in the last two hours of the dial. That is two positions out of nine. Three marks spread over nine positions would put, on average, two thirds of a mark in that zone. The fair share for a push of two is two thirds.

So the count of two is a little high. It beats its fair share by four thirds. The count of one, for a push of one, beats its fair share of one third by two thirds.

The multipliers allowed on the clock are the ones sharing no factor with nine. Those shuffle the dial instead of piling marks on top of each other. There are six of them, and their whole table fits in six lines.

multiplier   crossings   fair share   excess
    1            1           1/3        +2/3
    2            2           2/3        +4/3
    4            2           4/3        +2/3
    5            1           5/3        -2/3
    7            1           7/3        -4/3
    8            2           8/3        -2/3

Read the last column from the top and from the bottom at once. One and eight have opposite excesses. So do two and seven, and four and five. Each multiplier is paired with its reflection across the clock, and the pair cancels. Add the column and you get zero, which says nothing about how far the counts wander from fair.

Square the excesses instead. A miss on the low side now counts as much as a miss on the high side.

The squares are made of ninths. Two of the six excesses are four thirds, which square to sixteen ninths. The other four are two thirds, which square to four ninths. Altogether that is forty-eight ninths, or sixteen thirds.

I call this total the collision energy. The word comes from signal processing, where the energy of a signal is the sum of its squares. Nothing physical is moving.

The fair share is not a statistical assumption about random digits. The paper centers the table by removing the average of each residue class, and that exact centering simplifies to the multiplier divided by the base. The fair share is what the arithmetic itself subtracts.

The six-entry calculation in symbols

For an odd prime base $b$, write $m=b^2$. The marked positions are $d(b+1)$ for $0\le d<b$. At a unit multiplier $a$, put $x_d=d(b+1)a\bmod m$. The crossing count is

$$f_b(a)=\#\{d\mid x_d\ge m-a\}.$$

If $a=bq+s$ with $1\le s<b$, the paper first subtracts $1+q$. The resulting class mean is $s/b-1$. Subtracting that mean leaves

$$S^\circ(a)=f_b(a)-\frac ab.$$

The energy is

$$E_b=\sum_{\substack{1\le a<b^2\\(a,b)=1}}|S^\circ(a)|^2.$$

At three, the squared numerators are $4,16,4,4,16,4$, all over nine, and their sum is $48/9=16/3$.

Twenty-seven, and then some

Base three gives a clock of nine hours and three marks. Base five gives a clock of twenty-five hours, five marks and twenty permitted multipliers. Base thirteen gives 169 hours, thirteen marks and 156 multipliers. Every table can be built the same way, by counting crossings and subtracting fair shares.

The energies grow quickly. It helps to measure each one against the cube of its base.

base   multipliers      energy     energy / base^3
   3            6         16/3          0.198
   5           20           48          0.384
   7           42          176          0.513
  11          110          832          0.625
  13          156         1504          0.685
  31          930        24784          0.832
 101        10100       960064          0.932
 251        62750     15249520          0.964

At base three the energy is only a fifth of twenty-seven. By base 251 it is within four percent of the cube. The theorem says the ratio tends to exactly one.

$$E_b=b^3+O\left(b^2(\log b)^2\right)$$

The last column makes the one believable. It cannot make it certain. A column that reads 0.964 is equally happy to be heading for 0.98 or for 1.01. The coefficient has to come from somewhere in the arithmetic, and the rest of this article goes looking for it.

Two sawtooths at different speeds

Squaring a sum sets every term against every other term. So the energy, rewritten, is a sum over pairs.

The pairs have a classical shape. Count upward and keep only the fractional part of each step, and you get a sawtooth. It rises steadily and drops back to the start. Run two sawtooths side by side at different speeds and ask how well they line up. That comparison is a Dedekind sum, named for Richard Dedekind, and it has been studied for well over a century.

The collision energy is a grid of these comparisons. Both coordinates run from one up to one less than the base, the nonzero digits. The cell at $(k, u)$ compares two sawtooths whose speeds are in the ratio $u/k$. Add up the whole grid, multiply by four, and you have the energy exactly, to the last fraction.

Look along the diagonal first. There the two coordinates agree, the ratio is one, and each cell compares a sawtooth with itself. A sawtooth squared averages one twelfth, so each diagonal cell is worth about a twelfth of the $b^2$ hours on the clock. There are about $b$ cells on the diagonal, and the factor of four is still waiting. Four twelfths is a third, and the diagonal carries a third of the cube.

Off the diagonal, cells can repeat. The pairs (1, 2), (2, 4) and (3, 6) all have ratio two, so they hold identical values. They lie on one ray from the corner of the grid. Divide out the common factor and each ray comes back to a single reduced pair.

In the grid for base thirteen, the six circled cells run from (1, 2) out to (6, 12). They sit in six different places and hold exactly the same value, $4592/169$. The gold diagonal and everything off it can be tracked separately, base by base.

base   diagonal / base^3   off-diagonal / base^3
   3          0.154               0.044
  13          0.302               0.382
  31          0.322               0.510
 101          0.330               0.602
 251          0.332               0.632

The diagonal settles almost at once. It is already at 0.33 by base 101. The off-diagonal is the slow one, still climbing toward two thirds at 251. Whatever fixes the one lives off the diagonal.

The exact grid and its diagonal

Using the sawtooth $((x))=\{x\}-1/2$ away from integers and zero at integers, define

$$s(h,m)=\sum_{r=1}^{m-1}((r/m))((hr/m)).$$

The carry-boundary factorization and character orthogonality give

$$E_b=4\sum_{k,u=1}^{b-1}s(k^{-1}u\bmod b^2,b^2).$$

All inverses are modulo $b^2$. The diagonal is exactly

$$\Delta_b=4(b-1)s(1,b^2)=\frac{(b-1)(b^2-1)(b^2-2)}{3b^2}.$$

Reflection across the diagonal swaps a ratio with its inverse, and the identity $s(h,m)=s(h^{-1},m)$ makes those cells equal. Grouping by reduced ratio gives

$$\mathrm{Off}_b=8\sum_{\substack{1\le k<a<b\\(k,a)=1}}\left\lfloor\frac{b-1}{a}\right\rfloor s(k^{-1}a\bmod b^2,b^2).$$

The factor eight is the original four times the two orientations of each pair.

One pair weighs a quarter

Hans Rademacher found a reciprocity law that breaks each of these off-diagonal comparisons into one large term and some small change. Take the large term, count how many copies of each reduced pair fit inside the grid, and the pair with coordinates $k < a$ ends up carrying the weight

$$\frac{1}{k a^2}.$$

The pair (1, 2) weighs one quarter. The pair (1, 3) weighs one ninth. The pair (2, 3) weighs one eighteenth. The weights fall off quickly, and they go on forever. So the question becomes simple to state. What do the weights of all the reduced pairs add up to?

There is a short way to see it. Forget about reducing and allow every pair, common factors and all. Leonhard Euler already knew that total. It is the sum of the reciprocal cubes,

$$1+\frac18+\frac1{27}+\frac1{64}+\cdots$$

a number close to 1.202 that goes by $\zeta(3)$.

Now go back to the reduced pairs. Every pair is a reduced pair scaled up by some whole number. Double both coordinates and the weight falls by a factor of eight. Triple them and it falls by twenty-seven. So adding up all the scaled copies of all the reduced pairs gives the reduced total multiplied by the same sum of reciprocal cubes.

That makes the full total equal to the reduced total times $\zeta(3)$. But the full total is $\zeta(3)$ by itself. The reduced pairs must weigh exactly one.

A total of one, and then the coefficients fall into place. Rademacher’s large term carries a factor of one twelfth. The grid carries a factor of eight. Eight twelfths is two thirds, and that is the off-diagonal. The diagonal brings its third. Nothing is fitted to the table. The cube comes out with coefficient one because the reduced pairs weigh one.

The unit-mass identity and the classical comparison

Write $H_n=\sum_{j=1}^n1/j$. The classical Euler sum gives

$$\sum_{a>k\ge1}\frac1{ka^2}=\sum_{a\ge2}\frac{H_{a-1}}{a^2}=\zeta(3).$$

Every pair has a unique representation $(k,a)=d(k',a')$ with $(k',a')=1$. Absolute convergence allows grouping by $d$, so

$$\zeta(3)=\left(\sum_{d\ge1}\frac1{d^3}\right)\sum_{\substack{a'>k'\ge1\\(a',k')=1}}\frac1{k'a'^2},$$

and therefore

$$\sum_{\substack{a>k\ge1\\(a,k)=1}}\frac1{ka^2}=1.$$

Rademacher reciprocity gives the leading contribution $b^2/(12ka)$ for each reduced pair. Multiplying by the factor eight and the number of copies gives

$$\mathrm{Main}_b=\frac{2b^2}{3}\sum_{\substack{1\le k<a<b\\(k,a)=1}}\frac1{ka}\left\lfloor\frac{b-1}{a}\right\rfloor.$$

Replacing the floor by $(b-1)/a$ exposes the unit-mass sum, and the leading term is $2b^3/3$.

Room for whole copies

The smooth argument assumes something a finite grid cannot do. At base 31 the grid runs from one to thirty. The ray through (1, 7) fits four copies, at 7, 14, 21 and 28. The smooth formula would like thirty sevenths of a copy, a little more than four. Every ray loses a sliver like that to rounding.

A second loss comes from the small change in Rademacher’s law. Part of it is a Dedekind sum at a small modulus, and over a complete cycle those sums cancel exactly. The grid does not always end on a complete cycle. The last cycle gets cut short, and its leftover does not cancel.

The paper bounds both losses together. They are at most a constant times the square of the base times the square of its logarithm, which shrinks to nothing next to the cube. That proves the law. It does not say how big the losses actually are.

The lower panel shows the first loss at base 31. The smooth count $30/a$ slides down continuously while the whole copies drop in steps, and every shaded sliver between them is part of a copy the grid has no room for. Above it the tables from earlier become curves, the diagonal reaching its third almost at once and the unequal pairs still climbing toward two thirds at 251.

The bound and the signed remainder

The precise result, as $b$ grows through odd primes, is

$$E_b=b^3+O\left(b^2(\log b)^2\right).$$

Rademacher’s three-term reciprocity splits the off-diagonal into a main term, an elementary $O(b^2)$ correction and two smaller-modulus Dedekind sums. One of those sums cancels exactly by oddness over a complete reduced residue system.

For the other, at modulus $k$, the first absolute moment obeys

$$\sum_{(u,k)=1}|s(u,k)|\ll k(\log k)^2.$$

Complete unweighted periods sum to zero, so this one-period bound controls partial sums. Abel summation then incorporates the decreasing copy weights. Summing the slices gives the $O(b^2(\log b)^2)$ remainder. Separately, replacing the copy count $\lfloor(b-1)/a\rfloor$ by $(b-1)/a$ creates a floor defect bounded at the same scale. Exact cancellation is used before absolute values are taken.

For the concrete slice $b=31$, $k=7$, the three complete unweighted blocks sum to zero and the final two terms sum to $3/7$. Applying the varying repetition weights changes the sum. The original diagram below shows both this block cancellation and the separate rounding gaps.

Six complete carry fields

Each cell below is one centered multiplier entry, with the multiplier written $a=bq+s$. The columns fix $s$ and each column sums to zero. Reflection sends $(q,s)$ to $(b-1-q,b-s)$ and reverses the sign. The figures use a common nonlinear color scale after dividing each entry by its own base. This brings out weak bands beside the large entries without independently amplifying the larger fields.

Energy uses the unscaled entries. The displayed normalization is only for comparing the pictures. Every entry is computed by integer threshold counts. Zoom in to inspect the finer bands.

The character reading and four further views

The calculus in Carry Boundaries and Bernoulli Spectra gives the same energy a character representation. Put $S_\chi=\sum_{k=1}^{b-1}\chi(k)$ and use the paper’s generalized Bernoulli normalization. Then

$$E_b=\frac4{\varphi(b^2)}\sum_{\chi\ \mathrm{primitive\ odd}}|B_{1,\chi}|^2|S_\chi|^2.$$

The functional equation gives the equivalent weighted moment, again summed over primitive odd characters modulo $b^2$,

$$E_b=\frac{4b}{\pi^2(b-1)}\sum_\chi |L(1,\chi)|^2|S_\chi|^2.$$

These are exact descriptions of the same finite square mass. The carry, Dedekind and character formulas expose different parts of it.

Neighbors

Asking whether the digits of a sequence agree with a shifted copy of themselves is an old question in coding theory. Lempel and Greenberger built sequence families around it, and Kak and Chatterjee studied the digits of prime reciprocals as communication codes in exactly these terms. Kurt Girstmair tied the digits of $1/p$ to class numbers and wrote their variance through Dedekind sums. The reciprocity that splits each comparison is in Rademacher and Grosswald’s little book Dedekind Sums. The Euler sum behind the unit mass is worked out by Flajolet and Salvy.

The closest relative of the cube itself is continuous. Hilberdink, Luca and Tóth evaluate a sum of greatest common divisors that fixes the same leading scale for a smooth sawtooth energy. The finite version, with its complete table of multipliers, its exact centering and its clean third on the diagonal, is as far as I can determine new here. I would be glad to hear otherwise.

The full argument is in The Cubic Law for Digit-Collision Energy.

Three and a half percent

So the straying has a law. At base 251 the squared strays add to 15,249,520, and the cube is 15,813,251. The 563,731 still missing, about three and a half percent, is made of rounded-down copies and cycles cut off before they finish, and both come from the finite grid, exactly. The cubic law gives me a scale to subtract. I want to know whether the difference has an arithmetic shape of its own.