Packing Arrays and Packing Designs

A packing array is a b × k array, A with entriesa _i,j from a g-ary alphabet such that given any two columns,i and j, and for all ordered pairs of elements from a g-ary alphabet,(g ₁, g ₂), there is at most one row, r, such thata _r,i = g ₁ anda _r,j = g ₂. Further, there is a set of at leastn rows that pairwise differ in each column: they are disjoint. A central question is to determine, forgiven g, k and n, the maximum possible b. We examine the implications whenn is close to g. We give a brief analysis of the case n = g and showthat 2g rows is always achievable whenever more than g exist. We give an upper bound derivedfrom design packing numbers when n = g – 1. When g + 1 k then this bound is always at least as good as the modified Plotkin bound of 12]. When theassociated packing has as many points as blocks and has reasonably uniform replication numbers, we show thatthis bound is tight. In particular, finite geometries imply the existence of a family of optimal or near optimalpacking arrays. When no projective plane exists we present similarly strong results. This article completelydetermines the packing numbers, D(v, k, 1), when .