# Is this a bug in NCAlgebra library?

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?

• I will say that some of this looks like very unhealthy behavior. Since rule1 changed from NoncommutativeMultiply to Times I would guess that the symbol b is leaking somewhere in such a way that rule1 was seen as scalar-(nc-)times-something and that allowed the type of product to change to ordinary Times. But that's just a vague guess and this is something the package authors would need to investigate. Dec 1 '14 at 20:49
• I will be very thankful if someone tested this independently; for now I am not entirely sure if this is a bug of NCAlgebra or a consequence of external factors. Dec 1 '14 at 21:36
• I do not have NCAlgebra but I can say that testing the parts that do not rely on that package gave different results from what you showed. Dec 1 '14 at 22:04
• It might be a good idea to contact the package author directly (and also point them to this thread). Dec 1 '14 at 22:06
• I am removing the bugs tag because the bug appears to be in the package and not Mathematica itself. Sep 22 '16 at 14:11

## 2 Answers

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.

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.