\(\)

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*.

## Article

Download

View A Short Proof of Tight Bounds on the Smallest Support Size of Integer Solutions to Linear Equations