Top

Published in:

2014 | OriginalPaper | Chapter

The Plünnecke–Ruzsa Inequality: An Overview

Author : G. Petridis

Published in: Combinatorial and Additive Number Theory

Publisher: Springer New York

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this expository article we present an overview of the Plünnecke–Ruzsa inequality: the known proofs, some of its well-known applications and possible extensions. We begin with the graph-theoretic setting in which Plünnecke and later Ruzsa worked in. The more purely combinatorial proofs of the inequality are subsequently presented. In the concluding sections we discuss the sharpness of the various results presented thus far and possible extensions of the inequality to the non-commutative setting.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter On the Grothendieck Group Associated to Solutions of a Functional Equation Arising from Multiplication of Quantum Integers

next chapter Lerch Quotients, Lerch Primes, Fermat-Wilson Quotients, and the Wieferich-Non-Wilson Primes 2, 3, 14771

P. Balister, B. Bollobás, Projections, entropy and sumsets. Combinatorica 32, 125–141 (2012)MathSciNetCrossRefMATH

J. Bourgain, N. Katz, T. Tao, A sum-product estimate in finite fields, and applications. Geom. Funct. Anal. 14, 27–57 (2004)MathSciNetCrossRefMATH

W.T. Gowers, A new proof of Szemerédi’s theorem. Geom. Funct. Anal. 11, 465–588 (2001)MathSciNetCrossRefMATH

W.T. Gowers, A new way of proving sumset estimates (2011), http://gowers.wordpress.com/2011/02/10/a-new-way-of-proving-sumset-estimates/

A. Granville, An introduction to additive combinatorics, in Additive Combinatorics, ed. by A. Granville, M.B. Nathanson, J. Solymosi. CRM Proceedings and Lecture Notes (American Mathematical Society, New York, 2007), pp. 1–27

B.J. Green, T. Tao, An inverse theorem for the Gowers U ³(G) norm. Proc. Edin. Math. Soc. (2) 51(1), 75–153 (2008)

K. Gyarmati, M. Maltolcsi, I.Z. Ruzsa, Plünnecke’s inequality for different summands, in Building Bridges: Between Mathematics and Computer Science, ed. by M. Grötschel, G.O.H. Katona. Bolyai Society Mathematical Studies, vol. 19 (Springer, New York, 2008), pp. 309–320

K. Gyarmati, M. Maltolcsi, I.Z. Ruzsa, A superadditivity and submultiplicativity property for cardinalities of sumsets. Combinatorica 30(2), 163–174 (2010)MathSciNetCrossRefMATH

H.A. Helfgott, Growth and generation in \(SL_{2}(\mathbb{Z}/p\mathbb{Z})\). Ann. Math. 167, 601–623 (2008)MathSciNetCrossRefMATH

10.

M. Madiman, A.W. Marcus, P. Tetali, Entropy and set cardinality inequalities for partition-determined functions, with applications to sumsets. Random Structures Algorithms 40, 399–424 (2012)MathSciNetCrossRefMATH

11.

M.B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets (Springer, New York, 1996)CrossRefMATH

12.

G. Petridis, New proofs of Plünnecke-type estimates for product sets in groups. Combinatorica 32, 721–733 (2012)MathSciNetCrossRefMATH

13.

G. Petridis, Plünnecke’s inequality. Combin. Probab. Comput. 20, 921–938 (2011)MathSciNetCrossRefMATH

14.

G. Petridis, Upper bounds on the cardinality of higher sumsets. Acta Arith. 158, 299–319 (2013)MathSciNetCrossRefMATH

15.

H. Plünnecke, Eine zahlentheoretische anwendung der graphtheorie. J. Reine Angew. Math. 243, 171–183 (1970)MathSciNetMATH

16.

C. Reiher, Comments on ‘A new way of proving sumset estimates’ by Gowers, W.T. (2011), http://gowers.wordpress.com/2011/02/10/a-new-way-of-proving-sumset-estimates/

17.

I.Z. Ruzsa, On the cardinality of A + A and A − A, in Combinatorics (Keszthely 1976), ed. by A. Hajnal, V.T. Sós. Coll. Math. Soc. J. Bolyai, vol. 18 (North Holland, Amsterdam, 1978), pp. 933–938

18.

I.Z. Ruzsa, An application of graph theory to additive number theory. Scientia Ser. A 3, 97–109 (1989)MathSciNetMATH

19.

I.Z. Ruzsa, Addendum to: an application of graph theory to additive number theory. Scientia Ser. A 4, 93–94 (1990/1991)

20.

I.Z. Ruzsa, Generalized arithmetical progressions and sumsets. Acta Math. Hungar. 65(4), 379–388 (1994)MathSciNetCrossRefMATH

21.

I.Z. Ruzsa, Cardinality questions about sumsets, in Additive Combinatorics, ed. by A. Granville, M.B. Nathanson, J. Solymosi. CRM Proceedings and Lecture Notes (American Mathematical Society, New York, 2007), pp. 195–205

22.

I.Z. Ruzsa, Sumsets and structure, in Combinatorial Number Theory and Additive Group Theory (Springer, New York, 2009)

23.

I.Z. Ruzsa, Towards a noncommutative Plünnecke-type inequality, in An Irregular Mind Szemeredi is 70, ed. by I. Bárány, J. Solymosi. Bolyai Society Mathematical Studies, vol. 21 (Springer, New York, 2010), pp. 591–605

24.

T.W. Sanders, Green’s sumset problem at density one half. Acta Arith. 146(1), 91–101 (2011)MathSciNetCrossRefMATH

25.

T. Tao, Additive combinatorics. http://www.math.ucla.edu/~tao/254a.1.03w/notes1.dvi

26.

T. Tao, The tensor power trick. http://terrytao.wordpress.com/2008/08/25/tricks-wiki-article-the-tensor-product-trick/

27.

T. Tao, Product set estimates for non-commutative groups. Combinatorica 28(5), 574–594 (2008)CrossRef

28.

T. Tao, V.H. Vu, Additive Combinatorics (Cambridge University Press, Cambridge, 2006)CrossRefMATH

Title: The Plünnecke–Ruzsa Inequality: An Overview
Author: G. Petridis
Publisher: Springer New York
Book: Combinatorial and Additive Number Theory
Print ISBN: 978-1-4939-1600-9

Electronic ISBN: 978-1-4939-1601-6

Copyright Year: 2014
DOI: https://doi.org/10.1007/978-1-4939-1601-6_16

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner