1############################################################################
2##
3##  elements.gi
4##  Copyright (C) 2016-18                                   Wilf A. Wilson
5##
6##  Licensing information can be found in the README file of this package.
7##
8#############################################################################
9
10SEMIGROUPS.IndexPeriodByRank := function(x, rank)
11  local k, p, s, rank_s, powers, min_rank, index, lower, next, mid, y, z,
12  period, S;
13
14  k := rank(x);
15  p := 1;
16  s := x ^ 2;
17  rank_s := rank(s);
18  powers := [x, s];  # powers[i] = x ^ (2 ^ (i - 1)), e.g. powers[5] = x ^ 16.
19
20  # Locate the index between its closest powers of 2
21  while rank_s <= k - (2 ^ (p - 1)) do
22    k := rank_s;
23    p := p + 1;
24    s := s ^ 2;
25    rank_s := rank(s);
26    Add(powers, s);
27  od;
28
29  min_rank := rank_s;
30
31  if rank(x) = min_rank then
32    index := 1;
33  else
34    # Get the specific values of the closest powers of 2 to index
35    if k = min_rank then
36      lower := p - 2;
37    else
38      lower := p - 1;
39    fi;
40    # (2 ^ lower) < index of x <= (2 ^ (lower + 1))
41
42    index := (2 ^ lower) + 1;  # index is always a lower bound for the true index
43    next := lower;
44    lower := powers[lower + 1];
45
46    # Perform a 'binary search' to completion to nail down the position of index
47    # The index is the *least* number such that x ^ index = min_rank
48    while next > 0 do
49      mid := lower * powers[next];
50      next := next - 1;
51      if rank(mid) <> min_rank then
52        lower := mid;
53        index := index + (2 ^ next);
54      fi;
55    od;
56  fi;
57
58  y := x ^ index;
59  z := y * x;
60  if y = z then
61    period := 1;
62  elif IsMultiplicativeElementWithOne(y) and One(y) <> fail and z = One(y) then
63    period := 2;
64  else
65    S := Semigroup(y, z);
66    SetIsGroupAsSemigroup(S, true);
67    period := Size(S);
68  fi;
69  return [index, period];
70end;
71
72InstallMethod(IndexPeriodOfSemigroupElement, "for a multiplicative element",
73[IsMultiplicativeElement],
74function(x)
75  local index, y, z, period, S;
76
77  if not IsGeneratorsOfSemigroup([x]) then
78    ErrorNoReturn("Semigroups: IndexPeriodOfSemigroupElement: usage,\n",
79                  "the argument <x> must be the generator of a semigroup,");
80  fi;
81  index := NrDClasses(Semigroup(x));
82  y := x ^ index;
83  z := y * x;
84  if y = z then
85    period := 1;
86  elif IsMultiplicativeElementWithOne(y) and One(y) <> fail and z = One(y) then
87    period := 2;
88  else
89    S := Semigroup(y, z);
90    SetIsGroupAsSemigroup(S, true);
91    period := Size(S);
92  fi;
93  return [index, period];
94end);
95
96InstallMethod(SmallestIdempotentPower, "for a multiplicative element",
97[IsMultiplicativeElement],
98function(x)
99  local a, index, period, r;
100
101  if not IsGeneratorsOfSemigroup([x]) then
102    ErrorNoReturn("Semigroups: SmallestIdempotentPower: usage,\n",
103                  "the argument <x> must be the generator of a semigroup,");
104  fi;
105  a := IndexPeriodOfSemigroupElement(x);
106  index := a[1];
107  period := a[2];
108  # From Howie 1995, page 11
109  r := index mod period;
110  if r = 0 then
111    return index;
112  fi;
113  return index + period - r;
114end);
115
116InstallMethod(IsMultiplicativeZero,
117"for a semigroup with multiplicative zero and multiplicative element",
118[IsSemigroup and HasMultiplicativeZero, IsMultiplicativeElement],
119SUM_FLAGS,
120{S, x} -> MultiplicativeZero(S) <> fail and x = MultiplicativeZero(S));
121