Bin Derangements and the Gate Width Theorem

Write the twelve fractions from $1/13$ through $12/13$. Read their first decimal digits. Two rows begin with three.

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

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

Multiply every numerator by six and take the remainder after division by thirteen. Five becomes four, since $6\cdot5=30$ leaves remainder four. Both fractions begin with three. Eight becomes nine. Both begin with six.

No other numerator keeps its first digit. Call the collision count $C(g)$, where $g$ is the multiplier. We have $C(6)=2$.

Try every multiplier from two through twelve. Set the identity aside. Multiplication by one leaves all twelve rows alone.

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, only two nonidentity multipliers remain outside the zero set. At a thousand and nine, there are 998. Yet the number with no collisions is still nine.

In base seven, the count is six for every prime greater than seven. 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. This is the gate width theorem.

Phase-Filtered Ramanujan Sums and the Spectral Gate expresses these zeros through spectral cancellation. Here we can name them before computing a spectrum.

A list before the prime

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. The fraction $-1/9$ modulo thirteen means the number that gives $-1$ when multiplied by nine. That number is ten, since $9\cdot10=90$ is one less than a multiple of thirteen. At prime twenty-nine, the same fraction gives sixteen, since $9\cdot16=144$ is one less than a multiple of twenty-nine.

The fraction stays fixed. 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. These are all the zeros.

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

For an even base, the middle fraction is $-1$. It sends digit $d$ to $b-1-d$. 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. Multiplication modulo a prime scatters them. 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. 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. What stays the same is which numbers belong together.

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. Multiplication by $-p$ therefore permutes the digit classes modulo $b$. Two first digits agree exactly when their transformed remainders have the same last digit.

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

Multiply, reduce modulo the prime, then compare modulo the base. We can now look for 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$. Every other label occurs exactly once. The reverse rule is $g\equiv1-b/c\pmod p$.

Labels below the base give no collisions. Labels above the base always give a collision. We can prove both statements without examining a table.

Suppose a collision exists. Put $y=[gx]_p$. Since $x$ and $y$ agree modulo $b$, we can write $y=x+mb$ for an integer $m$. 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. 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)$. That interval contains no multiple of $p$. 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 they agree modulo $b$. The defining equation gives $(1-g)x\equiv-b\pmod p$, so $[gx]_p=x+b=y$.

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

Every nonidentity multiplier is on one side or the other. 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)$. The count and the list come from the same argument.

The scattered zeros line up

The left-hand tables order multipliers numerically. The right-hand tables order them by $c$. Columns stay fixed. No comparison is added or removed.

Columns are transformed remainders $x$. A colored cell means that $x$ and $[gx]_p$ share a last decimal digit. Color names that digit, not the original leading digit. The identity multiplier is omitted from both orders.

Gold marks the nine empty rows. On the right they become the bottom band, at labels one through nine. Label ten is omitted because it would give multiplier zero. Every row above the band contains a match.

The largest table has $1007\cdot1008=1{,}015{,}056$ cells, shown in both orders. The full-size plate retains every one. The colors reveal the changing arrangement beyond the gate. The empty band does not grow.

When the multipliers are shifts of 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.

The companion paper gives the formal statements and their relation to earlier work on sequence correlation.

Four matches, two ways

Return to the two crowded bins at thirteen. Inside the digit-three bin, we can go from four to five or from five to four. Inside the digit-six bin, we can go from eight to nine or from nine to eight.

Four ordered pairs. Each belongs to exactly one multiplier, namely 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. Adding over bins counts every collision outside the identity. The zero multipliers contribute nothing. 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 no remaining set to average. The mean requires $p>b+1$.

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

The mean from the bin sizes

Write $p-1=bQ+R$, with $0\le R<b$. 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. The only nonzero within-bin contributions are two per double bin. 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 tell us how each individual multiplier behaves. It tells us 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 distribute. Once the prime exceeds twice the base, every bin is crowded. More multipliers preserve a digit somewhere in the table.

But nine still preserve none. We can name them before making a single comparison. Reduce the same nine fractions modulo the chosen prime.

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