Opened 7 years ago

Closed 4 years ago

#15726 closed enhancement (fixed)

Implement tensor modules and algebras

Reported by: tscrim Owned by: sage-combinat
Priority: major Milestone: sage-7.4
Component: algebra Keywords: tensor module algebra
Cc: sage-combinat, nthiery, mshimo Merged in:
Authors: Travis Scrimshaw Reviewers: Darij Grinberg
Report Upstream: N/A Work issues:
Branch: 8b45d35 (Commits) Commit: 8b45d358f1cc00c9601fe1137bb19e827ed8a2b5
Dependencies: #15289 Stopgaps:

Description (last modified by tscrim)

Because they are both really useful.

Change History (50)

comment:1 Changed 7 years ago by tscrim

  • Description modified (diff)

comment:2 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:3 Changed 7 years ago by tscrim

  • Branch set to public/algebras/tensor_algebra-15726
  • Cc nthiery added
  • Commit set to 49c7a792f3bc8e0a08d82eafe178652cd3a9b034
  • Status changed from new to needs_review

Last 10 new commits:

93c60fdMerge branch 'develop' into public/algebras/tensor_algebra-15726
74b5dadFinished tensor_module.py and lazily imported new classes.
f9d81caMerge branch 'public/15567' of trac.sagemath.org:sage into public/algebras/tensor_algebra-15726
c21b140Using coproduct via multiplication.
3a0e50bMerge branch 'develop' into public/monoids/15289-indexed
d4606ccAdded more robustness to element creation.
fb91864Merge branch 'public/monoids/15289-indexed' into public/algebras/tensor_algebra-15726
04bc3c2Added some more documentation.
8eb868aMade the tensor module into a functor.
991953aMerge branch 'develop' into public/monoids/15289-indexed

comment:4 Changed 7 years ago by nthiery

Hi Travis!

Thanks for your work on free monoids and algebras; those features have been waiting around for too long! I glanced through the code, and here are some random thoughts that came to my mind:

  • Rather than importing IndexedFreeMonoid in the global namespace, it would be preferable to have FreeMonoid(...) construct an IndexedFreeMonoid when given appropriate arguments (and same things for its friends). Let's avoid the bad route we took with CombinatorialFreeModule and have at once a single entry point for free monoids! As an immediate side effect, the current code for the FreeAlgebra might well make it almost immediately work for any index set.
  • Mathematically speaking, the free algebra indexed by I is (isomorphic to) the algebra of the free monoid indexed by I is (isomorphic to) the tensor algebra of the free module indexed by I. So we now have three implementations of the free algebra!

I'd rather only have a single implementation, typically in FreeAlgebra(K, I), with FreeMonoid(I).algebra(K) pointing to it.

FreeAlgebra(K, I) should by the way be in the category Monoids().Algebras(K) which could allow for reusing some generic code.

TensorAlgebra(V) could then also point to FreeAlgebra(K, I). Possibly with some customization (e.g. printing using tensor symbol).

By the way, with the name TensorAlgebra, the user would probably expect to write the product using tensor rather than *. Actually I am not yet sure we actually want at this point to have TensorAlgebra with multiplicative notation.

Altogether, since TensorAlgebra does not bring a feature set really different from FreeAlgebra, I'd rather leave it name alone for now until we have a better view on how we want to handle tensor/symmetric/exterior modules.

  • It could be preferable to have TensorModule be a functorial construction, parallel to that for tensor products, and if possible sharing as much code as possible with it.
  • On a similar footing, the code for _repr_, _latex_, ... in TensorModule is duplicated from CombinatorialFreeModule_Tensor. Can we avoid that?
  • IndexedFreeAbelianGroup: do we want to write them additively or multiplicatively? In the later case, code could be shared with CombinatorialFreeModule.
  • TensorModule.algebra: this definition of .algebra is incompatible with the functorial construction with the same name (I.algebra() builds an algebra whose basis is indexed by I). Do we really need this method?
  • is_finite methods for Free...Monoid: this would be best achieved by setting the category appropriately.
  • IndexedMonoidElement: Describe the data structure
  • The doctests of init actually constructs an IndexedFreeAbelianMonoid. Is this on purpose?
  • _mul_(self, y) -> _mul_(self, other)
  • What is the semantic of comparisons (lt, ...)? Do we really need those comparisons?
  • pow: Can't we use a generic implementation?
  • IndexedMonoid?.contains seems generic enough to be lifted higher up in the class hierarchy
  • _an_element_: rather do the product of the first three elements (if available), similar to what's done in CombinatorialFreeModule?.an_element. This is less demanding on the index set (computing the cardinality may be expensive/not implemented)
  • gens: using PoorManMap in CombinatorialFreeModule.monomial is relevant to make it easy to allow for the short idiom: M.module_morphism(M.monomial*...). Do we need it here?
  • gens: define instead monoid_generators. gens defers by default to monoid_generators in the monoids category (at least with #10963).
  • ngens: kill the beast. self.gens().cardinality() is a better idiom. If we really want a shortcut, it should live in a more generic setting.

comment:5 Changed 7 years ago by mshimo

  • Cc mshimo added

comment:6 Changed 7 years ago by git

  • Commit changed from 49c7a792f3bc8e0a08d82eafe178652cd3a9b034 to 53e1bb48f75dab5c0f0bc02b8c25992284e87c37

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

1d35d04Merge branch 'develop' into public/algebras/tensor_algebra-15726
bd82ed8Merge branch 'develop' into public/monoids/15289-indexed
56703ebMade Indexed* have entry points through Free*.
163df6eChanged more _basis_keys to _indices, deprecated the former.
8db8e0aChanged _an_element_ to indexed_monoid.py.
760c939Merge branch 'public/monoids/15289-indexed' of trac.sagemath.org:sage into public/monoids/15289-indexed
6430964Merge branch 'public/monoids/15289-indexed' into public/algebras/tensor_algebra-15726
03057a4Merge branch 'develop' into public/monoids/15289-indexed
53e1bb4Merge branch 'public/monoids/15289-indexed' into public/algebras/tensor_algebra-15726

comment:7 Changed 7 years ago by git

  • Commit changed from 53e1bb48f75dab5c0f0bc02b8c25992284e87c37 to a45c49ba71f5cbd6b8fdb7729a4513a8bb3c77df

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

a2996e0Merge branch 'develop' into public/monoids/15289-indexed
a45c49bMerge branch 'public/monoids/15289-indexed' into public/algebras/tensor_algebra-15726

comment:8 Changed 7 years ago by git

  • Commit changed from a45c49ba71f5cbd6b8fdb7729a4513a8bb3c77df to 1f388e0054251e1ee3ae1d350ad1e258de1b54ba

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

69c881bMerge branch 'develop' into public/algebras/tensor_algebra-15726
c1cc341Merge branch 'develop' into public/monoids/15289-indexed
49068b2Merge branch 'develop' into public/monoids/15289-indexed
1f388e0Merge branch 'public/monoids/15289-indexed' into public/algebras/tensor_algebra-15726

comment:9 Changed 7 years ago by jhpalmieri

Is there any connection and/or overlap between this ticket and #15916?

comment:10 follow-up: Changed 7 years ago by tscrim

This is for a given basis of the underlying vector space, whereas #15916 is a coordinate free approach (at least, that's how I understand #15916).

comment:11 Changed 7 years ago by git

  • Commit changed from 1f388e0054251e1ee3ae1d350ad1e258de1b54ba to 8a7e9e329b50c44f0d3238db10df24c01540753d

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

6875cfbMerge branch 'develop' into public/monoids/15289-indexed
8a7e9e3Merge branch 'public/monoids/15289-indexed' into public/algebras/tensor_algebra-15726

comment:12 in reply to: ↑ 10 Changed 7 years ago by egourgoulhon

Replying to tscrim:

This is for a given basis of the underlying vector space, whereas #15916 is a coordinate free approach (at least, that's how I understand #15916).

See also my reply in ticket:15916#comment:5. Am I correct about the tensor symmetries?

comment:13 Changed 7 years ago by tscrim

For this, tensor symmetries are irrelevent since we are constructing the tensor algebra from a single vector space. There is something for tensor products of arbitrary free modules in combinat/free_module.py, but because we want a specified/distinguished basis, we can't identify A \otimes B with B \otimes A (as objects in memory).

comment:14 Changed 7 years ago by git

  • Commit changed from 8a7e9e329b50c44f0d3238db10df24c01540753d to 9d2fa708720ce123ce732fa5414d5a1d09823b11

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

1818a3eMerge branch 'develop' into public/monoids/15289-indexed
9d2fa70Merge branch 'public/monoids/15289-indexed' into public/algebras/tensor_algebra-15726

comment:15 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:16 Changed 7 years ago by git

  • Commit changed from 9d2fa708720ce123ce732fa5414d5a1d09823b11 to 3920f5b76fe6f53ef21f28896d2a97bd820be647

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

80cdab9Merge branch 'public/algebras/tensor_algebra-15726' of trac.sagemath.org:sage into public/algebras/tensor_algebras-15726
5d167a4Moved everything over to TensorAlgebra.
3920f5bFixing doctests and other problems.

comment:17 Changed 7 years ago by tscrim

I've removed TensorModule and just made it into TensorAlgebra since we always have a natural algebra structure. I've also made some fixes based upon the changes in #15289.

There is one feature that TensorAlgebra has different from FreeAlgebra, and that is handling coercions from finite tensor products of modules (which all coerce into the base module of TensorAlgebra). TensorAlgebra also has the Hopf algebra structure defined on it.

However they probably should be some subclassing of FreeAlgebra and/or CombinatorialFreeModule_Tensor. I haven't made it a functorial construction yet. Also tensor should not be the multiplication of two tensor algebra elements, but instead return the element in the tensor product of tensor algebras (this is not isomorphic to the tensor algebra since (1 # b) * (c # 1) = (c # 1) * (1 # b) where b,c are any elements the tensor algebra). So there is still room for improvement.

comment:18 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:19 Changed 6 years ago by git

  • Commit changed from 3920f5b76fe6f53ef21f28896d2a97bd820be647 to 726b7a92af369bbfa6517c59aec2973d68f87123

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

2e18ee9Merge branch 'public/algebras/tensor_algebra-15726' of trac.sagemath.org:sage into public/algebras/tensor_algebra-15726
726b7a9Added functor and construction; also added to the catalog.

comment:20 Changed 6 years ago by tscrim

I've rebased this and added the construction functor. From doing some reading (on wikipedia), the tensor algebra is a different construction than the free algebra, as this is a functor from modules to algebras, whereas the free algebra is a functor from sets to algebras (well...should be as the construction() and the corresponding functor currently isn't implemented).

FTR, I felt that it was better to not put TensorAlgebraFunctor as TensorAlgebra in the global namespace (instead injecting the class TensorAlgebra) because we would have syntax like TensorAlgebra(M.base_ring())(M). Plus having it accessible via construction() seems to be what we currently do in Sage.

comment:21 Changed 5 years ago by chapoton

  • Status changed from needs_review to needs_work

does not apply, needs rebase

comment:22 Changed 5 years ago by git

  • Commit changed from 726b7a92af369bbfa6517c59aec2973d68f87123 to e8c242edfd8a20363b8d97eaa555f9902d45ebb2

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

e8c242eMerge branch 'public/algebras/tensor_algebra-15726' of trac.sagemath.org:sage into public/algebras/tensor_algebra-15726

comment:23 Changed 5 years ago by tscrim

  • Milestone changed from sage-6.4 to sage-6.9
  • Status changed from needs_work to needs_review

comment:24 Changed 5 years ago by chapoton

  • Status changed from needs_review to needs_work

two failing doctests

comment:25 Changed 5 years ago by git

  • Commit changed from e8c242edfd8a20363b8d97eaa555f9902d45ebb2 to cfd9e11419be7cb17fe3c8cddfe0577189776448

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

cfd9e11Fixed import due to change in file location.

comment:26 Changed 5 years ago by tscrim

  • Status changed from needs_work to needs_review

Fixed. The location of the ascii_art moved.

comment:27 Changed 5 years ago by chapoton

  • Status changed from needs_review to needs_work

some failing doctests

comment:28 Changed 5 years ago by git

  • Commit changed from cfd9e11419be7cb17fe3c8cddfe0577189776448 to 6342a6021a7cc7ebfaf1a663fd6aa37ff95d22b8

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

a779769Merge branch 'public/algebras/tensor_algebra-15726' of trac.sagemath.org:sage into public/algebras/tensor_algebra-15726
6342a60Fixing doctest output order.

comment:29 Changed 5 years ago by tscrim

  • Milestone changed from sage-6.9 to sage-6.10
  • Status changed from needs_work to needs_review

comment:30 Changed 5 years ago by git

  • Commit changed from 6342a6021a7cc7ebfaf1a663fd6aa37ff95d22b8 to 7d171266c5ab43116a7be8d1aa21da5f61517bd6

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

7d17126Merge branch 'public/algebras/tensor_algebra-15726' into 7.1.b5

comment:31 Changed 5 years ago by git

  • Commit changed from 7d171266c5ab43116a7be8d1aa21da5f61517bd6 to 1be0f6ccfeb6793ea86588100a1dc5e40e7a77a0

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

ca59b6fMerge branch 'public/algebras/tensor_algebra-15726' into 7.3.b2
1be0f6ctrac 15726 remove oldstyle next

comment:32 Changed 4 years ago by git

  • Commit changed from 1be0f6ccfeb6793ea86588100a1dc5e40e7a77a0 to ab9930b076bd5db946b49a33f8a7024f4f98070d

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

c75dba9Merge branch 'public/algebras/tensor_algebra-15726' of git://trac.sagemath.org/sage into tensor
ab9930breview

comment:33 Changed 4 years ago by git

  • Commit changed from ab9930b076bd5db946b49a33f8a7024f4f98070d to 14428b1293616372f12f20cf4aa53acf48ed76bd

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

14428b1add a todo

comment:34 Changed 4 years ago by darij

I've just push a review commit. Couldn't check the doctests yet (Sage is still compiling), but if anything's wrong I suspect a syntax error in my doctests. If the tests pass and you're fine with the changes, this is a positive review!

comment:35 Changed 4 years ago by git

  • Commit changed from 14428b1293616372f12f20cf4aa53acf48ed76bd to e51dddccc85be7249d6cf545069195e01f5da1b2

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

e51dddccorrect errors of my own

comment:36 Changed 4 years ago by darij

OK, that was quite a few failing doctests, mostly just me being careless. Fixed... with one big exception: almost none of the coercion doctests work! Most strikingly, this here:

            sage: C = CombinatorialFreeModule(ZZ, Set([1,2]))
            sage: TAC = TensorAlgebra(C)
            sage: c = C.monomial(2)
            sage: TAC(c)

blows up! I don't understand coercion well enough to fix this; this probably needs you, Travis.

That said, some of my coercion doctests might be expecting too much.

comment:37 Changed 4 years ago by git

  • Commit changed from e51dddccc85be7249d6cf545069195e01f5da1b2 to 8b45d358f1cc00c9601fe1137bb19e827ed8a2b5

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

5b72866Merge branch 'public/algebras/tensor_algebra-15726' of git://trac.sagemath.org/sage into public/algebras/tensor_algebra-15726
8b45d35Fixing some issues with indexed free modules and removing some bad coercion tests.

comment:38 Changed 4 years ago by tscrim

I've fixed the issues. The first is that the indexed (free) monoid was not handling creating its elements properly when given a list (well, a finite enumerated set by the time it gets through the __classcall__). The second is #21405. I've elected to simply remove those tests for now since it is not a bug per se and the issues are independent.

comment:39 Changed 4 years ago by git

  • Commit changed from 8b45d358f1cc00c9601fe1137bb19e827ed8a2b5 to 204633bc375b2d84d5ea1ce455d69b6ee68828ae

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

7906f74Initial version of introducing coercion of base rings.
286883ereview
902fd3eMerge branch 'public/algebras/tensor_algebra-15726' of git://trac.sagemath.org/sage into tensor
204633bresurrect removed doctests

comment:40 Changed 4 years ago by darij

Thanks, this was a good edit.

But now that #21405 is as good as reviewed, I've put the doctests back (slightly corrected). They work!

comment:41 Changed 4 years ago by darij

  • Dependencies changed from #15289 to #15289, #21405
  • Milestone changed from sage-6.10 to sage-7.4
  • Reviewers set to Darij Grinberg

comment:42 Changed 4 years ago by git

  • Commit changed from 204633bc375b2d84d5ea1ce455d69b6ee68828ae to 8b45d358f1cc00c9601fe1137bb19e827ed8a2b5

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

comment:43 Changed 4 years ago by tscrim

  • Dependencies changed from #15289, #21405 to #15289

The issues brought up on #21405 is precisely why I kept them independent. I've reverted back the addition of #21405.

comment:44 Changed 4 years ago by darij

Thanks -- but is changing the commit back enough, or should we also make a new branch?

comment:45 Changed 4 years ago by tscrim

I set the branch to point back to the old commit, so it is enough.

comment:46 Changed 4 years ago by darij

Ah, I see. I was distracted by the change to free_module.py.

comment:47 Changed 4 years ago by darij

EDI:T ignore

Last edited 4 years ago by darij (previous) (diff)

comment:48 Changed 4 years ago by darij

  • Status changed from needs_review to positive_review

comment:49 Changed 4 years ago by tscrim

Thanks for the review.

comment:50 Changed 4 years ago by vbraun

  • Branch changed from public/algebras/tensor_algebra-15726 to 8b45d358f1cc00c9601fe1137bb19e827ed8a2b5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.