My first book

On one rainy morning in November,
just a few days shy of your birthday,
you came to see me.

We have only known each other for several months,
but it seemed like we have been friends
for the longest time.

You were holding your favorite book in your chest,
a book that was partially soaking wet,
and then placed it in my hand.

You told me to read it.
I laughed.
You knew I couldn’t read well.

I gave it back to you.

I couldn’t remember what you said to persuade me,
it was million years ago,
but you won. I promised you to read it.

You smiled ever so beautifully,
my attempt not to smile back failed miserably.
You told me you’d come back to make sure I read it.

You never did.

I never opened the book.
I buried it deep inside my closet,
because the sight of it reminded me of you.

But I made you a promise.
It takes exactly two years, three months, and seventeen days
to finally let you go.

Today, I want you to know,
although I believe you were watching me the whole time
from up there,

that I have finally finished reading my first book.

Dyck Paths Multiplication (Part 2)

In the previous post, I introduced the notion of Dyck path and Dyck word. I also introduced the concept of tunneling in a Dyck path. We can associate to a Dyck path a permutation. I also mentioned how you can label a Dyck path (or Dyck word) using a set of letters. In this post, I will define what the multiplication map is and give some examples to illustrate this further.

Multiplication of two Dyck paths

Given two Dyck paths D_1, D_2 \in \mathcal{D}_n, we define the product of D_1 and D_2, denoted by D_1 \times D_2, as follows:

  1. Associate to D_2 a permutation \sigma \in S_{2n}.
  2. Pair the steps in D_1 based on its tunnel.
  3. For k = 1, 2, \ldots, 2n, either
    1. write u in k-th position of the word of D_1 \times D_2 if step \sigma(k)^* of D_1 has not been read before, or
    2. write d in k-th position of the word of D_1 \times D_2 if step \sigma(k)^* of D_1 has been read.
  4. Associate the resulting word to its Dyck path, this will be the path D_1 \times D_2.

It is not obvious that the product of two Dyck paths will still yield another Dyck path. Fortunately, this is the case.

Theorem: If D_1, D_2 \in \mathcal{D}_n, then D_1 \times D_2 \in \mathcal{D}_n.

Proof: The resulting word of D_1 \times D_2 will have precisely n up-steps and n down-steps since there are n tunnels in D_1. Moreover, in the first k position, k \in \{1,2,\ldots,2n\}, the number of u will never be smaller than the number of d since the only way a d in position k is produced is to have the pair of step \sigma(k) of D_1 read. Before it is read, a u must have been written at some position l < k. Hence the resulting word is a Dyck word so the associated lattice path is a Dyck path.

Let’s have a look at a couple of examples.

Example 1. Let n = 3 and D_1, D_2 \in \mathcal{D}_3 be represented by uududd and uduudd, respectively. The Dyck path D_2 is associated to

\sigma = \left(1 \enspace 6\enspace 2 \enspace 3 \enspace 5 \enspace 4\right) \in S_6

so the way we read D_1 is we read the 1st step, followed by 6th, 2nd, 3rd, 5th, and 4th steps. Here are the steps to determine D_1 \times D_2:

  1. First we pair the steps in D_1. Step 1 is paired with step 6. Step 2 is paired with step 3, and step 4 is paired with step 5.
  2. We look at step \sigma(1) = 1 of D_1. Its pair, step 6, has not been read before. Hence, step 1 of D_1 \times D_2 is u.
  3. We look at step \sigma(2) = 6 of D_1. Its pair, step 1, has been read. Hence, step 2 of D_1 \times D_2 is d.
  4. We look at step \sigma(3) = 2 of D_1. Its pair, step 3, has not been read before. Hence, step 3 of D_1 \times D_2 is u.
  5. We look at step \sigma(4) = 3 of D_1. Its pair, step 2, has been read. Hence, step 4 of D_1 \times D_2 is d.
  6. We look at step \sigma(5) = 5 of D_1. Its pair, step 4, has not been read before. Hence, step 5 of D_1 \times D_2 is u.
  7. Last, we look at step \sigma(6) = 4 of D_1. Its pair, step 5, has been read. Hence, step 6 of D_1 \times D_2 is d.
  8. The resulting Dyck word is ududud, which can then be interpreted into the Dyck path of D_1 \times D_2.

In other words,

Example 2. Let n = 4 and D_1, D_2 \in \mathcal{D}_4 be represented by uudduudd and uuududdd, respectively. The Dyck path D_2 is associated to \sigma = \left(1 \enspace 2 \enspace 3 \enspace 8 \enspace 4 \enspace 7 \enspace 6 \enspace 5\right) and the steps of D_1 is paired in this manner: step 1 with step 4, step 2 with step 3, step 5 with step 8, and step 6 with step 7. The first step of D_1 \times D_2 is u. The second step of D_1 \times D_2 is again an u since the pair of step \sigma(2) = 2 in $D_1$, which is step 3, has not been read before. The third step of D_1 \times D_2 is d since the pair of step \sigma(3) = 3, which is step 2, has been read before. Continuing this process, the remaining steps are u, d, u, d, and d. Hence,

If P, Q \in \mathcal{D}_n, we can think of this multiplication operator as a map

\begin{aligned} \mu_Q\enspace \colon \mathcal{D}_n &\longrightarrow \mathcal{D}_n,\\ P &\longmapsto P \times Q. \end{aligned}

We will see below how multiplication works in \mathcal{D}_2, \mathcal{D}_3, and \mathcal{D}_4.

Multiplication in \large\mathcal{D}_2

There are only 2 Dyck paths of semilength 2, which are given below.

Two Dyck paths of semilength 2.

It can be verified that

In other words, \mu_1(1) = 1, \mu_1(2) = 2, \mu_2(1) = 2, and \mu_2(2) = 1. We can summarise the above information in a multiplication table below. The convention for D_1 \times D_2 is D_1 is picked from the column below \times, and D_2 is picked from the row to the right of \times.

Multiplication in \mathcal{D}_2

Multiplication in \large\mathcal{D}_3

There are 5 Dyck paths of semilength 3, which are given below.

Five Dyck paths of semilength 3.

The multiplication table is given below.

Multiplication in \mathcal{D}_3

Multiplication in \large\mathcal{D}_4

There are 14 Dyck paths of semilength 4.

Fourteen Dyck paths of semilength 4.

Here is the multiplication table.

Multiplication in \mathcal{D}_4

Further observations

Have a look at any multiplication table I provided above. If you look at any column, you will find every entry in that column to be different. To say it more precisely, given a Dyck path Q \in \mathcal{D}_n where n = 2, 3, 4, if P_1, P_2 \in \mathcal{D}_n with P_1 \neq P_2, then \mu_Q(P_1) \neq \mu_Q(P_2). In other words, \mu_Q is actually a bijection!

To come to think of it, it is not entirely clear that the multiplication map is well-defined (the proof is not as simple as we would like, as you see above), let alone that it is a bijection! If it is indeed a bijection, given any n, we can generate C_n bijections at the same time!

Conjecture. For any Q \in \mathcal{D}_n, the map \mu_Q is a bijection.

In the next post, I will give an explicit algorithm to tackle the following problem: given Q, R \in \mathcal{D}_n, how do you find P \in \mathcal{D}_n such that P \times Q = R? Note that giving such an algorithm doesn’t necessarily mean that it is a bijection. We need to say more to be entirely sure that it is a bijection.

There are several other nice observations about this multiplication, just by looking at the table above. But I think it deserves to be put as a single post, later 🙂

Dyck Paths Multiplication (Part 1)

In this series of posts, I will try to introduce a family of mappings between Dyck paths of the same length. The map itself can be thought of as multiplication of two Dyck paths. In this first part, I will lay out all the ingredients needed in order for us to define properly what it means here to multiply two Dyck paths. In the second part, I will define the multiplication map and give some concrete examples. In the third part, I will give a map to reverse the multiplication map we will see in the second post. This is an attempt to show that the family of mappings is indeed a family of bijections between Dyck paths. In the last part, I will highlight several interesting properties about this multiplication map: I have a proof for some observations, but mostly I will be giving some open questions.

Dyck paths and Dyck words

A Dyck path D of length 2n (or of semilength n) is a lattice path which starts at (0,0) and ends at (n,n) which does not cross above the diagonal line y = x (but if it touches the line, it’s okay).

Another interpretation for D, one which I will use throughout this series of posts, is as a path from (0,0) that ends at (2n,0) which consists of a series of up-steps (1,1) and down-steps (1,-1) such that it never goes below the x-axis.

Let \mathcal{D}_n be the set of all Dyck paths of length 2n. It is well-known that

\begin{aligned}\left|\mathcal{D}_n\right| = C_n = \frac{1}{n+1} \binom{2n}{n} \end{aligned},

the nth Catalan number. This gives a combinatorial interpretation of the Catalan numbers in terms of Dyck paths.

Now, given a Dyck path, we can associate to it its Dyck word, which is just the way we read the path from left to right, consisting of a string of us (for up-steps) and ds (for down-steps). Denote by \mathcal{D}_n^\dagger the set of all Dyck words of length 2n. Throughout this post, the terms Dyck path and Dyck word will be interchangeable, unless distinction is required. In other words, most of the times we will make no distinction between the set \mathcal{D}_n and \mathcal{D}_n^\dagger.

Below is an example of a Dyck path in \mathcal{D}_4. We can encode this Dyck path into uuduuddd.


A Dyck path in \mathcal{D}_4 with Dyck word uuduuddd

There are only C_2 = 2 Dyck paths of semilength 2, which are


Below we see the Dyck paths of semilength 4:


which, as you can see, are C_4 = 14 in total.

Note that if a Dyck word is given, for any k \in \{1,2,\ldots,2n\}, in the first k subword, the number of u must not exceed the number of d, for otherwise the Dyck path will cross below the x-axis. It is also obvious that the number of u and d in any Dyck word of length 2n must both be equal to n.

Dyck path tunneling

Given a Dyck path D \in \mathcal{D}_n, define a tunnel in D to be the horizontal segment between two lattice points of D that intersects D only in these two points and stays always below D. If D \in \mathcal{D}_n, then D has exactly n tunnels and each tunnel can be associated with a pair of (u,d) such that the step and the d step are connected by a tunnel. In the Dyck path in Figure 1 above, we have 4 tunnels: those connecting (0,0) with (8,0), (1,1) with (3,1), (3,1) with (7,1), and (4,2) with (6,2). See all the tunnels in red dashed line below.

Tunnels in a Dyck path

Given a Dyck path D \in \mathcal{D}_n, a step j is called the conjugate of step i if there is a tunnel connecting step i and step j of D. If step j is the conjugate of step i, we write j = i^*. Note that the conjugation map ^* is an involution, i.e. (i^*)^* = i for all 1 \le i \le 2n. In the Dyck path above, for example, 1^* = 8, 2^* = 3, 4^* = 7, and 5^* = 6.

Associating to a Dyck path a permutation

Let S_n be the set of permutation of n elements in the set \{1,2,\ldots,n\}. Given a Dyck path D \in \mathcal{D}_n, we can associate to it a permutation \sigma \in S_{2n} via the following rules:

  1. Read the Dyck word D^\dagger of D from left to right.
  2. If the k-th u from this Dyck word falls in position m, then define \sigma(m) = k, where k = 1, 2, \ldots, n.
  3. If the k-th d from this Dyck word falls in position m, then define \sigma(m) = 2n + 1 - k, where k = 1, 2, \ldots, n.

This association gives an injective map from \mathcal{D}_n to S_{2n}. To give an illustration, the Dyck path in Figure 1 above corresponds to

\sigma = \left(1 \enspace 2 \enspace 8 \enspace 3 \enspace 4 \enspace 7 \enspace 6 \enspace 5 \right).

Now observe that for any Dyck path D that is associated with \sigma \in S_{2n}, it is necessary that \sigma(1) = 1 (resp. \sigma(2n) = n+1) because the first (resp. last) step in any Dyck path is always an up-step (resp. a down-step).

Labeling a Dyck path

Let a Dyck path D \in \mathcal{D}_n be given. We can associate to it a string of length 2n consisting of letters x_1, x_2, \ldots, x_n, each appearing exactly twice, via the following rules:

  1. Pair the steps i and j so that they are connected by a tunnel.
  2. Label the i-th and j-th position of this string with one out of n letters x_1, x_2, \ldots, x_n.
  3. Once a letter has been used, it cannot be used anymore.

It is important to note that the order for choosing the letters to use does not matter. For example, the Dyck path in Figure 1 corresponds to x_1x_2x_2x_3x_4x_4x_3x_1, but it can also correspond to x_3x_4x_4x_2x_1x_1x_2x_3. What does matter is the position of the letters.

Now that we have all the stuff we need to know, I will define the multiplication map in the next post.

Super Catalan Numbers

In 1874, a French and Belgian mathematician EugĂšne Catalan introduced the numbers

S(m,n) \equiv \dfrac{(2m)!(2n)!}{m!n!(m+n)!},

now better known as super Catalan numbers, and stated that the numbers are integers. The entire text of his note in French, an item in a column called Questions which appeared in Nouvelles Annales de Mathématiques Volume 13, is as follows:

a, b Ă©tant deux nombres entiers quelconques, la fraction

\dfrac{(a+1)(a+2)\ldots 2a (b+1)(b+2)\ldots 2b}{1 \cdot 2 \cdot \ldots \cdot (a+b)}

est Ă©gale Ă  un nombre entier.

Unfortunately, there is also another sequence of numbers which goes by the name of super Catalan numbers too, called the Schröder-Hipparchus numbers. It makes the naming a bit ambiguous.

Nevertheless, S(m,n) can be viewed as a generalization of the famous Catalan numbers

\begin{aligned} \mathcal{C}_n = \frac{1}{n+1}\binom{2n}{n},\end{aligned}

because S(1,n) = 2\mathcal{C}_n. You can see the Catalan sequence here in Online Encyclopedia of Integer Sequences (OEIS).

You can prove that S(m,n) is always an integer for any non-negative integers m and n by observing that S(m,n) satisfies

4S(m,n) = S(m+1,n) + S(m,n+1),

and that S(m,0) is the central binomial coefficient \displaystyle\binom{2m}{m} \in \mathbb{Z}, where we can proceed by induction on n. Except for S(0,0) = 1, S(m,n) is always even so sometimes \dfrac{1}{2}S(m,n) is considered.

Unlike the Catalan numbers which so far have more than 200 combinatorial interpretations (Richard Stanley gave 66 interpretations in his book Enumerative Combinatorics 2, and he added some more as an addendum), you might be surprised to know that up to date, there is no known combinatorial interpretation of S(m,n). However, there are some combinatorial interpretations of the specific case of super Catalan numbers in terms of pairs of Dyck paths with restricted height (see a paper by Gessel, for instance), cubic plane trees (see a paper by Pippenger and Schleich), or restricted lattice paths (see this paper by Chen and Wang). The first two papers give a combinatorial interpretation for \dfrac{1}{2}S(m,2) and the last one gives a combinatorial interpretation for S(m,m+s) where 0 \le s \le 4.

There are also weighted interpretations of super Catalan numbers in terms of Krawtchouk polynomials in this paper by Georgiadis, Munemasa, and Tanaka. The most recent work on super Catalan numbers is due to Allen and Gheorghiciuc, who provided a weighted interpretation in terms of positive and negative 2-Motzkin paths in their paper here.

My current research is closely connected to super Catalan numbers, but not in a combinatorial flavor. However, I was curious why people haven’t been able to interpret these seemingly harmless numbers as a counting problem. To do that, I decided to do a bit of detour: I wandered around in the realm of combinatorics. Since one of the interpretations of the Catalan numbers is in terms of Dyck paths, I decided to start with Dyck paths.

To those who are not familiar, a Dyck path D \in \mathcal{D}_n of length 2n is a lattice path, starting at (0,0) and ending at (2n,0), that consists of up-steps (1,1) and down-steps (1,-1) and never goes below the x-axis. You could also think of Dyck paths of length 2n as such paths starting from (0,0) to (n,n) that lies below (but may touch) the diagonal line y = x. The number of Dyck paths of length 2n is the nth Catalan number \mathcal{C}_n. You can see some illustrations here.

It thus makes sense to find a combinatorial interpretation of super Catalan numbers in terms of Dyck paths, hoping that the description of S(m,n) relies solely on Dyck paths, only perhaps in more intricate detail. In order to come up with an interpretation, all I need to do is to find a very specific bijection between two Dyck paths that should work in general. That turns out to be a very difficult thing to do. I played with many bijections but none seemed to work. I ended up finding a curious family of bijections between Dyck paths of the same length, though. But more on that later, in another post.

So the moral of the story is you can wish to solve something, but you may end up getting something else. If you are lucky (or unlucky, depends on how you interpret it), that ‘something else’ might just be another question waiting to be discovered 😛

Intriguing Product of Cosines

Just recently I came across a question on Quora Indonesia (so it’s in Indonesian, which is obvious) about simplifying this expression:

\begin{aligned}\prod_{a=1}^{2015} \prod_{b=1}^{2015} \left(1 + \exp\left(\frac{2\pi i ab}{2015}\right)\right).\end{aligned}

I already wrote my answer there, in Indonesian. That is not as simple as I would expect, but it definitely is interesting enough to force me to write this post.

I was thinking, what if I replace that 2015 by a general positive integer n? In other words, what can we say about

\begin{aligned} \alpha(n) = \prod_{a=1}^{n} \prod_{b=1}^{n} \left(1 + \exp\left(\frac{2\pi i ab}{n}\right)\right)?\end{aligned}

As in what I wrote as an answer in that Quora post, let’s denote 1 + \exp\left(\dfrac{2\pi i ab}{n}\right) by \Lambda(a,b). Every pair of integers (a,b) \in \{1,2,\ldots,n\}^2 will be associated with a complex number \Lambda(a,b).

First, it is quite trivial if n = 1 or n is even. If n = 1, the above expression just boils down to 2. Now, if n = 2k for some k, then \Lambda(1,k) = 0, so the whole product will just be 0. We shall assume from this point that n is an odd number greater than 1.

Now, if either a or b is n, then \Lambda(a,b) = 2. Since there are 2n-1 pairs of (a,b) where at least one of a or b is n, then we can say that

\begin{aligned} \alpha(n) = 2^{2n-1} \prod_{a=1}^{n-1} \prod_{b=1}^{n-1} \Lambda(a,b).\end{aligned}

It is the last product that we should be interested at. Before anything, we shall make a couple of observations about the symmetry of \Lambda(a,b).

  1. For any a and b, \Lambda(a,b) = \Lambda(n-a,n-b), and
  2. For any a, \Lambda(a,b)\Lambda(a,n-b) = 4\cos^2\left(\dfrac{\pi ab}{n}\right) for any b.

These two observations enable us to write

\begin{aligned} \alpha(n) &= 2^{2n-1} \prod_{a=1}^{\frac{n-1}{2}} \left(\prod_{b=1}^{n-1} \Lambda(a,b)\right)^2 \\ &=  2^{2n-1} \prod_{a=1}^{\frac{n-1}{2}} \left(\prod_{b=1}^{\frac{n-1}{2}} 4\cos^2\left(\frac{\pi ab}{n}\right)\right)^2\\ &= 2^{2n-1} \prod_{a=1}^{\frac{n-1}{2}} \left(\prod_{b=1}^{\frac{n-1}{2}} 2\cos\left(\frac{\pi ab}{n}\right)\right)^4\\ &= 2^{2n-1} \times 2^{(n-1)^2}\prod_{a=1}^{\frac{n-1}{2}} \left(\prod_{b=1}^{\frac{n-1}{2}} \cos\left(\frac{\pi ab}{n}\right)\right)^4 \\ &= 2^{n^2} \prod_{a=1}^{\frac{n-1}{2}} \left(\prod_{b=1}^{\frac{n-1}{2}} \cos\left(\frac{\pi ab}{n}\right)\right)^4. \end{aligned}

By now I hope it is already clear why I wrote ‘product of cosines’ in the title. \alpha(n) is, after all, product of cosines. For simplicity, let us define, for every a where 1 \le a \le \dfrac{n-1}{2},

\begin{aligned}\mathcal{C}(a) = \prod_{b=1}^{\frac{n-1}{2}} \cos\left(\frac{\pi ab}{n}\right). \end{aligned}

Our function \alpha(n) is therefore

\begin{aligned} \alpha(n) = 2^{n^2} \prod_{a=1}^{\frac{n-1}{2}} \mathcal{C}(a)^4. \end{aligned}

Now, an observation can be made if n is prime. Define

\begin{aligned}\mathcal{S}(a) = \prod_{b=1}^{\frac{n-1}{2}} \sin\left(\frac{\pi ab}{n}\right), \end{aligned}

and observe that

\begin{aligned}\mathcal{C}(a)\mathcal{S}(a) &= \prod_{b=1}^{\frac{n-1}{2}} \cos\left(\frac{\pi ab}{n}\right)\sin\left(\frac{\pi ab}{n}\right) \\ &= \prod_{b=1}^{\frac{n-1}{2}} \frac{1}{2}\sin\left(\frac{2\pi ab}{n}\right) \\ &= \frac{1}{2^{\frac{n-1}{2}}} \times  \sin\left(\frac{2\pi a}{n}\right) \times \sin\left(\frac{4\pi a}{n}\right)\times \ldots \times \sin\left(\frac{(n-3)\pi a}{n}\right) \times \sin\left(\frac{(n-1)\pi a}{n}\right) \\ &= \frac{1}{2^{\frac{n-1}{2}}}\times\sin\left(\frac{\pi a}{n}\right)\times\sin\left(\frac{2\pi a}{n}\right)\times\sin\left(\frac{3\pi a}{n}\right)\times\sin\left(\frac{(n-1)\pi a}{2n}\right) \\ &= \frac{1}{2^{\frac{n-1}{2}}}\mathcal{S}(a).\end{aligned}

We then observe that \mathcal{S}(a) \neq 0, since none of \dfrac{\pi ab}{n} will be a multiple of \pi if n is prime and both a and b are less than n. Hence,

\begin{aligned} \mathcal{C}(a) = \frac{1}{2^{\frac{n-1}{2}}}\end{aligned}

for every 1 \le a \le \dfrac{n-1}{2}, and thus for n prime we conclude that

\begin{aligned}\alpha(n) = 2^{n^2} \times \left(\frac{1}{2^{\frac{n-1}{2}\times 4}}\right)^{\frac{n-1}{2}} = \frac{2^{n^2}}{2^{(n-1)^2}} = 2^{2n-1}.\end{aligned}

Well, in fact, this is what I initially thought the answer of that Quora question was going to be after trying some small odd integers n to replace 2015. Until I realised that it is going to be more complicated if n is composite. In this case, there will be 1 \le a,b \le \dfrac{n-1}{2} such that \dfrac{\pi ab}{n} is a multiple of \pi, and thus implying \mathcal{S}(a) = 0. In this case, we cannot use the same argument above to find \mathcal{C}(a): we need to think of another way.

At this stage, I really should try to work on the case of n = p_1^{k_1}p_2^{k_2}\ldots p_m^{k_m} but I think it will be much, much more complicated. So, at least for the time being, I will give you a case where n = pq where p and q are two distinct odd primes.

The result above regarding \mathcal{C}(a) can still be salvaged, though. It does still work for those 1 \le a \le \dfrac{n-1}{2} such that \gcd(a,n) = 1. So we need to know: how many such a are there? We can use the Principle of Inclusion-Exclusion to find out.

So, out of the \dfrac{n-1}{2} first positive integers, there will be \left\lfloor\dfrac{n-1}{2p}\right\rfloor numbers that are divisible by p and \left\lfloor\dfrac{n-1}{2q}\right\rfloor numbers that are divisible by q. There will be no number that is divisible by both p and q in the first \dfrac{n-1}{2} positive integers. Hence, there are

\dfrac{n-1}{2} - \left\lfloor\dfrac{n-1}{2p}\right\rfloor - \left\lfloor\dfrac{n-1}{2q}\right\rfloor

such a that are relatively prime to n = pq, where \mathcal{C}(a) = \dfrac{1}{2^{\frac{n-1}{2}}}.

Now, how about those that share the common factor p or q? Let’s have a look at those integers 1 \le a \le \dfrac{n-1}{2} where \gcd(a,n) = p. We can write a = pu for some integer u. Now, in the expansion of

\begin{aligned} \mathcal{C}(a) = \prod_{b=1}^{\frac{n-1}{2}} \cos\left(\frac{\pi kb}{q}\right),\end{aligned}

there will be exactly \left\lfloor\dfrac{n-1}{2q}\right\rfloor terms that are either 1 or -1, coming from those b that are multiples of q. How do we compute the product of other \dfrac{n-1}{2} - \left\lfloor\dfrac{n-1}{2q}\right\rfloor terms?

Well, there’s a trick that we can use. We need to split the product into smaller products.

\begin{aligned}\mathcal{C}(a) = \pm\prod_{b=1}^{\frac{q-1}{2}}\cos\left(\frac{\pi kb}{q}\right)\times\prod_{b=\frac{q+1}{2}}^{q-1}\cos\left(\frac{\pi kb}{q}\right)\times\prod_{b=q+1}^{\frac{3q-1}{2}}\cos\left(\frac{\pi kb}{q}\right)\times\cdots\times\prod_{b=\frac{n-q}{2}+1}^{\frac{n-1}{2}}\cos\left(\frac{\pi kb}{q}\right).\end{aligned}

The plus and minus sign there is due to the product of \cos(jk\pi) for all 1 \le j \le \left\lfloor\dfrac{n-1}{2q}\right\rfloor. It won’t matter which one is the actual sign anyway, since we are interested in \mathcal{C}(a)^4.

Now, have a look at the first product. Since 1 \le b \le \dfrac{q-1}{2} and k < q, none of the \dfrac{\pi kb}{q} will be an integer multiple of \pi. Therefore, we can apply the argument involving the product \mathcal{C}(a) and \mathcal{S}(a) as above to deduce that the first product must be \dfrac{1}{2^{\frac{q-1}{2}}}.

The rest of the products can be viewed exactly as the first product after you apply a suitable trigonometric identity first. For example, in the second product, you need to use \cos(\pi k - \theta) = (-1)^k \cos\theta.

We can then conclude that the product in every group will be \dfrac{1}{2^{\frac{q-1}{2}}}. Since there are \dfrac{2}{q-1}\left(\dfrac{n-1}{2} - \left\lfloor\dfrac{n-1}{2q}\right\rfloor\right) smaller products altogether, we conclude that for 1 \le a \le \dfrac{n-1}{2} such that \gcd(a,n) = p,

\begin{aligned} \mathcal{C}(a) = \left(\frac{1}{2^{\frac{q-1}{2}}}\right)^{\frac{2}{q-1}\left(\frac{n-1}{2} - \left\lfloor\frac{n-1}{2q}\right\rfloor\right)} = \frac{1}{2^{\frac{n-1}{2} - \left\lfloor\frac{n-1}{2q}\right\rfloor}}. \end{aligned}

Using the same reasoning, for 1 \le a \le \dfrac{n-1}{2} such that \gcd(a,n) = q, we have that

\begin{aligned} \mathcal{C}(a) = \left(\frac{1}{2^{\frac{p-1}{2}}}\right)^{\frac{2}{p-1}\left(\frac{n-1}{2} - \left\lfloor\frac{n-1}{2p}\right\rfloor\right)} = \frac{1}{2^{\frac{n-1}{2} - \left\lfloor\frac{n-1}{2p}\right\rfloor}}. \end{aligned}

We are now ready to compute \alpha(n)! From the first \dfrac{n-1}{2} positive integers, there are exactly \dfrac{n-1}{2} - \left\lfloor\dfrac{n-1}{2p}\right\rfloor - \left\lfloor\dfrac{n-1}{2q}\right\rfloor integers whose \mathcal{C}(a) = \dfrac{1}{2^{\frac{n-1}{2}}}. There are \left\lfloor\dfrac{n-1}{2p}\right\rfloor integers whose \mathcal{C}(a) = \dfrac{1}{2^{\frac{n-1}{2} - \left\lfloor\frac{n-1}{2q}\right\rfloor}}, and finally \left\lfloor\dfrac{n-1}{2q}\right\rfloor integers whose \mathcal{C}(a) = \dfrac{1}{2^{\frac{n-1}{2} - \left\lfloor\frac{n-1}{2p}\right\rfloor}}.


\begin{aligned} \alpha(n) &= 2^{n^2}\prod_{a=1}^{\frac{n-1}{2}} \mathcal{C}(a)^4 \\ &= 2^{n^2} \left(\dfrac{1}{2^{4 \times \frac{n-1}{2}}}\right)^{\dfrac{n-1}{2} - \left\lfloor\dfrac{n-1}{2p}\right\rfloor - \left\lfloor\dfrac{n-1}{2q}\right\rfloor} \left(\frac{1}{2^{4 \times \left(\frac{n-1}{2} - \left\lfloor\frac{n-1}{2q}\right\rfloor\right)}}\right)^{\left\lfloor\dfrac{n-1}{2p}\right\rfloor} \left(\frac{1}{2^{4 \times \left(\frac{n-1}{2} - \left\lfloor\frac{n-1}{2p}\right\rfloor\right)}}\right)^{\left\lfloor\dfrac{n-1}{2q}\right\rfloor} \\ &= 2^{2n-1+8\left\lfloor\dfrac{n-1}{2p}\right\rfloor\left\lfloor\dfrac{n-1}{2q}\right\rfloor}.\end{aligned}

You already see how complicated it is just in the case where n is a product of two distinct primes. In the original Quora question, n = 2015 = 5 \times 13 \times 31, so there are more cases to consider: those 1 \le a \le \dfrac{n-1}{2} = 1007 such that \gcd(a,2015) = 1, 5, 13, 31, 65, 155, 403. However, the idea stays the same. In this case, \alpha(2015) = 2^{13725}.

I might soon add the case where n = p^k for some k. Hopefully I will have time and energy to do the general case 😛

By the way, I am quite certain there is a more elegant way to find \alpha(n). You know, \Lambda(a,b) is too simple for the product to be this complicated. But maybe I am wrong…

The Power of Simple Things

Well it’s been ages since the last time I updated this blog. To be honest, I did want to write something, only if I haven’t been too busy sleeping. I am currently just doing research, reading literatures, and singing in the choir. Apparently doing research is really time-consuming, since I need to read many literatures and understand them before proceeding with the real research. Also the material I am currently studying is different with what I learned back in ITB, so I need to give more of my time to do the self-learning.

Speaking about reading literatures, I am currently self-learning one particular structure in mathematics called semisimple algebra. I won’t bother you with all the details, but it is an interesting object to study with, though. In short, an algebra A is a ring which is also a vector space (so we can multiply vector with vector as well as scalar with vector). Now consider a module U over A. Modules are basically just like vector space, where now the scalar set is no longer a field but a ring$. We call U as an A-module. Now U is called simple if its only submodules are the zero submodule and itself. We call U semisimple if U can be written as a direct sum of simple modules. Finally, we called an algebra A to be semisimple if every non-zero module over A is semisimple. What I am currently investigating is the special case when A is actually a group algebra \mathbb{C}G of \mathbb{C}-linear combination of elements in G, where G is any finite group.

Phew. That was long enough. Algebra is not really my forte, though. (I do miss integral and its friends!!) However, after spending so much time reading this particular thing, I admit I become more fascinated with algebra. To get the idea of this subject, I must have a strong understanding about group theory, but in a fancy level. At first I was quite skeptical about the idea of ‘fancy’ group theory. I didn’t have much experience dealing with groups. I did once learn it back then in my Algebra course in ITB, but what could be made complicated from just a set equipped with one single well-defined operation satisfying associativity, existence of the identity element, and existence of inverse elements?

Turns out I was wrong. Like, totally wrong. Up until now I am still amazed by how rich group theory is. I read so many new things I haven’t even heard before, like derived groups, composition series, chief series, solvability; not to mention things I have already heard but I have no idea what they are, e.g. Sylow theorems, general linear groups, group action, representation theory (which has a deep connection with semisimple algebras and module theory). That is just group theory. I haven’t talked about another more complex structures which I believe to possess a richer theory.

Before you stop reading because of what you just read, bear with me a little bit longer. What I really want to say from that rather abstract concepts which I believe not all of you would bother to understand is that we shouldn’t underestimate the power of simple things. Simple things can turn out to be not-so-simple and in fact they can probably involve a very serious and deeper understanding to master. Simple things are also the basic building blocks to grasp the more complicated ideas, so speaking that way, they are important.

Why do I use such a nonconcrete analogue just to explain that? Well probably because I do feel impressed with all this learning process and I don’t want to wait any longer to write something LOL. Hopefully it won’t take too long time for me to update this blog after this post. Anyway, thanks for reading!

Tentang Kedewasaan

Momen ulang tahun kemarin membuat saya berpikir cukup panjang mengenai kedewasaan. Saya sudah 22 tahun sekarang dan seperti harapan-harapan pada umumnya, saya diharapkan untuk makin dewasa. Nah, ini yang membuat saya berpikir. Kedewasaan itu apa ya? Apa yang saya lakukan setahun kemarin belum dewasa? Kalau begitu, kadar kedewasaan itu apa?

Jujur, saya tidak tahu apa itu kedewasaan. Bersikap seperti orang dewasa? Sikap yang bagaimana? Orang dewasa juga bisa berbuat salah. Lha, banyak kasus kriminal kan juga rata-rata pelakunya orang dewasa. Jelas kalau berbuat kriminal itu bukan sesuatu yang baik, jadi tidak mungkin dijadikan teladan. Lalu sikap yang seperti apa? Ini membuat saya bingung.

Saya cukup lama merenung sampai akhirnya sampai di suatu kesimpulan. Saya tidak perlu capek-capek memikirkan apa itu kedewasaan. Saya tidak perlu tahu juga apa kadar kedewasaan, karena itu bukan sesuatu yang saklek. Yang saya lakukan adalah berusaha menjalani hari ini lebih baik daripada kemarin. No thinking too much about the future. Ya merencanakan masa depan itu boleh, bagus malah. Tapi terlalu terbenam dalamnya, saya rasa tidak baik. Saya berprinsip, lakukan pekerjaan hari ini dengan baik dari kemarin. Kesusahan sehari cukup untuk sehari kok, jadi sebaiknya tidak dibawa-bawa lagi besoknya. Terdengar mudah, namun sulit. Kenapa? Karena.. You know, human. They like to overcomplicate things. Saya pun begitu. Ini yang jadi salah satu resolusi saya untuk tahun ini.

Kalau dipikir-pikir lagi.. Saya malah harusnya meniru anak kecil. Mereka selalu bermain, penuh rasa ingin tahu, dan iman mereka sangatlah murni. Tuhan saja berkata kalau Kerajaan Allah itu milik anak-anak kecil (Markus 10:13-16). Ya, kadang dalam beberapa hal, menjadi ‘dewasa’ itu berarti menjadi seperti anak kecil. Membingungkan, bukan? Makanya saya putuskan tidak usah dipikir. Cukup jalani saja hidup seperti hari ini adalah hari terakhir kita hidup. Nah, menjalaninya tentu tidak asal-asalan. Jalani seperti yang Tuhan kehendaki. Sepertinya itu yang memang harus kita lakukan, bukan?

Nah, kalau sekarang saya diminta mendefinisikan kedewasaan, saya akan jawab begini. Kedewasaan adalah suatu momen hidup dimana kita bisa menikmati Tuhan seutuhnya. Menjadi dewasa tidak sama dengan menjadi tua. Semakin tua tidak menjamin makin dewasa, meskipun semakin kita dewasa, pastilah kita makin tua 😛

Have a nice day, all!