Still preparing the reader…Long documents can take a little longer to load and typeset.
Still preparing the reader…Long documents can take a little longer to load and typeset.
Still preparing the reader…Long documents can take a little longer to load and typeset.
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.
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.
Cyclic coordinate agreement is the complement of cyclic Hamming distance. Lempel and Greenberger place this observable in the general theory of periodic-sequence correlation [1]. Kak and Chatterjee study Hamming distance between prime-reciprocal digit sequences and their cyclic shifts. They also bound numerical autocorrelation in a symmetric digit encoding and give a sufficient condition for zero numerical cross-correlation between two maximum-length sequences [2]. Those product-based correlations differ from the digit-match count considered here.
Phase-Filtered Ramanujan Sums and the Spectral Gate [3] expresses digit collisions through a spectral selector. The zero set also admits a direct description from the digit bins, without Fourier coordinates.
The result below works on the complete multiplier group without requiring the base to be a primitive root. It identifies every zero multiplier for every prime p>b and then evaluates the mean collision mass outside the zero set. The prime changes the sizes and contents of the bins, yet the number of zero multipliers remains fixed at b-1.
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 [5].
The identity multiplier is never deranging, since C(1)=p-1. The question concerns the remaining p-2 multipliers.
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.
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.
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 [4] 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.
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. At the boundary p=b+1, every bin is a singleton and every nonidentity multiplier is deranging. The constructive set is empty, so its mean is undefined.
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. ◻
The conjugation r\mapsto[br]_p turns interval geometry into congruence classes. It exposes every zero multiplier at once. The sum rule then gathers the remaining collisions through the exact bin sizes. These are separate pieces of the same finite partition. One locates the zero set, and the other weighs its complement.
When the base is primitive modulo the prime, the result reads as a complete statement about the zero lags of one reciprocal digit word. Without that hypothesis, it still classifies the full multiplier group. The zero gate keeps its width. Only the mass beyond it moves.
[1]A. Lempel and H. Greenberger, Families of sequences with optimal Hamming-correlation properties, IEEE Transactions on Information Theory 20 (1974), 90–94. doi:10.1109/TIT.1974.1055169.
[2]S. C. Kak and A. Chatterjee, On decimal sequences, IEEE Transactions on Information Theory 27 (1981), 647–652. doi:10.1109/TIT.1981.1056394.
[3]A. S. Petty, Phase-Filtered Ramanujan Sums and the Spectral Gate, April 2022. doi:10.5281/zenodo.21850675.
[4]G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008.
[5]R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Cambridge University Press, 2012.
Discussion
Sign in to join the discussion.