Let’s for any bijection $f: A \to A$ define its support as $$supp(f) = \{a \in A| f(a) \neq a\}$$

Now, let’s define $S_\infty$ as the group of all bijections $\mathbb{N} \to \mathbb{N}$ with finite support. By Cayley Theorem any finite group is isomorphic to a subgroup of $S_\infty$. Therefore, for any finite group $G$ we can define its Cayley length as

$$len_c (G) = \min \{\sum_{\alpha \in A} |supp(\alpha)| | A \subset S_\infty \langle A \rangle \cong G \}$$

Now, we can define a following function:

$$CL(n) = \max \{len_c(G) | |G| \leq n \}$$

What is the asymptotic of $CL$?

I managed to derive the following two bounds:

$$CL(n) = O(n \log(n))$$

This is because any finite group $G$ has a generating set of size $O(\log(n))$ and the size of supports of permutations, corresponding to each of those generators under left multiplicative action is $n$.

$$CL(n) = \Omega(n)$$

Suppose $p$ is prime. Then $len_c(C_p) = p$. Indeed, all non-trivial elements of $C_p$ have order $p$, any permutation of order $p$ has size of support dividing $p$.

However, I do not know, whether any of those bounds is tight...

  • 1
    $\begingroup$ Why do you say $CL(n)\geq n$? For example isn't $CL(6)=5$? More generally, if $n=pq$, with $p\leq q$ primes, then I think $CL(n)=n-1$ if $p$ divides $q-1$, and $CL(n)=p+q$ otherwise. In particular, in the latter case, $CL(n)$ will be much smaller than $n$. You can generalise this to product of more than two distinct primes. If none of them is congruent to $1$ mod any of the other, then $CL(n)$ will be the sum of the primes, so much smaller than $n$. $\endgroup$ – verret Sep 15 '20 at 1:41
  • 1
    $\begingroup$ Conversely, if $n$ is a prime power, then $CL(n)\geq n$, as witness by the cyclic group of order $n$. I think generally, $CL(n)$ will be larger than this. For example, I think $CL(8)>8$, as witness by the quaternion group. So sometimes $CL(n)$ is much smaller than $n$, sometimes it is larger than $n$, depending very much on the factorisation of $n$. Given that the function is not very smooth, it's not clear what you mean by the asymptotics... $\endgroup$ – verret Sep 15 '20 at 1:42
  • 1
    $\begingroup$ @verret, $CL$ is taken as a maximum over all $|G| \leq n$. Therefore monotonously grows. I would like to know how fast does it grow. $\endgroup$ – Yanior Weg Sep 15 '20 at 5:26
  • $\begingroup$ Ah, I missed that, I thought it was just for groups of order $n$... $\endgroup$ – verret Sep 15 '20 at 5:51
  • $\begingroup$ What is your argument that shows $CL(n)$ is in $O(n)$? $\endgroup$ – verret Sep 15 '20 at 5:53

Actually, $CL(n) = \Theta(n)$. Proof of $CL(n) = \Omega(n)$ can be found in the body of the question. To prove the bound $CL(n) = O(n)$ we will construct a "good" Cayley representation (a Cayley representation of $G$ is here a collection of permutations that generate a group isomorphic to $G$) for arbitrary group $G$ using the follwing recursive procedure:

Base: if $G \cong E$ then we do not need any permutations at all.

Step: Suppose, we have already done this for all groups of order less than $|G|$ and that for them all our Cayley representations satisfy the additional requirement of all generating permutations of any group $K$ being from $Sym(K)$. Now, suppose $H$ is some maximal normal subgroup of $G$ which is represented py permutations $p_1, ... , p_t$ from $Sym(H)$. Then $\frac{G}{H}$ is a simple group. Thus, as all simple groups are $2$-generated, we can take elements $g_1, g_2$ such that $\langle H \cup \{g_1, g_2\} \rangle = G$. Then $G$ can be represented by permutations $p_1, ... , p_t, (h \mapsto g_1 h), (h \mapsto g_2 h)$ from $Sym(G)$.

Now, let's demonstrate that the length (i.e. the sum of sizes of supports of all generating permutations) of Cayley representation constructed that way does not exceed $4|G|$:

Base: If $G \cong E$, then $0 \leq 4$

Step: If the inequality holds for every group of order less then $G$, then the length of the corresponding presentation for $H$ is $\leq 4|H| \leq 2|G|$. On the other hand the lengths of permutations $ (h \mapsto g_1 h)$ and $(h \mapsto g_2 h)$ are $|G|$ each. Thus the total length of this Cayley representation for $G$ $\leq 4|G|$.

Thus we can conclude, that $CL(n) \leq 4n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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