Rational Points and Integral Points on Elliptic Curve: y^2=x^3-9x+9

[2003.03.09]y^2=x^3-9x+9の有理点と整点

c1-c8,楕円対数の計算プログラム(pari/gp)

■楕円曲線
     E: Y²=X³-9X+9 ------ (1)
の有理点を求める。

■楕円曲線Eの判別式 Δ,j-不変量 j,conductor Nは、それぞれ、
     Δ = 11664
     j = 6912
     N = 324
である。
[pari/gpによる計算]

gp> e=ellinit([0,0,0,-9,9])
time = 191 ms.
%1 = [0, 0, 0, -9, 9, 0, -18, 36, -81, 432, -7776, 11664, 6912, [2.226681596905677465811651808, 1.184792530904095372701352047, -3.411474127809772838513003855]~, 1.931560707177880725808347023, 1.391493277287892038911814221*I, -0.6231879858987860622638245576, -2.075396611433224112933811734*I, 2.687753738711467623341581106]
gp> e.j
time = 0 ms.
%2 = 6912
gp> e.disc
time = 0 ms.
%3 = 11664
gp> ellglobalred(e)
time = 9 ms.
%4 = [324, [1, 0, 0, 0], 9]

■楕円曲線Eのねじれ点群は、Z/3Zである。
Eのねじれ点群は、位数3の点T(3,3)で生成される。よって、
E(Q)_tors = {(3,3), (3,-3), O}
である。
[pari/gpによる計算]

gp> elltors(e)
time = 22 ms.
%5 = [3, [3], [[3, 3]]]
gp> for(i=1,3,print(ellpow(e,[3,3],i)))
[3, 3]
[3, -3]
[0]
time = 18 ms.

■楕円曲線Eの有理点群のrankは、1であることが分かる。
Cremonaのmwrank3によって、このように有理点群の生成元P₁(1,1)が見つかる。よって、
     E(Q) = Z×Z/3Z
である。

■楕円曲線Eの全ての整点を、[4]の方法によって求める。
u=1,v=0とする。
以下の形式
     C: y² = f(x) ----- (3)
     f(x) = x^3-9x+9 -------- (4)
を得る。
3次方程式 f(x) = 0の最大の実数根をγとする。 ------ (*)

任意のP ∈ E(Q)に対して、有理整数m₁,m₀(m₀=0,1,2)が存在して、
     P = m₁P₁+m₀T ------ (5)
となる。
f(x)=x³-9x+9=0の根は、３個の実数(いずれも無理数)であり、
     γ ≒ 2.226681596905677465811651808,
     γ' ≒ 1.184792530904095372701352047,
     γ''≒ -3.411474127809772838513003855
である。

(X,Y)がEの整点であるとする。
f(X) > 0 iff (X > γ または γ'' < X < γ')

γ'' < X < γ'なる整点(X,Y)は、以下の6個である。
     (-3,±3),(0,±3),(1,±1) ------ (**)

よって、X > γの範囲で、Eの整点(X,Y)を求める。

gp> poldisc(x^3-9*x+9)
time = 1 ms.
%6 = 729
gp> rr=polroots(x^3-9*x+9)
time = 23 ms.
%7 = [-3.411474127809772838513003855 + 0.E-28*I, 1.184792530904095372701352047 + 0.E-28*I, 2.226681596905677465811651808 + 0.E-28*I]~
gp> factor(x^3-9*x+9)
time = 3 ms.
%8 = 
[x^3 - 9*x + 9 1]

gp> for(x=-3,1,y2=x^3-9*x+9;y=floor(sqrt(y2));if(y^2==y2,print([x,y])))
[-3, 3]
[0, 3]
[1, 1]
time = 9 ms.

■不等式1
P ∈ E(Q)が(5)で表現されるとすると、
h^(P) >= c₁|m₁|² ------- (7)
である。

[pari/gpによる計算]

gp> p0=[0];p1=[1,1];
time = 0 ms.
gp> read("c1.gp")
time = 61 ms.
gp> H=[ellbil(e,p1,p1)/2]
time = 40 ms.
%10 = [0.1938122974521380952592198293]
gp> dd=H[1]-x
time = 0 ms.
%11 = -x + 0.1938122974521380952592198293
gp> ww=polroots(dd)
time = 2 ms.
%12 = [0.1938122974521380952592198293 + 0.E-28*I]~
gp> c1=real(ww[1])
time = 0 ms.
%13 = 0.1938122974521380952592198293

■不等式2
c₂ = 2*max{|γ|,|γ'|,|γ''|}
とする。任意のx >= c₂に対して、
|∫_x^∞(dt/sqrt{f(t)})| <= 4*sqrt(2)|x|^-1/2 --------- (8)
となる。

[pari/gpによる計算]

gp> c2=2*max3(real(rr[1]),real(rr[2]),real(rr[3]))
time = 0 ms.
%14 = 4.453363193811354931623303616

■不等式3
u=1,v=0とする。
X₀を正の有理整数で、X₀ > vとする。
このとき、任意のP ∈ E(Q), X(P) >= X₀に対して、
x(P) > 0,
h^(P)-(1/2)*log x(P) <= c₃ ------ (9)
となる。

[pari/gpによる計算]

gp> c0=log(1)
time = 0 ms.
%15 = 0.E-28
gp> c3=cc3(c0,e)
time = 2 ms.
%16 = 2.933679987341000232672282109

■不等式1,2,3より、
     |φ(P)|=|(1/ω)∫_x(P)^∞(dt/sqrt{f(t)})| <= (4*sqrt(2)/ω)|x(P)|^-1 <= (4*sqrt(2)/ω)exp(c₃-c₁M²) ----------- (10)
を得る。

■主不等式
P ∈ E₀(R) iff x(P) >= γ iff X(P) >= u²γ+v なので、不等式2,3を満たすために、
     X₀ = floor(max{c₂,u²γ+v,v})+1
とする。

     M² < c₃c₁^-1-c₁^-1log(4*sqrt(2))+c₄c₁^-1(log M+c₇)(log log M+c₈)^r+2 ------- (11)
となる。

[pai/gpによる計算]

gp> X0=floor(max(c2,real(rr[3])))+1
time = 0 ms.
%17 = 5
gp> factor(e.j)
time = 0 ms.
%18 = 
[2 8]

[3 3]

gp> he=log(2^8*3^3)
time = 0 ms.
%19 = 8.841014310483891549523592682
gp> A0=AA(e,p0,he)
time = 4 ms.
%20 = 8.841014310483891549523592682
gp> A1=AA(e,p1,he)
time = 42 ms.
%21 = 8.841014310483891549523592682
gp> eb=eeb1(e,p1,A0,A1)
time = 8 ms.
%22 = 1.156879107184524492802293783
gp> c4=cc4(1,eb,A0*A1)
time = 1 ms.
%23 = 37916490592555.26652413733719
gp> c5=cc5(eb)
time = 0 ms.
%24 = 0.1457259545798626207524252008
gp> c6=cc6(c5,he)
time = 0 ms.
%25 = 8.986740265063754170276017882
gp> c7=cc7(c6,1,3)
time = 0 ms.
%26 = 10.18951922039853052833792978
gp> c8=cc8(c6,1,3)
time = 0 ms.
%27 = 9.420551073600526637706117324
gp> g(m)=m^2-(c3/c1+log(4*sqrt(2))/c1+(c4/c1)*(log(m)+c7)*(log(log(m))+c8)^2)
time = 0 ms.
gp> gdash(m)=2*m-(c4/c1)*((1/m)*(log(log(m))+c8)^2+(log(m)+c7)*2*(log(log(m))+c8)*(1/log(m))*(1/m))
time = 0 ms.
gp> nn(x)=x-g(x)/gdash(x)
time = 0 ms.
gp> x=10^100;for(i=1,320,x=nn(x);print(x))
5.000000000000000000000000000 E99
2.500000000000000000000000000 E99
1.250000000000000000000000000 E99
6.250000000000000000000000000 E98
3.125000000000000000000000000 E98
......
1478658439.445595866654955407
1057748929.335290718430500457
971663810.7682128359355406539
967704067.6054972918315683659
967695635.8190758360558520107
967695635.7808396215112238353
967695635.7808396215104375402
967695635.7808396215104375402
967695635.7808396215104375402
967695635.7808396215104375402
967695635.7808396215104375402
967695635.7808396215104375402
967695635.7808396215104375402
967695635.7808396215104375402
967695635.7808396215104375402
967695635.7808396215104375402
967695635.7808396215104375402
967695635.7808396215104375402
967695635.7808396215104375402
time = 2,194 ms.

主不等式(11)より、
     M < 967695635.7808396215104375402
であることが分かる。
しかし、ここで求めたMの上限は大き過ぎるので、LLL-algorithmによって、上限を下げる。

■不等式(10),(11)を単純に、
     |φ(P)| < K₁exp(-K₂M²), M < K₃ ------- (12)
と書くことができる。
ここで、
     K₁ = (4*sqrt(2)/ω)*exp(c₃),
     K₂ = c₁,
     K₃ = 967695635.7808396215104375402
である。

[pari/gpによる計算]

gp> K3=967695635.7808396215104375402
time = 0 ms.
%28 = 967695635.7808396215104375401
gp> K1=(4*sqrt(2)/2*real(e.omega[1]))*exp(c3)
time = 0 ms.
%29 = 102.6914735781639928322357297
gp> K2=c1
time = 0 ms.
%30 = 0.1938122974521380952592198293
gp> KK0(1,3,K3)
time = 0 ms.
%31 = 33711654366334202844.64015957

K₀=10³⁰, A=[1, 0 ; [K₀*φ(P₁)] K₀] にLLL-algorithmを適用して、reduced basis {b₁,b₂}を求めると、
     b₁ = [ -645251705169619, 128496873025805]^t
となる。このとき、
     ||b₁|| >= 2^(1/2)*3*K₃*sqrt(2) = 6*K₃ ----- (16)
ならば、
     M² <= K₂^-1(log(K₀K₁) - log(2^-3*3^(-2)*||b₁||²-3*K₃²)-3*K₃) ------ (17)
が成立する。

[pari/gpによる計算]

gp> default(realprecision,30)
   realprecision = 38 significant digits (30 digits displayed)
time = 0 ms.
gp> ec=ellinit([0,0,0,-9,9])
time = 16 ms.
%32 = [0, 0, 0, -9, 9, 0, -18, 36, -81, 432, -7776, 11664, 6912, [2.22668159690567746581165180818, 1.18479253090409537270135204757, -3.41147412780977283851300385576]~, 1.93156070717788072580834702325, 1.39149327728789203891181422118*I, -0.623187985898786062263824557610, -2.07539661143322411293381173418*I, 2.68775373871146762334158110591]
gp> K0=10^30
time = 0 ms.
%33 = 1000000000000000000000000000000
gp> a1=floor(K0*phi(ec,p1,K0))
time = 8 ms.
%34 = 199142244795814513314581226974
gp> aaa=[1,0;a1,K0]
time = 0 ms.
%35 = 
[1 0]

[199142244795814513314581226974 1000000000000000000000000000000]

gp> bbb=qflll(aaa,1)
time = 18 ms.
%36 = 
[-645251705169619 -209707090068208]

[128496873025805 41761540665781]

gp> b1n=nr(bbb)
time = 0 ms.
%37 = 657921887006132.951878616321277
gp> b1n-2^(1/2)*3*K3*sqrt(2)
time = 0 ms.
%38 = 657916080832318.266840887258651
gp> M2=(1/K2)*(log(K0*K1)-log(sqrt(3^(-2)*b1n^2/2-3*K3^2)-3*K3))
time = 1 ms.
%39 = 211.7222678466039411745161580
gp> sqrt(M2)
time = 0 ms.
%40 = 14.55067929158649077997784682

よって、
M <= 14
が得られた。
次に、K₃=14, K₀=10⁶, A=[1, 0 ; [K₀*φ(P₁)] K₀] として、再度、LLL-algorithmを適用する。
[pari/gpによる計算]

gp> K3=14
time = 0 ms.
%41 = 14
gp> KK0(1,3,K3)
time = 0 ms.
%42 = 7056.00000000000000000000000000
gp> K0=10^6
time = 0 ms.
%43 = 1000000
gp> a1=floor(K0*phi(ec,p1,K0))
time = 5 ms.
%44 = 199142
gp> aaa=[1,0;a1,K0]
time = 0 ms.
%45 = 
[1 0]

[199142 1000000]

gp> bbb=qflll(aaa,1)
time = 0 ms.
%46 = 
[-467 1165]

[93 -232]

gp> b1n=nr(bbb)
time = 0 ms.
%47 = 476.170137660899520629967418170
gp> b1n-2^(1/2)*3*K3*sqrt(2)
time = 0 ms.
%48 = 392.170137660899520629967418170
gp> M2=(1/K2)*(log(K0*K1)-log(sqrt(3^(-2)*b1n^2/2-3*K3^2)-3*K3))
time = 0 ms.
%49 = 73.44154705234914888285162496
gp> sqrt(M2)
time = 0 ms.
%50 = 8.569804376550794340941222586

よって、
M <= 8
が得られた。

■最後に、|m₁| <= 8, m₀=0,1,2について、P=m₁P₁+m₀Tが整点かどうかを確認する。

[pari/gpによる計算]

gp> check1(8,e,p1)
[7, -17]
[1, -1]
[1, 1]
[7, 17]
There are 4 integral points.
time = 29 ms.
gp> check1t(8,e,p1,[3,3])
[15, 57]
[0, 3]
[3, 3]
[-3, 3]
There are 4 integral points.
time = 23 ms.
gp> check1t(8,e,p1,[3,-3])
[-3, -3]
[3, -3]
[0, -3]
[15, -57]
There are 4 integral points.
time = 10 ms.

(**)で求めたEの6個の整点は、全て上記に含まれる。
よって、楕円曲線Eの整点は、(-3,±3),(0,±3),(1,±1),(3,±3),(7,±17),(15,±57)の12個に限る。

[2004.08.22追記]
■SIMATH-4.6(simcalc)によって、楕円曲線Eの整点を求める。
simcalcによると、楕円曲線EのMordell-Weil群E(Q)のrankは1であり、その生成元は(-3,3)である。
また、楕円曲線Eの整点を(Pと-Pを同一視して)求めると、
(-3,3), (3,3), (0,3), (1,1), (7,17), (15,57)
の6個となる。これらの点のそれぞれを(-1)倍した点も整点であるので、楕円曲線Eは合計6*2=12個の整点を持つ。

[simcalcによる計算]

> E=EC(0,0,0,-9,9)
                  simcalc in free(): warning: junk pointer, too high to make sense.
         E = EC(-9, 9)
> basismwg(E)
  basis :  PT(-3, 3, 1)
simcalc in free(): warning: junk pointer, too high to make sense.
         @ = 1
> faintp(E)
  all nontrivial integral points modulo negation :
  PT(3, 3, 1) = PT(3, 3, 1) + 0*PT(-3, 3, 1)
  PT(-3, 3, 1) = PT(0, 1, 0) + PT(-3, 3, 1)
  PT(0, 3, 1) = PT(3, -3, 1) - PT(-3, 3, 1)
  PT(1, 1, 1) = PT(3, -3, 1) + PT(-3, 3, 1)
  PT(15, 57, 1) = PT(0, 1, 0) - 2*PT(-3, 3, 1)
  PT(7, 17, 1) = PT(3, 3, 1) + 2*PT(-3, 3, 1)
 
simcalc in free(): warning: junk pointer, too high to make sense.
         @ = PT(3, 3, 1)

[参考文献]

[1]Joseph H. Silverman, John Tate(著), 足立恒雄, 木田雅成, 小松啓一, 田谷久雄(訳), "楕円曲線論入門", シュプリンガー・フェアラーク東京, 1995, p127, ISBN4-431-70683-6, {3900円}.
[2]Joseph H. Silverman, "The Arithmetic of Elliptic Curves", GTM 106, Springer-Verlag New York Inc., 1986, p59-60, ISBN0-387-96203-4.
[3]Nigel P. Smart, "The Algorithmic Resolution of Diophantine Equations", LMSST 41, Cambridge University Press, 1998, ISBN0-521-64633-2.
[4]R. J. Stroeker, N. Tzanakis, "Solving elliptic diophantine equations by estimating linear forms in elliptic logarithms", Acta. Math., 3, p209-220, 1994.

Last Update: 2005.08.21

H.Nakao