10
$\begingroup$

Definition. A finite group $G$ is called multifactorizable if for any positive integer numbers $a_1,\dots,a_n$ with $a_1\cdots a_n=|G|$ there are subsets $A_1,\dots,A_n\subset G$ such that $A_1\cdots A_n=G$ and $|A_i|=a_i$ for all $i\le n$.

In this case we shall write that the group $G$ is $a_1{\times}\cdots{\times}a_n$-factorizable.

It can be shown that each finite Abelian group is multifactorizable.

Problem 1. Is each finite (simple) group multifactorizable?

As was observed by Geoff Robinson in his answer to this question, each finite nilpotent group is multifactorizable.

Problem 2. Is each finite solvable group multifactorizable?

Added in Edit. It turns out that the alternating (solvable) group $A_4$ is not multifactorizable, more precisely, $A_4$ is not $2{\times}3{\times}2$-factorizable.

Now it remains to find an example of a finite simple group which is not multifactorizable.

Problem 3. Is the alternating group $A_5$ multifactorizable? In particular, is $A_5$ $2{\times}15{\times}2$-factorizable?


Added in Edit 2. By computer calculations, @Fracois Brunault proved that the alternating group $A_5$ is not multifactorizable. More precisely, the group $A_5$ is not $2{\times}3{\times}5{\times}2$-factorizable.

Added in Edit 3. On the other hand, as was remarked by @Gro-Tsen, it is an open problem (of minimal logarithmic signature) if any finite (simple) group $G$ can be written as the product $G=A_1\cdots A_n$ of subsets $A_i\subset G$ whose cardinality $|A_i|$ is a prime number or 4 such that $|G|=|A_1|\cdots|A_n|$. This problem is resolved for some classes of finite simple groups, see this paper for more information.

$\endgroup$
  • 1
    $\begingroup$ You might find it useful to consider the p-group version of this problem. Gerhard "Perhaps Sylow May Say Something" Paseman, 2018.11.26. $\endgroup$ – Gerhard Paseman Nov 26 '18 at 19:22
  • $\begingroup$ @GerhardPaseman Yes, the case when $a_i$ is a prime (power) also is very interesting and is included in this question. $\endgroup$ – Taras Banakh Nov 26 '18 at 19:35
  • 1
    $\begingroup$ Then this question is relevant: math.stackexchange.com/questions/850812/… $\endgroup$ – Ilya Bogdanov Nov 26 '18 at 20:08
  • $\begingroup$ Note that every group of order less than $12$ is definitely multifactorizable, and that $A_{4}$ is (up to isomorphism) the only group of order $12$ which is not multifactorizable. All groups of order less than $12$ and all groups of order $12$ other than (those isomorphic to) $A_{4}$ have a subgroup of order $d$ for each divisor $d$ of their order, and the argument used for nilpotent groups adapts to that situation. $\endgroup$ – Geoff Robinson Nov 28 '18 at 12:20
  • $\begingroup$ As I wrote in a comment on a related question, you might be interested in googling the keyword "minimal logarithmic signature" for a related problem which has come under some scrutiny in cryptography and on which some progress has been made. $\endgroup$ – Gro-Tsen Nov 28 '18 at 18:42
6
$\begingroup$

I wrote a Magma procedure to test whether $A_5$ is multifactorizable. A brute force search does not seem feasible, so I used the ideas in Taras Banakh's answer and in the comments.

Let $A_5 = ABCD$ with $|A|=2$, $|B|=3$, $|C|=5$, $|D|=2$. We may assume $A,B,C,D$ all contain the identity element. Then $A=\{e,a\}$ and $D=\{e,d\}$ where $a$ and $d$ distinct elements of order 2. Applying an automorphism of $A_5$ and using Taras's argument, we may reduce to the case $a=(1 2)(3 4)$ and $d=(2 3)(4 5)$.

I loop over all possible subsets $B$ of $A_5$ of size 3 containing $e$ such that $\# ABD = 12$ (there are 1248 such subsets). For each such $B$, I compute the list of all subsets of the form $ABcD$ with $c \in A_5$ which are disjoint from $ABD$ and are of size 12 (typically, there are about ten such subsets) and I test whether any of them add up to $A_5$. It turns out that there is no solution, so the group $A_5$ is not multifactorizable.

$\endgroup$
  • $\begingroup$ Thank you for this job! Now the question is resolved completely. But the problem of factorizability remains, nonetheless. Maybe it also has negative solution? $\endgroup$ – Taras Banakh Nov 28 '18 at 12:56
  • $\begingroup$ @TarasBanakh Your result about $A_4$ shows that that $a \times b \times c$-factorization does not hold in general, but I really have no clue about $a \times b$-factorization. $\endgroup$ – François Brunault Nov 28 '18 at 13:12
  • $\begingroup$ Why may we assume that all sets contain the identity element? $\endgroup$ – LSpice Nov 29 '18 at 16:43
  • 2
    $\begingroup$ @LSpice We may replace the first set $A $ by $gA $ to ensure $e \in A $. Then we may replace $AB $ by $gAB=(gAg^{-1})(gB) $ to ensure $e \in B$ also, and so on with the other sets. $\endgroup$ – François Brunault Nov 29 '18 at 18:42
6
$\begingroup$

Further to Gerhard Paseman's comment, it is true that finite $p$-groups are multifactorizable when $p$ is prime (and hence finite nilpotent groups are multifactorizable). Let $G$ be a $p$-group, and let each $a_{i}$ be a power of $p$ with $\prod_{i=1}^{n}a_{i} = |G|$. We show by double induction, first on $|G|$, then on $n,$ that there are subsets $A_{1},A_{2}, \ldots , A_{n}$ such that $A_{1}A_{2} \ldots A_{n} = G$ and that $A_{1}$ may be chosen to be a subgroup of $G$ of order $a_{1}.$

If $n = 1,$ we may take $A_{1} = G,$ so suppose that $n > 1.$ If $n =2,$ take $A_{1}$ to be a subgroup of $G$ of order $a_{1}$ and take $A_{2}$ to be a right transversal to $A_{1}$ in $G.$

Suppose then that $n > 2$ and the result is established for $n-1$ (and for $p$-groups of order less than $|G|)$.

Then $G$ has a subgroup $H$ of order $a_{1}a_{2},$ and there are subsets $A_{3},A_{4}, \ldots, A_{n}$ (with each $A_{i}$ of size $a_{i})$ such that $G = HA_{3} \ldots A_{n}.$

Since $n >2$, we have $a_{1}a_{2} < |G|$ and $|H| < |G|$. By induction ( or the case $n = 2$), $H$ has a subgroup $A_{1}$ of order $a_{1}$ and there is a subset $A_{2}$ of size $a_{2}$ of $H$ such that $A_{1}A_{2} = H.$

Then $G = A_{1} \ldots A_{n}$ with $A_{1}$ a subgroup of $G$ of order $a_{1}$ and each $A_{i}$ subset of $G$ of size $a_{i}$ for $i > 1.$

$\endgroup$
  • 1
    $\begingroup$ In fact, one can find subsets $A_{1},\ldots,A_{n}$ ( each $A_{i}$ of size $a_{i}$) such that each ``partial product" $A_{1}.\ldots A_{i}$ is a subgroup for $1 \leq i \leq n$ by a slight variant of this argument ( for $G$ a finite $p$-group of order $a_{1}\ldots a_{n}$). $\endgroup$ – Geoff Robinson Nov 27 '18 at 23:18
5
$\begingroup$

I've just discovered that the alternating group $A_4$ is not multifactorizable. Namely, it can not be written as the product $A_4=ABC$ of subsets $A,B,C\subset A_4$ of cardinality $|A|=2$, $|B|=3$, and $|C|=2$.

The argument is as follows. To derive a contradiction, assume that $A_4=ABC$ for some subsets $A,B,C\subset A_4$ of cardinality $|A|=2$, $|B|=3$, $|C|=2$. Observe that for any $a\in A$, $b\in B$ and $c\in C$ the equality $ABC=A_4$ implies that $$(b^{-1}a^{-1}Ab)(b^{-1}B)(Cc^{-1})=b^{-1}a^{-1}ABCc^{-1}=A_4,$$ so we can replace the sets $A,B,C$ by the sets $b^{-1}a^{-1}Ab$, $b^{-1}B$, $Cc^{-1}$ and assume that the sets $A,B,C$ contain the neutral element $e$ of $A_4$.

Then $A=\{e,a\}$ and $C=\{e,c\}$ for some $a,c\in A_4$.

We claim that $a^2=e$. Assuming that $a^2\ne e$, we would conclude that $a^3=e$. Since the sets $BC$ and $aBC\ni a$ are disjoint, $a\notin BC$. Then $a^2\in ABC=BC\cup aBC$ implies $a^2\in BC$ and hence $e=a^3\in aBC$, which is not possible as the sets $aBC$ and $eBC\ni e$ are disjoint. This contradiction shows that $a^2=e$. By analogy we can prove that $c^2=e$.

Since the sets $B\ni e$ and $aBc\ni ac$ are disjoint, $a\ne c$. Then $a,c,ac$ are the unique elements of order 2 in $A_4$.

Since the sets $B$, $aB\ni a$, $Bc\ni c$ and $aBc\ni ac$ are pairwise disjoint, the set $B$ contains no elements of order 2.

Fix any element $b\in B$ (or order 3). The group $A_4$ can be thought as the group of orientation-preserving isometries of a regular tetrahedron. Selecting a suitable enumeration of the vertices of the tetrahedron, we can assume that $a$ is the permutation $(12)(34)$ and $b$ is the cycle $(123)$. It is easy to check that $b^{-1}ab^{-1}=aba$.

One can check that $\{c,ac\}=\{bab^{-1},b^{-1}ab\}$ and $A_4\setminus\{e,a,c,ac\}=\{b,b^{-1},ab,ba,aba,ab^{-1},bab,b^{-1}a\}$.

It follows that $c=bab^{-1}$. Otherwise $c=b^{-1}ab$ and then the set $aBc\ni abb^{-1}ab=b$ is not disjoint with $B$.

Let $b'$ be the unique point of the set $B\setminus\{e,b\}$. Taking into account that the set $B$ is disjoint with $aB\cup Bc\cup aBc$, we conclude that $b'\notin\{b,ab,bc,abc\}=\{b,ab,b^{-1}ab^{-1},ab^{-1}ab^{-1}\}=\{b,ab,aba,ba\}$ and hence $b'\in\{b^{-1},ab^{-1},bab,b^{-1}a\}$.

If $b'=b^{-1}$, then $ab'c=ab^{-1}bab^{-1}=b^{-1}=b'$.

If $b'=ab^{-1}$, then $ab'c=ab^{-1}bab^{-1}=ab^{-1}=b'$.

If $b'=bab$, then $ab'c=ababbab^{-1}=abab^{-1}ab^{-1}=abaaba=ab^{-1}a=ab^{-1}ab^{-1}b=aabab=bab=b'$.

If $b'=b^{-1}a$, then $ab'c=ab^{-1}abab^{-1}=ab^{-1}ab^{-1}b^2ab^{-1}=aabab^{-1}ab^{-1}=baaba=b^{-1}a=b'$.

In all cases, we get $ab'c=b'$, which is not possible as the sets $aBc$ and $B$ are disjoint. This contradiction completes the proof.

Conclusion. Since the group $A_4$ is solvable, it answers negatively Problem 2 and (partly) Problem 1.

It remains find a finite simple group which is not multifactorizable.

$\endgroup$
  • $\begingroup$ For $A_4$, the maximum order for $|ABC|$ is $10$. Other groups of order $12$ are multifactorizable. Order $12$ is small enough so you can also check this quickly with a computer. $\endgroup$ – spin Nov 28 '18 at 2:56
  • $\begingroup$ @spin What about $A_5$? Is it $2{\times}15{\times}2$ factorizable? Can this be checked by computer? $\endgroup$ – Taras Banakh Nov 28 '18 at 7:11
  • $\begingroup$ I don't know. Maybe a naive computer search is not feasible for $A_5$. For all subsets $A$ and $C$ of $A_5$ containing the identity with $|A| = |C| = 2$, I tried a small amount (around 10000) of random subsets $B$ with $|B| = 15$. The maximum value I could find for $|ABC|$ was $58$. $\endgroup$ – spin Nov 28 '18 at 9:37
  • $\begingroup$ @TarasBanakh The same reasoning as in your argument shows that if $A_5=ABC$ with $A=\{e,a\}$ then $a^n \in BC$ (resp. $aBC$) if $n$ is even (resp. odd). Since the possible orders of $a$ are $2,3,5$, this implies that $a$ has order 2. $\endgroup$ – François Brunault Nov 28 '18 at 10:32
  • $\begingroup$ @FrançoisBrunault Thank you for this comments. Then $a$ and $c$ have order 2. The number of elements of order 2 in $A_5$ equals 15. So the brute force algorithm will require considering $15\times 14\times\binom{57}{15}=1\,615\,875\,386\,202\,000\approx 1.6×10^{15}$ cases, which is accessible for modern (even laptop) computers. Maybe some information (restricting the search) can be derived also for the set $B$? $\endgroup$ – Taras Banakh Nov 28 '18 at 10:53

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.