attachment:tutorial-implementing-algebraic-structures.txt of days28

   1 Tutorial: Implementing Algebraic Structures
   2 
   3 <span id="tutorial-implementing-algebraic-structures"></span>
   4 
   5 
   6 
   7 <p>This tutorial will discuss five concepts:</p>
   8 <ul class="simple">
   9 <li>constructing and manipulating new modules/vector spaces</li>
  10 <li>adding more algebraic structure</li>
  11 <li>defining morphisms</li>
  12 <li>defining coercions and conversions</li>
  13 <li>algebraic structures with several realizations</li>
  14 </ul>
  15 <p>At the end of this tutorial, the reader should be able to reimplement
  16 by himself the example of algebra with several realizations:</p>
  17 
  18 {{{id=0|
  19 Sets().WithRealizations()
  20 ///
  21 }}}
  22 
  23 <p>Namely, we consider an algebra $A(S)$ whose basis is indexed by the
  24 subsets $s$ of a given set $S$. $A(S)$ is endowed with three natural
  25 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
  26 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>
  27 basis are defined respectively by:</p>
  28 <blockquote>
  29 
  30 <p>Unknown directive type &quot;math&quot;.</p>
  31 <pre class="literal-block">
  32 .. math::
  33 
  34     In_s  = \sum_{&nbsp;t\subset s}&nbsp; F_t \qquad
  35     F_s   = \sum_{&nbsp;t\supset s}&nbsp; Out_t
  36 
  37 
  38 </pre></blockquote>
  39 <p>Each such basis gives a realization of $A$, where the elements are
  40 represented by their expansion in this basis. In the running exercises
  41 we will progressively implement this algebra and its three
  42 realizations, with coercions and mixed arithmetic between them.</p>
  43 <p>This tutorial heavily depends on the <a href="#id22"><span class="problematic" id="id23">`tutorial-using-free-modules`_</span></a>.</p>
  44 
  45 <h1>Subclassing free modules and including category information</h1>
  46 <p>As a warm-up, we implement the group algebra of the additive group
  47 $ZZ/5ZZ$. Of course this is solely for pedagogical purposes; group
  48 algebras are already implemented (see <tt class="docutils literal"><span class="pre">ZMod(5).algebra(ZZ)</span></tt>). Recall
  49 that a fully functional $ZZ$-module over this group can be created
  50 with the simple command:</p>
  51 
  52 {{{id=1|
  53 A = CombinatorialFreeModule(ZZ, Zmod(5), prefix='a')
  54 ///
  55 }}}
  56 
  57 <p>We reproduce the same, but by deriving a subclass of
  58 <a href="#id2"><span class="problematic" id="id3">:class:`CombinatorialFreeModule`</span></a>:</p>
  59 
  60 {{{id=2|
  61 class MyCyclicGroupModule(CombinatorialFreeModule):
  62        &quot;&quot;&quot;An absolutely minimal implementation of a module whose basis is a cyclic group&quot;&quot;&quot;
  63        def __init__(self, R, n, *args, **kwargs):
  64            CombinatorialFreeModule.__init__(self, R, Zmod(n), *args, **kwargs)
  65 ///
  66 }}}
  67 
  68 {{{id=3|
  69 A = MyCyclicGroupModule(QQ, 6, prefix='a') # or 4 or 5 or 11     ...
  70 a = A.basis()
  71 A.an_element()
  72 ///
  73 a[0] + 3*a[1] + 3*a[2]
  74 }}}
  75 
  76 <p>We now want to endow $A$ with its natural product structure, to get
  77 the desired group algebra. To define a multiplication, we should be in
  78 a category where multiplication makes sense, which is not yet the
  79 case:</p>
  80 
  81 {{{id=4|
  82 A.category()
  83 ///
  84 Category of modules with basis over Rational Field
  85 }}}
  86 
  87 <p>We can look at the available categories from the documentation in the
  88 reference manual: <a class="reference external" href="http://sagemath.com/doc/reference/categories.html">http://sagemath.com/doc/reference/categories.html</a></p>
  89 <p>Or we can use introspection:</p>
  90 
  91 {{{id=5|
  92 sage.categories.  # Look through the list of categories to pick one we want
  93 ///
  94 }}}
  95 
  96 <p>Once we have chosen an appropriate category (here
  97 <a href="#id4"><span class="problematic" id="id5">:class:`AlgebrasWithBasis`</span></a>), one can look at one example:</p>
  98 
  99 {{{id=6|
 100 E = AlgebrasWithBasis(QQ).example(); E
 101 ///
 102 An example of an algebra with basis: the free algebra on the generators ('a', 'b', 'c') over Rational Field
 103 }}}
 104 
 105 {{{id=7|
 106 e = E.an_element(); e
 107 ///
 108 B[word: ] + 2*B[word: a] + 3*B[word: b]
 109 }}}
 110 
 111 <p>and browse through its code:</p>
 112 
 113 {{{id=8|
 114 E??
 115 ///
 116 }}}
 117 
 118 <p>This code is meant as a template from which to start implementing a
 119 new algebra. In particular it suggests that we need to implement the
 120 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
 121 <tt class="docutils literal"><span class="pre">algebra_generators</span></tt>. Another way to get this list of methods is to
 122 ask the category (TODO: find a slicker idiom for this):</p>
 123 
 124 {{{id=9|
 125 from sage.misc.abstract_method import abstract_methods_of_class
 126 abstract_methods_of_class(AlgebrasWithBasis(QQ).element_class)
 127 ///
 128 {'required': [], 'optional': ['_add_', '_mul_']}
 129 }}}
 130 
 131 {{{id=10|
 132 abstract_methods_of_class(AlgebrasWithBasis(QQ).parent_class)
 133 ///
 134 {'required': ['__contains__'], 'optional': ['one_basis', 'product_on_basis']}
 135 }}}
 136 
 137 <p class="first admonition-title">Warning</p>
 138 <p class="last">the result above is not yet necessarily complete; many</p>
 139 
 140 
 141 <p>required methods in the categories are not yet marked as
 142 <a href="#id6"><span class="problematic" id="id7">:function:`abstract_methods`</span></a>. We also recommend browsing the
 143 documentation of this category: <a href="#id8"><span class="problematic" id="id9">:class:`AlgebrasWithBasis`</span></a>.</p>
 144 
 145 <p>Here is the obtained implementation of the group algebra:</p>
 146 
 147 {{{id=11|
 148 class MyCyclicGroupAlgebra(CombinatorialFreeModule):
 149 
 150        def __init__(self, R, n, **keywords):
 151            self._group = Zmod(n)
 152            CombinatorialFreeModule.__init__(self, R, self._group,
 153                category=AlgebrasWithBasis(R), **keywords)
 154 
 155        def product_on_basis(self, left, right):
 156            return self.monomial( left + right )
 157 
 158        def one_basis(self):
 159            return self._group.zero()
 160 
 161        def algebra_generators(self):
 162            return Family( [self.monomial( self._group(1) ) ] )
 163 
 164        def _repr_(self):
 165            return &quot;Jason's group algebra of %s over %s&quot;%(self._group, self.base_ring())
 166 ///
 167 }}}
 168 
 169 <p>Some notes about this implementation:</p>
 170 <ul>
 171 <li><p class="first">Alternatively, we could have defined <tt class="docutils literal"><span class="pre">product</span></tt> instead of
 172 <tt class="docutils literal"><span class="pre">product_on_basis</span></tt>:</p>
 173 <pre class="literal-block">
 174 ...       # def product(self, left, right):
 175 ...       #     return ## something ##
 176 
 177 </pre></li>
 178 <li><p class="first">For the sake of readability in this tutorial, we have stripped out
 179 all the documentation strings. Of course all of those should be
 180 present as in <tt class="docutils literal"><span class="pre">E</span></tt>.</p>
 181 </li>
 182 <li><p class="first">The purpose of <tt class="docutils literal"><span class="pre">**keywords</span></tt> is to pass down options like
 183 <tt class="docutils literal"><span class="pre">prefix</span></tt> to <a href="#id10"><span class="problematic" id="id11">:class:`CombinatorialFreeModules`</span></a>.</p>
 184 
 185 </li>
 186 </ul>
 187 <p>Let us do some calculations:</p>
 188 
 189 {{{id=12|
 190 A = MyCyclicGroupAlgebra(QQ, 2, prefix='a') # or 4 or 5 or 11     ...
 191 a = A.basis();
 192 f = A.an_element();
 193 A, f
 194 ///
 195 (Jason's group algebra of the cyclic group Zmod(2) over Rational Field, a[0] + 3*a[1])
 196 }}}
 197 
 198 {{{id=13|
 199 f * f
 200 ///
 201 10*a[0] + 6*a[1]
 202 }}}
 203 
 204 {{{id=14|
 205 f.
 206 f.is_idempotent()
 207 ///
 208 False
 209 }}}
 210 
 211 {{{id=15|
 212 A.one()
 213 ///
 214 a[0]
 215 }}}
 216 
 217 {{{id=16|
 218 x = A.algebra_generators().first() # Typically x,y,    ... = A.algebra_generators()
 219 [x^i for i in range(4)]
 220 ///
 221 [a[0], a[1], a[0], a[1]]
 222 }}}
 223 
 224 {{{id=17|
 225 g = 2*a[1]; (f + g)*f == f*f + g*f
 226 ///
 227 True
 228 }}}
 229 
 230 <p>This seems to work fine, but we would like to put more stress on our
 231 implementation to shake potential bugs out of it. To this end, we will
 232 use <a href="#id12"><span class="problematic" id="id13">:class:`TestSuite`</span></a>, a tool which will perform many routine tests
 233 on our algebra for us:</p>
 234 
 235 {{{id=18|
 236 TestSuite(A).run(verbose=True)
 237 ///
 238 running ._test_additive_associativity() . . . passrunning ._test_an_element() . . . passrunning ._test_associativity() . . . passrunning ._test_category() . . . passrunning ._test_elements() . . .  Running the test suite of self.an_element()  running ._test_category() . . . pass  running ._test_not_implemented_methods() . . . pass  running ._test_pickling() . . . pass  passrunning ._test_not_implemented_methods() . . . passrunning ._test_one() . . . passrunning ._test_pickling() . . . passrunning ._test_prod() . . . passrunning ._test_some_elements() . . . passrunning ._test_zero() . . . pass
 239 }}}
 240 
 241 <p>For more information on categories, see:</p>
 242 
 243 {{{id=19|
 244 sage.categories.primer?
 245 ///
 246 }}}
 247 
 248 <h2>Review</h2>
 249 <p>We wanted to create an algebra, so we:</p>
 250 <pre class="literal-block">
 251 # Created the underlying vector space using :class:`CombinatorialFreeModule`
 252 # Looked at ``sage.categories.&lt;tab&gt;`` to find an appropriate category
 253 # Loaded an example of that category to see what methods we needed to write
 254 # Added the category information and other necessary methods to our class
 255 # Ran :class:`TestSuite` to catch potential discrepancies
 256 
 257 </pre><h2>Exercises</h2>
 258 <ol class="arabic">
 259 <li><p class="first">Make a tiny modification to product_on_basis in
 260 &quot;MyCyclicGroupAlgebra&quot; to implement the <em>dual</em> of the group algebra
 261 of the cyclic group instead of its group algebra (product given by
 262 $b_fb_g=delta_{f,g}bf$).</p>
 263 <p>Run the <a href="#id14"><span class="problematic" id="id15">:class:`TestSuite`</span></a> tests (you may ignore the &quot;pickling&quot;
 264 errors). What do you notice?</p>
 265 
 266 <p>Fix the implementation of <tt class="docutils literal"><span class="pre">one</span></tt> and check that the tests now pass.</p>
 267 <p>Add the hopf algebra structure. Hint: look at the example:</p>
 268 
 269 {{{id=20|
 270 C = HopfAlgebrasWithBasis(QQ).example()
 271 ///
 272 }}}
 273 
 274 </li>
 275 <li><p class="first">Given a set $S$, say:</p>
 276 
 277 {{{id=21|
 278 S = Set([1,2,3,4,5])
 279 ///
 280 }}}
 281 
 282 <p>and a base ring, say:</p>
 283 
 284 {{{id=22|
 285 R = QQ
 286 ///
 287 }}}
 288 
 289 <p>implement an $R$-algebra:</p>
 290 
 291 {{{id=23|
 292 F = SubsetAlgebraOnFundamentalBasis(S, R)   # todo: not implemented
 293 ///
 294 }}}
 295 
 296 <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>
 297 
 298 {{{id=24|
 299 Subsets(S)
 300 ///
 301 Subsets of {1, 2, 3, 4, 5}
 302 }}}
 303 
 304 <p>and where the product is defined by $b_s b_t = b_{scup t}$.</p>
 305 </li>
 306 </ol>
 307 
 308 
 309 
 310 <h1>Morphisms</h1>
 311 <p>To better understand relationships between algebraic spaces, one wants
 312 to consider morphisms between them:</p>
 313 
 314 {{{id=25|
 315 A.module_morphism?
 316 A = MyCyclicGroupAlgebra(QQ, 2, prefix='a')
 317 B = MyCyclicGroupAlgebra(QQ, 6, prefix='b')
 318 A, B
 319 ///
 320 (Jason's group algebra of the cyclic group Zmod(2) over Rational Field, Jason's group algebra of the cyclic group Zmod(6) over Rational Field)
 321 }}}
 322 
 323 
 324 {{{id=26|
 325 def func_on_basis(g):
 326        r&quot;&quot;&quot;
 327        This function is the 'brain' of a (linear) morphism
 328        from A --&gt; B.  The input is the index of basis
 329        element of the domain (A).  The output is an element of the
 330        codomain (B).
 331        &quot;&quot;&quot;
 332        if g==1: return B.monomial(Zmod(6)(3))
 333        else:    return B.one()
 334 ///
 335 }}}
 336 
 337 <p>We can now define a morphism which extends this function to $A$ by
 338 linearity:</p>
 339 
 340 {{{id=27|
 341 phi = A.module_morphism(func_on_basis, codomain=B)
 342 f = A.an_element()
 343 f
 344 ///
 345 a[0] + 3*a[1]
 346 }}}
 347 
 348 {{{id=28|
 349 phi(f)
 350 ///
 351 b[0] + 3*b[3]
 352 }}}
 353 
 354 <h2>Exercise</h2>
 355 <p>Define a new free module <tt class="docutils literal"><span class="pre">In</span></tt> with basis indexed by the subsets of
 356 $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>
 357 <blockquote>
 358 
 359 <pre class="literal-block">
 360 .. math:: \phi(In_s) = \sum_{&nbsp;t\subset s}&nbsp; F_t
 361 
 362 
 363 
 364 </pre></blockquote>
 365 
 366 
 367 
 368 <h1>Diagonal and Triangular Morphisms</h1>
 369 <p>We now illustrate how to specify that a given morphism is diagonal or
 370 triangular with respect to some order on the basis which makes it
 371 invertible. Currently this feature requires the domain and codomain to
 372 have the same index set (in progress ...).</p>
 373 
 374 {{{id=29|
 375 X = CombinatorialFreeModule(QQ, Partitions(), prefix='x'); x = X.basis();
 376 Y = CombinatorialFreeModule(QQ, Partitions(), prefix='y'); y = Y.basis();
 377 ///
 378 }}}
 379 
 380 <p>A diagonal module morphism takes as argument a function whose input is
 381 the index of a basis element of the domain, and whose output is the
 382 coefficient of the corresponding basis element of the codomain:</p>
 383 
 384 {{{id=30|
 385 def diag_func(p):
 386        if len(p)==0: return 1
 387        else: return p[0]
 388 
 389 
 390 diag_func(Partition([3,2,1]))
 391 ///
 392 3
 393 }}}
 394 
 395 {{{id=31|
 396 X_to_Y = X.module_morphism(diagonal=diag_func, codomain=Y)
 397 f = X.an_element();
 398 f
 399 ///
 400 x[[]] + 2*x[[1]] + 3*x[[2]]
 401 }}}
 402 
 403 {{{id=32|
 404 X_to_Y(f)
 405 ///
 406 y[[]] + 2*y[[1]] + 6*y[[2]]
 407 }}}
 408 
 409 <p>Python fun-fact: <tt class="docutils literal"><span class="pre">~</span></tt> is the inversion operator (but be careful with
 410 int's!):</p>
 411 
 412 {{{id=33|
 413 ~2
 414 ///
 415 1/2
 416 }}}
 417 
 418 {{{id=34|
 419 ~(int(2))
 420 ///
 421 -3
 422 }}}
 423 
 424 <p>Diagonal module morphisms are invertible:</p>
 425 
 426 {{{id=35|
 427 Y_to_X = ~X_to_Y
 428 f = y[Partition([3])] - 2*y[Partition([2,1])]
 429 f
 430 ///
 431 -2*y[[2, 1]] + y[[3]]
 432 }}}
 433 
 434 {{{id=36|
 435 Y_to_X(f)
 436 ///
 437 -x[[2, 1]] + 1/3*x[[3]]
 438 }}}
 439 
 440 {{{id=37|
 441 X_to_Y(Y_to_X(f))
 442 ///
 443 -2*y[[2, 1]] + y[[3]]
 444 }}}
 445 
 446 <p>For triangular morphisms, just like ordinary morphisms, we need a
 447 function which accepts as input the index of a basis element of the
 448 domain and returns an element of the codomain.  We think of this
 449 function as representing the columns of the matrix of the linear
 450 transformation:</p>
 451 
 452 {{{id=38|
 453 def triang_on_basis(p):
 454        return Y.sum_of_monomials(mu for mu in Partitions(sum(p)) if mu &gt;= p)
 455 
 456 triang_on_basis([3,2])
 457 ///
 458 y[[3, 2]] + y[[4, 1]] + y[[5]]
 459 }}}
 460 
 461 {{{id=39|
 462 X_to_Y = X.module_morphism(triang_on_basis, triangular='lower', unitriangular=True, codomain=Y)
 463 f = x[Partition([1,1,1])] + 2*x[Partition([3,2])];
 464 f
 465 ///
 466 x[[1, 1, 1]] + 2*x[[3, 2]]
 467 }}}
 468 
 469 
 470 {{{id=40|
 471 X_to_Y(f)
 472 ///
 473 y[[1, 1, 1]] + y[[2, 1]] + y[[3]] + 2*y[[3, 2]] + 2*y[[4, 1]] + 2*y[[5]]
 474 }}}
 475 
 476 <p>Triangular module_morphisms are also invertible, even if <tt class="docutils literal"><span class="pre">X</span></tt> and
 477 <tt class="docutils literal"><span class="pre">Y</span></tt> are both infinite-dimensional:</p>
 478 
 479 {{{id=41|
 480 Y_to_X = ~X_to_Y
 481 f
 482 ///
 483 x[[1, 1, 1]] + 2*x[[3, 2]]
 484 }}}
 485 
 486 {{{id=42|
 487 Y_to_X(X_to_Y(f))
 488 ///
 489 x[[1, 1, 1]] + 2*x[[3, 2]]
 490 }}}
 491 
 492 <p>For details, see
 493 <a href="#id16"><span class="problematic" id="id17">:meth:`ModulesWithBasis.ParentMethods.module_morphism`</span></a> (and also
 494 <a href="#id18"><span class="problematic" id="id19">:class:`sage.categories.modules_with_basis.TriangularModuleMorphism`</span></a>):</p>
 495 
 496 
 497 {{{id=43|
 498 A.module_morphism?
 499 ///
 500 }}}
 501 
 502 <h2>Exercise</h2>
 503 <p>Redefine the morphism <tt class="docutils literal"><span class="pre">phi</span></tt> from the previous exercise to specify
 504 that it is triangular w.r.t. inclusion of subsets, and inverse this
 505 morphism. You may want to use the following comparison function as
 506 <tt class="docutils literal"><span class="pre">cmp</span></tt> argument to <tt class="docutils literal"><span class="pre">modules_morphism</span></tt>:</p>
 507 
 508 {{{id=44|
 509 def subset_cmp(s, t):
 510        &quot;&quot;&quot;
 511        A comparison function on sets which gives a linear extension
 512        of the inclusion order.
 513 
 514        INPUT:
 515 
 516         - ``x``, ``y`` -- sets
 517        EXAMPLES::
 518 
 519            sage: sorted(Subsets([1,2,3]), subset_cmp)
 520            [{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}]
 521        &quot;&quot;&quot;
 522        s = cmp(len(x), len(y))
 523        if s != 0:
 524            return s
 525        return cmp(list(x), list(y))
 526 ///
 527 }}}
 528 
 529 <h1>Coercions</h1>
 530 <p>Once we have defined a morphism from $X to Y$, we can register it as
 531 a coercion.  This will allow Sage to apply the morphism automatically
 532 whenever we combine elements of $X$ and $Y$ together. See
 533 <a class="reference external" href="http://sagemath.com/doc/reference/coercion.html">http://sagemath.com/doc/reference/coercion.html</a> for more
 534 information. As a training step, let us first define a morphism $X$ to
 535 $h$, and register it as a coercion:</p>
 536 
 537 {{{id=45|
 538 def triang_on_basis(p):
 539        return h.sum_of_monomials(mu for mu in Partitions(sum(p)) if mu &gt;= p)
 540 
 541 triang_on_basis([3,2])
 542 ///
 543 h[3, 2] + h[4, 1] + h[5]
 544 }}}
 545 
 546 {{{id=46|
 547 X_to_h = X.module_morphism(triang_on_basis, triangular='lower', unitriangular=True, codomain=h)
 548 X_to_h.
 549 X_to_h.register_as_coercion()
 550 ///
 551 }}}
 552 
 553 <p>Now we can convert elements from $X$ to $h$, but also do mixed
 554 arithmetic with them:</p>
 555 
 556 {{{id=47|
 557 h(x[Partition([3,2])])
 558 ///
 559 h[3, 2] + h[4, 1] + h[5]
 560 }}}
 561 
 562 {{{id=48|
 563 h([2,2,1]) + x[Partition([2,2,1])]
 564 ///
 565 2*h[2, 2, 1] + h[3, 1, 1] + h[3, 2] + h[4, 1] + h[5]
 566 }}}
 567 
 568 <h2>Exercise</h2>
 569 <p>Use the inverse of <tt class="docutils literal"><span class="pre">phi</span></tt> to implement the inverse coercion from
 570 <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
 571 method making it use <tt class="docutils literal"><span class="pre">phi</span></tt> and its inverse.</p>
 572 
 573 
 574 
 575 <h1>Application: new basis and quotients of symmetric functions</h1>
 576 <p>In the sequel, we show how to combine everything we have seen to
 577 implement a new basis of the algebra of symmetric functions:</p>
 578 
 579 {{{id=49|
 580 SF = SymmetricFunctions(QQ);  # A GradedHopfAlgebraWithBasis
 581 h  = SF.homogeneous()         # A particular basis, indexed by partitions (with some additional magic)
 582 ///
 583 }}}
 584 
 585 <p>$h$ is a graded algebra whose basis is indexed by partitions. Namely
 586 <tt class="docutils literal"><span class="pre">h([i])</span></tt> represents the sum of all monomials of degree $i$:</p>
 587 <blockquote>
 588 sage: h([2]).expand(4)
 589 x0^2 + x0*x1 + x1^2 + x0*x2 + x1*x2 + x2^2 + x0*x3 + x1*x3 + x2*x3 + x3^2</blockquote>
 590 <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>
 591 
 592 {{{id=50|
 593 h([3,2,2,1]) == h([3]) * h([2]) * h([2]) * h([1])
 594 ///
 595 True
 596 }}}
 597 
 598 
 599 {{{id=51|
 600 class MySFBasis(CombinatorialFreeModule):
 601        r&quot;&quot;&quot;
 602        Note: We would typically use SymmetricFunctionAlgebra_generic
 603        for this. This is as an example only.
 604        &quot;&quot;&quot;
 605 
 606        def __init__(self, R, *args, **kwargs):
 607            &quot;&quot;&quot; TODO: Informative doc-string and examples &quot;&quot;&quot;
 608            CombinatorialFreeModule.__init__(self, R, Partitions(), category=AlgebrasWithBasis(R), *args, **kwargs)
 609            self._h = SymmetricFunctions(R).homogeneous()
 610            self._to_h = self.module_morphism( self._to_h_on_basis, triangular='lower', unitriangular=True, codomain=self._h)
 611            self._from_h = ~(self._to_h)
 612            self._to_h.register_as_coercion()
 613            self._from_h.register_as_coercion()
 614 
 615        def _to_h_on_basis(self, la):
 616            return self._h.sum_of_monomials(mu for mu in Partitions(sum(la)) if mu &gt;= la)
 617 
 618        def product(self, left, right):
 619            return self( self._h(left) * self._h(right) )
 620 
 621        def _repr_(self):
 622            return &quot;Jason's basis for symmetric functions over %s&quot;%self.base_ring()
 623 
 624        &#64;cached_method
 625        def one_basis(self):
 626            r&quot;&quot;&quot; Returns the index of the basis element which is equal to '1'.&quot;&quot;&quot;
 627            return Partition([])
 628 X = MySFBasis(QQ, prefix='x'); x = X.basis(); h = SymmetricFunctions(QQ).homogeneous()
 629 f = X(h([2,1,1]) - 2*h([2,2]))  # Note the capital X
 630 f
 631 h(f)
 632 ///
 633 x[[2, 1, 1]] - 3*x[[2, 2]] + 2*x[[3, 1]]h[2, 1, 1] - 2*h[2, 2]
 634 }}}
 635 
 636 {{{id=52|
 637 f*f*f
 638 ///
 639 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]]
 640 }}}
 641 
 642 {{{id=53|
 643 h(f*f)
 644 ///
 645 h[2, 2, 1, 1, 1, 1] - 4*h[2, 2, 2, 1, 1] + 4*h[2, 2, 2, 2]
 646 }}}
 647 
 648 <p>As a final example, we implement a quotient of the algebra of
 649 symmetric functions:</p>
 650 
 651 {{{id=54|
 652 class MySFQuotient(CombinatorialFreeModule):
 653        r&quot;&quot;&quot;
 654        The quotient of the ring of symmetric functions by the ideal generated
 655        by those monomial symmetric functions whose part is larger than some fixed
 656        number ``k``.
 657        &quot;&quot;&quot;
 658 
 659        def __init__(self, R, k, prefix=None, *args, **kwargs):
 660 
 661            #  Note: Setting self._prefix is equivalent to using the prefix keyword
 662            #  in CombinatorialFreeModule.__init__
 663 
 664            if prefix is not None:
 665                self._prefix = prefix
 666            else:
 667                self._prefix = 'mm'
 668 
 669            CombinatorialFreeModule.__init__(self, R,
 670                Partitions(NonNegativeIntegers(), max_part=k),
 671                category = GradedHopfAlgebrasWithBasis(R), *args, **kwargs)
 672 
 673            self._k = k
 674            self._m = SymmetricFunctions(R).monomial()
 675 
 676            self.lift = self.module_morphism(self._m.monomial)
 677            self.retract = self._m.module_morphism(self._retract_on_basis, codomain=self)
 678 
 679            self.lift.register_as_coercion()
 680            self.retract.register_as_coercion()
 681 
 682        def _retract_on_basis(self, mu):
 683            r&quot;&quot;&quot; Takes the index of a basis element of a monomial
 684            symmetric function, and returns the projection of that
 685            element to the quotient.&quot;&quot;&quot;
 686 
 687            if len(mu) &gt; 0 and mu[0] &gt; self._k:
 688                return self.zero()
 689            return self.monomial(mu)
 690 
 691        &#64;cached_method
 692        def one_basis(self):
 693            return Partition([])
 694 
 695        def product(self, left, right):
 696            return self( self._m(left) * self._m(right) )
 697 MM = MySFQuotient(QQ, 3)
 698 mm = MM.basis()
 699 m = SymmetricFunctions(QQ).monomial()
 700 P = Partition
 701 f = mm[P([3,2,1])] + 2*mm[P([3,3])]
 702 f
 703 ///
 704 mm[[3, 2, 1]] + 2*mm[[3, 3]]
 705 }}}
 706 
 707 {{{id=55|
 708 m(f)
 709 ///
 710 m[3, 2, 1] + 2*m[3, 3]
 711 }}}
 712 
 713 {{{id=56|
 714 (m(f))^2
 715 ///
 716 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]
 717 }}}
 718 
 719 {{{id=57|
 720 f^2
 721 ///
 722 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]]
 723 }}}
 724 
 725 {{{id=58|
 726 (m(f))^2 - m(f^2)
 727 ///
 728 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]
 729 }}}
 730 
 731 {{{id=59|
 732 MM( (m(f))^2 - m(f^2) )
 733 ///
 734 0
 735 }}}