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?

Improve this question
$\endgroup$
8
  • 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
    Commented Oct 31, 2018 at 10:20
  • $\begingroup$ Yes, polynomially bounded. $\endgroup$
    – Pavel Madaj
    Commented Oct 31, 2018 at 10:22
  • 4
    $\begingroup$ As regards your title, note that "symmetric" generating subset usually means stable under $g\mapsto g^{-1}$. $\endgroup$
    – YCor
    Commented Oct 31, 2018 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
    Commented Oct 31, 2018 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
    Commented Oct 31, 2018 at 10:38

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .