mersenneforum.org  

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

Reply
 
Thread Tools
Old 2009-01-13, 18:06   #1
XYYXF
 
XYYXF's Avatar
 
Jan 2005
Minsk, Belarus

19016 Posts
Default Lucas-like sequence of polynomials: a tricky thing

Somewhere in 2001 I tried to improve a Lucas-Lehmer test, doing several iterations at once. So, if we have x as an intermediate result, we obtain

x2-2
x4-4x2+2
x8-8x6+20x4-16x2+2
and so on.

I did some calculations by hand (I was on holiday in a countryside and had no computer) and noticed that the coefficients of every polynomial could be easily factored.

I conjectured a very surprising and tricky general factorization of these coefficients, involving such strange things as the number of units in binary representation, etc:

http://www.primefan.ru/stuff/primes/polynomials.pdf

E.g., the polynomial of degree 256 has the following coefficients:
http://www.primefan.ru/stuff/primes/256.txt

With a computer I checked this formula up to high powers and found no counter-example.

In Nov 2002 I asked the PrimeNumbers Yahoo! group about that but with no success:
http://tech.groups.yahoo.com/group/p...s/message/9577

In Jan 2003 I tried to ask the NMBRTHRY community but my e-mail was rejected. The same file "polynomials.pdf" is still lying in the Articles subfolder of the Files section of PrimeNumbers Yahoo! group since that time:
http://tech.groups.yahoo.com/group/p...iles/Articles/

Recently I digged up this stuff and decided to post it there. Maybe something is already known about these tricky factorizations of the polynomial coefficients?

Last fiddled with by XYYXF on 2009-01-13 at 18:36
XYYXF is offline   Reply With Quote
Old 2009-01-14, 01:26   #2
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

111001102 Posts
Default

OEIS search
Jens K Andersen is offline   Reply With Quote
Old 2009-01-14, 05:31   #3
XYYXF
 
XYYXF's Avatar
 
Jan 2005
Minsk, Belarus

24·52 Posts
Default

Quote:
Originally Posted by Jens K Andersen View Post
I knew about the relation to Lucas polynomials yet in 2002:
http://tech.groups.yahoo.com/group/p...s/message/9577

My coefficients should come from the triangle
http://www.research.att.com/~njas/sequences/A108045

I see some relations to binomial coefficients in your link; will try to prove my conjecture using this... :-)

Last fiddled with by XYYXF on 2009-01-14 at 05:35
XYYXF is offline   Reply With Quote
Old 2009-01-14, 17:25   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by XYYXF View Post
Somewhere in 2001 I tried to improve a Lucas-Lehmer test, doing several iterations at once. So, if we have x as an intermediate result, we obtain

x2-2
x4-4x2+2
x8-8x6+20x4-16x2+2
and so on.
Well, the number of squarings is already optimal, so at best you'd be reducing the number of additions. Since the additions are (with probability around 1 - 2*2^-(limb size), or about 99.99999995% for 32 bits) likely to involve only 1 limb, your savings are bounded above (in the average case) by about twice the exponent in cycles. For exponents around 10^8, that would be 100 ms on a 2 GHz chip.
CRGreathouse is offline   Reply With Quote
Old 2009-01-30, 11:31   #5
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2·33·17 Posts
Default

Rather consider:

S(0)=2
S(1)=x
S(2)=x2-2
S(3)=x3-3x
and so on.

where S(n) = x S(n-1) - S(n-2) Tchebitchev.

This is related to the LLT.

T.

Last fiddled with by T.Rex on 2009-01-30 at 11:42
T.Rex is offline   Reply With Quote
Old 2009-03-11, 17:20   #6
maxal
 
maxal's Avatar
 
Feb 2005

3748 Posts
Default

Quote:
Originally Posted by XYYXF View Post
Somewhere in 2001 I tried to improve a Lucas-Lehmer test, doing several iterations at once. So, if we have x as an intermediate result, we obtain

x2-2
x4-4x2+2
x8-8x6+20x4-16x2+2
and so on.

I did some calculations by hand (I was on holiday in a countryside and had no computer) and noticed that the coefficients of every polynomial could be easily factored.

I conjectured a very surprising and tricky general factorization of these coefficients, involving such strange things as the number of units in binary representation, etc:
Your observation is a consequence of the following facts:
Polynomials P_n(x) are elements of Lucas sequence V(x,-1), namely:
P_n(x) = V_{2^n}(x,-1) = \left(\frac{x+\sqrt{x^2-4}}2\right)^{2^n} + \left(\frac{x-\sqrt{x^2-4}}2\right)^{2^n}
which can be also expressed as Chebyshev polynomial:
P_n(x) = 2 T_{2^n}\left(\frac{x}2\right)

An explicit formula for the coefficients of Chebyshev polynomials T_n(x) is given in http://www.research.att.com/~njas/sequences/A053120
The "main" term of this formula is the binomial coefficient {(n+m)/2-1\choose m-1}. Applying Lucas theorem to it, one can express this binomial coefficient as the product of "maximal powers of p ... equals to the number of positive integers m's satisfying inequality", similarly to how you defined \beta_{2i}(k). This way you can derive and prove your formula for P_n(x).

Last fiddled with by maxal on 2009-03-11 at 17:23
maxal is offline   Reply With Quote
Old 2010-08-26, 21:46   #7
XYYXF
 
XYYXF's Avatar
 
Jan 2005
Minsk, Belarus

24·52 Posts
Default

maxal, thanks you a lot, all is clear now.
Quote:
Originally Posted by XYYXF View Post
I conjectured a very surprising and tricky general factorization of these coefficients, involving such strange things as the number of units in binary representation, etc:

http://www.primefan.ru/stuff/primes/polynomials.pdf

E.g., the polynomial of degree 256 has the following coefficients:
http://www.primefan.ru/stuff/primes/256.txt
These url's doesn't work anymore; if someone is still interested, use the following links please:
http://www.primefan.ru/stuff/math/polynomials.pdf
http://www.primefan.ru/stuff/math/256.txt
XYYXF is offline   Reply With Quote
Old 2010-08-27, 11:52   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by maxal View Post
Your observation is a consequence of the following facts:
Polynomials P_n(x) are elements of Lucas sequence V(x,-1), namely:
P_n(x) = V_{2^n}(x,-1) = \left(\frac{x+\sqrt{x^2-4}}2\right)^{2^n} + \left(\frac{x-\sqrt{x^2-4}}2\right)^{2^n}
which can be also expressed as Chebyshev polynomial:
P_n(x) = 2 T_{2^n}\left(\frac{x}2\right)

An explicit formula for the coefficients of Chebyshev polynomials T_n(x) is given in http://www.research.att.com/~njas/sequences/A053120
The "main" term of this formula is the binomial coefficient {(n+m)/2-1\choose m-1}. Applying Lucas theorem to it, one can express this binomial coefficient as the product of "maximal powers of p ... equals to the number of positive integers m's satisfying inequality", similarly to how you defined \beta_{2i}(k). This way you can derive and prove your formula for P_n(x).
All of this masks the underlying group theory. The Lucas sequence is
in fact the orbit of an element of the twisted sub-group of GF(P^2).
The twisted sub-group is the set of elements whose multiplicative
inverse equals their algebraic conjugate. Note that the formula for P_n
above equals z^2^n + z' ^2^n where z and z' are in fact algebraic
conjugates and also note that they are multiplicative inverses. z and z'
are elements of the twisted group.

What the Lucas Lehmer test for M_p really does in a sense is to show
that the analogue of 'primitive root for p in Z/pZ*' exists in the group
whose order is p+1, not p-1. Why p+1 and not p-1?? Because for P =
2^n-1 we know the complete factorization of P+1. The Lucas Lehmer
test is really only exponentiating an element of the twisted group and
showing that it has the correct order.

The recurrence relation x_n = x_{n-1}^2 - 2 happens to have a simple
formula for x_n in terms of z and z'. BTW, it is this same formula that
makes x^2-2 a very poor choice of polynomial for Pollard Rho.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Tricky constant acceleration question lavalamp Puzzles 29 2009-12-14 15:27
Period of Lucas Sequence modulo a prime T.Rex Math 7 2007-06-04 21:30
A tricky way to estimate pi(x) XYYXF Math 13 2006-09-01 15:44
Tricky differentiaton 1 mfgoode Puzzles 16 2006-01-25 16:32
Tricky Problem with AMD 3700+ pseudorandom Hardware 11 2006-01-23 08:53

All times are UTC. The time now is 02:49.


Wed Oct 20 02:49:59 UTC 2021 up 88 days, 21:18, 0 users, load averages: 0.54, 0.85, 0.90

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.