8
$\begingroup$

I suspect that many permutation puzzles can be solved in $O(n \log n)$ moves, which has led me to the following question/conjecture:

Suppose that
1. $P_i$ for $i<k=O(1)$ are permutations on an $n$ element set $S$.
2. The group $G$ generated by $P$ is transitive.
3. Each $P_i$ has only $O(1)$ nontrivial cycles.
4. For all but $O(1)$ $u∈S$, $|\{v≠u: ∃i \, (P_i(u)=v ∨ P_i(v)=u)\}| = 2$
5. There are $i$ and $j$ such that $P_i$, $P_j$, $P_i P_j$, $P_i^{-1} P_j$ each move (i.e. act nontrivially on) $Ω(n / \log n)$ elements.

Question: Is every member of $G$ representable as a product $O(n \log n)$ elements of $P$?

I am also interested in special cases of (1)-(5), and in generalizations to other $P$.

(3)-(4) essentially state that $P$ has $O(1)$ branch points. Assuming (1)-(4) and that $G$ is not just a cycle, I conjecture that (5) is both necessary and sufficient, and that more generally, using $f(n)$ in place of $n / \log n$, we get $O(\max(n^2/f(n), n \log n))$. By a communication complexity (or distance function) argument, this is optimal (but I did not formally prove that $G$ is large enough, and same below).

By a counting argument, $O(n \log n)$ (if achievable) is optimal up to a constant factor. Conversely, if permutations behave randomly enough, and unless there is some approximate symmetry or slowly varying quantity, then $O(n \log n)$ should suffice (but it is open whether this actually holds for $S_n$ or $A_n$ generated by a pair of random permutations). A typical example of a slowly varying quantity is $Σ_{u,v} |d(R(u),R(v))-d(T(u),T(v))|$ for some distance function $d$, current sequence of moves/permutation $R$, and desired permutation $T$. However, the conditions in the question appear just enough for good mixing behavior.

The only primitive groups for the conditions appear to be $A_n$ and $S_n$. However, there are $P$ that preserve antipodal pairs (or more generally $i$-tuples for $i=O(1)$).

Applications to puzzles

Permutation groups with a distinguished set of generators can be viewed as puzzles: Each element is an instance of the puzzle, and the generators (such as $P_i$ above) are the permitted moves. The directed diameter is the maximum number of moves needed to solve a puzzle, with the undirected diameter also permitting inverse generators (such as $P_i^{-1}$) as moves.

An example is a Hungarian rings puzzle, where $A$ and $B$ are cyclic permutations of length $Θ(n)$ that intersect at two points (implemented mechanically as two interlocking rings filled with balls). A positive answer would imply that the puzzle can be solved in $O(n \log n)$ moves.

Another example is the generalized 15 puzzle, which uses pebbles on a graph $G$ with one empty space (and one pebble on each other vertex), with each move moving a pebble to the adjacent empty space. Thus, for each location of the empty space, the positions form a group. There are graphs requiring $Θ(n^3)$ moves (but not more), see Coordinating Pebble Motion on Graphs, the Diameter of Permutation Groups, and Applications. However, a positive answer implies that for every graph $G$ without cycles of length $o(n)$, one can solve a solvable puzzle in $Θ(n^2 \log n)$ moves, which is optimal (if $G$ is also nonseparable and has more than one cycle) since we take an average of $Θ(n)$ moves between branches with $O(1)$ choices. On a separate note, I do not know whether for graphs with logarithmic diameter, $O(n \log n)$ moves suffices.

The group structure makes typical permutation puzzles tractable. The decision problem is solvable using Schreier–Sims algorithm, and with exception of four Mathieu groups, every 4-transitive group includes every even permutation. If for some $k$, a permutation group is $k$-transitive (using $O(t)$ moves) and includes some permutation that moves just $k$-elements (using $O(t)$ moves), then it includes every even permutation (using $O(tn)$ moves, at least if inverses of moves are valid moves). In many puzzles, the commutator $ABA^{-1}B^{-1}$ moves just a few elements, and (separately from this) by relying on elements not moved by $A$, we can grow chains of elements and get $k$-transitivity, and typically get a quadratic time solution (or cubic time for generalized 15 puzzle). However, the optimal number of moves can be NP hard, so instead, we ask for asymptotic optimality (for positions that are not easier than random) up to a constant factor.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.