Try to obtain the MinimalGeneratingSet of an FP group with the clues of the relationship analysis among the relators based on graph theory.

[hongyi-zhao]

Hi here,

I try to obtain the MinimalGeneratingSet of an FP group with the clues of the relationship analysis among the relators based on graph theory. I wonder if the idea is feasible?

Here is an example:

gap> hom:=IsomorphismFpGroup(SpaceGroupOnLeftIT(3,229));;
gap> Image(IsomorphismSimplifiedFpGroup( Image(hom)));
<fp group on the generators [ f1, f2, f3, f6 ]>
gap> RelatorsOfFpGroup(last);
[ f1^2, f3^3, (f1*f2^-1)^2, f2^4, (f3*f2)^2, f6^-1*f3^-1*f6*f3, f6^-1*f2*f1*f6*f2*f1, (f1*f3^-1*f2)^2, f2*f6^-1*(f1*f6)^2*f2^-1*f6^-1, (f2^-1*f6^-1*f2^-1*f6)^2, 
  f3^-1*f2^-2*f6*f2*f3^-1*f2^-1*f1*f6*f1 ]

Is it possible to do some feasible analysis on the road of determining the MinimalGeneratingSet of this FP group with the help of grape package?

Regards, Zhao

[fingolfin]

I don't think so.

But it's not hard to do this anywhere. Don't use fp groups for this, use a pcp group, they are much better behaved. You can use the abelian invariants to get a lower bound on the rank of the group (turns out to be 3 here) and then use SmallGeneratingSet to get, well, a small generating set. It's not hard to guess a minimal generating set from there:

gap> H:=Image(IsomorphismPcpGroup(G));
Pcp-group with orders [ 2, 2, 3, 2, 2, 0, 0, 0 ]
gap> AbelianInvariants(H);
[ 2, 2, 2 ]
gap> SmallGeneratingSet(H);
[ g1, g2, g3, g6 ]
gap> Index(H,Subgroup(H, [H.1, H.2, H.3, H.6]));
1
gap> Index(H,Subgroup(H, [H.1, H.2, H.3*H.6]));
1

So the elements H.1, H.2, H.3*H.6 (resp. their preimages under the isomorphism) form a minimal generating set.

[hongyi-zhao]

Thank you very much for your wonderful idea. But, in the general case, considering that the group is not necessarily Abelian, I think we should enumerate all the possible tuples constructed using the result of SmallGeneratingSet and then construct the possible products to do the test before we can assert the possible minimal generating sets are found. What I mean is something like the following:

gap> G:= SpaceGroupOnLeftIT(3,161);;
gap> iso:=IsomorphismPcpGroup(G);;
gap> H:=Image(iso);;
gap> b:=Size(AbelianInvariants(H));;
gap> sgs:=SmallGeneratingSet(H);;
gap> List( [1..Length( sgs )], s -> List( Filtered(Tuples(sgs, s), x -> not ( Size(Unique(x) ) =1 or IsOne(Product(x) ) ) ), x -> Union(Difference(sgs, x), [Product(x)]) ) );;
gap> Filtered(last, x -> not IsEmpty(x));;
gap> List( last, x -> Filtered(x, y -> Size(y) >=b) );;
gap> List( last, x -> Filtered(x, y-> Index(H,Subgroup(H, y)) =1 ) );;
gap> Union(Filtered( last, x -> not IsEmpty(x)));
[ [ g1*g3, g2 ], [ g1, g2^2*g3 ], [ g1, g2^2*g3*g4^-1 ], [ g1, g2*g3^2*g4^-1 ], [ g1, g2*g3*g4^-1 ], [ g1*g3^-2*g4*g5^2, g2 ] ]
gap> Minimum(List(last, x -> Size(x)));
2

[fingolfin]

There is no need to enumerate all. You only need one and thus can end the search once you found one.

besides, the group might also not be 3-generated, the you find nothing.

In practice I'd think long and hard whether I really need a minimal generating set -- often a small one is sufficient

[hongyi-zhao]

I tried with SpaceGroupOnLeftIT(3, 171) and even by a thorough enumeration, the result is still wrong:

AugmentedMatrixOnLeft := function( m, b )
  local d, g;

  d:= Unique(DimensionsMat(m));
  if Size(d) <> 1 then
    Error( "The matrix is not square." );
  fi;
  d := d[1];
  g:=List([1..d], x-> Concatenation( m[x], [b[x]]));
  # 0*[1..d]=Zero([1..d]);
  Add(g, Concatenation( Zero([1..d]), [1] ) ); 
  return g;
end;

MinimalGeneratingSetofPcpGroup:= function( gens )
  local d, tgens, G, iso, H, b, sgs, tupsps, minsgs;

  # The correct result should be 2.
  # gens:=GeneratorsOfGroup( SpaceGroupOnLeftIT(3,171));

  d := DimensionOfMatrixGroup( Group(gens) ) - 1;
  tgens:= List( IdentityMat(d) ,x -> AugmentedMatrixOnLeft( IdentityMat(d), x ) ); 
  gens := Union( gens, tgens );

  G := AffineCrystGroupOnLeft(gens);

  iso:=IsomorphismPcpGroup(G);
  H:=Image(iso);
  b:=Size(AbelianInvariants(H));
  sgs:=SmallGeneratingSet(H);
  if Length( sgs ) > b then
    # https://stackoverflow.com/questions/72302100/seeking-the-minimal-generating-set-of-a-affinecrystgroup
    tupsps:=List( [1..Length( sgs )], s -> List( Filtered(Tuples(sgs, s), x -> not ( Size(Unique(x) ) =1 or IsOne(Product(x) ) ) ), x -> Union(Difference(sgs, x), [Product(x)]) ) );
    tupsps:=Union(Filtered(tupsps, x -> not IsEmpty(x)));

    minsgs:=Filtered( tupsps, x -> Size(x) >= b);
    minsgs:=Filtered( minsgs, x -> Index(H,Subgroup(H, x)) =1 );
    minsgs:=Filtered( minsgs, x -> not IsEmpty(x));
    minsgs:=Filtered( minsgs, x -> Size(x) = Minimum(List(minsgs, x -> Size(x))) );
    if not IsEmpty(minsgs) then
      minsgs:=minsgs[1];
    fi;
  else
    minsgs:=sgs;
    # List(sgs, x -> PreImagesRepresentative(iso, x));
  fi;

  return minsgs;
end;

Then I got the following result:

gap> MinimalGeneratingSetofPcpGroup( GeneratorsOfGroup( SpaceGroupOnLeftIT(3, 171)) );
[ g1^2*g2, g3, g5 ]

In fact, the correct size should be 2, as shown below:

So, I'm still confused. What's the cause of the problem?

Regards, Zhao

[fingolfin]

Computing minimal generating sets of infinite non-nilpotent polycyclic is in general a very hard problem, so don't expect some magic to happen here. Nor can you expect to just write down an algorithm.

But you can at least experiment a bit, and my point just was that a good starting point is to first work out a generating set for the maximal abelian quotient G/G', lift it to G, and then try to "tweak" it until you get something that works.

So first we start with generators for G/G':

gap> G:=SpaceGroupOnLeftIT(3, 171);
SpaceGroupOnLeftIT(3,171,'1')
gap> H:=Image(IsomorphismPcpGroup(G));
Pcp-group with orders [ 2, 3, 0, 0, 0 ]
gap> AbelianInvariants(H);
[ 0, 2 ]
gap> epi:=MaximalAbelianQuotient(H);
[ g1, g2, g5, g3, g4 ] -> [ g1, g2, g3, id, id ]
gap> MinimalGeneratingSet(Image(epi));
[ g1, g1*g2*g3 ]
gap> gens:=List(last, x -> PreImagesRepresentative(epi,x));
[ g1, g1*g2*g5 ]

Unfortunately the group these generate is too small:

gap> K:=Subgroup(H,gens);
Pcp-group with orders [ 2, 3, 0 ]
gap> Index(H,K);
infinity
gap> Pcp(K);
Pcp [ g1, g2, g5 ] with orders [ 2, 3, 0 ]

Now we can play around a bit to find something (one could write a program to "try a bit" of course, but don't expect it to terminate in general):

gap> K:=Subgroup(H, [H.1*H.3, H.2]); Index(H,K); Pcp(K);
Pcp-group with orders [ 2, 3, 0, 0, 0 ]
12
Pcp [ g1*g4, g2, g3*g4^2, g4^3, g5^4 ] with orders [ 2, 3, 0, 0, 0 ]
gap> K:=Subgroup(H, [H.1, H.2]); Index(H,K); Pcp(K);
Pcp-group with orders [ 2, 3, 0 ]
infinity
Pcp [ g1, g2, g5^4 ] with orders [ 2, 3, 0 ]
gap> K:=Subgroup(H, [H.1*H.3, H.2]); Index(H,K); Pcp(K);
Pcp-group with orders [ 2, 3, 0, 0, 0 ]
12
Pcp [ g1*g4, g2, g3*g4^2, g4^3, g5^4 ] with orders [ 2, 3, 0, 0, 0 ]
gap> K:=Subgroup(H, [H.1*H.3, H.2*H.4]); Index(H,K); Pcp(K);
Pcp-group with orders [ 2, 3, 0, 0, 0 ]
28
Pcp [ g1*g4^4, g2*g4, g3*g4^3, g4^7, g5^4 ] with orders [ 2, 3, 0, 0, 0 ]
gap> K:=Subgroup(H, [H.1*H.3, H.2*H.5]); Index(H,K); Pcp(K);
Pcp-group with orders [ 2, 3, 0, 0, 0 ]
3
Pcp [ g1*g4, g2, g3*g4^2, g4^3, g5 ] with orders [ 2, 3, 0, 0, 0 ]
gap> K:=Subgroup(H, [H.1*H.4, H.2*H.5]); Index(H,K); Pcp(K);
Pcp-group with orders [ 2, 3, 0, 0, 0 ]
3
Pcp [ g1*g4, g2, g3*g4^2, g4^3, g5 ] with orders [ 2, 3, 0, 0, 0 ]
gap> K:=Subgroup(H, [H.1*H.4, H.2]); Index(H,K); Pcp(K);
Pcp-group with orders [ 2, 3, 0, 0, 0 ]
12
Pcp [ g1*g4, g2, g3*g4^2, g4^3, g5^4 ] with orders [ 2, 3, 0, 0, 0 ]
gap> K:=Subgroup(H, [H.1*H.4, H.2*H.4]); Index(H,K); Pcp(K);
Pcp-group with orders [ 2, 3, 0, 0, 0 ]
4
Pcp [ g1, g2, g3, g4, g5^4 ] with orders [ 2, 3, 0, 0, 0 ]
gap> K:=Subgroup(H, [H.1*H.4, H.2*H.4*H.5]); Index(H,K); Pcp(K);
Pcp-group with orders [ 2, 3, 0, 0, 0 ]
1
Pcp [ g1, g2, g3, g4, g5 ] with orders [ 2, 3, 0, 0, 0 ]

[hongyi-zhao]

Computing minimal generating sets of infinite non-nilpotent polycyclic is in general a very hard problem, so don't expect some magic to happen here. Nor can you expect to just write down an algorithm.

This is also my puzzle: if so, how the systematic results given in GENERATORS AND RELATIONS FOR SPACE GROUPS were obtained (although some of them are wrong)?

spcgps.pdf

As an example, the following result shown in the above document is wrong:

In fact, this group is 2-generated, as shown below:

gap> G:=SpaceGroupOnLeftIT(3, 227);
SpaceGroupOnLeftIT(3,227,'2')
gap> H:=Image(IsomorphismPcpGroup(G));
Pcp-group with orders [ 2, 2, 3, 2, 2, 0, 0, 0 ]
gap> AbelianInvariants(H);
[ 2, 2 ]
gap> epi:=MaximalAbelianQuotient(H);
[ g1, g2, g3, g4, g5, g6, g7, g8 ] -> [ g1, g2, id, id, id, id, id, id ]
gap> MinimalGeneratingSet(Image(epi));
[ g2, g1*g2 ]
gap> gens:=List(last, x -> PreImagesRepresentative(epi,x));
[ g2, g1*g2 ]
gap> # Unfortunately the group these generate is too small:
gap> K:=Subgroup(H,gens);
Pcp-group with orders [ 2, 2, 2, 0, 0, 0 ]
gap> Index(H,K);
6
gap> Pcp(K);
Pcp [ g1, g2, g4, g6, g7, g8 ] with orders [ 2, 2, 2, 0, 0, 0 ]
gap> # So, we try other possibilities:
gap> K:=Subgroup(H, [H.1*H.2, H.1*H.3]); Index(H,K); Pcp(K);
Pcp-group with orders [ 2, 2, 3, 2, 2, 0, 0, 0 ]
1
Pcp [ g1, g2, g3, g4, g5, g6, g7, g8 ] with orders [ 2, 2, 3, 2, 2, 0, 0, 0 ]

Now we can play around a bit to find something (one could write a program to "try a bit" of course, but don't expect it to terminate in general):

I made the following more attempts:

gap> K:=Subgroup(H, [H.1*H.4, H.2*H.4*H.5]); Index(H,K); Pcp(K);
Pcp-group with orders [ 2, 3, 0, 0, 0 ]
1
Pcp [ g1, g2, g3, g4, g5 ] with orders [ 2, 3, 0, 0, 0 ]
gap> K:=Subgroup(H, [H.4*H.1, H.4*H.2*H.5]); Index(H,K); Pcp(K);
Pcp-group with orders [ 2, 3, 0, 0, 0 ]
1
Pcp [ g1, g2, g3, g4, g5 ] with orders [ 2, 3, 0, 0, 0 ]
gap> K:=Subgroup(H, [H.4*H.1, H.2*H.3*H.5]); Index(H,K); Pcp(K);
Pcp-group with orders [ 2, 3, 0, 0, 0 ]
1
Pcp [ g1, g2, g3, g4, g5 ] with orders [ 2, 3, 0, 0, 0 ]
gap> K:=Subgroup(H, [H.1*H.4, H.2*H.3*H.5]); Index(H,K); Pcp(K);
Pcp-group with orders [ 2, 3, 0, 0, 0 ]
13
Pcp [ g1*g4, g2*g4^9, g3*g4^4, g4^13, g5 ] with orders [ 2, 3, 0, 0, 0 ]
gap> K:=Subgroup(H, [H.1*H.2, H.3*H.5]); Index(H,K); Pcp(K);
Pcp-group with orders [ 2, 3, 0, 0, 0 ]
1
Pcp [ g1, g2, g3, g4, g5 ] with orders [ 2, 3, 0, 0, 0 ]
gap> K:=Subgroup(H, [H.2*H.1, H.5*H.3]); Index(H,K); Pcp(K);
Pcp-group with orders [ 2, 3, 0, 0, 0 ]
1
Pcp [ g1, g2, g3, g4, g5 ] with orders [ 2, 3, 0, 0, 0 ]

It seems that only trying the unique combinations of the origin generators and the products of their unique tuples of lowest power, a.k.a., 1, is enough.

[fingolfin]

In this example it is enough to try these combinations. In general it is not. If this was an undergrad class where I teach this, I would now give the exercise to find a counterexample.

[hongyi-zhao]

In this example it is enough to try these combinations.

I guess, as far as space group is concerned, for all pcp group isomorphism images of them, it is enough to try these combinations. Am I right?

In general it is not. If this was an undergrad class where I teach this, I would now give the exercise to find a counterexample.

1. In general, do you mean we should try the unique combinations of the origin generators from the size 1 to the length of these generators, and the products of all the possible powers of each element of all the non-duplicate tuples of these generators?
2. My level of group theory may be not as good as that of an undergraduate majoring in mathematics in your eyes :-(. After all, you are an internationally recognized expert in this field, while I am just a novice. Could you please give me such an exercise to find a counterexample? So that I can get a more intuitive understanding of the problem.

[hongyi-zhao]

https://github.com/gap-packages/grape/issues/45#issuecomment-1345264858

Computing minimal generating sets of infinite non-nilpotent polycyclic is in general a very hard problem, so don't expect some magic to happen here. Nor can you expect to just write down an algorithm.

See the following example:

gap> SG4d4565:=SpaceGroup(4,4565);
SpaceGroupOnRightBBNWZ( 4, 31, 3, 1, 1 )
gap> IsSolvable(SG4d4565);
false
gap> not IsFinite(SG4d4565) and not IsNilpotent(SG4d4565);
#I  LowerCentralSeriesOfGroup: may not stop for infinite group <G>
true
gap> IsomorphismPcpGroup(SG4d4565);
fail

In this case, the pcp isomorphism cannot be created at all. Based on the trick you provided here, I fall back to the fp isomorphism as follows:

gap> G:=SpaceGroup(4,4565);
SpaceGroupOnRightBBNWZ( 4, 31, 3, 1, 1 )
gap> iso:=IsomorphismSimplifiedFpGroup(Image(IsomorphismFpGroup(G)));
[ f1, f2, f3, f4, f5, f6, f7, f8 ] -> [ f1, f2, f2^-1*f1^2*f2*f1^-1*f2, f1^2*f2*f1^-1, f1*f2*f7*f2^-1*f1^-1, f2^2*f7*f2^-2, f7, f2*f7*f2^-1 ]
gap> H:=Image(iso);
<fp group on the generators [ f1, f2, f7 ]>
gap> AbelianInvariants(H);
[ 5 ]
gap> CosetTableDefaultLimit := 10;
10
gap> CosetTableDefaultMaxLimit := 10;
10
gap> # https://math.stackexchange.com/questions/1616541/how-to-bypass-breaking-of-loop-in-gap
gap> # This group can't be 1-generated:
gap> List( GeneratorsOfGroup(H), x->TryCosetTableInWholeGroup( Subgroup(H,[x]): silent) );
[ fail, fail, fail ]
gap> # So, try the following further:
gap> gens:=GeneratorsOfGroup(H);
[ f1, f2, f7 ]
gap> epi:=EpimorphismFromFreeGroup(H);
[ x1, x2, x3 ] -> [ f1, f2, f7 ]
gap> Fgens:=MappingGeneratorsImages(epi)[1];
[ x1, x2, x3 ]
gap> comb:=Filtered( Tuples( Fgens,2), x -> Size( Unique( x) )=2  );
[ [ x1, x2 ], [ x1, x3 ], [ x2, x1 ], [ x2, x3 ], [ x3, x1 ], [ x3, x2 ] ]
gap> List(last, x -> Product(x));
[ x1*x2, x1*x3, x2*x1, x2*x3, x3*x1, x3*x2 ]
gap> Combinations( Union( Fgens, last ),2 );
[ [ x1, x2 ], [ x1, x3 ], [ x1, x1*x2 ], [ x1, x1*x3 ], [ x1, x2*x1 ], [ x1, x2*x3 ], [ x1, x3*x1 ], [ x1, x3*x2 ], [ x2, x3 ], [ x2, x1*x2 ], [ x2, x1*x3 ], 
  [ x2, x2*x1 ], [ x2, x2*x3 ], [ x2, x3*x1 ], [ x2, x3*x2 ], [ x3, x1*x2 ], [ x3, x1*x3 ], [ x3, x2*x1 ], [ x3, x2*x3 ], [ x3, x3*x1 ], [ x3, x3*x2 ], [ x1*x2, x1*x3 ], 
  [ x1*x2, x2*x1 ], [ x1*x2, x2*x3 ], [ x1*x2, x3*x1 ], [ x1*x2, x3*x2 ], [ x1*x3, x2*x1 ], [ x1*x3, x2*x3 ], [ x1*x3, x3*x1 ], [ x1*x3, x3*x2 ], [ x2*x1, x2*x3 ], 
  [ x2*x1, x3*x1 ], [ x2*x1, x3*x2 ], [ x2*x3, x3*x1 ], [ x2*x3, x3*x2 ], [ x3*x1, x3*x2 ] ]
gap> List( last, x-> List(x, y-> MappedWord(y, Fgens,gens )));
[ [ f1, f2 ], [ f1, f7 ], [ f1, f1*f2 ], [ f1, f1*f7 ], [ f1, f2*f1 ], [ f1, f2*f7 ], [ f1, f7*f1 ], [ f1, f7*f2 ], [ f2, f7 ], [ f2, f1*f2 ], [ f2, f1*f7 ], 
  [ f2, f2*f1 ], [ f2, f2*f7 ], [ f2, f7*f1 ], [ f2, f7*f2 ], [ f7, f1*f2 ], [ f7, f1*f7 ], [ f7, f2*f1 ], [ f7, f2*f7 ], [ f7, f7*f1 ], [ f7, f7*f2 ], [ f1*f2, f1*f7 ], 
  [ f1*f2, f2*f1 ], [ f1*f2, f2*f7 ], [ f1*f2, f7*f1 ], [ f1*f2, f7*f2 ], [ f1*f7, f2*f1 ], [ f1*f7, f2*f7 ], [ f1*f7, f7*f1 ], [ f1*f7, f7*f2 ], [ f2*f1, f2*f7 ], 
  [ f2*f1, f7*f1 ], [ f2*f1, f7*f2 ], [ f2*f7, f7*f1 ], [ f2*f7, f7*f2 ], [ f7*f1, f7*f2 ] ]

gap> First( last,x-> TryCosetTableInWholeGroup( Subgroup(H,x): silent) <> fail and Index(H, Subgroup(H, x)) = 1 );
[ f1, f2*f7 ]

So, I draw the conclusion that this group is 2-generated.