[SeqFan] Re: Suggestion for a sequence: weights on a circle, roots of unity and Chebyshev's polynomials.

[Antti Karttunen]

>
> Brendan McKay wrote September 11 2005:
>
>> A recent puzzle in New Scientist suggests the following.
>>
>> Suppose you have n objects, with weights 1,2,3,...,n.
>> (That is, exactly one object with each of those weights.)
>>
>> How many ways are there to place these objects evenly spaced
>> around the circumference of a disk so that the disk will
>> exactly balance on the centre point?
>>
>> In algebraic terms, how many permutations p1,p2,...,pn
>> are such that the polynomial p1 + p2*x + ... + pn*x^(n-1)
>> has exp(2 pi i/n) as a zero? 
>
I wrote in the previous message:

>
> But when I started thinking how to compute this (or similar) sequences 
> by brute generate-and-test
> method, and how to do that without floating point arithmetic, I found 
> another interesting problem.
> Continued in the next message...


The question is this:

What is the (minimal) dimension of a linearly independent base
(consisting of reals) such that the real-components of all the nth
roots of unity (i.e. cosines of the corresponding angles) can be
represented as linear combinations (with rational coefficients) of that 
base?

E.g. for n=3, i.e. an equilateral triangle whose one vertex is located 
at (1,0)
the other two vertices are located at (-(1/2),sqrt(3)/2)
and (-(1/2),-sqrt(3)/2), the dimension is 1 as
both values 1 and -1/2 can be represented as the rational
multiples of 1.

For the 5th roots of unity (regular pentagon) we have the following
values for real-part: 1, (sqrt(5)-1)/4, -(sqrt(5)+1)/4, -(sqrt(5)+1)/4, 
(sqrt(5)-1)/4.

So for example 1 and sqrt(5)-1 can be used as a base, and its dimension 
is 2.
(Note that sqrt(5)+1 = 1*(sqrt(5)-1) + 2*1.)

For n-gon in general, we get the cosine's (real parts of the corresponding
roots of unity) with Chebyshev's polynomials of the first kind:

T_0(x) =1
T_1(x) = x
T_2(x) = 2x^2 - 1
T_3(x) = 4x^3  - 3x
T_4(x) = 8x^4 - 8x^2 +1
etc.
(see for example http://en.wikipedia.org/wiki/Chebyshev_polynomials
or http://mathworld.wolfram.com/ChebyshevPolynomialoftheFirstKind.html )

cos(2pi/n) should be among the zeros of polynomial
T_0(x) + T_1(x) + ... + T_(n-1)(x)

but I guess this gets unsolvable quite soon. Maybe there's an easier way.
For example, can the vertices of a regular heptagon given exactly 
without resorting to trigonometric functions?
And does it matter, do we need to know the exact value of the cos(2pi/n) 
(in terms of roots
and so on) to be able to determine the minimal dimension of such a base?

(And similarly for sine's (imaginary components of the roots of unity) 
with the
help of  http://en.wikipedia.org/wiki/Spread_polynomials
but I guess the resulting sequence is same, by the symmetry.)

See also http://en.wikipedia.org/wiki/Gaussian_period
which might contain some hints, although I don't see
them myself.


Hard question, or easy?


Terveisin,

Antti Karttunen