12
$\begingroup$

Definition. A finite group $G$ is factorizable if for any positive integer numbers $a,b$ with $ab=|G|$ there are subsets $A,B\subset G$ of cardinality $|A|=a$ and $|B|=b$ such that $AB=G$.

Problem 1. Is each finite group factorizable?

As I understood from these MO-posts (1, 2, 3), this problem is wide open and there is no intuition if it is true or not. So, we can ask a related

Problem 2. Which finite groups are factorizable?

The class of factorizable groups has a nice 3-space property that can be formulated in terms of bifactorizable subgroups.

A subgroup $H$ of a group $G$ is called bifactorizable if $H$ is factorizable and for any positive integer numbers $a,b$ with $ab=|G|$ there are sets $A,B\subset G$ such that $AHB=G$, $|A|\cdot |H|\cdot |B|=|G|$, $|A|$ divides $a$ and $|B|$ divides $b$.

Theorem. A finite group $G$ is factorizable if $G$ contains a bifactorizable subgroup $H$.

Proof. Given positive integers $a,b$ with $ab=|G|$ use the bifactorizability of $H$ to find subsets $A_1,B_1\subset G$ such that $AHB=G$, $|A_1|\cdot |H|\cdot |B_1|=|G|$, $|A_1|$ divides $a$, and $B_1$ divides $b$. The factorizability of $H$ yields two sets $A_2,B_2\subset H$ of cardinality $|A_2|=a/|A_1|$ and $|B_2|=b/|B_1|$ such that $A_2B_2=H$. Then the sets $A=A_1A_2$ and $B=B_2B_1$ have cardinality $|A|\le a$, $|B|\le b$ and $AB=A_1A_2B_2B_1=A_1HB_1=G$. It follows from $ab=|G|=|A|\cdot|B|\le ab$ that $|A|=a$ and $|B|=b$. $\square$

It is easy to see that a subgroup $H$ of a group $G$ is bifactorizable if it is factorizable and has prime index in $G$. Moreover, as was observed by M.Farrokhi D.G. in his answer to this post, a subgroup $H$ of a group $G$ is bifactorizable if $H$ is factorizable and the index of $H$ in $G$ is a prime power $p^k$ such that $p^{2k-1}$ divides $|G|$.

A normal subgroup $H$ of a group $G$ is factorizable if both groups $H$ and $G/H$ are factorizable. This implies

Corollary. A finite group $G$ is factorizable if $G$ contains a bifactorizable subgroup $H$ with factorizable quotient $G/H$.

This corollary reduces Problems 1,2 to studying the factorizability of finite simple groups. According to the classification of finite simple groups, each finite simple group is either cyclic of prime order, or alternating, or belongs to 16 families of groups of Lie type or is one of 27 sporadic groups.

Among these families only the factorizability of finite cyclic groups is trivially true.

Problem 3. Is each alternating group $A_n$ factorizable?

It may happen that the argument of Ilya Bogdanov from his answer to this MO-problem can be helpful here. On the other hand, it can be shown that the subgroup $A_n$ is bifactorizable in $A_{n+1}$ if and only if $A_n$ is factorizable and $n\ne 3$ is a power of a prime. It follows from the answer to this MO-question that the subgroup $A_3$ is not bifactorizable in $A_4$.

Problem 4. Is any hope to prove that some infinite family of simple groups of Lie type consists of factorizable groups?

$\endgroup$
  • $\begingroup$ Amazing to me that this seemingly basic problem in the theory of finite groups is apparently open. $\endgroup$ – Sam Hopkins Nov 26 '18 at 16:01
  • $\begingroup$ @SamHopkins I am not expert in Group Theory. I admit that this problem has an answer, known to specialists, see the answer of M.Farrokhi D.G. $\endgroup$ – Taras Banakh Nov 26 '18 at 16:12
  • $\begingroup$ I would guess that if the answer to the question is yes, then it might be possible to prove it, given that the problem has been reduced to the case of finite simple groups, about which a lot is known. But if the answer to the question is no, then it could be very hard to prove because you have so many subsets to consider! $\endgroup$ – Derek Holt Nov 26 '18 at 19:21
  • $\begingroup$ @DerekHolt Exactly this reduction to the case of finite simple groups follows from Corollary. For a negative answer maybe it will be easier to construct a counterexample to this related question: mathoverflow.net/questions/316262/… $\endgroup$ – Taras Banakh Nov 26 '18 at 19:33
  • 1
    $\begingroup$ 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:13
7
$\begingroup$

The problem both in case of numbers and groups are extensively studied in a more general setting. Here are the main references (books) I know:

Groups:

  • Products of Finite Groups (Adolfo Ballester-Bolinches, Ramon Esteban-Romero and Mohamed Asaad)(2010)
  • Factoring Groups into Subsets (Sandor Szabo and Arthur D. Sands)(2009)
  • Topics in Factorization of Abelian Groups (Sandor Szabo)(2004)
  • Products of Groups (Bernhard Amberg, Silvana Franciosi and Francesco de Giovanni)(1993)
  • Products of Conjugacy Classes in Groups (Zvi Arad and Marcel Herzog)(1985)

Also

  • The Maximal Factorizations of the Finite Simple Groups and Their Automorphism Groups (M. W. Liebeck, C. E. Praeger and J. Saxl)(1990)(86)(432)

Numbers:

  • Structural Additive Theory (David J. Grynkiewicz)(2013)
  • Combinatorial Number Theory and Additive Group Theory (Alfred Geroldinger and Imre Z. Ruzsa)(2009)
  • Additive Combinatorics (Terense Tao and Van Vu)(2006)
  • Additive Number Theory; The Classical Bases (Melvyn B. Nathanson)(1996)
  • Additive Number Theory: Inverse Problems and the Geometry of Sumsets (Melvyn B. Nathanson)(1996)
  • Foundations of a Structural Theory of Set Addition (Gregory A. Freiman)(1973)
$\endgroup$
  • $\begingroup$ Thank you fro the extensive references. But what about the above problems? What is the answer? Is each finite group factorizable or not? $\endgroup$ – Taras Banakh Nov 26 '18 at 14:37
6
$\begingroup$

Definition. We say that a group $G$ of order $n$ is good if it satisfies any of the following equivalent conditions:

  • For every divisor $d$ of $n$, there exists a nontrivial proper subgroup $H$ of $G$ such that either $d$ or $n/d$ divides $|H|$.
  • For every divisor $d$ of $n$, there exists a nontrivial proper subgroup $H$ of $G$ such that $[G:H]$ divides either $d$ or $n/d$.

In the above definition, we can replace the subgroups with maximal subgroups. A set of (maximal) subgroups appearing in the definition of a good group is called a good set of (maximal) subgroups.

Theorem. Every good finite group with a good set of factorizable subgroups is factorizable.

Proof. Let $X$ be a good set of factorizable subgroups of $G$. If $|G|=ab$, then there exists a subgroup $H\in X$ such that $|H|$ is divisible by $a$ or $b$, say $a$. Let $|H|=aa'$ and $H=AA'$ be such that $|A|=a$ and $|A'|=a'$. Then $G=H(H\backslash G)=A(A'(H\backslash G))$ is a factorization of $G$ with $|A|=a$ and $|A'(H\backslash G)|=b$. Therefore, $G$ is factorizable.

Corollary. Let $q\neq2,4$ be a prime power. If $A_{q-1}$ is factorizable, then so is $A_q$.

Proof. The group $A_q$ has a maximal subgroup $A_{q-1}$ of index $q$, and that $q$ divides either $a$ or $b$ whenever $|A_q|=ab$. Hence, $A_q$ is good with the good set $\{A_{q-1}\}$ of factorizable subgroups so that $A_q$ is factorizable.

As a result, we obtain a new proof that $A_9$ is factorizable.

I think a large class of finite simple groups can be studied using the above theorem and the following criterion of François Brunault:

  • If $|G|=ab$ and $G$ has a section of size $a$ or $b$, then $G=AB$ with $|A|=a$ and $|B|=b$.
$\endgroup$
  • $\begingroup$ I understand how Theorem implies Corollary for a prime q. But how do you derive it for prime powers? Why do you think that if a prime power $q$ divides $ab$, then it divides $a$ or $b$? $\endgroup$ – Taras Banakh Nov 26 '18 at 17:04
  • $\begingroup$ And what is a "section" in the result of Francois Brunault, you mention? $\endgroup$ – Taras Banakh Nov 26 '18 at 17:07
  • $\begingroup$ The definition of a "good" is not good as each group is good: just take $H=G$. Maybe "proper" should be added? $\endgroup$ – Taras Banakh Nov 26 '18 at 17:14
  • 1
    $\begingroup$ Suppose $q=p^k$. The largest power of $p$ dividing $|A_q|$ is at least $2k-1$, so either $q$ divides $a$ or $b$. A section is simply a pair of subgroups $H\subseteq K$ of $G$ and the size means $[K:H]$. The definition of good groups is fixed. $\endgroup$ – M. Farrokhi D. G. Nov 26 '18 at 17:18
  • $\begingroup$ Are all arternating groups good? $\endgroup$ – Taras Banakh Nov 26 '18 at 17:23

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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