[GAP Forum] cubic equations

[Stefan Kohl]

Dear Forum,

Muniru Asiru asked:

> Please assist me in programming Gap to find x(rational
> number) and y(integer number) so that
> (y-1)x^3+yx^2+(y+1)x-y=0,  y<>1.
> 
> The only solutions I got is (x,y)=(1/2,3).  Could
> anyone help find others?

A general remark in advance: It is well-known that there is no general
algorithm for computing the set of solutions of a diophantine equation,
or even only for deciding whether there is a solution at all.

However, now let's turn to Muniru Asiru's particular equation:

He asks for rational zeros of a certain family of cubic polynomials
with integer coefficients.

For approximating zeros of polynomials with integer coefficients,
GAP provides a function ContinuedFractionApproximationOfRoot( P, n ).
As the name suggests, this function computes the n-th continued fraction
approximation of some real zero of the polynomial P.

     As an example, let's compute the 20th continued fraction
     approximation of the third root of 2:

     gap> x := Indeterminate(Integers);; SetName(x,"x");
     gap> ContinuedFractionApproximationOfRoot(x^3-2,20);
     1348776323/1070524477
     gap> last^3-2;
     1671371601/1226845304290527628130119333

There is also another function ContinuedFractionExpansionOfRoot( P, n ),
which computes the first n terms of the corresponding continued fraction
expansions.

     As an example, let's compute the first 20 terms of the
     continued fraction expansion of the third root of 2:

     gap> ContinuedFractionExpansionOfRoot(x^3-2,20);
     [ 1, 3, 1, 5, 1, 1, 4, 1, 1, 8, 1, 14, 1, 10, 2, 1, 4, 12, 2, 3 ]

Both of these functions require that the leading coefficient of P is
positive, that P(0) is negative and that P has only one positive real zero.
These conditions are satisfied for Muniru Asiru's polynomial if y > 1,
and they are satisfied for its additive inverse if y < 0.

Now note that the continued fraction expansion of a rational number stops
after a finite number of terms.

Given this, we can start to look for solutions.

First we enter Muniru Asiru's family of polynomials:

gap> x := Indeterminate(Integers);; SetName(x,"x");
gap> pol := y -> (y-1)*x^3+y*x^2+(y+1)*x-y;;

Then we look for solutions with y > 1 ...

gap> Filtered([1..500000],
 >              y->Length(ContinuedFractionExpansionOfRoot(pol(y),10)) < 10);
[ 3 ]
gap> ContinuedFractionExpansionOfRoot(pol(3),10);
[ 0, 2 ]
gap> ContinuedFractionApproximationOfRoot(pol(3),10);
1/2

... and obtain the solution (1/2,3).

Next we look for solutions with y < 0 ...

gap> Filtered([1..500000],
 >             y->Length(ContinuedFractionExpansionOfRoot(-pol(-y),10)) < 10);
[ 418488 ]
gap> ContinuedFractionExpansionOfRoot(-pol(-418488),10);
[ 0, 1, 1, 5, 4, 2 ]
gap> ContinuedFractionApproximationOfRoot(-pol(-418488),10);
56/103

... and obtain the solution (56/103,-418488).

We can also look what happens slightly below and above -418488:

gap> ContinuedFractionExpansionOfRoot(-pol(-418486),10);
[ 0, 1, 1, 5, 4, 1, 1, 64099453, 1, 1 ]
gap> ContinuedFractionExpansionOfRoot(-pol(-418487),10);
[ 0, 1, 1, 5, 4, 1, 1, 128199214, 9, 2 ]
gap> ContinuedFractionExpansionOfRoot(-pol(-418488),10);
[ 0, 1, 1, 5, 4, 2 ]
gap> ContinuedFractionExpansionOfRoot(-pol(-418489),10);
[ 0, 1, 1, 5, 4, 2, 128199826, 1, 8, 2 ]
gap> ContinuedFractionExpansionOfRoot(-pol(-418490),10);
[ 0, 1, 1, 5, 4, 2, 64100066, 2, 1, 1 ]
gap> ContinuedFractionExpansionOfRoot(-pol(-418491),10);
[ 0, 1, 1, 5, 4, 2, 42733479, 1, 1, 3 ]

... and even still

gap> ContinuedFractionExpansionOfRoot(-pol(-420000),10);
[ 0, 1, 1, 5, 4, 2, 85093, 1, 14, 1 ]

If one wishes, one could probably use this pattern to greatly reduce
computation time when looking for further solutions.

Best wishes,

     Stefan Kohl

---------------------------------------------------------------------------
http://www.cip.mathematik.uni-stuttgart.de/~kohlsn/
---------------------------------------------------------------------------