Maximal sublattices of finite semidistributive lattices: the complement need not be an interval

Introduction

Let $L$ be a finite lattice and $M$ a maximal proper sublattice of $L$.¹ When $L$ is distributive the complement $L \setminus M$ is an interval: this is due to Chen, Koh and Tan [5] and to Rival [10]. Adams, Freese, Nation and Schmid [1 Theorem 7] extended this to finite bounded lattices, in the following precise form. Write $\operatorname{CJ}(u)$ and $\operatorname{CM}(v)$ for the canonical joinands of $u$ and the canonical meetands of $v$. If $u \in\operatorname{CM}(v)$ and $v \in\operatorname{CJ}(u)$, then $L \setminus[v,u]$ is a sublattice, and when $L$ is bounded every maximal sublattice arises in this way. The first half of their proof uses only semidistributivity, and they asked whether the characterization extends to finite semidistributive lattices; in their words, “We do not know” [1 after Theorem 7].

Adaricheva, Mata, Silberger and Zamojska-Dzienio [2] took up the question and stated the expected answer as a conjecture, their Hypothesis 1: the complement of a maximal sublattice of a finite semidistributive lattice is an interval. They proved it under additional hypotheses, for instance when some element of the complement is comparable with every other element of the complement [2 Theorem 5.5], and they described the complements completely for convex geometries of convex dimension two, a class of join semidistributive lattices. In earlier work [4] the author showed that their companion hypotheses for join semidistributive lattices and for arbitrary finite lattices fail, and checked by computer that the main conjecture holds for all lattices with at most fourteen elements. The main conjecture itself was left open there.

This note settles the question in the negative.

The lattice is built from a single 14-element semidistributive lattice $K$, drawn in Figure 1. It is the sublattice $L$ of $K \times K$ generated by the diagonal and one more pair; the diagonal, a copy of $K$, is the maximal sublattice (Theorem 4.3). By the theorem of Adams, Freese, Nation and Schmid such an example cannot be bounded, and indeed $K$ is not lower bounded (Remark 3.2). Every claim below reduces to a finite check that can be carried out by hand from Figure 1 and Table 1 and Table 2; the whole statement is also verified in Lean 4 (see the end of the paper).

$j$	$j_*$	$\mathord{\uparrow}j_* \setminus\mathord{\uparrow}j$	$\kappa(j)$	$m$	$m^*$	$\mathord{\downarrow}m^* \setminus\mathord{\downarrow}m$	$\kappa^d(m)$
1	0	$\{0,2,7\}$	7	4	9	$\{3,6,9\}$	3
2	0	$\{0,1,3,5,6,8,10\}$	10	5	10	$\{6,8,10\}$	6
3	1	$\{1,4\}$	4	7	12	$\{1,3,4,6,9,12\}$	1
5	3	$\{3,6,8,9,11,12\}$	11	9	12	$\{7,12\}$	7
6	3	$\{3,5\}$	5	10	13	$\{2,4,7,9,11,12,13\}$	2
7	2	$\{2,4,9\}$	9	11	13	$\{5,10,13\}$	5
8	6	$\{6,9,12\}$	12	12	11	$\{8,11\}$	8

$x$	0	1	2	3	4	5	6	7	8	9	10	11	12	13
$\varphi(x)$	0	6	7	8	12	10	8	7	8	11	10	11	11	13
$\psi(x)$	0	1	2	1	4	5	1	2	3	4	5	9	4	13
$[x,\varphi(x)]$	0	1, 3, 6	2, 7	3, 6, 8	4, 9, 12	5, 10	6, 8	7	8	9, 12	10	11	12, 11	13

Preliminaries

All lattices are finite. For a join-irreducible element $j$ of a lattice $A$ we write $j_*$ for its unique lower cover, and for a meet-irreducible element $m$ we write $m^*$ for its unique upper cover; $\mathrm{J}(A)$ and $\mathrm{M}(A)$ denote the sets of these elements, and $\mathord{\uparrow}x$, $\mathord{\downarrow}x$ the principal filter and ideal of $x$. A lattice is join semidistributive if $a \vee b = a \vee c$ implies $a \vee b = a \vee(b \wedge c)$, meet semidistributive if $a \wedge b = a \wedge c$ implies $a \wedge b = a \wedge(b \vee c)$, and semidistributive if it is both. Each law is a universally quantified implication between equations, so it passes to sublattices and to direct products.

The following criterion is well known (see [7 Chapter II]); we include the short proof of the direction we use.

Proof. Suppose $a \wedge b = a \wedge c = u$ but $v = a \wedge(b \vee c)$ is strictly above $u$. Among the join-irreducible elements below $v$ and not below $u$ choose a minimal one, $j$. Every join-irreducible element strictly below $j$ lies below $u$ by minimality, so $j_* \leq u$. Now $b \geq u \geq j_*$, and $b \not\geq j$ because otherwise $j \leq a \wedge b = u$. Hence $b \leq\kappa(j)$, and in the same way $c \leq\kappa(j)$. Then $b \vee c \leq\kappa(j)$, which is not above $j$, although $j \leq v \leq b \vee c$. This contradiction proves the first statement; the second is its dual. $\square$

The second lemma describes the sublattices of $A \times A$ we use. For a map $\varphi: A \to A$ put

Proof. The diagonal lies in $L_\varphi$ because $x \leq\varphi(x)$. The hypothesis makes $\varphi$ order preserving: if $a \leq b$, then $a$ lies in the filter $\{x : \varphi(a) \leq\varphi(x)\}$, hence so does $b$. It also makes $\varphi$ preserve meets: with $y = \varphi(a) \wedge\varphi(b)$, both $a$ and $b$ lie in $\mathord{\uparrow}\psi(y)$, so $a \wedge b \geq\psi(y)$ and $y \leq\varphi(a \wedge b)$; the reverse inequality is monotonicity. Now let $(x,y),(x',y') \in L_\varphi$. Then $x \wedge x' \leq y \wedge y' \leq\varphi(x) \wedge\varphi(x') = \varphi(x \wedge x')$, and $x \vee x' \leq y \vee y' \leq\varphi(x) \vee\varphi(x') \leq\varphi(x \vee x')$. So $L_\varphi$ is closed under both operations. $\square$

The lattice $K$

Let $K$ be the lattice of Figure 1, with elements $0,1,\ldots,13$; $0$ is the least and $13$ the greatest element, and its covering pairs are

It is a lattice: every pair of elements has a least upper bound and a greatest lower bound, as one reads off the figure. Its join-irreducible elements are $1,2,3,5,6,7,8$ and its meet-irreducible elements are $4,5,7,9,10,11,12$.

Proof. Table 1 lists, for each join-irreducible $j$, the set $\mathord{\uparrow}j^* \setminus\mathord{\uparrow}j$ of elements above $j^*$ and not above $j$, and for each meet-irreducible $m$ the set $\mathord{\downarrow}m^* \setminus\mathord{\downarrow}m$. Each of the fourteen sets has a greatest, respectively least, element, shown in the table; for instance $\mathord{\uparrow}3 \setminus\mathord{\uparrow}5 = \{3, 6, 8, 9, 11, 12\}$ has greatest element 11, since $3 \le6 \le8 \le11$ and $9 \le12 \le11$. Lemma 2.1 gives both semidistributive laws. □

The lattice $L$ and its diagonal

Define $\varphi: K \to K$ and $\psi: K \to K$ by Table 2.

Proof. Clearly $x \le\varphi(x)$ for every $x$. For each $y$ the set $\{x : y \le\varphi(x)\}$ is the filter $\mathord{\uparrow}\psi(y)$. For example, the values of $\varphi$ above 6 are taken exactly on $K \setminus\{0, 2, 7\} = \mathord{\uparrow}1$, and $\psi(6) = 1$; the other thirteen cases are checked in the same way from Figure 1. Lemma 2.2 shows that $L$ is a sublattice. Its elements are the pairs $(x,y)$ with $y$ in the interval $[x,\varphi(x)]$ listed in the last row of Table 2, which gives 26 pairs, fourteen of them on the diagonal. Finally $K \times K$ is semidistributive by Proposition 3.1, and so is its sublattice $L$. $\square$

Write $C = L \setminus D$ for the twelve pairs off the diagonal and $\bar{d} = (d,d)$ for the diagonal elements; Figure 2 shows $L$. The following computation, performed coordinatewise in $K$, is the heart of the example:

Starting from any pair of $C$ and joining or meeting with diagonal elements, one runs through all of $C$ and returns.²

Proof. $D$ is a sublattice, and it is proper because $C \ne\varnothing$. Let $S$ be a sublattice of $L$ with $D \subsetneq S$, and pick $c \in S \setminus D$. Each step of (1) joins or meets an element of $C$ with an element of $D \subseteq S$, and the twelve steps form a single cycle through all of $C$. Following the cycle from $c$ shows $C \subseteq S$, so $S = D \cup C = L$. $\square$

Proof. The first two assertions are Lemma 4.1 and Proposition 4.2. The elements of $L$ below $(1,3)$ are the pairs $(x,y)$ with $x \le1$ and $y \le3$, namely $(0,0)$, $(1,1)$ and $(1,3)$, and those below $(2,7)$ are $(0,0)$, $(2,2)$ and $(2,7)$. So both are minimal in $C$, and they are incomparable. Dually, the elements of $L$ above $(5,10)$ are $(5,10)$, $(10,10)$ and $(13,13)$, and those above $(12,11)$ are $(12,11)$, $(11,11)$ and $(13,13)$, so both are maximal in $C$.

If $C$ were an interval $[u,w]$, then $u \le(1,3) \wedge(2,7) = (0,0) \le(1,3) \le w$, so the diagonal element $(0,0)$ would lie in $C$. Hence $C$ is not an interval. It is not order convex either, since $(1,3) < (3,3) < (3,6)$ with $(1,3),(3,6) \in C$ and $(3,3) \in D$.

By [1 Theorem 7] the complement of a maximal sublattice $M$ of a bounded lattice is an interval $[v,u]$ with $u \in\operatorname{CM}(v)$ and $v \in\operatorname{CJ}(u)$; the asked extension to semidistributive lattices would force $C$ to be such an interval, and the conjecture of [2] would force $C$ to be an interval. Neither holds. $\square$

Remarks

Remark 5.1. $L$ is the sublattice of $K \times K$ generated by $D$ and the single pair $(1,3)$: the cycle (1) produces every pair of $C$ from $(1,3)$ and the diagonal. Exchanging the two coordinates gives an isomorphic example generated by $D$ and $(3,1)$. The example was found by a computer search over sublattices of $A \times A/\theta$ generated by the graph of the quotient map and a few further pairs, for small semidistributive lattices $A$ that are not bounded and congruences $\theta$ of $A$ (here $\theta$ is trivial and the graph is the diagonal); among the 46 sublattices of $K \times K$ generated by the diagonal and one further pair, these two are the smallest, and both give counterexamples. No step of the proof above depends on that search.

By [4 Theorem E], every semidistributive lattice with at most fourteen elements satisfies the conjecture, so the smallest counterexample has between 15 and 26 elements.

Formal verification

Formal verification. The statement of Theorem 4.3 is formalized in Lean 4 [9] with Mathlib [8]: the lattices $K$ and $L$ are given by their operation tables, the embedding of $L$ into $K \times K$ is checked to be an injective lattice homomorphism, both semidistributive laws are checked by the kernel, and maximality of $D$ is proved by the twelve steps of (1). The main theorem depends only on the standard axioms of Lean. The development and the search programs are archived in [3].

Use of generative AI

Use of generative AI. The author used Claude (Anthropic) to search for the example, to check it by computer and in Lean, and to draft the text; the author verified every step and is responsible for the content.

Declarations

• Funding: No funding was received for this work.

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

• Data and code availability: The Lean 4 development, the C and Python checks and the search programs are available at https://github.com/creelie/Conjecture-001 and Zenodo, doi:10.5281/zenodo.23353448.

• Author contribution: The author is the sole author of this work.

• Author contact: [email protected], [email protected]; ORCID 0000-0003-0466-750X.