Dear Tobias,
On Tue, Mar 02, 2010 at 09:10:16AM +0100, Tobias Columbus wrote:
> Now to something more conceptual:
> I thought a bit about generalizing Free Object constructions.
> I think there are actually some things that may be implemented on
> a very abstract level in a class "FreeObject" -- for example.
>
> First, elements of free objects are more or less strings.
> Currently I represent them as a list of tuples
>
> [ (<generator>,<power> ) ]
>
> Multiplication is just concatenation of lists, with some checks
> that the representation is reduced.
> If the free object is abelian, one could handle this by sorting
> the list after some order on the generators and by doing
> multiplication by a simple "merge" -- like in the merge-phases of
> merge-sort.
>
> With this construction, modules can be handled quite easily, too:
> A free module is a free abelian group with elements being lists
> [ (<coefficient>, <generator>) ]
> where the coefficients are from the base ring and not from ZZ.
>
> I am not so sure whether this representation works for rings,
> algebras and other objects with more than one inner operation,
> but I will think about that.
Thanks for your inspiring thoughts! Here is how I see the things now.
First, as you point out, free additive abelian semigroups / monoids /
groups are nothing more than NN, and ZZ-free modules respectively (I
am not sure we want to distinguish the free semigroups and free
monoids). Hence, the first steps would be to:
- Define CommutativeAdditiveGroups().free(gens) as
CombinatorialFreeModule(ZZ, gens)
- Implement a category SemiRings()
- Implement the SemiRing of positive (resp. non negative) natural numbers
Should those be called PositiveIntegers resp. NonNegativeIntegers,
extending the current NonNegativeIntegers which is just an enumerated set?
- Extend CombinatorialFreeModule to accept a semiring as base ring
This probably will require extending the categories Modules /
ModulesWithBasis / ... to accept a semiring as argument. Or instead
to define new categories SemiRingModules / ...?
This will be a good occasion to review all the methods of
CombinatorialFreeModule, and move up into the categories those that
do not depend on the data structure. And to see whether we want to
split a super class for FreeModule over a semiring (if it's just a
question of having a meaningless _negate_ method around, we can
leave things as is, at least for the moment).
- Define CommutativeAdditiveMonoids().free(gens) as
CombinatorialFreeModule(NonNegativeIntegers(), gens)
Next step: multiplicative abelian semigroups/monoids/groups. One way
would be to simply apply a functor constructing a multiplicative group
from an additive group, simply by delegating all multiplicative
operations to additive operations on the underlying group. There would
be a small overhead; I don't know how much we would care about it.
The other option would be to share the data structure by abstracting
away a super class of CombinatorialFreeModule (possibly just for
CombinatorialFreeModule.Element). While we are at it, we might want to
go the extra mile, and define a class whose instances are,
mathematically speaking, functions: A -> B (e.g. A is the set of names
of the generators and B is ZZ) taking a constant value
(e.g. ZZ.zero()) on all but a finite number of elements of A. The
storage is sparse, and the main operation is:
zip(f, element1, element2)
which returns the function: x -> f(element1(x), element2(x)), whose
main job is to handle the sparse representation.
I am not sure whether we want to share the data structure between the
abelian and non abelian cases, since in the abelian case we may prefer
a dictionary (as is done in CombinatorialFreeModule) rather than a
sorted list. Instead, we probably want to redo the same as above,
using words/lists as data structure.
Things like FreeAlgebras can simply be defined as
FreeMonoid(...).algebra() (with the latest sage-combinat patches). In
case we want to add further operations, we can do that by inheritance,
but I'll skip that for now.
> Anyway, one central property of free objects is the way one defines
> morphisms. There is a bijection between {set-mappings from the
> generators to some other object A} and {morphisms from the free
> object on these generators to the object A}. In my opinion this
> bijection may be implemented independent of the parent/category. The
> morphism is determined by the image of the generators and the
> morphism-properties. Now in the list- representation of elements
> this morphism-properties break down to applying the set-mapping
> generator by generator -- at least for monoids, groups and
> modules. And this seems to be independent of the category we are in.
We are heading at full steam toward operads here! I sure like that :-)
Besides there are several persons interested in implementing operads
in Sage. But that won't be instantaneous, and I don't have experience
yet on how useful this would be in practice for our problems. So I
vote for just implementing this by hand for the moment. With the
above, and since a morphism of free algebra can be constructed in two
steps (extension into monoid morphism; extension into module
morphism), there are just 4 types of morphisms to handle
(additive/multiplicative; commutative/non commutative).
> Regards and apologizes for this lengthy email
Well, mine is no shorter :-) I hope you are still on, even after it,
for taking over this very much needed project!
Best,
Nicolas
--
Nicolas M. Thiéry "Isil" <nthi...@users.sf.net>
http://Nicolas.Thiery.name/
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To post to this group, send email to sage-combinat-de...@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
