MRH

def std(p): # standardization (a.k.a. flattening) of an array. # INPUT: array. # OUTPUT: standardization of this array, i. e., the array consisting # of the elements 1, 2, ..., n (where n is the length of the array) # in the same order as in the input array. # WARNING: this implementation returns an array, not a permutation! n = len(p) q = [(p[i],i) for i in range(n)] q.sort() r = [(q[i][1]+1,i) for i in range(n)] r.sort() s = [r[i][1]+1 for i in range(n)] return s 

def MRcomult(p,k): # k-th graded component of the comultiplication of a permutation p # in the Malvenuto-Reutenauer Hopf algebra, returned as a pair # of permutations. (the actual Hopf-algebraic comultiplication of # p is obtained by tensoring these two permutations, and summing # these tensors over all k from 0 to length(p).) q = p._list r = std(q[:k]) s = std(q[k:]) return (Permutation(r),Permutation(s)) 

# example MRcomult(Permutation([1,5,3,6,2,4]),3) 

([1, 3, 2], [3, 1, 2])

def MRmult(p,q): # product of two permutations p and q in the Malvenuto-Reutenauer # Hopf algebra, returned as a list of permutations (the actual # Hopf-algebraic product is the formal sum of the permutations # in this list). P = p._list Q = q._list n = len(P) m = len(Q) R = [i+n for i in Q] perms = [] # the next for loop iterates over all subsets I of # {0,1,...,n+m-1}. for each such I, we will generate an # (n,m)-shuffle u of {1,2,...,n+m} (namely, the one which # has the values of p on the positions in I and the values # of q on the positions not in I). for I in Subsets(range(n+m),n): # set u to be an array of length n+m (we don't care # about its elements, as we will overwrite all of them): u = range(n+m) Pindex = 0 Rindex = 0 for i in range(n+m): if i in I: u[i] = P[Pindex] Pindex = Pindex + 1 else: u[i] = R[Rindex] Rindex = Rindex + 1 v = Permutation(u) perms.append(v) return perms 

# example MRmult(Permutation([1,3,2]),Permutation([3,1,2])) 

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

class MRHopf(CombinatorialFreeModule): # Malvenuto-Reutenauer Hopf algebra over ring R. def __init__(self, R, **keywords): self._basis = Permutations() CombinatorialFreeModule.__init__(self, R, self._basis, category=GradedHopfAlgebrasWithBasis(R), **keywords) def _repr_(self): return "The Malvenuto-Reutenauer Hopf algebra over %s"%(self.base()) def product_on_basis(self, p, q): perms = MRmult(p,q) a = self.zero() for r in perms: a = a + self.monomial(r) return a def one_basis(self): return Permutation([]) def coproduct_on_basis(self, p): a = tensor([self.zero(), self.zero()]) n = len(p) for k in range(n+1): (b, c) = MRcomult(p, k) a = a + tensor([self.monomial(b), self.monomial(c)]) return a def counit_on_basis(self, p): a = 0 if len(p) == 0: a = 1 return a def antipode_on_basis(self, p): # the following construction of the antipode is just the # recursive one that follows from S*id = eta epsilon. n = len(p) a = self.zero() if n == 0: a = self.one() for k in range(n): (b, c) = MRcomult(p, k) a = a - self.antipode_on_basis(b) * self.monomial(c) return a def homogeneous_component(self, n): basis = Permutations(n) M = CombinatorialFreeModule(self.base_ring(), basis, element_class=self.Element) M._name = '%s-th degree part of the Malvenuto-Reutenauer Hopf algebra'%(n) return M 

# abbreviate MRHopf(QQ) by MR, since this is where we will be working. MR = MRHopf(QQ) 

def MRH(p): # returns the basis element of the Malvenuto-Reutenauer # Hopf algebra over QQ which corresponds to the # permutation whose array representation is p. return MR.monomial(Permutation(p)) 

# now, a lot of examples. MR.one() 

B[[]]

MRH([3,2,1]) * MRH([1,2,3]) 

B[[3, 2, 1, 4, 5, 6]] + B[[3, 2, 4, 1, 5, 6]] + B[[3, 2, 4, 5, 1,
6]] + B[[3, 2, 4, 5, 6, 1]] + B[[3, 4, 2, 1, 5, 6]] + B[[3, 4, 2, 5,
1, 6]] + B[[3, 4, 2, 5, 6, 1]] + B[[3, 4, 5, 2, 1, 6]] + B[[3, 4, 5,
2, 6, 1]] + B[[3, 4, 5, 6, 2, 1]] + B[[4, 3, 2, 1, 5, 6]] + B[[4, 3,
2, 5, 1, 6]] + B[[4, 3, 2, 5, 6, 1]] + B[[4, 3, 5, 2, 1, 6]] + B[[4,
3, 5, 2, 6, 1]] + B[[4, 3, 5, 6, 2, 1]] + B[[4, 5, 3, 2, 1, 6]] +
B[[4, 5, 3, 2, 6, 1]] + B[[4, 5, 3, 6, 2, 1]] + B[[4, 5, 6, 3, 2,
1]]

MR.coproduct(MRH([3,2,1])) 

B[[]] # B[[3, 2, 1]] + B[[1]] # B[[2, 1]] + B[[2, 1]] # B[[1]] +
B[[3, 2, 1]] # B[[]]

MR.antipode(MRH([1,3,2])) 

-B[[2, 1, 3]] - B[[2, 3, 1]] + B[[3, 1, 2]]

# commented out for saving space: # TestSuite(MRHopf(QQ)).run(verbose=True) 

def MRHDynkinES_on_basis(p): # This will be the image of the basis element p of the # Malvenuto-Reutenauer Hopf algebra over R under the # Dynkin operator E*S n = len(p) a = MR.zero() for k in range(1, n+1): (b, c) = MRcomult(p, k) a = a + k * MR.monomial(b) * MR.antipode_on_basis(c) return a 

MRHDynkinES = MR.module_morphism(MRHDynkinES_on_basis, codomain=MR) # The Dynkin operator E*S of the Malvenuto-Reutenauer Hopf algebra over QQ. 

def MRHDynkinCheck_on_basis(p): # Transform permutation p to (E*S - E) ((E*S) (p)) in the MRH Hopf algebra. # Would be 0 if the MRH Hopf algebra was commutative or cocommutative. n = len(p) b = MRHDynkinES_on_basis(p) - n * MR.monomial(p) return MRHDynkinES(b) 

MRHDynkinCheck = MR.module_morphism(MRHDynkinCheck_on_basis, codomain=MR) # Endomorphism (E*S - E) \circ (E*S) of the MRH Hopf algebra. # Would be 0 if the MRH Hopf algebra was commutative or cocommutative. 

def MRHInvolute_on_basis(p): # Transform permutation p to (S^2-id)(p) in the MRH Hopf algebra. # Would be 0 if the MRH Hopf algebra was involutive. a = MR.monomial(p) b = MR.antipode(a) c = MR.antipode(b) return c - a 

MRHInvolute = MR.module_morphism(MRHInvolute_on_basis, codomain=MR) # Endomorphism S^2-id of the MRH Hopf algebra. # Would be 0 if the MRH Hopf algebra was involutive. 

def MRHpseudoid2_on_basis(p): # Transform permutation p to E'^{*2}(p) in the MRH Hopf algebra. # Here E' = E - eta epsilon, and ^{*2} means the 2nd power wrt # convolution. n = len(p) a = MR.zero() for k in range(1, n): (b, c) = MRcomult(p, k) a = a + MR.monomial(b) * MR.monomial(c) return a 

MRHpseudoid2 = MR.module_morphism(MRHpseudoid2_on_basis, codomain=MR) 

def MRHpseudoid3_on_basis(p): # Transform permutation p to E'^{*3}(p) in the MRH Hopf algebra. # Here E' = E - eta epsilon, and ^{*3} means the 3rd power wrt # convolution. n = len(p) a = MR.zero() for k in range(1, n): (b, c) = MRcomult(p, k) a = a + MR.monomial(b) * MRHpseudoid2_on_basis(c) return a 

MRHpseudoid3 = MR.module_morphism(MRHpseudoid3_on_basis, codomain=MR) 

def MRHpseudoid4_on_basis(p): # Transform permutation p to E'^{*4}(p) in the MRH Hopf algebra. # Here E' = E - eta epsilon, and ^{*4} means the 4rd power wrt # convolution. n = len(p) a = MR.zero() for k in range(1, n): (b, c) = MRcomult(p, k) a = a + MRHpseudoid2_on_basis(b) * MRHpseudoid2_on_basis(c) return a 

MRHpseudoid4 = MR.module_morphism(MRHpseudoid4_on_basis, codomain=MR) 

def MRHpseudoid1_on_basis(p): # Transform permutation p to E'(p) in the MRH Hopf algebra. # Here E' = E - eta epsilon. n = len(p) a = MR.monomial(p) if n == 0: a = MR.zero() return a 

MRHpseudoid1 = MR.module_morphism(MRHpseudoid1_on_basis, codomain=MR) 

def MRHlog4_on_basis(p): a = MRHpseudoid1_on_basis(p) - 1/2 * MRHpseudoid2_on_basis(p) + 1/3 * MRHpseudoid3_on_basis(p) - 1/4 * MRHpseudoid4_on_basis(p) return a 

MRHlog4 = MR.module_morphism(MRHlog4_on_basis, codomain=MR) 

def MRHlog4check_on_basis(p): a = MRHpseudoid1_on_basis(p) - 1/2 * MRHpseudoid2_on_basis(p) + 1/3 * MRHpseudoid3_on_basis(p) - 1/4 * MRHpseudoid4_on_basis(p) b = MRHpseudoid1(a) - 1/2 * MRHpseudoid2(a) + 1/3 * MRHpseudoid3(a) - 1/4 * MRHpseudoid4(a) return a - b 

MRHlog4check = MR.module_morphism(MRHlog4check_on_basis, codomain=MR) 

def matriciate(C, D, f, n): # INPUT: # C a graded combinatorial free module; # D a graded combinatorial free module; # f a map from C to D; # n a nonnegative integer. # OUTPUT: # a matrix which describes the map p_n f i_n w.r.t. the canonical bases of # the n-th homogeneous components of C and D, where p_n is the projection # from D onto the n-th homogeneous component, and i_n is the inclusion of # the n-th component into C. basCn = C.homogeneous_component(n).basis().keys() basDn = D.homogeneous_component(n).basis().keys() a = basCn.cardinality() b = basDn.cardinality() m = matrix(QQ, b, a) i = 0 for I in basCn: # set x to the hashtable of nonzero coefficients of f(e_I): x = (f(MR.monomial(I))).monomial_coefficients() j = 0 for J in basDn: # replace the (j, i)-th matrix element by the J-th coordinate of # f(e_I) (but only if it is nonzero, lest to return a nullpointer): if J in x: m[j, i] = x[J] j = j + 1 i = i + 1 return m 

for i in MR.homogeneous_component(3).basis().keys(): print(i) 

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

# example: the following gives the matrix representation of the # map S^2-id, restricted to the 3-rd degree of the # Malvenuto-Reutenauer Hopf algebra MR, with respect to the # basis of permutations. it is a matrix acting from the left. # for bigger sizes, use show(...) or print(....rows()) matriciate(MR, MR, MRHInvolute, 3) 

[ 0  0  0  0  0  0]
[ 0 -2  2 -2  2  0]
[ 0  2 -2  2 -2  0]
[ 0  2 -2  2 -2  0]
[ 0 -2  2 -2  2  0]
[ 0  0  0  0  0  0]

MatrixInvol4 = matriciate(MR, MR, MRHInvolute, 4) # print(MatrixInvol4.rows()) 

MatrixES4 = matriciate(MR, MR, MRHDynkinCheck, 4) # print(MatrixES4.rows()) 

# we want to prove/disprove that the image of MatrixES4 is contained in # the image of MatrixInvol4. (this would mean that E*S/E is an idempotent # in degree 4 of the largest involutive quotient of MR.) # we recall the linear-algebraic fact that Im A is contained in Im B # iff Ker B^T is contained in Ker A^T. in other words, iff A^T restricted # to Ker B^T is zero. 

AT = transpose(MatrixES4) BT = transpose(MatrixInvol4) KBT = kernel(BT) KBT.basis_matrix() * AT # ok, so no counterexample in degree 4 

MatrixLog4 = matriciate(MR, MR, MRHlog4check, 4) # print(MatrixLog4.rows()) 

AT = transpose(MatrixLog4) BT = transpose(MatrixInvol4) KBT = kernel(BT) KBT.basis_matrix() * AT # ok, so no counterexample in degree 4 

MatrixInvol5 = matriciate(MR, MR, MRHInvolute, 5) 

MatrixES5 = matriciate(MR, MR, MRHDynkinCheck, 5) 

AT = transpose(MatrixES5) BT = transpose(MatrixInvol5) KBT = kernel(BT) (KBT.basis_matrix() * AT).rows() # this is a matrix full of zeroes again, so it holds