An algorithm for computing an integral basis in an algebraic function field

This paper contains a new method for computing an integral basis for an algebraic function field using Puiseux expansions. The algorithm is very efficient because of the following two ingredients:

1) A good bound (in practice: sharp in most cases) for the number of terms that one needs to compute for the Puiseux expansions.

2) A precise bound for the denominators in the integral basis. A consequence of this bound is that in the intermediate computations the expressions can be truncated at exactly the right spot, every term that does not affect the final result can be skipped. This way the expressions will be small during the computation and hence the algorithm will be fast.

An integral basis is very useful for computations with algebraic curves. It can be used for L(D) computations (instead of using adjoint curves). It contains information about the singularities in a form that is very suitable for computer computations which leads to good efficiency, for example, my parametrization algorithm in Maple is often very efficient.

The algorithm is available in Maple V release 5. The implementation contains some special purpose code for the cases where the discriminant has a factor of multiplicity 2 or 3 (this is not explained in the paper). The Puiseux code, on which the integral basis algorithm is based, also contains improvements over the traditional method, such as a different Newton polygon that can be computed more quickly, and sharp bounds on which terms in the intermediate expressions are necessary and which are not (and so avoiding computing unnecessary terms, which greatly reduces expression swell). These improvements can be found in my implementation but they're not written down.

For the implementation see the files puiseux and integral_basis in the algcurves package.

Download this paper