Let $V$ be a finite dimensional vector space over a field $K$ of characteristic zero. Assume that we are given a set of (not necessarily homogeneous) elements $f_1,\ldots f_n$ in the tensor algebra $T(V)$. How can we decide if the ideal $I$ generated by the elements $f_i$ is the entire ring $T(V)$ or not? Is there any particular algorithm which is suitable for this problem? I am not interested in the particular structure of the ring $T(V)/I$, but only in the question of whether or not it is trivial. Another related question: how can we decide if $T(V)/I$ is finite dimensional or not?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
It is well known that the analogous question is undecideable for Groups. (By Encoding a Turing machine into the Generators and relations and using undecideablity theorems like the undecideabilty of the halting Problem there.)
You can expect that the question for algebras is undecideable as well, as you can for example encode Groups (or Turing machines) in your Algebra.
-
$\begingroup$ Thanks for the answer. Do you know if there are some results if the dimension of $V$ and the degree of the $f_i$ polynomials are restricted? In my case $V$ is of dimension 3, and there are 5 polynomials, of degree 2 (that is- containing monomials of degree at most 2) $\endgroup$ Mar 20, 2016 at 20:38
-
$\begingroup$ Unfortunately no. But I heard about examples in the Group case with only 2 or 3 relators and only 1 or 2 Relations which are up to now not known if they are trivial. Don't expect a solution in your case. Even in the smallest examples practically undecideable. $\endgroup$– hänselMar 20, 2016 at 20:43
-
$\begingroup$ @hänsel I'm confused by your last statement. Do you mean that it is not known whether the triviality problem is decidable for group presentations with say, 2 generators and 3 relators? (btw this gives no bound on the degree of the corresponding polynomials in the group algebra) or do you refer to specific examples of presentations (then, this has little to do with the undecidability issue) $\endgroup$– YCorMar 20, 2016 at 22:28
-
$\begingroup$ @ycor: no, I mean there exist concrete single examples with very few relators and very few, simple and short Relations which are unknown whether they present the trivial Group. $\endgroup$– hänselMar 20, 2016 at 22:35
-
$\begingroup$ Although this is undecidable there is the Knuth-Bendix aka noncommutative Groebner basis algorithm. This is implemented in magna, in the GAP package GBNP in Bergman and possibly in other places. If one of these terminates you are in luck, if not, you can't conclude anything. $\endgroup$– BWWMar 22, 2016 at 15:47