Additive Number Theory: Inverse Problems and the Geometry of Sumsets (Graduate Texts in Mathematics (165))

Many classical problems in additive number theory are direct problems, in which one starts with a set A of natural numbers and an integer H -> 2, and tries to describe the structure of the sumset hA consisting of all sums of h elements of A. By contrast, in an inverse problem, one starts with a sumset hA, and attempts to describe the structure of the underlying set A. In recent years there has been ramrkable progress in the study of inverse problems for finite sets of integers. In particular, there are important and beautiful inverse theorems due to Freiman, Kneser, Plünnecke, Vosper, and others. This volume includes their results, and culminates with an elegant proof by Ruzsa of the deep theorem of Freiman that a finite set of integers with a small sumset must be a large subset of an n-dimensional arithmetic progression. Cover......Page 1 Title......Page 4 Copyright......Page 5 Dedication......Page 6 Preface......Page 8 Contents......Page 10 Notation......Page 14 1.1 Direct and inverse problems......Page 16 1.2 Finite arithmetic progressions......Page 22 1.3 An inverse problem for distinct summands......Page 28 1.4 A special case......Page 33 1.5 Small sumsets: The case |2A| < 3k - 4......Page 36 1.6 Application: The number of sums and products......Page 44 1.7 Application: Sumsets and powers of 2......Page 46 1.8 Notes......Page 48 1.9 Exercises......Page 50 2.1 Addition in groups......Page 56 2.2 The e-transform......Page 57 2.3 The Cauchy-Davenport theorem......Page 58 2.4 The Erd6s-Ginzburg-Ziv theorem......Page 63 2.5 Vosper's theorem......Page 67 2.6 Application: The range of a diagonal form......Page 72 2.7 Exponential sums......Page 77 2.8 The Freiman-Vosper theorem......Page 82 2.9 Notes......Page 88 2.10 Exercises......Page 89 3.1 The Erdos-Heilbronn conjecture......Page 92 3.2 Vandermonde determinants......Page 93 3.3 Multidimensional ballot numbers......Page 96 3.4 A review of linear algebra......Page 104 3.5 Alternating products......Page 107 3.6 Erdos-Heilbronn, concluded......Page 110 3.7 The polynomial method......Page 113 3.8 Erd6s-Heilbronn via polynomials......Page 116 3.9 Notes......Page 121 3.10 Exercises......Page 122 4.1 Periodic subsets......Page 124 4.2 The addition theorem......Page 125 4.3 Application: The sum of two sets of integers......Page 132 4.4 Application: Bases for finite and a-finite groups......Page 142 4.5 Notes......Page 145 4.6 Exercises......Page 146 5.1 Small sumsets and hyperplanes......Page 148 5.2 Linearly independent hyperplanes......Page 150 5.3 Blocks......Page 157 5.4 Proof of the theorem......Page 167 5.6 Exercises......Page 178 6.1 Lattices and determinants......Page 182 6.2 Convex bodies and Minkowski's First Theorem......Page 189 6.3 Application: Sums of four squares......Page 192 6.4 Successive minima and Minkowski's second theorem......Page 195 6.5 Bases for sublattices......Page 200 6.6 Torsion-free abelian groups......Page 205 6.7 An important example......Page 209 6.9 Exercises......Page 211 7.1 Plunnecke graphs......Page 216 7.2 Examples of Plunnecke graphs......Page 218 7.3 Multiplicativity of magnification ratios......Page 220 7.4 Menger's theorem......Page 224 7.5 Plunnecke's inequality......Page 227 7.6 Application: Estimates for sumsets in groups......Page 232 7.7 Application: Essential components......Page 236 7.8 Notes......Page 241 7.9 Exercises......Page 242 8.1 Multidimensional arithmetic progressions......Page 246 8.2 Freiman isomorphisms......Page 248 8.3 Bogolyubov's method......Page 253 8.4 Ruzsa's proof, concluded......Page 259 8.5 Notes......Page 266 8.6 Exercises......Page 267 9.2 Small sumsets and long progressions......Page 270 9.3 The regularity lemma......Page 272 9.4 The Balog-Szemeredi theorem......Page 285 9.5 A conjecture of Erd6s......Page 292 9.6 The proper conjecture......Page 293 9.7 Notes......Page 294 9.8 Exercises......Page 295 References......Page 298 Index......Page 307 Back Cover......Page 312 "Many classical problems in additive number theory are direct problems, in which one starts with a set A of natural numbers and an integer h[actual symbol not reproducible]2 and tries to describe the structure of the sumset hA consisting of all sums of h elements of A. In contrast, in an inverse problem, one starts with a sumset hA and attempts to describe the structure of the underlying set A. In recent years, there has been remarkable progress in the study of inverse problems for finite sets of integers. In particular, there are important and beautiful inverse theorems due to Freiman, Kneser, Plunnecke, Vospel and others. This volume includes their results and culminates with an elegant proof by Rusza of the deep theorem of Freiman that a finite set of integers with a small sumset must be a large subset of an n-dimensional arithmetic progression. Inverse problems are a central topic in additive number theory. This graduate text gives a comprehensive and self-contained account of this subject. In particular, it contains complete proofs of results from exterior algebra, combinatorics, graph theory, and the geometry of numbers that are used in the proofs of the principal inverse theorems. The only prerequisites for the book are undergraduate courses in algebra, number theory, and analysis."--Page 4 de la couverture Many classical problems in additive number theory are direct problems, in which one starts with a set A of natural numbers and an integer H -> 2 , and tries to describe the structure of the sumset hA consisting of all sums of h elements of A . By contrast, in an inverse problem, one starts with a sumset hA , and attempts to describe the structure of the underlying set A . In recent years there has been ramrkable progress in the study of inverse problems for finite sets of integers. In particular, there are important and beautiful inverse theorems due to Freiman, Kneser, Plnnecke, Vosper, and others. This volume includes their results, and culminates with an elegant proof by Ruzsa of the deep theorem of Freiman that a finite set of integers with a small sumset must be a large subset of an n -dimensional arithmetic progression.