In the exercises below, we assume that the package has been loaded with:
package("Combinat"):
Also, to save some typing, we recommend to export the combinat library:
export(combinat):
1.1. Using existing combinatorial classes
List all the strict partitions of . Hint: use combinat::partitions::list with MaxSlope.
List all the vectors of and of length . Hint: use combinat::integerVectors::list with MaxPart; also try out i^3 $i=1..5, and use _concat.
Pretty print all the Dyck paths of length . Hint: use map, combinat::dyckWords::list, and combinat::dyckWords::printPretty.
List all the Motzkin paths of length (a Motzkin path is similar to a Dyck path, except that horizontal steps are allowed). Hint: use combinat::integerVectors.
Pretty print all the tableaux of size . Hint: use combinat::partitions::list, combinat::tableaux::list and combinat::tableaux::printPretty.
Count the number of partitions of with parts bounded below by . Hint: first try out how far you can go with combinat::partitions. Then, switch to combinat::decomposableObjects and use the constructors Multiset and Sequence with the MinLength and MaxLength options. Finally, optimize your grammar by implementing a combinatorial class for . Hint: check the examples of use of combinat::decomposableObjects in the guided tour.
Count how many distinct expressions can be built from the variables {x, y, z} and two binary operators f and g, with 10 variables altogether. Hint: use combinat::decomposableObjects, with the constructors Atom,Epsilon,Prod,Union. Then, display those with 3 and 4 variables. Improve the pretty printing using either a substitution, or the Alias constructor.
Try and analyze the following piece of code:
g := combinat::partitions::generator(4):
while (p := g()) <> FAIL do
print(p, combinat::partitions::printPretty(p))
end_while
Analyze the following piece of code:
makeGenerator :=
proc()
option escape;
local i;
begin
i := 0;
proc() begin i:=i+1; end;
end:
g:=makeGenerator():
g(), g(), g(), g(), g()
Modify it to build a generator for the cube powers of integers: 1, 8, 27, ...
Write a function that takes a power and returns a generator for all the -th powers of integers.
Reimplement those generators using the functions combinat::generators::fromNext and combinat::generators::map.
Build a generator for all the standard tableaux of size . Hint: use combinat::generators::pipe.
Build a generator for all the standard tableaux of any size.
Write a function of one argument n which returns a generator for all the Motzkin words of length n. Hint: use closures and don't forget the escape option.
Compute the average number of inversions among all the permutations of that avoid the pattern [1,4,3,2]. Hint: use combinat::permutations::inversionsNumber and combinat::permutations::hasPattern, and try out the following example:
select([1,2,3,4,5,6,7,8], not isprime);
Evaluate the complexity in time and memory of this computation.
Compute the same thing with a memory complexity of . Hint: use generators, combinat::generators::select, and try out this example:
makeAverager :=
proc()
option escape;
local sum,n;
begin
sum:=0;
n:=0;
proc(x)
begin
if args(0) = 0 then // call without argument
sum/n
else
sum := sum + x; // call with one argument
n := n + 1;
end_if;
end_proc;
end_proc:
g := makeAverager(): // create a new averager
g(1), g(5), g(0), g(10): // accumulate the numbers
g(); // return their average
1.3. Implementing new algebras
Implement the algebra SetAlgebra whose basis is indexed by sets and product given by the union of sets. Hint: look for the implementation of FreeAlgebra in the guided tour, use combinat::subsets as combinatorial class, and see ?_union.
Implement the natural morphism from FreeAlgebra to SetAlgebra which sends [a,c,a,a,b,c] to {a,b,c}.
1.3.2. The shuffle Hopf algebra
Implement the shuffle algebra ShuffleAlgebra on compositions. Hint: look for the implementation of FreeAlgebra in the guided tour, use combinat::words::shuffle, and try out
_plus(x^i $ i in [1,5,6,8])
Implement a function coconcat(u) that returns the list of all the couples of words and such that :
coconcat([1, 2, 3])
Make the shuffle algebra into a Hopf algebra (category Cat::HopfAlgebraWithBasis) by inserting the following method:
coproductBasis :=
proc(u: words) : ShuffleAlgebra
local v;
begin
_plus(dom::tensorSquare::term(v) $ v in coconcat(u))
end_proc:
You can now compute the coproduct of any element of the algebra using operators::coproduct, and reciprocally use operators::mu to compute the image in ShuffleAlgebra of any element of via the product. You may wish to issue:
export(operators, coproduct, mu):
Use this to check, on some examples, that this is indeed a Hopf algebra; that is that the product and coproduct are compatible.
Add the missing implementations for the counit and the antipode of the Hopf algebra.
Add a degree method to make ShuffleAlgebra into a graded Hopf algebra (Cat::GradedHopfAlgebraWithBasis), and write a procedure that checks systematically the compatibility of the product and coproduct up to a given degree.
coconcat := proc(l) local i; begin [ [[op(l,1..i)], [op(l, i+1..nops(l))]] $ i = 0 .. nops(l)] end:
We check its behavior:
coconcat([1, 2, 3])
prog::test(coconcat([a, b, b, c]),
[[[], [a, b, b, c]], [[a], [b, b, c]], [[a, b], [b, c]], [[a, b, b], [c]], [[a, b, b, c], []]]):
prog::test(coconcat([]),
[[[], []]]):
prog::test(coconcat([a]),
[[[], [a]], [[a], []]]):
Here is now the full featured code for the shuffle algebra:
domain ShuffleAlgebra
inherits Dom::FreeModule(Dom::Rational, combinat::words);
category Cat::GradedHopfAlgebraWithBasis(Dom::Rational);
degreeBasis := nops;
one := dom::term([]);
mult2Basis :=
proc(t1,t2)
begin
_plus(dom::term(v) $ v in combinat::words::shuffle(t1,t2));
end;
coproductBasis :=
proc(u: dom::basisIndices) : dom::tensorSquare
local v;
begin
_plus(dom::tensorSquare::term(v) $ v in coconcat(u))
end_proc;
end_domain:
Some sample computations:
ShuffleAlgebra([1, 2, 3])*ShuffleAlgebra([4, 5])
export(operators, coproduct):
a:=ShuffleAlgebra([1,2,3]): b:=ShuffleAlgebra([4,5]):
coproduct(a)*coproduct(b) - coproduct(a*b)
1.4. The degenerate Hecke Algebra
The Iwahori-Hecke algebra is the -algebra generated by elements for with the relations:
.
The -Hecke algebra is obtained by setting in these relations. Then, the first relation becomes . Let .
Use combinat::subClass to define the combinatorial class of the permutations of .
Define a parameterized domain HeckePi(n) for the Hecke algebra in the basis over the rational numbers (Dom::Rational).
Define the elementary generator . Check some braid relations.
Define a parameterized domain HeckeT(n) for the Hecke algebra in the basis over the rational numbers (Dom::Rational).
Check for small that sum and alternating sum of the are two idempotents.
Define the change of basis between the two versions. This can be done by hands or using the Bruhat order (combinat::permutations::smallerBruhat). Make the conversion automatic.
We need to compute with different coefficients, in particular we often need to compute with unknown coefficients taken out Dom::ExpressionField(). Modify the two parameterized domains HeckePi(n) and HeckeT(n) so that they accept a ring for second parameter with Dom::ExpressionField() as default value.
As a application we want now to compute the radical of . We use a characterization from Dickson. Let be a sub algebra of for a field of zero characteristic. Then is in the radical of if and only if the trace of each in the two sided (resp. left, right) ideal generated by (, resp. , ) is zero. For finite dimensional algebra , we realize as a matrix algebra by considering any faithful representation, for example the regular one.
Let be the generic element of . Compute and the spanning family for the ideal it generates.
Write a function trace that compute the trace of the endomorphism where .
Using Dickson criterion, compute the equation of the radical of .
What is the dimension of the radical, of the quotient ?
Write a function radNormal that normalize an element of modulo its radical.
Suppose that is an algebra with a basis . In MuPAD, is a certain domain Alg. The basis of is indexed by the element of the domain Alg::basisIndices. Like all combinatorial domain this domain may have a list method which can be called by Alg::basisIndices::list.
Write a function GetBasis to compute a basis of an algebra or more generally of a free module.
Write a function Generic Element to compute a generic element;
Write a function Radical to compute the radical of an algebra.
Perm := n -> combinat::subClass(combinat::permutations, Parameters=n):
domain SGAx(n: Type::NonNegInt)
category Cat::AlgebraWithBasis(Dom::ExpressionField());
inherits Dom::FreeModule(Dom::ExpressionField(), Perm(n));
axiom Ax::normalRep;
one := dom::term( [ $ 1..n ] );
mult2Basis :=
proc(p1: dom::basisIndices, p2: dom::basisIndices)
begin
dom::term( dom::basisIndices::_mult(p1,p2) );
end_proc;
end_domain:
domain Hecke0(n: Type::NonNegInt)
category Cat::AlgebraWithBasis(Dom::ExpressionField());
inherits Dom::FreeModule(Dom::ExpressionField(), Perm(n));
axiom Ax::normalRep;
basisName := hold(pi);
one := dom::term( [ $ 1..n ] );
mult2Basis :=
proc(p1: dom::basisIndices, p2: dom::basisIndices)
local tmp;
begin
for t in combinat::permutations::reducedWord(p2) do
if p1[t] < p1[t+1] then
tmp := p1[t];
p1[t] := p1[t+1];
p1[t+1]:= tmp;
end_if;
end_for;
dom::term(p1);
end_proc;
end_domain:
H3 := Hecke0(3):
H3([2,1,3])^2;
Pi1 := H3([2,1,3]);
Pi2 := H3([1,3,2]);
Pi1*Pi2*Pi1 - Pi2*Pi1*Pi2;
Perm3:=Perm(3):
_plus(combinat::permutations::sign(p)*H3(p) $ p in Perm3::list()) ;
x:=_plus(combinat::permutations::sign(p)*H3(p) $ p in Perm3::list()) ;
x^2;
x^2-x ;
delete(a);
y := _plus( a[op(p)]*H3(p) $ p in Perm3::list() ) ;
makeCoeff := p -> hold(a)[op(p)];
y:=H3::genericElement(makeCoeff) ;
y^2-y ;
//res := solve([coeff(y^2-y)], H3::genericCoefficients(makeCoeff)):
//nops(res) ;