This talk will discuss four concepts:
Getting Started: Free Modules / Vector Spaces
We begin with a minimal example. What does this give us?
{{{id=3| A = CombinatorialFreeModule(ZZ, Zmod(5)); /// }}} {{{id=37| A. /// }}} {{{id=8| A.an_element() /// B[0] + 3*B[1] + 3*B[2] }}}We can use any set whose elements are immutable as a basis.
{{{id=40| A = CombinatorialFreeModule(ZZ, CC); A.an_element() /// B[1.00000000000000*I] }}} {{{id=41| A = CombinatorialFreeModule(ZZ, Partitions(NonNegativeIntegers(), max_part=3)); A.an_element() /// B[[]] + 2*B[[1]] + 3*B[[2]] }}} {{{id=43| A = CombinatorialFreeModule(ZZ, ['spam', 'eggs', 42]); A.an_element() /// 2*B['eggs'] + 2*B['spam'] + 3*B[42] }}} {{{id=44| A = CombinatorialFreeModule(ZZ, ([1],[2],[3])); A.an_element() /// Traceback (most recent call last): File "We can customize the name of the basis however we want.
{{{id=94| A = CombinatorialFreeModule(ZZ, Zmod(5), prefix='a'); A.an_element() /// a[0] + 3*a[1] + 3*a[2] }}}Working with elements
{{{id=7| f = A.an_element(); f /// a[0] + 3*a[1] + 3*a[2] }}} {{{id=115| # We can perform linear operations on the elements of A print f print 2*f print 2*f - f /// a[0] + 3*a[1] + 3*a[2] 2*a[0] + 6*a[1] + 6*a[2] a[0] + 3*a[1] + 3*a[2] }}} {{{id=287| a[0] + 3*a[1] /// Traceback (most recent call last): File "To refer to elements directly, we must first get the basis for the module.
{{{id=17| a = A.basis() a[0] + 3*a[1] # copy-paste works if the prefix matches the name of the basis /// a[0] + 3*a[1] }}} {{{id=179| a[0] + 3*a[1] + 3*a[2] == f /// True }}} {{{id=68| a['is'] + a['this'] + a['a'] + a['bug'] # be careful, the input generally is *not* checked /// a['a'] + a['bug'] + a['is'] + a['this'] }}} {{{id=289| a /// Lazy family (Term map from Ring of integers modulo 5 to Free module generated by Ring of integers modulo 5 over Integer Ring(i))_{i in Ring of integers modulo 5} }}}A.basis() models the family $(B_i)_{i \in \ZZ_5}$. See the documentation for Family for more information.
{{{id=91| Family? /// }}}The elements of our module come with many methods for exploring/manipulating them:
{{{id=67| f. /// }}}Some notation:
Note that elements are printed starting with the (lexicographically by default) least index. leading/trailing refers to the greatest/least index, respectively.
{{{id=19| print f print "Leading term: ",f.leading_term() print "Leading monomial: ",f.leading_monomial() print "Leading support: ",f.leading_support() print "Leading coefficient: ",f.leading_coefficient() print "Leading item: ",f.leading_item() /// a[0] + 3*a[1] + 3*a[2] Leading term: 3*a[2] Leading monomial: a[2] Leading support: 2 Leading coefficient: 3 Leading item: (2, 3) }}} {{{id=278| f.leading_term? /// }}} {{{id=277| print "Support: ",f.support() print "Monomials: ",f.monomials() print "Coefficients: ",f.coefficients() /// Support: [0, 1, 2] Monomials: [a[0], a[1], a[2]] Coefficients: [1, 3, 3] }}} {{{id=283| # We can iterate through the items in an element for index, coeff in f: print "The coefficient of a_{%s} is %s"%(index, coeff) /// The coefficient of a_{0} is 1 The coefficient of a_{1} is 3 The coefficient of a_{2} is 3 }}} {{{id=290| # This uses the fact that f can be thought of as a dictionary index-->coefficient print f[0], f[1], f[2] /// 1 3 3 }}} {{{id=20| # This dictionary can be accessed explicitly with the monomial_coefficients method print f.monomial_coefficients() /// {0: 1, 1: 3, 2: 3} }}}The parent ($A$ in our example) has methods that are convenient for constructing elements.
{{{id=71| A. /// }}} {{{id=82| A.zero() /// 0 }}} {{{id=286| print A.sum_of_monomials(i for i in Zmod(5) if i > 2) print A.sum_of_terms((i+1,i) for i in Zmod(5) if i > 2) print A.sum(ZZ(i)*a[i+1] for i in Zmod(5) if i > 2) # Note coeff is not (currently) implicitly coerced /// a[3] + a[4] 4*a[0] + 3*a[4] 4*a[0] + 3*a[4] }}} {{{id=284| # It is safer to use A.sum() then to use sum() print A.sum([]),':', parent(A.sum([])) print sum([]),':', parent(sum([])) /// 0 : Free module generated by Ring of integers modulo 5 over Integer Ring 0 :The `map` methods are useful ways to transform elements:
{{{id=75| f.map_ /// }}} {{{id=73| print f,"-->", f.map_support (lambda i : i+3) print f,"-->", f.map_coefficients(lambda c : c-1) print f,"-->", f.map_term (lambda i,c: (i+3,c-1)) # f.map_mc is a deprecated synonym for f.map_term /// a[0] + 3*a[1] + 3*a[2] --> 3*a[0] + a[3] + 3*a[4] a[0] + 3*a[1] + 3*a[2] --> 2*a[1] + 2*a[2] a[0] + 3*a[1] + 3*a[2] --> 2*a[0] + 2*a[4] }}}Note: term and item are obviously not used completely consistently (yet)
This fully functional ZZ-module was created with the simple commands
A = CombinatorialFreeModule(ZZ, Zmod(5), prefix='a')
a = A.basis()
But we can do more...
Subclassing / Including Category Information
To define multiplication, we should be in a category where multiplication makes sense.
{{{id=78| A.category() /// Category of modules with basis over Rational Field }}}We can look at the available categories from the documentation in the reference manual:
http://sagemath.com/doc/reference/categories.html
Or we can use introspection...
{{{id=62| sage.categories. # Look through the list of categories to pick one we want /// }}} {{{id=79| E = AlgebrasWithBasis(QQ).example(); E # Look at an example, to see which methods to define /// An example of an algebra with basis: the free algebra on the generators ('a', 'b', 'c') over Rational Field }}} {{{id=233| e = E.an_element(); e /// B[word: ] + 2*B[word: a] + 3*B[word: b] }}} {{{id=80| E?? /// }}} {{{id=56| class MyCyclicGroupAlgebra(CombinatorialFreeModule): r"""Note: We would typically use the GroupAlgebra category that already exists. This is just an easy-to-implement example of the more general AlgebrasWithBasis category. """ # Copy and paste from our module implementation and source code of E def __init__(self, R, n, *args, **kwargs): """ TODO: Informative doc-string and examples """ self._n = n CombinatorialFreeModule.__init__(self, R, Zmod(n), category=AlgebrasWithBasis(R), *args, **kwargs) # Note that the following won't work if we choose a category without a product. def product_on_basis(self, left, right): r""" Product of basis elements, as per :meth:`AlgebrasWithBasis.ParentMethods.product_on_basis`. INPUT: - ``left``, ``right`` - indices of basis elements OUTPUT: - The element of self that is the product of the basis elements indexed by ``left`` and ``right`` """ return self.monomial( Zmod(self._n)(left + right) ) @cached_method def one_basis(self): r""" Returns the index of the basis element which is equal to '1'.""" return Zmod(self._n)(0) # The following methods are optional def _repr_(self): return "Jason's group algebra of the cyclic group Zmod(%s) over %s"%(self._n, self.base_ring()) @cached_method def algebra_generators(self): r""" Returns the generators of this algebra, as per :meth:`Algebras.ParentMethods.algebra_generators`. """ return Family( [self.monomial( Zmod(self._n)(1))] ) # We could have defined the following instead of product_on_basis: # def product(self, left, right): # r""" # Product of basis elements, as per :meth:`AlgebrasWithBasis.ParentMethods.product`. # # INPUT: # # - ``left``, ``right`` - elements of self # # OUTPUT: # # - The element of self that is the product of ``left`` and ``right`` # """ # return ## something ## /// }}} {{{id=83| # Let's look at the methods in the ParentMethods class of sage.categories.algebras_with_basis sage.categories.algebras_with_basis?? /// }}} {{{id=60| A = MyCyclicGroupAlgebra(QQ, 2, prefix='a') # or 4 or 5 or 11 ... a = A.basis(); f = A.an_element(); A, f /// (Jason's group algebra of the cyclic group Zmod(2) over Rational Field, a[0] + 3*a[1]) }}} {{{id=46| f * f /// 10*a[0] + 6*a[1] }}} {{{id=180| f. /// }}} {{{id=57| f.is_idempotent() /// False }}} {{{id=55| A.one() /// a[0] }}} {{{id=120| x = A.algebra_generators().first() # Typically x,y,... = A.algebra_generators() [x^i for i in range(4)] /// [a[0], a[1], a[0], a[1]] }}} {{{id=90| g = 2*a[1]; (f + g)*f == f*f + g*f /// True }}}TestSuite is a tool which will perform many routine tests of our algebra for us.
{{{id=124| TestSuite? /// }}} {{{id=281| TestSuite(A).run(verbose=True) /// running ._test_additive_associativity() . . . pass running ._test_an_element() . . . pass running ._test_associativity() . . . pass running ._test_category() . . . pass running ._test_elements() . . . Running the test suite of self.an_element() running ._test_category() . . . pass running ._test_not_implemented_methods() . . . pass running ._test_pickling() . . . pass pass running ._test_not_implemented_methods() . . . pass running ._test_one() . . . pass running ._test_pickling() . . . pass running ._test_prod() . . . pass running ._test_some_elements() . . . pass running ._test_zero() . . . pass }}} {{{id=292| # For more information on categories sage.categories.primer? /// }}}Review:
We wanted to create an algebra, so we
Morphisms
Creation of algebraic spaces isn't always enough. Often, we want to understand relationships between spaces. The module_morphism class helps us do this.
Diagonal and Triangular Morphisms
These currently require the domain and codomain to have the same index set (in progress...).
Coercions
Once we have defined a morphism from $X \to Y$, we can register it as a coercion. This will allow Sage to apply the morphism automatically when we refer to elements of $X$ and $Y$ together. See http://sagemath.com/doc/reference/coercion.html for more information.
{{{id=261| SF = SymmetricFunctions(QQ); # A GradedHopfAlgebraWithBasis h = SF.homogeneous() # A particular basis, indexed by partitions (with some additional magic) # Recall the definition: # h([i]) is the sum of all monomials of degree i print h([2]).expand(4) /// x0^2 + x0*x1 + x1^2 + x0*x2 + x1*x2 + x2^2 + x0*x3 + x1*x3 + x2*x3 + x3^2 }}} {{{id=268| # And h(mu) = prod( h(p) for p in mu ) h([3,2,2,1]) == h([3]) * h([2]) * h([2]) * h([1]) /// True }}} {{{id=262| def triang_on_basis(p): return h.sum_of_monomials(mu for mu in Partitions(sum(p)) if mu >= p) triang_on_basis([3,2]) /// h[3, 2] + h[4, 1] + h[5] }}} {{{id=263| X_to_h = X.module_morphism(triang_on_basis, triangular='lower', unitriangular=True, codomain=h) /// }}} {{{id=165| X_to_h. /// }}} {{{id=264| X_to_h.register_as_coercion() /// }}} {{{id=157| h(x[Partition([3,2])]) /// h[3, 2] + h[4, 1] + h[5] }}} {{{id=187| h([2,2,1]) + x[Partition([2,2,1])] /// 2*h[2, 2, 1] + h[3, 1, 1] + h[3, 2] + h[4, 1] + h[5] }}} {{{id=189| # This can be used to define a product class MySFBasis(CombinatorialFreeModule): r"""Note: We would typically use SymmetricFunctionAlgebra_generic for this. This is as an example only. """ def __init__(self, R, *args, **kwargs): """ TODO: Informative doc-string and examples """ CombinatorialFreeModule.__init__(self, R, Partitions(), category=AlgebrasWithBasis(R), *args, **kwargs) self._h = SymmetricFunctions(R).homogeneous() self._to_h = self.module_morphism( self._to_h_on_basis, triangular='lower', unitriangular=True, codomain=self._h) self._from_h = ~(self._to_h) self._to_h.register_as_coercion() self._from_h.register_as_coercion() def _to_h_on_basis(self, la): return self._h.sum_of_monomials(mu for mu in Partitions(sum(la)) if mu >= la) def product(self, left, right): return self( self._h(left) * self._h(right) ) def _repr_(self): return "Jason's basis for symmetric functions over %s"%self.base_ring() @cached_method def one_basis(self): r""" Returns the index of the basis element which is equal to '1'.""" return Partition([]) /// }}} {{{id=190| X = MySFBasis(QQ, prefix='x'); x = X.basis(); h = SymmetricFunctions(QQ).homogeneous() /// }}} {{{id=191| f = X(h([2,1,1]) - 2*h([2,2])) # Note the capital X print f print h(f) /// x[[2, 1, 1]] - 3*x[[2, 2]] + 2*x[[3, 1]] h[2, 1, 1] - 2*h[2, 2] }}} {{{id=193| f*f*f /// x[[2, 2, 2, 1, 1, 1, 1, 1, 1]] - 7*x[[2, 2, 2, 2, 1, 1, 1, 1]] + 18*x[[2, 2, 2, 2, 2, 1, 1]] - 20*x[[2, 2, 2, 2, 2, 2]] + 8*x[[3, 1, 1, 1, 1, 1, 1, 1, 1, 1]] }}} {{{id=200| h(f*f) /// h[2, 2, 1, 1, 1, 1] - 4*h[2, 2, 2, 1, 1] + 4*h[2, 2, 2, 2] }}}A final example:
{{{id=265| class MySFQuotient(CombinatorialFreeModule): r""" The quotient of the ring of symmetric functions by the ideal generated by those monomial symmetric functions whose part is larger than some fixed number k.""" def __init__(self, R, k, prefix=None, *args, **kwargs): # Note: Setting self._prefix is equivalent to using the prefix keyword # in CombinatorialFreeModule.__init__ if prefix is not None: self._prefix = prefix else: self._prefix = 'mm' CombinatorialFreeModule.__init__(self, R, Partitions(NonNegativeIntegers(), max_part=k), category = GradedHopfAlgebrasWithBasis(R), *args, **kwargs) self._k = k self._m = SymmetricFunctions(R).monomial() self.lift = self.module_morphism(self._m.monomial) self.retract = self._m.module_morphism(self._retract_on_basis, codomain=self) self.lift.register_as_coercion() self.retract.register_as_coercion() def _retract_on_basis(self, mu): r""" Takes the index of a basis element of a monomial symmetric function, and returns the projection of that element to the quotient.""" if len(mu) > 0 and mu[0] > self._k: return self.zero() return self.monomial(mu) @cached_method def one_basis(self): return Partition([]) def product(self, left, right): return self( self._m(left) * self._m(right) ) /// }}} {{{id=270| MM = MySFQuotient(QQ, 3) mm = MM.basis() m = SymmetricFunctions(QQ).monomial() /// }}} {{{id=274| P = Partition /// }}} {{{id=271| f = mm[P([3,2,1])] + 2*mm[P([3,3])] print f /// mm[[3, 2, 1]] + 2*mm[[3, 3]] }}} {{{id=275| print m(f) print print (m(f))^2 print print f^2 print print (m(f))^2 - m(f^2) print print MM( (m(f))^2 - m(f^2) ) /// m[3, 2, 1] + 2*m[3, 3] 8*m[3, 3, 2, 2, 1, 1] + 12*m[3, 3, 2, 2, 2] + 24*m[3, 3, 3, 2, 1] + 48*m[3, 3, 3, 3] + 4*m[4, 3, 2, 2, 1] + 4*m[4, 3, 3, 1, 1] + 14*m[4, 3, 3, 2] + 4*m[4, 4, 2, 2] + 4*m[4, 4, 3, 1] + 6*m[4, 4, 4] + 4*m[5, 3, 2, 1, 1] + 4*m[5, 3, 2, 2] + 12*m[5, 3, 3, 1] + 2*m[5, 4, 2, 1] + 6*m[5, 4, 3] + 4*m[5, 5, 1, 1] + 2*m[5, 5, 2] + 4*m[6, 2, 2, 1, 1] + 6*m[6, 2, 2, 2] + 6*m[6, 3, 2, 1] + 10*m[6, 3, 3] + 2*m[6, 4, 1, 1] + 5*m[6, 4, 2] + 4*m[6, 5, 1] + 4*m[6, 6] 8*mm[[3, 3, 2, 2, 1, 1]] + 12*mm[[3, 3, 2, 2, 2]] + 24*mm[[3, 3, 3, 2, 1]] + 48*mm[[3, 3, 3, 3]] 4*m[4, 3, 2, 2, 1] + 4*m[4, 3, 3, 1, 1] + 14*m[4, 3, 3, 2] + 4*m[4, 4, 2, 2] + 4*m[4, 4, 3, 1] + 6*m[4, 4, 4] + 4*m[5, 3, 2, 1, 1] + 4*m[5, 3, 2, 2] + 12*m[5, 3, 3, 1] + 2*m[5, 4, 2, 1] + 6*m[5, 4, 3] + 4*m[5, 5, 1, 1] + 2*m[5, 5, 2] + 4*m[6, 2, 2, 1, 1] + 6*m[6, 2, 2, 2] + 6*m[6, 3, 2, 1] + 10*m[6, 3, 3] + 2*m[6, 4, 1, 1] + 5*m[6, 4, 2] + 4*m[6, 5, 1] + 4*m[6, 6] 0 }}} {{{id=273| /// }}}