An optimization problem in finite groups Let $G$ be a finite group, say, of order $n$. I ran into the following problem (where $|A|$ denotes the cardinality of a set $A$):
To determine the minimum of $|A|+|B|$ for sets $A, B \subset G$ such that $A^{-1} \cdot B = G$.
Specifically, is this minimum the same as the minimum of sums $u+v$ for positive integers $u, v$ with $u \cdot v \ge n$?
In the latter (purely numerical) problem, one finds that the largest of $u, v$ (say, $u$) is $\lceil \sqrt{n} \rceil$, the other one being $v = \lceil \frac{n}{u} \rceil$.   (or vice versa). Seen as functions of $n$, solutions $u, v$ can be rather "irregular" and probably obstruct attempts for a proof by induction on $n$.
The two minima are seen to be equal if $G = \mathbb Z / n \mathbb Z$. I verified with Maple that the same goes for Dihedral groups of order $\le 16$. With many examples available now for the sets $A, B$, I still do not see a pattern that is provably decisive. The equation $A^{-1} \cdot B = G$ has this "geometric" interpretation: no translation $A \cdot g$ of $A$ can be disjoint with $B$.
My question derives from a geometric problem (largely solved in the mean time) to find conditions on the size of (two or more) subsets of the regular $n$-gon (essentially, $\mathbb Z / n \mathbb Z$) ensuring that the sets can be "rotated apart". An affirmative answer to my question implies that some critical boundary (called "spaghetti boundary") simply carries over from $\mathbb Z / n \mathbb Z$ to any finite group of order $n$.
The two minima may fail to be the same for all groups of order $n$. In that case, groups $G$ with a larger minimum may be of interest for use as a replacement of $\mathbb Z / n \mathbb Z$ in shuffled equi-$n$-squares: the key result, mentioned in my question "A toroidal version of Rubik's cube: how many shuffles?", has somewhat better chances to apply in the replacement square.
 A: If $A,B\subseteq G$ satisfy $A^{-1}\cdot B=G$ and $|A|+|B|<K\sqrt{|G|}$ for some absolute constant $K$, then for the set $S:=A^{-1}\cup B$ we have $S\cdot S=G$ and $|S|<2K\sqrt{|G|}$. Thus, if you could show the existence of such $A$ and $B$ for any finite group $G$, this would establish the Rohrbach Conjecture. Conversely, if the conjecture is true, then you can find $S\subseteq G$ with $|S|<K\sqrt{|G|}$ and $S\cdot S=G$ and define $A:=S^{-1}$ and $B:=S$ to get $A^{-1}\cdot B=G$ and $|A|+|B|<2K\sqrt{|G|}$. 
The bottom line is, your question is equivalent to an open, 80-year-old conjecture.
A: I am not sure how many groups have this property ( the group $A_{5}$ does, for example), and it gives rather a weak bound, but I mention a situation where neither $A$ nor $B$ need be a subgroup (in case others find it suggestive).
Let $G$ be a finite group of even order in which every element is strongly real ( that is, either an involution, or a product of two involutions). Let $A = B = I(G) = \{ x \in G :x^{2} = 1 \}.$ Then $A^{-1}B = G$  and $|A| + |B| = 2|I(G)|.$
The cardinality of $I(G)$ can be calculated fairly easily by character theory. We let ${\rm Irr}(G)$ denote the set of complex irreducible characters of $G$, and for $\chi \in {\rm Irr}(G),$ let $\nu(\chi)$ denote the Frobenius-Schur indicator of $\chi$. Then $\nu(\chi) \in \{0,1,-1 \}$ and $\nu(\chi) = \frac{1}{|G|} \sum_{g \in G} \chi(g^{2}).$ In fact, the fact that every element of $G$ is strongly real implies that $\nu(\chi) \neq 0$ for each $\chi \in {\rm Irr}(G).$ 
The cardinality $|I(G)|$ is equal to $\sum_{ \chi \in {\rm Irr}(G) } \nu(\chi) \chi(1).$ The Cauchy-Schwartz inequality impies that $|I(G)| \leq \sqrt{k(G)|G|},$ where $k(G)$ is the number of irreducible characters of $G$.
Later edit: all simple groups ${\rm SL}(2,2^{n})$ with $n >1$ have this property, and for such $G$ we have $|I(G)| = 2^{2n},$ giving $2|I(G)|$ very close to $2|G|^{\frac{2}{3}}.$ 
