A tuple $(A_1,\dots,A_n)$ of subsets of a finite group $G$ is called a factorization of $G$ if $G=A_1\cdots A_n$ and $|A_1|\cdots|A_n|=G$.

In Cryptology factorizations of groups are known as logarithmic signatures.

A factorization $(A_1,\dots,A_n)$ of a group $G$ is called

$\bullet$ minimal if for every $i\le n$ the cardinality $|A_i|$ is prime or equal to 4;

$\bullet$ prime if for every $i\le n$ the cardinality $|A_i|$ is prime;

$\bullet$ cyclic if for every $i\le n$ the set $A_i$ is cyclic in the sense that $A_i=\{a_i^k:0\le k<|A_i|\}$ for some $a_i\in A_i$;

$\bullet$ a decomposition if each set $A_i$ is a subgroup of $G$.

Since each group of prime cardinality is cyclic, each prime decomposition is cyclic.

It is easy to see that each cyclic set $A$ can be written as the product $A=A_1\cdots A_n$ of cyclic sets $A_1,\dots,A_n\subset A$ of prime cardinality with $|A|=|A_1|\cdots|A_n|$.

Consequently, for any finite group $G$ we have the implications:

$G$ has a prime decomposition $\Rightarrow$ $G$ has a cyclic decomposition $\Rightarrow$ $G$ has a cyclic factorization $\Rightarrow$ $G$ has a prime factorization $\Rightarrow$ $G$ has a minimal factorization.

For any prime number $p$ and any $n>1$ the cyclic group $C_{p^n}$ has a cyclic decomposition (and hence has a prime factorization) but does not have a prime decomposition.

The 8-element group $Q_8=\{1,-1,i,-i,j,-j,k,-k\}$ of quaternion units has a cyclic factorization but does not have a cyclic decomposition.

For other 3 properties we have 3 (open?) problems:

Problem M. Has every finite group $G$ a minimal factorization?

Problem P. Has every finite group $G$ a prime factorization?

Problem C. Has every finite group $G$ a cyclic factorization?

Problem M is well-known in Cryptography as the problem of existence of a minimal logarithmic signature. Minimal (and cyclic) logarithmic signatures have been constructed in many classical finite groups and also in some sporadic simple groups. By Theorem 2.1 in the Ph.D.Thesis of Singhi, solvable groups and all alternating groups have cyclic factorizations. Moreover, by the proof of Proposition 7.1 in this paper of Magliveras, every alternating group $A_n$ has a cyclic decomposition.

Nonetheless, Problem M is known to be open.

I am interested in the status of Problems P and C.

Have we a counterexample to Problem C?

What is the role of the number 4 in the definition of a minimal factorization?

Is there any example of a finite group for which we know that a minimal factorization exists but a prime (or cyclic) factorization cannot be constructed?

  • $\begingroup$ Wasn't it you who just gave $A_4$ as a counterexample for this yesterday? . . . mathoverflow.net/questions/316262 $\endgroup$ – Noam D. Elkies Nov 28 '18 at 20:58
  • 2
    $\begingroup$ @NoamD.Elkies No, $A_4$ is not a counterexample: $A_4$ contains a subgroup isomorphic to $C_2\times C_2$ and hence admits a decomposition $A_4=ABC$ with $|A|=|B|=2$ and $|C|=3$. What I proved yesterday, is that $A_4$ cannot be written as $A_4=ABC$ with $|A|=2$, $|B|=3$ and $|C|=2$. $\endgroup$ – Taras Banakh Nov 28 '18 at 21:10
  • $\begingroup$ The number $2$ is an exception in group theory, and in many cases (including p-groups), usually $4$ (say elements of order $4$) is used instead of $2$. $\endgroup$ – M. Farrokhi D. G. Nov 29 '18 at 7:18
  • $\begingroup$ Conjecture 1' is true for solvable groups. In general, if Conjecture 1' is not true for a group G, then G is not the product of its Sylow subgroups. However, not every group is the product of its Sylow subgroups. A counterexample is $A_6$. Here, by the product of Sylow subgroup, it means the product of Sylow $p_i$-subgroups with $p_i$ being the distinct prime divisors of $|G|$. $\endgroup$ – M. Farrokhi D. G. Nov 29 '18 at 9:52
  • $\begingroup$ @M.FarrokhiD.G. I have rewrote the problem. Now Conjecture 1' corresponds to Problems P and C. So, your observation about solvable groups can be written as the existnce of a cyclic factorization for any solvable group. $\endgroup$ – Taras Banakh Nov 29 '18 at 9:59

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.

Browse other questions tagged or ask your own question.