Some observations concerning the lattices of integer partitions are presented. We determine the size of the standard contexts, discuss a recursive construction and show that the lattices have unbounded breadth. Integer partitions have been studied since the time of Leibnitz and Euler and are still of interest (see e.g. Knuth [8] for a contemporary contribution and Andrews & Eriksson [2] for a monography). The set of all partitions of n, when endowed with the “dominance order”, forms a complete lattice. Almost 50 years ago Thomas Brylawski published a first major investigation on this topic. Building on his results we describe these lattices as concept lattices and extend some of his findings. Our presentation follows Brylawski's paper [3], where also the proofs not given here can be found. We suggest that the reader, before going through the technical definitions below, takes a look at Figure 1. It shows the lattice of the 42 partitions of the integer 10, ordered by dominance. A partition of a positive integer n is a nonincreasing n-tuple a := (a1, . . . , an) of integers ai ≥ 0 such that Pn i=1 ai = n. Usually we write such a partition as omitting summands which are equal to zero. The set of all partitions of n is denoted Part(n). A partition a := (a1, . . . , an) dominates a partition b := (b1, . . . , bn) iff
Introduction
Basic notions and facts i X aj ≥ j=1
i X bj j=1
holds for all i.
We mention an immediate consequence of this definition. Let l(a) denote the length, i.e., the number of nonzero summands of the partition a. When a ≥ b, then Plj(=b)1 aj ≥ Plj(=b)1 bj = n, which implies l(a) ≤ l(b). Thus longer partitions tend to be the lower part of the order. 7+3 6+4
To every partition a of n corresponds a unique associated (n + 1)-tuple ba := (a0, . . . , ban), defined by b
i bai := X aj j=1
for all i ∈ {0, . . . n}.
These associated tuples can be characterized as being precisely the nondecreasing (i.e., ai ≥ bai−1) and concave (i.e., 2bai ≥ bai−1 + bai+1) (n + 1)-tuples of integers b with a0 = 0 and an = n.
b b
The dominance order defined above corresponds to the componentwise order of the associated tuples, since a ≥ b ⇐⇒ ∀i
The componentwise minimum of nondecreasing and concave tuples is nondecreasing and concave. Dominance therefore is a meet-semilattice order of the partitions and thus automatically a lattice order.
Example 1. a := 5+1+1+1 and b := 4+2+2 are partitions of 8. Their infimum can be computed via the associated tuples: a = (0, 5, 6, 7, 8, . . .) b bb = (0, 4, 6, 8, 8, . . .) min(ba, bb) = (0, 4, 6, 7, 8, . . .) = bc for c = 4 + 2 + 1 + 1.
(5 + 1 + 1 + 1) ∧ (4 + 2 + 2) = 4 + 2 + 1 + 1.
max(ba, bb) = (0, 5, 6, 8, . . .) of ba and bb is not concave, since 2 · 6 6≥ 5 + 8, and does therefore not give the supremum.
The supremum of integer partitions can conveniently be computed using the notion of duality. The dual or conjugate partition a∗ of a partition a is defined as
ai∗ := |{j | aj ≥ i}|, i ∈ {1, . . . , n}.
A suggestive visualization is given by the Ferrers diagrams, which represent each partition of n by pebbles in an n×n-matrix, one row for each summand. The dual partition corresponds to the transposed array, see Figure 2 for an example.
Dualization is order-reversing, as Brylawski has shown, and thus is a lattice anti-automorphism (of order 2, i.e., x∗∗ = x holds for all x). This allows to compute the supremum of integer partitions as
a ∨ b = (a∗ ∧ b∗)∗.
3 + 2 + 1 + 1 = (4 + 2 + 1)∗ ab∗ = (0, 4, 5, 6, 7, 8, . . .) min(ab∗, bb∗) = (0, 3, 5, 6, 7, 8, . . .) = cb∗ for c = 5 + 2 + 1.
(5 + 1 + 1 + 1) ∨ (4 + 2 + 2) = 5 + 2 + 1.
Ferrers diagrams can also visualize the dominance order relation. For that it is
useful to rotate the diagrams counterclockwise by 90◦ and to think of them as
sand piles (see e.g. [
The standard contexts Brylawski used his characterization to determine the join-irreducible elements of the lattice. These are precisely the ones with a unique lower neighbor. The meet-irreducible partitions are the duals of these.
Proposition 2 ([
Because of the lattice anti-automorphism of order 2 the standard contexts are symmetric and may be read as adjacency matrices of graphs, however, with some vertices having loops. An example is shown in Figure 4.
KPart(9)
Proposition 3. The number of join-irreducible integer partitions of n (as well as the number of meet-irreducible ones) is The first values for n = 1, . . . , 15, . . . are (n + 1) · (n + 2) 6
− 1.
0, 1, 2, 4, 6, 8, 11, 14, 17, 21, 25, 29, 34, 39, 44, . . . . (Note that the nth value is equal to where n is the number of summands.) Proof. For given values of n, a ≥ 0, and m ≥ 1 there is at most one choice of q and r in Proposition 2, since q = (n − a) div m r = (n − a) mod m.
The condition q ≥ 2 requires that m ≤ b n−2a c. For a 6= 0 we must have m ≤ b n−3a c, except for the case that m divides n − a (and thus r = 0). The latter happens only if n − a is even and m = n−a . The number of solutions therefore is b n2 c for a = 0, b n−21 c when a 6= 0, m > b2n−3a c and r = 0, and Pan=1 b n−3a c else. Because of b n2 c + b n−21 c = n − 1 and Pan=1 b n−3a c = Pan=−01 b a3 c = b (n−1)6(n−2) c we get for the number of solutions n − 1 + (n − 1)(n − 2) 6 A simple way to turn a partition a := (a1, . . . , an) of n into a partition of n + 1 is to “add a 1 at the end2”, i.e., to obtain a + 1 := (a1, . . . , al(a), 1, 0, . . .). The 2 Recall that l(a) denotes the highest index of a non-zero summand of a as claimed in the proposition. 4
Embeddings tu mapping obviously is 1-1. It satisfies we can conclude that the mapping a 7→ a + 1 is an order isomorphism from Part(n) to Rn, with the induced order.
Proposition 4. The set Rn is infimum-closed, and so is its dual,
Rn∗ := {a∗ | a ∈ Rn}.
Proof. Note that a ∈ Rn iff the associated (n + 2)-tuple contains the entry n. Now let a and b be in Rn, and let i(a), i(b) be indices for which bai(a) = n = bbi(b). W.l.o.g. assume that i(a) ≥ i(b). Then bbi(a) ∈ {n, n + 1}, and the i(a)th entry of a[∧ b is min(n, n + 1) = n. Thus a ∧ b ∈ Rn.
Similarly, the elements a ∈ Rn∗ can be characterized as those satisfying a1 > a2, or, equivalently, 2 · ba1 > ba2. The first components of the associated (n + 2)tuple of a∗ ∧ b∗ are 0, min(a1, b1), and min(a1 + a2, b1 + b2). And indeed it follows from a1 > a2 and b1 > b2 that 2 · min(a1, b1) > min(a1 + a2, b1 + b2). Thus a∗ ∧ b∗ ∈ Rn∗. tu Lemma 1. The mapping a 7→ a + 1 is a lattice embedding of Part(n) into Part(n + 1), and so is its dual, a 7→ (a∗ + 1)∗.
Proof. Proposition 4 implicitly states that Rn also is supremum-closed (and Rn∗ as well). Because when a and b are in Rn, then a∗ and b∗ are in Rn∗ and so is a∗ ∧ b∗, according to the proposition. But then a ∨ b = (a∗ ∧ b∗)∗ is in Rn, as claimed. tu Note that Rn and Rn∗ are sublattices, but not complete sublattices, since Rn does not contain the largest and Rn∗ does not contain the smallest element of Part(n + 1).
The lemma tells us that the partition lattice of n contains that of n − 1 in at least two copies. This raises the question if a recursive construction is possible, perhaps even for the standard contexts. We say that a context embedding of (H, N, J ) into (G, M, I) is a pair of one-to-one mappings α : H → G, β : N → M such that h J n ⇐⇒ α(h) I β(n), and that a formal context (G, M, I) is symmetric if there are mappings δGM : G → M and δMG : M → G, inverse to each other, such that g I m
⇐⇒ δMG(m) I δGM (g).
For simplification it is common to use the same symbol for both δGM and δMG, for example, the symbol “ ∗”. The symmetry condition then simplifies to g I m ⇐⇒ m∗ I g∗.
Moreover, it is assumed that x∗∗ = x holds for all objects and all attributes x. Finally, when (H, N, J ) and (G, M, I) are symmetric formal contexts, then a context embedding is called a symmetric context embedding if holds for all n ∈ N . Graphically, this means that (G, M, I) can be written as a symmetric table (invariant under transposition) and that (H, N, J ) is isomorphic to an induced subcontext of (G, M, I), which is itself symmetric under the same symmetry.
The example for which we introduce these definitions is given in Figure 3. It shows the standard context of the lattice of partitions of the integer 9 as a symmetric table. It contains the standard contexts for n = 1, . . . , 8 as symmetrically embedded subcontexts3. More precisely, it shows a nested series of symmetric embeddings, as indicated in Figure 5.
This recursive construction of the standard context for n = 9 shows some regularities. But it is not obvious, what the general construction rule might be. The reason for that is given by the next proposition. 3 For n = 1, the standard context is empty. The object and attribute names apply only for n = 9. Proposition 5. There is no symmetric embedding of the standard context for the lattice of partitions of n = 9 into that for n = 10.
The proof is by exhaustive search: we wrote a simple computer program that checked all possible cases, without finding a solution. tu 5
Size and breadth Take another look at Figure 1. Two properties of the lattice are eye-catching: it is planar, and has many irreducible elements. In fact, half of its elements are join-irreducible (21 of 42), and the number of meet-irreducibles is 21 as well (but note that there are 12 doubly irreducible and 12 doubly reducible elements).
These observations are misleading, since they do not reflect a general trend. It turns out that for larger n the lattices of integer partitions grow much faster than their standard contexts. And as a consequence they must contain large Boolean lattices as suborders, which in turn implies a high order dimension.
The breadth of a complete lattice is the number of atoms of the largest Boolean lattice that it contains as a suborder, and is (in the doubly founded case) at the same time the size of the largest contranominal scale that is an induced subcontext of its standard context. Recall that the kth contranominal scale is
Nc(k) := ({1, . . . , k}, {1, . . . , k}, 6=).
We will show that partition lattices have unbounded breadth. The bounds which we derive are however very weak.
We start with an example. Consider the case n = 200. It is known (we found
the result in [12], where it is cited from [
3 972 999 029 388.
From Proposition 3 we obtain that the number of join-irreducible partitions is 201 · 202 6
A result of Albano and Chornomaz [
This can be generalized. The strategy is to show that the growth of the number of partitions forces the standard contexts to contain contranominal scales of arbitrary size. The partition function p(n) gives the number of partitions for each positive integer n. It is sequence a000041 in the OEIS [11], from where we cite the first values:
1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, . . . There is an explicit formula for p(n), but it is too complicated to be useful here. For an introduction see Wilf’s lecture notes [12], where also an asymptotic formula
1√ eπ√2n/3
p(n) ∼ 4n 3
(n → ∞)
can be found. For our purposes, an elementary lower bound suffices:
Theorem 1 (Maróti [
p(n) ≥ e2√n 14 for all n.
Theorem 2 (Albano & Chornomaz [
k
B(K) ≤ (k − 1)! |G|k−1.
Combining these two theorems yields our desired result that partition lattices have unbounded breadth: Theorem 3. For each integer k there is an integer nk such that for each n ≥ nk the lattice of partitions of n has breadth at least k.
Note that a concept lattice B(K) has breadth < k iff K is Nc(k)-free. Proof. Let n be an integer for which the partition lattice is Nc(k)-free and k ≤ |G|/2. Then the inequality of Theorem 2 must hold and must remain valid if we replace the left side by Maróti’s lower bound and the size of G by (n+1)2 , which 6 is an upper bound due to Proposition 3. This gives This can be rewritten as further as e2√n 14
k ≤ (k − 1)! · (n + 1)2k−2 6k−1
. e2√n
14k ≤ 6k−1(k − 1)! · (n + 1)2k−2, e√n ≤ s and eventually leads to where ck = log q √n ≤ ck + (k − 1) · log(n + 1), 14k 6k−1(k−1)! . Since the square root grows faster than any multiple of the logarithm, the inequality can only be fulfilled by finitely many values of n, when k is fixed.
As an example, let k := 4 and n := 200. Then ck = log(q 1643··64 ) = −1.571, √n = 14.14, and (k − 1) ∗ log(n + 1) = 15.91. The inequality holds, in contrast to the previous example, where we used exact values rather than approximations. But for n = 210, we get √n = 14.491 and (k − 1) ∗ log(n + 1) = 16.056, so that the inequality is violated. tu 6
Conclusion and outlook The lattices of integer partitions can be viewed as concept lattices. We described their standard contexts by a simple rule, based on Brylawski’s findings, and determined their sizes. It turns out that the lattices are of subexponential size wrt. their standard contexts, and thus are of unbounded breadth.
The next step in the mathematical study of these lattices could be the
characterization of the arrow relations and, building on that, the classification of
the possible subdirectly irreducible factors, see [
It remains open if the partition lattices can play a rôle in conceptual data
analysis. This seems unplausible at first. But we found the many applications
that integer partitions have within mathematics (cf. [
KPart(9)