An equation in finite groups

Question

Let $G$ be a finite group, $A$ a given subset and put and put $A^{-1}=\{ a^{-1}:a\in A\}$. We need a gap code for determining the maximum and minimum of all $|B|$ such that $B$ is a solution of the following equation $$ A^{-1}AB=G \; , \; |AB|=|A||B| $$

Note that the equation implies $\frac{|G|}{|A|^2-|A|+1}\leq |B|\leq\frac{|G|}{|A|}$ (for $|A|>1$), so the maximum and minimum are between the two numbers.

More information: I'm doing a research project, and I show that for every nonempty subset $A$ of $G$, its related subset $B$ mentioned in A GAP code for maximum and minimum cardinals of some classes of subsets of a finite group , satisfies the equation $(A^{-1}A)X=G$ (and $X=B$ is a minimal solution of the equation). Now I need to check some of its properties in some groups such as $S_n$ and $\mathbb{Z}_n$.

Thanks in advance!

Answer 1

minmax:=function(G,A)
     local B,AA,BA,BAA,size,minsize,maxsize;
       minsize:=Order(G);
        maxsize:=0;
          AA:=Unique(List(Cartesian(A,A),x->x[1]*x[2]^(-1)));
 for size in [Maximum(Int(Order(G)/(Number(AA)^2-Number(A)+1)),1)..Int(Order(G)/Number(A))] do
       for B in Combinations(List(G),size) do
          BA:=Unique(List(Cartesian(B,A),x->x[1]*x[2]));
             BAA:=Unique(List(Cartesian(B,AA),x->x[1]*x[2]));
             if Number(BA)=Number(B)*Number(A) and Number(BAA)=Order(G) then
             minsize:=Minimum(minsize,Number(B));
            maxsize:=Maximum(maxsize,Number(B));
         fi;
      od;
   od;
 return [minsize,maxsize];
  end;

Answer 2

Your own answer, @M.H., is a good attempt! The code is formatted (with minor inconsistencies), GAP reads the code with no errors, and the code is readable and seems to do what it is supposed to do (though it checks $BAA^{-1}$ and $|BA|$ instead of $A^{-1}AB$ and $|AA|$ as in the original question).

I have some performance optimisations which I will explain below. First, with the current version I have constructed and example which took over 50 seconds to calculate:

gap> G:=SymmetricGroup(4);
Sym( [ 1 .. 4 ] )
gap> A:=[ (3,4), (2,4), (1,2) ];
[ (3,4), (2,4), (1,2) ]
gap> minmax(G,A);time;
[ 4, 6 ]
51899

My version of the code is below. I've formatted it as I normally do (there is not strict rule how exactly to do it in your own code, but it is strongly recommended to indent it consistently). Note the use of IteratorOfCombinations to avoid forming a potentially huge set of all combinations, and replacing Unique by Set. The latter is particularly relevant: typing ?Unique in GAP, you will read that Set is more efficient in this case (always good to read documentation for each function that you'e trying to use!).

minmax1:=function(G,A)
local B,AA,BA,BAA,size,minsize,maxsize;
minsize:=Size(G);
maxsize:=0;
AA:=Set(List(Cartesian(A,A),x->x[1]*x[2]^(-1)));
for size in [Maximum(Int(Size(G)/(Size(AA)^2-Size(A)+1)),1)..Int(Size(G)/Size(A))] do
  for B in IteratorOfCombinations(AsList(G),size) do
    BA:=Set(List(Cartesian(B,A),x->x[1]*x[2]));
    BAA:=Set(List(Cartesian(B,AA),x->x[1]*x[2]));
    if Size(BAA)=Size(G) and Size(BA)=Size(B)*Size(A) then
      minsize:=Minimum(minsize,Size(B));
      maxsize:=Maximum(maxsize,Size(B));
    fi;
  od;
od;
return [minsize,maxsize];
end;

This speeds up the calculation a bit: in a new copy of G (to avoid reusing stored attributes) it takes 40 seconds

gap> G:=SymmetricGroup(4);
Sym( [ 1 .. 4 ] )
gap> A:=[ (3,4), (2,4), (1,2) ];
[ (3,4), (2,4), (1,2) ]
gap> minmax1(G,A);time;
[ 4, 6 ]
40200

Now observe that if the condition Size(BA)=Size(B)*Size(A) does not hold, there is no point in calculation of BAA. So one could calculate BA first, check its order and calculate BAA only after that:

minmax2:=function(G,A)
local B,AA,BA,BAA,size,minsize,maxsize;
minsize:=Size(G);
maxsize:=0;
AA:=Set(List(Cartesian(A,A),x->x[1]*x[2]^(-1)));
for size in [Maximum(Int(Size(G)/(Size(AA)^2-Size(A)+1)),1)..Int(Size(G)/Size(A))] do
  for B in IteratorOfCombinations(AsList(G),size) do
    BA:=Set(List(Cartesian(B,A),x->x[1]*x[2]));
    if Size(BA)=Size(B)*Size(A) then
      BAA:=Set(List(Cartesian(B,AA),x->x[1]*x[2]));
      if Size(BAA)=Size(G) then
        minsize:=Minimum(minsize,Size(B));
        maxsize:=Maximum(maxsize,Size(B));
      fi;  
    fi;
  od;
od;
return [minsize,maxsize];
end;

This results in a version that takes 15 seconds - more than three times faster than the initial one:

gap> G:=SymmetricGroup(4);
Sym( [ 1 .. 4 ] )
gap> A:=[ (3,4), (2,4), (1,2) ];
[ (3,4), (2,4), (1,2) ]
gap> minmax2(G,A);time;
[ 4, 6 ]
15257

For larger instances of the problem, one could try to use IteratorOfCartesianProduct in case Cartesian will run out of memory. But still the major bottleneck will be in iterating over combinations. You can use NrCombinations to estimate the number of iterations, and that grows very quickly. One could at least try to think what happens if A is a subset of B or vice versa and exclude some subsets from extra checks. But anyhow the current code seems to be a suitable place to start, it produces answers for small instances, and you can now follow the path outlined in my answer here and try to deal with larger cases.

Answer 3

Thanks again. Now, I write a code to check the above program for all subsets of SymmetricGroup(4) , with limited orders. But it does not work. What is the problem? G:=

SymmetricGroup(4);
local B,AA,AB,AAB,asize,bsize,minsize,maxsize;
for asize in [2..Int((Size(G)/2)-1)] do
for A in IteratorOfCombinations(AsList(G),asize) do
minsize:=Size(G);
 maxsize:=0;
 AA:=Set(List(Cartesian(A,A), x->x[1]^(-1)*x[2]));
 for bsize in [Maximum(Int(Size(G)/(Size(AA)),1)..Int(Size(G)/Size(A))] do
  for B in IteratorOfCombinations(AsList(G),bsize) do
     AB:=Set(List(Cartesian(A,B),x->x[1]*x[2]));
   AAB:=Set(List(Cartesian(AA,B),x->x[1]*x[2]));
if Size(AAB)=Size(G) and Size(AB)=Size(A)*Size(B) then
  minsize:=Minimum(minsize,Size(B));
  maxsize:=Maximum(maxsize,Size(B));
fi;
 od;
od;
 if minsize < maxsize then Print( A, " ",  minsize, " ", maxsize, "\n" );
fi;
od;
od;
   end;