Packing Sets

Abstract: For a given subset

A s u b s e t e q m a t h b b F_{q}^{*}

, we study the problem of finding a large packing set

B

of

A

, that is, a set

B s u b s e t e q m a t h b b F_{q}^{*}

such that

| A B | = | A | | B |

. We prove the existence of such a

B

of size

| B | g e (q - 1) / | A / A |

and show that this bound is in general optimal. The case that

q = p

is a prime and

A = 1, 2, l d o t s, l a m b d a

for some positive integer

l a m b d a

is particularly interesting in view of the construction of limited-magnitude error correcting codes. Here we construct a packing set

B

of size

| B | g g p (l a m b d a l o g p)^{- 1}

for any

l a m b d a l e c p^{1 / 2}

for some explicitly calcuable constant

c

. This result is optimal up to the logarithmic factor.

This page was built for publication: Packing Sets