////////////////////////////////////////////////////////////////////////////// // $Id: Tutorial.mu,v 1.6 2001/06/14 22:21:43 nthiery Exp $ // Name: Tutorial.mu // Purpose: A tutorial for PerMuVAR // Author: Nicolas M. Thiéry // Created: 2000/10 // Copyright: LGPL ////////////////////////////////////////////////////////////////////////////// // Part I : Basic operations on permutation groups // Part II : Basic operations on invariants // Part III: Studying the invariant ring // Part IV : Positive characteristic computations ////////////////////////////////////////////////////////////////////////////// // Part I: Basic operations on permutation groups ////////////////////////////////////////////////////////////////////////////// // Load the library PerMuVAR. // We assume MuPAD is already configured for PerMuVAR. For details, // see the file 'QuickInstall', section 'MuPAD configuration'. loadlib("PerMuVAR"): // Let's define the full symmetric group acting of {1..4} n:=4; S4:=Dom::PermutationGroup(n); // and list all permutations in S4 S4::allElements; // Define a permutation, and let it act on integers, or on lists p:=S4([4,3,2,1]); p(3); p([a,b,c,d]); // Define a permutation from it's disjoint cycle representation p:=S4([[1,2],[3,4]]); // Take a list, and put it in canonical form under the action of S4 S4::canonic([1,2,2,3]); // Define the cyclic group on 4 elements by mean of generators. C4 := Dom::PermutationGroup(4, [[[1,2,3,4]]]); // Define the alternating group A4 A4 := Dom::AlternatingGroup(4); // Define the natural action of the group S3 x C4 on the cartesian // product [1..3] x [1..4] S3 := Dom::SymmetricGroup(3); PS3P4 := Dom::PermutationGroupDirectProduct([S3, C4]); // Define the action of the symmetric group S4 on pairs of {1..4} G4 := Dom::PermutationGroupOnSets(S4,2); // Some information about the group G4::allCategories(); G4::size; // The size of the group G4::set; // The set on which G4 acts G4::card; // The size of this set // Let q be the permutation induced on pairs of {1..4} by the // permutation [4,3,2,1] q:=G4::induced(S4([4,3,2,1])); q({1,2}); // Action of q on lists. Note that each such list corresponds to a non // oriented multigraph on 4 nodes, and each list of 0 and 1 // corresponds to a simple non oriented graph. q([1,1,0,0,0,0]); // Pólya cycle indicator polynomial G4::cycleIndicatorPoly(z); // Pólya enumeration. This gives the generating series of the simple // graphs on 4 nodes by number of edges. expand(G4::weightEnum([1,t])); ////////////////////////////////////////////////////////////////////////////// // Part II: Basic operations on invariants ////////////////////////////////////////////////////////////////////////////// // Let's look at the simple case of the symmetric polynomial on 4 // variables, with rational coefficients. S4:=Dom::SymmetricGroup(4); IS4:=Dom::PermutationGroupInvariantRing(Dom::Rational, S4); // Given a monomial, say m:=x_1x_2x_3, the orbit sum of m is the sum // of all the monomials in the orbit of m by the action of the group. // For example, the orbit sum of m under the action of S4 is // x_1x_2x_3 + x_1x_2x_4 + x_1x_3x_4 + x_2x_3x_4 // PerMuVAR stores and display orbit sums compactly, by just keeping // track of the leading monomial. // // Monomials themselves are stored as list of non-negative integers; // the ith entry of the list is the power of the ith variable. // // Time for an example, the following defines the orbit sum of x_1^3. // Only the leading term is displayed. but this really represents the // symmetric powersum of degree 3. p3:=IS4([3,0,0,0]); IS4::poly(p3); // Same thing for the elementary symmetric polynomial of degree 3: e3:=IS4([1,1,1,0]); IS4::poly(e3); // Actually, you could get those invariants directly IS4::elementary(3); IS4::powersum(3); // Now we can form linear combination of orbit sums p3+4*e3; IS4::poly(p3+4*e3); // Or even product of orbit sums p3*e3; IS4::poly(p3*e3); // As you can see, PerMuVAR has rewritten the result as a linear // combination of orbit sums. Actually, any invariant can be uniquely // written as a linear combination of orbit sums (this follows easily // from the fact that a group of permutations sends monomials to // monomials). ////////////////////////////////////////////////////////////////////////////// // Part III: Studying the invariant ring ////////////////////////////////////////////////////////////////////////////// // Let's now move on to more advanced stuff. We refer to the // litterature for details. // Define the ring of invariant of the cyclic group C4 C4 :=Dom::PermutationGroup(4, [[[$1..4]]]); IC4:=Dom::PermutationGroupInvariantRing(Dom::Rational, C4); // Some information on the invariant ring IC4::dimen; IC4::isModular; IC4::isCohenMacaulay; IC4::isGorenstein; IC4::degreeBound(); IC4::degreeLowerBound(); IC4::degreeBoundIsOptimal(); // In this case, the degree bound is tight, but this is usually not // the case for bigger groups. Actually Noether degree bound is only // optimal for cyclic groups. Note that PerMuVAR also tries other // techniques to get a reasonnable degree bound, but most of the time, // it's still way of. This is really bad because the complexity of // most algorithms depends in first place on the quality of the degree // bound. If by chance you know in advance a good degree bound, please // set it using something like: IC4::degreeBound():=4; // Compute the Hilbert Series of IC4. This is the generating series of // the homogeneous components of degree d of the invariant ring. This // is also the generating series of orbit sums by degree. IC4::HilbertSeries(z); // Primary invariants of C4. By default, it's the symmetric powersums, // but you could set your own primary invariants using // IC4::setPrimaryInvariants. IC4::primaryInvariants(); // Compute the generating series of secondary invariants of IC4 IC4::secondaryInvariantsSeries(z); // Compute secondary invariants themselves for IC4 IC4::secondaryInvariants(); // This gives us a Hironaka decomposition of IC4. As a by-product, we // get irreducible secondary invariants for IC4: IC4::irreducibleSecondaryInvariants(); // Together with the primary invariants, the irreducible secondary // invariants form a reasonnably small homogeneous generating set of // the invariant ring. To be precise, it's a generating set which is // minimal among all generating sets containing the primary // invariants. // The information on the degree bound has been updated IC4::degreeBound(); IC4::degreeLowerBound(); IC4::degreeBoundIsOptimal(); // We can also compute directly a minimal generating set. This is // usually faster than computing a Hironaka decomposition. IC4::minimalGeneratingSet(); // Let's come back for a minute to the ring IS4 of symmetric // polynomial in 4 variables. It has a very nice Hilbert Series, which // incidently is also the generating series of partitions of d in 4 // parts. factor(IS4::HilbertSeries(z)); // Also, IS4 has only one secondary invariant. Indeed, IS4 is a // polynomial ring over the primary invariants! IS4::secondaryInvariantsSeries(z); ////////////////////////////////////////////////////////////////////////////// // Part IV: Positive characteristic computations ////////////////////////////////////////////////////////////////////////////// // Warning: everything below is right now experimental! I may be // buggy, if not completely incorrect. // The invariant ring of C5 with coefficients in Z/5Z C5 :=Dom::PermutationGroup(5, [[[$1..5]]]); IC5:=Dom::PermutationGroupInvariantRing(Dom::IntegerMod(5),C5); IC5::isModular; IC5::isCohenMacaulay; IC5::isGorenstein; IC5::degreeBound(); // Computation of a minimal generating set. // We don't have a good a priori degree bound, so we need to do the // full computation up to degree 10. This may take a few minutes! IC5::minimalGeneratingSet(); // Check that the degree bound is indeed (2p-3) IC5::degreeBound(); // The algorithm to compute Hironaka decomposition still works in the // modular case. Of course, the invariant ring may not be // Cohen-Macaulay, in which case the invariant ring will not be a // free-module over the primary invariants. The secondary invariants // will still generate the ring as a module, but will not be // independant. If the algorithm stumble on such a relation, it will // set dom::isCohenMacaulay to FALSE. // // Caveats: the algorithm won't use the Hilbert series to predict the // number of secondary invariants at each degree, which is good. On // the other hand, it will still use it as a stopping condition for // the degree, which may be completely incorrect! So, just consider // the result as a partial system of secondary invariants up to the // degree of dom::secondaryInvariantsSeries(). // The invariant ring of C3 with coefficients in Z/3Z C3 :=Dom::PermutationGroup(3, [[[$1..3]]]); IC3:=Dom::PermutationGroupInvariantRing(Dom::IntegerMod(3),C3); IC3::secondaryInvariants(); // The computation has detected a relation between the secondary invariants. IC3::isCohenMacaulay;