mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Diophantine Question (https://www.mersenneforum.org/showthread.php?t=12463)

 grandpascorpion 2009-09-16 13:36

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

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

[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.

 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

[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.

 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=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.

 fivemack 2009-09-16 17:24

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

 maxal 2009-09-16 21:04

1 Attachment(s)
[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 $$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=maxal;190010]$$(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$$.[/quote]
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.

All times are UTC. The time now is 16:31.