# Finding the Cycle Length of A Given Algorithm



## Approaching_Polymathism (Mar 11, 2017)

Hello everybody, like the title of this thread suggests I would like to know the solution to the following problems.

Q. 1: Given two algorithms, ( we shall notate these 'A.1' and 'A.2' ), and their respective cycle lengths, ( which shall be notated as so: 'C(A.1)' and 'C(A.2)' ), is it possible to work out the cycle length of the concatenation of the two formerly mentioned algorithms, without allowing access to a cube so as to try it out by the 'brute force method' ? ( I.e., given data that ( R U R' U ) has a cycle length of 5, and ( R U2 R' ) has a cycle length of 4, it their a strictly algebraic way of determining the cycle length of ( R U R' U R U2 R' ) ? )

Q. 2: Conversely, given one algorithm and it's cycle length is it possible to determine the cycle lengths of any smaller algorithms contained as a sub-set of the algorithm in question ? ( I.e., given the knowledge that ( R U R' U' r u r' u' ) has a cycle length of 60, is there a strictly algebraic way of working out the cycle lengths of ( R U R' U' ) and ( r u r' u' ) respectively ? )

If you are able to solve these problems I will appreciate it, or if you are unable to, at least offer helpful advice. I am aware the answer may require group theory and a fair deal of mathematics, but that is fine, I will quickly learn whatever is initially unfamiliar to me, so feel free to express your thoughts any way you wish, just be nice. Thank you.


----------



## xyzzy (Mar 11, 2017)

Rather than looking specifically at the Rubik's cube group, let's just look at groups in general.

What you call "cycle length" is usually called order, and the order of an element _x_ is denoted as o(_x_).

For any integer _l_, _m_, _n_ ≥ 2, there exists a group _G_ with two elements _x_, _y_ such that o(_x_) = _l_, o(_y_) = _m_, and o(_xy_) = _n_; one such example is given by the von Dyck groups, which can also be thought of as rotational symmetries on a spherical/Euclidean/hyperbolic plane. The von Dyck groups are, in the Euclidean and hyperbolic cases, infinite, but it turns out that we can still give examples of finite groups satisfying the stated criterion. (Cf. Theorem 1.64 in these lecture notes.)

What this means is that, unless we know some additional structure about the group we're working with, we can't make any claim about how the orders of _x_ and _y_ affect the order of _xy_. The obvious question to ask is then, does the Rubik's cube group have this additional structure to exploit? Unfortunately, no.

You don't even have to look very far. The order of R is 4 and the order of R' is also 4. What are the orders of (R R) and (R R')?

One of the few instances where we can deduce o(_xy_) given only o(_x_) and o(_y_) is in the case of abelian groups. In this case, provided that o(_x_) and o(_y_) are coprime, we have that o(_xy_) = o(_x_)o(_y_). Of course, the Rubik's cube group is nonabelian, so this doesn't apply to your problem.


----------



## Approaching_Polymathism (Mar 11, 2017)

Thank you for answering my question, I honestly didn't fully understand some of what you said, but I'll be sure to look at those links.


----------



## Bruce MacKenzie (Sep 3, 2017)

Approaching_Polymathism said:


> Hello everybody, like the title of this thread suggests I would like to know the solution to the following problems.
> 
> Q. 1: Given two algorithms, ( we shall notate these 'A.1' and 'A.2' ), and their respective cycle lengths, ( which shall be notated as so: 'C(A.1)' and 'C(A.2)' ), is it possible to work out the cycle length of the concatenation of the two formerly mentioned algorithms, without allowing access to a cube so as to try it out by the 'brute force method' ? ( I.e., given data that ( R U R' U ) has a cycle length of 5, and ( R U2 R' ) has a cycle length of 4, it their a strictly algebraic way of determining the cycle length of ( R U R' U R U2 R' ) ? )
> 
> ...



The order of an algorithm may be deduced from its permutation representation. Any algorithm may be represented as a permutation of the facelet positions and that permutation may be represented as a product of disjoint cycles. The order of the algorithm is the least common multiple of the the disjoint cycle lengths. The product of two algorithms is the product of their permutation representations and the order of that product may be deduced from its disjoint cycle representation. In GAP:

R := (3,17,11,21)(4,18,12,22)(25,39,46,30)(26,37,47,28)(27,38,48,29);
U := (1,3,5,7)(2,4,6,8)(25,28,31,34)(26,29,32,35)(27,30,33,36);
F := (1,20,9,18)(2,19,10,17)(25,35,40,38)(26,36,41,39)(27,34,42,37);
L := (7,23,15,19)(8,24,16,20)(31,45,40,36)(32,43,41,34)(33,44,42,35);
D := (9,15,13,11)(10,16,14,12)(37,40,43,46)(38,41,44,47)(39,42,45,48);
B := (5,22,13,24)(6,21,14,23)(28,48,43,33)(29,46,44,31)(30,47,45,32);

P1 := U * R^-1 * U * R;
(1,3,7,17,5)(2,4,8,18,6)(25,28,34,33,38)(26,29,35,31,39)(27,30,36,32,37)

P2 := R^-1 * U * U * R;
(1,5)(2,6)(7,17)(8,18)(25,36)(26,34)(27,35)(31,39)(32,37)(33,38)

P3 := P2 * P1;
(3,7,5)(4,8,6)(25,32,27,31,26,33)(28,34,29,35,30,36)

Order(P3);
6

So, the answer to your question is that the order of the concatenation of two algorithms may be calculated but its not trivial.


----------

