# Create pattern to "redo" Nest for symbolic purposes, e.g. for commutators

I am symbolically working with matrix commutators (comm) and face the following issue: There are nested commutators in my final results, defined as

NestedComm[mat1_, mat2_, n_] /; n > 1 := comm[NestedComm[mat1, mat2, n - 1], mat2];
NestedComm[mat1_, mat2_, 1] := comm[mat1, mat2];
NestedComm[mat1_, mat2_, 0] := mat1;


which due to the nature of the algorithm appear for instance as comm[comm[comm[a,b],b],b] in my final expressions. Note that the level of nesting n can in principle be anything from one to infinity. In order to make the results more readable, I am looking for a pattern or something else that would transform comm[comm[comm[a, b], b], b] to nestedComm[a,b,3] (the lowercase letter would be intended to avoid evaluation of the actual definition and to avoid the need of messing around with Hold and the like). The pattern should of course only apply if it is really a nested commutator according to the definition of NestedComm - there are also terms like comm[comm[comm[a,b],c],b] which should stay untouched by the transformation.

Is it somehow possible to automatically recognize this type of Nested functions and the corresponding level of nesting in order to replace them with a shorthand notation?

Update: It has not been clear from the question, that I do not want the nested comm[]objects to simplify automatically everywhere. Actually, my algorithm relies on them not being transformed to nestedComm[] throughout many steps of computation. But since the expressions may become quite involved and long, I would like to use a replacement rule/function/... on the final result, so that the nested objects are only simplified where I want them to be.

You might use transformation rules to transform nested commutators to nestedComm :

nestedCommRules = {
comm[comm[a_, b_], b_] :> nestedComm[a, b, 2],
nestedComm[comm[a_, b_], b_, n_] :> nestedComm[a, b, n + 1]
}


(It's possible that you may want to include comm[nestedComm[a_, b_, n_], b_] :> nestedComm[a, b, n + 1] as well, but you don't need it for your example above.)

Then you can do

comm[comm[comm[a, b], b], b] //. nestedCommRules
(* nestedComm[a, b, 3] *)

comm[comm[comm[a, b], c], b] //. nestedCommRules
(* comm[comm[comm[a, b], c], b] *)


You mentioned pattern matching, so I'm not sure this answers your question fully. Hopefully it's a start.

Note that you can use NestedComm instead of nestedComm if you implemented the original definitions of NestedComm using transformation rules rather than SetDelayed, but this is of course your choice.

• Forgot about the power of ReplaceRepeated in this situation, thank you very much for pointing me to it! Apr 12, 2017 at 17:05
• I appreciate the accept, but I would highly recommend waiting a while. Someone could very well give you a better answer -- there's a lot more to expression manipulation that I don't understand. Apr 12, 2017 at 17:06
• Ok, I will then wait another few days for people to reply ;) Apr 12, 2017 at 17:07

## Speed

We can make jjc385's operation far more efficient by replacing from the inside out, rather than repeatedly scanning the entire expression from the top down using //., as explained in How to remove redundant {} from a nested list of lists? and elsewhere.

Updated to scan only down to levelspec -3 for slightly improved efficiency.

Let's compare performance on a deeply nested expression.

nestedCommRules = {comm[comm[a_, b_], b_] :> nestedComm[a, b, 2],
nestedComm[comm[a_, b_], b_, n_] :> nestedComm[a, b, n + 1]};

inOutRules = {comm[comm[a_, b_], b_] :> nestedComm[a, b, 2],
comm[nestedComm[a_, b_, n_], b_] :> nestedComm[a, b, n + 1]};

deep = Nest[comm[#, b] &, a, 5000];

deep //. nestedCommRules            // RepeatedTiming
Replace[deep, inOutRules, {0, -3}]  // RepeatedTiming

{0.234, nestedComm[a, b, 5000]}

{0.00388, nestedComm[a, b, 5000]}


## Simplicity

I would encourage you to consider a different form that makes replacement simpler: comm[a, b, 3] to represent comm[comm[comm[a, b], b], b].

deep = Nest[comm[#, b] &, a, 5000];

rule = comm[comm[a_, b_, n_: 1], b_] :> comm[a, b, n + 1];

Replace[deep, rule, {0, -3}] // RepeatedTiming

{0.00455, comm[a, b, 5000]}


If that format won't work for you then perhaps:

rule =
comm[(nestedComm | comm)[a_, b_, n_: 1], b_] :> nestedComm[a, b, n + 1];

Replace[deep, rule, {0, -3}] // RepeatedTiming

{0.00473, nestedComm[a, b, 5000]}

• Sorry for the late response. Thank you very much for your answer and suggestions about the form of comm. Indeed, it is perfectly fine for me to use comm[a,b,x] to display nested commutators. Apr 25, 2017 at 13:04

An alternative is to use TagSetDelayed[] to set rules on how your comm[] and nestedComm[] objects should act. For instance:

comm /: comm[comm[x_, y_], y_] := nestedComm[x, y, 2];

comm /: comm[nestedComm[x_, y_, k_Integer?NonNegative], y_] := nestedComm[x, y, k + 1]


After evaluating those:

comm[comm[comm[a, b], b], b]
nestedComm[a, b, 3]

comm[comm[comm[a, b], c], b]
comm[comm[comm[a, b], c], b]

• Thank you very much. Didn't know about TagSetDelayed until now. Very interesting. As I understand, there is no possibility to use this only in some expressions, right? I would evaluate comm /: ..., then reevaluate the expression in question and afterwards need to ClearAll[comm] again in order to not use the rules in subsequent computation? Apr 13, 2017 at 10:03
• Wait, you don't always want the nested comm[] objects to automatically simplify? Apr 13, 2017 at 10:17
• Right, sorry if that wasn't clear. Actually it is important that they are not simplified throughout my algorithm. But I would like to use some rule/function/... on my final result so that the nested comm[]objects are only simplified there. Will make that clearer in the question Apr 13, 2017 at 10:20
• In that case, jjc's replacement rules are definitely the way to go, and not this. Apr 13, 2017 at 10:23
• Right, but for a future application, your solution might be more applicable. Appreciate your answer anyways, although there was missing information on my side - sorry for that Apr 13, 2017 at 10:25