11
$\begingroup$

I want to write a GAP program for checking the following question.

Let $G$ be a given finite group with order $n$. Is it true that for every factorization $n=ab$ there exist subsets $A$ and $B$ such that $|A|=a$, $|B|=b$ and $G=AB$?

We have many candidates for a counterexample such as $PSL(2,8)$, $PSL(2,11)$, $PSL(2,13)$, $SL(2,11)$, $SL(2,13)$, $PSL(2,17)$ and $PSL(2,19)$, and need to check them.

About $PSL_2(8)$, if it has a subgroup of index $21$ with the property (in the above question), then we can say that the answer for $PSL_2(8)$ is positive. Can some body check it by GAP?

Any help would be highly appreciated.

Now, can any one write a GAP code for $G=PSL_2(8)$, $a=21$ and $b=24$? (i.e. Are there subsets $A$ and $B$ such that $|A|=21$, $|B|=24$ and $PSL_2(8)=AB$? or equivalently, are there subsets $A$, $B$ of $PSL_2(8)$ such that $|A|=21$, $|B|=24$ and $|A^{-1}A\cap BB^{-1}|=1$?)

Considering the answer from Peter Mueller, we need to try some other cases for getting a counterexample. With do attention to https://math.stackexchange.com/questions/885778/subgroups-of-groups-of-order-36 and https://math.stackexchange.com/questions/882859/groups-of-order-n2-that-have-no-subgroup-of-order-n?lq=1 , I propose the following groups:

Groups of order $n=m^2$ with no subgroup of order $m$ (so $|G|=mm, a=b=m$). As one can see in the second link $n\geq 24^2$ ($m\geq 24$).

Now, is it true for every group $G$ of order $n=24^2$ and $a=b=24$? What about $n=28^2$, $n=30^2$, etc.?

$\endgroup$
  • 2
    $\begingroup$ I notice that $A,B$ are described as "subsets", suggesting that you will not require them to be subgroups of $G$. $\endgroup$ – Chip Eastham Jul 24 '14 at 10:20
  • 4
    $\begingroup$ I think there is more to this exercise than just writing a simple GAP program. For example ${\rm PSL}(2,8)$ has order $504$ and has about $1.86 \times 10^{150}$ subsets of size $252$. $\endgroup$ – Derek Holt Jul 24 '14 at 10:52
  • 3
    $\begingroup$ @hardmath: if you replace "subset" with "subgroup" then the statement is certainly false: consider $Q_8$ for example. $\endgroup$ – Derek Holt Jul 24 '14 at 10:54
  • 2
    $\begingroup$ I think if one of the subsets is a subgroup, even if not a normal subgroup, then you can choose (say) left coset representatives to form the other subset. So that would be an easy case to settle. $\endgroup$ – Chip Eastham Jul 24 '14 at 13:08
  • 5
    $\begingroup$ ${\rm PSL}(2,8)$ has no subgroups of index $21$ and none of index $24$. $\endgroup$ – Derek Holt Jul 24 '14 at 13:09
5
$\begingroup$

There are subsets $A$ and $B$ of orders $21$ and $24$ of $G=PSL(2,8)$ with $G=AB$. A naive search of course does not work. However, in trying to find first $A$ with $A^{-1}A$ being small, a good candidate to work with is $A=G_7G_3$, where $G_3$ and $G_7$ are subgroups of order $3$ and $7$. The smallest possible size of such a set $A^{-1}A$ is $48$. Finding $B$ with $AB=G$ is an exact cover problem: For each $g\in G$ set $S_g=\{ag\;|\;a\in A\}$. Then a set $B$ has the required property if and only if the sets $S_b$, $b\in B$, yield a disjoint union of $G$.

I can't offer a GAP code, rather a quick and naive Sage code which finds such good sets $A$ and $B$:

g = PSL(2,8)
n = g.order()
l = {i:x for i,x in enumerate(g)}
li = {y:x for x,y in l.items()}
g7 = g.sylow_subgroup(7)
s3 = g.subgroup([[z for z in g.conjugacy_classes_representatives()\
                  if z.order() == 3][0]])
n3 = g.normalizer(s3)
tv = [z[0] for z in g.cosets(n3)]
for g3 in [s3.conjugate(z) for z in tv]:
    A = [g(zz)*g(z) for zz in g7 for z in g3]
    AA = set([z1^(-1)*z2 for z1 in A for z2 in A])
    print len(AA)
    if len(AA) > 48:
        continue
    M = matrix(n,n,0)
    for i, x in l.items():
        for j in [li[a*x] for a in A]:
            M[i,j] = 1
    c = sage.combinat.matrices.dlxcpp.OneExactCover(M)
    if c == None:
        continue
    B = [[l[i] for i in range(n) if M[i] == row][0] for row in c]
    AB = set([a*b for a in A for b in B])
    print len(AB) == n # Check if AB = G
    break

One solution we get is $A=G_7G_3$ with $G_7$ and $G_3$ generated by $(3,8,6,4,9,7,5)$ and $(1,3,4)(2,7,8)(5,9,6)$, and $B=\{(), (1,2,4,3,5,6,7,9,8), (2,5,8,3,7,6,4), (1,2,5,7,3,6,8), (2,6,9,4,8,7,5), (1,2,7,8,6,4,5), (2,8)(3,7)(4,9)(5,6), (1,6,5,2,4,8,9,3,7), (1,4,6)(2,5,7)(3,8,9), (1,5,7,4,6,2,3,9,8), (2,7,6,3,4,9,5), (2,4)(3,6)(5,7)(8,9), (1,5)(3,6)(4,9)(7,8), (1,4,8,5,2,3,9,7,6), (2,9,5,7,4,3,8), (1,7)(2,5)(3,8)(4,9), (1,5,8,2,4,6,3,7,9), (2,3)(4,6)(5,9)(7,8), (1,2,6,8,4,7,9), (1,4,5,6,2,9,7,3,8), (1,4,8,6,9,3,5), (1,3,7,8,5,2,6,4,9), (1,2)(3,5)(6,9)(7,8), (1,3,9,8,2,4,7)\}$.

Added: (in view of the modification of the question) The groups of orders $24^2$ and $28^2$ are solvable by Burnside's $p^aq^b$-Theorem. Hence they don't give counterexamples, as pointed out in the answers to this related question by the OP. These answers, by the way, give more promising indications where possible counterexamples may reside. (As to $PSL(2,8)$, the two potential candidates $(a,b)=(21,24)$ and $(a,b)=(12,42)$ are given there. The first doesn't exist by the result from above, and a slight modification of the above code gives $G=AB$ with $|A|=12$, $|B|=42$, so the other one doesn't exist either.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.