# How large can a symmetric generating set of a finite group be?

Let $$G$$ be a finite group of order $$n$$ and let $$\Delta$$ be its generating set. I'll say that $$\Delta$$ generates $$G$$ symmetrically if for every permutation $$\pi$$ of $$\Delta$$ there exists $$f:G\rightarrow G$$ an automorphism of $$G$$ such that $$f\restriction\Delta=\pi$$.

How large can $$\Delta$$ be with respect to $$n$$? Specifically what's the asymptotic behaviour? Is there a class of groups (along with their symmetric generating sets) of unbounded order such that $$n$$ is polynomially bounded by $$|\Delta|$$. Has any other research been done on these generating sets?

• The asymptotic behavior of what? there are plenty of sequences that you can associate to your setting. By "$n$ polynomial wrt $|\Delta|$", you mean polynomially bounded? (sequence $(G_k,\Delta_k)$ with $|G_k|\le P(|\Delta_k|)$?). – YCor Oct 31 '18 at 10:20
• Yes, polynomially bounded. – Pavel Madaj Oct 31 '18 at 10:22
• As regards your title, note that "symmetric" generating subset usually means stable under $g\mapsto g^{-1}$. – YCor Oct 31 '18 at 10:25
• One thing that is easy to see: any subset $\Delta'$ of $\Delta$ of size $|\Delta|-2$ generates a proper subgroup of the group generated by $\Delta$ (because you need there to be an automorphism that fixes $\Delta'$ pointwise and swaps the other two elements). I think this implies YCor's bound, or something like it. On the other hand an elementary abelian group of order $2^n$ has a highly symmetric generating set of size $n$. – Colin Reid Oct 31 '18 at 10:33
• @ColinReid Nice, indeed, assuming $n\ge 1$ and writing $\Delta=\{g_1,\dots,g_n\}$ and $\Delta_i=\{g_1,\dots,g_i\}$, and $G_i$ the subgroup generated by $\Delta_i$, for every $i\le n-2$ we have $g_{i+1}\notin G_i$. Hence $1=G_0<G_1<\dots <G_{n-1}$, and thus $|G|\ge |G_{n-1}|\ge 2^{n-1}$. (Note that this bound is achieved, except for $n=2$, for which the lower bound is 3 instead of $2^{2-1}=2$.) – YCor Oct 31 '18 at 10:38

If $$G$$ has order $$n$$, then $$|\Delta| \leq \log_2 n + 1$$. This bound is sharp in the sense that it is attained for a sequence of groups of unbounded order (namely elementary abelian 2-groups).

Proof:

Let $$G$$ be a finite group and let $$\Delta$$ be a generating set with the property described in the OP (i.e. any permutation of $$\Delta$$ induces an automorphism of $$G$$).

Let $$k$$ be the cardinality of $$\Delta$$ and let $$\Delta = \{g_1,\dots,g_k\}$$. (Note this fixes a total order on $$\Delta$$.)

For any $$j=1,\dots,k$$, let $$\Delta_j := \{g_1,\dots,g_j\}$$ and let $$G_j$$ be the subgroup generated by $$\Delta_j$$. For $$j\leq k-2$$, $$G_j$$ must generate a proper subgroup of $$G_{j+1}$$, because $$G$$ has automorphisms that fix $$G_j$$ pointwise but do not fix $$G_{j+1}$$ pointwise (namely, those induced by any permutation of $$\Delta$$ that fixes $$\Delta_j$$ pointwise but moves $$g_{j+1}$$; note that for $$j\leq k-2$$, these exist).

As a consequence, $$[G_{j+1}:G_j]\geq 2$$ for $$j\leq k-2$$.

Also note $$|G_1|\geq 2$$ since $$g_1$$ cannot be the identity as there exist automorphisms of $$G$$ that do not fix it (as long as $$|\Delta|\geq 2$$).

Thus, by induction, $$|G_j|\geq 2^j$$ for $$j$$ up to $$k-1= (k-2)+1$$. In particular, $$G\supset G_{k-1}$$ must have order at least $$2^{k-1}$$.

This yields the bound given above.

This bound is attained for elementary abelian 2-groups of order $$n=2^{k-1}$$, for $$k\geq 3$$: let $$\Delta$$ consist of a basis (of $$k-1$$ elements) plus the product of the basis elements. (The condition $$k\geq 3$$ guarantees the product is distinct from any of the basis elements.) This choice of generators satisfies the condition $$\prod g_i = 1$$ inside the group, thus the basis elements $$g_1,\dots,g_{k-1}$$ can be sent to any $$k-1$$ of the $$k$$ elements of $$\Delta$$, inducing an automorphism, and the last element of $$\Delta$$ will automatically end up in the right place.