1. Exercises
In the exercises below, we assume that the package has been loaded with:
Also, to save some typing, we recommend to export the combinat library:
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.
1.2. Using generators
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
1.3.1. The set algebra
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.
1.3.2.1. Correction
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.
1.4.1. Correction
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) ;
