Consider subgroup of S_n generated by two cyclic permutations of the form described below. (Roughly speaking cycles having only two common elements).
Question: what is known about its growth and diameter ?
Growth seems to be about 2.7 – see computational experiments here: https://www.kaggle.com/competitions/santa-2023/discussion/464953
Remark: Grwoth and diameter are quite related – since probably one can estimate number of elements combinatorily and afterwards diameter can be estimated as about: log_growth(group-size).
The group is described like that. Let us give the examples first. It is generated by by two cyclic permutations denoted "l" and "r".
n = 10
l (0 1 2 3 4 5)
r (0 6 7 2 8 9)
n = 12
l (0 1 2 3 4 5 6)
r (0 7 8 9 2 10 11)
n = 22
l (0 1 2 3 4 5 6 7 8 9 10 11)
r (0 12 13 14 15 16 17 18 3 19 20 21)
n = 40
l (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)
r (0 21 22 23 24 25 26 27 28 29 30 31 32 33 6 34 35 36 37 38 39)
I.e. first is cycling moving 0…k, second is k+1…n with two intersecting positions.
That group can be thought as symmetry group of the puzzle consisting of two circles:
https://www.kaggle.com/code/marksix/visualize-allowed-moves
Or the similar subgroup appears when we make rotation of the Rubik's cube around two facets:
https://www.reddit.com/media?url=https%3A%2F%2Fpreview.redd.it%2Fimq4s00bgx1a1.gif%3Fformat%3Dmp4%26s%3Dabea9b805f838832ba835c36eeefd2e73fd2eae1
Best Answer
Here are some explorations of the groups generated by these intersecting cycles. It is a work in progress and not a complete answer.
Let $L$ and $R$ be the following cycle permutations:
$$L = (l_0, l_1, ..., l_m, ..., l_{M-1}) \\ R = (r_0, r_1, ..., r_n, ..., r_{N-1})$$ They share exactly two elements $l_0=r_0$ and $l_m=r_n$. So $L$ is a cycle of length $M$, in which the shared elements are a distance of $m$ apart, and $R$ is of length $N$ where the shared elements are $n$ apart. We may assume wlog that $m<=M/2$ and $n<=N/2$.
The question is about the diameter of the group as generated by these two cycles and their inverses.
If you think of this as a permutation puzzle, then there are $4$ possible moves (two faces that can be turned in either direction) and you want to know how many moves it takes to solve in the worst case. From the solved state you can do any of the $4$ moves to reach a different state. After that, one of the four moves would undo the previous one while the other three possible moves could create a new state. So after $k$ moves, at most $p_k=1+4+4\cdot3^1+4\cdot3^2+...+4\cdot3^{k-1}$ distinct states can be reached. If you know the size of the group then you can get a lower bound for the diameter by looking at when $p_k$ first exceeds the group size.
Let's try to find the size of the generated group. It should be noted that this has been analysed before by David Singmaster, but it is always good to replicate results. My results below match his, except that I found another special edge case (with $M=2$) that it seems he did not consider.
Let $S$ be the commutator $S=L^m R^n L^{-m} R^{-n}$.
If $m<M/2$ and $n<N/2$ (strict inequalities), then $S$ is merely a double swap $(l_0,l_m)(l_{2m},r_{2n})$.
We can conjugate $S$ by $L$ to get $S'= L S L^{-1}$ which will generally be the double swap $(l_1,l_{m+1})(l_{2m+1},r_{2n})$. For this to work we need $2m+1<M$ and $m>1$.
We can now let T be the permutation $T=(S S')^2$ which is the very useful 3-cycle $(l_{2m},l_{2m+1},r_{2n})$. This has only one element in common with the $R$ cycle, so it is easy to commute with $R^k$ to generate all even permutations of the $r_i$, and from there all even permutations of all $N+M-2$ elements. (For proof see for example the extension lemma on my page on rotational puzzles on graphs.) We therefore get at least the alternating group $A_{N+M-2}$. If $N$ and $M$ are both odd, then $L$ and $R$ are both even permutations and we get only the alternating group. If one or both $N$ and $M$ is even, then we must get odd permutations as well and hence the full symmetric group $S_{N+M-2}$.
If $2m+1=M$ and $M>6$ then we can use $S'= L^2 S L^{-2}$ instead, and the same argument works and again we get the alternating or symmetric group. Similarly, if $m=1$ and $M\ge6$ then $S'= L^3 S L^{-3}$ works.
The puzzle is symmetric, so we can swap the roles of $L$ and $R$. This means that the remaining cases will have $(M,m)$ and $(N,n)$ equal to $(3,1)$, $(4,1)$, $(5,1)$, or $(5,2)$. Note that if $(M,m)=(5,2)$ then we can use $L^2$ as a generator instead of $L$, because $(L^2)^3=L^5=L$. This makes it equivalent to having $(M,m)=(5,1)$ instead. Therefore all these cases have $m=n=1$, and fall under the puzzles analysed in rotational puzzles on graphs. The only exceptional case is $M=N=4$, $m=n=1$, which has a group isomorphic to $S_5$ rather than the expected $S_6$. See also this page for more.
So in almost all the cases so far, the size of the group is $\frac{(M+N-2)!}2$ when M and N are both odd, and $(M+N-2)!$ otherwise.
What is left now is to see what happens when $m=M/2$ and/or $n=N/2$.
Case 1: $M=2m$, and $\gcd(n,N)=1$
In this case $R^n$ is still an $N$-cycle, and $L$ swaps two adjacent elements in that cycle, making it equivalent to having $n=1$. It is easy to prove that all even permutations are possible.
Case 2: $M=2m$, and $N=2n$
The elements form antipodal pairs which never separate. The puzzle can be interpreted as having m+n-1 pieces, each of which has two possible orientations. An example of a physical puzzle of this sort is the Equator. All even permutations of these pairs is possible, and if $N$ or $M$ is divisible by $4$ then odd permutations too. Any two of these pairs can be flipped in place, and if $N$ or $M$ is not divisible by $4$ then any single pair can be flipped. So
Case 3: $M=2m$, and $\gcd(n,N)=d>2$
If $m=1$ then the pieces form $d$ orbits. In each orbit, all permutations are possible, so the group is $(S_{N/d})^d$ and has order $(N/d)!^d$.
If $m>1$, then those orbits from the $m=1$ case merge, and the usual alternating or symmetric group appears depending on the parities of $N$ and $M$.