MoreFCTests.2020

1507 days ago by tixu6187

def has_no_long_braid(M,x): r""" Return if a word x has a long braid with respect to the Coxeter matrix M. """ for i in range(0, len(x)-2): a = x[i] b = x[i+1] m = M[a][b] # coxeter matrices labels rows/columns from 1, not 0, so no problem. if m > 2 and i+m <= len(x): ab_braid = [a, b] * (m // 2) if m % 2: ab_braid.append(a) if x[i:i+m]==ab_braid: return False return True 
       
def isFC(self): R = self.reduced_words() P = self.parent() M = P.coxeter_matrix() return all(has_no_long_braid(M,x) for x in R) 
       
# Sage has braid_relations as a built-in function for Coxeter groups: # See https://github.com/sagemath/sage/blob/b8f53f72e817e78722ad1b40d70aa9071426700/src/sage/categories/coxeter_groups.py A5 = CoxeterGroup(["A", 5]) A5.braid_relations() 
        
[[[1, 2, 1], [2, 1, 2]],
 [[1, 3], [3, 1]],
 [[1, 4], [4, 1]],
 [[1, 5], [5, 1]],
 [[2, 3, 2], [3, 2, 3]],
 [[2, 4], [4, 2]],
 [[2, 5], [5, 2]],
 [[3, 4, 3], [4, 3, 4]],
 [[3, 5], [5, 3]],
 [[4, 5, 4], [5, 4, 5]]]
[[[1, 2, 1], [2, 1, 2]],
 [[1, 3], [3, 1]],
 [[1, 4], [4, 1]],
 [[1, 5], [5, 1]],
 [[2, 3, 2], [3, 2, 3]],
 [[2, 4], [4, 2]],
 [[2, 5], [5, 2]],
 [[3, 4, 3], [4, 3, 4]],
 [[3, 5], [5, 3]],
 [[4, 5, 4], [5, 4, 5]]]
# We mimicked the code for braid_relations to write a commutation_relations function: 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 A5 = CoxeterGroup(["A", 5]) commutation_relations(A5) 
        
[[1, 3],
 [3, 1],
 [1, 4],
 [4, 1],
 [1, 5],
 [5, 1],
 [2, 4],
 [4, 2],
 [2, 5],
 [5, 2],
 [3, 5],
 [5, 3]]
[[1, 3],
 [3, 1],
 [1, 4],
 [4, 1],
 [1, 5],
 [5, 1],
 [2, 4],
 [4, 2],
 [2, 5],
 [5, 2],
 [3, 5],
 [5, 3]]

For next time:

  • (Done) Get commutation_relations working
  • (Didn't Continue) Use the pattern of braid_orbits to build something like commutation_orbit
  • (Didn't Continue) Add the check for contains_long_braid into building the commutation class
def commute_once(w,i): return w[:i]+[w[i+1],w[i]]+w[i+2:] commute_once([5,3,4,1,5],2) 
        
[5, 3, 1, 4, 5]
[5, 3, 1, 4, 5]
def is_FC2(w, group): M=group.coxeter_matrix() if has_no_long_braid(M,w) == 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(M,y)==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 
       
A9 = CoxeterGroup(["A",9]) B6 = CoxeterGroup(["B", 6]) B6.coxeter_matrix() 
        
[1 3 2 2 2 2]
[3 1 3 2 2 2]
[2 3 1 3 2 2]
[2 2 3 1 3 2]
[2 2 2 3 1 4]
[2 2 2 2 4 1]
[1 3 2 2 2 2]
[3 1 3 2 2 2]
[2 3 1 3 2 2]
[2 2 3 1 3 2]
[2 2 2 3 1 4]
[2 2 2 2 4 1]
is_FC2([1,2,3,4,5,6,7,8],A9) 
        
True
True
is_FC2([3,5,1,4,5],B6),is_FC2([1,2,1],B6),is_FC2([5,6,5],B6),is_FC2([6,5,6],B6) 
        
(False, False, True, True)
(False, False, True, True)

From Saurabh:

Below is my depth-first version of is_FC along with its tests. It uses function recursion to take advantage of the function stack to implement a depth-first search.
def has_no_long_braid(M,x): r""" Return if a word x has a long braid with respect to the Coxeter matrix M. """ for i in range(0, len(x)-2): a = x[i] b = x[i+1] m = M[a][b] # coxeter matrices labels rows/columns from 1, not 0, so no problem. if m > 2 and i+m <= len(x): ab_braid = [a, b] * (m // 2) if m % 2: ab_braid.append(a) if x[i:i+m]==ab_braid: return False return True def commute_once(w,i): return w[:i] + [w[i+1], w[i]] + w[i + 2:] def depth_first_is_fully_commutative(M, word): def inner_is_fully_commutative(word, checked_words): if word in checked_words: return True if not has_no_long_braid(M, word): 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(word, []) A5 = CoxeterGroup(["A", 5]) M = A5.coxeter_matrix() testWord1 = [1, 2, 1] #121 should be braidable to 212 assert(not depth_first_is_fully_commutative(M, testWord1)) testWord2 = [1, 2] #12 should be FC assert(depth_first_is_fully_commutative(M, testWord2)) testWord3 = [2, 1, 2] #212 should be braidable to 121 assert(not depth_first_is_fully_commutative(M, testWord3)) testWord4 = [1, 2, 3, 4, 5] #12345 should be FC assert(depth_first_is_fully_commutative(M, testWord4)) testWord5 = [1, 2, 3, 4, 5, 4] #123454 has a '454' braid possibility assert(not depth_first_is_fully_commutative(M, testWord5)) testWord6 = [1, 3] #13 should be FC assert(depth_first_is_fully_commutative(M, testWord6)) testWord7 = [1, 4, 5] #145 should be FC assert(depth_first_is_fully_commutative(M, testWord7)) testWord8 = [1, 5, 1] #reduces to 5 assert(depth_first_is_fully_commutative(M, testWord8)) testWord9 = [4, 2, 3, 4] #4234 -> 2434 which has a '434' braid possibility assert(not depth_first_is_fully_commutative(M, testWord9)) testWord10 = [1, 1] #reduces to the identity assert(depth_first_is_fully_commutative(M, testWord10)) B6 = CoxeterGroup(["B", 6]) M2 = B6.coxeter_matrix() testWord11 = [3, 5, 1, 4, 5] #35145 -> 31545 which has a '545' braid possibility assert(not depth_first_is_fully_commutative(M2, testWord11)) testWord12 = [1, 2, 1] #121 should be braidable to 212 assert(not depth_first_is_fully_commutative(M2, testWord12)) print("If you see this message and no errors, then the tests passed! Nice!") 
        
If you see this message and no errors, then the tests passed! Nice!
If you see this message and no errors, then the tests passed! Nice!
depth_first_is_fully_commutative(M,[5,3,1,4,5]) 
        
False
False
w=[5,3,1,4,5] is_FC2(w,A5), depth_first_is_fully_commutative(M,w) 
        
(False, False)
(False, False)
""" TODO: 1. make sure we all understand Saurabh's elegant test using inner functions (I tested it; it's much faster than is_FC2!); 2. time the breadth-first and depth-first tests to see if one is always faster than the other; 2. clean up and re-organize our FCtests: put them in one place, with one fixed set of conventions (on things like what to use as inputs and how to order them). Question: are recursively defined functions faster than functions written using loops? """