Question: Let (W,S,M) be a Coxeter system, let w be the reduced word of an FC element, and let s\in S. Under what conditions is sw still the reduced word of an FC element? Answer: sw is still the reduced word of an FC element if and only if the following holds: (a) s is not a left descent of w (so sw is still reduced) (b) Let t be the first (==leftmost) letter in w which does not commute with s, let m=M[s,t] and let x_0 be the subword of w starting from (and including) that t. Then x_0 is not equivalent to a word of the form (tst...)w_3, reduced, where the expression inside the parentheses alternates in t,s and has length m-1. [From now on for us, when write a factorizaton w=xy and say it's reduced, we mean l(w)=l(x)+l(y) where l is the Coxeter length function.] Moreover, the condition in (b) is equivalent to the not having the following conditions all satisfied: (1) t is a left descent of x_0; (2) s is a left descent of x_1 (:= x_0-take-away-the-t-from-(1)/x_0-with-the-first-t-removed); (3) t is a left descent of x_2 (:= x_1-take-away-the-s-from-(2)); (4) s is a left descent of x_3 (:= x_2-take-away-the-t-from-(3)); ... (m-1) s/t is not left descent of x_{m-2}. Note that clearly, if (1)--(m-1) all hold, then by pushing the t or s's in (1)--(m) to the left of x_0, we get a reduced factorization (tst...)w_3 of x_0, so (b) holds. Is the converse true? TODO: (1) Prove/correct the answer. (2) Write a function still_reduced(s,w,M) to test if sw is still reduced using (a)+(1)--(m-1). (3) Paste our ealier codes for Problems 1-6 into this worksheet. 

# Problem number 1 from sage.all import * def cox_mat_gen(cox_typ,n):#cox_typ='F', 'H', or 'I', n=integer identifier (Num of gens for type F and H, Number of sides for type I) r""" Get the coxeter matrix by family and subscript for Coxeter groups not covered by Sage's CoxeterMatrix constructor. Supports families F_n, H_n, and I_2(n) INPUT: - ``cox_typ`` -- string; The family of Coxeter Group - ``n`` -- integer; A parameter describing a specific Coxeter group of a family; For families F and H, represents the subscript; for family I represents the parameter I_2(n) OUTPUT: A CoxeterMatrix object with the appropriate entries. EXAMPLES: Generate matrix for I_2(6) :: sage: cox_mat_gen('I', 6) [1 6] [6 1] """ if cox_typ == 'I': A = Matrix.identity(2) for r in range(2): for c in range(2): if r!=c: A[r,c]=n if cox_typ=='H': A = Matrix.identity(n) for r in range(n): for c in range(n): if r!=c: if r==0 and c==1: A[r,c]=5 elif c==0 and r==1: A[r, c] = 5 elif c==r+1 or r==c+1: A[r,c]=3 else: A[r,c]=2 if cox_typ=='F': A = Matrix.identity(n) for r in range(n): for c in range(n): if r!=c: if r==1 and c==2: A[r,c]=4 elif c==1 and r==2: A[r, c] = 4 elif c==r+1 or r==c+1: A[r,c]=3 else: A[r,c]=2 return CoxeterMatrix(A) 

 

from sage.all import * def ld_check(ld,w,M): r""" Determine if a letter is a left descent of a reduced FC word w. INPUT: - ``ld`` -- integer; the letter to test - ``w`` -- tuple; a reduced FC word (== reduced word of an FC element) - ``m`` -- CoxeterMatrix; the matrix of the Coxeter group to which w belongs. OUTPUT: Boolean; whether or not ld is a left descent of w. EXAMPLES: A basic usage :: sage: ld_check(3, (1, 4, 3, 5, 4, 2), CoxeterMatrix(['A', 5])) False sage: ld_check(4, (1, 4, 3, 5, 4, 2), CoxeterMatrix(['A', 5])) True """ k=-1 for i in range(len(w)): if w[i]==ld: k = i break if k==-1: #print(ld, "is not a Left Descent") return False else: for j in w[0:k]: if M[j,ld]!=2: #print(ld, "is not a Left Descent") return False #print(ld, "is a Left Descent") return True 

False

False

ld_check(3, (1, 4, 3, 5, 4, 2), CoxeterMatrix(['A', 5])) 

False

False

# Create the heap of a word w: a Poset on the indices of w. # Use zero_index=True to make the heap on {0, 1, ..., n-1} instead of {1, 2, ..., n} as is default. # Use display_labeling=True to have the elements of the poset be tuples (i, w[i]) that incorporate the letter at each index, useful when examining the heap manually. def make_heap(w, coxeter_matrix, **kargs): r""" Create the heap of a word in a Coxeter group. INPUT: - ``w`` -- tuple; a word - ``coxeter_matrix`` -- CoxeterMatrix; the matrix of the Coxter group in question - ``zero_index``-- keyword argument; boolean (default False); if True, create the poset on the indices {0, 1, ..., n-1} instead of {1, 2, ..., n} - ``display_labeling`` -- keyword argument; boolean (default False); if True, the elements of the poset will be tuples (i, w_i) instead of just the indices. Useful for inspecting manually. OUTPUT: A Poset on the indices of w. EXAMPLES: An example from our notes :: sage: p = make_heap((2, 3, 4, 1, 2, 1), CoxeterMatrix(['A', 4])) sage: p.covering_relations() [[1, 2], [1, 4], [2, 3], [2, 5], [4, 5], [5, 6]] sage: display(p) (In an appropriate environment, a visual display of the Hasse diagram of p) """ zero_index = 'zero_index' in kargs and kargs['zero_index'] display_labeling = 'display_labeling' in kargs and kargs['display_labeling'] # Elements are the indices {1, 2, ..., n} elements = list(range(1, len(w) + 1)) if not zero_index else list(range(len(w))) # Get the letter of w at a certain index, respecting the indexing convention letter = lambda index: w[index-1] if not zero_index else w[index] # The partial order is generated by the relations i \prec j for all i < j with m(w_i, w_j) != 2 relations = [(i, j) for [i, j] in Tuples(elements, 2) if i < j and coxeter_matrix[letter(i), letter(j)] != 2] # Create the poset from the transitive closure of these relations p = Poset((elements, relations)) if not display_labeling: return p else: return p.relabel({ i: (i, letter(i)) for i in elements }) 

def can_word1(w, m): r""" Uses the heap method to determine the canonical word of an FC word. This version doesn't use the heap directly, but instead assigns "levels" to indices/letters by "dropping" them. INPUT: - ``w`` -- tuple; an FC word (== reduced word of an FC element) - ``m`` -- CoxeterMatrix; the matrix of the Coxeter group to which w belongs OUTPUT: tuple; the canonical word of w. EXAMPLES: Get the same canonical word from two equivalent words :: sage: can_word1((1, 4, 3, 5, 4, 2), CoxeterMatrix(['A', 5])) (1, 4, 3, 5, 2, 4) sage: can_word1((4, 1, 5, 3, 2, 4), CoxeterMatrix(['A', 5])) (1, 4, 3, 5, 2, 4) """ letters = set(w) levels_by_index = {} for (i, x) in enumerate(w): neighbors = { y for y in letters if m[x, y] >= 3 } neighbor_levels = { levels_by_index[j] for j in range(i) if w[j] in neighbors } levels_by_index[i] = max(neighbor_levels) + 1 if len(neighbor_levels) > 0 else 1 levels = set(levels_by_index.values()) word = [] for level in sorted(levels): indices = [i for i in levels_by_index.keys() if levels_by_index[i] == level] letters = [w[i] for i in indices] word.extend(sorted(letters)) return tuple(word) 

 

def can_word1b(w, m): r""" Uses the heap method to determine the canonical word of an FC word. This version uses pure analysis of the actual heap poset; using the definition of "level" of an element in terms of chains INPUT: - ``w`` -- tuple; an FC word (== reduced word of an FC element) - ``m`` -- CoxeterMatrix; the matrix of the Coxeter group to which w belongs OUTPUT: tuple; the canonical word of w. EXAMPLES: Get the same canonical word from two equivalent words :: sage: can_word1((1, 4, 3, 5, 4, 2), CoxeterMatrix(['A', 5])) (1, 4, 3, 5, 2, 4) sage: can_word1((4, 1, 5, 3, 2, 4), CoxeterMatrix(['A', 5])) (1, 4, 3, 5, 2, 4) """ h = make_heap(w, m, zero_index=True) # Length of the longest chain in h max_level = h.height() # Keep track of the letters of w on each "level" letters_at_level = { n: [] for n in range(1, max_level + 1) } # The "level" of an element i in h is the longest length of a chain ending at i # (This is really inefficient) for i in h: level = max(len(c) for c in h.chains() if len(c) > 0 and c[-1] == i) # Record that the letter at index i is on this level: letters_at_level[level].append(w[i]) # Proceed upward through the levels, adding the letters on each level in lexicographic (== numeric) order word = [] for n in range(1, max_level + 1): word.extend(sorted(letters_at_level[n])) return tuple(word) 

 

import itertools # Helper functions from last time def is_FC_A(t): l=len(t) for i in range(l-1): 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 def all_words_length_k(n, k): # all tuples of n letters of length k return list(itertools.product(range(1,n+1), repeat=k)) def all_reduced_FC_length_k_A(n, k): # finds all reduced FC words of a given length reduced_FC = set() for w in all_words_length_k(n, k): if is_FC_A(w): reduced_FC.add(w) return reduced_FC # Generates all reduced FC elements of A_n, in canonical form. def fc_elems_A_1(n): k = 1 can_words = {()} M = CoxeterMatrix(['A', n]) while True: FC = all_reduced_FC_length_k_A(n, k) if len(FC) == 0: break for w in FC: can_words.add(can_word1(w,M)) k += 1 return can_words def fc_elems_A_1b(n): k = 1 can_words = {()} M = CoxeterMatrix(['A', n]) while True: FC = all_reduced_FC_length_k_A(n, k) if len(FC) == 0: break for w in FC: can_words.add(can_word1b(w,M)) k += 1 return can_words def fc_elems_A_2(n): k = 1 can_words = {()} M = CoxeterMatrix(['A', n]) while True: FC = all_reduced_FC_length_k_A(n, k) if len(FC) == 0: break for w in FC: can_words.add(can_word2(w, M)) k += 1 return can_words 

method_1 = fc_elems_A_1(4) print(method_1 == fc_elems_A_1b(4)) print(method_1 == fc_elems_A_2(4)) 

True
True

True
True

 

 

def left_descents(w,M): """ This function takes a word w and a the Coxeter matrix as a function m as arguments to determine the left descents of the word. It returns desc_list, the list of left descents, and not_desc_list, the list of the rest of the elements, as a tuple. EXAMPLES:: sage: left_descents((1, 5, 2, 3, 7), m)) ([1, 5, 7], [2, 3]) sage: left_descents((2, 2, 2, 3), m)) ([2, 2, 2], [3]) Note: the second example is not a fully reduced word. """ desc_list = [w[0]] not_desc_list = [] checked = set() for i in range(1, len(w)): v = w[i] if v in checked: not_desc_list.append(v) continue checked.add(v) x = 0 fail = False while x < i: if M[w[x], v] > 2: fail = True not_desc_list.append(v) break x += 1 if fail == False: desc_list.append(v) desc_list.sort() return desc_list, not_desc_list def can_word2(w, M): """This function takes a word, w, and a Coxeter matrix as a function m as arguments. It produces the canonical word of an FC word and returns it as a tuple. EXAMPLES:: sage: can_word2((1, 5, 2, 3, 7), m)) (1, 5, 7, 2, 3) sage: can_word2((2, 2, 2, 3), m)) (2, 2, 2, 3) """ total_descents = [] while len(w) != 0: descents, not_descents = left_descents(w,M) total_descents = total_descents + descents w = not_descents return tuple(total_descents) 

def commutes_through(s, w, M): for t in w: if M[s,t] != 2: return False return True def split(w, loc): return w[:loc], w[loc+1:] def still_reduced_FC(s, w, M): if ld_check(s,w,M): return False loc = -1 t = -1 for i,l in enumerate(w): if M[s,l] != 2: t = l loc = i break if t == -1: return True x = w[loc + 1:] p1 = () # p2 = () for _ in range(M[s,t]-2): try: loc = x.index(s) except: return True p1 = p2 p2, x = split(x, loc) if not commutes_through(s, p1+p2, M): return True s,t = t,s return False 

still_reduced_FC(10, (9,), CoxeterMatrix(['A',18])) 

True

True

def fc_elems(M): n = M.rank() can_words = {()} recent_words = {()} while True: new_words = set() for w in recent_words: for s in range(1,n+1): if still_reduced_FC(s, w, M): new_words.add(can_word2((s,)+w, M)) if len(new_words) == 0: break can_words.update(new_words) recent_words = new_words return can_words 

method_1 == fc_elems(CoxeterMatrix(['A',4])) 

True

True

fc_elems(CoxeterMatrix(['B',3])) 

{(),
 (1,),
 (1, 2),
 (1, 2, 3),
 (1, 2, 3, 2),
 (1, 2, 3, 2, 1),
 (1, 3),
 (1, 3, 2),
 (1, 3, 2, 3),
 (2,),
 (2, 1),
 (2, 1, 3),
 (2, 1, 3, 2),
 (2, 1, 3, 2, 3),
 (2, 3),
 (2, 3, 2),
 (2, 3, 2, 1),
 (3,),
 (3, 2),
 (3, 2, 1),
 (3, 2, 1, 3),
 (3, 2, 1, 3, 2),
 (3, 2, 1, 3, 2, 3),
 (3, 2, 3)}

{(),
 (1,),
 (1, 2),
 (1, 2, 3),
 (1, 2, 3, 2),
 (1, 2, 3, 2, 1),
 (1, 3),
 (1, 3, 2),
 (1, 3, 2, 3),
 (2,),
 (2, 1),
 (2, 1, 3),
 (2, 1, 3, 2),
 (2, 1, 3, 2, 3),
 (2, 3),
 (2, 3, 2),
 (2, 3, 2, 1),
 (3,),
 (3, 2),
 (3, 2, 1),
 (3, 2, 1, 3),
 (3, 2, 1, 3, 2),
 (3, 2, 1, 3, 2, 3),
 (3, 2, 3)}

len(fc_elems(cox_mat_gen('H',6))) 

3185

3185

print(cox_mat_gen('F',5)) 

[1 3 2 2 2]
[3 1 4 2 2]
[2 4 1 3 2]
[2 2 3 1 3]
[2 2 2 3 1]

[1 3 2 2 2]
[3 1 4 2 2]
[2 4 1 3 2]
[2 2 3 1 3]
[2 2 2 3 1]