Group theory and permutations

Arjen Markus (2 june 2005) Group theory is a very powerful tool in mathematics - it belongs to the field of algebra. You can do all kinds of (mathematically) useful things with it - just pick up any book on the subject.

It is surprisingly simple to use Tcl to do group-theoretical computations, like determining the set of elements generated by one or more "typical" elements - the generators.

In the script below I use permutations as the generators of some group and determine what (sub)group of the complete symmetric group they generate. It is a mere toy, compared to what can be done!

Note: I have not tried to optimise the computations nor do I do any error checking.

 # group_perm.tcl --
 #     Small experiment with group theory and permutations
 #

 # group --
 #     Generate the group from the given generators
 # Arguments:
 #     args      List of permutations, each one a generator
 # Result:
 #     List of elements of the group
 #
 proc group {args} {
     if { [llength $args] > 1 } {
          set generator [lindex $args 0]
          set result    [eval group [lrange $args 1 end]]
          set new       1
          while { $new } {
              set new      0
              set expanded $result
              foreach e $result {
                  set eleft  [combine $e $generator]
                  set eright [combine $generator $e]
                  if { [lsearch $expanded $eleft] < 0 } {
                      lappend expanded $eleft
                      set new 1
                  }
                  if { [lsearch $expanded $eright] < 0 } {
                      lappend expanded $eright
                      set new 1
                  }
             }
             set result $expanded
         }
     } else {
         set generator [lindex $args 0]
         set result    [list $generator]
         set enext     $generator
         set new 1
         while { $new } {
             set new 0
             set enext [combine $generator $enext]
             if { [lsearch $result $enext] < 0 } {
                 lappend result $enext
                 set new 1
             }
         }
     }
     return $result
 }

 # combine --
 #     Combine two permutations
 # Arguments:
 #     p         First permutation
 #     q         Second permutation (applied first)
 # Result:
 #     Permutation p.q
 #
 proc combine {p q} {
     set result {}
     foreach e $q {
         lappend result [lindex $p $e]
     }
     return $result
 }

 # main --
 #    A few simple tests
 #
 puts "Simple exchange - applied twice gives identity:"
 set p {0 2 1}
 puts [combine $p $p]
 puts "Cycle of 3 - applied three times gives identity:"
 set p {1 2 0}
 puts [combine $p $p]
 puts [combine [combine $p $p] $p]
 puts "Cycle of 3 - with inverse gives identity:"
 set q {2 0 1}
 puts [combine $p $q]

 #
 # Now the heavier stuff: create a (sub)group
 #
 puts "Simple subgroup of S3:"
 puts [group {0 2 1}]
 puts "S3 complete:"
 puts [group {1 2 0} {0 2 1}]
 puts "Subgroup of S4:"
 puts [group {1 0 2 3} {0 2 1 3}]
 puts "S4 complete:"
 puts [group {1 0 2 3} {1 2 3 0}]

Magnus is a free and open source Computer Algebra system in Infinite Group Theory, written in C/C++ with a Tcl/Tk front end. It is used worldwide to research problems in Infinite Group Theory.

GAP (Groups, Algorithms, Programming) is a computer algebra system for computational discrete algebra with particular emphasis on computational group theory. It features a user-friendly Tk GUI called sgpviz

Category Mathematics