2026/07/15 by André Carvalho
#math.GR #cs.FL
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 g,h\colon FY\longrightarrow FA, with h injective, such that their equalizer is nontrivial precisely when the transducer has a nontrivial fixed loop. As an immediate consequence, the rank of these equalizers cannot be computed in general, answering a question posed by Stallings in 1984. We further prove that there is no algorithm which decides whether the fixed subgroup of a virtual endomorphism of a finitely generated free group is trivial. Finally, we apply the main result to show that the stabilizer problem is undecidable for free subgroups of SL4(\mathbb Z), and that the upper-right-corner problem is undecidable for free subgroups of SL5(\mathbb Z), even when the given generators are promised to form a free basis, improving on recent results of Breuillard and Kocharyan.