Advanced Courses in Mathematics CRM Barcelona Centre de Recerca Matemàtica Managing Editor: Manuel Castellet Alfred Geroldinger Imre Z. Ruzsa Combinatorial Number Theory and Additive Group Theory Birkhäuser Basel · Boston · Berlin Authors: Alfred Geroldinger Imre Z. Ruzsa Institute for Mathematics and Alfréd Rényi Institute of Mathematics Scientific Computing P.O. Box 127 University of Graz 1364 Budapest, Hungary Heinrichstrasse 36 e-mail: [email protected] 8010 Graz, Austria e-mail: [email protected] 2000 Mathematical Subject Classification 11P70, 11B50, 11R27 Library of Congress Control Number: 2008941509 Bibliographic information published by Die Deutsche Bibliothek Die Deutsche Bibliothek lists this publication in the Deutsche Nationalbibliografie; detailed bibliographic data is available in the Internet at <http://dnb.ddb.de>. ISBN 978-3-7643-8961-1 Birkhäuser Verlag AG, Basel – Boston – Berlin This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in other ways, and storage in data banks. For any kind of use permission of the copyright owner must be obtained. © 2009 Birkhäuser Verlag, P.O. Box 133, CH-4010 Basel, Switzerland Part of Springer Science+Business Media Printed on acid-free paper produced from chlorine-free pulp. TCF ∞ Printed in Germany ISBN 978-3-7643-8961-1 e-ISBN 978-3-7643-8962-8 9 8 7 6 5 4 3 2 1 www.birkhauser.ch Foreword This book collects the material delivered in the 2008 edition of the DocCourse in Combinatorics and Geometry which was devoted to the topic of Additive Combi- natorics. The two first parts, which form the bulk of the volume, contain the two main advanced courses, Additive Group Theory and Non-unique Factorizations, by Alfred Geroldinger, and Sumsets and Structure, by Imre Z. Ruzsa. The first part focusses on the interplay between zero-sum problems, arising from the Erdo˝s–Ginzburg–Ziv theorem, and nonuniqueness of factorizations in monoids and integral domains. The second partdeals with structural set addition. It aims at describing the structure of sets in a commutative group from the knowledge of some properties of its sumset. Thethirdpartofthevolumecollectssomeoftheseminarswhichaccompanied the main courses and covers several aspects of contemporary methods and prob- lems in Additive Combinatorics: multiplicative properties of sumsets (Christian Elsholtz), a step further in the inverse 3k−4-theorem (Gregory A. Freiman), the isoperimetric method (Yahya O. Hamidoune), new developments around Følner’s theorem(NorbertHegyva´ri),thepolynomialmethod(GyulaKa´rolyi),asurveyon open problems (Melvyn B. Nathanson), spectral techniques for the sum-product problem (Jozsef Solymosi), and multidimensional inverse problems (Yonutz V. Stanchescu). WearegratefultoItziarBardaj´ıandLlu´ısVenafortheircarefulproofreading of all its chapters. This edition of the DocCourse has been supported by the Spanish project i-Math and by the Centre de Recerca Matem`atica, to which we express our grat- itude. We particularly want to thank the director, Prof. Joaquim Bruna, and the staffoftheCentredeRecercaMatema`ticafortheirexcellentjobinorganizingthis edition of the DocCourse. Barcelona,July 2008 Javier Cilleruelo, Marc Noy and Oriol Serra Coordinators of the DocCourse Contents Foreword v I Additive Group Theory and Non-unique Factorizations Alfred Geroldinger 1 Introduction 3 Notation 5 1 Basic concepts of non-unique factorizations 7 1.1 Arithmetical invariants . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2 Krull monoids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3 Transfer principles . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.4 Main problems in factorization theory . . . . . . . . . . . . . . . . 20 2 The Davenport constant and first precise arithmetical results 21 2.1 The Davenport constant . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Group algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3 Arithmetical invariants again . . . . . . . . . . . . . . . . . . . . . 29 3 The structure of sets of lengths 35 3.1 Unions of sets of lengths . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2 Almost arithmetical multiprogressions . . . . . . . . . . . . . . . . 38 3.3 The characterizationproblem . . . . . . . . . . . . . . . . . . . . . 42 4 Addition theorems and direct zero-sum problems 45 4.1 The theorems of Kneser and of Kemperman-Scherk . . . . . . . . . 45 4.2 OntheErdo˝s–Ginzburg–Zivconstants(G)andonsomeofitsvariants 48 5 Inverse zero-sum problems and arithmetical consequences 57 5.1 Cyclic groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.2 Groups of higher rank . . . . . . . . . . . . . . . . . . . . . . . . . 70 viii Contents 5.3 Arithmetical consequences . . . . . . . . . . . . . . . . . . . . . . . 75 Bibliography 79 II Sumsets and Structure Imre Z. Ruzsa 87 Introduction 89 Notation 91 1 Cardinality inequalities 93 1.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 1.2 Plu¨nnecke’s method . . . . . . . . . . . . . . . . . . . . . . . . . . 95 1.3 Magnification and disjoint paths . . . . . . . . . . . . . . . . . . . 97 1.4 Layered product . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 1.5 The independent addition graph . . . . . . . . . . . . . . . . . . . 101 1.6 Different summands . . . . . . . . . . . . . . . . . . . . . . . . . . 102 1.7 Plu¨nnecke’s inequality with a large subset . . . . . . . . . . . . . . 104 1.8 Sums and differences . . . . . . . . . . . . . . . . . . . . . . . . . . 106 1.9 Double and triple sums . . . . . . . . . . . . . . . . . . . . . . . . 109 1.10 A+B and A+2B . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 1.11 On the non-commutative case . . . . . . . . . . . . . . . . . . . . . 114 2 Structure of sets with few sums 119 2.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 2.2 Torsion groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 2.3 Freiman isomorphism and small models . . . . . . . . . . . . . . . 125 2.4 Elements of Fourier analysis on groups . . . . . . . . . . . . . . . . 128 2.5 Bohr sets in sumsets . . . . . . . . . . . . . . . . . . . . . . . . . . 132 2.6 Some facts from the geometry of numbers . . . . . . . . . . . . . . 134 2.7 A generalized arithmetical progressionin a Bohr set . . . . . . . . 135 2.8 Freiman’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 2.9 Arithmetic progressions in sets with small sumset . . . . . . . . . . 139 3 Location and sumsets 141 3.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 3.2 The Cauchy–Davenportinequality . . . . . . . . . . . . . . . . . . 142 3.3 Kneser’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 3.4 Sumsets and diameter, part 1 . . . . . . . . . . . . . . . . . . . . . 146 3.5 The impact function . . . . . . . . . . . . . . . . . . . . . . . . . . 147 3.6 Estimates for the impact function in one dimension . . . . . . . . . 149 3.7 Multi-dimensional sets . . . . . . . . . . . . . . . . . . . . . . . . . 152 3.8 Results using cardinality and dimension . . . . . . . . . . . . . . . 154 Contents ix 3.9 The impact function and the hull volume . . . . . . . . . . . . . . 157 3.10 The impact volume . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 3.11 Hovanskii’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 163 4 Density 167 4.1 Asymptotic and Schnirelmann density . . . . . . . . . . . . . . . . 167 4.2 Schirelmann’s inequality . . . . . . . . . . . . . . . . . . . . . . . . 169 4.3 Mann’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 4.4 Schnirelmann’s theorem revisited . . . . . . . . . . . . . . . . . . . 173 4.5 Kneser’s theorem, density form . . . . . . . . . . . . . . . . . . . . 177 4.6 Adding a basis: Erdo˝s’ theorem . . . . . . . . . . . . . . . . . . . . 177 4.7 Adding a basis: Plu¨nnecke’s theorem, density form . . . . . . . . . 179 4.8 Adding the set of squares or primes. . . . . . . . . . . . . . . . . . 182 4.9 Essential components. . . . . . . . . . . . . . . . . . . . . . . . . . 184 5 Measure and topology 185 5.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 5.2 Raikov’s theorem and generalizations . . . . . . . . . . . . . . . . . 185 5.3 The impact function . . . . . . . . . . . . . . . . . . . . . . . . . . 187 5.4 Meditation on convexity and dimension . . . . . . . . . . . . . . . 188 5.5 Topologies on integers . . . . . . . . . . . . . . . . . . . . . . . . . 191 5.6 The finest compactification . . . . . . . . . . . . . . . . . . . . . . 193 5.7 Banach density . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 5.8 The difference set topology . . . . . . . . . . . . . . . . . . . . . . 196 Exercises 199 Bibliography 207 III Thematic seminars 211 1 A survey on additive and multiplicative decompositions of sumsets and of shifted sets, Christian Elsholtz 213 1.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 1.2 Part I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 1.2.1 Multiplicative decompositions of sumsets . . . . . . . . . . 214 1.2.2 Multiplicative decompositions of shifted sets. . . . . . . . . 216 1.2.3 Some background from sieve methods . . . . . . . . . . . . 217 1.2.4 Proof of Theorem ?? . . . . . . . . . . . . . . . . . . . . . . 219 1.3 Part II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 1.3.1 Sumsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 1.3.2 Counting methods . . . . . . . . . . . . . . . . . . . . . . . 222 1.3.3 A result from extremal graph theory . . . . . . . . . . . . . 223 x Contents 1.3.4 The case of primes . . . . . . . . . . . . . . . . . . . . . . . 225 1.3.5 Chains of primes in arithmetic progressions . . . . . . . . . 226 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 2 On the detailed structure of sets with small additive property, Gregory A. Freiman 233 2.1 Small doubling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 2.2 Sums of different sets. . . . . . . . . . . . . . . . . . . . . . . . . . 237 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 3 The isoperimetric method, Yahya O. Hamidoune 241 3.1 Universal bounds of set products . . . . . . . . . . . . . . . . . . . 241 3.2 The Frobenius problem . . . . . . . . . . . . . . . . . . . . . . . . 243 3.3 The α+β-theorems . . . . . . . . . . . . . . . . . . . . . . . . . . 244 3.3.1 Direct theorems. . . . . . . . . . . . . . . . . . . . . . . . . 244 3.3.2 Inverse theorems . . . . . . . . . . . . . . . . . . . . . . . . 245 3.4 Torsion-free groups: The isoperimetric approach. . . . . . . . . . . 246 3.5 The isoperimetric formalism . . . . . . . . . . . . . . . . . . . . . . 248 3.6 The structure of k-atoms . . . . . . . . . . . . . . . . . . . . . . . 250 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 4 Additive structure of difference sets, Norbert Hegyva´ri 253 4.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 4.2 The case D(A) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 4.3 An intermezzo; D(D(A)) is highly well structured . . . . . . . . . . 258 4.4 First difference sets and Bohr sets I. . . . . . . . . . . . . . . . . . 258 4.5 Raimi’s theorem; difference set of partitions . . . . . . . . . . . . . 261 4.6 First difference sets and Bohr sets II; Følner’s theorem . . . . . . . 263 4.7 Applications of Følner theorem . . . . . . . . . . . . . . . . . . . . 263 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 5 The polynomial method in additive combinatorics, Gyula Ka´rolyi 267 5.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 5.2 Applications of the polynomial method to additive problems. . . . 271 5.3 Appendix: The Vandermonde matrix . . . . . . . . . . . . . . . . 275 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 6 Problems in additive number theory, III, Melvyn B. Nathanson 279 6.1 What sets are sumsets? . . . . . . . . . . . . . . . . . . . . . . . . 279 6.2 Describing the structure of hA as h→∞ . . . . . . . . . . . . . . 280 Contents xi 6.3 Representation functions . . . . . . . . . . . . . . . . . . . . . . . . 280 6.4 Sets with more sums than differences . . . . . . . . . . . . . . . . . 282 6.5 Comparative theory of linear forms . . . . . . . . . . . . . . . . . . 284 6.6 The fundamental theorem of additive number theory . . . . . . . . 286 6.7 Thin asymptotic bases . . . . . . . . . . . . . . . . . . . . . . . . . 287 6.8 Minimal asymptotic bases . . . . . . . . . . . . . . . . . . . . . . . 288 6.9 Maximal asymptotic non-bases . . . . . . . . . . . . . . . . . . . . 289 6.10 Complementing sets of integers . . . . . . . . . . . . . . . . . . . . 290 6.11 The Caccetta–H¨aggkvistconjecture . . . . . . . . . . . . . . . . . . 293 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 7 Incidences and the spectra of graphs, Jozsef Solymosi 299 7.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 7.2 The sum-product problem . . . . . . . . . . . . . . . . . . . . . . . 300 7.2.1 The sum-product graph . . . . . . . . . . . . . . . . . . . . 301 7.2.2 The spectral bound . . . . . . . . . . . . . . . . . . . . . . 303 7.3 Three-term arithmetic progressions . . . . . . . . . . . . . . . . . . 304 7.3.1 The 3-AP graph . . . . . . . . . . . . . . . . . . . . . . . . 304 7.4 Sidon functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 7.4.1 Sidon functions . . . . . . . . . . . . . . . . . . . . . . . . . 306 7.4.2 A bipartite incidence graph . . . . . . . . . . . . . . . . . . 308 7.4.3 The spectral bound . . . . . . . . . . . . . . . . . . . . . . 309 7.5 Incidence bounds on pseudolines . . . . . . . . . . . . . . . . . . . 310 7.5.1 The incidence bound . . . . . . . . . . . . . . . . . . . . . . 310 7.5.2 Strongly regular graphs . . . . . . . . . . . . . . . . . . . . 311 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313 8 Multi-dimensional inverse additive problems, Yonutz V. Stanchescu 315 8.1 Direct and inverse problems of additive and combinatorial number theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 8.2 The simplest inverse problem for sums of sets in several dimensions 316 8.3 Small doubling property on the plane . . . . . . . . . . . . . . . . 318 8.4 Planar sets with no three collinear points on a line . . . . . . . . . 321 8.5 Exact structure results . . . . . . . . . . . . . . . . . . . . . . . . . 323 8.6 Difference sets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 8.7 Finite Abelian groups . . . . . . . . . . . . . . . . . . . . . . . . . 325 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327