generatingFCelements(2)

""" A word falls into one of four categories: 1. reduced, fc 2. reduced, not fc 3. not reduced, but fc once reduced 3. not reduced, also not fc when reduced When we try to build up all length k fc words from reduced words of length-(k-1) fc elements by adding one letter on the right, Recall Fact 0. s is a right descent of w iff s appears as the last letter in some reduced word of w. Fact 1. If w is the reduced word of an element of length k-1 ands is a generator, then ws is not reduced if and only s is a right descent of w. Fact 2. If w is the reduced word of an fc element, then s is a right descent of w if and only if all letters to the right of the rightmost s in w commute with s. E.g. w = 213245, s = 2 has s as a right descent of w. E.g. w= 13245, s = 3 doesn't have s as a right descent of w. Combining facts 1 and 2, we have: if w is reduced and has length k-1, then for a generator s, ws is a longer (so length-k) fc element if and only if (1) s is not a right descent of w and (2) the new 's' doesn't cause a convex chain ...sts in ws. E.g. w = 213245. Fact 2: right descent set of w = {5, 2}, so w5=2132455=21324, w2= 21345, so w5 and w2 are actually shorter. On the other hand, say we are in A5, 1, 3, 4 are not right descents, so w1 = 2132451, w3 = 2132453, w4 = 2132454 are actually longer than w - they are of length 7. Why we need (2): w1 = 23(121)45, w4 = 2132(454) are not FC anymore. w3 turns out to be still FC. So if the input is w, the only new FC output we want to admit is w3 = 2132453. What would the code require? (a) find the right descents of the input w: easy by Fact 2, have code - s is a right descent of w iff (s in w and t not in w for t a neighbor of s. (b) checking if ws now has a ...sts chain ending in s -- easier than full isFC test in theory, maybe we can replace 'contains_long_braid' in our fc test by 'contains_long_braid_ending_in_s'. (There may be a shortcut to detect if ws has ...sts convex chains, but you have to be very careful, so we'll do it for now.) """ 

import itertools from collections import defaultdict, deque, OrderedDict 

# Cartier--Foata (CF) canonical form: # The CF canonical form of a reduced word w of an FC element is w=w_1w_2...w_k where each w_i is the product of the elements in the left descent set of (w_iw_{i+1}...w_k), with the elements written in increasing numerical order. For example, the CF form for 4153765 in the group A7 is just 1473565. A useful fact is that if w is the reduced word of an FC element, then a generator s in w is in the left descent if and only if all generators to the left of that s commute with s, equivalently, if and only if no neighbor of s in the Coxeter graph appears to its left in w. We'll assume for now that the Coxeter graph is a straight line like in types A and B, so neighbors of s are exactly s-1 and s+1, if they exist. This simplification allows us to omit specifyin the Coxeter matrix. def takeaway(t,x): """ Return the tuple obtained from l by removing the first occurence of x. EXAMPLES: sage: takeaway([1,2,5,2],2) sage: [1,5,2] """ i = t.index(x) return t[:i]+t[i+1:] def is_left_descent(w, s, M): """ Determine if s is a left descent of a fc element w. """ if s not in w: return False else: i = w.index(s) return all(t not in w[:i] for t in neighbors_of(s,M)) def CartierFoata_form(w,M): """ Return the Cartier--Foata canonical form of an FC reduced word w. EXAMPLES: sage: CartierFoata_form((3,1,5,4)) sage: (1,3,5,4) sage: CartierFoata_form((4,3,1,5)) sage: (1,4,3,5) sage: CartierFoata_form((4,1,5,3,7,6,5)) sage: (1,4,7,3,5,6,5) ..NOTE: The code will also work if w is input as a list (the output will still be a tuple). """ l = list(w) cf_form=[] while l != []: ll = l checked = set() cf_factor=[] for s in l: if s not in checked: ind = l.index(s) if is_left_descent(w,s,M): # check if s is 'blocked' cf_factor.append(s) checked.add(s) ll = takeaway(ll,s) cf_form = cf_form + sorted(cf_factor) l = ll return tuple(cf_form) 

def neighbors_of(s,M): # The index set starts at 1, not 0, by convention. """ Find the set of generators adjacent to s via the Coxeter matrix. """ S = M.index_set() return {t for t in S if M[s][t]>2} def long_braids_ending_in(s,M): """ Return all long braids ...sts of length M(s,t)>2. """ long_braids = set() for t in M.index_set(): m = M[s][t] # if m >3, create the long braid ending in s and add it to long_braids def contains_long_braid_ending_in(w,s,M): """ Check if w contains a long braid ...sts of length M(s,t)>2. """ for t in w: if t in neighbors_of(s,M).union({s,}): S = M.index_set() def no_long_braid_ending_in_s_after_commutations(w,s,M): # call this f(w,s,M) """ Check if all words obtained from w by commutation avoids long braids ending in s. """ 

def longer_FC_elements_from(w, M): new_elements =set() S = M.index_set() for s in S: if not is_left_descent(w,s,M): longer_element = (s,)+w if f(w,s,M): new_elements.add(longer_element) 

def fcol_up_to(n,M): """ Generate all FC elements of length up to n in the Coxeter group with Coxeter matrix M. """