If Two Subsets $A, B$ of a Finite Group $G$ are Large Enough, then $G=AB$
Problem 493
Let $G$ be a finite group and let $A, B$ be subsets of $G$ satisfying
\[|A|+|B| > |G|.\]
Here $|X|$ denotes the cardinality (the number of elements) of the set $X$.
Then prove that $G=AB$, where
\[AB=\{ab \mid a\in A, b\in B\}.\]
Sponsored Links
Contents
Proof.
Since $A, B$ are subsets of the group $G$, we have $AB\subset G$.
Thus, it remains to show that $G\subset AB$, that is any element $g\in G$ is of the form $ab$ for some $a\in A$ and $b\in B$.
This is equivalent to finding $a\in A$ and $b\in B$ such that $gb^{-1}=a$.
Consider the subset
\[B^{-1}:=\{b^{-1} \mid b \in B\}.\]
Since taking the inverse gives the bijective map $B \to B^{-1}$, $b \mapsto b^{-1}$, we have $|B|=|B^{-1}|$.
Also consider the subset
\[gB^{-1}=\{gb^{-1} \mid b\in B\}.\]
Note that multiplying by $g$ and by its inverse $g^{-1}$ give the bijective maps
\[B^{-1} \to gB^{-1}, b^{-1} \mapsto gb^{-1} \text{ and } gB^{-1} \to B^{-1}, gb^{-1} \mapsto b^{-1}.\]
Hence we have
\[ |B|=|B^{-1}|=|gB^{-1}|.\]
Since $A$ and $gB^{-1}$ are both subsets in $G$ and we have by assumption that
\[|A|+|gB^{-1}|=|A|+|B| > |G|,\]
the intersection $A\cap gB^{-1}$ cannot be empty.
Therefore, there exists $a \in A\cap gB^{-1}$, and thus $a\in A$ and $a=gb^{-1}$ for some $b\in B$.
As a result we obtain $g=ab$.
It yields that $G\subset AB$, and we have $G=AB$ as a consequence.
Related Question.
As an application, or use the similar technique, try the following
Every element in a finite field $F$ is the sum of two squares in $F$.
See the post↴
Each Element in a Finite Field is the Sum of Two Squares
for a proof of this problem.
Add to solve later
Sponsored Links
More from my site
Finite Group and a Unique Solution of an Equation
Let $G$ be a finite group of order $n$ and let $m$ be an integer that is relatively prime to $n=|G|$. Show that for any $a\in G$, there exists a unique element $b\in G$ such that
\[b^m=a.\]
We give two proofs.
Proof 1.
Since $m$ and $n$ are relatively prime […]- Group Homomorphism, Preimage, and Product of Groups
Let $G, G'$ be groups and let $f:G \to G'$ be a group homomorphism.
Put $N=\ker(f)$. Then show that we have
\[f^{-1}(f(H))=HN.\]
Proof.
$(\subset)$ Take an arbitrary element $g\in f^{-1}(f(H))$. Then we have $f(g)\in f(H)$.
It follows that there exists $h\in H$ […]
- The Product of a Subgroup and a Normal Subgroup is a Subgroup
Let $G$ be a group. Let $H$ be a subgroup of $G$ and let $N$ be a normal subgroup of $G$.
The product of $H$ and $N$ is defined to be the subset
\[H\cdot N=\{hn\in G\mid h \in H, n\in N\}.\]
Prove that the product $H\cdot N$ is a subgroup of […]
The Product of Distinct Sylow $p$-Subgroups Can Never be a Subgroup
Let $G$ a finite group and let $H$ and $K$ be two distinct Sylow $p$-group, where $p$ is a prime number dividing the order $|G|$ of $G$.
Prove that the product $HK$ can never be a subgroup of the group $G$.
Hint.
Use the following fact.
If $H$ and $K$ […]- Determine the Number of Elements of Order 3 in a Non-Cyclic Group of Order 57
Let $G$ be a group of order $57$. Assume that $G$ is not a cyclic group.
Then determine the number of elements in $G$ of order $3$.
Proof.
Observe the prime factorization $57=3\cdot 19$.
Let $n_{19}$ be the number of Sylow $19$-subgroups of $G$.
By […]
- If the Order of a Group is Even, then the Number of Elements of Order 2 is Odd
Prove that if $G$ is a finite group of even order, then the number of elements of $G$ of order $2$ is odd.
Proof.
First observe that for $g\in G$,
\[g^2=e \iff g=g^{-1},\]
where $e$ is the identity element of $G$.
Thus, the identity element $e$ and the […]
- Nontrivial Action of a Simple Group on a Finite Set
Let $G$ be a simple group and let $X$ be a finite set.
Suppose $G$ acts nontrivially on $X$. That is, there exist $g\in G$ and $x \in X$ such that $g\cdot x \neq x$.
Then show that $G$ is a finite group and the order of $G$ divides $|X|!$.
Proof.
Since $G$ acts on $X$, it […]
Normal Subgroup Whose Order is Relatively Prime to Its Index
Let $G$ be a finite group and let $N$ be a normal subgroup of $G$.
Suppose that the order $n$ of $N$ is relatively prime to the index $|G:N|=m$.
(a) Prove that $N=\{a\in G \mid a^n=e\}$.
(b) Prove that $N=\{b^m \mid b\in G\}$.
Proof.
Note that as $n$ and […]
