[GAP Forum] cubic equations
Stefan Kohl
kohl at mathematik.uni-stuttgart.de
Tue Feb 12 13:02:53 GMT 2008
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/
---------------------------------------------------------------------------
More information about the Forum
mailing list