cyclic polynomials and their solutions

Question

I'll call a polynomial in $z_1,..,z_N$ cyclic if it is invariant under cyclic permutation of the indices. I hope that's standard terminology.

I have N complex numbers $(z_1,...,z_N)$. I want to be able to compute what they are up to cyclic permutation, given the value of some set of cyclic polynomials. For example, if $N=2$ and I know the values of $z_1+z_2$ and of $z_1z_2$, then I could compute $(z_1,z_2)$ up to cyclic permutation. I imagine that there is a solution for general $N$. I also imagine that there is an algorithm that finds the solution from the given finite set of values. Floating point accuracy is good enough for me.

By using the symmetric polynomials, I should be able to find the $z_i$ except for an arbitrary permutation of the indices, but that's not good enough. (I use the word "should" because I don't know how one makes sure that some algorithm like Newton's method actually converges---one needs a good initial point.)

It would be nice to be able to do this with exactly N cyclic polynomials, as in the case N=2. Is the problem any easier if you are allowed to use polynomials in both $z_i$ and its conjugate $\overline{z_i}$: they still have to be invariant under cyclic permutation of the indices?

Answer 1

Actually, if $N>2$, it's impossible to find $N$ "cyclic polynomials" as you desire. That's the same as asking if the cyclic invariants are a polynomial ring, which is impossible by the Chevalley-Shepard-Todd theorem

I suspect in general, the right thing to look at is the sum of the $z_i$'s and all monomials in $p_h=\sum_{i=1}^N \zeta^{ih}z_i$ where the indices $h$ add to a multiple of $N$ (here $\zeta$ is a primitive $N$th root of unity).

So, that means we look at monomials $p_0^{k_0}p_1^{k_1}\cdots p_{N-1}^{k_{N-1}}$ where $\mathbf{k}\cdot (0,1,2,\dots, N-1)\equiv 0\pmod{N}$. It can't be that hard to come up with vectors that span the cone of such integer vectors as a semi-group, though I'll admit, I can't see what they might be at the moment.

Answer 2

So you have a cyclic group acting on complex affine space, and the situation at the level of function fields is clear enough: by basic Galois theory the extension of rational functions is a cyclic extension of degree n. It is a Kummer extension, even: write down a linear combination of the indeterminates with nth roots of unity as coefficients in a kind of obvious way, and you have an element whose nth power is cyclic, but transforms under a non-trivial character of the cyclic Galois group.

I think what you want is a description of the quotient as an affine variety. (Have to go now.)

Edit: My thought, given the other answer here, is that the quotient isn't generally an affine space. By the Noether normalization lemma, however, it is not so far from an affine space, though: a finite branched cover, let's say. The Noether lemma is not so "effective" - the usual proof doesn't tell you how to find the polynomial subring to work with. But with the high degree of structure here, perhaps this case is not the worst case.

Edit: Let's try the case n = 3 and think some about $L_1 = z_1+\zeta z_2+ \zeta^{2}z_3$ (in the context of $L_0 = z_1+z_2+z_3$ and $L_2 = z_1+\zeta ^{2} z_2+ \zeta z_3$) where $\zeta$ is a primitive cube root of 1. A cyclic shift one way multiplies $L_1$ by $\zeta$. Therefore $L_1 ^{3}$ is a cyclic polynomial in your sense. Same is true for $L_2 ^{3}$. Since $L_0$ is cyclic also, we seem to be making progress, because the forms $L_i$ are linearly independent (it's a Vandermonde determinant). Hence we have three cyclic polynomials, and we would be close to solving the problem if it were not for the fact that extracting a cube root gives one of three possible answers, for complex solutions. If we knew the cube root to take, it would all come down to Gaussian elimination.

Answer 3

Ben Webster's answer points the way very clearly to a complete answer, which I have figured out and now give. The simplest case occurs when N is prime. First consider the set of $N-1$ cyclic invariants $p_i p_1^{N-i}$ for $1\le i < N$. If we know the values of these polynomials, and also the value of $p_0(z)$, then, provided that $p_1\ne 0$, we can solve for $(z_1,\dots,z_N)$ up to cyclic permutation. To see this, note that $p_1$ is determined up to cyclic conjugation, since we know it up to multiplication by a power of $\zeta$. The other $p_i$s are then determined as well. This determines $(z_1,\dots,z_N)$ because the Vandermonde matrix is invertible.

However, possibly $p_1(z)=0$. We therefore need a similar construction, for each $i$, with $p_i$ playing the role of $p_1$. This is fine because it's just using a different primitive $N$-th root of unity. We need ALL these functions to cover the space. This covers all points except for those where $p_i(z)=0$ for $1\leq i\lt N$. But these are the points where $z_1=\dots=z_N$, determined by the value of $p_0(z)$.

When $N$ is not prime, we need only consider the case when $p_i(z)=0$ whenever $\zeta^i$ is a primitive $N$-th root of unity. Let $K\lt N$ be the largest divisor of $N$. Then we use primitive $K$-th roots of unity in the way already described, just replacing $N$ by $K$ in the above discussion. We can do the same for each divisor of $N$. My construction needs all these functions as well.

While this solves the mathematical question I originally asked, giving a set of cyclically invariant polynomials that determine $z$ up to cyclic permutation, it is not very nice from the computational point of view. If one starts with $N$ points, this process gives us something like $N^2$ functions to compute. So, for a thousand points, we need to compute a million functions. I wonder whether there is some smaller collection of cyclically invariant polynomials that could do the same job. Perhaps some application of the euclidean algorithm can find a good set of generators of the semigroup as in Ben's latest contribution.

In the biological application that I have in mind, equations like $p_1(z)$ will in practice never be zero, and so one should be able to use the set of $N$ functions that I gave explicitly at the beginning of this discussion.