betaFeedback

WorksMathematics

Arithmetic Universality and Integer Decomposition in Disjunctions of Three Staircase Simplices

Abstract

The staircase simplices {x∈[0,1]d:xσ(1)≤⋯≤xσ(d)}\{x\in[0,1]^d:x_{σ(1)}\le\cdots\le x_{σ(d)}\}, σ∈Sd σ\in S_d\,, are the d!d! unimodular cells of the staircase triangulation of the unit cube. The disjunctive hull (Cayley polytope) of a selection P0,…,PnP_0, \ldots, P_n of them has the integer decomposition property (IDP) if, for all integers λi≥0λ_i\ge0, every lattice point of ∑iλiPi\sum_iλ_i P_i is a sum of vertices, λiλ_i of them from PiP_i. For two simplices, IDP always holds. For three, every nontrivial finite abelian group GG arises, in the optimal dimension Θ(log⁡∣G∣)Θ(\log|G|), as the residue group of a simplex facet whose ∣G∣−1|G|-1 nonzero box points are Hilbert basis elements of the whole cone; kk times such a point is a sum of vertices exactly when its order in GG divides kk. Isolating this arithmetic is costly: if a simplex face has a single Hilbert basis element hh that is not a vertex, then khkh is a sum of vertices exactly when some qq divides kk, and d≥3q−2d\ge3q-2, attained for every q≥3q\ge3; we also find the least dimension for each GG with the fewest such elements. Without isolation, every nonzero submonoid of Z≥0\mathbb{Z}_{\ge0} omitting 11 is {k≥0:kh\{k\ge0:kh is a sum of vertices}\} for a Hilbert basis element hh of degree three. For every 0/10/1 polytope with NN vertices in Rr\mathbb{R}^r, three staircase simplices in dimension O(N(r+1))O(N(r+1)) have a face that has IDP exactly when the polytope does. Deciding whether a lattice point hh is a sum of vertices is strongly NP-complete, even given vertex expressions of 2h2h and 3h3h, and recognizing IDP of a designated facet is coNP-complete; for the whole hull, IDP can first fail in degree linear in dd, and it holds whenever d≤5d\le5. For a family of triples defined by words over three letters, we determine the entire Hilbert basis and characterize IDP by two forbidden subsequences.

Paper details

vlnc:W_kbhkbmt7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude, ChatGPT

View statement
Looking for related papers…