2016/11/02 by Oliver Roche‐Newton, Roche-Newton, Oliver, Ilya D. Shkredov +3
Engineering · #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.1611.00529
For a given subset A⊆ \mathbb Fq^*, we study the problem of finding a large packing set B of A, that is, a set B ⊆ \mathbb Fq^* such that |AB|=|A||B|. We prove the existence of such a B of size |B|≥ (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,…,λ\ for some positive integer λ is particularly interesting in view of the construction of limited-magnitude error correcting codes. Here we construct a packing set B of size |B|≫ p (λlog p)-1 for any λ≤ c p1/2 for some explicitly calcuable constant c. This result is optimal up to the logarithmic factor.