Sumsets and inverse theorems

Size and structure of A+B, hA and restricted or signed sumsets: Cauchy–Davenport and Vosper, Freiman-type and polynomial Freiman–Ruzsa theorems, small doubling, sums of dilates, h-fold sumsets with distinct terms, rectification, sets determined by k-sums, max-min (lunar) decompositions, and sum-product and product-set growth.

• Difference sets of full-dimensional lattice sets
• Distinct consecutive sums
• Explicit sum-product expanders over prime fields
• Large subspaces in sumsets
• Max-min indecomposable sequences and lunar primes
• Polynomial Freiman–Ruzsa theorem
• Possible sizes of h-fold sumsets
• Progressions in sets of small doubling
• Restricted signed sumsets
• Sets determined by their k-sums
• Small doubling and small tripling
• Sum-product estimates for sets of small doubling
• Sum-product problem over the reals
• Sums and products along graphs
• Sums of dilates
• Sumsets with at least r distinct terms
• Vosper's theorem

TheoremCauchy–Davenport–Chowla theorem#✓fully proved

Let \(q\) be a positive integer and let \(A\) and \(B\) be nonempty subsets of \(\mathbb{Z}/q\mathbb{Z}\) such that \(0 \in B\) and every nonzero element of \(B\) is a unit of \(\mathbb{Z}/q\mathbb{Z}\). Then \(|A + B| \ge \min(q, |A| + |B| - 1)\), where \(A + B = \{a + b : a \in A, b \in B\}\).

theorem cauchy_davenport_chowla (q : ℕ) (A B : Finset (ZMod q)) :
    0 < q → A.Nonempty → B.Nonempty → (0 : ZMod q) ∈ B →
      (∀ b ∈ B, b ≠ (0 : ZMod q) → IsUnit b) →
        min q (A.card + B.card - 1) ≤ (A + B).card

Sources

• R. C. Vaughan, The Hardy–Littlewood Method, 2nd ed., Cambridge Tracts in Mathematics 125, Cambridge University Press, 1997, Lemma 2.14; also stated as Lemma 3.5 in H. Wang and S. Tian, arXiv:2608.12397v1. Mathlib's ZMod.cauchy_davenport covers the prime-modulus special case.

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.