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.
When b is a primitive root modulo a prime p, the number C_p(b^\ell) of equal digit coordinates is the agreement form of cyclic-shift Hamming correlation for the base-b repetend of 1/p. We place this observable on the complete nonzero residue ensemble, where the lag theory requires neither primality nor a primitive-root hypothesis. Multiplication by b conjugates the digit bins to ordinary residue classes modulo b. For every prime p>b, the resulting coordinate formula shows that every C_p(g) is even and that precisely b-1 multipliers have no collisions. They are -\frac{u}{b-u}\pmod p, \qquad 1\leq u<b. For the multiplier b^\ell, 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}, and no smaller power of b determines it. Reflection gives S_\ell(a)+S_\ell(-a)=-1, an exact mean of -1/2, and a half-group law for every interior wrapping set.
How many digits of a repetend survive a cyclic shift? When b is a primitive root modulo p, the powers of b visit every nonzero residue. The digit in the position indexed by a residue r is \lfloor br/p\rfloor, and shifting the repetend by \ell positions replaces r by b^\ell r. Thus C_p(b^\ell) is exactly the number of agreements with that cyclic shift, while p-1-C_p(b^\ell) is its Hamming distance.
Sequence agreement under cyclic shift belongs to classical Hamming correlation theory [1]. Kak and Chatterjee studied prime-reciprocal digit sequences as communication codes and obtained bounds for their Hamming distance from cyclic shifts and for their autocorrelation [2]. Armstrong and Armstrong study changing bases, repetend multiplication, and its group structure [3]. These sources establish that the shift observable and its group-theoretic setting are prior art.
A neighboring number-theoretic literature weights digit values along a reciprocal orbit. Under primitive-root hypotheses, Girstmair connected those values with class-number factors and expressed digit variance using a Dedekind sum [4, 5]. Murty and Thangadurai extended digit-average questions to bases of prescribed order using generalized Bernoulli numbers and Dirichlet L-functions [6]. Those value statistics are distinct from the equality indicator considered here, but they identify the established arithmetic setting around reciprocal digits.
The present question is a family question rather than a claim to have introduced cyclic-shift agreement. Replace a single reciprocal orbit by the complete set of nonzero residues. In the full-reptend case the two ensembles coincide. When the order of b is smaller, the complete ensemble contains every orbit, and for the lag results the modulus need not be prime. Multiplication by the base then turns the digit intervals into ordinary residue classes. This conjugation gives the collision-coordinate formula, the base-only zero gate, the sharp determining modulus, and the reflection and half-group laws proved below. No priority claim is made for the underlying Hamming observable.
Let p>b\geq2, with p prime. 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.
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 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. ◻
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.
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). ◻
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 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.
The results above are symbolic. Independent exact checks with nfield [7] 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.
In a full repetend, C_p(b^\ell) counts the coordinates retained by a cyclic shift. The complete-residue formulation keeps that observable when b does not generate the multiplicative group and when the lag modulus is composite. It also exposes statements about an entire denominator family that cannot be read from a single reciprocal sequence.
The first such statement is the gate theorem. Its collision coordinate pairs the two possible displacement directions, proves evenness, and classifies the zero set by b-1 explicit multipliers. The second is sharp finite determination. At lag \ell, the deviation is a function on the units modulo b^{\ell+1}, and the two witnesses in Proposition 10 show that no lower power of the base carries the same information. Reflection then gives both the mean -1/2 and the half-group law for every interior wrapping cut.
These conclusions concern finite modular arithmetic, not the distribution of primes. Primes provide one source of unit classes, but primality is absent from the all-lag determination and reflection theorems. The contribution is therefore not a new definition of Hamming correlation. It is the exact complete-ensemble coordinate and the resulting classification of its zero gate, determining modulus, and reflection balance. This finite table is consequently ready for character or prime sampling without confusing those later questions with what has already been proved here.
[1]A. Lempel and H. Greenberger, Families of sequences with optimal Hamming-correlation properties, IEEE Trans. Inform. Theory 20 (1974), no. 1, 90–94. https://doi.org/10.1109/TIT.1974.1055169
[2]S. C. Kak and A. Chatterjee, On decimal sequences, IEEE Trans. Inform. Theory 27 (1981), no. 5, 647–652. https://doi.org/10.1109/TIT.1981.1056394
[3]N. J. Armstrong and R. J. Armstrong, Some properties of repetends, Math. Gaz. 87 (2003), no. 510, 437–443. https://doi.org/10.1017/S0025557200173619
[4]K. Girstmair, The digits of 1/p in connection with class number factors, Acta Arith. 67 (1994), no. 4, 381–386. https://doi.org/10.4064/aa-67-4-381-386
[5]K. Girstmair, Digit variance and Dedekind sums, J. Number Theory 65 (1997), no. 2, 197–205. https://doi.org/10.1006/jnth.1997.2149
[6]M. R. Murty and R. Thangadurai, The class number of \mathbb{Q}(\sqrt{-p}) and digits of 1/p, Proc. Amer. Math. Soc. 139 (2011), no. 4, 1277–1289. https://doi.org/10.1090/S0002-9939-2010-10560-9
[7]A. S. Petty, nfield, software repository. https://github.com/alexspetty/nfield
Discussion
Sign in to join the discussion.