3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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|)$?). $\endgroup$ – YCor Oct 31 '18 at 10:20
  • $\begingroup$ Yes, polynomially bounded. $\endgroup$ – Pavel Madaj Oct 31 '18 at 10:22
  • 4
    $\begingroup$ As regards your title, note that "symmetric" generating subset usually means stable under $g\mapsto g^{-1}$. $\endgroup$ – YCor Oct 31 '18 at 10:25
  • 5
    $\begingroup$ 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$. $\endgroup$ – Colin Reid Oct 31 '18 at 10:33
  • 5
    $\begingroup$ @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$.) $\endgroup$ – YCor Oct 31 '18 at 10:38
2
$\begingroup$

Cherry-picking the answer from YCor's and Colin Reid's comments:

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.