next up previous
Next: Endomorphisms vs. automorphisms Up: Layer cakes as lattices Previous: Large sublattices of Boolean

Large sublattices of Boolean layer cakes: Numbers

 

Using notation established in the previous subsection, let tex2html_wrap_inline4114 be the number of maximal proper sublattices of tex2html_wrap_inline3312 and write tex2html_wrap_inline4118 for the ratio tex2html_wrap_inline4120 . Our first objective is to prove

  Proposition677

The following corollary is immediate, settling the question posed at the end of subsection 3.1 (see also [2]):

  Corollary682

Proposition 3.3.1 is proven by counting the large maximal sublattices of type tex2html_wrap_inline4136 of tex2html_wrap_inline4138 as provided by Corollary 3.2.10.

Suppose tex2html_wrap_inline4140 , k=2i>0 even. Denote by tex2html_wrap_inline4144 the number of distinct partitions of a k-element set A into 2-element subsets.

  Lemma688

Proof: This is obviously true for k=4. Suppose A' has k'=2i+2 elements and the formula holds for k=2i. For any given 2-element subset tex2html_wrap_inline4160 , there are tex2html_wrap_inline4144 many partitions of the required type including tex2html_wrap_inline2496 . The number of such subsets is tex2html_wrap_inline4166 , so we obtain tex2html_wrap_inline4168 suitable partitions of A'. But each of these has been counted k'/2 times (= the number of blocks in any such partition), so tex2html_wrap_inline4174 which simplifies to tex2html_wrap_inline4176 as required.
tex2html_wrap_inline1902

Proof of Proposition 3.3.1: Assume that tex2html_wrap_inline3178 , tex2html_wrap_inline4182 is odd. We count the number of large maximal sublattices of type tex2html_wrap_inline4136 of tex2html_wrap_inline3926 : For each tex2html_wrap_inline3490 , there are as many of these as there are partitions of tex2html_wrap_inline3562 into 2-element subsets; hence their total number is tex2html_wrap_inline4192 . We conclude that tex2html_wrap_inline4194 . On the other hand, we have tex2html_wrap_inline4196 whenever tex2html_wrap_inline2058 . Hence

displaymath4108

displaymath4109

displaymath4110

Now tex2html_wrap_inline4200 whenever tex2html_wrap_inline2058 . We infer that tex2html_wrap_inline4204 for tex2html_wrap_inline2058 . It is obvious that tex2html_wrap_inline4208 is not bounded from above for any fixed exponent k, completing the proof.
tex2html_wrap_inline1902

Next, we use Theorem 3.2.11 to shed some light on the so-called sublattice spectrum question raised first by Birkhoff in the 1948 edition of his ``Lattice Theory''. In the wording of [4, p. 19,], the question reads as follows: ``Given n, what is the smallest integer tex2html_wrap_inline4216 such that every lattice with order tex2html_wrap_inline4218 contains a sublattice of exactly n elements?''

It is shown by Havas and Ward in [27] that tex2html_wrap_inline4216 indeed exists for any tex2html_wrap_inline3178 (n>0) and that tex2html_wrap_inline4228 for n>1. Not much seems to be known about the values of tex2html_wrap_inline4232 otherwise.

Theorem 3.2.11 provides the possible sizes of large sublattices of tex2html_wrap_inline3312 for n>6: These are either of the form tex2html_wrap_inline4238 or tex2html_wrap_inline4136 , with respective sizes tex2html_wrap_inline4242 and tex2html_wrap_inline4244 . Now tex2html_wrap_inline4246 , so tex2html_wrap_inline3312 contains no sublattices of size s for tex2html_wrap_inline4252 and for tex2html_wrap_inline4254 . It follows that tex2html_wrap_inline4256 must be bigger than tex2html_wrap_inline4258 .

Proposition718


next up previous
Next: Endomorphisms vs. automorphisms Up: Layer cakes as lattices Previous: Large sublattices of Boolean

Jürg Schmid