# Gap code for a certain property of subgroups

Let $$G$$ be a given finite group of order $$n$$. We would like to write a Gap code for:

Step1. find all divisors $$d$$ of $$n$$ such that there is no any subgroup of order $$d$$ or $$n/d$$,

Step2. for every $$d$$ from Step1 (if exists) check whether there exists subsets $$A$$ and $$B$$ of $$G$$ such that $$|A|=d$$, $$|B|=n/d$$ and $$G=AB$$ (where $$AB=\{ab:a\in A, b\in B\}$$).

We wrote the following code, but it takes long time, and we can't apply it for $$G=PSL(2,13)$$ (even for $$AGL(1,16)$$ of order 240):

MulAB:=function(A,B)
local a,b,M;
M:=[];
for a in A do
for b in B do
od;
od;
return M;
end;

IsABOK:=function(A,B,szG)
local a,b,c,M;
M:=[];
for a in A do
for b in B do
c := a*b;
if c in M then return false; else Add(M,c); fi;
od;
od;
return Size(M)=szG;
end;
Stp2:=function(G,d)
local C,A,B, D, szG, M, r;
r:=0;
szG := Size(G);
C:=Difference( Set(AsList(G)), Set([Identity(G)]) );
for A in IteratorOfCombinations(C,d-1) do
D:=Difference( C, AsSet(A) );
for B in IteratorOfCombinations(D,szG/d-1) do
#             M:=MulAB(A,B);
#             if Size(M)=szG then
if IsABOK(A, B, szG) then
Print("\n\n|A|=",d, ",\tA=",A);
Print("\n|B|=",szG/d, ",\tB=",B);
r := r + 1;
fi;
od;
od;
return r;
end;;
Stp1:=function(G)
local n, d, H, h, DList, i;
n := Size(G);
DList := [];
Append( DList, DivisorsInt(n) );
for H in AllSubgroups( G ) do
h := Size(H);
i := Position(DList, h) ;
if  IsInt(i) then Remove(DList, i); fi;
i := Position(DList, n/h) ;
if  IsInt(i) then Remove(DList, i); fi;
od;
#     Print( "\nDList:", DList );
return DList;
end;;
CheckGroup:=function(G)
local A, B, d, DList, num;
num:=0;
DList:=Stp1(G);
for d in DList do
num:=num+Stp2(G,d);
od;
return num;
end;;
IsNotAbelian := function(G)
return not IsAbelian(G);
end;;
Main:=function(minOrder, maxOrder)
local n, R, id, G, num;
R:=[];
for n in [minOrder..maxOrder] do
#         Print("\n\nn=",n, ":");
for id in IdsOfAllSmallGroups(n,IsNotAbelian) do
Print("\n\nId=",id);
G := SmallGroup(id);
Print(",\tG=",StructureDescription(G),":");
num := CheckGroup(G);
if num>0 then Add(R, G); fi;
od;
od;
Print("\n\nR=",R);
Print("\n\nnum=",num);
end;


How can we remove the problem?

Note that it is related to the question: A property for some finite groups (especially ${\rm PSL}(2,13)$)

Since you search through subsets, the combinatorial explosion of the number of subsets (such as: $${240\choose 16}\sim 10^{24}$$, even if each set only took a $$\mu s$$ to test this would take $$10^{10}$$ years) makes this search completely infeasible.
To have any chance of it completing in your lifetime, you need a criterion that will allow you to avoid construction of almost all of the sets. E.g. is there any way that one could show that two elements $$g_1,g_2$$ could never lie both in the same set $$A$$.
• Thanks for your answer. Indeed, we can consider the following conditions: 1. $A\cap B=\{ 1\}$ , 2. $B\subseteq A^{-1}A:=\{a_1^{-1}a_2:a_1,a_2\in A\}$, 3. If we choose subsets $A_0$ and $B_0$, then for the next choices $A\neq xA_0$ and $B\neq B_0y$, for all $x,y\in G$, 4. if the long time problem still persists, then choose random subsets $A$, $n_1$ times, and random subsets $B$, $n_2$ times (for each selection of $A$) , where the numbers $n_1$ and $n_2$ are given at the first. Now, how can we do these conditions in the above Gap code? Thanks again. Mar 11, 2020 at 5:28
• Correction: in the above text: $B\subseteq(G\setminus(A^{-1}A))\cup\{1\}$ where $A^{-1}A:=\{a_1^{-1}a_2:a_1,a_2\in A\}$. Mar 11, 2020 at 8:43
• This would helpt youy in finding $B$ once $A$ is given, but even running through all $A$ is hopeless. You need to find an earlier filter that allows you to construct candidates for $A$ effectively. Mar 11, 2020 at 14:40