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. In 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 of 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.

5 thoughts on “Lucas sequences and Chebyshev polynomials”

mbakermath says:

December 8, 2013 at 12:50 pm

I just corrected a few typos pointed out to me by Keith Conrad. Thanks, Keith!

Holly Krieger says:

December 10, 2013 at 4:31 pm

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

- mbakermath says:
  
  December 11, 2013 at 2:06 am
  
  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.”
  
Holly Krieger says:

December 11, 2013 at 5:00 pm

Criticisms of criticisms – how very dramatic. Thanks for the fun quote!

Pingback: Quadratic Reciprocity via Lucas Polynomials | Matt Baker's Math Blog

Matt Baker's Math Blog

Thoughts on number theory, graphs, dynamical systems, tropical geometry, pedagogy, puzzles, and the p-adics

Lucas sequences and Chebyshev polynomials

5 thoughts on “Lucas sequences and Chebyshev polynomials”

Leave a Reply Cancel reply

Share this:

Like this:

Related

5 thoughts on “Lucas sequences and Chebyshev polynomials”

Leave a Reply Cancel reply