§E20.3安定な和・内積・多項式評価

証明.$I$を$\{1,\dots,n\}$の空でない部分集合、$T$を$I$上の加算木とする。$T=(i)$ならば$v_T(x)=x_i$、$d_T(i)=0$であり、$v_T(x)=\sum_{i\in I}x_i\prod_{j=1}^{d_T(i)}(1+\delta_{i,j})$は空積の表示として成り立つ。$T=(T_1,T_2)$とし、$k=1,2$について、$|\delta_{i,j}|\le u$を満たす実数により$v_{T_k}(x)=\sum_{i\in I_k}x_i\prod_{j=1}^{d_{T_k}(i)}(1+\delta_{i,j})$と書けるとする。§E20.1 系 3.3により$|\delta|\le u$を満たす$\delta$が存在して

であり、$i\in I_k$に対して$d_T(i)=1+d_{T_k}(i)$であるから、$v_T(x)$も各$i$の因子の個数が$d_T(i)$である同じ形の表示をもつ。$I_1$、$I_2$の元の個数は$I$より少ないので、$I$の元の個数に関する帰納法により任意の加算木がこの表示をもち、$I=\{1,\dots,n\}$として(1)を得る。

(2)を示す。$d_T(i)\ge1$である$i$については、$d_T(i)u\le du<1$であるから、§E20.1 補題 4.1を$k=d_T(i)$、$\varepsilon_j=1$として適用して、$\prod_{j=1}^{d_T(i)}(1+\delta_{i,j})=1+\theta_i$、$|\theta_i|\le\gamma_{d_T(i)}$を満たす$\theta_i$を得る。$d_T(i)=0$である$i$については$\theta_i:=0=\gamma_0$と置く。$k\mapsto ku/(1-ku)$は$0\le k\le d$で単調非減少であるから$\gamma_{d_T(i)}\le\gamma_d$であり、$|v_T(x)-\sum_ix_i|=|\sum_ix_i\theta_i|\le\gamma_d\sum_i|x_i|$が成り立つ。▨

証明.$R_1=(1)$では$d_{R_1}(1)=0$である。$n\ge2$ならば$R_n=(R_{n-1},(n))$であるから、$d_{R_n}(n)=1$であり、$i\le n-1$に対して$d_{R_n}(i)=1+d_{R_{n-1}}(i)$である。$n$に関する帰納法により深さの式が成り立ち、その最大値は$n-1$である。$P_{j,0}=(j)$の元の深さは$0$であり、$P_{j,l}=(P_{2j-1,l-1},P_{2j,l-1})$の元の深さは$P_{2j-1,l-1}$または$P_{2j,l-1}$における深さに$1$を加えたものであるから、$l$に関する帰納法により$P_{j,l}$の元の深さはすべて$l$である。零を補った$x'$は$\sum_ix'_i=\sum_ix_i$と$\sum_i|x'_i|=\sum_i|x_i|$を満たす。定理 1.3 (2)を、逐次和には$d=n-1$で、対分割和には$x'$と$d=m$で適用する。▨

証明.$L$の定義域は$\R^n$であるから§E20.2 定義 5.4の$U_x$は$\R^n$であり、任意の$\delta\in\R^n$に対して

が成り立つ。

(1)を示す。$M\ge|L(x)|>0$である。$\varepsilon>0$に対して、§E20.2 定義 3.1の上限$s(\varepsilon)$は上の不等式により$M$以下である。$\delta:=\varepsilon(\operatorname{sgn}(c_ix_i))_i$は$\lVert\delta\rVert_\infty=\varepsilon$と$G_x(\delta)-G_x(0)=\varepsilon M$を満たすから、$s(\varepsilon)=M$である。したがって$\kappa_{\mathrm{abs}}(G_x,0)=M$である。

(2)を示す。$L(x+x\circ\delta)=\hat y$ならば、$|\hat y-L(x)|=|G_x(\delta)-G_x(0)|\le M\lVert\delta\rVert_\infty$であるから、$\lVert\delta\rVert_\infty\ge|\hat y-L(x)|/M$である。主張の$\delta$は$\sum_ic_ix_i\delta_i=\sum_i|c_ix_i|(\hat y-L(x))/M=\hat y-L(x)$を満たし、$M>0$であるから$c_ix_i\ne0$である$i$が存在して$\lVert\delta\rVert_\infty=|\hat y-L(x)|/M$である。▨

証明.(1)は補題 2.1 (1)を$c=(1,\dots,1)$として適用したものである。定理 1.3 (2)の$\theta=(\theta_1,\dots,\theta_n)$は$\sigma(x+x\circ\theta)=v_T(x)$と$\lVert\theta\rVert_\infty\le\gamma_d$を満たすので、$\eta_{\mathrm{comp}}(\sigma,x,v_T(x))\le\gamma_d$である。$\sigma(x)\ne0$ならば$\sum_i|x_i|>0$であり、補題 2.1 (2)により$\eta_{\mathrm{comp}}(\sigma,x,v_T(x))=|v_T(x)-\sigma(x)|/\sum_i|x_i|$であるから、(1)と合わせて等式が成り立つ。▨

証明.$y/2\le2y$から$y\ge0$であり、$x\ge y/2\ge0$である。条件$y/2\le x\le2y$は$x/2\le y\le2x$と同値であり、$F=-F$であるから、$x\ge y$としてよい。$x\le2y$から$0\le x-y\le y$である。$y=0$ならば$x=0$であり、$x-y=0\in F$である。$y>0$とし、§E20.1 補題 1.2の整数$e(y)$を$e$と置く。§E20.1 補題 1.3 (3)により$e(x)\ge e$であり、§E20.1 補題 1.3 (2)により$x$と$y$は$s_e$の整数倍であって、$y=ms_e$、$1\le m\le\beta^p-1$と書ける。したがって$x-y=ks_e$を満たす整数$k$があり、$0\le x-y\le y$から$0\le k\le m\le\beta^p-1$である。$|x-y|\le y\le N_{\max}$であるから、§E20.1 補題 1.3 (1)により$x-y\in F$であり、§E20.1 系 3.2 (1)により$\operatorname{fl}(x-y)=x-y$である。▨

証明.$t:=a+b$と置く。$a,b\in F$であるから$|r|=|t-s|\le|t-a|=|b|$かつ$|r|\le|t-b|=|a|$である。主張は$a$と$b$について対称であるから、$|b|\le|a|$としてよい。$b=0$ならば$t=a\in F$であり、$t$との距離が$0$である$F$の元は$t$だけであるから$s=t$、$r=0$である。$b\ne0$とし、$e:=e(|b|)$と置く。§E20.1 補題 1.3 (3)により$e(|a|)\ge e$であり、§E20.1 補題 1.3 (2)により$a$と$b$は$s_e$の整数倍であって、$|b|=ms_e$、$1\le m\le\beta^p-1$と書ける。したがって$t$も$s_e$の整数倍である。$s$が$s_e$の整数倍でないと仮定する。このとき$s\ne0$であり、§E20.1 補題 1.3 (2)により$e(|s|)<e$である。$e(\cdot)$の定義により$|s|<\beta^{e(|s|)+1}\le\beta^e$である。$|t|\ge\beta^e$ならば、$v:=\operatorname{sgn}(t)\beta^e=\operatorname{sgn}(t)\beta^{p-1}s_e$は$F$の元であり、$|t-v|=|t|-\beta^e<|t|-|s|\le|t-s|$を満たすので、$s$が最近接点であることに反する。よって$|t|<\beta^e=\beta^{p-1}s_e$であり、$t=ks_e$、$|k|<\beta^{p-1}$を満たす整数$k$について§E20.1 補題 1.3 (1)により$t\in F$である。このとき$s=t$は$s_e$の整数倍であり、仮定に反する。したがって$s$は$s_e$の整数倍であり、$r=ks_e$を満たす整数$k$がある。$|r|\le|b|$から$|k|\le m\le\beta^p-1$であり、$|r|\le|b|\le N_{\max}$であるから、§E20.1 補題 1.3 (1)により$r\in F$である。▨

証明.$t:=x+y$と置く。$F=-F$であり、$-s$は$-t$の最近接点であるから、$(x,y,s)$を$(-x,-y,-s)$に替えても仮定と結論は変わらない。したがって$x\ge0$としてよい。$t\in F$ならば、$t$との距離が$0$である$F$の元は$t$だけであるから$s=t$であり、$s-x=y\in F$である。このとき(2)の仮定は成り立たない。以下$t\notin F$とする。このとき$y\ne0$であり、$x\ge|y|>0$である。$v\in F$が$v\le t$を満たすならば$v\le s$である。実際、$s<v\le t$ならば$|v-t|<|s-t|$となり、$s$が最近接点であることに反する。同様に、$v\in F$が$v\ge t$を満たすならば$v\ge s$である。§E20.1 補題 1.3 (2)により$x=ms_e$、$e:=e(x)$、$1\le m\le2^p-1$と書く。

$y>0$の場合、$x<t\le2x$であり、$v=x$として$s\ge x$である。$2x\le N_{\max}$ならば$2x\in F$である。実際、$m\le2^{p-1}$ならば$2x=(2m)s_e$、$2m\le2^p$であり、$m>2^{p-1}$ならば$x\ge2^{p-1}s_e=2^e$かつ$2x=ms_{e+1}$であって、$2^{e+1}\le2x\le N_{\max}<2^{e_{\max}+1}$から$e+1\le e_{\max}$であるので、どちらの場合も§E20.1 補題 1.3 (1)が適用される。このとき$v=2x$として$s\le2x$である。$2x>N_{\max}$ならば$s\le N_{\max}<2x$である。したがって$x/2\le x\le s\le2x$であり、補題 3.1により$s-x\in F$である。また$|s|=s\ge x\ge|y|$である。

$y<0$の場合、$0\le t<x$である。$-y\ge x/2$ならば、$(-y)/2\le x\le2(-y)$であるから補題 3.1により$t=x-(-y)\in F$となり、$t\notin F$に反する。よって$-y<x/2$であり、$x/2<t<x$である。$e=e_{\min}$ならば、§E20.1 補題 1.3 (2)により$y$も$s_{e_{\min}}$の整数倍であるから$t=ks_{e_{\min}}$を満たす整数$k$があり、$0<t<x=ms_{e_{\min}}$から$0<k<m\le2^p-1$であって、§E20.1 補題 1.3 (1)により$t\in F$となり、$t\notin F$に反する。よって$e>e_{\min}$であり、$x/2=ms_{e-1}$は§E20.1 補題 1.3 (1)により$F$に属する。$v=x/2$と$v=x$として$x/2\le s\le x$であり、補題 3.1により$s-x\in F$である。また$|s|=s\ge x/2>-y=|y|$である。▨

証明.$t:=a+b$、$r:=t-s$と置く。$s=\operatorname{fl}(t)$は$t$の最近接点であるから、補題 3.3により$r\in F$、$|r|\le\min\{|a|,|b|\}$である。

$|a|\ge|b|$の場合。補題 3.4 (1)を$(x,y)=(a,b)$に適用して$s-a\in F$であるから、$z=s-a$である。$s-z=a\in F$であるから$a'=a$であり、$a-a'=0\in F$、$b-z=t-s=r\in F$である。$(a-a')+(b-z)=r$である。