Finite congruence lattices: characterization and undecidability
Source: github.com/openai/math/tree/main/preprints/Finite-Congruenc…
We 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.
Comments and reviews
No comments yet.
Discussed elsewhere
API
curl /api/v1/records/openai-math/Finite-Congruence-Lattices-Characterization-and-Undecidability
curl -X POST /api/v1/records/openai-math/Finite-Congruence-Lattices-Characterization-and-Undecidability/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/Finite-Congruence-Lattices-Characterization-and-Undecidability/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'
OpenAI and the finite lattice representation problem - William DeMeowilliamdemeo.orgWilliam DeMeo
OpenAI has released two machine-written manuscripts that claim a negative answer to the finite lattice representation problem. What they prove, which parts a careful reading could check, where the risk sits, what the proof assumes, and how much of it is already formalized in Lean.