In a totally ordered set the notion of sorting a finite sequence is defined through the existence of a suitable permutation of the sequence's indices. A drawback of this definition is that it only implicitly expresses how the elements of a sequence are related to those of its sorted counterpart. To alleviate this situation we prove a simple formula that explicitly describes how the kth element of a sorted sequence can be computed from the elements of the original sequence. As this formula relies only on the minimum and maximum operations we use it to define the notion of sorting for lattices. A major di erence of sorting in lattices is that it does not guarantee that sequence elements are only rearranged. To the contrary, sorting in general lattices may introduce new values into a sequence or completely remove values from it. We can show, however, that other fundamental properties that are associated with sorting are preserved. Furthermore, we address the problem that the direct application of our explicit formula for sorting leads to an algorithm with exponential complexity. We present therefore for distributive lattices a recursive formulation to compute the sort of a sequence. This alternative formulation, which is inspired by the identity nk = nk 11 + nk1 that underlies Pascal's triangle, allows for sorting in lattices with quadratic complexity and is in fact a generalization of insertion sort for lattices.
In this paper we present the results of two preprints [1,2] where we outline basic principles of a theory of sorting in lattices.
Sorting a sequence in a total order (X; ) is typically defined through the existence of a suitable permutation (cf. [3, p. 4]). There exists for each sequence x of length n in a totally ordered set a permutation ' of [1; n] = f1; : : : ; ng such that x ' is a increasing sequence. If x is injective, then ' is uniquely determined, and vice versa. However, regardless whether there is exactly one permutation, the rearrangement x" = x ' is uniquely determined and we thus refer to it as the increasing sort of x.
Sorting defines a map x 7! x" from Xn to the subset of increasing sequences. This
map has several interesting properties. First of all, it is idempotent
and thus a projection. Secondly, for each permutation
of [1; n] we have
x" " = x"
(
The definition of sorting through the existence of a suitable permutation only provides an implicit relationship between the elements of x and x". However, sometimes we prefer explicit relationships.
If, for example, someone asked whether there is for the numbers a and b and the exponent n a general relationship between the value (a + b)n and the powers an and bn, then the (obvious) answer is that this relationship is captured by the Binomial Theorem n (a + b)n = X n! an kbk
k=0 k which also shows that other powers of a and b are involved.
When looking for an explicit relationship between the elements of x and the
elements of its increasingly sorted counterpart x" = x1"; : : : ; xn" , one can provide an easy
answer for the first and last elements of x". In fact, we know that x1" is the least element
of fx1; : : : ; xng
whereas xn" is the greatest element of x
x1" = x1 ^ : : : ^ xn =
xn" = x1 _ : : : _ xn =
n
^ xk;
k=1
n
_ xk:
k=1
(
In Section 2 we prove Identity (7) that explicitly states how the elements x1"; : : : ; xn" are related to x1; : : : ; xn. This formula only uses the minimum and maximum operations on finite sets. Based on this observation, we define in Section 3 the notion of sorting of sequences in a lattice through simply replacing the minimum/maximum operations by the infimum/supremum operations, respectively. We also show that sorting in lattices in general not just reorders the elements of a sequence but really changes them. However, we are able to prove that our definition satisfies various properties that are associated with sorting.
The direct application of Identity (7) leads to an algorithm with exponential complexity (cf. Section 4). In order to address this problem, we prove the recursive Identity (19) for the case of bounded distributive lattices. This identity is closely related to the well-known fact that the binomial coe cient
n! can be e ciently computed through the recursion n! k k = =
n! k! (n n k 1 1! + k)! n k 1! which underlies Pascal’s triangle.
Furthermore, we prove that a lattice, in which the recursive Identity (19) holds, is necessarily distributive. The main advantage of our recursive identity is that it allows for an algorithm for sorting in lattices with quadratic complexity. In fact, this algorithm is a generalization of insertion sort for lattices (cf. Section 5).
A formula for sorting Let (X; ) be a totally ordered set, then each nonempty finite subset A of X contains a least and a greatest element [4, R. 6.5]. We also speak of the minimum and maximum of A and refer to these special elements as V A and W A, respectively. The following inequalities hold for all a 2 A ^ A a _ A For A = fx; yg we use the notation x ^ y and x _ y to denote the minimum and maximum of x and y, respectively.
The main results of this paper depend on a particular family of finite sets. Definition 1. For k 2 [1; n] we denote with N nk B nA [1; n] jAj = ko the set of subsets of [1; n] that contain exactly k elements. The set N nk consists of nk elements. Proposition 1. Let (x1; : : : ; xn) be a sequence in a totally ordered set, then the following identity holds for the elements of the sequence x1"; : : : ; xn" xkM =
^
1 i1<:::<ik n
xi1 _ : : : _ xik
We see then that x1M is the least element of x and thus equals x1" (cf. Identity (
Lemma 1. If x is a sequence of length n in a totally ordered set (X; ), then xM is a increasing sequence.
Before we prove Proposition 1 we introduce an abbreviation for the right hand side of Identity (7). For a sequence x of length n we define for 1 k n xk" = ^
_ xi: We remark that because (X; ) is a total order, we know that each element of xM is also an element of x. When applying Identity (8) it is sometimes convenient to use a slightly more explicit way to write the elements of xM. (6) (7) (8) (9) (10)
k < n and I be an arbitrary subset of [1; n] with k + 1 elements. If J is a subset of I with k elements, then we have by Inequality (6) and J I
xkM = x M k ^
_ xl L2N(nk) l2L _ x j j2J _ xi: i2I ^
_ xi = xkM+1;
I2N(k+n1) i2I which shows that xM is increasing.
Note that in the proof of Lemma 1 we have only used the fact that the minimum of a set is a lower bound for all elements of that set (cf. Inequality (6)).
Proof (Proposition 1). We will show that for each k with 1 k x" k xkM hold. Let ' be a permutation of [1; n] with n both xkM xk" and and let J
[1; n] be the subset for which holds. From the fact that J contains exactly k elements we conclude x" = x ' J = ' ([1; k])
_ j2' 1(B) xkM = xm": tu (11) (12) (13) tu xkM = ^
_ xi i2[1;k] = = = xk" x" i _ x" ' 1( j) by Inequality (6) by Identity (11) by Identity (12) by monotonicity of x".
Conversely, we conclude from the fact that (X; ) is a total order and Identity (11) that there exists a subset B of [1; n] with exactly k elements such that xkM = ^ _ xi = _ xi =
_ x" ' 1(i) = greatest element of ' 1(B). We have, thus, x"j = xm" where m = _(' 1(B)) is the However, since W(' 1(B)) is a subset of [1; n] that contains exactly k elements we obtain k imply xk" m. Since x" is increasing we conclude xk" xkM, which completes the proof.
xm". This inequality and Identity (13)
Let (X; ) be a partially ordered set that is also a lattice (X; ^; _), then for each x; y 2 X there exists the infimum x ^ y and the supremum x _ y (cf. [5, Chapter 3]). These operations are commutative and associative and they satisfy for all x; y 2 X the socalled absorption properties x _ (x ^ y) = x and x ^ (x _ y) = x. If (X; ) is a total order, then ^ and _ are the minimum and maximum operations of Section 2.
In a lattice, the infimum and supremum exist for every finite subset A and are denoted by V A and W A, respectively (cf. [5, p. 49]). We therefore know that for a sequence x of length n the value xkM = ^
_ xi Definition 2. If x is a sequence of length n in a lattice (X; ^; _), then we refer to xM as defined by Identity (8) as the increasing sort of x with respect to the lattice (X; ^; _). Before we start to investigate which properties that are traditionally associated with sorting are maintained by our definition we want to point out a major di erence: In a lattice the value xkM might be di erent from the original values x1; : : : ; xn. The reason for this is the following: While in a lattice the inequalities x ^ y x; y x _ y generally hold, there might be also the case that the set fx ^ y; x _ yg is di erent from the set fx; yg.
Examples of sorting in lattices As a first example we consider the finite set X = fx; y; zg. Figure 1 shows the lattice of all subsets of X. Let x be the sequence a = fxg; fyg; fzg , then aM = ;; ;; X . Thus, aM is a increasing sequence that consists of elements that are completely di erent from those of a.
{x,y} {x}
{x,y,z} {x,z} {y} ∅
As a second example we consider the lattice (N; gcd; lcm) where gcd(x; y) and lcm(x; y) denote the greatest common divisor and least common multiple of x and y, respectively. The associated partial order of this lattices is defined by divisibility of natural numbers. Table 1 shows some examples of our definition of sorting for di erent sequences in (N; gcd; lcm). Again we see that sorting in a lattice may change the elements in a sequence.
Elementary properties of sorting in lattices The following lemma states that xM is indeed a increasing sequence with respect to the partial order (X; ) of the lattice (X; ^; _). (X; ), then Identity (8) defines a increasing sequence xM.
Lemma 2. If x is a finite sequence in a lattice (X; ^; _) with associated partial order Proof. In order to prove this lemma we can proceed exactly as in the proof of Lemma 1 where (X; ) is a total order. As remarked on Page 2, we have used only the fact that V A is a lower bound of A which by definition also holds for lattices.
A simple consequence of Lemma 2 is the following Lemma 3 which states that sorting in lattices respects lower and upper bounds of the original sequence. order (X; ). If for 1 i n holds a xi b, then a Lemma 3. Let x be a sequence of length n in a lattice (X; ^; _) with associated partial b holds as well. x M i Proof. From Identity (10) follows that xnM is the supremum of the elements x1; : : : ; xn.
b. Lemma 2 ensures that xnM is the largest element of xM. Thus we b for 1 i
n. The case for the lower bound a is treated analogously.
The following lemma restates the idempotence of sorting for the case of lattices (cf. Iden)i = ^
_ A2N(nk) j2 (A) x j = ^
_ x j B2 (N(nk)) j2B
N nk = N nk and conclude have xi
M
M
Thus, we have xn
tity (
)M = xM holds.
Proof. We have for 1 (x (x )kM = k ^
n A2N(nk) i2A
_(x )kM = ^
_ x( j) = xkM: B2N(nk) j2B tu tu tu Lemma 4. If x is a finite sequence in a lattice (X; ^; _), then x M M = xM.
Proof. We know from Lemma 2 that xM is a increasing sequence in the partial order (X; ). Thus, the relation we can sort xM in the classical sense. From this follows by Identity (7) is a total order on the set nx1M; : : : ; xnMo
xM = xM " = x
M M : We can also show the invariance of sorting in lattices under permutations (cf. IdenLemma 5. If x is a sequence of length n in a lattice and a permutation of [1; n], then
Recursive sorting in lattices The definition of xM through Identity (8) is nice and succinct, but it is also quite impractical to use in computations. Table 2 shows simple performance measurements (conducted on a notebook computer) for computing (1; : : : ; n)M in (N; gcd; lcm). The reason for this dramatic slowdown is of course the exponential complexity inherent in Identity (8): In order to compute xM from x it is necessary to consider all 2n 1 nonempty subsets of [1; n]. For the remainder of this paper we assume that (X; ^; _; ?; >) is a bounded lattice. Here ? is the least element of X and the neutral element of join, that is, whereas > is the greatest element of X and the neutral element of meet, that is, 8x 2 X 8x 2 X:
We now introduce a notation that allows us to concisely refer to individual elements of both (x1; : : : ; xn)M and (x1; : : : ; xn 1)M. Here again, it is convenient to employ the notation for the binomial coe cient nk in the context of sorting in lattices. For a sequence x of length n we define for 0 m n 8 >>? xM mk B <>>>(x1; : : : ; xm)M(k) > > > > >:> k = 0 k 2 [1; m] k = m + 1 We know from Identity (8) that (x1; : : : ; xm)M(k) = ^ _ xi holds for 1 k
I2N(mk) i2I
k
n xM mk = ^
_ xi:
I2N(mk) i2I xM nk = xkM:
The main result of this section is Proposition 2, which states in Identity (19), how the kth element of (x1; : : : ; xn)M can be computed from (x1; : : : ; xn 1)M and xn by simply applying one join and one meet. The proof of Proposition 2 relies on the fact that the lattice under consideration is both bounded and distributive. of length n, then for 1 k
n holds Proposition 2. If (X; ^; _; ?; >) is a bounded distributive lattice and if x is a sequence x M nk = xM nk1 ^ x
M n 1 k 1 _ xn (19) Proof. For k = 1, we have x M n1 = n ^ xi i=1 0n 1 1 = BBBB^ B B
C
A xiCCCCC ^ xn
In other words, N nk can be represented as the following (disjoint) union N nk = N nk1
[ nB [ fng B 2 N nk 11 o :
x M nk = = = = = = ^
_ xi which completes the proof.
^ ^ ^ ^ ^ ^ ^ I2N(nk 11) i2I[fng I2N(nk 11) i2I[fng _ _ xi xi ^ 0 B BB_ xi _ xnCCCC B B 1 C
A 00 BBBB BB BB BB BB
^ BB BB@BB@I2N(nk 11) i2I A
C
C x M n 1 k 1 _ xn 1 C
C C _ xiCCCCC _ xnCCCC
C 1 C C C A by Identity (17) by Identity (20) by Identity (17) by associativity by distributivity by Identity (17) (20) tu The following Proposition 3 states that the converse of Proposition 2 also holds. Proposition 3. Let (X; ^; _; ?; >) be a bounded lattice which is not distributive. Then there exists a sequence x = (x1; x2; x3) in X such that Identity (19) is not satisfied. Proof. According to a standard result on distributive lattices [5, Theorem 4.7], a lattice is not distributive, if and only if it contains a sublattice which is isomorphic to either N5 or M3 (cf. Figure 2).
d M3 (21a) (21b) (21c) d b e a
c N5 b e c a From Identity (10) follows for the elements of xM = x1M; x2M; x3M
If X contains the sublattice N5, then we consider the sequence x = (c; d; b) and its subsequence (c; d). From Identity (21) then follows (c; d; b)M = (a; d; e) and (c; d)M = (a; e):
xM 32 = d xM 22 = e xM 21 = a:
xM 32 = xM 22 ^ x
M 21 _ x3 = e ^ (a _ b) = e ^ b = b instead of d.
If X contains the sublattice M3, then we consider the sequence x = (b; c; d) and its subsequence (b; c). From Identity (21) then follows (b; c; d)M = (a; e; e) and (b; c)M = (a; e):
x M 32 = e x M 22 = e x M 21 = a:
x M 32 = xM 2 2 ^ x
M 2 known fact known from sorting in a total order: If one knows that xn is greater or equal that the preceding elements x1; : : : ; xn 1 then sorting the sequence (x1; : : : ; xn) can be accomplished by sorting (x1; : : : ; xn 1) and simply appending xn. length n. If the condition xi xn holds for 1 i n
Lemma 6. Let (X; ^; _; ?; >) be a bounded distributive lattice and x be a sequence of x x M ni = xM n i 1
M nn = xn hold.
Proof. The first equation follows directly from the fact that xnM is the supremum of the values x1; : : : ; xn. Regarding the second equation, we know from Lemma 2 that if for 1 i n 1 the inequality xi
xn holds, then x M n 1 i
xn: x x M n 1 M n 1 i i _ xn = xn ^ xn = xM n i 1 tu general properties of meet and join then follows that This inequality is also valid for i = 0 because xM n01 = ? holds by Identity (16). From holds for 0 i n
x M ni = xM n i 1
M n 1
i 1 _ xn 5 Insertion sort in lattices Figure 3 graphically represents Identity (19) in a form that emphasizes its close relationship to Pascal’s triangle. Whenever an arrow & and and arrow . meet, the values are combined by a meet. In the case of an arrow &, however, first the value at the origin of the arrow is combined with the sequence value xn through a join.
Formula (22) outlines an algorithm that is based on Identity (19). The algorithm starts from x1 = (x1)M and successively computes (x1; : : : ; xi 1)M; xi 7! (x1; : : : ; xi 1; xi)M: (22) From Identity (19) follows that in step i exactly i joins and i meets must be performed.
n X 2 i = n(n + 1) 2 i=2 applications of join and meet. In other words, such an implementation has quadratic complexity. This algorithm can be considered as insertion sort [3, § 5.2.1] for lattices because one element at a time is added to an already “sorted” sequence. Table 3 shows some performance measurements for this algorithm in the bounded and distributive lattice (N; gcd; lcm; 1; 0).
sequence length 100 1000 10000 100000 time in s 0 0 3.4 420
These results show that sorting in lattices can now be applied to much larger sequences than those shown in Table 2 before the limitations of an algorithm with quadratic complexity become noticeable.
Proposition 1 states through Identity (7) a simple explicit relationship between the elements of a finite sequence in a totally ordered sets to its sorted counterpart.
A sorting algorithm that directly uses Identity (7) would have exponential complexity. Thus, Identity (7) appears not relevant for implementing computationally e cient algorithms. The reader should bear in mind, however, that this is also true for the Binomial Theorem. In fact, directly computing (x + y)n is normally more e cient than computing the expansion A more interesting aspect of Identity (7) is therefore that it allows to generalize the notion of sorting finite sequences to lattices. Compared to sorting in a totally ordered set, sorting in lattices is a more invasive procedure because it may change sequence elements. While this may be considered as a major drawback one should bear in mind that generalizations often lead to surprising properties. The real criterion for accepting a generalization is whether it provides new insights or has useful applications. With respect to sorting in lattices, the latter question has not been addressed in this paper and remains a topic of future research.
We are able to show that our definition of sorting in lattices maintains many properties that are associated with sorting. Another important results of this paper are Proposition 2, which proves Identity (19) for bounded distributive lattices, and Proposition 3, which shows that the distributivity is necessary for Identity (19) to hold. The remarkable points of Identity (19) are that it – exhibits a strong analogy between sorting and Pascal’s triangle, – allows to sort in lattices with quadratic complexity, and that it – is in fact a generalization of insertion sort for lattices.
I would like to thank the reviewers for their comments. I am also very grateful for the many corrections and valuable suggestions of my colleagues Jochen Burghardt and Hans Werner Pohl: Jochen Burghardt’s suggestion to investigate whether the distributivity in Proposition 2 is really necessary led to Proposition 3. Hans Werner Pohl pointed out the analogy of the algorithm in Equation 22 to insertion sort.