Memoirs of the Faculty of Education and Human Studies Akita University (Natural Science)
61 , 59 ‑ 63 (2006)
Chebyshev Polynomials over Finite
and Elliptic Curves
Fields
Hideji Ito
We study the number of the rational points of elliptic curves defined over finite fields as polynomials in the trace of the Frobenius endomorphism. We flnd Chebyshev polynomials are closely related to them and get many formulas involving factorization, discriminant, values of inner product etc.
1
Let
Then
cos e:
IntrOductiOn
n be a natural number and cos(ne) can be expressed as
6 a real number.
a polynomial in
cos(ne) = T (cose) (Tn(X) e Z[X]) The polynomial T (X) is called Chebyshev poly‑
nomial of the flrst kind and has broad application around mathematical sciences. (See [4], [5].) Alge‑
braically, some of the features of T (X) are the fol‑
10wing:
(i) T (X) can be defined recursively.
(ii) If m and n are odd and mln (i.e. m divides n) then Tm(X) divides T (X).
Now we know analogous phenomenon occurs re‑
lated to elliptic curves. Let E be an elliptic curve over Fp (the finite field with p elements, p being a ra‑
tional prime) and Np the number of rational points of E defined over Fp ( the algebraic extension of Fp of degree n). Also we put ap = tr (?T ), where ITp is the Frobenius endomorphism of E and the trace is taken with respect to the g‑adic representation of E.
Then, as is well known, we have Np" = I ‑ ap + p and
(i) ap" and hence Np can be computed recursively, (ii) aplap" for odd mln and Np‑ INp* for all mln.
Our starting point is to consider ap , Np and Np /Np as polynomials in ap, which we denote by A (X), F (X) and f (X) respectively. Here and in
the following, we suppress p in the notation of them for simplicity.
Our main results are:
(i) A (X) is essentially Chebyshev polynomial it‑
self .
This leads to many assertions about F (X). The most interesting things are those about f (X):
(ii) f (X) = n(X ‑ ( +p 1)), where Cn runs through all n‑the roots of unity other than 1.
(iii) (f , f )o = I + 22p + 32p2 + . . . + 22p2n‑3 + p2n‑2 where ( , )o is a natural analogue of usual inner product of Chebyshev polynomials of the flrst kind.
(For the precise statement, see later sections.) Throughout this paper p is a fixed rational prime number once and for all.
2 Npn as a pOlynOmial in ap
Notations being the same as in the introduction, we identify 7r with an imaginary quadratic number.
;:: Irn +=nlr , where f is the complex Then we have ap
conjugate of IT' We put apo = 2. Next lemma allows us to compute ap quite easily.
Lemma 2.2 ap +1 apap Pa 1
Proof. Since 7T f = p, we have ap +1 = 7rn+1 +
fn+1 IT f(7rn‑1 + fn‑1) ::: apap ‑ = 1T+ f)(1Tn+ fn) ̲
.[]
pap ‑1
‑ 9 ‑
Akita University
Example2.3。41(X)ニX,、42(X)ニX2−2p,
。43(X)=X3−3pX,。44(X)=X4−4pX2十2p2,
。45(X)ニX5−5pX3十5P2X。
The・rem2。4Aπ(X)ニ2Pπノ瓶(X/2〉,)
P700∫ From Lemma2ユwe have/1π+1(X)=
XAπ(X)一:P・4η_1(X),・41(X)=X。Since鳳+1(オ)ニ 2オ耽(ε)一簸_1(オ)an(i T1(哲)ニカ,we have A1(X)ニ 2p1/2T1(x/2Vp)and recursively we get our assertion,
(A general treatment is given in a recent paper[1】。
But their viewpoint is似uite diEerent from ours.They focus on recurrence relations。) □
Above theorem allows us toput1㌦(X)=1十pπ十
Lπ/21
Σe飾)X物一2κ』The・rem2。4als・enablesust・get
あコ
many results about1㌦.
Theorem2.5(Ooe伽伽げormぬo∫鑑)
ε鋤も一一(一1)η/22Pη/2玉f冗一even
ε無)一(一・)島+1Pκη些κ(∵)・カんe磁
P700∫This can be deduced from the known results about coeHicients of鑑(オ)(see[4]P24),□
The Chebyshev polynomia1鑑(X)satisfy the rec−
curence£ormula鑑+1(X)=2X鑑(X)一鑑_1(X).
Using this and theorem2.4,we have the recu皿ence formula for1㌦(X).
Theorem2.6既んα ε
鑑+1(X)ニX鑑(X)一P1㌦_1(X)十(1−X十P)(1十Pη)
P償oo∫。 From the definition and theorem2.4,we have鑑(x)ニ1−2プ/2鑑(x/2vの)十pη,So it h・ldstha鴫+・(X)ニ1−2P(η+1)/2鑑+・(X/2V7)+
Pη+1=1−2P(π+1)/2(2(x/2〉ワ)簸(x/2V多)一 鑑一・(x/2〉勿))+Pπ+1ニ1−2Pπ/2x馴x/2〉φ)+
2P(物+1)/2鑑一・(x/2》P)+Pη+1…(*)・onthe・ther
hand,XFπ(X)一p鑑_1(X)十(1−X十p)(1十 Pη)= X(1−2Pれ/2鑑(X/2vの)十Pπ)一P(1−
2P(洞)/瓶一・(X/2ゆ)+Pπ一1)+(1−X+P)(1+Pπ).
After cancelling this coincides with(*),口
As is well known,Chebyshev polynomials of the first kind fbrm orthogonal system under the inner pro(iuct
〈五9〉一煤讐婦9∈R回)
Define ana,logous inner product a850110ws:
〈簾鵜篶血(^9∈R[あ])
Combining theorem2.4and the orthogonality of Chebyshev polynomials,we get the following theorem in straightforwar(i way.
Theorem2。7
(i)〈一一
(・i)〈凡,瑞沁一 1(跳瓢
□
When one deal with Chebyshev polynomials
U几(X)of the second kind,that is,U脆(cosθ)=
sin(η十1)θ/sinθ,one use the following inner product:
〈ゐ9〉一五∫(z)9(∬)腰婦9∈R[z])
So we(iefine analogously:
〈^9〉・一
∫(の)9(の)爾血(^9∈R回)
and examine their values when applying Aηor鑑,
which is the contents of the next theorem.
Theorem2.8
(i) 〈Aη,Am〉1=
(ii)〈1㌦,瑞〉1ニ
2P2π ザηニm=1
4Pη+1π げπ≠1α寵πニm
−2Pηπ ザmニη一2
−2Pπ+2πザm=π+2
0 0亡んθrω歪5ε
(1+3P+P2)2μ 信ノηニmニ1
(1+2P+4P2+2P3+P4)2Pπ哲ノη=m=2
(1+4Pη+P2η)2Pπ げπ=㎜,π≧3
(1+Pη一P(η+m)/2+pm+P几+m)2μ
ザη=m土2
(1+Pπ)(1+〆)2Pπ ¢ノη≠m,m土2
P700∫。Use theorem2.4and the fbrmula鑑二
1/2(Uπ一Uη_2)(η≧2)and the orthogonality of Un
(〈uれ,uπ〉ニπ/2)。口
3 Np"/Np as a polynomial in ap
Since NplNp* for all n, we think it more preferable to investigate f = Np /Np (as polynomials in ap).
As F (X) = (1 +p ‑ X)f (X), the theorem 2.6
gives the following recurrence formula of f (X):
f +1(X) = Xf (X) ‑ pf ̲1(X) + I + p".
Example 3.1 fl(X) = 1, f2(X) = I + p + X, f3(X) = I ‑p+p2 + (1 +p)X+X2, f4(X) = I ‑ p‑
p2 + p3 + (1 ‑ 2p + p2)X + (1 + p)X2 + X3, f5(X) = 1 ‑ p + p2 ‑ p3 + p4 + (1 ‑ 2p ‑ 2p2 + p3)X + (1 ‑ 3p + p2)X2 + (1 + p)X3 + X4.
These examples suggest that f (X) X"‑1 + X ‑2 +. . .+X+ I (mod p). So one naturally suspect hat the cyclotomic number field Q(C ) has some rel‑
evance with the f (X). In fact we have the following theorem, which is very much like the known formula 2T (X/2) = H(X ‑ ( + 1)) ([5] p 227)
Theorem 3.2 We have
f (X) H(X ‑ (( + p 1))
where C runs through all n‑th roots of unity other than 1.
Proof. We introduce new variables U and V for which it holds that X = U + V and UV = p. Then we have A (X) = U +V . Substituting U by ( , we get a homomorphism ip : Z[U, V] H. Z[ ]. We have c (X) = +p( 1 and A (c (X)) = ip (A (X)) c (U" + V ) = (( )" + (p 1) I +p Hence we have F ( +p( 1) = F(c (X)) = ‑A (c (X)) + p + I = O. This means that + p ‑1 for all n th roots of unity give the the roots of F (X) = O. Since F (X) = (1 ‑ X + p)f (X), we have our assertion.
[]
We put gd(X) = H (X ‑ ( k + pC k)) where
(k, )=d
(k, n) means the greatest common divisor between k and n and ( = exp(2lri/n) (a primitive root of unity).
Then we have complete factorization of f (X) over Z.
Theorem 3.3 We have
f (X) = n gd(X)
dl ,d and gd(X) is irrieducible over Z.
Proof. Put ek = k + pC‑k. We have only to show that Q(C) = Q(gk) for (k,n) = 1. (If (k,n) = d, then simply take (d as and so on.) Since
(Ck)2 ‑ ek k +p = O and Q(Ck) = Q( ), the degree (Q(O : Q(ek)) 2. The general element ofthe galois group of Q(C)/Q is c : > (". Hence if Q(ek) Q(C) then there is some c* of order 2 that fixes ek. So we have +p( 1 = (" +p(C‑1)". Rewrite this as C" ‑ C = p( ‑1 ̲ ( ‑1)") = p((" 1 ‑ ( ‑1)"). From this we have ((C"‑1 ‑ 1) = p( 1 (1 ‑ ( "‑1)"‑1). Taking norm NQ(O/Q of both sides, we obtain N( "‑1 ‑ 1) = p ( )N( "‑1 ‑ 1). But N(("‑1 ̲ 1) cannot be zero.
Hence we have a contradiction. []
Corollary 3.4 The natural number n is prime if and only if f (X) is irreducible over Z (for all p).
Example 3.5 f4(X) = (1+p+X)(1‑2p+p2+X2),
f6(X) = (1 + p + X)(1 ‑ p + p2 ‑ (1 + p)X + X2)(1 ‑ p + p2 + (1 + p)X + X2), f8(X) = (1 + p + X)(1 ‑ 2p + p2 + X2)(1 + 2p2 + p4 ‑ 4pX2 + X4).
Theorem 3.6 For a rational prime , the discrim‑
inant 51 of the irreducible polynomial fL(X) is given as follows:
6 = (‑1)(t‑1)/2 /‑2(p ‑ 1)2(pl 1) ̲ 1‑3
Proof. From theorem 3.2 we have 5 = II((( + p 1) ‑ (CI + pCl‑1))2
C' C'
where ( and / run through Cl = (It = I ( C C 1, ' 1. Rewrite this as
51 = H(( ‑ l)2 ll(1 ‑ p(11 '))2
c, c' c, c'
The first component n(( ‑ C')2 is the field dis‑
criminant of Q((1)' Its value is (‑1)(t‑1)/2gt‑2 (see [6] p.9, for example). As for the second component, we can rewrite it as follows:
ll (1 1 ̲ )2 ̲ 2 ( .( i 3 ‑p))
‑
I
( p)
C l ("C3
(' C
' 1<i<j<l H ( i+j =p)2 ... (*) 1 i<j<l
because H i+j = 1. (From the right hand side 1 i<j<t
of the first equality on, we consider a fixed primitive
‑th root of unity.) Set n. = #{(i, j) I i + j s mod , I i < j < g}. Then we easily see that no = (g ‑ 1)/2, n. = ( ‑ 3)/2 for s O. This means that
‑ 1 ‑
Akita University
in the product (*), (i+j equals I for ( ‑ 1)/2 times, whereas i+j equals s( O mod g) for ( ‑ 3)/2 times.
L‑1 1 ( I ̲ p) l‑3
That is, (*) = (1 ‑ p) =
((')t=1.C' 1 (p ‑ 1)2(pL ‑ 1) . [] L‑3
Theorem 3.7 (Coefficient formulas off ) Puttmg f (X) = bf )Xk we have explictt for n‑1 mulas of b(n) as follows: k=0
b(" )1 = 1
b(n) k 1 n‑ (2k‑i) (pt +p2k 1 i)
::: ‑ ( 1)
n‑2k i=0
b(n) k 1 n‑(2k+1‑i) (pi +p2k i)
= ‑ ( 1) t z )
n‑(2k+1) i=0
(n ‑ k ‑ 1)
pk (k > 1)
+(‑1)k
k ‑Proof' Owing to recursive relations we have b(n+1) b(kn)1 pb(n 1) k k 1)'
For small values of n, we can easily check the validity of above formulas. The rest of the proof will go as usual by induction. []
Example 3.8 We give a few examples to ease the labor of the interested reader who want to see above formulas more down‑to‑earth way.
b( )2 = I + p (n 2)
b ̲3 = I ‑ (n ‑ 2)p + p2 (n 3)
( )b(" )4 = I ‑ (n ‑ 3)p ‑ (n ‑ 3)p2 + p3 (n 4) b ‑ I ‑ (n ‑ 4)p + 1/2(n ‑ 4)(n ‑ 3)p
‑5 ‑(n ‑ 4)p3 + p4 (n 5) b ‑ I ‑ (n ‑ 5)p + 1/2(n ‑ 5)(n ‑ 4)p
‑6 +1/2(n‑5)(n‑4)p3‑(n‑5)p4+p5 (n 6) b( ) ‑ I ‑ ( 6)p+ ( 5)p2 ( 4)p3 + (" 5)p4
‑7 ‑
( 6)p5 + p6 (n 7)
As a numerical example we write down f7(X) ex‑
plicitly.
f7(X) = 1‑ p+p2 ‑p3 +p4 ‑ p5 +p6 + (1‑2p+3p2 + 3p3 ‑ 2p4 + p5)X + (1 ‑ 3p+ 6p2 ‑ 3p3 + p4)X2 + (1 ‑ 4p ‑ 4p2 + p3)X3 + (1 ‑ 5p+ p2)X4 + (1 + p)X5 + X6
Theorem 3.9
2n‑2
(i) (fn'fn)o =7r ak Pk
̲ (k + 1)2 . . .o k < n ‑ 1 k=0 ak ‑ 2n‑ (k+ 1))2 ...n k 2n ‑ 2
2 pk + 2(n ‑ )pn‑1)
(
2n‑2 (ii) (fn ' fn)1 = 2P 7r
k=0
Example 3.10 To write out several cases explicitly will make the above theorem more impressive.
(fl' fl)o = 17r
(f2, f2)o ::: (1 + 22p + p2)1T
(f3, f3)o = (1 + 22p + 32p2 + 22p3 + p4)7r
< f4 , f4)o = (1 +22p+32p2 +42p3 +32p4 +22p5 +p6)7T (f5, f5>0 = (1 + 22p + 32p2 + 42p3 + 52p4
+42p5 + 32p6 + 22p7 + p8)7r (fl' fl)1 = 2p27T
(f2, f2)1 = (1 + 3p + p2)2p27r
(f3, f3)1 = (1 + p + 5p2 + p3 + p4)2p21T
(f4, f4)1 = (1 + p + p2 + 7p3 + p4 + p5 + p6)2p27r (f5, f5)1 = (1 + p + p2 + p3 + gp4
+p5 + p6 + p7 + p8)2p27r (Proof of theorem 3.9 (i))
Outline of our proof is as follows. We put fn(t) = fn(2 / t).
O Express fn(t) in terms of To, Tl ' " Tn‑1' (Here and in the sequel, we sometimes omit the vari‑
able from functions T; for simplicity.)
Use the orthogonality of the Tk. Then our as‑
sertion of the theorem reduces to an equality of poly‑
nomials in p.
(Proof of (j).) We have
f n(t) = lp ) T + 2 (; :: ) ko = o
( )
2 n‑3
p212T2 + ' ' ' + 2( pk)p(n‑2)/2Tn‑2 +
pk
2p(n‑1)/2Tn‑1 ' ' ' (**)
This can be proved by induction. Indeed, the cases of n ::: 1, 2 are obvious ("' fl(t) = 1, f2(t) = I + p + 21/ t = (1 + p)To + 21/ Tl)' Suppose up to n (**) holds. Then substitute (**) into the recurrence relation fn+1(t) : 2 /i tfn(t) Pf ̲1(t) + pn + 1.
After cancelling, we have the right form of fn+1(t) (in the first term, use the formula tTk ::: TITk =;
(1/2)(Tk+1 + Tk̲1)). []
(Proof of .) By the orthogonality of Tk
((To,To) = 7r, (Ti, Tj) = O if i j, (Tk, Tk) = IT12 for k O), what we have to show is
( lp )2+2 ( k 2p+2 p2+
(
= n= 2
)
n‑3
p p