[Grätzer and Schmidt 1963] proves that every algebraic lattice is isomorphic to the congruence lattice of a universal algebra. A finite lattice is algebraic. The finite lattice representation problem asks whether every finite lattice is the congruence lattice of a finite universal algebra. The answer is generally suspected to be no.

Question 1: What is the smallest lattice which is not known to be a congruence lattice of a finite universal algebra?

Remark: By "smallest" I mean "of smallest cardinal". By "not known" I don't mean that it should have been conjectured somewhere to be a counter-example.

[Pálfy and Pudlák 1980] proves that the above problem is equivalent to ask whether every finite lattice is the lattice of an interval in the subgroup lattice of a finite group. As pointed out by the authors, this theorem does not imply that every congruence lattice of a finite universal algebra is the lattice of an interval in the subgroup lattice of a finite group (whereas the converse is true), it is just an equivalence between two problems.

Question 2: What is the smallest lattice which is not known to be the lattice of an interval in the subgroup lattice of a finite group?

Remark: same as above.

This short course by William DeMeo provides a clear review of the background for this problem.

  • 1
    William DeMeo might know whether Ralph Freese or J.B. Nation respond to emails. They would be the first people I would ask about this problem. I don't know Gabor Czedli, but I've seen recent ArXiv submissions from that author. If you feel bold, you might try an email address from one of those papers. Gerhard "Email Subgroups Of Lattice Theorists" Paseman, 2018.01.21. – Gerhard Paseman Jan 21 at 23:40
  • 4
    Yes, Ralph and JB respond to emails, but Ralph is a busy department chair now and JB is retired (though still active), so if you ask them a question about this they will likely forward it to me. :) If you are very interested in this problem, I would encourage you come to come to our conference honoring Freese, Lampe, and Nation, and we can talk about it some more. – William DeMeo Jan 22 at 6:52
  • 1
    You cited my notes for a presentation I gave as a grad student in a group theory class. While I appreciate that, there are better sources for background on the problem. For example, Peter Palfy has a nice survey, and the Wikipedia entry for this problem lists other good references. – William DeMeo Jan 23 at 10:16
up vote 6 down vote accepted

Answer to Question 1:

enter image description here

All other lattices of size at most 7 are known to be representable as the congruence lattice of a finite algebra. See my thesis and this MO question.

Answer to Question 2: The same lattice that answers question 1.

However, there may be other 7-element lattices that are not known to occur as intervals in subgroup lattices of finite groups.

It is know that every lattice of size at most 6 is "group representable" in the above sense. See Watatani (1996) MR1409040 and Aschbacher (2008) MR2393428.

  • Do you have a lower-bound on the cardinal of a finite algebra to have this lattice as congruence lattice? Same question for a subgroup index? – Sebastien Palcoux Jan 22 at 7:23
  • I don't have a lower bound. That would be nice. Even better would be an upper bound! ;) By the way, if this lattice is representable at all, then a minimal representation will be an interval in a subgroup lattice (that is, the algebra will be a G-set). So, I searched for this lattice in the subgroup lattices of all groups in the Gap small groups library (except I skipped groups of order 2^k for k=7,8,9,10,11). Also, the group would have to be nonsolvable, the group action would be primitive, and the Aschbacher-O'Nan-Scott type could not be affine. – William DeMeo Jan 22 at 7:24
  • I realize this doesn't answer your question about the index. That's a harder question. Of course the lattice might occur in the subgroup lattice of a massive group as the interval above a subgroup of small index. However, we (Freese, Jipsen, and I) have used the computer to search unary algebras with at most 8 elements (or maybe it was 9 or 10 elements? ...I can't remember now). Anyway, we did not find this lattice as a congruence lattice of any algebra with at most 8 elements. – William DeMeo Jan 22 at 7:29
  • I think a promising direction is to study the properties a group must have if this lattice is to appear in its subgroup lattice above a (core-free) subgroup. Some unpublished notes about this are here. – William DeMeo Jan 22 at 7:35
  • You don't have a lower bound means that you cannot even prove that $|A|>2$ for such a finite algebra $A$? You proved in your thesis that if $H<G$ is core-free and $[H,G]$ is isomorphic to the above lattice then $G$ is a non-solvable primitive permutation group. Now all the intervals $[H,G]$ with $H$ core-free are available in GAP at index $< 32$ (via the transitive permutation groups), so you can quickly check that $|G:H| \ge 32$. – Sebastien Palcoux Jan 22 at 8:28

If an interval of finite groups $[H,G]$ is lattice-isomorphic to William's lattice then $|G:H|\ge 32$.

gap> TestDeMeoTransitive(2,30);
[  ]

TransitiveIntermediate:=function(d,r)
    local G,H,a,N,s;
    G:=TransitiveGroup(d,r);
    H:=Stabilizer(G,1);
    N:=IntermediateSubgroups(G,H);
    return N;
end;;

TestDeMeoTransitive:=function(d1,d2)
    local LL,d,n,r,int,sub,inc,L,l,i,j,G;
    LL:=[];
    for d in [d1..d2] do
        n:=NrTransitiveGroups(d);
        for r in [1..n] do
            G:=TransitiveGroup(d,r);
            if IsPrimitive(G) and not IsSolvable(G) then
                int:=TransitiveIntermediate(d,r);
                sub:=int.subgroups; inc:=int.inclusions;
                if Length(sub)=5 and Length(inc)=9 then
                   L:=List(Filtered(inc,i->i[1]=0),j->j[2]);
                   if Length(L) = 3 and Length(Filtered(inc,(i->i[1] in L) and i[2]=6)) = 1 then
                       Add(LL,[d,r]);
                   fi;
                fi;
            fi;
        od;
    od;
    return LL;
end;;

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.