A new book: the representation theory of finite monoids

I am writing a book with Springer on the representation theory of finite monoids.  A preliminary version is here.  Comments and feedback are welcome.

The uniform word problem for finite semigroups

The goal of this post is to prove the following theorem of Gurevich. Stronger results have been proven by Mark Sapir and can be found in his survey with Olga Kharlampovich. The version stated here lets one prove the results of this post without appealing to Malcev’s theorem on residual finiteness.

Theorem. (Gurevich). There exists a finite set of relations over the alphabet and a word such that if is any class of semigroups containing all finite nilpotent semigroups and , then the following algorithmic problem is undecidable. Given a word , it is undecidable whether for every homomorphism with .

We recall here that a semigroup is nilpotent if for some and . Necessarily is a zero, that is, for all .

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 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.

Equalizers of free monoid morphisms, supports of rational power series and a question of Pin

In this mathoverflow question, J.-E. Pin asked if it is decidable whether the support of a -rational power series in non-commuting variables is a regular language. I pointed out that the answer is no and will elaborate here because it is fairly cute.

Isomorphism of oriented matroids from a semigroup viewpoint

This is in some sense a sequel to this post. Basically, I want to show that the somewhat awkward, in my opinion, definition of isomorphism of oriented matroids found, for example, here can be interpreted as isomorphism of underlying unary monoids. Moreover, we will show that a unary monoid is the underlying monoid of an oriented matroid if and only if a certain “Gelfand” representation by covectors is faithful and yields an oriented matroid.

Hyperplane face semigroups and zonotopes

Hyperplane face semigroups have attracted interest in recent years due to applications to Markov chains, descent algebras and buildings. Here I’ll describe an alternative way to think about hyperplane face semigroups from the zonotope view point.

Endomorphism monoids of finite topological spaces

This post is inspired by this Mathoverflow question.

The question asks when a transformation monoid on a set can be the monoid of all continuous maps for some topology on . The OP observes that the monoid must contain all constant maps and asks what else, if anything is needed.

This question is equivalent to asking which monoids can be represented as endomorphism monoids of a topological space. Indeed, a transformation monoid containing all constant maps is the same thing as a monoid whose minimal ideal consists of left zeroes and acts faithfully on the left of it. (Note my functions act on the left.) So if for a topological space , then is the minimal ideal of with some topology.

Combinatorics on Words

I am recording here some neat proofs of some theorems on combinatorics on words. No great originality is claimed.

Welcome to Semigroups

This is my new blog. I’m not sure how often I will get around to posting, but I’ll try to be doing it from time to time.