# What is the asymptotic of finite group Cayley length?

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...

• 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$. – verret Sep 15 '20 at 1:41
• 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... – verret Sep 15 '20 at 1:42
• @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. – Yanior Weg Sep 15 '20 at 5:26
• Ah, I missed that, I thought it was just for groups of order $n$... – verret Sep 15 '20 at 5:51
• What is your argument that shows $CL(n)$ is in $O(n)$? – verret Sep 15 '20 at 5:53

## 1 Answer

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$$.