Solving system of polynomial equations over rationals

asked 2019-12-21 17:10:21 +0200

azerbajdzan
201 ●4 ●10 ●20

updated 2019-12-22 13:06:14 +0200

I want to solve a system of polynomial equations but I need only rational solutions. What is the best method to do it in Sage?

For example:

Input:

R.<a1,b1,b2,c1,c2> = QQ[]
J = R.ideal(5*(9 + 2*a1^2 - b2), 5*(-324 + 4*a1*b1 + b2^2 - c2), 10*(729 + 2*a1 + b1^2 + 243*b2 - 9*b2^2 + 2*a1*c1 + b2*c2), 5*(6561 + 4*b1 - 2916*b2 + 4*b1*c1 + 486*c2 - 36*b2*c2 + c2^2), 2*(-59048 + 10*c1 + 5*c1^2 - 7290*c2 - 45*c2^2))
J.variety()

Output:

[]

Or example with some solutions (same as above but added constant 1889566 to last equation):

Input:

R.<a1,b1,b2,c1,c2> = QQ[]
J = R.ideal(5*(9 + 2*a1^2 - b2), 5*(-324 + 4*a1*b1 + b2^2 - c2), 
 10*(729 + 2*a1 + b1^2 + 243*b2 - 9*b2^2 + 2*a1*c1 + b2*c2), 
 5*(6561 + 4*b1 - 2916*b2 + 4*b1*c1 + 486*c2 - 36*b2*c2 + c2^2), 
 2*(-59048 + 10*c1 + 5*c1^2 - 7290*c2 - 45*c2^2)+1889566)
J.variety()

Output:

[{a1: 0, c1: 0, b1: 0, b2: 9, c2: -243},
 {a1: 0, c1: -2, b1: 0, b2: 9, c2: -243}]

It takes quite a lot of time for the output to appear, while in Mathematica it takes a second. So is there a better method in Sage than the one I used?

edit retag flag offensive close merge delete

Comments

Please add the system. Otherwise we have to make guesses and assumptions which may not apply to your case.

rburing ( 2019-12-21 17:45:33 +0200 )edit

@rburing: I added an example of the system.

azerbajdzan ( 2019-12-21 18:10:24 +0200 )edit

How do you "solve" this with Mathematica ?

Emmanuel Charpentier ( 2019-12-22 22:25:36 +0200 )edit

@Emmanuel Charpentier: Reduce[the system,Rationals]

azerbajdzan ( 2019-12-22 22:51:47 +0200 )edit

add a comment

answered 2019-12-23 00:12:20 +0200

Emmanuel Charpentier
7057 ●6 ●46 ●137

In turns out that these equation systems can be solved more quickly in SR than in the relevant polynomial ring over QQ:

sage: reset()
sage: %cpaste
Pasting code; enter '--' alone on the line to stop or use Ctrl-D.
:R1.<a1,b1,b2,c1,c2> = QQ[]
:S2=[5*(9 + 2*a1^2 - b2),
:    5*(-324 + 4*a1*b1 + b2^2 - c2), 
:    10*(729 + 2*a1 + b1^2 + 243*b2 - 9*b2^2 + 2*a1*c1 + b2*c2), 
:    5*(6561 + 4*b1 - 2916*b2 + 4*b1*c1 + 486*c2 - 36*b2*c2 + c2^2), 
:    2*(-59048 + 10*c1 + 5*c1^2 - 7290*c2 - 45*c2^2)+1889566]
:J2=R1.ideal(*S2)
:J2.dimension()
:
:--
0
sage: %time Sol2=J2.variety()
CPU times: user 1min 2s, sys: 67.9 ms, total: 1min 3s
Wall time: 1min 3s
sage: Sol2
[{c2: -243, c1: 0, b2: 9, b1: 0, a1: 0},
 {c2: -243, c1: -2, b2: 9, b1: 0, a1: 0}]

So far, so good. Solving in SR is faster but find more "rational" solutions :

sage: %cpaste
Pasting code; enter '--' alone on the line to stop or use Ctrl-D.
:# Conversion to SR
:SV=list(map(lambda u:var(repr(u).upper()),R1.gens()))
:D1=dict(zip(R1.gens(),SV))
:
:--
sage: %time Sol2Rat=[v  for v in solve(list(map(lambda u:u.subs(D1), S2)), SV, s
....: olution_dict=True) if all([v[u] in QQ for u in v.keys()])]
CPU times: user 4.95 s, sys: 40.2 ms, total: 4.99 s
Wall time: 4.22 s
sage: Sol2Rat
[{A1: 0.003086423021009911,
  B1: -5.88025749412356e-08,
  B2: 9.00001905233677,
  C1: -1.0,
  C2: -242.9996569468267},
 {A1: -0.003086423021009911,
  B1: 5.88025749412356e-08,
  B2: 9.00001905233677,
  C1: -1.0,
  C2: -242.9996569468267},
 {A1: 6.593646591661152,
  B1: -405.391447368421,
  B2: 95.95235186316432,
  C1: 5160.704545454545,
  C2: -1809.177777777778},
 {A1: -6.590559824368825,
  B1: 404.8549618320611,
  B2: 95.87096774193549,
  C1: -5152.047619047619,
  C2: -1805.641304347826},
 {A1: -6.593646591661152,
  B1: 405.391447368421,
  B2: 95.95235186316432,
  C1: -5162.704545454545,
  C2: -1809.177777777778},
 {A1: 6.590559824368825,
  B1: -404.8549618320611,
  B2: 95.87096774193549,
  C1: 5150.047619047619,
  C2: -1805.641304347826},
 {A1: 0, B1: 0, B2: 9, C1: 0, C2: -243},
 {A1: 0, B1: 0, B2: 9, C1: -2, C2: -243}]
sage: len(Sol2Rat)
8

That makes me question the validity of the test of rationality v[u] in QQ. Advice ?

edit flag offensive delete link

Comments

The solutions returned by solve seem to be numerical approximations. I tried to find a way to solve over RIF or RBF but I didn't manage. Anyway, to decide for certain that an approximate solution isn't rational you would need infinite precision. But maybe one could build in a tolerance (find rational solutions of bounded height).

rburing ( 2019-12-23 09:40:14 +0200 )edit

@Emmanuel Charpentier, @rburing: I think I know why Mathematica computes it in a second while Sage in more than a minute. Mathematica computes Groebner basis in a more clever way, that there are polynomials in as few variables as possible, in this cases Mathematica's Groebner basis contained one polynomial only in one variable and four polynomials only in two variables. So once you have a polynomial only in one variables you immediately have rational values of one variable. While Sage's Groebner basis contained two polynomials in two variables, ten polynomials in four variables and seven polynomials in five variables. Then it is not a surprise that Sage has problems solving such Groebner basis that are maybe even more complicated than the original system of equations.

azerbajdzan ( 2019-12-23 12:03:50 +0200 )edit

add a comment

Solving system of polynomial equations over rationals

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Solving system of polynomial equations over rationals edit

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Solving system of polynomial equations over rationals