Non-Full Rank Factorization of Finite Abelian Groups

Khalid Amin

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

DOI: 10.4236/ojdm.2017.72005                

Abstract

Tilings of p-groups are closely associated with error-correcting codes. In [1], M. Dinitz, attempting to generalize full-rank tilings of  Zⁿ₂  to arbitrary finite abelian groups, was able to show that if p ≥5, then Zⁿ_p  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 ${\displaystyle {\cup }_{i\in I}}{T}_i={ℝ}^n$ and $\mathrm{int}\left(T_i\right){\displaystyle {\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<\left|a\right|$ ; here $\left|a\right|$ 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 $\langle A\rangle =\langle B\rangle =G$ , where $\langle A\rangle$ 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, ${\mathbb{Z}}_p^n$ viewed as a vector space of $n$ -tuples $\left(x_1,x_2,\cdots ,x_n\right)$ over ${\mathbb{Z}}_p$ . Then subspaces correspond to subgroups. Moreover, ${\mathbb{Z}}_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|\left\{i:1\le i\le n,x_i\ne y_i\right\}\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(x,y)\le e\right\}$ .

A perfect error-correcting code is a subset $C$ of ${\mathbb{Z}}_p^n$ such that

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

Observe that in the language of tiling, this says that ${\mathbb{Z}}_p^n=CS\left(0,e\right)$ is a factorization of ${\mathbb{Z}}_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, $\left|G\right|=\left|A\right|\left|B\right|$ , where $\left|A\right|$ 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 $\langle a_i\rangle$ , 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={\mathbb{Z}}_3^n$ and assume $G=AB$ is a factorization of $G$ , where $\left|A\right|=3$ , then either $A$ or $B$ is a non-full-rank factor of $G$ .

Proof:

Note that $\left|G\right|=3^n$ . We induct on $n$ .

If $n=1$ , then $\left|B\right|=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, $\langle A\rangle \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{\displaystyle {\cup }_{}}aB{\displaystyle {\cup }_{}}{a}^{2}B\cdots (\ast )$

from which we get

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

Comparing $(\ast )$ 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 $\langle AH/H\rangle \ne G/H$ or $\langle BH/H\rangle \ne G/H$ from which it follows that either $\langle A\rangle \ne G$ or $\langle B\rangle \ne 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.