Listing elements which satisfy a property

Question

A subgroup $H$ of $G$ is said to be pronormal in $G$ if for each $g \in G$, there exists $x\in \langle H, H^g \rangle$ such that $H^x = H^g$.

A test for pronormality of a subgroup is given by the following GAP code:

IsPronormal := function(G,H)
               return(ForAll(Set(G),g->IsConjugate(Group(Union(H,H^g)),H,H^g)));
               end;;

Now for a non-pronormal subgroup $H$, I want to explicitly find its pronormaliser in the group $G$, that is the set of all $g\in G$ such that $H$ and $H^g$ are conjugate in $\langle H, H^g \rangle$. How do I use GAP to list these elements?

Please clarify what do you want to find? Are you interested, in your notation, in finding $x$ for any fixed $g$? — Olexandr Konovalov, Sep 14 '17 at 16:45
By the way, if you look at the documentation of IsConjugate, it mentions RepresentativeAction - is that the function you're looking for? — Olexandr Konovalov, Sep 14 '17 at 20:33
@AlexanderKonovalov, My apologies for the late reply. I want to find all the elements $g\in G$ such that $H$ and $H^g$ are conjugate in $\langle H, H^g \rangle$ — R Maharaj, Sep 15 '17 at 10:59
But if the subgroup is pronormal, then each $g \in G$ has this property. Am I missing something? — Olexandr Konovalov, Sep 15 '17 at 12:55
@AlexanderKonovalov, Yes precisely if a subgroup $H$ is pronormal in $G$, then each $g \in G$. But I want to find out if for a non-pronormal subgroup, which elements of $g\in G$ satisfy this property. This is called the pronormaliser, which is analogous to the normaliser for normal subgoups. Sorry if this was not clear. — R Maharaj, Sep 16 '17 at 14:02
Thanks - I've updated the answer. I suggest to look which list manipulation tools are available in the GAP manual here - besides ForAll there are Filtered, ForAny, Number, First, etc. — Olexandr Konovalov, Sep 18 '17 at 12:20

Olexandr Konovalov · Answer 1 · 2017-09-18T12:39:47.560

I will start with the code review, examining IsPronormal function given in the question.

The initial version indeed does what's written on the box. It precisely matches the given definition. This is a good starting point following the paradigm "Make it right, then make it fast".

I would only reformat it differently - there is no need to make such redundant indentation, and also return is a keyword and not a function, so there is no need to use in parentheses in return(...):

IsPronormal := function(G,H)
return ForAll( Set(G), g -> IsConjugate( Group( Union(H,H^g) ), H, H^g ) );
end;

(just to make it clear, GAP is not sensitive to indentation, and individual formatting preferences may vary, but it's good to use consistent style - for example, following the style used in the GAP library).

Let's now create some group, for example $S_6$:

gap> S:=SymmetricGroup(6);
Sym( [ 1 .. 6 ] )
gap> Size(S);
720

This is a list of representatives of conjugacy classes of its subgroups:

gap> ccr:=List(ConjugacyClassesSubgroups(S),Representative);;
gap> Length(ccr);
56
gap> ccr[42];
Group([ (4,5), (3,5,6) ])

Now we will check for each subgroup whether it is pronormal in $S_6$. It takes almost a minute:

gap> r:=List(ccr,g -> IsPronormal(S,g));
[ true, false, false, false, false, false, true, true, false, false, false, true, 
  true, true, false, false, false, false, false, false, true, true, true, true, 
  true, true, true, true, true, true, true, false, false, true, true, false, false, 
  true, true, true, true, true, true, true, true, true, true, true, true, true, 
  true, true, true, true, true, true ]
gap> time;
58821

The first improvement is by replacing Set(G) by G. GAP "knows" how to enumerate all elements of this group, so there is no need to create a set of its elements. Not only that it takes some time, but also GAP may run out of memory for large groups, while it can be perfectly capable of enumerating their elements one by one:

IsPronormal := function(G,H)
return ForAll( G, g -> IsConjugate( Group( Union(H,H^g) ), H, H^g ) );
end;

This helps a little bit with performance. Also, the new result matches the old one:

gap> r1:=List(ccr,g -> IsPronormal(S,g));;
gap> time;
53658
gap> r1=r;
true

The next step is to look at Group( Union(H,H^g) ). This generates a new group taking a set-theoretic union of all elements of H and H^g as generators. This list of generators is redundant (indeed, the answer to this question uses generators of groups, not their lists of elements).

IsPronormal := function(G,H)
return ForAll( G, g -> IsConjugate( 
  ClosureGroup( H, GeneratorsOfGroup(H^g) ), H, H^g ) );
end;

Now we are getting same results almost twice faster:

gap> r2:=List(ccr,g -> IsPronormal(S,g));;
gap> time;
34142
gap> r2=r;
true

There is another redundant calculation here: H^g is computed twice. We need to rewrite the function as follows to avoid this:

IsPronormal := function(G,H)
local g, K;
for g in G do
  K:=H^g;
  if not IsConjugate( ClosureGroup( H, GeneratorsOfGroup(K) ), H, K ) then
    return false;
  fi;
od;
return true;
end;

Caching H^g in K helps to bring down the runtime just under half a minute:

gap> r3:=List(ccr,g -> IsPronormal(S,g));;
gap> time;
29717
gap> r3=r;
true

Further steps:

whether we need to check the condition for all elements $g \in G$. For example, one can exclude all central elements $g$ (will not help in the case of the symmetric group, but useful in general case)
obviously, we do not have to check the condition for $g \in H$
can we instead of iterating over all $g \in G$ check only representatives of conjugacy classes of elements of $G$? This seems not to be the case here, but this is useful advice to keep in mind for the future.

Now to compute pronormaliser, one could start with the following prototype (basically, replace ForAll by Filtered in one of the versions of IsPronormal above):

Pronormaliser:=function(G,H)
return Filtered(G,g -> IsConjugate( ClosureGroup( H, GeneratorsOfGroup(H^g) ), H, H^g ) );
end;

For a given $G$ and $H$, it returns a list of all elements $g\in G$ such that $H$ and $H^g$ are conjugate in $\langle H, H^g \rangle$. It may then be improved following the same approach as above.

Remark: I've used some crude approach to testing to check that each new version of the code returns the same result as previous ones. There is a better way to automate testing - please see "Using regression tests" in the Software Carpentry lesson on GAP for further details.

score 1 · Answer 2 · edited Sep 25 '17 at 09:57

Obviously, in a test of pronormality one needs to consider each conjugate of H only once, that is, it is enough to run through a right transversal of the normalizer of H in G:

IsPronormal := function ( G, H )
    local g, K;
    for g in RightTransversal( G, Normalizer( G, H ) ) do
        K := H ^ g;
        if not IsConjugate( ClosureGroup( H, GeneratorsOfGroup( K ) ), H, K )
            then
            return false;
        fi;
    od;
    return true;
end;

Similarly, what is called "pronormaliser" in the original question can be computed as a list of right cosets of the normaliser of H in G:

Pronormaliser := function ( G, H )
    local g, K, N, res;
    N := Normalizer( G, H );
    res := [  ];
    for g in RightTransversal( G, N ) do
        K := H ^ g;
        if IsConjugate( ClosureGroup( H, GeneratorsOfGroup( K ) ), H, K ) then
            Add( res, N * g );
        fi;
    od;
    return res;
end;

Alternatively, return Union(res) but this can be a long list in bigger groups.

But I doubt that the given definition of "pronormaliser" is correct terminology since in general this set is not a subgroup. (A natural definition would be the "largest subgroup of G in which H is pronormal", if such a thing exists.)

Listing elements which satisfy a property

2 Answers2