Bin Derangements and the Gate Width Theorem

Write down the twelve fractions from $1/13$ to $12/13$ and look at their first decimal digits. Two rows begin with 3,

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

Two others, $8/13$ and $9/13$, begin with 6. Every other first digit belongs to just one row. If we group the numerators by their first digit, we have ten bins. Eight hold one number. Two hold two.

Now multiply every numerator by 6 and take the remainder after division by 13. The numerator 5 becomes 4, because $6\times5=30$ leaves remainder 4. Both fractions begin with 3. That is one collision. The numerator 8 becomes 9, and both of those fractions begin with 6. That is another.

No other numerator keeps its first digit under this multiplication. The collision count for 6 is two.

Try every multiplier from 2 to 12. Multiplication by 1 would leave all twelve rows alone, so set it aside.

Multiplier	Collisions
2	0
3	0
4	0
5	0
6	2
7	0
8	0
9	0
10	0
11	2
12	0

Nine zeros. Each of those nine multipliers moves every numerator out of its original digit bin. I call it bin deranging.

Nine at $p=13$. Nine at $p=29$. Nine at $p=83$. Nine at $p=1009$.

At thirteen there are only two nonidentity multipliers left over. At a thousand and nine there are 998. Yet the number with no collisions is still nine. For every prime greater than ten, the count is the same.

In base seven the count is six, for every prime greater than seven. In base three it is two. In any base $b$, every prime $p>b$ has exactly $b-1$ bin-deranging multipliers. This is the gate width theorem.

A list before the prime

There is more to the answer than a count. In base ten, the entire zero set comes from nine fixed fractions. The first is $-1/9$. The last is $-9$, with $-1$ in the middle.

These are fractions in modular arithmetic. For example, $-1/9$ modulo 13 means the number that gives $-1$ when multiplied by 9. That number is 10, since $9\times10=90$ is one less than a multiple of 13. At prime 29, the same fraction gives 16, since $9\times16=144$ is one less than a multiple of 29.

The fraction stays fixed. Its residue changes with the prime.

For a general base, the list is

$$g_u\equiv-\frac{u}{b-u}\pmod p.$$

Run $u$ from 1 to $b-1$. 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. The first and last fractions multiply to 1. So do the second and second-last. In the general formula, $u$ and $b-u$ give inverse multipliers. If a multiplier moves every row out of its bin, undoing that multiplication does too.

For an even base, the middle fraction is $-1$. In decimal this is the familiar complement operation. It exchanges digit 0 with 9, 1 with 8, and so on. No decimal digit is its own complement, so every row changes bins. The complement sits in the middle of a larger exact family.

From first digits to last digits

The bins are short intervals of numerators. At thirteen, 4 and 5 sit together because their fractions both begin with 3. But multiplying an interval modulo a prime scatters its entries. It is hard to see all the zero multipliers by watching those intervals move.

Replace each numerator $r$ by the remainder of $10r$ divided by 13. The pair 4 and 5 becomes 1 and 11. The pair 8 and 9 becomes 2 and 12.

The first pair now shares a last digit. So does the second. This happens for every bin. A shared first digit in the fractions becomes a shared last digit in the transformed remainders.

In base $b$, the substitution is $x=[br]_p$, where the brackets mean take the remainder modulo $p$ between 1 and $p-1$. A collision under multiplication by $g$ is now exactly

$$x\equiv[gx]_p\pmod b.$$

Multiply $x$ by $g$, reduce modulo $p$, then compare modulo the base. The order of those steps is important. We have replaced a question about intervals by a question about numbers separated by whole multiples of $b$.

The two sides of ten

There is a useful way to label each nonidentity multiplier. Solve

$$c(1-g)\equiv b\pmod p$$

and choose $c$ between 1 and $p-1$. Each multiplier gets exactly one label. The label $b$ is excluded because it would give $g=0$.

Now the zero set has a simple description. Labels below the base give no collisions. Labels above the base always give at least one collision.

The reason is short enough to follow here. Suppose a collision occurs. Its transformed remainders $x$ and $y$ have the same last digit in the chosen base, so $y=x+mb$ for an integer $m$. The equation defining $c$ then forces $x+mc$ to be divisible by $p$.

If $0<c<b$, the number $x+mc$ lies between $x$ and $y$. Whether $m$ is positive or negative, stepping by $c$ takes us part of the way that stepping by $b$ does. Both endpoints are strictly between 0 and $p$. Nothing between them can be divisible by $p$.

That rules out a collision on the entire lower side.

On the upper side, we can write down a collision. For $c>b$, take $x=p-c$. Multiplication by $g$, followed by reduction modulo $p$, sends it to $x+b$. Both numbers lie between 1 and $p-1$, and they agree modulo $b$.

At thirteen, the multiplier 6 has label $c=11$. The construction gives $x=2$ and $y=12$. They end in the same digit. Undo the substitution and they become the original pair 8 and 9, the collision we saw at the beginning.

So the zero labels are exactly $1,2,\ldots,b-1$. Solving for $g$ and setting $u=b-c$ gives the fractions $-u/(b-u)$. The count and the list come from the same argument.

The proof examines every nonzero multiplier. It works whether the base visits all the nonzero residues in one cycle or divides them among several. When the base does visit them all, multiplying by a power of the base is a cyclic shift of the repetend, and these $b-1$ multipliers give exactly its zero-match shifts. On a shorter cycle, a shift can miss every digit in that cycle while still producing collisions elsewhere. The full table is the object being classified here.

Four matches, two ways

Return to the two crowded bins at thirteen. Inside the digit-3 bin, there are two ways to go from one residue to a different residue. We can go from 4 to 5, or from 5 to 4. Inside the digit-6 bin, we can go from 8 to 9, or from 9 to 8.

Four ordered pairs in total. Each pair belongs to exactly one multiplier.

This gives a second result. A bin containing $n_d$ residues has $n_d(n_d-1)$ ordered pairs with different entries. Add those counts over the bins and we have all the collisions outside the identity. The zero multipliers contribute nothing. The remaining $p-b-1$ multipliers share the total, so their mean is

$$\overline C=\frac{\sum_d n_d(n_d-1)}{p-b-1}.$$

At thirteen, four matches divided between two multipliers gives a mean of two. At the boundary prime eleven, all ten bins are singletons. Every nonidentity multiplier is deranging and there is no remaining set to average. The mean requires $p>b+1$.

We can evaluate the sum from just the bin sizes. Divide $p-1$ by $b$, writing $p-1=bQ+R$. Then $R$ bins contain $Q+1$ residues and the other $b-R$ contain $Q$. Substitution gives

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

For prime 29 in base ten, eight bins hold three residues and two hold two. They supply $8\times6+2\times2=52$ matches. There are 18 nonidentity multipliers outside the zero set, so the mean is $52/18=26/9$.

At thirteen, seventeen and nineteen, the mean is still exactly two. More generally, that value holds throughout $b+1<p\leq2b+1$. When the residues divide evenly among the bins, the mean is exactly their common size $Q$.

The sum does not tell us how each individual multiplier will behave. It tells us exactly how many matches they have to share.

Nine, with room to spare

At thirteen, the two crowded bins leave only four matches to distribute. Once the prime is greater than twice the base, every bin is crowded. Many more multipliers preserve a digit somewhere in the table.

But nine still preserve none. We can name them before making a single comparison, by reducing the same nine fractions modulo the chosen prime. Their inverse pairs survive, and the complement remains at the center.

The base fixes the width of the gate. The prime fills in what happens beyond it.