Minimal size of subsets $A,B$ in a finite group $G$ such that $AB=G$

Question

Given a finite group $G$ with $N$ elements what are the "smallest" possible subsets $A,B$ of $G$ such that $G=AB$ (ie. every element of $G$ is a product of an element in $A$ and an element in $B$)?

We have of course $\sharp(A)\sharp(B)\geq N$ but can one always find two subsets $A,B$ of size roughly $\sqrt N$ with the property $G=AB$? Since I do not know the optimal answer a good definition of "roughly" should be part of an answer (one can surely not do better than $A,B$ of size $O(1)+\sqrt N$ but I guess this is much to optimistic. It is perhaps more reasonable to hope for $\sqrt N$ times something bounded).

The optimal answer $A,B$ of size (at most) $1+\sqrt N$ works for cyclic groups: take $A=\mathbb N\left\lceil \sqrt N\right\rceil\cap \{0,\dots,N-1 \}$ and $ B= \{ 0,1,\dots,\left\lfloor \sqrt{N} \right \rfloor \} $ in $\mathbb Z/N\mathbb Z= \{0,\dots,N-1\}$.

On the other hand, if $G$ has a (not-necessarily normal) subgroup $H$ of size roughly $\sqrt{N}$ one can consider $A=H$ and take for $B$ coset-representantives.

Combining the two constructions we get a nearly optimal result for abelian groups.

Is there for example a sequence of "bad" groups $G_i$ such that, say $$\left((1+\sharp(A_i))(1+\sharp(B_i))-\sharp(G_i)\right)\Big/\sqrt{\sharp(G_i)}$$ is unbounded for every (sequence of) subsets $A_i,B_i\subset G_i$ such that $G_i=A_iB_i$? (The existence of such a sequence would of course the hope for the existence of $A,B$ of size $O(1)\sqrt{\sharp(G)}$ (with $AB=G$) in every finite group $G$.

Answer 1

For square root of N times something bounded, this can be done with A=B (and the bound being 4 over the square root of 3) according to

Kozma and Lev, Bases and decomposition numbers of finite groups Arch. Math. (Basel) 58 (1992), 417-424

which seems to do as you say, namely find a subgroup of order about the square root of N (via an appeal to CFSG).

It wouldn't surprise me if the O(1)+square root of N case is open.

Answer 2

I don't know how interesting my answer can be after a comment by Ben Green, but this would be too long for a comment, and I hope it can be helpful, somehow.

Your question is tightly related to the behavior of a function first introduced, afaik, by the late M. Kervaire, and studied to some extent by the same author (and his students) and A. Plagne (and his students); see, e.g., the references in É. Balandraud, The isoperimetric method in non-abelian groups with an application to optimally small sumsets, IJNT, Vol. 4, No. 6 (2008), 927-958. To wit, for a group $\mathbb G$ let $\mu_\mathbb{G}$ be the function

$\mathbb N^2 \to \mathbb N \cup \{\infty\}: (s,t) \mapsto \min\{|AB|: A, B \in\mathcal P(\mathbb G), |A| = s, |B| = t\}$.

Now, if $\mathbb G_1, \mathbb G_2, \ldots$ is a sequence of finite groups with $|\mathbb G_n| = n$ for each $n$, your question does essentially refer, if I'm not missing anything, to the asymptotic behavior of the restriction of $\mu_n := \mu_{\mathbb G_n}$ to a subset $S_n \times T_n$ of $\mathbb N^2$ such that $\min(S_n, T_n) = O(1) + \sqrt{n}$ and $\max(S_n, T_n)= O(1) + \sqrt{n}$ for $n \to \infty$, for which you'd like to have $\mu_n(S_n,T_n) = n$ for all sufficiently large $n$, and "uniformly" with respect to the actual choice of the sequences $(S_n)_{n \in \mathbb N}$ and $(T_n)_{n \in \mathbb N}$.

This in turn has a seemingly intimate, but still unclear relation with the classical Cauchy-Davenport theorem and its generalizations, which is something that I myself am trying to investigate with the aid of Alain and Éric.

Edit. As pointed out by quid in the comments below, it is better, with respect to the question raised by the OP, to re-write the above in terms of the "dual" of $\mu_\mathbb{G}$, namely the function

${\rm M}_\mathbb{G}: \mathbb N^2 \to \mathbb N: (s,t) \mapsto \max\{|AB|: A, B \in\mathcal P(\mathbb G), |A| = s, |B| = t\}$.

But now you would rather check out if, for a certain sequence $\mathbb G_1, \mathbb G_2, \ldots$ of groups, it holds $\limsup_n (n - \max_{s \in S_n, t \in T_n} {\rm M}_{\mathbb G}(s,t)) \ne 0$, "uniformly" with respect to $(S_n)_{n \in \mathbb N}$ and $(T_n)_{n \in \mathbb N}$.

Answer 3

In general, one expects to need $N\log N$ "random" products to cover a set of size $N$, by coupon collecting analysis. So my intuition is that you need more than just $\sqrt N$ elements in the sets $A$ and $B$, closer to $\sqrt{N\log N}$.

The odds of covering an $N$-element set with $cN$ selections (fixed c as $N\rightarrow\infty$) is approximately $e^{cN}/N!$ I think, and you only have ${N\choose \sqrt{cN}}^2$ possible choices of $(A,B)$, and this is only of size $N^{2\sqrt{cN}}$, much smaller than the dominant $N!$.

But the above is just randomness theory, not invoking theory of groups.