Polynomial enumeration of multidimensional lattices

Abstract

Denoting the nonnegative (resp. signed) integers by N (resp. Z) and the real numbers by R, let K ⊂ Rm and f: Rm→ R. Then f is a storing function (resp. packing function) on K whenever f|(Zm{square original of or equal to} K) is an injection into (resp. bijection onto)N. Unit translations gm of some P. Chowla [1961] polynomials are packing functions on the corresponding Nm, and all compositions of these polynomials yield further packing functions on various Nr. We study this accessible family of packing functions, using standard properties of ordered trees to classify all those compositions, up to a simple equivalence, which define polynomial packing functions on each Nm. The number c(m) of equivalence classes is an exponentially growing function for large m, whence the uniqueness conjecture of our prior two-dimensional work has no counterpart for larger m. We obtain the admissible degrees for composition polynomials in m variables; we describe the tre structures for all such polynomials with extremal degrees. The m-variable polynomials of least degree form a rather irregular number a(m) of equivalence classes. Density considerations give some degree constraints on a general polynomial packing function whose domain K is the topological closure of a nonvoid open cone. © 1979 Springer-Verlag New York Inc.