We propose and study the following problem: given $X \subset Z_n$, construct a maximum packing of $dev X$ (the development of X), i.e., a maximum set of pairwise disjoint translates of X. Such a packing is optimal when its size reaches the upper bound $\lfloor {n\over |X|}\rfloor$. In particular, it is perfect when its size is exactly equal to ${n\over |X|}$, i.e. when it is a partition of $Z_n$. We apply the above problem for constructing Bose's families. A (q, k) Bose's family (BF) is a nonempty family $\cal F$ of subsets of the field GF(q) such that: (i) each member of $\cal F$ is a coset of the kth roots of unity for k odd (the union of a coset of the (k - 1)th roots of unity and zero for k even); (ii) the development of $\cal F$, i.e., the incidence structure $(GF(q),{\cal B}: = (X +g \ | \ (X, g ) \in {\cal F} x GF(q)), is a semilinear space. A(q, k)-BF is optimal when its size reaches the upper bound $\lfloor {q-1\over k(k-1)}\rfloor$. In particular, it is perfect when its size is exactly equal to ${q-1\over k(k-1)}$; in this case the (q,k)-BF is a (q,k,1) difference family and its development is a linear space. If the set of (q, k)-BF's is not empty, there is a bijection preserving maximality, optimality, and perfectness between this set with the set of packings of $dev X$, where X is a suitable $\lfloor{k\over2}\rfloor}-subset of $\Z_n$, $n={q-1\over 2k}$ for k odd, $n={q-1\over2(k-1)}$ for k even.
A packing problem and its application to Bose's families
BURATTI, Marco
1996
Abstract
We propose and study the following problem: given $X \subset Z_n$, construct a maximum packing of $dev X$ (the development of X), i.e., a maximum set of pairwise disjoint translates of X. Such a packing is optimal when its size reaches the upper bound $\lfloor {n\over |X|}\rfloor$. In particular, it is perfect when its size is exactly equal to ${n\over |X|}$, i.e. when it is a partition of $Z_n$. We apply the above problem for constructing Bose's families. A (q, k) Bose's family (BF) is a nonempty family $\cal F$ of subsets of the field GF(q) such that: (i) each member of $\cal F$ is a coset of the kth roots of unity for k odd (the union of a coset of the (k - 1)th roots of unity and zero for k even); (ii) the development of $\cal F$, i.e., the incidence structure $(GF(q),{\cal B}: = (X +g \ | \ (X, g ) \in {\cal F} x GF(q)), is a semilinear space. A(q, k)-BF is optimal when its size reaches the upper bound $\lfloor {q-1\over k(k-1)}\rfloor$. In particular, it is perfect when its size is exactly equal to ${q-1\over k(k-1)}$; in this case the (q,k)-BF is a (q,k,1) difference family and its development is a linear space. If the set of (q, k)-BF's is not empty, there is a bijection preserving maximality, optimality, and perfectness between this set with the set of packings of $dev X$, where X is a suitable $\lfloor{k\over2}\rfloor}-subset of $\Z_n$, $n={q-1\over 2k}$ for k odd, $n={q-1\over2(k-1)}$ for k even.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.