Ask Your Question

Using CombinatorialFreeModule

asked 2010-09-01 00:30:58 -0500

BWW gravatar image

updated 2010-09-01 07:02:19 -0500

Could I please have some help on using CombinatorialFreeModule? I have looked at the documentation and the only examples are free modules on a finite set. I have designed my own class and I now want to work with linear combinations of instances of the class. I have been told that one issue is that instances have to be immutable (so they can be hashed?). The attributes of my class are all integers and tuples (of integers). However I am not sure if this is sufficient.

Let's say I have defined a class G whose attributes are all integers and tuples. Then the idea would be say M = CombinatorialFreeModule(QQ,G) to define the free module on instances of G with rational coefficients. Then if g,h,k are instances of G I would hope to be able to put say a = (2/3)g + 4h and b = (-3)h + 2k be able to add these and multiply by rational numbers.

For example, a simple (but inefficient) way to calculate the chromatic polynomial of a graph would be to use contraction/deletion. This starts with a graph and finishes with a polynomial but the intermediate stages are formal linear combinations of graphs. Similarly the skein relation approach to link polynomials has intermediate stages which are formal linear combinations of link projections.

edit retag flag offensive close merge delete


Hi BWW, could you post some example code of what you want, or what breaks?

niles gravatar imageniles ( 2010-09-01 04:48:16 -0500 )edit

3 answers

Sort by ยป oldest newest most voted

answered 2010-09-02 12:01:53 -0500

Jason Bandlow gravatar image

Here is a minimal example that may do what you want:

class Foo(SageObject):
    # This class defines what a 'Foo' is and what can be done with it.
    def __init__(self, i):
        self.i = i

    def _repr_(self):
        return str(self.i)

class Foos(Parent, UniqueRepresentation):
    # This class represents the set of all 'Foo's
    def __contains__(self, f):
        return isinstance(f, Foo)

    Element = Foo

Here is how to use this with CombinatorialFreeModule:

sage: F = Foos()
sage: f = Foo(1)
sage: g = Foo(2)
sage: f
sage: g
sage: f + g
TypeError: unsupported operand type(s) for +: 'Foo' and 'Foo'
sage: M = CombinatorialFreeModule(QQ, F)
sage: a = M.monomial(f)
sage: b = M.monomial(g)
sage: a + b
B[2] + B[1]
sage: 2*a
edit flag offensive delete link more


As in Jason's example, it's almost certainly a good idea to use SageObject as a base class from which to inherit. Other structures in Sage will interact better with "class Foo(SageObject): ..." than with "class Foo(): ...".

John Palmieri gravatar imageJohn Palmieri ( 2010-09-02 13:28:01 -0500 )edit

Jason, This seems to do what I want. Thanks for your help.

BWW gravatar imageBWW ( 2010-09-02 22:29:19 -0500 )edit

answered 2010-09-02 03:42:07 -0500

You can give CombinatorialFreeModule a Family as a basis. For example:

sage: CombinatorialFreeModule(QQ, Family(NN))
Free module generated by Family (Non negative integer semiring) over Rational Field

sage: CombinatorialFreeModule(QQ, Family(NN, lambda d: Partitions(d)))
Free module generated by Lazy family (<lambda>(i))_{i in Non negative integer semiring} over Rational Field

Look at the implementation of the example of an algebra with basis in sage/categories/examples/ (docs here) and trac #9280 for examples of this.

edit flag offensive delete link more


By the way, you could also look at the implementation of group algebras as an example of a Hopf algebra with basis, in sage/categories/examples/

John Palmieri gravatar imageJohn Palmieri ( 2010-09-02 10:54:09 -0500 )edit

answered 2010-09-01 06:45:12 -0500

niles gravatar image

The problem may be simply that you need to give CombinatorialFreeModule a list of basis elements:

sage: P = PolynomialRing(QQ,'x')
sage: Q = PolynomialRing(QQ,'y')
sage: R = PolynomialRing(QQ,'z')
sage: C = CombinatorialFreeModule(QQ,[P,Q,R])
sage: C
Free module generated by {Univariate Polynomial Ring in x over Rational Field, Univariate Polynomial Ring in y over Rational Field, Univariate Polynomial Ring in z over Rational Field} over Rational Field
sage: B = [x for x in C.basis()]
sage: q = 3/5*B[0] + 1/2*B[1]
sage: q
3/5*B[Univariate Polynomial Ring in x over Rational Field] + 1/2*B[Univariate Polynomial Ring in y over Rational Field]
sage: q in C

sage: P.rename('p')
sage: Q.rename('q')
sage: R.rename('r')
sage: C = CombinatorialFreeModule(QQ,[P,Q,R])
sage: C
Free module generated by {p, q, r} over Rational Field

Is this something like what you're trying to do?

You've probably seen it already, but here's the documentation for CombinatorialFreeModule. If this still isn't doing what you want, you could try implementing addition and scalar multiplication for your class; this is described in the "How To Implement" section of the Coercion documentation.

edit flag offensive delete link more


The examples in the documentation give finite lists. I require the (potentially) infinite set of all instances of a class.

BWW gravatar imageBWW ( 2010-09-01 06:53:00 -0500 )edit

My class does not have addition and multiplication. This is purely formal (as in, for example, the group algebra of a group which may be infinite).

BWW gravatar imageBWW ( 2010-09-01 06:54:19 -0500 )edit

I agree that Parents and Elements will come into this. I have tried reading the documentation on Categories and I have simply not grasped the idea.

BWW gravatar imageBWW ( 2010-09-01 07:48:17 -0500 )edit

It sounds like you're not so interested in the free module itself as the ability to do arithmetic over QQ with instances of your class--is that right? If so, I think the Coercion documentation is really the right place for you. For example . . .

niles gravatar imageniles ( 2010-09-01 09:19:13 -0500 )edit

if you define a method `_add_`, then you will automatically be able to take instances `p` and `q` and have `p+q` be a new instance of your class. And I strongly suggest skipping to the main example, which is a basic implementation of Localization rings:

niles gravatar imageniles ( 2010-09-01 09:23:06 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2010-09-01 00:30:58 -0500

Seen: 238 times

Last updated: Sep 02 '10