Take the 2-minute tour ×

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?

share|improve this question

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer
Do you mean to sum from i=1 to N in the definition of $p_h$, and the indices called h to add up to a multiple of N? This seems to give an infinite set of cyclic invariants. I was hoping that one could solve this problem with N invariants, which you say is impossible, or with not many more than N, the fewer the better. –  David Epstein Feb 23 '12 at 10:50
Well, you don't need infinitely many. Just vectors that span the positive cone in the subgroup $\{\mathbf{k}\cdot (1,2,\dots,N)\equiv 0\pmod{N}$. –  Ben Webster Feb 24 '12 at 0:41

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.

share|improve this answer
Could you spell this out for someone who has never studied Kummer theory, nor Chevalley-Shepard-Todd? By "rational functions", do you mean the field of rational functions over the complex numbers with one variable? Or are you taking the quotient field of the polynomial ring in N variables? I don't understand the connection between Galois theory and my problem, though I did have the vague feeling they were connected when I posed the problem. I vaguely remember from 50 years ago a correspondence between points and maximal ideals, but it's very vague. A readable source? "A kind of obvious way"??? –  David Epstein Feb 23 '12 at 11:04
What does the quotient look like? For the full symmetric group, one gets complex projective space, the correspondence being between the roots of a polynomial and its coefficients. But I suppose that in the cyclic case there will be some branching. (Don't fully understand what I'm saying here, but it feels right.) –  David Epstein Feb 23 '12 at 11:09
In the application I have in mind (finite approximations to smooth simple closed curves in the plane), singularities in the quotient space will be avoided by insisting that the polygonal approximation has no self-intersections. The open subset of the quotient that survives may not be too easy to work with, but it should be much less ad hoc than what is in the biology literature---one possible important application is to shapes of cells as they appear in images taken with a microscope. –  David Epstein Feb 23 '12 at 11:24
Sorry for the "thinking aloud". The idea I have now added seems to solve the problem "up to a finite number of possibilities". But perhaps it will serve as a better basis for discussion. –  Charles Matthews Feb 23 '12 at 15:49
Ben Webster says that 3 cyclically invariant polynomials cannot solve the problem for n=3. Suppose we look at $L_0$, $L_1^3$, $L_2^3$ and $L_1L_2$. Then the 3 choices of $L_1$ are linked to the 3 choices of $L_2$. This gives 3 choices of $(z_1,z_2,z_3)$, which is EXACTLY right, isn't it? Furthermore we get singularities exactly when $L_1=0$ or $L_2=0$, though I don't really understand what the singularity looks like.If this is right, then it's very nice, and indicates that Ben Webster knew what he was talking about. Any thoughts on $n=4$? –  David Epstein Feb 23 '12 at 19:14

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.

share|improve this answer

Your Answer


