# 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.