OKlibrary  0.2.1.6
Order.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 17.5.2010 (Swansea) */
00002 /* Copyright 2010, 2012 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00022 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.mac")$
00023 
00024 /* Given an associative composition and an element a, compute the closure
00025    of {a}, i.e., the subsemigroup generated by a:
00026 */
00027 closure_element_sgr(compo_, a) := block([p : compo_(a,a), res : {a}],
00028  while not elementp(p,res) do (
00029   res : adjoin(p,res),
00030   p : compo_(p,a)
00031  ),
00032  res)$
00033 
00034 /* Given an associative composition and an element a, compute the
00035    order of a:
00036 */
00037 order_element_sgr(compo_, a) := length(closure_element_sgr(compo_, a))$
00038 /* Remarks:
00039    1. The set of elements of order 1 of a semigroup S is
00040       idempotents_grd(S).
00041    2. In a group, the order of an element a is the smallest n >= 0 such
00042       that a^n = 1.
00043 */
00044 
00045 /* More efficiently, for compo_ and element a decide whether a has
00046    order precisely n:
00047 */
00048 test_order_element_sgr(compo_, a, n) := block(
00049  [p : compo_(a,a), res : {a}, l : 1],
00050   while not elementp(p,res) and l <= n do (
00051    res : adjoin(p,res), l : l+1,
00052    p : compo_(p,a)
00053   ),
00054   is(l=n))$
00055 
00056 /* For a semigroup S and a number n, the subset of S of elements of
00057    order precisely n:
00058 */
00059 subset_order_sgr(S,n) :=
00060  subset(first(S), lambda([x], test_order_element_sgr(second(S), x, n)))$
00061 
00062 
00063 /* Computing the triple [index, period, order] of a: */
00064 ipo_element_sgr(compo_, a) := block(
00065  [p : compo_(a,a), h : sm2hm({[a,1]}), i : 2, index],
00066   index : ev_hm(h,p),
00067   while index = false do (
00068     set_hm(h,p,i),
00069     i : i + 1,
00070     p : compo_(p,a),
00071     index : ev_hm(h,p)
00072   ),
00073   [index, i-index, i-1])$
00074 /* Recall: The period of a is the number of elements in the kernel of a,
00075    that is, the largest subgroup contained in the subsemigroup generated by a,
00076    while the index is the smallest exponent i such that a^i is in the kernel.
00077 */
00078 
00079 /* Computing a pair [[index,period,order],kernel], where the kernel is
00080    given as a list of elements, with the first element the first generating
00081    element (of the kernel) encountered, and with the following elements the
00082    powers of this element: */
00083 ipokernel_element_sgr(compo_, a) := block(
00084  [p : compo_(a,a), h : sm2hm({[a,1]}), i : 2, index],
00085   index : ev_hm(h,p),
00086   while index = false do (
00087     set_hm(h,p,i),
00088     i : i + 1,
00089     p : compo_(p,a),
00090     index : ev_hm(h,p)
00091   ),
00092   block([period : i-index, order : i-1],
00093     [[index, period, order],
00094      map(first, 
00095          sort(sublist(hm2osm(h), lambda([p], second(p) >= index)),
00096               lambda([p1,p2], is(second(p1) < second(p2)))))
00097     ]))$
00098 /* Recall, that the kernel is a cyclic (sub-)group. Thus the last element
00099    in the kernel list is its neutral element, which is also the (unique)
00100    idempotent element in the subsemigroup generated by a.
00101 */
00102