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

From Groupprops
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

Applications

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.

Similar facts

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.