4-descent,8-descent

4-descent, 8-descent

[2002.06.30]4-descent,8-descent

4-descentによって有理点を探すプログラム(pari/gp)
8-descentによって有理点を探すプログラム(pari/gp)

■自然数nが合同数であることを示すには、楕円曲線
    E_n: y² = x³-n²x
の自明でない(y!=0である)有理点を少なくとも１つ求めることができれば、十分である。

同様に、nが(3/π)-合同数であることを示すには、楕円曲線
    C_n: y² = x³+2nx²-3n²x
の自明でない(y!=0である)有理点を少なくとも１つ求めることができれば、十分である。
よって、E_nまたはC_nのMordell-Weil rankが１以上であることが分かれば良く、rankを正確に求めることは必須でない。

Cremonaのmwrankでは、高さ(Canonical Height)の大きい有理点を求めるのに、時間がかかるので、rankの確定をしない別の方法(4-descent,8-descent)で、有理点を求めてみる。

■Allan J. MacLeodの論文[1]に記述されている4-descentのアルゴリズムを紹介する。
位数２の点を少なくとも１つ持つ楕円曲線
    E: y² = x³+ax²+bx ---------- (1)
を考える。
一般性を失うことなく、x=du²/v², y=duw/v³, だだし、dはsquarefree(２乗因子を含まない), (d,v)=1 と置くことができる。
(1)に代入すると、
    d²w² = d³u⁴+d²au²b²+dbv⁴ ---------- (2)
となる。よって、d|b, b=deである。
dはbのsquarefree因子であり、有限個しかない。dは負の値も取り得ることに注意する。
最初に少し単純な２次方程式
    h² = df²+afg+eg² ---------- (3)
を考える。
２次方程式(3)の１つの解(h₀,f₀,g₀)でg₀!=0なるものを見つけることができたとする。
このとき、(3)の解を次のようにパラメータ表示できる。x=f/g, y=h/gとすると、(3)は、
    y² = dx²+ax+e
となる。点(x₀,y₀)=(f₀/g₀,h₀/g₀)を通る傾きmの直線が曲線(3)と再び出合う点のx座標は、
    x = {a+dx₀+m(mx₀-2y₀)}/(m²-d) ----------- (4)
である。ここで、m=p/qが有理数であるとすると、
    x = {ag₀q²+df₀q²+p(f₀p-2h₀q)}/{g₀(p²-dq²)} ----------- (5)
となる。
元の問題(2)を解くためは、f/g=v²/u²(★最初のxの表示と比較すると、(u,v)が入れ換わっていることに注意する)でパラメータ表示すると、以下の２つの２次方程式を解けばよい。
    ku² = g₀(p²-dq²) ----------- (6)
    kv² = f₀p²-2h₀pq+(ag₀+df₀)q² ----------- (7)
ここで、kはsquarefreeである。
kは(6),(7)の右辺の２次方程式の終結式g₀(a²-4b)を割り切る。k₀を終結式のsquarefree因子(負の値も可能)とする。
k=k₀に対して、(6)の１つの解(u₀,p₀,q₀)を見つけたとする。
曲線(6)と(p₀,q₀)を通る傾きr/sの直線との交点を考えることにより、(p,q)を次のようにパラメータ表示できる。
    p = 2u₀k₀rs-p₀(g₀s²+k₀r²) ----------- (8)
    q = q₀(g₀s²-k₀r²) ----------- (9)
k₀*(7)に、(8),(9)を代入すると、４次方程式
    z² = z₁r⁴+z₂r³s+z₃r²s²+z₄r³+z₅s⁴ ----------- (10)
を得る。ただし、
    z₁ = k₀³(ag₀q₀²+df₀q₀²+f₀p₀²-2h₀p₀q₀) ---------- (11)
    z₂ = 4u₀k₀³(h₀q₀-f₀p₀) ---------- (12)
    z₃ = 2k₀²(f₀(2u₀²k₀-dg₀q₀²+g₀p₀²)-ag₀²q₀²) ---------- (13)
    z₄ = -4u₀g₀k₀²(f₀p₀+h₀q₀) ---------- (14)
    z₅ = g₀²k₀(ag₀q₀²+df₀q₀²+f₀p₀²+2h₀p₀q₀) ---------- (15)
である。
４次方程式(10)が解(r,s)を持てば、(8),(9)から(p,q)を得て、(6),(7)より、(u,v)を得る。★より(u,v)の値を入れ換えた後、x=du²/v²を得て、(2)より、w=sqrt(du⁴+au²v²+ev⁴), y=duw/v³を得る。

■同様に[1]に記述されている8-descentのアルゴリズムを紹介する。
4-descentでは、４次方程式(10)の解(r,s)の高さが大きいことが問題である。
そこで、(10)の右辺が(r,s)の２次式の積に分解できたと仮定する。つまり、
    z₁r⁴+z₂r³s+z₃r²s²+z₄r³+z₅s⁴ = (u₁r²+u₂rs+u₃s²)(v₁r²+v₂rs+v₃s²)----------- (17)
とする。ここで、u₁,u₂,u₃,v₁,v₂,v₃は有理整数であり、以下を満たす。
    z₁ = u₁v₁
    z₅ = u₃v₃
    z₂ = u₁v₂+v₁u₂
    z₄ = u₃v₂+v₃u₂
    z₃ = u₁v₃+u₂v₂+u₃v₁

次の２つの２次方程式を考察する。
    u₁r²+u₂rs+u₃s² = k₁m² ----------- (18)
    v₁r²+v₂rs+v₃s² = k₁t² ----------- (19)
ここで、k₁はsquarefreeである。k₁は、(18),(19)の左辺の２次方程式の終結式
    u₁²u₃²-u₁u₂v₂v₃-2u₁u₃v₁v₃+u₁u₃v₂²+u₂²v₁v₃-u₂u₃1₁v₂+u₃²v₁² ---------- (20)
を割り切る。
２次方程式(19)の１つの解(k₁,t₁,r₁,s₁)を見つけることができたら、(r,s)を以下のように、パラメータ表示できる。
    r = i²k₁r₁-2ijk₁t₁+j²(r₁v₁+s₁v₂) ---------- (21)
    s = s₁(i²k₁-j²v₁) ---------- (22)
k₁*(18)を(21),(22)で置き換えると、以下の４次式が平方数となることが必要である。
    c₁i⁴+c₂i³j+c₃i²j²+c₄ij³+c₅j⁴ ------------ (23)
ただし、
    c₁ = k₁³(r₁²u₁+r₁s₁u₂+s₁²u₃) ---------- (24)
    c₂ = -2k₁³t₁(2r₁u₁+s¹u₂) ---------- (25)
    c₃ = k₁²(4k₁t₁²u₁+2r₁²u₁v₁+2r₁s₁u₁v₂+s₁²(u₂v₂-2u₃v₁)) ---------- (26)
    c₄ = -2k₁²t₁(2r₁u₁v₁+s₁(2u₁v₂-u₂v₁)) ---------- (27)
    c₅ = k₁(r₁²u₁v₁²+r₁s₁v₁(2u₁v₂-u₂v₁)+s₁²(u₁v₂²-v₁(u₂v₂-u₃v₁))) ---------- (28)
である。
４次式(23)が平方数になる(i,j)を見つけたら、(21),(22)より、(r,s)が求まり、4-descentと同様に(p,q),(u,v),(x,y)が順に求まる。

■Allan J. MaxLeodの論文[1]では、UBASICのプログラムをコンパイルできる高級言語に変換して、200MHzまたは300MHz PCで実行している。
ここでは、4-descent, 8-descentのアルゴリズムをpari/GPでプログラムしてみる。
今回より、pari-2.1.4および(gpコンパイラである)gp2c-0.0.1pl1を使用してみた。
4-descent,8-descentによって、Loox T9/80W(Crusoe 5800/800MHz)上で、7が合同数であることを確認する。
(1)4-descent

bash-2.05a$ gp2c-run -g 4-descent.gp
Reading GPRC: ./gp2c_gprc ...Done.

                  GP/PARI CALCULATOR Version 2.1.4 (released)
                       i386 running netbsd 32-bit version
               (readline v4.2a enabled, extended help available)

                       Copyright (C) 2002 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and 
comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

   realprecision = 28 significant digits
   seriesprecision = 16 significant terms
   format = g0.28

parisize = 4000000, primelimit = 500000
gp> congr(7,9,9,9)
[x,y]=[112/9, 980/27]
time = 113 ms.
%1 = 1
gp> \q
Good bye!

(2)8-descent

bash-2.05a$ gp2c-run -g 8-descent.gp
Reading GPRC: ./gp2c_gprc ...Done.

                  GP/PARI CALCULATOR Version 2.1.4 (released)
                       i386 running netbsd 32-bit version
               (readline v4.2a enabled, extended help available)

                       Copyright (C) 2002 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and 
comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

   realprecision = 28 significant digits
   seriesprecision = 16 significant terms
   format = g0.28

parisize = 4000000, primelimit = 500000
gp> congr(7,9,9,9,9)
[x,y]=[-49/25, -1176/125]
time = 260 ms.
%1 = 1
gp> \q
Good bye!

[参考文献]

[1]Allan J. MacLeod, "A simple practical higher descent for large height rational points on certain elliptic curves", Dept. of Mathmatics and Statics Univercity of Paisley, June 15, 2002.
[2]Joseph H. Silverman, "The Arithmetic of Elliptic Curves", GTM 106, Springer-Verlag New York Inc., 1986, ISBN0-387-96203-4.
[3]Joseph H. Silverman, "Advanced Topics in the Arithmetic of Elliptic Curves", GTM 151, Springer-Verlag New York Inc., 1994, ISBN0-387-94328-5.

Last Update: 2005.06.12

H.Nakao