Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $A,B$ be two subsets of a finite group $G$. If $|A|+|B|>|G|$, show that $G=AB$. My attempt is : Since $|A|+|B|>|G|$, there exists one common element in both sets $A$ and $B$, say $g$. Then since $G$ is a group, by closure, $g^2 \in G$, which implies that $G \subset AB$. Let $a \in A$, $b \in B$. Then I get stuck at proving another inclusion.

share|improve this question
2  
When you say $A$ and $B$ are subsets, do you actually mean subgroups? –  anon271828 Feb 14 '13 at 15:12
2  
Inclusion $AB\subset G$ is obvious. But your proof is wrong since you proved only that some element of $G$ is in $AB$ –  no identity Feb 14 '13 at 15:12
    
That $AB\subseteq G$ is trivial. –  Tobias Kildetoft Feb 14 '13 at 15:13
1  
@anon271828 If $A$ and $B$ were subgroups there'd be nothing to do. Since $|A|+|B|>|G|$ implies either $|A|>|G|/2$ or $|B|>|G|/2$ which would force either $A=G$ or $B=G$. Although it's possible the question is that straightforward. –  JSchlather Feb 14 '13 at 16:06
1  
@peoplepower, why should this be a counterexample? Surely $\mathbb Z_5 = A + B$ here. –  Andreas Caranti Feb 14 '13 at 16:34

1 Answer 1

up vote 9 down vote accepted

Take any $g \in G$. Let $A^{-1} = \lbrace a^{-1}, a \in A \rbrace$. Then $\vert A^{-1}g \cap B \vert \gt 0$ by easy counting. Let $b = a^{-1} g$ for some $a \in A$. Then $ab = a a^{-1} g = g$.

share|improve this answer
2  
+1 It's the argument that can be used to show that in a finite field $F$ of odd order $q$ every element is the sum of two squares. In this case $A = B = \{ u^2 : u \in F \}$ has $(q+1)/2 > q/2$ elements. –  Andreas Caranti Feb 14 '13 at 16:30
1  
"Let $b=a^{-1} g, \exists a \in A$" Ok it's clear what you mean, but this really contradicts all rules of mathematical well-defined formulas. Why not "Choose $a \in A$ with $b=a^{-1} g$?" –  Martin Brandenburg Feb 14 '13 at 16:35
    
Good proof. Two more corrections: You can say $A^{-1}g\cap B\ne\varnothing$, $\left\vert A^{-1}g \cap B \right\vert \ne 0$, or even $\left\vert A^{-1}g \cap B \right\vert \gt 0$ but not $\left\vert A^{-1}g \cap B \right\vert \ne \varnothing$. And using \phi$(\phi)$ instead of \emptyset$(\emptyset)$ or \varnothing$(\varnothing)$ for the empty set is just bad juju. –  Travis Bemrose Apr 10 at 20:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.