*This is a follow-up to [a recent question of mine](https://mathoverflow.net/questions/442104/example-of-trickiness-of-finite-lattice-representation-problem):*


For $n\in\mathbb{N}$ let $C(n)$ be the smallest $k$ such that every bounded lattice with cardinality $\le n$ which is isomorphic to the congruence lattice of some finite algebra, is isomorphic to the congruence lattice of some algebra with cardinality $\le k$.



> 
> What do we know about the growth rate of $C(n)$?
> 
> 
> 


I'm especially interested in *lower bounds*, since right now my main interest is pedagogical (explaining why the finite congruence representation problem is difficult). Keith Kearnes' answer to my above-linked question uses a theorem of Bunn/Grow/Insall/Thiem which implies that for infinitely many $n$ we have $C(n)\ge 2(n-3)$. However, I don't know whether $C$ is known to grow faster than linear.



How large must algebras with a given congruence lattice be?
**What do we know about the growth rate of $C(n)$?**
We know the exact value of $C(n)$ if, in its definition,
we restrict to the class of distributive lattices.
Otherwise we only have partial results. Let me say a few words.
**Claim.**  

If $L$ is a finite distributive that has a maximal chain
$\ell\_1<\ell\_2<\cdots < \ell\_n$, then  



1. $L$ is representable as the
congruence lattice of an algebra of size $n$, and
2. $L$ is not representable as the congruence
lattice of any algebra of size $< n$.



Reasons:  

For for the first item, observe that
if $L$ is a finite distributive lattice
with a specified maximal chain
$\gamma: \ell\_1<\ell\_2<\cdots < \ell\_n$,
then it has a $0,1$-embedding into a Boolean lattice $B$
in such a way that the chain $\gamma$ remains a maximal chain.
Next, any Boolean lattice $B$ with an $n$-element
maximal chain is isomorphic to a power-set
lattice $\mathscr{P}(S)$ where
$S=\{s\_1,\ldots,s\_{n-1}\}$ is a set of size $n-1$.
Assume that $0\notin S$.
Next,
$\mathscr{P}(S)$ can be embedded into the lattice
$\Pi(\{0\}\cup S)$ of partitions of $\{0\}\cup S$
by mapping $U\subseteq S$ to the partition where $\{0\}\cup U$
is one cell and the other cells are singletons.
This is a $0,1$-embedding.
Altogether we have $0,1$-embeddings  

$L\leq B\cong \mathscr{P}(S)\leq \Pi(\{0\}\cup S)$,  

which compose to a $0,1$-embedding of
$L$ into a partition lattice
on a set of size $|\{0\}\cup S|=n$.
  



From here we cite
Quackenbush, R.; Wolk, B.  

Strong representation of congruence lattices.  

Algebra Universalis 1 (1971/72), 165-166.
which shows that any $0,1$-distributive sublattice $L$
of the lattice of the lattice of equivalence relations
on an $n$-element set is a representation of $L$
as a congruence lattice. 
For the second item of the claim, it is impossible
to represent any lattice $L$ with a maximal chain
of $n$-elements as a congruence lattice
on a set of size $k<n$, since the full
lattice of partitions on a $k$-element set
does not have a chain of $n$ elements.



In particular, if we relativize the definition
of $C(n)$ to the class of distributive
lattices, we get the following.
Let $C\_{\textrm{Dist}}(n)$ be
the least $k$ such that every bounded *distributive*
lattice with cardinality $\leq n$ which is isomorphic
to the congruence lattice of some finite algebra,
is isomorphic to the congruence lattice of some
algebra with cardinality $k$.
With this definition and the preceding remarks,
we get $C\_{\textrm{Dist}}(n)=n$. (If you look
at all bounded distributive
lattices with cardinality $\leq n$,
they are all representable, and the hardest
to represent is the $n$-element chain.
This can be represented as the congruence lattice
of an $n$-element algebra, but of no smaller algebra.)



What I said above about distributive lattices
can be extended a little bit.
A finite distributive lattice is a sublattice
of a power of the $2$-element lattice, $\mathbf{2}$.
The same kinds of results mentioned above can be proved for
the smallest nondistributive lattices
$M\_3$ and $N\_5$. Namely, $M\_3$ can be represented as a congruence
lattice on a $3$-element set, $N\_5$ can be represented
as a congruence lattice on a $4$-element set, and any sublattice
of a power of either representation is a congruence representation.
For this see
Snow, John W.  

Every finite lattice in $\mathscr{V}(M\_3)$
is representable.  

Algebra Universalis 50 (2003), no. 1, 75-81.
and
Snow, John W.  

Subdirect products of hereditary congruence lattices.   

Algebra Universalis 54 (2005), no. 1, 65-71. 
When you move to $M\_4$, it starts to get complicated, as is
explained in [an answer](https://mathoverflow.net/q/442105) to an earlier question.
In fact, it is not hard to produce a $0,1$-embedding of
$M\_q$ into the lattice of partitions of a $q$-element
set whenever $q$ is an odd prime, but the least size
congruence representation of $M\_{p+1}$ has
size $2p$ when $p$ is an odd prime. Thus, if $p$ and $q$
are odd primes satisfying $p<q<2p$, then there
is a $0,1$-embedding of $M\_{p+1}$ into $M\_q$
and then into the lattice
of partitions of a $q$-element set, but there is
no congruence representation of $M\_{p+1}$ on a $q$-element set.



Let me jump ahead to identify what seems to be the hardest
part of this problem. In
Pálfy, Péter Pál; Pudlák, Pavel  

Congruence lattices of finite algebras and
intervals in subgroup lattices of finite groups.  

Algebra Universalis 11 (1980), no. 1, 22-27.
Palfy and Pudlak isolate three properties of a
finite bounded lattice $L$ of size strictly
greater than $2$:
(A) $L$ is simple.  

(B) For any nonzero $x\in L$ there exist
$y\_1, y\_2\in L$ such that $x\vee y\_1=x\vee y\_2=1$
and $y\_1\wedge y\_2=0$.  

(C) Any $x\in L$ that is not zero and not an atom
dominates at least $4$ atoms.
Palfy and Pudlak show two things about these properties.
They show that if $L$ is any finite lattice,
then it can embedded as an upper
interval $[u,1]$ in a lattice $L'$ which satisfies
(A), (B), and (C) and has size $|L'|=5|L|+1$.
If one can represent $L'$ as a congruence
lattice of a finite algebra $\mathbf{A}$, then one
can represent $L$ as the congruence lattice
of $\mathbf{A}/u$. Thus, $L'$
(satisfying (A), (B), (C)) is only slightly larger
than $L$ (not necessarily satisfying (A), (B), (C)),
yet any upper bound on the size
of a minimal congruence lattice representation for $L'$
is also an upper bound on the size
of a minimal congruence lattice representation for $L$.  



Second, they show that if $L$
satisfies (A), (B), and (C)
and $L$ is representable as the congruence
lattice of a finite algebra $\mathbf{A}$, then there
is representation of $L$ as the congruence lattice
of a transitive $G$-set $\mathbf{B}$ satisfying $|B|\leq |A|$.
This says that, if $L$ is sufficiently complicated
and representable as a congruence lattice, then it
is representable as the congruence lattice of
a transitive $G$-set for some finite group $G$.
Such $G$-sets are isomorphic to $G/H$
under the action of left multiplication by elements of $G$
for some subgroup $H\leq G$.
Hence, if $L$ satisfies the conditions (A), (B), and (C),
and $L$ is representable as the congruence
lattice of a finite algebra, then a minimal
congruence representation may be assumed
to be of the form of a transitive $G$-set $G/H$
of size $|B|=[G:H]$, and the lattice $L$
will be isomorphic to interval in $\textrm{Sub}(G)$
of subgroups containing $H$.
If we try to estimate $C(n)$
for some $n$ equal to the size of some
Palfy-Pudlack lattice (defined as satisfying
their conditions (A), (B), (C)), we
find that we are asking for the least
index $[G:H]$ in a finite group
if the interval in $\textrm{Sub}(G)$
of subgroups containing $H$ has size $n$.



The work of Palfy and Pudlak suggests that the hard
lattices to represent are those satisfying (A), (B), and (C).
If $L$ is such a lattice, which is representable
as a congruence lattice and it has size $n$,
then to compute $C(n)$ we must be able to
determine $[G:H]$ where $G/H$
is the smallest algebra affording a congruence
representation of $L$.
This has been attempted for the sequence
of lattices $L=M\_n$, for which see


Baddeley, Robert; Lucchini, Andrea  

On representing finite lattices as intervals
in subgroup lattices of finite groups.  

J. Algebra 196 (1997), no. 1, 1-100.


They give $G$-set congruence
lattice representations for $M\_n$ for
$n$ of the form
$1, 2, q+1, q+2, ((q^t+1)/(q+1))+1$,
$q$ a prime power. I believe that it is still
unknown whether $M\_n$ is representable for other
values of $n$.






































