Opened 8 years ago
Closed 7 years ago
#16590 closed enhancement (fixed)
interface sympy Diophantine function(s)
Reported by:  Ralf Stephan  Owned by:  Ralf Stephan 

Priority:  major  Milestone:  sage6.7 
Component:  number theory  Keywords:  pellian, integers, solution 
Cc:  John Cremona  Merged in:  
Authors:  Ralf Stephan  Reviewers:  Kannappan Sampath, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  9a8c2f3 (Commits, GitHub, GitLab)  Commit:  9a8c2f3b419b5f199a7f2b1d61ac507924f559b1 
Dependencies:  Stopgaps: 
Description (last modified by )
In sympy the solution of Diophantine equations is available for several types of equations (http://docs.sympy.org/latest/modules/solvers/diophantine.html). This metaticket aims at
 implementing a global
solve_diophantine()
function that wraps the sympy functionality and takes symbolic expressions (up to order 2)
 univariate polynomials (up to order 2)
 multivariate polynomials (up to order 2)
 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)}
Change History (40)
comment:1 Changed 8 years ago by
Description:  modified (diff) 

comment:2 Changed 8 years ago by
Description:  modified (diff) 

comment:3 Changed 8 years ago by
Description:  modified (diff) 

comment:4 Changed 8 years ago by
Cc:  John Cremona added 

Description:  modified (diff) 
comment:6 Changed 8 years ago by
sage: sage: from sympy.solvers.diophantine import * sage: sage: from sympy import sympify sage: diop_solve(sympify(x*y10)) {(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:8 Changed 8 years ago by
Owner:  set to Ralf Stephan 

comment:9 Changed 8 years ago by
Dependencies:  → #16624 

comment:10 Changed 8 years ago by
Branch:  → u/rws/interface_sympy_diophantine_function_s_ 

comment:11 Changed 8 years ago by
Commit:  → 827e50525a7aaee701f9382bd58302b82f650474 

Branch pushed to git repo; I updated commit sha1. New commits:
827e505  16590: add documentation

comment:12 Changed 8 years ago by
Commit:  827e50525a7aaee701f9382bd58302b82f650474 → d9989ed7fbf72d51fe3ccbb97e45049416f85515 

comment:13 Changed 8 years ago by
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
Milestone:  sage6.3 → sage6.4 

comment:15 Changed 8 years ago by
Commit:  d9989ed7fbf72d51fe3ccbb97e45049416f85515 → 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 spkginstall

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 spkginstall

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
Authors:  → Ralf Stephan 

Dependencies:  #16624 
Report Upstream:  N/A → Reported upstream. No feedback yet. 
Status:  new → needs_review 
Merged in #16624.
Edit: removed nonsense
comment:17 Changed 8 years ago by
Report Upstream:  Reported upstream. No feedback yet. → Fixed upstream, but not in a stable release. 

The x^29
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 Sagejust remove that doctest, the failure is not our fault.
comment:18 Changed 8 years ago by
Commit:  bd23c244786c4e73d2c6b036d34b758a9efbfe2a → e2ff58b2d7953c953e9aad77d5a8539244fd3498 

comment:19 Changed 8 years ago by
Branch:  u/rws/interface_sympy_diophantine_function_s_ → u/rws/16590 

comment:20 Changed 8 years ago by
Commit:  e2ff58b2d7953c953e9aad77d5a8539244fd3498 → 584192418d064dc76b31eb7a09c33dcaf8bb89d9 

Milestone:  sage6.4 → sage6.6 
Report Upstream:  Fixed upstream, but not in a stable release. → 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
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*yy==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*yy==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
Commit:  584192418d064dc76b31eb7a09c33dcaf8bb89d9 → 395579004ceacd7b34f78ddb86c2687df0158844 

comment:23 Changed 7 years ago by
Fixed. Why dictionaries have to be sorted to be comparable is beyond me.
comment:25 Changed 7 years ago by
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
Milestone:  sage6.6 → sage6.7 

comment:27 Changed 7 years ago by
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 BrahmaguptaPell 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
Branch:  u/rws/16590 → u/rws/165901 

comment:29 Changed 7 years ago by
Commit:  395579004ceacd7b34f78ddb86c2687df0158844 → b8501cd41176f054ea085d24779f8a4666589b9d 

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)

comment:30 Changed 7 years ago by
Reviewers:  → Kannappan Sampath 

Status:  needs_review → 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
Status:  positive_review → 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 item had failures: 1 of 20 in sage.symbolic.expression.Expression.solve_diophantine [2394 tests, 1 failure, 31.23 s]
comment:32 Changed 7 years ago by
Commit:  b8501cd41176f054ea085d24779f8a4666589b9d → c2b1a59983ba6420fd42eedb2aebaabcfefe5dc0 

comment:33 Changed 7 years ago by
Status:  needs_work → needs_review 

comment:34 Changed 7 years ago by
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
Commit:  c2b1a59983ba6420fd42eedb2aebaabcfefe5dc0 → 259bf765b93e7840a15abd00c0bb7afbaa86d03f 

Branch pushed to git repo; I updated commit sha1. New commits:
259bf76  16590: fix doctest

comment:37 Changed 7 years ago by
Reviewers:  Kannappan Sampath → 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
Commit:  259bf765b93e7840a15abd00c0bb7afbaa86d03f → 9a8c2f3b419b5f199a7f2b1d61ac507924f559b1 

Branch pushed to git repo; I updated commit sha1. New commits:
9a8c2f3  16590: fix doctest

comment:39 Changed 7 years ago by
Status:  needs_review → positive_review 

comment:40 Changed 7 years ago by
Branch:  u/rws/165901 → 9a8c2f3b419b5f199a7f2b1d61ac507924f559b1 

Resolution:  → fixed 
Status:  positive_review → closed 
However, the last solution shown in the workaround is incomplete, see https://github.com/sympy/sympy/issues/7671