next up previous
Next: Outlook Up: Layer cakes as lattices Previous: Endomorphisms vs. automorphisms

Computation

 

The results reported on the numbers and sizes of large sublattices of tex2html_wrap_inline3926 would not have been obtained without a heavy dose of experimental mathematics preceding the theoretical analysis. Also, one may wonder why just the P(0,2,3,n;n) are the chosen ones among all the layer cakes available. These questions are addressed in [44] whose core is the classification of all 5505 proper maximal sublattices of tex2html_wrap_inline4050 (with 37 elements) into isomorphism types and which provided the clues for the classification of all large sublattices of the lattices tex2html_wrap_inline3926 for all n. Nüssli's Masters Thesis relies on a bunch of C tex2html_wrap_inline4404 programs designed to generate maximal sublattices of tex2html_wrap_inline3312 . They give acceptable running times for tex2html_wrap_inline4408 on a SUN-workstation, but for tex2html_wrap_inline2058 the situation becomes more difficult (mainly due to storing and listing problems).

Apart from the more heuristic considerations reported in 3.1 which led to layer cake lattices, their outstanding feature - from the computational point of view - is that they are lattices of sets and that join and meet are basically set union and intersection. Since such operations are very fast in most programming languages, we obtain good running times even for brute force algorithms.

So why levels 2 and 3? The attractive feature here is the easy graphical representation of sublattices of any L(X): If S is such a sublattice, represent it as a graph G(S) with vertex set X and with all 2-sets of S as edges; there is no need to display 3-sets of S which arise as joins of 2-sets (these are given by adjacent pairs of edges of G(S)), so only the join-irreducible 3-sets must be marked additionally. The effect of the quadrangle argument used so heavily in subsection 3.2 then reduces to adding the diagonals to a 4-cycle in G(S).

We illustrate this by an example. What is the number of elements it takes to generate tex2html_wrap_inline3926 for tex2html_wrap_inline1854 ? Looking for generating sets consisting of 2-sets exclusively, the following pictures provide an answer:

figure761

Denote by g(n) the least number of 2-sets needed to generate tex2html_wrap_inline3926 . It is not hard to see from the figure that tex2html_wrap_inline4440 and that tex2html_wrap_inline4442 . We think that these bounds are sharp but have not proved it. So the problem of determining the size of minimal generating sets of tex2html_wrap_inline3926 is open, as well as some related questions: E.g., given a generating set tex2html_wrap_inline4446 , is it possible to find a generating set tex2html_wrap_inline4448 (resp. tex2html_wrap_inline4450 ) consisting of 2-sets (resp. 3-sets) exclusively such that tex2html_wrap_inline4452 (resp. tex2html_wrap_inline4454 )?


next up previous
Next: Outlook Up: Layer cakes as lattices Previous: Endomorphisms vs. automorphisms

Jürg Schmid