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[sup]2[/sup]-2
x[sup]4[/sup]-4x[sup]2[/sup]+2
x[sup]8[/sup]-8x[sup]6[/sup]+20x[sup]4[/sup]-16x[sup]2[/sup]+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:

[url]http://www.primefan.ru/stuff/primes/polynomials.pdf[/url]

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

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:
[url]http://tech.groups.yahoo.com/group/primenumbers/message/9577[/url]

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:
[url]http://tech.groups.yahoo.com/group/primenumbers/files/Articles/[/url]

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?

[URL="http://www.research.att.com/~njas/sequences/?q=%221+-8+20+-16+2%22"]OEIS search[/URL]

[QUOTE=Jens K Andersen;158620][URL="http://www.research.att.com/~njas/sequences/?q=%221+-8+20+-16+2%22"]OEIS search[/URL][/QUOTE]
I knew about the relation to [url=http://mathworld.wolfram.com/LucasPolynomial.html]Lucas polynomials[/url] yet in 2002:
[url]http://tech.groups.yahoo.com/group/primenumbers/message/9577[/url]

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

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

[QUOTE=XYYXF;158548]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[sup]2[/sup]-2
x[sup]4[/sup]-4x[sup]2[/sup]+2
x[sup]8[/sup]-8x[sup]6[/sup]+20x[sup]4[/sup]-16x[sup]2[/sup]+2
and so on.[/QUOTE]

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.

Rather consider:

S(0)=2
S(1)=x
S(2)=x[sup]2[/sup]-2
S(3)=x[sup]3[/sup]-3x
and so on.

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

This is related to the LLT.

T.

[QUOTE=XYYXF;158548]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[sup]2[/sup]-2
x[sup]4[/sup]-4x[sup]2[/sup]+2
x[sup]8[/sup]-8x[sup]6[/sup]+20x[sup]4[/sup]-16x[sup]2[/sup]+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:[/QUOTE]
Your observation is a consequence of the following facts:
Polynomials [tex]P_n(x)[/tex] are elements of [url=http://en.wikipedia.org/wiki/Lucas_sequence]Lucas sequence[/url] [tex]V(x,-1)[/tex], namely:
[tex]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}[/tex]
which can be also expressed as [url=http://en.wikipedia.org/wiki/Chebyshev_polynomial]Chebyshev polynomial[/url]:
[tex]P_n(x) = 2 T_{2^n}\left(\frac{x}2\right)[/tex]

An explicit formula for the coefficients of Chebyshev polynomials [tex]T_n(x)[/tex] is given in [url]http://www.research.att.com/~njas/sequences/A053120[/url]
The "main" term of this formula is the binomial coefficient [tex]{(n+m)/2-1\choose m-1}[/tex]. Applying [url=http://en.wikipedia.org/wiki/Lucas_theorem]Lucas theorem[/url] 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 [tex]\beta_{2i}(k)[/tex]. This way you can derive and prove your formula for [tex]P_n(x)[/tex].

[b]maxal[/b], thanks you a lot, all is clear now.
[QUOTE=XYYXF;158548]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:

[url]http://www.primefan.ru/stuff/primes/polynomials.pdf[/url]

E.g., the polynomial of degree 256 has the following coefficients:
[url]http://www.primefan.ru/stuff/primes/256.txt[/url][/QUOTE]These url's doesn't work anymore; if someone is still interested, use the following links please:
[url]http://www.primefan.ru/stuff/math/polynomials.pdf[/url]
[url]http://www.primefan.ru/stuff/math/256.txt[/url]

[QUOTE=maxal;165130]Your observation is a consequence of the following facts:
Polynomials [tex]P_n(x)[/tex] are elements of [url=http://en.wikipedia.org/wiki/Lucas_sequence]Lucas sequence[/url] [tex]V(x,-1)[/tex], namely:
[tex]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}[/tex]
which can be also expressed as [url=http://en.wikipedia.org/wiki/Chebyshev_polynomial]Chebyshev polynomial[/url]:
[tex]P_n(x) = 2 T_{2^n}\left(\frac{x}2\right)[/tex]

An explicit formula for the coefficients of Chebyshev polynomials [tex]T_n(x)[/tex] is given in [url]http://www.research.att.com/~njas/sequences/A053120[/url]
The "main" term of this formula is the binomial coefficient [tex]{(n+m)/2-1\choose m-1}[/tex]. Applying [url=http://en.wikipedia.org/wiki/Lucas_theorem]Lucas theorem[/url] 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 [tex]\beta_{2i}(k)[/tex]. This way you can derive and prove your formula for [tex]P_n(x)[/tex].[/QUOTE]

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.