No Algorithm Can Decide Which Finite Lattices Are Full Congruence Lattices

A finite lattice need not be the complete collection of congruences of any finite algebra. The September 2026 manuscript claims more: no algorithm can always decide which finite lattices are such collections.^†

A congruence is an equivalence relation compatible with an algebra’s operations: if two inputs are identified, applying an operation must leave their outputs identified. Ordered from finer to coarser, these relations form a lattice. The representation question asks whether a proposed finite lattice occurs as the full congruence lattice of some finite algebra—not merely as a sublattice of one.

A three-element example shows how operations constrain the possible identifications. Take objects x, y, and z, and one unary operation with f(x) = x, f(y) = x, and f(z) = y. Identifying x with y is compatible because their images agree. Identifying x with z is not: their images lie in different blocks. The same operation rules out identifying y with z. Exactly three of the five possible partitions survive, forming a chain. This is an illustration of the mechanism, not a counterexample to the manuscript’s claims.

The manuscript characterizes representability using colored complete graphs. Its reconstruction takes every admissible self-map of the graph as a unary operation, so the resulting algebra has precisely the intended congruences.

The graph has a finite, nonempty vertex set. Each pair of vertices receives a color drawn from the proposed lattice. For a three-element chain 0 < a < 1, for example, the edge xy can have color a, the edges from z to x and y color 1, and every loop color 0.

A placement maps vertices to vertices and may send several vertices to the same point. It is admissible if it never raises an edge’s color: the color between the images of p and q must be at most the original color between them. In the three-vertex example, 15 of the 27 possible maps meet this condition. The reconstruction uses all admissible placements as operations.

For each lattice element a, identify p and q when their edge color is at most a. Three conditions ensure that these threshold relations are exactly the algebra’s congruences.

First, only loops have color 0, and colors obey a lattice triangle inequality: the direct color from p to q is at most the join of the colors along any detour through u. Join means least common upper bound. This makes each threshold relation transitive. If both detour colors are at most a, their join—and therefore the direct color—is at most a. Admissible placements preserve threshold relations because they only lower colors.

Second, the threshold relations must distinguish lattice elements. Whenever a is not below b, some pair must have color at most a but not at most b. Otherwise distinct lattice elements could produce the same relation.

Third, a path condition excludes extra congruences. For any nonempty set S of edges, mark their images under every admissible placement. Whenever a pair’s color is below the join of the colors in S, a path of marked edges must connect that pair.

To see how this rules out additional congruences, take any congruence θ and let S contain all its pairs, including loops. Let a be the join of their edge colors. Then θ is contained in the threshold relation at a. Every marked edge remains in θ, because the placements are operations; the path condition and transitivity give the reverse containment. Thus every congruence is a threshold relation. Including loops also handles the one-point case.

For any fixed number of graph vertices, the conditions can be checked by finitely many computations. One can test one vertex, then two, then three, and continue. If a lattice has a representation, this search eventually finds a witness. If it has none, the search may run forever. The property is semidecidable: a “yes” can eventually be certified, but failure to find a witness does not certify “no.”

A computable bound on witness size would turn the search into a decision procedure: check all candidates up to that bound. Conversely, a decider would give such a bound. For each lattice size, there are only finitely many order tables. Run the decider on them, find witnesses for the “yes” cases, and take the largest witness size. Each witness search terminates because the decider has identified a representable lattice. The manuscript’s undecidability claim therefore rules out a computable universal bound on witness size.

The manuscript’s undecidability reduction connects circuit solvability to representation through two bounds. First, the number of elements in a template lattice is bounded computably by the syntax of the circuit it represents, independently of the numerical solution. Second, a representation on m points yields a common reading whose cell sizes are at most 60^m m!. The explainer gives the role of these bounds but omits the structural and counting arguments that establish them.

Here is how the transfer works. Suppose a representation decider existed. The witness-bound argument would give a computable bound on the size of a representation for any template lattice of a given size. Since the template size is itself bounded by the circuit’s syntax, this would put a computable bound on m for the templates relevant to that circuit. The second bound then limits the cell sizes in the common reading, and thus gives a finite range for the values in a replacement solution. These values need not be the values in the original solution; the claim is that an existing solution has a bounded replacement.

The construction encodes positive integers in weighted templates. Addition is handled by comparing totals, while multiplication is forced through squares. For positive x, y, and z, a side unit for a value v has size 16v, and its square unit has size (16v)². Requiring the square for x + y to equal the squares for x and y plus 32 side units for z gives:

Expanding and canceling the square terms leaves 512xy = 512z, hence z = xy. This identity is the exact arithmetic step, not the whole reduction. The deeper omitted argument is what forces all the size comparisons into one common reading so that the arithmetic constraints hold together.

Once the replacement values are bounded, one can search the finite box of possible values and decide whether the circuit has a positive-integer solution. The manuscript invokes the established undecidability of that problem; therefore, as the manuscript argues, a representation decider cannot exist. The algorithm does not construct a template from unknown solution values. Rather, a template associated with the circuit shows that any existing solution would have a bounded replacement.

The manuscript also claims undecidability for full subgroup intervals in finite groups, using a separate bounded-replacement argument. It does not claim that this property and congruence-lattice representability agree for each lattice.

It describes a minimum non-representable lattice using an unevaluated Busy Beaver constant: a finite description, not a computed diagram. The three-point model illustrates the graph mechanism but does not establish these global claims. For congruence-lattice representability, the central consequence the manuscript claims is that positive instances have finite, checkable witnesses, yet no computable uniform bound limits their size.