## Cyclic n-roots

cyclic 

ě
ď
ď
ď
í
ď
ď
ď
î
 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 .

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 ).

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) . 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 , column ``greedy'' gives the dimension of the resultant matrix constructed by the greedy algorithm .

 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


D. Bini and B. Mourrain. Polynomial test suite. 1996.


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.


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


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.


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