Finite lattice representation and undecidability

The explanation

Take three objects, a, b and c. Sort them into groups. There are five ways: all apart, three ways to pair two of them, or all together. Ordered by merging, these five groupings form a small diagram. Mathematicians call such a diagram a lattice: any two of its points have a least point above both and a greatest point below both.

Now add a rule that moves a to b, b to c, and c to a. Call a grouping a congruence if the rule respects it. Objects in one group must land in one group. Pairing a with b now fails, because the rule then pairs b with c. Only two groupings survive: all apart and all together. A finite algebra is a finite set with finitely many such rules. Its congruences, ordered by merging, always form a lattice. Different rules give different lattices.

The finite lattice representation problem runs the other way. Pick any finite lattice. Is there a finite algebra whose congruences form exactly that lattice, with nothing extra? The rules may be anything at all, and as many as needed.

Grätzer and Schmidt showed in 1963 that every lattice of a broad kind is the congruence lattice of some algebraSource 1. That algebra need not be finiteSource 2. In 1980, Pálfy and Pudlák tied the finite question to finite groups. Every finite lattice has a finite algebra exactly when every finite lattice is an interval in the subgroup lattice of a finite groupSource 3. That interval is the set of subgroups between two fixed ones. Many lattices were known to work. Every finite lattice of width at most two doesSource 4. Among lattices with at most seven elements, only one possible exception was left, and the paper handles itSource 5.

The two papers claim the answer is no. One claims there is a finite lattice that no finite algebra of any kind realizesSource 6. The other claims something stronger. No computer program can take a lattice's table and always decide whether a finite algebra realizes itSource 7. If every lattice worked, the program that always says yes would decide it. So the stronger claim also gives the negative answerSource 8. The same undecidability is claimed for subgroup intervals in finite groupsSource 9. There is a smallest counterexample, with more than seven elementsSource 10. Its description uses a Busy Beaver number, so its actual size is not computedSource 11.

The single obstacle is that nothing about a hypothetical algebra is bounded. Every lattice in the argument is finite. But a group realizing it could have any order, any rank and any field sizeSource 12. The paper builds lattices whose shapes force long chains of simple subgroups inside any such group. It then needs a bound on those chains that holds for every finite group at onceSource 13. The classification of finite simple groups, a large body of earlier work, supplies the key inputsSource 14.

There is also a positive tool. The paper turns a lattice into a question about finite colored graphs. A lattice is realizable exactly when a suitable colored graph existsSource 15. Searching through graphs finds every yes answer. What fails is a stopping rule for the no answersSource 16.

How sure is this? A computer proof checker called Lean has a formal proof of the colored-graph criterion. That covers the equivalence between realizability and the graph test. The undecidability results, the subgroup-interval result and the counterexample lie outside that check. They rest on long arguments using the classification of finite simple groups. No specialist review of either paper has been published.

What it doesn't show. This does not give the size of a counterexample, or a way to compute it.