most recent 30 from http://mathoverflow.net 2013-05-24T14:46:28Z http://mathoverflow.net/feeds/question/51170 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/51170/an-equation-in-the-free-associative-ring Mark Sapir 2011-01-05T01:04:30Z 2011-01-05T17:52:50Z

<p>Let $X$ be an alphabet, $u,v,p,q,r,s$ be words in the alphabet $X$. I am looking for four elements in the free associative ring $R$ (i.e. four linear combinations of words in $X$) $x,y,z,t$ such that $$u-v=x(p-q)y+z(r-s)t.$$ Is this problem decidable? </p> <p>The problem is motivated by the need to define an analog of Dehn functions for associative rings. In groups, the Dehn function is recursive iff the word problem is decidable. The question (asked by E. Zelmanov) is whether the same is true for rings. </p> <p><b> Update: </b> An easier problem: is there an algorithm for solving the equation</p> <p>$$u-v=x(p-q)y$$ (one summand)?</p>

http://mathoverflow.net/questions/51170/an-equation-in-the-free-associative-ring/51226#51226 Pace Nielsen 2011-01-05T17:52:50Z 2011-01-05T17:52:50Z

<p>If I understand your question, the answer to your easier problem is yes. (I'm assuming that by the free associative ring over $X$ you mean to take coefficients of words over the integers.)</p> <p>First, you can order words in the alphabet, initially by degree, and then by ordering elements in $X$ and using a lexicographical ordering on words of equal degree.</p> <p>Case 1: $u=v$. Then if $p=q$ you can let $x,y$ be arbitrary. If $p\neq q$ then either $x=0$ or $y=0$.</p> <p>Case 2: $u\neq v$. Clearly $p\neq q$. Without loss of generality, we may assume that $u$ is of larger order than $v$, and also that $p$ is of larger order than $q$ (replacing $x$ by $-x$ if necessary).</p> <p>Let $x'$ be the term from $x$ with largest order, and let $x''$ be the term (with non-zero support) with smallest order (these might agree), and similarly define $y',y''$. We must then have $x'py'=u$ and $x''qy''=v$. There are thus only finitely many choices for $x',x'',y',y''$. </p> <p>But then there are only finitely many choices for terms between $x'$ and $x''$ if we limit ourselves to words in elements of $X$ appearing in $u,v,p,q$. If $x$ involved a term with an element of the alphabet $X$ not appearing in those four words, a simple argument tells us that $x(p-q)y$ would have a term that cannot cancel involving that variable, hence could not equal $u-v$. Thus, there are only finitely terms to try (and letting the coefficients be arbitrary constants, you get a system of linear equations).</p>