Opened 7 years ago
Closed 4 years ago
#15726 closed enhancement (fixed)
Implement tensor modules and algebras
Reported by:  tscrim  Owned by:  sagecombinat 

Priority:  major  Milestone:  sage7.4 
Component:  algebra  Keywords:  tensor module algebra 
Cc:  sagecombinat, 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 )
Because they are both really useful.
Change History (50)
comment:1 Changed 7 years ago by
 Description modified (diff)
comment:2 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:3 Changed 7 years ago by
 Branch set to public/algebras/tensor_algebra15726
 Cc nthiery added
 Commit set to 49c7a792f3bc8e0a08d82eafe178652cd3a9b034
 Status changed from new to needs_review
comment:4 Changed 7 years ago by
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 haveFreeMonoid(...)
construct anIndexedFreeMonoid
when given appropriate arguments (and same things for its friends). Let's avoid the bad route we took withCombinatorialFreeModule
and have at once a single entry point for free monoids! As an immediate side effect, the current code for theFreeAlgebra
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)
, withFreeMonoid(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 toFreeAlgebra(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 haveTensorAlgebra
with multiplicative notation.
Altogether, since
TensorAlgebra
does not bring a feature set really different fromFreeAlgebra
, 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 fromCombinatorialFreeModule_Tensor
. Can we avoid that?
IndexedFreeAbelianGroup
: do we want to write them additively or multiplicatively? In the later case, code could be shared withCombinatorialFreeModule
.
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 forFree...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
inCombinatorialFreeModule.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
 Cc mshimo added
comment:6 Changed 7 years ago by
 Commit changed from 49c7a792f3bc8e0a08d82eafe178652cd3a9b034 to 53e1bb48f75dab5c0f0bc02b8c25992284e87c37
Branch pushed to git repo; I updated commit sha1. New commits:
1d35d04  Merge branch 'develop' into public/algebras/tensor_algebra15726

bd82ed8  Merge branch 'develop' into public/monoids/15289indexed

56703eb  Made Indexed* have entry points through Free*.

163df6e  Changed more _basis_keys to _indices, deprecated the former.

8db8e0a  Changed _an_element_ to indexed_monoid.py.

760c939  Merge branch 'public/monoids/15289indexed' of trac.sagemath.org:sage into public/monoids/15289indexed

6430964  Merge branch 'public/monoids/15289indexed' into public/algebras/tensor_algebra15726

03057a4  Merge branch 'develop' into public/monoids/15289indexed

53e1bb4  Merge branch 'public/monoids/15289indexed' into public/algebras/tensor_algebra15726

comment:7 Changed 7 years ago by
 Commit changed from 53e1bb48f75dab5c0f0bc02b8c25992284e87c37 to a45c49ba71f5cbd6b8fdb7729a4513a8bb3c77df
comment:8 Changed 7 years ago by
 Commit changed from a45c49ba71f5cbd6b8fdb7729a4513a8bb3c77df to 1f388e0054251e1ee3ae1d350ad1e258de1b54ba
Branch pushed to git repo; I updated commit sha1. New commits:
69c881b  Merge branch 'develop' into public/algebras/tensor_algebra15726

c1cc341  Merge branch 'develop' into public/monoids/15289indexed

49068b2  Merge branch 'develop' into public/monoids/15289indexed

1f388e0  Merge branch 'public/monoids/15289indexed' into public/algebras/tensor_algebra15726

comment:9 Changed 7 years ago by
Is there any connection and/or overlap between this ticket and #15916?
comment:10 followup: ↓ 12 Changed 7 years ago by
comment:11 Changed 7 years ago by
 Commit changed from 1f388e0054251e1ee3ae1d350ad1e258de1b54ba to 8a7e9e329b50c44f0d3238db10df24c01540753d
comment:12 in reply to: ↑ 10 Changed 7 years ago by
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
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
 Commit changed from 8a7e9e329b50c44f0d3238db10df24c01540753d to 9d2fa708720ce123ce732fa5414d5a1d09823b11
comment:15 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:16 Changed 7 years ago by
 Commit changed from 9d2fa708720ce123ce732fa5414d5a1d09823b11 to 3920f5b76fe6f53ef21f28896d2a97bd820be647
comment:17 Changed 7 years ago by
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
 Milestone changed from sage6.3 to sage6.4
comment:19 Changed 6 years ago by
 Commit changed from 3920f5b76fe6f53ef21f28896d2a97bd820be647 to 726b7a92af369bbfa6517c59aec2973d68f87123
comment:20 Changed 6 years ago by
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
 Status changed from needs_review to needs_work
does not apply, needs rebase
comment:22 Changed 5 years ago by
 Commit changed from 726b7a92af369bbfa6517c59aec2973d68f87123 to e8c242edfd8a20363b8d97eaa555f9902d45ebb2
Branch pushed to git repo; I updated commit sha1. New commits:
e8c242e  Merge branch 'public/algebras/tensor_algebra15726' of trac.sagemath.org:sage into public/algebras/tensor_algebra15726

comment:23 Changed 5 years ago by
 Milestone changed from sage6.4 to sage6.9
 Status changed from needs_work to needs_review
comment:24 Changed 5 years ago by
 Status changed from needs_review to needs_work
two failing doctests
comment:25 Changed 5 years ago by
 Commit changed from e8c242edfd8a20363b8d97eaa555f9902d45ebb2 to cfd9e11419be7cb17fe3c8cddfe0577189776448
Branch pushed to git repo; I updated commit sha1. New commits:
cfd9e11  Fixed import due to change in file location.

comment:26 Changed 5 years ago by
 Status changed from needs_work to needs_review
Fixed. The location of the ascii_art
moved.
comment:27 Changed 5 years ago by
 Status changed from needs_review to needs_work
some failing doctests
comment:28 Changed 5 years ago by
 Commit changed from cfd9e11419be7cb17fe3c8cddfe0577189776448 to 6342a6021a7cc7ebfaf1a663fd6aa37ff95d22b8
comment:29 Changed 5 years ago by
 Milestone changed from sage6.9 to sage6.10
 Status changed from needs_work to needs_review
comment:30 Changed 5 years ago by
 Commit changed from 6342a6021a7cc7ebfaf1a663fd6aa37ff95d22b8 to 7d171266c5ab43116a7be8d1aa21da5f61517bd6
Branch pushed to git repo; I updated commit sha1. New commits:
7d17126  Merge branch 'public/algebras/tensor_algebra15726' into 7.1.b5

comment:31 Changed 5 years ago by
 Commit changed from 7d171266c5ab43116a7be8d1aa21da5f61517bd6 to 1be0f6ccfeb6793ea86588100a1dc5e40e7a77a0
comment:32 Changed 4 years ago by
 Commit changed from 1be0f6ccfeb6793ea86588100a1dc5e40e7a77a0 to ab9930b076bd5db946b49a33f8a7024f4f98070d
comment:33 Changed 4 years ago by
 Commit changed from ab9930b076bd5db946b49a33f8a7024f4f98070d to 14428b1293616372f12f20cf4aa53acf48ed76bd
Branch pushed to git repo; I updated commit sha1. New commits:
14428b1  add a todo

comment:34 Changed 4 years ago by
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
 Commit changed from 14428b1293616372f12f20cf4aa53acf48ed76bd to e51dddccc85be7249d6cf545069195e01f5da1b2
Branch pushed to git repo; I updated commit sha1. New commits:
e51dddc  correct errors of my own

comment:36 Changed 4 years ago by
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
 Commit changed from e51dddccc85be7249d6cf545069195e01f5da1b2 to 8b45d358f1cc00c9601fe1137bb19e827ed8a2b5
comment:38 Changed 4 years ago by
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
 Commit changed from 8b45d358f1cc00c9601fe1137bb19e827ed8a2b5 to 204633bc375b2d84d5ea1ce455d69b6ee68828ae
comment:40 Changed 4 years ago by
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
 Dependencies changed from #15289 to #15289, #21405
 Milestone changed from sage6.10 to sage7.4
 Reviewers set to Darij Grinberg
comment:42 Changed 4 years ago by
 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
 Dependencies changed from #15289, #21405 to #15289
comment:44 Changed 4 years ago by
Thanks  but is changing the commit back enough, or should we also make a new branch?
comment:45 Changed 4 years ago by
I set the branch to point back to the old commit, so it is enough.
comment:46 Changed 4 years ago by
Ah, I see. I was distracted by the change to free_module.py
.
comment:48 Changed 4 years ago by
 Status changed from needs_review to positive_review
comment:49 Changed 4 years ago by
Thanks for the review.
comment:50 Changed 4 years ago by
 Branch changed from public/algebras/tensor_algebra15726 to 8b45d358f1cc00c9601fe1137bb19e827ed8a2b5
 Resolution set to fixed
 Status changed from positive_review to closed
Last 10 new commits:
Merge branch 'develop' into public/algebras/tensor_algebra15726
Finished tensor_module.py and lazily imported new classes.
Merge branch 'public/15567' of trac.sagemath.org:sage into public/algebras/tensor_algebra15726
Using coproduct via multiplication.
Merge branch 'develop' into public/monoids/15289indexed
Added more robustness to element creation.
Merge branch 'public/monoids/15289indexed' into public/algebras/tensor_algebra15726
Added some more documentation.
Made the tensor module into a functor.
Merge branch 'develop' into public/monoids/15289indexed