About subsets of finite groups with $A^{-1}A=G$ or $AA^{-1}=G$?

Question

Regarding to the problems Does $A^{-1}A=G$ imply that $AA^{-1}=G$? and Is it true that if $|A|>\frac{|G|}{2}$ then $A^{-1}A=AA^{-1}=G$?, we are looking for some subsets $A$ of $G$ with $\lfloor \frac{|G|}{2}\rfloor-2 \leq |A|\leq \lfloor \frac{|G|}{2}\rfloor$ such that $A^{-1}A=G$ and $AA^{-1}\neq G$ or $AA^{-1}=G$ and $A^{-1}A\neq G$.

Do such $G$ (non-abelian) and $A$ exist?

We propose the following GAP code:

test:=function(G)
local A,AA1,1AA, size;
for size in [Int(Order(G)/2)-2.. Int(Order(G)/2)] do
  for A in Combinations(List(G), size) do
    1AA:=Unique(List(Cartesian(A,A),x->x[1]^(-1)*x[2]));
    AA1:=Unique(List(Cartesian(A,A),x->x[1]*x[2]^(-1)));
    if (1AA=G and Number(AA1)<Number(G)) or 
       (AA1=G and Number(1AA)<Number(G)) then 
      Print( A, " ",  1AA, " ", AA1, "\n" );
    fi;
  od;
od;
end;

Now,

(1) Is it okay (any comment)?

(2) How can we include the command "fail" in case nothing $A$?

(3) How can we run the code for all non-abelian groups of orders between the two numbers $n_1$ and $n_2$?

Answer 1

If this code is correct, one should also be able to find the example from this question setting size to $9$. However, for $G=S_4$ the calculation completes after several minutes and reports nothing. Therefore, the answer to (1) seems to be "No" :(. Here is the outline what I recommend to do next.

The first step should be to make it correct. I suggest to add the 2nd argument to the test function to specify the order of the subset A to search. In this case, for example, considering all 9-element subsets of $S_4$ you should be able to find the example mentioned above. You need to debug and fix the code so you have the version which works correctly before starting to improve it.

Here is my guess (but I may be wrong!):

I think the problem is that in 1AA=G (and in the other check) lists are compared as ordered lists, so even when they coincide as sets, the check returns false. Try to use IsEqualSet (see ?IsEqualSet) for a quick fix before refactoring the code at a later stage.

The next step would be to create so called regression tests. Using them, you will be able to rerun previously performed calculations to check that new changes do not impact their correctness or worsen their performance. This is explained in more details in Using regression tests from the GAP Software Carpentry lesson. I suggest to establish a collection of tests, covering examples when it should find something (as in $S_4$ above), examples where it finds nothing, and examples which you can check by hands. Do not ignore trivial examples: for example, you may test abelian groups to check that the code does not report false positives.

So, now you would have inefficient code, but at least it is expected to be correct. Remember "make it right, then make it fast" rule! It's the right time now to make if fast to be able to analyse groups of as large order as possible.

There are several obvious bottlenecks in the implementation from the question. Suggestions include:

• using iterators of combinations and cartesian products instead of generating full lists of them
• doing only one pass over the cartesian product instead of two
• stopping calculation of the list as soon as it contains all elements of the group
• etc.

but I suggest that I will write them in more detail later when you will fix the initial implementation. Also, these are only suggestions for a more efficient implementation of the very straightforward check of the condition in question. It could be that theoretical insights (for example, proving that some subsets could be excluded from checks) will give much better advantage that a mere code optimisation.

When you will at least some correct version of the code to test one group and one possible order of the subset, you can look at (2). Create another function which tests one group for all possible orders of the subset A, calling test(G,n) for each n from [Int(Order(G)/2)-2.. Int(Order(G)/2)]. To fit together well, now we see that test should not only print what it is doing, but should also return something for the calling function to analyse. For example, it may return fail or false if no examples were found, and return true or maybe A if they are - the choice may depend on the further needs. Dependently on this output, the calling function may decide whether to stop or to check the next possible n.

Now you should be ready to do (3) and check small groups systematically. See Small groups search from the GAP Software Carpentry lesson explaining how to do this. You may be lucky and find an example you're looking for even with the straightforward implementation!