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.
The consecutive digit bins make additive digit agreement exactly computable, both as an overlap count and as a Fourier power profile. Let b\ge2 be a positional base and let p\nmid b be prime. The digit function \delta(r)=\left\lfloor\frac{br}{p}\right\rfloor, \qquad 1\le r<p, partitions the nonzero residues modulo p into consecutive digit bins. We define the spectral power \Phi(k) by taking the additive Fourier transform of each bin indicator and summing the squared magnitudes.
Write p-1=bq+\rho with 0\le\rho<b. For nonzero k\in\mathbb Z/p\mathbb Z, we prove \Phi(k) =(b-\rho) \frac{\sin^2(\pi kq/p)}{\sin^2(\pi k/p)} +\rho \frac{\sin^2(\pi k(q+1)/p)}{\sin^2(\pi k/p)}. At zero frequency, \Phi(0)=bq^2+\rho(2q+1), and Parseval gives \sum_k\Phi(k)=p(p-1). The zero mode is the total same-bin collision mass. More generally, \Phi is the Fourier transform of the additive digit-collision count. That count is itself an explicit sum of the two triangular profiles determined by the bin lengths.
The spectral power is flat if and only if p\le b+1, which is exactly the range in which the digit function is injective on the nonzero residues.
In base ten at p=13, the digit function divides the twelve nonzero residues into bins of sizes (1,1,1,2,1,1,2,1,1,1). Their zero-frequency collision mass is 16, while every nonzero frequency is \Phi(k)=8+8\cos^2\left(\frac{\pi k}{13}\right). Ten small integers determine an entire additive power profile.
The digit partition of a prime p in base b is the collection of bins B_d= \left\{r\in\{1,\ldots,p-1\} \mathrel{\Big|} \left\lfloor\frac{br}{p}\right\rfloor=d\right\}, \qquad 0\le d<b. The bin sizes n_d=|B_d| are integer invariants of the pair (p,b). Their squared sum counts ordered pairs of remainders that emit the same digit. In collision language, it is the total collision mass of the digit function.
The squared bin count is only the zero-frequency part of a larger object. Transform each bin indicator on the additive group \mathbb Z/p\mathbb Z, square its magnitude, and sum over the digits. The result is the spectral power \Phi(k). Its value at k=0 recovers the collision mass. The remaining frequencies show how that mass is distributed under additive translation, and Fourier inversion recovers the complete additive collision profile.
Comparing digit labels before and after an additive shift gives a Hamming-correlation observable, with the residue zero omitted. This belongs to the classical theory of finite sequence families [1]. Parseval, the finite autocorrelation transform, and the interval Dirichlet kernel are standard Fourier tools [2, 3]. The result below is the exact evaluation forced by the arithmetic digit partition. Its bins have only two lengths, so the full power spectrum is a sum of two explicit interval kernels, its inverse transform is a pair of triangular profiles, and flatness has the sharp boundary p\le b+1.
The calculation rests on one elementary fact. The digit function is nondecreasing, so every nonempty bin is an interval of consecutive residues. The Fourier transform of such an interval is a finite geometric sum. Its magnitude depends only on the interval length. Those lengths take only two values, which reduces the spectral power to two interval kernels. We use the standard unnormalized Fourier transform on the finite cyclic group [2]. The interval kernel is the classical Dirichlet kernel [3].
The construction uses the additive residue coordinate. Fourier coordinates taken along powers of the base live on the multiplicative orbit instead. Magnitude and orbit order carry different information.
For each d\in\{0,1,\ldots,b-1\}, extend the indicator of B_d to \mathbb Z/p\mathbb Z by setting \mathbf 1_{B_d}(0)=0. Define \widehat{\mathbf 1}_{B_d}(k) =\sum_{r\in B_d}e^{-2\pi i kr/p}, \qquad k\in\mathbb Z/p\mathbb Z.
Lemma 1 (Consecutive bins). Every nonempty bin B_d is an interval of consecutive integers.
Proof. The condition \delta(r)=d is equivalent to \frac{dp}{b}\le r<\frac{(d+1)p}{b}. The integer points in a half-open real interval are consecutive. Intersecting with \{1,\ldots,p-1\} removes the residue zero from the first interval. The strict upper inequality excludes p from the last one. ◻
Lemma 2 (Two bin lengths). Write p-1=bq+\rho, \qquad 0\le\rho<b. Then exactly \rho bins have size q+1, and exactly b-\rho bins have size q.
Proof. Write p=bQ+s. Since p\nmid b, we have 1\le s<b. The number of integer points in the dth half-open interval is \left\lceil\frac{(d+1)p}{b}\right\rceil -\left\lceil\frac{dp}{b}\right\rceil, with one removed from the first interval because the partition omits r=0. The first bin has size Q. Each later difference is either Q or Q+1, since the corresponding increment of ds/b is less than one. We have q=Q and \rho=s-1. The sizes sum to p-1=bQ+s-1, so exactly s-1=\rho bins have the larger size. ◻
Lemma 3 (Interval transform). Suppose B is an interval of n consecutive residues. For nonzero k\in\mathbb Z/p\mathbb Z, \left| \sum_{r\in B}e^{-2\pi i kr/p} \right| = \left| \frac{\sin(\pi kn/p)}{\sin(\pi k/p)} \right|. At k=0, the magnitude is n. The formula gives zero when B is empty.
Proof. There is nothing to prove when n=0. Otherwise write B=\{a,a+1,\ldots,a+n-1\}. At nonzero frequency, \sum_{r\in B}e^{-2\pi i kr/p} =e^{-2\pi i ka/p} \frac{1-e^{-2\pi i kn/p}} {1-e^{-2\pi i k/p}}. The first factor records the position of the interval and has modulus one. Taking absolute values gives the stated formula. At zero frequency the sum has n terms. ◻
Definition 4. The spectral power of the digit function at frequency k is \Phi(k)= \sum_{d=0}^{b-1} \left|\widehat{\mathbf 1}_{B_d}(k)\right|^2. Equivalently, encode digit d by the dth coordinate vector in \mathbb C^b. Then \Phi(k) is the squared norm of the Fourier transform of that vector-valued encoding. A relabeling of the digits only permutes the coordinates and leaves \Phi unchanged.
Theorem 5 (Spectral power formula). Let p-1=bq+\rho with 0\le\rho<b. For nonzero k\in\mathbb Z/p\mathbb Z, \Phi(k) =(b-\rho) \frac{\sin^2(\pi kq/p)}{\sin^2(\pi k/p)} +\rho \frac{\sin^2(\pi k(q+1)/p)}{\sin^2(\pi k/p)}. At zero frequency, \Phi(0) =(b-\rho)q^2+\rho(q+1)^2 =bq^2+\rho(2q+1).
Proof. By Lemma 1, every nonempty bin is a consecutive interval. Lemma 3 shows that its squared Fourier magnitude depends only on its length. Lemma 2 gives b-\rho bins of length q and \rho bins of length q+1. Summing their contributions proves both formulas. ◻
Corollary 6 (Total spectral power). \sum_{k=0}^{p-1}\Phi(k)=p(p-1).
Proof. Finite Parseval gives \sum_{k=0}^{p-1} \left|\widehat{\mathbf 1}_{B_d}(k)\right|^2 =p n_d. Summing over d gives \sum_{k=0}^{p-1}\Phi(k) =p\sum_{d=0}^{b-1}n_d =p(p-1). ◻
At zero frequency, \Phi(0)=\sum_{d=0}^{b-1}n_d^2. This is the number of ordered pairs (r,s) of nonzero residues for which \delta(r)=\delta(s). It is the total collision mass of the digit partition.
The other frequencies resolve the same equality relation under additive shifts. For h\in\mathbb Z/p\mathbb Z, define C_{\mathrm{add}}(h) =\sum_{d=0}^{b-1} \sum_{r\in\mathbb Z/p\mathbb Z} \mathbf 1_{B_d}(r)\mathbf 1_{B_d}(r+h). Thus C_{\mathrm{add}}(h) counts additive digit collisions at shift h. Terms involving the residue zero contribute nothing.
Proposition 7 (Exact collision profile). Choose the representative j\in\{0,1,\ldots,p-1\} of h and put t(h)=\min\{j,p-j\}, \qquad x_+=\max\{x,0\}. Then C_{\mathrm{add}}(h) =(b-\rho)\bigl(q-t(h)\bigr)_+ +\rho\bigl(q+1-t(h)\bigr)_+.
Proof. Translation does not change the overlap of a bin with a copy of itself, so consider an interval I=\{0,1,\ldots,n-1\} in \mathbb Z/p\mathbb Z. Its overlap at shift h is |I\cap(I-h)| =(n-j)_+ + \bigl(n-(p-j)\bigr)_+. The two terms count the ordinary differences j and j-p between points of I.
Every digit-bin length is at most p/2. For p=2, there is only one nonzero residue, so each occurring length is 1=p/2. For odd p, we have q\le(p-1)/2. If an occurring length q+1 exceeded p/2, then q=(p-1)/2. The identity p-1=bq+\rho would force b=2 and \rho=0, so no bin of length q+1 would occur. Thus at most one of the two overlap terms is nonzero, and |I\cap(I-h)|=\bigl(n-t(h)\bigr)_+. There are b-\rho bins of length q and \rho bins of length q+1. Summing their overlaps gives the formula. ◻
Proposition 8 (Additive collision transform). The Fourier transform of C_{\mathrm{add}} is \Phi. More precisely, \sum_{h=0}^{p-1} C_{\mathrm{add}}(h)e^{-2\pi i kh/p} =\Phi(k). Consequently, C_{\mathrm{add}}(h) =\frac1p\sum_{k=0}^{p-1} \Phi(k)e^{2\pi i kh/p}.
Proof. For each digit d, set s=r+h. Then \sum_{h,r} \mathbf 1_{B_d}(r)\mathbf 1_{B_d}(r+h) e^{-2\pi i kh/p} = \widehat{\mathbf 1}_{B_d}(k) \overline{\widehat{\mathbf 1}_{B_d}(k)}. Summing over the digits gives \Phi(k). Finite Fourier inversion gives the second identity. ◻
There are two different totals. The collision mass satisfies \sum_h C_{\mathrm{add}}(h)=\Phi(0) and depends on the bin sizes. The total spectral power satisfies \sum_k\Phi(k)=pC_{\mathrm{add}}(0)=p(p-1) and is independent of the base for fixed p. At shift zero every nonzero residue matches itself, regardless of how the bins are divided.
Here collision means equality of digit-bin labels after a declared arithmetic move. The move in Proposition 8 is additive translation. A multiplicative move gives the different count C_{\mathrm{mult}}(g) =\sum_{d=0}^{b-1} \sum_{r\in\mathbb Z/p\mathbb Z} \mathbf 1_{B_d}(r)\mathbf 1_{B_d}(gr), \qquad g\in(\mathbb Z/p\mathbb Z)^{\times}. Both counts begin with the same digit partition. They differ in the action applied before equality is tested.
For p=13 and b=10, the bin sizes are (n_0,n_1,n_2,n_3,n_4,n_5,n_6,n_7,n_8,n_9) =(1,1,1,2,1,1,2,1,1,1). Here q=1 and \rho=2. The zero mode is \Phi(0)=8\cdot1^2+2\cdot2^2=16. For k\ne0, Theorem 5 gives \Phi(k) =8+2\left| \frac{\sin(2\pi k/13)}{\sin(\pi k/13)} \right|^2 =8+8\cos^2\left(\frac{\pi k}{13}\right). Since \sum_{k=1}^{12} \cos^2\left(\frac{\pi k}{13}\right) =\frac{11}{2}, we obtain \sum_{k=0}^{12}\Phi(k) =16+96+44 =156 =13\cdot12, in agreement with Corollary 6.
Call p digit-partitioning in base b when \delta is injective on \{1,\ldots,p-1\}. Equivalently, every bin contains at most one residue.
Proposition 9 (Flatness criterion). The following conditions are equivalent.
The prime p is digit-partitioning in base b.
The inequality p\le b+1 holds.
The spectral power is constant on \mathbb Z/p\mathbb Z.
When these conditions hold, \Phi(k)=p-1 at every frequency.
Proof. Suppose first that p\le b. Since p\nmid b, we have b>p. For 1\le r<s<p, \frac{bs}{p}-\frac{br}{p} =\frac{b(s-r)}p >1, so the two floors are distinct. If p=b+1, then \delta(r) =\left\lfloor r-\frac{r}{p}\right\rfloor =r-1, \qquad 1\le r<p, which is again injective. If p>b+1, then p-1>b, and the pigeonhole principle forces two residues into one bin. This proves the equivalence of the first two conditions.
If every bin is empty or a singleton, then each occupied bin contributes one at every frequency. There are p-1 occupied bins, so \Phi(k)=p-1 for all k.
Conversely, suppose \Phi is constant. Corollary 6 shows that the constant value is p-1. Hence \sum_{d=0}^{b-1}n_d^2 =\Phi(0) =p-1 =\sum_{d=0}^{b-1}n_d. Each n_d is a nonnegative integer, so every n_d equals zero or one. The digit function is injective. ◻
The spectral power retains magnitudes and discards phase. For one bin beginning at a_d, its Fourier coefficient contains the factor e^{-2\pi i ka_d/p}. Taking the squared magnitude removes that factor. Summing over the bins retains the total power at each additive frequency but not the relative phases of the bins.
The consecutive-bin structure and the two possible bin lengths determine every value of \Phi. The zero mode is the total collision mass. Fourier inversion returns the two triangular overlap profiles, and flatness occurs exactly at the digit-partitioning boundary p\le b+1.
Multiplicative orbit order is separate information. At p=7, both b=8 and b=10 lie in the flat range, so both give \Phi(k)=6 at every additive frequency. Yet 8 has multiplicative order one modulo 7, while 10 has order six. The same additive power profile therefore occurs with different multiplicative orbit orders. The same flat additive power can sit on a fixed point or a six-cycle.
[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]A. Terras, Fourier Analysis on Finite Groups and Applications, Cambridge University Press, 1999. https://doi.org/10.1017/CBO9780511626265.
[3]A. Zygmund, Trigonometric Series, Volumes I and II, third edition, Cambridge University Press, 2003. https://doi.org/10.1017/CBO9781316036587.
Discussion
Sign in to join the discussion.