Abstract:
For rationally fibred surfaces over Q and also over R, an effective algorithm exists that decides if such a surface has a proper parametrisation. This algorithm uses a diagonalised form of the surface equation. We show, using recent algorithms for quadratic forms, that diagonalisation is not necessary. The resulting algorithm only uses operations on polynomials (as opposed to rational functions), which keeps all occurring degrees small and avoids spurious factors in the discriminant.

Click here for the full text (in PDF).

© ACM, 2006. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation (ISSAC'06, Genova, Italy), July 2006, pp. 340-344, http://doi.acm.org/10.1145/1145768.1145823.

Erratum:
The proof of Theorem 4.2 is wrong. As I realised while preparing my talk for ISSAC'06, there is a big difference between reducing the coefficients of a Gram matrix, and reducing the coefficients of the vectors that generate a module (which is then made into a quadratic form module by means of the usual inner product). The latter is done by the references I give in the proof, and the algorithms there compute roughly the same, and also the same as the Gröbner basis technique used in Schicho's original paper.

For the former, however, I still did not find any algorithm in the literature. The suggestion of adapting Eisenbrand and Rote's method to polynomial coefficients will, of course, work, but recent experiments done with John Cremona seem to indicate that this leads to a rather inefficient algorithm.

However, over polynomial rings it is possible to compute a basis for a quadratic form module that is reduced in the sense of Hermite: if we measure individual entries by their degrees, this means that the basis vectors are ordered by increasing "length" (which is the degree of the corresponding diagonal entry of the Gram matrix); and that the degrees of off-diagonal entries are strictly smaller than the degree of the corresponding diagonal entry. An algorithm for achieving the Hermite reduction is found without effort: the LLL-algorithm is made for it, if we replace the Lovász condition by a simple degree comparison, and do the other obvious adaptations for the polynomial case. In fact, the resulting algorithm also gives a Hermite-reduced basis for integral quadratic forms, but it takes much too long there, which was the reason for introducing the Lovász condition in the first place. Termination and efficiency of the polynomial version are easily proved by analogy to the usual LLL.

Two problems remain: the first is that the LLL algorithm will fail if we encounter a nonzero vector that is a zero of the quadratic form. This is very well possible if we consider arbitrary quadratic forms. In our application, this is only a very happy coincidence, since a zero of the form is exactly what we are after. In the general case, this means that the algorithm will not return a Hermite reduction in all cases.

The second problem is that the algorithm is only efficient in terms of coefficient operations, and coefficient growth is not taken into account. I hope to resolve this issue in the near future.

See also the slides to my ISSAC'06 talk (PDF).