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.

We consider a first order language in which we have a binary relation symbol =, a binary operation symbol +, a unary operation – (think negation), two unary function symbols and a constant . We do not include unary function symbols for scalars because we can already express undecidable statements in this limited language!

If consists of a vector space over a field together with two endomorphisms of , then we can interpret variables as elements of and in the usual way. We interpret and by and . So for instance, if and only if is invertible.

If is a field, we denote by the set of all sentences in our first order language that are true in every model with a finite dimensional -vector space and . Our goal is to prove is undecidable, that is, there is no algorithm to determine whether a sentence in our first order language is true in all finite dimensional -vector spaces with a pair of distinguished endomorphisms.

Recall that a semigroup is *residually finite* if, for all with , there is a homomorphism with a finite semigroup and . The following theorem of Malcev is usually stated for groups but the proof actually gives the result for semigroups.

**Theorem 1.** (Malcev)

*Every finitely generated semigroup of matrices over a field is residually finite.*

As a consequence, we obtain the following corollary.

**Corollary 2.** *Suppose is a finitely generated semigroup and . Then cannot be separated by homomorphisms into finite semigroups if and only if cannot be separated by finite dimensional representations over .*

*Proof.* If is a homomorphism with finite and , then the composition of with the regular representation of (where denotes the result of adding an identity to ) gives a finite dimensional representation separating and .

Conversely, if is a representation with , then because is residually finite by Malcev’s theorem, we can find a homomorphism with finite such that .

Gurevich proved that the uniform word problem for finite semigroups is undecidable. More precisely, he proved that there is a finitely presented semigroup such that it is undecidable given words over whether and can be separated by homomorphisms into finite semigroups, i.e., one cannot decide if is a consequence of the relations in finite semigroups.

**Theorem 3.** *For any field , the theory of finite dimensional vector spaces over with two distinguished endomorphisms is undecidable.*

*Proof.* Let be the semigroup above from Gurevich’s theorem. Let be words over and consider the sentence One has that if and only if , induces a representation of . Thus for all with finite dimensional over if and only if cannot be separated by finite dimensional representations over . Corollary 2 then implies that this occurs if and only if cannot be separated by homomorphisms into finite semigroups. It follows from Gurevich’s theorem that we cannot decide whether . This proves the theorem.

One can similarly, prove the undecidability of the theory of a finite dimensional vector space together with two distinguished automorphisms using the exact same proof scheme as above, but using Slobodoskoi’s theorem in place of Gurevich’s theorem.

**Update.** I’m thinking of writing a future post with a proof of Gurrvich’s theorem. His proof shows something stronger than what I have stated, which in particular allows one to avoid the use of Malcev’s theorem in proving the undecidability of the first order theory of a finite dimensional vector space with two endomorphisms.

In fact, using the details of Gurevich’s proof I think one can replace fields by any base ring with identity (commutative is not necessary). If one so desires one can even assume the endomorphisms are nilpotent of index 2.

Pingback: The uniform word problem for finite semigroups | Semigroups: a personal perspective