Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 35 (1994), No. 1, 85-89.

Factoring by Nonsubgroup Factors

Keresztély Corrádi and Sándor Szabó

Department of Computer Sciences, Eötvös University Budapest H–1088 Budapest, Hungary Department of Mathematics, University of Bahrain P. O. Box 32038, State of Bahrain

Abstract. For each finite abelian group we determine the numbers q_{1},…, q_{n} such that if the group is a direct product of subsets of cardinalities q_{1},…, q_{n} and each subset contains the identity element of the group, then at least one of the subsets is in fact a subgroup of the group. MSC 1991: Primary 20K01; Secondary 52C22

1. Introduction

Let G be a finite abelian group written multiplicatively with identity element e. Let A_{1},…, A_{n} be subsets of G. If each element g of G is uniquely expressible in the form

g = a_{1} ⋯ a_{n}, a_{1} ∈ A_{1},…, a_{n} ∈ A_{n},

then we say that G is factored into the product of the subsets A_{1},…, A_{n}. We also can express this fact such that the product A_{1} ⋯ A_{n} is direct and gives G. If e ∈ A_{1} ∩⋯∩A_{n}, then the factorization and the subsets are called normed. If G is a direct product of cyclic subgroups of order t_{1},…, t_{s}, then we say that G is of type (t_{1},…, t_{s}). We would like to point out that the type of a group is not always uniquely determined. For instance (6) and (2, 3) are types of the cyclic group of order six.

Direct product of subgroups is the most well-know instance of factorization of a finite abelian group. However, more genral factorizations occur naturally. These factorizations are in an intimate connection with certain type of high dimensional tilings. Further factorizations play role in estimating Ramsey numbers of graphs and they used in coding theory as well. The result of this paper is not motivated directly by these applications. Our main stimulus was the following theorem of L. Rédei.

In each normed factorization of a finite abelian group by subsets of prime cardinalities at least one of the factors must be a subgroup of the group.

The next example shows that Rédei’s theorem not necessarily holds for normed factorizations with general factors. Let G be the cyclic group of order 8 with generator x and let

A_{1} = {e, x^{2}}, A_{2} = {e, x, x^{4}, x^{5}}.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}1994 Heldermann Verlag, Berlin

Now G = A_{1}A_{2} is a normed factorization of G and the factors A_{1} and A_{2} are not subgroups of G.

However, for finite groups of type (2,…, 2) a sharper result than Rédei’s theorem holds. Sands and Szabó proved that in each factorization of a finite group of type (2,…, 2) by subsets of cardinality four at least one of the factors is a subgroup of the group.

We set forth the following problem. A group G of type (t_{1},…, t_{s}) is given. For which integers q_{1},…, q_{n} does it follow that in each normed factorization G = A_{1} ⋯ A_{n}, with |A_{1}| = q_{1},…, |A_{n}| = q_{n} at least one of the factors A_{i} is a subgroup of G.

The answer which is the content of this paper is the next theorem.

Theorem 1. Let G = A_{1} ⋯ A_{n} be a normed factorization of the finite abelian group G, where |A_{1}| = q_{1} …, |A_{n}| = q_{n}. In the following cases at least one of the factors must be a subgroup of G.

(1) G is of type (2,…, 2) and either q_{i} = 2 for some i, 1 ≤ i ≤ n or q_{1} = ⋯ = q_{n} = 4.

(2) G is of type (2,…, 2, 2p), where p is a prime and q_{1},…, q_{n} is a rearrangement of 2,…, 2, 2p or 2,…, 2, p. (The p = 2 case is included.)

(3) G is not of the types (2,…, 2) and (2,…, 2, 2p), where p is a prime and each q_{i} is a prime.

In all the other cases there are normed factorizations without subgroup factors.

If H_{1} is a subgroup of G and if the normed subset A_{1} is a complete set of representatives modulo H_{1}, then G = A_{1}H_{1} is a normed factorization of G. Similarly, if H_{2} is a subgroup of H_{1} and if the normed subset A_{2} is a complete set of representatives modulo H_{2}, then H_{1} = A_{2}H_{2} is a normed factorization of H_{1} and so G = A_{1}A_{2}H_{2} is a normed factorization of G. In this way we can construct a large stock of factorizations of G. Note that in the resulted factorizations at least one of the factors is always a subgroup of G. On the other hand by Theorem 1 in cases (1), (2), and (3) G does not have other type of normed factorizations. Shortly, there is a straightforward way to construct normed factorizations of G and by Theorem 1 in cases (1), (2), and (3) there are no further normed factorizations of G.

2. Factoring with subgroup factors

In this section we will use characters of finite abelian groups. If A is a subset and χ is a character of G then we denote the sum

∑_{a∈A} χ(a)

by χ(A). If the product A_{1} ⋯ A_{n} is direct, then

χ(A_{1} ⋯ A_{n}) = χ(A_{1}) ⋯ χ(A_{n}).

If χ is not the principal character of G, then χ(G) = 0. Therefore if χ is not the principal character of G, then from the factorization G = A_{1} ⋯ A_{n} it follows that χ(A_{i}) = 0 for some i, 1 ≤ i ≤ n.

Lemma 1. Let G be a group of type (2,…, 2, 2p), where p is a prime. If G = A_{1} ⋯ A_{n} is a normed factorization of G such that |A_{1}| = ⋯ = |A_{n−1}| = 2 and |A_{n}| = 2p, then at least one of the factors A_{i} is a subgroup of G.

Proof. Now G is a direct product of subgroups of types (2,…, 2) and (2p). Let x be a generator of the (2p) type direct factor. Let A_{i} = {e, a_{i}} for each i, 1 ≤ i ≤ n − 1 and consider a character χ of G for which χ(x) is a primitive 2pth root of unity. Since χ is not the principal character of G, χ(A_{i}) = 0 for some i, 1 ≤ i ≤ n. If 1 ≤ i ≤ n − 1, then 0 = χ(A_{i}) = 1+χ(a_{i}), that is, χ(a_{i}) = −1 and so a_{i} is a second order element of G. Hence A_{i} is a subgroup of G. Thus suppose that χ(A_{n}) = 0 for each character χ of G for which χ(x^{2}) is a primitive pth root of unity. Now by Theorem 1 of [2] A_{n} can be factored in the form A_{n} = ⟨x^{2}⟩{e, a}. As a = bx^{2}, where b is a second order element, A_{n} is a subgroup of G.

We are now in position to prove the first half of the main result. Consider the normed factorization G = A_{1} ⋯ A_{n} of the finite abelian group G.

If G is of type (2,…, 2) and if |A_{i}| = 2 for some i, 1 ≤ i ≤ n, then A_{i} is a subgroup of G since each element of G \ {e} is of second order.

If G is of type (2,…, 2) and |A_{1}| = ⋯ = |A_{n}| = 4, then by the quoted result of Sands and Szabó one of the factors A_{i} is a subgroup of G.

If G is of type (2,…, 2, 2p), where p is a prime and |A_{1}| = ⋯ = |A_{n−1}| = 2 and |A_{n}| = 2p, then by Lemma 1 one of the factors A_{i} is a subgroup of G.

Finally, if each |A_{i}| is a prime, then by Rédei’s theorem one of the factors A_{i} is a subgroup of G no matter what is the type of G.

3. Factoring without subgroup factors

Let G be a finite abelian group and q_{1},…, q_{n} be integers such that q_{1} ⋯ q_{n} = |G|, q_{1} ≥ 2,…, q_{n} ≥ 2 and q_{n} is composite, say q_{n} = uv, u ≥ 2 and v ≥ 2. In order to construct a normed factorization G = A_{1} ⋯ A_{n} with |A_{1}| = q_{1},…, |A_{n}| = q_{n} consider a chain of subgroups

{e} = K_{0} ⊂ K_{1} ⊂ ⋯ ⊂ K_{n} ⊂ K_{n+1} = G  (1)

such that

|K_{1} : K_{0}| = u, |K_{2} : K_{1}| = q_{1},…, |K_{n} : K_{n−1}| = q_{n−1}, |K_{n+1} : K_{n}| = v.

Choose B_{i} to be a complete set of representatives modulo K_{i} in K_{i+1} for each i, 1 ≤ i ≤ n such that e ∈ B_{i}. Clearly K_{i+1} = K_{i}B_{i} is a normed factorization of K_{i+1} for each i, 1 ≤ i ≤ n. Hence

G = K_{1}B_{1}B_{2} ⋯ B_{n} = B_{1}B_{2} ⋯ B_{n−1}(K_{1}B_{n})

is a normed factorization of G and

|B_{1}| = q_{1},…, |B_{n−1}| = q_{n−1}, |K_{1}B_{n}| = uv = q_{n}.

There is a great degree of freedom when choosing B_{i} and we try to exploit this to avoid the occurrence of subgroups among the factors.

Lemma 2. Let T be a finite abelian group and let H, L be subgroups of T with L ⊂ H and L ≠ H. If |T : H| ≥ 3 or if |T : H| = 2 and H/L is not of type (2,…, 2), then there is a complete set of representatives B of T modulo H such that e ∈ B and the product LB is direct and is not a subgroup of T.

Proof. First consider the case |T : H| ≥ 3. Let B be a complete set of representatives modulo H in T with e ∈ B. If LB is not a subgroup of T, then we are done. Thus suppose that LB = M is a subgroup of T. There are elements b ∈ B \ {e} and h ∈ H \ L. Let C = {bh} ∪ (B \ {b}). Clearly C is also a complete set of representatives modulo H in T. If LC is not a subgroup of T we are done. Thus suppose that LC = N is a subgroup of T. Then M ∩ N = LB ∩ LC = L(B ∩ C) is a subgroup of M and so |M ∩ N| divides |M|. As |M ∩ N| = |L|(|B| − 1) and |M| = |L||B|, we have |B| − 1 divides |B|. Thus |B| = 2. On the other hand |T : H| = |B| = 2 which is a contradiction.

Turn to the case when H/L is not of type (2,…, 2). As before we are done unless |B| = 2. If b^{2} ∉ L, then LB is not a subgroup of T and we are done. Thus we may assume that b^{2} ∈ L. As H/L is not of type (2,…, 2), h can be chosen such that h^{2} ∉ L. If LC = L{e, bh} is a subgroup of T, then (bh)^{2} ∈ L. Since (bh)^{2} = b^{2}h^{2} and b^{2} ∈ L, we have that h^{2} ∈ L which is a contradiction.

We are now in position to prove the second half of the main result. In order to construct nonsubgroup normed factors B_{1},…, B_{n−1}, K_{1}B_{n} we consider a chain of subgroups (1). Then we will apply Lemma 2 with the choice

L = K_{0} = {e},  H = K_{i},  T = K_{i+1},  1 ≤ i ≤ n − 1

and

L = K_{1},  H = K_{n},  T = K_{n+1} = G.

Let G be a finite group of type (2,…, 2). Since the case when q_{i} = 2 for some i, 1 ≤ i ≤ n is settled suppose that q_{1} ≥ 4,…, q_{n} ≥ 4. Since the case q_{1} = ⋯ = q_{n} = 4 is also settled we may assume that q_{i} ≥ 8 for some i, 1 ≤ i ≤ n, say q_{n} ≥ 8. Let u = 2 and v = q_{n}/2. Now |K_{i+1} : K_{i}| ≥ 4 for each i, 1 ≤ i ≤ n and so Lemma 2 is applicable.

Let G be of type (2,…, 2, p), where p is an odd prime. The case when q_{1},…, q_{n} is a rearrangement of 2,…, 2, 2p is settled so we assume that this is not the case. We may assume that q_{n} = 2^{t} or q_{n} = 2^{t}p, where t ≥ 2 since this is only a matter of indexing the numbers q_{1},…, q_{n}.

First consider the case q_{n} = 2^{t}. Let u = 2 and v = q_{n}/2. There is a q_{i} that is divisible by p. Assume that p divides q_{1}. Now K_{2},…, K_{n} and K_{n+1}/K_{1} are not of type (2,…, 2) and so Lemma 2 is applicable.

Secondly consider the case q_{n} = 2^{t}p, t ≥ 2. Let u = p and v = 2^{t}. Now K_{2} …, K_{n} are not of type (2,…, 2) and |K_{n+1} : K_{n}| = 2^{t} ≥ 4. Hence Lemma 2 is applicable.

Let G be of type (2,…, 2, 4). The case when q_{1},…, q_{n} is a rearrangement of 2,…, 2, 4 is settled so we assume that q_{i} ≥ 8 for some i, 1 ≤ i ≤ n or q_{i} = 4 and q_{j} = 4 for some i and j, 1 ≤ i < j ≤ n.

First assume that q_{1} = 4 and q_{n} = 4. Let u = 2 and v = 2. Let K_{1} be of type (2) and be a direct factor of K_{n+1} = G. As G is of type (2,…, 2, 4) and |K_{2}| = 8, we can choose K_{2},…, K_{n} such that they are of type (2, 4) or (2,…, 2, 4) Hence K_{2} …, K_{n} and K_{n+1}/K_{1} are not of type (2,…, 2) and so Lemma 2 is applicable.

Secondly assume that q_{n} ≥ 8. Let u = 2 and v = q_{n}/2. Let K_{1} of type (2) such that K_{1} is the unique subgroup of the (4) type direct factor of K_{n+1} = G. As G is of type (2,…, 2, 4) we can choose K_{2},…, K_{n} such that they are of types (4) or (2,…, 2, 4). Now K_{2},…, K_{n} are not of type (2,…, 2) and |K_{n+1} : K_{1}| = q_{n}/2 ≥ 4. Therefore Lemma 2 is applicable.

Let G be a finite abelian group not of types (2,…, 2) and (2,…, 2, 2p), where p is a prime. The case when q_{1},…, q_{n} are primes is settled by Rédei’s theorem so we assume that some q_{i} is composite, say q_{n} = uv, u ≥ 2 and v ≥ 2.

First suppose that some q_{i}, 1 ≤ i ≤ n − 1 is divisible by an odd prime. We may assume that this is q_{1}. Now K_{2},…, K_{n} and K_{n+1}/K_{1} are not of type (2,…, 2) and so Lemma 2 is applicable.

Secondly suppose that q_{n} is divisible by an odd prime. We may assume that u is an odd prime. Now K_{2},…, K_{n} is not of type (2,…, 2) and as G is not of types (2,…, 2) and (2,…, 2, 2p), K_{n+1}/K_{1} is not of type (2,…, 2). Therefore Lemma 2 is applicable.

Thirdly we may assume that each q_{1},…, q_{n} is a power of two and so G is a 2-group. Let u = 2 and v = q_{n}/2. As G is not of types (2,…, 2) and (2,…, 2, 4), we can choose K_{1},…, K_{n} such that K_{1} is of type (2) and K_{2},…, K_{n} and K_{n+1}/K_{1} are not of type (2,…, 2). Therefore Lemma 2 is applicable.

This completes the proof of the main result of the paper.

References

[1] L. Rédei: Die neue Theorie der endlichen abelschen Gruppen und Verallgemeinerung des Hauptsatzes von Hajós, Acta Math. Acad. Sci. Hungar. 16 (1965), 329–373.

[2] A.D. Sands, S. Szabó: Factorization of periodic subsets, Acta Math. Hung. 57 (1991), 159–167.