 mersenneforum.org A missing identity
 Register FAQ Search Today's Posts Mark Forums Read 2008-02-27, 00:42 #1 fivemack (loop (#_fork))   Feb 2006 Cambridge, England 2·29·109 Posts A missing identity I feel that L2185A, an Aurifeullian factor of lucas(2185) which equals 5*fib(437)^2 - 5*fib(437) + 1, ought to be an SNFS-number. But I can't work out how to attack it. There are any number of identities writing one Fibonacci number in terms of others, but they're almost all homogeneous in terms of some pair of Fibonacci numbers - for example, fib(437) = A^3 + 3AB^2 + B^3 where A=fib(145), B=fib(146) - and so no use if I want to expand an expression containing both fib(437) and fib(437)^2. fib(3n) = 5*fib(n)^3 + 3*fib(n), but 437 isn't a multiple of 3, and a bit of lattice reduction fails to find any expressions for fib(437) in terms of powers of fib(145) or fib(146) alone with reasonable coefficients.   2008-03-01, 10:22 #2 maxal   Feb 2005 22·32·7 Posts why not simply to represent the number N=fib(437) as whatever best polynomial of degree 2 or 3 (not even referring to fibonaccity of N) and substitute it into 5*N^2 - 5*N + 1 to get its representation as a polynomial of degree 4 or 6 ? If that does not work, please explain why and, in particular, what are the "reasonable coefficients". Last fiddled with by maxal on 2008-03-01 at 10:25   2008-03-03, 01:46   #3
maxal

Feb 2005

111111002 Posts Quote:
 Originally Posted by fivemack any expressions for fib(437) in terms of powers of fib(145) or fib(146) alone with reasonable coefficients.
There is an expression in terms of powers of L(145) and L(146) (Lucas numbers):

5 * F(437)^2 = L(874) + 2 = (3*L(876) + L(870))/8 + 2
= (L(146)^6 - 6*L(146)^4 + 9*L(146)^2 - 2)*3/8
+ (L(145)^6 + 6*L(145)^4 + 9*L(145)^2 + 2)*1/8 + 2

5 * F(437) = (3*L(3*146) - L(3*145)) / 2
= (L(146)^3 - 3*L(146))*3/2 - (L(145)^3 + 3*L(145))/2

Therefore:

5*F(437)^2 - 5*F(437) + 1 = [ (3*L(146)^6 - 18*L(146)^4 - 12*L(146)^3 + 27*L(146)^2 + 36*L(146)) + (L(145)^6 + 6*L(145)^4 + 4*L(145) + 9*L(145)^2 + 12*L(145)) + 20 ] / 8

Does that work for you?   2008-03-03, 14:11 #4 fivemack (loop (#_fork))   Feb 2006 Cambridge, England 632210 Posts The problem is that SNFS requires a homogeneous polynomial as input; so you can use a decomposition of Fib(x) as a normal polynomial in Fib(y) and use A=Fib(y), B=1, or you can decompose it as a homogeneous polynomial in A=Fib(y) and B=Fib(z). What you can't use is a non-homogeneous polynomial in Fib(y) and Fib(z). 'reasonable coefficients' means two or three digits; constructions giving polynomials with coefficients some power of the input have most of the drawbacks of GNFS.   2008-03-04, 05:04 #5 maxal   Feb 2005 22·32·7 Posts OK. Here is a homogeneous polynomial of the degree 4 of x=L(219) and y=L(218): 5*F(437)^2 - 5*F(437) + 1 = ( y^4 - 3*x*y^3 + 9*x^2*y^2 - 7*x^3*y + 11*x^4 ) / 25 Similarly, this is a homogeneous polynomial of the degree 8 of x=L(110) and y=L(109): 5*F(437)^2 - 5*F(437) + 1 = ( 11*y^8 - 76*x*y^7 + 222*x^2*y^6 - 308*x^3*y^5 + 170*x^4*y^4 + 38*x^5*y^3 + 37*x^6*y^2 + 6*x^7*y + x^8 ) / 625  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post jcrombie Miscellaneous Math 51 2013-09-09 18:51 only_human Software 2 2012-05-11 13:43 ewmayer Lounge 12 2010-02-04 21:26 grandpascorpion Math 2 2009-11-10 20:44 SPWorley Math 6 2009-08-28 18:02

All times are UTC. The time now is 08:32.

Fri Oct 23 08:32:26 UTC 2020 up 43 days, 5:43, 0 users, load averages: 1.71, 1.41, 1.40