interface sympy Diophantine function(s)

[rws]

In sympy the solution of Diophantine equations is available for several types of equations (​http://docs.sympy.org/latest/modules/solvers/diophantine.html). This meta-ticket aims at

• implementing a global solve_diophantine() function that wraps the sympy functionality and takes
  1. symbolic expressions (up to order 2)
  2. univariate polynomials (up to order 2)
  3. multivariate polynomials (up to order 2)
  4. quadratic forms
• where useful implementing member functions solve_diophantine()

It is however not possible to directly make the resp. sympy functions fully usable with Sage, from within Sage. If desired that must be done in sympy.

Until then there is the following workaround:

sage: from sympy.solvers.diophantine import *
sage: from sympy import sympify
sage: var('x,y,m')
(x, y, m)
sage: diop_solve(sympify(x**2 + y**2 - 5))
{(-2, -1), (-2, 1), (2, -1), (2, 1)}
sage: diop_solve(sympify(x**2 - 3*y**2 - 1))
{(-sqrt(3)*(-sqrt(3) + 2)**t/2 + (-sqrt(3) + 2)**t + sqrt(3)*(sqrt(3) + 2)**t/2 + (sqrt(3) + 2)**t,
  -sqrt(3)*(-sqrt(3) + 2)**t/3 + (-sqrt(3) + 2)**t/2 + (sqrt(3) + 2)**t/2 + sqrt(3)*(sqrt(3) + 2)**t/3)}

[rws]

However, the last solution shown in the workaround is incomplete, see ​https://github.com/sympy/sympy/issues/7671. Still, it would be good to have the functionality at hand in Sage.

[rws]

sage: sage: from sympy.solvers.diophantine import *
sage: sage: from sympy import sympify
sage: diop_solve(sympify(x*y-10))
{(-10, -1), (-5, -2), (-2, -5), (-1, -10), (1, 10), (2, 5), (5, 2), (10, 1)}

sage: solve(x*y==10,x)
[x == 10/y]
sage: assume(x,'integer')
sage: assume(y,'integer')
sage: solve(x*y==10,x,y,solution_dict=True)
([{x: 10/y}], [1])

Solve with assumption 'integer' for all variables should definitely call diop_solve(), but also the shorter solve_diophantine(expr) without assumptions should be available. Not sure what the output of [1] above means.

[rws]

Irrelevant comment deleted. Sorry.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​827e505

16590: add documentation

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​e598b2c	16590: fix doctests
​d9989ed	16590: roll back changes to quadratic_forms/; finish documentation

[rws]

This is completed IMO, modulo the review. The failing doctest depends on #16624, so I'll wait with setting 'needs review' for that.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​1568fe4	Merge branch 'develop' into t/16590/interface_sympy_diophantine_function_s_
​6365073	shortened patch
​04d8d62	remove doc/src/modules/mpmath from patch; remove files via spkg-install
​4c9f288	16624: remove mpmath/tests/__init__.py too
​056a4c1	Merge branch 'public/sympy075' of trac.sagemath.org:sage into t/16590/interface_sympy_diophantine_function_s_
​60f9af7	Merge branch 'develop' into t/16624/public/sympy075
​e6c24d3	16624: use standard patch script in spkg-install
​8488e19	Merge branch 'public/sympy075' of trac.sagemath.org:sage into t/16590/interface_sympy_diophantine_function_s_
​bd23c24	16590: fix merge mistake

[rws]

Merged in #16624.

Edit: removed nonsense

[rws]

The x^2-9 doctest failure is only fixed in sympy master but not 0.7.5, so we would still have to wait for this fix. I would however support any reviewer that wants to have the code in Sage---just remove that doctest, the failure is not our fault.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​5479f61	Merge branch 'develop' into t/16590/interface_sympy_diophantine_function_s_
​e2ff58b	16590: cosmetics

[rws]

With the new sympy, also the last doctest passes. Squashed it all into one commit.

---

New commits:

​5841924

16590: interface sympy Diophantine function(s)

[jkeitel]

Some of the tests depend on ordering at the moment:

File "src/sage/symbolic/expression.pyx", line 10089, in sage.symbolic.expression.Expression.solve_diophantine
Failed example:
    solve_diophantine(x^2+y^2==25)
Expected:
    [(-4, 3), (4, -3), (0, -5), (-4, -3), (0, 5), (4, 3)]
Got:
    [(4, -3), (0, -5), (-4, -3), (-4, 3), (0, 5), (4, 3)]
**********************************************************************
File "src/sage/symbolic/expression.pyx", line 10105, in sage.symbolic.expression.Expression.solve_diophantine
Failed example:
    solve_diophantine(x*y-y==10, (x,y))
Expected:
    [(6, 2), (2, 10), (3, 5), (0, -10), (-1, -5), (11, 1), (-4, -2), (-9, -1)]
Got:
    [(-1, -5), (0, -10), (-9, -1), (-4, -2), (2, 10), (11, 1), (6, 2), (3, 5)]
**********************************************************************
File "src/sage/symbolic/expression.pyx", line 10107, in sage.symbolic.expression.Expression.solve_diophantine
Failed example:
    solve_diophantine(x*y-y==10, solution_dict=True)
Expected:
    [{x: 6, y: 2},
     {x: 2, y: 10},
     {x: 3, y: 5},
     {x: 0, y: -10},
     {x: -1, y: -5},
     {x: 11, y: 1},
     {x: -4, y: -2},
     {x: -9, y: -1}]
Got:
    [{y: -5, x: -1},
     {y: -10, x: 0},
     {y: -1, x: -9},
     {y: -2, x: -4},
     {y: 10, x: 2},
     {y: 1, x: 11},
     {y: 2, x: 6},
     {y: 5, x: 3}]

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0906224	Merge branch 'develop' into t/16590/16590
​3955790	16590: fix doctests; cosmetics

[rws]

Fixed. Why dictionaries have to be sorted to be comparable is beyond me.

[rws]

Passes all patchbot tests.

[knsam]

I would like to review this ticket and perhaps contribute more code around this theme. I am working on a review of this code and should be available before the end of this week. :-)

[knsam]

OK, so this ticket is really an interface to Sympy code and all the tests pass.

A suggestion that you might want to consider: Pell's equation is in no reasonable sense a correct attribution. I would prefer Brahmagupta-Pell equation. For historic comments, see A. Weil's book "Number Theory, An approach through history from Hammurapi to Legendre" or Whitford's book "Pell's equation" for some of the early history.

Modulo this, positive review.

[rws]

I agree with the attribution change. Please add your name to the Reviewers field of the ticket. Thanks for the review.

---

New commits:

​b8501cd

16590: interface sympy Diophantine function(s)

[tscrim]

Would anyone believe I actually recently have a use for this, for me coming and my combinatorial/representation theory background? :P Just a trivial push to get this into Sage.

[vbraun]

doctests depends on x/y order which is apparently random:

sage -t --long src/sage/symbolic/expression.pyx
**********************************************************************
File "src/sage/symbolic/expression.pyx", line 10122, in sage.symbolic.expression.Expression.solve_diophantine
Failed example:
    res.sort(); res
Expected:
    [{y: -1, x: -9},
     {y: -2, x: -4},
     {y: -5, x: -1},
     {y: -10, x: 0},
     {y: 10, x: 2},
     {y: 5, x: 3},
     {y: 2, x: 6},
     {y: 1, x: 11}]
Got:
    [{x: 0, y: -10},
     {x: -1, y: -5},
     {x: -4, y: -2},
     {x: -9, y: -1},
     {x: 11, y: 1},
     {x: 6, y: 2},
     {x: 3, y: 5},
     {x: 2, y: 10}]
**********************************************************************
1 item had failures:
   1 of  20 in sage.symbolic.expression.Expression.solve_diophantine
    [2394 tests, 1 failure, 31.23 s]

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​c4fb08a	Merge branch 'develop' into t/16590/16590-1
​c2b1a59	16590: fix doctest

[tscrim]

This test

all(sol[i] == res[i] for i in range(len(sol)))

still depends on the order of the solutions (which is machine dependent as per Volker's note), not the (only) print order of the dicts. So I think a better test would be

all(solution in res for solution in sol)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​259bf76

16590: fix doctest

[rws]

Thanks!

[tscrim]

Sorry, I just realized this isn't quite sufficient. We should also add an and len(res) == len(sol) as there could be more "solutions" in sol than there should be. Once you add that, you can set positive review. Thanks.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9a8c2f3

16590: fix doctest