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