Hard Cases

Most exciting of all these computations are symbolic computations of Faugère, Rouillier, and Zimmermann and the numerical computations of Verschelde.

My (Sottile's) recent interest in this conjecture was spurred by the communication of the computation of an instance of m,p=4,3 of Faugère, Rouillier, and Zimmermann. They first used FGB to calculate a degree reverse lexicographic Gröbner basis for the polynomial system of Conjecture 1 for m,p=3,4 with s_i=i. This yielded a Gröbner basis of size 32M. They then computed a rational univariate representation (a sophisticated substitute for an eliminant) in two ways. Once using a multi-modular implementation of the FGLM algorithm and a second time using RS, an improvement of the RealSolving software under development. The eliminant had degree 462 and size 3M, thus its general coefficient had 2,000 digits. Using an early implementation of Uspensky's algorithm, they verified that all of its zeroes were real, establishing an instance of Conjecture 1 for m,p=3,4. In the course of this calculation, they found it necessary to rewrite their software.

Also notable is the case m,p=8,2 (also one instance each of 7,2 and 4,3) computed by Jan Verschelde [V] using his implementation of the SAGBI homotopy algorithm in [HSS]. Since the polynomial system of Conjecture 1 was ill-conditioned, he instead used the equivalent system of Conjecture 1 described previously where the rational normal curve is paramerteised by Chebyshev polynomials. These numerical calculations give approximate solutions whose condition numbers determine a neighborhood containing a solution. The solutions of this real system are stable under complex conjugation, so it sufficed to check that each neighbourhood and its complex conjugate were disjoint from all other neighborhoods. This computation took approximately 25 hours on a 166MHz Pentium II processor with 64M running Linux. These algorithms are `embarrassingly parallelizable', and in principle they can be used to check far larger polynomial systems.