Non-Full Rank Factorization of Finite Abelian Groups

Abstract

Tilings of p-groups are closely associated with error-correcting codes. In [1], M. Dinitz, attempting to generalize full-rank tilings of  Zn2  to arbitrary finite abelian groups, was able to show that if p 5, then Znp  admits full-rank tiling and left the case p=3, as an open question. The result proved in this paper the settles of the question for the case p=3.

Share and Cite:

Amin, K. (2017) Non-Full Rank Factorization of Finite Abelian Groups. Open Journal of Discrete Mathematics, 7, 51-53. doi: 10.4236/ojdm.2017.72005.

1. Introduction

A factorization of a finite abelian group G is a collection of subsets

A 1 , , A i , , A k of G such that each element g G can be represented in the form g = a 1 a i a k . In this case, we write G = A 1 , , A i , , A k and if each A i contains the identity element e of G , we say we have a normalized factori- zation of G .

The notion of factorization of abelian groups arose when G. Hajós [3] found the answer to “Minkowski’s conjecture” about lattice tiling of n by unit cubes or clusters of unit cubes. The geometric version of “Minkowski’s conjecture” can be explained as follows:

A lattice tiling of n is a collection { T i : i I } of subsets of n such that i I T i = n and int ( T i ) int ( T j ) = , if i j , i , j I . Two unit cubes are called twins if they share a complete ( n 1 ) -dimensional face. Minkowski was wondering if there exists a tiling of n by unit cubes such that there are no twins! Minkowski’s conjecture is usually expressed as follows:

Each lattice tiling of n by unit cubes contains twins.

As mentioned above, it was G. Hajós [3] who solved Minkowski’ conjecture. His answer was in the affirmative, after translating the conjecture into an equivalent conjecture about finite abelian groups. Its group―theoretic equivalence reads as follows:

“If G is a finite abelian group and G = A 1 , , A i , , A k is a normalized factorization of G , where each of the subsets A i is of the form { e , a , a 2 , , a k } , where k < | a | ; here | a | denotes order of a , then at least one of the subsets A i is a subgroup of G ”.

Rėdei [4] generalized Hajos’s theorem to read as follows:

“If G is a finite abelian group and G = A 1 A i A k is a normalized factori- zation of G , where each of the subsets A i contains a prime number of elements, then at least one of the subsets A i is a subgroup of G ”.

2. Preliminaries

A tiling is a special case of normalized factorization in which there are only two subsets, say A and B of a finite abelian groups G , such that G = A B is a factorization of G .

A tiling of a finite abelian group G is called a full-rank tiling if G = A B implies that A = B = G , where A denotes the subgroup generated by A . In this case, A and B are called full-rank factors of G . Otherwise, it is called a non-full-rank tiling of G . As suggested by M. Dinitz [1] and also in that of O. Fraser and B. Gordon [2] , finding answers to certain questions is sometimes easier in one context than in others. In this connection consider the group, p n viewed as a vector space of n -tuples ( x 1 , x 2 , , x n ) over p . Then subspaces correspond to subgroups. Moreover, p n is equipped with a metric, called Hamming distance d H , which is defined as follows:

For x = ( x 1 , x 2 , , x n ) and y = ( y 1 , y 2 , , y n ) ,

d H ( x , y ) = | { i : 1 i n , x i y i } | .

With respect to this metric, the sphere S ( x , e ) with center at x and radius e is the set S ( x , e ) = { y : d H ( x , y ) e } .

A perfect error-correcting code is a subset C of p n such that

x C S ( x , e ) = p n and S ( x , e ) S ( y , e ) = , if x y .

Observe that in the language of tiling, this says that p n = C S ( 0 , e ) is a factorization of p n [6] .

Factorization and Partition

Let G = A B be a factorization of a finite Abelian group G . Then the sets

{ a B : a A } form a partition of G . Also, | G | = | A | | B | , where | A | as before denotes the number of elements of A .

Definition

Let A and A be subsets of G . We say that A is replaceable by A , if whenever G = A B is a factorization of G , then so is G = A B .

Redei [4] showed that if G = A B is a factorization of G , where

A = { e , a 1 , a 2 , , a p 1 } , and p is a prime, then A is replaceable by a i , for each i , 1 i p 1 .

Definition

A subset A of G is periodic, if there exists g G , g e such that

g A = A . It is easy to see that if A is periodic, then A = H C , where H is a proper subgroup of G [5] .

Before we show the aim of this paper, we mention the following observation. If G = A B is a factorization of G , then for any a A , and b B , then so is G = a 1 A b 1 B , so we may assume all factorizations G = A B are normalized.

Theorem

Let G = 3 n and assume G = A B is a factorization of G , where | A | = 3 , then either A or B is a non-full-rank factor of G .

Proof:

Note that | G | = 3 n . We induct on n .

If n = 1 , then | B | = 1 . Thus, B is a non-full-rank factor of G .

Let n > 1 and assume the result is true for all such groups of order less than 3 n .

Let A = { e , a , b } . Then in G = A B , by Rédei [4] , A can be replace by

A = { e , a , a 2 } .

If a 3 = e , then A is a subgroup of G . Thus, A G , so A is a non-full- rank factor of G .

If a 3 e , then from G = { e , a , a 2 } B , we get the following partition of G :

G = e B a B a 2 B ( )

from which we get

G = a B a 2 B a 3 B ( ) .

Comparing ( ) with ( ) , we obtain B = a 3 B . Thus, B is periodic, from which it follows that B = H C , where H is a a proper subgroup of G . Now, from G = A B , we obtain the factorization G / H = A B / H = ( A / H ) ( B / H ) of the quotient group G / H , which is of order less than 3 n . So, by inductive assumption, either A H / H G / H or B H / H G / H from which it follows that either A G or B G . That is either A or B is a non-full-rank factor of G QED.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1] Dinitz, M. (2006) Full Rank Tilings of Finite Abelian Groups, SIAM Journal on Discrete Mathematics, 20, 160-170.
https://doi.org/10.1137/S0895480104445794
[2] Fraser, O. and Gordon, B. (1977) Solution to a Problem by A.D. Sands. Glasgow Mathematical Journal, 20, 115-117.
[3] Hajós, G. (1949) Sur la factorisation des groupe abeliens, Casopis Pest. Ma. Fys., 74, 157-162.
[4] Rédei, L. (1965) Die neue Theorie der endlihen abelschen und verallgemeinerung des hauptsatze von Hajos. Acta Mathematica Hungarica, 16, 329-373.
https://doi.org/10.1007/BF01904843
[5] Sands, A.D. and Szabo, S. (1991) Factorization of Periodic Subset. Acta Mathematica Hungarica, 57, 159-1167.
https://doi.org/10.1007/BF01903814
[6] Szabo, S. (2004) Topics in Factorization of Abelian Groups, Birkhauser, Beijing.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.