MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Interesting question! I only made the braces appear, by adding extra backslashes. – user9072 Apr 9 '13 at 9:05
For finite simple groups of Lie type I believe you can always cook up a subgroup of order $N^{1/2 + f(r)}$ where $r$ the rank and $f(r)$ is some function of $r$ that tends to zero as $r$ increases. Then, taking coset representatives, as you suggest, you've got yourself a not-far-from-optimal $A$ and $B$, at least for large rank. I think something similar will work for $Alt(n)$ where $r$ is now the number of primes dividing $n$ (or something). So if I were looking for non-abelian simple counter-examples I'd look at low-rank groups of Lie type, or $Alt(n)$ for $n$ prime-ish. – Nick Gill Apr 9 '13 at 10:29
[Comment continued]: I thought about simple groups first because it seems reasonably clear that you can reduce this question to one about simple groups by considering a composition series (?) I say "reasonably clear" but I haven't written down a proof... – Nick Gill Apr 9 '13 at 10:31
I think you will get close to the optimum in most nilpotent groups by taking $A$ to be a subgroup, since if $G$ is nilpotent, every divisor of $|G|$ is the order of some subgroup of $G$. That said, this doesn't work if $|G|=p^n$ where $n$ is a fixed odd number and $p$ varies, so you would need to combine it somehow with the strategy for cyclic groups. – Colin Reid Apr 9 '13 at 10:35
So, the strategy when A = H is a subgroup generalizes to A being your favorite set with $|A A^{-1}| = O(|A|)$, by a similar packing argument (if you accept a constant factor at the end). The aim is then to find such a set with $|A| \approx \sqrt{N}$. This gives rise to the cyclic example above, and should do what Colin Reid wants for nilpotent groups (see above). I don't know Whether you could use something like this to avoid the use of CFSG in the general case. – Freddie Manners Apr 9 '13 at 17:07

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.

share|cite|improve this answer
That's a very nice result! – Roland Bacher Apr 10 '13 at 8:18

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

share|cite|improve this answer
It seems to me what you say is rather somehow 'dual' or 'at the opposite end' to what is asked. Consider the case of a cyclic group of square order $m^2$. As explained in the question in thsi case one can choose $A$, $B$ of size $m$. Yet it is not at all true that every choice of sets of this size will do (take the subgroup or two cosets of it of order m). Put differently, the question asks for conditions when max |AB| over certain sets A,B is the order of the group, not min. – user9072 Apr 9 '13 at 15:03
On second reading: sorry, I did not pay enough attention to the "uniformly" you mentioned. So, my first comment is not completely to the point. However, I still think that the two problems are at opposite ends of the spectrum. But then there can be no harm in having this related type of problem mentioned. – user9072 Apr 9 '13 at 15:19
@quid. You're right. Replacing min with max is certainly closer to the spirit of the OP. I guess this is what you meant by the term "dual". – Salvo Tringali Apr 9 '13 at 17:23

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.

share|cite|improve this answer
Is this exactly "coupon collecting analysis"? For each choice of B = {b_1,..,b_k} you can try and estimate the probability that AB is all of G, if A is chosen randomly. But then you have to sum over a large selection of B's, and the triangle inequality may be too crude. In fact, I posed as an open problem (Barbados workshop, March 2012) the question of deciding whether the log N should really be there. Can Z/NZ be covered by O(N^{1/2}) translates of a random set A of size N^{1/2}? – Ben Green Apr 9 '13 at 11:15

Your Answer


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.