Can a group have more subgroups than it has elements?

I'm looking for a group for which the number of subgroups is more than the number of elements in the group! I tried a few possibilities - it can't be cyclic, and I think we'll have to consider group of infinite order.

-
The smallest example has order $4$. – Mikko Korhonen May 25 '14 at 15:16
@Yves: my apologies; I misspoke. – Qiaochu Yuan May 25 '14 at 20:01
To bounce on Qiaochu's erased comment, it's not hard to see that if $x=4^n$ (to simplify), and $G$ is a vector space over $F_2$ of dimension $2n$, then $G$ has at most $n2^{4n^2}=n2^{4\log_2(x)^2}$ subgroups, and has at least $2^{n^2}$ subgroups (namely graphs of linear maps between two spaces of dimension $n$); I'm lazy to check the precise behavior but it's essentially in $\exp(\log(x)^2)$. It would sound plausible that it's essentially the largest possible number of subgroups...? – YCor May 25 '14 at 20:18
concerning infinite groups, plenty of countable groups (e.g. a free group on 2 generators, or $\mathbf{Q}$) have $2^{\aleph_0}$ many groups. Also I guess that "most" uncountable groups $G$ have $2^{|G|}$ subgroups). – YCor May 25 '14 at 20:39

Consider the product of $n \gt 2$ copies of $\mathbb{Z}_2$, a group of order $2^n$. Each nonzero element in this (additive) group has order two, so in addition to the trivial subgroup, there are $2^n - 1$ subgroups of order two.

Of course there are also proper subgroups of order greater than two, so more subgroups than elements.

-
$n = 2$ works also. – Mikko Korhonen May 25 '14 at 15:14
@MikkoKorhonen: Sort of. For $n=2$ we have the trivial subgroup and three subgroups of order two, for a total of exactly four proper subgroups. If you are allowed to count the group itself, that would give five "subgroups", but in the more restricted sense of proper subgroups we need $n \gt 2$. – hardmath May 25 '14 at 15:23

$C_2 \times C_2 \times C_2$ has 8 elements. Each of the 7 non-identity elements generates a subgroup of order 2. Any pair of non identity elements also generates a subgroup isomorphic to $C_2 \times C_2$. There are 7 of these subgroups, for a total of 14 nontrivial proper subgroups.

-

Number of subgroups of $D_{2n}=\sigma(n)+\tau(n)$, where $\sigma$ and $\tau$ are sum of divisors and number of divisors of $n$, so determine all $n$ for which $\sigma(n)+\tau(n)>2n$ and you will have alot many examples (just do not try primes bigger than $3$)

For $n=4$, $\sigma(n)+\tau(n)=10>4$, so $D_4$ is an example.

For $n=5$, $\sigma(n)+\tau(n)$, not true.

For $n=6$, $\sigma(n)+\tau(n)=16>12$. so $D_6$ is an example..

and so on....

-