Let n be a positive integer which is not a prime power. Show that there is a permutation a1, a2, ... , an of 1, 2, ... , n such that cos(2πa1/n) + 2 cos(2πa2/n) + 3 cos(2πa3/n) + ... + n cos(2πan/n) = 0.
Solution
We show that a slightly stronger result is true: we can find such a permutation for n not a power of 2.
Put ck = cos(2πk/n). We show first that for odd n = 2m+1 we have c1 + 2c2 + 3c3 + ... + mcm + (m+1)c2m+1 + (m+2)cm+1 + (m+3)cm+2 + ... + (2m+1)c2m = 0 (*). This follows almost immediately from c1 + c2 + ... + cn = 0 (1), ck = cn-k (2) and cn = 1 (3). (1) just says that the sum of the complex roots of 1 has zero real part (obvious from the polynomial zn = 1), (2) follows from cos(-x) = cos x, and (3) is immediate. So we have c1 + c2 + ... + cm = -1/2. Hence (2m+2)(c1 + c2 + ... + cm) = -(m+1) = -(m+1) c2m+1, which is (*).
Next we show that if the result is true for n, then it is also true for 2n. We show first by a similar argument to the above that c1 + 3c3 + 5c5 + 7c7 + ... + (2n-1)c2n-1 = 0 (**). Note first that c2 + c4 + c6 + ... + c2n is just ∑ cos(2πk/n) and so is zero by (1). Subtracting from c1 + c2 + c3 + ... + c2n = 0 gives that c1 + c3 + c5 + c7 + ... + c2n-1 = 0. But ci = c2n-i, so c1 + 3c3 + 5c5 + 7c7 + ... + (2n-1)c2n-1 = (2n-1)c1 + (2n-3)c3 + ... + c2n-1. Adding the two sides gives 2n x (c1 + c3 + ... + c2n-1) = 0, so each side is zero, giving (**).
Now by assumption we have ∑ akck = 0 where ck = cos(2πk/n) for some permutation ak of 1,2,3, ... , n. So ∑ (2ak)c2k = 0, where c2k = cos(2π2k/2n). Putting this together with (**) gives the result for 2n.
Thanks to Lauri Ahlroth for this
© John Scholes
jscholes@kalva.demon.co.uk
4 January 2004
Last corrected/updated 4 Jan 04