Functional Decomposition and Groebner Basis

Jaime Gutierrez and Rosario Rubio San Miguel
Universidad de Cantabria
Departamento de Matematicas, Estadistica y Computacion
Facultad de Ciencias, Avda. Los Castros s/n
Santander, Cantabrria, 39005
Spain
E-mail:jaime@matesco.unican.es

Abstract

The functional decompositon problem for univariate rational functions can be stated as follows (see Zippel (1991)): given an univariate rational function f(x) with coefficients in an arbitrary field $\K$, $f \in \K(x)$, determine whether there exist two rational functions $g, h \in \K(x)$ with degree larger than one, such that f(x)=g(h(x)), and, in the affirmative case, compute them. This problem has several applications, for instance, faithful re-parameterizing unfaithfully parameterized curves, providing a birationality test for subfields of $\K(x)$, computing intermediate fields in a simple purely transcendental field extension $\K$, etc.

The method in Alonso, Gutierrez and Recio (1995) for decomposing a univariate rational function used the concept of near-separated polynomial: to each univariate rational function f(x)=f_n(x)/f_d(x), we associate the near-separated polynomial f_n(x)f_d(y)-f_n(y)f_d(x), The key of the algorithm is based on the following:

``Given two rational functions f(x), h(x), there exists a rational function g(x) such that $f=g\circ h$ if and only if the near-separated polynomial associated to h divides the one associated to f".

The generalization of the decomposition problem to multivariate rational functions seems more involved. Similarly, we translate the above idea to multivariate functional decomposition. Now, to each list of multivariate rational functions $\{f_1(\sub{x}),\dots,f_r(\sub{x})\}$, we consider the near-separated ideal, Ideal $\big( \{f_{in}(\sub x)f_{id}(\sub y)-f_{in}(\sub y)f_{id}(\sub x) \hskip2pt\vert\hskip2pt i=1,\dots,r \}\bigl)$, of the polynomial ring $\K[\sub{x},\sub{y}]$. Using this new concept and the Gröbner basis theory, we get the following theorem. In the polynomial ring $\K[\sub{x},\sub{y}]$ we have:

``If the near-separated ideal associated to $\{f_1,\dots,f_r\}$ is a subset of the one associated to $\{h_1,\dots,h_s\}$, then $\K(f_1(\sub{x}),\dots,f_r(\sub{x}))\subset \K(h_1(\sub{x}),\dots,h_s(\sub{x}))\subset \K(\sub{x})$."

The converse holds if we consider the near-separated ideals over $S^{-1}\K[\sub{x},\sub{y}]$, the ring of fractions of $\K[\sub{x},\sub{y}]$ with denominator S, the multiplicative closed set generated by all the polynomials in the variables $\sub{x}$ and $\sub{y}$.

These results shed a new light on multivariate decomposition problem with application to compute intermediate fields in a purely transcendental field extension $\K$, which is a classical topic in Algebra (see Sweedler (1993)).