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: sage-6.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:

Status badges

Description (last modified by Ralf Stephan)

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

Change History (40)

comment:1 Changed 8 years ago by Ralf Stephan

Description: modified (diff)

comment:2 Changed 8 years ago by Ralf Stephan

Description: modified (diff)

comment:3 Changed 8 years ago by Ralf Stephan

Description: modified (diff)

comment:4 Changed 8 years ago by Ralf Stephan

Cc: John Cremona added
Description: modified (diff)

comment:5 Changed 8 years ago by Ralf Stephan

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 Ralf Stephan (previous) (diff)

comment:6 Changed 8 years ago by Ralf Stephan

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 Ralf Stephan

Another annoyance of that sympy package has to be tolerated: https://github.com/sympy/sympy/issues/7692

Version 0, edited 8 years ago by Ralf Stephan (next)

comment:8 Changed 8 years ago by Ralf Stephan

Owner: set to Ralf Stephan

comment:9 Changed 8 years ago by Ralf Stephan

Dependencies: #16624

comment:10 Changed 8 years ago by Ralf Stephan

Branch: u/rws/interface_sympy_diophantine_function_s_

comment:11 Changed 8 years ago by git

Commit: 827e50525a7aaee701f9382bd58302b82f650474

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

827e50516590: add documentation

comment:12 Changed 8 years ago by git

Commit: 827e50525a7aaee701f9382bd58302b82f650474d9989ed7fbf72d51fe3ccbb97e45049416f85515

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

e598b2c16590: fix doctests
d9989ed16590: roll back changes to quadratic_forms/; finish documentation

comment:13 Changed 8 years ago by Ralf Stephan

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 For batch modifications

Milestone: sage-6.3sage-6.4

comment:15 Changed 8 years ago by git

Commit: d9989ed7fbf72d51fe3ccbb97e45049416f85515bd23c244786c4e73d2c6b036d34b758a9efbfe2a

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

1568fe4Merge branch 'develop' into t/16590/interface_sympy_diophantine_function_s_
6365073shortened patch
04d8d62remove doc/src/modules/mpmath from patch; remove files via spkg-install
4c9f28816624: remove mpmath/tests/__init__.py too
056a4c1Merge branch 'public/sympy075' of trac.sagemath.org:sage into t/16590/interface_sympy_diophantine_function_s_
60f9af7Merge branch 'develop' into t/16624/public/sympy075
e6c24d316624: use standard patch script in spkg-install
8488e19Merge branch 'public/sympy075' of trac.sagemath.org:sage into t/16590/interface_sympy_diophantine_function_s_
bd23c2416590: fix merge mistake

comment:16 Changed 8 years ago by Ralf Stephan

Authors: Ralf Stephan
Dependencies: #16624
Report Upstream: N/AReported upstream. No feedback yet.
Status: newneeds_review

Merged in #16624.

Edit: removed nonsense

Last edited 8 years ago by Ralf Stephan (previous) (diff)

comment:17 Changed 8 years ago by Ralf Stephan

Report Upstream: Reported upstream. No feedback yet.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 8 years ago by git

Commit: bd23c244786c4e73d2c6b036d34b758a9efbfe2ae2ff58b2d7953c953e9aad77d5a8539244fd3498

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

5479f61Merge branch 'develop' into t/16590/interface_sympy_diophantine_function_s_
e2ff58b16590: cosmetics

comment:19 Changed 8 years ago by Ralf Stephan

Branch: u/rws/interface_sympy_diophantine_function_s_u/rws/16590

comment:20 Changed 8 years ago by Ralf Stephan

Commit: e2ff58b2d7953c953e9aad77d5a8539244fd3498584192418d064dc76b31eb7a09c33dcaf8bb89d9
Milestone: sage-6.4sage-6.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:

584192416590: interface sympy Diophantine function(s)

comment:21 Changed 7 years ago by Jan Keitel

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: 584192418d064dc76b31eb7a09c33dcaf8bb89d9395579004ceacd7b34f78ddb86c2687df0158844

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

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

comment:23 Changed 7 years ago by Ralf Stephan

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

comment:24 Changed 7 years ago by Ralf Stephan

Passes all patchbot tests.

comment:25 Changed 7 years ago by Kannappan Sampath

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 Ralf Stephan

Milestone: sage-6.6sage-6.7

comment:27 Changed 7 years ago by Kannappan Sampath

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 Ralf Stephan

Branch: u/rws/16590u/rws/16590-1

comment:29 Changed 7 years ago by Ralf Stephan

Commit: 395579004ceacd7b34f78ddb86c2687df0158844b8501cd41176f054ea085d24779f8a4666589b9d

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


New commits:

b8501cd16590: interface sympy Diophantine function(s)

comment:30 Changed 7 years ago by Travis Scrimshaw

Reviewers: Kannappan Sampath
Status: needs_reviewpositive_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 Volker Braun

Status: positive_reviewneeds_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 git

Commit: b8501cd41176f054ea085d24779f8a4666589b9dc2b1a59983ba6420fd42eedb2aebaabcfefe5dc0

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

c4fb08aMerge branch 'develop' into t/16590/16590-1
c2b1a5916590: fix doctest

comment:33 Changed 7 years ago by Ralf Stephan

Status: needs_workneeds_review

comment:34 Changed 7 years ago by Travis Scrimshaw

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)

comment:35 Changed 7 years ago by git

Commit: c2b1a59983ba6420fd42eedb2aebaabcfefe5dc0259bf765b93e7840a15abd00c0bb7afbaa86d03f

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

259bf7616590: fix doctest

comment:36 Changed 7 years ago by Ralf Stephan

Thanks!

comment:37 Changed 7 years ago by Travis Scrimshaw

Reviewers: Kannappan SampathKannappan 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: 259bf765b93e7840a15abd00c0bb7afbaa86d03f9a8c2f3b419b5f199a7f2b1d61ac507924f559b1

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

9a8c2f316590: fix doctest

comment:39 Changed 7 years ago by Ralf Stephan

Status: needs_reviewpositive_review

comment:40 Changed 7 years ago by Volker Braun

Branch: u/rws/16590-19a8c2f3b419b5f199a7f2b1d61ac507924f559b1
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.