<p>In this note, we study the size of the support of integer solutions to linear equations <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(Ax=b, ~x\in \mathbb {Z}^n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>A</mi> <mi>x</mi> <mo>=</mo> <mi>b</mi> <mo>,</mo> <mspace width="3.33333pt" /> <mi>x</mi> <mo>∈</mo> <msup> <mrow> <mi mathvariant="double-struck">Z</mi> </mrow> <mi>n</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> where <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(A\in \mathbb {Z}^{m\times n}, b\in \mathbb {Z}^n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>A</mi> <mo>∈</mo> <msup> <mrow> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow> <mi>m</mi> <mo>×</mo> <mi>n</mi> </mrow> </msup> <mo>,</mo> <mi>b</mi> <mo>∈</mo> <msup> <mrow> <mi mathvariant="double-struck">Z</mi> </mrow> <mi>n</mi> </msup> </mrow> </math></EquationSource> </InlineEquation>. We give an upper bound on the smallest support size as a function of <i>A</i>, taken as a worst case over all <i>b</i> such that the above system has a solution. This bound is asymptotically tight, and in fact matches the bound given in [<CitationRef CitationID="CR1">1</CitationRef>], while the proof presented here is simpler, relying only on linear algebra.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the smallest support size of integer solutions to linear equations

  • Yatharth Dubey,
  • Siyue Liu

摘要

In this note, we study the size of the support of integer solutions to linear equations \(Ax=b, ~x\in \mathbb {Z}^n\) A x = b , x Z n where \(A\in \mathbb {Z}^{m\times n}, b\in \mathbb {Z}^n\) A Z m × n , b 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.