## Abstract

Siegel’s Lemma is concerned with finding a "small” nontrivial integer solution of a large system of homogeneous linear equationswith integer coefficients, where the number of variables substantially exceeds the number of equations (for example, n equations and N variables with N ≥ 2n), and "small” means small in the maximum norm. Siegel’s Lemma is a clever application of the Pigeonhole Principle, and it is a pure existence argument. The basically combinatorial Siegel’s Lemma is a key tool in transcendental number theory and diophantine approximation. David Masser (a leading expert in transcendental number theory) asked the question whether or not the Siegel’s Lemma is best possible. Here we prove that the socalled "Third Version of Siegel’s Lemma” is best possible apart from an absolute constant factor. In other words, we show that no other argument can beat the Pigeonhole Principle proof of Siegel’s Lemma (apart from an absolute constant factor). To prove this, we combine a concentration inequality (i.e., Fourier analysis) with combinatorics.

Original language | English (US) |
---|---|

Title of host publication | A Journey through Discrete Mathematics |

Subtitle of host publication | A Tribute to Jiri Matousek |

Publisher | Springer International Publishing |

Pages | 165-206 |

Number of pages | 42 |

ISBN (Electronic) | 9783319444796 |

ISBN (Print) | 9783319444789 |

DOIs | |

State | Published - Jan 1 2017 |

## All Science Journal Classification (ASJC) codes

- Computer Science(all)
- Mathematics(all)
- Economics, Econometrics and Finance(all)
- Business, Management and Accounting(all)