Knowing that the group is Abelian messes up Sylow and Hall subgroup computation?

[hungaborhorvath]

This is a bug in the master branch.
I have observed this by PR #706, and I cannot debug it. It is likely that it have been introduced by my PR #535.

Without knowing that the group is abelian everything works fine:

gap> F := FreeGroup("x", "y");; x := F.1;; y := F.2;;
gap> G := F/[x*y*x^(-1)*y^(-1), x^30, (x*y)^70];;
gap> IdGroup(SylowSubgroup(G, 2));
[ 4, 2 ]
gap> IdGroup(HallSubgroup(G, [2,3]));
[ 12, 5 ]
gap> 

But if the group knows at a certain point that it is Abelian, things become messed up:

gap> F := FreeGroup("x", "y");; x := F.1;; y := F.2;;
gap> G := F/[x*y*x^(-1)*y^(-1), x^30, (x*y)^70];;
gap> IdGroup(SylowSubgroup(G,2));
[ 4, 2 ]
gap> IsAbelian(G);
true
gap> IdGroup(HallSubgroup(G,[2,3]));
[ 4, 2 ]

Note, that if I only call HallSubgroup, then everything is fine.

gap> F := FreeGroup("x", "y");; x := F.1;; y := F.2;;
gap> G := F/[x*y*x^(-1)*y^(-1), x^30, (x*y)^70];;
gap> IdGroup(HallSubgroup(G, [2,3]));
[ 12, 5 ]

Further, if IsAbelian is called before SylowSubgroup, then everything is fine.

gap> F := FreeGroup("x", "y");; x := F.1;; y := F.2;;
gap> G := F/[x*y*x^(-1)*y^(-1), x^30, (x*y)^70];;
gap> IsAbelian(G);
true
gap> IdGroup(SylowSubgroup(G, 2));
[ 4, 2 ]
gap> IdGroup(HallSubgroup(G, [2,3]));
[ 12, 5 ]

The main difference is in method selection for HallSubgroup. If the group knows itself to be abelian, then the nilpotent method is called in grp.gi:2927. I have checked (by putting Print(IdGroup(S)); commands into this method everywhere) that this call computes everything properly up until the return S moment, but apparently somehow returns the 2-sylow subgroup and not S. Further, I have no idea why it counts whether first one computes SylowSubgroup or not, and I have no idea why everything works again if IsAbelian is checked at the beginning. Could it be that the pcgs method conflicts with the nilpotent method?

[hulpke]

In line 2935 of grp.gi you always assign (a pointer to) the same list smallpi. Replace it with

      SetHallSubgroup(G, ShallowCopy(smallpi), S);

and everything works fine.

[hungaborhorvath]

@hulpke Great, thanks! I honestly do not entirely understand the programming difference here (even though I checked out ShallowCopy earlier), but it indeed works. Would it mean that I should do this everywhere else where I may have done something similar?

I will include this in a separate PR.

[ChrisJefferson]

The thing to remember is that GAP doesn't copy lists when you assign them, it is still the "same list". For example:

gap> l := [];
[  ]
gap> x := l;
[  ]
gap> Add(l, 2);
gap> l;
[ 2 ]
gap> x;
[ 2 ]
gap>

[hungaborhorvath]

@ChrisJefferson Thank you. I think I might understand now what happened.

SetHallSubgroup(G, smallpi, S); sets the Hall subgroup for the list smallpi, and not for its value. Is this the intended behaviour? That is, should ShallowCopy be used here rather than in oper1.g:858? Is this even what really happened?

There is something I still do not understand. The nilpotent method for HallSubgroup should return S, and not the value from the list ComputedHallSubgroups. Or because I put it there first, it will return the particular element from the list?

[ChrisJefferson]

@hungaborhorvath : Yes, this is the intended behaviour. The reason we don't put the ShallowCopy in oper1.g is because, in every case I've ever seen previously, there hasn't been a need for a ShallowCopy, as code builds a list to use in a Set operation, sets, and then never touches the list again (it looks to me like there are 2 places in the standard library where a ShallowCopy has to be made, although I didn't carefully check all cases).

If we always ShallowCopied, it would be (slightly) safer, but much more expensive.

[hungaborhorvath]

@ChrisJefferson Ok, thanks.

[bh11]

@ChrisJefferson I tend to think that this should rather be fixed in oper1.g – the risk of accidentally changing a key and resulting in wrong results seems relatively high to me. However, I'd use Immutable instead of ShallowCopy – which also avoids most of the overhead if the key is already immutable, including the most frequent case when the key is a prime.

Probably, it would make sense to use Immutable also for the attribute value. (Do we need mutable key dependent attributes?)

[hungaborhorvath]

Ok, it seems that there are different preferences, so I reopen this.

[ChrisJefferson]

I've never done enough with KeyDependantOperation. With DeclareAttribute, you choose if the attribute should be mutable or not.

I have no idea if there are any users of KeyDependantOperation which are relying on mutable values. We could add mutability as a choice.