Maximal sublattices of convex geometries: four counterexamples

Introduction

Let $L$ be a finite lattice and $M$ a maximal proper sublattice of $L$, and write $C = L \setminus M$ for its complement. When $L$ is distributive, Chen, Koh and Tan [6 Theorem 4] and Rival [14 Theorem 3] showed that $C$ is an interval $[a,b]$ in which $a$ is the only join-irreducible and $b$ the only meet-irreducible element. Adams, Freese, Nation and Schmid [1 Theorem 7] proved that $C$ is an interval whenever $L$ is bounded, and asked whether this remains true for finite semidistributive lattices [1 p. 7].

Adaricheva, Mata, Silberger and Zamojska-Dzienio [2] took up this question. Since a lattice is semidistributive exactly when it satisfies both the join and the meet semidistributive laws, they also studied the two halves separately, and especially convex geometries, which are join semidistributive. They put forward the following statements [2 pp. 2–4 and 25], numbered as there.

Question 2. Is it always the case for complements of maximal sublattices of convex geometries that the only join-irreducible element is the minimum and the only meet-irreducible elements are the maxima?

Hypothesis 1 is the question of [1]. Hypothesis 2 implies Hypothesis 1, since a semidistributive lattice and its dual are both join semidistributive, and a set that is a union of intervals with a common least element and also with a common greatest element is an interval. Adaricheva et al. proved Hypotheses 2, 3 and 4 and gave a positive answer to Question 2 for convex geometries of convex dimension two [2 Section 6]. We show that, beyond that case, none of these statements holds in general.

The four examples are given explicitly in § 3–§ 6, with proofs that can be checked by hand. § 7 reports the exhaustive computations that located them and shows that they are the smallest of their kind within the ranges searched. In particular no join-semidistributive lattice with at most fourteen elements violates Hypothesis 2; of the 672 convex geometries on five points exactly six do, the smallest being the one of Theorem A, and all of them have convex dimension four; and among the convex geometries on six points of convex dimension at most three with at most twenty-five closed sets, the one of Theorem B is the only one that does.

Hypothesis 1 remains open. Our convex geometries are not meet semidistributive (a convex geometry that is meet semidistributive is distributive [2]), so they say nothing about it. The computations confirm Hypothesis 1 for all semidistributive lattices with at most fourteen elements; by [1 Theorem 7] only the lattices that are not bounded matter, and we find exactly one such lattice up to size, with fourteen elements.

All four examples are also verified in the proof assistant Lean 4 [12] with Mathlib [10]. The formal statements are the negations of the hypotheses themselves, quantified over all finite lattices, with convex geometries described as in [2] by join semidistributivity and lower semimodularity. For Theorem B the formal proof also identifies the lattice with the family of closed sets and shows that three linear orders of the six points realize this family and that no one or two orders do. The proofs use only the standard axioms.

Preliminaries

All lattices are finite. We write $x \prec y$ when $y$ covers $x$. An element $j \ne0$ is join-irreducible if $j = x \lor y$ implies $j \in\{x,y\}$, equivalently if it has exactly one lower cover; meet-irreducible elements are defined dually. A lattice is join semidistributive if $x \vee y = x \vee z$ implies $x \vee y = x \vee(y \wedge z)$, and lower semimodular if $x \prec x \vee y$ implies $x \wedge y \prec y$.

A convex geometry on a finite set $X$ is a family $\mathcal{G}$ of subsets of $X$ that contains $\varnothing$ and $X$, is closed under intersection, and has the anti-exchange property: if $A \in\mathcal{G}$, $p \ne q$ lie outside $A$, and $q$ lies in the least member of $\mathcal{G}$ containing $A \cup\{p\}$, then $p$ does not lie in the least member containing $A \cup\{q\}$. Ordered by inclusion, $\mathcal{G}$ is a lattice with $A \wedge B = A \cap B$ and $A \vee B$ the least member of $\mathcal{G}$ containing $A \cup B$. A family that contains $\varnothing$ and $X$ and is closed under intersection has the anti-exchange property exactly when every member $A \ne X$ has a one-point extension $A \cup\{x\}$ in the family [8]. Every family obtained by intersecting the initial segments of some linear orders of $X$ is a convex geometry, and every convex geometry arises in this way; the least number of orders needed is the convex dimension [8]. The lattices of closed sets of convex geometries are exactly the finite lattices that are join semidistributive and lower semimodular [3]; these are Dilworth’s meet-distributive lattices [7]. Following [2] we use the word convex geometry for these lattices as well.

If $M$ is a maximal sublattice of $L$ and $0 \notin M$, then $M \cup\{0\}$ is a sublattice, so $C = \{0\}$; dually for $1$. Such complements satisfy all the statements above, and in the examples below $0,1 \in M$. To show that a sublattice $M$ is maximal it suffices to show that every sublattice containing $M$ and one element of $C$ is all of $L$.

The convex geometry of Theorem A

Let $X = \{a,b,c,d,e\}$ and let $\mathcal{G}_{17}$ consist of the seventeen sets

where we write $ac$ for $\{a,c\}$ and so on. They are the intersections of the initial segments of the four orders

so $\mathcal{G}_{17}$ is a convex geometry. Directly: $\mathcal{G}_{17}$ is closed under intersection, and the one-point extensions

and $de \subset ade$ show that every member other than $X$ has one. Figure 1 shows its lattice.

Proof: The members containing $e$ form a filter, which is closed under joins and meets. For such a member $A$ the intersections $A \cap b$ and $A \cap c$ are $\varnothing$, $b$ or $c$, and $A \vee b$, $A \vee c$ contain $e$. Finally $b \cap c = \varnothing$, and $b \vee c = X$ because $X$ is the only member containing $b$ and $c$. So $M$ is a sublattice.

Let $S$ be a sublattice that contains $M$ and some $x \in C$. We first show $a \in S$ or $d \in S$. If $x$ is $a$ or $d$ there is nothing to show. Otherwise $x$ is one of $ac$, $ad$, $abd$, $acd$, and then $a = ae \cap x \in S$, or $x = bd$, and then $d = de \cap bd \in S$. Next, if $a \in S$ then $d = de \cap(a \vee b) = de \cap abd \in S$, and if $d \in S$ then $a = ae \cap(c \vee d) = ae \cap acd \in S$. So $a, d \in S$, and then

all lie in $S$. Hence $S = G_{17}$, and $M$ is maximal.

Proof Proof of Theorem A: The complement $C$ of Proposition 3.1 has the two minimal elements $a$ and $d$, which are atoms of $G_{17}$ and hence join-irreducible. A union of intervals with a common least element has a least element, so Hypothesis 2 fails. The element $ad \in C$ covers exactly $a$ and $d$, both outside $M$, so Hypothesis 4 fails at $x = ad$. Finally $C$ has no minimum but contains the join-irreducible elements $a$ and $d$, so the first half of Question 2 has a negative answer.

Remark 3.2. The convex dimension of $G_{17}$ is four: its meet-irreducible elements $b$, $c$, $ac$, $bd$, $ae$, $de$, $abd$, $acd$, $abde$, $acde$ contain the antichain $\{ac, bd, ae, de\}$, so at least four orders are needed (by the argument of Lemma 4.1 below, or [8]), and four suffice. The complement $C$ is order convex, and in fact every complement of a maximal sublattice of a convex geometry on at most five points is order convex (§ 7). Since Adaricheva et al. derive the convexity of complements in convex geometries from Hypothesis 4 [2 Lemma 6.7], the restriction of Hypothesis 3 to convex geometries is still open.

The convex geometry of Theorem B

Let $X = \{a,b,c,d,e,f\}$ and let $\mathcal{G}_{25}$ consist of the twenty-five sets

They are exactly the intersections of the initial segments of the three orders

so $\mathcal{G}_{25}$ is a convex geometry; again one can check directly that it is closed under intersection and that every member other than $X$ has a one-point extension. Its lattice is drawn in Figure 2.

Proof: The orders (3) show that it is at most three. Suppose that the members of $\mathcal{G}_{25}$ are the intersections of the initial segments of some linear orders. Every initial segment is then a member, and every member $K \ne X$ is the intersection of the least initial segments of each order that contain it. If $K$ is meet-irreducible, it is therefore one of these initial segments. The sets $ab$, $de$ and $cf$ are meet-irreducible, with the single upper covers $abc$, $bde$ and $cef$, and no two of them are comparable; since the initial segments of one order form a chain, they are initial segments of three different orders.

The argument is the easy half of the theorem of Edelman and Jamison that the convex dimension is the width of the poset of meet-irreducible closed sets [8].

Proof: As in Proposition 3.1, the members containing $d$ form a filter; for such a member $A$ the intersections $A \cap a$ and $A \cap f$ lie in $\{\varnothing, a, f\}$ and $A \vee a$, $A \vee f$ contain $d$; and $a \cap f = \varnothing$, $a \vee f = X$, because $X$ is the only member containing $a$ and $f$. So $M$ is a sublattice.

Let $S$ be a sublattice that contains $M$ and some $x \in C$. First, $S$ contains one of $b$, $c$, $e$: if $x$ is one of $ab$, $bc$, $be$, $abc$, $bce$, $bcef$ then $b = x \cap bd$; if $x = ce$ then $e = ce \cap de$; and if $x$ is $cf$ or $cef$ then $c = x \cap bcd$. Next,

so $b, c, e \in S$. Finally

lie in $S$, and $S = \mathcal{G}_{25}$.

Proof Proof of Theorem B: By Lemma 4.1 the convex dimension of $\mathcal{G}_{25}$ is three. The complement $C$ of Proposition 4.2 has the three minimal elements $b$, $c$ and $e$, all atoms, so it has no least element and Hypothesis 2 fails. The element $bc \in C$ covers exactly $b$ and $c$, so Hypothesis 4 fails at $x = bc$, and the join-irreducible elements $b$, $c$, $e$ of $C$ show that the first half of Question 2 fails as well.

Remark 4.3. In $\mathcal{G}_{17}$ and in $\mathcal{G}_{25}$ the maximal sublattice consists of the least element, two atoms whose join is the greatest element, and the filter generated by a third atom. The complement of $M$ in $\mathcal{G}_{25}$ is again order convex: none of its members contains $d$, while every member of $M$ other than $\varnothing$, $a$ and $f$ does.

The convex geometry of Theorem C

Let $X = \{a, b, c, d\}$ and let $\mathcal{G}_{11}$ consist of

the intersections of the initial segments of the orders $a < c < b < d$, $a < d < b < c$ and $b < c < a < d$. It is closed under intersection, and $\varnothing\subset a \subset ab \subset abc \subset X$, $b \subset bc \subset abc$, $c \subset ac \subset abc$, $ad \subset abd \subset X$ are one-point extensions of all its members, so it is a convex geometry, of convex dimension three. Its lattice is drawn in Figure 3.

Proof: The members not containing $a$ are $\varnothing, b, c, bc$; they are closed under intersection, and $b \lor c = bc$. A join of one of $b, c, bc$ with $ad$ or $abd$ is $abd$ if it does not contain $c$, and $X$ if it does, because $X$ is the only member containing $a$, $c$ and $d$; meets give $ad \cap b = ad \cap c = ad \cap bc = \varnothing$, $abd \cap b = abd \cap bc = b$ and $abd \cap c = \varnothing$. So $M$ is a sublattice. If a sublattice $S$ contains $M$ and some $x \in C$, then $a = ad \cap x \in S$, hence $ab = a \lor b$, $ac = a \lor c$ and $abc = ab \lor c$ lie in $S$, and $S = \mathcal{G}_{11}$. The only member strictly between $ac$ and $X$ is $abc$, so $ac$ has the single upper cover $abc$.

Theorem C follows: $ac$ is a meet-irreducible element of $C$ that is not a maximal element of $C$. Here $C$ is an interval and its only join-irreducible element is its minimum $a$, so $\mathcal{G}_{11}$ satisfies Hypotheses 2 and 4; the failure of Question 2 is independent of the failure of Hypothesis 2.

The lattice of Theorem D

Let $L_{10} = \{0,1,\ldots,9\}$ be the lattice with covering pairs

drawn in Figure 4.

Theorem D follows. Adams, Freese, Nation and Schmid [1 Figure 1] drew an infinite lattice with a maximal sublattice isomorphic to $M_3$ and noted that an obvious modification gives finite lattices with the same property. We have not determined whether the complements in those lattices are order convex; $L_{10}$ is the smallest lattice in which the complement of a maximal sublattice is not.

Computations

The examples were found by two exhaustive searches.

All lattices with at most fourteen elements. The program nauty-genposetg of Brinkmann and McKay [5, 11] lists the posets on $n$ points up to isomorphism; adding a least and a greatest element and keeping the lattices gives every lattice with $n+2$ elements once. For each lattice our C program finds all maximal sublattices by running through all subsets, and tests Hypotheses 1–4 and both halves of Question 2. For fourteen elements it treats the 1,104,891,746 posets on twelve points and keeps the lattices that are join or meet semidistributive. A second program, written independently in Python, repeats the convexity test for all lattices with at most ten elements and the tests of Question 2 for all convex geometries with at most eleven elements. The lattice counts agree with the sequence A006966 of [13].

$|L|$	lattices	SD$_{\vee}$	SD	CG	non-convex	Q2, meet half	H1, H2, H4, Q2 join half
2–9	1,377	302	273	70	0	0	0
10	5,994	636	534	62	1	0	0
11	37,622	2,171	1,720	121	15	1	0
12	262,776	7,756	5,767	244	167	3	0
13	2,018,305	28,822	20,013	497	–	12	0
14	16,873,364	110,805	71,546	1,031	–	33	0

(v) Up to isomorphism there are 8,435 convex geometries on six points of convex dimension at most three with at most 25 closed sets, and $\mathcal{G}_{25}$ is the only one of them that violates Hypothesis 2.

For part (iv) the convex geometries on five points were generated directly: a search through families of subsets of $X$, closed under intersection and with one-point extensions, produced the 59,386 labelled and 672 unlabelled geometries, in agreement with the known counts. The maximal sublattices were found with a SAT solver [9]: a model of the clauses saying that a set of elements is closed under joins and meets, contains 0 and 1 and is proper is extended greedily to a maximal sublattice, which is then excluded, until no model remains. The 597 geometries with at most 22 closed sets were checked again by the C program. For part (v) we ran through all pairs of linear orders of six points, with a fixed first order, formed the intersections of the initial segments of the three orders, and kept the 56,990 families with at most 25 members; they fall into 8,435 isomorphism classes, whose maximal sublattices we found in the same way. Up to fourteen elements there is exactly one semidistributive lattice that is not bounded; it has fourteen elements, and its six maximal sublattices have intervals as complements.

Questions

Hypothesis 2 holds in convex dimension two [2] and fails in convex dimension three. By Theorem E a counterexample of convex dimension three has more than fourteen elements and at least six points, and $\mathcal{G}_{25}$ is the smallest one on six points.

Problem 1. What is the least number of closed sets of a convex geometry of convex dimension three that violates Hypothesis 2?

Problem 2. Is the complement of a maximal sublattice of a finite convex geometry always order convex?

The main question, Hypothesis 1, is untouched by the examples above: a counterexample would have to be semidistributive and not bounded, and Theorem E shows it would have more than fourteen elements.

Declarations

Funding. This research received no specific grant from any funding agency in the public, commercial or not-for-profit sectors.

Competing interests. The author has no competing interests to declare.

Data availability. The Lean 4 development, the programs of § 7 and their outputs are archived with the source of this paper [4].

Use of generative AI. During the preparation of this work the author used Claude (Anthropic) to search the literature, to run and check the computations and the formal proofs, and to draft the text. The author checked every step of the proofs and every reference, and takes full responsibility for the content.