Algorithms for near solutions to polynomial equations (Q840709)

Let \(K\) be a field, \(F(x,y)\) a polynomial over \(K\), and \(m\) a nonnegative integer. We say that a polynomial \(g\) over \(K\) is an \(m\)-near solution of \(F(x,y)\) if there exists an element \(c\in K\) such that \(F(x,g)=cx^m\). In this case we say that \(c\) is an \(m\)-value of \(F(x,y)\) corresponding to \(g\). In particular, for \(c=0\), by viewing the equation \(F(x,y)=0\) as a polynomial equation over \(K[x]\) with variable \(y\), every solution in \(K[x]\) of this equation is also an \(m\)-near solution. In this paper, the author provides an algorithm that gives all \(m\)-near solutions of a given polynomial \(F(x,y)\) over \(K\). This algorithm is polynomial time reducible to solving one-variable equations over \(K\). In order to introduce and analyze the algorithm, the author defines the notions of upper and lower approximate solutions of the equation \(F(x,y)=0\), as well as the notion of independent set of upper (lower) approximate solutions. This paper continues his previous work on near solutions to polynomial equations [J. Symb. Comput. 33, No. 2, 239--254 (2002; Zbl 1046.13020); Acta Arith. 123, No. 2, 163--181 (2006; Zbl 1152.11012)].