Sergey Kitaev 1 Abstract On shortening universal words for multi-dimensional permutations Abstract. A universal word (u-word) for d -dimensional permutations of length n is a 2-dimensional word with d-1 rows, any size n window of which is order-isomorphic to exactly one permutation of length n , and all permutations of length n are covered. It is known that u-words (in fact, even u-cycles, a stronger claim) for d -dimensional permutations exist. In this paper, we use the idea of incomparable elements to prove that u-words of length (n!)^{d-1}+n-1-i(n-1) , for d\geq 2 and 0\leq i\leq\frac{2^{d-1}}{n-1}\left[(1+(n-1)!)^{d-1}-\left(1+\frac{(n-1)!}{2}\right)^{d-1}\right], for d -dimensional permutations of length n exist, which generalizes the respective result of Kitaev, Potapov and Vajnovszki for “usual” permutations ( d=2 ). Keywords: universal word; u-word; combinatorial generation; multi-dimensional permutation AMS Subject Classifications: 05A05 1 Introduction There is a long line of research in the literature dedicated to the studies of universal objects of various types, in particular, the notion of a universal cycle ( u-cycle ) for combinatorial structures, generalizing the notion of a de Bruijn sequence , was introduced in [ 6 ] and has been studied extensively for various objects. Considering the linear (i.e., non-cyclic) version of a universal cycle, we arrive to the notion of a universal word ( u-word ), also appearing in the literature in various places, e.g. in [ 13 ] . There are several ways to define the notion of a multi-dimensional permutation, and the visual motivation for the term “multi-dimensional” in one of the definitions is depicted, for example, in [ 18 , Fig. 2] . Following the definition in [ 1 ] , the authors of this paper [ 14 ] , using a greedy algorithm and arguing that the typical graph theoretical approach is not (easily) applicable, generalized the results in [ 6 , 9 , 11 ] by establishing the existence of u-cycles for d -permutations, from which it trivially follows that u-words for d -dimensional permutations exist. The main goal of this paper is to generalize the results in [ 13 ] by showing how incomparable elements can be used to shorten u-words for d -dimensional permutations. We will prove the following theorem that generalizes the respective result in [ 13 ] (given by substituting d=2 ). Theorem 1.1 . U-words of length (n!)^{d-1}+n-1-i(n-1) , for d\geq 1 and 0\leq i\leq\frac{2^{d-1}}{n-1}\left[(1+(n-1)!)^{d-1}-\left(1+\frac{(n-1)!}{2}\right)^{d-1}\right], for d -dimensional permutations of length n exist. While the steps of the proof of Theorem 1.1 are similar to those in [ 13 ] to prove the respective result, there are several obstacles that we need to overcome to be able to produce results for d dimensions, in particular, the notion of twin permutations needs to be defined properly. As it is mentioned in [ 14 ] , extending results on universal objects for “usual” 2-dimensional permutations to d -dimensional analogues is not possible in a generic way such as taking products of universal cycles discussed in [ 7 ] . Our work is related to a broader area of research on universal words (of combinatorial objects other than permutations) and shortenings of them, e.g. [ 5 , 10 ] for u-p-words/cycles, [ 4 ] for shortening of u-cycles for word-patterns and set partitions, and [ 2 ] for 2-dimensional u-p-words/cycles. The paper is organized as follows. In Section 2 we give all necessary definitions and in Section 3 we prove Theorem 1.1 . Concluding remarks are provided in Section 4 . 2 Preliminaries 2.1 d -dimensional permutations Our introduction of multi-dimensional permutations is largely inspired by the corresponding definitions in [ 3 , 14 ] . Consider a permutation \pi=\pi_{1}\pi_{2}\dots\pi_{n} of length n , that is, an element of the symmetric group S_{n} . Throughout this paper, we use one-line notation for \pi , but recall that its two-line form is given by {\footnotesize\pi=\left(\begin{array}[]{cccc}1&2&\dots&n\\ \pi_{1}&\pi_{2}&\dots&\pi_{n}\end{array}\right).} A d -dimensional permutation of length n , or d -dimensional n -permutation , is defined as an ordered (d-1) -tuple (\pi^{2},\pi^{3},\dots,\pi^{d}) where each \pi^{i}=\pi^{i}_{1}\pi^{i}_{2}\dots\pi^{i}_{n}\in S_{n} for i=2,\dots,d . For instance, the triple (321,123,231) is a 4-dimensional permutation of length 3. We denote by S^{d}_{n} the set of all d -dimensional permutations of length n . Note that S^{2}_{n}=S_{n} , so ordinary permutations are naturally viewed as 2-dimensional. We extend the two-line notation to a d -line notation . Specifically, if we define \pi^{1}=\pi^{1}_{1}\pi^{1}_{2}\ldots\pi^{1}_{n}=12\dots n , then a d -dimensional permutation \Pi=(\pi^{2},\pi^{3},\dots,\pi^{d}) can be represented as a d\times n matrix: \Pi=\left(\begin{array}[]{cccc}\pi^{1}_{1}&\pi^{1}_{2}&\dots&\pi^{1}_{n}\\ \pi^{2}_{1}&\pi^{2}_{2}&\dots&\pi^{2}_{n}\\ \pi^{3}_{1}&\pi^{3}_{2}&\dots&\pi^{3}_{n}\\ \vdots&&\dots&\vdots\\ \pi^{d}_{1}&\pi^{d}_{2}&\dots&\pi^{d}_{n}\end{array}\right). Alternatively, we may write this compactly as \Pi=\left\{\pi^{i}_{j}\right\}_{\begin{subarray}{c}1\leq i\leq d\\ 1\leq j\leq n\end{subarray}}. By analogy with two-line notation, we interpret the columns of the matrix as the elements of \Pi , denoted \Pi_{1},\Pi_{2},\dots,\Pi_{n} , so that \Pi=\Pi_{1}\Pi_{2}\dots\Pi_{n},\quad\text{where }\Pi_{j}=(\pi^{1}_{j},\pi^{2}_{j},\dots,\pi^{d}_{j})^{T}=(j,\pi^{2}_{j},\pi^{3}_{j},\dots,\pi^{d}_{j})^{T}. As a concrete example, let \Pi=(\pi^{2},\pi^{3})\in S^{3}_{5} , where \pi^{2}=21534 and \pi^{3}=41253 . Then: {\footnotesize\Pi=\left(\begin{array}[]{ccccc}1&2&3&4&5\\ 2&1&5&3&4\\ 4&1&2&5&3\end{array}\right).} The corresponding elements of \Pi are then: \Pi_{1}=(1,2,4)^{T},\quad\Pi_{2}=(2,1,1)^{T},\quad\Pi_{3}=(3,5,2)^{T},\quad\Pi_{4}=(4,3,5)^{T},\quad\Pi_{5}=(5,4,3)^{T}. For a (2-dimensional) permutation, or word, \pi , the reduced form of \pi , denoted \red(\pi) , is obtained by replacing the i -th smallest element in \pi by i . For example, \red(5294)=3142 . Any i consecutive elements of a word or permutation w form a factor of w . If u is a factor of w , we also say that w covers \red(u) . Let \pi be a 2-dimensional permutation of \{1,\ldots,n\} and x an element of \{1,\ldots,n\} . For x1 , we let x^{-} denote an element y such that x-10 , if i of its rows are of the form x_{1}x_{2}\ldots x_{n} with |x_{n}-x_{1}|=1 and the remaining rows are monotone (that is, either increasing, 12\ldots n , or decreasing, n(n-1)\ldots 1 ). To ensure unambiguity of the definition, we assume that n\geq 3 , but in either case, our definition generalizes the notion of twins in [ 13 ] . For example, the 5-dimensional 4-permutation \left(\begin{array}[]{cccc}4&3&2&1\\ 2&1&4&3\\ 1&4&3&2\\ 1&2&3&4\end{array}\right) is of type 2, where the top and bottom rows are monotone. If a permutation is not of type i for some i>0 , we say it is of type 0 . Two distinct d -dimensional n -permutations are i -twins if both of them are of type i , the monotone rows in them match each other (in position and type) and the permutations belong to the same cluster (i.e. both permutations have the same signature, the reduced forms of the leftmost n-1 columns). For example, \left(\begin{array}[]{ccc}3&2&1\\ 2&1&3\\ 1&3&2\\ 1&2&3\end{array}\right) and \left(\begin{array}[]{ccc}3&2&1\\ 2&1&3\\ 2&3&1\\ 1&2&3\end{array}\right) , as well as \left(\begin{array}[]{ccc}1&3&2\\ 1&3&2\end{array}\right) , \left(\begin{array}[]{ccc}1&3&2\\ 2&3&1\end{array}\right) , \left(\begin{array}[]{ccc}2&3&1\\ 1&3&2\end{array}\right) and \left(\begin{array}[]{ccc}2&3&1\\ 2&3&1\end{array}\right) , are 2 -twins. For another example, \left(\begin{array}[]{ccc}1&2&3\\ 1&3&2\end{array}\right) and \left(\begin{array}[]{ccc}1&2&3\\ 2&3&1\end{array}\right) are 1-twins. Finally, examples of (4-dimensional) 3-twins are \left(\begin{array}[]{cccc}3&1&2&4\\ 2&4&1&3\\ 2&3&4&1\end{array}\right) and \left(\begin{array}[]{cccc}4&1&2&3\\ 3&4&1&2\\ 1&3&4&2\end{array}\right) . Note that the same cluster can have more than one class of i -twins for a fixed i , where an i -twin class is an equivalence class under the equivalence relation of being i -twins. However, while each cluster has one (d-1) -twin class (see Lemma 3.1 ), for n\geq 4 some clusters do not have an i -twin class for some values of i\neq d-1 . Also note that by definition, any i -twin class is contained within a cluster. We invite the Reader to verify the statements of the following results in Figure 3 , the largest clustered graph of overlapping permutations that is feasible to draw in full in this paper. Lemma 3.1 . Each cluster contains exactly 2^{d-1} (d-1) -twins within one (d-1) -twin class. Moreover, for a permutation of type i>0 , the size of its i -twin class is 2^{i} . Proof. For the first claim, let the signature of a cluster be “ S=\left\{s^{j}_{m}\right\}_{\begin{subarray}{l}1\leq j\leq d\\ 1\leq m\leq n-1\end{subarray}} ”. The only possibilities to create (d-1) -twins are to adjoin, independently in each row j , 2\leq j\leq d , (s^{j}_{1})^{+} or (s^{j}_{1})^{-} at the end of s^{j}_{1}\ldots s^{j}_{n-1} , which results in 2^{d-1} options. The second claim follows from essentially the same arguments keeping in mind that the monotone rows are fixed (so that we cannot have i -twins with different sets/placements of monotone rows).∎ Parallel edges between two clusters are multiple edges oriented in the same way. Lemma 3.2 . For i>0 , an i -twin class I in cluster X contributes 2^{i} parallel edges from X to some cluster Y , and there are no other edges from X to Y . Also, if there are k (disjoint) i -twin classes I_{1} , I_{2},\ldots,I_{k} in cluster X then there are distinct clusters Z_{1} , Z_{2},\ldots,Z_{k} , each having i -twin classes with 2^{i} parallel edges from Z_{j} to X , j=1,2,\ldots,k . Proof. By definition, all i -twins in the set I have the same reduced form of the n-1 rightmost columns, since the leftmost and rightmost entries have the same relative order to the middle n-2 entries. Hence, each i -twin contributes an edge oriented towards the same cluster, say Y . By Lemma 3.1 , there are 2^{i} i -twins which completes the proof of the first claim, because edges (equivalently, d -dimensional n -permutations) starting in the same cluster and ending in the same cluster have, within each row, the same relative ordering of the first n-1 elements and the same relative ordering of the last n-1 elements, which determines the relative ordering of all pairs of elements except for the first and last. Now, assume, w.l.o.g., that the i non-monotone rows in a class I_{j} are the top rows, and for m=1,\ldots,i , the m -th row in an i -twin is s^{m}_{1}\ldots s^{m}_{n} . There are 2^{i} parallel edges coming to X from the cluster Z_{j} having i -twins with the top i rows s^{m}_{0}s^{m}_{1}\ldots s^{m}_{n-1} , m=1,\ldots,i , where s^{m}_{0}\in\{(s^{m}_{n-1})^{+},(s^{m}_{n-1})^{-}\} , and the monotone rows matching the respective rows in the class I_{j} . Note that \red(s^{m}_{0}s^{m}_{1}\ldots s^{m}_{n-1}) is the same regardless of which i -twin in I_{j} was chosen to define s^{m}_{1}\ldots s^{m}_{n} . Finally, the only way I_{a}\neq I_{b} can occur within the same cluster X is if the monotone rows differ. In such a case, Z_{a}\neq Z_{b} necessarily follows. ∎ Lemma 3.3 . The clustered graph of overlapping permutations can be partitioned into a disjoint union of cycles of length n-1 formed by 2^{d-1} parallel edges between clusters (any other edges are to be ignored). Also, for each i , 1\leq i\leq d-1 , there are \frac{1}{n-1}{d-1\choose i}((n-1)!)^{i}2^{d-i-1} (1) disjoint cycles of length n-1 formed by 2^{i} parallel edges between clusters. Proof. First note that from Lemma 3.1 (first part) and Lemma 3.2 , we can partition the clustered graph of overlapping permutations into a disjoint union of cycles formed by 2^{d-1} parallel edges, and there are disjoint cycles of 2^{i} parallel edges formed by i -twins. Next, observe that each cycle formed by 2^{i} parallel edges must be of length n-1 . This follows from the observation that if there are 2^{i} parallel edges from a cluster X to a cluster Y then the signature (of length n-1 ) of Y restricted to non-monotone rows is the cyclic shift of the signature of X restricted to non-monotone rows one position to the right, while the monotone rows stay the same. Hence, only n-1 distinct shifts will take place. Finally, for computing the number of disjoint cycles formed by 2^{i} parallel edges, we first note that there are {d-1\choose i}((n-1)!)^{i}2^{d-1-i} possible ways to choose an i -twin class to start such a cycle, where {d-1\choose i}2^{d-1-i} is the number of ways to select monotone rows and their types, and ((n-1)!)^{i} ways is the number of ways to pick the signature of non-monotone rows. However, because each cycle is of length n-1 we need to divide by this number (otherwise, we count each cycle n-1 times since it can begin in any permutation of the cycle). ∎ To complete our proof of Theorem 1.1 we follow the following observations. Note that each edge in the clustered graph of overlapping permutations corresponds to a d -dimensional permutation. Since u-cycles for d -dimensional permutations exist [ 14 ] , the clustered graph must contain an Eulerian cycle. Consider an Eulerian path in this graph, which gives a u-word of length (n!)^{d-1}+n-1 . For any fixed i , 1\leq i\leq d-1 , pick a cycle of length n-1 formed by 2^{i} parallel edges (that exists by Lemma 3.2 ). Decide on a row j of each vertex of the cycle to make the first element be equal to the last element, that is, to be of the form s_{1}s_{2}\ldots s_{n-1}s_{1} . Using a repeated element in each row j effectively removes n-1 edges from the cycle and reduces the number of permutations in the graph by n-1 . The graph remains balanced and connected and hence an Eulerian cycle still exists that corresponds to a u-word of length (n!)^{d-1}+n-1-(n-1) . We can now chose another (arbitrary!) cycle to remove that would result in a u-word of length (n!)^{d-1}+n-1-2(n-1) . And so on. The maximum compression is achieved by removing all multiple edges – one from each set of parallel edges and n-1 from each cycle – where, for (n-1) -cycles comprising 2^{i} parallel edges, this requires “removing a cycle” 2^{i}-1 times (leaving 1 edge per set), resulting in the total number of applications being calculated by multiplying the formula in Lemma 3.3 by 2^{i}-1 and summing over all i : \frac{2^{d-1}}{n-1}\sum_{i=1}^{d-1}{d-1\choose i}((n-1)!)^{i}(1-2^{-i})=\frac{2^{d-1}}{n-1}\left[(1+(n-1)!)^{d-1}-\left(1+\frac{(n-1)!}{2}\right)^{d-1}\right]. \left(\begin{array}[]{ccc}1&2&3\\ 1&2&3\end{array}\right) \left(\begin{array}[]{ccc}1&2&1\\ 1&2&3\end{array}\right) \left(\begin{array}[]{ccc}1&2&3\\ 1&2&1\end{array}\right) \left(\begin{array}[]{ccc}1&2&1\\ 1&2&1\end{array}\right) “ \left(\begin{array}[]{cc}1&2\\ 1&2\end{array}\right) ” \left(\begin{array}[]{ccc}2&1&2\\ 2&1&2\end{array}\right) \left(\begin{array}[]{ccc}3&2&1\\ 2&1&2\end{array}\right) \left(\begin{array}[]{ccc}2&1&2\\ 3&2&1\end{array}\right) \left(\begin{array}[]{ccc}3&2&1\\ 3&2&1\end{array}\right) “ \left(\begin{array}[]{cc}2&1\\ 2&1\end{array}\right) ” \left(\begin{array}[]{ccc}1&2&3\\ 2&1&2\end{array}\right) \left(\begin{array}[]{ccc}1&2&1\\ 2&1&2\end{array}\right) \left(\begin{array}[]{ccc}1&2&3\\ 3&2&1\end{array}\right) \left(\begin{array}[]{ccc}1&2&1\\ 3&2&1\end{array}\right) “ \left(\begin{array}[]{cc}1&2\\ 2&1\end{array}\right) ” \left(\begin{array}[]{ccc}2&1&2\\ 1&2&3\end{array}\right) \left(\begin{array}[]{ccc}3&2&1\\ 1&2&3\end{array}\right) \left(\begin{array}[]{ccc}2&1&2\\ 1&2&1\end{array}\right) \left(\begin{array}[]{ccc}3&2&1\\ 1&2&1\end{array}\right) “ \left(\begin{array}[]{cc}2&1\\ 1&2\end{array}\right) ” Figure 4: The clustered graph giving the maximum compression possibility using incomparable elements at distance 2 for 3-dimensional 3-permutations Figure 4 shows the graph corresponding to the maximum compression possibility using incomparable elements at distance 2 for 3-dimensional 3-permutations. A particular Eulerian path in the graph goes as follows: \left(\begin{array}[]{ccc}1&2&3\\ 1&2&3\end{array}\right) \rightarrow \left(\begin{array}[]{ccc}1&2&1\\ 1&2&1\end{array}\right) \rightarrow \left(\begin{array}[]{ccc}3&2&1\\ 3&2&1\end{array}\right) \rightarrow \left(\begin{array}[]{ccc}3&2&1\\ 2&1&2\end{array}\right) \rightarrow \left(\begin{array}[]{ccc}3&2&1\\ 1&2&3\end{array}\right) \rightarrow \left(\begin{array}[]{ccc}2&1&2\\ 1&2&1\end{array}\right) \rightarrow \left(\begin{array}[]{ccc}1&2&3\\ 3&2&1\end{array}\right) \rightarrow \left(\begin{array}[]{ccc}1&2&3\\ 2&1&2\end{array}\right) \rightarrow \left(\begin{array}[]{ccc}1&2&1\\ 1&2&3\end{array}\right) \rightarrow \left(\begin{array}[]{ccc}2&1&2\\ 1&2&3\end{array}\right) \rightarrow \left(\begin{array}[]{ccc}1&2&3\\ 1&2&1\end{array}\right) \rightarrow \left(\begin{array}[]{ccc}1&2&1\\ 3&2&1\end{array}\right) \rightarrow \left(\begin{array}[]{ccc}2&1&2\\ 3&2&1\end{array}\right) \rightarrow \left(\begin{array}[]{ccc}1&2&1\\ 2&1&2\end{array}\right) \rightarrow \left(\begin{array}[]{ccc}3&2&1\\ 1&2&1\end{array}\right) \rightarrow \left(\begin{array}[]{ccc}2&1&2\\ 2&1&2\end{array}\right) . This path can be transformed into a u-word of length 18 for 3 -dimensional 3 -permutations, as given below, using the following general description. Consider the (k+1) -st step A\rightarrow B , involving the matrices A=\left\{a_{i,j}\right\}_{\begin{subarray}{c}1\leq i\leq d-1\\ 1\leq j\leq n\end{subarray}} and B=\left\{b_{i,j}\right\}_{\begin{subarray}{c}1\leq i\leq d-1\\ 1\leq j\leq n\end{subarray}} in an Eulerian path, and assume that the matrix X_{k}=\left\{x_{i,j}\right\}_{\begin{subarray}{c}1\leq i\leq d-1\\ 1\leq j\leq k+n\end{subarray}} has already been constructed (with X_{0} being the initial matrix in the Eulerian path). Note that \red(x_{i,k+1}x_{i,k+2}\ldots x_{i,k+n})=a_{i,1}a_{i,2}\ldots a_{i,n} . To construct X_{k+1} , we proceed independently in each row x_{i,1}x_{i,2}\ldots x_{i,n+k} , 1\leq i\leq d-1 , where \max_{i} denotes the largest element in row i of X_{k} : • If possible, let x_{i,n+k+1} be the smallest option in \{x_{i,1},\ldots,x_{i,n+k},1+\max_{i}\} such that \red(x_{i,k+2}x_{i,k+3}\ldots x_{i,k+n+1})=b_{i,1}b_{i,2}\ldots b_{i,n} , and do not change the other elements in row i of X_{k} . This includes the case when b_{i,n}=n . • Otherwise, we have b_{i,n}