1#############################################################################
2##
3##  projective.gi
4##                                recog package
5##                                                        Max Neunhoeffer
6##                                                            Ákos Seress
7##
8##  Copyright 2006-2008 by the authors.
9##  This file is free software, see license information at the end.
10##
11##  A collection of find homomorphism methods for projective groups.
12##
13#############################################################################
14
15SLPforElementFuncsProjective.TrivialProjectiveGroup :=
16   function(ri,g)
17     return StraightLineProgramNC( [ [1,0] ], 1 );
18   end;
19
20FindHomMethodsProjective.TrivialProjectiveGroup := function(ri, G)
21  local gens;
22  gens := GeneratorsOfGroup(G);
23  if not ForAll(gens, ri!.isone) then
24      return NeverApplicable;
25  fi;
26  SetSize(ri, 1);
27  Setslpforelement(ri, SLPforElementFuncsProjective.TrivialProjectiveGroup);
28  Setslptonice(ri, StraightLineProgramNC([[[1,0]]],Length(gens)));
29  SetFilterObj(ri, IsLeaf);
30  return Success;
31end;
32
33FindHomMethodsProjective.BlocksModScalars := function(ri,G)
34  # We assume that ri!.blocks is a list of ranges where the diagonal
35  # blocks are. Note that their length does not have to sum up to
36  # the dimension, because some blocks at the end might already be trivial.
37  # Note further that in this method it is understood that G should *neither*
38  # be recognised as a matrix group *nor* as a projective group. Rather,
39  # all "block-scalars" shall be ignored. This method is only used when
40  # used as a hint by FindHomMethodsMatrix.BlockDiagonal!
41  local H,data,hom,middle,newgens,nrblocks,topblock;
42  nrblocks := Length(ri!.blocks);  # this is always >= 1
43  if ForAll(ri!.blocks,b->Length(b)=1) then
44      # All blocks are projectively trivial, so nothing to do here:
45      SetSize(ri,1);
46      Setslpforelement(ri,SLPforElementFuncsProjective.TrivialProjectiveGroup);
47      Setslptonice( ri, StraightLineProgramNC([[[1,0]]],
48                                              Length(GeneratorsOfGroup(G))));
49      SetFilterObj(ri,IsLeaf);
50      ri!.comment := "_BlocksDim=1";
51      return Success;
52  fi;
53
54  if nrblocks = 1 then   # in this case the block is everything!
55      # no hints for the factor, will run into diagonal and notice scalar
56      data := rec(poss := ri!.blocks[1]);
57      newgens := List(GeneratorsOfGroup(G),x->RECOG.HomToDiagonalBlock(data,x));
58      H := GroupWithGenerators(newgens);
59      hom := GroupHomByFuncWithData(G,H,RECOG.HomToDiagonalBlock,data);
60      SetHomom(ri,hom);
61      # The following is already be set, but make it explicit here:
62      Setmethodsforfactor(ri,FindHomDbProjective);
63      # no kernel:
64      findgensNmeth(ri).method := FindKernelDoNothing;
65      return Success;
66  fi;
67  # Otherwise more than one block, cut in half:
68  middle := QuoInt(nrblocks,2)+1;   # the first one taken
69  topblock := ri!.blocks[nrblocks];
70  data := rec(poss := [ri!.blocks[middle][1]..topblock[Length(topblock)]]);
71  newgens := List(GeneratorsOfGroup(G),x->RECOG.HomToDiagonalBlock(data,x));
72  H := GroupWithGenerators(newgens);
73  hom := GroupHomByFuncWithData(G,H,RECOG.HomToDiagonalBlock,data);
74  SetHomom(ri,hom);
75
76  # the factor are the last few blocks:
77  # The following is already be set, but make it explicit here:
78  Setmethodsforfactor(ri,FindHomDbProjective);
79  if middle < nrblocks then   # more than one block in factor:
80      forfactor(ri).blocks := List(ri!.blocks{[middle..nrblocks]},
81                                   x->x - (ri!.blocks[middle][1]-1));
82      Add(forfactor(ri).hints,
83          rec( method := FindHomMethodsProjective.BlocksModScalars,rank := 2000,
84               stamp := "BlocksModScalars" ),1);
85  fi; # Otherwise the factor is to be recognised projectively as usual
86
87  # the kernel is the first few blocks:
88  findgensNmeth(ri).args[1] := 10 + nrblocks;
89  findgensNmeth(ri).args[2] := 5 + middle - 1;
90  # The following is already set, but make it explicit here:
91  forkernel(ri).blocks := ri!.blocks{[1..middle-1]};
92  Add(forkernel(ri).hints,
93      rec( method := FindHomMethodsProjective.BlocksModScalars, rank := 2000,
94           stamp := "BlocksModScalars" ),1);
95  Setimmediateverification(ri,true);
96  return Success;
97end;
98
99SLPforElementFuncsProjective.StabilizerChain := function(ri,x)
100  local r;
101  r := SiftGroupElementSLP(ri!.stabilizerchain,x);
102  return r.slp;
103end;
104
105FindHomMethodsProjective.StabilizerChain := function(ri,G)
106  local Gm,S,SS,d,f,fu,opt,perms,q;
107  d := ri!.dimension;
108  f := ri!.field;
109  q := Size(f);
110  fu := function() return RandomElm(ri,"StabilizerChain",true).el; end;
111  opt := rec( Projective := true, RandomElmFunc := fu );
112  Gm := GroupWithGenerators(ri!.gensHmem);
113  S := StabilizerChain(Gm,opt);
114  perms := ActionOnOrbit(S!.orb,ri!.gensHmem);
115  SS := StabilizerChain(Group(perms));
116  if Size(SS) = Size(S) then
117      SetSize(ri,Size(S));
118      ri!.stabilizerchain := S;
119      Setslptonice(ri,SLPOfElms(StrongGenerators(S)));
120      ForgetMemory(S);
121      Unbind(S!.opt.RandomElmFunc);
122      Setslpforelement(ri,SLPforElementFuncsProjective.StabilizerChain);
123      SetFilterObj(ri,IsLeaf);
124  else
125      ForgetMemory(S);
126      SetHomom(ri,OrbActionHomomorphism(G,S!.orb));
127      Setmethodsforfactor(ri,FindHomDbPerm);
128  fi;
129  return Success;
130end;
131
132RECOG.HomProjDet := function(data,m)
133  local x;
134  x := LogFFE(DeterminantMat(m),data.z);
135  if x = fail then return fail; fi;
136  return data.c ^ (x mod data.gcd);
137end;
138
139FindHomMethodsProjective.ProjDeterminant := function(ri,G)
140  local H,c,d,detsadd,f,gcd,hom,newgens,q,z;
141  f := ri!.field;
142  d := ri!.dimension;
143  q := Size(f);
144  gcd := GcdInt(q-1,d);
145  if gcd = 1 then return NeverApplicable; fi;
146  z := Z(q);
147  detsadd := List(GeneratorsOfGroup(G),x->LogFFE(DeterminantMat(x),z) mod gcd);
148  if IsZero(detsadd) then return NeverApplicable; fi;
149  Info(InfoRecog,2,"ProjDeterminant: found non-trivial homomorphism.");
150  c := PermList(Concatenation([2..gcd],[1]));
151  newgens := List(detsadd,x->c^x);
152  H := GroupWithGenerators(newgens);
153  hom := GroupHomByFuncWithData(G,H,RECOG.HomProjDet,
154                                rec(c := c, z := z, gcd := gcd));
155  SetHomom(ri,hom);
156  Setmethodsforfactor(ri,FindHomDbPerm);
157  findgensNmeth(ri).args[1] := 8;
158  findgensNmeth(ri).args[2] := 5;
159  Setimmediateverification(ri,true);
160  return Success;
161end;
162
163RECOG.IsBlockScalarMatrix := function(blocks, x)
164  local b, s;
165  if not IsDiagonalMat(x) then
166      return false;
167  fi;
168  for b in blocks do
169      s := b[1];
170      s := x[s,s];
171      if not ForAll(b, pos -> x[pos,pos] = s) then
172          return false;
173      fi;
174  od;
175  return true;
176end;
177
178# scale the given block-scalar matrix x so that its last block
179# is the identity matrix
180RECOG.HomNormLastBlock := function(data, x)
181  local blocks, pos, s;
182  blocks := data!.blocks;
183  if not RECOG.IsBlockScalarMatrix(blocks, x) then
184      return fail;
185  fi;
186  pos := blocks[Length(blocks)][1];
187  s := x[pos,pos];
188  if not IsOne(s) then
189      x := s^-1 * x;
190  fi;
191  return x;
192end;
193
194FindHomMethodsProjective.BlockScalarProj := function(ri,G)
195  # We just norm the last block and go to matrix methods.
196  local H,data,hom,newgens,g;
197  data := rec( blocks := ri!.blocks );
198  newgens := [];
199  for g in GeneratorsOfGroup(G) do
200      g := RECOG.HomNormLastBlock(data, g);
201      if g = fail then
202          return NeverApplicable;
203      fi;
204      Add(newgens, g);
205  od;
206  H := GroupWithGenerators(newgens);
207  hom := GroupHomByFuncWithData(G,H,RECOG.HomNormLastBlock,data);
208  SetHomom(ri,hom);
209
210  findgensNmeth(ri).method := FindKernelDoNothing;  # This is an iso
211
212  # Switch to matrix mode:
213  Setmethodsforfactor(ri,FindHomDbMatrix);
214  Add(forfactor(ri).hints,
215      rec( method := FindHomMethodsMatrix.BlockScalar, rank := 2000,
216           stamp := "BlockScalar" ), 1);
217  forfactor(ri).blocks := ri!.blocks{[1..Length(ri!.blocks)-1]};
218  return Success;
219end;
220
221RECOG.MakeAlternatingMatrixReps := function(deg,f,tens)
222  local a,b,gens,gens2,i,m,ogens,r;
223  a := AlternatingGroup(deg);
224  gens := List(GeneratorsOfGroup(a),x->PermutationMat(x,deg,f));
225  ogens := ShallowCopy(gens);
226  for i in [1..tens] do
227      gens2 := [];
228      for i in [1..Length(gens)] do
229          Add(gens2,KroneckerProduct(gens[i],ogens[i]));
230      od;
231      gens := gens2;
232  od;
233  m := GModuleByMats(gens,f);
234  r := MTX.CollectedFactors(m);
235  return List(r,x->x[1].generators);
236end;
237
238RECOG.MakeSymmetricMatrixReps := function(deg,f,tens)
239  local a,b,gens,gens2,i,m,ogens,r;
240  a := SymmetricGroup(deg);
241  gens := List(GeneratorsOfGroup(a),x->PermutationMat(x,deg,f));
242  ogens := ShallowCopy(gens);
243  for i in [1..tens] do
244      gens2 := [];
245      for i in [1..Length(gens)] do
246          Add(gens2,KroneckerProduct(gens[i],ogens[i]));
247      od;
248      gens := gens2;
249  od;
250  m := GModuleByMats(gens,f);
251  r := MTX.CollectedFactors(m);
252  return List(r,x->x[1].generators);
253end;
254
255# The method installations:
256
257AddMethod( FindHomDbProjective, FindHomMethodsProjective.TrivialProjectiveGroup,
258  3000, "TrivialProjectiveGroup",
259        "check if all generators are scalar multiples of the identity matrix" );
260AddMethod( FindHomDbProjective, FindHomMethodsProjective.ProjDeterminant,
261  1300, "ProjDeterminant",
262        "find homomorphism to non-zero scalars mod d-th powers" );
263AddMethod( FindHomDbProjective, FindHomMethodsProjective.FewGensAbelian,
264  1250, "FewGensAbelian",
265     "if very few generators, check IsAbelian and if yes, do KnownNilpotent");
266# Note that we *can* in fact use the Matrix method here, because it
267# will do the right thing when used in projective mode:
268AddMethod( FindHomDbProjective, FindHomMethodsMatrix.ReducibleIso,
269  1200, "ReducibleIso",
270        "use MeatAxe to find a composition series, do base change" );
271AddMethod( FindHomDbProjective, FindHomMethodsProjective.NotAbsolutelyIrred,
272  1100, "NotAbsolutelyIrred",
273        "write over a bigger field with smaller degree" );
274AddMethod( FindHomDbProjective, FindHomMethodsProjective.ClassicalNatural,
275  1050, "ClassicalNatural",
276        "check whether it is a classical group in its natural representation" );
277AddMethod( FindHomDbProjective, FindHomMethodsProjective.Subfield,
278  1000, "Subfield",
279        "write over a smaller field with same degree" );
280AddMethod( FindHomDbProjective, FindHomMethodsProjective.C3C5,
281  900, "C3C5",
282        "compute a normal subgroup of derived and resolve C3 and C5" );
283#AddMethod( FindHomDbProjective, FindHomMethodsProjective.Derived,
284#   900, "Derived",
285#        "restrict to derived subgroup" );
286# Superseded by C3C5.
287AddMethod( FindHomDbProjective, FindHomMethodsProjective.C6,
288   850, "C6",
289        "find either an (imprimitive) action or a symplectic one" );
290AddMethod( FindHomDbProjective, FindHomMethodsProjective.D247,
291   840, "D247",
292        "play games to find a normal subgroup" );
293# We can do the following early on since it will quickly fail for
294# non-sporadic groups:
295AddMethod( FindHomDbProjective, FindHomMethodsProjective.SporadicsByOrders,
296   820, "SporadicsByOrders",
297        "generate a few random elements and compute the proj. orders" );
298AddMethod( FindHomDbProjective, FindHomMethodsProjective.AltSymBBByDegree,
299   810, "AltSymBBByDegree",
300        "try BB recognition for dim+1 and/or dim+2 if sensible" );
301AddMethod( FindHomDbProjective, FindHomMethodsProjective.TensorDecomposable,
302   800, "Tensor",
303        "find a tensor decomposition" );
304AddMethod( FindHomDbProjective, FindHomMethodsProjective.FindElmOfEvenNormal,
305   700, "FindElmOfEvenNormal",
306        "find D2, D4 or D7 by finding an element of an even normal subgroup" );
307AddMethod( FindHomDbProjective, FindHomMethodsProjective.LowIndex,
308   600, "LowIndex",
309        "find an (imprimitive) action on subspaces" );
310AddMethod( FindHomDbProjective, FindHomMethodsProjective.ComputeSimpleSocle,
311   550, "ComputeSimpleSocle",
312        "compute simple socle of almost simple group" );
313AddMethod( FindHomDbProjective, FindHomMethodsProjective.ThreeLargeElOrders,
314   500, "ThreeLargeElOrders",
315        "look at three large element orders" );
316AddMethod( FindHomDbProjective, FindHomMethodsProjective.LieTypeNonConstr,
317   400, "LieTypeNonConstr",
318        "do non-constructive recognition of Lie type groups" );
319AddMethod( FindHomDbProjective, FindHomMethodsProjective.StabilizerChain,
320   100, "StabilizerChain",
321        "last resort: compute a stabilizer chain (projectively)" );
322
323# Old methods which are no longer used:
324
325#AddMethod( FindHomDbProjective, FindHomMethodsProjective.FindEvenNormal,
326#   825, "FindEvenNormal",
327#        "find D2, D4 or D7 by finding reducible normal subgroup" );
328#AddMethod( FindHomDbProjective, FindHomMethodsProjective.AlternatingBBByOrders,
329#   580, "AlternatingBBByOrders",
330#        "generate a few random elements and compute the proj. orders" );
331
332##
333##  This program is free software: you can redistribute it and/or modify
334##  it under the terms of the GNU General Public License as published by
335##  the Free Software Foundation, either version 3 of the License, or
336##  (at your option) any later version.
337##
338##  This program is distributed in the hope that it will be useful,
339##  but WITHOUT ANY WARRANTY; without even the implied warranty of
340##  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
341##  GNU General Public License for more details.
342##
343##  You should have received a copy of the GNU General Public License
344##  along with this program.  If not, see <http://www.gnu.org/licenses/>.
345##
346
347