8
$\begingroup$

I'm trying to come up with a good explanation for my students of why the finite lattice representation problem is difficult. I've already shown that the "greedy approach" to representing the lattice drawn in this post as the congruence lattice on a finite algebra - namely, realize the lattice as a sublattice of a lattice of partitions on some large enough finite set $X$, and then look at the algebra on $X$ given by all functions respecting each partition in that sublattice - breaks down.

I'd now like to explain why this doesn't lead to an easy negative solution. Towards that end:

Is there a not-too-hard-to-verify example of a bounded lattice $L$ such that

  • $L$ is isomorphic to the congruence lattice of some finite algebra, but

  • the smallest $n$ such that $L$ embeds into the bounded lattice of partitions of $\{1,...,n\}$ is strictly less than the smallest size of an algebra with congruence lattice $\cong L$?

Essentially, a concrete example of this would give a convincing argument that the failure of the greedy strategy doesn't actually tell us much.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

$M_4$, the modular lattice of height two with four atoms is an example.

$M_4$ arises as the subgroup lattice of the symmetric group on $3$ letters, hence it arises as the congruence lattice of a regular $S_3$-set. This is an algebra with $6$ elements. There is no representation of $M_4$ as the congruence lattice of a finite algebra $\mathbf{A}$ where $\mathbf{A}$ has fewer than $6$ elements. This is proved in

A minimal congruence lattice representation for $M_{p+1}$
Roger Bunn, David Grow, Matt Insall, Philip Thiem
J. Aust. Math. Soc. 108 (2020), 332-340

Their main result is that if $p$ is an odd prime, then a minimal congruence lattice representation of $M_{p+1}$ has size $2p$, so a minimal congruence lattice representation of $M_4 = M_{3+1}$ has size $2\cdot 3 = 6$. A few years ago I posted a shorter proof of the Bunn-Grow-Insall-Thiem theorem to the arxiv.

On the other hand, it is possible to embed $M_4$ into the lattice of partitions of a $5$-element set, and $5<6$. The following four partitions of $\{1,2,3,4,5\}$ generate such an $M_4$:

12/34/5
13/25/4
14/35/2
15/24/3

Improve this answer
$\endgroup$
4
  • $\begingroup$ Lovely, thank you! $\endgroup$
    – Noah Schweber
    Commented Mar 5, 2023 at 17:37
  • $\begingroup$ Somewhat-follow-up question: is there a sequence $(L_i)_{i\in\mathbb{N}}$ of lattices such that $(i)$ each $L_i$ is isomorphic to the congruence lattice of a finite algebra but $(ii)$ the function $i\mapsto f(i)$ sending $i$ to the smallest size of an algebra with congruence lattice $\cong L_i$ is (say) super-polynomial? $\endgroup$
    – Noah Schweber
    Commented Mar 5, 2023 at 21:44
  • $\begingroup$ I don't know. There aren't many results which tell you, given $L$, the size of the smallest algebra $A$ with $\textrm{Con}(A)\cong L$. $\endgroup$
    – Keith Kearnes
    Commented Mar 6, 2023 at 1:43
  • $\begingroup$ I've asked a follow-up question about this (also, my original comment was botched - of course the point is that the size of the algebra should be compared to the size of the lattice). $\endgroup$
    – Noah Schweber
    Commented Mar 6, 2023 at 5:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .