ABSTRACT (original book): This book proposes a novel approach to the study of Diophantine equations: specify an appropriate definition of the equation’s size, order all polynomial Diophantine equations by size, and then solve the equations in increasing order.
Natural questions about the solution set of Diophantine equations are studied in this book using this approach. Is the set empty? Is it finite or infinite? Can all integer solutions be parametrized? By ordering equations by size, the book attempts to answer these questions in a systematic manner. When the size grows, the difficulty of finding solutions increases and the methods required to determine solutions become more advanced. Along the way, the reader will learn dozens of methods for solving Diophantine equations, each of which is illustrated by worked examples and exercises. The book ends with solutions to exercises and a large collection of open problems, often simple to write down yet still unsolved.
The original approach pursued in this book makes it widely accessible. Many equations require only high school mathematics and creativity to be solved, so a large part of the book is accessible to high school students, especially those interested in mathematical competitions such as olympiads. The main intended audience is undergraduate students, for whom the book will serve as an unusually rich introduction to the topic of Diophantine equations. Many methods from the book will be useful for graduate students, while Ph.D. students and researchers may use it as a source of fascinating open questions of varying levels of difficulty. CITATION (original book): B. Grechuk. Polynomial Diophantine Equations: A Systematic Approach. Springer International Publishing, 2024, ISBN 978-3-031-62949-5. https://doi.org/10.1007/978-3-031-62949-5
Amazon: https://a.co/d/aRd0XMe
Google Books: https://books.google.co.uk/books?id=rj8eEQAAQBAJ
Natural questions about the solution set of Diophantine equations are studied in this book using this approach. Is the set empty? Is it finite or infinite? Can all integer solutions be parametrized? By ordering equations by size, the book attempts to answer these questions in a systematic manner. When the size grows, the difficulty of finding solutions increases and the methods required to determine solutions become more advanced. Along the way, the reader will learn dozens of methods for solving Diophantine equations, each of which is illustrated by worked examples and exercises. The book ends with solutions to exercises and a large collection of open problems, often simple to write down yet still unsolved.
The original approach pursued in this book makes it widely accessible. Many equations require only high school mathematics and creativity to be solved, so a large part of the book is accessible to high school students, especially those interested in mathematical competitions such as olympiads. The main intended audience is undergraduate students, for whom the book will serve as an unusually rich introduction to the topic of Diophantine equations. Many methods from the book will be useful for graduate students, while Ph.D. students and researchers may use it as a source of fascinating open questions of varying levels of difficulty. CITATION (original book): B. Grechuk. Polynomial Diophantine Equations: A Systematic Approach. Springer International Publishing, 2024, ISBN 978-3-031-62949-5. https://doi.org/10.1007/978-3-031-62949-5
Amazon: https://a.co/d/aRd0XMe
Google Books: https://books.google.co.uk/books?id=rj8eEQAAQBAJ
Introduction
Introduction
Polynomial Diophantine equations are equations of the form:
P[,,...,]=0
x
1
x
2
x
n
where P is a polynomial with integer coefficients. The book described in the abstract (from now on, we will refer to this book as “the book”) introduces the following project: order all such equations by a parameter called “size”, and solve the equations in this order. Because the number of polynomial Diophantine equations grows exponentially with size, this project would be impossible without computer assistance, and Wolfram Mathematica has been selected as the main software system for it. This notebook briefly explains the methodology and contains some of the Mathematica code used in the book. The reader is referred to the book for more details.To order equations, the book introduces the size H of a polynomial P as:
H[P]=Abs[]2^
m
∑
j=1
a
j
d
j
where m is the number of monomials of P (in reduced form), is the degree of monomial j, and is its coefficient. In other words, to compute the size of a polynomial, we just substitute 2 in place of each variable, replace each coefficient by its absolute value, and evaluate. The described Mathematica code can be used to generate all Diophantine equations with the given set of monomials with size in a given range, that cannot be solved using the given list of methods. By an obvious modification of the code, one can also generate all the smallest equations that can be solved by any given method M but cannot be solved by any easier method. These equations can be used as exercises for students for practising method M. Further, the code can be used to check whether any given equation (of any size) can be solved by any of the listed methods.
d
j
a
j
Describing all solutions to unrestricted equations
Describing all solutions to unrestricted equations
In Mathematica, the size of a polynomial can be computed using the function:
In[]:=
valH[poly_]:=Total[Map[Abs[#/.Map[#2&,Variables[poly]]]&,MonomialList[poly]]]
For example:
In[]:=
valH[x^3+y^3+z^3-3]
Out[]=
27
The following function, whose utility functions Explicit and ExplicitFamily we shall update progressively below, returns all polynomials (except the ones that we want to exclude) with monomials drawn from a given list and with size H in the given range.
(*ThisfunctionexcludespolynomialsPforwhichtheequationP=0isalreadysolved.Becausewehavenotsolvedanyequationssofar,itoutputsFalse*)Explicit[poly_]:=False(*ThisfunctionexcludespolynomialsPsuchthatequationQ=0canbesolvedforanypolynomialQwiththesamemonomialsasP.BecausewehavenotsolvedanyequationssofaritoutputsFalse*)ExplicitFamily[poly_]:=False(*Thisfunctionoutputsallpolynomialswiththegivenlistofmonomialsofsizeuptoagivenbound,forwhichthecorresponsingequationsarenotexcludedbyfunctionsExplicitandExplicitFamily*)polylistH[allmonlist_,H_]:=polybiglist={};monlen=Length[allmonlist];deglist=ConstantArray[0,monlen];Fori=1,i≤monlen,i++,moni=allmonlist[[i]];deglist[[i]]=Max@ExponentMonomialList[moni]/.ThreadVariables[moni]x.,x.;;bvars=Variables[Sum[Indexed[b,{j}]1,{j,1,monlen}]];blist=Solve[{Sum[Indexed[b,{j}]2^deglist[[j]],{j,1,monlen}]<=H,Sum[Indexed[b,{j}]1,{j,1,monlen}]>0,0≤bvars≤1},bvars,Integers];Forbcount=1,bcount≤Length[blist],bcount++,cof1poly=Sum[Indexed[b,{j}]allmonlist[[j]],{j,1,monlen}]/.{blist[[bcount]]}[[1]];If!ExplicitFamily[cof1poly],bmonlist=MonomialList[cof1poly];monlen2=Length[bmonlist];deglist2=ConstantArray[0,monlen2];Fori=1,i≤monlen2,i++,moni=bmonlist[[i]];deglist2[[i]]=Max@ExponentMonomialList[moni]/.ThreadVariables[moni]x.,x.;;aexpr=Sum[Abs[Indexed[a,{k}]2^deglist2[[k]]],{k,1,monlen2}];avars=Variables[Sum[Indexed[a,{k}]1,{k,1,monlen2}]];alist=Solve[{aexprH,0<Abs[avars]},avars,Integers];If[Length[alist]>0,apolylist=Sum[Indexed[a,{k}]bmonlist[[k]],{k,1,monlen2}]/.alist;For[acount=1,acount≤Length[apolylist],acount++,poly=apolylist[[acount]];If[!Explicit[poly],polybiglist=Append[polybiglist,poly]]]];polybiglist
We also define a function that enumerates the monomials that can appear in a polynomial of a range of sizes. We assume a default of at most 5 variables, which can be reduced by specifying a third parameter; we can also restrict the monomials explicitly by specifying a fourth parameter. For example, the following code outputs all polynomials in variables x,y,z,t of size up to 4.
In[]:=
ml2[H_,V_]:=Map[Apply[Times,#]&,Map[{x,y,z,t,u}[[1;;V]]^#&,Flatten[Map[Permutations[PadRight[#,V]]&,IntegerPartitions[Floor[Log2[H]]]],1]]];ml[maxH_,maxV_]:=Append[DeleteDuplicates[Join@@Table[ml2[i,maxV],{i,maxH,2,-1}]],1];printRangeH[Hmin_,Hmax_,V_,m_]:=Module[{H,monlist},monlist=If[m=={},ml[Hmax,V],m];For[H=Hmin,H≤Hmax,H++,Print["Non-excluded polynomials of size H = ",H," are: ",polylistH[monlist,H]]]]printRangeH[Hmin_,Hmax_,V_]:=printRangeH[Hmin,Hmax,V,{}]printRangeH[Hmin_,Hmax_]:=printRangeH[Hmin,Hmax,5]printRangeH[1,4,4]
Non-excluded polynomials of size H = 1 are: {-1,1}
Non-excluded polynomials of size H = 2 are: {-2,2,-t,t,-z,z,-y,y,-x,x}
Non-excluded polynomials of size H = 3 are: {-3,3,-1-t,1-t,-1+t,1+t,-1-z,1-z,-1+z,1+z,-1-y,1-y,-1+y,1+y,-1-x,1-x,-1+x,1+x}
Non-excluded polynomials of size H = 4 are: {-4,4,-2t,2t,-2-t,2-t,-2+t,2+t,-2z,2z,-2-z,2-z,-2+z,2+z,-t-z,-t+z,t-z,t+z,-2y,2y,-2-y,2-y,-2+y,2+y,-t-y,-t+y,t-y,t+y,-y-z,-y+z,y-z,y+z,-2x,2x,-2-x,2-x,-2+x,2+x,-t-x,-t+x,t-x,t+x,-x-z,-x+z,x-z,x+z,-x-y,-x+y,x-y,x+y,-tz,tz,-ty,ty,-yz,yz,-tx,tx,-xz,xz,-xy,xy,-,,-,,-,,-,}
2
t
2
t
2
z
2
z
2
y
2
y
2
x
2
x
As we can see, many of the resulting polynomials are the same up to renaming or permuting the variables, substitutions of the form ->, or multiplication by a non-zero constant. Let us call polynomials related by these transformations equivalent. To output only one polynomial from each equivalence class, we can use the following functions.
x
i
-x
i
In[]:=
(*Thisfunctioncheckswhetherallcoefficientsofthepolynomialhaveacommonfactor*)gcdCheck[poly_]:=Quiet[GCD[GCD@@Flatten[CoefficientList[poly,Variables[poly]]]]>1](*ThenexttwofunctionsareauxiliaryfunctionsneededforPermCheckandSignCheck*)valPowers[poly_]:=(pvars=Variables[poly];nvars=Length[pvars];rules=Table[pvars[[varcount]]10100^(nvars-varcount),{varcount,1,nvars}];poly/.rules)valAbsPowers[poly_]:=(nvars2=Length[Variables[poly]];rules2=Table[v[varcount2]10100^(nvars2-varcount2),{varcount2,1,nvars2}];Total[Map[Abs[#/.rules2]&,MonomialList[poly]]])(*Thisfunctionselectsonepolynomialfromthoseobtainedbypermutationofthevariablesx,y,z,t,u*)PermCheck[poly_]:=(permres=False;sp=poly/.MapThread[Rule,{{x,y,z,t,u},Table[v[n],{n,1,5}]}];pvars=Variables[sp];If[Sort[pvars]Sort[Array[v,Length[pvars]]],permres=True];If[permres,myVal=valAbsPowers[sp];perms=Permutations[pvars];For[permcount=1,permcount≤Length[perms]&&permres,permcount++,perm=perms[[permcount]];rules=Table[pvars[[varcount]]perm[[varcount]],{varcount,1,Length[pvars]}];poly1=sp/.rules;If[valAbsPowers[poly1]>myVal,permres=False]]];!permres);(*Thisfunctionselectsonlyonepolynomialfromonesobtainedbysignchangesofvariablesx,y,z,t,u*)SignCheck[poly_]:=(signres=True;polynew=poly/.MapThread[Rule,{{x,y,z,t,u},Table[v[n],{n,1,5}]}];myVal=valPowers[polynew];signs=Tuples[{-1,1},Length[Variables[polynew]]];For[scount=1,scount≤Length[signs]&&signres,scount++,sign=signs[[scount]];rules=Table[pvars[[varcount]]sign[[varcount]]pvars[[varcount]],{varcount,1,Length[Variables[polynew]]}];poly1=polynew/.rules;If[valPowers[poly1]>myVal||valPowers[-poly1]>myVal,signres=False;scount=Length[signs]+1];];!signres);(*NowweupdatethefunctionsExplicitandExplicitFamilytoexcludeallpolynomialsfromeachequivalenceclassexceptone*)Explicit[poly_]:=gcdCheck[poly]||PermCheck[poly]||SignCheck[poly]ExplicitFamily[poly_]:=PermCheck[poly]
Now the function printRangeH returns only one polynomial from each equivalence class. For example, here are the lists up to size 6.
Now let us find integer solutions to the equations P=0 for the polynomials P ordered by their size H. As we can see, the first polynomials have at most one variable. Equations in one variable are easy and can be solved by the Reduce function in Mathematica. For example:
Now let us exclude such equations from our list. To do this, we update the function ExplicitFamily as follows:
After this, the list of remaining polynomials up to size 6 is:
As we can see, the first remaining polynomial is x+y. The Mathematica function Reduce can easily parametrize all integer solutions to the corresponding equation x+y=0:
Now let us exclude such equations from our list. To do this, we update the function ExplicitFamily as follows:
After this, the list of remaining polynomials up to size 8 is:
The smallest remaining equation is xy=0. This can also be easily solved by the Reduce function:
More generally, any equation of the form QR=0 for non-constant polynomials Q,R reduces to a pair of equations Q=0 and R=0. Hence, it suffices to consider only equations P=0 for P irreducible over the rationals. In Mathematica, this can be checked using the function IrreduciblePolynomialQ. For example:
So, let us update the function Explicit as follows:
After this, the list of remaining polynomials up to size 8 is:
The smallest remaining equation is 1+xy=0. This can also be easily solved by the Reduce function:
More generally, if a polynomial P+r is reducible over Q for some rational number r, then the equation P=0 can be rewritten as QR=c for some integer c. Such equations have been discussed in Section 1.3 of the book. The following code checks whether P+r is reducible for any rational number r=a/b with |a|<=50 and |b|<=5.
We can then eliminate such equations by updating the function Explicit as follows:
After this, the list of remaining polynomials up to size 10 is:
In this example, (0,0) is the only real solution and is therefore the only integer solution. More generally, if the set of real solutions is bounded in any of the variables, then there are only finitely many integer values of this variable to check, see Section 1.4 of the book. Such equations can be identified as follows:
We can then eliminate such equations by updating the function Explicit as follows:
After this, the list of remaining polynomials up to size 10 is:
Obviously, these expressions involving square roots cannot be acceptable descriptions of the set of integer solutions. However, both these equations have only two monomials, and the general method for solving all such equations has been presented in Section 1.6 of the book. To eliminate such equations, we modify the ExplicitFamily function as follows:
After this, the list of remaining polynomials up to size 10 is:
Some of the listed equations of size 10 can be simplified by linear substitutions. For example, the equation x+x y+t z = 0 can be simplified to x u+t z = 0 where u=y+1. This equation has two monomials and has been already excluded. The following Mathematica function tries some easy linear substitutions and identifies equations that can be reduced by such substitutions to equations of smaller size.
We can then eliminate such equations by updating the function Explicit as follows:
After this, the list of remaining polynomials up to size 11 is:
see Section 4.1 of the book. The code for identifying these families of equations is as follows:
We then eliminate such equations by updating the functions ExplicitFamily and Explicit as follows:
After this, the list of remaining polynomials up to size 14 is:
and therefore obviously no integer solutions. The following code eliminates equations that have no solutions modulo m for some m<=100.
After the corresponding update of the ExplicitFamily and Explicit functions:
the list of remaining polynomials up to size 14 becomes:
Then the list of remaining polynomials up to size 15 becomes:
Then the list of remaining polynomials up to size 15 becomes:
All the remaining equations of size 14 have three monomials. Sections 4.3.1 and 4.3.2 of the book explain how to solve a large family of such equations. The following code eliminates equations from this family:
After including this in the Explicit function:
the list of remaining polynomials up to size 16 becomes:
After including this in the Explicit function:
the list of remaining polynomials up to size 17 becomes:
have been left open in the book, see Open Question 4.17.
Equations in two variables
Equations in two variables
Let us now consider equations in two variables. For size less than 32 the equations must have degree at most 4, hence the list of possible monomials is {x^4,x^3 y,x^2 y^2,x y^3,y^4, x^3 ,x^2 y ,x y^2 ,y^3,x^2 ,x y ,y^2 ,x ,y,1}.
Let us generate the list of all two-variable equations of size up to 20 not excluded so far.
Such equations have been discussed in Section 3.3.2 in the book: it turns out that for any real solution (x,y) either |x| or |y| or |x+y| or |x-y| is bounded. This allows us to find all integer solutions easily. Such equations can be eliminated with the following function:
Now we include this into the Explicit function:
Then the remaining two-variable equations up to size 23 are:
All these equations are quadratic in y with discriminant D(x) “close” to being a perfect square, see Section 3.3.1 of the book. Many equations of this type can be eliminated by the following code:
Now we include this into the Explicit function:
Then the remaining two-variable equations up to size 25 are:
As you can see, the described methods resolve all two-variable equations up to size 24. Out of the remaining equations of size 25, the first three are Thue equations, that is, equations of the form P(x,y)=c where P is an irreducible homogeneous polynomial and c is a non-zero integer. Such equations can be solved by standard methods that are incorporated in the Reduce function of Mathematica. For example:
Section 3.3.3 of the book defines Thue-like equations as equations of the form P(x,y)=c where P is an arbitrary (not necessarily irreducible) homogeneous polynomial and c any integer, and explains that such equations can be solved as well. The following function identifies Thue-like equations:
Because the last three families of equations do not depend on their coefficients they can be eliminated using function ExplicitFamily:
Then the remaining two-variable equations up to size 26 are:
We now update the Explicit function:
Most of other remaining two-variable equations of size 26 belong to the family ax+by=P(x,y) discussed in Section 3.3.9 of the book. The following function identifies such equations:
Because this family does not depend on their coefficients, it can be eliminated in ExplicitFamily:
Then the remaining two-variable equations up to size 27 are:
are exactly the ones listed in Table 3.19 of the book: they are the smallest two-variable equations for which the integer solutions are not explicitly known. We know that there are algorithms that can in principle solve these equations in finite time, but either the algorithms are too complicated to implement, or their running time is too long to wait.
Because these families do not depend on the values of non-zero coefficients, they can be eliminated in ExplicitFamily:
Let us now list all two-variable equations of size up to 29 that do not belong to any of the listed solvable families:
These are exactly the smallest and the next-smallest open two-variable equations, see Section 3.5.1 of the book.
Existence of integer solutions
Existence of integer solutions
We next discuss the problem of determining whether a given Diophantine equation has any integer solution, see Chapter 7 of the book. For all equations that have an obvious small solution, the answer to this Problem is trivially “Yes”, hence all such equations can be excluded. In particular, all equations with no free term can be immediately excluded because they have a solution with all variables 0. We therefore modify the program for generating equations so that it generates equations such that the last monomial in the list is always present.
If we now use a list of monomials with the last monomial 1, it will only generate equations with a free term.
As mentioned above, all equations with small solutions can be eliminated. We next modify the Explicit function so that it eliminates all equations for which the Mathematica command FindInstance is able to find an integer solution.
Here is the list of all equations with no small integer solutions of size up to 10.
In fact, the listed equations have no integer solutions at all for an obvious reason: either they have no real solutions or they have no solutions modulo some integer. We next eliminate such equations.
Equations that have real solutions and solutions modulo every integer but still do not have any integer solutions are called counterexamples to the integral Hasse principle. The smallest such counterexample has size 13, as can be seen from the following code.
Below is the list of all counterexamples to the integral Hasse principle of size up to 20.
As we can see, all the listed counterexamples to the integral Hasse principle are cubic equations in two or three variables, so it is interesting what are the smallest counterexamples in other categories. For example, the smallest quadratic counterexamples have size 25, as witnessed by the following code:
Now we return to the general equations. As we can see, most of the listed counterexamples to the integral Hasse principle are either of the form QR=c for some integer c, or have a set of real solutions restricted in one of the variables, or are in Weierstrass form, or are quadratic equations. For all these families, the problem of existence of integer solution has been discussed in the book. We next eliminate such examples.
To speed up the search, from now on we consider only equations in at most three variables.
Now let us produce the list of remaining equations in at most three variables up to size 22.
Then the list of the remaining equations up to size 29 with at most 3 variables is:
Solutions of this size can be easily found by function LargeSolCheck discussed in the previous section:
Let us now exclude the equations for which this function is able to find an integer solution.
Now the remaining equations in at most 3 variables up to size 30 are
which is beyond the range that the function LargeSolCheck explored. The smallest equations that we were not able to manually solve are the equations:
x^4+2x+y^3−y−2=0
x^4+xy+y^3+4=0
x^4+x+y^3+y+4=0
x^3−x^2+xy+y^4+1=0
x^4+2x+y^3−y−2=0
x^4+xy+y^3+4=0
x^4+x+y^3+y+4=0
x^3−x^2+xy+y^4+1=0
which are the equations left open in Section 7.3.1 of the book.
Conclusions
Conclusions
This document presents a sample of the Mathematica code that has been used in the book to automatically exclude easy families of Diophantine equations and produce difficult equations for manual solving. As mentioned in the introduction, there are many other way the code can be used, after obvious modifications. For example, the following code outputs all equations in at most 3 variables of size up to 20 that have no solutions modulo some small integer (and therefore no integer solutions), but cannot be solved by other methods described in Chapter 1 of the book. These equations can be used as exercises for students who learning this method. Note that the standard code that eliminates equations solvable by ModCheck is replaced by the opposite code that. conversely, includes only equations solvable by this method.
We end by mentioning that some of the code used for the book is not included due to the length restriction of this document. For example, we did not include the code for generating homogeneous equations used in Chapter 6, nor the code for generating equations ordered by length or by canonical ordering used in Chapter 8. That code is available on request.
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Polynomial Diophantine equations: a systematic approach
by Bogdan Grechuk & Aubrey de Grey
Wolfram Community, STAFF PICKS, October 23, 2024
https://community.wolfram.com/groups/-/m/t/3305960
by Bogdan Grechuk & Aubrey de Grey
Wolfram Community, STAFF PICKS, October 23, 2024
https://community.wolfram.com/groups/-/m/t/3305960