Minkowski Length of 3D Lattice Polytopes

We study the Minkowski length L(P) of a lattice polytope P, which is defined to be the largest number of non-trivial primitive segments whose Minkowski sum lies in P. The Minkowski length represents the largest possible number of factors in a factorization of polynomials with exponent vectors in P, and shows up in lower bounds for the minimum distance of toric codes. In this paper we give a polytime algorithm for computing L(P) where P is a 3D lattice polytope. We next study 3D lattice polytopes of Minkowski length 1. In particular, we show that if Q, a subpolytope of P, is the Minkowski sum of L=L(P) lattice polytopes Q _i , each of Minkowski length 1, then the total number of interior lattice points of the polytopes Q ₁,??,Q _L is at most 4. Both results extend previously known results for lattice polygons. Our methods differ substantially from those used in the two-dimensional case.