1 · The essentials
The question is whether every finite arrangement of a certain kind can describe all the ways to identify elements of a finite mathematical system while respecting its operations. The arrangements are called lattices, and the systems are called algebras. The manuscripts give a negative answer: some finite lattices cannot arise this way. The main manuscript also presents an exact description, using graphs with colors, of which lattices do arise. It further shows in the manuscript that no algorithm can always decide whether a given finite lattice has such a representation. A related question about finite groups also has no general deciding algorithm, according to the manuscript. The main result has a Lean formalization, although the supplied summary does not specify exactly which claims it covers.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine a chart listing every permitted way to merge departments in an organization while keeping its rules consistent. The question is whether every chart of the required shape can be the complete chart for some finite organization; the negative answer says that some shapes cannot occur. The image captures the demand for a complete list, but not the mathematical rules governing algebras.
Why it matters
These results distinguish between being a finite lattice and being the complete lattice of congruences of a finite algebra. They also separate an exact mathematical characterization from an algorithm that always decides membership: the main manuscript supplies the former while showing in the manuscript that the latter cannot exist. The corresponding undecidability claim for finite groups extends this limitation to a second representation question.
2 · Going further
For a finite nonempty lattice , the representation question asks whether there exists a finite nonempty algebra such that is isomorphic to , the lattice of all congruences of . A congruence is an equivalence relation compatible with the algebra's operations. The word “full” is essential: the target is the entire congruence lattice, not merely a selected part of it. The companion manuscript states that there exists such an with no representation by any finite nonempty algebra of any finite signature.
The main manuscript gives an explicit colored-graph characterization of the finite nonempty lattices that admit these representations. This is the only information the supplied abstract provides about the mechanism of the argument; it does not describe the graph conditions or the steps connecting them to congruences. Alongside this characterization, the manuscript shows that deciding the representation property is undecidable.
The main manuscript also shows that recognition of full subgroup intervals in finite groups is undecidable. Such an interval consists of all subgroups between a chosen lower subgroup and a chosen upper subgroup, ordered by inclusion. The companion manuscript focuses on the negative existence result, whereas the main manuscript places that conclusion alongside a characterization and two undecidability results. The main result has a Lean formalization, but the supplied material does not identify its precise coverage.
Useful notions
- Finite sets and equivalence relations
- Partially ordered sets and lattices
- Algebras and their operations
- Groups and subgroups
- Algorithms and decision problems
What was known before / what is new
Before
The source identifies the finite lattice representation problem as the question being answered negatively. It supplies no account of earlier partial results or historical development, so no more specific prior state of knowledge is asserted here.
New
The companion manuscript shows that some finite nonempty lattice is not the full congruence lattice of any finite nonempty algebra of any finite signature. The main manuscript gives an explicit colored-graph characterization of the representable finite nonempty lattices and shows that recognition is undecidable. It also shows that recognizing full subgroup intervals in finite groups is undecidable.
Limits and assumptions
The representation statements concern finite nonempty lattices and finite algebras; the companion manuscript explicitly specifies finite nonempty algebras of any finite signature. The requirement is representation as the full congruence lattice, and the group result concerns full subgroup intervals in finite groups. Undecidability rules out a single algorithm that correctly decides every instance, not the possibility of resolving individual instances. The main result has a Lean formalization, but its exact scope is not supplied, so formal verification of every characterization and undecidability claim cannot be asserted. The abstracts provide neither the colored-graph conditions nor details of the argument, and they list no remaining open questions.
Mini glossary
- Lattice —
- A partially ordered set in which every pair of elements has a least upper bound and a greatest lower bound.
- Congruence —
- An equivalence relation on an algebra that is compatible with all of its operations.
- Full congruence lattice —
- The lattice of all congruences of an algebra, ordered by inclusion.
- Finite signature —
- A finite collection of operation symbols, each with a specified number of inputs.
- Full subgroup interval —
- The collection of all subgroups lying between two chosen subgroups, ordered by inclusion.
- Undecidability —
- The absence of an algorithm that terminates with the correct yes-or-no answer for every instance of a decision problem.
Keywords : Finite lattices · Congruence representation · Undecidability
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
Some finite lattices are not congruence lattices of any finite algebra, answering the finite lattice representation problem negatively. Moreover, no algorithm decides whether a finite lattice has such a representation, or whether it is a full subgroup interval of a finite group.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
Finite congruence lattices: characterization and undecidability
24/09/2026We give an explicit colored-graph characterization of the finite nonempty lattices that occur as full congruence lattices of finite algebras, and prove that deciding this representation property is undecidable. In particular, the finite lattice representation problem has a negative answer. We also prove that recognition of full subgroup intervals in finite groups is undecidable.
A negative solution to the finite lattice representation problem
24/09/2026We give a negative solution to the finite lattice representation problem. We prove that there is a finite nonempty lattice that is not the full congruence lattice of any finite nonempty algebra of any finite signature.