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?

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.

Update: An easier problem: is there an algorithm for solving the equation

$$u-v=x(p-q)y$$ (one summand)?


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

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.

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

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

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

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

  • $\begingroup$ @Pace: Thanks! Yes, coefficients are integers. This seems to work for the easier question. Now what to do with the original question? In principle, instead of $p-q, r-s$ there should be arbitrary given elements of the free ring (and arbitrary number of them). I do not even have intuition about what to expect: decidability or undecidability. On the one hand it is hard to imagine that this problem is undecidable. On the other hanmd it looks very similar to the Post correspondence problem. $\endgroup$ – Mark Sapir Jan 5 '11 at 17:59
  • $\begingroup$ My approach would be to first show that one can limit the alphabet to involve only variables appearing in the given words. Second, consider the cases when $p,q,r,s$ are distinct and when they are not. You might need to do subcases when $r$ and $s$ occur as subwords of $p$ and $q$... $\endgroup$ – Pace Nielsen Jan 5 '11 at 19:26
  • $\begingroup$ @Pace: I think you can assume that all words involve all letters in the alphabet and that all of them are distinct. The summands in $x(p−q)y$, $z(r−s)t$ and $u−v$ must cancel somehow. This certainly implies that u and v must have subwords from the set $\{p,q,r,s\}$. Also if $u=u′pu′′$ for some words $u',u''$, then $u′qu′′$ is one of the summands, it must cancel with one of the other summands, etc. This gives some tree of cases. But I cannot find any regularity in that tree. $\endgroup$ – Mark Sapir Jan 5 '11 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.