Symbolics.jl simplify behaves differently for different variable names

[AronT-TLV]

Bug description
I was trying to simplify some expression and it didn’t work. Boiling it down to its simplest form, if I use different letters of the alphabet sometimes the exact same expression simplifies and sometimes it doesn’t. I give 5 examples below to show it’s not even the order of the alphabet. I also go in and out of the Julia REPL each time to be sure previous attempts don’t influence the next.

Version Info:

julia> versioninfo()
Julia Version 1.10.5
Commit 6f3fdf7b362 (2024-08-27 14:19 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: macOS (arm64-apple-darwin22.4.0)
  CPU: 12 × Apple M2 Max
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-15.0.7 (ORCJIT, apple-m1)
Threads: 1 default, 0 interactive, 1 GC (on 8 virtual cores)
Environment:
  JULIA_EDITOR = vi 

From the Project.toml
Symbolics = "0c5d862f-8b57-4792-8d23-62f2024744c7"

From the Manifest.toml

[[deps.SymbolicUtils]]
deps = ["AbstractTrees", "ArrayInterface", "Bijections", "ChainRulesCore", "Combinatorics", "ConstructionBase", "DataStructures", "DocStringExtensions", "DynamicPolynomials", "IfElse", "LinearAlgebra", "MultivariatePolynomials", "NaNMath", "Setfield", "SparseArrays", "SpecialFunctions", "StaticArrays", "SymbolicIndexingInterface", "TermInterface", "TimerOutputs", "Unityper"]
git-tree-sha1 = "9d983078d9e99421fcca44c373e4304b8421fdde"
uuid = "d1185830-fcd6-423d-90d6-eec64667417b"
version = "3.6.0"

Replicating the bug:

%  julia
…
using Symbolics
julia> @variables a  x y x̄ ȳ
5-element Vector{Num}:
 a
 x
 y
 x̄
 ȳ
 
 julia> simplify(a*y + a*ȳ)
a*(y + ȳ)

% julia
…
julia> using Symbolics

julia> @variables b  x y x̄ ȳ
5-element Vector{Num}:
 b
 x
y
 x̄
 ȳ

julia> simplify(b*y + b*ȳ)
b*y + b*ȳ
 
%  julia
…
julia> using Symbolics

julia> @variables c  x y x̄ ȳ
5-element Vector{Num}:
 c
 x
 y
 x̄
 ȳ

julia> simplify(c*y + c*ȳ)
c*(y + ȳ)

% julia                                                          
…  
julia> using Symbolics

julia> @variables d  x y x̄ ȳ
5-element Vector{Num}:
 d
 x
 y
 x̄
 ȳ

julia> simplify(d*y + d*ȳ)
d*y + d*ȳ

% julia
…
julia> using Symbolics

julia> @variables e  x y x̄ ȳ
5-element Vector{Num}:
 e
 x
 y
 x̄
 ȳ

julia> simplify(e*y + e*ȳ)
e*y + e*ȳ

[ChrisRackauckas]

I'm not sure there's anything odd here. It's just a property of a rewrite based rule system that the rule application order can change the result. The order in which the rules are applied can be a function of the lexicographical sorting, since that's the default sort ordering on the arguments.

[ufechner7]

@ChrisRackauckas Would you agree that this is just wrong:

julia> simplify(d*y + d*ȳ)
d*y + d*ȳ

The result is not simplified. Either there is a rule that identical factors should be drawn before the sum, using a bracket, or not. If there is such a rule it should always be applied.

[ChrisRackauckas]

But that's not this issue? This issue is about "strange random fashion". The answer is that it's not random and it's instead based on sort ordering which is a property inherent to rule-based rewriting systems since they are a greedy algorithm, and you'd need a non-greedy e-graph approach (which would be much more expensive too) in order to not have that property. So, case closed.

But yes, we should also improve the rewrite rules in simplify. That's a different discussion from the one in this thread.

[AronT-TLV]

@ChrisRackauckas
I get its not random and yes that is definitely the wrong description because the behavior is consistent. So I changed the description of the issue and hopefully that meets your objection.

Certainly from my perspective as a user of this package who doesn't understand the underlying algorithm in depth, even after reading your last response I have no idea why just changing the letter of the variable leads to different results on different runs. In other words I still don't understand why "a" works and "b" doesn't. So it seems there are two possibilities:

• Since I don't fully understand the behavior of the algorithm I am misunderstanding what simplify does and need guidance on how to choose variable name. This should be explained in the documentation or
• this is not how simplify should behave and is a bug

[ChrisRackauckas]

It's a bit of both. Lexicographical sorting means that different sort behaviors can change the out come of a rule-based eager pattern matching system. But the default results for simplify should improve to make this case better. Basically the rules that are defined need to be robust to that behavior.

So with the new issue here, yes that is something to handle which is why I didn't close the issue. Hopefully that makes sense.

[AronT-TLV]

Yes that explanation makes sense. Thanks!