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.
Fix an integer base b\ge2 and a prime p\nmid b. The first base-b digit partitions the nonzero residues modulo p. Let K mark pairs in the same digit bin, let G be its two-dimensional Fourier transform, and let C_{p,b}(a) count the same-bin collisions between x and ax. We prove the exact identity C_{p,b}(a) =\frac1{p^2}\sum_{k,k'\bmod p} G(k,k')c_p(k+ak'), where c_p is the classical Ramanujan sum. Its two values isolate the spectral line k+ak'=0 and recover the collision formula. Thus the Ramanujan kernel enters the collision calculation exactly.
A normalized phase coefficient measures the spectral mass that survives cancellation. It lies between C_{p,b}(a)/(p-1) and 1, vanishes exactly when the collision count vanishes, and equals 1 at the identity. When b is primitive modulo p, these statements apply directly to repetend autocorrelation. Euclidean division p=bq+r gives the exact coarse bin word and the continued-fraction tail of p/b. The remainder r fixes both coarse objects, while the quotient and modulus remain visible in the full spectrum. The gate vanishes exactly when multiplication moves every digit bin away from itself, turning spectral cancellation into a finite disjointness problem.
A prime Ramanujan sum takes only two values, yet those values can isolate one line from an entire two-dimensional spectrum. Applied to the digit partition of long division, the selected line counts exactly how many residues keep their digit under multiplication. A classical arithmetic kernel therefore becomes a finite gate for phase survival.
Long division puts two finite structures on the nonzero residues. Multiplication moves a residue through its orbit, while the first displayed digit places it in an interval. A collision occurs when the multiplication leaves that interval label unchanged.
Ramanujan sums and their Dirichlet series are classical [2, 3]. Fourier inversion, orthogonality, Parseval’s identity, and finite-group line selection are standard [5]. Cyclic digit matching is Hamming correlation [6]. Kak and Chatterjee study Hamming distance between prime-reciprocal digit sequences and their cyclic shifts and also bound a numerical digit-product autocorrelation [7]. The equality count used here is Hamming correlation. The result here is the collision-specific assembly. A prime Ramanujan sum detects the linear relation between the two Fourier coordinates of the same-bin kernel. Combining its two values with the vanishing total spectrum leaves the exact spectral slice and hence the collision count. The normalized phase coefficient introduced below then measures how much unsigned spectral mass survives that cancellation.
For fixed n\ge1 and \operatorname{Re}(s)>1, one has \sum_{q=1}^{\infty}\frac{c_q(n)}{q^s} =\frac{\sigma_{1-s}(n)}{\zeta(s)} by the classical theory of Ramanujan and Hardy. Equation (1) gives the analytic context. In the collision identity below, the prime Ramanujan sum instead serves as a finite selector on a linear form in two frequency variables.
Let \mathbb F_p be the field of residues modulo p, represented by 0,1,\ldots,p-1, and put e_p(t)=\exp\!\left(\frac{2\pi i t}{p}\right). For x\in\{1,\ldots,p-1\} define the digit map \delta_{p,b}(x)=\left\lfloor\frac{bx}{p}\right\rfloor. For 0\le d<b, let B_d=\{x\in\mathbb F_p^*\mid \delta_{p,b}(x)=d\}, \qquad f_d=\mathbf 1_{B_d}, where each f_d is extended to \mathbb F_p by f_d(0)=0. Its additive Fourier transform is \widehat f_d(k)=\sum_{x\in\mathbb F_p}f_d(x)e_p(-kx).
The same-bin kernel and its two-dimensional transform are K(x,y)=\sum_{d=0}^{b-1}f_d(x)f_d(y) and G(k,k') =\sum_{x,y\in\mathbb F_p}K(x,y)e_p(-kx-k'y) =\sum_{d=0}^{b-1}\widehat f_d(k)\widehat f_d(k'). For a\in\mathbb F_p^* define the multiplicative collision count C_{p,b}(a) =\sum_{x\in\mathbb F_p^*}K(x,ax) =\bigl|\{x\in\mathbb F_p^*\mid \delta_{p,b}(x)=\delta_{p,b}(ax)\}\bigr|.
For m\in\mathbb F_p, the prime Ramanujan sum is c_p(m)=\sum_{x\in\mathbb F_p^*}e_p(mx) = \begin{cases} p-1 & m=0,\\ -1 & m\ne0. \end{cases}
Theorem 1 (Ramanujan collision identity). For every a\in\mathbb F_p^*, C_{p,b}(a) =\frac1{p^2}\sum_{k,k'\in\mathbb F_p} G(k,k')c_p(k+ak').
Proof. Fourier inversion in both variables gives K(x,y)=\frac1{p^2}\sum_{k,k'\in\mathbb F_p} G(k,k')e_p(kx+k'y). Set y=ax and sum over x\ne0. The inner sum becomes \sum_{x\in\mathbb F_p^*}e_p\bigl((k+ak')x\bigr) =c_p(k+ak'). Substitution yields (4). ◻
Corollary 2 (Spectral slice). For every a\in\mathbb F_p^*, C_{p,b}(a) =\frac1p\sum_{k\in\mathbb F_p}G(k,-a^{-1}k).
Proof. Let S(a)=\sum_{k+ak'=0}G(k,k'). Since K(0,0)=0, Fourier inversion at the origin gives T=\sum_{k,k'\in\mathbb F_p}G(k,k')=p^2K(0,0)=0. The two values of c_p turn the numerator in (4) into (p-1)S(a)-\bigl(T-S(a)\bigr)=pS(a). Division by p^2 gives C_{p,b}(a)=S(a)/p. The relation k+ak'=0 is equivalent to k'=-a^{-1}k. ◻
Theorem 1 is the precise Ramanujan connection. The kernel acts on the linear form k+ak' in the full two-dimensional spectrum.
The slice formula also appears in The Autocorrelation Formula [1]. Here the two-valued Ramanujan selector supplies its derivation from the full spectrum.
Put \Sigma_{p,b}(a)=\sum_{k\in\mathbb F_p}G(k,-a^{-1}k) and M_{p,b}(a) =\sum_{d=0}^{b-1}\sum_{k\in\mathbb F_p} |\widehat f_d(k)|\,|\widehat f_d(-a^{-1}k)|.
Definition 3. The phase-gate coefficient is \Gamma_{p,b}(a) =\frac{|\Sigma_{p,b}(a)|}{M_{p,b}(a)}.
The denominator is positive. Indeed, the term k=0 contributes \sum_d|B_d|^2, and the bins partition p-1 nonzero residues.
Theorem 4 (Exact gate bounds). For every a\in\mathbb F_p^*, \frac{C_{p,b}(a)}{p-1} \le \Gamma_{p,b}(a)\le1. Moreover, \Gamma_{p,b}(a)=0 \quad\Longleftrightarrow\quad C_{p,b}(a)=0, and \Gamma_{p,b}(1)=1. If C_{p,b}(a)>0, then \Gamma_{p,b}(a)\ge\frac1{p-1}.
Proof. Corollary 2 gives \Sigma_{p,b}(a)=pC_{p,b}(a). The triangle inequality gives |\Sigma_{p,b}(a)|\le M_{p,b}(a).
For each digit d, Cauchy–Schwarz and Parseval give \begin{aligned} &\sum_{k\in\mathbb F_p} |\widehat f_d(k)|\,|\widehat f_d(-a^{-1}k)|\\ &\qquad\le \left(\sum_k|\widehat f_d(k)|^2\right)^{1/2} \left(\sum_k|\widehat f_d(-a^{-1}k)|^2\right)^{1/2} =p|B_d|. \end{aligned} Multiplication by -a^{-1} permutes the frequency indices. Summing over the bins yields M_{p,b}(a)\le p\sum_d|B_d|=p(p-1). Together with (7), this proves (6). It also proves the equivalence of the two zero conditions. A positive collision count is a positive integer, which gives the final lower bound.
When a=1, the reality of f_d gives \widehat f_d(-k)=\overline{\widehat f_d(k)}. Hence M_{p,b}(1)=\sum_{d,k}|\widehat f_d(k)|^2=p(p-1). The identity map fixes every nonzero residue, so C_{p,b}(1)=p-1 and (7) gives the same value for \Sigma_{p,b}(1). ◻
The coefficient \Gamma_{p,b}(a) is the normalized fraction of unsigned spectral mass that survives cancellation along one slice. The spectral-slice identity ties that surviving mass exactly to the collision count. The lower bound for a positive gate is for fixed p; it decreases with the modulus and gives no uniform positive gap over all primes.
Assume that b is a primitive root modulo p. The remainders in the long division of 1/p are 1,b,b^2,\ldots,b^{p-2}\pmod p. The corresponding digit word is d_j=\delta_{p,b}(b^j\bmod p), \qquad 0\le j<p-1. For a cyclic lag \ell\in\mathbb Z/(p-1)\mathbb Z define R_{p,b}(\ell) =\bigl|\{j\bmod(p-1)\mid d_j=d_{j+\ell}\}\bigr|.
Proposition 5 (Repetend specialization). If b is primitive modulo p, then R_{p,b}(\ell)=C_{p,b}(b^\ell). Consequently, R_{p,b}(\ell) =\frac1{p^2}\sum_{k,k'\in\mathbb F_p} G(k,k')c_p(k+b^\ell k') =\frac1p\sum_{k\in\mathbb F_p} G(k,-b^{-\ell}k). The phase-gate coefficient vanishes exactly at the zero autocorrelation lags.
Proof. As j runs modulo p-1, the residue x=b^j runs once through \mathbb F_p^*. The equality d_j=d_{j+\ell} is exactly \delta_{p,b}(x)=\delta_{p,b}(b^\ell x). The remaining statements follow from Theorems 1 and 4. ◻
Call p digit-partitioning in base b when \delta_{p,b} is injective on \mathbb F_p^*.
Proposition 6 (Singleton bins). If p is digit-partitioning in base b, then G(k,k')=c_p(k+k') and C_{p,b}(a)= \begin{cases} p-1 & a=1,\\ 0 & a\ne1. \end{cases} If b is also primitive modulo p, then R_{p,b}(\ell)=(p-1)\mathbf 1_{\{\ell=0\}}.
Proof. Injectivity makes every nonempty bin a singleton. Therefore K(x,y)=\mathbf 1_{\{x=y\ne0\}} and G(k,k') =\sum_{x\in\mathbb F_p^*}e_p(-(k+k')x) =c_p(k+k'). The equality \delta_{p,b}(x)=\delta_{p,b}(ax) then holds exactly when x=ax. Since x\ne0, this is equivalent to a=1. Proposition 5 gives the autocorrelation formula. ◻
For singleton bins, the full transform is the Ramanujan kernel.
Write p=bq+r, \qquad 1\le r<b. The remainder is nonzero because p\nmid b. Put n_d=|B_d|.
Theorem 7 (Exact bin word). The bin sizes satisfy n_0=q and, for 1\le d<b, n_d =q+\left\lceil\frac{(d+1)r}{b}\right\rceil -\left\lceil\frac{dr}{b}\right\rceil. Define w_0=0 and w_d =\left\lceil\frac{(d+1)r}{b}\right\rceil -\left\lceil\frac{dr}{b}\right\rceil \qquad (1\le d<b). Every w_d is 0 or 1, and exactly r-1 entries are 1. Thus n_d=q+w_d for every digit d.
Proof. The condition \delta_{p,b}(x)=d is equivalent to \frac{dp}{b}\le x<\frac{(d+1)p}{b}. For d=0, the positive integers in this interval are 1,\ldots,q, so n_0=q. For 1\le d<b, the number of integers in the half-open interval is \left\lceil\frac{(d+1)p}{b}\right\rceil -\left\lceil\frac{dp}{b}\right\rceil. Substitution of (8) gives (9). Since 0<r/b<1, each successive ceiling rises by either 0 or 1. The increments telescope to \sum_{d=1}^{b-1}w_d =\left\lceil\frac{br}{b}\right\rceil -\left\lceil\frac{r}{b}\right\rceil =r-1. ◻
The binary word (w_0,\ldots,w_{b-1}) will be called the excess-bin word. It depends only on b and the remainder r. Different remainders give different words because the number of 1 entries is r-1.
If the first entry is restored to 1, the word becomes \widetilde w_d =\left\lceil\frac{(d+1)r}{b}\right\rceil -\left\lceil\frac{dr}{b}\right\rceil, \qquad 0\le d<b. This is the rational upper mechanical word of slope r/b. Mechanical words, their Christoffel representatives, and their continued-fraction structure are classical [8]. The excess-bin word is the version left after the excluded zero residue removes the first rise.
Corollary 8 (Continued-fraction tail). Use the finite simple continued fraction whose final partial quotient is greater than 1. Then \frac pb =\left[q,\operatorname{CF}\!\left(\frac br\right)\right]. For a fixed base, the remainder r determines both the continued-fraction tail and the excess-bin word.
Proof. Equation (8) gives \frac pb=q+\frac rb=q+\frac1{b/r}. The Euclidean algorithm for b/r supplies the remaining partial quotients [4]. ◻
In base 10, primes different from 2 and 5 lie in four unit residue classes with the following coarse data.
| r=p\bmod10 | continued-fraction tail | excess bins |
|---|---|---|
| 1 | [10] | 0 |
| 3 | [3,3] | 2 |
| 7 | [1,2,3] | 6 |
| 9 | [1,9] | 8 |
For a general base b, every prime p\nmid b lies in one of the \varphi(b) unit residue classes modulo b. These classes label the coarse excess pattern; the quotient and modulus supply the remaining spectral data.
Corollary 9 (Zero-frequency mass). With p=bq+r, G(0,0) =bq^2+(2q+1)(r-1). Thus the quotient q remains visible in the full spectrum.
Proof. Equation (2) and \widehat f_d(0)=n_d give G(0,0)=\sum_{d=0}^{b-1}n_d^2. Theorem 7 gives n_d=q+w_d, with r-1 entries of w equal to 1. Expansion gives the displayed formula. The value changes with q even when r is fixed. ◻
The Euclidean remainder fixes the coarse excess pattern. The quotient and the modulus remain visible in the Fourier data. A continued-fraction tail organizes the first layer of the geometry; the phase gate retains the full quotient and modulus data.
The zero set of the phase gate has a direct combinatorial form.
Proposition 10 (Collision-free multipliers). For a\in\mathbb F_p^*, the following conditions are equivalent.
C_{p,b}(a)=0.
\Gamma_{p,b}(a)=0.
aB_d\cap B_d=\varnothing for every 0\le d<b.
Proof. The first two conditions are equivalent by Theorem 4. A contribution to C_{p,b}(a) is exactly a residue x\in B_d for which ax\in B_d. Such a residue exists exactly when aB_d\cap B_d is nonempty for some d. ◻
This converts spectral cancellation into a finite disjointness problem.
The collision count is a line selected from a two-dimensional spectrum. The prime Ramanujan sum performs that selection exactly. The vanishing total spectrum makes the weighted combination of the line and its complement equal to p times the line sum. Normalizing the surviving mass by the unsigned phase mass gives the phase gate.
The Euclidean division p=bq+r supplies a second exact layer. The remainder fixes the excess-bin word and the continued-fraction tail, while the quotient remains visible even at zero frequency. Together they separate the coarse Euclidean label from the full phase data.
The boundary is concrete. For fixed b and p, determine the multipliers that move every digit bin away from itself.
[1]A. S. Petty, The Autocorrelation Formula, January 2022. https://doi.org/10.5281/zenodo.21850316.
[2]S. Ramanujan, On certain trigonometrical sums and their applications in the theory of numbers, Trans. Cambridge Philos. Soc. 22 (1918), 259–276.
[3]G. H. Hardy, Note on Ramanujan's trigonometrical function c_q(n) and certain series of arithmetical functions, Proc. Cambridge Philos. Soc. 20 (1921), 263–271.
[4]A. Ya. Khinchin, Continued Fractions, Dover, 1997.
[5]A. Terras, Fourier Analysis on Finite Groups and Applications, Cambridge University Press, 1999.
[6]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.
[7]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.
[8]M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, vol. 90, Cambridge University Press, 2002.
Discussion
Sign in to join the discussion.