# Plünnecke–Ruzsa inequality

The **Plünnecke–Ruzsa inequality** is a theorem of [additive combinatorics](https://www.edgepedia.org/additive-combinatorics) that bounds the size of iterated sumsets and difference sets: if two finite sets \( A \) and \( B \) in an abelian group satisfy \( |A+B| \le K|A| \), then \( |kB - \ell B| \le K^{k+\ell}|A| \) for all non-negative integers \( k \) and \( \ell \).<sup>[1](https://people.maths.ox.ac.uk/greenbj/papers/additive-combinatorics.pdf)</sup> Here \( A+B = \{a+b : a \in A, b \in B\} \) is the sumset, \( kB \) denotes the set of sums of \( k \) elements of \( B \), and \( K \) measures how little \( A \) expands when added to \( B \). The hypothesis \( |A+B| \le K|A| \) is a small-doubling condition, and the theorem says that such controlled growth propagates: every further iterated sumset grows at most exponentially in the number of summands, with base \( K \).<sup>[2](https://simonrs.com/eulercircle/combinatorics2025/om-addcomb.pdf)</sup>

| Key fact | Detail |
|---|---|
| Statement | If \( |A+B| \le K|A| \) in an abelian group, then \( |kB - \ell B| \le K^{k+\ell}|A| \) for all integers \( k, \ell \ge 0 \)<sup>[1](https://people.maths.ox.ac.uk/greenbj/papers/additive-combinatorics.pdf)</sup> |
| Original proof | Helmut Plünnecke, 1970, *Journal für die reine und angewandte Mathematik* 243, pp. 171–183, by graph-theoretic methods<sup>[3](https://www.degruyterbrill.com/document/doi/10.1515/crll.1970.243.171/html)</sup> |
| Elementary proof | Giorgis Petridis, 2012, *Combinatorica* 32(6), 721–733, avoiding Menger's theorem and graph products<sup>[4](https://www.arxiv.symmetricfunctions.com/paper/1101.3507v3)</sup> |
| Different summands | If \( |A+B_i| \le K_i|A| \) for \( i = 1, \ldots, m \), there is \( A' \subseteq A \) with \( |A'+B_1+\cdots+B_m| \le K_1 \cdots K_m |A'| \)<sup>[5](https://mathoverflow.net/questions/488042/petridis-inequality-and-pl%C3%BCnneckes-inequality-with-different-summands)</sup> |
| Formal verification | Formalized in Lean's Mathlib and in the Isabelle Archive of Formal Proofs (2022)<sup>[6](https://isa-afp.org/entries/Pluennecke_Ruzsa_Inequality.html)</sup><sup> • </sup><sup>[7](https://math.iisc.ac.in/~gadgil/proofs-and-programs-2023/doc/Mathlib/Combinatorics/Additive/PluenneckeRuzsa.html)</sup> |

## Statement and meaning

The theorem is usually stated in the form recorded by Ben Green: suppose \( A \) and \( B \) are finite sets in an abelian group with \( |A+B| \le K|A| \). Then for integers \( k, \ell \ge 0 \),

\[ |kB - \ell B| \le K^{k+\ell}|A|. \]

The number \( K \) is an expansion factor: it says that adding \( B \) to \( A \) enlarges \( A \) by at most a factor \( K \). The conclusion converts this one-step control into control of arbitrarily complicated expressions built from \( B \), such as \( 3B - 2B \), at the multiplicative price \( K^{k+\ell} \).<sup>[1](https://people.maths.ox.ac.uk/greenbj/papers/additive-combinatorics.pdf)</sup> In lecture formulations the same result appears as: a set with bounded doubling has bounded growth in all further iterated sumsets.<sup>[8](https://ocw.mit.edu/courses/18-217-graph-theory-and-additive-combinatorics-fall-2019/245c8a2c0be8190116b9cc243d3bc1d0_RwikpgvkN_o.pdf)</sup>

The subset version is essential to the proof. A stronger intermediate statement holds: there exists a non-empty subset \( X \subseteq A \) for which the ratio \( |X+B|/|X| \) is minimal, and \( |X + kB| \le K^k|X| \) for every \( k \).<sup>[1](https://people.maths.ox.ac.uk/greenbj/papers/additive-combinatorics.pdf)</sup><sup> • </sup><sup>[2](https://simonrs.com/eulercircle/combinatorics2025/om-addcomb.pdf)</sup> This well-chosen portion of \( A \) captures the least-expanding part of the interaction with \( B \), and it controls the growth of the whole additive structure generated by \( B \).<sup>[2](https://simonrs.com/eulercircle/combinatorics2025/om-addcomb.pdf)</sup> Setting \( \ell = 0 \) and \( k \) arbitrary gives the special case \( |kB| \le K^k|A| \).<sup>[2](https://simonrs.com/eulercircle/combinatorics2025/om-addcomb.pdf)</sup>

A version for different summands generalizes the single-\( B \) statement: if \( A, B_1, \ldots, B_m \) are finite subsets of an abelian group with \( |A+B_i| \le K_i|A| \), then there is a subset \( A' \) of \( A \) such that \( |A' + B_1 + \cdots + B_m| \le K_1 \cdots K_m |A'| \).<sup>[5](https://mathoverflow.net/questions/488042/petridis-inequality-and-pl%C3%BCnneckes-inequality-with-different-summands)</sup> Ruzsa proved a general version of Plünnecke's inequality for different summands in 2008, assuming information on the sumsets \( A + B_{i_1} + \cdots + B_{i_l} \) for all choices of indices and deducing control of \( X + B_1 + \cdots + B_k \) for some non-empty \( X \subseteq A \).<sup>[9](https://arxiv.org/abs/0810.1488)</sup>

## History

**Plünnecke, 1970.** Helmut Plünnecke proved the inequality in the paper "Eine zahlentheoretische Anwendung der Graphentheorie" ("A number-theoretic application of graph theory"), published in 1970 in volume 243 of the *Journal für die reine und angewandte Mathematik*, pages 171–183.<sup>[3](https://www.degruyterbrill.com/document/doi/10.1515/crll.1970.243.171/html)</sup> His original proof was quite long and involved a fair amount of machinery from graph theory.<sup>[1](https://people.maths.ox.ac.uk/greenbj/papers/additive-combinatorics.pdf)</sup>

**Ruzsa, 1989.** His proof, in turn, was a great simplification of the arguments implicit in Plünnecke's work.<sup>[10](https://www.borisbukh.org/DiscreteMath14/notes_additive_inequalities.pdf)</sup> Ruzsa also proved the different-summands generalization.<sup>[9](https://arxiv.org/abs/0810.1488)</sup>

**Petridis, 2011–2012.** Giorgis Petridis, a combinatorialist whose work on sumset estimates appears in *Combinatorica* and *Combinatorics, Probability & Computing*, introduced a new method in two papers.<sup>[11](https://dblp.org/pid/55/10545.html)</sup> In "Plünnecke's Inequality" (2011) he gave a proof completed with no reference to [Menger's theorem](https://www.edgepedia.org/mengers-theorem) or Cartesian products of graphs, showing that the inequality is a direct consequence of Plünnecke's conditions and little else.<sup>[12](https://arxiv.org/abs/1101.2532)</sup> In "New Proofs of Plünnecke-type Estimates for Product Sets in Groups" (*Combinatorica* 32 (2012), 721–733) he presented a new and unexpectedly short proof of the Plünnecke–Ruzsa sumset inequalities for abelian groups, together with a new proof of a theorem of Tao on triple products that generalizes these inequalities without any commutativity assumption, and a further generalization to general groups.<sup>[4](https://www.arxiv.symmetricfunctions.com/paper/1101.3507v3)</sup> The Petridis proof is now the standard one taught: it chooses a non-empty \( X \subseteq A \) minimizing \( |X+B|/|X| \) and shows by induction on \( n \) that \( |X + nB| \le (|X+B|/|X|)^n |X| \).<sup>[13](https://calc-path.com/combinatorics/modules/algebraic-combinatorics)</sup> It is a direct proof by induction, unusual for extremal combinatorics.<sup>[10](https://www.borisbukh.org/DiscreteMath14/notes_additive_inequalities.pdf)</sup>

## The key lemma

The modern proof rests on a triple-product estimate. In one form, Petridis' lemma states: suppose \( A, B \subseteq G \) are finite sets with \( |A+B| \le K|B| \), and \( Z \subseteq B \) is non-empty with \( |A+Z|/|Z| \) minimal. Then \( |A+Z+C| \le K|Z+C| \) for all finite \( C \subseteq G \).<sup>[14](https://doi.org/10.1016/j.ejc.2015.02.006)</sup> An equivalent formulation gives \( |A+B'+C| \cdot |B'| \le |A+B'| \cdot |B'+C| \) whenever \( B' \subseteq B \) minimizes \( |A+B'|/|B'| \).<sup>[5](https://mathoverflow.net/questions/488042/petridis-inequality-and-pl%C3%BCnneckes-inequality-with-different-summands)</sup> The lemma is proved by induction on \( |C| \), translating so that \( 0 \in C \) and peeling off one element at a time.<sup>[10](https://www.borisbukh.org/DiscreteMath14/notes_additive_inequalities.pdf)</sup>

The second ingredient is the **Ruzsa triangle inequality**: if \( A, B, C \) are finite subsets of an abelian group, then \( |A|\,|B-C| \le |A-B|\,|A-C| \).<sup>[15](https://ocw.mit.edu/courses/18-217-graph-theory-and-additive-combinatorics-fall-2019/c145c88ab6b56bf04e52b1bc51a2d592_MIT18_217F19_ch7.pdf)</sup> It is proved by an explicit injection \( (A-B) \times C \to (A-C) \times (C-B) \).<sup>[10](https://www.borisbukh.org/DiscreteMath14/notes_additive_inequalities.pdf)</sup> Combining Plünnecke's inequality, which bounds sums, with Ruzsa's triangle inequality, which converts sums into differences and transfers the bound from the subset \( X \) back to \( A \), yields the full \( |kB - \ell B| \le K^{k+\ell}|A| \).<sup>[2](https://simonrs.com/eulercircle/combinatorics2025/om-addcomb.pdf)</sup><sup> • </sup><sup>[13](https://calc-path.com/combinatorics/modules/algebraic-combinatorics)</sup>

## Applications

**Freiman's theorem.** In the standard proof architecture, Plünnecke–Ruzsa first bounds \( |nA - mA| \) by \( K^{O(1)}|A| \), so all iterated sumsets are under control before Freiman modeling, Bogolyubov's lemma, and geometry of numbers are applied.<sup>[13](https://calc-path.com/combinatorics/modules/algebraic-combinatorics)</sup> In Yufei Zhao's graduate course at MIT on graph theory and additive combinatorics, the inequality is proved once and then used many times in the development of [Freiman's theorem](https://www.edgepedia.org/freimans-theorem).<sup>[8](https://ocw.mit.edu/courses/18-217-graph-theory-and-additive-combinatorics-fall-2019/245c8a2c0be8190116b9cc243d3bc1d0_RwikpgvkN_o.pdf)</sup>

**Approximate groups.** Plünnecke's inequalities are one of the two fundamental tools, alongside Ruzsa's covering lemma, illustrated in the theory of approximate groups: if \( A \) is a finite subset of an abelian group with \( |A+A| \le K|A| \), then \( |mA - nA| \le K^{m+n}|A| \), an approximate version of the subgroup property \( mH = H \).<sup>[16](https://ems.press/content/serial-article-files/11508?nt=1)</sup>

**Wider use.** The inequality is applied wherever many-fold sumsets must be bounded from a single doubling assumption, for example in bounding \( |kA - kA| \le K^{2k}|B| \) in work on Vinogradov mean value theorems in finite fields,<sup>[17](https://academic.oup.com/qjmath/article/75/3/1007/7721813)</sup> in sum-product problems,<sup>[18](https://pmc.ncbi.nlm.nih.gov/articles/PMC10952923/)</sup> in bounds for sums of dilates,<sup>[19](https://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p37)</sup> and in the study of sumsets of progression-free sets.<sup>[20](https://doi.org/10.1007/s11139-025-01157-9)</sup>

## Sharpness and scope

Petridis investigated the sharpness of Plünnecke's inequality and showed that it can be sharp for arbitrarily long, but not for infinite, commutative graphs; a key step is a construction of arbitrarily long regular commutative graphs, and he also proved a necessary condition for the inequality to be attained.<sup>[12](https://arxiv.org/abs/1101.2532)</sup>

**Non-abelian groups.** The inequality does not hold as stated without commutativity. In the free product \( H * \langle x \rangle \) with \( x \) of infinite order, the set \( A = H \cup \{x\} \) satisfies \( |A^2| \le 3|A| \) but \( A^3 \supseteq HxH \) with \( |HxH| = |H|^2 \), so \( |A^3| \ge \tfrac{1}{4}|A|^2 \).<sup>[16](https://ems.press/content/serial-article-files/11508?nt=1)</sup> Replacing small doubling with small tripling, \( |A^3| \le K|A| \), restores the conclusion \( |A^m| \le K^{m-2}|A| \) by an argument of Ruzsa.<sup>[16](https://ems.press/content/serial-article-files/11508?nt=1)</sup> Petridis' method itself works just as well for non-abelian groups as for abelian groups, and his 2012 paper includes non-commutative generalizations.<sup>[14](https://doi.org/10.1016/j.ejc.2015.02.006)</sup><sup> • </sup><sup>[4](https://www.arxiv.symmetricfunctions.com/paper/1101.3507v3)</sup>

**Compact groups.** A Plünnecke–Ruzsa inequality extends to analytic settings: for \( K \)-analytic sets \( A, B \) in a compact abelian group with [Haar measure](https://www.edgepedia.org/haar-measure) \( \mu \) and \( 0 < \mu(A+B) \le \alpha\,\mu(A) \), one has \( \mu(mB - nB) \le \alpha^{m+n}\mu(A) \), proved by approximating the compact group by Lie groups and passing to the limit.<sup>[21](https://arxiv.org/abs/1712.07615)</sup>

**Formal proofs.** The inequality has been machine-verified twice: Angeliki Koutsoukou-Argyraki and Lawrence C. Paulson formalized Plünnecke's inequality and the Plünnecke–Ruzsa inequality in the Isabelle Archive of Formal Proofs in May 2022, following [Timothy Gowers](https://www.edgepedia.org/timothy-gowers)' 2022 Cambridge notes "Introduction to Additive Combinatorics" and using a proof due to Petridis;<sup>[6](https://isa-afp.org/entries/Pluennecke_Ruzsa_Inequality.html)</sup> the result is also in the Lean mathematical library Mathlib, where the addition version is noted to be genuinely harder than the subtraction version because a double-counting argument is unavailable.<sup>[7](https://math.iisc.ac.in/~gadgil/proofs-and-programs-2023/doc/Mathlib/Combinatorics/Additive/PluenneckeRuzsa.html)</sup>

## References

1. [Ben Green, "Sumset inequalities", notes on additive combinatorics, Theorem 4.4.1](https://people.maths.ox.ac.uk/greenbj/papers/additive-combinatorics.pdf)
2. ["Topics in Additive Combinatorics", lecture notes, Section 4: Plünnecke's Inequality](https://simonrs.com/eulercircle/combinatorics2025/om-addcomb.pdf)
3. [Helmut Plünnecke (1970). "Eine zahlentheoretische Anwendung der Graphentheorie." Journal für die reine und angewandte Mathematik 243, 171–183](https://www.degruyterbrill.com/document/doi/10.1515/crll.1970.243.171/html)
4. [Giorgis Petridis (2012). "New Proofs of Plünnecke-type Estimates for Product Sets in Groups." Combinatorica 32(6), 721–733](https://www.arxiv.symmetricfunctions.com/paper/1101.3507v3)
5. [MathOverflow: "Petridis' inequality and Plünnecke's inequality with different summands"](https://mathoverflow.net/questions/488042/petridis-inequality-and-pl%C3%BCnneckes-inequality-with-different-summands)
6. [Angeliki Koutsoukou-Argyraki, Lawrence C. Paulson (2022). "The Plünnecke-Ruzsa Inequality." Archive of Formal Proofs](https://isa-afp.org/entries/Pluennecke_Ruzsa_Inequality.html)
7. [Mathlib.Combinatorics.Additive.PluenneckeRuzsa documentation](https://math.iisc.ac.in/~gadgil/proofs-and-programs-2023/doc/Mathlib/Combinatorics/Additive/PluenneckeRuzsa.html)
8. [MIT OCW 18.217, Lecture 22 notes: Structure of set addition II](https://ocw.mit.edu/courses/18-217-graph-theory-and-additive-combinatorics-fall-2019/245c8a2c0be8190116b9cc243d3bc1d0_RwikpgvkN_o.pdf)
9. [Imre Ruzsa (2008). "Plunnecke's inequality for different summands." arXiv:0810.1488](https://arxiv.org/abs/0810.1488)
10. [Boris Bukh, "Walk through Combinatorics: Sumset inequalities", course notes](https://www.borisbukh.org/DiscreteMath14/notes_additive_inequalities.pdf)
11. [dblp: Giorgis Petridis](https://dblp.org/pid/55/10545.html)
12. [Giorgis Petridis (2011). "Plünnecke's Inequality." arXiv:1101.2532](https://arxiv.org/abs/1101.2532)
13. ["Combinatorics — Algebraic and Additive Combinatorics"](https://calc-path.com/combinatorics/modules/algebraic-combinatorics)
14. ["A statistical approach to covering lemmas", European Journal of Combinatorics](https://doi.org/10.1016/j.ejc.2015.02.006)
15. [MIT OCW 18.217, Chapter 7: Structure of set addition](https://ocw.mit.edu/courses/18-217-graph-theory-and-additive-combinatorics-fall-2019/c145c88ab6b56bf04e52b1bc51a2d592_MIT18_217F19_ch7.pdf)
16. [Matthew C. H. Tointon, "A Brief Introduction to Approximate Groups", EMS Newsletter, March 2020](https://ems.press/content/serial-article-files/11508?nt=1)
17. ["Quadratic Vinogradov mean value theorem in finite fields", Quarterly Journal of Mathematics 75(3)](https://academic.oup.com/qjmath/article/75/3/1007/7721813)
18. ["Convexity, superquadratic growth, and dot products", PMC](https://pmc.ncbi.nlm.nih.gov/articles/PMC10952923/)
19. ["New Upper Bound for Sums of Dilates", Electronic Journal of Combinatorics 24(3), #P3.37](https://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p37)
20. ["A note on sumsets of progression-free sets", The Ramanujan Journal](https://doi.org/10.1007/s11139-025-01157-9)
21. ["A Plünnecke-Ruzsa inequality in compact abelian groups", arXiv:1712.07615](https://arxiv.org/abs/1712.07615)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Numbers and algebra › Number theory › Analytic number theory › Additive number theory › Sumsets and additive combinatorics*

*Initially written Sep 17, 2026 · Reviewed: Sep 19, 2026; Oct 15, 2026 · Edited: Sep 19, 2026; Oct 15, 2026; Oct 25, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license