Suppose that $A_1, \dots, A_k \in M_n(\mathbb{Q})$ and $S$ is the semigroup generated by them. Two questions: are there always a finite set of relations $\{R_i\}$ among the $A_j$ such that $S$ is isomorphic to semigroup $\langle a_1, \dots, a_k | R_i\rangle$? By a relation I mean something of the form $w = w'$ where $w,w'$ are two words. If this is true, is it true that there is a bound on the length of the relations? That is, is there an $l$ which is a function of $n$, and perhaps the maximum absolute values of the entries of the $A_i$ so that we may always find a set of relations $R_i$ of length $\le l$?
$\begingroup$
$\endgroup$
6
asked Feb 3, 2010 at 22:02
-
$\begingroup$ Looks like it might be undecidable because of the word problem. $\endgroup$– Steve HuntsmanCommented Feb 3, 2010 at 22:27
-
$\begingroup$ But he word problem in matrix rings is trivially decidable. What I really wanted was that if you start listing words in the matrix generators in order of length and looking for coincidences, is there a point when you know that you've found a set of relations which generates them all. $\endgroup$– Victor MillerCommented Feb 4, 2010 at 2:45
-
$\begingroup$ Thanks for the answer. Yes, I really meant the putative bound to be a function of the height. My original problem (which I didn't state) really involved $M_n(\mathbb{Z})$ so that absolute value would be the same as height. $\endgroup$– Victor MillerCommented Feb 4, 2010 at 14:17
-
$\begingroup$ There are only finitely many such matrices, so conditional on the first part, there is a function of the height and n, but that doesn't say the function is computable. $\endgroup$– Douglas ZareCommented Feb 4, 2010 at 15:51
-
$\begingroup$ Ok, to be more specific, the kind of bound that I envision would be something like $H^{kn}$, where $H$ is the maximum height of a generator, $k$ is the number of generators, and $n$ is the dimension of the matrices. If one looks at a commutative case of Siegel's lemma en.wikipedia.org/wiki/Siegel%27s_lemma one gets a bound something like this, so one would expect $k$ and $n$ to enter into the exponent. One the other hand, I suspect that this may be the worse case. If the semigroup is far from being commutative then I might hope that one could do better. $\endgroup$– Victor MillerCommented Feb 4, 2010 at 16:12
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
1
Free semigroups on 2 generators have a faithful 2x2 representation over Z by sending the generators to
1 1
0 1
and its transpose. There are finitely generated subsemigroups of this free semigroup that are not finitely presented. I don't know who first proved this, but an example is in http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.98.795&rep=rep1&type=pdf
answered Jul 10, 2011 at 16:22
-
$\begingroup$ @Benjamin: Thanks. That shows that I was making too general a request. The real question that I'm interested in (should this be a separate MO question?) is: Let $A,B$ be non-commuting $n \times n$ matrices with coefficients in $\mathbb{Z}$ which generate a finite semigroup. Let $G$ denote the semigroup generated by $A+B,A-B$. Does $G$ have a finite presentation (with the given generators) with the kind of bound I asked for? $\endgroup$ Commented Jul 11, 2011 at 13:34
$\begingroup$
$\endgroup$
2
You are asking whether there is a faithful matrix representation of a finitely generated semigroup with no finite presentation. I don't know the answer to that. Note that only finitely many relations are needed to specify the representation variety $V_n$, so if the answer is yes, you would get a sequence of finitely presented semigroups with the same representation variety $V_n$, and thus a family of finitely presented semigroups with no faithful representation in dimension $n$. That's not a surprise, but it may be a way to look for an example.
Edit: Let me correct an example I had here before.
There is no bound on the length of relations possible for matrices with entries whose entries are at most 1, since you can represent the additive semigroup generated by 1 and $0\le p/q \le 1$, which is determined by commutativity and $p*1 = q * (p/q)$ in additive notation.
$$1\to \left( \begin{array}{cc} 1 & 1 \\\ 0 & 1\end{array}\right), ~~~~\frac pq \to \left( \begin{array}{cc} 1 & \frac pq \\\ 0 & 1\end{array}\right) $$.
Perhaps a bound would be possible not in terms of the magnitudes of the entries, but some other height function.
This type of example can be embedded in a slightly more complicated fashion when n=1, since you can have relations between 2, 3, and $2^p/3^q$ in the multiplicative semigroup of rationals. If that seems contrived because one of the generators is redundant, take 4, 9, and $2^{2p+1}/3^{2q+1}$.
answered Feb 4, 2010 at 4:51
-
$\begingroup$ Wait a moment. To represent Z/n over M_m(Q) requires m>= phi(n), I think. So you could imagine a bound which involved the number of generators and the size of the matrices. $\endgroup$ Commented Feb 4, 2010 at 12:32
-
$\begingroup$ Thanks. I didn't notice the Q instead of C. I replaced that example with a couple of others. $\endgroup$ Commented Feb 4, 2010 at 13:37