§E20.38頑健な幾何計算

証明.§D3.4 系 6.2により行列式は各列について線形であるから

である。同じ系により、二つの列が等しい行列式は$0$であり、二つの列を入れ替えると符号が変わるので、$\det(a,a)=0$、$-\det(b,a)=\det(a,b)$、$-\det(a,c)=\det(c,a)$であり、(1)の等式が成り立つ。その右辺は$(a,b,c)$を$(b,c,a)$に替えても変わらず、$(b,a,c)$に替えると$\det(b,a)+\det(a,c)+\det(c,b)=-(\det(a,b)+\det(c,a)+\det(b,c))$となる。右辺で$c=a$とすると$\det(a,b)+\det(b,a)+\det(a,a)=0$であり、$c=b$とすると$\det(a,b)+\det(b,b)+\det(b,a)=0$である。

$(1-\lambda)c+\lambda d-a=(1-\lambda)(c-a)+\lambda(d-a)$であるから、§D3.4 系 6.2の第2列についての線形性により(2)が成り立つ。

(3)を示す。$a\ne b$とし、$v:=b-a$、$w:=c-a$と置く。$w=tv$ならば、第2列についての線形性と二つの列が等しい行列式が$0$であることにより$D(a,b,c)=t\det(v,v)=0$である。逆に$D(a,b,c)=v_xw_y-v_yw_x=0$とする。$v_x\ne0$ならば、$t:=w_x/v_x$と置くと$w_x=tv_x$かつ$w_y=v_yw_x/v_x=tv_y$である。$v_x=0$ならば$v_y\ne0$であり、$t:=w_y/v_y$と置くと、$v_yw_x=v_xw_y=0$から$w_x=0=tv_x$であり、$w_y=tv_y$である。いずれの場合も$c=a+tv$である。

$a=b$ならば、(1)により$D(a,a,c)=D(a,c,a)=0$である。さらに$c\ne a$のとき$v:=c-a$、$c=a$のとき$v:=(1,0)$と置くと、$a,b,c$は直線$\{a+\tau v\mid\tau\in\R\}$に属するので共線である。$a\ne b$かつ$D(a,b,c)=0$ならば、前段により$c$は直線$\{a+\tau(b-a)\mid\tau\in\R\}$に属し、$a$と$b$も$\tau=0,1$としてこの直線に属するので、$a,b,c$は共線である。$a\ne b$であり、$a,b,c$が直線$\{q+\tau v\mid\tau\in\R\}$に属するとし、$a=q+t_av$、$b=q+t_bv$、$c=q+t_cv$と書く。$a\ne b$から$t_a\ne t_b$であり、$c-a=\frac{t_c-t_a}{t_b-t_a}(b-a)$であるから、前段により$D(a,b,c)=0$である。▨

証明.$x\in F$とする。$x=0$ならば$x=0\cdot s$である。$x\ne0$とする。$0<\beta^{e_{\min}}$であるから§E20.1 補題 1.2の整数について$e(0)=e_{\min}$であり、§E20.1 補題 1.3 (3)により$e_{\min}=e(0)\le e(|x|)$である。§E20.1 補題 1.3 (2)を$e=e_{\min}$として適用すると、$x$は$s$の整数倍である。$s>0$であるから$k=x/s$は一意である。§E20.1 補題 1.2 (1)により$N_{\max}$は$F$の最大元であり、$F=-F$であるから$|x|\le N_{\max}$であり、$|k|\le N_{\max}/s$である。

§D3.4 系 6.2の各列についての線形性により

である。$D(A,B,C)$は定義 1.1の展開式により整数の差と積で表されるので整数であり、$s^2>0$であるから$D(a,b,c)$と$D(A,B,C)$の符号は一致する。▨

証明.$E$は変数から減算と乗算だけで構成され、除算を含まないので、§E20.36 定義 4.1 (2)により$D_E=\R^6$であり、$f_E(\xi)$は$D$の展開式に一致する。§E20.36 定義 4.1 (3)において$E(X)$が定まらないのは除数の区間が$0$を含む場合だけであるから、式の構成に関する帰納法により$E(X)$は定まる。§E20.36 定理 4.2 (1)または§E20.36 定理 4.2 (3)により$f_E(X)\subset Y$であり、§E20.36 命題 7.1を$S=X$に適用して結論を得る。▨

証明.$\xi:=(a_x,a_y,b_x,b_y,c_x,c_y)$と置くと$X=\{\xi\}$であり、系 3.2により$f_E(\xi)=D(a,b,c)$である。$F$の元は整数と$\beta$の整数冪の積であるから有理数である。

手順定義 3.3 (1)において、変数$\xi_i$に対する値$\operatorname{out}_F([\xi_i,\xi_i])$は、端点が$F$に属するので§E20.36 定理 3.3 (1)により$[\xi_i,\xi_i]$に等しい。$E$の七つの演算のそれぞれについて、区間$Y_1,Y_2$に対する$Y_1\circ Y_2$の端点は§E20.36 定理 2.3 (1)により$Y_1,Y_2$の端点の高々四つの和・差・積の最小値と最大値である。$Y_1\circ Y_2\subset[-N_{\max},N_{\max}]$であるかは端点と$\pm N_{\max}$の比較で定まり、$\operatorname{fl}_\downarrow(z)$と$\operatorname{fl}_\uparrow(z)$は有限集合$F$の各元と$z$の比較で定まる。ここに現れる値はすべて有理数であるから、手順定義 3.3 (1)は有理数の有限回の四則演算と大小比較の後に、$E_F(X)$を得るか$E_F(X)$が定まらないことを知って終了する。$E_F(X)$が定まるならば、系 3.2を$X=\{\xi\}$と$Y=E_F(X)$に適用すると、$\inf E_F(X)>0$ならば$D(a,b,c)>0$であり、$\sup E_F(X)<0$ならば$D(a,b,c)<0$である。したがって手順定義 3.3 (1)が値を返すならば、その値は$\operatorname{sgn}D(a,b,c)$である。

手順定義 3.3 (2)において、命題 3.1 (1)により各座標$x$について$x/s$は整数であり、$D(A,B,C)$は整数の四回の減算、二回の乗算、一回の減算で得られる。命題 3.1 (2)により$\operatorname{sgn}D(A,B,C)=\operatorname{sgn}D(a,b,c)$である。これで(1)は示された。

$D(a,b,c)=0$とする。$E_F(X)$が定まるならば、§E20.36 定理 4.2 (3)により$0=f_E(\xi)\in E_F(X)$であり、$\inf E_F(X)\le0\le\sup E_F(X)$である。したがって手順定義 3.3 (1)は値を返さず、(1)により手順定義 3.3 (2)は$\operatorname{sgn}0=0$を返す。▨

証明. 必要性を示す。$p\in[a,b]\cap[c,d]$をとり、$t,s\in[0,1]$によって$p=(1-t)a+tb=(1-s)c+sd$と書く。$j\in\{x,y\}$について、$p_j=(1-t)a_j+tb_j$は$\min\{a_j,b_j\}$以上$\max\{a_j,b_j\}$以下であり、$p_j=(1-s)c_j+sd_j$は$\min\{c_j,d_j\}$以上$\max\{c_j,d_j\}$以下であるから、条件 (a)が成り立つ。補題 1.2 (2)と補題 1.2 (1)により

である。$1-s$と$s$は非負で和が$1$であるから、$D(a,b,c)$と$D(a,b,d)$がともに正ならば右辺は正であり、ともに負ならば右辺は負である。いずれも左辺が$0$であることと両立しないので、条件 (b)が成り立つ。この議論は$p\in[a,b]\cap[c,d]$だけを用いるので、$(a,b)$と$(c,d)$を入れ替えて適用すると条件 (c)を得る。

十分性を示す。三条件が成り立つとし、$\alpha:=D(a,b,c)$、$\beta:=D(a,b,d)$、$\gamma:=D(c,d,a)$、$\delta:=D(c,d,b)$と置く。実数$\mu,\nu$が$\mu\nu\le0$と$(\mu,\nu)\ne(0,0)$を満たすならば、$\mu=\nu$から$\mu^2\le0$すなわち$\mu=\nu=0$が従うので$\mu\ne\nu$であり、$\mu(\mu-\nu)=\mu^2-\mu\nu\ge0$と$(\mu-\nu)^2-\mu(\mu-\nu)=\nu^2-\mu\nu\ge0$から$0\le\mu/(\mu-\nu)\le1$である。三条件と結論は$(a,b)$と$(c,d)$の入れ替えで保たれ、この入れ替えは$(\alpha,\beta)$と$(\gamma,\delta)$を入れ替えるので、$(\alpha,\beta)\ne(0,0)$の場合と$\alpha=\beta=\gamma=\delta=0$の場合を示せば足りる。

$(\alpha,\beta)\ne(0,0)$とする。前段により$\alpha\ne\beta$かつ$s:=\alpha/(\alpha-\beta)\in[0,1]$であり、$p:=(1-s)c+sd$は$[c,d]$に属する。補題 1.2 (2)により$D(a,b,p)=(1-s)\alpha+s\beta=\alpha-s(\alpha-\beta)=0$である。$a=b$ならば補題 1.2 (3)により$\alpha=\beta=0$となり、$(\alpha,\beta)\ne(0,0)$と両立しないので、$a\ne b$である。補題 1.2 (3)により$p=a+t(b-a)$を満たす$t\in\R$が存在する。$c=d$ならば$\alpha=\beta$となり、$\alpha\ne\beta$と両立しないので、$c\ne d$である。$\gamma=\delta=0$ならば、補題 1.2 (3)により$a$と$b$は$c,d$を含む直線$\{c+\tau(d-c)\mid\tau\in\R\}$に属するので、$a,b,c$と$a,b,d$はそれぞれ共線であり、補題 1.2 (3)により$\alpha=\beta=0$となって$(\alpha,\beta)\ne(0,0)$と両立しない。したがって$(\gamma,\delta)\ne(0,0)$であり、前段により$\gamma\ne\delta$かつ$t':=\gamma/(\gamma-\delta)\in[0,1]$である。補題 1.2 (2)により、任意の$\tau\in\R$に対して

であり、$\gamma\ne\delta$であるからこの値が$0$となる$\tau$は$t'$だけである。一方、補題 1.2 (2)と補題 1.2 (1)により$D(c,d,p)=(1-s)D(c,d,c)+sD(c,d,d)=0$であり、$p=(1-t)a+tb$であるから$t=t'\in[0,1]$である。したがって$p\in[a,b]\cap[c,d]$である。

$\alpha=\beta=\gamma=\delta=0$とする。$a,b,c,d$がすべて直線$\{q+\tau v\mid\tau\in\R\}$に属するような$q\in\R^2$と$v\in\R^2\setminus\{0\}$が存在する。実際、$a\ne b$ならば、補題 1.2 (3)により$\alpha=\beta=0$から$c,d$は$\{a+\tau(b-a)\mid\tau\in\R\}$に属するので、$q:=a$、$v:=b-a$とすればよい。$a=b$かつ$c\ne d$ならば、補題 1.2 (3)により$\gamma=0$から$a=b$は$\{c+\tau(d-c)\mid\tau\in\R\}$に属するので、$q:=c$、$v:=d-c$とすればよい。$a=b$かつ$c=d$ならば、$q:=a$とし、$c\ne a$のとき$v:=c-a$、$c=a$のとき$v:=(1,0)$とすればよい。

$a=q+t_av$、$b=q+t_bv$、$c=q+t_cv$、$d=q+t_dv$と書く。$\lambda\in[0,1]$に対して$(1-\lambda)a+\lambda b=q+((1-\lambda)t_a+\lambda t_b)v$であり、$\lambda\mapsto(1-\lambda)t_a+\lambda t_b$は$[0,1]$を$T_{ab}:=[\min\{t_a,t_b\},\max\{t_a,t_b\}]$の上へ写すので、$[a,b]=\{q+\tau v\mid\tau\in T_{ab}\}$である。$T_{cd}:=[\min\{t_c,t_d\},\max\{t_c,t_d\}]$と置くと、同じ理由で$[c,d]=\{q+\tau v\mid\tau\in T_{cd}\}$である。$v_j\ne0$を満たす$j\in\{x,y\}$をとると、$\varphi(\tau):=q_j+\tau v_j$は$\R$から$\R$への狭義単調な全単射であり、$\varphi(t_a)=a_j$、$\varphi(t_b)=b_j$、$\varphi(t_c)=c_j$、$\varphi(t_d)=d_j$であるから、$\varphi$は$T_{ab}$を$[\min\{a_j,b_j\},\max\{a_j,b_j\}]$の上へ、$T_{cd}$を$[\min\{c_j,d_j\},\max\{c_j,d_j\}]$の上へ写す。条件 (a)によりこの二つの閉区間は共通の元$r$をもち、$\tau_0:=\varphi^{-1}(r)$は$T_{ab}\cap T_{cd}$に属する。したがって$q+\tau_0v\in[a,b]\cap[c,d]$である。▨