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

Hence,

\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…