Lucas sequences and Chebyshev polynomials

This is a sequel to last week’s blog post “Two applications of finite fields to computational number theory“.  The main reason I decided to write a follow-up is that I’ve learned a lot about Concluding Observations #1 and #6 from that post during the last week.   LucasBookIn Observation #1, I mentioned without further comment a recursive procedure for computing square roots modulo a prime; it turns out that this procedure is essentially equivalent to Cipolla’s algorithm, but was discovered independently by Lehmer (who it seems did not know about Cipolla’s work).  I learned this from the wonderful book “Édouard Lucas and Primality Testing” by Hugh C. Williams, which I highly recommend to anyone interested in the history of mathematics.  In explaining the connection between the algorithms of Cipolla and Lehmer, I’ll make a digression into the general theory of Lucas sequences, which I had some vague knowledge of before but which I’ve learned a lot about in the last week from reading Williams’ book.  In Observation #6, I asked if there was a conceptual explanation for the fact that the Chebyshev polynomial x^2 - 2 shows up in the Lucas-Lehmer test; Greg Kuperberg sent me just such an explanation and I will expand on his comments below.

Note: In this post I will assume more background in abstract algebra than in the last post.

Lucas and primality testing

On this web page, Williams writes: “[In the book] I show the tremendous influence on primality testing wielded by Édouard Lucas, the first individual to show that primality testing could be performed, at least on certain forms of numbers, without recourse to the laborious and tedious process of trial division.”

One of Lucas’ wonderful discoveries was that the Fibonacci sequence (F_n) defined by F_0 = 0, F_1 = 1 and F_{n+1} = F_n + F_{n-1} for n \geq 1 has a natural “companion sequence” (L_n) (the Lucas sequence) defined by L_0 = 2, L_1 = 1, and L_{n+1} = L_n + L_{n-1} for n \geq 1.   The relationship between the sequences (F_n) and (L_n) is, roughly speaking, like the relationship between sine and cosine.  For example, we have (*) F_{2n} = F_n L_n (similar to the formula \sin(2x) = 2 \sin(x) \cos(x)) and (**) L_n^2 - 5F_n^2 = 4(-1)^n.  Lucas discovered the sequence (L_n) in connection with primality testing.  In fact, he showed that the 39-digit Mersenne number M_{127} = 2^{127} - 1 is prime using roughly the following argument.

First all, by examining the factorizations of various Fibonacci numbers, Lucas noticed that if p is a prime divisor of F_n such that p \nmid F_m for all proper divisors m of n (such a prime is called a primitive prime divisor of F_n), then p \equiv \pm 1 \pmod{n}.  (For example, 17 is a primitive prime divisor of F_9 = 34 and a non-primitive prime divisor of F_{27} = 196418.)  Formulas (*) and (**) readily imply that if p is an odd prime and p \mid L_{2^n}, then p is a primitive prime divisor of F_{2^{n+1}} and hence p \equiv \pm 1 \pmod{2^{n+1}}.  Thus to show that M_{127} is prime, it suffices to show that M_{127} \mid L_{2^{126}} (apply the previous sentence to a prime dividing M_{127}).  This is what Lucas actually did — but how?  Lucas noticed that if we set r_k = L_{2^k} then r_0 = 1, r_1 = 3 and r_{k+1} = r_k^2 - 2 for k \geq 1; thus he needed to show that r_{126} \equiv 0 \pmod{M_{127}}.  This requires performing about 120 squaring operations and 120 divisions with numbers of up to 39 digits.  As Williams writes in Section 3.2: “This is a lot of work by hand, but Lucas’ solution to this problem is very characteristic of him; he made the performance of this tedious arithmetic into something like a game.  He said he used a 127 \times 127 chessboard to effect the computations.”  Lucas would encode the squaring procedure in binary on the chessboard, with pawns in squares representing 1 and empty squares representing 0.  He would take pawns away and move them around according to a specific procedure until the only pawns remaining were in the first row, and then the first row would give the least residue of r_k^2 modulo M_{127}  in binary.  In the end, Lucas proved in this way that M_{127} is prime without ever writing anything down!

General Lucas sequences and fast computation

Lucas considerably generalized the companion relationship between (F_n) and (L_n) as follows.  Let B,C be nonzero integers, and let \alpha,\beta be the two complex roots of the quadratic polynomial t^2 - Bt + C.  Define two sequences (U_n), (V_n) by U_n = \frac{\alpha^n - \beta^n}{\alpha - \beta} and V_n = \alpha^n + \beta^n.  Then (U_n), (V_n) satisfy the recurrence relations U_0 = 0, U_1 = 1 and U_{n+1} = BU_n - CU_{n-1} and V_0 = 2, V_1 = B and V_{n+1} = BV_n - CV_{n-1}.  The sequences U_n and V_n satisfy an enormous number of relations reminiscent of trigonometric identities.  For example, we have V_n^2 - \Delta U_n^2 = 4C^n where \Delta = B^2 - 4C and V_m = 2U_{m+1} - BU_m.  We also have the important duplication formulas U_{2n} = U_n V_n = BU_n^2 - 2C U_n U_{n-1} = 2U_{n+1}U_n - BU_n^2 and V_{2n} = V_n^2 - 2C^n.

By combining the recurrence relations and duplication formulas, it is possible to compute U_m and V_m in O(\log_2 m) additions and multiplications.  This is something that Lehmer knew, but oddly there is no evidence that Lucas was aware of this.  The idea is as follows: we write m = (b_0 b_1 \cdots b_\ell)_2 in binary and begin with the ordered pair (U_0,U_1).  Moving from left to right in the binary representation of m, given (U_k,U_{k+1}) we compute either (U_{2k},U_{2k+1}) (if the bit is a 0) or (U_{2k+1},U_{2k+2}) (if the bit is a 1).  This process will terminate with the ordered pair (U_m, U_{m+1}).   (To compute U_{2k+1} we use the formula U_{2k+1} = U_{k+1}^2 - CU_k^2, which follows from the recurrence relation and duplication formulas.)  One can then compute V_m as V_m = 2U_{m+1} - BU_m.  These computations can of course all be done modulo N if that is all we care about.

As a special case, this gives a fast way to compute the Fibonacci number F_m (note that F_m = U_m with the parameters B = 1 and C = -1).  For example, to compute F_{11} we write 11 in binary as 1011_2 and then use the formulas F_{2k} = F_k^2 + 2F_k F_{k-1} = 2F_{k+1}F_k - F_k^2 and F_{2k+1} = F_{k+1}^2 + F_k^2 to successively compute (F_1,F_2), (F_2,F_3), (F_5,F_6),(F_{11},F_{12}).

Chebyshev polynomials

We can consider (generalized) Lucas sequences made up of polynomials as well as integers.  A particularly interesting choice is to take B=x and C=1.  The corresponding sequence of polynomials U_n is denoted S_n(x) and V_n is denoted C_n(x).  These are referred to as Chebyshev polynomials (of the second and first kind, respectively, and normalized to be monic).  For example, we have S_2(x) = x and C_2(x) = x^2 - 2, and S_3(x) = x^2 - 1 and C_3(x) = x^3 - 3x.  The polynomial C_n(x) satisfies the important identity C_n(x + x^{-1}) = x^n + x^{-n}, from which one deduces that if z lies on the complex unit circle (so that z^{-1} = \bar{z}, then C_n(z + \bar{z}) = z^n + \bar{z}^n.  In other words, we have C_n(2\cos\theta) = 2\cos(n\theta).  Thus the group homomorphism z \mapsto z^n on the unit circle becomes x \mapsto C_n(x) after applying the transformation z = e^{i\theta} \mapsto z + \bar{z} = 2\cos\theta.  Similarly, we have S_n(x+x^{-1}) = \frac{x^n - x^{-n}}{x - x^{-1}}.

The Cipolla-Lehmer algorithm for modular square roots

Let p be an odd prime and let a be a quadratic residue modulo p.  We will explain an efficient (but not provably polynomial-time) algorithm for computing the two square roots of a modulo p using Lucas sequences.  It is a minor modification of an algorithm due to Lehmer (cf. Studies in Number Theory, ed. by W. J. LeVeque, Prentice-Hall 1969) which is more or less equivalent to Cipolla’s algorithm.

As in Cipolla’s algorithm, the first step is to find an integer t such that d:= t^2 - a is a quadratic non-residue modulo p.  Let F be the finite field of order p^2, and let \sqrt{d} be a square root of d in F.  By Cipolla’s theorem, (t + \sqrt{d})^{\frac{p+1}{2}} belongs to the prime subfield {\mathbf F}_p of F and is a square root of a.   (Indeed, by Galois theory we have \alpha^p = \bar{\alpha} for all \alpha = x+y\sqrt{d} \in F, so (t + \sqrt{d})^{p+1} = (t+\sqrt{d})(t+\sqrt{d})^p = (t+\sqrt{d})(t-\sqrt{d}) = t^2 - d = a.)  By the theory of Lucas sequences, if we set V_0 = 2, V_1 = 2t and V_{n+1} = 2t V_n - a V_{n-1} \pmod{p} then V_n = \alpha^n + \beta^n in F, where \alpha = t+\sqrt{d} and \beta = t - \sqrt{d}.   It follows that \frac{1}{2} V_{\frac{p+1}{2}} is a square root of a modulo p.  Indeed, since \alpha^{\frac{p+1}{2}} belongs to {\mathbf F}_p and \beta = \bar{\alpha}, we have \alpha^{\frac{p+1}{2}} = \beta^{\frac{p+1}{2}} and so V_{\frac{p+1}{2}} = \alpha^{\frac{p+1}{2}}+\beta^{\frac{p+1}{2}} = 2\alpha^{\frac{p+1}{2}}.  Thus the quantity \alpha^{\frac{p+1}{2}} in Cipolla’s square root formula is equal to \frac{1}{2} V_{\frac{p+1}{2}}.  We therefore obtain:

Cipolla-Lehmer algorithm: Compute t such that d:= t^2 - a is a quadratic non-residue modulo p.  Define a sequence of integers modulo p by V_0 = 2, V_1 = 2t and V_{n+1} \equiv 2t V_n - a V_{n-1} \pmod{p}.  Compute V_{\frac{p+1}{2}} using the efficient procedure described above.  Then the square roots of a modulo p are \pm \frac{1}{2} V_{\frac{p+1}{2}}.

The Lucas-Lehmer test and the Chebyshev polynomial x^2 - 2

We now present a modified version of Greg Kuperberg’s proof of the Lucas-Lehmer test which highlights the connection with the Chebyshev polynomial f(x) = C_2(x) = x^2 - 2.  We recall the statement of the Lucas-Lehmer test: Let n = 2^m - 1 be a Mersenne number.  Then n is prime if and only if f^{(m-2)}(4) \equiv 0 \pmod{n}, where f^{(k)} denotes the k^{\rm th} iterate of f.

To prove this, first suppose that n = p is prime.  By quadratic reciprocity, 2 is a quadratic residue mod p and 3 is not.  Let F be the finite field with p^2 elements (which we can write concretely as {\mathbf F}_p[\sqrt{3}]), and denote the non-trivial automorphism of F by \alpha \mapsto \bar{\alpha}.  Then the “circle group” C = \{ \alpha \in F \; : \; \alpha \bar\alpha = 1 \} is cyclic of order p+1 = 2^m, since it’s the kernel of the norm homomorphism from the cyclic group F^\times to {\mathbf F}_p^\times, which is known to be surjective.  (We will only need the fact that C is a cyclic group of order dividing p+1, which is slightly easier to see since \alpha^{p+1} = \alpha \bar{\alpha} = 1 for \alpha \in C, and C is a subgroup of a cyclic group and is therefore cyclic.)

We claim that 2+\sqrt{3} is a generator of the cyclic group C.  Since |C| is a power of 2, this is equivalent to saying that 2+\sqrt{3} is not a square in C.  Suppose for the sake of contradiction that we had c^2 = 2+\sqrt{3} for some c \in C.  By the properties of Chebyshev polynomials discussed above, the map \alpha \mapsto \alpha + \bar\alpha transforms the squaring map on C to the map x \mapsto f(x) on {\mathbf F}_p.  Thus b^2 - 2 = f(b) = (2+\sqrt{3})+(2-\sqrt{3})=4, where b = c + \bar{c} \in {\mathbf F}_p.  This implies that 6 is a quadratic residue mod p, a contradiction (since 2 is a residue and 3 is a non-residue).

Thus (2+\sqrt{3})^{2^m} = 1 but (2+\sqrt{3})^{2^{m-1}} \neq 1 in C.  Applying the transformation \alpha \mapsto \alpha + 1/\alpha (note that \bar\alpha = 1/\alpha for \alpha \in C), the first condition implies that f^{(m)}(4)=2 in {\mathbf F}_p.   Since f(a)=2 iff a = \pm 2 and \alpha + 1/\alpha = 2 iff \alpha = 1, it follows from the second condition that f^{(m-1)}(4)=-2.  Since f(a)=-2 iff a=0, we obtain f^{(m-2)}(4)=0 in {\mathbf F}_p as desired.

Now suppose that f^{(m-2)}(4) \equiv 0 \pmod{n} and let q be a prime dividing n.  Let R = ({\mathbf Z}/n{\mathbf Z})[x]/(x^2 - 3), and let \tilde{R} = ({\mathbf Z}/q{\mathbf Z})[x]/(x^2 - 3).  Then there is a natural surjective homomorphism R \to \tilde{R}, and \tilde{R} is isomorphic to either {\mathbf F}_q \times {\mathbf F}_q or {\mathbf F}_{q^2}, depending on whether or not 3 is a square modulo q.  Projecting onto the first factor in the former case, we obtain a surjective homomorphism R \to F where F is either {\mathbf F}_q or {\mathbf F}_{q^2}.

We claim that the image in F^\times of 2+\sqrt{3} \in R^\times has order n+1 = 2^m.  Given the claim, it follows that n+1 divides either q-1 or q^2 - 1, and in any case q > \sqrt{n}.  Since this is true for all prime divisors q of n, we conclude that n is prime.

To prove the claim, we essentially reverse the argument above.  Since f^{(m-2)}(4) = 0 in {\mathbf Z}/n{\mathbf Z}, and hence in R, it follows that f^{(m-1)}(4)=-2 and f^{(m)}(4)=2 in F.  Thus (2+\sqrt{3})^{2^m} + (2-\sqrt{3})^{2^m} =2 and (2+\sqrt{3})^{2^m} = 1.  If (2+\sqrt{3})^{2^{m-1}} = 1 in F then f^{(m-1)}(4)=2, a contradiction.  Thus 2+\sqrt{3} has order 2^m in F^\times as claimed.

Concluding observations:

1. For the record, Lehmer’s proof of correctness for the Cipolla-Lucas algorithm is slightly different from ours and goes as follows.  Let U_n be the complementary Lucas sequence modulo p and note that 0 = U_{p+1} = U_{\frac{p+1}{2}} V_{\frac{p+1}{2}}, so either U_{\frac{p+1}{2}} = 0 or V_{\frac{p+1}{2}} = 0.  The relation V_{\frac{p+1}{2}}^2 - 4d U_{\frac{p+1}{2}}^2 = 4a^{\frac{p+1}{2}} together with Euler’s criterion shows that V_{\frac{p+1}{2}} \neq 0, since d is a quadratic non-residue mod p.  Thus U_{\frac{p+1}{2}} = 0 and V_{\frac{p+1}{2}}^2 = 4a as desired.

2. The ring denoted {\mathbf Z}/n{\mathbf Z}[\sqrt{d}] in this earlier post is isomorphic to the ring R = ({\mathbf Z}/n{\mathbf Z})[x]/(x^2 - d) considered above.

3. Our Chebyshev polynomials C_n(x) are related to the usual Chebyshev polynomials T_n(x) (as defined here, for example) via the conjugation relation T_n(x) = \frac{1}{2} C_n(2x).  The Chebyshev polynomials have many important properties; for example, they form a family of orthogonal polynomials and C_n(x) has the minimal L^\infty-norm (maximal absolute value) on [-2,2] among all monic polynomials of degree n with real coefficients (and is the unique minimizer).

4. As mentioned above, Lucas was interested in primitive prime divisors of the Fibonacci sequence.  Carmichael (who studied Lucas’s work carefully but was also quite critical of it) proved that F_n has a primitive prime divisor for all n>12.  Much later, Schinzel proved that all sufficiently large terms in any Lucas sequence have primitive prime divisors.

4 thoughts on “Lucas sequences and Chebyshev polynomials

  1. This is interesting, Matt, thanks! I was curious whether someone has looked into primitive prime divisors of sequences of evaluated Chebyshev polynomials, and it looks like this was just done by a student of Ih: http://search.proquest.com/docview/1368766797

    I am interested in your short aside, though…what sort of critical things did Carmichael have to say about Lucas?

    – Holly

    Reply
    • Holly, thanks for the reference to Wakefield’s work, I didn’t know about that.
      As for Carmichael’s criticisms, let me quote from Williams’ book:
      “Lucas has been criticized for his many errors and omissions, particularly by Carmichael; however, there can be no doubt that for the most part Lucas understood very well the basic principles behind his results. It is true that his statements and proofs thereof often leave something to be desired; but, on the other hand, these defects are often very easily repaired and do not require the machinery that Carmichael thought necessary. Indeed, it is the author’s opinion that Carmichael’s work, while putting Lucas on a much more solid mathematical footing, tended to muddy the waters rather than clarify them… Certainly, his presentation lacks the charm and infectious enthusiasm that so characterizes Lucas’ work. It should be kept in mind that during the brief time during which Lucas was developing his seminal work on primality testing [1876-1878]… he wrote at least 70 papers on many other subjects. Considering this immense outpouring of activity during such a brief time period, it is easy to forgive him for the few, easily correctable deficiencies that we have mentioned.”

      Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s