The computation of puiseux expansions and a quantitative version of runge's theorem on diophantine equations
Cameron L. Stewart, Peter Garth Walsh · 1994
The purpose of this thesis is to study the hypotheses and the conclusions of Runge's theorem on binary diophantine equations. Using a recent quantitative version of Eisenstein's theorem on power series expansions of algebraic functions, a quantitative generalization of Runge's theorem is obtained. In particular, using this quantitative version of Eisenstein's theorem, it is shown that the Newton polygon process computes the singular part of a Puiseux expansion in time which is polynomial in the degrees and in the logarithm of the height of the polynomial defining the algebraic function. A complexity bound for the number of elementary operations to perform this algorithm is computed. As a consequence of this, a polynomial time algorithm to test a bivariate polynomial for irreducibility over a local field is given. A complexity bound for the number of elementary operations required to perform this algorithm is computed. The motivation for the above results comes from the fact that the condition one requires for the generalization of Runge's theorem to hold is that the bivariate polynomial F (x, y) in consideration should be reducible as a polynomial in y with coefficients from the local field Q (($x\sp{-1}$)). Thus, the hypotheses of this general version of Runge's theorem can be verified in polynomial time, which is the first of two purposes of this thesis. The second purpose of this thesis is to compute on upper bound for the absolute value of integer solutions to diophantine equations which are treatable by Runge's method of proof. Using once again the recent quantitative version of Eisenstein's theorem on power series expansions of algebraic functions, a new upper bound for the absolute value of integer solutions to these diophantine equations is computed. Other results on diophantine equations pertaining to Runge's theorem are also obtained. In particular, using Runge's theorem, a quantitative version of a theorem of Skolem is proved. Finally, Runge's method is applied to a class of superelliptic diophantine equations.