Non-Full Rank Factorization of Finite Abelian Groups

Show more

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 ${\mathbb{R}}^{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 ${\mathbb{R}}^{n}$ is a collection $\left\{{T}_{i}:i\in I\right\}$ of subsets of ${\mathbb{R}}^{n}$ such that ${\cup}_{i\in I}}{T}_{i}={\mathbb{R}}^{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 ${\mathbb{R}}^{n}$ by unit cubes such that there are no twins! Minkowski’s conjecture is usually expressed as follows:

Each lattice tiling of ${\mathbb{R}}^{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

${\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.

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.