An Almost-Optimal Upper Bound on the Push Number of the Torus Puzzle

We prove the claim by focusing on a generic column $C_j$ and showing that, once $C_j$ is rotated $m-1$ times, FillColumns performs no additional rotations on $C_j$.

Indeed, FillColumns ensures that each rotation of $C_j$ moves some element $x$ having target column $C_j$ into the body of $C_j$ and, specifically, into $C_j[2]$. Since $m-1$ additional downward rotations of $C_j$ are needed for $x$ to leave the body of $C_j$, we have that after performing any number $h\in \{0,\mathrm{\dots },m-1\}$ rotations of $C_j$, the body of $C_j$ contains at least $h$ elements whose target column is $C_j$. Then, if the $(m-1)$-th rotation of $C_j$ is performed, it must result in a column that is near-full. The claim follows by observing that FillColumns only rotates columns that are not near-full. $◀$

Let $A_0=A$ be the input matrix to FillColumns, and let $A_h$ be the matrix as arranged immediately after the completion of the $h$-th iteration of the outer while loop of Algorithm 1, if it exists. We associate a potential $\mathrm{\Psi }(A_h)$ to each $A_h$, where $\mathrm{\Psi }(A_h)$ is defined as the number of elements $x$ in $A_h$ that are in the body of some column other than their target column, i.e., $\mathrm{\Psi }(A_h)=|\{(i,j)\in \{2,\mathrm{\dots },m\}\times \{1,\mathrm{\dots },n\}:\mathrm{t}-\mathrm{col}(C_j[i])\ne j\}|$. The following lemma shows that each group of $n$ iterations of the outer while loop starting from some configuration $A_h$ decreases the potential by at least half the number of underfull columns in $A_h$.

We assume that $A_{h+n}$ exists since otherwise the claim is trivially true. For an underfull column $C_j$ of $A_h$, we let $X_j$ be the set of elements $x$ in $R$ that have $C_j$ as their target column (i.e., such that $\mathrm{t}-\mathrm{col}(x)=j$), while for each near-full column $C_j$ we let $X_j=\mathrm{\varnothing }$.

Since row $R$ of configuration $A_h$ contains at most one element with target column $C_j$ for each of the $n-f$ near-full columns $C_j$, there must be at least $f$ distinct elements in $R$ whose target column is underfull. Hence, ${\sum }_{j=1}^n|X_j|\ge f$.

In the rest of the proof we argue that at least $\frac{1}{2}{\sum }_{j=1}^n|X_j|$ elements from ${\cup }_{j=1}^n{X}_j$ are placed in the bodies of their respective columns in $A_{n+h}$. Since the only way for FillColumns to move an element $x$ from the head to the body of its target column $C_j$ is that of rotating $C_j$ until some other element $y\ne x$ with $\mathrm{t}-\mathrm{col}(y)\ne j$ ends up in $R$, causing $\mathrm{\Psi }(\cdot )$ to decrease by $1$, this will imply that $\mathrm{\Psi }(A_{h+n})\le \mathrm{\Psi }(A_h)-\frac{1}{2}{\sum }_{j=1}^n|X_j|\le \mathrm{\Psi }(A_h)-\frac{f}{2}$, as claimed.

In particular, we focus on a specific column $C_j$ with $|X_j|\ge 1$, and we show that at least $\max \{1,|X_j|-1\}\ge \frac{|X_j|}{2}$ of the elements in $X_j$ are in the body of $C_j$ in configuration $A_{h+n}$. Since row $R$ is rotated $n$ times from configuration $A_h$ to configuration $A_{h+n}$, and $C_j$ is only rotated if $\mathrm{t}-\mathrm{col}(C_j[1])=j$, we have that each element $x\in X_j$ becomes the head of $C_j$ in some (distinct) configuration $A_{\mathrm{\ell }(x)}$ with . Let $x_1,\mathrm{\dots },x_k$ be the elements in $X_j$, in increasing order of $\mathrm{\ell }(x_i)$. Consider then the $\mathrm{\ell }(x_i)$-th iteration of the outer while loop of FillColumns. If $i=1$ or , then $C_j$ is underfull in $A_{\mathrm{\ell }(x_i)}$, which means that $x$ is moved to the body of $C_j$ in such iteration, and never leaves it in the following iterations. It follows that at least $\max \{1,k-1\}$ elements are in the body of $C_j$ in configuration $A_{h+n}$. $◀$

The above lemma allows us to upper bound the number of rotations of the first row.

We partition the rotations of $R$ performed by FillColumns into $1+\lfloor \log n\rfloor$ phases. We say that a configuration $A_h$ belongs to the $i$-th phase if its number of underfull columns lies in the half-open interval $[\frac{n}{2^{i-1}},\frac{n}{2^i})$. We also say that a rotation of $R$ belongs to phase $i$ if the configuration $A_h$ from which it is performed belongs to phase $i$.

By our definition of $\mathrm{\Psi }(\cdot )$, we have that if $A_h$ is in phase $i$, then $\mathrm{\Psi }(A_h)\le \frac{n}{2^{i-1}}(m-1)$. Moreover, Lemma 3 ensures that, if $A_{h+n}$ exists, then $\mathrm{\Psi }(A_{h+n})\le \mathrm{\Psi }(A_h)-\frac{n}{2^{i+1}}$. This shows that there can be at most $\frac{n}{2^{i-1}}(m-1)\cdot \frac{2^{i+1}}{n}=4(m-1)$ disjoint groups of $n$ rotations of $R$ in phase $i$. Hence, the number of rotations of $R$ in each phase is at most . The claim follows by multiplying $4mn$ by the number of phases. $◀$

The stopping condition of FillColumns, together with Lemma 2 and Lemma 4, imply the following corollary, which summarizes the result of this section.

As a warm-up, we start by sketching how a single body-full column $C_j$ can be made body-sorted using $O(n\cdot \log m)$ rotations. The procedure will only rotate $R$ and $C_j$, hence all elements in the body of columns other than $C_j$ will remain in their initial positions. In particular, any other column that is already body-full (resp. body-sorted) will remain body-full (resp. body-sorted). This also means that the set of elements in $R$ will remain unchanged, although their order might change.

The idea is that of simulating the RadixSort algorithm on the elements in the body of $C_j$. We achieve this by repeatedly unloading the body of $C_j$ into $R$ and then re-loading the same elements back into $C_j$ in a suitable order. In particular, the procedure consists of $\lceil \log (m-1)\rceil$ phases, where the $\mathrm{\ell }$-th phase sorts the elements $x$ of $C_j$ according to the $\mathrm{\ell }$-th least significant bit of (a suitably shifted version of) $\mathrm{t}-\mathrm{row}(x)$. This sorting step is stable; hence, after the last phase is completed, column $C_j$ is body-sorted.

In details, a phase is subdivided into three sub-phases. In the first sub-phase we unload all elements of $C_j$ into $R$ with the sequence of rotations ${(C_{j}R)}^{m-1}{R}^{n-m+1}$, which also ensures that the overall number of rotations of $R$ is $n$. The second sub-phase rotates $R$ $n$ additional times and, before each rotation, we check whether the element $x$ on the head of $C_j$ should be moved to the body of $C_j$, namely if $\mathrm{t}-\mathrm{col}(x)=j$, $\mathrm{t}-\mathrm{row}(x)\ge 2$, and the $\mathrm{\ell }$-th least significant bit $\mathrm{lsb}(\mathrm{t}-\mathrm{row}(x)-2,\mathrm{\ell })$ of $\mathrm{t}-\mathrm{row}(x)-2$ is set. At this point, $R$ has been rotated $2n$ times, and all the elements that were originally in the body of $C_j$ and have their $\mathrm{\ell }$-th least significant bit set are now in the body of $C_j$. The third and final sub-phase is similar to the second one, with the only difference that the condition $\mathrm{lsb}(\mathrm{t}-\mathrm{row}(x)-2,\mathrm{\ell })=1$ is replaced with $\mathrm{lsb}(\mathrm{t}-\mathrm{row}(x)-2,\mathrm{\ell })=0$. This loads the remaining elements into $C_j$. Observe that in the second and third sub-phases, the elements inserted in $C_j$ are encountered in the same order in which they were unloaded, hence each phase is stable.

Unfortunately, while sequentially applying the above simulation of RadixSort on each column $C_j$ would render all columns body-full, this would require $\mathrm{\Omega }(n^2\cdot \log m)$ rotations, which is asymptotically larger than our $O(mn\cdot \log n)$ goal whenever $n=\omega (m)$.

To circumvent this issue, we show how to generalize the above RadixSort-inspired scheme to handle a number $k$ of up to $\frac{n}{m-1}$ columns in parallel. The resulting procedure, which we name RadixSortBodies, performs $O((n+km)\cdot \log m)$ rotations and its pseudocode is given in Algorithm 3.

Let $𝒞=\{j_1,j_2,\mathrm{\dots },j_k\}$ be a set of $k$ column indices. RadixSortBodies starts by unloading, in parallel, the bodies of all columns $C_j$ with $j\in 𝒞$ into $R$. In order to do that, we choose $k$ pairwise-disjoint subsets $I_1,\mathrm{\dots },I_k$ of $\{1,\mathrm{\dots },n\}$, each containing $m-1$ elements, e.g., we can choose $I_h=\{(h-1)(m-1)+1,(h-1)(m-1)+2,\mathrm{\dots },h(m-1)\}$.⁶⁶6The algorithm described previously for sorting the body of a single column corresponds to the case $k=1$, $𝒞=\{j_1\}$, and the choice $I_1=\{1,\mathrm{\dots },j_1\}\cup \{n-m+j_1+2,\mathrm{\dots },n\}$ (where the second set of the union might be empty). Intuitively, set $I_h$ is associated to column $C_{j_h}$ and contains the $m-1$ indices $i$ corresponding to the positions $R[i]$ into which RadixSortBodies unloads the elements in the body of $C_{j_h}$.

As before, the procedure works in $\lceil \log (m-1)\rceil$ phases, where the $\mathrm{\ell }$-th phases is concerned with sorting the elements of interest w.r.t. their $\mathrm{\ell }$-th least significant bit. Similarly, each phase is also split into three sub-phases.

The first sub-phase unloads all elements in the body of the columns $C_j$ with $j\in 𝒞$ into $R$. In order to do so, we define $\rho (j,r)=((j-r-1)modn)+1$ so that, as a result of performing $r$ rotations of $R$, the element that ends up in $R[j]$ is the one that was originally placed in $R[\rho (j,r)]$. In this sub-phase, row $R$ is rotated $n$ times and, before each rotation, we check whether $\rho (j_h,r)\in I_h$ for each $h\in 𝒞$. For all $j_h$ that satisfy the above condition, we rotate $C_{j_h}$, thus moving the element currently on the tail of $C_{j_h}$ into $R$.

The second and third sub-phases behave similarly to one another, and handle the elements having their $\mathrm{\ell }$-th least significant bit set to $1$ and $0$, respectively. The second (resp. third) sub-phase, rotates $R$ $n$ times and, before each rotation, checks whether any of the elements currently on the heads the columns whose bodies are to be sorted should be loaded into their column’s body. More precisely, if $x$ is the head of some column $C_j$ with $j\in 𝒞$, this happens when $\mathrm{t}-\mathrm{col}(x)=j$, $\mathrm{t}-\mathrm{row}(x)\ge 2$, and $\mathrm{lsb}(\mathrm{t}-\mathrm{row}(x)-2,\mathrm{\ell })=1$ for the second sub-phase (resp. $\mathrm{lsb}(\mathrm{t}-\mathrm{row}(x)-2,\mathrm{\ell })=0$ for the third sub-phase). Notice that, within each of the last two sub-phases, the loaded elements are inserted in the bodies of the respective columns in the same order as they were unloaded in the first phase, hence the overall algorithm is stable. Figure 5 shows some configurations encountered during an execution of RadixSortBodies.

It is now easy to transform any matrix in which each column is body-full into a matrix in which each column is body-sorted using $O(mn\cdot \log n)$ rotations.

Indeed, it suffices to arbitrarily partition the $n$ columns into $k=\lceil \frac{n}{\lfloor \frac{n}{m-1}\rfloor }\rceil$ groups $G_1,G_2,\mathrm{\dots },G_k$ of $\lfloor \frac{n}{m-1}\rfloor$ columns each, except possibly for $G_k$ (which has size $nmod(m-1)$). Then, we iteratively make the columns in each group $G_i$ body-full by invoking RadixSortBodies on the columns in $G_i$, which requires $O\left((n+\frac{n}{m-1}\cdot m)\cdot \log m\right)=O(n\cdot \log m)$ rotations. Since the number of groups is $O(m)$, the overall number of rotations is $O(mn\cdot \log m)$.
The following lemma summarizes the discussion in this section.

We start by describing an auxiliary procedure that takes as input a collection of $k$ pairs $(c_1,c_1^{\prime }),\mathrm{\dots },(c_k,c_k^{\prime })$ of column indices, where all such indices are distinct, and swaps each element in $R[c_j]$ with that in $R[c_j^{\prime }]$, for all $j=1,\mathrm{\dots },k$. We name this procedure SwapPairs and we give its pseudocode in Algorithm 4.

SwapPairsperforms $O(nk)$ rotations but produces some side effects. More precisely, the procedure needs to use a distinct auxiliary column for each pair $(c_j,c_j^{\prime })$ which, for the sake of simplicity, we chose to be column $C_j$. The elements in the body of each auxiliary column $C_j$ will undergo a circular shift, which can be either upward (i.e., $C_j[i]$ moves to $C_j[i-1]$ for $i=3,\mathrm{\dots },m$, and $C_j[2]$ moves to $C_j[m]$) or downward (i.e., $C_j[i]$ moves to $C_j[i+1]$ for $i=2,\mathrm{\dots },m-1$, and $C_j[m]$ moves to $C_j[2]$). The direction of these rotations is controlled by an additional input parameter $d\in \{\text{U},\text{D}\}$, where U (resp. D) denotes an upward (resp. downward) rotation.

We note that these side effects are unavoidable as long as the algorithm needs to work for matrices of arbitrary dimensions. Indeed, it is impossible to swap two (or any even number of pairs of) elements without introducing side effects, as this would allow one to change the parity of the permutation induced by positions of the elements in the matrix (see Remark 1).

The procedure works in three phases. In the first phase, row $R$ is rotated $n$ times. Before the generic $r$-th rotation, we check for which indices $j=1,\mathrm{\dots },k$ the element originally in $R[c_j]$ is now in $R[j]$, i.e., i.e., we check whether $\rho (j,r)=c_j$. For any such index $j$, we rotate $C_j$ one time if $d=\text{D}$ or $m-1$ times if $d=\text{U}$ (effectively simulating an upward rotation of $C_j$). Denoting with $S_1$ the sequence of all rotation performed in the first phase, the overall effect of the phase is the following, where $j=1,\mathrm{\dots },k$ and all elements that not explicitly handled are unaffected:

• $\mathrm{■}$

  When $d=\text{D}$, $R[c_j]\stackrel{S_1}{\to }{C}_j[2]$, $C_j[m]\stackrel{S_1}{\to }R[c_j]$, and $C_j[i]\stackrel{S_1}{\to }{C}_j[i+1]$ for $i=2,\mathrm{\dots },m-1$;

• $\mathrm{■}$

  When $d=\text{U}$, $R[c_j]\stackrel{S_1}{\to }{C}_j[m]$, $C_j[2]\stackrel{S_1}{\to }R[c_j]$, and $C_j[i]\stackrel{S_1}{\to }{C}_j[i-1]$ for $i=3,\mathrm{\dots },m$.

In the second phase, $R$ is again rotated $n$ times. Before the generic $r$-th rotation, we find all columns $C_j$ that satisfy $\rho (j,r)=c_j^{\prime }$, and we rotate each such column $m-1$ times if $d=\text{D}$, or one time if $d=\text{U}$. The net effect of the sequence $S_2$ of rotations performed during the second phase (on the matrix resulting from the first phase) is the following:

• $\mathrm{■}$

  When $d=\text{D}$, $R[c_j^{\prime }]\stackrel{S_2}{\to }{C}_j[m]$, $C_j[2]\stackrel{S_2}{\to }R[c_j^{\prime }]$, and $C_j[i]\stackrel{S_2}{\to }{C}_j[i-1]$ for $i=3,\mathrm{\dots },m$.

• $\mathrm{■}$

  When $d=\text{U}$, $R[c_j^{\prime }]\stackrel{S_2}{\to }{C}_j[2]$, $C_j[m]\stackrel{S_2}{\to }R[c_j^{\prime }]$, and $C_j[i]\stackrel{S_2}{\to }{C}_j[i+1]$ for $i=2,\mathrm{\dots },m-1$;

The third and final phase is identical to the first one, hence its sequence of rotations $S_3$ produces the same net effect (on the matrix resulting from the second phase) as that of sequence $S_1$. Figure 6 shows some example configurations obtained after the different phases, and after successive executions of SwapPairs.
We can now use SwapPairs to apply any involution to $R$, as the following lemma shows.

Let ${\tau }_1,{\tau }_2,\mathrm{\dots },{\tau }_k$ be the $k=a_2(\pi )$ transpositions of $\pi$, where ${\tau }_j=(c_j{c}_j^{\prime })$. We invoke SwapPairs using the same value of $d$ as the one in the statement and with the $k$ pairs of column indices $(c_j,c_j^{\prime })$ for $j=1,\mathrm{\dots },k$.

We now prove that such a call has the desired effect. To see that each pair of elements $R[c_j],R[c_j^{\prime }]$ with $j=1,\mathrm{\dots },k$ is indeed swapped, observe that:

• $\mathrm{■}$

  When $d=\text{D}$, $R[c_j]\stackrel{S_1}{\to }{C}_j[2]\stackrel{S_2}{\to }R[c_j^{\prime }]\stackrel{S_3}{\to }R[c_j^{\prime }]$ and $R[c_j^{\prime }]\stackrel{S_1}{\to }R[c_j^{\prime }]\stackrel{S_2}{\to }{C}_j[m]\stackrel{S_3}{\to }R[c_j]$.

• $\mathrm{■}$

  When $d=\text{U}$, $R[c_j]\stackrel{S_1}{\to }{C}_j[m]\stackrel{S_2}{\to }R[c_j^{\prime }]\stackrel{S_3}{\to }R[c_j^{\prime }]$ and $R[c_j^{\prime }]\stackrel{S_1}{\to }R[c_j^{\prime }]\stackrel{S_2}{\to }{C}_j[2]\stackrel{S_3}{\to }R[c_j]$.

To see that the body of each column $C_j$ with $j\in \{1,\mathrm{\dots },k\}$ undergoes the claimed circular shift, observe that:

• $\mathrm{■}$

  When $d=\text{D}$, $C_j[i]\stackrel{S_1}{\to }{C}_j[i+1]\stackrel{S_2}{\to }{C}_j[i]\stackrel{S_3}{\to }{C}_j[i+1]$ for $i=2,\mathrm{\dots },m-1$, and $C_j[m]\stackrel{S_1}{\to }R[c_j]\stackrel{S_2}{\to }R[c_j]\stackrel{S_3}{\to }{C}_j[2]$.

• $\mathrm{■}$

  When $d=\text{U}$, $C_j[i]\stackrel{S_1}{\to }{C}_j[i-1]\stackrel{S_2}{\to }{C}_j[i]\stackrel{S_3}{\to }{C}_j[i-1]$ for $i=3,\mathrm{\dots },m$, and $C_j[2]\stackrel{S_1}{\to }R[c_j]\stackrel{S_2}{\to }R[c_j]\stackrel{S_3}{\to }{C}_j[m]$.

To conclude the proof, notice that all elements not explicitly discussed above retain their positions after the rotations in $S_1$, $S_2$, and $S_3$. $◀$

We now employ the above result to place all elements in $R$ in their target position, while keeping all columns $C_2,\mathrm{\dots },C_n$ body sorted, and possibly causing circular shift in the body of $C_1$.

It is folklore that any permutation $\pi$ can be written as the product of two involutions (see, e.g., [28]). One can also ensure that, when $\pi$ is even, these two involutions have the same number of transpositions, while the odd case requires one more transposition. We formally state this result in the following two lemmas, in a way that is convenient for the sequel.

Assume w.l.o.g. that $\pi =(\mathrm{1\hspace{0.33em}2}\mathrm{\dots }\mathrm{\ell })$. The proof is split in two cases, depending on the parity of $\pi$. If $\pi$ is even, then $\mathrm{\ell }=2k+1$ for some positive integer $k$. We choose $\sigma =(\mathrm{1\hspace{0.33em}2}k+1)(\mathrm{2\hspace{0.33em}2}k)(\mathrm{3\hspace{0.33em}2}k-1)\mathrm{\dots }(kk+2)$, and $\upsilon =(\mathrm{2\hspace{0.33em}2}k+1)(\mathrm{3\hspace{0.33em}2}k)(\mathrm{4\hspace{0.33em}2}k-1)\mathrm{\dots }(k+1k+2)$. Observe that $a_2(\sigma )=a_2(\upsilon )=k$. An example is shown in Figure 7 (left).

If $\pi$ is odd, then $\mathrm{\ell }=2k$ for some positive integer $k$. We choose ${\sigma }^{+}=(\mathrm{1\hspace{0.33em}2}k)(\mathrm{2\hspace{0.33em}2}k-1)(\mathrm{3\hspace{0.33em}2}k-2)\mathrm{\dots }(kk+1)$, and ${\upsilon }^{+}=(\mathrm{2\hspace{0.33em}2}k)(\mathrm{3\hspace{0.33em}2}k-1)(\mathrm{4\hspace{0.33em}2}k-2)\mathrm{\dots }(kk+2)$. Observe that $a_2({\sigma }^{+})=k$ and $a_2({\upsilon }^{+})=k-1$. An example is shown in Figure 7 (middle). We also choose ${\sigma }^{-}=(\mathrm{1\hspace{0.33em}2}k-1)(\mathrm{2\hspace{0.33em}2}k-2)(\mathrm{3\hspace{0.33em}2}k-3)\mathrm{\dots }(k-1k+1)$ and ${\upsilon }^{-}=(\mathrm{1\hspace{0.33em}2}k)(\mathrm{2\hspace{0.33em}2}k-1)(\mathrm{3\hspace{0.33em}2}k-2)\mathrm{\dots }(kk+1)$. Observe that $a_2({\sigma }^{-})=k-1$ and $a_2({\upsilon }^{-})=k$. An example is shown in Figure 7 (right). $◀$

Let $C_1^{\text{even}},C_2^{\text{even}},\mathrm{\dots }{C}_h^{\text{even}}$ and $C_1^{\text{odd}},C_2^{\text{odd}},\mathrm{\dots },C_k^{\text{odd}}$ be the non-trivial even and odd cycles of $\pi$, respectively. Lemma 9 shows that we can write each even cycle $C_i^{\text{even}}$ as $C_i^{\text{even}}={\sigma }_i{\upsilon }_i$, where ${\sigma }_i$ and ${\upsilon }_i$ are two involutions with the same number of transpositions. We let ${\sigma }^{\text{even}}={\sigma }_1{\sigma }_2\mathrm{\dots }{\sigma }_h$ and ${\upsilon }^{\text{even}}={\upsilon }_1{\upsilon }_2\mathrm{\dots }{\upsilon }_h$. Similarly, Lemma 9 shows that we can write each odd cycle $C_i^{\text{odd}}$ as both $C_i^{\text{odd}}={\sigma }_i^{+}{\upsilon }_i^{+}$ and $C_i^{\text{odd}}={\sigma }_i^{-}{\upsilon }_i^{-}$, where each of ${\sigma }_i^{+}$, ${\upsilon }_i^{+}$, ${\sigma }_i^{-}$, and ${\upsilon }_i^{-}$ is an involution, $a_2({\sigma }_i^{+})=a_2({\upsilon }_i^{+})+1$, and $a_2({\sigma }_i^{-})=a_2({\upsilon }_i^{-})-1$.

The rest of the proof depends on the parity of $\pi$. We consider the case in which $\pi$ is even first, which implies that $k$ is also even. We let ${\sigma }^{\text{odd}}={\sigma }_1^{-}{\sigma }_2^{+}{\sigma }_3^{-}{\sigma }_4^{+}{\sigma }_5^{-}\mathrm{\dots }{\sigma }_k^{+}$ and ${\upsilon }^{\text{odd}}={\upsilon }_1^{-}{\upsilon }_2^{+}{\upsilon }_3^{-}{\upsilon }_4^{+}{\upsilon }_5^{-}\mathrm{\dots }{\upsilon }_k^{+}$ (notice the alternating superscripts). The claim follows by choosing $\sigma ={\sigma }^{\text{even}}{\sigma }^{\text{odd}}$ and $\upsilon ={\upsilon }^{\text{even}}{\upsilon }^{\text{odd}}$.

We now consider the case in which $\pi$ is odd, which implies that $k$ is also odd. We let $\tau$ be an arbitrary transposition of ${\upsilon }_k^{-}$, and we define ${\upsilon }_k^{\prime }={\upsilon }_k^{-}\tau$ as the involution obtained by removing $\tau$ from ${\upsilon }_k^{-}$ (observe that $\tau$ is its own inverse), so that $a_2({\sigma }_k^{-})=a_2({\upsilon }_k^{-})-1=a_2({\upsilon }_k^{\prime })$. We let ${\sigma }^{\text{odd}}={\sigma }_1^{-}{\sigma }_2^{+}{\sigma }_3^{-}{\sigma }_4^{+}{\sigma }_5^{-}\mathrm{\dots }{\sigma }_{k-1}^{+}{\sigma }_k^{-}$ and ${\upsilon }^{\text{odd}}={\upsilon }_1^{-}{\upsilon }_2^{+}{\upsilon }_3^{-}{\upsilon }_4^{+}{\upsilon }_5^{-}\mathrm{\dots }{\upsilon }_{k-1}^{+}{\upsilon }_k^{\prime }$ (notice the alternating superscripts). The claim follows by choosing $\sigma ={\sigma }^{\text{even}}{\sigma }^{\text{odd}}$, $\upsilon ={\upsilon }^{\text{even}}{\upsilon }^{\text{odd}}$, and $\tau$ as defined above. $◀$

We can finally show how the elements in $R$ can be sorted, i.e., permuted according to ${\pi }_R^{-1}$. We start with a simplification: we assume w.l.o.g. that if ${\pi }_R$ is odd, then $m$ is even. Indeed, the case in which ${\pi }_R$ is odd and $m$ is odd can be avoided by noticing that, whenever this happens, $n$ must be even since otherwise the matrix would not be sortable (see Remark 1). Hence, we can reduce to the case in which ${\pi }_R$ is even by rotating $R$.

We proceed differently depending on the parity of ${\pi }_R$. If ${\pi }_R$ is even, we use Lemma 10 to write ${\pi }_R^{-1}$ as the product $\sigma \upsilon$ of two involutions $\sigma ,\upsilon$ with $a_2(\sigma )=a_2(\upsilon )$. Then we execute procedure SwapPairs twice: the first call applies $\sigma$ to $R$ and uses $d=\text{U}$, while the second applies $\upsilon$ to the resulting configuration and uses $d=\text{D}$. Invoking Lemma 8 twice shows that all rotations caused to the column bodies cancel out, while the elements originally in $R$ get permuted according to ${\pi }_R^{-1}=\sigma \upsilon$, i.e., they end up in the sorted configuration.

The only remaining case is the one in which ${\pi }_R$ is odd and $m$ is even. In this case, we use Lemma 10 to write ${\pi }_R^{-1}$ as the product $\sigma \upsilon \tau$ of two involutions $\sigma ,\upsilon$ with $a_2(\sigma )=a_2(\upsilon )$, and a transposition $\tau$. We call procedure SwapPairs five times. The first two calls apply involutions $\sigma$ and $\upsilon$ to $R$, in this order, with $d=\text{U}$ and $d=\text{D}$ respectively. Using Lemma 8 twice, we have that the combined effect of these two calls to SwapPairs leaves the positions of the elements not in $R$ unaffected. The third call swaps the elements involved in the transposition $\tau$, while causing a circular shift in body of $C_1$ (the direction of such shift is not important). Since $m$ is even, the number of elements in the body of $C_1$ is odd, and the permutation ${\pi }_1$ describing their circular shift is even, hence it can be written as the product ${\sigma }_1{\tau }_1$ of two involutions ${\sigma }_1{\tau }_1$ with the same number of transpositions. Since we can equivalently consider the transposed version $A^T$ of matrix $A$, we use the fourth and fifth calls to SwapPairs to apply ${\sigma }_1$ and ${\tau }_1$, in this order, to the first row of $A^T$, i.e., to column $C_1$ of $A$. By using opposite values of $d$ in these two final calls, we ensure any side effects introduced by the fourth call are undone by the fifth and last call. An example is provided in Figure 8. The above discussion is summarized in the following lemma.

Algorithm 5 shows the final pseudocode for solving the Torus Puzzle when $m\le n$ (which can be assumed w.l.o.g.), where lines from 6 onward handle sorting $R$ as described above.
The main result of this paper follows from combining Corollary 5 and Lemmas 6, 7, and 11.