Constructing unlabelled lattices

arXiv:1609.08255v2 [math.CO] 18 Feb 2018

Volker Gebhardt, Stephen Tawn
18 February 2018

Abstract
We present an improved orderly algorithm for constructing all unlabelled lattices up to a given size, that is, an algorithm that constructs the
minimal element of each isomorphism class relative to some total order.
Our algorithm employs a stabiliser chain approach for cutting branches
of the search space that cannot contain a minimal lattice; to make this
work, we grow lattices by adding a new layer at a time, as opposed to
adding one new element at a time, and we use a total order that is compatible with this modified strategy.
The gain in speed is between one and two orders of magnitude. As an
application, we compute the number of unlabelled lattices on 20 elements.

1

Introduction

Enumerating all isomorphism classes of unlabelled lattices, in the sense of systematically constructing a complete list of isomorphism classes up to a certain size threshold, is a difficult combinatorial problem. The number un of
isomorphism classes of unlabelled lattices on n elements grows exponentially
in n [KL71, KW80], as does the typical size of an isomorphism class. Indeed, the largest value of n for which un has been published previously is
n = 19 [JL15, Slo].
When trying to enumerate combinatorial objects modulo isomorphism, one
typically faces the problem that the number and the size of the isomorphism
classes are so large that trying to weed out isomorphic objects through explicit
isomorphism tests is out of the question. Instead, an orderly algorithm is needed,
that is, an algorithm that traverses the search space in such a way that every
isomorphism class is encountered exactly once.
A general strategy for the construction of isomorphism classes of combinatorial objects using canonical construction paths was described in [McK98].
Orderly algorithms for enumerating isomorphism classes of unlabelled lattices,
as well as special subclasses of unlabelled lattices, were given in [HR02, JL15].
The fastest published method currently is the one described in [JL15]; the computations of u18 and u19 reported in [JL15] took 26 hours respectively 19 days
on 64 CPUs.
Both authors acknowledge support under UWS grant 20721.81112.
acknowledges support under the Spanish Project MTM2013-44233.
MSC-class: 05A15 (Primary) 06A07, 05-04 (Secondary)
Keywords: unlabelled lattice, enumeration, orderly algorithm

1

Volker Gebhardt

The algorithms described in [HR02, JL15] follow a similar strategy: (i) A
total order <wt on all labelled lattices of a given size is defined. (ii) Starting
from the (unique) <wt -minimal lattice on 2 elements, the <wt -minimal labelled
representative of each isomorphism class of unlabelled lattices with at most n
elements is constructed using a depth first search, where the children of a parent
lattice are obtained by adding a single new element covering the minimal element
of the parent lattice. (iii) For each parent lattice, one child is obtained for every
choice for the covering set of the added element that yields a labelled lattice
that is <wt -minimal in its isomorphism class of unlabelled lattices.
It is the test for <wt -minimality in step (iii) that takes most of the time:
While there are some necessary conditions that are easy to verify, ensuring that
the newly constructed labelled lattice is indeed <wt -minimal in its isomorphism
class requires checking the candidate covering set of the added element against
all possible relabellings of the elements of the existing lattice; details are given
in Section 2. Basically, one has a certain permutation group that acts on a
configuration space of covering sets, and one must verify that a given candidate
is minimal in its orbit.
It turns out that the elements of a <wt -minimal labelled lattice are arranged
by levels (cf. Section 2), and thus it is tempting to construct and test candidate
covering sets of a new element level by level, exploiting the levellised structure
for a divide-and-conquer approach; such an approach promises two advantages:
(i) The orbit of the restriction of a candidate covering set to a given level is
potentially much smaller than the orbit of the complete covering set. (ii) The
entire branch of the search space that corresponds to the candidate configuration
of covers on the given level can potentially be discarded in a single test.
However, we shall see that the constructions from [HR02, JL15] do not adapt
well to this levellised approach: In order to make the levellised approach work,
we need to modify the depth-first-search to add one level at a time as opposed to
one element at a time, and we need to modify the total order to be level-major.
The structure of the paper is as follows: In Section 2, we recall some results
from [HR02, JL15] that are needed later, and we interpret the total order used
in [HR02, JL15] as row-major. In Section 3, we describe our new construction
using a level-major order and prove the results required to establish its correctness. In Section 4, we remark on implementation details and compare the
performance of our new approach to that of those published in [HR02, JL15].
We thank the Institute for Mathematics at the University of Seville (IMUS)
for providing access to a 64-node 512 GB RAM computer that was used for
an earlier version of this paper, Peter Jipsen and Nathan Lawless for providing
the code for the algorithm used in [JL15] for timing comparisons, and Jukka
Kohonen for suggesting to include a discussion of graded lattices.

2

Background

We start by giving a brief summary of the algorithms from [HR02, JL15]. We
refer to these sources for details.
Definition 1. A finite poset L is an n-poset, if the elements of L are labelled
0, 1, . . . , n − 1, where 0 is a lower bound of L and 1 is an upper bound of L.
2

An n-poset that is a lattice is called an n-lattice. To avoid confusion with the
numerical order of integers, we denote the partial order of an n-poset L by ⊑L
and ⊒L , or simply ⊑ and ⊒ if the poset is obvious.
Notation 2. Assume that L is an n-poset.
For a ∈ L, we define the shadow of a as ↓ a = ↓L a = {x ∈ L : x ⊑L a}
and the shadeSof a as ↑ a = ↑L a = {x ∈ L : x ⊒
SL a}. For A ⊆ L, we define
↑ A = ↑L A = a∈A ↑L a as well as ↓ A = ↓L A = a∈A ↓L a.
We say that a ∈ L has depth dep(a) = depL (a) = p, if the maximum length
of any chain from 1 to a in L is p + 1. Given a non-negative integer k, we call
levk (L) = {a ∈ L : depL (a) = k} the k-th level of L. We say that L is levellised,
if depL (i) ≤ depL (j) holds for all 0 < i ≤ j < n.
For a, b ∈ L, we write a ≺ L b (or simply a ≺ b) if a is covered by b in L,
that is, a ⊑ L b holds andca ⊑ L c
x ⊑ L b implies x = a or x = b. We denote the
covering set of a ∈ L by a = L a = {x ∈ L : a ≺ x}, and we say that a ∈ L
is an atom in L if 0 ≺L a holds.
If L is a lattice and a, b ∈ L, we denote the least common upper bound of a
and b in L by a ∨ L b (or simply a ∨ b), and the greatest common lower bound
of a and b in L by a ∧ L b (or simply a ∧ b).

2.1

Canonical representatives

The idea of an orderly algorithm is to construct all those lattices that are minimal, with respect to a suitable total order, in their isomorphism class. In this
section, we recall the total order used in [HR02, JL15] and some of its properties.
Definition 3. Let L be an n-poset.
(a) For A ⊆ L, we define wtL (A) =

P

2j .

j∈A

(b) For i ∈ L, we define wtL (i) = wtL

c

L


i .


(c) We define wt(L) = wtL (2), wtL (3), . . . , wtL (n − 1) .

Ordering n-lattices lexicographically with respect to wt(L), we obtain a total
order <wt on the set of all n-lattices.
Remark 4. An n-poset L is completely defined by its covering relation. Indeed,
the upper bound 1 is not covered by any element, and it covers precisely those
elements that are not covered by any other element. Similarly, the lower bound 0
covers no element, and it is covered precisely by those elements that do not cover
any other element. Thus, L is completely described by specifying the pairs (i, j),
for 1 < i, j < n, for which i ≺ j holds.
The latter information can be interpreted as an (n − 2) by (n − 2) matrix
over F2 , and the total order <wt from Definition 3 amounts to a row-major
lexicographic order on the associated matrices; cf. Figure 1.
Theorem 5 ([HR02, Theorem 1]). If L is a <wt -minimal n-lattice and one has
0 < i ≤ j < n, then depL (i) ≤ depL (j) holds.
Corollary 6. If L is a <wt -minimal n-lattice and one has 0 < i and i ≺ j,
then j < i holds.
3

Remark 7. Theorem 5 and Corollary 6 say that a <wt -minimal n-lattice L is
levellised, that is, that the non-minimal levels of L are filled by elements labelled
in their numerical order; cf. Figure 2.
Remark 8. Any relabelling π ∈ Sym({0, . . . , n − 1}) of the elements of an nlattice L acts on each level of L, as depL (π(i)) = depL (i) holds for every i ∈ L.
In particular, if L is a levellised lattice with the elements labelled as in Figure 2,
then the relabelled lattice π(L) is levellised if and only if
π ∈ Sym({0}) × Sym({1}) × Sym({2, . . . , a2 − 1})×
× Sym({a2 , . . . , a3 − 1}) × · · · × Sym({ak , . . . , n − 1})
holds.
Theorem 9 ([HR02, Theorem 2]). If L is a <wt -minimal n-lattice, one has
wtL (2) ≤ wtL (3) ≤ . . . ≤ wtL (n − 1) .
Remark 10. Theorem 9 says that the rows of the matrices describing the
covering relation of a <wt -minimal n-lattice L (cf. Figure 1) are sorted in nondecreasing order with respect to a (right-to-left) lexicographic order on the rows.

2.2

Incremental construction

The algorithms from [HR02, JL15] work by traversing a tree of <wt -minimal
n-lattices in a depth-first manner; the root of the tree is the unique 2-lattice,
e is a descendant of the <wt -minimal n-lattice L, if L
e is
and an (n + 1)-lattice L
e is <wt -minimal.
obtained from L by adding a new cover of 0 (labelled n) and L
e is determined by L and the covering set of the new element n;
The lattice L
the possible choices for the latter can be characterised effectively.

Definition 11 ([HR02]). If L is an n-lattice, a non-empty antichain A ⊆ L\{0}
is called a lattice-antichain for L, if a∧L b ∈ {0}∪(↑L A) holds for any a, b ∈ ↑L A.

Remark 12. To test the condition in Definition 11, it is clearly sufficient to
verify that a ∧L b ∈ ↑L A holds for those pairs (a, b) that are minimal in the set

(a, b) ∈ (↑L A) × (↑L A) : a ∧L b 6= 0

with respect to the product partial order in L × L.
2

n−1
n−1

2

Figure 1: Interpreting the order <wt as row-major lexicographic order on the
matrices specifying the covering relation. Note that adding a column for 1 would
not affect the order: An entry in this column is determined by the other entries
in the same row, and it is checked after those in the lexicographic comparison.
4

Theorem 13 ([HR02, Lemma 2]). Let L be an n-lattice. A subset A ⊆ L \ {0}
is a lattice-antichain for L, if and only if L is a subposet
c of an (n + 1)-lattice LA
in which 0 ≺LA n (that is, n is an atom in LA ) and LA n = A hold.
Remark 14. In the situation of Theorem 13, it is clear that the pair (L, A)
uniquely determines LA and vice versa.
Moreover, the covering relation of LA is obtained from the covering relation
of L by
(i) adding the pair (0, n);
(ii) adding all pairs of the form (n, a) for a ∈ A; and
(iii) removing all pairs of the form (0, a) for a ∈ A that are present.
As mentioned in Remark 4, the covers of 0 need not be stored explicitly; in this
case, only step (ii) is needed.
Indeed, this definition of LA makes sense for any n-poset L and any A ⊆ L.
It is obvious from the definitions that one has wtLA (n) = wtL (A). Moreover, for
1 ≤ i < n, we have i 6⊑LA n and thus wtLA (i) = wtL (i) and depLA (i) = depL (i).
The following two results are consequences of Remark 14 and Theorem 9.
Corollary 15 ([HR02, §3]). If L is an n-lattice and A is a lattice-antichain
for L such that LA is <wt -minimal, then L is <wt -minimal.
Corollary 16 ([HR02, §5]). If L is an n-lattice and A is a lattice-antichain

for L such that LA is <wt -minimal, then one has A ∩ levk−1 (L) ∪ levk (L) 6= ∅
for k = depL (n − 1).

2.3

Testing for canonicity

In the light of Corollary 16, there are two cases to consider for testing whether
the descendant LA of a <wt -minimal n-lattice L defined by a lattice-antichain A
for L with depL (n − 1) = k is <wt -minimal:
(A) A ∩ levk (L) 6= ∅, that is, depLA (n) = k + 1
(B) A ∩ levk (L) = ∅ 6= A ∩ levk−1 (L), that is, depLA (n) = k
Case (A):
In this case, the new element n forms a separate level of LA ; cf. Figure 3(a).
As LA is levellised by construction and the non-minimal elements of L correspond to the levels 0, . . . , k of LA , any relabelling π of LA for which π(LA ) is
levellised must fix n and induce a relabelling of L by Remark 8. By Remark 14
1
2

3

···

a2 −1

a2 a1 +1 ···

a3 −1

···

···

···

ak ak +1 ···

···
n−1

0

Figure 2: A levellised n-lattice; the dashed lines separate the levels.
5

and the definition of the lexicographic order, wt(π(LA )) < wt(LA ) implies
wt(π(L)) ≤ wt(L). By Corollary 15, the latter implies wt(π(L)) = wt(L) and
thus π(L) = L.
To test whether LA is <wt -minimal, it is thus sufficient to check that

(1)
wtL (A) = min wtL (π(A)) : π ∈ Stab(L) × Sym({n}) ∼
= Stab(L)
holds, again using Remark 14.

Case (B):
In this case, the new element n is added to the lowest existing non-trivial
level of L; cf. Figure 3(b). Thus, a relabelling π of LA for which π(LA ) is
levellised need not fix n and induce a relabelling of L. It will, however, induce a
relabelling of the lattice L′ induced by the levels 0, . . . , k − 1, k + 1 of L (or LA ),
and one has π(L′ ) = L′ by the same arguments as in the previous case.
If the lowest non-trivial level of LA contains the elements ak , . . . , n, checking

whether LA is <wt -minimal means testing that wtLA (ak ), . . . , wtLA (n) is lexicographically minimal in its
the group Stab(L′ )× Sym({ak , . . . , n}).
corbit under
′
Observe that one has LA i ⊆ L for ak ≤ i ≤ n, and that the action
of π ∈ Stab(L′ ) × Sym({ak , . . . , n}) not only modifies the individual weights
wtLA (i) (by relabelling the elements of L′ ), but also permutes their positions in
the sequence (by acting on {ak , . . . , n}).

2.4

Vertically indecomposable lattices

Definition 17. An n-lattice L is vertically decomposable, if there exists an element i ∈ L \ {0, 1} that is comparable to every other element of L. Otherwise, L
is vertically indecomposable.
One can speed up the construction by restricting to lattices that are vertically
indecomposable; a straightforward recursion makes it possible to recover all
lattices from the vertically indecomposable ones. We refer to [HR02, §5] for
details.

3

An improved algorithm


The test for minimality of wtL (A) or wtLA (ak ), . . . , wtLA (n) in their orbit
under the acting permutation group is the most time consuming part of the
construction and thus an obvious target for improvement.
In Section 3.1, we sketch the basic idea for a more efficient algorithm, but
we will see that the construction of [HR02, JL15] has to be modified to make
this idea work. We describe our modified construction in Section 3.2.

L \ {0}

(

1
··· ···

L′ \ {0}

···

ak ··· n−1
n

(

1
···

ak−1 ···
ak

0

···

···
ak −1

··· n−1 n
0

(a) Case (A).

(b) Case (B).

Figure 3: The lattice LA obtained by adding a new cover n of 0 to the n-lattice L.
6

3.1

Stabiliser chain approach

Case (A) from Section 2.3 suggests a possible approach, namely the use of a
standard technique from computational group theory: stabiliser chains.
Since Stab(L) preserves each level of L by Remark 8 and L is levellised,
it is tempting to construct and test lattice-antichains level by level: Defining
Sk := Stab(L) as well as Ad := A ∩ levd (L) and Sd−1 := Sd ∩ Stab(Ad ) for
d = k, . . . , 1, condition (1) is equivalent to the following condition:

for d = k, . . . , 1
(2)
wtL (Ad ) = min wtL (π(Ad )) : π ∈ Sd

The sets Ad for d = k, . . . , 1 can be constructed and tested one at a time; this
offers two advantages: Firstly, if the test at level d fails, the levels d − 1, . . . , 1
don’t have to be constructed; an entire branch of the search space is discarded
in one step. Secondly, even if thePtest succeeds on all levels, the cost of testing
k
condition (2) is proportional to d=1 |ASd d |, and thus in general much smaller
Q
k
than |AStab(L) | = d=1 |ASd d |, which is the cost of testing condition (1) directly.
However, when trying to use a similar approach for Case (B), we run into
problems: We must compare


wtLA (ak ), . . . , wtLA (n) = wtL (ak ), . . . , wtL (n − 1), wtL (A)

lexicographically to its images under the elements of the acting permutation
group Stab(L′ ) × Sym({ak , . . . , n}), but if A has only been constructed partially, wtLA (n) = wtL (A) is not completely determined; in the interpretation of
Remark 4 and Figure 1, the leftmost entries of the last row of the binary matrix
corresponding to LA are undefined.
The elements of the group Stab(L′ ) × Sym({ak , . . . , n}) can permute the
rows of this matrix, so the position of the undefined entries will vary. Clearly,
the lexicographic comparison of the two matrices must stop once it reaches an
entry that is undefined in one of the matrices being compared; in this situation,
the order of the two matrices cannot be decided on the current level.
The problem is that the position in the matrix at which the lexicographic
comparison must stop depends on the relabelling that is applied (cf. Figure 4). A
consequence of this is that the subset of elements of Stab(L′ )×Sym({ak , . . . , n})
for which the parts of the matrices that can be compared are equal does not
form a subgroup, so applying a stabiliser chain approach is not possible.

3.2

Levellised construction

The analysis at the end of the preceding section indicates that the problem is
that possible relabellings can swap an element whose covering set is only partially determined with an element whose covering set is completely determined,
or in other words, that we add a new element to an existing level of L.
The idea for solving this problem is simple: Rather than adding one element
at a time, possibly to an already existing level, we only ever add an entire level at
a time; that way, the problem of adding elements to an existing level is avoided.
To make the stabiliser chain approach work in this setting, we must use a total
order that compares parts of the covering sets in the same order in which they are
constructed; that is, we have to compare the entries of the matrices describing
the covering relations in level-major order.
7

Notation 18. For a levellised n-lattice L with n > 2 and depL (n − 1) = k,
let L′ denote the lattice induced by the levels 0, . . . , k − 1, k + 1 of L, that is,
the lattice obtained from L by removing its last non-trivial level.
Note that L′ is a levellised n′ -lattice for some n′ < n.
The total order we are about to define uses the partition of the covering set of
each element according to levels.
Definition 19. Given a levellised n-lattice L with depL (n − 1) = k, an element
cd
c 
i ∈ L \ {0} and an integer d ∈ {1, . . . , k − 1}, we define L i =
L i ∩ lev d (L).
Definition 20. Using induction on n, we define a relation < on the set of
levellised n-lattices that are isomorphic as unlabelled lattices as follows:
Given n > 2 and levellised n-lattices L1 and L2 that are isomorphic as
unlabelled lattices, we say L1 < L2 , if one of the following holds:
• L′1 < L′2
• L′1 = L′2 = L′ and, denoting depL1 (n − 1) = depL2 (n − 1) = k and
levk (L1 ) = levk (L2 ) = {ak , . . . , n − 1}, there exist ℓ ∈ {1, . . . , k − 1} as
well as i ∈ {ak , . . . , n − 1} such that both of the following hold:
cd 
cd 
– wtL′
L2 j if d > ℓ, or d = ℓ and j ∈ {ak , . . . , i − 1}
L1 j = wtL′
cℓ 
cℓ 
– wtL′
L2 i
L1 i < wtL′

Remark 21. The relation from Definition 20 corresponds to a level-major lexicographic comparison of the binary matrices describing the covering relations
of L1 and L2 as illustrated in Figure 5.
As L1 and L2 are levellised, both matrices are lower block triagonal, with
the blocks defined by the levels. Moreover, as L1 and L2 are isomorphic as
unlabelled lattices, the block structures of both matrices are identical.
Notice also that the matrix describing the covering relation of L′1 (respectively L′2 ) is obtained from that of L1 (respectively L2 ) by removing the lowest
row and the rightmost column of blocks.
Lemma 22. The relation < from Definition 20 is a total order on the set of
levellised n-lattices that are isomorphic as unlabelled lattices.
ak

ak

n

n
2

ak −1

2

ak −1

Figure 4: Lexicographic comparison of a lattice LA obtained from a partially
constructed lattice-antichain A (left) and a relabelling (right); only the relevant
parts of the matrices are shown. Thick lines indicate the boundaries between
levels. The parts of the lattice-antichain not yet constructed are shown in grey.

8

Proof. Verifying transitivity is routine. Trichotomy holds, as for s ∈ {1, 2} and
i ∈ {2, . . . , n − 1} with depL1 (i) = depL2 (i) = D, one has
k

Ls

i=


D−1
S cd


i


 d=1 Ls




 {1}

; if

; if

D−1
S cd
Ls
d=1

D−1
S cd
Ls
d=1

i 6= ∅

i=∅

cd 
cd 
c
c
whence L1 i = L2 i holds if and only if one has wtL′
L2 i
L1 i = wtL′
for d = 1, . . . , D − 1.
Definition 23. An n-lattice L is canonical if L is levellised and <-minimal
among all levellised n-lattices that are isomorphic to L as unlabelled lattices.
Lemma 24. Every isomorphism class of unlabelled lattices on n elements contains a unique canonical n-lattice.
Proof. The set of representatives that are levellised n-lattices is clearly nonempty and finite, and < is a total order on this set by Lemma 22.
The following Theorem 26 is an analogue of Corollary 15.
Lemma 25. If L is a levellised (n + 1)-lattice for n > 1, then L = L \ {n} is a
levellised n-lattice and depL (i) = depL (i) holds for i = 1, . . . , n − 1. Moreover,
for a, b ∈ L one has the following identities:

a ∧L b ; if a ∧L b 6= n
a ∨L b = a ∨L b and a ∧L b =
0
; if a ∧L b = n
Proof. As L is levellised, 1 ≤ i < n implies depL (i) ≤ depL (n), so i 6⊑L n, and
hence depL (i) = depL (i). As L is levellised, so is L.
A routine verification shows the identities for a ∨L b and a ∧L b; in particular,
L is an n-lattice.
Theorem 26. If L is a canonical n-lattice, then L′ is canonical.
2

n−1
n−1

2

Figure 5: Interpreting the order < as level-major lexicographic order on the
matrices specifying the covering relation. Thick lines indicate the boundaries
between levels. The entries of the matrix shown in grey are zero.

9

Proof. Iterated application of Lemma 25 shows that L′ is levellised.
Assume that π ′ is a relabelling of L′ such that π ′ (L′ ) is levellised and one
has π ′ (L′ ) < L′ . We can trivially extend π ′ to a relabelling π of L such that
′
π(L) = π ′ (L′ ) < L′ , contradicting the assumption that L is canonical.

Theorem 26 means that we can again construct a tree of canonical n-lattices in
a depth-first manner; the root of the tree is the unique 2-lattice, and an (n + m)e is a descendant of a canonical n-lattice L, if L
e is obtained from L by
lattice L
e is canonical.
adding m new covers of 0 (labelled n, . . . , n + m − 1) and L
e
The lattice L is determined by L and the covering sets of the new elements n, . . . , n + m − 1; the possible choices for the latter can again be characterised effectively using lattice-antichains, although this time, extra compatibility conditions are needed. The following Theorem 29, a generalisation of
Theorem 13, makes this precise.
Notation 27. Given m ∈ N+, ann-poset L, and An , . . . , An+m−1 ⊆ L \ {0},
let LAn ,...,An+m−1 = · · · LAn · · · An+m−1 denote the (n + m)-poset obtained
c
i = Ai
from L by adding m new atoms n, . . . , n + m − 1 with LAn ,...,A
n+m−1
for i = n, . . . , n + m − 1. (See Remark 14.)
Lemma 28. Let L be a levellised n-poset with depL (n − 1) = k, let m ∈ N+ ,
and let Ai ⊆ L \ {0} for i = n, . . . , n + m − 1. The following are equivalent:
e = LAn ,...,An+m−1 is a levellised (n+m)-poset with dep e (a) = depL (a) ≤ k
(A) L
L
for 1 ≤ a < n and depLe (n) = . . . = depLe (n + m − 1) = k + 1.
(B) Ai ∩ levk (L) 6= ∅ holds for n ≤ i < n + m.

Proof. As L is levellised, one has depL (a) ≤ depL (n − 1) = k for all a ∈ L \ {0},
and induction using Remark 14 shows that depLe (a) = depL (a) ≤ k holds for
all a ∈ L \ {0}, which implies depLe (i) ≤ k + 1 for i = n, . . . , n + m − 1 by
construction. Thus, for any i = n, . . . , n + m − 1, one has depLe (i) = k + 1 if
c 
e
e
and only if ∅ =
6
e i ∩ levk (L) = Ai ∩ levk (L) = Ai ∩ levk (L) holds. Finally,
L
e is
as L is levellised, depLe (n) = . . . = depLe (n + m − 1) = k + 1 implies that L
levellised.

Theorem 29. Let L be a levellised n-lattice with depL (n − 1) = k, let m ∈ N+ ,
and let Ai ⊆ L \ {0} for i = n, . . . , n + m − 1. The following are equivalent:
e = LAn ,...,An+m−1 is a levellised (n + m)-lattice, dep e (a) = depL (a) ≤ k
(A) L
L
for 1 ≤ a < n, and depLe (n) = . . . = depLe (n + m − 1) = k + 1.
(B)

(i) Ai ∩ levk (L) 6= ∅ holds for n ≤ i < n + m;

(ii) Ai is a lattice-antichain for L for n ≤ i < n + m; and
(iii) if a, b ∈ (↑L Ai ) ∩ (↑L Aj ) for n ≤ i < j < n + m, then a ∧L b 6= 0.
Proof. We use induction on m. In the case m = 1, condition (B)(iii) is vacuous
e = LAn is a lattice if and only if An is a
and, by Theorem 13, the poset L
lattice-antichain for L. Together with Lemma 28, the claim for m = 1 is shown.
Let m > 1 and consider L◦ = LAn ,...,An+m−2 and A = An+m−1 ; we have
e
L = (L◦ )A . By Lemma 28, we can assume depLe (a) = depL◦ (a) = depL (a) ≤ k
10

for 1 ≤ a < n and depLe (n) = . . . = depLe (n + m − 1) = depL◦ (n) = . . . =
depL◦ (n + m − 2) = k + 1. In particular, ↑Le A = ↑L◦ A = ↑L A holds. Also, for
i = n, . . . , n + m − 1 and a ∈ L, we have i ⊑Le a if and only if a ∈ ↑L Ai holds.
First assume that (A) holds.
Induction using Lemma 25 shows that the sets An , . . . , An+m−2 are latticeantichains for L, and a, b ∈ (↑L Ai ) ∩ (↑L Aj ) for n ≤ i < j < n + m − 1 implies
a∧L b 6= 0. Further, by Theorem 13, the set A is a lattice-antichain for L◦ , which
means that for a, b ∈ ↑L◦ A = ↑L A, one has a ∧L◦ b ∈ {0} ∪ ↑L◦ A = {0} ∪ ↑L A.
Let a, b ∈ ↑L A. If a ∧L b 6= 0 holds, we have a ∧L b = a ∧L◦ b by repeated
application of Lemma 25, whence a ∧L b ∈ ↑L A. Thus, A is a lattice-antichain
for L. On the other hand, if a ∧L b = 0 holds, then n + m − 1 is a maximal
e and the lattice property of L
e then implies
common lower bound of a and b in L,
that i 6⊑Le a, that is a ∈
/ ↑L Ai , holds for all n ≤ i < n + m − 1. In particular,
have condition (B)(iii). Together with Lemma 28, we have thus shown (B).
Now assume that (B) holds.
By induction, L◦ is a levellised (n + m − 1)-lattice. Let a, b ∈ ↑L◦ A = ↑L A.
If we have a ∧L b 6= 0, then a ∧L◦ b = a ∧L b ∈ ↑L A = ↑L◦ A holds, using
Lemma 25 and the fact that A is a lattice-antichain for L by assumption. On
the other hand, a ∧L b = 0 implies a ∧L◦ b = 0, as by assumption, there is no
i ∈ {n, . . . , n+m−2} such that a, b ∈ ↑L Ai holds. Thus, A is a lattice-antichain
e is a lattice by Theorem 13. Together with Lemma 28, we have
for L◦ , whence L
thus shown (A).
Notation 30. Let L be a levellised n-lattice with depL (n − 1) = k, let m ∈ N+ ,
and let Ai ⊆ L \ {0} for i = n, . . . , n + m − 1. For d = 1, . . . , k we define
LW dL (An , . . . , An+m−1 ) as the sequence



wtL An ∩ levd (L) , . . . , wtL An+m−1 ∩ levd (L)

and we define the sequence LW L (An , . . . , An+m−1 ) as the concatenation of
LW kL (An , . . . , An+m−1 ), . . . , LW 1L (An , . . . , An+m−1 ) in this order.

Theorem 31. Let L be a levellised n-lattice with depL (n − 1) = k, let m ∈ N+ ,
and assume that Ai ⊆ L \ {0} for i = n, . . . , n + m − 1 satisfy condition (B) from
Theorem 29. Then LAn ,...,An+m−1 is a canonical (n + m)-lattice if and only if:
(i) L is canonical; and
(ii) the sequence LW L (An , . . . , An+m−1 ) is lexicographically minimal under
the action of Stab(L) × Sym({n, . . . , n + m − 1}) given by





π LW L (An , . . . , An+m−1 ) = LW L π Aπ−1 (n) , . . . , π Aπ−1 (n+m−1)
for π ∈ Stab(L) × Sym({n, . . . , n + m − 1}).

Proof. As any π ∈ Stab(L)×Sym({n, . . . , n+m−1}) induces a relabelling of the
e = LAn ,...,An+m−1 ,
elements of L, the action is well-defined. Moreover, defining L
cd
Theorem 29 implies Le i = Ai ∩ levd (L) for i = n, . . . , n + m − 1 and 1 ≤ d ≤ k.
e ′ is canonical, so (i)
e is canonical. By Theorem 26, L = L
First assume that L
holds. If (ii) does not hold, there exist π ∈ Stab(L) × Sym({n, . . . , n + m − 1})
as well as ℓ ∈ {1, . . . , k} and i ∈ {n, . . . , n + m − 1} such that one has
11




– wtL π Aπ−1 (j) ∩ levd (L) = wtL Aj ∩ levd (L) if d > ℓ, or d = ℓ and
j ∈ {n, . . . , i − 1}; and



– wtL π Aπ−1 (i) ∩ levℓ (L) < wtL Ai ∩ levℓ (L) .

b=L
By Theorem 29, L
π (A

),...,π(Aπ−1 (n+m−1) ) is a levellised (n + m)-lattice,
and L = L = L holds by construction. Hence, the above conditions mean
e is not canonical, contradicting the assumption. Thus (ii) holds.
that L
b′

π −1 (n)

e′

e is not canonical, there is a relabelling π of L
e such that L
b = π(L)
e
Conversely, if L
b
e
e
is levellised and L < L holds. As π actson the levels of L it induces a relabelling
b ′ = π(L)
e ′=π L
e ′ = π(L), which is levellised as well. If (i)
of L, and we have L
b<L
e implies that one has L
b′ = L
e′ = L
holds, we cannot have π(L) < L, so L
and there exist ℓ ∈ {1, . . . , k} as well as i ∈ {n, . . . , n + m − 1} such that both
of the following hold:
cd 
cd 
– wtL
b j = wtL
e j if d > ℓ, or d = ℓ and j ∈ {n, . . . , i − 1}
L
L
– wtL

cℓ 
cℓ 
b i < wtL
ei .
L
L

As we have

cd

b
L

j = π(Aπ−1 (j) ) ∩ levd (L) for j = n, . . . , n + m − 1 and 1 ≤ d ≤ k,

the above conditions imply that





LW L π Aπ−1 (n) , . . . , π Aπ−1 (n+m−1) = π LW L (An , . . . , An+m−1 )

b ′ = L,
is lexicographically smaller than LW L (An , . . . , An+m−1 ). Since π(L) = L
we have π ∈ Stab(L) × Sym({n, . . . , n + m − 1}), so (ii) does not hold.

Corollary 32. Let L be a levellised n-lattice with depL (n − 1) = k, let m ∈ N+ ,
and assume that Ai ⊆ L \ {0} for i = n, . . . , n + m − 1 satisfy condition (B) from
Theorem 29. Then LAn ,...,An+m−1 is a canonical (n + m)-lattice if and only if:
(i) L is canonical; and
(ii) for d = k, . . . , 1, the sequence LW dL (An , . . . , An+m−1 ) is lexicographically
minimal under the action of Sd given by





π LW dL (An , . . . , An+m−1 ) = LW dL π Aπ−1 (n) , . . . , π Aπ−1 (n+m−1)

for π ∈ Sd , where we define Sk = Stab(L) × Sym({n, . . . , n + m − 1}) and
Sd−1 = Sd ∩ Stab LW dL (An , . . . , An+m−1 ) for d = k, . . . , 2.

Proof. Since the sequence LW L (An , . . . , An+m−1 ) is the concatenation of the sequences LW kL (An , . . . , An+m−1 ), . . . , LW 1L (An , . . . , An+m−1 ) in this order, condition (ii) from Theorem 31 is equivalent to condition (ii) of this corollary.
Remark 33. Corollary 32 makes it possible to construct the lattice-antichains
An , . . . , An+m−1 level by level: The comparison at step d in condition (ii) only
involves the elements of An , . . . , An+m−1 that live on the level d of L. In particular, the benefits of using stabiliser chains mentioned in Section 3.1 apply:

12

(i) If the test at level d fails, the levels d − 1, . . . , 1 do not have to be constructed; an entire branch of the search space is discarded in one step.
(ii) The cost of testing condition (ii) of Corollary 32 is in general much smaller than the cost of testing condition (ii) of Theorem 31: The former is
proportional to
k
X

d=1

S
LW dL (An , . . . , An+m−1 ) d ,

while the latter is proportional to
k
Y
S
LW L (An , . . . , An+m−1 ) k =

d=1

S
LW dL (An , . . . , An+m−1 ) d .

Figure 6 shows the comparisons that are made when testing one step of condition (ii) of Corollary 32. Note that a reordering of the rows of the matrix
does not change the position at which the lexicographic comparison stops; this
property is necessary for the stabiliser chain approach to work.

4
4.1

Implementation and results
Implementation notes

This section sketches some ideas that are crucial for an efficient implementation
of the algorithm presented in the preceding sections.
4.1.1

Representing antichains using up-closed sets

While the theoretical results of Section 3 are formulated in terms of antichains,
it is easier and computationally more efficient to work with sets S that are upclosed, meaning that ↑ S = S holds. (For instance, testing whether A ⊆ L is a
lattice-antichain for L only involves ↑L A.)
Clearly, if A is an antichain, then ↑L A is up-closed and the set of minimal
elements of ↑L A is equal to A.
n

n+m−1
n−1

2

Figure 6: Lexicographic comparison of a lattice LAn ,...,An+m−1 obtained from
a sequence of partially constructed lattice-antichains and a relabelling; only
the relevant part of the matrix is shown. Thick lines indicate the boundaries
between levels. Parts of the lattice-antichains not yet constructed are shown in
grey. Parts of the lattice-antichains known to coincide are shown in black.
13

Lemma 34. Let L be a levellised n-lattice with depL (n − 1) = k, let A and B
be antichains in L, and let ℓ ∈ {1, . . . , k}. The following are equivalent:


(i) One has wtL A ∩ levd (L) = wtL B∩ levd (L) for d = k, . . . , ℓ − 1, and
wtL A ∩ levℓ (L) < wtL B ∩ levℓ (L) .


for d = k, . . . , ℓ−1,
(ii) One has wtL (↑L A)∩lev d(L) = wtL (↑L B)∩levd (L)

and wtL (↑L A) ∩ levℓ (L) < wtL (↑L B) ∩ levℓ (L) .
Proof. If (i) holds, one has ((↑L A) \ A) ∩ levd (L) = ((↑L B) \ B) ∩ levd (L) for
d = k, . . . , ℓ, since L is levellised. In particular, one has

(↑L B) \ (↑L A) ∩ levℓ (L) = (B \ A) ∩ levℓ (L) and

(↑L A) \ (↑L B) ∩ levℓ (L) = (A \ B) ∩ levℓ (L) ,

which together with (i) imply (ii).
As A and B are the sets of minimal elements of ↑L A respectively ↑L B, the
converse implication is obvious.

Corollary 35. Let L be a levellised n-lattice with depL (n − 1) = k, let m ∈ N+ ,
and assume that Ai ⊆ L \ {0} for i = n, . . . , n + m − 1 satisfy condition (B) from
Theorem 29. Then LAn ,...,An+m−1 is a canonical (n + m)-lattice if and only if:
(i) L is canonical; and
(ii) for d = k, . . . , 1, the sequence LW dL (↑L An , . . . , ↑L An+m−1 ) is lexicographically minimal under the action of Sd as in Corollary 32.
Proof. The claim follows
 from Corollary 32 with Lemma 34 and the observation
that one has ↑L π(A) = π(↑L A) for any A ⊆ L and π ∈ Sd .

4.1.2

Packed representation of antichains and Beneš networks

Let L be a canonical n-lattice with depL (n − 1) = k, and let m ∈ N+ . To
generate the descendants of L with m elements on level k +1, we use a backtrack
search to construct the sets (↑L Ai ) ∩ levd (L) for d = k, . . . , 1 (outer loop) and
i = n, . . . , n + m − 1 (inner loop).
Every time a candidate set (↑L Ai ) ∩ levd (L) has been chosen, we use condition (B) from Theorem 29 to check for possible contradictions (backtracking if there are any), and to keep track of any elements whose presence in
(↑L Ai ) ∩ levd′ (L) for some d > d′ ≥ 1 is forced by the choices made so far
(restricting the possible choices later in the backtrack search if there are any).
Once all candidate sets on the current level have been chosen, we check for
minimality under the action of the appropriate stabiliser Sd (cf. Corollary 35),
backtracking if necessary.
Given the large number of configurations that have to be generated and tested
for canonicity, it is critical to use an efficient data structure to store a configuration of antichains.
The sets (↑L An )∩levd (L), . . . , (↑L An+m−1 )∩levd (L) are encoded as a single
(m · |levd (L)|)-bit integer. That way, a lexicographic comparison of two configurations reduces to a single comparison of two (m · |levd (L)|)-bit integers.

14

When constructing lattices with up to 18 elements, m·|levd (L)| is at most 64;
when constructing lattices with up to 23 elements, m · |levd (L)| is at most 128.
Thus, on a 64-bit CPU, a lexicographic comparison of two configurations costs
only very few clock cycles.
To be able to apply permutations to a packed representation as described above
effectively, we pre-compute a Beneš network [Knu09, § 7.1.3] for each generator
of the stabiliser Sd . That way, the application of the generator to the sequence
(↑L An ) ∩ levd (L), . . . , (↑L An+m−1 ) ∩ levd (L) is realised by a sequence of bitwise operations (XOR and shift operations) on the (m · |levd (L)|)-bit integer
representation.

If the sequence (↑L An ) ∩ levd (L), . . . , (↑L An+m−1 ) ∩ levd (L) is lexicographically minimal in its orbit under the action of Sd , then the computation of this
orbit also yields generators of Sd−1 [Cam99, § 1.13]; we limit the number of
generators by applying a technique known as Jerrum’s filter [Cam99, § 1.14].
4.1.3

Vertically indecomposable lattices

Restricting the construction to vertically indecomposable lattices is very easy:
By the following lemma, the only modification required is to avoid adding a
new level that contains a single element whose covering set equals the lowest
non-trivial level of the given lattice in any step of the construction.
Lemma 36. Let L be a levellised n-lattice, let m ∈ N+ , and let Ai ⊆ L \ {0}
for i = n, . . . , n + m − 1 satisfy condition (B) from Theorem 29.
(a) If L is vertically decomposable, then LAn ,...,An+m−1 is vertically decomposable.
(b) If L is vertically indecomposable, then LAn ,...,An+m−1 is vertically decomposable if and only if m = 1 and ↑L An = L \ {0} hold.
e = LAn ,...,An+m−1 .
Proof. Let k = depL (n − 1) and let L

(a) As L is vertically decomposable, there exists i ∈ L \ {0, 1} such that i is
comparable to every element of L. In particular, j ⊑L i holds for any
j ∈ levk (L), since L is levellised. For any a ∈ {n, . . . , n + m − 1}, one has
e
Aa ∩ levk (L) 6= ∅, and thus a ⊑Le i, so i is comparable to every element of L.
e is vertically decomposable if and only if there exists
(b) This is obvious, as L
e \ {0}.
a ∈ {n, . . . , n + m − 1}, such hat one has a ⊑Le i for all i ∈ L

4.1.4

Graded lattices

Definition 37. A lattice L is called graded with rank function ρ : L → N if
one has ρ(a) = ρ(b) + 1 for any a, b ∈ L satisfying a ≺ L b.
Remark 38. It is clear from the definitions that a lattice L is graded if and
only if depL is a rank function for L, that is, if and
S only ifca ≺L b implies
depL (a) = depL (b) + 1; the latter is equivalent to a∈levℓ (L) L a = levℓ−1 (L)
for ℓ = 1, . . . , depL (0).

15

Lemma 39. Let L be a levellised n-lattice with depL (n − 1) = k, let m ∈ N+ ,
and assume that Ai ⊆ L \ {0} for i = n, . . . , n + m − 1 satisfy condition (B)
from Theorem 29. Then LAn ,...,An+m−1 is graded if and only if
(a) L is graded; and
(b)

n+m−1
S

Ai = levk (L) holds.

i=n

e = LAn ,...,An+m−1 . By Theorem 29, one has dep e (a) = depL (a) for
Proof. Let L
L
a ∈ L \ {0}, and depLe (i) = k + 1 = depL (0) for n ≤ i < n + m. By construction,
e for ℓ = 0, . . . , k, as well
depLe (0) = k + 2 holds. Thus, one has levℓ (L) = levℓ (L)
e
e
as levk+1 (L) = {n, . . . , n + m − 1} and levk+1 (L) = {0} = levk+2 (L).
As a ≺L b is equivalent to a ≺Le b for a, b ∈ L \ {0} and a ∈ L \ {0} (resp.
e
e if and only if a covers no other element of L
a ∈ L\{0})
covers 0 in L (resp. in L)
c
e
(resp. of L), the claim follows with Remark 38, noting that one has Le i = Ai
for i = n, . . . , n + m − 1 by construction.

In order to restrict the construction to graded lattices, it is thus sufficient to
enforce condition (b) of Lemma 39 in every step of the construction. In the light
of Lemma 36, the construction can be restricted to vertically indecomposable
graded latticed by avoiding to add a new level that contains a single element in
any step of the construction.
Note, however, that the stabiliser chain approach does not yield any benefit for graded lattices compared to [HR02, JL15], since by condition (b) of
Lemma 39, the construction of covering sets only involves a single level anyway.

4.2

Results and performance

Table 1 shows the number in of isomorphism classes of vertically indecomposable
unlabelled lattices on n elements, and the number un of isomorphism classes of
unlabelled lattices on n elements for n ≤ 20; the values i20 and u20 are new.
Table 2, Figure 7 and Figure 8 show the total CPU time and the real time
taken by the computations for n ≥ 14 using the algorithm described in this
paper and the algorithm from [JL15] for two hardware configurations:
(A) 4 threads on a system with one 4-core Intel Xeon E5-1620 v2 CPU (clock
frequency 3.70 GHz) with DDR3-1600 RAM (single thread bandwidth1
14.9 GB/s; total bandwidth 35.3 GB/s). The system load was just over 4
during the tests.
(B) 20 threads on a system with two 10-core Intel Xeon E5-2640 v4 CPUs
(clock frequency 2.60 GHz) with DDR4-2400 RAM (single thread bandwidth 9.9 GB/s; total bandwidth 89.2 GB/s). The system load was just
over 20 during the tests.
The algorithm described in this paper was implemented in C using pthreads
by the first author. The authors of [JL15] kindly provided C-code using MPI
implementing their algorithm. All code was compiled using GCC with maximal
optimisations for the respective architecture. The compiler version was 4.8.1 for
hardware configuration (A) and 4.8.5 for hardware configuration (B).
1 http://zsmith.co/bandwidth.html

16

n

1

2

3

4

5

6

7

8

9

10

11

in
un

1
1

1
1

0
1

1
2

2
5

7
15

27
53

126
222

664
1 078

3 954
5 994

26 190
37 622

n

12

13

14

15

16

in
un

190 754
262 776

1 514 332
2 018 305

12 998 035
16 873 364

119 803 771
152 233 518

1 178 740 932
1 471 613 387

n

17

18

19

20

in
un

12 316 480 222
15 150 569 446

136 060 611 189
165 269 824 761

1 582 930 919 092
1 901 910 625 578

19 328 253 734 491
23 003 059 864 006

15

16

17

18

19

20

§ 3-4

(B)

14

CPU
real

8.69
4.07

58.1
16.8

550
142

5 840
1 490

66 600
16 900

—
—

—
—

§ 3-4 [JL]

(A)

n

CPU
real

73.4
18.4

728
183

7 830
1 990

90 900
23 000

—
—

—
—

—
—

CPU
real

10.6
3.27

72.9
7.01

695
42.5

7 360
428

84 200
4 900

1 030 000
61 500

13 000 000
805 000

[JL]

Table 1: Numbers in and un of isomorphism classes of vertically indecomposable
unlabelled lattices, respectively arbitrary unlabelled lattices, on n elements.

CPU
real

165
8.49

1 610
80.8

17 100
854

196 000
9 780

2 400 000
120 000

—
—

—
—

Table 2: Total CPU time and real time for the longer computations from Table 1
using the algorithm presented in this paper (labelled § 3-4) and the algorithm
from [JL15] (labelled [JL]). Times are given in seconds.

17

1012
105

in
1011

in

1010
103
109
§ 3-4, CPU
§ 3-4, real
[JL], CPU
[JL], real

108
107
14

15

16
n

17

18

time [s]

104

102
101
100

Figure 7: Growth of the number in of vertically indecomposable lattices with n
elements, as well as of the CPU time and real time taken for their enumeration
on hardware configuration (A), in terms of n.

1014

107

in

1013

106

1012

in

1011

104

1010

103

109

§ 3-4, CPU
§ 3-4, real
[JL], CPU
[JL], real

108
107
14

15

16

17
n

18

19

20

time [s]

105

102
101
100

Figure 8: Growth of the number in of vertically indecomposable lattices with n
elements, as well as of the CPU time and real time taken for their enumeration
on hardware configuration (B), in terms of n.

18

Remark 40.
1. For longer enumerations, the speedup compared to the algorithm from
[JL15] is between a factor of 13 (hardware configuration (A), n = 15) and
a factor of 30 (hardware configuration (B), n = 18).
On both hardware configurations, the speedup increases with n. This
is expected in the light of Remark 33, as the benefits of the stabiliser chain
approach are the more pronounced, the more levels a lattice has.
2. Obtaining a meaningful complexity analysis seems out of reach, as estimating the average case complexity would require a detailed understanding
of the tree of canonical lattices. Experimentally, the algorithm seems to
be close to optimal in the sense that the computation time grows roughly
linearly in the number of lattices constructed.
3. On hardware configuration (A), the L2 and L3 cache hit rates during
the computations were on average around 55-60% respectively 80-85%; on
hardware configuration (B), this information could not be obtained. The
high L3 cache hit hate suggests that DRAM bandwidth is not a significant
limiting factor for the overall performance of the algorithm.
4. The throughput corresponds to roughly 1 800 CPU clock cycles per lattice
on hardware configuration (A) and to roughly 1 750 CPU clock cycles per
lattice on hardware configuration (B); these figures include pre-computations and inter-thread communication. This similarity of these values
in spite of the different DRAM speeds on hardware configuration (A) and
hardware configuration (B) is consistent with DRAM bandwidth not being
a significant limiting factor for the overall performance.
5. C source code implementing the described algorithm is available at the
URL https://bitbucket.org/vgebhardt/unlabelled-lattices under
the GNU GPL v. 3+.

References
[Cam99] Peter J. Cameron. Permutation groups, volume 45 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge,
1999. MR1721031
[HR02]

Jobst Heitzig and Jürgen Reinhold. Counting finite lattices. Algebra
Universalis, 48(1):43–53, 2002. MR1930032

[JL15]

Peter Jipsen and Nathan Lawless. Generating all finite modular
lattices of a given size. Algebra Universalis, 74(3-4):253–264, 2015.
MR3397437

[KL71]

Walter Klotz and Lutz Lucht. Endliche Verbände. J. Reine Angew.
Math., 247:58–68, 1971. MR0276146

[Knu09] Donald E. Knuth. The art of computer programming. Vol. 4, Fasc. 1.
Addison-Wesley, Upper Saddle River, NJ, 2009. Bitwise tricks & techniques; Binary decision diagrams.

19

[KW80] D. J. Kleitman and K. J. Winston. The asymptotic number of lattices.
Ann. Discrete Math., 6:243–249, 1980. Combinatorial mathematics,
optimal designs and their applications (Proc. Sympos. Combin. Math.
and Optimal Design, Colorado State Univ., Fort Collins, Colo., 1978).
MR593536

[McK98] Brendan D. McKay. Isomorph-free exhaustive generation.
gorithms, 26(2):306–324, 1998. MR1606516
[Slo]

J. Al-

Neil J. A. Sloane. The on-line encyclopedia of integer sequences.
https://oeis.org. Sequences A006966 and A058800.

Volker Gebhardt
v.gebhardt@westernsydney.edu.au

Stephen Tawn
stephen@tawn.co.uk
http://www.stephentawn.info

Western Sydney University
Centre for Research in Mathematics
Locked Bag 1797, Penrith NSW 2751, Australia
http://www.westernsydney.edu.au/crm

20

