An enlarged family of packing polynomials on multidimensional lattices

Abstract

Here N = {0, 1, 2, . . .}, while a function f on Nm or a larger domain is a packing function if its restriction f|Nm is a bijection onto N. (Packing functions generalize Cantor's [1] pairing polynomials, and yield multidimensional-array storage schemes.) We call two functions equivalent if permuting arguments makes them equal. Also s(x) = x1 + ⋯ + xm when x = (x1, . . . , xm); and such an f is a diagonal mapping if f(x) < f(y) whenever x, y ∈ Nm and s(x) < s(y). Lew [7] composed Skolem's [14], [15] diagonal packing polynomials (essentially one for each m) to construct c(m) inequivalent nondiagonal packing polynomials on each Nm. For each m > 1 we now construct 2m-2 inequivalent diagonal packing polynomials. Then, extending the tree arguments of the prior work, we obtain d(m) inequivalent nondiagonal packing polynomials, where d(m)/c(m) → ∞ as m → ∞. Among these we count the polynomials of extremal degree. © 1996 Springer-Verlag New York Inc.