Enumerating kth Roots in the Symmetric Inverse Monoid Christopher W. York Dr. Valentin V. Andreev, Mentor Department of Mathematics October 1, 2014 The Symmetric Inverse Monoid
Denoted SIM(n), the symmetric inverse monoid is the set of all partial one-to-one mappings from the set {1,2,,n} onto itself with the operation of composition For example, maps 1 to 5, 2 to itself, 3 to 1, 4 to 3, and 5 to nothing. Cycle and Path Notation Every element in SIM(n) can be expressed as the product of disjoint paths and cycles
Paths map a number to the one next to it and the last number to nothing and are denoted with brackets. For example, [12357] maps 1 to 2, 2 to 3, 3 to 5, 5 to 7, and 7 to nothing Cycles map the last number to the first number and are denoted with parenthesis. For example, (3452) maps 3 to 4, 4 to 5, 5 to 2, and 2 to 3 Length of a path or cycle is the number of numbers in it. For example, [12357] is of length 5.
Raising Elements to a Power k Raising an element in SIM(n) to the th power means applying the mapping unto itself times, creating a skipping by effect For example, This breaks a path into paths of lengths differing by at most 1 Fact: Let where are disjoint paths and/or cycles. Then Definition of kth Root
An element is a kth root of if and only if . For example, in , [123456789] is a 4th root of [159][26][37][48]. The aim is to find formulas to determine the number of kth roots any element of SIM(n). Previous Research Annin et al. [2] first determined whether an element in the symmetric group, an algebraic structure similar to SIM(n), has a kth root
Recently, Annin [1] determined whether an element in SIM(n) has a kth root both papers posed the question of how many kth roots an element has Interlacing Paths Raising a path to the th power breaks it into paths, so creating a th root of an element would be the interlacing of paths in groups of . If all the paths cant be legally interlaced, then there are no th roots of
the element Ex.: The interlacing of [123], [45], [67], and [89] would be [146825793]. Clearly, . The order of paths in the interlacing matters There can only be paths starting with the longest paths and lengths varying by at most 1. The Root Counting Function
The number of distinct th roots an element will be denoted by . This is equivalent to the number of ways to interlace all the paths of in groups of . A Simple Case Let where are disjoint paths of the same length all greater than 1. Then. There are interlacings, whose order doesnt matter
The order within the interlacings does matter A slightly More Complex Case Let where are disjoint paths and the lengths of are equal and is of length 1 less than the others. All lengths are greater than 1. Then . Again, there are interlacings, whose order doesnt matter The smaller path has to be at the end of the interlacing its in
There is a probability that the smaller path will be in a right place An element with two weakly varying lengths Let be the product of disjoint paths where the first paths are equal length and the other paths are of length 1 less those paths. All lengths are greater than 1. The general form of the number of roots is is the probability the smaller paths will be in the right places in the
interlacings Paths of length 1 Fact: whenever . This is the only instance where raising a path to the th power breaks it into less than paths Therefore, proper interlacings of paths only length 1 can have any number of paths as long as its at most .
For example, if and , proper interlacings of s paths can include [12], [1], [134], [1234]. Partitions of the number of paths can represent this Some Helpful Formulas Let where is a product of disjoint paths and is a product of disjoint cycles Then .
Paths and cycles cannot be interlaced Let where and are products of disjoint paths such that all paths in are at longer than those in by at least 2. Then . Paths varying by lengths of more than one cannot be interlaced Further Research Elements with more than two varying lengths
Elements with cycles Elements with weakly varying lengths starting with paths length 1 Creating programs to calculate the number roots Thank you for listening! References [1] Annin, S. et al., On kth roots in the symmetric inverse monoid. Pi Mu Epsilon 13:6 (2012), 321-331.
[2] Annin, S., Jansen, T. and Smith, C., On kth roots in the symmetric and alternating Groups, Pi Mu Epsilon Journal 12:10 (2009), 581-589.