Find the longest word in a symmetric group which satisfies a certain property.

lijr07
255 ●6 ●13 ●32

Let $A, B$ be two list of equal length $k$ , where $A$ is weakly increasing. For example, $A=[1, 1, 2, 3, 3, 4]$ , $B=[12, 9, 10, 15, 15, 14]$ .

Define $m_{A,B}$ to be the multiset of pairs $[ A_i, B_i ]$ , $i \in k$ , (this is a multi-set of pairs of integers, not a list of pairs, so the order of pairs in $m_{A,B}$ does not matter).

By a result in symmetric group, there is a unique element with maximal length (length of the reduced word) in the symmetric group $S_k$ ( $k$ is the length of $A$ ) such that $m_{A,w(sorted(B))} = m_{A,B}$ , where $sorted(B)$ is to sorted B such that it is weakly increasing, and the action of $w=s_{i_1} \cdots s_{i_m}$ on a list $L$ is defined by: $s_j(L)$ means exchanging the jth and j+1th elements of $L$ , and for $w,w' \in S_k$ , $w w'(L) = w(w'(L))$ .

There is a method to compute the longest word $w$ by checking all elements in $S_k$ . But it takes a long time when $k$ is large. The following function works fine and returns correct result.

 def LongestPerm(A,Bsorted,B):
    k = len(A)
    S = set([(A[i],B[i]) for i in range(k)])
    W = WeylGroup('A'+str(k-1), prefix = 's')

    winner = W.one()
    for w in W:
        wstr = w.inverse().to_permutation_string()
        if set([(A[int(wstr[i])-1],Bsorted[i]) for i in range(k)]) == S:      
            if w.length()>winner.length():
                winner = w
    return winner

In the example that

A=[1, 1, 2, 3, 3, 4]
B=[12, 9, 10, 15, 15, 14]

we have

w=s4*s5*s4*s2*s1

Is there some method to compute $w$ faster (without checking all elements of $S_k$ )? Thank you very much.

add a comment

2 Answers

Sort by » oldest newest most voted

answered 3 years ago

Max Alekseyev

6932 ●9 ●52 ●162

updated 3 years ago

You don't need to consider all permutations - it's enough to take one suitable permutation and multiply it by elements of the stabilizers of $A$ and $B$ from left and right, respectively.

Here is an example:

# returns list of cycles generating the stabilizer of L
def fixed_sets(L):
    D = dict()
    for p,l in enumerate(L):
        D.setdefault(l,[]).append(p+1)
    return [tuple(s) for s in D.values() if len(s)>1]

A=[1,1,2,3,3,4]
B=[12,9,10,15,15,14]

k = len(A)

S = SymmetricGroup(k)
SA = S.subgroup(fixed_sets(A))
SB = S.subgroup(fixed_sets(B))

perm = S( Word(B).standard_permutation() / Word(A).standard_permutation() )

# testing can be done like this:
#sortedB = sorted(B)
#assert set( zip(A,[sortedB[i-1] for i in perm.domain()]) ) == set( zip(A,B) )

W = WeylGroup('A'+str(k-1), prefix = 's')
winner = max( (W(a*perm*b) for a in SA for b in SB), key=lambda s: s.length() )

print( winner )

link

Comments

@max, thank you very much!

lijr07 ( 3 years ago )

@max, I checked some more examples and found that some of the results given by your codes do not agree with the function LongestPerm in the question. I slightly modified your codes and wrote it as an answer below. Thanks again!

lijr07 ( 3 years ago )

I've corrected an error in my code.

Max Alekseyev ( 3 years ago )

@max, thank you very much!

lijr07 ( 3 years ago )

add a comment

answered 3 years ago

lijr07
255 ●6 ●13 ●32

updated 3 years ago

I modified Max Alekseyev's answer. The result of the following codes agree with the result of the function LongestPerm in the post.

def LongestPermWInSBWInverseSA(W,A,B): 
    t1=StablizerOfTuple(A)
    t2=StablizerOfTuple(sorted(B))
    s=W.simple_reflections()
    #print(t1,t2)
    t3=[]
    for i in t1:
        t3.append(s[i])
    t4=[]
    for i in t2:
        t4.append(s[i])
    t5=find_permutation2(B,sorted(B))
    w=W.one()
    for i in t5:
        w=w*s[i]
    #print(t4,w,t3)
    r2=LongestPermInDoubleCosetWeylGroup(W,t4,w,t3)
    r=r2

    return r

def find_permutation2(L1, L2):
    perm = Word(L1).standard_permutation() / Word(L2).standard_permutation()
    assert [L2[i-1] for i in perm] == L1
    r=perm.reduced_word()
    return r

def LongestPermInDoubleCosetWeylGroup(W,S1,w,S2): 
    g1=W.subgroup(S1)
    g2=W.subgroup(S2)
    winner = W.one()
    for u1 in g1:
        for u2 in g2:
            t1=u1*w*u2
            if t1.length()>winner.length():
                winner=t1
    r=winner

    return r

def SymmetricGroupActionOnListSi(i,L): #  w=s_i,  L=[a1,a2,...,an]
    r1=[]
    for j in L:
        r1.append(j)

    t1=r1[i-1]
    r1[i-1]=r1[i]
    r1[i]=t1 

    r=r1

    return r

def StablizerOfTuple(A): # A is a list, weakly increasing
    k = len(A)
    r=[]
    for i in [1..k-1]:
        t1=SymmetricGroupActionOnListSi(i,A)
        if t1==A:
            r.append(i)
    return r

A=[1,1,2,3,3,4,6]
B=[12,9,12,15,15,14,12]
k = len(A)
W = WeylGroup('A'+str(k-1), prefix = 's')
t1=LongestPermWInSBWInverseSA(W,A,B)
print(t1)

link

Comments

You can save some lines by using max() function like in my answer.

Max Alekseyev ( 3 years ago )

@max, thank you very much for your nice answer!

lijr07 ( 3 years ago )

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Find the longest word in a symmetric group which satisfies a certain property.

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Find the longest word in a symmetric group which satisfies a certain property. savecancel

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Find the longest word in a symmetric group which satisfies a certain property.