INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A08

FACTORIZATIONS AND PAIGE’S THEOREM ON COMPLETE MAPS

Sándor Szabó

Institute of Mathematics and Informatics, University of Pécs, Ifjúság u. 6, 7624 Pécs, HUNGARY

                              sszabo7@hotmail.com

Received: 5/28/05, Accepted: 3/2/6, Published: 3/10/06

Abstract

A theorem of L. J. Paige on complete maps is proved using factorizations of abelian groups.

Let G be a finite abelian group written multiplicatively with identity element e. Let a_{1}, …, a_{n} be all the elements of G. A permutation b_{1}, …, b_{n} of the elements of G is called a complete permutation of G if a_{1}b_{1}, …, a_{n}b_{n} is also a permutation of the elements of G. In other words a function f : G → G is called a complete map of G if f is one-to-one and if the function g : G → G defined by g(a) = af(a), a ∈ G is also one-to-one. In 1947 L. J. Paige has proved the following result.

Theorem 1. If a finite abelian group G does not have exactly one element of order two, then G possess a complete map.

For extensions of Paige’s theorem see [1], [2] and for an application to geometry see [4], [5]. Let A_{1}, …, A_{n} be subsets of G. If each element a of G is uniquely expressible in the form

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

then we say that the equation G = A_{1} ⋯ A_{n} is a factorization of G. In this note we give a new proof for Paige’s theorem using factorizations. If a finite abelian group G is a direct product of cyclic groups of orders t_{1}, …, t_{n} respectively, then we say that G is of type (t_{1}, …, t_{n}). The order of an element a of G is denoted by |a| and ⟨a⟩ stands for the span of a.

Proof. We divide the proof into smaller steps.

(1) A group of type (2, 2, 2) has a complete map.

In order to prove this claim Let G be a group of type (2, 2, 2) with basis elements x, y, z, where |x| = |y| = |z| = 2. Table 1 shows that G has a complete map.

(2) A group of type (2n, 2), where n ≥ 1 has a complete map.

\begin{matrix}a : & e & x & y & xy & z & xz & yz & xyz \\ f(a) : & e & z & xz & x & xyz & xy & y & yz \\ af(a) : & e & xz & xyz & y & xy & yz & z & x \end{matrix} ; Table 1

In order to prove the claim let G be a group of type (2n, 2), n ≥ 1. Let x, y be basis elements of G such that |x| = 2n, |y| = 2. Set

\begin{aligned}H & = ⟨x⟩, K = ⟨y⟩, M = ⟨x^{2}⟩, N = ⟨x^{n}⟩, \\ C & = \{e, x, x^{2}, …, x^{n−1}\}. \end{aligned}

We use Table 2 to show that G has a complete map.

\begin{matrix}a : & x^{2k} & x^{2k}y & x^{2k+1} & x^{2k+1}y \\ f(a) : & x^{n−k} & x^{2n−k}y & x^{n−k}y & x^{2n−k} \\ af(a) : & x^{n+k} & x^{k} & x^{n+k+1}y & x^{k+1}y \end{matrix} ; Table 2

As k runs from 0 to n − 1, the elements in the first row run over the elements of the sets M, My, Mx, Mxy respectively. Note that

G = HK

= M{e, x}{e, y} = M{e, x, y, xy}

are factorizations of G. It follows that the sets M, My, Mx, Mxy form a partition of G. Thus a runs over the elements of G. Similarly, the factorizations

G = HK

= xHK = xCNK = xC{e, x^{n}}{e, y}

give that the sets Cx, Cx^{n+1}y, Cxy, Cx^{n+1} form a partition of G. Therefore f(a) runs over the elements of G. Finally, the equations

G = HK

= H{e, y} = H ∪ Hy = H ∪ Hxy = H{e, xy} = CN{e, xy} = C{e, x^{n}}{e, xy} show that the sets Cx^{n}, C, Cx^{n+1}y, Cxy form a partition of G. It follows that af(a) runs over the elements of G. Therefore G has a complete map.

(3) Let G be a finite abelian group and let H be a subgroup of G. If both H and the factor group G/H have a complete map, then so does G. In particular, if G is the direct product of the groups H and K such that both H and K have complete maps, then so does G.

To prove the claim assume that h_{1}, …, h_{r} are all the elements of H and k_{1}, …, k_{r} is a complete permutation of H, that is, h_{1}k_{1}, …, h_{r}k_{r} are all the elements of H. Then assume that a_{1}H, …, a_{s}H are all the elements of G/H and b_{1}H, …, b_{s}H is a complete permutation of G/H. This means that a_{1}b_{1}H, …, a_{s}b_{s}H is a rearrangement of the elements of G/H. It follows that these cosets are disjoint and their union is equal to G, that is, G = {a_{1}b_{1}, …, a_{s}b_{s}}H is a factorization of G. In other words

\begin{matrix}a_{1}b_{1}h_{1}k_{1}, & … & , a_{1}b_{1}h_{r}k_{r} \\ ⋮ & ... & ⋮ \\ a_{s}b_{s}h_{1}k_{1}, & … & , a_{s}b_{s}h_{r}k_{r} \end{matrix}

are all the elements of G. Therefore G has a complete map.

(4) A group of type (2^{α(1)}, 2^{α(2)}), where α(1) ≥ α(2) ≥ 1 has a complete map.

To prove the claim let G be a group of type (2^{α(1)}, 2^{α(2)}), with α(1) ≥ α(2) ≥ 1. If α(1) = 1, then by step (2), G has a complete map. So we may assume that α(2) ≥ 2 and start an induction on α(2). Now G has a subgroup H of type (2, 2) such that the factor group G/H is of type (2^{α(1)−1}, 2^{α(2)−1}). By step (2), H has a complete map. By the inductive assumption G/H has a complete map. Therefore by step (3), G has a complete map.

(5) A non-cyclic group of type (2, …, 2) has a complete map.

In order to prove this assertion let G be a group of type (2, …, 2), where the number of 2’s is n and n ≥ 2. First let us deal with the case when n is even. The n = 2 case has already been settled in step (2). So we may assume that n ≥ 4. As G is a direct product of subgroups of types (2, 2), …, (2, 2), one can use step (3) repeatedly to show that G has a complete map. Let us turn to the case when n is odd. The n = 3 case has already been settled in step (1). We may assume that n ≥ 5. Now G is a direct product of groups of types (2, 2, 2), (2, 2), …, (2, 2) and we can use step (3) to show that G has a complete map.

(6) A group of type (2^{α(1)}, …, 2^{α(n)}), where n ≥ 3 and α(1) ≥ ⋯ ≥ α(n) ≥ 1 has a complete map.

In order to verify the claim consider a group G of type (2^{α(1)}, …, 2^{α(n)}), where n ≥ 3 and α(1) ≥ ⋯ ≥ α(n) ≥ 1. Set t = α(1) + ⋯ + α(n). If α(1) = 1, that is, if t = n, then by step (5) we are done. We may assume that α(1) ≥ 2, that is, t ≥ n + 1 and start an induction on t. Clearly G has a subgroup H of type (2, 2) such that the factor group G/H is of type (2^{α(1)−1}, 2^{α(2)−1}, 2^{α(3)}, …, 2^{α(n)}) or (2^{α(1)−1}, 2^{α(3)}, …, 2^{α(n)}) depending on whether α(2) ≥ 2 or α(2) = 1. By step (2), H has a complete map. By the inductive assumption G/H has a complete map. Finally by step (3), G has a complete map.

(7) A finite abelian group of odd order has a complete map.

Indeed, the map f : G → G defined by f(a) = a, a ∈ G is suitable.

(8) We are ready to finish the proof. Let G be a finite abelian group such that G does not have exactly one element of order two. The group G can be written uniquely as a direct product of the groups H and K such that the order of H is odd and the order of K is a power of 2. Since G does not have exactly one element of order two, K is not a cyclic group, that is, K is not of type (2^{α}). Therefore, by steps (4), (5), (6), K has a complete map. By step (7), H has a complete map. Hence by step (3), G has a complete map.

This completes the proof.

References

1. M. Hall, Jr., A combinatorial problem on abelian groups, Proc. Amer. Math. Soc. 3 (1952), 584–587.

2. M. Hall, Jr. and L. J. Paige, Complete mappings of finite groups, Pacific J. Math. 5 (1955), 541–549.

3. L. J. Paige, A note on finite abelian groups, Bulletin Amer. Math. Soc. 53 (1947), 590–593.

4. S. Szabó, A remark on regular polygons, Mat. Lapok 28 (1980), 199–202. (in Hungarian)

5. S. Szabó, On finite abelian groups and parallel edges, Mathematics Magazine, 66 (1993), 36–39.