A cute application of the Burnside’s lemma

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}}.

See you next time!

Advertisements

Infinite parts of zero natural density

Welcome again to my blog. Although, I do concede that looking at the frequency of my posts and the lack of readership, it is my blog that welcomes me.

Today we are going to talk about a very counter-intuitive construction. I credit discovery of this construction to my friend Yash Singh, who came up with it during a conversation over the phone. It’s most certainly possible though that someone came up with this before.

So we’re going to talk about partitioning the set of natural numbers in a counter-intuitive manner. Suppose {\mathbb{N}=\{ 0,1,2\dots\}} is the set of all natural numbers. The task is to partition this set into infinitely many parts, each part containing infinitely many elements, and each part having a natural density zero.

Hence, this most certainly proves that natural density cannot give us a probability measure on the set of natural numbers. This can of course be proven with easier constructions (it is probably the first exercise in this topic). However, this construction takes the natural density much more further away from being a measure.

To state more formally, we are going to create sets {P_i \subset \mathbb{N}}, i = 1, 2, \dots such that {\mathbb{N}= \bigsqcup_{i \ge 1} P_i } and at the same time for each {i}, the natural density is zero, which is to say the following:

\displaystyle \limsup_{n \rightarrow \infty } \frac{| \{ 0,1,2\dots n\} \cap P_i| }{| \{ 0,1,2\dots n\}| }=0.

So the construction is the following. Consider the collection of all prime numbers {\mathbb{P}} and let {D=\bigcup_{p \in \mathbb{P}} \bigcup_{j \ge 1} \{ p^j\}}, the set of all prime powers. Note that any number in {D} is the power of at most one prime.

Define the enumeration {f:\mathbb{N}\rightarrow D} given by {f(i) =}{i}th least number in {D}”. So more formally,

\displaystyle f(i) = \begin{cases} \min \left( D\setminus \{ f(0), f(1) \dots f(i-1)\} \right) \ \ \ \ \ \hfill\text{ if } i>0 \\ 2 \hfill \text{ if } i = 0\end{cases} .

Now let {\mathbb{P}=\{ p_1, p_2, p_3 \dots\}} be the enumeration of primes in increasing order. Now just define {P_k = \{ i \ | \ f(i) \text{ is a power of } p_k \}}. So we have a partition! All that is left is to prove that the density of each partition is zero.

Take the partition {P_i} for some {i} and choose some large {n}. Let {f(n)=m}. For any {j}, how many powers of {p_j} are less than or equal to {m}? It’s clearly {\lfloor \log_{p_j}(m)\rfloor = \lfloor \frac{\log(m)}{\log(p_j)}\rfloor}. We conclude that

\displaystyle \frac{| P_i \cap \{ 0 , 1 \dots n\}|}{ | \{ 0,1\dots n\}|} = \frac{\lfloor \frac{\log(m)}{\log(p_i)}\rfloor}{\sum_{ p_j \le m}^{} \lfloor \frac{\log(m)}{\log(p_j)}\rfloor} \le \frac{\lfloor \frac{\log(m)}{\log(p_i}\rfloor}{\log(m) |\{ p_i\ | \ p_i \le m \}|} \le \frac{1}{| \{ p_i \ | \ p_i \le m\}|} \rightarrow 0.

And that’s it! I hope you enjoyed reading this short construction. Please let me know if you spot any errors by email or by comments. Have a good day!