Return to Question

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?

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?

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 $\{(123),(12)(34)\} < S_4$ as a set of permutations that preserve a relation: any relation on $\{1,2,3,4\}$ that is preserved by these two permutations 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?

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?

You can skip to the question below: it is self-contained, but not self-motivating.

Motivation

The following came up in my work recently.

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 $\{(123),(12)(34)\} < S_4$ as a set of permutations that preserve a relation: any relation on $\{1,2,3,4\}$ that is preserved by these two permutations 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?

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 $\{(123),(12)(34)\} < S_4$ as a set of permutations that preserve a relation: any relation on $\{1,2,3,4\}$ that is preserved by these two permutations 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?