Open problems — frontiers of group theory

The "basic invariants" of the cube group (order, diameter, structure theorem) are completely settled. But step out by even one notch and several problems still resist the mathematical community after 50 years — spanning combinatorics, geometry, complexity, and quantum algorithms.

16.1 4×4×4's God's number

The 4×4×4's diameter is bounded only to [22, 36] HTM. With order $|G_4|\approx 7.4\times 10^{45}$, exhaustive enumeration is impossible — 27 orders of magnitude beyond the atom count of the observable universe. The strongest approaches use:

• Subgroup-chain reduction — Thistlethwaite-style but the 4×4×4 lacks fixed centres, so reduction (3 phases to bring the puzzle to 3×3×3-equivalent) precedes the 3×3×3 algorithm. Total estimate 35–45 HTM.
• Symmetry reduction — collapse by the 48 outer cube symmetries, leaving |G|/48. Still far too large.
• Learning-guided search — DeepCubeA (UCI, 2019) uses RL to approximate an optimal-distance heuristic, solving most states in feasible time but not proving lower bounds.

16.2 Asymptotics of n×n×n

For general n × n × n, Demaine, Demaine, Eisenstat, Lubiw, Winslow (2018) proved that finding the optimal alg is NP-complete for n ≥ 2. The same paper established asymptotic bounds:

The Θ-bracket is tight, but the exact constant inside is unknown. We have $c_1\le c_2$ with $c_1{n}^2/\log n\le \mathrm{diam}(G_n)\le c_2{n}^2/\log n$, but the explicit values of $c_1,c_2$ are open. This is a flagship problem in "puzzle complexity."

16.3 Statistical properties of optimal solutions

The 3×3 HTM diameter = 20 is settled. But what is the average optimal solve length? Rokicki measured over all 4.3 × 10¹⁹ states an average $\bar{d}\approx 17.97$ HTM. So nearly 99% of states need 16–20 moves — the distance distribution is highly concentrated. The following sub-questions remain open:

• Is the distance distribution exactly Gaussian? (Empirically near-Gaussian, but no theoretical reason)
• Is the count N(d) of states at distance d log-concave?
• Is the QTM/HTM ratio 26/20 = 1.3 a universal constant?

16.4 Which solver is best?

Thistlethwaite (1981) and Kociemba's two-phase (1992) are subgroup-chain descent algorithms, slicing state space into lookup layers. But several entirely different approaches exist:

• Korf's IDA* (1997) — iterative-deepening A* directly on the Cayley graph with three pattern-database heuristics. First algorithm shown to be provably optimal.
• Rokicki's symmetry-augmented BFS (2010) — halves state space via the 48 cube symmetries before BFS, the algorithm used to prove God's number = 20.
• DeepCubeA (UCI, 2019) — learns a Q-function; not provably optimal but consistently near-optimal in practice.
• min2phase / cube20.org — production-grade two-phase implementations, averaging well under 20 moves with constant-factor speedups.

Which method is Pareto-optimal in "average optimal length × runtime"? Tied tightly to G's structure (generator symmetry, subgroup-chain decomposability), this remains a long-running research question.

16.5 Quantum algorithms?

Can a quantum computer solve the cube in subexponential time? This sits at the intersection of black-box group theory and quantum algorithms. Shor's algorithm handles Abelian groups (integer factorization, discrete log); the non-Abelian Hidden Subgroup Problem (HSP) — open:

For Abelian G there is an $O(\mathrm{poly}\log |G|)$ quantum algorithm; for general non-Abelian G, subexponential $2^{O(\sqrt{\log |G|})}$ is known only for some classes (dihedral groups, certain solvable groups). The cube group is a perfect non-Abelian HSP testbed — any polynomial quantum algorithm on G would be a major breakthrough.

16.6 Random-walk cutoff threshold

Diaconis (1980s) introduced the cutoff phenomenon: for many natural random walks on groups, $d_{TV}(t)$ sits near 1 for a long time and then drops sharply within a narrow window (§24). The classic example: Bayer–Diaconis (1992) proved 52 cards need $\frac{3}{2}{\log }_{2}52\approx 8.5$ riffle shuffles to mix. For the cube:

Lower bound ~18, upper ~30, exact threshold unproven. WCA's 25-move scramble is no accident — above the estimated cutoff, above the proven God's number (20), without hitting known extremal positions.