Sumsets and basic growth inequalities

Define the sumset by allowing one summand from each input set; repeated outputs are recorded only once. The product of the two cardinalities counts ordered representations, rather than distinct sums. Fixing any one element in either input gives an injective translate of the other, so the sumset has at least the larger input cardinality and at most their product. Both inequalities are elementary, but equality cases already distinguish closure from nearly collision-free addition.

For a single set the doubling constant divides the size of its self-sum by the original size. A bounded constant means that many ordered pairs have collided when the set is large. It does not mean that every element participates equally in those collisions. For unequal inputs the quotient by the first set is an asymmetric expansion ratio. Swapping the inputs preserves the numerator but changes this ratio, so a growth statement must specify its denominator.

Suppose the inputs lie in the integers, listed in increasing order. Start with the sums of the least element of the second input and every element of the first. Continue with the greatest element of the first input and the remaining elements of the second. This produces a strictly increasing chain with one fewer element than the sum of the input sizes. No representation collision can occur along that chosen chain, giving the integer lower bound below.

That argument uses an order compatible with addition. In a cyclic group there is no globally compatible linear order, and wraparound can invalidate the bound. For the group of prime order the Cauchy–Davenport theorem supplies a replacement, truncated at the ambient size. The prime assumption is substantive: a proper subgroup in a composite-order cyclic group has a self-sum equal to itself, violating the untruncated integer estimate. This theorem is stated here; the elementary ordered-chain proof does not prove it.

An integer arithmetic progression with a fixed nonzero step has self-sum consisting of twice as many positions minus one. Its doubling constant therefore approaches two as its length grows. A finite subgroup instead has doubling exactly one. These are two different models of additive structure. A translated subgroup also has doubling one, even when the translate itself does not contain the identity or form a subgroup. Translation preserves cardinality and all additive relations involving equally many summands.

The converse direction requires deeper results: small doubling constrains a set, but the appropriate structural object depends on torsion and on the ambient group. Before invoking such a theorem, compute a few sumsets exactly and test whether the proposed model respects the ambient arithmetic. A small numerical example can diagnose a missing wraparound hypothesis, while it cannot establish that every bounded-doubling set has the observed form. Later lessons turn this initial counting signal into rigorous structure theorems.