\documentclass{article} \usepackage{axiom} \begin{document} \title{grptheory.spad} \author{Timothy Daly} \maketitle \begin{abstract} \end{abstract} \eject \tableofcontents \eject \section{todo} \section{References} \begin{verbatim} john stallings (free groups) topology of finite graphs \end{verbatim} \section{Miller Problem} \begin{verbatim} let R be a finitely generated commutative ring a polynomial ring in 7 variables x1..x7 modulo the ideal generate by these 29 polynomials \end{verbatim} \section{Dihedral Group} \begin{verbatim} Dihedral group D3 = where a = flip over, b = rotate 120 degrees \end{verbatim} \section{The Trivial Group \cite{1}, pp264-265} $$$$ if we let $$R_1 = t^{-1}rtr^{-2}$$ $$S_1 = r^{-1}srs^{-2}$$ $$T_1 = s^{-1}tst^{-2}$$ then by sustitution of $r$ by $R_1$, $s$ by $S_1$, and $t$ by $T_1$ we get: $$R_2 = T_1^{-1}R_1T_1R_1^{-2} = t^2s^{-1}t^{-1}st^{-1}rtr^{-2}s^{-1}tst^{-2}r^2t^{-1}r^{-1}tr^2t^{-1}r^{-1}t$$ $$S_2 = R_1^{-1}S_1R_1S_1^{-2} = r^2t^{-1}r^{-1}tr^{-1}srs^{-2}t^{-1}rtr^{-2}s^2r^{-1}s^{-1}rs^2r^{-1}s^{-1}r$$ $$T_2 = S_1^{-1}T_1S_1T_1^{-2} = s^2r^{-1}s^{-1}rs^{-1}tst^{-2}r^{-1}srs^{-2}t^2s^{-1}t^{-1}st^2s^{-1}t^{-1}s$$ which is given by the presentation: $$$$ Rewrites could either use Todd-Coxeter or Knuth-Bendix \section{Constructing a Presentation} \begin{verbatim} \end{verbatim} \section{Tietze Transformations \cite{2}} \begin{verbatim} \end{verbatim} \section{Representation} \begin{verbatim} What happens if the group is infinite? What happens if the object is a function as in the D3 case? This is a record with two fields, generators and relations. Generators can be represented as records with four fields, The index field is a unique positive integer The name is a symbol The power is an integer The object is anything \end{verbatim} \section{Magnus Abilities} \begin{verbatim} Abelian group Algorithms involving the whole group Compute the canonical decomposition of A Compute the order of A Compute the order of the torsion subgroup of A Compute the primary decomposition of A Compute the torsion-free rank of A Compute the torsion subgroup of A Is A finite? Is A free abelian? Is A trivial? Algorithms involving a subgroup Compute the canonical decomposition for H Compute the index of H in A Compute the isolator of H in A Compute the order of H Compute the order of the torsion subgroup of H Compute the primary decomposition for H Compute the torsion-free rank of H Is H isolated in A? Is H pure in A? Is H = A? is H trivial? Compute a virtual free complement of H in A Algorithms involving a word Compute the canonical decomposition of W Compute the maximal root of W Compute the order of W Compute the p-height of W Find the inverse of W Does W generate a direct summand? Is W a proper power? Is the subgroup gennerated by W pure? Is W trivial in A? Compute the primary decomposition of W Reduce W Algorithms involving words and subgroups Is W in H? Compute the order of W modulo H Algorithms involving Maps Find the inverse of H Compute the order of H Does M extend to a homomorphism Is H an automorphism? Is H an epimorphism? Is H a monomorphism? Algorithms involving two elements Is w1 = w2? Is w1 a power of w2? Compute the product of w1w2 in abelian form Algorithms involving two subgroups Compute the join of H1 and H2 Does H1 contain H2? Is H1 = H2? Is H1 isomorphic to H2? Amalgamated Products Algorithms involving the whole group Compute the canonical decomposition of G abelianized Compute an integral homology group of G Find a finite rewriting system for G Find a ShortLex automatic structure for G Is G free? Is G hyperbolic? Is G metric small cancellation? Is G perfect? Algorithms involving a subgroup Enumerate relators for H Is H abelian? Is H trivial? Algorithms involving a word Compute the centralizer of W in G Compute the cyclic normal form of W Compute the inverse of W in the freely reduced form Compute the maximal root of W in G Compute the normal form of W Compute the reduced form of W Cyclically reduce W Find the i-th initial segment of the freely reduced form of W Find the i-th terminal segment of the freely reduced form of W Freely reduce W Is W a proper power in G? Is W trivial in G? Algorithms involving maps Extend M to a homomorphism Algorithms involving two elements Are W2 and W1 conjugate in F? Compute the product W2*W1 Compute the product W1*W2 Is W2 = W1? Is W1 a proper power of W2? Is W2 a proper power of W1? Make another object Abelian Quotient of G Another Presentation of G Nilpotent Quotient of G Quotient of G Finitely Presented Groups Algorithms involving the whole group Compute the canonical decomposition of G abelianized Compute an integral homology group of G Compute the order of G Compute a system of Schreier representatives for G when G is finite Find a finite rewriting system for G Find a permutation representation of G when G is finite Find a ShortLex automatic structure for G Is G abelian? Is G finite? Is G metric small cancellation? Is G nilpotent? Is G trivial? Algorithms involving a subgroup Compute the index of H in G Compute a presentation for H Compute a Schreier transversal of H in G Enumerate relators for H Find a permutation representation of G on the cosets of H in G Is H abelian? Is H central? Is H nilpotent? Is H trivial? Algorithms involving a word Compute the inverse of W in the freely reduced form Cyclically reduce W Find the i-th initial segment off tthe freely reduced form of W Find the Schreier representative of W Find the i-th terminal segment of the freely reduced form of W Freely reduce W Is W central in G? Is W of finite order in G? Is W trivial in G? Algorithms involving a word and subgroups Find the Schreier representative of W modulo H Algorithms involving maps Does M extend to a homomorphism? Algorithms involving maps and subgroups Compute the image of H under h Algorithms involving maps and words Compute the image of W under h Algorithms involving two elements Are W1 and W2 conjugate in G? Is W1 = W2? Compute the product W1*W2 Free Groups Algorithms involving the whole group Find the n-th element of F Is F automatic? Randomly enumerate automorphisms of F Randomly enumerate automorphisms of F of finite order Algorithms involving a subgroup Compute a finite index subgroup of F with H as a free factor Compute the Nielsen basis for H Compute the normalizer of H in F Compute the rank of H Is H malnormal in F? Is H normal in F? Is H trivial? What is the index of H in F? Algorithms involving a word Compute the centralizer of W in F Compute the inverse of W in freely reduced form Compute the maximal root of W in F Cyclically reduce W Find the i-th initial segment of the freely reduced form of W Find the i-th terminal segment of the freely reduced form of W Freely reduce W Is W a commutator in F? Is W in the commutator subgroup of F? Is W part of a basis in F? Is W a proper power in F? Is W trivial in F? Algorithms involving a word and subgroups Compute the right Schreier representative of W mod H Does a conjugate of W represent an element of H? Does a power of W represent an element of H? Does W represent an element of H? Find the canonical decomposition of W in the Nielsen basis for H Algorithms involving maps Extend M to a homomorphism Algorithms involving two elements Are W2 and W1 conjugate in F? Compute the product W2*W1 Compute the product W1*W2 Is W2 = W1? Make another object Abelian Quotient of F Amalgamated product Another presentation of F Quotient of F Equations Find a solution of E Quadratic Equation Algorithms involving sets Is S part of a basis of F? Algorithms involving homomorphisms and words Algorithms involving homomorphisms Compute the inverse of H Express H as a product of Whitehead automorphisms Is H an automorphism? Is H an epimorphism? Is H an IA-automorphism? Is H an inner automorphism? Is H a monomorphism? Is H of finite order? Algorithms involving tuples Reduce T by Whitehead automorphisms Free nilpotent groups Algorithms involving the whole group Compute a basis of N Find a presentation of N Find a term of lower central series of N Compute the Hirsch number of N Algorithms involving a subgroup Compute a basis for H Compute the Hirsch length of H Compute the index of H in N Find the normal closure of H in N Find the normal closure of H in N (long procedure) Find a presentation of H Is H central in N? Is H normal in N? Algorithms involving a word Compute the canonical decomposition of W Compute the centralizer of W Compute the inverse of W in freely reduced form Compute the maximal root of W Cyclically reduce W Find in which term of the lower central series W lies Freely reduce W Is W central in N? Is W an element of the commutator subgroup of N? Is W a proper power? Is W trivial in N? Algorithms involving a word and subgroups Decompose W in terms of a basis of H Determine whether W lies in H Algorithms involving maps Does M extend to a homomorphism? Find the inverse of H Is H an IA-automorphism? Is H an automorphism? Is H an epimorphism? Algorithms involving two elements Compute the product W1*W2 Compute the product W2*W1 Is W1 = W2? Algorithms involving two subgroups HNN extensions Algorithms involving the whole group Compute the canonical decomposition of G abelianized Compute an integral homology group of G Find a finite rewriting system for G Find a ShortLex automatic structure for G Is G abelian? Is G free? Algorithms involving a subgroup Is H abelian? Is H trivial? Algorithms involving a word Compute the cyclic normal form of W Compute the inverse of W in freely reduced form Compute the maximal root of W in G Compute the normal form of W Compute the reduced form of W Cyclically reduce W Find the i-th initial segment of the freely reduced form of W Find the i-th terminal segment of the freely reduced form of W Freely reduce W Is W a proper power in G? Is W trivial in G? Algorithms involving maps Extend M to a homomorphism Algorithms involving two elements Are W2 and W1 conjugate in F? Compute the product W1*W2 Compute the product W2*W1 Is W2 = W1? Is W1 a proper power of W2? Is W2 a proper power of W1? Make another object Abelian Quotient of G Another Presentation of G Nilpotent Quotient of G Quotient of G Algorithms involving homomorphisms Nilpotent Groups Algorithms involving the whole group Compute the canonical decomposition of G Compute a basis of G Compute the class of G Compute the lower central factors of G Compute the order of G Find a term of lower central series of G Find a polycyclic presentation of G Compute the Hirsch number of G Is G abelian? Is G finite? Is G free nilpotent? Is G trivial? Algorithms involving a subgroup Compute a basis for H Compute the class of H Compute the Hirsch length of H Compute the index of H in G Find the normal closure of H in G Find a presentation of H Is H abelian? Is H central? Is H normal? Is H trivial? Algorithms involving a word Compute the canonical decomposition of W Compute the inverse of W in freely reduced form Compute the order of W Cyclically reduce W Find in which term of the lower central series W lies Freely reduce W Is W central in G? Is W an element of the commutator subgroup of G? Is W trivial in G? Algorithms involving a word and subgroups Decompose W in terms of a basis of H Determine whether W lies in H Algorithms involving maps Does M extend to a homomorphism? Is H an IA-automorphism? Is H an automorphism? Is H an epimorphism? Algorithms involving two elements Compute the product W1*W2 Compute the product W2*W1 Is W1 = W2? Algorithms involving two subgroups Compute the join of H1 and H2 Does H1 contain H2? Is H1 = H2? One Relator Groups Algorithms involving the whole group Compute the canonical decomposition of G abelianized Compute the integral homology of G Enumerate all the consequences of the defining relator of G Find a finite rewriting system of G Find an HNN presentation of G Find a ShortLex automatic structure of G Is G abelian? Is G free? Is G metric small cancellation? Algorithms involving a subgroup Compute a presentation for H in G Enumerate relators for H Is H a Magnus subgroup Algorithms involving a word Compute the inverse of W in freely reduced form Cyclically reduce W Find the i-th initial segment of the freely reduced form of W Find the i-th terminal segment of the freely reduced form of W Freely reduce W Is W trivial in G? Algorithms involving a word and subgroups Does W represent an element of a Magnus subgroup H? Algorithms involving two elements Compute the product W1*W2 Compute the product W2*W1 Are W1 and W2 conjugate in G? Small Cancellation Groups Algorithms involving the whole group Compute the canonical decomposition of G abelianized Compute an integral homology group of G Compute the order of G Find a finite rewriting system for G Find a ShortLex automatic structure for G Is G abelian? Is G finite? Is G trivial? Algorithms involving a subgroup Compute a presentation for H Enumerate relators for H Is H abelian? Is H trivial? Algorithms involving a word Compute the inverse of W in freely reduced form Cyclically reduce W Find the i-th initial segment of a freely reduced form of W Find the i-th terminal segment of a freely reduced form of W Freely reduce W Is W trivial in G? Algorithms involving two elements Compute the product W1*W2 Compute the product W2*W1 Are W1 and W2 conjugate in G? \end{verbatim} \section{Presentation Functions} \subsection{Tietze Transformations} \begin{verbatim} \end{verbatim} \section{Word Functions} \begin{verbatim} given a word: empty? multiply == concat use exp notation identity? unit? length prefix A, subword B, suffix C of ABC cyclic permutation reverse submonoid intersection union operation set subset \end{verbatim} \section{The Algebra} <>= )abbrev category MAGTYPE MagnusType )abbrev category PRESENT Presentation )abbrev category ISGROUP InfiniteSemiGroup )abbrev domain FINPRES FinitePresentation )abbrev domain ELEMENT Element )abbrev domain WORD Word ++ Description: Lowest level category for the magnus type tower Presentation(): Category == with nil ++ Description: Lowest level category for the magnus type tower MagnusType(): Category == Join(BasicType, CoercibleTo OutputForm) with hash: % -> SingleInteger ++ \axiom{hash()} produces a unique number representing this type latex: % -> String ++ \axiom{latex(s)} produces for output the latex form of this expression add hash(s:%):SingleInteger == 0$SingleInteger latex(s:%):String =="\mbox{\bf Unimplemented}" ++ Author: ++ Date Created: ++ Date Last Updated: ++ Basic Functions: ++ Related Constructors: ++ Also See: ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: ++ the class of all multiplicative semigroups, i.e. a set ++ with an associative operation \spadop{*}. Note that this ++ differs from SemiGroup because it does not include equality. ++ ++ Axioms: ++ \spad{associative("*":(%,%)->%)}\tab{30}\spad{ (x*y)*z = x*(y*z)} ++ ++ Conditional attributes: ++ \spad{commutative("*":(%,%)->%)}\tab{30}\spad{ x*y = y*x } InfiniteSemiGroup(): Category == MagnusType() with "*": (%,%) -> % ++ x*y returns the product of x and y. "**": (%,PositiveInteger) -> % ++ x**n returns the repeated product ++ of x n times, i.e. exponentiation. "^": (%,PositiveInteger) -> % ++ x^n returns the repeated product ++ of x n times, i.e. exponentiation. Element(): Exports == Implementation where L ==> List OutputForm Scripts ==> Record(sub:L,sup:L,presup:L,presub:L,args:L) Exports ==> Join(OrderedSet, ConvertibleTo InputForm, ConvertibleTo Element) with new: () -> % ++ new() returns a new element whose name starts with %. new: % -> % ++ new(s) returns a new element whose name starts with %s. resetNew: () -> Void ++ resetNew() resets the internals counters that new() and ++ new(s) use to return distinct elements every time. coerce: String -> % ++ coerce(s) converts the string s to a element. name: % -> % ++ name(s) returns s without its scripts. scripted?: % -> Boolean ++ scripted?(s) is true if s has been given any scripts. scripts: % -> Scripts ++ scripts(s) returns all the scripts of s. script: (%, List L) -> % ++ script(s, [a,b,c,d,e]) returns s with subscripts a, ++ superscripts b, pre-superscripts c, pre-subscripts d, ++ and argument-scripts e. Omitted components are taken to be empty. ++ For example, \spad{script(s, [a,b,c])} is equivalent to ++ \spad{script(s,[a,b,c,[],[]])}. script: (%, Scripts) -> % ++ script(s, [a,b,c,d,e]) returns s with subscripts a, ++ superscripts b, pre-superscripts c, pre-subscripts d, ++ and argument-scripts e. subscript: (%, L) -> % ++ subscript(s, [a1,...,an]) returns s ++ subscripted by \spad{[a1,...,an]}. superscript: (%, L) -> % ++ superscript(s, [a1,...,an]) returns s ++ superscripted by \spad{[a1,...,an]}. argscript: (%, L) -> % ++ argscript(s, [a1,...,an]) returns s ++ arg-scripted by \spad{[a1,...,an]}. elt: (%, L) -> % ++ elt(s,[a1,...,an]) or s([a1,...,an]) returns s subscripted ++ by \spad{[a1,...,an]}. string: % -> String ++ string(s) converts the element s to a string. ++ Error: if the element is subscripted. list: % -> List % ++ list(sy) takes a scripted element and produces a list ++ of the name followed by the scripts. sample: constant -> % ++ sample() returns a sample of % identity: () -> % ++ identity returns the identity element identity?: % -> Boolean ++ identity returns true if arg is the identity element -- "+": (%,%) -> % -- ++ make a new element from two previous words Implementation ==> add count: Reference(Integer) := ref 0 xcount: AssociationList(%, Integer) := empty() istrings:PrimitiveArray(String) := construct ["0","1","2","3","4","5","6","7","8","9"] -- the following 3 strings shall be of empty intersection nums:String:="0123456789" ALPHAS:String:="ABCDEFGHIJKLMNOPQRSTUVWXYZ" alphas:String:="abcdefghijklmnopqrstuvwxyz" hd:String := "*" lhd := #hd ord0 := ord char("0")$Character istring : Integer -> String syprefix : Scripts -> String syscripts: Scripts -> L convert(s:%):InputForm == convert(s pretend String)$InputForm -- convert(s:%):Element == s pretend Element coerce(s:String):% == VALUES(INTERN(s)$Lisp)$Lisp x = y == EQUAL(x,y)$Lisp x < y == GGREATERP(y, x)$Lisp coerce(x:%):OutputForm == outputForm(x pretend Symbol) subscript(sy, lx) == script(sy, [lx, nil, nil(), nil(), nil()]) elt(sy,lx) == subscript(sy,lx) superscript(sy, lx) == script(sy,[nil(),lx, nil(), nil(), nil()]) argscript(sy, lx) == script(sy,[nil(),nil(), nil(), nil(), lx]) syprefix sc == ns: List Integer := [#sc.presub, #sc.presup, #sc.sup, #sc.sub] while #ns >= 2 and zero? first ns repeat ns := rest ns concat concat(concat(hd, istring(#sc.args)), [istring n for n in reverse_! ns]) syscripts sc == all := sc.presub all := concat(sc.presup, all) all := concat(sc.sup, all) all := concat(sc.sub, all) concat(all, sc.args) script(sy: %, ls: List L) == sc: Scripts := [nil(), nil(), nil(), nil(), nil()] if not null ls then (sc.sub := first ls; ls := rest ls) if not null ls then (sc.sup := first ls; ls := rest ls) if not null ls then (sc.presup := first ls; ls := rest ls) if not null ls then (sc.presub := first ls; ls := rest ls) if not null ls then (sc.args := first ls; ls := rest ls) script(sy, sc) script(sy: %, sc: Scripts) == scripted? sy => error "Cannot add scripts to a scripted word" (concat(concat(syprefix sc, string name sy)::%::OutputForm, syscripts sc)) pretend % string e == not scripted? e => PNAME(e)$Lisp error "Cannot form string from non-atomic words." -- Scripts ==> Record(sub:L,sup:L,presup:L,presub:L,args:L) latex e == s : String := (PNAME(name e)$Lisp) pretend String if #s > 1 and s.1 ^= char "\" then s := concat("\mbox{\it ", concat(s, "}")$String)$String not scripted? e => s ss : Scripts := scripts e lo : List OutputForm := ss.sub sc : String if not empty? lo then sc := "__{" while not empty? lo repeat sc := concat(sc, latex first lo)$String lo := rest lo if not empty? lo then sc := concat(sc, ", ")$String sc := concat(sc, "}")$String s := concat(s, sc)$String lo := ss.sup if not empty? lo then sc := "^{" while not empty? lo repeat sc := concat(sc, latex first lo)$String lo := rest lo if not empty? lo then sc := concat(sc, ", ")$String sc := concat(sc, "}")$String s := concat(s, sc)$String lo := ss.presup if not empty? lo then sc := "{}^{" while not empty? lo repeat sc := concat(sc, latex first lo)$String lo := rest lo if not empty? lo then sc := concat(sc, ", ")$String sc := concat(sc, "}")$String s := concat(sc, s)$String lo := ss.presub if not empty? lo then sc := "{}__{" while not empty? lo repeat sc := concat(sc, latex first lo)$String lo := rest lo if not empty? lo then sc := concat(sc, ", ")$String sc := concat(sc, "}")$String s := concat(sc, s)$String lo := ss.args if not empty? lo then sc := "\left( {" while not empty? lo repeat sc := concat(sc, latex first lo)$String lo := rest lo if not empty? lo then sc := concat(sc, ", ")$String sc := concat(sc, "} \right)")$String s := concat(s, sc)$String s anyRadix(n:Integer,s:String):String == ns:String:="" repeat qr := divide(n,#s) n := qr.quotient ns := concat(s.(qr.remainder+minIndex s),ns) if zero?(n) then return ns new() == sym := anyRadix(count()::Integer,ALPHAS) count() := count() + 1 concat("%",sym)::% new x == n:Integer := (u := search(x, xcount)) case "failed" => 0 inc(u::Integer) xcount(x) := n xx := not scripted? x => string x string name x xx := concat("%",xx) xx := (position(xx.maxIndex(xx),nums)>=minIndex(nums)) => concat(xx, anyRadix(n,alphas)) concat(xx, anyRadix(n,nums)) not scripted? x => xx::% script(xx::%,scripts x) resetNew() == count() := 0 for k in keys xcount repeat remove_!(k, xcount) void scripted? sy == not ATOM(sy)$Lisp name sy == not scripted? sy => sy str := string first list sy for i in lhd+1..#str repeat not digit?(str.i) => return((str.(i..#str))::%) error "Improper scripted word" scripts sy == not scripted? sy => [nil(), nil(), nil(), nil(), nil()] nscripts: List NonNegativeInteger := [0, 0, 0, 0, 0] lscripts: List L := [nil(), nil(), nil(), nil(), nil()] str := string first list sy nstr := #str m := minIndex nscripts for i in m.. for j in lhd+1..nstr while digit?(str.j) repeat nscripts.i := (ord(str.j) - ord0)::NonNegativeInteger -- Put the number of function scripts at the end. nscripts := concat(rest nscripts, first nscripts) allscripts := rest list sy m := minIndex lscripts for i in m.. for n in nscripts repeat #allscripts < n => error "Improper script count in word" lscripts.i := [a::OutputForm for a in first(allscripts, n)] allscripts := rest(allscripts, n) [lscripts.m, lscripts.(m+1), lscripts.(m+2), lscripts.(m+3), lscripts.(m+4)] istring n == n > 9 => error "Can have at most 9 scripts of each kind" istrings.(n + minIndex istrings) list sy == not scripted? sy => error "Cannot convert a word to a list if it is not subscripted" sy pretend List(%) sample() == "aElement"::% identity() == " "::% identity?(e) == e = identity() -- (u:% + v:%):% == u ++ Description: The primitive type ++ Author: Tim Daly ++ Date Created: Nov 5, 2002 ++ Date Last Updated: ++ Basic Functions: ++ Related Constructors: ++ Also See: ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: A finite presentation object FinitePresentation(Generators:GEN,Relations:REL): Exports == Implementation where GEN ==>List(Element) REL ==>List(Symbol) PRES ==>Record(generators: GEN, relations: REL) Exports == Presentation() with New: () -> $ ++ \axiom{New()} creates a new, empty presentation New: (GEN,REL) -> $ ++ \axiom{New()} create a new presentation generators: $ -> GEN ++ \axiom{generators(presentation)} returns the generator set relations: $ -> REL ++ \axiom{relations(presentation)} returns the relations set setGenerators: ($,GEN) -> $ ++ \axiom{setGenerators(presentation)} changes the generators ++ of a FinitePresentation setRelations: ($,REL) -> $ ++ \axiom{setRelations(presentation)} changes the relations ++ of a FinitePresentation coerce: % -> OutputForm ++ print the result Implementation == add import GEN import PRES Rep := PRES New():$ == a:=sample()$GEN b:=sample()$REL construct(a,b)$% New(gen:GEN ,rel:REL):$ == construct(gen,rel)$Rep generators(a:%) == a.generators relations(a:%) == a.relations setGenerators(a:%,b:GEN) == setelt(a::Rep,generators,b) a setRelations(a:%,b:REL) == setelt(a::Rep,relations,b) a coerce(a:%):OutputForm == hconcat ["<"::OutputForm, hspace(1), commaSeparate [b::OutputForm for b in generators(a)], hspace(1), "|"::OutputForm, hspace(1), commaSeparate [c::OutputForm for c in relations(a)], hspace(1),">"::OutputForm]$List(OutputForm) ++ Description: A Word is a list of Elements ++ Author: Tim Daly ++ Date Created: Nov 5, 2002 ++ Date Last Updated: ++ Basic Functions: ++ Related Constructors: ++ Also See: ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: A finite presentation object Word(): Exports == Implementation where Exports == with new: () -> % ++ new returns a new word -- coerce: Element -> % -- ++ coerce(Element) takes a word and makes it an element -- coerce: (x:%) -> List OutputForm -- ++ coerce(%) takes a word and prints it "+": (Element,Element) -> % ++ \axiom{\+} creates a new element "+": (Element,%) -> % ++ \axiom{\+} creates a new element -- "+": (%,%) -> % -- ++ \axiom{\+} creates a new element Implementation == SetCategory add Rep := List(Element) new() == list(script("a"::Element,[[],[],[],[]])$Element)$Rep -- coerce(x:%):List(OutputForm) == -- [ for i in 1..#x repeat (x.i)::OutputForm ] -- coerce(w:Element) == list(w)$Rep (u:Element + v:Element) == cons(u,list(v))$Rep (u:Element + v:%):% == cons(u,v)$Rep -- (u:% + v:%):% == cons(u,v)$Rep @ \section{The Input File} The [[new()]] returns a new element with a generated name. <>= )clear all -- should be %A, type Element new()$Element @ The [[new(Element)]] returns a new element with a name constructed from the argument by prefixing it with a percent sign and appending a digit. <>= )clear all -- should be %B, type Element a:=new()$Element -- should be %%B0, type Element new(a)$Element @ The [[resetNew]] function resets the generated names so they start with a capital A again. <>= )clear all -- should be %C, type Element a:=new()$Element -- should be %D, type Element a:=new()$Element -- no output, type Void resetNew()$Element -- should be %A, type Element a:=new()$Element @ The [[coerce(String)]] function takes a string and returns an Element with that name. <>= )clear all -- should be abc, type Element coerce("abc")$Element -- should be a, type Element x:ELEMENT:="abc" @ The [[script?(Element)]] function returns true if the element has scripts, false otherwise. <>= )clear all -- should be %B, type Element aa:=new()$Element -- should be false, type Boolean scripted? aa -- should be -- 3 2 -- %B (5) -- 4 1 -- type Element bb:=script(aa,[[1],[2],[3],[4],[5]]::List(List(OutputForm))) -- should be true, type Boolean scripted? bb @ The [[script(Element,List(List(OutputForm)))]] function takes an unscripted element and a List of Lists of OutputForm. The second argument has the form \begin{verbatim} [list of subscripts, list of superscripts, list of presuperscripts, list of presubscripts, list of arguments] \end{verbatim} so a valid entry is \begin{verbatim} [[1],[2],[3],[4],[5]] \end{verbatim} <>= )clear all -- should be -- 3 2 -- a (5) -- 4 1 -- type Element bb:=script("a",[[1],[2],[3],[4],[5]]::List(List(OutputForm))) -- should be true, type Boolean scripted? bb @ The [[name(Element)]] function returns the internal name of the subscripted element. Here we make a fully scripted element and then ask for its name. <>= )clear all -- should be -- 3 2 -- a (5) -- 4 1 -- type Element bb:=script("a",[[1],[2],[3],[4],[5]]::List(List(OutputForm)))$Element -- find the name name bb @ <>= )clear all -- make a fully subscripted element bb:=script("a",[[1],[2],[3],[4],[5]]::List(List(OutputForm))) -- find the subscripts scripts bb @ <>= )clear all aa:=new()$Element -- add some subscripts bb:=subscript(aa,[1,2,3]) @ <>= )clear all aa:=new()$Element -- add some subscripts bb:=superscript(aa,[1,2,3]) @ <>= )clear all aa:=new()$Element -- add some subscripts bb:=argscript(aa,[1,2,3]) @ <>= -- compile the source )cd /root/work/axiom )compile grptheory.spad <> <> <> <> <> <> <> <> <> <> <> -- create a new element n:Element := "a" -- create the identity element i:Element := identity() -- is an element equal to itself? (n = n)$Element -- ask the same question using the identity? function identity?(n) -- is this element equal to the identity? (n = i)$Element -- ask the same question using the identity? function identity?(i) -- create another set of symbols for the relations y:SYMBOL:="b" b:List(Symbol):=[y] -- construct a Record type ctype:=Record(gen:List(Element),rel:List(Symbol)) -- construct an element of this new type c:=construct(a,b)$ctype -- look at the generators c.gen -- look at the relations c.rel -- now look at a MagnusPresentation fptype:=FinitePresentation(a,b) -- and construct an element m:=New(a,b)$fptype -- ask for the generators generators(m) -- ask for the relations relations(m) -- make a new set of symbols -- note that we use 'a instead of a so we don't get the value of a -- which was defined above. d:=["a","b","c"]$List(Element) f:=['a,'b,'c]$List(Symbol) -- now make a Presentation with generator symbols g:=New(d,f)$fptype -- ask for the generators generators(g) -- ask for the relations relations(g) -- show f g -- show the operations on f )show fptype @ \section{The Spool File} <>= Starts dribbling to grptheory.spool (Wed Nov 6 10:47:43 2002) G82322 (1) -> )read grptheory.input -- create the set of symbols for the generators a:=brace()$Set(Symbol) (1) {} Type: Set Symbol -- create another set of symbols for the relations b:=brace()$Set(Symbol) (2) {} Type: Set Symbol -- construct a Record type ctype:=Record(gen:Set(Symbol),rel:Set(Symbol)) (3) Record(gen: Set Symbol,rel: Set Symbol) Type: Domain -- construct an element of this new type c:=construct(a,b)$ctype (4) [gen= {},rel= {}] Type: Record(gen: Set Symbol,rel: Set Symbol) -- look at the generators c.gen (5) {} Type: Set Symbol -- look at the relations c.rel (6) {} Type: Set Symbol -- now look at a MagnusPresentation fptype:=FinitePresentation(a,b) (7) FinitePresentation(BRACE ,BRACE ) Type: Domain -- and construct an element x:=New()$fptype (8) [{},{}] Type: FinitePresentation(BRACE ,BRACE ) -- ask for the generators generators(x) (9) {} Type: Set Symbol -- ask for the relations relations(x) (10) {} Type: Set Symbol -- make a new set of symbols -- note that we use 'a instead of a so we don't get the value of a -- which was defined above. d:=construct(['a,'b,'c])$Set(Symbol) (11) {a,b,c} Type: Set Symbol --d:=['a,'b,'c]$List(Symbol) -- now make a Presentation with generator symbols f:=New(d,a)$fptype (12) [{a,b,c},{}] Type: FinitePresentation(BRACE ,BRACE ) -- ask for the generators generators(f) (13) {a,b,c} Type: Set Symbol -- ask for the relations relations(f) (14) {} Type: Set Symbol -- show f f (15) [{a,b,c},{}] Type: FinitePresentation(BRACE ,BRACE ) -- show the operations on f )show fptype FinitePresentation(BRACE ,BRACE ) is a domain constructor. Abbreviation for FinitePresentation is FINPRES This constructor is exposed in this frame. Issue )edit /root/work/axiom/grptheory.spad to see algebra source code for FINPRES ------------------------------- Operations -------------------------------- New : () -> % coerce : % -> OutputForm generators : % -> Set Symbol hash : % -> SingleInteger latex : % -> String relations : % -> Set Symbol New : (Set Symbol,Set Symbol) -> % setGenerators : (%,Set Symbol) -> % setRelations : (%,Set Symbol) -> % G82322 (16) -> )spool Finished dribbling to grptheory.spool. @ \section{The Makefile} <<*>>= PAM=grptheory.spad.pamphlet WORK=/home/root/work/axiom all: notangle -Rgrptheory.spad ${PAM} >grptheory.spad notangle -Rgrptheory.input ${PAM} >grptheory.input AXIOMsys <${WORK}/grptheory.input | tee ${WORK}/grptheory.output @ \eject \begin{thebibliography}{99} \bibitem{1} Sims, Charles, {\sl Computation with Finitely Presented Groups}, Encyclopedia of Mathematics and Its Applications No. 48, Cambridge University Press, (1994), ISBN 0-521-43213-8 \bibitem{2} Baumslag, Gilbert, {\sl Topics in Combinatorial Group Theory}, Lectures in Mathematics, pp 47-55, $Birkh\:auser$, (1993), ISBN 3-7643-2921-1, ISBN 0-8176-2921-1 \end{thebibliography} \end{document}