全有理距離点問題
全有理距離点問題とは、以下を参照してください。
3辺の長さがすべて有理数の三角形${\triangle ABC}$があります。 点$A$から直線$BC$への垂線の足を$D$とすると、辺$BD,CD$の長さは有理数です。
これは第二余弦定理より簡単に示されます。
1
1
もし、全有理距離点問題が真なら、そのような点は有理点であるべきです。
Figure 1
証明
このように点$\alpha,\beta,\gamma,R$を設定し、辺$OR,αR,βR,γR$の長さが有理数であるとします。
ここでは$p=1$です。
このとき、$\triangle ORα$に着目すると、 定理1より、点$R$から直線$αO$への垂線の足を$υ$としたとき、辺$Oυ$の長さは有理数となります。
よって、点$R$の$x$座標$A$は有理数です。
同様に、単位正方形の対称性から、点$R$の$y$座標$B$も有理数であると証明できます。$\small\blacksquare$
2
全有理距離点問題と命題
「頂点の座標がある自然数$p$で$(0,0),(-p,0),(-p,-p),(0,-p)$と表される正方形の、四つすべての頂点からの距離が整数値となるような、座標平面上の格子点が存在する。」
は同値です。
証明
Figure 1で、定理2より$A,B$は有理数です。
辺$OR,αR,βR,γR$の長さも有理数で、正方形の一辺の長さが$1$ですので、
$A,B,OR,αR,βR,γR$の分母の最小公倍数倍に図を拡大すれば、命題を満たすような点が存在することが分かります。
逆に、命題が成り立つような点があるとき、その図を$p^{-1}$倍だけ縮小すれば、全有理距離点問題が成り立つような点があると分かります。$\small\blacksquare$
3
Figure 2
Figure 1を、$A,B,OR,αR,βR,γR$の分母の最小公倍数倍拡大した図です。ここで、$n,m,k,l$は辺$QO,QU,QT,QS$の長さで、整数です。整数$a,b$は点$Q$の$x$座標$y$座標で、整数$p$は正方形の一辺の長さです。さらに、$p$は$A,B,OR,αR,βR,γR$の分母の最小公倍数でもあります。三平方の定理より、次が成り立ちます。\begin{eqnarray}
a^2+b^2 &= n^2 & \quad\quad\dots(1)\\
(a+p)^2+b^2 &= m^2 &\quad\quad\dots(2)
\\ a^2+(b+p)^2&=k^2 &\quad\quad\dots(3)
\\ (a+p)^2+(b+p)^2&=l^2 &\quad\quad\dots(4)\\
\end{eqnarray}さらに、三平方の定理の逆と補題3から、次の補題が成り立ちます。全有理距離点問題と式(1),(2),(3),(4)が成り立ち、かつ$p \not= 0$であるような整数解が存在することは、同値です。
式(2)から式(1)を式(3)から式(1)を式(4)から式(1)をそれぞれ辺々引いて、\begin{aligned}
2ap+p^2&=m^2-n^2 \\
m^2-n^2-p^2&=2ap &\space\space\space\space\dots(2') \\
\\
2bp+p^2&=k^2-n^2 \\
k^2-n^2-p^2&=2bp &\space\space\space\space\space\dots(3') \\
\\
2(a+b)p+2p^2&=k^2-l^2 \\
k^2-n^2-2p^2&=2(a+b)p &\space\space\space\space\space\dots(4')
\end{aligned}となります。
2
4を法とした平方剰余は、1か0になります。 平方剰余については、以下を参照してください。なので、整数$t$について、\begin{aligned}
t \equiv 0 \space \pmod 2 \iff t^2 \equiv 0 \space \pmod 4 \\
t \equiv 1 \space \pmod 2 \iff t^2 \equiv 1 \space \pmod 4 \\
\end{aligned}が成立します。
1
式(2')について、4の平方剰余を適応させます。平方数は4を法として、1か0になるので、左辺は8通りのパターンがあります。\begin{array}{lll|l}
m^2 & -n^2 & -p^2 & 2ap \space\space\space \pmod 4 \\
\hline 0 & 0 & 0 & 0 \\
0 & 0 & -1 & 3 \\
0 & -1 & 0 & 3 \\
0 & -1 & -1 & 2 \space\space\space\space(a \equiv 1,3)\\
1 & 0 & 0 & 1\\
1 & 0 & -1 & 0 \space\space\space\space(a \equiv 2,0)\\
1 & -1 & 0 & 0 \\
1 & -1 & -1 & 3 \\
\end{array}表にすると、右辺が奇数になる組が出てきますが、右辺は$2ap \equiv 0,2$より、偶数しかありえないため、そのパターンを除きます。\begin{array}{lll|l}
m^2 & -n^2 & -p^2 & 2ap \space\space\space \pmod 4 \\
\hline 0 & 0 & 0 & 0 \\
0 & -1 & -1 & 2 \space\space\space\space(a \equiv1,3)\\
1 & 0 & -1 & 0 \space\space\space\space(a \equiv2,4)\\
1 & -1 & 0 & 0 \\
\end{array}式(3'),式(4')でもします。\begin{array}{lll|l} k^2 & -n^2 & -p^2 & 2bp \space\space\space \pmod 4 \\
\hline 0 & 0 & 0 & 0 \\
0 & 0 & -1 & 3 \\
0 & -1 & 0 & 3 \\
0 & -1 & -1 & 2 \space\space\space\space(b \equiv1,3)\\
1 & 0 & 0 & 1\\
1 & 0 & -1 & 0 \space\space\space\space(b \equiv 2,0)\\
1 & -1 & 0 & 0 \\
1 & -1 & -1 & 3 \\
\end{array}\begin{array}{lll|l} l^2 & -n^2 & -2p^2 & 2(a+b)p \space\space\space \pmod 4 \\
\hline 0 & 0 & 0 & 0 \\
0 & 0 & -2 & 2 \space\space\space\space(a+b \equiv1,3)\\
0 & -1 & 0 & 3 \\
0 & -1 & -2 & 1 \\
1 & 0 & 0 & 1\\
1 & 0 & -2 & 3 \\
1 & -1 & 0 & 0 \\
1 & -1 & -2 & 2 \space\space\space\space(a+b \equiv 1,3)\\
\end{array}同様にありえないものを除きます。\begin{array}{lll|l} k^2 & -n^2 & -p^2 & 2bp \space\space\space \pmod 4 \\
\hline 0 & 0 & 0 & 0 \\
0 & -1 & -1 & 2 \space\space\space\space(b \equiv 1,3)\\
1 & 0 & -1 & 0 \space\space\space\space(b \equiv 2,0)\\
1 & -1 & 0 & 0 \\
\end{array}\begin{array}{lll|l} l^2 & -n^2 & -2p^2 & 2(a+b)p \space\space\space (mod \space 4) \\
\hline 0 & 0 & 0 & 0 \\
0 & 0 & -2 & 2 \space\space\space\space(a+b \equiv 1,3)\\
1 & -1 & 0 & 0 \\
1 & -1 & -2 & 2 \space\space\space\space(a+b \equiv 1,3)\\
\end{array}3つの表では、$n,p$が共通して入っているので、 それをまとめて1つの表にします。\begin{array}{lll:ll|lll}
m^2 & k^2 & l^2 & n^2 & p^2 & a & b & a+b \space\space\space \pmod 4 \\
\hline 0 & 0 & 0 & 0 & 0 & \small{any} & \small{any} & \small{any} \\
1 & 1 & 0 & 0 & 1 & 2,0 & 2,0 & 1,3 \\
1 & 1 & 1 & 1 & 0 & \small{any} & \small{any} & \small{any} \\
0 & 0 & 1 & 1 & 1 & 1,3 & 1,3 & 1,3 \\
\end{array}$a+b$が合致しない組が出てくるので、それを除きます。\begin{array}{lll:ll|lll}
m^2 & k^2 & l^2 & n^2 & p^2 & a & b & a+b \space\space\space \pmod 4 \\
\hline 0 & 0 & 0 & 0 & 0 & \small{any} & \small{any} & \small{any} \\
1 & 1 & 1 & 1 & 0 & \small{any} & \small{any} & \small{any} \\
\end{array}よって、整数$n,m,k,l,p$の組みは、法を2として、次の2組になります。\begin{aligned}
\begin{cases}
n \equiv 0 \space , \space m \equiv 0 \space , \space k \equiv 0 \space , \space l \equiv 0 \space , \space p \equiv 0 \space\space\space\space\space& \dots\boxed{1} \\
n \equiv 1 \space , \space m \equiv 1 \space , \space k \equiv 1 \space , \space l \equiv 1 \space , \space p \equiv 0 & \dots\boxed{2}
\end{cases} \\ \pmod 2 \end{aligned}ここから、$p$が偶数であることが分かります。$ p \equiv 0 \space \pmod 2
\space\space\space\space\space\space\space\space\dots(5) $これを定理5とします。式(1),(2),(3),(4)を満たす自然数解は、以下の2組に限ります。 \begin {aligned} \begin{cases} n \equiv 0 \space , \space m \equiv 0 \space , \space k \equiv 0 \space , \space l \equiv 0 \space , \space p \equiv 0 \space\space\space\space\space& \dots\boxed{1} \\ n \equiv 1 \space , \space m \equiv 1 \space , \space k \equiv 1 \space , \space l \equiv 1 \space , \space p \equiv 0 & \dots\boxed{2} \end{cases} \\
\mod 2
\end{aligned}
2
命題
「頂点の座標がある自然数$p$で$(0,0),(-p,0),(-p,-p),(0,-p)$と表される正方形の、四つすべての頂点からの距離が整数値となるような、座標平面上の格子点が存在する。」
を満たす格子点$(a,b)$と自然数$p$が存在するなら、
任意の自然数$\lambda$を用いて、
格子点$( a \lambda , b \lambda )$と、正方形の一辺の長さ$ p \lambda $も、命題を満たし、逆も成り立ちます。
$\lambda$倍だけ拡大した図により、この補題の証明はすぐにできます。ここで、式(1)に対して、4の平方剰余を適応すると、$$ \begin{array}{ll|l} a^2 & b^2 & n^2 \space\space\space (mod \space 4)\\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 2 \\ \end{array} $$4を法として平方数は0か1に合同なので、一番下の組はあり得ません。$\boxed{1}$の組では、$n^2 \equiv 0 \space (mod \space 4)$より、この表の一番上の組が当てはまります。よって、$a,b$は偶数であることが分かります。定理5より、$p$は偶数ですので、補題6より、\begin{align} a' = \frac{a}{2} \space , \space b' = \frac{b}{2} \space , \space p' = \frac{p}{2} \end{align}とすると、新たに命題を満たす組、点$(a',b')$と正方形の一辺の長さ$p'$が求められます。この組は、定理5より$\boxed{1}$か$\boxed{2}$のどちらかになります。そして、$p$は正方形の一辺の長さより、$0 < p$なので、$p' < p$が成り立ちます。もし、この組が$\boxed{1}$に属するなら、同様にして、新たに命題を満たす組を求めることができて、さらに小さい正方形の一辺の長さの値を求めることができます。この性質から、無限降下法より、$\boxed{1}$の組から、必ず$\boxed{2}$の組を求めることができます。すべての$\boxed{1}$の組が、必ず$\boxed{2}$の組にたどり着くので、$\boxed{2}$の組さえ求めればいいです。どの$\boxed{1}$の組からも、$\boxed{2}$の組を求められます。
補題7は直感的には当たり前です。だから重要なのは、小さい組を求めていく際、$n,m,k,l$が同時に奇数になり、$n,m,k,l$が奇数になった時、$p$は偶数であるということです。つまり、$n,m,k,l$の2の素因数の数は同じで、それよりも$p$の2の素因数の数の法が多いということです。
3
次は、$\boxed{2}$の組です。このとき、$ n = 2n'+1 \space , \space m = 2m'+1 \space , \space k = 2k'+1 \space , \space l = 2l'+1 \space , \space p = 2p' $と置けます。ここで、$n' \space , \space m' \space , \space k' \space , \space l' \space , \space p'$は、整数です。これを式(1)へ代入すると、\begin{aligned} a^2+b^2 &= n^2 \\ a^2+b^2 &= (2n'+1)^2 \\ a^2+b^2 &= 4n'^2+4n'+1 \equiv 1 & (mod \space 4) \end{aligned}\begin{array}{ll|l} a^2 & b^2 & n^2 \space\space\space (mod \space 4)\\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 2 \\ \end{array}表より、$a$または$b$のどちらかが奇数で、どちらかが偶数となる必要があります。どちらが奇数でどちらが偶数であっても一般性を失わないので、ここで$a$が偶数、$b$が奇数とします。よって、$a = 2a' \space , \space b = 2b'+1$として、再度式(1)に代入します。\begin{aligned} a^2+b^2 &= n^2 \\ (2a')^2+(2b'+1)^2 &= (2n'+1)^2 \\ 4a'^2+4b'^2+4b'+1 &= 4n'^2+4n'+1 \\ a'^2+b'^2+b' &= n'^2+n' \\ a'^2+b'(b'+1) &= n'(n'+1) \end{aligned}ここで、$b'(b'+1)$や、$n'(n'+1)$は、連続する2整数の積より、偶数です。よって、$a'$も偶数と分かります。なので、$a'=2a''$とします。ここで、$a''$は整数です。つぎは、これを踏まえて、式(2)に代入します。\begin{aligned} (a+p)^2+b^2 &= m^2 \\ (4a''+2p')^2+(2b'+1)^2 &= (2m'+1)^2 \\ 16a''^2+16a''p'+4p'^2+4b'^2+4b'+1 &= 4m'^2+4m'+1 \\ 4a''^2+4a''p'+p'^2+b'^2+b' &= m'^2+m' \\ (2a''+p')^2+b'(b'+1) &= m'(m'+1) \\ \end{aligned}ここで、$b'(b'+1)$と、$m'(m'+1)$は、偶数なので、$2a''+p'$は偶数となります。よって、$p'$は偶数です。なので、$p'=2p''$とします。ここで、$p''$は整数です。 ここまでで分かったことは次の通りです。\begin{aligned} a \equiv 0 \space (mod \space 4) \\ b \equiv 1 \space (mod \space 2) \\ p \equiv 0 \space (mod \space 4) \end{aligned}中学2年の頃にここまでやってからそのあと進展がありません。wikipediaには、全有理距離点問題の解となるような点は、もとの正方形の辺上に存在しないことは既知であると書いています。単位正方形の四つすべての頂点から有理距離となるような座標平面上の点が存在するかどうかは知られていない。ただし、そのような点がもとの正方形の辺上に存在しないことは既知である。Wikipedia
3
分かったことから、プログラミングをして、具体例を出してみましょう。4つとも有理数となる点はなくとも、3つくらいならたくさんあるはずです。ここでは、GNU MPライブラリをつかって、C言語で書きます。
1
まずは、式(1),(2),(3),(4)を満たす$a,b,p$の範囲の制限を考えます。Figure 2
点$Q$は正方形の内部である可能性があります。しかし、正方形の対称性から、探索範囲は$-\frac{p}{2} \le a , b < N$としましょう。 ここで、$a$が4の倍数、$b$が奇数であることより、\begin{aligned} -\frac{p}{2} &\le a < N \\ -\frac{4p''}{2} &\le 4a'' < N \\ -\frac{p''}{2} &\le a'' < \frac{N}{4} \\ \end{aligned}\begin{aligned} -\frac{p}{2} &\le b < N \\ -\frac{4p''}{2} &\le 2b'+1 < N \\ -p''-\frac{1}{2} &\le b' < \frac{N}{2}-\frac{1}{2} \\ \end{aligned}となります。また、補題6より、$gcd(a,b,p) = 1$となるものだけ計算しましょう。ここで、$gcd(a,b,p)$は、\begin{aligned} \gcd(a,b,p) &= \gcd(4a'',2b'+1,4p'') \\ &= \gcd(\gcd(4a'',4p''),2b'+1) \\ &= \gcd(4\gcd(a'',p''),2b'+1) \\ &= \gcd(\gcd(a'',p''),2b'+1) \end{aligned}残念ながら、C言語にはgcdを計算するライブラリがないので、関数を作りましょう。一番下のコードが一番早そうです。、、、C++ですけどね。#include <stdio.h>
#include <stdlib.h>
long gcdl(long a, long b){
if(a == 0)return labs(b);
if(b == 0)return labs(a);
a = labs(a);
b = labs(b);
int az = __builtin_ctzl(a);
int bz = __builtin_ctzl(b);
int shift = az < bz ? az : bz;
b >>= bz;
while (a != 0){
a >>= az;
long diff = b - a;
az = __builtin_ctzl(labs(diff));
b = a < b ? a : b;
a = labs(diff);
}
return b << shift;
}
これでいいはず。と、ここでGMPにgcdが入っていたことに気づきます。まぁいいや。
2
あとは式(1),(2),(3),(4)を見ながらVScodeでかきかきします。#include
#include <time.h>
#include <gmp.h>
#include <stdlib.h>
long gcdl(long a, long b){
if(a == 0)return labs(b);
if(b == 0)return labs(a);
a = labs(a);
b = labs(b);
int az = __builtin_ctzl(a);
int bz = __builtin_ctzl(b);
int shift = az < bz ? az : bz;
b >>= bz;
while (a != 0){
a >>= az;
long diff = b - a;
az = __builtin_ctzl(labs(diff));
b = a < b ? a : b;
a = labs(diff);
}
return b << shift;
}
int main(int argc, char const *argv[])
{
long cpu_time;
double sec;
mpz_t am;
mpz_t bm;
mpz_t apm;
mpz_t bpm;
mpz_t nm;
mpz_t mm;
mpz_t km;
mpz_t lm;
mpz_inits(am,bm,apm,bpm,nm,mm,km,lm,NULL);
long N;
long N4;
long N2;
long a;
unsigned long au;
long b;
unsigned long bu;
long p;
long ap;
unsigned long apu;
long bp;
unsigned long bpu;
char flag;
long gcd;
N = 10000;
N4 = N / 4;
N2 = N / 2;
for (p = 1; p < N4; p++){
for(a = (long)-p/2; a < N4; a++){
if(a != 0){
gcd = gcdl(a,p);
ap = a + p;
au = 4 * labs(a); //a = 4 * a'
apu = 4 * labs(ap); //a+p = 4(a'+p')
mpz_ui_pow_ui(am,au,2UL); //am = a^2
mpz_ui_pow_ui(apm,apu,2UL); //apm = (a+p)^2
for (b = -p; b <= N2; b++){
if(b != 0){
bu = 1 + 2 * b; // b = 1+2b'
if(gcdl(gcd,bu) == 1){
flag = 0;
bp = bu + 4 * p; //b+p = b + 4*p'
bu = labs(bu);
bpu = labs(bp);
mpz_ui_pow_ui(bm,bu,2UL); //bm = b^2
mpz_ui_pow_ui(bpm,bpu,2UL); //bpm = (b+p)^2
mpz_add(nm,am,bm);
mpz_add(mm,apm,bm);
mpz_add(km,am,bpm);
mpz_add(lm,apm,bpm);
if(mpz_perfect_square_p(nm)){
flag++;
}
if(mpz_perfect_square_p(mm)){
flag++;
}
if(mpz_perfect_square_p(km)){
flag++;
}
if(mpz_perfect_square_p(lm)){
flag++;
}
if(flag > 2){
fprintf(stderr,"\ra:%d b:%d p:%d flag:%d\n",4*a,1+2*b,4*p,flag);
}
}
}
}
}
}
fprintf(stderr,"\r[%d]",p);
}
mpz_clears(am,bm,apm,bpm,nm,mm,km,lm,NULL);
cpu_time = clock();
sec = (double)cpu_time / CLOCKS_PER_SEC;
fprintf(stderr,"%lf sec\n", sec);
return 0;
}
こんな感じで適当に時間を計ったり、今どこまで進んでるのか見れるようにしたりしましょう。めっちゃ汚いですけどいいでしょう。Windows11なのでGMPを動かすためにCygwin64Terminalで動かします。パソコンのスペックはAMD Ryzen 9 5900HX with Radeon Graphics 3.30 GHzというCPU全振りノートパソコンで頑張ります。N = 10000です。
3
結果はこちら。a:28 b:21 p:44 flag:3
a:-24 b:-7 p:52 flag:3
a:104 b:153 p:100 flag:3
a:20 b:-49 p:148 flag:3
a:52 b:-63 p:228 flag:3
a:-80 b:39 p:276 flag:3
a:360 b:-105 p:424 flag:3
a:272 b:615 p:456 flag:3
a:1840 b:897 p:456 flag:3
a:44 b:-117 p:600 flag:3
a:828 b:7429 p:600 flag:3
a:-304 b:-297 p:700 flag:3
a:-168 b:-315 p:740 flag:3
a:752 b:2145 p:816 flag:3
a:364 b:4725 p:836 flag:3
a:400 b:-279 p:840 flag:3
a:4140 b:437 p:876 flag:3
a:8008 b:5425 p:920 flag:3
a:-476 b:-231 p:996 flag:3
a:364 b:627 p:1200 flag:3
a:680 b:153 p:1212 flag:3
a:2576 b:345 p:1384 flag:3
a:828 b:7429 p:1452 flag:3
a:-408 b:931 p:1500 flag:3
a:112 b:1575 p:1560 flag:3
a:1960 b:441 p:1560 flag:3
a:-276 b:115 p:1596 flag:3
a:196 b:315 p:1628 flag:3
a:924 b:-385 p:2028 flag:3
a:448 b:975 p:2280 flag:3
a:-472 b:3465 p:2320 flag:3
a:164 b:-123 p:2356 flag:3
a:600 b:-481 p:2436 flag:3
a:476 b:711 p:2604 flag:3
a:3360 b:217 p:2888 flag:3
a:-644 b:483 p:3000 flag:3
a:-396 b:403 p:3000 flag:3
a:520 b:231 p:3288 flag:3
a:-900 b:-945 p:3364 flag:3
a:2604 b:-1085 p:3380 flag:3
a:-1664 b:427 p:3500 flag:3
a:-496 b:1953 p:3576 flag:3
a:1672 b:1995 p:3660 flag:3
a:4464 b:527 p:3696 flag:3
a:-1340 b:4389 p:4380 flag:3
a:-1716 b:1463 p:4500 flag:3
a:-368 b:465 p:4680 flag:3
a:-88 b:1935 p:4732 flag:3
a:6232 b:-713 p:4808 flag:3
a:9240 b:-805 p:4836 flag:3
a:-2444 b:2511 p:5244 flag:3
a:-2340 b:1349 p:5476 flag:3
a:-588 b:1715 p:5476 flag:3
a:2772 b:-2679 p:5500 flag:3
a:76 b:-1443 p:6000 flag:3
a:3848 b:-1335 p:6120 flag:3
a:1596 b:2275 p:6204 flag:3
a:-3080 b:-711 p:6240 flag:3
a:92 b:525 p:6460 flag:3
a:1512 b:55 p:6920 flag:3
a:2108 b:9269 p:7000 flag:3
a:-2924 b:-693 p:7800 flag:3
a:5016 b:1313 p:8092 flag:3
a:-2964 b:5723 p:8200 flag:3
a:-164 b:-1677 p:8400 flag:3
a:4200 b:-3367 p:8772 flag:3
a:6396 b:-3655 p:9108 flag:3
[2499]4579.421000 sec
み、醜い。これやったところで何になるんだろうと思いました。
4
ここまで書いてきましたが、24時から9時間程度やっているので疲れました。にしても初投稿が15000字超えたのはやばいですね。もうちょっと砕かないと。 最近買う本もこの問題につながるような本ばっかりです。 整数論が好きなの?と思われるかもしれませんが、本はまだ全然読んでません。楕円方程式を力技で特殊解求めるプログラム「楕円方程式solver」を公開中です。どうぞ。使い方は、twitterにありますおりゃぁぁぁ!
pic.twitter.com/FHOttUPTIw
— Y.K. (@eyV6a3AdWcAoZhY) December 5, 2023Twitter
数強さん達は、「どうやったらそんな発想できるの」とか、「どんだけ数学が好きなの」っていうことしかないので、数強でない私の記事は、つまらないと思いまthでも、ソファ問題とか、コラッツ予想とかじゃなくて、全有理距離点問題は、理解しやすいのはもちろん、手もかなり動きやすい未解決問題だと思うし、実際手を動かしたらこの記事のように、結構いいとこまで行けたりします。だからはまりました。でもやっぱり進まないので、世の中そんな簡単じゃないなと思いました。おゎり