Siegel’s Lemma is sharp

Research output: Chapter in Book/Report/Conference proceedingChapter

1 Scopus citations

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 languageEnglish (US)
Title of host publicationA Journey through Discrete Mathematics
Subtitle of host publicationA Tribute to Jiri Matousek
PublisherSpringer International Publishing
Pages165-206
Number of pages42
ISBN (Electronic)9783319444796
ISBN (Print)9783319444789
DOIs
StatePublished - Jan 1 2017

All Science Journal Classification (ASJC) codes

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

Fingerprint

Dive into the research topics of 'Siegel’s Lemma is sharp'. Together they form a unique fingerprint.

Cite this