Opened 8 years ago

Closed 7 years ago

# interface sympy Diophantine function(s)

Reported by: Owned by: rws rws major sage-6.7 number theory pellian, integers, solution cremona Ralf Stephan Kannappan Sampath, Travis Scrimshaw N/A 9a8c2f3 9a8c2f3b419b5f199a7f2b1d61ac507924f559b1

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)
• 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)}
```

### comment:1 Changed 8 years ago by rws

• Description modified (diff)

### comment:2 Changed 8 years ago by rws

• Description modified (diff)

### comment:3 Changed 8 years ago by rws

• Description modified (diff)

### comment:4 Changed 8 years ago by rws

• Description modified (diff)

### comment:5 Changed 8 years ago by 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.

Last edited 8 years ago by rws (previous) (diff)

### comment:6 Changed 8 years ago by 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.

### comment:7 Changed 8 years ago by rws

Irrelevant comment deleted. Sorry.

Last edited 8 years ago by rws (previous) (diff)

### comment:8 Changed 8 years ago by rws

• Owner changed from (none) to rws

### comment:9 Changed 8 years ago by rws

• Dependencies set to #16624

### comment:10 Changed 8 years ago by rws

• Branch set to u/rws/interface_sympy_diophantine_function_s_

### comment:11 Changed 8 years ago by git

• Commit set to 827e50525a7aaee701f9382bd58302b82f650474

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

 ​827e505 `16590: add documentation`

### comment:12 Changed 8 years ago by git

• Commit changed from 827e50525a7aaee701f9382bd58302b82f650474 to d9989ed7fbf72d51fe3ccbb97e45049416f85515

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`

### comment:13 Changed 8 years ago by rws

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

### comment:14 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

### comment:15 Changed 8 years ago by git

• Commit changed from d9989ed7fbf72d51fe3ccbb97e45049416f85515 to bd23c244786c4e73d2c6b036d34b758a9efbfe2a

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`

### comment:16 Changed 8 years ago by rws

• Authors set to Ralf Stephan
• Dependencies #16624 deleted
• Report Upstream changed from N/A to Reported upstream. No feedback yet.
• Status changed from new to needs_review

Merged in #16624.

Edit: removed nonsense

Last edited 8 years ago by rws (previous) (diff)

### comment:17 Changed 8 years ago by rws

• Report Upstream changed from Reported upstream. No feedback yet. to Fixed upstream, but not in a stable release.

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.

### comment:18 Changed 7 years ago by git

• Commit changed from bd23c244786c4e73d2c6b036d34b758a9efbfe2a to e2ff58b2d7953c953e9aad77d5a8539244fd3498

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`

### comment:19 Changed 7 years ago by rws

• Branch changed from u/rws/interface_sympy_diophantine_function_s_ to u/rws/16590

### comment:20 Changed 7 years ago by rws

• Commit changed from e2ff58b2d7953c953e9aad77d5a8539244fd3498 to 584192418d064dc76b31eb7a09c33dcaf8bb89d9
• Milestone changed from sage-6.4 to sage-6.6
• Report Upstream changed from Fixed upstream, but not in a stable release. to N/A

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

New commits:

 ​5841924 `16590: interface sympy Diophantine function(s)`

### comment:21 Changed 7 years ago by 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}]
```

### comment:22 Changed 7 years ago by git

• Commit changed from 584192418d064dc76b31eb7a09c33dcaf8bb89d9 to 395579004ceacd7b34f78ddb86c2687df0158844

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

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

### comment:23 Changed 7 years ago by rws

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

### comment:24 Changed 7 years ago by rws

Passes all patchbot tests.

### comment:25 Changed 7 years ago by 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. :-)

### comment:26 Changed 7 years ago by rws

• Milestone changed from sage-6.6 to sage-6.7

### comment:27 Changed 7 years ago by 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.

### comment:28 Changed 7 years ago by rws

• Branch changed from u/rws/16590 to u/rws/16590-1

### comment:29 Changed 7 years ago by rws

• Commit changed from 395579004ceacd7b34f78ddb86c2687df0158844 to b8501cd41176f054ea085d24779f8a4666589b9d

New commits:

 ​b8501cd `16590: interface sympy Diophantine function(s)`

### comment:30 Changed 7 years ago by tscrim

• Reviewers set to Kannappan Sampath
• Status changed from needs_review to positive_review

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.

### comment:31 Changed 7 years ago by vbraun

• Status changed from positive_review to needs_work

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 of  20 in sage.symbolic.expression.Expression.solve_diophantine
[2394 tests, 1 failure, 31.23 s]
```

### comment:32 Changed 7 years ago by git

• Commit changed from b8501cd41176f054ea085d24779f8a4666589b9d to c2b1a59983ba6420fd42eedb2aebaabcfefe5dc0

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

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

### comment:33 Changed 7 years ago by rws

• Status changed from needs_work to needs_review

### comment:34 Changed 7 years ago by 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 `dict`s. So I think a better test would be

```all(solution in res for solution in sol)
```

### comment:35 Changed 7 years ago by git

• Commit changed from c2b1a59983ba6420fd42eedb2aebaabcfefe5dc0 to 259bf765b93e7840a15abd00c0bb7afbaa86d03f

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

 ​259bf76 `16590: fix doctest`

Thanks!

### comment:37 Changed 7 years ago by tscrim

• Reviewers changed from Kannappan Sampath to Kannappan Sampath, Travis Scrimshaw

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.

### comment:38 Changed 7 years ago by git

• Commit changed from 259bf765b93e7840a15abd00c0bb7afbaa86d03f to 9a8c2f3b419b5f199a7f2b1d61ac507924f559b1

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

 ​9a8c2f3 `16590: fix doctest`

### comment:39 Changed 7 years ago by rws

• Status changed from needs_review to positive_review

### comment:40 Changed 7 years ago by vbraun

• Branch changed from u/rws/16590-1 to 9a8c2f3b419b5f199a7f2b1d61ac507924f559b1
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.