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…

Covering Rational Numbers with Arbitrarily Small Intervals

Take any arbitrary \epsilon > 0. There is a collection of intervals \{I_n\}_{n \in \mathbb{N}} so that

\begin{aligned}\mathbb{Q} \subseteq \bigcup_{n = 1}^{\infty} I_n\end{aligned}

and the sum of their length never exceeds \epsilon.

To see this, for any \epsilon > 0, take any positive sequence (a_n) converging to \epsilon. For example, a_n = \dfrac{\epsilon}{2^n} will do. Since rational numbers are countably many, we can cover every rational number r_n with open interval I_n centered at r_n with \ell(I_n) = a_n.

This is used to show that rational numbers, in the universe of real numbers, have measure zero, since we can control how small our \epsilon is going to be.

Hampir Tidak Ada Bilangan Rasional, Tapi…

Sebelum mulai, saya mau minta kalian pilih satu buah bilangan apa saja yang terletak di antara 0 dan 1 (ini berarti 0 dan 1 tidak boleh dipilih ya). Kalau sudah, diingat-ingat saja. Gak akan saya apa-apain kok.

Kenapa saya minta seperti itu? Kalau saya minta sebutkan satu bilangan di antara 0 dan 1, pasti kebanyakan akan jawab \frac{1}{2}. Mungkin ada beberapa yang kreatif jawabnya \frac{5}{6}. Lebih kreatif lagi kalau jawabnya \frac{354566}{583948}. Tapi jauh lebih kreatif orang yang jawab \frac{1}{2}\sqrt{2} atau \frac{\pi}{4} atau \log(2). Nah, seberapa kreatifkah kalian? 😛

Faktanya, hampir setiap orang yang diminta untuk berikan satu angka di antara 0 dan 1, pasti akan memberikan jawaban berupa bilangan rasional. Mungkin karena bilangan-bilangan itu yang dekat dengan mereka. Mungkin cuma anak matematika yang akan jawab \frac{\pi}{4} atau \ln(2), karena mereka lebih sering berurusan dengan bilangan-bilangan semacam itu ketimbang anak-anak lainnya.

Sekarang, saya mau berikan suatu fakta yang mungkin agak ironis: di kumpulan bilangan real, hampir tidak ada bilangan rasional. Artinya, jumlah bilangan irasional jauh, jauh, jauh lebih banyak daripada bilangan rasional. Lebih mengejutkan lagi, dengan menganggap semua bilangan di antara 0 dan 1 terdistribusi secara merata, kalau kita harus mengambil satu angka dari antara 0 dan 1, katakanlah a \in (0,1), maka peluang bahwa a bilangan rasional adalah 0. Dengan kata lain, peluang bahwa a bilangan irasional adalah 1.

Buktinya tidaklah sederhana. Bahkan tampak aneh dan tidak wajar ya? Jelas-jelas dari interval (0,1) bilangan rasional ada banyak. Ambil saja \frac{1}{2}, \frac{1}{4}, \frac{1}{6}, \ldots yang belum lagi ditambah \frac{1}{3}, \frac{1}{5}, \frac{1}{7}, \ldots. Itu baru yang bentuknya \frac{1}{n}, belum ditambah dengan yang bentuknya lebih ‘tidak karuan’ seperti \frac{11}{5476} dan lain sebagainya. Mau ditulis semua juga tidak mungkin saking banyaknya, kan? Bagaimana mungkin kalau kita mengambil satu bilangan dari antara 0 dan 1, peluang terambil bilangan rasional adalah 0?

Penjelasan di bawah ini sudah masuk ke ranah yang lebih matematis. Coba dibaca saja, tidak harus terlalu dipahami. Buat yang memang tidak bisa paham, percaya sajalah :D. Mungkin bisa langsung lompat ke dua paragraf terakhir.

Untuk menjelaskan ini, kita butuh suatu konsep yang disebut ukuran (measure). Secara kasar, namanya juga ukuran, pasti ia dibutuhkan untuk memberikan gambaran seberapa besar suatu objek. Nah dalam konteks ini, predikat ukuran melekat pada himpunan. Jadi, kita bisa mengukur seberapa besar suatu himpunan.

Secara intuitif, kalau kita punya selang I = (0,1), ukuran himpunan ini adalah panjangnya kan? Jadi ukurannya 1. Sekarang, kalau kita punya persegi panjang di bidang berdimensi dua R = \{(x,y) \in \mathbb{R}^2 \mid 0 \le x \le 2, 0 \le y \le 3\}, ukuran himpunan ini secara intuitif adalah luasnya, yaitu 6. Kalau kita punya kubus di ruang berdimensi tiga Q = \{(x,y,z) \in \mathbb{R}^3 \mid 0 \le x \le 2, 0 \le y \le 2, 0 \le z \le 2\}, ukuran himpunan ini secara intuitif adalah volumenya, yaitu 8. Ukuran memang dipakai untuk memperumum konsep panjang (di ruang berdimensi satu), luas (di ruang berdimensi dua), dan volume (di ruang berdimensi tiga). Memperumum di sini maksudnya apa? Maksudnya adalah kalau kita ingin bekerja di ruang berdimensi n, kita tetap bisa punya suatu alat untuk mengukur seberapa besar suatu himpunan.

Ada banyak jenis ukuran, namun yang populer salah satunya adalah ukuran Lebesgue. Sekarang, sedikit lebih formal. Misalkan m adalah ukuran Lebesgue, maka m adalah suatu pemetaan yang membawa himpunan tak kosong ke suatu bilangan real non-negatif yang diperluas \mathbb{R}_+^{\star} = \mathbb{R} \cup \{\infty\}, yang kelak dinamakan ukuran himpunan ini. Dari penjelasan sebelumnya, kita memperbolehkan ukuran suatu himpunan tak berhingga.

Sekarang, mari bicara dalam domain bilangan real \mathbb{R} saja. Jika I = (a,b), definisikan m(I) = b-a. Sekarang, bagaimana untuk kelas himpunan yang lebih besar? Sekarang, coba pandang himpunan (0,1) \cup (2,3). Masuk akal kan kalau kita mendefinisikan m((0,1) \cup (2,3)) = m((0,1)) + m((2,3)) = 1 + 1 = 2? Ini sudah membuat lebih banyak himpunan bisa diukur. Sekarang, berhingga banyaknya himpunan-himpunan yang saling disjoin (yaitu tidak memiliki irisan) bisa dihitung ukurannya.

Secara umum, jika a_1 < b_1 < a_2 < b_2 < \ldots < a_n < b_n, maka

m\left(\displaystyle\bigcup_{i = 1}^n (a_i, b_i)\right) = \displaystyle\sum_{i = 1}^n m((a_i, b_i)).

Bahkan, ini kita bisa perumum lagi untuk kasus terhitung banyaknya himpunan-himpunan yang saling disjoin, yaitu jika a_1 < b_1 < a_2 < b_2 < \ldots < a_n < b_n < \ldots, maka

m\left(\displaystyle\bigcup_{i = 1}^{\infty} (a_i, b_i)\right) = \displaystyle\sum_{i = 1}^{\infty} m((a_i, b_i)).

Ekspresi terakhir tidaklah masalah karena ukuran suatu himpunan boleh tak berhingga.

Sekarang, coba kita formalkan. Jika E suatu himpunan terukur (yaitu yang ukurannya terdefinisi dengan baik), maka

  1. m(E) \ge 0.
  2. Jika E_1, E_2, \ldots adalah subhimpunan dari E yang saling disjoin, maka m\left(\displaystyle\bigcup_{i = 1}^{\infty} E_i\right) = \displaystyle\sum_{i = 1}^{\infty} m(E_i).

Dari dua sifat di atas kita bisa dapatkan fakta ini.

Fakta: Jika A dan B adalah dua himpunan terukur dan A \subset B, maka m(A) \le m(B). Ini bisa didapat dengan menggunakan fakta bahwa B = A \cup (B\setminus A), dan karena A dan B\setminus A adalah dua himpunan yang saling disjoin, maka m(B) = m(A) + m(B\setminus A) \ge m(A).

Sekarang, kita ingin menghitung ukuran suatu singleton, yaitu himpunan yang terdiri dari satu anggota. Misalkan A = \{a\} dan B = (a - \frac{\epsilon}{2}, a + \frac{\epsilon}{2}), untuk suatu \epsilon > 0. Jelas A \subset B dan kita tahu bahwa m(B) = \epsilon.

Karenanya, 0 \le m(A) \le m(B) = \epsilon. Tapi kita bisa pilih \epsilon yang sekecil-kecilnya, sehingga ini memberikan m(A) = 0. Jadi ukuran dari suatu himpunan singleton adalah 0.

Sekarang, perhatikan himpunan bilangan rasional \mathbb{Q}. Karena \mathbb{Q} terhitung, maka kita bisa enumerasi \mathbb{Q} = \{q_i \mid i \in \mathbb{N}\}. Karenanya,

m(\mathbb{Q}) = m\left(\displaystyle\bigcup_{i = 1}^{\infty} \{q_i\}\right) = \displaystyle\sum_{i = 1}^{\infty} m(\{q_i\}) = \displaystyle\sum_{i=1}^{\infty} 0 = 0.

Jadi, ukuran bilangan rasional adalah nol! Kalau kita batasi diri bekerja pada bilangan rasional yang terletak di antara 0 dan 1, yaitu \mathbb{Q} \cap (0,1), maka dengan menggunakan fakta di atas bisa didapatkan m(\mathbb{Q} \cap (0,1)) = 0.

Apa artinya ukuran suatu himpunan 0? Mengingat bahwa ukuran adalah perumuman konsep panjang, luas, atau volume, kita bisa bilang kalau himpunan yang berukuran 0 pada dasarnya dapat diabaikan; hampir tidak ada. Kenapa hampir? Ya karena sebenarnya mereka ada. Kita bekerja dengan bilangan rasional dari SD, kok. 😛

Kembali ke permasalahan di atas. Dari penjelasan secara matematis di atas (semoga tidak terlalu sulit untuk dipahami ya 😩 ) dapat disimpulkan bahwa bilangan rasional hampir tidak ada. Kalau kita kaitkan dengan peluang (yang sebenarnya juga adalah ukuran), kita bisa bilang bahwa peluang mengambil bilangan rasional dari antara 0 dan 1 adalah 0, karena ukuran bilangan rasional adalah 0. Artinya, kalau kita harus mengambil satu bilangan yang terdistribusi merata dari antara 0 dan 1, maka pasti bilangan tersebut adalah bilangan irasional.

Mengingat hampir setiap orang yang diminta untuk mengambil suatu bilangan dari antara 0 dan 1 akan menjawab dengan bilangan rasional, maka sebenarnya ini sangat ironis, kan?

‘Paradoks’ Diagonal

Banyak orang yang saya kenal cenderung memanfaatkan gambar untuk membuktikan suatu pernyataan matematika tertentu. Padahal dalam membuktikan suatu kebenaran matematika, gambar tidak bisa digunakan sebagai acuan utama. Gambar hanyalah alat bantu. Apa yang tampak di gambar belumlah tentu seperti yang terjadi sebenarnya.

Untuk mengilustrasikan hal ini, saya mau menulis tentang apa yang orang sebut sebagai Paradoks Diagonal. Sebenarnya ini bukan suatu paradoks, karena tidak ada pernyataan yang saling bertolak belakang sebagai implikasi dari pernyataan ini. Saya lebih suka menyebutnya ‘Paradoks’ Diagonal. *ketahuan gak kreatif ya* :p

Di sebuah persegi satuan, kita tahu panjang diagonalnya adalah \sqrt{2}. Namun, kalau kita buat ‘tangga’ sepanjang diagonal, yaitu kumpulan garis horizontal dan vertikal sepanjang diagonal, lama kelamaan ia akan semakin mirip dengan diagonal. Namun, panjang total tangga ini adalah panjang total garis horizontal + panjang total garis vertikal yang adalah 2. Jadi, apakah ini berarti 2 = \sqrt{2}?


diagonal paradoxKita harus berhati-hati ketika mengambil limit di sini. Fungsi l \colon A \rightarrow \mathbb{R} di mana A adalah himpunan semua kurva dengan panjang berhingga dan l(C) menyatakan panjang kurva C bukan fungsi yang kontinu. Dengan kata lain, jika kita punya barisan kurva \{C_n\} yang konvergen ke kurva C, maka belum tentu l(C_n) juga konvergen ke l(C).

Untuk melihat fakta tersebut, misalkan pada selang (a,b) kita punya barisan fungsi \{f_n\} yang konvergen ke g, yaitu

f_n(x) \rightarrow g(x) saat n \rightarrow \infty, \forall x \in (a,b).

Nah, untuk setiap n \in \mathbb{N}, dari pelajaran Kalkulus kita tahu bahwa

l(f_n) = \displaystyle\int_a^b \sqrt{f_n'(x)^2 + 1}\ dx dan l(g) = \displaystyle\int_a^b \sqrt{g'(x)^2 + 1}\ dx.

Dalam kasus anak tangga ini, f_n'(x) hanya bernilai 0, \infty, dan bahkan tidak terdefinisi di titik tertentu, padahal g'(x) = 1. Jadi, dapat disimpulkan l(f_n) tidak konvergen ke l(g).