Lucas-like sequence of polynomials: a tricky thing

XYYXF · 2009-01-13, 18:06

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

x²-2
x⁴-4x²+2
x⁸-8x⁶+20x⁴-16x²+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?

Jens K Andersen · 2009-01-14, 01:26

OEIS search

XYYXF · 2009-01-14, 05:31

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... :-)

CRGreathouse · 2009-01-14, 17:25

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

x²-2
x⁴-4x²+2
x⁸-8x⁶+20x⁴-16x²+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.

T.Rex · 2009-01-30, 11:31

Rather consider:

S(0)=2
S(1)=x
S(2)=x²-2
S(3)=x³-3x
and so on.

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

This is related to the LLT.

T.

maxal · 2009-03-11, 17:20

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

x²-2
x⁴-4x²+2
x⁸-8x⁶+20x⁴-16x²+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)$ .

XYYXF · 2010-08-26, 21:46

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

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

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.

2009-01-13, 18:06	#1
XYYXF Jan 2005 Minsk, Belarus 110010000₂ 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 x²-2 x⁴-4x²+2 x⁸-8x⁶+20x⁴-16x²+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-30, 11:31	#5
T.Rex Feb 2004 France 13·73 Posts	Rather consider: S(0)=2 S(1)=x S(2)=x²-2 S(3)=x³-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

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

2009-01-14, 01:26	#2
Jens K Andersen Feb 2006 Denmark 2·5·23 Posts	OEIS search