Approximating linear forms

[2003.02.23]|xlog 2+ylog 3+zlog 5-log 7|<=exp(-X), X=max{|x|,|y|,|z|}<=10^30の整数解

格子の簡約基底からc1を計算/不等式の解を確認するプログラム(pari/gp)

■LLLアルゴリズムの応用として、次のような近似線型形式の問題を解く。
α_i ∈ C^*(i=0,1,...,n)と正実数定数c₂,c₃が与えられたとする。
ある正整数qと与えられた整数x₁,...,x_n,|x_i|<=X_i,X_iは与えられた大きな定数に対する,以下の不等式のHの上界を小さくする。

    |α₀+Σ_i=1ⁿ x_iα_i|<= c₂exp(-c₃H^q)

ここでは、α_i(i=0,...,n)が全て実数の場合を考える。
CをX₀ⁿ程度の定数とする。 n次正方行列Aを以下のように定義し、Aの列で生成される格子(lattice)Lを考察する。

     A = (1     0     0     ...     0)
            (0     1     0     ...      0)
            (              .........          )
            (0     0     0     ..1     0)
            ([Cα_i] ... [Cα_n-1] [Cα_n])

次のLemmaが役に立つ。
     S = Σ_i=1^n-1X_i²,
     T = (1+Σ_i=1ⁿX_i)/2
とする。
c₄²>= T²+Sならば、
     H <= ((log(Cc₂)-log(sqrt(c₄²-S)-T))/c₃)^1/q,
または、
     x₁ = ... = x_n-1 = 0, x_n = -[Cα₀]/[Cα_n]
の少なくとも一方が成立する。

ここで、もしHの上界が存在すれば、
     O((log(Cc₂))^1/q) = O((log(X₀ⁿc₂))^1/q) = O((log(X₀))^1/q)
の形である。

■近似線型形式の不等式
     |xlog 2+ylog 3+zlog 5-log 7|<=exp(-X), X=max{|x|,|y|,|z|}<=10³⁰ -------- (*)
の整数解を全て求める。

■最初に、X = 10³⁰, C = 10¹²⁰とする。pari/gpで、３次正方行列AにLLLアルゴリズムを適用する。

gp> read("c1.gp")
time = 20 ms.
gp> default(realprecision,200)
   realprecision = 202 significant digits (200 digits displayed)
time = 0 ms.
gp> X=10^30;C=10^120;
time = 1 ms.
gp> a1=floor(log(2)*C);a2=floor(log(3)*C);a3=floor(log(5)*C);A=[1,0,0;0,1,0;a1,a2,a3]
time = 39 ms.
%2 = 
[1 0 0]

[0 1 0]

[693147180559945309417232121458176568075500134360255254120680009493393621969694715605863326996418687542001481020570685733 1098612288668109691395245236922525704647490557822749451734694333637494293218608966873615754813732088787970029065957865742 1609437912434100374600759333226187639525601354268517721912647891474178987707657764630133878093179610799966303021715562899]

gp> B=qflll(A,1)
time = 78 ms.
%3 = 
[4060535220813473179470427942242968714387 11674393050961254733776823598235062731635 -4639379471213979060531690295981996470437]

[2058207310687925084067508172296662873603 2064455038139311695735771215736105201410 12112040966086232785177656872805381432903]

[-3153722392647650206893800952749411328727 -6437097214055626290244204777120064567462 -6269682209059685444990994252341657929536]

gp> c4=nr(B)/sqrt(c1)
time = 0 ms.
%5 = 6070477214613532680667314465111620081789.8757582792910108505653234799794541405150644733947131255005636088543617573756875121452996673778773855250138578269067920094725474880475586236111562931613414903082
gp> H=hmax(C,c2,c3,X,B)
time = 24 ms.
%6 = 184.70595531223119092907833117333845291422902850091516156627619890561746949931507697221275790577797423624768184436430927481727227056484707429417256960278651070214414167544527319739227824609528942426785

これにより、Xの簡約された上界(reduced bound) H=184が得られた。

■次に、X=184,C=10^9とする。定義し直した正方行列AにLLLアルゴリズムを適用する。

gp> X=184;C=10^9;
time = 0 ms.
gp> a1=floor(log(2)*C);a2=floor(log(3)*C);a3=floor(log(5)*C);A=[1,0,0;0,1,0;a1,a2,a3]
time = 4 ms.
%11 = 
[1 0 0]

[0 1 0]

[693147180 1098612288 1609437912]

gp> c1=cc1(B)
time = 9 ms.
%13 = 0.11389872709694825057224298278505659965652058718259187886661324191724288859300500841260775895552053780363392131906501733414782473248378523842151380596549897457374714068041333057679532087733634576209445
gp> H=hmax(C,c2,c3,X,B)
time = 13 ms.
%14 = 13.359406384198615292185499755883159127342212669598282253395077131170529386701566425564321598262031551377178637485582017241259125071674767474411774153642110948126507291318578691794350314663335107912137

これにより、Xの簡約された上界H=13が得られた。

■次に、X=13,C=10^6とする。定義し直した正方行列AにLLLアルゴリズムを適用する。

gp> X=13;C=10^6;
time = 0 ms.
gp> a1=floor(log(2)*C);a2=floor(log(3)*C);a3=floor(log(5)*C);A=[1,0,0;0,1,0;a1,a2,a3]
time = 3 ms.
%17 = 
[1 0 0]

[0 1 0]

[693147 1098612 1609437]

gp> B=qflll(A,1)
time = 1 ms.
%18 = 
[-90 -19 -17]

[-15 -114 62]

[49 86 -35]

gp> c1=cc1(B)
time = 7 ms.
%19 = 0.45528257533167157712363828687324482226304695822460228396001810498202518434495908403117328519673226692875807352155363887602955522232789842456763970319535140379674124978944579054160743721257060064712380
gp> H=hmax(C,c2,c3,X,B)
time = 10 ms.
%20 = 8.9221233587894292096664485236977020338589256977386035418074996266433465406271449725583460697151192327907019622558711363446873312367350688777306108236441370782935766889607400734683302298433569979021215

これにより、Xの簡約された上界H=8が得られた。

■最後に、|x|,|y|,|z|<= 8を満たす全ての整数の組(x,y,z)に対して、不等式(*)を満たすかどうか確認する。

gp> check(8)
[-5, 2, 2]
[-2, 0, 2]
[-2, 3, 0]
[-1, -2, 3]
[-1, 1, 1]
[0, 0, 1]
[1, 0, 1]
[1, 1, 0]
[1, 7, -4]
[2, -1, 1]
[2, 2, -1]
time = 21,996 ms.

これにより、不等式(*)の整数解[x,y,z]は、上記の11個に限ることが証明できた。

[参考文献]

[1]Nigel P. Smart, "The Algorithmic Resolution of Diophantine Equations", LMSST 41, Cambridge University Press, 1998, ISBN0-521-64633-2, p82-93.
[2]Henri Cohen, "A Course in Computational Algebraic Number Theory", GTM 138, Springer-Verlag New York Inc., 1996, ISBN-387-55640-0, p79-105.

Last Update: 2005.06.12

H.Nakao