## Cyclic n-roots

cyclic [1]

ì
ï
ï
ï
í
ï
ï
ï
î
 x1+x2+···+xn = 0 x1x2+ x2 x3 + ···+xnx1 = 0 ··· x1··· xn-1+ x2··· xn+···+xnx1··· xn-2 = 0 x1x2··· xn = 1

A simplified formulation is obtained in terms of n-1 equations in n-1 new variables by dividing the k-th polynomial by xnk for k=1,..., n. The new variables are yi=xi/xn, i=1, ..., n-1, and the system:

 y1+y2+··· + yn-1 + 1 = 0, y1 y2+ y2 y3 + ···+ y1 = 0, ··· y1··· yn-1+ y2··· yn-1+···+ y1··· yn-2 = 0 y1 y2··· yn-1 = xn-n.

References for this problem can be found in [2].

Characteristics:
• Dimension 0 for n=1,2,3,5,6,7.
• Positive-dimensional variety for n=4,8.
• Degree known for n£ 8.

 n 1 2 3 4 5 6 7 8 degree 1 2 6 16 70 156 924 1152

Degree £ (  2  n - 2 n -1
) (see [5]).

Example 1:
```proc(n)
local i,j,k,kk,polys,factor;

polys := array(1..n);

for i from 1 to n-1 do		# poly
polys[i] := 0;
for j from 1 to n do        # start var
factor := 1;

for k from j to j+i-1 do
if k <= n then factor := factor * x[k];
else kk := k-n; factor := factor * x[kk]; fi;
od;
polys[i] := polys[i] + factor;
od;
od;

polys[n] := 1;
for i from 1 to n do polys[n] := polys[n] * x[i]; od;
polys[n] := polys[n] - 1;
convert(polys,list);

end:
```

Problem: Bound the number of roots.

· Solution by I.Z Emeris, INRIA, Projet SAGA, 2004 Route des Lucioles,BP 93, 06902 Sophia-Antipolis (France), emeris@sophia.inria.fr, (5 May 1995)

Mixed volumes bound the number of isolated roots. The results concern the Lift-Prune algorithm by Emiris and Canny (1995) [4]. Its public implementation is accessible at ftp://www.inria.fr/saga/emiris.

 #isolated mixed Lift-Prune n roots volume CPU time 3 6 6 0s 4 0 16 0s 5 70 70 0s 6 156 156 2s 7 924 924 27s 8 1152 2560 4m 19s = 259s 9 unknown 11016 40m 59s = 2459s 10 unknown 35940 4h 50m 14s = 17414s 11 unknown 184756 38h 26m 44s = 138404s

Table 1: Lift-Prune executed on a DEC Alpha 3300.

Problem: Compute a resultant matrix.

· Solution by I.Z Emeris, INRIA, Projet SAFIR, 2004 Route des Lucioles,BP 93, 06902 Sophia-Antipolis (France), emeris@sophia.inria.fr, 5 May 1995

Sparse resultants essentially produce multiplication tables and reduce the solution of zero-dimensional problems to an eigencomputation. Some preliminaty results on a SUN Sparc 20 follow for the simplified formulation. deg R stands for the total degree of the sparse resultant in the input coefficients, M is the resultant matrix computed by the incremental algorithm [4], column ``greedy'' gives the dimension of the resultant matrix constructed by the greedy algorithm [3].

 n deg R dim M rank M greedy time 4 6 6 5 7 0s 5 20 26 26 32 0s 6 66 102 102 176 3s 7 270 685 627 ³ 1273 1508s

Table 2: The incremental and greedy algorithms.

## References

[1]
D. Bini and B. Mourrain. Polynomial test suite. 1996.

[2]
G. Björck and R. Fröberg. A faster way to count the solutions of inhomogeneous systems of algebraic equations, with applications to cyclic n-roots. J. Symbolic Computation, 12:329--336, 1991.

[3]
J. Canny and P. Pedersen. An algorithm for the Newton resultant. Technical Report 1394, Comp. Science Dept., Cornell University, 1993.

[4]
I.Z. Emiris and J.F. Canny. Efficient incremental algorithms for the sparse resultant and the mixed volume. J. Symbolic Computation, 20(2):117--149, August 1995.

[5]
L. Pottier. Bounds for degree of the n-cyclic system. INRIA Sophia-Antipolis, Manuscript, 1995.