Star operations

# Determines if letter s is a left-descent of w, a reduced word of an FC element in the Coxeter group with matrix m def is_left_descent_fc(s, 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 """ try: i = w.index(s) return not any(m[x,s] >= 3 for x in w[:i]) except: return False def left_descents_fc(w, m): return set(x for x in w if is_left_descent_fc(x, w, m)) def get_coxeter_matrix(family, n): 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 family == 'F' and n > 4: m = matrix(ZZ, n, n, lambda i, j: 1 if i == j else 3 if abs(i - j) == 1 else 2) m[1,2] = 4 m[2,1] = 4 return CoxeterMatrix(m) elif family == 'H' and n > 4: m = matrix(ZZ, n, n, lambda i, j: 1 if i == j else 3 if abs(i - j) == 1 else 2) m[0,1] = 5 m[1,0] = 5 return CoxeterMatrix(m) elif family == 'I': m = matrix(ZZ, 2, 2, lambda i, j: 1 if i == j else n) return CoxeterMatrix(m) else: return CoxeterMatrix([family, n]) # Uses the left-descents method to determine the canonical word of an FC word w in Coxeter group w/ matrix m def can_word(w, m): r""" Uses the left-descents method to determine the canonical word of an FC word w in Coxeter group w/ matrix m. 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) """ cur_word = list(w) out_word = [] while len(cur_word) > 0: # Get the left descents of the remaining word as a set left_descents = left_descents_fc(cur_word, m) # Move them to the front in lexicographic order out_word.extend(sorted(list(left_descents))) for x in left_descents: # Remove the first occurence of each cur_word.remove(x) return tuple(out_word) # Determines if sw is still a reduced word of an FC element given an FC word w. def still_reduced_fc(s, w, m): r""" Returns whether the word w is still reduced and fully commutative after prepending the letter s. w is assumed to be reduced and fully commutative. INPUT: - ``s`` -- integer; the generator letter to be prepended to w. - ``w`` -- integer tuple; the original reduced FC word to prepend s to. - ``M`` -- CoxeterMatrix; the matrix representing the Coxeter Group that s and w are elements of. OUTPUT: boolean, whether sw is reduced and FC or not. EXAMPLES: sage: M = CoxeterMatrix(['A',4]) sage: still_reduced_FC(1, (2,1), M) false sage: still_reduced_FC(1, (3,1), M) false sage: still_reduced_FC(1, (2,3), M) true """ if is_left_descent_fc(s, w, m): return False # Find the first letter in w that doesn't commute with s. (j, t) = next(((i, x) for (i, x) in enumerate(w) if m[s,x] >= 3), (None, None)) if j is None: return True u = list(w[j:]) for i in range(m[s,t] - 1): letter = t if i % 2 == 0 else s if is_left_descent_fc(letter, u, m): u.remove(letter) else: return True return False def fc_elts(m): r""" Obtains the set of (canonical words of) FC elements in the Coxeter group with matrix m. INPUT: - ``m`` -- CoxeterMatrix; the matrix of the Coxeter group. OUTPUT: set; the set of canonical words of FC elements. EXAMPLES: sage: fc_elts(CoxeterMatrix(['A', 3])) sage: {(1, 2), (3, 2), (1, 3), (1, 3, 2), (1,), (3, 2, 1), (2,), (3,), (2, 1, 3, 2), (2, 1), (1, 2, 3), (), (2, 3), (2, 1, 3)} """ n = m.rank() fc_canonical_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): sw = can_word((s,) + w, m) new_words.add(sw) if len(new_words) == 0: break fc_canonical_words.update(new_words) recent_words = new_words return fc_canonical_words 

def coset_decomposition_left_fc(w, J, m): r""" Obtains the coset decomposition of a reduced FC word w in the Coxeter group with matrix m. Writes w uniquely as w_J * w^J, where w_J is in <W_J>. INPUT: - ``w`` -- tuple; the word to decompose - ``J`` -- set of integers; the subset of the generators with respect to which the decomoposition will be performed - ``m`` -- CoxeterMatrix; the matrix of the Coxeter group to which w and J belong OUTPUT: length-2 tuple containing the word w_J (the J-string) in the first entry, and w^J in the second. w_J * w^J == w. EXAMPLES: sage: coset_decomposition_left_fc((1, 6, 2, 5, 4, 6, 5), (5, 6), CoxeterMatrix(['B', 6])) sage: ((6, 5, 6), (1, 2, 4, 5)) """ left = [] # The J-string right = list(w) # The remainder while True: x = next((x for x in J if is_left_descent_fc(x, right, m)), None) if x is not None: left.append(x) right.remove(x) else: return (tuple(left), tuple(right)) def coset_decomposition_right_fc(w, J, m): (left, right) = coset_decomposition_left(tuple(reversed(w)), J, m) return (tuple(reversed(right)), tuple(reversed(left))) 

 

coset_decomposition_left_fc((1, 4, 3, 5, 4, 2), (4, 5), get_coxeter_matrix('A', 5)) 

((4, 5), (1, 3, 4, 2))

((4, 5), (1, 3, 4, 2))

def left_star_fc(direction, w, J, m): r""" Performs the left upper or lower star operation of w with respect to the pair of non-commuting generators J, if possible. INPUT: - ``direction`` -- integer; +1 for upper star and -1 for lower star - ``w`` -- tuple; the word to act on - ``J`` -- set of length 2; a pair of non-commuting generators with respect to which the star operations are defined. - ``m`` -- CoxeterMatrix; the matrix of the Coxeter group to which w and J belong OUTPUT: None if the star operation is not defined on w; a tuple that is the resulting word otherwise. EXAMPLES: sage: left_star_fc(+1, (1, 4, 3, 5, 4, 2), (1, 2), CoxeterMatrix(['A', 5])) (2, 1, 4, 3, 5, 4, 2) sage: left_star_fc(+1, (2, 1, 4, 3, 5, 4, 2), (1, 2), CoxeterMatrix(['A', 5])) None sage: left_star_fc(-1, (2, 1, 4, 3, 5, 4, 2), (1, 2), CoxeterMatrix(['A', 5])) (1, 4, 3, 5, 4, 2) """ mst = m[J[0], J[1]] (left, right) = coset_decomposition_left_fc(w, J, m) # left is the J-string if direction > 0 and 1 <= len(left) <= mst - 2: # Increase the length of the J-string other = next(x for x in J if not left[0] == x) return (other,) + left + right elif direction < 0 and 2 <= len(left) <= mst - 1: # Decrease the length of the J-string return left[1:] + right else: # This star operation is not defined on w return None 

def left_star_closure_fc(w, m, directions={-1, +1}): r""" Obtains the left (upper|lower|both) star closure of a reduced FC word w in the Coxeter group with matrix m. INPUT: - ``w`` -- tuple; the word to act on - ``m`` -- CoxeterMatrix; the matrix of the Coxeter group to which w and J belong - ``directions`` -- subset of {-1, +1}; default {-1, +1}; whether to take the closure under upper, lower, or both stars. OUTPUT: set; the set of canonical (FC) words in the left star closure of w. EXAMPLES: sage: left_star_closure_fc((1, 2), get_coxeter_matrix('I', 4)) {(1, 2), (2,), (2, 1, 2)} """ adjacent_pairs = [(x, y) for (x, y) in Tuples(range(1, m.rank() + 1), 2) if x < y and m[x,y] >= 3] w = can_word(w, m) closure = {w} recent_words = {w} while True: new_words = set() for w in recent_words: for J in adjacent_pairs: for d in directions: n = left_star_fc(d, w, J, m) if n is not None: c = can_word(n, m) if c not in closure: new_words.add(c) if len(new_words) == 0: break closure.update(new_words) recent_words = new_words return closure 

left_star_closure_fc((1, 2), get_coxeter_matrix('I', 10)) 

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

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

 

 

def left_star_classes_fc(m): r""" Partitions the set of reduced FC words in the Coxeter group with matrix m into equivalence classes under the "is left-star related to" relation. INPUT: - ``m`` -- CoxeterMatrix; the matrix of the Coxeter group OUTPUT: set; contains (frozen) sets representing the equivalence classes of reduced FC words. EXAMPLES: sage: left_star_classes_fc(CoxeterMatrix(['A', 3])) {frozenset({(1, 3, 2), (2, 1, 3, 2)}), frozenset({(1, 2), (2,), (3, 2)}), frozenset({()}), frozenset({(1, 2, 3), (2, 3), (3,)}), frozenset({(1, 3), (2, 1, 3)}), frozenset({(1,), (2, 1), (3, 2, 1)})} """ fc_elements = fc_elts(m) classes = set() while len(fc_elements) > 0: # Grab a random FC element; take its closure w = fc_elements.pop() closure = frozenset(left_star_closure_fc(w, m)) # Add the closure to our set of equivalence classes classes.add(closure) # Remove that equivalence class from fc_elements fc_elements.difference_update(closure) return classes 

left_star_classes_fc(get_coxeter_matrix('B', 4)) 

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

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

left_star_closure_fc((1, 4), get_coxeter_matrix('B', 4), directions={+1}) 

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

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