OctoInformBeta

OpenAI preprint, September 2026 · §2. A finite colored-graph characterization · §2

Theorem 2.2 [Graph criterion]: A finite lattice LL is a congruence lattice of a finite algebra exactly when a complete graph carries an LL-coloring meeting five conditions

Finite congruence lattices characterized by colored complete graphs.

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

Given a finite lattice LL, for instance the five-element lattice M3M_3 with three pairwise incomparable atoms, is there a finite algebra whose congruences, ordered by inclusion, form a lattice isomorphic to LL? Which finite lattices arise in this way is the finite lattice representation problem.

The graph criterion of the paper Finite congruence lattices: characterization and undecidability (OpenAI, preprint, 2026) answers the question with colorings of the edges of a finite complete graph by the elements of LL.

Algebras and Congruences

An algebra 𝑨\mathbf{A} on a set AA consists of finitely many operations f0,…,fm−1f_0, \dots, f_{m-1} on AA, the operation fif_i having an arity ni≥0n_i \ge 0 and sending every nin_i-tuple of elements of AA to an element of AA; constants, of arity 00, are allowed, and so is m=0m = 0.✦

A congruence of 𝑨\mathbf{A} is an equivalence relation θ\theta on AA that is compatible with every operation of 𝑨\mathbf{A}: whenever a,b∈Ania, b \in A^{n_i} satisfy ajθbja_j \mathrel{\theta} b_j for every jj, also fi(a)θfi(b)f_i(a) \mathrel{\theta} f_i(b). The congruence lattice Con⁡(𝑨)\operatorname{Con}(\mathbf{A}) of 𝑨\mathbf{A} is the set of its congruences, ordered by inclusion.✦

A partially ordered set LL is representable, written R(L)R(L), when there are an integer n>0n > 0, an algebra 𝑨\mathbf{A} on {0,…,n−1}\{0, \dots, n-1\} and an order isomorphism L≅Con⁡(𝑨)L \cong \operatorname{Con}(\mathbf{A}) of LL onto all of Con⁡(𝑨)\operatorname{Con}(\mathbf{A}).✦

Colorings and Graph Witnesses

Let LL be an ordered set and AA a set. An LL-coloring of AA 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\} and loops (p,p)(p,p) counted as edges. A self-map ff of AA 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.✦

Fix a finite set SS of seed edges, ordered pairs of points of AA. A marked edge of SS is an ordered pair (f(p),f(q))(f(p), f(q)) with (p,q)∈S(p,q) \in S and ff an admissible self-map of AA, and ΓS\Gamma_S is the graph on AA whose edges are the marked edges.✦ Two points pp and qq of AA are connected in ΓS\Gamma_S when they lie in one class of the equivalence closure of the marked edges.✦

Now let LL be a lattice with least element 00, and for a nonempty finite set SS of seed edges write aS=⋁(p,q)∈Sd(p,q)a_S = \bigvee_{(p,q) \in S} d(p,q). An LL-coloring dd of AA is a graph witness when it is symmetric, gives the color 00 to the loops and to no other edge, satisfies the triangle inequality, separates each pair a≰ba \not\le b of LL by an edge whose color lies below aa and not below bb, and, for every nonempty finite set SS of seed edges, connects in ΓS\Gamma_S every pair of points whose color lies below aSa_S: for all p,q,u∈Ap, q, u \in A, all a,b∈La, b \in L and all such SS, d(p,q)=d(q,p),d(p,q)=0⇔p=q,d(p,q)≤d(p,u)∨d(u,q),a≰b⟹d(p′,q′)≤a and d(p′,q′)≰b for some p′,q′∈A,d(p,q)≤aS⟹p and q are connected in ΓS.\begin{gathered} d(p,q) = d(q,p), \qquad d(p,q) = 0 \iff p = q, \qquad d(p,q) \le d(p,u) \vee d(u,q), \\ a \not\le b \implies d(p',q') \le a \text{ and } d(p',q') \not\le b \text{ for some } p', q' \in A, \\ d(p,q) \le a_S \implies p \text{ and } q \text{ are connected in } \Gamma_S. \end{gathered}(1)✦

A lattice LL with least element 00 has a graph witness when, for some n>0n > 0, some LL-coloring of {0,…,n−1}\{0, \dots, n-1\} is a graph witness.✦

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}.(2)✦

In the paper, the result reads: a finite nonempty lattice LL with least element 00 is the full congruence lattice of a finite algebra if and only if there is an LL-colored complete graph (A,d)(A,d) such that (i) d(p,q)≠0d(p,q) \ne 0 for p≠qp \ne q and d(p,q)≤d(p,u)∨d(u,q)d(p,q) \le d(p,u) \vee d(u,q), (ii) whenever a≰ba \not\le b in LL, some vertices p,qp, q have d(p,q)≤ad(p,q) \le a and d(p,q)≰bd(p,q) \not\le b, and (iii) for every nonempty edge set SS, vertices p,qp, q with d(p,q)≤aSd(p,q) \le a_S lie in one connected component of ΓS\Gamma_S; for each fixed |A||A| these conditions involve only lattice inequalities, finite vertex labelings and paths.

What Is Checked

The claim (2) is stated over finite lattices LL with least element 00, algebras with finitely many operations on the sets {0,…,n−1}\{0, \dots, n-1\}, their congruences, the ordered set Con⁡(𝑨)\operatorname{Con}(\mathbf{A}) and the property R(L)R(L), and over the LL-colorings of these sets with their admissible self-maps, marked edges, connectivity in ΓS\Gamma_S, graph witnesses (1) and the lattices that have one.

Let LL be an ordered set, dd an LL-coloring of a set AA and SS a finite set of seed edges. A closed marking for SS is an equivalence relation on AA that contains every marked edge of ΓS\Gamma_S.✦ The library proves, for all p,q∈Ap, q \in A, p and q are connected in ΓS⇔(p,q)∈ρ for every closed marking ρ for S.p \text{ and } q \text{ are connected in } \Gamma_S \iff (p,q) \in \rho \text{ for every closed marking } \rho \text{ for } S.(3)✦

For a finite lattice LL with least element 00 and a finite set AA, the library defines a decision procedure δA\delta_A that assigns to each LL-coloring dd of AA, in finitely many steps, a truth value with δA(d)=true⇔d is a graph witness.\delta_A(d) = \text{true} \iff d \text{ is a graph witness}.(4)✦