mersenneforum.org > Math Lucas-like sequence of polynomials: a tricky thing
 Register FAQ Search Today's Posts Mark Forums Read

 2009-01-13, 18:06 #1 XYYXF     Jan 2005 Minsk, Belarus 24×52 Posts 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
 2009-01-14, 01:26 #2 Jens K Andersen     Feb 2006 Denmark 3468 Posts
2009-01-14, 05:31   #3
XYYXF

Jan 2005
Minsk, Belarus

24·52 Posts

Quote:
 Originally Posted by Jens K Andersen OEIS search
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

2009-01-14, 17:25   #4
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by XYYXF 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.

 2009-01-30, 11:31 #5 T.Rex     Feb 2004 France 32×103 Posts 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
2009-03-11, 17:20   #6
maxal

Feb 2005

11×23 Posts

Quote:
 Originally Posted by XYYXF 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

2010-08-26, 21:46   #7
XYYXF

Jan 2005
Minsk, Belarus

24×52 Posts

maxal, thanks you a lot, all is clear now.
Quote:
 Originally Posted by XYYXF 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

2010-08-27, 11:52   #8
R.D. Silverman

Nov 2003

22×5×373 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post lavalamp Puzzles 29 2009-12-14 15:27 T.Rex Math 7 2007-06-04 21:30 XYYXF Math 13 2006-09-01 15:44 mfgoode Puzzles 16 2006-01-25 16:32 pseudorandom Hardware 11 2006-01-23 08:53

All times are UTC. The time now is 19:30.

Sun Jan 16 19:30:09 UTC 2022 up 177 days, 13:59, 0 users, load averages: 0.90, 1.13, 1.23