Plünnecke–Ruzsa inequalities

Among the nonempty subsets of A choose X minimizing the ratio of the size of X+B to the size of X. Such a minimizer exists because A is finite. Call its ratio kappa; it is at most the original ratio K. The minimizing property says that every subset of X expands by at least kappa under addition by B. This lower bound on smaller pieces is the extra ingredient that a generic subset, or the whole set A, need not satisfy.

Petridis’s lemma turns that local minimality into a global upper bound after any further finite set C is added. A proof orders the translates of X indexed by C and separates each new translate into points already covered and points newly exposed. The minimizing property bounds the expansion of the discarded pieces, allowing an upper bound on what the new pieces contribute. Commutativity aligns the translated copies. This is a proof mechanism, not an assumption that different translates are disjoint.

Take C to be successive iterated sumsets of B. Induction then bounds X plus m copies of B by kappa to the power m times the size of X, for every nonnegative integer m. The same selected X works throughout this induction. Define zero copies of B to mean the singleton containing the group identity. That convention makes the initial case exact and avoids confusing zero-fold addition with the empty set, whose sum with any set would be empty.

The conclusion concerns X, not necessarily A. Replacing X by A in the intermediate inequality requires an additional argument or hypothesis; the minimizing-subset proof by itself does not supply it. For example, a set may contain pieces with different expansion rates, and selecting the least-expanding piece can be essential. The theorem does not promise that X retains a fixed proportion of A either. Separate later results address large subsets, sometimes at a cost in constants or exponents.

Apply the Ruzsa triangle inequality with the intermediate set equal to negative X. The two numerator factors become X plus m copies of B and X plus n copies of B, while the denominator is the size of X. Substituting the subset-growth bounds leaves an upper bound for mB−nB by K to the power m+n times the size of X. Finally enlarge that size to the size of A. This yields the usual Plünnecke–Ruzsa estimate for all nonnegative m and n.

In particular, small self-doubling gives exponential-in-the-number-of-summands control on iterated differences. The estimate is often deliberately loose, and finite ambient groups add an independent upper bound from their total size. It does not assert that every sumset realizes the exponential growth rate. Noncommutative groups require different formulations because the translate argument and rearrangement of sums no longer apply unchanged. The role of this theorem is to carry a bounded growth hypothesis into the higher sums needed by structural arguments.