CombinedFCTests

1434 days ago by nasc3063

Conventions:

-Use tuples for words of elements (ex: (1,2,3))

-Function inputs are ordered as (word, type, matrix)

-Also see http://doc.sagemath.org/html/en/developer/coding_basics.html

-We also referenced 

https://github.com/sagemath/sage/blob/b8f53f72e817e78722ad1b40d70aa9071426700b/src/sage/categories/coxeter_groups.py 

-Question: How many of these rely on a reduced word as an input?

Helper Functions

-For future: Add a helper function that checks if an inputted word is reduced, if not, reduce it. (eg. check for ss) 

 

contains_long_braid: Returns if a word  "word" has a long braid with respect to the Coxeter matrix "matrix".

       Ex) 

       M=A5.coxeter_matrix()
       contains_long_braid((1,3,2,1), M), contains_long_braid((4,3,5,4,1), M), contains_long_braid((1,2,3,2), M)

       Returns: 

       (False, False, True)
def contains_long_braid(word, matrix): """ Returns if a word "word" has a long braid with respect to the Coxeter matrix "matrix". sage: contains_long_braid((1,3,2,1),M) sage: False """ for i in range(0, len(word)-2): a = word[i] b = word[i+1] m = matrix[a][b] #coxeter matrices labels rows/columns from 1, not 0, so no problem. if m > 2 and i+m <= len(word): ab_braid = [a, b] * (m // 2) if m % 2: ab_braid.append(a) if word[i:i+m]==ab_braid: return True return False 
       

contains_square: Returns if a word  "word" has a consecutive occurences of the same generator (a square), indicating the word is not reduced. 

To-do: Implement within our FC tests.
def contains_square(word): for i in range(0, len(word)-2): a = word[i] b = word[i+1] if a==b: return True return False 
       

commutation_relations: We mimicked the code for braid_relations to write a commutation_relations function

       Ex) 

       A5 = CoxeterGroup(["A", 5])

       commutation_relations(A5)

       Expected output: 

       [[1, 3],
        [3, 1],
        [1, 4],
        [4, 1],
        [1, 5],
        [5, 1],
        [2, 4],
        [4, 2],
        [2, 5],
        [5, 2],
        [3, 5],
        [5, 3]]
 
def commutation_relations(group): rels = [] M=group.coxeter_matrix() I=group.index_set() for ii, i in enumerate(I): for j in I[ii+1:]: m = M[i, j] if m==2: rels += [[i, j], [j, i]] return rels 
       

commute_once: Commutes a word "word" at a given index "i" once

       Ex)

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

       Returns: 

       [5, 3, 1, 4, 5]
def commute_once(word,i): return word[:i]+[word[i+1],word[i]]+word[i+2:] 
       

Fully Commutative Test Functions

isFullyCommutative :relies on http://doc.sagemath.org/html/en/reference/categories/sage/categories/coxeter_groups.html#sage.categories.coxeter_groups.CoxeterGroups.ElementMethods.reduced_word_graph

       Ex) 

       A5 = CoxeterGroup(["A", 5])

       testWord1 = A5.from_reduced_word((1, 2, 1)) #121 should be braidable to 212
       isFullyCommutative(testWord1)

       Returns: 

       False
def isFullyCommutative(word): return all(edge[2] == 2 for edge in word.reduced_word_graph().edges()) #edge[2] is the edge's color, i.e., the length m of the corresponding braid move 
       

isFC: Relies on reduced_word() to get all reduced words of the input first. (This may not be necessary)

  Ex) 

       A5 = CoxeterGroup(["A", 5])

       testWord1 = A5.from_reduced_word((1, 2, 1)) #121 should be braidable to 212
       isFC(testWord1)

       Returns: 

       False
def isFC(self): """ Returns is a reduced word is fully commutative sage: isFC((1,2,1)) sage: False """ R = self.reduced_words() P = self.parent() M = P.coxeter_matrix() return all(has_no_long_braid(M,x) for x in R) 
       

is_FC2:

  Ex) 

       A9 = CoxeterGroup(["A", 9])

       is_FC2(A9,(1,2,3,4,5,6,7,8))

       Returns: 

       True
def is_FC2(w, group): M=group.coxeter_matrix() if has_no_long_braid(w,M) == False: return False l = len(w) current_words=[(w,-1)] #words being checked, the second coordinate keeps track of the position a commutation started to generate the word, but it's -1 for the initial word w recorded_words=[w] while current_words != []: new_words=[] # words whose commutation offsprings are to be generated and checked for long braids next for k in current_words: x=k[0] j=k[1] for i in range(l-1): if i != j: a = x[i] b = x[i+1] m = M[a][b] if m==2: y = commute_once(x,i) if y not in recorded_words: if has_no_long_braid(y,M)==False: return False else: new_words.append((y,i)) recorded_words.append(y) current_words = new_words #update pool of things to be checked return True 
       

is_FC_depth_recursive: Uses function recursion to take advantage of the function stack to implement a depth-first search  

  Ex) 

       A9 = CoxeterGroup(["A", 9])

       is_FC_depth_recursive(A9,(1,2,3,4,5,6,7,8))

       Returns: 

       True
def is_FC_depth_recursive(w,M): # Saurabh's recursive code def inner_is_fully_commutative(word, checked_words): if word in checked_words: return True if contains_long_braid(word,M): return False checked_words.append(word) for i in range(len(word) - 1): a = word[i] b = word[i + 1] if M[a][b] == 2 and not inner_is_fully_commutative(commute_once(word, i), checked_words): return False return True return inner_is_fully_commutative(w, []) 
       

is_FC_depth: An iterative function using a stack to implement depth-first traversal

  Ex) 

       A9 = CoxeterGroup(["A", 9])

       is_FC_depth(A9,(1,2,3,4,5,6,7,8))

       Returns: 

       True
def is_FC_depth(w, M): """ Returns if a word if FC using depth first traversal by means of the function stack sage: is_FC_depth(A9, (1,2,3,4,5,6,7,8)) sage: true """ if contains_long_braid(w,M): return False else: l, checked, stack = len(w), {w}, deque([w]) while stack: word = stack.pop() for i in range(l-1): a, b = word[i], word[i+1] if M[a][b] == 2: new_word = commute_once(word,i) if new_word not in checked: if contains_long_braid(new_word,M): return False else: checked.add(new_word) stack.append(new_word) return True 
       

is_FC_breadth: An iterative function using a queue to implement breadth-first traversal

       Ex) 

       A9 = CoxeterGroup(["A", 9])

       if_FC_breadth(A9,(1,2,3,4,5,6,7,8))

       Returns: 

       True
def is_FC_breadth(w, M): # M is the Coxeter matrix """ Returns if a word is FC using breadth first traversal by means of a queue """ if contains_long_braid(w,M): return False else: l, checked, queue = len(w), {w}, deque([w]) while queue: word = queue.pop() for i in range(l-1): a, b = word[i], word[i+1] if M[a][b] == 2: new_word = commute_once(word,i) if new_word not in checked: if contains_long_braid(new_word,M): return False else: checked.add(new_word) queue.appendleft(new_word) return True