The first order theory of two endomorphisms of a finite dimensional vector space is undecidable

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 \Bbbk 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 \Bbbk\langle a,b\rangle-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 \Bbbk is a finite field, then the first order theory of finite dimensional \Bbbk\langle a,b\rangle-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 a,b and a constant 0. We do not include unary function symbols for scalars because we can already express undecidable statements in this limited language!

If (V,A,B) consists of a vector space V over a field \Bbbk together with two endomorphisms A,B of V, then we can interpret variables as elements of V and =,+,-,0 in the usual way. We interpret a and b by A and B. So for instance, (V,A,B)\models \forall x(ax=0\rightarrow x=0)\wedge \forall y\exists x(ax=y) if and only if A is invertible.

If \Bbbk is a field, we denote by T_\Bbbk the set of all sentences in our first order language that are true in every model (V,A,B) with V a finite dimensional \Bbbk-vector space and A,B\in \mathrm{End}(V). Our goal is to prove T_\Bbbk is undecidable, that is, there is no algorithm to determine whether a sentence \varphi in our first order language is true in all finite dimensional \Bbbk-vector spaces with a pair of distinguished endomorphisms.

Recall that a semigroup S is residually finite if, for all s,s'\in S with s\neq s', there is a homomorphism f\colon S\to T with T a finite semigroup and f(s)\neq f(s'). 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 S is a finitely generated semigroup and s,s'\in S. Then s,s' cannot be separated by homomorphisms into finite semigroups if and only if s,s' cannot be separated by finite dimensional representations over \Bbbk.
Proof. If f\colon S\to T is a homomorphism with T finite and f(s)\neq f(s'), then the composition of f with the regular representation T\to \mathrm{End}(\Bbbk T^1) of T (where T^1 denotes the result of adding an identity to T) gives a finite dimensional representation separating s and s'.

Conversely, if f\colon S\to M_n(\Bbbk) is a representation with f(s)\neq f(s'), then because f(S) is residually finite by Malcev’s theorem, we can find a homomorphism g\colon f(S)\to T with T finite such that gf(s)\neq gf(s').

Gurevich proved that the uniform word problem for finite semigroups is undecidable. More precisely, he proved that there is a finitely presented semigroup S=\langle a,b\mid u_1=v_1,\ldots, u_n=v_n\rangle such that it is undecidable given words u,v over a,b whether u and v can be separated by homomorphisms into finite semigroups, i.e., one cannot decide if u=v is a consequence of the relations u_1=v_1,\ldots, u_n=v_n in finite semigroups.

Theorem 3. For any field \Bbbk, the theory T_\Bbbk of finite dimensional vector spaces over \Bbbk with two distinguished endomorphisms is undecidable.
Proof. Let S=\langle a,b\mid u_1=v_1,\ldots, u_n=v_n\rangle be the semigroup above from Gurevich’s theorem. Let u,v be words over a,b and consider the sentence \varphi_{u,v}= \forall x\left((u_1x=v_1x)\wedge (u_2x=v_2x)\wedge \cdots\wedge (u_nx=v_nx)\right)\rightarrow \forall x(ux=vx). One has that (V,A,B)\models \forall x\left((u_1x=v_1x)\wedge (u_2x=v_2x)\wedge \cdots\wedge (u_nx=v_nx)\right) if and only if a\mapsto A, b\mapsto B induces a representation of S. Thus (V,A,B)\models \varphi_{u,v} for all (V,A,B) with V finite dimensional over \Bbbk if and only if u,v cannot be separated by finite dimensional representations over \Bbbk. Corollary 2 then implies that this occurs if and only if u,v cannot be separated by homomorphisms into finite semigroups. It follows from Gurevich’s theorem that we cannot decide whether \varphi_{u,v}\in T_{\Bbbk}. 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.

Advertisements

About Benjamin Steinberg

Mathematician interested in semigroups, groups and automata.
This entry was posted in Math and tagged , . Bookmark the permalink.

One Response to The first order theory of two endomorphisms of a finite dimensional vector space is undecidable

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s