The Bounds of Skolem Functions and Their Applications

AbstractWe apply an effective version of Hilbert′s Irreducibility Theorem to obtain upper bounds of the Skolem functions for formulas of the form ∀x ∃y ∀z ƒ(x, y, z) ≠ 0 over N or Z, where ƒ is a polynomial. We also apply a result of Matijasevic and Robinson to obtain lower bounds of the Skolem functions for formulas of the form ∀x ∃y ∃z ƒ(x, y, z) = 0. We then use these results to obtain the computational complexities of the winning strategies of diophantine games of length 3 and 4. In addition, we show that if the Generalized Riemann Hypothesis is true, then there is a polynomial time algorithm for the decision problem for diophantine equations with parameters over Z assuming that the degrees of the variables in the equations are bounded. This may be compared with our previous result that without this assumption the decision problem for diophantine equations with parameters is co-NP-complete