• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Finding the Cycle Length of A Given Algorithm

Joined
Jan 29, 2017
Messages
2
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

Member
Joined
Dec 24, 2015
Messages
2,878
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.
 
Last edited:
Joined
Sep 3, 2017
Messages
105
Location
USA
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. :)

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.
 
Last edited:
Top