![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
In this paper, we introduce a kind of decomposition of a finite group called a uniform group factorization, as a generalization of exact factorizations of a finite group. A group G is said to admit a uniform group factorization if there exist subgroups such that
and the number of ways to represent any element
as
(
) does not depend on the choice of g. Moreover, a uniform group factorization consisting of cyclic subgroups is called a uniform cyclic group factorization. First, we show that any finite solvable group admits a uniform cyclic group factorization. Second, we show that whether all finite groups admit uniform cyclic group factorizations or not is equivalent to whether all finite simple groups admit uniform group factorizations or not. Lastly, we give some concrete examples of such factorizations.
1 Introduction
Throughout this paper, all groups are assumed to be finite and nontrivial, and the basic notations follow [Citation5] and Atlas [Citation3]. For a group G, we denote by Pp a p-Sylow subgroup of G.
A group G is said to admit a factorization (resp. a group factorization) of length k by an ordered tuple of subsets (resp. subgroups) if
Moreover, is called exact if
, and is called maximal if
are maximal subgroups. Such factorizations of a group were investigated in many previous works in the literature. A pioneering work by Miller [Citation24] reveals that, in contrast to the fact that any group factorization
of length two implies that
as well (hence the ordering of the two factors does not matter), the ordering of factors is in fact essential for factorizations of length three or longer. In particular, he showed that
but
for some Sylow subgroups P2, P3, and P5.
In group theory, one of the main directions is to study simple groups. Following the vigorous works on group factorizations of length two by Zappa [Citation29] and Szép [Citation27, Citation28], Itô [Citation15] studied group factorizations of the projective special linear group for each prime power q. In particular, he showed that there is an exact maximal group factorization by two non-normal subgroups of
if
and q > 7. This fact together with the main theorem by [Citation28] gives a short proof of the simplicity of
. In this context, some authors worked on exact group factorizations of simple groups; for example, [Citation6, Citation7, Citation12], and so on. Subsequently, Liebeck, Praeger, and Saxl [Citation20] determined whether each sporadic simple group G and its automorphism group
have maximal group factorizations of length two. After that, Giudici [Citation8] determined all group factorizations of length two for sporadic simple groups. In recent years, there have been many studies (e.g., [Citation2, Citation18, Citation19]) on exact group factorizations of length two of almost simple groups (i.e., groups G such that
for some simple group S). In 2021, Rahimipour [Citation26] constructed exact group factorizations of length three or four for some sporadic simple groups.
Independent of the works described above, Magliveras [Citation21] studied exact factorizations, where he called them logarithmic signatures, to construct a symmetric-key encryption scheme known as PGM cryptosystem. (See also [Citation1, Citation17, Citation23].) For a logarithmic signature , the size of
is defined by the sum of the cardinality of each component of
. Since the size of a logarithmic signature corresponds to the size of the key in the cryptosystem, it is desirable to find a logarithmic signature of as small size as possible. In 2002, González Vasco and Steinwandt [Citation10] gave a lower bound on the size of logarithmic signatures of a finite group. A logarithmic signature matching the lower bound is called a minimal logarithmic signature. It has been conjectured that any finite group has a minimal logarithmic signature. In this context, there are various previous works on constructing minimal logarithmic signatures for finite groups; for example, [Citation9, Citation13, Citation16, Citation25].
The present paper introduces the notion of uniform factorizations of a finite group as an analogy of logarithmic signatures (or exact factorizations). Let G be a finite group and a tuple of subsets of G. If, for any
, the number of tuples
with
does not depend on the choice of g, then
is called a uniform factorization of G and we write
. Obviously, the tuple (G) of length one is a uniform factorization. If
are proper subsets, the factorization is said to be proper. If
are subgroups of G, then
is called a uniform group factorization of G. Moreover, if they are cyclic subgroups of G, then
is called a uniform cyclic group factorization of G.
Uniform cyclic group factorizations for various finite groups are expected to have applications in computer algebra. For example, they can be applied to efficient generation of uniformly random elements of a finite group G. A straightforward method involves assigning an integer from 1 to to each element and selecting the x-th element for a uniformly random number
. Although this method is feasible when the elements of G are efficiently enumerable, in general, this method requires storing all elements in a table, which requires a huge storage space when
is large. In contrast, if a uniform cyclic group factorization
exists, such a random element
can be generated by
where hi is a generator of Hi and
is chosen uniformly at random. This method only requires storing k elements
, significantly reducing the storage space. Here we emphasize that, in order to make the element g uniformly random, it is not necessary for a decomposition of g into elements of Hi’s being unique. The requirement is that there are a constant number of such decompositions independent of g, justifying our relaxed condition for uniform factorizations compared to logarithmic signatures. We note that there is a line of studies (e.g., [Citation4]) on the problem of generating group elements with a distribution close to uniform, while the above method based on uniform cyclic group factorizations generates perfectly uniform distribution.
Now it is natural to ask the following question:
Question 1.1. Does any finite group have a uniform cyclic group factorization?
One of the two main results of this paper asserts that Question 1.1 can be reduced to the case of non-solvable groups. Precisely, we have the following theorem:
Main Theorem 1.2 (Theorem 3.3). Any finite solvable group admits a uniform cyclic group factorization. In particular, any finite abelian group admits a uniform cyclic group factorization.
The other main result of this paper asserts that Question 1.1 can be further reduced to the case of uniform (not necessarily cyclic) group factorizations for simple groups. Precisely, we have the following theorem:
Main Theorem 1.3 (Theorem 3.4). Let n be a positive integer. The following are equivalent.
Any
admits a uniform cyclic group factorization, where
is the set of groups of order at most n.
Any
admits a proper uniform group factorization, where
consists of groups in
not cyclic of prime power.
Any
admits a proper uniform group factorization, where
consists of simple groups in
.
This paper consists of five sections. In Section 2, we introduce the notion of uniform cyclic group factorizations. In Section 3, we prove the main theorems described above. In Section 4, we discuss relationships among logarithmic signatures and uniform cyclic group factorizations of finite groups. In Section 5, we construct some concrete examples of uniform group factorizations by following methods of constructing logarithmic signatures (e.g., [Citation9]). In particular, we give uniform cyclic group factorizations of the alternating groups.
2 Uniform cyclic group factorizations
Let G be a finite group and an ordered tuple of subsets of G. Define the multiplication map
by
Then, is called a factorization of G if
is surjective. The integer k is called the length of
. We write
when
is a factorization of G. If all
are proper subsets of G, then
is called a proper factorization of G.
Definition 2.1.
Let G be a finite group and a factorization of G.
The factorization
is a uniform factorization of G if
does not depend on
. The integer
is called the multiplicity of
. In this case, we write
, or simply
.
The factorization
is a uniform group factorization of G if
is a uniform factorization of G and all
are subgroups of G.
The factorization
is a uniform cyclic group factorization of G if
is a uniform group factorization of G and all
are cyclic subgroups of G.
Remark 2.2.
If a finite group G admits a direct product decomposition into (normal) subgroups
, then it follows immediately that
is a uniform group factorization of G with multiplicity one.
The following lemma enables recursive construction of uniform group factorizations.
Lemma 2.3.
Let G be a group and a uniform group factorization of G with multiplicity t. If each Hi (
) has a uniform cyclic group factorization with multiplicity ti, then G also has a uniform cyclic group factorization with multiplicity
.
Proof.
Let be a uniform cyclic group factorization of Hi for
. Let
be the ordered tuple of cyclic groups in the following:
Since for any
is expressed as
we have
, which proves the statement. □
Example 2.4.
For a finite group G, uniform cyclic group factorizations are not necessarily unique. In fact, the symmetric group S5 has the following three uniform cyclic group factorizations:
The multiplicities of and
are 1 since the product of the cardinality of each subgroup equals
. The multiplicity of
is 2 since the product of the cardinality of each subgroup equals
.
The following lemma is fundamental.
Lemma 2.5.
Let G and be two finite groups, and
a group homomorphism. Let
be subgroups of G. Define
. If
is a uniform group factorization of
with multiplicity
, then
is a uniform group factorization of G with multiplicity
.
Proof.
For any , we define a map
by sending
to
. The map
is surjective because for any
, by taking
such that
, we have
and
. Then we have
Let . Put
Since the map defined by
is bijective and
, it implies that
. Thus we have
Therefore, is a uniform group factorization of G with multiplicity
. □
Proposition 2.6.
Let G be a cyclic group. The following are equivalent:
G admits a proper uniform group factorization.
is not a prime power.
Moreover, if these conditions hold, then the factorization in (i) can be made cyclic and with multiplicity one.
Proof.
Let γ be a fixed generator of G. Set .
To show that negation of (ii) implies negation of (i), assume that for some prime number p. Then any proper (and nontrivial) subgroup of G is a cyclic group of the form
, where
. Thus, any tuple of proper subgroups
can not be a factorization since
. Therefore, G has no proper uniform group factorization.
To show that (ii) implies (i), assume that n is not a prime power. In this case, n can be written as with
being coprime. Now we have
by Chinese Remainder Theorem, therefore G admits a proper uniform cyclic group factorization with multiplicity one by Remark 2.2. □
3 Main results
The aim of this section is to prove the main results of this paper.
First, we mention that the next assertion follows from Lemma 2.5 immediately.
Lemma 3.1.
Let G be a finite group with a proper normal subgroup N, and the canonical surjection. Let
be subgroups of G. If
is a uniform group factorization of G/N, then
is a uniform group factorization of G. Moreover, if
is a proper uniform group factorization, then so is
.
The next lemma is easy but is useful in proving our first main theorem.
Lemma 3.2.
Any finite abelian group admits a uniform cyclic group factorization.
Proof.
The structure theorem for finite abelian groups implies that the group in the statement is a direct product of cyclic subgroups. Then the claim follows from Remark 2.2. □
Now we give the first main theorem of this paper.
Theorem 3.3.
Any finite solvable group admits a uniform cyclic group factorization.
Proof.
Let
be a subnormal series of finite length with strict inclusions such that
is an abelian group for
. From Lemma 3.2,
admits a uniform cyclic group factorization, say
for
. Now by taking a preimage of a generator of
(
), we can construct a cyclic subgroup
of Gi with
. Then by Lemma 3.1,
is a uniform group factorization of Gi for
. By applying Lemma 2.3 recursively for
, it follows that
is a uniform cyclic group factorization of Gi. Now is the factorization of G = G0 as in the statement. □
For a positive integer n, we define three sets , and
as follows.
is the set consisting of isomorphism classes of finite groups of order at most n.
is the subset of
obtained by removing cyclic groups of prime power.
is the subset of
obtained by removing non-simple groups.
By definition, we have the following inclusions:
Now we give the second main theorem of this paper.
Theorem 3.4.
Let be an integer. The following are equivalent.
Any
admits a uniform cyclic group factorization.
Any
admits a proper uniform group factorization.
Any
admits a proper uniform group factorization.
Proof.
(a) (b): Let
. If G is not cyclic, it has a uniform cyclic group factorization by (a). Since G is not cyclic, the factorization is proper. If G is a cyclic group whose order is not a prime power, it admits a proper uniform group factorization by Proposition 2.6. Therefore, (a) implies (b).
(b) (c): This implication is trivial.
(c) (a): We show the assertion by induction on n. For a positive integer n, we suppose that (c) holds. Then the condition (c) for
also holds, therefore the induction hypothesis implies that the condition (a) for
holds as well. Let
. If G is a cyclic group (including the base case n = 1), then G itself can be regarded as a uniform cyclic group factorization of G. Thus, we may assume that G is not cyclic. If G is a simple group, then G admits a proper uniform group factorization, say
, by (c). Since (a) holds for
as mentioned above, each component of
admits a uniform cyclic group factorization, therefore G also admits a uniform cyclic group factorization by Lemma 2.3. If G is not a simple group, then a maximal normal subgroup of G exists, say N. Since
and (a) holds for
as mentioned above, G/N admits a uniform cyclic group factorization, say
. From this, we can obtain a uniform group factorization
of G as in Lemma 3.1, where any component other than N can be chosen as being cyclic (as well as those in
). Now since
and (a) holds for
as mentioned above, N admits a uniform cyclic group factorization. Hence by Lemma 2.3, G also admits a uniform cyclic group factorization.
Therefore, (c) implies (a). □
4 Logarithmic signatures and uniform cyclic group factorizations
Let G be a finite group, and a tuple of subsets of G. The tuple
is called a logarithmic signature (or an exact factorization) of G, which is named by [Citation21], if
is a uniform factorization of G with multiplicity one. If
is a logarithmic signature, the size of
is defined by
.
González Vasco and Steinwandt [Citation10] gave a lower bound on the size of logarithmic signatures. The lower bound is given as follows. Suppose that , where the pi’s are distinct prime numbers and ai is a positive integer. Then they showed that the following inequality holds for any logarithmic signature
:
If the equality holds, is called a minimal logarithmic signature of G.
Let G be a finite group. We define the following sets:
By definition, we have relations of inclusion among these sets.
Table
The next proposition shows that these notions are in fact distinct.
Proposition 4.1.
The following statements hold:
There exists G such that
, and
.
There exists G such that
, and
.
There exists G such that
, and
.
There exists G such that
, and
.
Proof.
(1) Let . Set
for
and
. Since
and
, we have
, therefore
and
. On the other hand, since H1 is not a group, we have
, therefore
and
.
(2) Let . Set
for
and
. Since
and
, we have
, therefore
and
. On the other hand, since H1 is not cyclic, we have
, therefore
and
.
(3) Let G be any cyclic group, and . Then we have
, therefore
and
. On the other hand, we have
, therefore
and
.
(4) Let n > 1 be an integer which is neither 4 nor a prime number. Let G be a cyclic group of order n. Set . Then we have
, therefore
and
. On the other hand, we have
, therefore
and
.
The proof is completed. □
There is a line of research on the following question: Does every finite group have a minimal logarithmic signature? On the other hand, our question in this paper is: Does every finite group have a uniform cyclic group factorization? Since there is no inclusion relation between and
in general, these questions are independent. Compared to (minimal) logarithmic signatures, uniform cyclic group factorizations are more restrictive from the viewpoint that each Hi is restricted to a cyclic group, while it is less restrictive from the viewpoint that the multiplicity may be larger than one.
The former viewpoint leads to the fact that not every existing construction of (minimal) logarithmic signatures yields uniform (cyclic) group factorizations (e.g., the construction method of double coset decomposition [Citation13, Citation16]). We note that some of them are indeed useful for constructing uniform (cyclic) group factorizations. For example, [Citation16, Theorem 3.1] gives a minimal logarithmic signature of PSL(n, q) () which yields a uniform group factorization of it.
The latter viewpoint allows for other construction methods on uniform cyclic group factorizations which are not applicable to (minimal) logarithmic signatures. In particular, since and
are equivalent when the length of factorization is two, a uniform group factorization of G is immediately obtained from
(see Section 5.3).
5 Examples
5.1 Sylow systems
Let G be a finite group, and the prime factors of
. For any
, we take a Sylow subgroup
of G. Then the ordered tuple
is called a Sylow system of G if
is a uniform group factorization with multiplicity 1 for any permutation σ. It is well-known that any finite solvable group has a Sylow system [Citation11, Subsection 6.4, Theorem 4.3].
There are the following three cases:
G has a Sylow system.
G does not have a Sylow system, but has a uniform group factorization with multiplicity 1 consisting of Sylow subgroups.
G has neither a Sylow system nor a uniform group factorization with multiplicity 1 consisting of Sylow subgroups.
Some researchers have studied which finite groups belong to which type; for example, see . Since groups classified as Types (I) and (II) have uniform group factorizations, it is an important research question to make it clear which non-solvable groups belong to Types (I) or (II).
Table 1 Sylow systems and uniform group factorizations of finite groups.
5.2 Alternating groups
Let be a family of finite groups such that Gn acts on a set Xn. Then,
is a stabilizer chain of
if, for any
, there exists
such that the stabilizer
is isomorphic to
. González Vasco, Rötteler, and Steinwandt constructed a uniform group factorization of each Mathieu group with multiplicity 1 based on stabilizer chains; for details, see [Citation9]. Their method can be also extended to the case of some other groups. In this subsection, as an example, we give a uniform cyclic group factorization of the alternating group An
. First, we show the following useful lemma.
Lemma 5.1.
Let G be a finite group, and
non-trivial subgroups of G. Assume that the following conditions (a) and (b) are satisfied.
.
For any
, there exists
such that
.
Then, is a proper uniform group factorization of G with multiplicity 1.
Proof.
Let . By condition (b), there exists
such that
. Then, we have
. By condition (a), such expression is unique. Therefore,
is a proper uniform group factorization of G with multiplicity 1. □
Now, we construct a uniform cyclic group factorization of the alternating group An.
Proposition 5.2.
For any integer , the alternating group An admits a uniform cyclic group factorization with multiplicity 1.
Proof.
We show the statement by induction on n.
If n = 3, the assertion follows obviously since A3 is cyclic (of order three).
Suppose that n > 3. We consider the natural action of An on . Take
, which acts on
naturally.
First, we suppose that n is odd. We consider the subgroup K of An generated by . Then, for any
, we observe that
fixes the point n, that is,
Thus, it follows from Lemma 5.1 that is a uniform group factorization. By induction hypothesis, H has a uniform cyclic group factorization, and so does An by Lemma 2.3.
Now, we suppose that for some positive integer m. We put
Then, it is easy to check that σ1 and σ2 belong to An. Let and
. Let
. If
, then
fixes the point n. Otherwise,
fixes the point n, where e is the identity element of K2. Thus,
is a uniform group factorization of An by Lemma 5.1. By induction hypothesis, H has a uniform cyclic group factorization, and so does An by Lemma 2.3. □
Remark 5.3.
A construction of a uniform group factorization of An can be found in [Citation22]. However, the construction needs to be corrected. Indeed, if for some odd integer
, then the group
appeared in the construction by [Citation22] is not a subgroup of An.
5.3 Group factorizations of length two
Let G be a finite group, and subgroups of G. In general,
does not imply
. However, when k = 2,
implies
. More precisely, the following lemma can be seen in [Citation24].
Lemma 5.4.
Let G be a finite group, and H1 H2 subgroups of G. If , then
is a uniform group factorization of G with multiplicity
.
Proof.
For any , we write
for some
and
. We then have
This implies the assertion immediately. □
By Lemma 5.4, if (H1, H2) is a uniform group factorization of a finite group G, and (resp.
) is a maximal subgroup containing H1 (resp. H2), then
is also a uniform group factorization. Thus, we may assume that H1 and H2 are maximal without loss of generality.
Liebeck, Praeger, and Saxl [Citation20] showed that sporadic simple groups , J2, HS, He, Ru,
have maximal group factorizations of length two (which are in fact uniform group factorizations from Lemma 5.4), and the other sporadic simple groups do not have such factorizations (see also [Citation8]). By Lemma 5.4, these sporadic simple groups have a uniform cyclic group factorization with multiplicity greater than 1. A natural question is whether it is essential that the multiplicity of these cyclic group factorizations be greater than 1. We left as an open problem to find (or prove the inexistence of) a group G such that G has a uniform cyclic group factorization with multiplicity greater than 1, but does not have one with multiplicity 1.
Additional information
Funding
References
- Bohli, J. M., Steinwandt, R., González Vasco, M. I., Martínez, C. Weak keys in MST1. Des. Codes Cryptogr 37(3): 509–524. DOI: 10.1007/s10623-004-4040-y.
- Burness, T. C., Li, C. H. (2021). On solvable factors of almost simple groups. Adv. Math. 377:Paper No. 107499, 36 pp. DOI: 10.1016/j.aim.2020.107499.
- Conway, J. H., Curtis, R. T., Norton, S. P., Parker, R. A., Wilson, R. A. (1985). An ATLAS of Finite Groups. Oxford: Oxford University Press.
- Dixon, J. D. (2008). Generating random elements in finite groups. Electron. J. Comb. 15:R94–R94.
- Dixon, J. D., Mortimer, B. (1996). Permutation Groups. Graduate Texts in Mathematics, 163. New York: Springer-Verlag, xii + 346 pp.
- Gentchev, Ts. R. (1986). Factorizations of the sporadic simple groups. Arch. Math. (Basel) 47:97–102. DOI: 10.1007/BF01193676.
- Gentchev, Ts. R. (1986). Factorizations of the groups of Lie type of Lie rank 1 or 2. Arch. Math. (Basel) 47:439–499. DOI: 10.1007/BF01189858.
- Giudici, M. (2006). Factorisations of sporadic simple groups. J. Algebra 304:311–323. DOI: 10.1016/j.jalgebra.2006.04.019.
- González Vasco, M. I., Rötteler, M., Steinwandt, R. (2003). On minimal length factorizations of finite groups. Exp. Math. 12(1):1–12. DOI: 10.1080/10586458.2003.10504708.
- González Vasco, M. I., Steinwandt, R. (2002). Obstacles in two public-key cryptosystems based on group factorizations. Tatra Mt. Math. Publ. 25:23–37.
- Gorenstein, D. (2007). Finite Groups, 301. Providence, RI: American Mathematical Society.
- Hering, C., Liebeck, M. W., Saxl, J. (1987). The factorizations of the finite exceptional groups of Lie type. J. Algebra 106(2):517–527. DOI: 10.1016/0021-8693(87)90013-5.
- Holmes, P. E. (2003). On minimal factorisations of sporadic groups. Exp. Math. 13(4):435–440. DOI: 10.1080/10586458.2004.10504552.
- Holt, D., Rowley, P. (1993). On products of Sylow subgroups in finite groups. Arch. Math. (Basel) 60(2):105–107. DOI: 10.1007/BF01199094.
- Itô, N. (1953). On the factorizations of the linear fractional group LF(2,pn). Acta Sci. Math. (Szeged) 15:79–84.
- Lempken, W., van Trung, T. (2005). On minimal logarithmic signatures of finite groups. Exp. Math. 14(3):257–269. DOI: 10.1080/10586458.2005.10128924.
- Lempken, W., van Trung, T., Magliveras, S. S., Wandi, W. (2009). A public key cryptosystem based on non-abelian finite groups. J. Cryptology 22(1):62–74. DOI: 10.1007/s00145-008-9033-y.
- Li, C. H., Xia, B. (2019). Factorizations of almost simple groups with a factor having many non-solvable composition factors. J. Algebra 528:439–473. DOI: 10.1016/j.jalgebra.2019.03.012.
- Li, C. H., Xia, B. (2022). Factorizations of almost simple groups with a solvable factor, and Cayley graphs of solvable groups. Mem. Amer. Math. Soc. 279(432):iv + 99 pp.
- Liebeck, M. W., Praeger, C. E., Saxl, J. (1990). The maximal factorizations of the finite simple groups and their automorphism groups. Mem. Amer. Math. Soc. 86(432):iv + 151 pp. DOI: 10.1090/memo/0432.
- Magliveras, S. S. (1986). A cryptosystem from logarithmic signatures of finite groups. In: Proceedings of the 29th Midwest Symposium on Circuits and Systems, pp. 972–975.
- Magliveras, S. S. (2002). Secret and public-key cryptosystems from group factorizations. Tatra Mt. Math. Publ. 25:1–12.
- Magliveras, S. S., Stinson, D. R., van Trung, T. (2002). New approaches to designing public key cryptosystems using one-way functions and trapdoors in finite groups. J. Cryptology 15(4):285–297. DOI: 10.1007/s00145-001-0018-3.
- Miller, G. A. (1913). The product of two or more groups. Bull. Amer. Math. Soc. 19:303–310. DOI: 10.1090/S0002-9904-1913-02335-8.
- Rahimipour, A. R., Ashrafi, A. R., Gholami, A. (2018). The existence of minimal logarithmic signatures for some finite simple groups. Exp. Math. 27(2):138–146. DOI: 10.1080/10586458.2016.1235997.
- Rahimipour, A. R. (2021). Exact factorizations of Sporadic simple groups. Exp. Math. 30:441–446. DOI: 10.1080/10586458.2018.1556137.
- Szép, J. (1950). On the structure of groups which can be represented as the product of two subgroups. Acta Sci. Math. (Szeged) 12:57–61.
- Szép, J. On factorisable simple groups. Acta Sci. Math. (Szeged) 14:22.
- Zappa, G. (1942). Sulla costruzione dei gruppi prodotto di due dati sottogruppi permutabili tra loro. (Italian), Atti Secondo Congresso Un. Mat. Ital., Bologna, 1940. Rome: Edizioni Cremonese, pp. 119–125.