Covering and packing in \({\mathbb Z^n}\) and \({\mathbb R^n}\). II (Q971928): Difference between revisions

In the present part (II), the authors deal with the group \( G=\mathbb Z^n\) and examine the effect of linear transformations on minimal covering and maximal packing densities of finite sets \(\mathcal A\subset \mathbb Z^n\). They show that the set of all densities for sets \(\mathcal A\) of given cardinality is closed and they caracterize four-element sets \(\mathcal A\subset \mathbb Z^n\) which are ''tiles'' see [\textit{W. M. Schmidt} and \textit{D. M. Tuller}, ``Covering and packings in \(\mathbb Z^n\) and \(\mathbb R^n\). I'', Monatsh. Math. 153, No. 3, 265--281 (2008; Zbl 1151.11029)] for the part (I). {Definitions:} Let \(\mathbb G\) be an additive group and \(\mathcal A\) a finite non empty subset. A further subset \(\mathcal S\) provides a \textit{covering} if the sum \(\mathcal A+\mathcal S=\mathbb G\). We say \(\mathcal S\) provides a \textit{packing} and write \(\mathcal A\downarrow \mathcal S\) if group elements can be written in at most one way as \(a+s\) with \(a\in\mathcal A, s\in\mathcal S\). We say that \(\mathcal S\) provides a \textit{tiling} if both \(\mathcal A+\mathcal S=\mathbb G\) and \(\mathcal A\downarrow \mathcal S\). A set \(\mathcal A\) is called a \textit{tile} if there exists a set \(\mathcal S\) with \(\mathcal A\oplus \mathcal S=\mathbb G\) Let \(\Lambda\subset \mathbb Z^n\) be a free \(\mathbb Z\)-module of finite, positive rank \(r\). A subset \(\mathcal S\subset \Lambda\) will be said \textit{periodic} with period \(q>0\) if \(\mathcal S\) is invariant under translation by elements \(q{\mathbf \ell} \) with \(\mathbf \ell\in\Lambda\). The \textit{density } \(d(S;\Lambda)\) of the set \(\mathcal S\) is the number of its images in the quotient \(\Lambda/q\Lambda\) divided by \(q^r\). Given \(\mathcal A\subset \Lambda\), the \textit{minimal covering frequency} \(c(\mathcal A;\Lambda)\) is the infimum of \(d(\mathcal S;\Lambda)\) over periodic sets with \(\mathcal A+\mathcal S=\Lambda\), and the \textit{maximal packing frequency} \(p(\mathcal A;\Lambda)\) is the supremum of \(d(\mathcal S;\Lambda)\) over periodic sets \(\mathcal S\) with \(\mathcal A\downarrow \mathcal S\). The \textit{minimum covering density} of \(\mathcal A\subset \Lambda\) is \(C(\mathcal A;\Lambda):=|\mathcal A|c(\mathcal A;\Lambda)\) and the \textit{maximal packing density} is \(P(\mathcal A;\Lambda):=|\mathcal A|p(\mathcal A;\Lambda)\). Let \(\Gamma\) be a submodule of \(\Lambda\); a set \(\mathcal S\subset \Lambda\) is called \textit{\(\Gamma\)-periodic} if \(\mathcal S+\Gamma=\mathcal S\) and \(\mathcal S\) is periodic. For a set \(\mathcal A\subset \Lambda\), define \(c_\Gamma(\mathcal A;\Lambda)\) to be the infimum \(d(\mathcal S;\Lambda)\) of \(\Gamma\)-periodic sets with \(\mathcal A+\mathcal S=\Lambda\). Similarly define \(p_\Gamma(\mathcal A;\Lambda)\) in terms of \(\Gamma\)-periodic sets. Let \(C(\nu)\) resp. \(P(\nu)\) be the set of values \(C(\mathcal A)\) (resp. \(P(\mathcal A)\)) as \(\mathcal A\) ranges through the sets of cardinality \(|A|=\nu+1\) (and lying in arbitrary \(\Lambda\)). Call a set \(R\subset \mathbb R\) \textit{non ascending} (resp. \textit{non descending}) if every non-empty subset has a maximal (resp. minimal) element. Results: We give the statement of four of the seven theorems of the article: Suppose that \(\Lambda\subset \Lambda'\) are free \(\mathbb Z\)-modules of finite rank. Then \(\mathcal A\subset \Lambda\) has \(c(\mathcal A;\Lambda)=c(\mathcal A;\Lambda')\) and \(p(\mathcal A;\Lambda)=p(\mathcal A;\Lambda')\). 1) Let \(T:\Lambda\rightarrow\Lambda'\) be a linear map with kernel \(\Gamma\). Then \(\mathcal A\subset \Lambda\) has \(c(T(\mathcal A);\Lambda'))=c_\Gamma(\mathcal A;\Lambda)\) and if \(T\) is \(1-1\) on \(\mathcal A\), then also \(p(T(\mathcal A);\Lambda')=p_\Gamma(\mathcal A;\Lambda)\). 2) \(C(\nu)\) is closed and non-ascending and \(P(\nu)\) is closed and non-descending. 3) A set \(\mathcal A=\{\mathbf a_0,\mathbf a_1,\mathbf a_2,\mathbf a_3\}\) of cardinality \(4\) is a tile precisely if there is no permutation \(i,j,k,\ell\) of \(0,1,2,3\) with \(u(\mathbf a_i-\mathbf a_j)=v(\mathbf a_k-\mathbf a_\ell)\) where \(u,v\) are integers of opposite parity. (See also [\textit{M. Szegedy}, Algorithms to tile the infinite grid with finite clusters (1998) \url{http:/www.cs.rutgers.edu/szegedy/}] used for this last result).