4
$\begingroup$

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
        AddSet(M, a*b);
    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
    Add(A,Identity(G));
    D:=Difference( C, AsSet(A) );
    for B in IteratorOfCombinations(D,szG/d-1) do
        Add(B,Identity(G));
       #             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)$)

and also A GAP code for a class of small groups

Thanks in advance.

$\endgroup$

1 Answer 1

6
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Mar 11, 2020 at 5:28
  • $\begingroup$ 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\}$. $\endgroup$ Mar 11, 2020 at 8:43
  • $\begingroup$ 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. $\endgroup$
    – ahulpke
    Mar 11, 2020 at 14:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .