[SeqFan] Re: Suggestion for a sequence: weights on a circle

[T. D. Noe]

>>The suggested sequence (number of ways to arrange the weights) would
>>start (first term n=1)
>>
>>0 0 0 0 0 4 0 0 0 48 0 1464 0 1440 96
>>
>>
>>Hugo Pfoertner
>>
>>
>>
>
>The above sequence is still not in OEIS, by the way. In above sequence
>Hugo seems to
>have discarded the reflections mirrored over the X-axis (or the
>real-axis if we think in the
>terms of roots of unity), so maybe we need another sequence which gives
>also them.
>(*2 of the above one, there are no symmetrical solutions because all the
>weights are different...)
>
>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.

The sequence above counts the circular permutations of weights.  I suggest
taking 1/2 * above sequence and submitting it to OEIS.  The 1/2 factor
removes the reversal of the permutations, leaving the essentially different
solutions.

The computations can be done without floating-point arithmetic by using
polynomial GCD.  As mentioned in a previous e-mail, for a permutation
(w1,w2,..wn) to be a solution, the polynomial P(x)=w1+w2*x+...+wn*x^(n-1)
must have e^(2 pi I/n) as a root.  This means that P(x) and the nth
cyclotomic polynomial have a common zero or, equivalently,
gcd(P(x),Phi(n,x)) = Phi(n,x) because Phi(n,x) is irreducible.  This means
Phi(n,x) divides P(x) or, equivalently, P(x)=0 (mod Phi(n,x)).  These are
all computable via integer operations.

In fact, using this approach, it is easy to show that there are no
solutions when n is prime.  In this case, Phi(n,x) is an irreducible
polynomial of degree n-1 and all coefficients 1.  Because P(x) is also of
degree n-1, the only way for gcd(P(x),Phi(n,x)) = Phi(n,x) is for P(x) =
Phi(n,x).  However, this is not possible because P(x) has coefficients 1..n.

For odd prime p, there is always a solution when n=2p.  In this case,
Phi(2p,x) = Phi(p,-x), an irreducible polynomial of degree p-1 with
coefficients alternating 1,-1,1,..,-1,1.  The following permutation is
always a solution: w1=1, w3=2, w5=3,..., w(2p-1)=p and w(p+1)=p+1,
w(p+3)=p+2, w(p+5)=p+3,... with the indices>2p wrapping.  For example, n=14
has solution (1,12,2,13,3,14,4,8,5,9,6,10,7,11). For this solution,
w(i)-w(i+p) = p (even i) or -p (odd i).  Let's verify that r=e^(pi I/p) is
a root of P(x).  Combining the i and i+p terms of P(x), we obtain r^i
(w(i)+w(i+p)r^p)) = +-p r^i because r^p=-1.  Doing this for every i, we
obtain P(r) = p*(1-r+r^2-...+r^(p-1)) = 0 because the parenthesized
expression is Phi(p,-r) and r is a zero of Phi(p,-x).

Tony