I was asked by Melvvyn Nathanson to give a talk last year at his summer number theory seminar at the CUNY grad center about problems of wild type and in what sense they are wild.

Many books, papers and lecture notes on representation theory make the following assertion: the first order theory of finite dimensional modules over the free algebra on two generators over a field can interpret the word problem for finitely generated groups and hence is undecidable. For example, type “wild representation type undecidability” into Google and see what comes up.

The sources usually cited for this result in fact prove the undecidability of the word problem for groups is encoded in the first order theory of **all** -modules, not just the finite dimensional modules. In fact the group algebra of a finitely presented group with undecidable word problem is the key module used in the proof and this is **never** finite dimensional. Willard used Slobodoskoi’s undecidability of the uniform word problem for finite groups to prove that if is a finite field, then the first order theory of finite dimensional -modules is undecidable.

My goal here is to put on the web a proof that the first order theory of a finite dimensional vector space with two distinguished endomorphisms is undecidable (over any field). There are two tools in this proof: Malcev’s theorem on residual finiteness of finitely generated linear semigroups and Gurevich’s theorem that the uniform word problem for finite semigroups is undecidable. No claim is made here to great originality. I am sure there are experts who know everything I am writing.

A result of Prest implies you can interpret the first order theory of two endomorphisms of a finite dimensional vector space into the finite dimensional representation theory of any finite acyclic quiver of wild representation type (as well as most examples of finite dimensional algebras of wild type). So the first order theory of finite dimensional representations of any wild type quiver is undecidable.

Continue reading →