Tutorial: Implementing Algebraic Structures
system:sage


Tutorial: Implementing Algebraic Structures -- Sage Reference Manual v4.4.4
system:sage

<div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../genindex.html" title="General Index" accesskey="I">index</a></li>
        <li class="right">
          <a href="../modindex.html" title="Global Module Index" accesskey="M">modules</a> |</li>
  
    
      <a href="../../index.html"><img src="../_static/sagelogo.png" style="vertical-align: middle" title="Sage Logo"></a>
    
  
  
        <li><a href="../index.html">Sage Reference v4.4.4</a> &raquo;</li>
 
      </ul>
    </div>  

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body">
            
  <div class="section" id="tutorial-implementing-algebraic-structures">
<h1>Tutorial: Implementing Algebraic Structures<a class="headerlink" href="#tutorial-implementing-algebraic-structures" title="Permalink to this headline">¶</a></h1>
<p>This tutorial will discuss five concepts:</p>
<blockquote>
<ul class="simple">
<li>constructing and manipulating new modules/vector spaces</li>
<li>adding more algebraic structure</li>
<li>defining morphisms</li>
<li>defining coercions and conversions</li>
<li>algebraic structures with several realizations</li>
</ul>
</blockquote>
<p>At the end of this tutorial, the reader should be able to reimplement
by himself the example of algebra with several realizations:</p>
<div class="highlight-python">

{{{id=0|
Sets().WithRealizations()
///
}}}

</div>
<p>Namely, we consider an algebra <img class="math" src="../_images/math/496761119df26cc13f4b05a2e99254eff491d695.png" alt="A(S)"> whose basis is indexed by the
subsets <img class="math" src="../_images/math/f37bba504894945c07a32f5496d74299a37aa51c.png" alt="s"> of a given set <img class="math" src="../_images/math/ad28c83c99a8fd0dd2e2e594c9d02ee532765a0a.png" alt="S">. <img class="math" src="../_images/math/496761119df26cc13f4b05a2e99254eff491d695.png" alt="A(S)"> is endowed with three natural
basis: <tt class="docutils literal"><span class="pre">F</span></tt>, <tt class="docutils literal"><span class="pre">In</span></tt>, <tt class="docutils literal"><span class="pre">Out</span></tt>; in the first basis, the product is
given by the union of the indexing sets. The <tt class="docutils literal"><span class="pre">In</span></tt> basis and <tt class="docutils literal"><span class="pre">Out</span></tt>
basis are defined respectively by:</p>
<blockquote>
<div class="math">
<p><img src="../_images/math/273511d798b9d83ad84ab5a6dbc4b67339e81f5c.png" alt="In_s  = \sum_{t\subset s} F_t
F_s   = \sum_{t\supset s} Out_t"></p>
</div></blockquote>
<p>Each such basis gives a realization of <img class="math" src="../_images/math/019e9892786e493964e145e7c5cf7b700314e53b.png" alt="A">, where the elements are
represented by their expansion in this basis. In the running exercises
we will progressively implement this algebra and its three
realizations, with coercions and mixed arithmetic between them.</p>
<p>This tutorial heavily depends on the <a class="reference external" href=":file:../../demos/demo-using-free-modules.rst">using free modules tutorial</a>.</p>
<div class="section" id="subclassing-free-modules-and-including-category-information">
<h2>Subclassing free modules and including category information<a class="headerlink" href="#subclassing-free-modules-and-including-category-information" title="Permalink to this headline">¶</a></h2>
<div class="highlight-python">

{{{id=1|
class MyCyclicGroupModule(CombinatorialFreeModule):
       &quot;&quot;&quot;An absolutely minimal implementation of a module whose basis is a cyclic group&quot;&quot;&quot;
       def __init__(self, R, n, *args, **kwargs):
           CombinatorialFreeModule.__init__(self, R, Zmod(n), *args, **kwargs)
///
}}}

{{{id=2|
A = MyCyclicGroupModule(QQ, 6, prefix=&#39;a&#39;) # or 4 or 5 or 11     ...
a = A.basis()
A.an_element()
///
a[0] + 3*a[1] + 3*a[2]
}}}

</div>
<p>We now want to endow <img class="math" src="../_images/math/019e9892786e493964e145e7c5cf7b700314e53b.png" alt="A"> with its natural product structure, to get
the group algebra of the cyclic group. Of course this is solely for
pedagogical purposes; group algebras are already implemented (see
<tt class="docutils literal"><span class="pre">ZMod(3).algebra(QQ)</span></tt>).</p>
<p>To define a multiplication, we should be in a category where
multiplication makes sense, which is not yet the case:</p>
<div class="highlight-python">

{{{id=3|
A.category()
///
Category of modules with basis over Rational Field
}}}

</div>
<p>We can look at the available categories from the documentation in the
reference manual: <a class="reference external" href="http://sagemath.com/doc/reference/categories.html">http://sagemath.com/doc/reference/categories.html</a></p>
<p>Or we can use introspection:</p>
<div class="highlight-python">

{{{id=4|
sage.categories.  # Look through the list of categories to pick one we want
///
}}}

</div>
<p>Once we have chosen an appropriate category (here
<tt class="xref docutils literal"><span class="pre">AlgebrasWithBasis</span></tt>), one can look at one example:</p>
<div class="highlight-python">

{{{id=5|
E = AlgebrasWithBasis(QQ).example(); E
///
An example of an algebra with basis: the free algebra on the generators ('a', 'b', 'c') over Rational Field
}}}

{{{id=6|
e = E.an_element(); e
///
B[word: ] + 2*B[word: a] + 3*B[word: b]
}}}

</div>
<p>and browse its code:</p>
<div class="highlight-python"><pre>sage: E??</pre>
</div>
<p>This code is meant as a template from which to start implementing a
new algebra. In particular it suggests that we need to implement the
methods <tt class="docutils literal"><span class="pre">product_on_basis</span></tt>, <tt class="docutils literal"><span class="pre">one_basis</span></tt>, <tt class="docutils literal"><span class="pre">_repr_</span></tt> and
<tt class="docutils literal"><span class="pre">algebra_generators</span></tt>. Another way to get this lists of methods is to
ask the category (TODO: find a slicker idiom for this):</p>
<div class="highlight-python">

{{{id=7|
from sage.misc.abstract_method import abstract_methods_of_class
abstract_methods_of_class(AlgebrasWithBasis(QQ).element_class)
///
{'required': [], 'optional': ['_add_', '_mul_']}
}}}

{{{id=8|
abstract_methods_of_class(AlgebrasWithBasis(QQ).parent_class)
///
{'required': ['__contains__'], 'optional': ['one_basis', 'product_on_basis']}
}}}

</div>
<div class="admonition warning">
<p class="first admonition-title">Warning</p>
<p class="last">the result above is not yet necessarily complete; many</p>
</div>
<p>required methods in the categories are not yet marked as
<a href="#id1"><span class="problematic" id="id2">:function:`abstract_methods`</span></a>. We also recommend browsing the
documentation of this category: <tt class="xref docutils literal"><span class="pre">AlgebrasWithBasis</span></tt>.</p>
<p>Here is the obtained implementation of the group algebra:</p>
<div class="highlight-python">

{{{id=9|
class MyCyclicGroupAlgebra(CombinatorialFreeModule):

       def __init__(self, R, n, **keywords):
           self._group = Zmod(n)
           CombinatorialFreeModule.__init__(self, R, self._group,
               category=AlgebrasWithBasis(R), **keywords)

       def product_on_basis(self, left, right):
           return self.monomial( left + right )

       def one_basis(self):
           return self._group.zero()

       def algebra_generators(self):
           return Family( [self.monomial( self._group(1) ) ] )

       def _repr_(self):
           return &quot;Jason&#39;s group algebra of %s over %s&quot;%(self._group, self.base_ring())
///
}}}

</div>
<p>Some notes about this implementation:</p>
<blockquote>
<ul>
<li><p class="first">Alternatively, we could have defined <tt class="docutils literal"><span class="pre">product</span></tt> instead of
<tt class="docutils literal"><span class="pre">product_on_basis</span></tt>:</p>
<div class="highlight-python"><div class="highlight"><pre>...       # def product(self, left, right):
...       #     return ## something ##
</pre></div></div>
</li>
<li><p class="first">For the sake of readability in this tutorial, we have stripped out
all the documentation strings. Of course all of those should be
present as in <tt class="docutils literal"><span class="pre">E</span></tt>.</p>
</li>
<li><p class="first">The purpose of <tt class="docutils literal"><span class="pre">**keywords</span></tt> is to pass down options like
<tt class="docutils literal"><span class="pre">prefix</span></tt> to <tt class="xref docutils literal"><span class="pre">CombinatorialFreeModules</span></tt>.</p>
</li>
</ul>
</blockquote>
<p>Let us do some calculations:</p>
<div class="highlight-python">

{{{id=10|
A = MyCyclicGroupAlgebra(QQ, 2, prefix=&#39;a&#39;) # 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=11|
f * f
///
10*a[0] + 6*a[1]
}}}

{{{id=12|
f.
f.is_idempotent()
///
False
}}}

{{{id=13|
A.one()
///
a[0]
}}}

{{{id=14|
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=15|
g = 2*a[1]; (f + g)*f == f*f + g*f
///
True
}}}

</div>
<p>This seems to work fine, but we would like to put more stress on our
implementation to shake potential bugs out of it. To this end, we will
use <tt class="xref docutils literal"><span class="pre">TestSuite</span></tt> a tool which will perform many routine tests on
our algebra for us:</p>
<div class="highlight-python">

{{{id=16|
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
}}}

</div>
<p>For more information on categories, see:</p>
<div class="highlight-python"><pre>sage: sage.categories.primer?</pre>
</div>
<div class="section" id="review">
<h3>Review<a class="headerlink" href="#review" title="Permalink to this headline">¶</a></h3>
<p>We wanted to create an algebra, so we:</p>
<div class="highlight-python"><pre>1 Created the underlying vector space using :class:`CombinatorialFreeModule`
2 Looked at ``sage.categories.&lt;tab&gt;`` to find an appropriate category
3 Loaded an example of that category to see what methods we needed to write
4 Added the category information and other necessary methods to our class
5 Ran :class:`TestSuite` to catch potential discrepancies</pre>
</div>
</div>
<div class="section" id="exercise">
<h3>Exercise<a class="headerlink" href="#exercise" title="Permalink to this headline">¶</a></h3>
<ol class="arabic">
<li><p class="first">Make a tiny modification to product_on_basis in
&#8220;MyCyclicGroupAlgebra&#8221; to implement the <em>dual</em> of the group algebra
of the cyclic group instead of its group algebra (product given by
<img class="math" src="../_images/math/c4273648663621e3a36a0a8171bcb582afea01e9.png" alt="b_fb_g=\delta_{f,g}bf">).</p>
<p>Run the <tt class="xref docutils literal"><span class="pre">TestSuite</span></tt> tests (you may ignore the &#8220;pickling&#8221;
errors). What do you notice?</p>
<p>Fix the implementation of <tt class="docutils literal"><span class="pre">one</span></tt> and check that the tests now pass.</p>
<p>Add the hopf algebra structure. Hint: look at the example:</p>
<div class="highlight-python">

{{{id=17|
C = HopfAlgebrasWithBasis(QQ).example()
///
}}}

</div>
</li>
<li><p class="first">Given a set <img class="math" src="../_images/math/ad28c83c99a8fd0dd2e2e594c9d02ee532765a0a.png" alt="S">, say:</p>
<div class="highlight-python">

{{{id=18|
S = Set([1,2,3,4,5])
///
}}}

</div>
<p>and a base ring, say:</p>
<div class="highlight-python">

{{{id=19|
R = QQ
///
}}}

</div>
</li>
</ol>
<p>implement an <img class="math" src="../_images/math/eff43e84f8a3bcf7b6965f0a3248bc4d3a9d0cd4.png" alt="R">-algebra:</p>
<div class="highlight-python">

{{{id=20|
F = SubsetAlgebraOnFundamentalBasis(S, R)   # todo: not implemented
///
}}}

</div>
<p>whose basis <tt class="docutils literal"><span class="pre">(b_s)_{s\subset</span> <span class="pre">S}</span></tt> is indexed by the subsets of
<tt class="docutils literal"><span class="pre">S</span></tt>:</p>
<div class="highlight-python">

{{{id=21|
Subsets(S)
///
Subsets of {1, 2, 3, 4, 5}
}}}

</div>
<p>and where the product is defined by <img class="math" src="../_images/math/6b565110c962a8a35c5956be773303d76bec1ddd.png" alt="b_s b_t = b_{s\cup t}">.</p>
</div>
</div>
<div class="section" id="morphisms">
<h2>Morphisms<a class="headerlink" href="#morphisms" title="Permalink to this headline">¶</a></h2>
<p>To better understand relationships between algebraic spaces, one wants
to consider morphisms between them.</p>
<blockquote>
sage: A.module_morphism?
sage: A = MyCyclicGroupAlgebra(QQ, 2, prefix=&#8217;a&#8217;)
sage: B = MyCyclicGroupAlgebra(QQ, 6, prefix=&#8217;b&#8217;)
sage: A, B
(Jason&#8217;s group algebra of the cyclic group Zmod(2) over Rational Field, Jason&#8217;s group algebra of the cyclic group Zmod(6) over Rational Field)</blockquote>
<div class="highlight-python">

{{{id=22|
def func_on_basis(g):
       r&quot;&quot;&quot;
       This function is the &#39;brains&#39; of a (linear) morphism
       from A --&gt; B.  The input is the index of basis
       element of the domain (A).  The output is an element of the
       codomain (B).
       &quot;&quot;&quot;
       if g==1: return B.monomial(Zmod(6)(3))
       else:    return B.one()
///
}}}

</div>
<p>We can now define a morphism which extends this function to <img class="math" src="../_images/math/019e9892786e493964e145e7c5cf7b700314e53b.png" alt="A"> by
linearity:</p>
<div class="highlight-python">

{{{id=23|
phi = A.module_morphism(func_on_basis, codomain=B)
f = A.an_element()
f
///
a[0] + 3*a[1]
}}}

{{{id=24|
phi(f)
///
b[0] + 3*b[3]
}}}

</div>
<div class="section" id="id3">
<h3>Exercise<a class="headerlink" href="#id3" title="Permalink to this headline">¶</a></h3>
<p>Define a new free module <tt class="docutils literal"><span class="pre">In</span></tt> with basis indexed by the subsets of
<img class="math" src="../_images/math/ad28c83c99a8fd0dd2e2e594c9d02ee532765a0a.png" alt="S">, and a morphism <tt class="docutils literal"><span class="pre">phi</span></tt> from <tt class="docutils literal"><span class="pre">In</span></tt> to <tt class="docutils literal"><span class="pre">F</span></tt> defined by</p>
<blockquote>
<div class="math">
<p><img src="../_images/math/22f3a94bfbae23e8eb5ec4e9ba964e6cc32959de.png" alt="\phi(In_s) = \sum_{t\subset s} F_t"></p>
</div></blockquote>
</div>
</div>
<div class="section" id="diagonal-and-triangular-morphisms">
<h2>Diagonal and Triangular Morphisms<a class="headerlink" href="#diagonal-and-triangular-morphisms" title="Permalink to this headline">¶</a></h2>
<p>We now illustrate how to specify that a given morphism is diagonal or
triangular with respect to some order on the basis which makes it
invertible. Currently this feature requires the domain and codomain to
have the same index set (in progress ...).</p>
<div class="highlight-python">

{{{id=25|
X = CombinatorialFreeModule(QQ, Partitions(), prefix=&#39;x&#39;); x = X.basis();
Y = CombinatorialFreeModule(QQ, Partitions(), prefix=&#39;y&#39;); y = Y.basis();
///
}}}

</div>
<p>A diagonal module_morphism takes as argument a function whose input is
the index of a basis element of the domain, and whose output is the
coefficient of the corresponding basis element of the codomain:</p>
<div class="highlight-python">

{{{id=26|
def diag_func(p):
       if len(p)==0: return 1
       else: return p[0]


diag_func(Partition([3,2,1]))
///
3
}}}

{{{id=27|
X_to_Y = X.module_morphism(diagonal=diag_func, codomain=Y)
f = X.an_element();
f
///
x[[]] + 2*x[[1]] + 3*x[[2]]
}}}

{{{id=28|
X_to_Y(f)
///
y[[]] + 2*y[[1]] + 6*y[[2]]
}}}

</div>
<p>Python fun-fact: <tt class="docutils literal"><span class="pre">~</span></tt> is the inversion operator (but be careful with
int&#8217;s!):</p>
<div class="highlight-python">

{{{id=29|
~2
///
1/2
}}}

{{{id=30|
~(int(2))
///
-3
}}}

</div>
<p>Diagonal module_morphisms are invertible:</p>
<div class="highlight-python">

{{{id=31|
Y_to_X = ~X_to_Y
f = y[Partition([3])] - 2*y[Partition([2,1])]
f
///
-2*y[[2, 1]] + y[[3]]
}}}

{{{id=32|
Y_to_X(f)
///
-x[[2, 1]] + 1/3*x[[3]]
}}}

{{{id=33|
X_to_Y(Y_to_X(f))
///
-2*y[[2, 1]] + y[[3]]
}}}

</div>
<p>For triangular morphisms, just like ordinary morphisms, we need a
function which accepts as input the index of a basis element of the
domain and returns an element of the codomain.  We think of this
function as representing the columns of the matrix of the linear
transformation:</p>
<div class="highlight-python">

{{{id=34|
def triang_on_basis(p):
       return Y.sum_of_monomials(mu for mu in Partitions(sum(p)) if mu &gt;= p)

triang_on_basis([3,2])
///
y[[3, 2]] + y[[4, 1]] + y[[5]]
}}}

{{{id=35|
X_to_Y = X.module_morphism(triang_on_basis, triangular=&#39;lower&#39;, unitriangular=True, codomain=Y)
f = x[Partition([1,1,1])] + 2*x[Partition([3,2])];
f
///
x[[1, 1, 1]] + 2*x[[3, 2]]
}}}

</div>
<div class="highlight-python">

{{{id=36|
X_to_Y(f)
///
y[[1, 1, 1]] + y[[2, 1]] + y[[3]] + 2*y[[3, 2]] + 2*y[[4, 1]] + 2*y[[5]]
}}}

</div>
<p>Triangular module_morphisms are also invertible, even if <tt class="docutils literal"><span class="pre">X</span></tt> and
<tt class="docutils literal"><span class="pre">Y</span></tt> are both infinite-dimensional:</p>
<div class="highlight-python">

{{{id=37|
Y_to_X = ~X_to_Y
f
///
x[[1, 1, 1]] + 2*x[[3, 2]]
}}}

{{{id=38|
Y_to_X(X_to_Y(f))
///
x[[1, 1, 1]] + 2*x[[3, 2]]
}}}

</div>
<p>For details, see
<tt class="xref docutils literal"><span class="pre">ModulesWithBasis.ParentMethods.module_morphism()</span></tt> (and also
<tt class="xref docutils literal"><span class="pre">sage.categories.modules_with_basis.TriangularModuleMorphism</span></tt>):</p>
<div class="highlight-python"><pre>sage: A.module_morphism?</pre>
</div>
<div class="section" id="id4">
<h3>Exercise<a class="headerlink" href="#id4" title="Permalink to this headline">¶</a></h3>
<p>Redefine the morphism <tt class="docutils literal"><span class="pre">phi</span></tt> from the previous exercise to specify
that it is triangular w.r.t. inclusion of subsets, and inverse this
morphism. You may want to use the following comparison function as
<tt class="docutils literal"><span class="pre">cmp</span></tt> argument to <a href="#id5"><span class="problematic" id="id6">``</span></a>modules_morphism:</p>
<div class="highlight-python">

{{{id=39|
def subset_cmp(s, t):
       &quot;&quot;&quot;
       A comparison function on sets which gives a linear extension
       of the inclusion order.

       INPUT:

        - ``x``, ``y`` -- sets
       EXAMPLES::

           sage: sorted(Subsets([1,2,3]), subset_cmp)
           [{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}]
       &quot;&quot;&quot;
       s = cmp(len(x), len(y))
       if s != 0:
           return s
       return cmp(list(x), list(y))
///
}}}

</div>
</div>
</div>
<div class="section" id="coercions">
<h2>Coercions<a class="headerlink" href="#coercions" title="Permalink to this headline">¶</a></h2>
<p>Once we have defined a morphism from <img class="math" src="../_images/math/3500fbbc90d70f5aef3b6b368b9edad60bef041a.png" alt="X \to Y">, we can register it as
a coercion.  This will allow Sage to apply the morphism automatically
whenever we combine elements of <img class="math" src="../_images/math/6a47ca0fe7cb276abc022af6ac88ddae1a9d6894.png" alt="X"> and <img class="math" src="../_images/math/ce58e4af225c93d08606c26554caaa5ae32edeba.png" alt="Y"> together. See
<a class="reference external" href="http://sagemath.com/doc/reference/coercion.html">http://sagemath.com/doc/reference/coercion.html</a> for more
information. As a training step, let us first define a morphism <img class="math" src="../_images/math/6a47ca0fe7cb276abc022af6ac88ddae1a9d6894.png" alt="X"> to <img class="math" src="../_images/math/8189a5b5a0917b8c93350827be4038af1839139d.png" alt="h">, and
register it as a coercion:</p>
<div class="highlight-python">

{{{id=40|
def triang_on_basis(p):
       return h.sum_of_monomials(mu for mu in Partitions(sum(p)) if mu &gt;= p)

triang_on_basis([3,2])
///
h[3, 2] + h[4, 1] + h[5]
}}}

{{{id=41|
X_to_h = X.module_morphism(triang_on_basis, triangular=&#39;lower&#39;, unitriangular=True, codomain=h)
X_to_h.
X_to_h.register_as_coercion()
///
}}}

</div>
<p>Now we can convert elements from <img class="math" src="../_images/math/6a47ca0fe7cb276abc022af6ac88ddae1a9d6894.png" alt="X"> to <img class="math" src="../_images/math/8189a5b5a0917b8c93350827be4038af1839139d.png" alt="h">, but also do mixed
arithmetic with them:</p>
<div class="highlight-python">

{{{id=42|
h(x[Partition([3,2])])
///
h[3, 2] + h[4, 1] + h[5]
}}}

{{{id=43|
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]
}}}

</div>
<div class="section" id="id7">
<h3>Exercise<a class="headerlink" href="#id7" title="Permalink to this headline">¶</a></h3>
<p>Use the inverse of <tt class="docutils literal"><span class="pre">phi</span></tt> to implement the inverse coercion from
<tt class="docutils literal"><span class="pre">F</span></tt> to <tt class="docutils literal"><span class="pre">In</span></tt>. Reimplement <tt class="docutils literal"><span class="pre">In</span></tt> as an algebra, with a product
method making it use <tt class="docutils literal"><span class="pre">phi</span></tt> and its inverse.</p>
</div>
</div>
<div class="section" id="application-new-basis-and-quotients-of-symmetric-functions">
<h2>Application: new basis and quotients of symmetric functions<a class="headerlink" href="#application-new-basis-and-quotients-of-symmetric-functions" title="Permalink to this headline">¶</a></h2>
<p>In the sequel, we show how to combine everything we have seen to
implement a new basis of the algebra of symmetric functions:</p>
<div class="highlight-python">

{{{id=44|
SF = SymmetricFunctions(QQ);  # A GradedHopfAlgebraWithBasis
h  = SF.homogeneous()         # A particular basis, indexed by partitions (with some additional magic)
///
}}}

</div>
<p><img class="math" src="../_images/math/8189a5b5a0917b8c93350827be4038af1839139d.png" alt="h"> is a graded algebra whose basis is indexed by partitions. Namely
<tt class="docutils literal"><span class="pre">h([i])</span></tt> represents the sum of all monomials of degree <img class="math" src="../_images/math/34857b3ba74ce5cd8607f3ebd23e9015908ada71.png" alt="i">:</p>
<blockquote>
sage: h([2]).expand(4)
x0^2 + x0*x1 + x1^2 + x0*x2 + x1*x2 + x2^2 + x0*x3 + x1*x3 + x2*x3 + x3^2</blockquote>
<p>and <tt class="docutils literal"><span class="pre">h(\mu)</span> <span class="pre">=</span> <span class="pre">prod(</span> <span class="pre">h(p)</span> <span class="pre">for</span> <span class="pre">p</span> <span class="pre">in</span> <span class="pre">mu</span> <span class="pre">)</span></tt>:</p>
<div class="highlight-python">

{{{id=45|
h([3,2,2,1]) == h([3]) * h([2]) * h([2]) * h([1])
///
True
}}}

</div>
<div class="highlight-python">

{{{id=46|
class MySFBasis(CombinatorialFreeModule):
       r&quot;&quot;&quot;
       Note: We would typically use SymmetricFunctionAlgebra_generic
       for this. This is as an example only.
       &quot;&quot;&quot;

       def __init__(self, R, *args, **kwargs):
           &quot;&quot;&quot; TODO: Informative doc-string and examples &quot;&quot;&quot;
           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=&#39;lower&#39;, 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 &gt;= la)

       def product(self, left, right):
           return self( self._h(left) * self._h(right) )

       def _repr_(self):
           return &quot;Jason&#39;s basis for symmetric functions over %s&quot;%self.base_ring()

       @cached_method
       def one_basis(self):
           r&quot;&quot;&quot; Returns the index of the basis element which is equal to &#39;1&#39;.&quot;&quot;&quot;
           return Partition([])
X = MySFBasis(QQ, prefix=&#39;x&#39;); x = X.basis(); h = SymmetricFunctions(QQ).homogeneous()
f = X(h([2,1,1]) - 2*h([2,2]))  # Note the capital X
f
h(f)
///
x[[2, 1, 1]] - 3*x[[2, 2]] + 2*x[[3, 1]]
h[2, 1, 1] - 2*h[2, 2]
}}}

{{{id=47|
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=48|
h(f*f)
///
h[2, 2, 1, 1, 1, 1] - 4*h[2, 2, 2, 1, 1] + 4*h[2, 2, 2, 2]
}}}

</div>
<p>As a final example, we implement a quotient of the algebra of
symmetric functions:</p>
<div class="highlight-python">

{{{id=49|
class MySFQuotient(CombinatorialFreeModule):
       r&quot;&quot;&quot;
       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``.
       &quot;&quot;&quot;

       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 = &#39;mm&#39;

           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&quot;&quot;&quot; Takes the index of a basis element of a monomial
           symmetric function, and returns the projection of that
           element to the quotient.&quot;&quot;&quot;

           if len(mu) &gt; 0 and mu[0] &gt; 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) )
MM = MySFQuotient(QQ, 3)
mm = MM.basis()
m = SymmetricFunctions(QQ).monomial()
P = Partition
f = mm[P([3,2,1])] + 2*mm[P([3,3])]
f
///
mm[[3, 2, 1]] + 2*mm[[3, 3]]
}}}

{{{id=50|
m(f)
///
m[3, 2, 1] + 2*m[3, 3]
}}}

{{{id=51|
(m(f))^2
///
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]
}}}

{{{id=52|
f^2
///
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]]
}}}

{{{id=53|
(m(f))^2 - m(f^2)
///
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]
}}}

{{{id=54|
MM( (m(f))^2 - m(f^2) )
///
0
}}}

</div>
</div>
</div>


          </div>
        </div>
      </div>
      <div class="sphinxsidebar">
        <div class="sphinxsidebarwrapper">
            <h3><a href="../index.html">Table Of Contents</a></h3>
            <ul>
<li><a class="reference external" href="">Tutorial: Implementing Algebraic Structures</a><ul>
<li><a class="reference external" href="#subclassing-free-modules-and-including-category-information">Subclassing free modules and including category information</a><ul>
<li><a class="reference external" href="#review">Review</a></li>
<li><a class="reference external" href="#exercise">Exercise</a></li>
</ul>
</li>
<li><a class="reference external" href="#morphisms">Morphisms</a><ul>
<li><a class="reference external" href="#id3">Exercise</a></li>
</ul>
</li>
<li><a class="reference external" href="#diagonal-and-triangular-morphisms">Diagonal and Triangular Morphisms</a><ul>
<li><a class="reference external" href="#id4">Exercise</a></li>
</ul>
</li>
<li><a class="reference external" href="#coercions">Coercions</a><ul>
<li><a class="reference external" href="#id7">Exercise</a></li>
</ul>
</li>
<li><a class="reference external" href="#application-new-basis-and-quotients-of-symmetric-functions">Application: new basis and quotients of symmetric functions</a></li>
</ul>
</li>
</ul>

            <h3>This Page</h3>
            <ul class="this-page-menu">
              <li><a href="../_sources/demos/tutorial-implementing-algebraic-structures.txt" rel="nofollow">Show Source</a></li>
            </ul>
          <div id="searchbox" style="display: none">
            <h3>Quick search</h3>
              <p class="searchtip" style="font-size: 90%">
              Enter search terms or a module, class or function name.
              </p>
          </div>
          <script type="text/javascript">$('#searchbox').show(0);</script>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../genindex.html" title="General Index">index</a></li>
        <li class="right">
          <a href="../modindex.html" title="Global Module Index">modules</a> |</li>
  
    
      <a href="../../index.html"><img src="../_static/sagelogo.png" style="vertical-align: middle" title="Sage Logo"></a>
    
  
  
        <li><a href="../index.html">Sage Reference v4.4.4</a> &raquo;</li>
 
      </ul>
    </div>
    
    <div class="footer">
      &copy; Copyright 2005--2010, The Sage Development Team.
      Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 0.6.3.
    </div>
    <script type="text/javascript">
/*global jQuery, window */
/* Sphinx sidebar toggle.  Putting this code at the end of the body
 * enables the toggle for the live, static, and offline docs.  Note:
 * sage.misc.html.math_parse() eats jQuery's dollar-sign shortcut. */
var jq = jQuery;  
jq(document).ready(function () {
    var bar, bod, bg, fg, key, tog, wid_old, wid_new, resize, get_state, set_state;
    bod = jq('div.bodywrapper');
    bar = jq('div.sphinxsidebar');
    tog = jq('<div class="sphinxsidebartoggle"></div>');
    
    /* Delayed resize helper.  Not perfect but good enough. */
    resize = function () {
        setTimeout(function () {
            tog.height(bod.height());
        }, 100);
    };
    jq(window).resize(function () {
        resize();
    });
    
    /* Setup and add the toggle. See Sphinx v0.5.1 default.css. */
    fg = jq('div.sphinxsidebar p a').css('color') || 'rgb(152, 219, 204)';
    bg = jq('div.document').css('background-color') || 'rgb(28, 78, 99)';
    wid_old = '230px';
    wid_new = '5px';
    tog.css('background-color', bg)
        .css('border-width', '0px')
        .css('border-right', wid_new + ' ridge ' + bg)
        .css('cursor', 'pointer')
        .css('position', 'absolute')
        .css('left', '-' + wid_new)
        .css('top', '0px')
        .css('width', wid_new);
    bod.css('position', 'relative');
    bod.prepend(tog);
    resize();
    
    /* Cookie helpers. */
    key = 'sphinxsidebar=';
    set_state = function (s) {
        var date = new Date();
        /* Expiry in 7 days. */
        date.setTime(date.getTime() + (7 * 24 * 3600 * 1000));
        document.cookie = key + encodeURIComponent(s) + '; expires=' +
            date.toUTCString() + '; path=/';
    };
    get_state = function () {
        var i, c, crumbs = document.cookie.split(';');
        for (i = 0; i < crumbs.length; i += 1) {
            c = crumbs[i].replace(/^\s+/, '');
            if (c.indexOf(key) === 0) {
                return decodeURIComponent(c.substring(key.length, c.length));
            }
        }
        return null;
    };
    
    /* Event handlers. */
    tog.mouseover(function (ev) {
        tog.css('border-right-color', fg);
    }).mouseout(function (ev) {
        tog.css('border-right-color', bg);
    }).click(function (ev) {
        if (bod.hasClass('wide')) {
            bod.removeClass('wide');
            bod.css('margin-left', wid_old);
            bar.css('width', wid_old);
            bar.show();
            set_state('visible');
        } else {
            set_state('hidden');
            bar.hide();
            bar.css('width', '0px');
            bod.css('margin-left', wid_new);
            bod.addClass('wide');
        }
        resize();
    });
    
    /* Hide the normally visible sidebar? */
    if (get_state() === 'hidden') {
        tog.trigger('click');
    } else {
        set_state('visible');
    }
});
    </script>