OKlibrary  0.2.1.6
general.hpp File Reference

Plans in general regarding semigroups. More...

Go to the source code of this file.

## Detailed Description

Plans in general regarding semigroups.

Todo:
Transformations
• The abbreviation for transformations is "trf", in the two forms "trf_l" (via lists), and "trf_sm" (more general, via set-maps).
• Provide trf_sm_compo and trf_sm_mon.
• Compare "Acronyms" in Algebra/Lisp/Groupoids/Groups/plans/SymmetricGroups.hpp.
• It seems we should switch "trf_l" -> "trfl", and likewise "trf_sm" -> "trfsm".
• There is also "trff", that is, transformations as functions.
Todo:
The natural operation of N
• For every semigroup (S,*) we have the natural operation of N by "exponentiation", (n,x) -> x^n for x in S and n in N.
• This operation is an operation of the prering (N,+,*,0,1) on (S,*) (i.e., a "premodule"; see ComputerAlgebra/Algebra/Lisp/Ringframes/plans/BasicNotions.hpp), that is, a homomorphism of (N,+,*,0,1) into the transformation-prering of S (with map-composition as multiplication, and pointwise-composition (in S) as addition).
• If S is a monoid, than N_0 can operate, and if S is a group, then Z can operate.
1. Algorithmically, these are just case distinctions: if n = 0, then return the neutral element, if n < 0, then compute the inverse x' and return (x')^(-n).
2. According to our general philosophy "no polymorphism at the Maxima/Lisp level", we should thus have three functions, providing these three different operations.
3. Perhaps all this should go to Algebra/Lisp/Ringframes/Operations ?
4. And perhaps the group-case to Algebra/Lisp/Ringframes/Modules ?
5. Or perhaps we keep it all in this module, with links to the other modules ?
6. Compare "Module Operations" in ComputerAlgebra/Algebra/Lisp/Ringframes/plans/general.hpp.
• In [Henri Cohen, A Course in Computational Algebraic Number Theory, Springer, 1993] one finds four basic algorithms.
1. "Right-left binary"
2. "Left-right binary"
3. "Left-right binary, using bits"
4. "Left-right base 2^k"; with a "flexible" improvement in the Addendum (page 547).
5. Furthermore "addition chains" are mentioned.
6. And we need also to provide the simple iterated multiplication.
• An additional "service" possibly provided by a semigroup in this context is a (fast) squaring algorithm.
1. This could be an additional parameter for all the above (fast) methods.
2. While instances are provided which just use the semigroup multiplication.
• Semigroups could also provide the complete operation of N:
1. In permutation groups where the elements are given by their cycle presentation, powers can be computed directly very efficiently; see "Computing powers, based on the cycle representation" in ComputerAlgebra/Algebra/Lisp/Groupoids/Groups/plans/SymmetricGroups.hpp.
2. So if an algorithm uses the operation of N (or N_0, or Z) on a semigroup (monoid, group), then the operation should be provided as a parameter.
Todo:
Semilattices
• Should semilattices yield of submodule of this module, or should it be separate?

Definition in file general.hpp.