How do you call this fact about sum of powers of n-th unity root?

118 Views Asked by At

I often see identity

$$\sum_{k=0}^{n-1}e^{\tau ika/n} = \cases {n \quad \text{ if }n | a\\0\quad \text{ otherwise}}$$

in the context of generating functions. It allows to zero out all members of sequence, indexed by $a$, except every $n$-th one (n divides a). The textbooks seem to consider it so obvious that it does not need any proof. Is it right or there is one?

5

There are 5 best solutions below

1
On

(Assuming that $\tau$ in your formula stands for $2 \pi$) this is an immediate consequence of the "well-known" formula for the (finite) geometric sum $$ \sum_{k=0}^{n-1} x^k = \cases {n \quad \quad \text{ if } x = 1\\ \frac{x^n-1}{x-1}\quad \text{ otherwise}} $$ applied to $x = e^{\tau ia/n}$. (Note that $x = 1$ exactly if $n$ divides $a$.)

0
On

The sum becomes zero when multiplied by $\exp(\tau\mathbf ia/n)-1$, which factor is nonzero when $n\not\,\mathrel\backslash a$, so the sum must have been $0$ already in this case. But when $n\mathrel\backslash a$ then $\exp(\tau\mathbf ika/n)=1^k=1$ and the sum becomes $\sum_{i=0}^{n-1}1=n$.

3
On

The intuitive geometric approach is to look at all the $n$th roots. I mean, draw them as points on a piece of paper (or in your head). See how nicely they're distributed, all evenly along the unit circle. That means their sum is equal to $0$.

Now raise them to some power. If that power is a multiple of $n$, then they will all end up at $1$, and their sum will be $n$. However, if the power is not a multiple of $n$, they will still be spread out. They might end up some on top of others, in which case you will have "piles" of points, where each pile has $\gcd(n, a)$ points. So each pile will weigh the same as any other pile, and they're still evenly spread out along the unit circle (although possibly a bit sparser). Therefore their sum is $0$.

0
On

The numbers $x_k =e^{2\pi i \frac{k}{n}}$, $0 \le k \le n-1$ are the roots of the polynomial $x^n-1$. The sums $S_a= \sum_{k=0}^{n-1} x_k^a$ have period $n$ in $a$ ( $S_{a+n} = S_a$ ) so it is enough to prove the assertion for $0\le a \le n-1$. For $a=0$ it's true (easy check). Let's show that $S_1, \ldots, S_{n-1} =0$. We can show in fact that for every symmetric polynomial in $x_k$ homogenous of degree $d$, $1\le d \le n-1$ we have $P(x_1, \ldots, x_n) =0$. Indeed, $P(x_1,\ldots, x_k)$ will be expressed in terms of the fundamental symmetric polynomials in $x_k$, $e_1 = \sum x_k$, $e_2 = \sum x_k x_l$, $e_n = x_1 \ldots x_n$. Now from Viete relations we have $e_1 = ...= e_{n-1} = 0$. Now any monomial in the expression of $P(x_1, \ldots, x_n)$ in terms of the $e_i$ involves only $e_1$, $\ldots e_{n-1}$ and is of degree $>0$. Therefore, every such monomial evaluated in $e_1$, $\ldots e_n$ give $0$, and so $P(x_1, \ldots, x_n)= 0$.

0
On

For $n$, $a$ integers, $n>0$ the map

$$ k\!\!\!\!\mod n \mapsto a k \!\!\!\!\mod n$$ maps $\mathbb{Z}/n $ onto $\gcd (a,n)\cdot \mathbb{Z}/n\simeq \mathbb{Z}/(n/d)$ with fibres of cardinality $\gcd (a,n)=\colon d$. Therefore we have

$$S_a = \gcd (a,n)\cdot S'_1$$

where the sum $S'$ is the sum of the roots of the equation $X^{\frac{n}{d}}-1$, and this from Viete's equalities is $0$ is $d < n$, and $n$ if $d= n$.