﻿ Non-Full Rank Factorization of Finite Abelian Groups

Open Journal of Discrete Mathematics
Vol.07 No.02(2017), Article ID:75432,3 pages
10.4236/ojdm.2017.72005

Non-Full Rank Factorization of Finite Abelian Groups

Khalid Amin

Department of Mathematics, College of Science, University of Bahrain, Bahrain, Kingdom of Bahrain

Received: November 23, 2016; Accepted: April 14, 2017; Published: April 17, 2017

ABSTRACT

Tilings of $p$ -groups are closely associated with error-correcting codes. In [1] , M. Dinitz, attempting to generalize full-rank tilings of ${ℤ}_{2}^{n}$ to arbitrary finite abelian groups, was able to show that if $p\ge 5$ , then ${ℤ}_{p}^{n}$ 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$ .

Keywords:

Factorization of Abelian Groups, Error-Correcting Codes

1. Introduction

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

${A}_{1},\cdots ,{A}_{i},\cdots ,{A}_{k}$ of $G$ such that each element $g\in G$ can be represented in the form $g={a}_{1}\cdots {a}_{i}\cdots {a}_{k}$ . In this case, we write $G={A}_{1},\cdots ,{A}_{i},\cdots ,{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 $\left\{{T}_{i}:i\in I\right\}$ of subsets of ${ℝ}^{n}$ such that ${\cup }_{i\in I}{T}_{i}={ℝ}^{n}$ and $\mathrm{int}\left({T}_{i}\right){\cap }_{}\mathrm{int}\left({T}_{j}\right)=\varnothing$ , if $i\ne j$ , $i,j\in I$ . Two unit cubes are called twins if they share a complete $\left(n-1\right)$ -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},\cdots ,{A}_{i},\cdots ,{A}_{k}$ is a normalized factorization of $G$ , where each of the subsets ${A}_{i}$ is of the form $\left\{e,a,{a}^{2},\cdots ,{a}^{k}\right\}$ , 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}\cdots {A}_{i}\cdots {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=AB$ is a factorization of $G$ .

A tiling of a finite abelian group $G$ is called a full-rank tiling if $G=AB$ 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 $\left({x}_{1},{x}_{2},\cdots ,{x}_{n}\right)$ 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=\left({x}_{1},{x}_{2},\cdots ,{x}_{n}\right)$ and $y=\left({y}_{1},{y}_{2},\cdots ,{y}_{n}\right)$ ,

${d}_{H}\left(x,y\right)=|\left\{i:1\le i\le n,{x}_{i}\ne {y}_{i}\right\}|$ .

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

A perfect error-correcting code is a subset $C$ of ${ℤ}_{p}^{n}$ such that

${\cup }_{x\in C}S\left(x,e\right)={ℤ}_{p}^{n}$ and $S\left(x,e\right){\cap }_{}S\left(y,e\right)=\varnothing$ , if $x\ne y$ .

Observe that in the language of tiling, this says that ${ℤ}_{p}^{n}=CS\left(0,e\right)$ is a factorization of ${ℤ}_{p}^{n}$ [6] .

Factorization and Partition

Let $G=AB$ be a factorization of a finite Abelian group $G$ . Then the sets

$\left\{aB:a\in A\right\}$ 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}^{\prime }$ be subsets of $G$ . We say that $A$ is replaceable by ${A}^{\prime }$ , if whenever $G=AB$ is a factorization of $G$ , then so is $G={A}^{\prime }B$ .

Redei [4] showed that if $G=AB$ is a factorization of $G$ , where

$A=\left\{e,{a}_{1},{a}_{2},\cdots ,{a}_{p-1}\right\}$ , and $p$ is a prime, then $A$ is replaceable by $〈{a}_{i}〉$ , for each $i,1\le i\le p-1$ .

Definition

A subset $A$ of $G$ is periodic, if there exists $g\in G$ , $g\ne e$ such that

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

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

Theorem

Let $G={ℤ}_{3}^{n}$ and assume $G=AB$ 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=\left\{e,a,b\right\}$ . Then in $G=AB$ , by Rédei [4] , $A$ can be replace by

${A}^{\prime }=\left\{e,a,{a}^{2}\right\}$ .

If ${a}^{3}=e$ , then $A$ is a subgroup of $G$ . Thus, $〈A〉\ne G$ , so $A$ is a non-full- rank factor of $G$ .

If ${a}^{3}\ne e$ , then from $G=\left\{e,a,{a}^{2}\right\}B$ , we get the following partition of $G$ :

$G=eB{\cup }_{}aB{\cup }_{}{a}^{2}B\cdots \left(\ast \right)$

from which we get

$G=aB{\cup }_{}{a}^{2}B{\cup }_{}{a}^{3}B\cdots \left(\ast \ast \right)$ .

Comparing $\left(\ast \right)$ with $\left(\ast \ast \right)$ , we obtain $B={a}^{3}B$ . Thus, $B$ is periodic, from which it follows that $B=HC$ , where $H$ is a a proper subgroup of $G$ . Now, from $G=AB$ , we obtain the factorization $G/H=AB/H=\left(A/H\right)\left(B/H\right)$ of the quotient group $G/H$ , which is of order less than ${3}^{n}$ . So, by inductive assumption, either $〈AH/H〉\ne G/H$ or $〈BH/H〉\ne G/H$ from which it follows that either $〈A〉\ne G$ or $〈B〉\ne G$ . That is either $A$ or $B$ is a non-full-rank factor of $G$ QED.

Cite this paper

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

References

1. 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. 2. Fraser, O. and Gordon, B. (1977) Solution to a Problem by A.D. Sands. Glasgow Mathematical Journal, 20, 115-117.

3. 3. Hajós, G. (1949) Sur la factorisation des groupe abeliens, Casopis Pest. Ma. Fys., 74, 157-162.

4. 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. 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. 6. Szabo, S. (2004) Topics in Factorization of Abelian Groups, Birkhauser, Beijing.