Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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).

share|cite|improve this question
I deleted my answer because the hint I gave was incorrect. – Américo Tavares Jul 4 '11 at 20:28
up vote 8 down vote accepted

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$).

share|cite|improve this answer
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.

share|cite|improve this answer
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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.