Algebra seminar: talk by Alan Logan

On Wednesday 6th December 2023, the Charlotte Scott Centre for Algebra had the pleasure of welcoming Alan Logan (Heriot-Watt University) for a talk entitled Post’s Correspondence Problem in Group Theory at the research seminar of Lincoln University.

Abstract: Post’s Correspondence Problem (the PCP) is a classical decision problem that asks whether for pairs of free monoid morphisms g,h:Σ*→Δ* there exists any non-trivial x∈Σ* such that g(x)=h(x); see Wikipedia for more details. Post’s Correspondence Problem for a group Γ takes pairs of group homomorphisms g,h:F(Σ)→Γ instead, and similarly asks whether there exists an x such that g(x)=h(x) holds for non-elementary reasons.

In this talk I will contrast this problem with the classical free monoid setting and its surrounding theory, and then sketch a proof that this problem is decidable for Γ virtually nilpotent. This proof is based on the “non-homogeneous PCP” (NPCP), which generalises the twisted conjugacy problem for a group. Indeed, it is well-known that if the twisted conjugacy problem is decidable for a class of finitely presented groups C, then the conjugacy problem is decidable for virtually-C groups; we generalise this result by proving that if both the PCP and NPCP are decidable for a class of groups C then the PCP is decidable for virtually-C groups. Joint work with Laura Ciobanu and Alex Levine.