The digit partition constrains how many independent directions a prime’s pairwise agreement matrix can retain. Let b\ge2, let p\nmid b be prime, let L=\operatorname{ord}_p(b), and let C=(p-1)/L be the number of multiplicative cosets generated by the base. The synchronized cross-alignment matrix has C orbit channels at each of the L orbit frequencies. We write its frequency fibers as explicit Hermitian Gram matrices.
This factorization has a consequence that is not visible from the matrix entries alone. If \nu is the number of occupied digit bins, then the zero-frequency fiber has rank at most \min(C,\nu), while every nonzero fiber has rank at most \min(C,\nu-1). The missing direction comes from the identity that the digit-bin indicators sum to one. We obtain the exact kernel decomposition and the bound \operatorname{rank}\mathbf A_b(p) \le \min(C,\nu)+(L-1)\min(C,\nu-1). In particular, when C\ge\nu, the nullity is at least L(C-\nu+1)-1.
For C=2 we give both eigenvalue branches in closed form at every frequency. When both orbit words have distinct digits, the spectrum has exactly two global levels if and only if the cross-orbit digit-equality count is nonzero and supported at exactly one cyclic shift. This explains the two levels at p=13 in base ten and also shows why two multiplicative cosets do not by themselves force a two-level spectrum.
Two multiplicative cosets do not determine a two-level spectrum. In base ten, the two cosets at p=13 produce exactly the levels 2/3 and 4/3. In base four, the two cosets at p=7 produce four levels, \frac13,\qquad \frac23,\qquad \frac43,\qquad \frac53. The orbit count is the same. The spectrum is not. The difference lies in how the digit bins occupy the Fourier fibers.
The synchronized cross-alignment matrix records how often two fractions display the same base-b digit at the same long-division position. Ordering by multiplicative coset separates that matrix into small Hermitian Fourier fibers. Inside every nonzero fiber, the digit indicators sum to zero. One digit-coordinate direction disappears. When the orbit channels outnumber the remaining digit directions, this forces a kernel in that fiber. The Fourier decomposition then assembles the fiber kernels into the kernel of the full matrix.
Coordinatewise equality is Hamming similarity. Its cyclic correlation theory begins well before the present construction [1], and Kak and Chatterjee study the same observable for full-period reciprocal digit sequences [2]. Repetend multiplication and multiplicative orbit structure are also classical [3]. The simultaneous diagonalization of circulant blocks and Fourier analysis on finite groups are standard [4, 5]. The contribution here is the rank bound forced by the digit partition of unity, the exact kernel decomposition for the complete denominator ensemble, and the two-coset rigidity criterion. None of the underlying Hamming or Fourier machinery is claimed as new.
There are two constraints. First, a frequency fiber has one column for each multiplicative coset but only one row for each occupied digit. Second, the digit indicators form a partition of unity. At nonzero frequency their sum vanishes, so one digit direction disappears. These two facts give an exact kernel decomposition and a uniform rank bound. They also identify a precise obstruction to positive definiteness when the number of cosets is too large for the available digit directions.
The same fiber description settles the two-coset case. Each frequency contributes the two eigenvalues of an explicit two-by-two Hermitian matrix, and a rigidity argument characterizes the exceptional collapse to two global levels.
The Fourier coordinate used here is the exponent along the multiplicative orbit of b. In the primitive-root case, its orbit characters become multiplicative characters modulo p, and the eigenvalues become exact finite character-sum energies.
Here fractional field names the finite family \{k/p:1\le k<p\}; no algebraic-field structure is asserted.
Fix a base b\ge2 and a prime p\nmid b. Put \begin{aligned} G&=(\mathbb Z/p\mathbb Z)^*, & H&=\langle b\rangle,\\ L&=|H|=\mathop{\mathrm{ord}}_p(b), & C&=[G:H]=\frac{p-1}{L}. \end{aligned} Every residue is represented by its least positive integer. Define the digit map \delta(r)=\left\lfloor\frac{br}{p}\right\rfloor, \qquad 1\le r<p, and let \mathcal D=\delta(G),\qquad \nu=|\mathcal D| be the set and number of occupied digit bins.
Lemma 1 (Occupied digit count). The number of occupied digit bins is \nu=\min(b,p-1).
Proof. If b<p, each interval \left[\frac{dp}{b},\frac{(d+1)p}{b}\right), \qquad 0\le d<b, has length p/b>1 and contains an integer in \{1,\ldots,p-1\}. Thus every digit occurs and \nu=b.
If b>p, then for 1\le r<s<p, \frac{b(s-r)}p>1. Hence \lfloor bs/p\rfloor>\lfloor br/p\rfloor, so the digit map is injective and \nu=p-1. The case b=p is excluded by p\nmid b. ◻
Choose representatives c_1,\ldots,c_C for the cosets of H. For d\in\mathcal D, define the digit word and its orbit Fourier coefficient by x_{a,d}(t) =\mathbf 1_{\{\delta(c_ab^t\bmod p)=d\}}, \qquad X_{a,d}(j) =\sum_{t=0}^{L-1}x_{a,d}(t)e^{-2\pi ijt/L}. Let Y_j be the \nu\times C matrix Y_j(d,a)=X_{a,d}(j).
For prime denominators, the synchronized cross-alignment matrix is A_{r,s} =\frac1L\sum_{t=0}^{L-1} \mathbf 1_{\{\delta(b^tr\bmod p)=\delta(b^ts\bmod p)\}}. This formula defines the prime cross-alignment matrix studied below.
Proposition 2 (Orbit-symbol factorization). After the residues are ordered as c_ab^u, Fourier transformation in u\in\mathbb Z/L\mathbb Z gives the following unitary similarity over \mathbb C. \mathbf A_b(p)\ \sim\ \bigoplus_{j=0}^{L-1}M_j, \qquad M_j=\frac1L Y_j^*Y_j. Consequently, \operatorname{spec}\mathbf A_b(p) =\biguplus_{j=0}^{L-1}\operatorname{spec}M_j with multiplicity, and \ker M_j=\ker Y_j. Consequently, for the complexification of the real matrix, \ker\bigl(\mathbf A_b(p)_{\mathbb C}\bigr) \cong\bigoplus_{j=0}^{L-1}\ker Y_j.
Proof. For residues c_ab^u and c_{a'}b^v, A_{(a,u),(a',v)} =\frac1L\sum_{t=0}^{L-1}\sum_{d\in\mathcal D} x_{a,d}(t+u)x_{a',d}(t+v). After shifting the summation index, this depends on v-u modulo L. Thus every coset-to-coset block is circulant. The length-L Fourier transform diagonalizes all of these blocks simultaneously [4]. At frequency j the coset-indexed symbol has entries M_j(a,a') =\frac1L\sum_{d\in\mathcal D} \overline{X_{a,d}(j)}X_{a',d}(j), which is exactly L^{-1}Y_j^*Y_j. The spectral union follows from the direct sum. Finally, \ker(Y_j^*Y_j)=\ker Y_j because \langle Y_j^*Y_jv,v\rangle=\|Y_jv\|^2. ◻
Changing a coset representative from c_a to c_ab^q cyclically shifts its digit word. This multiplies the corresponding column of Y_j by a complex number of modulus one. Reordering the cosets permutes the columns. The matrices M_j therefore change only by unitary similarity. The fiber spectra are intrinsic.
The complex Fourier decomposition does not change the rank of the original real matrix. A real matrix has the same rank over \mathbb R and \mathbb C, and unitary similarity preserves rank. Moreover, Y_{(-j)\bmod L}=\overline{Y_j}, so conjugate frequencies have equal rank and conjugate fibers.
The orbit symbols contain an exact conservation law. \sum_{d\in\mathcal D}x_{a,d}(t)=1 for every coset a and every orbit position t. Its Fourier transform is supported only at zero frequency.
Theorem 3 (Rank and kernel law). The cross-alignment matrix satisfies \mathop{\mathrm{rank}}\mathbf A_b(p) =\sum_{j=0}^{L-1}\mathop{\mathrm{rank}} Y_j and \mathop{\mathrm{nullity}}\mathbf A_b(p) =\sum_{j=0}^{L-1}\bigl(C-\mathop{\mathrm{rank}} Y_j\bigr). Moreover, \mathop{\mathrm{rank}} Y_0\le\min(C,\nu), \qquad \mathop{\mathrm{rank}} Y_j\le\min(C,\nu-1) \quad (j\ne0). Therefore \boxed{\; \mathop{\mathrm{rank}}\mathbf A_b(p) \le \min(C,\nu)+(L-1)\min(C,\nu-1). \;} If x_+=\max(x,0), then equivalently \mathop{\mathrm{nullity}}\mathbf A_b(p) \ge (C-\nu)_+ +(L-1)(C-\nu+1)_+.
Proof. The exact rank and nullity identities follow from Proposition 2 and \ker M_j=\ker Y_j.
At zero frequency, Y_0 has \nu rows and C columns, so its rank is at most \min(C,\nu). For j\ne0, the partition-of-unity identity gives, for every column a, \sum_{d\in\mathcal D}Y_j(d,a) =\sum_{t=0}^{L-1}e^{-2\pi ijt/L}=0. Thus every column lies in the (\nu-1)-dimensional sum-zero hyperplane of \mathbb C^\nu. Hence \mathop{\mathrm{rank}} Y_j\le\min(C,\nu-1). Summing these bounds gives the rank inequality. Subtracting from CL=p-1 gives the nullity inequality. ◻
Corollary 4 (Forced kernel). If C\ge\nu, then \mathop{\mathrm{nullity}}\mathbf A_b(p)\ge L(C-\nu+1)-1. In particular, if L>1 and C\ge\nu, the matrix is singular. More generally, \mathbf A_b(p) is positive definite if and only if Y_j has column rank C at every frequency.
Proof. The displayed bound is Theorem 3 with both positive parts expanded. The positive-definiteness criterion follows because every M_j=L^{-1}Y_j^*Y_j is positive semidefinite and is positive definite exactly when Y_j has column rank C. ◻
The loss of one direction at nonzero frequency is not a numerical accident. It is the Fourier image of the fact that the digit bins partition unity. For C<\nu, the displayed rank bound is p-1. The partition-of-unity constraint alone therefore does not force a kernel in that range.
Proposition 5 (Sharpness at base two). For b=2 and p=7, the rank bound is attained. \mathop{\mathrm{rank}}\mathbf A_2(7)=4,\qquad \mathop{\mathrm{nullity}}\mathbf A_2(7)=2.
Proof. Here L=3, C=2, and \nu=2. The two orbit words are 001,\qquad 011. At zero frequency the two columns of Y_0 are (2,1)^T and (1,2)^T, so \mathop{\mathrm{rank}} Y_0=2. At each nonzero frequency, the columns lie in the one-dimensional sum-zero line. They are nonzero, so each corresponding Y_j has rank one. The exact rank law gives 2+1+1=4, and the matrix has size six. ◻
If b is a primitive root modulo p, then C=1. Each fiber is a scalar. Write X_d=X_{1,d}.
Corollary 6 (Primitive-root energy). Suppose L=p-1. Then the eigenvalue at orbit frequency j is \lambda_j =\frac1L\sum_{d\in\mathcal D}|X_d(j)|^2. If n_d=\#\{r\in G:\delta(r)=d\}, then \lambda_0=\frac1L\sum_{d\in\mathcal D}n_d^2, \qquad 0\le\lambda_j\le\lambda_0.
Proof. Apply Proposition 2 with C=1. At zero frequency X_d(0)=n_d. For every j, |X_d(j)|\le n_d by the triangle inequality, which proves the upper bound. ◻
The trivial orbit frequency is therefore the largest primitive-root eigenvalue. The numerator \sum_dn_d^2 is the digit-bin sum; the matrix normalization divides it by the orbit length. This is one place where orbit-frequency eigenvalues and unnormalized digit-bin power must not be conflated.
Proposition 7 (Spectral excess). Let \lambda_1,\ldots,\lambda_{p-1} be the eigenvalues of \mathbf A_b(p). Then \sum_{k=1}^{p-1}(\lambda_k-1)^2 =\sum_{\substack{r,s\in G\\r\ne s}}A_{r,s}^2. This quantity vanishes exactly when p is digit-partitioning in base b, equivalently when p\le b+1.
Proof. The matrix is real symmetric and has unit diagonal. Therefore \sum_k(\lambda_k-1)^2 =\operatorname{tr}(\mathbf A_b(p)-I)^2 =\sum_{r,s}|A_{r,s}-\delta_{r,s}|^2, which is the stated off-diagonal sum. It vanishes exactly when the matrix is the identity. If the digit map is injective, distinct residues remain distinct after multiplication by every power of b, so their digits never agree and the matrix is the identity. If the digit map is not injective, one distinct pair agrees at the first position and gives a positive off-diagonal entry.
It remains to classify injectivity. If p>b+1, then p-1 residues enter only b digit bins. If p\le b+1, either b=p-1 and \delta(r)=r-1, or b\ge p and b(s-r)/p\ge1 whenever 1\le r<s<p. In either case the digit map is strictly increasing. Hence the matrix is the identity exactly when p\le b+1. ◻
Suppose now that C=2. For a=1,2 and 0\le j<L, put q_a(j)=\sum_{d\in\mathcal D}|X_{a,d}(j)|^2, \qquad z(j)=\sum_{d\in\mathcal D} \overline{X_{1,d}(j)}X_{2,d}(j).
Theorem 8 (Two-coset branches). At frequency j, the two eigenvalues are \lambda_j^\pm =\frac{q_1(j)+q_2(j) \pm\sqrt{(q_1(j)-q_2(j))^2+4|z(j)|^2}}{2L}. The spectrum of \mathbf A_b(p) is the multiset of these 2L values.
Proof. The frequency fiber is M_j=\frac1L \begin{pmatrix} q_1(j) & z(j)\\ \overline{z(j)} & q_2(j) \end{pmatrix}. The displayed values are the two roots of its characteristic polynomial. Proposition 2 supplies the spectral union over all frequencies. ◻
This formula shows why two cosets do not generally produce two global levels. They produce two branches at every frequency. Those branches need not be constant.
There is a sharp criterion in the collision-free within-orbit case. Let w_a(t)=\delta(c_ab^t\bmod p) be the two orbit words and define their cyclic cross-equality count by Q(\ell)=\#\{t:w_1(t)=w_2(t+\ell)\}, \qquad \ell\in\mathbb Z/L\mathbb Z.
Corollary 9 (Two-level rigidity). Assume that every digit occurs at most once in each orbit word. Then \lambda_j^\pm =1\pm\frac{|\widehat Q(j)|}{L}, \qquad \widehat Q(j)=\sum_{\ell=0}^{L-1} Q(\ell)e^{-2\pi ij\ell/L}. For an integer m>0, the matrix has exactly the two global levels 1+m/L and 1-m/L, each with multiplicity L, if and only if Q=m\,\delta_s for one cyclic shift s, where \delta_s is the unit point mass at s.
Proof. Distinct digits within each word give q_1(j)=q_2(j)=L at every frequency. Expanding z(j) and grouping pairs by \ell=s-t gives z(j)=\widehat Q(j). Theorem 8 yields the first formula.
If Q=m\delta_s, then |\widehat Q(j)|=m for every j, which gives the two levels. Conversely, two constant levels force |\widehat Q(j)|=m at every frequency, since each fiber has trace two and it contributes one copy of each level. The cyclic autocorrelation satisfies \sum_tQ(t)Q(t+\ell) =\frac1L\sum_{j=0}^{L-1}|\widehat Q(j)|^2 e^{-2\pi ij\ell/L}. It therefore vanishes for every nonzero \ell. Since Q is nonnegative, two positive entries at distinct positions would make one of these off-zero autocorrelations positive. Thus Q is supported at one shift, and its nonzero value is m. ◻
Proposition 10 (Two exact contrasts). In base ten at p=13, the cross-alignment spectrum consists of 4/3 and 2/3, each with multiplicity six. In base four at p=7, there are two multiplicative cosets but four spectral levels. \frac13,\quad\frac23,\quad\frac43,\quad\frac53.
Proof. For b=10 and p=13, the two orbit words are 076923,\qquad 153846. Each has distinct digits. Their cross-equality count is Q=2\delta_3, so Corollary 9 gives 1\pm2/6 at every frequency.
For b=4 and p=7, the two length-three orbit words are 021,\qquad 123. Again, each word has distinct digits, but now Q=(1,1,0). Its Fourier magnitudes are 2,1,1. The two branches are consequently 1\pm2/3 at zero frequency and 1\pm1/3 at the other two frequencies, giving the four displayed levels. ◻
For 0\le j<L, define the character of H by \psi_j(b^t)=e^{-2\pi ijt/L}. This is the finite-group character coordinate associated with the orbit [5]. If B_d=\{r\in G:\delta(r)=d\}, then the orbit Fourier coefficient is the finite character sum X_{a,d}(j) =\sum_{r\in B_d\cap c_aH}\psi_j(c_a^{-1}r). Thus each fiber M_j is the Gram matrix of digit-bin character sums across the multiplicative cosets.
When C=1, the subgroup H is all of G, and the \psi_j are the multiplicative characters modulo p under the discrete-logarithm identification. Corollary 6 becomes \lambda_j =\frac1{p-1}\sum_{d\in\mathcal D} \left|\sum_{r\in B_d}\psi_j(r)\right|^2. This is an exact incomplete-character-sum energy.
The additive Fourier transform of the intervals B_d on \mathbb Z/p\mathbb Z is \widehat{\mathbf 1}_{B_d}(k) =\sum_{r\in B_d}e^{-2\pi ikr/p}. It is a different construction. It measures digit-bin magnitude in the residue coordinate. The present Fourier transform lives in the multiplicative orbit coordinate and diagonalizes the cross-alignment matrix. Keeping these two domains separate prevents the numerical scale and the interpretation of one spectrum from being assigned to the other.
The orbit-symbol factorization decomposes the kernel exactly, one frequency at a time. The digit indicators sum to one before the Fourier transform and to zero away from zero frequency. This missing digit direction gives rank and nullity bounds depending only on the orbit count, orbit length, and number of occupied digits. It forces a kernel when the orbit channels cannot fit in the remaining digit directions, as the base-two example at seven shows.
Every two-coset spectrum has two explicit branches at each frequency. A two-level collapse is exceptional. When the two orbit words have no internal digit repetitions, it occurs exactly when all cross-orbit equality is nonzero and concentrated at one cyclic shift. The decimal prime thirteen has this property. Two cosets alone do not force it.
For a primitive-root prime, the eigenvalues are exact finite energies of multiplicative characters over digit bins. Sharpness of the rank bound and collisions among frequency branches are now exact finite problems. The deeper question is which digit partitions force more kernel than the partition of unity alone.
[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]P. J. Davis, Circulant Matrices, 2nd ed., Chelsea, 1994.
[5]A. Terras, Fourier Analysis on Finite Groups and Applications, Cambridge University Press, 1999. https://doi.org/10.1017/CBO9780511626265.
Discussion
Sign in to join the discussion.