mersenneforum.org > Math Diophantine Question
 Register FAQ Search Today's Posts Mark Forums Read

 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+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
2009-09-16, 15:12   #2
R.D. Silverman

Nov 2003

22×5×373 Posts

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.

 2009-09-16, 15:53 #3 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 18EF16 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 503 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, 17:00   #5
R.D. Silverman

Nov 2003

22·5·373 Posts

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.

2009-09-16, 17:24   #6
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

13×491 Posts

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

Last fiddled with by fivemack on 2009-09-16 at 17:25

2009-09-16, 21:04   #7
maxal

Feb 2005

22×32×7 Posts

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.
Attached Files
 browkin8572.pdf (146.3 KB, 236 views)

Last fiddled with by maxal on 2009-09-16 at 21:24

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

Feb 2005

22·32·7 Posts

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.

Last fiddled with by maxal on 2009-09-17 at 15:35

 2009-09-20, 16:31 #10 grandpascorpion     Jan 2005 Transdniestr 503 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 22·32·7 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 Nick Number Theory Discussion Group 2 2016-12-18 14:49 flouran Math 7 2009-12-12 18:48 Batalov Puzzles 3 2009-04-10 11:32 philmoore Puzzles 8 2008-05-19 14:17

All times are UTC. The time now is 12:06.

Thu Apr 22 12:06:44 UTC 2021 up 14 days, 6:47, 0 users, load averages: 1.86, 2.18, 2.01