Diophantine Quadruples

[2005.08.28]Diophantusの4つ組

Diophantusの4つ組を探すプログラム(pari/gp)

■Diophantusの3つ組,4つ組,m-組
互いに異なる3つの正整数の組{a,b,c}で、ab+1,bc+1,ca+1がいずれも平方数であるようなものをDiophantusの3つ組(Diophantine triple)と呼ぶ。

同様に、互いに異なる4つの正整数の組{a₁,a₂,a₃,a₄}で、任意のi,j(1<=i<j<=4)に対して,a_ia_j+1がいずれも平方数であるようなものをDiophantusの4つ組(Diophantine quadruple)と呼ぶ。

同様に、Diophantusの5つ組(quintuple)、6つ組(sextuple)、m-組(m-tuple)も定義できる。

例えば、{1,3,8}は、Diophantusの3つ組である。
    1*3+1=4=2²,
    3*8+1=25=5²,
    8*1+1=9=3²

同様に、{1,3,8,120}は、(Fermatが見つけた)Diophantusの4つ組である。
    1*3+1=4=2²,
    1*8+1=9=3²,
    3*8+1=25=5²,
    1*120+1=121=11²,
    3*120+1=361=19²,
    8*120+1=961=31²

Diophantusは、正有理数の4つ組{1/16, 33/16, 17/4. 105/16}を見つけている。
    (1/16)*(33/16)+1=289/256=(17/16)²,
    (1/16)*(17/4)+1=81/64=(9/8)²,
    (1/16)*(105/16)+1=361/256=(19/16)²,
    (33/16)*(17/4)+1=625/16=(25/4)²,
    (33/16)*(105/16)+1=3721/256=(61/16)²,
    (17/4)*(105/16)+1=1849/64=(43/8)²

■Diophantus(参考文献[8]p513)によると、xを任意の正整数とするとき、{x,x+2,4x+4}は、Diophantusの3つ組であることが示されている。
    x*(x+2)+1=x²+2x+1=(x+1)²,
    (x+2)*(4x+4)+1=4x²+12x+9=(2x+3)²,
    (4x+4)*x+1=4x²+4x+1=(2x+1)²

よって、Diophantusの3つ組{a,b,c}は無限個存在する。

■Theorem(Arkin,Hoggatt,Straus),1979
任意のDiophantusの3つ組{a,b,c}は、4つ組{a,b,c,d₊}に拡張できる。
ただし、
    ab+1=r², ac+1=s², bc+1=t²,
    d₊=a+b+c+2abc+2rst,
    r,s,tは正整数
である。

[証明]
以下のように、ad₊+1が平方数であることが簡単に分かる。
    ad₊+1 = (2bc+1)a²+(b+c+2rst)a+1
       = (bc+t²)a²+2rsta+ab+ac+1 = t²a²+2rsta+(ab+1)(ac+1)
       = t²a²+2rsta+r²s² = (at+rs)².
同様に、
    bd₊+1=(bs+rt)²,
    cd₊+1=(cr+st)²
を得る。
さらに、d₊は正整数であり、max{a,b,c} < d₊であるので、{a,b,c,d₊}はDiophantusの4つ組である。

■Diophantusの正則な4つ組
{a,b,c,d}(a < b < c < d)がDiophantusの4つ組であり、d=d₊を満たすとき、4つ組{a,b,c,d}は正則(regular)であるという。
このとき、{a,b,c,d}をDiophantusの正則な4つ組と呼ぶ。

Diophantusの4つ組{a,b,c,d}は、小さい範囲、例えば、max{a,b,c,d} <= 10⁶では、全て正則であることが知られている。

■参考文献[1]によると、Diophantusの4つ組{a,b,c,d}(0 < a < b < c < d)で、d <= 10⁶を満たすものは、207個存在する。
以下では、これを全て求めてみる。
max{a,b,c,d} <= 10⁶では、4つ組が全て正則であることを利用すると、この範囲の4つ組(207個)を効率良く計算できる。

[pari/gp(gp2c)による計算]

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

                  GP/PARI CALCULATOR Version 2.1.6 (released)
                       i386 running netbsd 32-bit version
                (readline v1.0 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 = 128000000, primelimit = 500000
gp> sd4r(10^6)
1:[1, 3, 8, 120]
2:[1, 3, 120, 1680]
3:[1, 3, 1680, 23408]
4:[1, 3, 23408, 326040]
5:[1, 8, 15, 528]
6:[1, 8, 120, 4095]
7:[1, 8, 528, 17955]
8:[1, 8, 4095, 139128]
9:[1, 8, 17955, 609960]
10:[2, 4, 12, 420]
11:[2, 4, 420, 14280]
12:[2, 4, 14280, 485112]
13:[1, 15, 24, 1520]
14:[1, 15, 528, 32760]
15:[1, 15, 1520, 94248]
16:[3, 5, 16, 1008]
17:[3, 5, 1008, 62496]
18:[1, 24, 35, 3480]
19:[1, 24, 1520, 148995]
20:[1, 24, 3480, 341055]
21:[2, 12, 24, 2380]
22:[2, 12, 420, 41184]
23:[2, 12, 2380, 233244]
24:[3, 8, 21, 2080]
25:[3, 8, 120, 11781]
26:[3, 8, 2080, 203841]
27:[4, 6, 20, 1980]
28:[4, 6, 1980, 194040]
29:[1, 35, 48, 6888]
30:[1, 35, 3480, 494208]
31:[1, 35, 6888, 978120]
32:[5, 7, 24, 3432]
33:[5, 7, 3432, 487344]
34:[1, 48, 63, 12320]
35:[2, 24, 40, 7812]
36:[2, 24, 2380, 461760]
37:[3, 16, 33, 6440]
38:[3, 16, 1008, 195585]
39:[4, 12, 30, 5852]
40:[4, 12, 420, 81510]
41:[6, 8, 28, 5460]
42:[1, 63, 80, 20448]
43:[3, 21, 40, 10208]
44:[3, 21, 2080, 528360]
45:[7, 9, 32, 8160]
46:[1, 80, 99, 32040]
47:[2, 40, 60, 19404]
48:[4, 20, 42, 13572]
49:[4, 20, 1980, 637602]
50:[5, 16, 39, 12600]
51:[5, 16, 1008, 324615]
52:[8, 10, 36, 11628]
53:[1, 99, 120, 47960]
54:[3, 33, 56, 22360]
55:[9, 11, 40, 15960]
56:[1, 120, 143, 69168]
57:[1, 120, 1680, 809999]
58:[2, 60, 84, 40612]
59:[3, 40, 65, 31416]
60:[4, 30, 56, 27060]
61:[5, 24, 51, 24640]
62:[6, 20, 48, 23188]
63:[6, 20, 1980, 954408]
64:[8, 15, 45, 21736]
65:[8, 15, 528, 254541]
66:[10, 12, 44, 21252]
67:[1, 143, 168, 96720]
68:[11, 13, 48, 27600]
69:[1, 168, 195, 131768]
70:[2, 84, 112, 75660]
71:[3, 56, 85, 57408]
72:[4, 42, 72, 48620]
73:[6, 28, 60, 40508]
74:[7, 24, 57, 38480]
75:[8, 21, 55, 37128]
76:[12, 14, 52, 35100]
77:[1, 195, 224, 175560]
78:[3, 65, 96, 75208]
79:[5, 39, 72, 56392]
80:[13, 15, 56, 43848]
81:[1, 224, 255, 229440]
82:[2, 112, 144, 129540]
83:[4, 56, 90, 80940]
84:[7, 32, 69, 62040]
85:[8, 28, 66, 59340]
86:[14, 16, 60, 53940]
87:[1, 255, 288, 294848]
88:[3, 85, 120, 122816]
89:[5, 51, 88, 90048]
90:[15, 17, 64, 65472]
91:[1, 288, 323, 373320]
92:[2, 144, 180, 208012]
93:[3, 96, 133, 153680]
94:[4, 72, 110, 127092]
95:[6, 48, 88, 101660]
96:[8, 36, 78, 90100]
97:[9, 32, 75, 86632]
98:[12, 24, 70, 80852]
99:[16, 18, 68, 78540]
100:[1, 323, 360, 466488]
101:[17, 19, 72, 93240]
102:[1, 360, 399, 576080]
103:[2, 180, 220, 317604]
104:[3, 120, 161, 232408]
105:[4, 90, 132, 190532]
106:[5, 72, 115, 165984]
107:[6, 60, 104, 150100]
108:[8, 45, 91, 131328]
109:[9, 40, 87, 125552]
110:[10, 36, 84, 121220]
111:[12, 30, 80, 115444]
112:[15, 24, 77, 111112]
113:[18, 20, 76, 109668]
114:[1, 399, 440, 703920]
115:[3, 133, 176, 281520]
116:[7, 57, 104, 166320]
117:[19, 21, 80, 127920]
118:[1, 440, 483, 851928]
119:[2, 220, 264, 465612]
120:[4, 110, 156, 275100]
121:[5, 88, 135, 238056]
122:[8, 55, 105, 185136]
123:[10, 44, 96, 169260]
124:[11, 40, 93, 163968]
125:[20, 22, 84, 148092]
126:[3, 161, 208, 402600]
127:[7, 69, 120, 232232]
128:[21, 23, 88, 170280]
129:[2, 264, 312, 660100]
130:[3, 176, 225, 476008]
131:[4, 132, 182, 385020]
132:[6, 88, 140, 296148]
133:[8, 66, 120, 253828]
134:[11, 48, 105, 222088]
135:[12, 44, 102, 215740]
136:[16, 33, 95, 200928]
137:[22, 24, 92, 194580]
138:[5, 115, 168, 386976]
139:[23, 25, 96, 221088]
140:[2, 312, 364, 909900]
141:[3, 208, 261, 652400]
142:[4, 156, 210, 524900]
143:[6, 104, 160, 399900]
144:[8, 78, 136, 339900]
145:[12, 52, 114, 284900]
146:[13, 48, 111, 277400]
147:[16, 39, 105, 262400]
148:[24, 26, 100, 249900]
149:[3, 225, 280, 757016]
150:[5, 135, 192, 519064]
151:[9, 75, 136, 367640]
152:[15, 45, 112, 302744]
153:[25, 27, 104, 281112]
154:[4, 182, 240, 699732]
155:[7, 104, 165, 481032]
156:[8, 91, 153, 446040]
157:[13, 56, 123, 358560]
158:[14, 52, 120, 349812]
159:[26, 28, 108, 314820]
160:[9, 87, 152, 476560]
161:[27, 29, 112, 351120]
162:[4, 210, 272, 914892]
163:[5, 168, 231, 776968]
164:[6, 140, 204, 686140]
165:[7, 120, 185, 622224]
166:[8, 105, 171, 575128]
167:[10, 84, 152, 511212]
168:[12, 70, 140, 470844]
169:[14, 60, 132, 443932]
170:[15, 56, 129, 433840]
171:[20, 42, 120, 403564]
172:[21, 40, 119, 400200]
173:[24, 35, 117, 393472]
174:[28, 30, 116, 390108]
175:[29, 31, 120, 431880]
176:[5, 192, 259, 995472]
177:[6, 160, 228, 876308]
178:[8, 120, 190, 730236]
179:[10, 96, 168, 645668]
180:[12, 80, 154, 591852]
181:[15, 64, 141, 541880]
182:[16, 60, 138, 530348]
183:[20, 48, 130, 499596]
184:[24, 40, 126, 484220]
185:[30, 32, 124, 476532]
186:[11, 93, 168, 688000]
187:[31, 33, 128, 524160]
188:[8, 136, 210, 914628]
189:[16, 68, 150, 653268]
190:[17, 64, 147, 640200]
191:[32, 34, 132, 574860]
192:[11, 105, 184, 850680]
193:[15, 77, 160, 739704]
194:[21, 55, 144, 665720]
195:[33, 35, 136, 628728]
196:[12, 102, 184, 901460]
197:[17, 72, 159, 778960]
198:[18, 68, 156, 764260]
199:[24, 51, 145, 710360]
200:[34, 36, 140, 685860]
201:[35, 37, 144, 746352]
202:[18, 76, 168, 919820]
203:[19, 72, 165, 903392]
204:[24, 57, 155, 848632]
205:[36, 38, 148, 810300]
206:[37, 39, 152, 877800]
207:[38, 40, 156, 948948]
time = 14mn, 57,561 ms.
gp> quit
Good bye!
bash-2.05a$

■Diophantusの5つ組予想,4つ組予想
(Diophantine quintuples Conjecture)
Diophantiusの5つ組は存在しない。

Diophantusの5つ組予想より、少し強いDiophantusの4つ組予想もある。
(Diophantine quadruples Conjecture)
{a,b,c,d}がDiophantusの4つ組で、d > max{a,b,c}を満たすならば、d=d₊である。

また、参考文献[1]によると、Andrej Dujellaによって、

(Theorem 1) Diophantusの5つ組は高々有限個しか存在しない。
(Theorem 2) Diophantusの6つ組は存在しない。

が証明されている。
さらに、Theorem 1はeffectiveであること、つまり、次のCorollaryが証明されていることに注意する。
(Corollary 4)
    {a,b,c,d,e}(a < b < c < d < e)がDiophantusの5つ組であるならば、
    d < 10²¹⁷¹,
    e < 10^10²⁶
    である。

■Gap原理(Gap principle)
Andrej Dujella[1]によって、以下の命題が証明されている。
(Proposition 1)
    {a,b,c,d}がDiophantusの4つ組で、a < b < c < dとする。
    このとき、d=d₊またはd > 2.695c^3.5a^2.5である。

■Gap原理を利用して、Diophantusの4つ組{a,b,c,d}で、max{a,b,c,d}<= 10⁶を満たすものを求めると、このようになる。

[2005.09.02追記]
アルゴリズムを少し改良して、Diophantusの4つ組で、max{a,b,c,d}<=10⁷を満たすものを求めると、このようになった。これらの4つ組は全て正則であることが確認できた。

[2005.09.06追記]
Diophantusの4つ組で、max{a,b,c,d}<=10⁸を満たすものを求めると、このようになった。これらの4つ組は全て正則であることが確認できた。

M	max{a,b,c,d}<=M を満たす Diophantusの4つ組 {a,b,c,d}の個数	pari/gp(gp2c)による計算時間[s] (LOOX T9/80W)
10³	3	0.197
10⁴	18	0.384
10⁵	69	8.089
10⁶	207	223.827
10⁷	585	6367.239
10⁸	1548	194316.923

[参考文献]

[1]Andrej Dujella, "There are only finitely many Diophantine quintuples", 2004, p1-28.
[2]Andrej Dujella, "On the size of Diophantine m-tuples", 2000, Feb 11, p1-16.
[3]Andrej Dujella, "A proof of the Hoggatt-Bergum Conjecture", Proceedings of the AMS, Vol.127 No.7, 1999, p1999-2005.
[4]Andrej Dujella, "Diophantine m-tuples and elliptic curves", J.de Th\'eorie des Nombres de Bordeau 13(2001), p111-124.
[5]藤田育嗣, "Diophantine m-tuples and simultaneous Pell equations", thesis, p1-7.
[6]Richard K. Guy, "Unsolved Problems in Number Theory Third Edtion", Springer-Verlag, 2004, ISBN0-387-2060-7, p310, D29:Diophantie m-tuples.
[8]Leonard Eugene Dickson, "History of the Theory of Numbers Volume III: Quadratic and Higher Forms", Dover Publishing, Inc., 2005, ISBN0-486-44234-9, p513-521, Chap.XIX.

Last Update: 2007.01.01

H.Nakao