Repository: sympy/sympy
Pull request: fail when no subset solves poly system; better removal of redundant solutions
<!-- Your title above should be a short description of what
was changed. Do not include the issue number in the title. -->

Until the Groebner approach is used to solve systems of polynomials, it might be advantageous to try solve the equations with the traditional methods (instead of a system-of-equations approach). The added test fails to solve as a system, but a solution can be found.

#### References to other Issues or PRs
<!-- If this pull request fixes an issue, write "Fixes #NNNN" in that exact
format, e.g. "Fixes #1234" (see
https://tinyurl.com/auto-closing for more information). Also, please
write a comment on that issue linking back to this pull request once it is
open. -->
closes #27001

#### Brief description of what is fixed or changed


#### Other comments


#### Release Notes

<!-- Write the release notes for this release below between the BEGIN and END
statements. The basic format is a bulleted list with the name of the subpackage
and the release note for this PR. For example:

* solvers
  * Added a new solver for logarithmic equations.

* functions
  * Fixed a bug with log of integers. Formerly, `log(-x)` incorrectly gave `-log(x)`.

* physics.units
  * Corrected a semantical error in the conversion between volt and statvolt which
    reported the volt as being larger than the statvolt.

or if no release note(s) should be included use:

NO ENTRY

See https://github.com/sympy/sympy/wiki/Writing-Release-Notes for more
information on how to write release notes. The bot will check your release
notes automatically to see if they are formatted correctly. -->

<!-- BEGIN RELEASE NOTES -->
* solvers
    * better removal of redundant solutions from systems of equations
    * positive-dimensional systems of polynomials which raised an error may now report a solution
<!-- END RELEASE NOTES -->


Problem statement:
Possible bug with sympy.solve
For some systems of equations, sympy.solve can succeed when solving with respect to a subset of variables but raises an error when asked to solve with respect to a large set containing that variable set (containing that subset). This seems like a bug, as it should at least be able to find the same solutions it could find with the smaller variable set.

Here is a minimal example.
The following code can be executed without an error:
```
from sympy import symbols, solve
a1,a2,a3=symbols(['a1','a2','a3'])
eqnSystem=[a1, a1**2]
solve(eqnSystem,[a1,a2],dict=True)
```

But  an error will be raised if the following line is then executed:
```
solve(eqnSystem,[a1,a2,a3],dict=True)
```
The error raise is *no valid subset found*.

If solve can solve the system with respect to `[a1,a2]`, shouldn't it also be able to find some solution with respect to `[a1,a2,a3]`?

Hints from issue discussion:
This comes from SO:
https://stackoverflow.com/questions/78913691/why-might-sympy-solve-succeed-with-respect-to-fewer-variables-but-fail-w-r-t-mo

This is the error:
```python
In [2]: solve([x, x**2], [x, y, z])
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
Cell In[2], line 1
----> 1 solve([x, x**2], [x, y, z])

File ~/current/active/sympy/sympy/solvers/solvers.py:1172, in solve(f, *symbols, **flags)
   1170         solution = _solve(f[0], *symbols, **flags)
   1171 else:
-> 1172     linear, solution = _solve_system(f, symbols, **flags)
   1173 assert type(solution) is list
   1174 assert not solution or type(solution[0]) is dict, solution

File ~/current/active/sympy/sympy/solvers/solvers.py:1896, in _solve_system(exprs, symbols, **flags)
   1894         solved_syms = list(got_s)
   1895     else:
-> 1896         raise NotImplementedError('no valid subset found')
   1897 else:
   1898     try:

NotImplementedError: no valid subset found
```
The problem comes from the overly complicated looking code here:
https://github.com/sympy/sympy/blob/9ae79a9b5802d2697e0644895e91734c33be5a1b/sympy/solvers/solvers.py#L1869-L1896
I don't know what that is doing but it should be rewritten some other way.

Calling `solve_poly_system` in a loop of combinatoric size should not happen...
The following still fails: subsets should additionally not exceed the length of equations.
```
from sympy import symbols, solve
s=a1,a2,a3,a4,a5=symbols(['a1','a2','a3','a4','a5'])
eqnSystem3=[8*a1**4*a2 + 4*a1**2*a2**3 - 8*a1**2*a2*a4 + a2**5/2 - 2*a2**3*a4 + 8*a2*a3**2 + 2*a2*a4**2 + 8*a2*a5, 12*a1**4 + 6*a1**2*a2**2 - 8*a1**2*a4 + 3*a2**4/4 - 2*a2**2*a4 + 4*a3**2 + a4**2 + 4*a5, 16*a1**3 + 4*a1*a2**2 - 8*a1*a4, -8*a1**2*a2 - 2*a2**3 + 4*a2*a4]
solve(eqnSystem3,s,dict=True)
```

Commit message: update existing soln

When testing to see if a solution is a superset of another, update the other with the values of the solution being tested, first.

Patch to review:
diff --git a/sympy/solvers/solvers.py b/sympy/solvers/solvers.py
index 869c8aa7fdc0..b1210a2baaf6 100644
--- a/sympy/solvers/solvers.py
+++ b/sympy/solvers/solvers.py
@@ -1893,7 +1893,7 @@ def _solve_system(exprs, symbols, **flags):
                 if got_s:
                     solved_syms = list(got_s)
                 else:
-                    raise NotImplementedError('no valid subset found')
+                    failed.extend([g.as_expr() for g in polys])
             else:
                 try:
                     result = solve_poly_system(polys, *symbols)
@@ -1985,10 +1985,13 @@ def key(sym):
                         # check that it is independent of previous solutions
                         iset = set(rnew.items())
                         for i in newresult:
-                            if len(i) < len(iset) and not set(i.items()) - iset:
-                                # this is a superset of a known solution that
-                                # is smaller
-                                break
+                            if len(i) < len(iset):
+                                # update i with what is known
+                                i_items_updated = {(k, v.xreplace(rnew)) for k, v in i.items()}
+                                if not i_items_updated - iset:
+                                    # this is a superset of a known solution that
+                                    # is smaller
+                                    break
                         else:
                             # keep it
                             newresult.append(rnew)
diff --git a/sympy/solvers/tests/test_solvers.py b/sympy/solvers/tests/test_solvers.py
index 6f8275ee3197..b93f6e9f8e78 100644
--- a/sympy/solvers/tests/test_solvers.py
+++ b/sympy/solvers/tests/test_solvers.py
@@ -2571,6 +2571,14 @@ def test_issue_20747():
 
 def test_issue_27001():
     assert solve((x, x**2), (x, y, z), dict=True) == [{x: 0}]
+    s = a1, a2, a3, a4, a5 = symbols('a1:6')
+    eqs = [8*a1**4*a2 + 4*a1**2*a2**3 - 8*a1**2*a2*a4 + a2**5/2 - 2*a2**3*a4 +
+        8*a2*a3**2 + 2*a2*a4**2 + 8*a2*a5, 12*a1**4 + 6*a1**2*a2**2 -
+        8*a1**2*a4 + 3*a2**4/4 - 2*a2**2*a4 + 4*a3**2 + a4**2 + 4*a5, 16*a1**3
+        + 4*a1*a2**2 - 8*a1*a4, -8*a1**2*a2 - 2*a2**3 + 4*a2*a4]
+    assert solve(eqs, s, dict=True) == [
+        {a4: 2*a1**2 + a2**2/2, a5: -a3**2}, {a1: 0, a2: 0, a5: -a3**2 - a4**2/4},
+        {a1: 0, a4: a2**2/2, a5: -a3**2}]
 
 
 def test_issue_20902():


Code review comments:
diff_hunk: @@ -2571,6 +2571,14 @@ def test_issue_20747():
 
 def test_issue_27001():
     assert solve((x, x**2), (x, y, z), dict=True) == [{x: 0}]
+    s = a1, a2, a3, a4, a5 = symbols('a1:6')
+    eqs = [8*a1**4*a2 + 4*a1**2*a2**3 - 8*a1**2*a2*a4 + a2**5/2 - 2*a2**3*a4 +
+        8*a2*a3**2 + 2*a2*a4**2 + 8*a2*a5, 12*a1**4 + 6*a1**2*a2**2 -
+        8*a1**2*a4 + 3*a2**4/4 - 2*a2**2*a4 + 4*a3**2 + a4**2 + 4*a5, 16*a1**3
+        + 4*a1*a2**2 - 8*a1*a4, -8*a1**2*a2 - 2*a2**3 + 4*a2*a4]
+    assert solve(eqs, s, dict=True) == [
+        {a4: 2*a1**2 + a2**2/2, a5: -a3**2}, {a1: 0, a2: 0, a5: -a3**2 - a4**2/4},
+        {a1: 0, a4: a2**2/2, a5: -a3**2}]
path: sympy/solvers/tests/test_solvers.py
text: @author:
```suggestion
        {a4: 2*a1**2 + a2**2/2, a5: -a3**2}, {a1: 0, a2: 0, a5: -a3**2 - a4**2/4}]
```