OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction · §1

Theorem 1.1 [Main theorem]: L≅Con(𝑨)L \cong \mathrm{Con}(\mathbf{A}), 𝑨\mathbf{A} finite, exactly when LL has one; under decidable equality and order, whether one exists on nn vertices is decidable

Representable finite lattices are those with a graph witness.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Take a finite lattice LL and ask whether it is isomorphic to the congruence lattice of a finite algebra.

Algebras and Congruences

An algebra 𝑨\mathbf{A} on a set AA is a finite list of operations f1,…,fmf_1, \dots, f_m on AA, each fif_i a map Aki→AA^{k_i} \to A of some arity ki≥0k_i \ge 0; constants (ki=0k_i = 0) and the empty list (m=0m = 0) are allowed.✦ A finite algebra 𝑨\mathbf{A} is an algebra on the set {0,1,…,n−1}\{0, 1, \dots, n-1\} for some n>0n > 0.

An equivalence relation θ\theta on AA is compatible with 𝑨\mathbf{A} when, for each operation fif_i of arity k=kik = k_i and all a1,…,ak,b1,…,bk∈Aa_1, \dots, a_k, b_1, \dots, b_k \in A, a1θb1,…,akθbk⟹fi(a1,…,ak)θfi(b1,…,bk).a_1 \mathrel{\theta} b_1, \ \dots, \ a_k \mathrel{\theta} b_k \implies f_i(a_1, \dots, a_k) \mathrel{\theta} f_i(b_1, \dots, b_k).(1)✦ A congruence of 𝑨\mathbf{A} is an equivalence relation on AA compatible with 𝑨\mathbf{A}.✦ The congruence lattice Con(𝑨)\mathrm{Con}(\mathbf{A}) of 𝑨\mathbf{A} is the set of all congruences of 𝑨\mathbf{A}, ordered by inclusion.✦

A partially ordered set LL is representable, written R(L)R(L), when there are a finite algebra 𝑨\mathbf{A} and an order isomorphism L≅Con(𝑨)L \cong \mathrm{Con}(\mathbf{A}) of LL onto Con(𝑨)\mathrm{Con}(\mathbf{A}).✦

Graph Witnesses

Let LL be a lattice with least element 00. An LL-coloring of a set AA of vertices is a map d:A×A→Ld\colon A \times A \to L, with d(p,q)d(p,q) the color of the edge {p,q}\{p,q\}; loops (p,p)(p,p) count as edges. A self-map ff of AA is admissible for dd when d(f(p),f(q))≤d(p,q)for all p,q∈A.d(f(p), f(q)) \le d(p,q) \quad \text{for all } p, q \in A.(2)✦

Fix a finite set SS of ordered pairs of vertices, the seed edges, and put aS=⋁(p,q)∈Sd(p,q)a_S = \bigvee_{(p,q) \in S} d(p,q). The marked graph ΓS\Gamma_S is the graph on AA whose edges, the marked edges, are the pairs (f(p),f(q))(f(p), f(q)) with (p,q)∈S(p,q) \in S and ff admissible for dd.✦ Vertices pp and qq are connected in ΓS\Gamma_S when they lie in one class of the equivalence relation on AA generated by the marked edges.✦

An LL-coloring dd of AA is a graph witness for LL when the following hold:✦

  1. d(p,q)=d(q,p)d(p,q) = d(q,p) for all vertices p,qp, q;

  2. d(p,q)=0d(p,q) = 0 exactly when p=qp = q;

  3. d(p,q)≤d(p,r)∨d(r,q)d(p,q) \le d(p,r) \vee d(r,q) for all vertices p,q,rp, q, r;

  4. for all a,b∈La, b \in L with a≰ba \not\le b there are vertices p,qp, q with d(p,q)≤ad(p,q) \le a and d(p,q)≰bd(p,q) \not\le b;

  5. for every nonempty finite set SS of seed edges, any two vertices p,qp, q with d(p,q)≤aSd(p,q) \le a_S are connected in ΓS\Gamma_S.

The lattice LL has a graph witness on nn vertices when some LL-coloring of {0,1,…,n−1}\{0, 1, \dots, n-1\} is a graph witness for LL, and it has a graph witness when it has one on nn vertices for some n>0n > 0.✦

The Claim

Theorem 1. Let LL be a finite lattice with least element 00. Then R(L)⇔L has a graph witness.R(L) \iff L \text{ has a graph witness.}(3)✦ If, moreover, equality and order in LL are decidable, then for every natural number nn it is decidable whether n>0 and L has a graph witness on n vertices.n > 0 \text{ and } L \text{ has a graph witness on } n \text{ vertices.}(4)✦

In the paper, the result reads: (i) a finite nonempty lattice LL is representable exactly when it satisfies the finite colored-graph criterion of Theorem 2.2, and for each candidate graph size the criterion is decidable by a finite test; (ii) there is no deterministic Turing machine that, given the order table of a finite nonempty lattice LL, always halts and decides R(L)R(L); (iii) there is a nonrepresentable finite lattice L0L_0 of minimum cardinality, specified by the finite formulas of §17, every finite lattice of smaller cardinality is representable, and |L0|>7|L_0| > 7; (iv) given the order table of a finite nonempty lattice LL, it is undecidable whether, for some finite group GG and subgroup H≤GH \le G, L≅[H,G]L \cong [H,G], the interval of subgroups KK with H≤K≤GH \le K \le G. The theorem above is part (i), with the graph witness as the criterion of Theorem 2.2.

What Is Checked

The claim is stated over finite lattices with a least element, over finite algebras, their congruences (1) and representability, and over graph witnesses with the admissible self-maps (2), marked graphs and connectivity they are built from.

Beside the claim, the library gives a decision procedure for graph witnesses: for a finite lattice LL with least element and decidable equality and order, and an LL-coloring of a finite set of vertices with decidable equality, it is decidable whether the coloring is a graph witness for LL.✦