All lattices considered in this paper are finite and distributive. For very basic notation, definitions, and concepts we refer the reader to [4]; many basic definitions are also given at the start of Section 2.

Classical results of Birkhoff and Dilworth, which we review in more detail in Section 2, show that any finite distributive lattice L can be embedded, as a sublattice, into a product of chains. They further yield a one-to-one correspondence (Corollary 2.5) between the tight such embeddings and chain decompositions of the poset J(L) of non-zero irreducible elements of L.

Our main goal in this paper is to reverse the point of view of this correspondence: instead of cataloguing the various embeddings of a particular lattice L into products of chains, we catalogue the various sublattices of a given product ℘ of chains.

Starting with the product of a set of chains, J(℘) is the parallel sum of the chains we get from the chains of by removing their minimum elements. One main idea is that, for a tight sublattice L of ℘, J(L) is isomorphic to an extension of J(℘). See Figure 1 for an example. If we consider only tight sublattices of ℘, this is the whole picture: in Remark 4.4, we observe that L ↦ J(L) gives a one-to-one correspondence between the tight sublattices of ℘ and the spanned poset extensions of J(℘)–extensions with the same set of elements as J(℘).

But what if we consider non-tight embeddings/sublattices? One can see two examples of non-tight embeddings in the bottom half of Figure 2. As every lattice has a tight embedding into products of chains, non-tight embeddings are seldom considered. However, when we look to catalogue the sublattices of given product of chains, it is natural to consider them. In the paper [9], out of which this paper grew, we found it useful to consider non-tight sublattices of products of chains. We needed a characterisation of all sublattices of a product of chains.

In Section 3, we use a result of Rival [8] which characterises the sublattices of ℘, to construct, for each sublattice of ℘, a preorder (reflexive transitive relation) D_℘(L) which contains J(℘). In fact, D_℘(L) is a refinement of the poset that we get from J(℘) by appending a new zero and unit.

This preorder is an analogue of J(L) in the sense that our main theorem, Theorem 4.1 is an analogue of Theorem 2.1, representing L as the appropriatly defined lattice of ‘downsets’ of D_℘(L). Using this, we prove Corollary 4.2 in Section 4, and so acheive our main goal of cataloguing the sublattices of ℘, by giving a correspondence between them and the so-called spanned preorder extensions of . Results similar to those is this section can by found with a different presentation in the recent article [7] of Retakh and Saks.

In Section 5, we return to the point of view of embeddings of a given lattice, and extend Birkhoff’s classical correspondence between the tight embeddings of a lattice L into products of chains and the chain decompositions of J(L). Birkhoff’s correspondence is categorical, and so is our extension, extending the correspondence between morphisms, but we avoid talk of categories. We get, in Theorem 5.3, a one-to-one correspondence between embeddings of a lattice L into products of chains, and ‘pointed chain covers’ of an extension J^⋄(L) of J(L). Similar results can by found with a different presentation in the recent article [7].

In [5], Koh used a clever construction to show that any distributive lattice L can be represented as the lattice of maximal antichains of some poset P. We finish off, in Section 6, by showing that his construction arises naturally from our point of view, and extend it to determine, in Corollary 6.12, all posets P such that for a given L.

A lattice embedding e : L → L′ is a {0, 1}-embedding if it preserves the zero and unit elements: e(0_L) = 0_L′ and e(1_L) = 1_L′. It is tight if it is a {0, 1}-embedding and preserves covers: x ≺ y implies that e(x) ≺ e(y). An element x of a lattice L is join-irreducible if x = a ∨ b implies that x = a or x = b. Meet-irreducible elements are defined analogously. The set of non-zero join-irreducible elements of L is denoted J(L). It induces a subposet of L which is also denoted by J(L). For a subset S of a lattice L, we let ∨S = ∨_x∈S x be the join of the elements of S. We often write ∨_L S to specify that the join takes place in L. A subset S of a poset is a downset or ideal if x ∈ S and y ≤ x implies y ∈ S. The minimum downset containing an element x is denoted 〈x]. A chain C of length n in a poset P is subposet isomorphic to the linear order Z_n+1 on the n + 1 elements {0, 1, . . . , n}. A chain decomposition of a poset P is a partition of its elements into a family of chains C₁, . . . , C_d. For a family of disjoint chains, the product $\prod \mathcal{C}:={\prod }_{i=1}^d{C}_i$ consists of all d-tuples x = (x₁, . . . , x_d) where x_i ∈ C_i for each i ∈ [d]. It is ordered by x ≤ y if x_i ≤ y_i for each i.

In his famous representation theorem in [1], Birkhoff showed that where , for a poset P, is the family of downsets of P ordered by inclusion. Specifically, he showed the following.

Theorem 2.1.([1])

Let L be a finite distributive lattice. The map

is a lattice isomorphism. Its inverse is S ↦ → ∨_L S.

Observing that a downset in is join-irreducible if and only if it has a unique maximal element, one can easily show that is an isomorphism. Thus P ≅ Q if . This immediatly yields a one-to-one correspondence, L ↦ J(L), between finite distributive lattices and finite posets.

For a chain decomposition of a poset let be the family of chains we get from the chains in by adding a new minimum element to each. In [2], Dilworth proved the following embedding theorem.

Theorem 2.2.([2])

For any chain decompositionof a poset P the map S ↦ ∨_℘S is an embedding ofinto.

With Theorem 2.1, this immediately gives the following.

Corollary 2.3

For any decompositionof J(L) into chains, the map

is an embedding of L into.

In [6], Larson makes explicit a converse to Corollary 2.3, showing essentially the following.

Theorem 2.4.([6])

The embeddingsof Corollary 2.3 are tight, and for every tight embedding e there is a chain decompositionof J(L) such that.

It is a trivial observation that different chain decompositions of J(L) yield different embeddings of L into products of chains, so with Corollary 2.3, this yields the following correspondence.

Corollary 2.5

Let L be a finite distributive lattice. The mapis a one-to-one correspondence between the chain decompositions of J(L) and the tight embeddings of L into products of chains.

Recalling a result of Rival in the first subsection, we use it in the second subsection to construct the preorder D_℘(L) and the appropriate notion of a downset lattice. We then give an immediate restatement of Theorem 2.1 in terms of our new definitions. This will be a special case of our main theorem, which will be put off until the next section. In the third subsection, we look at some examples to try to give intuition to the construction. In the fourth subsection, we clean up some technical details of the construction.

3.1. Rival’s Theorem

An irreducible interval of a lattice L is the set [α, β] = {x ∈ L | α ≤ x ≤ β} for any join-irreducible element α of L and any meet-irreducible element β. For a set ℐ of irreducible intervals of L we let ∪ℐ = ∪_I∈ℐI. The set ℐ is closed if I ⊆ ∪ℐ implies I ∈ ℐ. The key to our results is the following theorem of Rival.

3.2. Setup and The Definition of D_℘(L)

For the rest of the paper ℘ is always a product of finite chains . We will denote the elements of a chain C_i by integers, so that α + 1 will denote the cover of an element α in C_i; but we still refer to the maximum element of C_i as 1_Ci. The subscript differentiates it from the element 1 that is occasionally used in examples to label the first or second element of a chain. We let 0 = (0_C1, . . . , 0_Cd) and 1 = (1_C1, . . . , 1_Cd) denote the zero and unit of ℘. When L is a sublattice of ℘, Theorem 3.1 yields a unique closed family ℐ_L such that L = ℘ ℐ_L. The join-irreducible elements of ℘ are clearly of the form

for i ∈ [d] and α ∈ C_i and the meet-irreducible elements are

for j ∈ [d] and β ∈ C_j. We generally use the notation α_i and β^j but add the parentheses when needed for clarity, in particular, we do this when α has or β has a subscript. The irreducible intervals of ℘ are exactly the intervals [α_i, β^j] for i, j ∈ [d], α ∈ C_i, and β ∈ C_j, where α ≤ β if i = j. Though an empty set is not technically an interval of a poset, it will be useful to consider the empty set [α_i, β_i], when α > β, as an irreducible interval of ℘.

Given and , let be the subposet of ℘ induced by J(℘) ∪ {0, 1}. Occasionally, in arguments, we will let (α + 1)_i refer to 1 when α = 1_Ci. This is consistant with viewing 1 as a new unit of C_i. Dually, we will occasionally let (β − 1)_j refer to 0 when β = 0_Cj. These shortcuts will help us avoid having to deal seperately with the extremal cases of α and β in arguments.

Recall that a poset, and in particular , is a reflexive relation. We refer to a reflexive relation simply as a reflexive digraph, and view posets as reflexive digraphs, saying (x, y) is an arc, or writing x → y, to mean x ≤ y. A spanned extension of is any digraph on the elements of , which contains it. A preorder is a transitive reflexive digraph.

The following is our extension of J(L), we chose to label it with a D rather than a J to emphasise the fact that it is a digraph, and not necessarily a poset.

Definition 3.4. ( and )

For any digraph D, let be the family of downsets of D ordered by inclusion, and be the subfamily of non-trivial downsets.

As with posets, it is clear for digraphs that unions and intersections of downsets are downsets, so is indeed a poset for any digraph D. In ourmain theorem we will see that is, in fact, the lattice L when D is the spanned extension D_℘(L) of .

For a poset P let P^∨ be the poset we get from P by adding a new minimum element and let P^⋄ be the poset we get from P^∨ by adding a new maximum element. It has been observed in several places, (see, for example, [6]), that

(3.1)$${\mathcal{D}}_{\text{nt}}(P^{\diamond })\cong \mathcal{D}(P).$$

Indeed, the isomorphism is the map that drops the appended unit. As implies P ≅ P′ we have

(3.2)$${\mathcal{D}}_{\text{nt}}(P^{\diamond })\cong {\mathcal{D}}_{\text{nt}}(Q^{\diamond })\Rightarrow P^{\diamond }\cong Q^{\diamond }.$$

With (3.1), the following base case of our main theorem is immediate from Theorem 2.1. It will also be clear from the top example in Figure 2 of the next subsection.