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

Some holomorphic functions

Some time ago, I saw this beautiful video shared by Prof. Terrence Tao on Google plus. The video is from the youtube channel 3Blue1Brown, where you can find some very good mathematical videos.

A much appreciable component of the particular video was the visualization done to illustrate holomorphic functions. Here’s a clip from the video:
video.gif

Looking at the said video, I was inspired to make my own holomorphic function visualizer. Here are some illustrations made from my program. In the images below are visualizations of the complex plane, the blue grid is the image of the gray grid. The vertical mark on the x-axis is (1+0i).

f(z) = e^z

exp

f(z) = z^2
square

f(z) = iz
itimes

f(z) = \frac{1}{z}

inverse

f(z) = cos(z)

cos

f(z) = cos(z)                      (Again!)

cos2

An interesting thing to note here is that the perpendicularity in the lines of the grid is maintained in the image. This is a trivial consequence of the Cauchy-Riemann equations for a holomorphic function. (This fact was also mentioned in the video).

I even tried to incorporate the logarithm defined for arguments in the region -\pi <\theta <\pi  . Here’s what it looks like:

log

Of course, it behaves very badly when I try to go outside my domain.

badlog.gif

The logarithm inspires us to define our coordinates on the associated Reimann surface (or, the covering space of complex plane with the zero removed. Picture is below), instead of the 2D coordinates used in the program. The determination of which “floor” of the surface the vertex is on can be done by recording the mouse movement history. This idea could perhaps occupy me for some time in the future.

A plot of the multi-valued imaginary part of the complex logarithm function (from Wikipedia)
riema.png

Another interesting discussion is that of the animation of the zeta-function in this video. In the video, the animator makes a continuous change of the grid lines to the function values. To be technical, this sort of continuous change is a homotopy of the identity function to the given function. The animator uses a simple linear homotopy, but it doesn’t look very natural.

Here’s a discussion on StackExchange about how to do the above homotopy in such a manner that the intermediate functions are holomorphic. My initial goal with the program was to try to animate that (you can spot the reminiscent code on GitHub). It is a future goal, for now.

If you have any interesting comments, or if would like to see your favorite holomorphic function animated, or if you want a better explanation of anything said above, please comment below.

Thanks for reading.