""" We wrote two functions to test if a given word w (not necessarily reduced) is fully commutative (FC).
The first function, isFullyCommutative, requires less coding but relies on Sage's reduced_word_graph() method, which returns the reduced word graph of w with colorings of the edges by the length of the relevant braid. The Sage source code for reduced_word_graph() goes through the ordered list of reduced words of w, checks if each word is related to a latter word by a single braid move, then creates a colored edge if so. Thus, reduced_word_graph() checks {n choose 2} pairs of reduced words if there are n reduced words and does a bit too much: we don't need the full graph, and we can stop once we see a long braid in one reduced word of w by Stembridge's criterion. This is the idea for our second function:
In the second function, isFC, we go through the list of reduced words of w and checks if each reduced word contains a long braid; if any reduced word does, we return "False". We will single out the presence test for long braid as a subroutine. Note that isFC checks at most n reduced words if n is the number of reduced words. This function still relies on Sage's reduced_words() function to return all reduced words of w in the first step.
Depending on how efficiently Sage computes reduced_words() for w, the second function may or may not be optimal, the reason being that we don't need the entire list of reduced words before checking for long braids. Instead, we can take the input, repeatedly apply commutation moves to generate new words, check each newly generated word for long braid, and stop if we find one long braid and move on otherwise. For example, if we have a very long word w=31234546787 in A8 in (with the usual labelling of generators), then one commutation at the leftmost possible place produces 1323454678, where we immediately see the long braid 323 and hence can stop, without worrying about other reduced words at all! We already have the subroutine to check for long braids from the second function, so to implement the above idea it remains to (a) write another subroutine to apply one commutation relation (easy) and (b) make sure we generate the new words in an optimal way/order. I'm not sure whether it's better to use a breadth-first approach or a depth-first approach (see this week's notes). We should discuss this next time.
I think the method described in the last paragraph is actually faster than the second for the following reason: it appears that Sage generates the reduced_words() list via a method called braid_orbit(), which uses only word manipulation and is available at src/sage/combinat/root_system/braid_orbit.pyx. Thus, this current Sage method isn't using any more advanced math about reduced words that we don't know, so what's described in the last paragraph should be a more efficient method much more tailored to our needs, just as the second function is more tailored and efficient than the first function.
"""
|
|
"""
The first function: 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
"""
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
"""
TESTS
"""
A5 = CoxeterGroup(["A", 5])
testWord1 = A5.from_reduced_word([1, 2, 1]) #121 should be braidable to 212
assert(not isFullyCommutative(testWord1))
testWord2 = A5.from_reduced_word([1, 2]) #12 should be FC
assert(isFullyCommutative(testWord2))
testWord3 = A5.from_reduced_word([2, 1, 2]) #212 should be braidable to 121
assert(not isFullyCommutative(testWord3))
testWord4 = A5.from_reduced_word([1, 2, 3, 4, 5]) #12345 should be FC
assert(isFullyCommutative(testWord4))
testWord5 = A5.from_reduced_word([1, 2, 3, 4, 5, 4]) #123454 has a '454' braid possibility
assert(not isFullyCommutative(testWord5))
testWord6 = A5.from_reduced_word([1, 3]) #13 should be FC
assert(isFullyCommutative(testWord6))
testWord7 = A5.from_reduced_word([1, 4, 5]) #145 should be FC
assert(isFullyCommutative(testWord7))
testWord8 = A5.from_reduced_word([1, 5, 1]) #reduces to 5
assert(isFullyCommutative(testWord8))
testWord9 = A5.from_reduced_word([4, 2, 3, 4]) #4234 -> 2434 which has a '434' braid possibility
assert(not isFullyCommutative(testWord9))
testWord10 = A5.from_reduced_word([1, 1]) #reduces to the identity
assert(isFullyCommutative(testWord10))
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! |
w = A5.from_reduced_word([1, 2, 1, 4, 3, 2])
g = w.reduced_word_graph()
g.show()
|
"""
The following routine will be useful for our second function and potentially a third one.
"""
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
M=A5.coxeter_matrix()
has_no_long_braid(M,[1,3,2,1]), has_no_long_braid(M,[4,3,5,4,1]), has_no_long_braid(M,[1,2,3,2])
(True, True, False) (True, True, False) |
"""
The second function: isFC
Relies on reduced_word() to get all reduced words of the input first. (This may not be necessary)
"""
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)
A5 = CoxeterGroup(["A", 5])
testWord1 = A5.from_reduced_word([1, 2, 1]) #121 should be braidable to 212
assert(not isFC(testWord1))
testWord2 = A5.from_reduced_word([1, 2]) #12 should be FC
assert(isFC(testWord2))
testWord3 = A5.from_reduced_word([2, 1, 2]) #212 should be braidable to 121
assert(not isFC(testWord3))
testWord4 = A5.from_reduced_word([1, 2, 3, 4, 5]) #12345 should be FC
assert(isFC(testWord4))
testWord5 = A5.from_reduced_word([1, 2, 3, 4, 5, 4]) #123454 has a '454' braid possibility
assert(not isFC(testWord5))
testWord6 = A5.from_reduced_word([1, 3]) #13 should be FC
assert(isFC(testWord6))
testWord7 = A5.from_reduced_word([1, 4, 5]) #145 should be FC
assert(isFC(testWord7))
testWord8 = A5.from_reduced_word([1, 5, 1]) #reduces to 5
assert(isFC(testWord8))
testWord9 = A5.from_reduced_word([4, 2, 3, 4]) #4234 -> 2434 which has a '434' braid possibility
assert(not isFC(testWord9))
testWord10 = A5.from_reduced_word([1, 1]) #reduces to the identity
assert(isFC(testWord10))
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! |
"""
The third function: to be written!
"""
|
|
|
|
|
|
|
|