Primitive zonotopes (Q724942)

The authors introduce the notion of a \textit{primitive zonotope}: a zonotope generated by the primitive integer vectors of \(q\)-norm \(\leq p\), that is, \[ Z_q(d, p) := \left\{ \lambda_v v : \, v \in \mathbb{Z}^d, \;\|v\|_q \leq p, \;\gcd(v) = 1, \;v \succ 0, \;0 \leq \lambda_v \leq 1 \right\} . \] Here \(\succ\) denotes the lexicographic order, i.e., \(v \succ 0\) means that the first nonzero entry of \(v\) is positive. These polytopes are interesting because they have a large symmetry group, a large diameter, and many vertices relative to their grid embedding size. The authors derive several properties of primitive zonotopes, including lower bounds for their diameters and connections to the computational complexity of multicriteria matroid optimization.