SymmetricGroups.hpp File Reference

Plans on providing the basic symmetric groups. More...

Go to the source code of this file.

Detailed Description

Plans on providing the basic symmetric groups.

  • As special cases of groups we provide the symmetric groups sym_grp(X) and sym_grp(n).
  • In SymmetricGroups.mac; the submodule PermutationGroups contains then all these special algorithms.
  • For a permutation there are four basic models:
    1. (i) A function which is a bijection; a problem is how to provide an order, so that we can put these elements into a set?
    2. (ii) A set-map.
    3. (iii) A list of elements.
    4. (iv) A set of cycles (each a non-empty list, smallest element first, which altogether partition the base set).
  • Likely we should provide all four models, with conversions between them.
    1. For (ii), (iii), (iv) equality between elements is clear, but for (i) we need an equality test.
    2. Composition for (ii), (iii), (iv) must happen eagerly, but for (i) it can happen "totally lazily" and "lazily".
    3. The problem with (iv) is that to enforce uniqueness, we need an order on the elements, so that the cycle always starts with the first element in the order.
      • So perhaps it is only provided with ordered base-set, or for standardised elements.
      • Perhaps, since the cycle presentation is combinatorial in nature, we provide it only for standardised elements (i.e., in {1,...,n}).
      • Furthermore, perhaps for a cycle presentation of a permutation, only the non-trivial cycles are given, while trivial (one-element) cycles are discarded.
      • Or we speak of "reduced cycles".
      • Or, as in [Rotman], of a "complete factorisation".
  • Compare "Transformations" in Algebra/Lisp/Groupoids/Semigroups/plans/general.hpp.
  • For transformations as lists, yet we use "trf_l" as well as "trfl".
  • For transformations as functions yet we use "trff".
  • Perhaps the forms without underscore are preferable, since we get more underscores in the rest of the names.
  • DONE For permutations (special transformations) we use "per"; perhaps it should be "pmt"?
Computing powers, based on the cycle representation

Definition in file SymmetricGroups.hpp.