Diophantine Question

grandpascorpion · 2009-09-16, 13:36

I have a 4th degree polynomial F(k) and I'm looking for a algorithm/heuristic to find solutions of the form: f(k) = r^2 where k, r, and F(x)'s coefficients are all integers.

(I'm looking for something better than setting r to particular values and solving the resulting quartic)

I actually have several such similar polynomials (call them F(i)(k)) and my goal is to find k's such that F(i)(k) = r(i)^2 for several of these polynomials (again where all the variables/coefficients are all integers). My goal would be to find an x which solved several of these relations.

Background: I'm trying to create an a.p. of 6 or more terms. (http://www.primepuzzles.net/puzzles/puzz_413.htm)

x=n/d
y=(n+k)/(d+k)

When,
a = n*(n+k)*(k+2*d)
b = d*(d+k)*(2*n+k)

a*b is a number such that ax+b/x, a+b and ay+b/y form an arithmetic progression of three terms.

For a given x=n/d, I'm trying to find rational solutions for z(v) where

z(v)a + b/z(v) = v(xa + b/x)

for
v = 2, 3, and 4
v = -2, 2, and 3
v = -3, -2, and 2
OR
v= -4, -3, and -2

The quartic polynomials F(v)(k) evaluating to the square of an integer allows for rational solutions to z(v).

Unfortunately, these polynomials are rather gnarly. For instance,
F(2)(k) works out to be:

(4*n^6 - 4*d*n^5 - 3*d^2*n^4 + 6*d^3*n^3 - 4*d^4*n^2)*k^4 +

(8*n^7 + 8*d*n^6 - 26*d^2*n^5 + 10*d^3*n^4 + 6*d^4*n^3 - 12*d^5*n^2)*k^3 +

(4*n^8 + 28*d*n^7 - 23*d^2*n^6 - 32*d^3*n^5 + 42*d^4*n^4 - 24*d^5*n^3 - 8*d^6*n^2)*k^2 +

(16*d*n^8+ 16*d^2*n^7 - 52*d^3*n^6 + 20*d^4*n^5 + 12*d^5*n^4 - 24*d^6*n^3)*k +

(16*d^2*n^8 - 16*d^3*n^7 - 12*d^4*n^6 + 24*d^5*n^5 - 16*d^6*n^4)

At present, I'm just trying different k up to a threshold for each n/d and have found numerous 5 term sequences. (Actually, I found that simplifying the problem to use y=(n+k)/(d+k) resulted in finding many more solutions than when y some totally random rational < x).

===============================================

Any pointers would be appreciated. Thanks

R.D. Silverman · 2009-09-16, 15:12

Quote:

Originally Posted by grandpascorpion

I have a 4th degree polynomial F(k) and I'm looking for a algorithm/heuristic to find solutions of the form: f(k) = r^2 where k, r, and F(x)'s coefficients are all integers.

We would ALL like such an algorithm. Unfortunately, no efficient ones
are known.

r^2 = F(k) is an elliptic (or hyper-Elliptic curve). While methods
are known for finding integer points, they are generally ad-hoc.
One general method is to find the Heegner points, but of course there
is no general method for doing that either.

Finding integer points on elliptic curves is a very very very DEEP subject.

And of course, there will only be finitely many. There may be none
if the rank of the curve is 0.

fivemack · 2009-09-16, 15:53

Yes, finding points on elliptic curves is a deep subject; it's just about practical for smallish curves, but the algorithms are real pigs to implement and you need lots of them. If you can afford $400, buy a copy of the Magma computer algebra system; for small examples you can use

http://magma.maths.usyd.edu.au/calc/

and say for example

E:=EllipticCurve([0,0,1,-7,6]);
Rank(E);
IntegralPoints(E);

I can't quite remember the sequence of manipulations required to convert a quartic polynomial and a single rational point into an EllipticCurve and a map back to the y^2=quartic model.

grandpascorpion · 2009-09-16, 16:51

Thank you both for your feedback.

I wonder if a better tack would be to check if one (or more) of these polynomials (in three variables: n,d and k) can be factored into two smaller polynomials say g(n,d,k) and h(n,d,k).

By setting g(n,d,k) = h(n,d,k), perhaps I make some progress simplifying it(say by using substitution).

Is there a tool (preferably free or on-line) that can check if a multivariable polynomial is irreducible. I have PARI installed but it can only check/factor single-variable polynomials.

Could Magma handle something like that? I tried Wolfram Alpha but it exceeded the upper bound on query length.

R.D. Silverman · 2009-09-16, 17:00

Quote:

Originally Posted by grandpascorpion

Thank you both for your feedback.

I wonder if a better tack would be to check if one (or more) of these polynomials (in three variables: n,d and k) can be factored into two smaller polynomials say g(n,d,k) and h(n,d,k).

.

This will not help.

fivemack · 2009-09-16, 17:24

Quote:

Originally Posted by grandpascorpion

Thank you both for your feedback.

I wonder if a better tack would be to check if one (or more) of these polynomials (in three variables: n,d and k) can be factored into two smaller polynomials say g(n,d,k) and h(n,d,k).

This is trivial with magma:

Code:

P<n,d,k>:=PolynomialRing(Rationals(),3);
F:=(4*n^6 - 4*d*n^5 - 3*d^2*n^4 + 6*d^3*n^3 - 4*d^4*n^2)*k^4 +
(8*n^7 + 8*d*n^6 - 26*d^2*n^5 + 10*d^3*n^4 + 6*d^4*n^3 - 12*d^5*n^2)*k^3 +
(4*n^8 + 28*d*n^7 - 23*d^2*n^6 - 32*d^3*n^5 + 42*d^4*n^4 - 24*d^5*n^3 - 8*d^6*n^2)*k^2 +
(16*d*n^8+ 16*d^2*n^7 - 52*d^3*n^6 + 20*d^4*n^5 + 12*d^5*n^4 - 24*d^6*n^3)*k +
(16*d^2*n^8 - 16*d^3*n^7 - 12*d^4*n^6 + 24*d^5*n^5 - 16*d^6*n^4);
Factorisation(F);

but the factors are uninteresting:

Code:

[
    <d + 1/2*k, 1>,
    <n, 2>,
    <n + k, 1>,
    <n^5*d + 1/2*n^5*k - n^4*d^2 + 1/2*n^4*d*k + 1/2*n^4*k^2 - 3/4*n^3*d^3 - 
        15/8*n^3*d^2*k - 1/2*n^3*d*k^2 + 3/2*n^2*d^4 + 5/4*n^2*d^3*k - 
        3/8*n^2*d^2*k^2 - n*d^5 - 1/4*n*d^4*k + 3/4*n*d^3*k^2 - 1/2*d^5*k - 
        1/2*d^4*k^2, 1>
]

maxal · 2009-09-16, 21:04

Quote:

Originally Posted by grandpascorpion

Background: I'm trying to create an a.p. of 6 or more terms. (http://www.primepuzzles.net/puzzles/puzz_413.htm)

That's a tough problem.
If $n$ is such that for some $k$ of its divisors: $d_1, d_2, \dots, d_k$ , we have
$\frac{n}{d_i} + d_i = m + q\cdot i$ for $i=1,2,\dots,k$
then
$(m+qi)^2 - 4n = \left( \frac{n}{d_i} - d_i \right)^2$ for $i=1,2,\dots,k$
form a sequence of $k$ squares whose second differences equal the constant $2 q^2$ .

For example, $n=36400$ gives a sequence of squares
$33^2, 150^2, 213^2, 264^2, 309^2$
whose second differences equal $2\cdot 27^2 = 1458$ .

Finding sequences of squares with constant second differences is a rather hard task (see the attached paper) and additional requirement of having difference of the special form $2 q^2$ makes it even harder.

grandpascorpion · 2009-09-16, 22:38

Thank you maxal. Very interesting paper.

maxal · 2009-09-17, 15:32

Quote:

Originally Posted by maxal

$(m+qi)^2 - 4n = \left( \frac{n}{d_i} - d_i \right)^2$ for $i=1,2,\dots,k$
form a sequence of $k$ squares whose second differences equal the constant $2 q^2$ .

I forgot to mention an important property - this sequence does not represent squares of consecutive terms of an arithmetic progression.

While the sequence
$(m+qi)^2 = \left( \frac{n}{d_i} + d_i \right)^2$
also has the second differences equal $2 q^2$ , it is a trivial and uninteresting sequence of this kind.

grandpascorpion · 2009-09-20, 16:31

Actually ther\ latter relation is precisely for what I'm looking to find solutions (for i=1,2 ... k where k>=6 and all the variables involved are integers). And, there's no need to square both sides of the equation since both sides of the equation must be positive.

I understand if it's not considered interesting by you. But, it's not trivial to calculate, is it? Sorry, if I misunderstood what you meant.

Thanks.

maxal · 2009-09-22, 19:32

I was discussing connection to the problem of finding sequence of squares with a constant second difference. A trivial solution to this problem is given by squares of the terms of an arithmetic progression. A non-trivial (and hard-to-find) solution is a sequence of squares whose bases do not form an arithmetic progression.

In this respect, the sequence of squares $\left( \frac{n}{d_i} + d_i \right)^2$ is trivial while the sequence $\left( \frac{n}{d_i} - d_i \right)^2$ is non-trivial.

2009-09-16, 13:36	#1
grandpascorpion Jan 2005 Transdniestr 503 Posts	Diophantine Question I have a 4th degree polynomial F(k) and I'm looking for a algorithm/heuristic to find solutions of the form: f(k) = r^2 where k, r, and F(x)'s coefficients are all integers. (I'm looking for something better than setting r to particular values and solving the resulting quartic) I actually have several such similar polynomials (call them F(i)(k)) and my goal is to find k's such that F(i)(k) = r(i)^2 for several of these polynomials (again where all the variables/coefficients are all integers). My goal would be to find an x which solved several of these relations. Background: I'm trying to create an a.p. of 6 or more terms. (http://www.primepuzzles.net/puzzles/puzz_413.htm) x=n/d y=(n+k)/(d+k) When, a = n(n+k)(k+2d) b = d(d+k)(2n+k) ab is a number such that ax+b/x, a+b and ay+b/y form an arithmetic progression of three terms. For a given x=n/d, I'm trying to find rational solutions for z(v) where z(v)a + b/z(v) = v(xa + b/x) for v = 2, 3, and 4 v = -2, 2, and 3 v = -3, -2, and 2 OR v= -4, -3, and -2 The quartic polynomials F(v)(k) evaluating to the square of an integer allows for rational solutions to z(v). Unfortunately, these polynomials are rather gnarly. For instance, F(2)(k) works out to be: (4n^6 - 4dn^5 - 3d^2n^4 + 6d^3n^3 - 4d^4n^2)k^4 + (8n^7 + 8dn^6 - 26d^2n^5 + 10d^3n^4 + 6d^4n^3 - 12d^5n^2)k^3 + (4n^8 + 28dn^7 - 23d^2n^6 - 32d^3n^5 + 42d^4n^4 - 24d^5n^3 - 8d^6n^2)k^2 + (16dn^8+ 16d^2n^7 - 52d^3n^6 + 20d^4n^5 + 12d^5n^4 - 24d^6n^3)k + (16d^2n^8 - 16d^3n^7 - 12d^4n^6 + 24d^5n^5 - 16d^6n^4) At present, I'm just trying different k up to a threshold for each n/d and have found numerous 5 term sequences. (Actually, I found that simplifying the problem to use y=(n+k)/(d+k) resulted in finding many more solutions than when y some totally random rational < x). =============================================== Any pointers would be appreciated. Thanks

2009-09-20, 16:31	#10
grandpascorpion Jan 2005 Transdniestr 1F7₁₆ Posts	Actually ther\ latter relation is precisely for what I'm looking to find solutions (for i=1,2 ... k where k>=6 and all the variables involved are integers). And, there's no need to square both sides of the equation since both sides of the equation must be positive. I understand if it's not considered interesting by you. But, it's not trivial to calculate, is it? Sorry, if I misunderstood what you meant. Thanks. Last fiddled with by grandpascorpion on 2009-09-20 at 16:50

2009-09-22, 19:32	#11
maxal Feb 2005 2²×5×13 Posts	I was discussing connection to the problem of finding sequence of squares with a constant second difference. A trivial solution to this problem is given by squares of the terms of an arithmetic progression. A non-trivial (and hard-to-find) solution is a sequence of squares whose bases do not form an arithmetic progression. In this respect, the sequence of squares $\left( \frac{n}{d_i} + d_i \right)^2$ is trivial while the sequence $\left( \frac{n}{d_i} - d_i \right)^2$ is non-trivial. Last fiddled with by maxal on 2009-09-22 at 19:34

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Basic Number Theory 13: Pythagorean triples and a few Diophantine equations	Nick	Number Theory Discussion Group	2	2016-12-18 14:49
Diophantine Equation	flouran	Math	7	2009-12-12 18:48
Simple Diophantine equation	Batalov	Puzzles	3	2009-04-10 11:32
Diophantine problem	philmoore	Puzzles	8	2008-05-19 14:17

2009-09-16, 15:53	#3
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2×7×461 Posts	Yes, finding points on elliptic curves is a deep subject; it's just about practical for smallish curves, but the algorithms are real pigs to implement and you need lots of them. If you can afford $400, buy a copy of the Magma computer algebra system; for small examples you can use http://magma.maths.usyd.edu.au/calc/ and say for example E:=EllipticCurve([0,0,1,-7,6]); Rank(E); IntegralPoints(E); I can't quite remember the sequence of manipulations required to convert a quartic polynomial and a single rational point into an EllipticCurve and a map back to the y^2=quartic model.

2009-09-16, 16:51	#4
grandpascorpion Jan 2005 Transdniestr 767₈ Posts	Thank you both for your feedback. I wonder if a better tack would be to check if one (or more) of these polynomials (in three variables: n,d and k) can be factored into two smaller polynomials say g(n,d,k) and h(n,d,k). By setting g(n,d,k) = h(n,d,k), perhaps I make some progress simplifying it(say by using substitution). Is there a tool (preferably free or on-line) that can check if a multivariable polynomial is irreducible. I have PARI installed but it can only check/factor single-variable polynomials. Could Magma handle something like that? I tried Wolfram Alpha but it exceeded the upper bound on query length.

2009-09-16, 22:38	#8
grandpascorpion Jan 2005 Transdniestr 503 Posts	Thank you maxal. Very interesting paper.