A Short Proof of Tight Bounds on the Smallest Support Size of Integer Solutions to Linear Equations
\(\)
In this note, we study the size of the support of solutions to linear Diophantine equations $Ax=b, ~x\in\Z^n$ where $A\in\Z^{m\times n}, b\in\Z^n$. We give an asymptotically tight upper bound on the smallest support size, parameterized by $\|A\|_\infty$ and $m$, and 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 Leora, Oertel, Mathematical Programming 2022, while the proof presented here is simpler, relying only on linear algebra. It removes a factor of order $\log\log(\sqrt{m}\inftynorm{A})$ to the current best bound given in Aliev, De Loera, Eisenbrand, Oertel, Weismantel SIAM Journal on Optimization 2018.