Constructing minimal supplements with GAP
$begingroup$
The problem is this:
Suppose we are given a finite group $G$ and a normal subgroup $N$ of $G$ which is not contained in $Phi(G)$. Call a subgroup $H$ of $G$ a minimal supplement for $N$ (in $G$) if $G=NH$ and $G>NM$ for every proper subgroup $M$ of $H$. Given, $G$, $N$, what is an efficient way of constructing a minimal supplement for $N$ in $G$ with GAP?
I'd appreciate any ideas.
group-theory finite-groups gap computer-algebra-systems
$endgroup$
add a comment |
$begingroup$
The problem is this:
Suppose we are given a finite group $G$ and a normal subgroup $N$ of $G$ which is not contained in $Phi(G)$. Call a subgroup $H$ of $G$ a minimal supplement for $N$ (in $G$) if $G=NH$ and $G>NM$ for every proper subgroup $M$ of $H$. Given, $G$, $N$, what is an efficient way of constructing a minimal supplement for $N$ in $G$ with GAP?
I'd appreciate any ideas.
group-theory finite-groups gap computer-algebra-systems
$endgroup$
add a comment |
$begingroup$
The problem is this:
Suppose we are given a finite group $G$ and a normal subgroup $N$ of $G$ which is not contained in $Phi(G)$. Call a subgroup $H$ of $G$ a minimal supplement for $N$ (in $G$) if $G=NH$ and $G>NM$ for every proper subgroup $M$ of $H$. Given, $G$, $N$, what is an efficient way of constructing a minimal supplement for $N$ in $G$ with GAP?
I'd appreciate any ideas.
group-theory finite-groups gap computer-algebra-systems
$endgroup$
The problem is this:
Suppose we are given a finite group $G$ and a normal subgroup $N$ of $G$ which is not contained in $Phi(G)$. Call a subgroup $H$ of $G$ a minimal supplement for $N$ (in $G$) if $G=NH$ and $G>NM$ for every proper subgroup $M$ of $H$. Given, $G$, $N$, what is an efficient way of constructing a minimal supplement for $N$ in $G$ with GAP?
I'd appreciate any ideas.
group-theory finite-groups gap computer-algebra-systems
group-theory finite-groups gap computer-algebra-systems
asked Jan 7 at 5:33
the_foxthe_fox
2,58711533
2,58711533
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
This is a difficult problem in general.
One method that should work for moderately sized groups is to start by finding representatives of the conjugacy classes of maximal subgroups of $G$ using the function $mathtt{ConjugacyClassesMaximalSubgroups}$. Then create a list $mathtt{L}$ say of those maximal subgroup representatives that do not contain $N$. Since you are assuming that $N notle Phi(G)$, the list $mathtt{L}$ will be nonempty.
Now repeat the following process. Find representatives of the conjugacy classes of maximal subgroups of $mathtt{L[1]}$, and make a list $mathtt{LL}$ of those groups in $mathtt{L}$ that supplement $N$. If $mathtt{LL}$ is nonempty then replace $mathtt{L}$ by $mathtt{LL}$ and repeat. When $mathtt{LL}$ is empty, you know that the current $mathtt{L[1]}$ is a minimal supplement.
This should find you a minimal supplement moderately quickly. If you wanted all minimal supplements (up to conjugacy), then it would be more difficult, because you would have to do these calculations for every group in each list $mathtt{L}$.
If $N$ happened to be abelian, then all supplements would intersect $N$ in a normal subgroup of $G$, so another approach might be to find the normal subgroups $M$ of $G$ that are properly contained in $N$, and find complements of $N/M$ in $G/M$, using the function $mathtt{ComplementClassesRepresentatives}$.
Here is some GAP code for the procedure above.
MinimalSupplement := function(G,N)
local max, supp, oldsupp, gN;
max := MaximalSubgroupClassReps(G);
supp := Filtered(max, x -> not IsSubset(x,N));
if Length(supp) = 0 then
Error("Normal subgroup lies in Frattini subgroup");
fi;
gN := GeneratorsOfGroup(N);
while Length(supp) > 0 do
oldsupp := supp;
supp := MaximalSubgroupClassReps(oldsupp[1]);
supp := Filtered(supp, x ->
G = Subgroup(G, Concatenation(GeneratorsOfGroup(x),gN)) );
od;
return oldsupp[1];
end;
$endgroup$
$begingroup$
I wonder if we can do any better than that. For example, if $|N|$ is relatively small, then your suggestion is perhaps the only way to go. (But maybe one could check first if $N$ has a complement in $G$.) What if it is, instead, relatively large? Can we work from the bottom up?
$endgroup$
– the_fox
Jan 8 at 9:51
$begingroup$
(I will wait a bit before accepting since I was actually hoping for some GAP code.)
$endgroup$
– the_fox
Jan 8 at 9:51
$begingroup$
This already has a detailed description of the process. What the first point where you stop while trying to put this into the GAP code?
$endgroup$
– Alexander Konovalov
Jan 8 at 10:42
1
$begingroup$
OK, on this occasion, since I had more or less done this already, I will post some GAP code for the procedure I described. I am not really a GAP expert, so it is possible that it could be improved. I agree that it would be a good idea to check for the existence of complements first, but as far as I know that is only possible when $N$ is solvable. I agree with Alexander that is not in general reasonable to ask people to write GAP code for you.
$endgroup$
– Derek Holt
Jan 8 at 13:18
$begingroup$
I think "MaximalSubgroupClassReps" will shorten the code a bit.
$endgroup$
– the_fox
Jan 8 at 13:28
|
show 1 more comment
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3064687%2fconstructing-minimal-supplements-with-gap%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
This is a difficult problem in general.
One method that should work for moderately sized groups is to start by finding representatives of the conjugacy classes of maximal subgroups of $G$ using the function $mathtt{ConjugacyClassesMaximalSubgroups}$. Then create a list $mathtt{L}$ say of those maximal subgroup representatives that do not contain $N$. Since you are assuming that $N notle Phi(G)$, the list $mathtt{L}$ will be nonempty.
Now repeat the following process. Find representatives of the conjugacy classes of maximal subgroups of $mathtt{L[1]}$, and make a list $mathtt{LL}$ of those groups in $mathtt{L}$ that supplement $N$. If $mathtt{LL}$ is nonempty then replace $mathtt{L}$ by $mathtt{LL}$ and repeat. When $mathtt{LL}$ is empty, you know that the current $mathtt{L[1]}$ is a minimal supplement.
This should find you a minimal supplement moderately quickly. If you wanted all minimal supplements (up to conjugacy), then it would be more difficult, because you would have to do these calculations for every group in each list $mathtt{L}$.
If $N$ happened to be abelian, then all supplements would intersect $N$ in a normal subgroup of $G$, so another approach might be to find the normal subgroups $M$ of $G$ that are properly contained in $N$, and find complements of $N/M$ in $G/M$, using the function $mathtt{ComplementClassesRepresentatives}$.
Here is some GAP code for the procedure above.
MinimalSupplement := function(G,N)
local max, supp, oldsupp, gN;
max := MaximalSubgroupClassReps(G);
supp := Filtered(max, x -> not IsSubset(x,N));
if Length(supp) = 0 then
Error("Normal subgroup lies in Frattini subgroup");
fi;
gN := GeneratorsOfGroup(N);
while Length(supp) > 0 do
oldsupp := supp;
supp := MaximalSubgroupClassReps(oldsupp[1]);
supp := Filtered(supp, x ->
G = Subgroup(G, Concatenation(GeneratorsOfGroup(x),gN)) );
od;
return oldsupp[1];
end;
$endgroup$
$begingroup$
I wonder if we can do any better than that. For example, if $|N|$ is relatively small, then your suggestion is perhaps the only way to go. (But maybe one could check first if $N$ has a complement in $G$.) What if it is, instead, relatively large? Can we work from the bottom up?
$endgroup$
– the_fox
Jan 8 at 9:51
$begingroup$
(I will wait a bit before accepting since I was actually hoping for some GAP code.)
$endgroup$
– the_fox
Jan 8 at 9:51
$begingroup$
This already has a detailed description of the process. What the first point where you stop while trying to put this into the GAP code?
$endgroup$
– Alexander Konovalov
Jan 8 at 10:42
1
$begingroup$
OK, on this occasion, since I had more or less done this already, I will post some GAP code for the procedure I described. I am not really a GAP expert, so it is possible that it could be improved. I agree that it would be a good idea to check for the existence of complements first, but as far as I know that is only possible when $N$ is solvable. I agree with Alexander that is not in general reasonable to ask people to write GAP code for you.
$endgroup$
– Derek Holt
Jan 8 at 13:18
$begingroup$
I think "MaximalSubgroupClassReps" will shorten the code a bit.
$endgroup$
– the_fox
Jan 8 at 13:28
|
show 1 more comment
$begingroup$
This is a difficult problem in general.
One method that should work for moderately sized groups is to start by finding representatives of the conjugacy classes of maximal subgroups of $G$ using the function $mathtt{ConjugacyClassesMaximalSubgroups}$. Then create a list $mathtt{L}$ say of those maximal subgroup representatives that do not contain $N$. Since you are assuming that $N notle Phi(G)$, the list $mathtt{L}$ will be nonempty.
Now repeat the following process. Find representatives of the conjugacy classes of maximal subgroups of $mathtt{L[1]}$, and make a list $mathtt{LL}$ of those groups in $mathtt{L}$ that supplement $N$. If $mathtt{LL}$ is nonempty then replace $mathtt{L}$ by $mathtt{LL}$ and repeat. When $mathtt{LL}$ is empty, you know that the current $mathtt{L[1]}$ is a minimal supplement.
This should find you a minimal supplement moderately quickly. If you wanted all minimal supplements (up to conjugacy), then it would be more difficult, because you would have to do these calculations for every group in each list $mathtt{L}$.
If $N$ happened to be abelian, then all supplements would intersect $N$ in a normal subgroup of $G$, so another approach might be to find the normal subgroups $M$ of $G$ that are properly contained in $N$, and find complements of $N/M$ in $G/M$, using the function $mathtt{ComplementClassesRepresentatives}$.
Here is some GAP code for the procedure above.
MinimalSupplement := function(G,N)
local max, supp, oldsupp, gN;
max := MaximalSubgroupClassReps(G);
supp := Filtered(max, x -> not IsSubset(x,N));
if Length(supp) = 0 then
Error("Normal subgroup lies in Frattini subgroup");
fi;
gN := GeneratorsOfGroup(N);
while Length(supp) > 0 do
oldsupp := supp;
supp := MaximalSubgroupClassReps(oldsupp[1]);
supp := Filtered(supp, x ->
G = Subgroup(G, Concatenation(GeneratorsOfGroup(x),gN)) );
od;
return oldsupp[1];
end;
$endgroup$
$begingroup$
I wonder if we can do any better than that. For example, if $|N|$ is relatively small, then your suggestion is perhaps the only way to go. (But maybe one could check first if $N$ has a complement in $G$.) What if it is, instead, relatively large? Can we work from the bottom up?
$endgroup$
– the_fox
Jan 8 at 9:51
$begingroup$
(I will wait a bit before accepting since I was actually hoping for some GAP code.)
$endgroup$
– the_fox
Jan 8 at 9:51
$begingroup$
This already has a detailed description of the process. What the first point where you stop while trying to put this into the GAP code?
$endgroup$
– Alexander Konovalov
Jan 8 at 10:42
1
$begingroup$
OK, on this occasion, since I had more or less done this already, I will post some GAP code for the procedure I described. I am not really a GAP expert, so it is possible that it could be improved. I agree that it would be a good idea to check for the existence of complements first, but as far as I know that is only possible when $N$ is solvable. I agree with Alexander that is not in general reasonable to ask people to write GAP code for you.
$endgroup$
– Derek Holt
Jan 8 at 13:18
$begingroup$
I think "MaximalSubgroupClassReps" will shorten the code a bit.
$endgroup$
– the_fox
Jan 8 at 13:28
|
show 1 more comment
$begingroup$
This is a difficult problem in general.
One method that should work for moderately sized groups is to start by finding representatives of the conjugacy classes of maximal subgroups of $G$ using the function $mathtt{ConjugacyClassesMaximalSubgroups}$. Then create a list $mathtt{L}$ say of those maximal subgroup representatives that do not contain $N$. Since you are assuming that $N notle Phi(G)$, the list $mathtt{L}$ will be nonempty.
Now repeat the following process. Find representatives of the conjugacy classes of maximal subgroups of $mathtt{L[1]}$, and make a list $mathtt{LL}$ of those groups in $mathtt{L}$ that supplement $N$. If $mathtt{LL}$ is nonempty then replace $mathtt{L}$ by $mathtt{LL}$ and repeat. When $mathtt{LL}$ is empty, you know that the current $mathtt{L[1]}$ is a minimal supplement.
This should find you a minimal supplement moderately quickly. If you wanted all minimal supplements (up to conjugacy), then it would be more difficult, because you would have to do these calculations for every group in each list $mathtt{L}$.
If $N$ happened to be abelian, then all supplements would intersect $N$ in a normal subgroup of $G$, so another approach might be to find the normal subgroups $M$ of $G$ that are properly contained in $N$, and find complements of $N/M$ in $G/M$, using the function $mathtt{ComplementClassesRepresentatives}$.
Here is some GAP code for the procedure above.
MinimalSupplement := function(G,N)
local max, supp, oldsupp, gN;
max := MaximalSubgroupClassReps(G);
supp := Filtered(max, x -> not IsSubset(x,N));
if Length(supp) = 0 then
Error("Normal subgroup lies in Frattini subgroup");
fi;
gN := GeneratorsOfGroup(N);
while Length(supp) > 0 do
oldsupp := supp;
supp := MaximalSubgroupClassReps(oldsupp[1]);
supp := Filtered(supp, x ->
G = Subgroup(G, Concatenation(GeneratorsOfGroup(x),gN)) );
od;
return oldsupp[1];
end;
$endgroup$
This is a difficult problem in general.
One method that should work for moderately sized groups is to start by finding representatives of the conjugacy classes of maximal subgroups of $G$ using the function $mathtt{ConjugacyClassesMaximalSubgroups}$. Then create a list $mathtt{L}$ say of those maximal subgroup representatives that do not contain $N$. Since you are assuming that $N notle Phi(G)$, the list $mathtt{L}$ will be nonempty.
Now repeat the following process. Find representatives of the conjugacy classes of maximal subgroups of $mathtt{L[1]}$, and make a list $mathtt{LL}$ of those groups in $mathtt{L}$ that supplement $N$. If $mathtt{LL}$ is nonempty then replace $mathtt{L}$ by $mathtt{LL}$ and repeat. When $mathtt{LL}$ is empty, you know that the current $mathtt{L[1]}$ is a minimal supplement.
This should find you a minimal supplement moderately quickly. If you wanted all minimal supplements (up to conjugacy), then it would be more difficult, because you would have to do these calculations for every group in each list $mathtt{L}$.
If $N$ happened to be abelian, then all supplements would intersect $N$ in a normal subgroup of $G$, so another approach might be to find the normal subgroups $M$ of $G$ that are properly contained in $N$, and find complements of $N/M$ in $G/M$, using the function $mathtt{ComplementClassesRepresentatives}$.
Here is some GAP code for the procedure above.
MinimalSupplement := function(G,N)
local max, supp, oldsupp, gN;
max := MaximalSubgroupClassReps(G);
supp := Filtered(max, x -> not IsSubset(x,N));
if Length(supp) = 0 then
Error("Normal subgroup lies in Frattini subgroup");
fi;
gN := GeneratorsOfGroup(N);
while Length(supp) > 0 do
oldsupp := supp;
supp := MaximalSubgroupClassReps(oldsupp[1]);
supp := Filtered(supp, x ->
G = Subgroup(G, Concatenation(GeneratorsOfGroup(x),gN)) );
od;
return oldsupp[1];
end;
edited Jan 8 at 13:32
answered Jan 7 at 15:20
Derek HoltDerek Holt
52.8k53570
52.8k53570
$begingroup$
I wonder if we can do any better than that. For example, if $|N|$ is relatively small, then your suggestion is perhaps the only way to go. (But maybe one could check first if $N$ has a complement in $G$.) What if it is, instead, relatively large? Can we work from the bottom up?
$endgroup$
– the_fox
Jan 8 at 9:51
$begingroup$
(I will wait a bit before accepting since I was actually hoping for some GAP code.)
$endgroup$
– the_fox
Jan 8 at 9:51
$begingroup$
This already has a detailed description of the process. What the first point where you stop while trying to put this into the GAP code?
$endgroup$
– Alexander Konovalov
Jan 8 at 10:42
1
$begingroup$
OK, on this occasion, since I had more or less done this already, I will post some GAP code for the procedure I described. I am not really a GAP expert, so it is possible that it could be improved. I agree that it would be a good idea to check for the existence of complements first, but as far as I know that is only possible when $N$ is solvable. I agree with Alexander that is not in general reasonable to ask people to write GAP code for you.
$endgroup$
– Derek Holt
Jan 8 at 13:18
$begingroup$
I think "MaximalSubgroupClassReps" will shorten the code a bit.
$endgroup$
– the_fox
Jan 8 at 13:28
|
show 1 more comment
$begingroup$
I wonder if we can do any better than that. For example, if $|N|$ is relatively small, then your suggestion is perhaps the only way to go. (But maybe one could check first if $N$ has a complement in $G$.) What if it is, instead, relatively large? Can we work from the bottom up?
$endgroup$
– the_fox
Jan 8 at 9:51
$begingroup$
(I will wait a bit before accepting since I was actually hoping for some GAP code.)
$endgroup$
– the_fox
Jan 8 at 9:51
$begingroup$
This already has a detailed description of the process. What the first point where you stop while trying to put this into the GAP code?
$endgroup$
– Alexander Konovalov
Jan 8 at 10:42
1
$begingroup$
OK, on this occasion, since I had more or less done this already, I will post some GAP code for the procedure I described. I am not really a GAP expert, so it is possible that it could be improved. I agree that it would be a good idea to check for the existence of complements first, but as far as I know that is only possible when $N$ is solvable. I agree with Alexander that is not in general reasonable to ask people to write GAP code for you.
$endgroup$
– Derek Holt
Jan 8 at 13:18
$begingroup$
I think "MaximalSubgroupClassReps" will shorten the code a bit.
$endgroup$
– the_fox
Jan 8 at 13:28
$begingroup$
I wonder if we can do any better than that. For example, if $|N|$ is relatively small, then your suggestion is perhaps the only way to go. (But maybe one could check first if $N$ has a complement in $G$.) What if it is, instead, relatively large? Can we work from the bottom up?
$endgroup$
– the_fox
Jan 8 at 9:51
$begingroup$
I wonder if we can do any better than that. For example, if $|N|$ is relatively small, then your suggestion is perhaps the only way to go. (But maybe one could check first if $N$ has a complement in $G$.) What if it is, instead, relatively large? Can we work from the bottom up?
$endgroup$
– the_fox
Jan 8 at 9:51
$begingroup$
(I will wait a bit before accepting since I was actually hoping for some GAP code.)
$endgroup$
– the_fox
Jan 8 at 9:51
$begingroup$
(I will wait a bit before accepting since I was actually hoping for some GAP code.)
$endgroup$
– the_fox
Jan 8 at 9:51
$begingroup$
This already has a detailed description of the process. What the first point where you stop while trying to put this into the GAP code?
$endgroup$
– Alexander Konovalov
Jan 8 at 10:42
$begingroup$
This already has a detailed description of the process. What the first point where you stop while trying to put this into the GAP code?
$endgroup$
– Alexander Konovalov
Jan 8 at 10:42
1
1
$begingroup$
OK, on this occasion, since I had more or less done this already, I will post some GAP code for the procedure I described. I am not really a GAP expert, so it is possible that it could be improved. I agree that it would be a good idea to check for the existence of complements first, but as far as I know that is only possible when $N$ is solvable. I agree with Alexander that is not in general reasonable to ask people to write GAP code for you.
$endgroup$
– Derek Holt
Jan 8 at 13:18
$begingroup$
OK, on this occasion, since I had more or less done this already, I will post some GAP code for the procedure I described. I am not really a GAP expert, so it is possible that it could be improved. I agree that it would be a good idea to check for the existence of complements first, but as far as I know that is only possible when $N$ is solvable. I agree with Alexander that is not in general reasonable to ask people to write GAP code for you.
$endgroup$
– Derek Holt
Jan 8 at 13:18
$begingroup$
I think "MaximalSubgroupClassReps" will shorten the code a bit.
$endgroup$
– the_fox
Jan 8 at 13:28
$begingroup$
I think "MaximalSubgroupClassReps" will shorten the code a bit.
$endgroup$
– the_fox
Jan 8 at 13:28
|
show 1 more comment
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3064687%2fconstructing-minimal-supplements-with-gap%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown