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…