# Implementation of Foissy's Hopf algebra of ordered forests. Ordered forests are rooted forests # (i. e., forests consisting of rooted trees), endowed with a total ordering on the set of # vertices. (The total ordering does not have to respect any structure like roots or # connected components. This is what makes this Hopf algebra noncommutative.) # This Hopf algebra is supposedly isomorphic to PQSym (parking functions), although I don't know # how. It should be in Foissy's papers. # # Note that ordered forests are considered up to isomorphy, but isomorphisms have to respect # the total order *and* the roots, so not many things end up isomorphic. # Ordered forests are encoded as lists of integers with some particular properties. # Here is how this encoding works: # Let f be an ordered forest. We enumerate the vertices by integers from 0 to n-1 # (where n is the number of vertices) such that the total ordering places vertex # 0 before vertex 1, vertex 1 before vertex 2, etc., vertex n-2 before vertex n-2. # Now, we encode f as a list [a_1, a_2, ..., a_n] of n integers, where a_i is # the number of the father of vertex i if i has a father; # -1 if i is a root. # This list uniquely determines f. But, of course, not every list of n integers # comes from an ordered forest. We check whether it comes from a forest using the # function IsOF. # EXAMPLE: The ordered rooted forest (where the root is the lowermost vertex of # each connected component) # 0 5 4 # \ / | # 1 2 6 # \ / # 3 # is encoded as [2,3,-1,6,2,-1]. # !! WARNING !! # I am going to use some conflicting notations in the following. Namely, beginning with # the definition of the Hopf algebra Ordforst, I will encode ordered forests as lists of # NONNEGATIVE integers, rather than integers >= -1 as above. This is because I want to # use the IntegerList class, but that class doesn't allow negative integers in the list. # So a forest which I encoded by [a_1, a_2, ..., a_n] in the above will be encoded by # [1+a_1, 1+a_2, ..., 1+a_n] when it comes to working with the Hopf algebra. def IsOF(ys): # INPUT: # list ys of integers (hopefully). # OUTPUT: # true if ys describes an ordered forest; false otherwise. # Here, the first encoding is used, i. e., the list should contain integers >= -1. n = len(ys) for j in ys: if j >= n or j < -1: return false xs = copy(ys) k = 1 while True: for j in range(n): # this for loop more or less squares the adjacency matrix y = xs[j] if y >= 0: xs[j] = xs[y] k = 2*k # now, k tells us which power of the adjacency matrix we have computed if (k >= n): for j in range(n): if xs[j] >= 0: return false return true class OForests(Parent): # OForests(n) will be the class of all ordered rooted forests on n vertices. # Note that, by Cayley's formula, it contains (n+1)^(n-1) elements # (since ordered rooted forests on n vertices correspond to ordered unrooted # trees on n+1 vertices). def __init__(self, n): self.n = n return Parent.__init__(self, category=(EnumeratedSets())) def __repr__(self): return "Ordered forests on %s"%self.n + " elements" def __contains__(self, ys): return len(ys) == self.n and IsOF(ys) def cardinality(self): return self.n def list(self): # Not the optimal way. The Pruefer code might lead to a better solution, # since ordered rooted forests on n vertices are equivalent to ordered # rooted trees on n+1 vertices with the root having label 1. # I don't care much for speed in this method, however; for what I am doing # the list method is not a bottleneck. # The list returned contains the forests encoded by the first encoding # (i. e., they are lists of integers >= -1). listofoforests = [] n = self.n D = mrange([n+1]*n) for ys in D: zs = [i-1 for i in ys] if IsOF(zs): listofoforests.append(zs) return listofoforests def IsOFplus(ys): # INPUT: # list ys of integers (hopefully). # OUTPUT: # true if ys describes an ordered forest WITH RESPECT TO THE SECOND ENCODING; # false otherwise. # "Second encoding" means that the list contains only nonnegative integers. return IsOF([y-1 for y in ys]) class Ordforst(CombinatorialFreeModule): # Hopf algebra of ordered rooted forests over a ring R. # WARNING: They are encoded by the second encoding, so that they appear as # lists of nonnegative integers (in particular, a 0 in such a list means a # root of our forest, whereas a -1 is impossible). def __init__(self, R, **keywords): self._basis = IntegerVectors().filter(IsOFplus) CombinatorialFreeModule.__init__(self, R, self._basis, category=GradedHopfAlgebrasWithBasis(R), **keywords) def _repr_(self): return "The Hopf algebra of ordered rooted forests over %s"%(self.base()) def product_on_basis(self, p, q): n = len(p) # m = len(q) q2 = [i+n if i > 0 else 0 for i in q] return self(p + q2) def one(self): return self([]) def list_coproduct_on_basis(self, p): a = [] n = len(p) q = [i-1 for i in p] # translate into normal syntax for I in Subsets(range(n)): admissiblecut = True for i in I: if q[i] != -1: if not (q[i] in I): admissiblecut = False break # break out of the "for i in I" loop if admissiblecut == True: k = len(I) r = [0]*k s = [0]*(n-k) runnerr = 0 runners = 0 backrefs = [0]*n for i in range(n): if i in I: r[runnerr] = q[i] backrefs[i] = runnerr runnerr += 1 else: if not (q[i] in I): s[runners] = q[i] else: s[runners] = -1 backrefs[i] = runners runners += 1 r1 = [backrefs[i]+1 if i != -1 else 0 for i in r] s1 = [backrefs[i]+1 if i != -1 else 0 for i in s] a.append([s1,r1]) return a def coproduct_on_basis(self, p): a = tensor([self.zero(), self.zero()]) for i in self.list_coproduct_on_basis(p): (b, c) = i a += tensor([self(b), self(c)]) return a def counit_on_basis(self, p): a = 0 if len(p) == 0: a = 1 return a @cached_method def antipode_on_basis(self, p): # the following construction of the antipode is just the # recursive one that follows from id*S = eta epsilon. n = len(p) a = self.zero() if n == 0: a = self.one() for i in self.list_coproduct_on_basis(p): (b, c) = i if b != []: a -= self(b) * self.antipode_on_basis(self._basis(c)) return a #def homogeneous_component(self, n): # to do! #basis = IntegerVectors().filter(IsOFplus).filter... #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 OF = Ordforst(QQ) # OF is the Hopf algebra of ordered forests over the rational numbers. This is where # we will be working. def OFInvolute_on_basis(p): x = OF(p) y = OF.antipode(x) y = OF.antipode(y) return (y - x) OFInvolute = OF.module_morphism(OFInvolute_on_basis, codomain=OF) # OFInvolute is the map S^2 - id : OF -> OF. def OFConvolution(f, g): # INPUT: # two endomorphisms of the vector space OF, given by their restrictions f and g to the standard basis. # OUTPUT: # convolution of these endomorphisms, also restricted to the standard basis. def OFCfg(x): a = OF.zero() ys = OF.list_coproduct_on_basis(x) for y in ys: (b, c) = y a += f(b) * g(c) return a return OFCfg def OFidentity(x): # canonical inclusion of basis of OF into OF return OF(x) # obsolete function: # OFid2 = OFConvolution(OFidentity, OFidentity) def OFidbar(x): # restriction of id - eta epsilon : OF -> OF to the standard basis b = OF.zero() if len(x) != 0: b = OF(x) return b @cached_function def OFidbarpower(n): # INPUT: # nonnegative integer n. # OUTPUT: # restriction of the n-th convolution power of OFidbar to the standard basis. if n == 0: def OFcu(x): # This is just the map eta epsilon (restricted to the standard basis). if len(x) == 0: return OF.one() else: return OF.zero() return OFcu elif n == 1: return OFidbar else: m = int(n) / int(2) M = n - m return OFConvolution(OFidbarpower(m), OFidbarpower(M)) def OFlogid_on_basis(x): # INPUT: # ordered rooted forest x. # OUTPUT: # log* id (x) in OF, where log* means logarithm with respect to convolution. n = len(x) a = OF.zero() #if n != 0: # a = ((-1)**n) * (factorial(n-1)) * (OF([0]))**n # we are using the fact that the n-th term in the exponential # # series has a very simple form, and the higher terms vanish. for i in range(1,n+1): a += QQ((-1)**i) / QQ(i) * (OFidbarpower(i))(x) return (-a) # OFlogid is the logarithm of the identity map id : OF -> OF in the convolution # algebra Hom(OF, OF). OFlogid = OF.module_morphism(OFlogid_on_basis, codomain=OF) def OFlogidcheck_on_basis(x): u = OFlogid_on_basis(x) v = OFlogid(u) return (v - u) def OFDynkinES_on_basis(p): # This will be the image of the basis element p of the # Ordforst Hopf algebra under the Dynkin operator E*S n = len(p) a = OF.zero() for i in OF.list_coproduct_on_basis(p): (b, c) = i k = len(b) a += k * OF(b) * OF.antipode_on_basis(OF._basis(c)) return a OFDynkinES = OF.module_morphism(OFDynkinES_on_basis, codomain=OF) # The Dynkin operator E*S of the Ordforst Hopf algebra. def OFDynkinCheck_on_basis(p): # Transform ordered rooted forest p to (E*S - E) ((E*S) (p)) in # the Ordforest Hopf algebra. # Would be 0 if the Ordforst Hopf algebra was commutative or # cocommutative. n = len(p) b = OFDynkinES_on_basis(p) - n * OF(p) return OFDynkinES(b) OFDynkinCheck = OF.module_morphism(OFDynkinCheck_on_basis, codomain=OF) class listofvectors(): # List of vectors in some given module (not necessarily a concrete # vector space). Certain methods, however, will require the ground # ring to be a field, or at least certain elements of it to be # invertible. # # This probably implements some of 11111 functionality, but it does so # in a rather clumsy way. def __init__(self, basering, module, xs): self.vectors = xs self.basering = basering self.undermodule = module return object.__init__(self) def base_ring(self): return self.basering def underlying_module(self): return self.undermodule def list(self): return self.vectors def show(self): print('List of vectors in module:') print self.undermodule print('over the base ring') print self.basering print('The vectors are:') for i in self.vectors: print i def reduction_blind(self, v): # Computes the reduction of a vector v modulo self, under the # assumption that self is in echelon form already. w = v xs = self.vectors # the vectors in the list - in echelon form, # with highest terms strictly decreasing. for t in xs: wcoeffs = w.monomial_coefficients() tcoeffs = t.monomial_coefficients().items() tleader = max(tcoeffs) if tleader[0] in w.monomial_coefficients(): w = w - (wcoeffs[tleader[0]] / tleader[1]) * t return w @cached_method def echelon(self): # Returns the echelon form of self. This is a list of vectors # which spans the same submodule as self, but has its # sequence of highest terms strictly decreasing. # It is assumed that the module knows division by elements of # the base ring and equality checking. echeloned = [] # The echeloned variable contains a list of # vectors already brought into echelon form. # This list will grow step by step until it # spans the same submodule as self. xs = self.vectors for v in xs: w = v # Now reduce v modulo echelon: for t in echeloned: wcoeffs = w.monomial_coefficients() tcoeffs = t.monomial_coefficients().items() tleader = max(tcoeffs) if tleader[0] in wcoeffs: w = w - (wcoeffs[tleader[0]] / tleader[1]) * t # Now w is the reduction of v modulo echelon. # If w == 0, then v was linearly dependent on echelon, # and we don't have to do anything. # If w != 0, then we now add w to echelon. if w != 0: echeloned.append(w) # w might have been added to the wrong place, so # let us sort. I know this is not the best way; # if the bisect module would allow for keys, then # this would be easy to improve. echeloned.sort(key=lambda x : max(x.monomial_coefficients().items()), reverse=True) return listofvectors(self.basering, self.undermodule, echeloned) def reduction(self, v): # Computes the reduction of a vector v modulo self. return self.echelon().reduction_blind(v) def contains_blind(self, v): # Finds out whether a vector v lies in the submodule generated # by self, under the assumption that self is in echelon form # already. return (self.reduction_blind(v) == 0) def contains(self, v): # Finds out whether a vector v lies in the submodule generated # by self. return (self.reduction(v) == 0) def isbiggerthan(self, anotherlist, verbose=False): # Finds out whether the submodule spanned by self contains that # spanned by anotherlist (another list of vectors). result = True xs = self.echelon() for y in anotherlist.list(): if not xs.contains_blind(y): result = False if verbose == True: print "The offending vector is: " print y break return result def issmallerthan(self, anotherlist, verbose=False): # Finds out whether the submodule spanned by self is contained # in that spanned by anotherlist (another list of vectors). return anotherlist.isbiggerthan(self, verbose=verbose) def isequivalentto(self, anotherlist, verbose=False): # Finds out whether the submodule spanned by self equals # that spanned by anotherlist (another list of vectors). # (For instance, self.isequivalentto(self.echelon()) should # always return True.) u = anotherlist.isbiggerthan(self, verbose=verbose) v = self.isbiggerthan(anotherlist, verbose=verbose) return (u and v) def add(self, anotherlist): # Gives the disjoint union of self with anotherlist (another list # of vectors, which of course should be in the same module). # This union generates the sum of the respective submodules. us = self.vectors us.extend(anotherlist.list()) return listofvectors(self.basering, self.undermodule, us) def product(self, anotherlist): # Gives the list formed by pairwise products of vectors in # self with vectors in anotherlist. # This, of course, makes sense only when the underlying module is # an algebra. # This new list generates the product of the respective submodules # (in the sense in which, e. g., the product of ideals is # defined). us = self.vectors vs = anotherlist.list() ws = [p * q for p in us for q in vs] return listofvectors(self.basering, self.undermodule, ws) def power(self, n): # Returns the n-th power of the list with respect to the # above-defined product function. if n == 0: return listofvectors(self.basering, self.undermodule, [self.undermodule.one()]) elif n == 1: return self else: m = int(n) / int(2) M = n - m return self.power(m).product(self.power(M)) def dimension(self): # Gives the dimension of the submodule generated by self. return len(self.echelon().list()) def image(self, f): # Returns the list of the images of the vectors under a morphism f. # The module in which they lie is the codomain of f. ys = [f(x) for x in self.vectors] return listofvectors(self.basering, f.codomain(), ys) @cached_function def OFbasis(n): # Basis of the n-th graded component of OF, as a listofvectors. xs = OForests(n).list() ys = [OF([i+1 for i in x]) for x in xs] return listofvectors(QQ, OF, ys) @cached_function def OFinvolimage(n): # Basis of the image of the n-th graded component of OF under # S^2 - id, in echelon form. return OFbasis(n).image(OFInvolute).echelon() @cached_function def OFinvolimagefull(n): # Basis of the n-th graded component of (S^2 - id)(OF), in # echelon form. w = listofvectors(QQ, OF, []) for k in range(n+1): for i in range(k+1): if k - i > 2: # this is specific to Ordforst. generally, > 1. r = OFbasis(i).product(OFinvolimage(k-i)).product(OFbasis(n-k)) r = r.echelon() w = w.add(r) w = w.echelon() return w def OFsubalgcomp(U, n): # INPUT: # U: a list of listsofvectors, where each vector in U[i] lies in the # (i+1)-th graded component of OF. # n: an integer. # OUTPUT: # A list of listsofvectors, the i-th of which generates the (i+1)-th # graded component of the subalgebra of OF generated by U. The list # has length n. A = [0]*n l = len(U) if l > n: l = n # forget about the generators that are too high for us to use for i in range(l): A[i] = U[i] for i in range(l, n): A[i] = listofvectors(QQ, OF, []) for i in range(n): for j in range(1,i+1): if i - j < l: A[i] = A[i].add(A[j-1].product(U[i-j])).echelon() return A def OFinvolimageUfull(U, n): # Basis of the n-th graded component of (S^2 - id)(subalgebra with list U), # in echelon form. w = listofvectors(QQ, OF, []) Ubasis = [listofvectors(QQ, OF, [OF.one()])] Ubasis.extend(U) Uinvolimage = [basispart.image(OFInvolute).echelon() for basispart in Ubasis] for k in range(n+1): for i in range(k+1): if k - i > 2: # this is specific to Ordforst. generally, > 1. r = Ubasis[i].product(Uinvolimage[k-i]).product(Ubasis[n-k]) r = r.echelon() w = w.add(r) w = w.echelon() return w def OFconjcheck(n, U): # Checks Dynkin conjecture for given integer n on the n-th # graded component of the subalgebra generated by U. # Note that the answer is only meaningful if U is # the n-th graded component of a graded Hopf subalgebra of OF. # U should be given as a listofvectors. subalg = OFsubalgcomp(U, n) basislist = subalg[n-1] involist = OFinvolimageUfull(subalg, n) dynkinlist = basislist.image(OFDynkinCheck) return involist.isbiggerthan(dynkinlist) OFlogidcheck = OF.module_morphism(OFlogidcheck_on_basis, codomain=OF) def OFconj2check(n, U): # Checks Eulerian conjecture for given integer n on the n-th # graded component of the subalgebra generated by U. # Note that the answer is only meaningful if U is # the n-th graded component of a graded Hopf subalgebra of OF. # U should be given as a listofvectors. subalg = OFsubalgcomp(U, n) basislist = subalg[n-1] involist = OFinvolimageUfull(subalg, n) # eulerlist = basislist.image(OFlogidcheck) # return involist.isbiggerthan(eulerlist, verbose=True) for forest in basislist.list(): if not involist.contains(OFlogidcheck(forest)): print "Counterexample: (log id) o (log id) - (log id) of the forest" print forest print "is not in the ideal generated by (S^2 - id)(our subalgebra)." return "Conjecture wrong." # OFmylist is a list of listsofvectors. The subalgebra of OF which they # generate is a connected graded Hopf subalgebra, and it is this # subalgebra which I used to obtain my counterexample in # counterMO84345.pdf. OFmylist = [listofvectors(QQ, OF, [OF([0])]), listofvectors(QQ, OF, [OF([2,0]), OF([0,1])]), listofvectors(QQ, OF, [OF([2,3,0]), OF([3,0,2])]), listofvectors(QQ, OF, [OF([2,4,0,3])])] # The following function computes a counterexample to the conjecture # that log id (the logarithm of the identity map id : H -> H in the # convolution algebra Hom(H, H)) is an idempotent endomorphism of H # for every involutive Hopf algebra H. (An "involutive Hopf algebra" # means a Hopf algebra whose antipode is an involution. Note that # log id is an idempotent endomorphism of H for many Hopf algebras H, # in particular for all commutative and all cocommutative ones.) # The counterexample lets H be the largest involutive quotient of the # subalgebra of OF generated by the elements in OFmylist (this actually # is a Hopf subalgebra). # The function doesn't really compute in the quotient, but it checks # whether log id is idempotent modulo the ideal generated by the image # of our subalgebra under S^2 - id. This is, of course, equivalent. def OFconj2counterex(): return OFconj2check(5, OFmylist) # SANITY CHECKS: # Here is a sanity check: OFsubalgcomp(OFmylist, 5)[4] should span the # same subspace of OF as the following list OFmylist5(): def OFmylist5(): forlist = [[0,0,0,0,0], [0,0,0,5,0], [0,0,0,0,4], [0,0,4,0,0], [0,0,0,3,0], [0,0,4,5,0], [0,0,5,0,4], [0,3,0,0,0], [0,0,2,0,0], [0,3,0,5,0], [0,0,2,5,0], [0,3,0,0,4], [0,0,2,0,4], [0,3,4,0,0], [0,4,0,3,0], [0,3,5,0,4], [2,0,0,0,0], [0,1,0,0,0], [2,0,0,5,0], [2,0,0,0,4], [0,1,0,5,0], [0,1,0,0,4], [2,0,4,0,0], [2,0,0,3,0], [0,1,4,0,0], [0,1,0,3,0], [2,0,4,5,0], [2,0,5,0,4], [0,1,4,5,0], [0,1,5,0,4], [2,3,0,0,0], [3,0,2,0,0], [2,3,0,5,0], [3,0,2,5,0], [2,3,0,0,4], [3,0,2,0,4], [2,4,0,3,0]] for i in forlist: if not IsOFplus(i): return "Error: "; print i; print "is not a forest" return listofvectors(QQ, OF, [OF(i) for i in forlist]) # yes, it works: # sage: OFsubalgcomp(OFmylist, 5)[4].isequivalentto(OFmylist5()) # True # Testing that the image of OFmylist5() under OFInvolute is really the # same as OFinvolimageUfull(OFsubalgcomp(OFmylist, 5), 5) # OFinvolimageUfull(OFsubalgcomp(OFmylist, 5), 5).isequivalentto(OFmylist5().image(OFInvolute)) # This returns True.