On the Smallest Support Size of Integer Solutions to Linear Equations

Abstract

In this note, we study the size of the support of integer solutions to linear equations $Ax=b,x\in {\mathbb{Z}}^n$ where $A\in {\mathbb{Z}}^{m\times n},b\in {\mathbb{Z}}^n$. We give an upper bound on the smallest support size as a function of $A$, taken as a worst case over all $b$ such that the above system has a solution. This bound is asymptotically tight, and in fact matches the bound given in Aliev, Averkov, De Loera and Oertel Mathematical Programming 2022, while the proof presented here is simpler, relying only on linear algebra.

Mathematical Programming, 2025