mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-09-16, 13:36   #1
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default 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+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
grandpascorpion is offline   Reply With Quote
Old 2009-09-16, 15:12   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by grandpascorpion View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2009-09-16, 15:53   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,323 Posts
Default

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.
fivemack is offline   Reply With Quote
Old 2009-09-16, 16:51   #4
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

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.
grandpascorpion is offline   Reply With Quote
Old 2009-09-16, 17:00   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by grandpascorpion View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2009-09-16, 17:24   #6
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

142638 Posts
Default

Quote:
Originally Posted by grandpascorpion View Post
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>
]

Last fiddled with by fivemack on 2009-09-16 at 17:25
fivemack is offline   Reply With Quote
Old 2009-09-16, 21:04   #7
maxal
 
maxal's Avatar
 
Feb 2005

22·32·7 Posts
Default

Quote:
Originally Posted by grandpascorpion View Post
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.
Attached Files
File Type: pdf browkin8572.pdf (146.3 KB, 210 views)

Last fiddled with by maxal on 2009-09-16 at 21:24
maxal is offline   Reply With Quote
Old 2009-09-16, 22:38   #8
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

Thank you maxal. Very interesting paper.
grandpascorpion is offline   Reply With Quote
Old 2009-09-17, 15:32   #9
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

Quote:
Originally Posted by maxal View Post
(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.

Last fiddled with by maxal on 2009-09-17 at 15:35
maxal is offline   Reply With Quote
Old 2009-09-20, 16:31   #10
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

1111101112 Posts
Default

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
grandpascorpion is offline   Reply With Quote
Old 2009-09-22, 19:32   #11
maxal
 
maxal's Avatar
 
Feb 2005

25210 Posts
Default

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
maxal is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 11:10.

Sat Nov 28 11:10:38 UTC 2020 up 79 days, 8:21, 3 users, load averages: 1.60, 1.22, 1.14

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.