= Solution
For $M<N$ homogeneous equations $\sum_{j=1}^N a_{ij}z_j=0$ with integral coefficients $|a_{ij}|\le A$, $A\ge1$, <Siegel lemma> supplies a nonzero integral vector with
$$
0<\|z\|_\infty\le Q=\left\lfloor(2NA)^{M/(N-M)}\right\rfloor.
$$
Map the <integer> box $\{0,\ldots,Q\}^N$ to the $M$ equation values. There are $(Q+1)^N$ inputs, while each output coordinate lies in $[-NAQ,NAQ]$, so there are at most $(2NAQ+1)^M$ outputs. Since $Q+1>(2NA)^{M/(N-M)}$ and $2NAQ+1\le2NA(Q+1)$, the input count is strictly larger. Two inputs have the same image; their nonzero difference solves every equation and has the stated norm bound. This proves the lemma by the <pigeonhole proof of integer Siegel lemma>.
Rational coefficients are handled by clearing denominators. For coefficients in a <number field> of degree $d$, expansion in a rational basis gives at most $dM$ rational equations; if $N>dM$ the same argument gives an <integer> solution with the corresponding effective bound after clearing the basis denominators. The lemma concerns homogeneous equations; arbitrary inhomogeneous <integer> equations need not be soluble.
Back to article page
