7
$\begingroup$

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.

$\endgroup$
7
  • 2
    $\begingroup$ When you say $A$ and $B$ are subsets, do you actually mean subgroups? $\endgroup$
    – anon271828
    Feb 14, 2013 at 15:12
  • 2
    $\begingroup$ Inclusion $AB\subset G$ is obvious. But your proof is wrong since you proved only that some element of $G$ is in $AB$ $\endgroup$
    – Norbert
    Feb 14, 2013 at 15:12
  • $\begingroup$ That $AB\subseteq G$ is trivial. $\endgroup$ Feb 14, 2013 at 15:13
  • 1
    $\begingroup$ @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. $\endgroup$
    – JSchlather
    Feb 14, 2013 at 16:06
  • 1
    $\begingroup$ @peoplepower, why should this be a counterexample? Surely $\mathbb Z_5 = A + B$ here. $\endgroup$ Feb 14, 2013 at 16:34

1 Answer 1

13
$\begingroup$

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$.

$\endgroup$
4
  • 2
    $\begingroup$ +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. $\endgroup$ Feb 14, 2013 at 16:30
  • 1
    $\begingroup$ "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$?" $\endgroup$ Feb 14, 2013 at 16:35
  • $\begingroup$ 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. $\endgroup$ Apr 10, 2014 at 20:42
  • $\begingroup$ Very clever. +1 $\endgroup$
    – user384138
    Jun 3, 2017 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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