Motivation
The following came up in my work recently. (NB this is the motivation, not the question I'm asking. You can skip to the actual question below, which is self-contained, but not self-motivating.)
Take a symmetric group $S_n$ and some subgroup $H < S_n$. Can we find a binary relation $\sim_H$ on $\{1,\dots,n\}$ so that a permutation $f \in S_n$ satisfies $f \in H$ precisely if it preserves $\sim_H$, i.e. if $x \sim_H y$ implies $f(x) \sim_H f(y)$ for all $x,y \in \{1,\dots,n\}$?
Now, the analogous question for transformation monoids has a straightforward negative answer: the number of transformation monoids on the four-element set is known, and vastly exceeds the number of possible binary relations on the four-element set.
One can show by a direct proof that the question above also has a negative answer. While there are no counterexamples among the subgroups of $S_2$ and $S_3$, one already cannot characterize $\langle(123),(12)(34)\rangle < S_4$ as a set of permutations that preserve a relation: any relation on $\{1,2,3,4\}$ that is preserved by the two permutations generating this subgroup is in fact preserved by all elements of $S_4$.
However, this raises another question: would a naive counting argument, similar to the one used for transformation monoids, succeed given more information about the number of subgroups of $S_n$?
Question
It follows from Corollary 3.3 of László Pyber's Enumerating finite groups of given order that the number of relations on an $n$-element set definitively and permanently overtakes the number of subgroups of $S_n$ at $n = 94$.
Is there any $n < 94$ for which the symmetric group $S_n$ has more than $2^{n\times n}$ subgroups? I strongly suspect that the answer is no. Can this be proven using known results or bounds?
