codes – Globbering Mattress

This post is about a cute equality that I discovered today. One of the joys of mathematics is to do be able to have one idea with multiple different viewpoints that enable us to see it. This equality is a very good demonstration of the philosophy.

First I will state the equality, and then I will tell you why I was dealing with it in the first place. The equality is the following.

Proposition
Suppose ${n,q \in \mathbb{N}}$ , ${n,q\ge 2}$ are such that ${\gcd(n,q)=1}$ . Let ${\text{ord}_n(q)}$ denote the multiplicative order of ${q}$ in the group ${(\mathbb{Z}/n\mathbb{Z})^{*}}$ . Then the following holds

$\displaystyle \frac{1}{ \text{ord}_n(q)} \sum_{j=0}^{ \text{ord}_n(q) - 1} \gcd(q^j - 1 , n) = \sum_{d | n}^{ } \frac{\varphi(d)}{ \text{ord}_d(q)} .$

Proof: Both sides count the same thing, namely the number of cycles of the ‘multiplication by ${q}$ ‘ map ${m_q:\frac{\mathbb{Z}}{n\mathbb{Z}} \rightarrow \frac{\mathbb{Z}}{ n \mathbb{Z}}}$ . Note that because ${\gcd(n,q)=1}$ , this map is a permutation. By an easy application of the Burnside’s lemma (also known as Cauchy-Frobenius theorem and “The lemma that is not Burnside’s”) on the action of the group generated by ${m_q}$ inside the permutation group of ${S_n}$ , we can get the left side of the equality. Let ${G = \langle m_q \rangle}$ be this group acting on ${\mathbb{Z}_n}$ . The size of the group is undoubtably ${\text{ord}_n(q)}$ . How many elements are fixed by the element ${m_q^j}$ for some ${j}$ ? That would be the elements of the set ${\{ i \in\mathbb{Z}/n\mathbb{Z} \ | \ iq^j \equiv_n i\}= \{ i\in \mathbb{Z}/n\mathbb{Z}\ | \ i(q^j-1) \equiv_n 0\}= \{ i \in \mathbb{Z}/n\mathbb{Z} \ | \ n/\gcd(q^j-1,n) \text{ divides } i\}.}$ Scratch your head a little and you will see that there are exactly ${\gcd(q^j - 1,n)}$ such elements in ${\mathbb{Z}/n\mathbb{Z}}$ .

Therefore, by plugging in the formula of the Cauchy-Frobenius lemma, we get that the number of orbits is

$\displaystyle \frac{1}{ |G|} \sum_{g \in G}^{ }| (\mathbb{Z}/n\mathbb{Z})^{g} | = \frac{1}{\text{ord}_n(q)} \sum_{j=0}^{\text{ord}_n(q) - 1} \gcd(q^j-1,n).$

Now for the right hand side.

Note that for any ${i \in \mathbb{Z}_n}$ , ${\gcd(i,n) = \gcd(iq,n)}$ . Hence if we write ${\mathbb{Z}_n = \bigsqcup_{d| n} \{ k \in \mathbb{Z}_n \ | \ \gcd(k,n)= d \} }$ , then ${m_q}$ permutes the elements of each of those disjoint sets. If we call ${V_d = \{ k \in \mathbb{Z}_n \ | \ \gcd(k,n) = d \}}$ , then it is clear that ${|V_d| = \varphi(n/d)}$ , ${\varphi}$ being the Euler phi function. As a ${\langle m_q\rangle}$ -set, the action of ${m_q}$ on ${V_d}$ is isomorphic to the action of ${m_q}$ on ${\left(\frac{\mathbb{Z}}{(n/d)\mathbb{Z}}\right)^{*}}$ . Hence the number of cycles of the action of ${m_q}$ on ${V_d}$ as a permutation is equal to the number of cosets of ${\langle m_q \rangle \subset \left( \frac{\mathbb{Z}}{d \mathbb{Z}} \right) ^{*}}$ which is equal to ${\frac{\varphi(n/d)}{ \text{ord}_{n/d}(q ) }}$ .

Hence, the right side should be the sum below.

$\displaystyle \sum_{d | n }^{ } \frac{\varphi(n/d)}{ \text{ord}_{n/d}(q)} = \sum_{d | n}^{} \frac{\varphi(d)}{ \text{ord}_d(q)} .$

$\Box$

And that’s it. I have no background in algorithmic number theory, but it does look to me that the left side should be much faster to compute than the right side of the equality. If you know the current state of the art time complexities of calculating ${\text{ord}_d(q)}$ and ${\varphi(d)}$ , please let me know via email or comments or the contact box.

Somehow this formula is not mentioned on OEIS when ${q=2}$ . Only the right side is stated there. So I’m making an edit.

Why was I thinking about this, you may ask? I am reading about Cyclic codes, and the number of cyclic codes over a finite field ${\mathbb{F}_q}$ , where ${q}$ is a power of some prime is the number of factors of ${x^n-1 \in \mathbb{F}_q[x]}$ .

So how many cyclic codes exist for a given ${n}$ ? I’ll sketch the details.

It’s sufficient to ask this question only when ${(n,q)= 1}$ . The answer then hinges on how many irreducibles does ${x^n-1 \in \mathbb{F}_q[x]}$ split into, so the number of factors is ${2}$ to that power (it can be shown that all irreducibles in the factorization have multiplicity 1).

We know that in the in some field extension of ${\mathbb{F}_q}$ , the polynomial ${x^n-1}$ completely splits as follows, where ${\beta}$ is a primitive ${n}$ th root of unity.

$\displaystyle x^n-1 = (x-1) (x-\beta) ( x - \beta^{2}) \dots (x- \beta^{n-1}).$

Now for any root ${\beta^i}$ of ${x^n-1}$ , what are the conjugates of ${\beta^{i}}$ ? Because we know the structure of the Galois group, we know that the set of conjugates are ${\{ \beta^{i}, \beta ^{iq}, \beta^{iq^{2}} \dots \}}$ . Since a complete set of conjugates would give us one irreducible, the irreducibles are in bijection with the number of cycles of the multiplication map. Hence the problem reduces to simply finding the number of cycles of ${m_q:\mathbb{Z}/n\mathbb{Z} \rightarrow \mathbb{Z}/n\mathbb{Z}}$ .