Website of David Sevilla

Decomposition of rational functions

WarningThe following text contains mathematical unicode symbols.

WarningThe following text may not reflect the current state of the art.

One can consider intermediate fields in the extension K(x1,…,xn)/K where the x1,…,xn are algebraically independent transcendentals over K. All such intermediate fields are finitely generated, thus an inclusion between two such fields is equivalent to a system of polynomial equations, namely the given by expressing one set of generators in terms of another. Therefore, computational techniques, both theoretical and practical, can be used to study the subfield lattice of these extensions. In particular, given an intermediate field F, we may want to find all the intermediate fields in the original extension that contain F. Actually, finding fields in K that are transcendental over F is easy (if they exist). In [2] we presented an algorithm to compute those fields in the extension which are algebraic over F.

The case n=1 has already a rich structure. All intermediate fields are generated by single rational functions over K (although not uniquely), and the relation

K(f) ⊆ K(h) ⇔ ∃ g such that f = g ∘ h

allows one to translate questions about inclusion of fields into questions of decomposition of rational functions, that is, how to write a function as a composition of simpler ones.

The particular case of polynomial decomposition is a well-studied topic. From the theoretical point of view, its good properties were discovered one century ago by Ritt; in particular, it is known that for any given polynomial f satisfying a certain tameness condition, any two complete decompositions

f = g1 ∘ ⋯ ∘ gr = h1 ∘ ⋯ ∘ hs

(where the gi and the hj are indecomposable) have the same length, and one can transform one decomposition into the other my means of a finite number of steps, which are also well determined.

It is known that these results do not hold for rational functions. In [1] we show one counterexample to the first statement, namely a degree 12 rational function in Q(x) with two decompositions of different length; although their existence in C(x) was known and it is elementary to prove it, this is the first such example with rational coefficients. This function appeared in the context of Monstrous Moonshine, see that section for more information. In a similar fashion we have studied the case of finite field coefficients, see [4].

Considering more computational points of view, there are many algorithms that compute decompositions f = g ∘ h of rational functions with varied efficiency. I developed one such algorithm, described in [9], which is quite fast in practice (although runs in exponential time in the worst case) and later I used it for the computations in Monstrous Moonshine mentioned above.

Most of the known algorithms test many candidates for h, which is a time-consuming process. An approach that may lead to some improvement, which I started during my period as a Ph. D. student, is to use the knowledge about automorphisms of the extensions in order to quickly discard many of them; or to determine at least one such h from one of those automorphisms. See [8] and [3] for an approach.

Other, more theoretical, related computational problem I am interested in is the intersection problem: given rational functions f1 and f2, to decide whether K(f1)∩K(f2) = K and to compute a generator of K(f1)∩K(f2). This is a difficult problem that has generated a good amount of literature, and I feel that part of the computational approach I am involved in may prove fruitful.

Related publications

WarningThese files are downloadable for personal use only. They may not correspond exactly to the published versions.

  1. Building counterexamples to generalizations for rational functions of Ritt's decomposition Theorem (with J. Gutierrez), Journal of Algebra 303 no. 2 (Sep 2006), p. 655-667. ISSN 0021-8693. DOI 10.1016/j.jalgebra.2006.06.015 Download PDF
  2. Computation of unirational fields (with J. Gutierrez), Journal of Symbolic Computation 41 no. 11 (Nov 2006), Special Issue on the Occasion of Volker Weispfenning's 60th Birthday, p. 1222-1244. ISSN 0747-7171. DOI 10.1016/j.jsc.2005.05.009. Download PDF
  3. On decomposition of tame polynomials and rational functions (with J. Gutierrez), Lect. Notes in Comp. Sci. 4194 (Sep 2006), Computer Algebra in Scientific Computing (CASC 2006), p. 219-226. Springer, Berlin. ISBN 978-3-540-45182-2. DOI 10.1007/11870814_18. Download PDF
  4. On Ritt's decomposition Theorem in the case of finite fields (with J. Gutierrez), Finite Fields and their Applications 12 no. 3 (July 2006), p. 403-412. ISSN 1071-5797. DOI 10.1016/j.ffa.2005.08.004 Download PDF
  5. Computation of unirational fields (with J. Gutierrez), extended abstract, Proceedings of the 2005 Algorithms, Algebra and Logic (A3L 2005), p. 129-134. BOD Norderstedt, Germany, 2005. ISBN 3-8334-2669-1. Download PDF
  6. Computing unirational fields of arbitrary transcendence degree (with J. Gutierrez and R. Rubio), extended abstract, Electronic Proceedings of the First Joint Meeting AMS-RSME, June 2003. Link to page Download PDF
  7. On multivariate rational function decomposition (with J. Gutierrez and R. Rubio), Journal of Symbolic Computation 33 no. 5 (May 2002), p. 545-562. ISSN 0747-7171. DOI 10.1006/jsco.2000.0529 Download PDF
  8. Computing the fixing group of a rational function (with J. Gutierrez and R. Rubio), Proceedings of the 5th International workshop on Computer Algebra in Scientific Computing (CASC 2002), p. 159-164. Institüt für Informatik, Technische Universität München, 2002. ISBN 3-9808546-0-4. Download PDF
  9. Unirational fields of transcendence degree one and functional decomposition (with J. Gutierrez and R. Rubio), Proceedings of the 2001 International Symposium on Symbolic and Algebraic Computation (ISSAC 2001), p. 167-175. ACM, New York, 2001. ISBN 1-58113-417-7. doi.acm.org/10.1145/384101.384124 Download PDF