Is this a bug in NCAlgebra library?

Question

In course of my work with NCAlgebra package for Mathematica, http://math.ucsd.edu/~ncalg/ , I encountered unexpected behavior of replacements. I am using Mathematica 8 with compatible version of NCAlgebra, 4.0.4. I would like to rule out the possibility of botched installation of NCAlgebra, although on my computer it seems to pass all in-built tests.

I define two very similar transformation rules and an expression to use them on:

<<NC`    
<<NCAlgebra`
rule1 = b_ ** a_ :> -a ** b;
rule2 = HoldPattern[b_ ** a_] :> -a ** b;
expr = -x ** x ** y - y ** x;

Now I apply these rules using two different methods: Substitute and ReplaceAll:

expr /. rule1
SubstituteSingleReplace[expr, rule1]
expr /. rule2
SubstituteSingleReplace[expr, rule2]
  (*result*)
x ** y - x ** x ** y
x ** y + x ** x ** y
x ** y - x ** x ** y
x ** y - x ** x ** y

Nothing special, Substitute and ReplaceAll are expected to work a little differently.

b=2;
rule1
expr /. rule1
SubstituteSingleReplace[expr, rule1]
expr /. rule2
SubstituteSingleReplace[expr, rule2]

Now things become strange. rule1 now looks differently - non-commutative multiplication ** is replaced by commutative product Times:

b_ a_ :> -a ** b

The results of replacements look really weird (note that the change in result of ReplaceAll is likely due to change of the rule)

y ** x + x ** x ** y
-2 y ** x - 2 x ** x ** y
x ** y - x ** x ** y
2 x - x ** x ** y

Are the inner workings of the pattern are affected by the definitions of global variables? I thought previosly that this behavior can be negated by using HoldPattern[_], but with this example it is proved ineffective.

What can be done to fix this?

Answer 1

You should try the newest version of NCAlgebra:

https://github.com/NCAlgebra/NC

In version 5.0.0, Substitute and Transform were replaced by the more reliable NCReplace, NCReplaceAll, and NCReplaceRepeated. These closely mirror the corresponding Mathematica Replace commands. In your example:

<< NC`
<< NCAlgebra`
rule1 = b_ ** a_ :> -a ** b;
rule2 = HoldPattern[b_ ** a_] :> -a ** b;
rule3 = b_ ** a_ -> -a ** b;
expr = -x ** x ** y - y ** x

all three substitutions:

NCReplaceAll[expr, rule1]
NCReplaceAll[expr, rule2]
NCReplaceAll[expr, rule3]

result in:

x ** y + x ** y ** x

Be careful with such rules though as you are relying on Mathematica's pattern matching to select which of the two "sides" of x**x**y get swapped. For example:

expr = -y ** x ** z - y ** x
NCReplaceAll[expr, rule1]

results in

x ** y + x ** z ** y

not

x ** y + z ** y ** x

Your rule also generates an infinite recursion if used with NCReplaceRepeated.

Answer 2

There are two related bugs. SubstituteSingleReplace calls RulesComplement to construct a list of rules and their opposites (so in your case b_ ** a_ :> -a ** b and -b_ ** a_ :> a ** b). Unfortunately, the function incorrectly uses Rule when given a RuleDelayed (my In[1] was loading the package):

In[2]:= RulesComplement[b_ ** a_ :> -a ** b]
Out[2]= {b_ ** a_ :> -a ** b, -b_ ** a_ -> a ** b}

This is not trivial to fix. One option without touching the package is to patch the DownValues of RulesComplement:

DownValues[RulesComplement] = (DownValues[RulesComplement] /.
   Which[pre___, lhs_ === RuleDelayed, Rule[a_, -#1[[2]]], post___] :>
   Which[pre,
     lhs === RuleDelayed, 
     RuleDelayed[a, Evaluate[Extract[#1, {2}, Function[{x}, Unevaluated[-x], HoldAll]]]], 
     post])

This code finds the Which statement in the definition of RulesComplement, specifically the clause treating RuleDelayed, and essentially replaces Rule by RuleDelayed. This is complicated by the fact that we want the part #1[[2]] (right-hand side of the rule) to be extracted but not further evaluated.

The second bug is in SubstituteSingleReplace itself: it splits each rule into left-hand side and right-hand side and evaluates both. This is done in order to construct a more general rule that will match NonCommutativeMultiply with more arguments.

Instead of fixing it, I suggest using the following code (after you fix RulesComplement) instead of SubstituteSingleReplace.

With[{pre = Unique[], post = Unique[]},
  SetNonCommutative[pre, post];
  mySubstituteSingleReplace[expr_, rules_] :=
    expr /.
      (RulesComplement[Flatten[{rules}]] /.
        (f : Rule | RuleDelayed)[lhs_, rhs_] :> 
        f[pre___ ** lhs ** post___, pre ** rhs ** post])
]

First find the rules with their opposites, then construct rules which allow additional factors in the NonCommutativeMultiply, namely rules of the form pre___ ** lhs ** post___ :> pre ** rhs ** post. This is straightforward for RuleDelayed, but for Rule we have to be careful that the right-hand side of the new rule is evaluated and pre and post could have values. This is the reason for using Unique[]. The code does not deal correctly with HoldPattern, so your rule2 isn't supported, sorry.