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.