Verifies that 1260 is the highest possible order of an element in the 3x3 Rubik's cube group

rubik.py

"""
This module verifies that 1260 is the highest possible order of an element in the 3x3 Rubik's cube group.
This is only an upper bound but it turns out that it can also be achieved, so this estimate is precise.
The approach is loosely based on the answer by 'jmerry' at https://math.stackexchange.com/questions/2392906/
"""

from functools import lru_cache
import math


@lru_cache(maxsize=None)
def set_of_partitions(n: int) -> set[tuple[int, ...]]:
    """
    Returns the set of integer partitions of a given non-negative integer n.
    These encode cycle lengths of a permutation of degree n.
    """
    if n == 0:
        return {()}
    result = set()
    for k in range(1, n + 1):
        for q in set_of_partitions(n - k):
            p = tuple(sorted((k,) + q))
            result.add(p)
    return result


def sign(partition: tuple[int, ...]) -> int:
    """
    Computes the sign of a permutation represented by its sequence of cycle lengths, i.e. a partition.
    """
    return (-1) ** (sum(k - 1 for k in partition))


def get_highest_order() -> tuple[int, tuple[int, ...], tuple[int, ...]]:
    """
    Computes the highest possible order of an element in the 3x3 Rubik's cube group.
    Also returns the cycle lengths of the corresponding edge and corner permutations.
    This is only an upper bound a priori, but it turns out to be precise.
    """
    highest_order = 1
    best_edge_partition: tuple[int, ...] = ()
    best_corner_partition: tuple[int, ...] = ()
    edge_partitions = set_of_partitions(12)
    corner_partitions = set_of_partitions(8)
    for corner_partition in corner_partitions:
        for edge_partition in edge_partitions:
            valid = sign(corner_partition) == sign(edge_partition)
            if not valid:
                continue
            order = math.lcm(2 * math.lcm(*edge_partition), 3 * math.lcm(*corner_partition))
            if order > highest_order:
                highest_order = order
                best_edge_partition = edge_partition
                best_corner_partition = corner_partition
    return (highest_order, best_edge_partition, best_corner_partition)


def main():
    highest_order, edge_partition, corner_partition = get_highest_order()
    print(f"The highest possible order in the Rubik's cube group is {highest_order}.")
    print(f"The edge permutation decomposes into cycles of lengths {edge_partition}.")
    print(f"The corner permutation decomposes into cycles of lengths {corner_partition}.")


if __name__ == "__main__":
    main()