Past exam of the mathematics course of the University of Cambridge / 2001 / iii / Paper 20 / 4 / i / Solution

For $M<N$ homogeneous equations ${\sum }_{j=1}^N{a}_{ij}{z}_j=0$ with integral coefficients $|a_{ij}|\le A$, $A\ge 1$, Siegel lemma supplies a nonzero integral vector withMap the integer box $\{0,\dots ,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\le 2NA(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.