A note on separated factors of separated polynomials (Q1373276)

This paper is directed toward decomposition of univariate rational functions [\textit{C. Alonso, J. Gutierrez} and \textit{T. Recio}, FRAC: A Maple package for computing in the rational function field \(\mathbb{K}(X)\), in R. J. Lopez, ed., Maple V: Mathematics and its application (Birkhäuser, Basel), 107-115 (1994; Zbl 0813.65048); A rational function decomposition algorithm by near-separated polynomials, J. Symb. Comput. 19, 527-544 (1995; Zbl 0840.68048); \textit{R. Zippel}, Rational function decomposition, Proc. ISSAC'91 (ACM Press, New York), 1-6 (1991)] by factorizing bivariate polynomials. Let \(\mathbb{K}\) be an arbitrary field. A non-constant polynomial \(f(x,y)\) in \(\mathbb{K} [x,y]\) is called near-separated if there exist non-zero polynomials \(r(x), u(x)\) in \(\mathbb{K}[x]\) and \(s(y), t(y)\) in \(\mathbb{K}[y]\) such that \(r(x)\) (respectively \(s(y)\)) is not a constant times \(u(x)\) (respectively \(t(y)\)) and \(f(x,y)= r(x)s(y)- t(y) u(x)\). The list \([r(x), s(y), t(y), u(x)]\) is called a representation of \(f(x,y)\). The main result extends to rational functions a theorem [\textit{M. Fried} and \textit{R. MacRae}, On curves with separated variables, Math. Ann. 180, 220-226 (1969; Zbl 0185.28803)] concerning separated factors of separated polynomials. Theorem 1. Let \(f(x)= f_n(x)/ f_d(x)\), \(g(x)= g_n(x)/ g_d(x)\), \(f_1(x)= f_{1n}(x)/ f_{1d}(x)\) and \(g_1(x)= g_{1n}(x)/ g_{1d}(x)\) be non-constant rational functions in \(\mathbb{K}(x)\), given in prime form. Then \[ f_{1n}(x) g_{1d}(y)- g_{1n}(y) f_{1d}(x)\quad\text{divides}\quad f_n(x)g_d(y)- g_n(y)f_d(x) \] in \(\mathbb{K}[x,y]\) if and only if there exists a rational function \(h(x)= h_n(x)/ h_d(x)\) in \(\mathbb{K}(x)\), such that \(f(x)= h(f_1(x))\) and \(g(x)= h(g_1(x))\). The proof of the theorem essentially proceeds in one direction by observing that \((x-y)\) divides \(h_n(x)h_d(y)- h_d(x)h_n(y)\) and in the other direction by using the field-theoretic approach of \textit{M. Fried} and \textit{R. MacRae} (loc. cit.). The analogous result for polynomials was the key to the first polynomial decomposition algorithm [\textit{R. Barton} and \textit{R. Zippel}, Polynomial decomposition algorithms, J. Symb. Comput. 1, 159-168 (1985; Zbl 0605.12012)], and a particular version was the key to a practical rational function decomposition algorithm [\textit{C. Alonso, J. Gutierrez} and \textit{T. Recio}, loc. cit.]. The particular case with \(f=g\), \(f_1=g_1\) clarifies Netto's proof of Lüroth's theorem [cf. \textit{A. Schinzel}, Selected topics on polynomials, Univ. Michigan Press, Ann Arbor (1982; Zbl 0487.12002)] and has been used by \textit{M. Fried} [Global construction of exceptional covers, Contemp. Math. 168, 69-100 (1994; Zbl 0849.12002)]. It is proved that any two representations of a near-separated polynomial are related by a rational linear function, and also a simple relation between the degrees of the polynomial and the elements of its representation. A simple procedure is given to determine whether a polynomial \(f(x,y)\) is near-separated and if so to find its representation. Assume that univariate factors have been removed. Then if \(f(0,0)=0\) we take \(r(x)= f(x,0)\), \(t(y)= -f(0,y)\) and determine the remaining polynomials by solving a linear system. Otherwise, we take \(r(x)= f(x,0)\), \(s(y)= f(0,y)/r(0)\) and let \(g(x,y)= f-rs\). Then, for any constant \(\alpha\) such that \((x-\alpha) \nmid g(x,y)\), the remaining polynomials are given by \(t(y)= g(\alpha,y)\) and \(u(x)= g(x,y)/ t(y)\). Two corollaries give necessary and sufficient conditions for two rational functions to have a common component in their functional decomposition.