######## Package for computing with polynomials ###### ######## in non commutative indeterminates ###### ######## Procedures definitions ###### noncom[alphabet] := proc() if nargs = 0 then noncom['_ALPHABET'] := [a, b]; else noncom['_ALPHABET'] := sort(args[1]); _ALPHABET := noncom['_ALPHABET']; fi; _ALPHABET; end: noncom[alphabet](): ##################################################### # Given a word w, compute the ordered list of its letters ##################################################### noncom[uncat] := proc(mot) if length(mot) <= 1 then [mot] else zip(proc(x, y) substring(x, y..y) end, [mot $ length(mot)], [$ 1..length(mot)]) fi; end: ##################################################### # Generating all words up to a given length. ##################################################### noncom[all_words] := proc(n) if n = 1 then _ALPHABET else map(proc(z, w) op(map(proc(x, y) y.x end, w, z)) end, noncom[all_words](n-1), _ALPHABET) fi end: ##################################################### # Computing the degree of a polynomial, that is, # the length of the longest word appearing in it. ##################################################### noncom[degree] := proc(poly) if poly = 0 then -infinity elif type(poly, complex) then 0 elif type(poly, string) then length(poly) elif type(poly, `*`) then noncom[degree](op(2, poly)) elif type(poly, `+`) then map(noncom[degree], convert(poly, list)); max(op(")); fi end: ##################################################### # Scalar product on the space of all polynomials. # It is defined on words as the Kronecker delta function. ##################################################### noncom[scalar] := proc(poly1, poly2) if type(poly1, complex) then if type(poly2, complex) then poly1 * poly2 else 0 fi elif type(poly1, string) then if type(poly2, complex) then 0 elif type(poly2, string) then if poly1 = poly2 then 1 else 0 fi elif type(poly2, `*`) then op(1, poly2) * noncom[scalar](poly1, op(2, poly2)) elif type(poly2, `+`) then map(proc(x, y) noncom[scalar](x, y) end, poly2, poly1) else 0 fi elif type(poly1, `*`) then op(1, poly1) * noncom[scalar](op(2, poly1), poly2) elif type(poly1, `+`) then map(proc(x, y) noncom[scalar](x, y) end, poly1, poly2) else 0 fi end: ##################################################### # Concatenation product of two polynomials, # given as linear sums of words. # The procedures also handles ordered pairs of words, # in order to compute in the tensor algebra. # We assume compatibility of parameters. ##################################################### noncom[`&c`] := proc(poly1, poly2) option operator; if type(poly1, complex) or type(poly2, complex) then poly1*poly2 elif type(poly1, string) then if type(poly2, `*`) then op(1, poly2) * cat(poly1, op(2, poly2)) elif type(poly2, string) then cat(poly1, poly2) elif type(poly2, `+`) then map(proc(x, y) noncom[`&c`](y, x) end, poly2, poly1) fi; elif type(poly1, list) then if type(poly2, complex) then poly1 * poly2 elif type(poly2, list) then zip(proc(x, y) noncom[`&c`](x, y) end, poly1, poly2) elif type(poly2, `*`) then op(1, poly2) * noncom[`&c`](poly1, op(2, poly2)) elif type(poly2, `+`) then map(proc(x, y) noncom[`&c`](y, x) end, poly2, poly1) else 0 fi elif type(poly1, `*`) then op(1, poly1) * noncom[`&c`](op(2, poly1), poly2) elif type(poly1, `+`) then map(noncom[`&c`], poly1, poly2) else 0 fi; end: ##################################################### # Computation of the miror image of a polynomial ##################################################### noncom[`&~`] := proc(poly) if type(poly, complex) then poly elif type(poly,string) then if length(poly) = 1 then poly else ``.(noncom[`&~`](substring(poly, 2..length(poly)))).(substring(poly, 1..1)) fi elif type(poly, `*`) then op(1, poly) * noncom[`&~`](op(2, poly)) elif type(poly, `+`) then map(noncom[`&~`], poly) fi end: ########################################################### # Computation of the coefficient of a word in a polynomial ########################################################### noncom[coeff] := proc(mot, poly) option remember; if mot = 1 then if type(poly, complex) then poly elif type(poly, string) then 0 elif type(poly, `*`) then 0 elif type(poly, `+`) then map(proc(x, y) noncom[coeff](y, x) end, poly, mot); convert(", `+`); fi; elif type(mot, string) then if type(poly, complex) then if mot = 1 then poly else 0 fi elif type(poly, string) then if mot = poly then 1 else 0 fi elif type(poly, `*`) then if mot = op(2, poly) then op(1, poly) else 0 fi elif type(poly, `+`) then map(proc(x, y) noncom[coeff](y, x) end, poly, mot); convert(", `+`); fi; else NULL fi; end: ##################################################### # Computation of the left cancellation operator: # (poly1)^{-1}(poly2) # This is a derivation for the shuffle product. ##################################################### noncom[`&l_`] := proc(poly1, poly2) option operator; if type(poly1, complex) then poly1 * poly2 elif type(poly1, string) then if type(poly2, complex) then 0 elif type(poly2, string) then if length(poly1) > length(poly2) or substring(poly2, 1..length(poly1)) <> poly1 then 0 else substring(poly2, length(poly1)+1..length(poly2)) fi; elif type(poly2, `*`) then op(1, poly2) * noncom[`&l_`](poly1, op(2,poly2)) elif type(poly2, `+`) then map(proc(x, y) noncom[`&l_`](y, x) end, poly2, poly1) fi; elif type(poly1, `*`) then op(1, poly1) * noncom[`&l_`](op(2, poly1), poly2) elif type(poly1, `+`) then map(noncom[`&l_`], poly1, poly2) fi; if " = `` then 1 else " fi; end: noncom[`&r_`] := proc(poly1, poly2) options operator; if type(poly2, complex) then poly1 * poly2 elif type(poly2, string) then if type(poly1, complex) then 0 elif type(poly1, string) then if length(poly2) > length(poly1) or substring(poly1, length(poly1)-length(poly2)+1..length(poly1)) <> poly2 then 0 else substring(poly1, 1..length(poly1)-length(poly2)) fi; elif type(poly1, `*`) then op(1, poly1) * noncom[`&r_`](op(2,poly1), poly2) elif type(poly1, `+`) then map(proc(x, y) noncom[`&r_`](y, x) end, poly1, poly2) fi; elif type(poly2, `*`) then op(1, poly2) * noncom[`&r_`](op(2, poly2), poly1) elif type(poly2, `+`) then map(noncom[`&r_`], poly2, poly1) fi; if " = `` then 1 else " fi; end: ##################################################### # Returns a procedure computing the fox derivative # with respect to a letter ##################################################### noncom[fox] := proc(lettre, poly) if type(poly, complex) then 0 elif type(poly, string) then convert(map(proc(x) if nops(x) = 0 then 1 else cat(op(x)) fi end, map(proc(x, y) subsop(x=NULL, y) end, map(proc(x, y, z) if op(x, y) = z then x fi end, [$1..length(poly)], uncat(poly), lettre), uncat(poly) )), `+`) elif type(poly, `*`) then op(1, poly) * fox(lettre, op(2, poly)) elif type(poly, `+`) then map(proc(x, y) fox(y, x) end, poly, lettre) else 0 fi end: ###### This part of the package develops a set of ######### ###### procedures to compute shuffle products of ######### ###### non commutative polynomials. We use the tree ####### ###### representation of a polynomial. It realizes ####### ###### the simple identity: ######## # ###### P = (P, 1) + sum_{a \in '_ALPHABET'} a &l_ P ######## ###### where &l_ is the left cancellation operator. ####### ######################################################### # Converting a polynomial to a tree. # ######################################################### noncom[`shuffle/poly2tree`] := proc(poly) if type(poly,complex) then [poly] elif type(poly, string) then [0, op(map(noncom[`shuffle/poly2tree`], map(proc(x,y) noncom[`&l_`](x, y) end, noncom['_ALPHABET'], poly)) )] elif type(poly, `*`) then noncom[`shuffle/multree`](op(1, poly), noncom[`shuffle/poly2tree`](op(2, poly))) else [noncom[`shuffle/constcoeff`](poly), op(map(noncom[`shuffle/poly2tree`], map(proc(x,y) noncom[`&l_`](x,y) end, noncom['_ALPHABET'], poly)) )] fi end: ######################################################### # Converting a tree to a polynomial. # ######################################################### noncom[`shuffle/tree2poly`] := proc(arb) if nops(arb) = 1 then op(arb) else op(1,arb) + convert(zip(noncom[`&c`], noncom['_ALPHABET'], map(noncom[`shuffle/tree2poly`], [op(2..nops(arb),arb)]) ),`+`) fi end: ######################################################### # Multiplying a polynomial in tree form by a scalar. # ######################################################### noncom[`shuffle/multree`] := proc(scalar, tree) if scalar = 0 then [0] elif nops(tree) = 1 then [scalar*op(tree)] else [scalar*op(1,tree), op(map(proc(x,y) noncom[`shuffle/multree`](y,x) end, [op(2..nops(tree),tree)], scalar)) ] fi end: ######################################################### # Grabbing the constant coefficient of a polynomial # # (to put it at the root of the tree). # ######################################################### noncom[`shuffle/constcoeff`] := proc(poly) map(proc(x) if type(x, complex) then x else 0 fi end, poly) end: ######################################################### # Computing the sum of two polynomials given as trees. ######################################################### noncom[`shuffle/sumtrees`] := proc(tree1, tree2) if nops(tree1) = 1 then if nops(tree2) = 1 then [op(tree1)+op(tree2)] else [op(tree1)+op(1, tree2), op(2..nops(tree2),tree2)] fi elif nops(tree2) = 1 then [op(1, tree1)+op(tree2), op(2..nops(tree1),tree1)] else [op(1,tree1)+op(1,tree2), op(zip(noncom[`shuffle/sumtrees`],[op(2..nops(noncom['_ALPHABET'])+1, tree1)], [op(2..nops(noncom['_ALPHABET'])+1, tree2)])) ] fi end: ######################################################### # The shuffle product of two polynomials. We make use # # of the fact that the left cancellation operator is # # a derivation with respect to the shuffle product. # ######################################################### noncom[`shuffle/shuff_trees`] := proc(tree1, tree2) if nops(tree1) = 1 then noncom[`shuffle/multree`](op(tree1),tree2) elif nops(tree2) = 1 then noncom[`shuffle/multree`](op(tree2),tree1) else [op(1,tree1)*op(1,tree2), op(map(proc(k, x) noncom[`shuffle/sumtrees`]( noncom[`shuffle/shuff_trees`](op(k, op(1,x)), op(2,x)), noncom[`shuffle/shuff_trees`](op(1,x),op(k, op(2,x))) ) end, [i$i=2..nops(noncom['_ALPHABET'])+1], [tree1,tree2] ) ) ] fi end: noncom[`&s`] := proc(poly1, poly2) option operator; noncom[`shuffle/shuff_trees`](noncom[`shuffle/poly2tree`](poly1), noncom[`shuffle/poly2tree`](poly2)); noncom[`shuffle/tree2poly`]("); end: noncom[`<`] := proc(poly1, poly2) options operator; if type(poly1, complex) or type(poly2, complex) then 0 elif type(poly1, string) then if length(poly1) = 1 then noncom[`&c`](poly1, poly2) else noncom[`&c`](substring(poly1, 1..1), noncom[`&s`](substring(poly1, 2..length(poly1)), poly2) ) fi elif type(poly1, `*`) then noncom[`<`](op(2, poly1), poly2) * op(1, poly1) elif type(poly1, `+`) then map(proc(x, y) noncom[`<`](y, x) end, poly1, poly2) fi end: noncom[`&rt`] := proc(poly1, poly2) options operator; if type(poly1, complex) or type(poly2, complex) then 0 elif type(poly2, string) then if length(poly2) = 1 then noncom[`&c`](poly1, poly2) else noncom[`&c`](noncom[`&s`](poly1, substring(poly2, 1..length(poly2)-1)), substring(poly2, length(poly2)..length(poly2))) fi elif type(poly2, `*`) then noncom[`&rt`](poly1, op(2, poly2)) * op(1, poly2) elif type(poly2, `+`) then map(proc(x, y) noncom[`&rt`](y, x) end, poly2, poly1) fi end; ######## Definition of help functions associated ######## ######## with procedures of the package ######## `help/text/noncom` := TEXT( `HELP FOR: Introduction to the noncom package`, ``, `CALLING SEQUENCE:`, ` (args)`, ` noncom[](args)`, ``, `SYNOPSIS: `, `- To use a noncom function,`, ` either define that function alone using the command`, ` with(noncom, ), or define all noncom functions`, ` using the command with(noncom). Alternatively, invoke`, ` the function using the long form noncom[].`, ` This long form notation is necessary whenever there is a`, ` conflict between a package function name and another function`, ` used in the same session.`, ``, `- The functions available are:`, ``, ` all_words degree coeff`, ` &c &l_, &r_, &~`, ` shuffle/constcoeff shuffle/multree shuffle/poly2tree`, ` shuffle/shuff_trees shuffle/sumtrees shuffle/tree2poly`, ` &s, &rt, <`, ``, `- The package also uses a global variable noncom['_ALPHABET'].`, ` See noncom['_ALPHABET'] and noncom[alphabet] for more information.`, ``, `- For more information on a particular function see noncom[].`, ``, `- The package deals with computations on non commutative`, ` polynomials. That is, polynomials with non commuting`, ` indeterminates. A good introduction to the subject is:`, ``, ` LOTHAIRE M., Combinatorics on Words, Addison-Wesley, 1982.`, ``, ` More specialized references are:`, ``, ` BERSTEL J., REUTENAUER C., Formal Series and Their Languages,`, ` EATCS Monographs on Comp. Sci., Springer-Verlag, 1988.`, ``, ` REUTENAUER C., Free Lie Algebras, Oxford University Press, 1993.`, ``, ` We have tried to keep with notations used in the last reference.`, ``, ` Non commutative polynomials form an algebra, namely, the algebra`, ` of the free monoid (on a given alphabet). They are linear sums of words.`, ` This representation is called the linear representation of the`, ` polynomial. One may also use a tree representation for the polynomial`, ` in analogy to the tree representation for the free monoid.`, ` This tree representation is not to be explicitely used,`, ` although there are no impossibility to do so.`, ` Polynomials are converted into their tree representation`, ` for computing shuffle products. These conversions are`, ` transparent to the user.`, ``, `- For example, to compute the concatenation product of two`, ` polynomials P1 and P2, one could type:`, ``, ` with(noncom, &c); P1 &c P2;`, `` ): `help/noncom/text/alphabet` := TEXT( ``, `HELP FOR: alphabet, procedure for initializing and/or`, ` changing the underlying alphabet.`, ``, `SYNOPSIS:`, `- The algebra of polynomials with non commutative indeterminates`, ` is a free associative algebra. It is custom to define it`, ` starting with an alphabet A = {a, b, ...} of indeterminates.`, ``, `- The default value, and often sufficient for computations,`, ` is {a, b}. We make use of a global variable _ALPHABET`, ` that contains the value of the current underlying alphabet.`, ` To change its value, invoke the procedure alphabet(L),`, ` where L is a new list of indeterminates to be used as letters.`, ``, ` The user should be warned that it is assumed that letters`, ` of the underlying alphabet are chosen among the usual`, ` latin alphabet {a, b, c, ..., x, y, z},`. ` It is wisdom to set it at the beginning of a session and leave it`, ` unchanged (especially when computing shuffle products).`, ``, `EXAMPLES:`, `> _ALPHABET;`, ``, ` [a, b]`, ``, `> alphabet([x, y, z]);`, ``, ` [x, y, z]`, ``, `> _ALPHABET;`, ``, ` [x, y, z]`, ``, `SEE ALSO: noncom[_ALPHABET].`, `` ): `help/noncom/text/_ALPHABET` := TEXT( ``, `HELP FOR: _ALPHABET, global variable defining the underlying alphabet`, ``, `SYNOPSIS:`, `- The algebra of polynomials with non commutative indeterminates`, ` is a free associative algebra. It is custom to define it`, ` starting with an alphabet A = {a, b, ...} of indeterminates.`, ``, `- The default value, and often sufficient for computations,`, ` is {a, b}. Its value may be changed using the procedure`, ` noncom[alphabet].`, ``, `EXAMPLES:`, `> _ALPHABET;`, ``, ` [a, b]`, ``, `SEE ALSO: noncom[alphabet].`, `` ): `help/noncom/text/uncat` := TEXT( `HELP FOR: uncat, a procedure for decomposing a word`, ` into the list of its letters.`, ``, `CALLING SEQUENCE:`, ` uncat(w)`, ``, `PARAMETERS`, `- w, any noncommutative word`, ``, `SYNOPSIS:`, `- The function returns a list formed of the letters`, ` of the word w. Note that it does not rely on the value`, ` of the underlying alphabet.`, ``, `EXAMPLES:`, `> uncat(abcab);`, ``, ` [a, b, c, a, b]`, ``, ``, `SEE ALSO: cat, noncom[alphabet], noncom[_ALPHABET].`, `` ): `help/noncom/text/degree` := TEXT( ``, `HELP FOR: degree, function to compute the degree of a`, ` non commutative polynomial.`, ``, `CALLING SEQUENCE:`, ` degree(P)`, ``, `PARAMETERS:`, ` P - a polynomial with non commutative indeterminates`, ` given in linear form (see help(noncom) for details).`, ``, `SYNOPSIS:`, `- The function returns the degree of a polynomials,`, ` that is, the length of the longest word appearing in it.`, ` As usual, the degree of the zero polynomial is -infinity.`, ``, `EXAMPLES:`, `> degree(abb - 4*abbab + 2);`, ``, ` 5`, ``, `> degree(0);`, ``, ` - infinity`, `` ): `help/noncom/text/all_words` := TEXT( ``, `HELP FOR: all_words, a function for generating all words,`, ` of a given length.`, ``, `CALLING SEQUENCE:`, ` all_words(n)`, ``, `PARAMETERS`, `- n, an integer`, ``, `SYNOPSIS:`, `- The function will generate words up to the given length`, ` using the global variable noncom['_ALPHABET'].`, ``, `EXAMPLES:`, `> _ALPHABET;`, ``, ` [a, b]`, ``, `> all_words(2);`, ``, ` [a, b, aa, ba, ab, bb]`, ``, `> all_words(3);`, ``, ` [a, b, aa, ba, ab, bb, aaa, baa, aba, bba, aab, bab, abb, bbb]`, `` ): `help/noncom/text/degree` := TEXT( ``, `HELP FOR: degree, a function for computing the degree,`, ` of a polynomial.`, ``, `CALLING SEQUENCE:`, ` degree(P)`, ``, `PARAMETERS`, `- P, a non commutative polynomial`, ``, `SYNOPSIS:`, `- The function returns the maximal length of words`, ` appearing in the polynomial P.`, ``, `EXAMPLES:`, `> P := 3*abb - 2*abab + 1;`, ``, ` P := 3 abb - 2 abab + 1`, ``, `> degree(P); `, ``, ` 4`, ``, `> degree(a + 3*b);`, ``, ` 1`, ``, `> degree(1);`, ``, ` 0`, ``, `> degree(0);`, ``, ` - infinity`, `` ): `help/noncom/text/degree` := TEXT( ``, `HELP FOR: scalar, a function for computing the scalar,`, ` product of non comutative polynomials.`, ``, `CALLING SEQUENCE:`, ` scalar(P, Q)`, ``, `PARAMETERS`, `- P, Q, polynomials in non commutative indeterminates.`, ``, `SYNOPSIS:`, `- The function computes the scalar product of two polynomials.`, ` Words form an orthonormal basis for this scalar products.`, ``, `EXAMPLES:`, `> scalar(abb, abb);`, ``, ` 1`, ``, `> scalar(abb, abab);`, ``, ` 0`, ``, `> P := 3*abb - 2*abab + 1;`, ``, ` P := 3 abb - 2 abab + 1`, ``, `> Q := abb - 2 * abab + ab;`, ``, ` Q := abb - 2 abab + ab`, `` ): `help/noncom/text/&c` := TEXT( ``, `HELP FOR: &c, concatenation product`, ``, `CALLING SEQUENCE:`, ` P1 &c P2`, ``, `PARAMETERS`, ` P1, P2 - polynomials with non commutative indeterminates`, ` given in linear form (see help(noncom) for details).`, ``, `SYNOPSIS:`, `- The function computes the concatenation product of two`, ` non commutative polynomials. When P1 and P2 are simple`, ` words, this product coincides with the usual product in`, ` the free monoid. The product is in fact a bilinearization`, ` of the latter.`, ``, `- Polynomials with more than one term must be listed between`, ` parentheses for the product to be properly computed.`, ``, `EXAMPLES:`, `> (ab - 2) &c (a + b - c);`, ``, ` aba + abb - abc - 2 a - 2 b + 2 c`, ``, `> P1 := ab - 2;P2 := a + b - c;`, ``, ` P1 := ab - 2`, ``, ` P2 := a + b - c`, ``, `> P1 &c P2;`, ``, ` aba + abb - abc - 2 a - 2 b + 2 c`, ``, `See also: concat, concatenation or dot operator .`, `` ): `help/noncom/text/coeff` := TEXT( ``, `HELP FOR: coeff, a function to compute the coefficient`, ` of a word in a polynomial.`, ``, `CALLING SEQUENCE:`, ` coeff(w, P)`, ``, `PARAMETERS`, ` w - a word,`, ` P - a polynomials with non commutative indeterminates`, ``, `SYNOPSIS:`, `- The function looks for the word w in the polynomial P`, ` and returns its coefficient if found.`, ``, `EXAMPLES:`, `> P;`, ``, ` 3 abb - 2 abab + 1`, ``, `> coeff(abb, P);`, ``, ` 3`, ``, `> coeff(a, P);`, ``, ` 0`, ``, `> coeff(2*a, P);`, ``, `` ): `help/noncom/text/&~` := TEXT( ``, `HELP FOR: &~, miror image of a non commutative polynomial`, ``, `CALLING SEQUENCE:`, ` &~(P)`, ``, `PARAMETERS`, ` P - a polynomial with non commutative indeterminates`, ` given in linear form (see help(noncom) for details).`, ``, `SYNOPSIS:`, `- The function, when applied to a word, returns the miror`, ` image of the word, that is, the word obtained by reading`, ` it from right to left. It is extended to polynomials`, ` by linearity.`, ``, `EXAMPLES:`, `> &~(abab - 4*bab + 2);`, ``, ` baba - 4 bab + 2`, `` ): `help/noncom/text/&l_` := TEXT( ``, `HELP FOR: &l_, (left) cancellation operator on non commutative polynomials`, ``, `CALLING SEQUENCE:`, ` P1 &l_ P2`, ``, `PARAMETERS`, `- P1, P2 - polynomials with non commutative indeterminates`, ` given in linear form (see help(noncom) for details).`, ``, `SYNOPSIS:`, `- When P1 = u, P2 = v are words, the function returns the unique`, ` word w such that v = uw, if it exists. It returns 0 if it does not.`, ` The function computes the bilinear extension of this action`, ` to non commutative polynomials.`, ``, `EXAMPLES:`, `> P1 := a - b + 2; P2 := ab - abb + 3;`, ``, ` P1 := a - b + 2`, ``, ` P2 := ab - abb + 3`, ``, `> P1 &l_ P2;`, ``, ` b - bb + 2 ab - 2 abb + 6`, ``, `` ): `help/noncom/text/&r_` := TEXT( ``, `HELP FOR: &r_, (right) cancellation operator on non commutative polynomials`, ``, `CALLING SEQUENCE:`, ` P1 &r_ P2`, ``, `PARAMETERS`, `- P1, P2 - polynomials with non commutative indeterminates`, ` given in linear form (see help(noncom) for details).`, ``, `SYNOPSIS:`, `- When P1 = u, P2 = v are words, the function returns the unique`, ` word w such that u = wv, if it exists. It returns 0 if it does not.`, ` The function computes the bilinear extension of this action`, ` to non commutative polynomials.`, ``, `EXAMPLES:`, `> P1 := a - b + 2; P2 := ab - abb + 3;`, ``, ` P1 := a - b + 2`, ``, ` P2 := ab - abb + 3`, ``, `> P1 &r_ P2;`, ``, ` - 2 abb + 3 a - 3 b + 6`, ``, `` ): `help/noncom/text/coeff` := TEXT( ``, `HELP FOR: coeff(w, P), a function to get the coefficient of`, ` a word in a polynomial.`, ``, `CALLING SEQUENCE:`, ` coeff(w, P)`, ``, `PARAMETERS`, `- w a word, P a polynomial with non commutative indeterminates.`, ``, `SYNOPSIS:`, `- The function returns the coefficient of the word w if it appears`, ` with a non null coefficient in P, otherwise it returns NULL.`, ``, `EXAMPLES:`, `> coeff(ab, 3*abb - 2);`, ``, ` 0`, ``, `> coeff(abb, 3*abb - 2);`, ``, ` 3`, ``, `> coeff(1, 3*abb - 2);`, ``, ` -2`, `> coeff(abb - 2, 2*ab - 1);`, ``, `` ): `help/noncom/text/fox` := TEXT( ``, `HELP FOR: fox(x, P), a function to compute the fox derivative of`, ` a polynomial with respect to a letter x.`, ``, `CALLING SEQUENCE:`, ` fox(x, P)`, ``, `PARAMETERS`, `- x a letter, P a polynomial with non commutative indeterminates.`, ``, `SYNOPSIS:`, `- The function computes the fox derivative of P with respect to`, ` the letter x. The derivative of a word w may be combinatorially`, ` described as follows: erase an occurence of a letter x in w,`, ` everywhere possible.`, ``, `EXAMPLES:`, `> P;`, ``, ` 3 abb - 2 abab + 1`, ``, `> fox(a, P);`, ``, ` 3 bb - 2 bab - 2 abb`, ``, `> fox(a, bb + 2);`, ``, ` 0`, ``, `> fox(a, aaaaab);`, ``, ` 5 aaaab`, `` ): `help/noncom/text/&s` := TEXT( ``, `HELP FOR: &s, shuffle product of polynomials in non commutative`, ` indeterminates.`, ``, `CALLING SEQUENCE:`, ` P1 &s P2`, ``, `PARAMETERS`, `- P1, P2 - polynomials with non commutative indeterminates`, ` given in linear form (see help(noncom) for details).`, ``, `SYNOPSIS:`, `- The shuffle product may be recursively defined on words`, ` following the rule u &s v = a(u_1 &s v) + b(u &s v_1),`, ` where it is assumed that u = au_1 and v = bv_1 are non`, ` empty words. This product is associative, commutative.`, ` The empty word is the identity element for this product.`, ``, `- Using the above rule to compute shuffle product of high`, ` degree polynomials is time consuming. We use a tree representation`, ` for polynomials, that is we implement polynomials as trees,`, ` using the identity: P = (P, 1) + sum_{a \in _ALPHABET} a &l_ P.`, ` In other words, monomials (words) of a polynomial are sorted according`, ` to their first letter. For example, one may write:`, ``, ` bba + ab - 3 + b - 2 aa`, ` as:`, ` -3 + a (b - 2a) + b (ba + 1),`, ` and so forth.`, ``, ` We use the _ALPHABET global variable and order these components.`, ` The recursive tree decomposition associated with the above polynomial is:`, ``, ` -3`, ` /\\`, ` / \\`, ` / \\`, ` 0 1`, ` /\\ /\\`, ` / \\ / \\`, ` -2 1 0 0`, ` / \\`, ` / \\`, ` 1 0`, ` We warn the user that the function may behave strangely if the`, ` underlying alphabet does not coincide with the set of letters`, ` appearing in the polynomials P1 and P2. See the examples.`, ``, `EXAMPLES:`, ` P1 := ab - 2; P2 := a + b; `, ``, ` P1 := ab - 2`, ``, ` P2 := a + b`, ``, `> P1 &s P2; `, ``, ` - 2 a + 2 aab + aba + 2 abb + bab - 2 b`, ``, `> _ALPHABET;`, ``, ` [a, b]`, ``, `> a &s d;`, ``, ` 0`, ``, ``, `SEE ALSO: noncom[shuffle/poly2tree], noncom[shuffle/tree2poly],`, ` noncom[shuffle/shuff_trees].`, `` ): `help/noncom/text/&rt` := TEXT( ``, `HELP FOR: &rt, (right) chronological product of polynomials`, ` in non commutative indeterminates.`, ``, `CALLING SEQUENCE:`, ` P1 &rt P2`, ``, `PARAMETERS`, `- P1, P2 - polynomials with non commutative indeterminates`, ` given in linear form (see help(noncom) for details).`, ``, `SYNOPSIS:`, `- The (right) chronological product may be recursively defined on words`, ` following the rule u &rt v = ((u &rt v_1) + (v_1 &rt u)) &c a,`, ` where it is assumed that v = av_1 is a non empty word,`, ` and where &c denotes the concatenation product.`, ` This product is not associative nor commutative but.`, ` satisfies the identity:`, ` P &rt (Q &rt R) = (P &rt Q + Q &rt P) &rt R.`, ` The empty word is a right identity element for this product.`, ``, ` This product is related to the shuffle product.`, ``, `EXAMPLES:`, `> ab &rt a;`, ``, ` aba`, ``, `> a &rt ab; `, ``, ` 2 aab`, ``, `> (a + 2*ab) &rt (ab - 1);`, ``, ` 2 aab + 4 aabb + 2 abab`, ``, `SEE ALSO: noncom[&c]`, `` ): `help/noncom/text/<` := TEXT( ``, `HELP FOR: <, (left) chronological product of polynomials`, ` in non commutative indeterminates.`, ``, `CALLING SEQUENCE:`, ` P1 < P2`, ``, `PARAMETERS`, `- P1, P2 - polynomials with non commutative indeterminates`, ` given in linear form (see help(noncom) for details).`, ``, `SYNOPSIS:`, `- The (left) chronological product may be recursively defined on words`, ` following the rule u < v = ((u < v_1) + (v_1 < u)) &c a,`, ` where it is assumed that v = av_1 is a non empty word,`, ` and where &c denotes the concatenation product.`, ` This product is not associative nor commutative but.`, ` satisfies the identity:`, ` (P < Q) < R = P < (R < Q + Q < R).`, ` The empty word is a left identity element for this product.`, ``, ` This product is related to the shuffle product.`, ``, `EXAMPLES:`, `> ab < a;`, ``, ` aab + aba`, ``, `> a < ab;`, ``, ` aab`, ``, `> (a + 2*ab) &rt (ab - 1);`, ``, ` 2 aab + 4 aabb + 2 abab`, ``, `> (ab - 1) &rt (a + 2*ab);`, ``, ` aba - a - 2 ab + 4 aabb + 2 abab`, ``, `SEE ALSO: noncom[&c]`, `` ): save ``.`noncom.m`; quit;