Implement indexed monoids #15289

tscrim · 2013-10-16T16:13:40Z

Implements free (abelian) monoids whose generators are indexed by an arbitrary set. This also moves common code from CombinatorialFreeModule into a new class sage.misc.indexed_generators.IndexedGenerators. With this we can now create (noncommutative) polynomials whose generators are given by a combinatorial object.

Also implements a very crude and basic version for groups.

Depends on #15309
Depends on #15169
Depends on #16349

CC: @sagetrac-sage-combinat @nthiery @sagetrac-mshimo @simon-king-jena

Component: algebra

Keywords: days54

Author: Travis Scrimshaw

Branch: 69ec7b2

Reviewer: Nicolas M. Thiéry

Issue created by migration from https://trac.sagemath.org/ticket/15289

The text was updated successfully, but these errors were encountered:

tscrim · 2013-10-16T16:53:20Z

comment:1

Initial version. I might add a _basis_keys attribute to CombinatorialFreeModule for backwards compatibility...

nthiery · 2013-10-16T17:09:00Z

comment:2

Hi Travis,

Thanks for working on this feature! I'll try to look at it, but that won't be immediately. I would have thought we already had a ticket about that, but I might be wrong. For the record, here is a link to a discussion we had (a long time ago) about such features:

https://groups.google.com/forum/#!searchin/sage-combinat-devel/CombinatorialFreeModule$20free$20monoid/sage-combinat-devel/EH8M6bWPylk/a-FG4uFQm7AJ

Thanks again!

Cheers,
Nicolas

tscrim · 2013-10-16T23:05:48Z

comment:3

Hey Nicolas,

I believe there is a ticket about making free abelian groups as ZZ-modules, and another one about converting between additive and multiplicative groups. However they currently don't apply to CombinatorialFreeModule, and none of the tickets on CombinatorialFreeModule would apply here as far as I remember.

Here's a new version which gives a groups version so we can do Laurent polynomials. This is not are fancy as the discussion would like, but it serves my purposes for now.

Best,

Travis

tscrim · 2013-10-23T01:49:02Z

comment:4

Here's with some more functionality additions. I did make one major change and made the iterator return (generator, exp), as opposed to (index, exp) and similar to how FreeMonoid works.

Frequently I'm finding myself calling _sorted_items(), but I'm needing to manipulate the indices of the generators. I'm wondering if we should make it into a public method (perhaps with a better name since there is no true sorting occurring when it is not free).

tscrim · 2013-11-02T05:35:48Z

Dependencies: #15309

tscrim · 2013-11-02T05:35:48Z

comment:5

Rebased to 5.13.beta2.

tscrim · 2013-11-02T21:19:49Z

Attachment: trac_15289-indexed_monoids-ts.patch.gz

tscrim · 2013-11-07T06:14:04Z

Changed dependencies from #15309 to #15309 #15169

tscrim · 2013-11-07T19:35:25Z

comment:7

Added git version.

New commits:

`[c1b5afe](https://github.com/sagemath/sagetrac-mirror/commit/c1b5afe)`	`#15289: Implemented indexed monoids and groups.`
`[6fd33b2](https://github.com/sagemath/sagetrac-mirror/commit/6fd33b2)`	`#15169: Fix FreeAlgebra element constructor from a base field.`

tscrim · 2013-11-07T19:35:25Z

Commit: c1b5afe

tscrim · 2013-11-07T19:35:25Z

Branch: public/monoids/15289-indexed

tscrim · 2013-11-09T00:10:42Z

Changed keywords from none to days54

sagetrac-git · 2013-12-03T19:41:21Z

Changed commit from c1b5afe to 9dca526

sagetrac-git · 2013-12-03T19:41:21Z

Branch pushed to git repo; I updated commit sha1. New commits:

`[9dca526](https://github.com/sagemath/sagetrac-mirror/commit/9dca526)`	`Added comparison operations.`
`[a493bee](https://github.com/sagemath/sagetrac-mirror/commit/a493bee)`	`Merge branch 'master' into public/monoids/15289-indexed`

sagetrac-git · 2014-02-08T17:37:26Z

Branch pushed to git repo; I updated commit sha1. New commits:

`545a8df`	`Merge branch 'develop' into public/monoids/15289-indexed`
`2975c87`	`Merge branch 'develop' into public/monoids/15289-indexed`
`4002b0d`	`Merge branch 'develop' into public/monoids/15289-indexed`
`9e9b769`	`Merge branch 'develop' into public/monoids/15289-indexed`
`a278afa`	`Added cardinality methods.`
`f681606`	`Added cardinality to free abelian monoid for consistancy.`
`3a0e50b`	`Merge branch 'develop' into public/monoids/15289-indexed`
`d4606cc`	`Added more robustness to element creation.`
`991953a`	`Merge branch 'develop' into public/monoids/15289-indexed`

sagetrac-git · 2014-02-08T17:37:26Z

Changed commit from 9dca526 to 991953a

sagetrac-git · 2014-02-11T21:37:43Z

Branch pushed to git repo; I updated commit sha1. New commits:

`56703eb`	`Made Indexed* have entry points through Free*.`
`163df6e`	`Changed more _basis_keys to _indices, deprecated the former.`

sagetrac-git · 2014-02-11T21:37:43Z

Changed commit from 991953a to 163df6e

sagetrac-git · 2014-02-11T21:47:23Z

Branch pushed to git repo; I updated commit sha1. New commits:

`8db8e0a`	Changed `_an_element_` to indexed_monoid.py.

sagetrac-git · 2014-02-11T21:47:23Z

Changed commit from 163df6e to 8db8e0a

tscrim · 2014-02-11T21:54:27Z

comment:14

Hey Nicolas,

From your comments on #15726, I've made the appropriate changes here.

All Indexed* now goes through Free*, but as a special case, I have IndexedFreeAbelianGroup as FreeGroup(index_set=X, abelian=True). Should we do the same for FreeMonoid?
I want to leave __pow__ alone since they are more specialized for the data structures.
The __contains__, are you suggesting putting it into Parent? If so, that might be a can of worms and should be done on another ticket.
I'd like to keep IndexedFreeAbelianGroup as multiplicative since I want to use them as a basis indexing set for polynomials.
Similarly, the comparisons are using lex ordering, so it gives a nice default order on terms when modeling polynomial rings with indexed generators.

Thank you for looking at this (and #15726). As always, I appreciate your wisdom and insight.

Best,

Travis

New commits:

`8db8e0a`	Changed `_an_element_` to indexed_monoid.py.

sagetrac-git · 2014-06-20T23:26:40Z

Changed commit from 73a4e48 to d4fe805

sagetrac-git · 2014-07-01T16:11:45Z

Changed commit from d4fe805 to 56cd05d

sagetrac-git · 2014-07-01T16:11:45Z

Branch pushed to git repo; I updated commit sha1. New commits:

`56cd05d`	`Some fixes discussed.`

sagetrac-git · 2014-07-01T16:25:08Z

Branch pushed to git repo; I updated commit sha1. New commits:

`f1f5547`	`Fixed category issue.`

sagetrac-git · 2014-07-01T16:25:08Z

Changed commit from 56cd05d to f1f5547

sagetrac-git · 2014-07-01T16:37:44Z

Changed commit from f1f5547 to f6a73fd

sagetrac-git · 2014-07-01T16:37:44Z

Branch pushed to git repo; I updated commit sha1. New commits:

`f6a73fd`	`Fixed failing doctests in categories due to new intermediate categories.`

nthiery · 2014-07-01T17:20:42Z

comment:62

I checked the recent commits, and we have been discussing side by side for the last ones today. doc and pdf doc compiles. Positive review assuming all long tests pass (running them now).

Thanks Travis!

Cheers,
Nicolas

nthiery · 2014-07-01T17:22:28Z

Reviewer: Nicolas M. Thiéry

tscrim · 2014-07-01T17:23:41Z

comment:64

Thank you for doing the review Nicolas.

sagetrac-git · 2014-07-01T17:47:53Z

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

`69ec7b2`	`Fixed c3_controlled.pyx doctests.`

sagetrac-git · 2014-07-01T17:47:53Z

Changed commit from f6a73fd to 69ec7b2

vbraun · 2014-07-03T02:03:54Z

Changed branch from public/monoids/15289-indexed to 69ec7b2

kcrisman · 2015-02-08T02:43:51Z

Changed commit from 69ec7b2 to none

kcrisman · 2015-02-08T02:43:51Z

comment:68

Hi guys, please see http://ask.sagemath.org/question/25763/incorrect-parsing-of-docstring-of-sagestructureindexed_generatorsindexedgenerators/ where it seems that putting "\left" becomes something quite different in html. I assume this is not desired; see #17745.

tscrim added this to the sage-6.1 milestone Oct 16, 2013

tscrim added c: algebra labels Oct 16, 2013

tscrim assigned sagetrac-sage-combinat Oct 16, 2013

tscrim added the s: needs review label Oct 16, 2013

This comment has been minimized.

Sign in to view

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.1, sage-6.2 Jan 30, 2014

nthiery added s: positive review and removed s: needs review labels Jul 1, 2014

sagetrac-git mannequin added s: needs review and removed s: positive review labels Jul 1, 2014

tscrim added s: positive review and removed s: needs review labels Jul 1, 2014

vbraun removed the s: positive review label Jul 3, 2014

vbraun closed this as completed in d1701a0 Jul 3, 2014

kcrisman mentioned this issue Feb 24, 2015

typo causes latex error in indexed generators #17745

Closed

fchapoton mentioned this issue Nov 24, 2018

remove a bunch of deprecated renamed keywords #26744

Closed

Implement indexed monoids #15289

Implement indexed monoids #15289

Comments

tscrim commented Oct 16, 2013

tscrim commented Oct 16, 2013

nthiery commented Oct 16, 2013

tscrim commented Oct 16, 2013

This comment has been minimized.

tscrim commented Oct 23, 2013

tscrim commented Nov 2, 2013

tscrim commented Nov 2, 2013

tscrim commented Nov 2, 2013

tscrim commented Nov 7, 2013

tscrim commented Nov 7, 2013

tscrim commented Nov 7, 2013

tscrim commented Nov 7, 2013

tscrim commented Nov 9, 2013

sagetrac-git mannequin commented Dec 3, 2013

sagetrac-git mannequin commented Dec 3, 2013

sagetrac-git mannequin commented Feb 8, 2014

sagetrac-git mannequin commented Feb 8, 2014

sagetrac-git mannequin commented Feb 11, 2014

sagetrac-git mannequin commented Feb 11, 2014

sagetrac-git mannequin commented Feb 11, 2014

sagetrac-git mannequin commented Feb 11, 2014

tscrim commented Feb 11, 2014

sagetrac-git mannequin commented Jun 20, 2014

sagetrac-git mannequin commented Jul 1, 2014

sagetrac-git mannequin commented Jul 1, 2014

sagetrac-git mannequin commented Jul 1, 2014

sagetrac-git mannequin commented Jul 1, 2014

sagetrac-git mannequin commented Jul 1, 2014

sagetrac-git mannequin commented Jul 1, 2014

nthiery commented Jul 1, 2014

nthiery commented Jul 1, 2014

tscrim commented Jul 1, 2014

sagetrac-git mannequin commented Jul 1, 2014

sagetrac-git mannequin commented Jul 1, 2014

vbraun commented Jul 3, 2014

kcrisman commented Feb 8, 2015

kcrisman commented Feb 8, 2015