WorksMathematics
Arithmetic Universality and Integer Decomposition in Disjunctions of Three Staircase Simplices
Abstract
The staircase simplices , , are the unimodular cells of the staircase triangulation of the unit cube. The disjunctive hull (Cayley polytope) of a selection of them has the integer decomposition property (IDP) if, for all integers , every lattice point of is a sum of vertices, of them from . For two simplices, IDP always holds. For three, every nontrivial finite abelian group arises, in the optimal dimension , as the residue group of a simplex facet whose nonzero box points are Hilbert basis elements of the whole cone; times such a point is a sum of vertices exactly when its order in divides . Isolating this arithmetic is costly: if a simplex face has a single Hilbert basis element that is not a vertex, then is a sum of vertices exactly when some divides , and , attained for every ; we also find the least dimension for each with the fewest such elements. Without isolation, every nonzero submonoid of omitting is is a sum of vertices for a Hilbert basis element of degree three. For every polytope with vertices in , three staircase simplices in dimension have a face that has IDP exactly when the polytope does. Deciding whether a lattice point is a sum of vertices is strongly NP-complete, even given vertex expressions of and , and recognizing IDP of a designated facet is coNP-complete; for the whole hull, IDP can first fail in degree linear in , and it holds whenever . For a family of triples defined by words over three letters, we determine the entire Hilbert basis and characterize IDP by two forbidden subsequences.