Decomposing a finite group as a product of subsets

Question

My friend Wim van Dam asked me the following question:

• For every finite group $G$, does there exist a subset $S\subset G$ such that $\left|S\right| = O(\sqrt{\left|G\right|})$ and $S\times S = G$? Also, can we describe such an $S$ explicitly?

I believe it's not hard to show that if we choose $S$ uniformly at random, then $\left|S\right| = O(\sqrt{\left|G\right| \log \left|G\right| })$ suffices. But this still leaves the problems of giving an explicit construction and of removing the $\log \left|G\right|$ term.

Of course, if $G$ happens to have a subgroup $H$ of size $\approx \sqrt{\left|G\right|}$, then we just take the union of $H$ with a collection of coset representatives and are done. So, this suggests the possibility of a win-win analysis, where we identify the relatively rare finite groups that don't have a subgroup of the right size and handle them in a different way. Work on approximate subgroups might also be relevant.

In the likely event that this has already been solved, just a link to the paper would be great (a half hour of googling didn't succeed).

Answer 1

This problem, first raised in 1937 by H. Rohrbach, has been considered, for instance, in the paper "On $h$-bases and $h$-decompositions of the finite solvable and alternating groups" (J. Number theory 49 (3), 1994) by Gadi Kozma and Arieh Lev. The paper contains historical remarks and further references.

The abstract of the paper reads as follows:

Let $G$ be a finite group such that every composition factor of $G$ is either cyclic or isomorphic to the alternating group on $n$ letters for some integer $n$. Then for every positive integer $h$ there is a subset $A\subseteq G$ such that $|A|\le(2h-1)|G|^{1/h}$ and $A^h=G$. The following generalization for the group $G$ also holds: For every positive integer $h$ and any nonnegative real numbers $\alpha_1,\alpha_2,\dotsc,\alpha_h$ so that $\alpha_1+\alpha_2+\dotsb+\alpha_h=1$ there are subsets $A_1,A_2,\dotsc,A_h\subseteq G$ such that $|A_1|\le|G|^{\alpha_1}$, $|A_i| \le 2|G|^{\alpha_i}$ for $2\le i\le h$ and $A_1A_2\dotsb A_h=G$. In particular, the above conclusions hold if $G$ is a finite group and either $G$ is an alternating group or $G$ is solvable.

Answer 2

It was brought to my attention by Noga Alon that my previous answer (which I keep to avoid any confusion) was in fact incorrect: the Rohrbach conjecture got solved completely by Finkelstein, Kleitman, and Leighton in 1988 ("Applying the classification theorem for finite simple groups to minimize pin count in uniform permutation architectures"), and independently by Kozma and Lev in 1992 ("Bases and decomposition numbers of finite groups").

Explicitly, there exists a subset $S\subseteq G$ of size $|S|\le(4/\sqrt 3)|G|^{1/2}$ such that every element of $G$ is representable as a product of two elements from $S$.

Answer 3

An update: following a lead from Seva's answer, I discovered in that their 2003 paper Communication Complexity of Simultaneous Messages, Babai, Gal, Kimmel, and Lokam (see Section 7, "Decompositions of Groups") state explicitly that what I want is an open problem. Or strictly speaking, a slight generalization to the $k$-fold rather than $2$-fold Cartesian product---but if more had been known for the $2$-fold case they would've said so. They call what I'm asking for the "Rohrbach Conjecture."

Besides discussing Kozma and Lev's progress on the Rohrbach Conjecture (mentioned in Seva's answer), Babai et al. also prove the following weaker result (their Theorem 2.17, special case relevant for this MO post):

For every finite group $G$, there exists a subset $S\subset G$ with $\left|S\right| = O(\sqrt{\left|G\right|})$ such that $\left|S\times S\right| \ge (1-1/\sqrt{e})\left|G\right|$.

In an embarrassing postscript, Anna Gal, one of the authors of this paper, occupies the office next to mine!