Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2307.08826 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913713430200320 |
|---|---|
| author | Dubey, Yatharth Liu, Siyue |
| author_facet | Dubey, Yatharth Liu, Siyue |
| contents | In this note, we study the size of the support of integer solutions to linear equations $Ax=b, ~x\in\Z^n$ where $A\in\Z^{m\times n}, b\in\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_08826 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the Smallest Support Size of Integer Solutions to Linear Equations Dubey, Yatharth Liu, Siyue Optimization and Control Number Theory 90C10, 11D04 In this note, we study the size of the support of integer solutions to linear equations $Ax=b, ~x\in\Z^n$ where $A\in\Z^{m\times n}, b\in\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. |
| title | On the Smallest Support Size of Integer Solutions to Linear Equations |
| topic | Optimization and Control Number Theory 90C10, 11D04 |
| url | https://arxiv.org/abs/2307.08826 |