Bin Derangements and the Gate Width Theorem

Multiply every nonzero remainder modulo thirteen by the same number and ask whether any of them keeps its first decimal digit. For nine of the eleven multipliers other than one, none does. At twenty-nine the count is nine again, at eighty-three it is nine, and at a thousand and nine, with over a thousand multipliers to choose from, it is still exactly nine.

Counts like this usually grow with the problem. The oldest version is the matching problem Montmort solved in 1708, usually told today as a cloakroom handing back hats at random, where the number of ways for nobody to get their own hat grows so quickly that its share of all the ways settles near $1/e$. Here the prime can grow without limit and the count does not move. In base $b$ there are always exactly $b-1$ of these multipliers, and they can be written down as fixed fractions before the prime is even chosen. Phase-Filtered Ramanujan Sums and the Spectral Gate found these zeros as a cancellation in a spectrum. Here they come straight from the digit bins.

Thirteen’s bins are small enough to hold in your head. Two of its fractions begin with three,

4/13 = 0.307692...
5/13 = 0.384615...

two more, $8/13$ and $9/13$, begin with six, and every other first digit belongs to just one fraction. Grouping the numerators by first digit gives ten bins, eight holding one number and two holding two.

Multiply every numerator by six and take the remainder after division by thirteen. Five becomes four, since $6\cdot5=30$ leaves remainder four, and both fractions begin with three. Eight becomes nine, and both begin with six. No other numerator keeps its first digit, so if $C(g)$ counts the collisions for multiplier $g$, we have $C(6)=2$.

Now try every multiplier from two through twelve. One is left out, since it leaves all twelve rows alone.

Each of the nine multipliers with a zero moves every numerator out of its original digit bin, and I call such a multiplier bin deranging, after the hats.

At thirteen only two nonidentity multipliers lie outside the zero set, and at a thousand and nine there are 998, yet the number with no collisions is nine both times. In base seven the count is six for every prime greater than seven, and in base three it is two. For every integer base $b\ge2$ and every prime $p>b$ there are exactly $b-1$ bin-deranging multipliers, and that is the gate width theorem.

A list before the prime

In base ten the entire zero set comes from nine fixed fractions, running from $-1/9$ to $-9$ with $-1$ in the middle.

These are fractions in modular arithmetic. The fraction $-1/9$ modulo thirteen means the number that gives $-1$ when multiplied by nine, which is ten, since $9\cdot10=90$ is one less than a multiple of thirteen. At twenty-nine the same fraction gives sixteen, since $9\cdot16=144$ is one less than a multiple of twenty-nine. The fraction stays fixed while its residue changes with the prime.

For a general base, run $u$ from one through $b-1$. The list is

Every denominator is smaller than $p$, so every division is defined, the resulting multipliers are distinct, and these are all the zeros.

Read the list from opposite ends and the first and last fractions multiply to one, as do the second and second-last. In the formula, $u$ and $b-u$ give inverse multipliers, so undoing a bin derangement is another bin derangement.

For an even base the middle fraction is $-1$, which sends digit $d$ to $b-1-d$, and no digit is its own complement in an even base. Decimal pairs zero with nine, one with eight, and so on. In an odd base the middle digit is its own complement, so this argument does not give a derangement.

From first digits to last digits

The bins are intervals of numerators, and multiplication modulo a prime scatters them, but a change of labels makes them easier to follow. Replace each numerator $r$ by the remainder of $10r$ divided by thirteen. The pair four and five becomes one and eleven, and the pair eight and nine becomes two and twelve.

A shared first digit has become a shared last digit. The digit itself need not stay the same, but which numbers belong together does.

To see why, use base $b$ and write $x=[br]_p$. The brackets mean take the remainder between one and $p-1$. If $d$ is the first digit of $r/p$, long division says

The prime $p>b$ is coprime to the base, so multiplication by $-p$ permutes the digit classes modulo $b$, and two first digits agree exactly when their transformed remainders have the same last digit.

Multiplication by $g$ also survives the relabeling, since the transformed image of $[gr]_p$ is $[gx]_p$. A collision is now exactly

Multiply, reduce modulo the prime, then compare modulo the base. What we are looking for now is numbers separated by whole multiples of $b$.

The two sides of ten

Give each nonidentity multiplier a label $c$ between one and $p-1$ by solving

The label $b$ is excluded because it would give $g=0$, and every other label occurs exactly once. The reverse rule is $g\equiv1-b/c\pmod p$.

Labels below the base give no collisions and labels above the base always give one, and both statements can be proved without examining a table.

Suppose a collision exists and put $y=[gx]_p$. Since $x$ and $y$ agree modulo $b$, we can write $y=x+mb$ for an integer $m$, and they are distinct because $g\ne1$. Multiplying the relation $mb\equiv(g-1)x$ by $c$ gives

Now suppose $0<c<b$. Stepping by $c$ takes us only part of the way that stepping by $b$ does, so the number $x+mc$ lies strictly between $x$ and $y$, whether $m$ is positive or negative.

Both endpoints lie in the open interval $(0,p)$, which contains no multiple of $p$, so the required divisibility is impossible. That settles every label below the base.

Above the base, write down a match. For $c>b$, take

Both lie between one and $p-1$ and agree modulo $b$, and the defining equation gives $(1-g)x\equiv-b\pmod p$, so $[gx]_p=x+b=y$.

At thirteen, multiplier six has label eleven, and the construction gives $x=2$ and $y=12$. Undo the substitution and they become eight and nine, the collision from the beginning.

Every nonidentity multiplier is on one side or the other, and the zero labels are exactly $1,2,\ldots,b-1$. Substitute $c=b-u$ into $g=1-b/c$ and we recover $-u/(b-u)$, so the count and the list come from the same argument.

The scattered zeros line up

The left-hand tables order multipliers numerically and the right-hand tables order them by $c$. The columns stay fixed, and no comparison is added or removed.

Columns are transformed remainders $x$, and a colored cell means that $x$ and $[gx]_p$ share a last decimal digit, with the color naming that digit rather than the original leading digit. The identity multiplier is left out of both orders.

Gold marks the nine empty rows, which on the right become the bottom band at labels one through nine. Label ten is left out because it would give multiplier zero, and every row above the band contains a match.

The largest table has $1007\cdot1008=1{,}015{,}056$ cells, shown in both orders and all kept in the full-size plate. The colors show the arrangement beyond the gate changing from prime to prime while the empty band stays the same width.

Multipliers that shift one repetend

The proof uses every nonzero remainder. It does not require the base to visit them all in one cycle.

If $b$ is a primitive root modulo $p$, its powers visit all $p-1$ remainders. Multiplication by $b^\ell$ then compares a complete repetend with its shift by $\ell$. Nonzero shifts and nonidentity multipliers correspond one to one, so exactly $b-1$ nonzero shifts have no digit matches.

On a shorter cycle, a shift can miss every digit there while producing collisions elsewhere. The full multiplier classification does not give the exact zero count on that shorter word.

Bin Derangements and the Gate Width Theorem gives the formal statements and their relation to earlier work on sequence correlation.

Four matches, two ways

Thirteen’s two crowded bins allow four moves in all. Inside the digit-three bin we can go from four to five or from five to four, and inside the digit-six bin from eight to nine or from nine to eight. Each of those four ordered pairs belongs to exactly one multiplier, the destination divided by the starting residue modulo thirteen.

A bin containing $n_d$ residues has $n_d(n_d-1)$ ordered pairs with distinct entries, and adding over bins counts every collision outside the identity. The zero multipliers contribute nothing and the remaining $p-b-1$ multipliers share the total, so their mean is

At thirteen, four matches divided between two multipliers gives a mean of two. At the boundary prime eleven every bin is a singleton, all nonidentity multipliers are deranging, and there is nothing left to average, so the mean requires $p>b+1$.

At twenty-nine, eight bins hold three residues and two hold two, supplying $8\cdot6+2\cdot2=52$ matches. Eighteen nonidentity multipliers lie outside the zero set, giving a mean of $52/18=26/9$.

The mean from the bin sizes

Write $p-1=bQ+R$, with $0\le R<b$, so there are $R$ bins of size $Q+1$ and $b-R$ of size $Q$. Their ordered pairs total

$$\begin{aligned} \sum_d n_d(n_d-1) &=R(Q+1)Q\\ &\quad +(b-R)Q(Q-1)\\ &=Q\bigl(b(Q-1)+2R\bigr). \end{aligned}$$

There are $p-b-1=b(Q-1)+R$ multipliers to share those pairs. Thus

$$\overline C=\frac{Q\bigl(b(Q-1)+2R\bigr)}{b(Q-1)+R}.$$

The mean equals two throughout $b+1<p\le2b+1$. In this range the bins have one or two members, apart from the endpoint where all have two, so the only nonzero within-bin contributions are two per double bin, and their total is twice the number of nonidentity multipliers outside the gate.

When $R=0$ and the mean is defined, all bins have the same size $Q$ and the formula reduces to $\overline C=Q$.

The sum does not say how each individual multiplier behaves, only exactly how many matches they have to share.

The fraction list, the relabeling, and the pairs

These wider plates place the four prime fields side by side, join the change of coordinates to its parameter line, and collect the ordered pairs inside the two crowded bins.

At thirteen the two crowded bins leave only four matches to share out. Once the prime passes twice the base every bin is crowded and more multipliers keep a digit somewhere in the table, but nine still keep none, and they are the same nine fractions, $-1/9$ through $-9$, reduced modulo whatever prime we choose.