# For which $n$ is $\int \limits_0^{2\pi} \prod \limits_{k=1}^n \cos(k x)\,dx$ non-zero?

I can verify easily that for $n=1$ and $2$ it's $0$, $3$ and $4$ nonzero, $4$ and $5$ $0$, etc. but it seems like there must be something deeper here (or at least a trick).

-
I deleted my answer because the hint I gave was incorrect. –  Américo Tavares Jul 4 '11 at 20:28

Apparently, this isn't an easy question. See here for $n \leq 10$.

EDIT: As Jason pointed out below, the last paragraph on the linked page sketches the proof that the integral is non-zero iff $n$ $=$ $0$ or $3$ mod $4$ (that is, iff $n \in \lbrace 3,4,7,8,11,12,\ldots\rbrace$).

-
well, great searching :) –  user9413 Jul 4 '11 at 19:31
@Chandru, actually this was quite easy to find. –  Shai Covo Jul 4 '11 at 19:37
The last paragraph on the linked page sketches the solution for all $n$. –  Jason Swanson Jul 4 '11 at 19:42
@user11867: Thanks for pointing this out. –  Shai Covo Jul 4 '11 at 19:47

Write $\cos(kx)=(e^{ikx}+e^{-ikx})/2$. Obtain

$$\begin{array}{ll} \int_0^{2\pi}\prod_{k=1}^n\cos(kx)dx & =\int_0^{2\pi} \prod_{k=1}^n \frac{e^{k i x} + e^{- k i x}}{2} dx \\ & = 2^{-n}\int_0^{2\pi} e^{-(1+2+\cdots+n) \cdot i x} \prod_{k=1}^n \left( 1 + e^{2 k i x} \right) dx \\ & =2^{-n}\int_0^{2\pi}e^{-n(n+1)/2\cdot ix}\sum_{\sigma\in\Sigma} e^{2\sigma ix}dx \\ & =2^{-n}\sum_{\sigma\in\Sigma}\int_0^{2\pi}e^{(2\sigma -n(n+1)/2)\cdot ix}dx\end{array}$$

where $\Sigma$ is the multiset of numbers comprised of the sums of subsets of $\{1,\cdots,n\}$. The integral in the summand is given by $+1$ if $2\sigma=n(n+1)/2$ and $0$ otherwise. Therefore the sum is nonzero if and only if there is a $n(n+1)/4\in\Sigma$, i.e. $n(n+1)/4$ can be written as a sum of numbers taken from the set $\{1,\cdots,n\}$. Firstly $4\mid n(n+1)\Leftrightarrow n\equiv 0,-1$ mod $4$ is necesesary, and moreover

Lemma. Any number $0\le S\le n(n+1)/2$ may be written as a sum of numbers in $\{1,\cdots,n\}$.

Proof. $S=0$ corresponds to the empty product. $S=1$ corresponds to the term $1$ itself. Otherwise suppose the claim holds true for $n$ as induction hypothesis, and we seek to prove the claim still holds true for $n+1$. Let $0\le S\le (n+1)(n+2)/2$. If $S\le n(n+1)/2$ then simply take the numbers from $\{1,\cdots,n\}$ via induction hypothesis, otherwise $0\le S-(n+1)\le n(n+1)/2$ and we may invoke the induction hypothesis on $S-(n+1)$, then add $n+1$ to that sum to obtain a sum of elements from $\{1,\cdots,n,n+1\}$ which add up to $S$.

Therefore, $n\equiv 0,-1$ mod $4$ is both necessary and sufficient for the integral to be positive.

-
Ah! You know I didn't understand this comment a year ago, but recently I revisited the problem and I like this solution much better than the other one. –  Alexander Gruber Oct 4 '12 at 1:56
To clarify for other future readers who may be confused as I first was: This version of the proof hinges on the fact that $\int_0^{2\pi}e^{ikx}dx=0$ if and only if $k=0$. We can write every term in the integrand as $e^{i\left(-\frac{n(n+1)}{2}+2\delta\right)x}$ for some $\delta \in \mathbb{Z}$, so for a non-zero term we need $n(n+1)=4\delta$, or in other words $n(n+1)\equiv 0 \mod{4}$. All other terms vanish, so for the integral to be nonzero, we need either $n$ or $n+1$ to be congruent to $0\mod{4}$, whence $n\equiv 0 \text{ or } -1 \mod{4}$. Voila! Thanks again @anon. –  Alexander Gruber Oct 4 '12 at 2:04
But as this derivation goes, $n\equiv 0 or -1 (mod 4)$ is a necessary condition. It still remains to show that this condition is sufficient and there indeed are subset of $\{1,2,3,...,n\}$ such that $n(n+1)=4\sum k$. –  Hans Dec 16 '13 at 4:16
@Hansen This answer is two years old so my memory may be faulty, but IIRC I simply stated without proof that every number $\le n(n+1)/2$ could be written as a sum of numbers from $\{1,\cdots,n\}$. This can be shown by induction on $n$. (Say it holds up to $n$, and we have a number $\Sigma\le (n+1)(n+2)/2$. If $\Sigma\le n(n+1)/2$ then invoke the induction hypothesis, else invoke the induction hypothesis on $\Sigma-(n+1)$.) –  anon Dec 16 '13 at 4:26
Nice proof, anon. Have 2 up-votes, one for the answer and one for the last comment. :-) –  Hans Dec 16 '13 at 15:58

Hint: Start as anon did with $$\int_0^{2\pi}\prod_{k=1}^n\cos(kx)\,\mathrm{d}x =\int_0^{2\pi}e^{-i\frac{n(n+1)}{2}x}\prod_{k=1}^n(1+e^{i2kx})\,\mathrm{d}x\tag{1}$$ which would be $2\pi$ times the coefficient of $x^{n(n+1)/2}$ in $$\prod_{k=1}^n(1+x^{2k})\tag{2}$$ $(2)$ is the number of ways to write $n(n+1)/2$ as the sum of distinct even integers $\le2n$.

So $(1)$ is non-zero precisely when you can write $n(n+1)/2$ as the sum of distinct even integers $\le2n$ (a much simpler problem).

Claim: $\dfrac{n(n+1)}{2}$ can be written as the sum of distinct even integers no greater than $2n$ in at least one way precisely when $n\in\{0,3\}\pmod{4}$.

Proof: By induction.

If $n\in\{1,2\}\pmod{4}$, then $\dfrac{n(n+1)}{2}$ is odd, and so cannot be written as the sum of even integers.

Suppose that $n\in\{0,3\}\pmod{4}$ and $\dfrac{n(n+1)}{2}$ can be written as the sum of distinct even integers no greater than $2n$. Then $$\frac{(n+4)(n+5)}{2}=\frac{n(n+1)}{2}+(2n+4)+(2n+6)$$ Thus, if the statement is true for $n$, it is true for $n+4$.

Once we note that $\dfrac{3(3+1)}{2}=2+4$ and $\dfrac{4(4+1)}{2}=4+6$, we are done. QED

-
How is your last statement any easier than the modulo arithmetic in anon's solution? –  Hans Dec 16 '13 at 4:21
@Hansen: it is when $n(n+1)/2$ is even, that is when $n\in\{0,3\}\pmod{4}$. –  robjohn Dec 16 '13 at 5:15
Could you please show the derivation for "write $n(n+1)/2$ as the sum of distinct even integers $\le 2n$" so as to explain why this formulation is "a much simpler problem"? –  Hans Dec 16 '13 at 15:18
@Hansen: are you talking about anon's original argument from two and a half years ago, or the modification made yesterday? The "modulo arithmetic in anon's solution", while similar to what I wrote over a year ago, was added less than 12 hours ago. I have added a very simple inductive argument for my claim. –  robjohn Dec 16 '13 at 16:28
I was talk about anon's original argument from two and a half years ago. I did not see the difference between your original argument and anon's original argument. Now the sufficient condition arguments of you two are a bit different. Both are very nice! I up-voted your answer. –  Hans Dec 16 '13 at 17:38