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.
1996
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/920043
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 14
social impact