I am writing a book with Springer on the representation theory of finite monoids. A preliminary version is here. Comments and feedback are welcome.
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.
Posted in Math
Tagged logic, Math
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.
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.
Posted in Math
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.
Posted in Math
Tagged Math, Semigroups