Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

A Journey Through Discrete MathematicsSiegel’s Lemma Is Sharp

A Journey Through Discrete Mathematics: Siegel’s Lemma Is Sharp [Siegel’s Lemma is concerned with finding a “small” nontrivial integer solution of a large system of homogeneous linear equations with 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 so-called “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.] http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

A Journey Through Discrete MathematicsSiegel’s Lemma Is Sharp

Editors: Loebl, Martin; Nešetřil, Jaroslav; Thomas, Robin
Beck, József
Springer Journals — Oct 6, 2017
Download PDF
41 pages

Loading next page...
 
/lp/springer-journals/a-journey-through-discrete-mathematics-siegel-s-lemma-is-sharp-VMd50Uhc97
Publisher
Springer International Publishing
Copyright
© Springer International publishing AG 2017
ISBN
978-3-319-44478-9
Pages
165 –206
DOI
10.1007/978-3-319-44479-6_8
Publisher site
See Chapter on Publisher Site

Abstract

[Siegel’s Lemma is concerned with finding a “small” nontrivial integer solution of a large system of homogeneous linear equations with 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 so-called “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.]

Published: Oct 6, 2017

There are no references for this article.