FC elements in S4 -- Sage

# [Rachel] The function "words" has arguments s and k, where s is the generating set (which must be a list) and k is the length of the generated words. For k <= 3, "words" # generates all of the reduced words of length k on A_s. Otherwise, "words" provides a shorter list of words that are more likely to be reduced. # global vars newlist = [] def consec(word): r""" Determines if the input tuple has two consecutive letters that are the same. EXAMPLES:: sage: consec((1,2,2)) True """ val = any(word[i]==word[i+1] for i in range(len(word)-1)) #val = any(i==j for i,j in zip(word, word[1:])) return val def bad_pattern(word): r""" Checks the input tuple, which will have no identical consecutive letters, to see if there are obviously unreduced patterns. If the length of the tuple is less than or equal to three, these patterns do not apply. The return value of this function is true if there is a "bad" pattern and false if the word does not contain these patterns. EXAMPLES:: sage: bad_pattern(4, 5, 4, 5, 6) True sage: bad_pattern(4, 2, 4, 1) False sage: bad_pattern(1, 2, 4, 1) False Note that while example three is not fully reduced, it does not have any obviously bad patterns, so it passes the preliminary test. """ if len(word) >= 4: for i in range(0, len(word) - 3): a = word[i] == word[i+2] b = word[i+1] == word[i+3] if a == b: return true else: return false else: return false def words(s,k): """ Takes the generating set s and a word length k as an input, does preliminary check of obviously unreduced words. Returns words that are more likely to be reduced of length k on A_s and do not have any obviously unreduced patterns. EXAMPLES:: sage: words([1, 2, 3], 3) [1, 2, 1] [3, 2, 1] [1, 3, 1] [2, 3, 1] [2, 1, 2] [3, 1, 2] [1, 3, 2] [2, 3, 2] [2, 1, 3] [3, 1, 3] [1, 2, 3] [3, 2, 3] """ wordlist = Tuples(s,k).list() for i in wordlist: if consec(i) == true: pass elif bad_pattern(i) == true: pass else: newlist.append(i) for i in newlist: print(i) length = len(newlist) if length == 0: print("There are no words of length " + str(k) + " on A_" + str(len(s)) + "." ) else: print("There are " + str(length) + " total words of length " + str(k) + " on A_" + str(len(s)) + " with no obvious reducible patterns." )

# [Thomas] The following function takes in a word (implemented as a tuple t) and checks if it's the reduced word of an FC element in type A via the specialization of Stembridges's criteria. It is not necessary to specify the rank (i.e., the number of generators) of the type-A group. from sage.all import * def is_FC_A(t): l=len(t) for i in range(l): for j in range (i+1,l): if t[j]==t[i]:#checking for a+1 and a-1 between close pairs of a if t[i+1:j].count(t[i]+1) != 1 or t[i+1:j].count(t[i]-1) != 1: print(t, "is not FC and Reduced") return False break print(t, "is FC and Reduced") return True t1=(3,2,1,3) t2=(1,2,1) t3=(2,1,4,3,6,2,5) t4=(1,2,2) t5=(2,3,1,2) t6=(2,2) t7=(1,2,3,1) t8=(1,4,5,3,2,1) t9=(2,1,2) t10=(2,4,2) is_FC_A(t1) is_FC_A(t2) is_FC_A(t3) is_FC_A(t4) is_FC_A(t5) is_FC_A(t6) is_FC_A(t7) is_FC_A(t8) is_FC_A(t9) is_FC_A(t10)

((3, 2, 1, 3), 'is not FC and Reduced')
((1, 2, 1), 'is not FC and Reduced')
((2, 1, 4, 3, 6, 2, 5), 'is FC and Reduced')
((1, 2, 2), 'is not FC and Reduced')
((2, 3, 1, 2), 'is FC and Reduced')
((2, 2), 'is not FC and Reduced')
((1, 2, 3, 1), 'is not FC and Reduced')
((1, 4, 5, 3, 2, 1), 'is not FC and Reduced')
((2, 1, 2), 'is not FC and Reduced')
((2, 4, 2), 'is not FC and Reduced')
False

((3, 2, 1, 3), 'is not FC and Reduced')
((1, 2, 1), 'is not FC and Reduced')
((2, 1, 4, 3, 6, 2, 5), 'is FC and Reduced')
((1, 2, 2), 'is not FC and Reduced')
((2, 3, 1, 2), 'is FC and Reduced')
((2, 2), 'is not FC and Reduced')
((1, 2, 3, 1), 'is not FC and Reduced')
((1, 4, 5, 3, 2, 1), 'is not FC and Reduced')
((2, 1, 2), 'is not FC and Reduced')
((2, 4, 2), 'is not FC and Reduced')
False

def words_up_to(n, k): r""" Generate words (as tuples) over {1, ..., n} of length up to k. INPUT: - ``n`` -- integer; specifices the alphabet as {1, ..., n} - ``k`` -- integer; maximum length of words to generate OUTPUT: A Python generator generating the words in order of increasing length in lexicographic order EXAMPLES: A basic usage :: sage: list(words_up_to(2, 2)) [(), (1,), (2,), (1, 1), (1, 2), (2, 1), (2, 2)] """ for w in FiniteWords(n): if len(w) > k: break else: yield tuple(w)

# [Joel] We first computed via wiring diagrams that the longest element in S_4 has length 6. Using Thomas's functions to filter Rachel's list of all words on the generators of S_4 up to length 6, we get the set of all distinct words which are reduced words of FC elements in S_4. redFC = { w for w in words_up_to(3, 6) if is_FC_A(w) }

WARNING: Output truncated!

full_output.txt




((), 'is FC and Reduced')
((1,), 'is FC and Reduced')
((2,), 'is FC and Reduced')
((3,), 'is FC and Reduced')
((1, 1), 'is not FC and Reduced')
((1, 2), 'is FC and Reduced')
((1, 3), 'is FC and Reduced')
((2, 1), 'is FC and Reduced')
((2, 2), 'is not FC and Reduced')
((2, 3), 'is FC and Reduced')
((3, 1), 'is FC and Reduced')
((3, 2), 'is FC and Reduced')
((3, 3), 'is not FC and Reduced')
((1, 1, 1), 'is not FC and Reduced')
((1, 1, 2), 'is not FC and Reduced')
((1, 1, 3), 'is not FC and Reduced')
((1, 2, 1), 'is not FC and Reduced')
((1, 2, 2), 'is not FC and Reduced')
((1, 2, 3), 'is FC and Reduced')
((1, 3, 1), 'is not FC and Reduced')
((1, 3, 2), 'is FC and Reduced')
((1, 3, 3), 'is not FC and Reduced')
((2, 1, 1), 'is not FC and Reduced')
((2, 1, 2), 'is not FC and Reduced')
((2, 1, 3), 'is FC and Reduced')
((2, 2, 1), 'is not FC and Reduced')
((2, 2, 2), 'is not FC and Reduced')
((2, 2, 3), 'is not FC and Reduced')
((2, 3, 1), 'is FC and Reduced')
((2, 3, 2), 'is not FC and Reduced')
((2, 3, 3), 'is not FC and Reduced')
((3, 1, 1), 'is not FC and Reduced')
((3, 1, 2), 'is FC and Reduced')
((3, 1, 3), 'is not FC and Reduced')
((3, 2, 1), 'is FC and Reduced')
((3, 2, 2), 'is not FC and Reduced')
((3, 2, 3), 'is not FC and Reduced')
((3, 3, 1), 'is not FC and Reduced')
((3, 3, 2), 'is not FC and Reduced')
((3, 3, 3), 'is not FC and Reduced')
((1, 1, 1, 1), 'is not FC and Reduced')
((1, 1, 1, 2), 'is not FC and Reduced')
((1, 1, 1, 3), 'is not FC and Reduced')
((1, 1, 2, 1), 'is not FC and Reduced')
((1, 1, 2, 2), 'is not FC and Reduced')
((1, 1, 2, 3), 'is not FC and Reduced')
((1, 1, 3, 1), 'is not FC and Reduced')
((1, 1, 3, 2), 'is not FC and Reduced')
((1, 1, 3, 3), 'is not FC and Reduced')
((1, 2, 1, 1), 'is not FC and Reduced')
((1, 2, 1, 2), 'is not FC and Reduced')
((1, 2, 1, 3), 'is not FC and Reduced')
((1, 2, 2, 1), 'is not FC and Reduced')
((1, 2, 2, 2), 'is not FC and Reduced')
((1, 2, 2, 3), 'is not FC and Reduced')
((1, 2, 3, 1), 'is not FC and Reduced')
((1, 2, 3, 2), 'is not FC and Reduced')
((1, 2, 3, 3), 'is not FC and Reduced')
((1, 3, 1, 1), 'is not FC and Reduced')

...

((3, 3, 1, 3, 2, 1), 'is not FC and Reduced')
((3, 3, 1, 3, 2, 2), 'is not FC and Reduced')
((3, 3, 1, 3, 2, 3), 'is not FC and Reduced')
((3, 3, 1, 3, 3, 1), 'is not FC and Reduced')
((3, 3, 1, 3, 3, 2), 'is not FC and Reduced')
((3, 3, 1, 3, 3, 3), 'is not FC and Reduced')
((3, 3, 2, 1, 1, 1), 'is not FC and Reduced')
((3, 3, 2, 1, 1, 2), 'is not FC and Reduced')
((3, 3, 2, 1, 1, 3), 'is not FC and Reduced')
((3, 3, 2, 1, 2, 1), 'is not FC and Reduced')
((3, 3, 2, 1, 2, 2), 'is not FC and Reduced')
((3, 3, 2, 1, 2, 3), 'is not FC and Reduced')
((3, 3, 2, 1, 3, 1), 'is not FC and Reduced')
((3, 3, 2, 1, 3, 2), 'is not FC and Reduced')
((3, 3, 2, 1, 3, 3), 'is not FC and Reduced')
((3, 3, 2, 2, 1, 1), 'is not FC and Reduced')
((3, 3, 2, 2, 1, 2), 'is not FC and Reduced')
((3, 3, 2, 2, 1, 3), 'is not FC and Reduced')
((3, 3, 2, 2, 2, 1), 'is not FC and Reduced')
((3, 3, 2, 2, 2, 2), 'is not FC and Reduced')
((3, 3, 2, 2, 2, 3), 'is not FC and Reduced')
((3, 3, 2, 2, 3, 1), 'is not FC and Reduced')
((3, 3, 2, 2, 3, 2), 'is not FC and Reduced')
((3, 3, 2, 2, 3, 3), 'is not FC and Reduced')
((3, 3, 2, 3, 1, 1), 'is not FC and Reduced')
((3, 3, 2, 3, 1, 2), 'is not FC and Reduced')
((3, 3, 2, 3, 1, 3), 'is not FC and Reduced')
((3, 3, 2, 3, 2, 1), 'is not FC and Reduced')
((3, 3, 2, 3, 2, 2), 'is not FC and Reduced')
((3, 3, 2, 3, 2, 3), 'is not FC and Reduced')
((3, 3, 2, 3, 3, 1), 'is not FC and Reduced')
((3, 3, 2, 3, 3, 2), 'is not FC and Reduced')
((3, 3, 2, 3, 3, 3), 'is not FC and Reduced')
((3, 3, 3, 1, 1, 1), 'is not FC and Reduced')
((3, 3, 3, 1, 1, 2), 'is not FC and Reduced')
((3, 3, 3, 1, 1, 3), 'is not FC and Reduced')
((3, 3, 3, 1, 2, 1), 'is not FC and Reduced')
((3, 3, 3, 1, 2, 2), 'is not FC and Reduced')
((3, 3, 3, 1, 2, 3), 'is not FC and Reduced')
((3, 3, 3, 1, 3, 1), 'is not FC and Reduced')
((3, 3, 3, 1, 3, 2), 'is not FC and Reduced')
((3, 3, 3, 1, 3, 3), 'is not FC and Reduced')
((3, 3, 3, 2, 1, 1), 'is not FC and Reduced')
((3, 3, 3, 2, 1, 2), 'is not FC and Reduced')
((3, 3, 3, 2, 1, 3), 'is not FC and Reduced')
((3, 3, 3, 2, 2, 1), 'is not FC and Reduced')
((3, 3, 3, 2, 2, 2), 'is not FC and Reduced')
((3, 3, 3, 2, 2, 3), 'is not FC and Reduced')
((3, 3, 3, 2, 3, 1), 'is not FC and Reduced')
((3, 3, 3, 2, 3, 2), 'is not FC and Reduced')
((3, 3, 3, 2, 3, 3), 'is not FC and Reduced')
((3, 3, 3, 3, 1, 1), 'is not FC and Reduced')
((3, 3, 3, 3, 1, 2), 'is not FC and Reduced')
((3, 3, 3, 3, 1, 3), 'is not FC and Reduced')
((3, 3, 3, 3, 2, 1), 'is not FC and Reduced')
((3, 3, 3, 3, 2, 2), 'is not FC and Reduced')
((3, 3, 3, 3, 2, 3), 'is not FC and Reduced')
((3, 3, 3, 3, 3, 1), 'is not FC and Reduced')
((3, 3, 3, 3, 3, 2), 'is not FC and Reduced')
((3, 3, 3, 3, 3, 3), 'is not FC and Reduced')

WARNING: Output truncated!

full_output.txt




((), 'is FC and Reduced')
((1,), 'is FC and Reduced')
((2,), 'is FC and Reduced')
((3,), 'is FC and Reduced')
((1, 1), 'is not FC and Reduced')
((1, 2), 'is FC and Reduced')
((1, 3), 'is FC and Reduced')
((2, 1), 'is FC and Reduced')
((2, 2), 'is not FC and Reduced')
((2, 3), 'is FC and Reduced')
((3, 1), 'is FC and Reduced')
((3, 2), 'is FC and Reduced')
((3, 3), 'is not FC and Reduced')
((1, 1, 1), 'is not FC and Reduced')
((1, 1, 2), 'is not FC and Reduced')
((1, 1, 3), 'is not FC and Reduced')
((1, 2, 1), 'is not FC and Reduced')
((1, 2, 2), 'is not FC and Reduced')
((1, 2, 3), 'is FC and Reduced')
((1, 3, 1), 'is not FC and Reduced')
((1, 3, 2), 'is FC and Reduced')
((1, 3, 3), 'is not FC and Reduced')
((2, 1, 1), 'is not FC and Reduced')
((2, 1, 2), 'is not FC and Reduced')
((2, 1, 3), 'is FC and Reduced')
((2, 2, 1), 'is not FC and Reduced')
((2, 2, 2), 'is not FC and Reduced')
((2, 2, 3), 'is not FC and Reduced')
((2, 3, 1), 'is FC and Reduced')
((2, 3, 2), 'is not FC and Reduced')
((2, 3, 3), 'is not FC and Reduced')
((3, 1, 1), 'is not FC and Reduced')
((3, 1, 2), 'is FC and Reduced')
((3, 1, 3), 'is not FC and Reduced')
((3, 2, 1), 'is FC and Reduced')
((3, 2, 2), 'is not FC and Reduced')
((3, 2, 3), 'is not FC and Reduced')
((3, 3, 1), 'is not FC and Reduced')
((3, 3, 2), 'is not FC and Reduced')
((3, 3, 3), 'is not FC and Reduced')
((1, 1, 1, 1), 'is not FC and Reduced')
((1, 1, 1, 2), 'is not FC and Reduced')
((1, 1, 1, 3), 'is not FC and Reduced')
((1, 1, 2, 1), 'is not FC and Reduced')
((1, 1, 2, 2), 'is not FC and Reduced')
((1, 1, 2, 3), 'is not FC and Reduced')
((1, 1, 3, 1), 'is not FC and Reduced')
((1, 1, 3, 2), 'is not FC and Reduced')
((1, 1, 3, 3), 'is not FC and Reduced')
((1, 2, 1, 1), 'is not FC and Reduced')
((1, 2, 1, 2), 'is not FC and Reduced')
((1, 2, 1, 3), 'is not FC and Reduced')
((1, 2, 2, 1), 'is not FC and Reduced')
((1, 2, 2, 2), 'is not FC and Reduced')
((1, 2, 2, 3), 'is not FC and Reduced')
((1, 2, 3, 1), 'is not FC and Reduced')
((1, 2, 3, 2), 'is not FC and Reduced')
((1, 2, 3, 3), 'is not FC and Reduced')
((1, 3, 1, 1), 'is not FC and Reduced')

...

((3, 3, 1, 3, 2, 1), 'is not FC and Reduced')
((3, 3, 1, 3, 2, 2), 'is not FC and Reduced')
((3, 3, 1, 3, 2, 3), 'is not FC and Reduced')
((3, 3, 1, 3, 3, 1), 'is not FC and Reduced')
((3, 3, 1, 3, 3, 2), 'is not FC and Reduced')
((3, 3, 1, 3, 3, 3), 'is not FC and Reduced')
((3, 3, 2, 1, 1, 1), 'is not FC and Reduced')
((3, 3, 2, 1, 1, 2), 'is not FC and Reduced')
((3, 3, 2, 1, 1, 3), 'is not FC and Reduced')
((3, 3, 2, 1, 2, 1), 'is not FC and Reduced')
((3, 3, 2, 1, 2, 2), 'is not FC and Reduced')
((3, 3, 2, 1, 2, 3), 'is not FC and Reduced')
((3, 3, 2, 1, 3, 1), 'is not FC and Reduced')
((3, 3, 2, 1, 3, 2), 'is not FC and Reduced')
((3, 3, 2, 1, 3, 3), 'is not FC and Reduced')
((3, 3, 2, 2, 1, 1), 'is not FC and Reduced')
((3, 3, 2, 2, 1, 2), 'is not FC and Reduced')
((3, 3, 2, 2, 1, 3), 'is not FC and Reduced')
((3, 3, 2, 2, 2, 1), 'is not FC and Reduced')
((3, 3, 2, 2, 2, 2), 'is not FC and Reduced')
((3, 3, 2, 2, 2, 3), 'is not FC and Reduced')
((3, 3, 2, 2, 3, 1), 'is not FC and Reduced')
((3, 3, 2, 2, 3, 2), 'is not FC and Reduced')
((3, 3, 2, 2, 3, 3), 'is not FC and Reduced')
((3, 3, 2, 3, 1, 1), 'is not FC and Reduced')
((3, 3, 2, 3, 1, 2), 'is not FC and Reduced')
((3, 3, 2, 3, 1, 3), 'is not FC and Reduced')
((3, 3, 2, 3, 2, 1), 'is not FC and Reduced')
((3, 3, 2, 3, 2, 2), 'is not FC and Reduced')
((3, 3, 2, 3, 2, 3), 'is not FC and Reduced')
((3, 3, 2, 3, 3, 1), 'is not FC and Reduced')
((3, 3, 2, 3, 3, 2), 'is not FC and Reduced')
((3, 3, 2, 3, 3, 3), 'is not FC and Reduced')
((3, 3, 3, 1, 1, 1), 'is not FC and Reduced')
((3, 3, 3, 1, 1, 2), 'is not FC and Reduced')
((3, 3, 3, 1, 1, 3), 'is not FC and Reduced')
((3, 3, 3, 1, 2, 1), 'is not FC and Reduced')
((3, 3, 3, 1, 2, 2), 'is not FC and Reduced')
((3, 3, 3, 1, 2, 3), 'is not FC and Reduced')
((3, 3, 3, 1, 3, 1), 'is not FC and Reduced')
((3, 3, 3, 1, 3, 2), 'is not FC and Reduced')
((3, 3, 3, 1, 3, 3), 'is not FC and Reduced')
((3, 3, 3, 2, 1, 1), 'is not FC and Reduced')
((3, 3, 3, 2, 1, 2), 'is not FC and Reduced')
((3, 3, 3, 2, 1, 3), 'is not FC and Reduced')
((3, 3, 3, 2, 2, 1), 'is not FC and Reduced')
((3, 3, 3, 2, 2, 2), 'is not FC and Reduced')
((3, 3, 3, 2, 2, 3), 'is not FC and Reduced')
((3, 3, 3, 2, 3, 1), 'is not FC and Reduced')
((3, 3, 3, 2, 3, 2), 'is not FC and Reduced')
((3, 3, 3, 2, 3, 3), 'is not FC and Reduced')
((3, 3, 3, 3, 1, 1), 'is not FC and Reduced')
((3, 3, 3, 3, 1, 2), 'is not FC and Reduced')
((3, 3, 3, 3, 1, 3), 'is not FC and Reduced')
((3, 3, 3, 3, 2, 1), 'is not FC and Reduced')
((3, 3, 3, 3, 2, 2), 'is not FC and Reduced')
((3, 3, 3, 3, 2, 3), 'is not FC and Reduced')
((3, 3, 3, 3, 3, 1), 'is not FC and Reduced')
((3, 3, 3, 3, 3, 2), 'is not FC and Reduced')
((3, 3, 3, 3, 3, 3), 'is not FC and Reduced')

full_output.txt

def word_to_permutation(w, group): r""" Convert a word to the permutation it represents in a Symmetric Group w/ its Coxeter presentation. INPUT: - ``w` -- tuple; the word to convert - ``group`` -- some (large enough) SymmetricGroup OUTPUT: A PermutationGroupElement from the given group that the word represents EXAMPLES: The singleton tuple (1,) is converted to the adjacent transposition (1,2) in any SymmetricGroup(n) with n >= 2 :: sage: word_to_permutation((1,), SymmetricGroup(4)) (1,2) """ el = group.identity() # Multiply together the adjacent transpositions that the numbers in w represent; # We must do so in reverse order since Sage's symmetric groups use the convention that p * q == p then q for x in reversed(w): # Multiply by the tranposition (x, x+1) el = el * group("({0}, {1})".format(x, x+1)) return el

# [Chase] There are 18 distinct words in S_4 that are reduced words of FC elements print('Number of words that are reduced words of FC elements: ' + str(len(redFC))) S4 = SymmetricGroup(4) fc_permutations = { word_to_permutation(w, S4) for w in redFC } # There are 14 distinct FC permutations in S_4 print('Number of distinct FC elements: ' + str(len(fc_permutations)))

Number of words that are reduced words of FC elements: 18
Number of distinct FC elements: 14

Number of words that are reduced words of FC elements: 18
Number of distinct FC elements: 14

def avoids_321(p): r""" Determines if a permutation avoids the pattern 321. INPUT: - ``p` -- PermutationGroupElement; element of some SymmetricGroup OUTPUT: Boolean; whether or not p avoids 321 EXAMPLES: Basic usage :: sage: S4 = SymmetricGroup(4) sage: x = S4("(1,3)") sage: y = S4("(1,2)") sage: avoids_321(x) False sage: avoids_321(y) True """ for [i, j, k] in Tuples(p.domain(), 3): if i < j < k and p(i) > p(j) > p(k): return False return True

True

True

# [Chase] The FC permutations in S4 are precicely the permutations that avoid the pattern 321. Let's verify that: avoiders = { p for p in S4 if avoids_321(p) } # avoiders is equal as a set to fc_permutations print(avoiders == fc_permutations)

True

True

FC elements in S4

1434 days ago by chme3268