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. ([url]http://www.primepuzzles.net/puzzles/puzz_413.htm[/url])

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

[QUOTE=grandpascorpion;189944]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.

[/QUOTE]

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.

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

[url]http://magma.maths.usyd.edu.au/calc/[/url]

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.

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.

[QUOTE=grandpascorpion;189970]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).

.[/QUOTE]

This will not help.

[QUOTE=grandpascorpion;189970]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).
[/QUOTE]

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);
[/code]

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>
]
[/code]

[QUOTE=grandpascorpion;189944]Background: I'm trying to create an a.p. of 6 or more terms. ([url]http://www.primepuzzles.net/puzzles/puzz_413.htm[/url])[/quote]
That's a tough problem.
If [tex]n[/tex] is such that for some [tex]k[/tex] of its divisors: [tex]d_1, d_2, \dots, d_k[/tex], we have
[tex]\frac{n}{d_i} + d_i = m + q\cdot i[/tex] for [tex]i=1,2,\dots,k[/tex]
then
[tex](m+qi)^2 - 4n = \left( \frac{n}{d_i} - d_i \right)^2[/tex] for [tex]i=1,2,\dots,k[/tex]
form a sequence of [tex]k[/tex] squares whose second differences equal the constant [tex]2 q^2[/tex].

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

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 [tex]2 q^2[/tex] makes it even harder.

Thank you maxal. Very interesting paper.

[QUOTE=maxal;190010][tex](m+qi)^2 - 4n = \left( \frac{n}{d_i} - d_i \right)^2[/tex] for [tex]i=1,2,\dots,k[/tex]
form a sequence of [tex]k[/tex] squares whose second differences equal the constant [tex]2 q^2[/tex].[/quote]
I forgot to mention an important property - this sequence does not represent squares of consecutive terms of an arithmetic progression.

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

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.

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 [tex]\left( \frac{n}{d_i} + d_i \right)^2[/tex] is trivial while the sequence [tex]\left( \frac{n}{d_i} - d_i \right)^2[/tex] is non-trivial.