OctoInformBeta

Finite lattice representation and undecidability

A finite algebra is a nonempty finite set AA with a finite list of total operations on AA, each of finite arity, where the list may be empty and an operation of arity zero is a constant. The congruences of a finite algebra AA, ordered by inclusion, form its congruence lattice Con⁡(A)\operatorname{Con}(A). A finite nonempty lattice LL is representable, written ℛ(L)\mathcal R(L), when LL is isomorphic to the whole congruence lattice Con⁡(A)\operatorname{Con}(A) of some finite algebra AA. The finite lattice representation problem asks whether every finite lattice is representable. The order table of LL is the table that lists, for each pair of elements of LL, whether the first lies below the second. A second question asks whether ℛ(L)\mathcal R(L) can be decided from the order table of LL.

Grätzer and Schmidt proved that every algebraic lattice is the congruence lattice of an algebra, not necessarily finite. For a subgroup HH of a finite group GG, [H,G][H,G] is the interval of all subgroups KK with H≤K≤GH\le K\le G. Pálfy and Pudlák proved that every finite lattice is representable if and only if every finite lattice is isomorphic to an interval [H,G][H,G] of some finite group GG. Pudlák and Tůma proved that every finite lattice embeds in the lattice of equivalence relations of a finite set.

For a finite lattice LL with least element 00, an LL-colored complete graph is a finite nonempty set AA with a symmetric map d:A×A→Ld\colon A\times A\to L such that d(p,q)=0d(p,q)=0 exactly when p=qp=q. A map f:A→Af\colon A\to A is admissible for dd when d(f(p),f(q))≤d(p,q)d(f(p),f(q))\le d(p,q) for all p,q∈Ap,q\in A. For a nonempty set SS of pairs of points of AA, aSa_S is the join of the colors d(p,q)d(p,q) of the pairs (p,q)∈S(p,q)\in S. The graph ΓS\Gamma_S on AA has as its edges the pairs {f(p),f(q)}\{f(p),f(q)\} with (p,q)∈S(p,q)\in S and ff admissible. The preprint proves that ℛ(L)\mathcal R(L) holds exactly when some LL-colored complete graph satisfies d(p,q)≤d(p,u)∨d(u,q)d(p,q)\le d(p,u)\vee d(u,q) for all p,q,u∈Ap,q,u\in A, contains for each a≰ba\not\le b in LL a pair with d(p,q)≤ad(p,q)\le a and d(p,q)≰bd(p,q)\not\le b, and, for each nonempty SS, joins by a path in ΓS\Gamma_S every pair with d(p,q)≤aSd(p,q)\le a_S. For each number of vertices, a finite test decides whether such a graph exists. No Turing machine, given the order table of a finite lattice LL, always halts and decides ℛ(L)\mathcal R(L). In particular, the finite lattice representation problem has a negative answer.

Of these results, the Lean library Universal contains the characterization of ℛ(L)\mathcal R(L) by LL-colored complete graphs and its finite test, and not the undecidability. For a finite group GG and a subgroup HH, the unary algebra on the left cosets G/HG/H has one operation xH↦gxHxH\mapsto gxH for each g∈Gg\in G. The Lean library also proves that the congruence lattice of this algebra is isomorphic to [H,G][H,G]. The Lean library takes as a hypothesis of its finite test that equality and order in LL can be decided. Each result on these pages is the Lean library’s, stated as the Lean library states it and linked to the Lean declaration behind it. Lean has checked every result of the Lean library, so the Lean library is the reference, and where the preprint states a result differently, the page gives the Lean library’s statement with the preprint’s beside it. The preprint is a guide only, which gives the results their order and their names.