generatingFCelements(1)

1470 days ago by tixu6187

import itertools from collections import defaultdict, deque, OrderedDict 
       
We want to generate all FC elements of a given Coxeter groups, arranged according to their lengths, in increasing order. 
       
https://github.com/sagemath/sage/blob/b8f53f72e817e78722ad1b40d70aa9071426700b/src/sage/categories/coxeter_groups.py#L945 http://doc.sagemath.org/html/en/reference/categories/sage/categories/coxeter_groups.html#sage.categories.coxeter_groups.CoxeterGroups.ParentMethods.elements_of_length https://docs.python.org/3/library/functools.html#functools.lru_cache 
       
def F(n): """ Return the Coxeter matrix of type F Weyl group with n generators. """ A = list(CoxeterMatrix(['A',n])) A[2][1], A[1][2] = 4, 4 return matrix(A) F(7) 
        
[1 3 2 2 2 2 2]
[3 1 4 2 2 2 2]
[2 4 1 3 2 2 2]
[2 2 3 1 3 2 2]
[2 2 2 3 1 3 2]
[2 2 2 2 3 1 3]
[2 2 2 2 2 3 1]
[1 3 2 2 2 2 2]
[3 1 4 2 2 2 2]
[2 4 1 3 2 2 2]
[2 2 3 1 3 2 2]
[2 2 2 3 1 3 2]
[2 2 2 2 3 1 3]
[2 2 2 2 2 3 1]
F7 = CoxeterGroup(F(7)) F7 
        
Coxeter group over Universal Cyclotomic Field with Coxeter matrix:
[1 3 2 2 2 2 2]
[3 1 4 2 2 2 2]
[2 4 1 3 2 2 2]
[2 2 3 1 3 2 2]
[2 2 2 3 1 3 2]
[2 2 2 2 3 1 3]
[2 2 2 2 2 3 1]
Coxeter group over Universal Cyclotomic Field with Coxeter matrix:
[1 3 2 2 2 2 2]
[3 1 4 2 2 2 2]
[2 4 1 3 2 2 2]
[2 2 3 1 3 2 2]
[2 2 2 3 1 3 2]
[2 2 2 2 3 1 3]
[2 2 2 2 2 3 1]
F7_l2 = F7.elements_of_length(2) for x in F7_l2: print(x.reduced_word()) 
        
[1, 2]
[2, 1]
[2, 3]
[3, 1]
[3, 2]
[3, 4]
[4, 1]
[4, 2]
[4, 3]
[4, 5]
[5, 1]
[5, 2]
[5, 3]
[5, 4]
[5, 6]
[6, 1]
[6, 2]
[6, 3]
[6, 4]
[6, 5]
[6, 7]
[7, 1]
[7, 2]
[7, 3]
[7, 4]
[7, 5]
[7, 6]
[1, 2]
[2, 1]
[2, 3]
[3, 1]
[3, 2]
[3, 4]
[4, 1]
[4, 2]
[4, 3]
[4, 5]
[5, 1]
[5, 2]
[5, 3]
[5, 4]
[5, 6]
[6, 1]
[6, 2]
[6, 3]
[6, 4]
[6, 5]
[6, 7]
[7, 1]
[7, 2]
[7, 3]
[7, 4]
[7, 5]
[7, 6]
# Function 1: fcol1(len,M) # use Sage to generate all elements of length len in the Coxeter group given by the matrix M, then pick out the FC ones using our isFC test. def fcol1(l,M): W = CoxeterGroup(M) L = W.elements_of_length(l) fcol = [] for x in L: w = tuple(x.reduced_word()) if is_FC_breadth(w, M): fcol.append(w) return fcol A7 = CoxeterMatrix(['A',7]), fcol1(7,A7) #fcol1(7,F7) 
        
Traceback (click to the left of this block for traceback)
...
AttributeError: 'tuple' object has no attribute 'append'
Traceback (most recent call last):        for x in L:
  File "", line 1, in <module>
    
  File "/tmp/tmpdUZ5Cj/___code___.py", line 14, in <module>
    A7 = CoxeterMatrix(['A',_sage_const_7 ]), fcol1(_sage_const_7 ,A7)
  File "/tmp/tmpdUZ5Cj/___code___.py", line 10, in fcol1
    if is_FC_breadth(w, M):
  File "/tmp/tmp3m8JUg/___code___.py", line 21, in is_FC_breadth
    if contains_long_braid(w,M):
  File "/tmp/tmp3m8JUg/___code___.py", line 12, in contains_long_braid
    ab_braid.append(a)
AttributeError: 'tuple' object has no attribute 'append'
# our FC test def contains_long_braid(word, matrix): for i in range(0, len(word)-2): a = word[i] b = word[i+1] m = matrix[a][b] 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 def commute_once(word,i): return word[:i]+(word[i+1],word[i])+word[i+2:] def is_FC_breadth(w, M): # M is the Coxeter matrix 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 
       
""" TODO: 1. make fcol1 work, so we can check better functions against it. 2. Use the idea in b to write a function is_rw_of_FC(w,M). (Sarah) 3. Use the idea in c to write a function fcol2_upto(l,M) to generate all fc elements of length up to l. Also, try to write fcol2(l,M) to get just the fc elements of length exactly l. ( Natalie, Saurabh, Wei) 4. Learn about cacheing to see if we can speed up 3. (Tianyuan) 5. Paste the code for the Cartier--Foata canonical form. IDEAS: a. Incorporate more efficient FC criteria for specific Coxeter groups into our functions, including isFC. b. Recall that in any Coxeter group W for any element w, all reduced words of w are relatable by braid moves, which are either commutations or longer braid moves like sts=tst, stst=tsts. Q: Let w be a word. When is w the reduced word of an FC element? Claim: If and only if no word reachable from w via a sequence of commutations has two consecutive occurrences of the same letter ('ss') or a long braid. 'Only if': easy. 'I the non-recursive is_FC functions weren'tf': Prove the contrapositive: "if w is not the reduced word of an FC element, then we can reach a 'bad' word via commutation". c. Given a reduced word w=s_1s_2...s_k of an FC element, then it can be obtained from the subword w'=s_1s_2...s_{k-1} by adding s_k to the right. Note that w' is also the reduced word of an FC element, which means that we can use fcol(l-1,M)'s results to build fcol(l,M). This inductive method would be good if we want all fcol up to a certain length, say 0, then 1, then 2, then 3, then 4, but I don't know how efficient this is if we just want a certain length, say 10. Cacheing? d. We'll probably need a canonical word for each FC element (so that we can check if it's been recorded). There is a such a notion called the Cartier--Foata form, and we have code for it. """ 
       

From Saurabh: this is a quickly-written fcol1 and fcol2. This is a quick hodgepodge of code I put together to get something working. After working with elements_of_length, I realized that that method doesn't return duplicate words in different forms. I made these methods assuming that we did want duplicate words if they were in different forms (eg. we would want both [1, 5] and [5, 1] for length-2 words even though they are the same).
def contains_long_braid(word, matrix): 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 def commute_once(word,i): #It seems like Sage is inconsistent on whether it uses lists or tuples for words: this version of commute_once only works with lists return word[:i]+[word[i+1],word[i]]+word[i+2:] def is_FC_and_Reduced(w,M): 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 a == b: #Added check for seeing if the word is reduced return False 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, []) def fcol1(l, group): fcReducedWords = [] for element in group.elements_of_length(l): if not is_FC_and_Reduced(element.reduced_word(), group.coxeter_matrix()): continue for tupleWord in element.reduced_word_graph().vertices(): #elements_of_length doesn't return duplicate words in different forms, so graph traversal is necessary word = list(tupleWord) #vertices returns words as tuples even though reduced_word() returns words as lists if word not in fcReducedWords: fcReducedWords.append(word) return fcReducedWords def fcol2(l, group): lengthOneWords = [element.reduced_word() for element in group.elements_of_length(1)] #TODO: figure out how to get 'letters' without calling elements_of_length(1) if l == 1: return lengthOneWords smallerLengthFCElements = fcol2(l - 1, group) correctLengthFCElements = [] M = group.coxeter_matrix() for smallerFCWord in smallerLengthFCElements: for letter in lengthOneWords: correctLengthWord = smallerFCWord + letter if correctLengthWord not in correctLengthFCElements and is_FC_and_Reduced(correctLengthWord, M): correctLengthFCElements.append(correctLengthWord) return correctLengthFCElements A5 = CoxeterGroup(["A", 5]) print(fcol1(3, A5)) print("\n\n\n") print(fcol2(3, A5)) #quick consistency check: is also a correctness check if either fcol1 or fcol2 is correct result1 = fcol1(5, A5) result2 = fcol2(5, A5) assert(sum(1 for word in result1 if word in result2) == len(result1)) 
        
[[1, 2, 3], [2, 1, 3], [2, 3, 1], [2, 3, 4], [1, 3, 2], [3, 1, 2], [3,
2, 1], [1, 3, 4], [3, 1, 4], [3, 4, 1], [3, 2, 4], [3, 4, 2], [3, 4, 5],
[1, 2, 4], [1, 4, 2], [4, 1, 2], [2, 1, 4], [2, 4, 1], [4, 2, 1], [2, 4,
3], [4, 2, 3], [1, 4, 3], [4, 1, 3], [4, 3, 1], [4, 3, 2], [1, 4, 5],
[4, 1, 5], [4, 5, 1], [2, 4, 5], [4, 2, 5], [4, 5, 2], [4, 3, 5], [4, 5,
3], [1, 2, 5], [1, 5, 2], [5, 1, 2], [2, 1, 5], [2, 5, 1], [5, 2, 1],
[2, 3, 5], [2, 5, 3], [5, 2, 3], [1, 3, 5], [1, 5, 3], [3, 1, 5], [3, 5,
1], [5, 1, 3], [5, 3, 1], [3, 2, 5], [3, 5, 2], [5, 3, 2], [3, 5, 4],
[5, 3, 4], [1, 5, 4], [5, 1, 4], [5, 4, 1], [2, 5, 4], [5, 2, 4], [5, 4,
2], [5, 4, 3]]




[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 2], [1, 3, 4], [1, 3, 5], [1,
4, 2], [1, 4, 3], [1, 4, 5], [1, 5, 2], [1, 5, 3], [1, 5, 4], [2, 1, 3],
[2, 1, 4], [2, 1, 5], [2, 3, 1], [2, 3, 4], [2, 3, 5], [2, 4, 1], [2, 4,
3], [2, 4, 5], [2, 5, 1], [2, 5, 3], [2, 5, 4], [3, 1, 2], [3, 1, 4],
[3, 1, 5], [3, 2, 1], [3, 2, 4], [3, 2, 5], [3, 4, 1], [3, 4, 2], [3, 4,
5], [3, 5, 1], [3, 5, 2], [3, 5, 4], [4, 1, 2], [4, 1, 3], [4, 1, 5],
[4, 2, 1], [4, 2, 3], [4, 2, 5], [4, 3, 1], [4, 3, 2], [4, 3, 5], [4, 5,
1], [4, 5, 2], [4, 5, 3], [5, 1, 2], [5, 1, 3], [5, 1, 4], [5, 2, 1],
[5, 2, 3], [5, 2, 4], [5, 3, 1], [5, 3, 2], [5, 3, 4], [5, 4, 1], [5, 4,
2], [5, 4, 3]]
[[1, 2, 3], [2, 1, 3], [2, 3, 1], [2, 3, 4], [1, 3, 2], [3, 1, 2], [3, 2, 1], [1, 3, 4], [3, 1, 4], [3, 4, 1], [3, 2, 4], [3, 4, 2], [3, 4, 5], [1, 2, 4], [1, 4, 2], [4, 1, 2], [2, 1, 4], [2, 4, 1], [4, 2, 1], [2, 4, 3], [4, 2, 3], [1, 4, 3], [4, 1, 3], [4, 3, 1], [4, 3, 2], [1, 4, 5], [4, 1, 5], [4, 5, 1], [2, 4, 5], [4, 2, 5], [4, 5, 2], [4, 3, 5], [4, 5, 3], [1, 2, 5], [1, 5, 2], [5, 1, 2], [2, 1, 5], [2, 5, 1], [5, 2, 1], [2, 3, 5], [2, 5, 3], [5, 2, 3], [1, 3, 5], [1, 5, 3], [3, 1, 5], [3, 5, 1], [5, 1, 3], [5, 3, 1], [3, 2, 5], [3, 5, 2], [5, 3, 2], [3, 5, 4], [5, 3, 4], [1, 5, 4], [5, 1, 4], [5, 4, 1], [2, 5, 4], [5, 2, 4], [5, 4, 2], [5, 4, 3]]




[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 2], [1, 3, 4], [1, 3, 5], [1, 4, 2], [1, 4, 3], [1, 4, 5], [1, 5, 2], [1, 5, 3], [1, 5, 4], [2, 1, 3], [2, 1, 4], [2, 1, 5], [2, 3, 1], [2, 3, 4], [2, 3, 5], [2, 4, 1], [2, 4, 3], [2, 4, 5], [2, 5, 1], [2, 5, 3], [2, 5, 4], [3, 1, 2], [3, 1, 4], [3, 1, 5], [3, 2, 1], [3, 2, 4], [3, 2, 5], [3, 4, 1], [3, 4, 2], [3, 4, 5], [3, 5, 1], [3, 5, 2], [3, 5, 4], [4, 1, 2], [4, 1, 3], [4, 1, 5], [4, 2, 1], [4, 2, 3], [4, 2, 5], [4, 3, 1], [4, 3, 2], [4, 3, 5], [4, 5, 1], [4, 5, 2], [4, 5, 3], [5, 1, 2], [5, 1, 3], [5, 1, 4], [5, 2, 1], [5, 2, 3], [5, 2, 4], [5, 3, 1], [5, 3, 2], [5, 3, 4], [5, 4, 1], [5, 4, 2], [5, 4, 3]]