Bin Derangements and the Gate Width Theorem
Abstract
Let p be prime and let b be an integer with 2\leq b<p. The leading-digit map \delta(r)=\left\lfloor\frac{br}{p}\right\rfloor, \qquad 1\leq r\leq p-1, partitions the nonzero residues modulo p into b bins. A multiplier is called bin deranging when it moves every residue out of its original bin. The bin-deranging multipliers are exactly -\frac{u}{b-u}\pmod p, \qquad 1\leq u<b. There are therefore exactly b-1 of them for every prime p>b. The count depends only on the base and requires no primitive-root hypothesis. The proof uses the permutation r\mapsto br\pmod p, which turns the interval bins of the digit map into ordinary residue classes modulo b.
When b is a primitive root modulo p, the same set gives exactly the zero lags in the cyclic digit-match autocorrelation of 1/p. For p>b+1, an independent double count gives the exact mean collision count over the nonidentity, nonderanging multipliers. Writing p-1=bQ+R with 0\leq R<b, that mean is \frac{Q\bigl(b(Q-1)+2R\bigr)}{b(Q-1)+R}. It equals 2 throughout the full range b+1<p\leq 2b+1. The base fixes the width of the zero gate. The prime determines what happens beyond it.
Nine Zeros at Prime Thirteen
Take p=13 in base 10. The twelve nonzero residues split into the ten digit bins \begin{array}{c|cccccccccc} d&0&1&2&3&4&5&6&7&8&9\\ B_d&\{1\}&\{2\}&\{3\}&\{4,5\}&\{6\}&\{7\}& \{8,9\}&\{10\}&\{11\}&\{12\}. \end{array} Multiplication by 6 leaves two residues in their original bins, as does multiplication by 11. Every other nonidentity multiplier moves every residue into a different bin. There are nine such multipliers. The same count is obtained for every prime greater than 10.
The finite gate in Phase-Filtered Ramanujan Sums and the Spectral Gate [1] asks which multipliers avoid every same-bin match. The prime changes the sizes and contents of the bins, yet the number of such multipliers remains fixed at b-1. That stable count demands both an explanation and an exact identification of the multipliers.
For the rest, fix a prime p and an integer b with 2\leq b<p. Let [a]_p denote the least positive residue of a nonzero class a modulo p. For 1\leq r<p, define \delta(r)=\left\lfloor\frac{br}{p}\right\rfloor and B_d=\{r\in\{1,\ldots,p-1\}\mid\delta(r)=d\}, \qquad 0\leq d<b. The sets B_d are consecutive intervals. Their exact sizes are |B_d| =\left\lfloor\frac{(d+1)p}{b}\right\rfloor -\left\lfloor\frac{dp}{b}\right\rfloor -\mathbf 1_{\{d=b-1\}}, where the last term removes the excluded endpoint p from the last bin. Equivalently, if p-1=bQ+R, \qquad 0\leq R<b, then exactly R bins have size Q+1 and the other b-R bins have size Q.
Indeed, B_d is the intersection of \{1,\ldots,p-1\} with the half-open interval [dp/b,(d+1)p/b). Counting those integers gives (1). Each count is Q or Q+1, and the counts sum to p-1=bQ+R, which gives the stated distribution.
For g\in\mathbb F_p^\times, define its collision count by C(g)=\#\{r\in\{1,\ldots,p-1\}\mid \delta(r)=\delta([gr]_p)\}.
Definition 1. A multiplier g\in\mathbb F_p^\times is bin deranging when C(g)=0. Thus no residue remains in its original bin under multiplication by g. This is the partition form of the usual derangement condition [3].
The identity multiplier is never deranging, since C(1)=p-1. The question concerns the remaining p-2 multipliers.
Intervals become residue classes
The bins are awkward to move multiplicatively because they are intervals. One change of variables removes that difficulty.
Lemma 2 (Conjugation). For 1\leq r<p, put x=[br]_p. Then br=p\delta(r)+x. For any r,s\in\{1,\ldots,p-1\}, \delta(r)=\delta(s) \quad\Longleftrightarrow\quad [br]_p\equiv[bs]_p\pmod b. The permutation r\mapsto[br]_p therefore sends the digit bins to the residue classes modulo b inside \{1,\ldots,p-1\}.
Proof. The first identity is Euclidean division. Reducing it modulo b gives x\equiv-p\delta(r)\pmod b. Since p>b is prime, p is invertible modulo b. The values of \delta lie in \{0,\ldots,b-1\}, so two such values are equal exactly when their corresponding values of x are congruent modulo b. ◻
Lemma 3 (Collision congruence). For every g\in\mathbb F_p^\times, C(g)=\#\{x\in\{1,\ldots,p-1\}\mid x\equiv[gx]_p\pmod b\}.
Proof. Multiplication by b permutes the nonzero residues modulo p. Apply Lemma 2 to r and [gr]_p, then replace [br]_p by x. The second transformed residue is [gx]_p. ◻
The interval problem has now become a congruence problem. Its entire zero set is controlled by one residue.
The gate width theorem
For g\in\mathbb F_p^\times\setminus\{1\}, define c(g)=\left[b(1-g)^{-1}\right]_p. The value c(g)=b cannot occur. Indeed, it would imply (1-g)^{-1}=1 and hence g=0.
Lemma 4 (The zero side). If 1\leq c(g)<b, then C(g)=0.
Proof. Suppose a collision exists. Lemma 3 gives residues x and y in \{1,\ldots,p-1\} with y=[gx]_p, \qquad y=x+mb for some integer m. The defining congruence c(g)(1-g)\equiv b\pmod p gives x+mc(g)\equiv0\pmod p.
If m\geq0, then 0<x+mc(g)=y-m\bigl(b-c(g)\bigr)<p. If m<0, write m=-n with n\geq1. Then 0<x-nc(g)=y+n\bigl(b-c(g)\bigr)<p. In either case a positive integer strictly smaller than p is divisible by p, which is impossible. No collision exists. ◻
Lemma 5 (The positive side). If b<c(g)<p, then C(g)>0.
Proof. Set x=p-c(g), \qquad y=x+b=p-c(g)+b. The assumption b<c(g)<p places both x and y in \{1,\ldots,p-1\}, and x\equiv y\pmod b. Also (1-g)x\equiv-b\pmod p, so [gx]_p=y. Thus x gives a collision. ◻
The two lemmas cover every nonidentity multiplier because c(g) is nonzero and cannot equal b.
The set of deranging multipliers is the zero gate. Its cardinality is the gate width.
Theorem 6 (Gate width). Let p be prime and let b be an integer with 2\leq b<p. The bin-deranging multipliers are exactly \left\{-\frac{u}{b-u}\pmod p\ \middle|\ 1\leq u<b\right\}. There are exactly b-1 of them.
Proof. The map g\longmapsto c(g)=\left[b(1-g)^{-1}\right]_p is a bijection from \mathbb F_p^\times\setminus\{1\} onto \mathbb F_p^\times\setminus\{b\}. Its inverse is c\mapsto1-bc^{-1}. The exclusions on each side make both maps well defined. Lemmas 4 and 5 show that C(g)=0 exactly when c(g)\in\{1,\ldots,b-1\}. Solving c(1-g)=b gives g=1-b/c. Put u=b-c to obtain (5).
These b-1 multipliers are distinct. Equality of the expressions for u_1 and u_2 implies b(u_1-u_2)\equiv0\pmod p. Since 0<b<p and |u_1-u_2|<p, this forces u_1=u_2. ◻
The theorem does more than count the zero set. It writes down every element in it. The prime changes their locations modulo p, while the base fixes their number.
Corollary 7 (Inverse pairing). The deranging multipliers are closed under inversion. The parameters u and b-u give inverse elements. If b is even, the middle parameter u=b/2 gives the self-inverse multiplier -1.
Proof. The two expressions -\frac{u}{b-u} \quad\hbox{and}\quad -\frac{b-u}{u} have product 1. When u=b/2, either expression is -1. ◻
For subsets A,D\subseteq\mathbb F_p^\times, write A/D=\{ad^{-1}\mid a\in A,\ d\in D\}.
Corollary 8 (Ratio set). The union of the within-bin ratio sets has size \left|\bigcup_{d=0}^{b-1}B_d/B_d\right|=p-b.
Proof. A multiplier g belongs to B_d/B_d exactly when some y\in B_d satisfies gy\in B_d. The union therefore contains precisely the nonderanging multipliers. Theorem 6 removes b-1 elements from the p-1 nonzero residues, leaving p-b. ◻
Example 9 (The base-ten gate at thirteen). For b=10 and p=13, formula (5) gives \{2,3,4,5,7,8,9,10,12\}. The only nonidentity multipliers outside the zero set are 6 and 11. Each has collision count 2. These statements follow directly from the bins displayed in Section 1.
Repetend lags
The multiplier theorem does not need a primitive root. Its interpretation as a complete lag theorem does.
Assume that b is a primitive root modulo p. The standard link between multiplicative order and recurring expansions [2] shows that the base-b repetend of 1/p has length p-1. Its digit at position j is a_j=\delta([b^j]_p), \qquad 0\leq j<p-1. For a nonzero lag \ell modulo p-1, define the cyclic digit-match autocorrelation \mathcal R(\ell) =\#\{j\in\{0,\ldots,p-2\}\mid a_j=a_{j+\ell}\}, where the subscript is read modulo p-1.
Proposition 10 (Zero lags). If b is a primitive root modulo p, then \mathcal R(\ell)=C([b^\ell]_p). Exactly b-1 nonzero lags have autocorrelation zero. They are the lags for which b^\ell\equiv-\frac{u}{b-u}\pmod p for some 1\leq u<b.
Proof. As j runs from 0 to p-2, the residue [b^j]_p runs once through \mathbb F_p^\times. Replacing [b^j]_p by r turns the condition a_j=a_{j+\ell} into \delta(r)=\delta([b^\ell r]_p). This proves the identity. The map from nonzero lags to nonidentity multipliers is bijective, so Theorem 6 gives the count and the displayed characterization. ◻
Remark 11. If b is not a primitive root, its powers visit only the subgroup generated by b. Every full-group derangement that lies in this subgroup gives a zero lag on the shorter orbit. The converse need not hold, since a multiplier may avoid collisions on the subgroup while having collisions elsewhere in \mathbb F_p^\times. Theorem 6 therefore remains a full-group statement outside the primitive-root case. An exact count on a shorter repetend requires the collision function restricted to its orbit.
The sum rule
Let n_d=|B_d|. The first moment of the collision counts follows from one exact double count.
Proposition 12 (Sum rule). \sum_{g\in\mathbb F_p^\times}C(g) =\sum_{d=0}^{b-1}n_d^2.
Proof. Count ordered pairs (r,s) of nonzero residues that lie in the same bin. The right side counts them one bin at a time. For each pair there is exactly one multiplier g=sr^{-1} with s=[gr]_p, so the left side counts the same pairs one multiplier at a time. ◻
Equation (2) and the bin-size distribution following (1) give \sum_{d=0}^{b-1}n_d^2 =R(Q+1)^2+(b-R)Q^2 =bQ^2+R(2Q+1).
Call a multiplier constructive when it is not the identity and has positive collision count. If p>b+1, the number of such multipliers is (p-2)-(b-1)=p-b-1=b(Q-1)+R.
Theorem 13 (Mean constructive collision count). Let p>b+1. The mean of C(g) over the constructive multipliers is \overline C =\frac{Q\bigl(b(Q-1)+2R\bigr)}{b(Q-1)+R}. If b is a primitive root modulo p, the same expression is the mean of \mathcal R(\ell) over the nonzero lags for which \mathcal R(\ell)>0.
Proof. The deranging multipliers contribute zero, while C(1)=p-1. Subtracting the identity term from the sum rule and using (6) gives \begin{aligned} \sum_{\substack{g\neq1\\mathbb{C}(g)>0}}C(g) &=bQ^2+R(2Q+1)-(p-1)\\ &=Q\bigl(b(Q-1)+2R\bigr). \end{aligned} Division by (7) proves (8). Under the primitive-root hypothesis, Proposition 10 identifies nonzero lags with nonidentity multipliers. ◻
Corollary 14 (Exact special ranges). Under the hypotheses of Theorem 13, the following statements hold.
If R=0, then \overline C=Q.
The equality \overline C=2 holds exactly when b+1<p\leq2b+1.
As Q tends to infinity with b fixed, \overline C=Q+O_b(1) and \overline C/Q tends to 1.
Proof. The first statement follows by setting R=0 in (8). For the second, subtract 2 after clearing the positive denominator. The equality becomes (Q-1)\bigl(b(Q-2)+2R\bigr)=0. Thus either Q=1 with R>0, which gives b+1<p<2b+1, or Q=2 and R=0, which gives p=2b+1. These cases combine into the stated range.
Finally, rewrite (8) as \overline C =Q+\frac{QR}{b(Q-1)+R}. Since 0\leq R<b, the second term remains bounded when b is fixed. ◻
Gate Width and Collision Mass
Two exact quantities emerge from the same finite partition. The first is the width of the zero gate. It is always b-1, regardless of the prime. The second is the mean weight beyond the gate. It depends on how p-1 divides by b.
The separation is visible before any limiting argument. The conjugation r\mapsto[br]_p turns interval geometry into congruence classes and exposes the b-1 forbidden values of c(g). The sum rule then gathers the remaining collisions through the exact bin sizes. One argument determines where collision counts vanish. The other determines their total mass.
The finite arithmetic is available for direct exploration in the nfield repository [4].
The base fixes the width of the gate. The prime fills in what happens beyond it.
References
[1]A. S. Petty, Phase-Filtered Ramanujan Sums and the Spectral Gate, research paper, April 2022, revised August 2026. doi:10.5281/zenodo.21850675.
[2]G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008.
[3]R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Cambridge University Press, 2012.
[4]A. S. Petty, nfield, software repository. https://github.com/alexspetty/nfield.