Minkowski sum

Definition

Definition for two subsets

Suppose $G$ is an abelian group with the group operation denoted additively, and $A,B$ are (possibly equal, possibly distinct) subsets of $G$ . The Minkowski sum or sumset of $A$ and $B$ , denoted $A+B$ , is defined as:

$\!A+B:=\{a+b\mid a\in A,b\in B\}$

Definition for finitely many subsets

Suppose $G$ is an abelian group with the group operation denoted additively, and $A_{1},A_{2},\dots ,A_{n}$ are (possibly equal, possibly distinct) subsets of $G$ . The Minkowski sum or sumset of all these subsets, denoted $A_{1}+A_{2}+\dots +A_{n}$ or $\sum _{i=1}^{n}A_{i}$ , is defined as:

$\sum _{i=1}^{n}A_{i}=\{\sum _{i=1}^{n}a_{i}\mid a_{i}\in A_{i}\}$

Non-abelian version

The non-abelian version of this is simply called product of subsets in the group. The non-abelian group is not commutative, i.e., it is possible to have subsets $A,B$ of a group $G$ such that $AB\neq BA$ . In fact, a product of subgroups also need not commute. In fact, it commutes if and only if the product either way is a subgroup.

Facts

Upper bounds on size

The size of the Minkowski sum of two subsets is bounded by the product of their sizes. Similarly, the size of the Minkowski sum of finitely many subsets is bounded by the product of their sizes.

Lower bounds on size

Roughly speaking, we expect the size of the sum to be about the sum of the sizes of the subsets, provided that they are as far as possible from being subgroups as possible. Some results in this direction are: