A Gap code for the alternating group $A_4$

Question

I need a GAP code for checking the following question:

Is it true that for every subset $A$ of the alternating group $A_4$ with $4$ elements there exists a subset $B$ of order $3$ such that $A_4=AB$?

Any advice?

Thanks in advance

Answer 1

Actually, one can assume that both sets $A$ and $B$ contain the identity element. Anyway, there are easy examples showing that some sets $A$ fail to give $G=AB$ for a set $B$ of size $3$. For instance, choose $A=\{(), (1,2)(3,4), (1,4,3), (2,3,4)\}$. Then $A^{-1}A$ has size $11$. On the other hand, $BB^{-1}$ has size at least $3$. But $G=AB$ with $|G|=|A||B|$ implies that $A^{-1}A$ and $BB^{-1}$ have only the identity element in common, a contradiction.

Answer 2

This is the brute-force calculation that answers the question affirmatively taking less than in a second:

gap> G:=AlternatingGroup(4);
Alt( [ 1 .. 4 ] )
gap> ForAll( Combinations(AsList(G),4), 
>            a -> ForAny( Combinations(AsList(G),3), 
>                         b -> Subgroup(G,Union(a,b))=G) );
true

But of course this is suitable only for toy examples. One could use NrCombinations to check how many cases it needs to enumerate, and e.g. for $A_5$ we have:

gap> NrCombinations([1..60],3);
34220
gap> NrCombinations([1..60],4);
487635

If the answer would be affirmative, then checking this as above would require all $34220 \times 487635 = 16686869700$ iterations.

Edit

Thanks to Peter Mueller for pointing out that I have wrongly interpreted $AB$ as $\langle A \cup B\rangle$. If $AB$ denotes $\{ ab \mid a \in A, b \in B\}$, then in GAP one can proceed as follows:

1) create an auxiliary function to calculate the set of pairwise products of elements of two sets:

gap> f:=function(a,b)
> return Set(List(Cartesian(a,b),Product));
> end;
function( a, b ) ... end

For example,

gap> f([1,2],[3,4]);
[ 3, 4, 6, 8 ]

2) if we want just to modify a little bit the code from above, we could do the following

gap> ForAll( Combinations( AsList(G),4),
>            a -> ForAny( Combinations(AsList(G),3),
>                         b -> IsEqualSet( AsList(G),f(a,b) ) ) );
false

(note IsEqualSet to compare lists as sets, not depending on how they are ordered).

Indeed, the definition of $AB$ matters - now the answer is negative. Let's just find one of the subsets which gives us a counterexample:

gap> x:=First( Combinations( AsList(G),4),
>            a -> ForAll( Combinations(AsList(G),3),
>                         b -> not IsEqualSet( AsList(G),f(a,b) ) ) );
[ (), (2,3,4), (1,2)(3,4), (1,2,3) ]

In this case, $A^{-1}A$ is of order $10$:

gap> xinv:=List(x,t->t^-1);
[ (), (2,4,3), (1,2)(3,4), (1,3,2) ]
gap> f(xinv,x);
[ (), (2,3,4), (2,4,3), (1,2)(3,4), (1,2,3), (1,2,4), (1,3,2), (1,3,4), 

(1,4,2), (1,4,3) ] gap> Length(last); 10

One could find 216 quadruples $A$ for which there are no triples $B$ such that $G=AB$, and I've checked the one from Peter Mueller's answer will be also among them. The order of $A^{-1}A$ for these quadruples is either 10 or 11.

That's of course still is a GAP code for exploring small examples interactively. For larger examples, I suggest to look at the approach here.