Synopsis of MAGMA program to decompose 
rational functions (Version 14/4/05, revised 12/6/06)

Datatypes needed:

C:=RationalField(); (or any other field of coefficients)
S<x,y>:=PolynomialRing(C,2);
FF<t>:= FunctionField(C);
P<t>:= PolynomialRing(C);
PP<z>:= PolynomialRing(FF);


Functions 

all_comp:=function(f);
//Input:  a rational function f in normal form
//Output: the full list Sep of exponent - vectors
//    of all near - separate divisors of nabla_f
//    the list L of divisors of nabla_f

all_comp_L:=function(L);
//Input:  the list L of factors of nabla_f, f in normal form
//Output: the full list Sep of exponent - vectors
//    of all near - separate divisors of nabla_f
//    the list L of divisors of nabla_f

all_decomps:= function(f)
//Input:  f, a univariate rational function in normal form
//Output: the list of all maximal decompositions of f
//    up to equivalence.

all_decomps_L:= function(L)
//Input:  the list L of irreducible factors of nabla_f
//Output: the list of all maximal decompositions of f
//        up to equivalence.

a_pol:= function(L,v)
//Input:  L, a list of irr factors of nabla_f of a normalized function f,
//        and an exponent vector v
//Output: the corresponding product of irreducible factors
//    (bivariate polynomial used later as a(y,x))

comp_field:= function(g1,g2)
//Input:  rational functions g1,g2
//Output: the normalized Lueroth - generator of the composite field K(g1,g2);

deg:=function(f) 
// Input:  f in FF; Output: degree of f;

enormalize :=function(D,DD,f)
// replaces `normalize' in positive characteristic

etriple:= function(D,DD,a)
// replaces `triple' in positive characteristic

factor_sequence := function(L, elist)
//Input:  L, list of irreducible factors with
//    multiplicities of nabla_f
//    elist, a list of exponent lists describing
//    a sequence a1 | a2 | ... of near separate
//    consecutive divisors of nabla_f
//Output: the corresponding normalized sequence of composition
//    factors of f;
//    Note: elist represents a1 | a2 | a3 | ...
//                           |    |    |
//                           h1   h2'  h3'
//
//    with ai = nabla_hi' and h2' = g2 o h1, h3' = g3 o h2'...
//    h:=(h1,g2,g3,...)

factor_set:=function(f)
//Input:  f in FF, a univariate rational function in normal form
//Output: L, the set of irreducible factors with multiplicities
//        of nabla_f

full_comp := function(h)
//Input:  a list h of rational functions [ h[1],h[2],...,h[i] ]
//Output: the composite function f:=h[i] o h[i-1] o ... o h[1]

full_decomp := function(f)
//Input:  a rational function f (assumed to be normalized)
//Output: some full decomposition of f

full_decomp_L := function(L)
//Input:  the set of irreducible factors of nabla_f
//Output: some full decomposition of normal function f

inter_field_chains:= function(f)
//Input:  f, a univariate rational function
//Output: the list of all maximal chains of
//    intermediate fields M: K(f) <= M <= K(x)

inter_field_chains_L:= function(L)
//Input:  the list L of irreducible factors of nabla_f
//Output: the list of all maximal chains of
//        intermediate fields M: K(f) <= M <= K(x)

inter_field_gens := function(dec_seq)
//Input:  dec_seq, list of comp factors of f in
//    a full decomposition.
//Output: corresponding list of subfield generators.

inter_fields:= function(f)
//Input:  f, a univariate rational function
//Output: the list of all intermediate fields
//        M(h) with K(f) <= M(h) <= K(x).
//
//    The output consists of a list of pairs
//    <v,h>, where h is a normalized generator
//    for M(h) and v is an integer vector with
//    non negative entries.
//    M(h) <= M(g) iff v(g)-v(h) is non-negative.

inter_fields_L:= function(L)
//Input:  the list L of irreducible factors of nabla_f
//Output: the list of all intermediate fields
//        M(h) with K(f) <= M(h) <= K(x).
//
//    The output consists of a list of pairs
//    <v,h>, where h is a normalized generator
//    for M(h) and v is an integer vector with
//    non negative entries.
//    M(h) <= M(g) iff v(g)-v(h) is non-negative.

left := function(M,f) // left action of GL_2 on K(x)\ K
// Input:  f in FF, M matrix in C^2;  Output: M o f;

leftfactor := function(f,h)
// Input: f=p/q and h=r/s in FF, where h is right-factor of f.
// Output: g in FF with f = g o h,

nearsep := function(a)
// Input:  a in S, multiple of y-x without univariate factors,
//     a/(y-x) is a divisor of the Bezoutian of f = f_d/f_n, ie,
//     a is a divisor of Nabla_f = f_d(y)f_n(x) = f_d(x)f_n(y).
// Output: h in FF, boolean b. If b=0, h=t;
//                             if b=1, h=r/s is a right factor of f

normalize :=function(f)
// Input: function f in K(x)\ K
// Output: N:= the normal form of f in left GL_2 - orbit
//       : M:= 2 x 2 matrix with N = M o f.

normalize_decomp := function(h_list)
//normalizes a decomposition list

right := function(f,M)
// right action of GL_2 on K(x); 
// Input:  f in FF, M matrix in C^2;  Output: f^M;

triple:= function(a) 
// Input:  a in S;
// Output: 1 if a satisfies the triple identities for
// Bezoutian. 0 otherwise



Some combinatorial and data functions used in the program 
"all_comps()", which calculates all inequivalent 
decompositions

compare_ge := function(v,w)
//Input:  integer vectors v,w of same length
//Output: 1 if v >= w in the dominance pre - order
//    (ie v >= w iff v-w is non-negative)
//    0 otherwise, -1 if v,w have diff length

equal_list := function(X,Y)
//Input:  X,Y are chains of vectors listed in compatible order.
//        so X <> Y, iff for some (first) i, X[i] <> Y[i]
//Output: 1 if the lists X and Y are equal.
//    0 otherwise

extend_chains := function(CC,r)
//Input:  CC, a list of (all maximal) chains of a subposet
//        S of the poset P of integral vectors (under dominance order)
//    r, an element of P \ S.
//Output: BB, the extended list of all maximal chains of S U { r }
//
//Iterative algorithm: for every C in CC let XC_r be the set of elements in C which
//             are comparable to r. There are two cases:
//             (i)  XC_r = C, in which case C U {r} is a maximal chain
//                  of S U {r} and replaces C in BB.
//             (ii) XC_r < C, in which case C is a maximal chain of
//                  S U {r} and therefore appears in BB.
//             We also need to add to BB the maximal XC_r U {r}'s with
//                     XC_r < C.                     ~~~~~~~

insert_maxs := function(max,CC)
//Input:   max, the set of maximal elements in a subposet S of the poset
//         P of integral vectors (under dominance order)
//     CC, the list of all maximal chains of T:=S \ max
//Output:  newCC, the list of all maximal chains of S
//
//theory:  Every element of newCC must have as last member an element of max.
//     Removing this yields a (possibly non - maximal) chain of T.
//     On the other hand for every c in T there is some s in max with c U {s} in newCC.
//     But these will not give all of newCC. We construct newCC as follows:
//         We first consruct the list newC, which will contain newCC, but also might
//     contain some repetitions and non-maximal chains. In the end this will
//     be straightened out.
//     Here is how to obtain newC:
//     for every c in T and every s in max let c'_s := c' U {s} where c' <= c is the
//     largest subchain of c consisting of elements comparable to s.
//     ( If c'=c, then c'_s is in newCC, and for every c there is some s such that this happens).
//     Every element of newCC is of this form, but not every c'_s is maximal and therefore
//     in newCC. Let newC be the list of all the c'_s.
//         In the last step we remove repetitions and non-maximal elements from newC.
//     The result is newCC.

interval := function(l,u)
//Input:  l,u two integral vectors of same length
//Output: the dominance - interval [l,u] in lex - order,
//    if l <= u. If not l <= u, then the function returns
//    I:=[*l*];

lists_lt := function(X,Y)
//Input: lists X,Y
//Output: 1 if set X is subset of set Y
//    0 otherwise

list2set := function(L)
//Input:  list L
//Output: set containing the elements of L

max_chains := function(S)
//Input:  S, a poset of integral vectors (under dominance)
//Output: the list of all maximal chains in S.

max_chains2 := function(S)
//Input:  S, a poset of integral vectors (under dominance)
//Output: the list of all maximal chains in S.
//    (recursive version)

maximals := function(Set)
//Input:  Set, a poset of integral vectors (under dominance)
//Output: the set of all maximal elements in Set.

next:= function(l,v,u)
// Input: integer vectors l,v,u of the same length
// Output: w the rev-lex - successor of v in the
// "dominance - interval" [l,u];
// If such a successor exists, the function also returns
// a boolean 1; otherwise it returns v and boolean 0.

set2list := function(S)
//Input:  set S
//Output: list containing the elements of S

monodromy:= function(f)
//Input:  f in FF (FF=Q(t))
//Output: M := Monodromy group over Q of f.