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

The Problem

Let $r,q,m$ be positive integers such that $4 \leq r$ and $1<m,q\leq r/2$. Is it the case that

$$\left | \sum_{k=0}^{q-1} \zeta^{km}\right | < \left |\sum_{k=0}^{q-1} \zeta^{k}\right |,$$

where $\zeta$ is a primitive $r^{th}$ root of unity.

Continuous Variant

Through use of a non-standard trigonometric identity which may be found here we can change the previous inequality to

$$|\sin(mq\pi/r)\sin(\pi/r)| < |\sin(m\pi/r)\sin(q\pi/r)|.$$

Then we may substitute real variables. Let $\theta \in (0,\pi/4]$ and $a,b \in \mathbb R$ so that $0< a\theta, b \theta \leq \pi$. The we have the inequality

$$| \sin(ab \theta) \sin(\theta) |< | \sin(a \theta)\sin(b \theta) |. $$

Fix $\theta$ and consider the function


where $(x,y) \in [1,\pi/(2\theta)]^2=X$. So if we can show that $f$ has a unique maximum on $X$ at $(1,1)$ we would also have our result. One can show with a somewhat painful computation that the critical points of $f$ are on the line $x=y$, so we can consider instead the function


and the corresponding inequality


I have some partial results in this case where essentially I can control the inequality depending on where $x^2\theta$ is modulo $2\pi$. Which comes down to everything except when the residue of $x^2\theta$ modulo $2\pi$ is in the interval $(2x\theta-\theta,2x\theta)$.


Let the generalized binomial coefficient $C_q(n,k)$ be the coefficient of $x^k$ in the polynomial $(1+x+\cdots+x^{q-1})^k$, sometimes this appears in the literature as $\binom{n}{k}_q$. Define

$$PC_q(n,r,k)=\sum_{j \in \mathbb Z} C_q(n,k+rj)$$

then the sums in the statement of the problem arise naturally as the coefficients of a discrete Fourier expansion of $PC_q$. In particular proving the desired inequality shows that $PC_q$ behaves as a sine function as $n \rightarrow \infty$. There's some more background on $C_q$ and $PC_q$ is this answer.

share|cite|improve this question
up vote 3 down vote accepted

Actually, I believe something a bit stronger is true: For any $S \subseteq \{1,\dots,r\}$ with $|S|=q$, we have $$ (*) |\sum_{j \in S} \zeta^j| \leq |\sum_{k=0}^{q-1} \zeta^k|.$$

Consider an arbitrary $S$, and let $v$ be the unit vector in the direction of $\sum_{j \in S} \zeta^j$ (here and later on we're thinking of the complex numbers as a $2$-dimensional real vectors). Let $S'$ be the set consisting of the $q$ roots of unity having largest (positive) projection onto $v$. Then we have \begin{eqnarray*} |\sum_{j \in S} \zeta^j| &=& proj_{v}\left(\sum_{j \in S} \zeta^j\right) \\ &=& \sum_{j \in S} proj_v \left(\zeta^j\right) \\ &\leq& \sum_{j \in S'} proj_v \left(\zeta^j\right) \\ &=& proj_v \left(\sum_{j \in S'} \zeta^j \right) \\ &\leq& | \sum_{j \in S'} \zeta^j | \end{eqnarray*} But for any $v$ the set $S'$ consists of $q$ consecutive roots of unity, so the last expression is the right hand side of (*).

If equality holds, then $S$ must consist of $q$ consecutive residues modulo $r$. In other words, the set $\{1, m, 2m, \dots, (q-1)m\}$ is some permutation of $\{a,a+1,\dots,a+q-1\}$ (modulo $r$) for some $a$ and $q$. Let us fix some $m,a,q$ for which this occurs.

For $1 \leq j \leq q$, let $f(j)$ be the integer between $0$ and $q-1$ such that $mj$ is congruent to $a+f(j)$ modulo $r$. One of two things must happen:

-If $f(j)=j$ for all $j$, then $a=m=1$, not allowed.

-Otherwise, there is some $j$ for which $f(j)>f(j+1)$. But this would imply $m(j+1)-mj \geq a+r-(a+q-1)$, or, rearranging, $m+q \geq r+1$, which is also not allowed.

Essentially what the second case corresponds to is that your condition on $m$ and $q$ versus $r$ makes it impossible to "wrap around" from one end of the interval to the other between two consecutive multiples of $m$.

share|cite|improve this answer
Could you prove your last statement for the benefit of slow readers like me? (that $S^prime$ consists of $q$ consecutive roots) – Alexander Gruber Feb 15 '13 at 0:20
Since all roots of unity have the same magnitude, the roots with largest projection onto $v$ are those whose direction lies closest to $v$. So if you take an arc centered at $v$ and growing in size, then $S'$ will consist of all the roots of unity in that arc when it first contains $q$ points (possibly leaving a single endpoint out if it jumps from $q-1$ to $q+1$). – Kevin Costello Feb 15 '13 at 1:32
One other note: I've been assuming that actually $\zeta=\exp\left(\frac{2 \pi i}{r}\right)$ (since it seems like if you allow $\zeta$ to be an arbitrary primitive root of unity than, for example the inequality with $\zeta=\exp\left(2 \pi i \frac{3}{11}\right)$ and $m=4$ is exactly the reverse of the one with $\zeta=\exp\left(2 \pi i \frac{1}{11}\right)$ and $m=3$). If I'm misunderstanding something, please let me know. – Kevin Costello Feb 15 '13 at 1:38
How do we know that the first $q$ roots of unity are closest to the direction of $v$? $v$ should be able to be in just about any direction right? – Alexander Gruber Feb 15 '13 at 7:12
Right, but the absolute value of the sum any $q$ consecutive roots of unity is the same as the sum of the first $q$ (since they differ only by a rotation). – Kevin Costello Feb 15 '13 at 7:55

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.