• 検索結果がありません。

Memoirs of the Faculty of Education and Human Studies  Akita University (Natural Science) 

N/A
N/A
Protected

Academic year: 2021

シェア "Memoirs of the Faculty of Education and Human Studies  Akita University (Natural Science) "

Copied!
5
0
0

読み込み中.... (全文を見る)

全文

(1)

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. 

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

(2)

 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)

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

‑ 

(  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

(4)

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)). [] 

(5)

(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 

ko  ko  k=0 

+2(1 + p)2pn‑2 + 2pn‑1 

= I + 22p + 32p2 + . . . + n2pn‑1 + (n ‑ 1)2p   + 02 2n‑3  + p2n‑2 

+ " ' 4 p " '(* * *). 

Left hand side becomes ((pn ̲ 1)/(p ‑ 1))2 +  n‑1  2((pn‑k ̲ 1)/(p ‑ 1))2pk. Multiply (p ‑ 1)2 to 

the right side of (* * *). We obtain  k=1 

(p ‑ 1)2(1 + 4p + gp2 + . . . + 4p2n‑3 + p2n 2  ‑) 

= 1+2p+2p2 +...+2pn‑1 ̲ (4n 2)pn +2pn+1+ 

+ 2p2n‑1 + p2n. 

A bit of calculation gives you that (pn ̲ 1)2 +  2  (pn‑k ̲ 1)2pk equals to the nght side of the  n‑l  above formula. []  k=1 

(Proof of theorem 3.9 (ii)). Express fn in terms of  the Um' We have 

f n(t)   (1+pn‑k l)U +p(n‑1)/2Un 1  n‑2 

The rest is some calculation as before (in this case  k=0  use the orthogonality of Um)' We omit the details. 

C] 

On what way does our investigation contribute to  the theory of elliptic curves ? This question certainly  demands further study. 

Finally we note that we owe a great deal to Math‑

ematica. Many results were discovered or checked by  the machine computation relying on it. 

References 

[1] Don Aharonov and Alan Beardon and Kathy  Driver, Fibonacci. Ohebyshev, and Orthogonal Poly‑

nomials, American Math. Monthly 112 (2005), 612‑

630. 

[2] H.J.Hsiao, On factorization of Ohebyshev's  Polynomials of the first kind, Bulletin of the Insti‑

tute of Mathematics, Academia Sinica 12 (1) (1984),  89‑94. 

[3] A.W.Knapp, Elliptic Gurves(1992), Princeton  University Press, Princeton, New Jersey. 

[4] J.C.Mason and D.C.Handscomb, Ohebyshev  Polynomials (2002), Chapman & Hall/CRC. 

[5] T.J.Rivlin, Chebyshev Polynomials:From Ap‑

proximation Theory to Algebra and Number Theory  (1990), John Wiley, New York. 

[6] L.C.Washington, Introduction to Oyclotomic  Fields (1982), Springer. 

4 COncludlng RemarkS 

We regard the number of rational points of elliptic  curves over finite fields as a polynomial in the trace  of the Frobenius endomorphism. Discovering those  polynomials are some variants of Chebyshev polyno‑

mials, we derive many results(such as, recurrence re‑

lations, coefficient formula, values of inner product,  factorization, discriminant etc.). 

You might wonder what essential part elliptic  curves do play in our treatise. The answer is they  play very little part as yet. You can formulate our  results quite abstractly without mentioning elliptic  curves. 

But a theory is of small value if it has no relevance  with the existing (important) theories of mathemat‑

ics. This is the reason we wrote this paper as it is. 

DEPARTMENT OF MATHEMATICS  FACULTY OF EDUCATION AND HUMAN  AKITA UNIVERSITY 

AKITA OI0‑8502, JAPAN  E‑mail : itohQmath.akita‑u.ac.jp 

STUDIES 

‑ 3 ‑

Akita University

参照

関連したドキュメント

The bacteria on the hexagonal plates O,1um in dtameter CC, arrows) and unicellular bacteria aiter 90 days

Fukui NationalCollegeof TechnologyGeshi-cho,Sabae,Fukui 916-8507 Kanazawa University, Faculty of Education Kakuma-machi,Kanazawa, Ishikawa 920-1164 Akita Prefectural

[r]

*2 Kanazawa University, Institute of Science and Engineering, Faculty of Geosciences and civil Engineering, Associate Professor. *3 Kanazawa University, Graduate School of

・スポーツ科学課程卒業論文抄録 = Excerpta of Graduational Thesis on Physical Education, Health and Sport Sciences, The Faculty of

Standard domino tableaux have already been considered by many authors [33], [6], [34], [8], [1], but, to the best of our knowledge, the expression of the

Now it makes sense to ask if the curve x(s) has a tangent at the limit point x 0 ; this is exactly the formulation of the gradient conjecture in the Riemannian case.. By the

This research was supported by Natural Science Foundation of the Higher Education Institutions of Jiangsu Province (10KJB110003) and Jiangsu Uni- versity of Science and