# Product of subsets whose total size exceeds size of group equals whole group

Jump to: navigation, search

## Statement

Suppose $G$ is a finite group and $A,B$ are (possibly equal, possibly distinct) subsets of $G$ such that $|A| + |B| > |G|$. Then, every $g \in G$ can be written as $ab$, where $a \in A$, $b \in B$. In other words, the product of subsets $AB$ equals $G$.

Note that this statement as given here applies only to the product of two subsets.

## Related facts

### Strictness

If $|A| + |B| = |G|$, it is not necessary that $AB = G$. An example is when $A,B$ are both equal to each other and a subgroup of index two in $G$.

## Proof

Given: A finite group $G$, (possibly equal, possibly distinct) subsets $A,B$ of $G$ such that $|A| + |B| > |G|$. An element $g \in G$.

To prove: There exists $a \in A, b \in B$ such that $g = ab$.

Proof:

Step no. Assertion/construction Given data used Previous steps used Explanation
1 The set $gB^{-1} = \{ gb^{-1} \mid b \in B \}$ is a subset of $G$ of the same size as $B$. $g \in G, B \subseteq G$ inversion is one-one, and left multiplication by $g$ is one-one, so the composite is one-one.
2 $A \cap gB^{-1}$ is non-empty. Let $a = gb^{-1}$ be an element of the intersection. $|A| + |B| > |G|$ Step (1) By Step (1) and the given information, $|A| + |gB^{-1}| > |G|$. By the principle of inclusion-exclusion, the subsets must intersect.
3 $g = ab$ for the $a,b$ obtained in Step (2). Step (2) Direct from Step (2), by multiplying both sides on the right by $b$.