Putnam 2008, Problem A-6

Prove that there exists a constant $c > 0$ such that in every nontrivial finite group $G$ there exists a sequence of length at most $c \log |G|$ with the property that each element of $G$ equals the product of some subsequence.

Solution:
For notational convenience, we will interpret the problem as allowing the empty subsequence, whose product is the identity element of the group. To solve the problem in the interpretation where the empty subsequence is not allowed, simply append the identity element to the sequence given by one of the following solutions.

**First solution:** Put $n = |G|$. We will say that a sequence $S$ produces an element $g \in G$ if $g$ occurs as the product of some subsequence of $S$. Let $H$ be the set of elements produced by the sequence $S$.

Start with $S$ equal to the empty sequence. If at any point the set $H^{-1}H = \{h_1^{-1}h_2 : h_1^{-1}, h_2 \in H\}$ fails to be all of $G$, extend $S$ by appending an element $g$ of $G$ not in $H^{-1}H$. Then $Hg \cap H$ must be empty, otherwise there would be an equation of the form $h_1g = h_2$ with $h_1,h_2 \in G$, or $g = h_1^{-1}h_2$, a contradiction. Thus we can extend $S$ by one element and double the size of $H$.

After $k \leq \log_2 n$ steps, we must obtain a sequence $S = a_1, \ldots, a_k$ for which $H^{-1}H = G$. Then the sequence $a_k^{-1}, \ldots, a_1^{-1}, a_1, \ldots, a_k$ produces all of $G$ and has length at most $(2/\ln 2) \ln n$.

**Second solution:**
Put $m = |H|$. We will show that we can append one element $g$ to $S$ so that the resulting sequence of $k+1$ elements will produce at least $2m - m^2/n$ elements of $G$. To see this, we compute
$$\sum_{g \in G} |H \cup Hg| = \sum_{g \in G} (|H| + |Hg| - |H \cap Hg|)$$
$$= 2mn - \sum_{g \in G} |H \cap Hg|$$
$$= 2mn - |\{(g,h) \in G^2 : h \in H \cap Hg\}|$$
$$= 2mn - \sum_{h \in H} |\{g \in G : h \in Hg\}|$$
$$= 2mn - \sum_{h \in H} |H^{-1}h|$$
$$= 2mn - m^2.$$

By the pigeonhole principle, we have $|H \cup Hg| \geq 2m - m^2/n$ for some choice of $g$, as claimed.

In other words, by extending the sequence by one element, we can replace the ratio $s = 1 - m/n$ (i.e., the fraction of elements of $G$ not generated by $S$) by a quantity no greater than
$$1 - (2m - m^2/n)/n = s^2.$$

We start out with $k = 0$ and $s = 1 - 1/n$; after $k$ steps, we have $s \leq (1 - 1/n)^{2^k}$. It is enough to prove that for some $c > 0$, we can always find an integer $k \leq c \ln n$ such that
$$\left(1 - \frac{1}{n}\right)^{2^k} < \frac{1}{n},$$
as then we have $n - m < 1$ and hence $H = G$.

To obtain this last inequality, put
$$k = \lfloor 2 \log_2 n \rfloor < (2/\ln 2) \ln n,$$
so that $2^{k+1} \geq n^2$. From the facts that $\ln n \leq \ln 2 + (n-2)/2 \leq n/2$ and $\ln(1 - 1/n) < -1/n$ for all $n \geq 2$, we have
$$2^k \ln\left(1 - \frac{1}{n}\right) < -\frac{n^2}{2n} = -\frac{n}{2} < -\ln n,$$
yielding the desired inequality.

**Remark:** An alternate approach in the second solution is to distinguish between the cases of $H$ small (i.e., $m < n^{1/2}$, in which case $m$ can be replaced by a value no less than $2m-1$) and $H$ large. This strategy is used in a number of recent results of Bourgain, Tao, Helfgott, and others on small doubling or small tripling of subsets of finite groups.

In the second solution, if we avoid the rather weak inequality $\ln n \leq n/2$, we instead get sequences of length $\log_2(n \ln n) = \log_2(n) + \log_2(\ln n)$. This is close to optimal: one cannot use fewer than $\log_2 n$ terms because the number of subsequences must be at least $n$.