On the smallest support size of integer solutions to linear equations
成果类型：
Article; Early Access
署名作者：
Dubey, Yatharth; Liu, Siyue
署名单位：
Amazon.com; Carnegie Mellon University
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-025-02202-7
发表日期：
2025
关键词：
摘要：
In this note, we study the size of the support of integer solutions to linear equations Ax = b, x is an element of Z(n )where A is an element of Z(mxn), b is an element of 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 [1], while the proof presented here is simpler, relying only on linear algebra.