An Almost-Optimal Upper Bound on the Push Number of the Torus Puzzle
Pith reviewed 2026-05-21 16:17 UTC · model grok-4.3
The pith
The Torus Puzzle can be solved with O(mn log max{m,n}) unit rotations in a restricted model, implying an almost-optimal upper bound on the push number.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We provide an algorithm that solves the Torus Puzzle using O(mn · log max {m, n}) unit rotations in a model that is more restricted than that of the original puzzle. This implies a corresponding upper bound on the push number and reduces the gap between the known upper and lower bounds from Θ(max{m,n}) to Θ(log max{m, n}).
What carries the argument
An algorithm that solves the puzzle using unit rotations in a restricted model more constrained than the original.
If this is right
- The push number of the Torus Puzzle is at most O(mn log max{m, n}).
- The gap between upper and lower bounds on the push number shrinks from Θ(max{m,n}) to Θ(log max{m, n}).
- The more permissive drag number variant, already known to be O(mn), is now within a logarithmic factor of the push number.
Where Pith is reading between the lines
- The fact that a stricter model suffices suggests that arbitrary shifts in the permissive variant do not reduce the asymptotic move count by more than a log factor.
- The approach might extend to other row-column shift puzzles or grid rearrangement tasks where move counts depend on dimension sizes.
- Empirical tests on moderate-sized grids could check whether the logarithmic term appears in practice or can be removed.
Load-bearing premise
The bound from the more restricted model also serves as an upper bound for the standard push number in the original puzzle.
What would settle it
An instance of the Torus Puzzle requiring more than c mn log max{m,n} unit rotations for some constant c would disprove the upper bound.
read the original abstract
We study the Torus Puzzle, a solitaire game in which the elements of an input $m \times n$ matrix need to be rearranged into a target configuration via a sequence of unit rotations (i.e., circular shifts) of rows and/or columns. Amano et al. proposed a more permissive variant of the above puzzle, where each row and column rotation can shift the involved elements by any amount of positions. The number of rotations needed to solve the original and the permissive variants of the puzzle are respectively known as the \emph{push number} and the \emph{drag number}, where the latter is always smaller than or equal to the former and admits an existential lower bound of $\Omega(mn)$. While this lower bound is matched by an $O(mn)$ upper bound, the push number is not so well understood. Indeed, to the best of our knowledge, only an $O(mn \cdot \max\{ m, n \})$ upper bound is currently known. In this paper, we provide an algorithm that solves the Torus Puzzle using $O(mn \cdot \log \max \{m, n\})$ unit rotations in a model that is more restricted than that of the original puzzle. This implies a corresponding upper bound on the push number and reduces the gap between the known upper and lower bounds from $\Theta(\max\{m,n\})$ to $\Theta(\log \max\{m, n\})$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims an O(mn log max{m,n}) upper bound on the push number of the Torus Puzzle. It does so by exhibiting an explicit algorithm that solves the puzzle using that many unit rotations inside a model explicitly described as more restricted than the standard Torus Puzzle model; the abstract asserts that this yields a corresponding upper bound on the (standard) push number and reduces the gap to the known Omega(mn) lower bound from Theta(max{m,n}) to Theta(log max{m,n}).
Significance. If the transfer from the restricted model to the standard push number holds, the result would be a substantial improvement over the prior O(mn max{m,n}) upper bound and would nearly match the existential Omega(mn) lower bound up to a logarithmic factor. The construction of an explicit algorithm rather than an existential argument is a methodological strength.
major comments (1)
- [Abstract] Abstract (paragraph on implications): the central claim that the O(mn log max{m,n}) algorithm in the more restricted rotation model implies an upper bound on the standard push number is not supported by any exhibited argument showing that every sequence produced remains a legal sequence of unit row/column rotations in the original model or that its length upper-bounds the minimum length in the standard model. This transfer is load-bearing for the headline result.
Simulated Author's Rebuttal
We thank the referee for the careful reading of the manuscript and for identifying the need to strengthen the justification for the central implication in the abstract. We respond to the major comment below.
read point-by-point responses
-
Referee: [Abstract] Abstract (paragraph on implications): the central claim that the O(mn log max{m,n}) algorithm in the more restricted rotation model implies an upper bound on the standard push number is not supported by any exhibited argument showing that every sequence produced remains a legal sequence of unit row/column rotations in the original model or that its length upper-bounds the minimum length in the standard model. This transfer is load-bearing for the headline result.
Authors: We agree that the abstract asserts the implication without an explicit one-sentence justification, which should be added for clarity. In the full paper the restricted model is defined as a strict subset of the legal operations of the standard model: every move is still a unit (by-1) circular shift of a single row or column, but the algorithm is constrained to select only certain rows/columns at each step according to a predetermined ordering. Consequently every sequence our algorithm produces is a valid sequence of unit rotations in the original model, and its length therefore upper-bounds the push number. We will revise the abstract (and add a short clarifying paragraph in the introduction) to state this transfer explicitly. revision: yes
Circularity Check
Explicit constructive algorithm yields non-circular upper bound
full rationale
The paper derives the O(mn log max{m,n}) upper bound on push number by exhibiting a concrete algorithm that produces a solving sequence of unit rotations. Because the algorithm operates inside an explicitly more restricted move set whose operations are a subset of those permitted in the standard model, every sequence it outputs is valid in the original puzzle by definition of the restriction; the length of that sequence is therefore a valid (constructive) upper bound without any reduction to fitted parameters, self-definitional equations, or load-bearing self-citations. The abstract and description contain no ansatz smuggling, renaming of known results, or uniqueness theorems imported from prior author work; the derivation is self-contained against the external benchmark of the algorithm's own move count.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Basic facts about the group generated by row and column rotations on an m by n grid.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.