The Collision Invariant
Abstract
Let p>b\geq2 be prime. The digit function \delta(r)=\lfloor br/p\rfloor partitions the nonzero residues modulo p into b contiguous bins. Multiplication by b sends these intervals to ordinary residue classes modulo b. We use that conjugation to obtain an exact coordinate formula for the number C(g) of residues that remain in the same bin under multiplication by g. Every collision count is even, and exactly b-1 multipliers have no collisions. They are -\frac{u}{b-u}\pmod p, \qquad 1\leq u<b. For the multiplier b^\ell, primality is unnecessary. If N>b^{\ell+1} and (N,b)=1, then S_\ell(N)=C_N(b^\ell)-\left\lfloor\frac{N-1}{b}\right\rfloor depends only on N modulo b^{\ell+1}. We prove that this is the smallest determining power of b. On the resulting finite unit group, reflection forces S_\ell(a)+S_\ell(-a)=-1 and hence an exact mean of -1/2. The same reflection exchanges every interior wrapping set with its complement, so each such set contains exactly half of the units. The global bias and the local balance come from the same finite symmetry.
Introduction
For a prime p > b, the digit function \delta(r)=\lfloor br/p\rfloor assigns to each nonzero residue modulo p its leading digit in base b. It partitions the residues into b bins B_d=\{r:\delta(r)=d\}. More explicitly, |B_d| =\left\lfloor\frac{(d+1)p}{b}\right\rfloor -\left\lfloor\frac{dp}{b}\right\rfloor -\mathbf 1_{\{d=b-1\}}. If p-1=bQ+R with 0\leq R<b, then R bins have size Q+1 and the others have size Q. Nothing probabilistic enters this partition. It is the direct division of the interval \{1,\ldots,p-1\} by the first base-b digit.
Digit restrictions along the primes form a neighboring analytic literature [1]. The question here is finite. Fix the interval partition and ask how a modular multiplier meets it.
The definitions extend without change to every integer N>b with (N,b)=1. For 1\leq r<N, put \delta_N(r)=\left\lfloor\frac{br}{N}\right\rfloor. For an integer x, let [x]_N denote its least nonnegative residue modulo N.
Definition 1. For g\in(\mathbb Z/N\mathbb Z)^\times, the collision count is C_N(g)=\#\{r\in\{1,\ldots,N-1\}: \delta_N(r)=\delta_N([gr]_N)\}.
The collision count measures how many residues share a bin with their image under multiplication by g. It is a function on the multiplicative group that encodes the interaction between the additive structure of the bins and the multiplicative action of g.
For \ell\geq1, the collision deviation at lag \ell is S_\ell(N)=C_N([b^\ell]_N) -\left\lfloor\frac{N-1}{b}\right\rfloor. For prime p we write \delta, C, and S_\ell(p) when the modulus is clear.
The Linearization
The key structural observation is that multiplication by b transforms the bin partition into a congruence partition.
Lemma 2 (Conjugation). Let N>b with (N,b)=1. For 1\leq r<N, put x=[br]_N. Then br=N\delta_N(r)+x and \delta_N(r)=\delta_N(s) \quad\Longleftrightarrow\quad [br]_N\equiv[bs]_N\pmod b. Under the permutation r\mapsto[br]_N, the digit bins become the residue classes modulo b inside \{1,\ldots,N-1\}.
Proof. The first identity is Euclidean division. Reducing it modulo b gives x\equiv-N\delta_N(r)\pmod b. The integer N is invertible modulo b, and the digit lies in \{0,\ldots,b-1\}. Thus the residue of x modulo b determines the digit and is determined by it. Multiplication by b permutes the nonzero residue classes modulo N. ◻
The interval problem has become a congruence problem. The rest of the argument stays in that coordinate system.
Lemma 3 (Collision congruence). For every g\in(\mathbb Z/N\mathbb Z)^\times, C_N(g)=\#\{x\in\{1,\ldots,N-1\}: x\equiv[gx]_N\pmod b\}.
Proof. Apply Lemma 2 to the pair r and [gr]_N, then replace [br]_N by x. The second transformed residue is [gx]_N. ◻
The Gate Width Theorem
Fix a prime p>b and write p-1=bQ+R, \qquad 0\leq R<b. For g\in\mathbb F_p^\times\setminus\{1\}, define the least positive residue c(g)=\bigl[b(1-g)^{-1}\bigr]_p.
Lemma 4 (Collision coordinate). For every g\in\mathbb F_p^\times\setminus\{1\}, C(g)=2\#\{j\in\{1,\ldots,Q\}:[jc(g)]_p>jb\}.
Proof. By Lemma 3, a collision is a pair x,y\in\{1,\ldots,p-1\} satisfying y=[gx]_p, \qquad y=x+kb for a nonzero integer k with |k|\leq Q. The case k=0 would force g=1, and the bound follows from |y-x|\leq p-2. The defining congruence c(g)(1-g)\equiv b\pmod p gives x+kc(g)\equiv0\pmod p.
Let 1\leq j\leq Q. For k=j, the unique candidate is x=p-[jc(g)]_p, and x+jb\leq p-1 exactly when [jc(g)]_p>jb. For k=-j, the unique candidate is x=[jc(g)]_p, and x-jb\geq1 under the same condition. Thus every successful j supplies two collisions and every collision arises in one of these two ways. The two displacements have opposite signs, so the two collisions are distinct. ◻
Corollary 5 (Bilateral parity). The integer C(g) is even for every g\in\mathbb F_p^\times.
Proof. Lemma 4 handles g\neq1. For the identity, C(1)=p-1, which is even. ◻
Theorem 6 (Gate width). For any prime p > b, \{g \in (\mathbb{Z}/p\mathbb{Z})^{\times} : C(g) = 0\} = \left\{-\frac{u}{b - u} \bmod p : u = 1, \ldots, b{-}1\right\}. In particular, exactly b - 1 multipliers have C(g) = 0, independent of p.
Proof. The identity has C(1)=p-1. For g\neq1, the value c(g)=b would imply (1-g)^{-1}=1 and hence g=0. If c(g)<b, then for 1\leq j\leq Q we have jc(g)\leq Q(b-1)<p \quad\hbox{and}\quad [jc(g)]_p=jc(g)<jb. Lemma 4 gives C(g)=0. If c(g)>b, the index j=1 contributes and C(g)>0. Therefore the zero set is given by 1\leq c(g)<b.
Solving c(1-g)=b and putting u=b-c gives g=-\frac{u}{b-u}\pmod p, \qquad 1\leq u<b. The identity g=1-bc(g)^{-1} recovers g from c(g). Thus the b-1 elements are distinct. ◻
Remark 7. The deranging multipliers form a rational family parameterized by u. The count b - 1 depends only on the base, not on the prime. No primitive-root hypothesis is needed.
The Finite Determination Theorem
Theorem 8 (Finite determination). Let b\geq2 and \ell\geq1. For every integer N>b^{\ell+1} with (N,b)=1, the collision deviation S_\ell(N) depends only on N modulo b^{\ell+1}.
Proof. Put B=b^\ell, \qquad m=bB=b^{\ell+1}. For 1\leq r<N, define the slice index n(r)=\lfloor mr/N\rfloor. Dividing the inequalities n(r)\leq mr/N<n(r)+1 by B shows that the original digit is \delta_N(r)=\left\lfloor\frac{n(r)}{B}\right\rfloor. To read the transformed digit, write Br=qN+y with 1\leq y<N. Then mr=bBr=bqN+by and therefore n(r)=bq+\delta_N(y), \qquad \delta_N([Br]_N)=n(r)\bmod b.
The two digits agree exactly on the diagonal set G_{\ell,b} =\{n\in\{0,\ldots,m-1\}: \lfloor n/B\rfloor=n\bmod b\}. It has the explicit form G_{\ell,b} =\{d(B+1)+bk: 0\leq d<b,\ 0\leq k<b^{\ell-1}\}. Indeed, d is the leading base-b digit of the slice index, while the congruence condition fixes its final digit. In particular, |G_{\ell,b}|=B and both 0 and m-1 belong to it.
For 0\leq n<m, the floor difference \left\lfloor\frac{(n+1)N}{m}\right\rfloor -\left\lfloor\frac{nN}{m}\right\rfloor counts the integers in slice n, except that the final difference also includes the endpoint r=N. All internal slice endpoints are nonintegral because (N,m)=1. Since the final slice is diagonal, the extra endpoint is removed by C_N([B]_N) =-1+\sum_{n\in G_{\ell,b}} \left( \left\lfloor\frac{(n+1)N}{m}\right\rfloor -\left\lfloor\frac{nN}{m}\right\rfloor \right).
Write N=mt+a with 1\leq a<m. The coprimality condition makes a a unit modulo m, so b\nmid a. Every summand separates as t+\left\lfloor\frac{(n+1)a}{m}\right\rfloor -\left\lfloor\frac{na}{m}\right\rfloor. Also \left\lfloor\frac{N-1}{b}\right\rfloor =Bt+\left\lfloor\frac{a-1}{b}\right\rfloor =Bt+\left\lfloor\frac ab\right\rfloor. The B copies of t cancel, leaving S_\ell(N) =-1-\left\lfloor\frac ab\right\rfloor +\sum_{n\in G_{\ell,b}} \left( \left\lfloor\frac{(n+1)a}{m}\right\rfloor -\left\lfloor\frac{na}{m}\right\rfloor \right). The right side depends only on the least positive residue a=[N]_m. ◻
Definition 9. Let m=b^{\ell+1}. Represent each unit class modulo m by its least positive integer a\in\{1,\ldots,m-1\}. Define S_\ell(a) by the right side of (1). Equivalently, it is the common value of S_\ell(N) over all N>m with N\equiv a\pmod m.
Among powers of b, the modulus in Theorem 8 cannot be lowered.
Proposition 10 (Optimal base power). Put B=b^\ell and m=bB. The unit classes a=1, \qquad a'=m-B+1 are congruent modulo B, while S_\ell(a)=0, \qquad S_\ell(a')=-(b-1)b^{\ell-1}. Thus no power b^k with k\leq\ell determines S_\ell.
Proof. Both classes are congruent to 1 modulo b and are therefore units modulo m. In (1), the only diagonal increment for a=1 occurs at n=m-1. Hence S_\ell(1)=0.
Write a diagonal index as n=d(B+1)+bk, \qquad 0\leq d<b, \qquad 0\leq k<b^{\ell-1}. Since a'=m-B+1, reduction modulo m gives [na']_m=[n(1-B)]_m=d+bk. This lies between 0 and B-1. The corresponding floor increment is 1 exactly when [na']_m\geq m-a'=B-1. Equality occurs only for d=b-1 and k=b^{\ell-1}-1, which gives n=m-1. Thus the diagonal sum is again 1. Finally, \left\lfloor\frac{a'}b\right\rfloor =(b-1)b^{\ell-1}, and the claimed value follows from (1). ◻
The Reflection Identity
Theorem 11 (Reflection). Let m=b^{\ell+1} and let a be the least positive representative of a unit modulo m. Then S_\ell(a)+S_\ell(m-a)=-1.
Proof. Write d_n(a)=\left\lfloor\frac{(n+1)a}{m}\right\rfloor -\left\lfloor\frac{na}{m}\right\rfloor. Equation (1) gives S_\ell(a) =-1-\left\lfloor\frac ab\right\rfloor +\sum_{n\in G_{\ell,b}}d_n(a).
For 1\leq n\leq m-2, neither na nor (n+1)a is divisible by m. Hence \left\lfloor\frac{n(m-a)}m\right\rfloor =n-1-\left\lfloor\frac{na}m\right\rfloor and d_n(m-a)=1-d_n(a).
At the two endpoints, d_0(a)=0, \qquad d_{m-1}(a)=1. Both endpoints lie in G_{\ell,b}. Their paired totals are therefore 0 and 2, while each of the other b^\ell-2 diagonal slices has paired total 1.
Since b\nmid a, \left\lfloor\frac ab\right\rfloor +\left\lfloor\frac{m-a}b\right\rfloor =b^\ell-1. Combining the floor terms and diagonal contributions gives S_\ell(a)+S_\ell(m-a) =-2-(b^\ell-1)+0+2+(b^\ell-2)=-1. ◻
Corollary 12 (Grand mean). The average of S_{\ell} over all units modulo b^{\ell+1} is -1/2.
Proof. The map a\mapsto m-a permutes the units. Summing the reflection identity over every unit counts the total of S_\ell twice and gives -\phi(m). Division by 2\phi(m) gives the mean. ◻
The Half-Group Structure
The finite formula for S_\ell(a) is a sum of floor increments. The increment at index n equals 1 when (n+1)a crosses a multiple of m. This local balance does not depend on whether n belongs to the collision diagonal.
Let m\geq3 and let 1\leq n\leq m-2. Using least positive representatives for the units, define W_n=\{a\in(\mathbb Z/m\mathbb Z)^\times: [(n+1)a]_m<a\}.
Theorem 13 (Half-group). For every m\geq3 and every 1\leq n\leq m-2, |W_n|=\frac{\phi(m)}2.
Proof. Put c=n+1, so 2\leq c\leq m-1. If a is a unit, then [ca]_m is nonzero. Also [ca]_m=a would imply (c-1)a\equiv0\pmod m and hence c\equiv1\pmod m, which is impossible. Therefore [ca]_m is always strictly below or strictly above a.
Reflection gives [c(m-a)]_m=m-[ca]_m. It reverses the strict comparison with a. Thus a\mapsto m-a carries W_n bijectively onto its complement in the unit group. The two sets have the same size. ◻
Corollary 14. For m=b^{\ell+1}, every diagonal slice in G_{\ell,b} other than 0 and m-1 has a wrapping set of size \phi(m)/2.
The collision diagonal chooses which local increments enter S_\ell. Their exact half-group balance is already present on every interior slice.
Finite Checks
The results above are symbolic. Independent exact checks with nfield [2] evaluated the gate theorem for all 404 pairs with 2\leq b\leq16 and prime b<p\leq127. At lag one, finite determination was checked for every eligible prime through 5000 in bases 3,5,7, and 10, giving 2623 prime instances with every unit class represented. Reflection and the exact mean were checked on every unit class in those four finite tables. For base 3 and lags 1,2,3, finite determination was also checked for all 2986 eligible prime instances through 8000. These finite calculations are independent checks and are not used in the proofs.
Finite Arithmetic
Multiplication by the base does the structural work. It turns interval membership into a congruence, exposes the complete zero gate, and makes every collision count bilateral. At lag \ell, the same coordinate change removes the size of N and leaves a function on the units modulo b^{\ell+1}. Proposition 10 shows that no smaller power of the base carries the full function.
Reflection on that finite group has two exact effects. It forces the global mean to be -1/2, and it exchanges the two sides of every interior wrapping cut. Neither statement depends on the distribution of primes. A prime selects a unit class, but the collision geometry is already complete on the finite modulus.
The invariant is therefore finite before it is analytic. Its arithmetic table is fixed before a prime is asked to occupy it.
References
[1]C. Mauduit and J. Rivat, Sur un problème de Gelfond: la somme des chiffres des nombres premiers, Ann. of Math. 171 (2010), 1591–1646.
[2]A. S. Petty, nfield, software repository. https://github.com/alexspetty/nfield