§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$とする。§E20.1 補題 1.2の整数$e(|x|)$は$e_{\min}$以上であるから、§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$が存在する。補題 1.2 (1)の等式を$\alpha,\beta,\gamma,\delta$に適用し、§D3.4 系 6.2により二つの列を入れ替えると行列式の符号が変わることを用いると

である。$\alpha\ne\beta$であるから$\gamma\ne\delta$であり、特に$(\gamma,\delta)\ne(0,0)$であるから、前段により$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]$である。▨