The Post Correspondence Problem for free groups is undecidable
Source: arxiv.org/abs/2607.13951
We prove that the Post Correspondence Problem for finitely generated free groups is undecidable, even when one of the two homomorphisms is injective and has finite-index image. This resolves a longstanding open problem in algorithmic group theory. The proof proceeds through a connection with finite-state transducers. Given a cyclic tag system $\mathcal C$, we effectively construct a finite partial deterministic inverse transducer $\mathcal T_{\mathcal C}$ whose fixed-point set is nontrivial if and only if $\mathcal C$ halts. We then associate to any such transducer two homomorphisms…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.13951
curl -X POST /api/v1/records/arxiv/2607.13951/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.13951/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'