On Minimal Support for Lattices and Semigroups
summary
Assumes Ax = b, x ≥ 0, gcd of minors = 1 and asks how small the support of an integer solution can be. Results give explicit bounds: for Hilbert-basis matrices one needs at most 2m−2 generators and cannot in general beat about 7/6·m; general bounds are roughly support ≤ m + log sqrt(det(A A^T)) (and for m=1 support ≤ 1 + log(max entry)), with matching lower bounds ≈ m·log(max)^{1−ε}. Proofs use geometry of numbers, Minkowski, and generating functions; integer-Carathéodory rank is computable in polytime for fixed n, hardness remains open.
AI-written summary · about