Article title: Diophantine equations: a systematic approach
Author of the article: Bogdan Grechuk,
Code title: Vieta jumping method for solving Diophantine equations
Author of the code: Aubrey de Grey
Author of the article: Bogdan Grechuk,
Code title: Vieta jumping method for solving Diophantine equations
Author of the code: Aubrey de Grey
Article abstract
Article abstract
This paper initiates a novel research direction in the theory of Diophantine equations: define an appropriate version of the equation’s size, order all polynomial Diophantine equations starting from the smallest ones, and then solve the equations in that order. By combining a new computer-aided procedure with human reasoning, we solved the Hilbert’s tenth problem for all polynomial Diophantine equations of size less than 31, where the size is defined in (Zidane, 2018). In addition, we solved this problem for all equations of size equal to 31, with a single exception. Further, we solved the Hilbert’s tenth problem for all two-variable Diophantine equations of size less than 32, all symmetric equations of size less than 39, all three-monomial equations of size less than 45, and, in each category, identified the explicit smallest equations for which the problem remains open. As a result, we derived a list of equations that are very simple to write down but which are apparently difficult to solve. As we know from the example of Fermat’s Last Theorem, such equations have a potential to stimulate the development of new methods in number theory.
Introduction
Introduction
The aim of the paper is to investigate which Diophantine equations has integer solutions. Many different methods for solving equations are analysed. We have discovered that one of the methods, based on Vieta jumping technique, is powerful and at the same time easy to automate. To illustrate the method consider equation +--2+xyz. Assume that is has an integer solution (). Let us replace x by a new variable , to get a quadratic equation in : -tyz+-+20. One root of this quadratic equation is x. By the properties of quadratic equations, the second root satisfies yz-=yz-x. In other words, if () is a solution to our equation, then () is also a solution. Now let us choose a solution () with |x|+|y|+|z| minimal. Then we must have |yz-x|≥|x|. By a similar argument, |xz-y|≥|y| and |-xy-z|≥|z|. Now consider optimization problem of maximizing t over the real variables () subject to constraints +--2+xyz, |x|≥t, |y|≥t, |z|≥t, |yz-x|≥|x|, |xz-y|≥|y|, and |-xy-z|≥|z|. It is easy to check in Mathematica that the optimal value is 0. This implies that any solution with |x|+|y|+|z| minimal must have |x|=0, |y|=0, or |z|=0. On the other hand, it is also easy to check in Mathematica that our equation +--2+xyz has no integer solutions with some variable equal to 0. Hence, it has no integer solutions at all.
The same method can be easily written in the form of more general algorithm. Consider equation, where P is a polynomial with integer coefficients. Call variable eligible if (i) the equation can be written in the form ++0, where is a non-zero integer and and are polynomials in other variables, and (ii) for every solution to modulo , (x) is divisible by . Then we solve optimization problem of maximizing t over the real variables () subject to constraints , for each i, and for each eligible variable . Let T be the optimal value. If T=∞, and FindInstance cannot solve the equation, give up. Otherwise check whether the equation has any integer solution with for some i. If there is no such solution, the there is no integer solution at all. The code below implements this method.
2
x
2
y
2
z
x,y,z
t
t
2
t
2
y
2
z
t
1
t
2
t
2
t
1
x,y,z
yz-x,y,z
x,y,z
x,y,z,t
2
x
2
y
2
z
2
x
2
y
2
z
The same method can be easily written in the form of more general algorithm. Consider equation
P(,...,)=0
x
1
x
n
x
i
a
i
2
x
i
Q
i
x
i
R
i
a
i
Q
i
R
i
x=(,...,
x
1
x
n
P=0
a
i
Q
i
a
i
x,y,z,t
P(,...,)=0
x
1
x
n
||≥t
x
i
|-(/)-|≥||
Q
i
a
i
x
i
x
i
x
i
||≤T
x
i
Code (Vieta jumping method for solving Diophantine equations)
Code (Vieta jumping method for solving Diophantine equations)
The input to FindInstanceWithVieta should be a polynomial with integer coefficients. The output can be either an integer solution, or {} if the method proves that no integer solutions exist, or the message “The methods available to FindInstanceWithVieta are insufficient to find the requested instances or prove they do not exist.”
FindInstanceWithVieta[sdn_]:=(vars=Variables[sdn];vcc=Length[vars];v2=Map[v[#]&,Range[vcc]];vsdp=sdn/.MapThread[Rule,{vars,v2}];vcl=Reverse[CoefficientRules[vsdp]];{vdm,vdc}={Keys[vcl],Values[vcl]};vl=Table[qp=Position[vdm,ReplacePart[ConstantArray[0,vcc],vv->2]];If[qp{}||Sort[Transpose[vdm][[vv]]][[-2]]≥2,Nothing,(qp2=vdc[[qp[[1,1]]]];lp=Total[Select[MonomialList[vsdp],Keys[CoefficientRules[#,v2]][[1,vv]]==1&]];{v[vv],Simplify[v[vv]+lp/(v[vv]*qp2)],Abs[qp2]≠1&&!AllTrue[Tuples[Range[Abs[qp2]]-1,vcc],Divisible[lp/.MapThread[Rule,{v2,#}],Abs[qp2]]&]})],{vv,1,vcc}];mk=Quiet[MaxValue[{Apply[Min,Abs[Join[v2,Select[vl,#[[3]]&][[All,2]]]]],vsdp0&&AllTrue[vl,#[[3]]||Abs[#[[2]]]≥Abs[#[[1]]]&]},v2]];If[mk==Infinity,vsol=Quiet[FindInstance[vsdp==0,v2,Integers]],(*Print["Vieta limit is ",N[mk]];*)vsl=Table[vvl=Position[vl,vv];vvl=If[vvl=={},0,vvl[[1,1]]];Quiet[FindInstance[vsdp==0&&(Abs[v[vv]]<=N[mk]||(vvl>0&&vl[[vvl,3]]&&Abs[vl[[vvl,2]]]<=N[mk])),v2,Integers]],{vv,1,vcc}];If[Position[vsl,{_}]!={},vsol=vsl[[Position[vsl,{_}][[1,1]]]],oks=Map[v[#]&,Select[Range[vcc],MatchQ[vsl[[#]],{}]&]];If[oks==v2,vsol={},mk2=Quiet[MaxValue[{Apply[Min,Abs[Join[oks,Select[vl,MemberQ[oks,#[[1]]]&&#[[3]]&][[All,2]]]]],vsdp0&&AllTrue[vl,#[[3]]||Abs[#[[2]]]≥Abs[#[[1]]]&]},v2]];(*Print["relaxed Vieta limit is ",N[mk2]];*)vsol=Quiet[FindInstance[vsdp==0&&(mk2==Infinity||Apply[Or,Map[Abs[#]≤N[mk2]&,Join[oks,Select[vl,MemberQ[oks,#[[1]]]&&#[[3]]&][[All,2]]]]]),v2,Integers]]]]];If[MatchQ[vsol,{___}],Print[vsol/.MapThread[Rule,{v2,vars}]],Print["The methods available to FindInstanceWithVieta are insufficient to find the requested instances or prove they do not exist."]]);
Examples
Examples
Below are the examples of equations that current FindInstance method cannot solve but our method can.
FindInstance[2+++xyz-==0,{x,y,z},Integers]
2
x
2
y
2
z
FindInstance[2+++xyz-0,{x,y,z},Integers]
2
x
2
y
2
z
FindInstanceWithVieta[2+++xyz-]
2
x
2
y
2
z
{}
FindInstance[4+x^2+y^2+xyz+z^20,{x,y,z},Integers]
FindInstance[4+++xyz+0,{x,y,z},Integers]
2
x
2
y
2
z
FindInstanceWithVieta[4+x^2+y^2+xyz+z^2]
{}
FindInstance[2+3x+x^2y+y^2+yz^2==0,{x,y,z},Integers]
FindInstance[2+3x+y++y0,{x,y,z},Integers]
2
x
2
y
2
z
FindInstanceWithVieta[2+3x+x^2y+y^2+yz^2]
{}
FindInstance[1+2x^2+y^2-6xyz==0,{x,y,z},Integers]
FindInstance[1+2+-6xyz0,{x,y,z},Integers]
2
x
2
y
FindInstanceWithVieta[1+2x^2+y^2-6xyz]
{}
Here is an example of an equation with a solution.
FindInstanceWithVieta[2+x^2+y^2+xyz+z^2]
{{x-3,y-4,z-9}}
Here is an example for which the method fails.
FindInstanceWithVieta[1+x^2y+y^2+z^2]
The methods available to FindInstanceWithVieta are insufficient to find the requested instances or prove they do not exist.