Mediterr. j. math. 4 (2007), 109–117 1660-5446/010109-9, DOI 10.1007/s00009-007-0106-1 c 2007 Birkh¨
auser Verlag Basel/Switzerland

Mediterranean Journal of Mathematics

R´edei’s Theorem is a Consequence of its (p, p) Special Case and Haj´ os’ Theorem Kereszt´ely Corr´adi and S´andor Szab´o Abstract. In the paper we reduce R´edei’s theorem to its (p, p) special case using Haj´ os’ theorem. The paper also contains a proof for the (p, p) case. Mathematics Subject Classification (2000). Primary 20K01; Secondary 52C22. Keywords. Factoring of finite abelian groups, Haj´ os’ theorem, R´edei’s theorem.

1. Introduction Let G be a finite abelian group. We use multiplicative notations in connection with abelian groups. We call the group operation multiplication and we call the neutral element identity element and we denote it by e. Let G be a finite abelian group and let A1 , . . . , An be subsets of G. If the product A1 · · · An is direct and is equal to G, then we say that G is factored into its subsets A1 , . . . , An . We say that a subset A of G is cyclic if it is in the form A = {e, a, a2 , . . . , ar−1 }. Clearly A is a subgroup of G if ar = e. In 1941 G. Haj´os [1] proved that if a finite abelian group is factored into cyclic subsets, then at least one of the factors is a subgroup. A subset A of G is called normalized if e ∈ A. In 1965 L. R´edei [3] proved that if a finite abelian group is a direct product of normalized subsets of prime cardinalities, then at least one of the factors is a subgroup. If a group is a direct product of cyclic subgroups of orders q1 , . . . , qs , then we say that G is of type (q1 , . . . , qs ). Let p be a prime. A group of type (p, . . . , p) is called an elementary p-group. The special case of R´edei’s theorem when the group G is of type (p, p) has many interesting applications. (See [2], [6].) The main result of this paper is that R´edei’s theorem can be derived from this (p, p) special case using Haj´ os’ theorem. There are two excellent proofs for the (p, p) special case of R´edei’s theorem in [2] and [7] respectively. We present here another proof which seems better motivated than the known proofs.

110

K. Corr´ adi and S. Szab´ o

Mediterr. j. math.

2. The (p, p) case Let p be a prime and let G be an elementary abelian group with |G| = p2 and let A be a normalized subset of G that has p elements. The set of subgroups of G of order p will be denoted by S. Further let SA be the set of all S ∈ S for which ai ≡ aj

(mod S)

(2.1)

for each pair of distinct elements ai , aj in A. Clearly, (2.1) is equivalent to the assertion that a−1 i aj ∈ S, or (2.1) is equivalent to the fact that AS = G is a factorization of G. We can see that SA = SB where B = Aa−1 for each a ∈ A. Lemma 2.1. Let A be a normalized subset of G with |A| = p and let R ∈ S. If p > 2 and |A \ R| < |SA |, then A = R. Proof. Assume, on the contrary that, there is an a ∈ A \ R. Let SA = {Si : 1 ≤ i ≤ u}. Note that R ∈ SA and consequently A and R are both complete set of representatives in G modulo Si for each i, 1 ≤ i ≤ u. There are uniquely determined elements ri ∈ R \ A such that a ≡ ri (mod Si ). Since |R \ A| < u, there are distinct indices k, l with rk = rl . Then a ≡ rk ark−1

and so rk ∈ R.

(mod Sk ), a ≡ rk

(mod Sl )

∈ Sk ∩ Sl = {e} gives that a = rk ∈ R, which is a contradiction since


Lemma 2.2. Let A, B be normalized subsets of order p in G and let G = AB be a factorization of G. Then |SA | + |SB | ≥ |S|. Proof. We show that S = SA ∪ SB . Assume, on the contrary that, there is an S ∈ S such that S ∈ SA and S ∈ SB . There are ai , aj ∈ A, bk , bl ∈ B such that −1 a−1 i aj , bk bl ∈ S \ {e}. Therefore there is an integer r such that 1 ≤ r ≤ p − 1 and −1 r bk bl = (a−1 i aj ) . Set −1 r C = a−1 i A, D = bk B, F = {c : c ∈ C}. −1 we get that G = CD is a Multiplying the factorization G = AB by a−1 i bk factorization of G. By Proposition 3 of [4] in this factorization the factor C can be replaced by F to get the factorization G = F D of G. On the other hand −1 r
{e} = F ∩ D, a−r i aj ∈ F , bk bl ∈ D yield a contradiction.

We are now in position to state the main result of this section. Theorem 2.3. Let p be an odd prime and let G be an elementary abelian group of order p2 . If G = AB is a normalized factorization of G, where |A| = |B| = p, then A or B is a subgroup of G. Proof. Let SA = {Si : 1 ≤ i ≤ v}. By Lemma 2.2, we may assume that v ≥ (p + 1)/2. We choose elements c, d in G such that S1 = c , G = c, d , Si = cdl(i) , 1 ≤ i ≤ v,

Vol. 4 (2007)

R´edei’s theorem

111

0 = l(1) < · · · < l(v) ≤ p − 1. Let A have the form

A = {cm(j) dj : 0 ≤ j ≤ p − 1}, where m(0) = 0. Since A is a complete set of representatives in G modulo Si for each i, 1 ≤ i ≤ v it follows that {j − l(i)m(j) : 1 ≤ j ≤ p − 1}

is a reduced residue system modulo p for each i, 1 ≤ i ≤ v. Let us define t(j) by m(j) ≡ jt(j) (mod p) for 1 ≤ j ≤ p − 1. Let u(1) < · · · < u(w) be all the distinct elements among t(1), . . . , t(p − 1) and let Js = {j : t(j) = u(s)}. Clearly the sets J1 , . . . , Jw are disjoint and |J1 | + · · · + |Jw | = p − 1. Set j j As = {(ct(j) d) : j ∈ Js } = {(cu(s) d) : j ∈ Js }, Rs = cu(s) d . One can see that |A ∩ Rs | = |As | + 1 = |Js | + 1, and S1 , . . . , Sv , R1 , . . . , Rw are distinct elements of S. Hence v + w ≤ p + 1. Let p be a prime. The modulo p residue classes of the integers form a field of p elements. We denote this field by GF(p). We introduce the following polynomials with coefficients in GF(p). p−1
[j(1 − t(j)z)]µ , 1 ≤ µ ≤ v − 1. Fµ (z) = j=1

Note that Fµ (z) is the zero polynomial for each µ, 1 ≤ µ ≤ v − 1 since l(1), . . . , l(v) are distinct roots of these polynomials. So p−1 w 


λ λ 0= j µ (t(j)) = j µ (u(s)) s=1 j∈Js

j=1

for each 0 ≤ λ ≤ µ ≤ v − 1. Now v + w ≤ p + 1, v ≥ (p + 1)/2 imply that w ≤ (p + 1)/2. Consider the system of linear equations w
[u(s)]λ xs = 0, 0 ≤ λ ≤ w − 1. s=1

The determinant of the system is the Vandermonde determinant   1 u(1) . . . [u(1)]w−1 1 u(2) . . . [u(2)]w−1 

   = u(i) − u(j) = 0. det  .  . . . .. .. ..   .. 1≤j
(2.2)

112

K. Corr´ adi and S. Szab´ o

Mediterr. j. math.

This holds for each µ, w − 1 ≤ µ ≤ v − 1. In particular it holds for µ = (p − 1)/2. This gives that
j  = 0, 1 ≤ s ≤ w. p j∈Js

The terms of the sums are Legendre symbols and we used the Euler criterion on quadratic residues to get the sums. As the value of a Legendre symbol is ±1, it follows that each |Js | is even. Consequently w ≤ (p − 1)/2. If |Js | = 2, say Js = {k, l}, then using (2.2) in the special cases µ = (p − 1)/2, µ = (p − 3)/2 we get k   l  k1  l 1 + = 0, + =0 p p p k p l which in turn imply the contradiction that k = l. Thus |Js | ≥ 4 for each s, 1 ≤ s ≤ w. (This and Lemma 2.1 take care of the p ≤ 7 cases.) It follows that w ≤ (p − 1)/4. If w ≥ 4, then |Js | ≤ (p − 1)/4 for some s, 1 ≤ s ≤ w. For the sake of definiteness assume that |J1 | = f ≤ (p − 1)/4. Then
j µ = 0, w − 1 ≤ µ ≤ v − 1. j∈J1

Consider the system of equations
j µ xj = 0, w − 1 ≤ µ ≤ w + f − 2. j∈J1

The determinant of the system is not zero and so the system has only the trivial solution xj = 0, j ∈ J1 . On the other hand xj = 1, j ∈ J1 is a solution of the system. This contradiction forces w ≤ 3. If w = 3, then the equations in (2.2) hold for 2 ≤ µ ≤ (p− 1)/2. If p ≥ 7, then (p − 3)/2 ≥ (p − 1)/3 and there is an s with |Js | ≤ (p − 1)/3. Then the previous argument can be repeated and leads to a contradiction. So w ≤ 2 holds for p ≥ 7. Then J1 or J2 has at least (p − 1)/2 elements and so Lemma 2.1 gives that A is a subgroup of G.


3. Reduction of the general case to the (p, p) case Let G be a finite abelian group. Let a ∈ G and let r be an integer for which |a| ≥ r. The subset {e, a, a2 , . . . , ar−1 } of G will be denoted by [a, r]. Theorem 3.1. Let G be a finite abelian group and let G = A1 · · · An

(3.1)

be a normalized factorization of G, where the factors have prime orders. Then one of the factors is a subgroup in G.

Vol. 4 (2007)

R´edei’s theorem

113

Proof. The case n = 1 is obvious. So we may assume that n ≥ 2 and start an induction on n. By Lemma 3 of [5] in the factorization (3.1) each Ai can be replaced by [ai , pi ], where ai ∈ Ai \ {e} and |Ai | = pi . If |ai | = pi , then [ai , pi ] is not a subgroup of G. There must exist an i such that each element of Ai \ {e} has order pi since otherwise there would be a factorization G = [a1 , p1 ] · · · [an , pn ] without subgroup factors. But by Haj´ os’ theorem this is not possible. We may assume that A1 is a factor such that each element in A1 \ {e} has order p1 . Choose an a1 ∈ A1 \ {e} and set H1 = a1 . By Lemma 3 of [5] in the factorization (3.1) the factor A1 can be replaced by H1 to get the factorization G = H1 A2 · · · An . Using this we obtain the factorization G/H1 = (A2 H1 )/H1 · · · (An H1 )/H1 . There is a permutation B1 , B2 , . . . , Bn of the factors H1 , A2 , . . . , An such that B1 = H1 and the products B1 , B1 B2 , . . . , B1 B2 · · · Bn form an ascending chain of subgroups of G. By suitable choice of the indexing in (3.1) we may assume that B2 = A2 , . . . , Bn = An . Consider the subgroup M = H1 A2 · · · An−1 , that is, the penultimate member of the mentioned chain. Note that H1 , A2 , . . . , An−1 are all subsets of M . If A1 ⊂ M , then M = A1 A2 · · · An−1 is a factorization of M . By the inductive assumption one of the factors A1 , . . . , An−1 is a subgroup of M and so is of G. For the rest of the proof we assume that A1 ⊂ M . From this point we have two ways to finish the proof. We give one version here and present the second argument in the Appendix. The factor A1 can be represented in the form A1 = {e, x, x2 d2 , . . . , xp−1 dp−1 }, where H1 = x , |x| = p = p1 , d2 , . . . , dp−1 ∈ G and each |di | is either 1 or p. As A1 ⊂ M , we get {d2 , . . . , dp−1 } ⊂ M . In particular pn = |An | = |G : M | = p1 = p. In the factorizations G = A1 A2 · · · An , G = H1 A2 · · · An the factor An can be replaced by An = [y, pn ] = [y, p] for each y ∈ An \ {e} to get the factorizations G = A1 A2 · · · An−1 An , G = H1 A2 · · · An−1 An . M An

(3.2) An

are factorizations of G. So is a complete Observe that G = M An , G = set of representatives in G modulo M . We may assume that dr ∈ M for some r, 2 ≤ r ≤ p − 1. So dr ≡ y s (mod M ) for some unique s, 1 ≤ s ≤ p − 1. There is a unique t such that st ≡ 1 (mod p), 1 ≤ t ≤ p − 1. Since |G : M | = p and since

114

K. Corr´ adi and S. Szab´ o

Mediterr. j. math.

[y, p] is a complete set of representatives in G modulo M , it follows that dtr ≡ y (mod M ). By Proposition 3 of [4], in the factorizations (3.2) we may replace A1 by At1 to get the factorizations G = At1 A2 · · · An−1 An , G = H1 A2 · · · An−1 An . Here At1 has the following form: At1 = {e, xt , x2t dt2 , . . . , x(p−1)t dtp−1 }. There are elements u2 , . . . , up−1 in An such that −1

(x2t dt2 )

−1

∈ M u2 , . . . , (x(p−1)t dtp−1 )

∈ M up−1 ,

that is, x2t dt2 u2 ∈ M, . . . , x(p−1)t dtp−1 up−1 ∈ M. Set B = {e, xt , (x2t dt2 )u2 , . . . , (x(p−1)t dtp−1 )up−1 }. Note that B ⊂ M and that the product BA2 · · · An−1 is a factorization of M . Indeed, the products coming from BA2 · · · An−1 are among the products coming from At1 A2 · · · An−1 An and this product is direct. From the factorization M = BA2 · · · An−1 by the inductive assumption it follows that at least one of the factors is a subgroup of M . We may assume that B is a subgroup since otherwise there is nothing to prove. Thus B = H1 = x . For each i, 2 ≤ i ≤ p − 1 there is a j, 0 ≤ j ≤ p − 1 such that xit dti ui = xj . From −1 ui = xj (xit dti ) , |x| = p, dpi = e it follows that upi = e. In particular ur = y has order p. Since y ∈ An \ {e} was an arbitrary element we get that each element in An \ {e} has order p. From ui ∈ [y, p] we get that ui ∈ y ⊂ x, y . As t and p are relatively prime di ∈ x, y and so A1 ⊂ x, y . If An ⊂ x, y , then there is a z ∈ An \ {e} such that z ∈ x, y . Repeating the previous argument with z in place of y we get that A1 ∈ x, z . Then A1 ⊂ x, y ∩ x, z = x , that is, A1 is a subgroup of G. Therefore, we are left with the case An ⊂ x, y . In this case the product A1 An is a factorization of the elementary abelian group
x, y , which has order p2 .

4. A localization principle A subset A of an abelian group G is called periodic if there is a g ∈ G such that Ag = A and g = e. The element g is called a period of A. One can verify that all the periods of A augmented with e form a subgroup H of G. We call H the subgroup of periods of A. Note that there is a subset B of G such that the product HB is direct and gives A. If A is normalized, then H ⊂ A holds. The next result can help to localize a subgroup factor in R´edei’s theorem.

Vol. 4 (2007)

R´edei’s theorem

115

Theorem 4.1. Let G be a finite abelian group and let G = A1 · · · An be a normalized factorization of G, where each |Ai | is a prime. If a partial product A1 · · · Am is periodic, then one of its factors is a subgroup of G. Proof. If m = n, then by R´edei’s theorem one of the factors A1 , . . . , An is a subgroup of G. If m = 1, then A1 is a subgroup of G. Assume therefore that 2 ≤ m ≤ n − 1 and start an induction on m. Let D be the subgroup of periods of A1 · · · Am . Then D = {e} and D ⊂ A1 · · · Am . From the factorization G = A1 · · · An by R´edei’s theorem some Ai is a subgroup of G. We are done if i ≤ m so we assume that i ≥ m + 1. We may assume that L = An is a subgroup of G since this is only a matter of indexing the factors. First we prove that if none of A1 , . . . , Am is a subgroup of G, then there is permutation B1 , . . . , Bm of A1 , . . . , Am such that L, LB1 , . . . , LB1 · · · Bm is an ascending chain of subgroups in G. For each permutation B1 , . . . , Bm of A1 , . . . , Am let i be the maximal index for which L, LB1 , . . . , LB1 · · · Bi is an ascending chain of subgroups in G. (If i = 0, then the chain consists of only L.) Fix i and assume that this maximal i occurs by the original indexing. The product LB1 · · · Bi is a subgroup of G and the product B1 · · · Bi is not periodic if i ≤ m − 1 since otherwise the induction assumption would give a subgroup among B1 , . . . , Bi . Set H = LB1 · · · Bi . From the factorization G = A1 · · · An by considering the factor group we get the factorization G/H =

n−1

(Aj H)/H.

j=i+1

The product (Ai+1 H)/H · · · (Am H)/H (4.1) is periodic in G/H. This is because D ∩ H = {e} and so (DH)/H is a subgroup of the group of periods of (4.1) in G/H. Note that (DH)/H is isomorphic to D and D is not equal to {e}. By the inductive assumption one of the factors in (4.1) is periodic, say (Ai+1 H)/H is periodic. But then LB1 · · · Bi Ai+1 is a subgroup in G. This contradicts the maximality of i. We may assume that L, LA1 , . . . , LA1 · · · An−1 is an ascending chain of subgroups of G and G = LA1 · · · An−1 .  Let l ∈ L\{e}, d ∈ D\{e}. Assume that |d| is a prime. Set C = L\{l} ∪{ld}. We can choose d such that C is not a subgroup except when |L| = 2 and D is an elementary 2-group. Note that G = CA1 · · · An−1 is a factorization. By R´edei’s theorem one of the factors is a subgroup. Only C can be a subgroup and so |L| = 2, D is an elementary 2-group and |d| = 2. Let M = LA1 · · · An−2 . One can verify

116

K. Corr´ adi and S. Szab´ o

Mediterr. j. math.

by induction that d ∈ M . Hence |An−1 | = |G : M | = 2. From the factorization G = CA1 · · · An−1 we get that CAj is a subgroup for some j, 1 ≤ j ≤ n − 1. If j = n − 1, then using C ∩ M = {e} one gets that Aj = M ∩ CAj is a subgroup of G. This is a contradiction so CAn−1 is a subgroup and |CAn−1 | = 4 holds. From the factorization G = M An−1 it follows that M ∩ CAn−1 is a subgroup of order 2. As C ∩ M = {e}, it follows that M ∩ CAn−1 = C and we get that CAn−1 is an
elementary group. Consequently An−1 is a subgroup of G.

5. Appendix Second proof of Theorem 2. We have seen in the first proof that if G = A1 · · · An is a normalized factorization of G, where each |Ai | = pi is a prime, then there is a factor, say A1 such that the elements of A1 \ {e}, have order p1 . Setting H1 = x , where x ∈ A1 \ {e} we get the factorization G = H1 A2 · · · An and H1 , H1 A2 , . . . , H1 A2 · · · An are subgroups of G. The penultimate member M = H1 A2 · · · An−1 satisfies A1 ∈ M . Set K1 = y , where y ∈ A1 \ M . From the factorization G = M K1 we get pn = |An | = |G : M | = |K1 | = p1 . We may repeat the previous procedure with K1 in place of H1 . This provides that K1 Ai is a subgroup of G for some i, 2 ≤ i ≤ n. If i = n, then Ai = M ∩ K1 Ai is a subgroup of G. So we may assume that K1 An is a subgroup of G. Now |K1 An | = p1 pn = p21 . If K1 An is cyclic, then its unique subgroup of order p1 must be K1 and we get that K1 ⊂ M , which is a contradiction. Note that G = M K1 An , |G : M | = p1 and |K1 An | = p21 . So we can see that K1 An is an elementary group of order p21 . In particular each element of An \ {e} has order p1 . Set L1 = u , where u ∈ An \ {e}. Then G = A1 · · · An−1 L1 is a factorization of G. Now L1 Aj is a subgroup of G for some j, 1 ≤ j ≤ n − 1. If j = 1, then Aj = M ∩ L1 Aj is a subgroup of G. We may assume that L1 A1 is a subgroup of G. Set M1 = v , where v ∈ An \ L1 . (If there is no such v, then p1 = 2 and A1 is a subgroup of G.) It follows that M1 A1 is a subgroup of G. If there is a v ∈ An \ L1 with M1 A1 = L1 A1 , then A1 = L1 A1 ∩ M1 A1 is a subgroup of G. We are left with the case when L1 A1 = A1 An is a factorization of the elementary abelian group L1 A1 .

References ¨ [1] G. Haj´ os, Uber einfache und mehrfache Bedeckung des n-dimensionalen Raumes mit einem W¨ urfelgitter, Math. Z. 47 (1941), 427–467. [2] L. Lov´ asz and A. Schrijver, Remarks on a theorem of R´edei, Studia Sci. Math. Hungar. 16 (1983), 449–454. [3] L. R´edei, Die neue Theorie der endlichen abelschen Gruppen und Verallgemeinerung des Hauptsatzes von Haj´ os, Acta Math. Sci. Hungar. 16 (1965), 329–373.

Vol. 4 (2007)

R´edei’s theorem

117

[4] A. D. Sands, Replacement of factors by subgroups in the factorization of abelian groups, Bull. London Math. Soc. 32 (2000), 297–304. [5] S. Szab´ o, Factoring an infinite abelian group by subsets, Periodica Math. Hungar. 10 (2000), 135–140. [6] T. Sz˝ onyi, Around R´edei’s theorem, Discrete Math. 208/209 (1999), 557–575. [7] E. Wittmann, Einfacher Beweis des Hauptsatzes von Haj´ os-R´edei f¨ ur elementare Gruppen von Primzahlquadratordnung, Acta Math. Acad. Sci Hungar. 20 (1969), 227– 230. Kereszt´ely Corr´ adi Department of General Computer Technics E¨ otv¨ os University P´ azm´ any P. s´et´ any 1/c H-1117 Budapest Hungary e-mail: [email protected] S´ andor Szab´ o Institute of Mathematics and Informatics University of P´ecs Ifj´ us´ ag u. 6 H-7624 P´ecs Hungary e-mail: [email protected] Received: March 31, 2005 Revised: April 13, 2006 Accepted: April 30, 2006