# Olympiad - sequence of sum of complex numbers

This is the other problem I couldn't solve in the olympiad test I took today.

Let $c_1, ... , c_n$ be complex numbers with unitary norm, and $S_k=\sum_{i=1}^n c_i^k$, $k\in \mathbb{N}$. Suppose $S_1, S_2, ...$ converges. Prove that $c_i=1$ for every $i=1, ..., n$.

By using De Moivre's formula, the problem is equivalent to showing that $\cos(k\theta_1) + ... +\cos(k\theta_n)$ has no limit as $k\to\infty$ unless all $\theta_i$'s are $0$ (mod $2\pi$) (and an analogous claim for the sum of sines).

I don't know how to prove that.

-
Try proving it for n = 1 first, then n = 2. – Qiaochu Yuan Feb 5 '11 at 23:08
@Qiaochu: I think I see clearly why it's true for $n=1$, but I seem unable to treat the case $n=2$. – kevincuadros Feb 5 '11 at 23:27
I am having trouble giving a hint that does not give too much away. Okay, so can you solve the problem when n = 2 and theta_1 is a rational multiple of pi, but theta_2 isn't? Can you think about how to adapt this solution to the case where neither of them have this property? – Qiaochu Yuan Feb 5 '11 at 23:39

I've edited the answer twice without deleting the previous versions, to keep the history of the answer and the comments transparent. That makes it much longer than it originally was, but if you're just interested in the end result, the first and last paragraphs make up a concise and complete proof.

If $S_k$ converges, then the differences $\Delta S_k := S_{k+1} - S_k$ must converge to zero. Hence the differences $\Delta^2 S_k := \Delta S_{k+1} - \Delta S_k$ must also converge to zero, and so on for $\Delta^n S_k$ for all $n$. But $\Delta^n S_k = \sum_{i=1}^{n} (c_i - 1)^n c_i^k$. There can be either one or two values of $c_i$ for which the absolute value of $c_i - 1$ is maximal. If there is only one, the corresponding term will dominate the sum for sufficiently large $n$, in the sense that its absolute value becomes greater than the absolute value of the sum of all the other contributions. Since this term only converges to zero if $c_i - 1 = 0$, it follows that $c_i = 1$ for all $i$.

If there are two (conjugate) maximal values of $c_i - 1$, there is a linear combination of $S_k$ and its complex conjugate in which only one of these maximal values occurs; if $S_k$ had a limit, so would its complex conjugate and this linear combination.

Edit in response to kevincuadros's question about the linear combination part:

In trying to clarify this, I can see now why you didn't "fully get" it -- because I hadn't thought it through properly :-)

What I had in mind was this: If there are two different values $c_i$ with maximal absolute value of $c_i - 1$, they are conjugate. Both may occur more than once; let $\mu_1$ and $\mu_2$ be their multiplicities. Then $\mu_1 S_k - \mu_2 S_k^\mathrm{*}$ will contain one of them with multiplicity $\mu_1^2 - \mu_2^2$ and the other with multiplicity $\mu_1\mu_2 - \mu_2\mu_1=0$. I was thinking that we could then reason that since this linear combination contains only one of the two, we can apply the above proof to it, and then argue that if $S_k$ had a limit, then so would $S_k^\mathrm{*}$ and any linear combination of them. But I see now that that doesn't work out because we could have $\mu_1=\mu_2$, and hence $\mu_1^2-\mu_2^2$, and in that case neither of the two would occur in that linear combination, so we still have to deal with that case.

So in that case, the contributions from these conjugates cancel in the imaginary part and add up in the real part. If $S_k$ is to converge, its real part must converge. But $(c_i - 1)^n c_i^k$ comes arbitrarily close to being real infinitely often; thus its real part comes arbitrarily close to $|c_i - 1|^n$ infinitely often, and hence the argument for the general case carries through.

To make the full proof more concise, we can forget about the whole linear combination thing and just argue as follows: If there are two distinct values of $c_i$ with equal maximal absolute value of $c_i - 1$, they are conjugate. Then consider the sum of the real parts of their contributions, which comes arbitrarily close to the sum of their absolute values infinitely often, and hence the argument for the general case carries through.

Further edit to salvage the style of the proof:

I don't really like the above fix, since part of the point of the original proof was to avoid saying something like "x gets arbitrarily close to y an infinite number of times". So here's a slightly nicer fix:

If there are two distinct values of $c_i$ with equal maximal absolute value of $c_i - 1$, they are conjugate. Then the real parts of their contributions add up to $|c_i-1|^n$ times the cosine of an angle that changes with $k$. Since the ratio of $|c_i-1|^n$ to the absolute value of the sum of all other terms goes to infinity with increasing $n$, increasing $n$ will yield arbitrarily small upper bounds on the cosine. But since $c_i \neq \pm 1$, the cosine necessarily violates these bounds. (Note that this doesn't use the property that the cosine gets arbitrarily close to 1, only that it doesn't remain arbitrarily close to 0, which is much less and doesn't require an argument using rational and irrational numbers.)

-
that's clever. I just don't fully get the linear combination part, could you clarify it for me? – kevincuadros Feb 7 '11 at 23:38
@kevincuadros: Thanks. I edited the answer in response to your question. – joriki Feb 8 '11 at 10:38
@kevincuadros: I edited it again to make the fix more in keeping with the style of the original proof. The first (original) and last (new) paragraph now make up a concise and complete proof. – joriki Feb 8 '11 at 12:10

I've not done olympiads, so I'm not sure if this is the intended method.. but anyhow... we may assume without loss of generality that no $c_i = 1$, and that we are working by induction and know the result for $n-1$ and are seeking it for $n$ ($n=1$ is trivial.)

One fact which is often useful is that if a sequence $a_1,a_2,...$ converges, then the means $b_m = {1 \over m}( a_1 + ... + a_m)$ will converge to the same limit. Applying it to the sequence $S_1, S_2,...$, the averages $T_m = {1 \over m}\sum_{k=1}^m (\sum_{i=1}^n c_i^k) = \sum_{i=1}^n {1 \over m}(\sum_{k=1}^m c_i^k)$ will also converge to $L:=\lim\limits_{k\rightarrow\infty}S_k$. But the sum ${1 \over m} (\sum_{k=1}^m c_i^k)$ can be summed directly as a geometric series to ${1 \over m}{c_i^{m+1} - c_i \over c_i - 1}$. As $m$ goes to infinity this goes to zero. So the limit $L$ must be zero.

Since $S_1, S_2,..$ converges to zero and $|c_1| = 1$, $U_m := (c_1)^{-m}S_m$ also goes to zero. But $U_m$ is exactly $1 + \sum_{i=2}^m (c_i/c_1)^m$. So the sequence $U_m - 1 = \sum_{i=2}^m (c_i/c_1)^m$ converges to $-1$, contradicting the induction hypothesis.

-
This is really slick! The argument I had in mind was Yuval Filmus's, but the clever observation in the second paragraph neatly circumvents this. – Qiaochu Yuan Feb 6 '11 at 1:08
Cesaro summation, Fourier series' best friend :) The $c_i^k$ reminded me of the functions $e^{ikt}$, which sent me in that direction. – Zarrax Feb 6 '11 at 2:05

Let $c_i = \exp(2\pi i \alpha_i)$. Choose a basis $\beta_j$ (over the rationals) for all $\alpha_i$, such that in the resulting representation, the coefficient of every $\beta_j$ is integral, and the coefficients of $\beta_j$ don't have a common multiple.

If there is any rational $\beta_j$, let $M$ be the maximal coefficient of $\beta_j$, and replace $c_i$ with $c_i^M$; now the "rational" part of the sum is constant; adjust the basis accordingly so that the other properties still hold. We can remove the rational basis member (if any) from the basis.

Now construct a sequence of $k$s $S_1$ such that $\{k \beta_i\} \approx 0$, and another sequence of $k$s $S_2$ such that $\{k \beta_1\} \approx 1/2$ and $\{k \beta_i\} \approx 0$ for $i \geq 2$. The limit for $S_1$ and $S_2$ is different (since the coefficients of $\beta_1$ are all integers and not all even); this contradiction shows that all coefficients must be rational.

Now go back to the original $c_i$, and write $\alpha_i = p_i/q_i$. If not all $\alpha_i$ are $0$, choose some prime $Q$ dividing one of the $q_i$. Let $M$ be the least common multiple of all $q_i$. Form a new set of $c_i$ by replacing $c_i$ with $c_i^{M/Q}$. We now have either $c_1 = 1$ or $c_i = p_i/Q$. Now for multiples of $Q$ all $c_i^k = 1$ and so the sum is some constant $C$, whereas for anything else, this won't be the case, and so in particular the real part of the sum will be smaller than $C$. This contradiction shows that, in fact, all $\alpha_i$ must be $0$, i.e. all $c_i$ are $1$.

-
I'm afraid I don't understand your solution, on from "choose a basis for...". If you could spare some time to explain it to me in more detail, it'll be greatly appreciated. – kevincuadros Feb 7 '11 at 23:37
The reals numbers can be viewed as a vector space over the rationals; a basis for them is called a Hamel basis. While such a basis would do for my purposes, in this case, since the number of quantities involved is finite, you can find it by "brute force". --- – Yuval Filmus Feb 8 '11 at 1:46
--- Namely, consider the $\alpha_j$ in order. Occasionally you'll find out that $\alpha_j$ can be expressed as a rational combination of the preceding $\alpha$'s - in this case we drop it. Continuing this way, we arrive at a basis for the $\alpha_j$. To get the $\beta_j$ we need to apply some appropriate normalization. – Yuval Filmus Feb 8 '11 at 1:48