数理解析研究所講究録 1286 巻 2002 年 61-78

61-expansion に関連した
Fine 距離と alsh 関数系$\beta$赤間陽二 0 竹内大輔

東北大学大学院理学研究科数学専攻〒 980-8578 仙台市青葉区荒巻字青葉(TEL)022(217)7708 (FAX)022(217)7713
平成 14 年 4 月 29 日
概要

進法の冗長度を -\oplus \mbox{\boldmath $\varphi$} ion のエントロピーを用いて定義し, 符号
つき 2 進表現と Gray code のそれを計算した. また, 実数表現の冗長度と実数演算のTuring 機械による計算可能性との関係を認識した.
距離と Walsh 完備直交関数系は 2-expansi0n
解析における
Fine
Walshに沿った定義だが, それを一般の \beta -expansion&こ沿った定義に拡張した.
$\beta$$\beta$$\mathrm{T}\mathrm{y}\mathrm{p}\triangleright 2$1

序論

実数の表現法として 10 進法,2 進法などが用いられるが, 基数ることの重要性として, 次の 2 点を考える.

1.

$\beta$進法$(1 <\beta\not\in \mathrm{N})$は, 実数の表現法として,$n$$\beta$を一般化す

進法 $(1 <n\in \mathrm{N})$ より,

実数計算のある自然な理論では優れている.
その実数計算の理論は, Weihrauch が \mbox{\boldmath $\nu$}印 2 lin 機械という計算モデルを用いて定式化したものであり, その計算モデルは数値解析・実$\mathrm{g}$際のプログラミング言語の基準からは自然なものである.

Type-2 Turing 機械では, 実数は記号の無限列として入出力されるのだが, その出力無限列の有限部分は入力無限列の有限部分にしか依存しな
い 1. この性質のため, 10 進法で実数を表現すると実数の 3 倍が計算で
きない.
しかし

$\beta$進法を用いると, 実数$x= \sum f(i)\beta^{\vee:}$$x$の表現が複数あることになる

with

(1)

$f(i)\in \mathrm{Z}\cap[0,\beta)$.

$\frac{i=0}{*\mathrm{a}\mathrm{h}\mathrm{m}\mathrm{a}@\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{h}.\mathrm{t}\mathrm{o}\mathrm{h}\mathrm{o}\mathrm{k}\mathrm{u}_{\backslash }\mathrm{a}c\mathrm{j}\mathrm{p}}$1 これは, 丁度, 入カストリームからの情報を処理して出力ストリームに書き出す

ログラ A に対応する.

$\mathrm{C}$

言語のプ

62
そのような冗長性などにより, 進法では実数の加減乗除が機械により計算可能になるのである.
$\beta$$\mathrm{T}\psiarrow 2$$\mathrm{h}\mathrm{r}\ovalbox{\tt\small REJECT}$

2. 実数の -expansion[8] は, 解析数論. エルゴールド理論の初等的例を$\beta$与えるため重要である.
実数

$x$

の

$\beta$-expansion は, 式 (1) に条件

all $N\geq 0$$|x \sim\sum_{\mathrm{t}=0}^{N}f(i)\beta^{-i}|<\beta^{-N}\mathrm{f}\mathrm{o}\mathrm{r}$を要請して得られる文字列 $a_{-0}a_{-1}\ldots$ である.
例えば$\beta$$x$に対して一意に決まる.

として$l(\beta^{-1}+\beta^{-2}+\beta^{-3}+\cdots+\beta^{-t})=1$$l\leq\beta\leq l+1$を満たす唯一の正根を考える $(l=1,2, \ldots, t=1,2,3, \ldots, \infty)$ . こ
れらは全て Pisot 数であり,が普通の黄金比であり$l+1$ である.
では記号 0, 1,
または $l-1$ の後に長さ$\lambda_{l}^{(t)}$$\lambda_{1}^{(2)}$$\lambda_{l}^{(1)}=l,$...

$\beta\cdot \mathrm{e}\mathrm{x}\mathrm{p}\mathrm{a}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}$

の記号

$l$

$\lambda_{l}^{(\infty)}=$$t$の連が現れない.

に対して,全体の文字列としての複雑さは, 位相的エントロピー [3] として定式化され, その値はである.

各$\beta$$\beta- \mathrm{e}\mathrm{x}\mathrm{p}\mathrm{a}\mathrm{n}8\mathrm{i}\mathrm{o}\mathrm{n}$$\log_{2}\beta$

進法の一つの非冗長化が -expansion であり,のエントロ
ピーから 進法の冗長度が $1-\log_{2}\beta/\log_{2}(]\beta[)$ と定義できる (ここで] [は$\beta$$\beta$$\beta-\exp \mathrm{a}\mathrm{e}1\S \mathrm{i}\mathrm{o}\mathrm{n}$$\beta$$\beta$以上の最小の整数である).

をノイズのある通信路で伝達した場合ビット誤りを検出できるわけだが, その検出 の目安が冗長度である$\beta$$\lambda_{l}^{(t)}\mathrm{r}\mathrm{i}\mathrm{o}\mathrm{n}$$J\mathrm{J}$と思われる 2

冗長な表現法と実数演算が計算可能になる表現法に関係があるのがが興味
深い. もしそうならば, 冗長度が計算論的にどのような意味をもっのがを考えたい. 本論文では実数の加減乗除が計算可能である符号っき 2 進記法 [10] の符号つき 2 進記法の冗長度をはかる. 付録において, Gray code にょる実数表

現法のエントロピーも計算する.
また, 各
に対して,
間の距離として, Wakh 解析におけるFine 距離を一般化する. こうして得られた距離たちは互いに同値でないが,同様の性質を満たす. Walsh 解析 [9] とはー let 弾析の最も基本・単純なものであり,に基づくものであり, Walsh の完備正規直交関数系を伴う. Walsh の完備正規直交関数系を用いると, 離散フーリエ変換にょり実
数演算が高速に計算でき, 一方, 組合せ論的最適化問題の近似率のより厳密な値を導ける [2]. 本論文では, Walsh の完備正規直交関数系をの場合がら が一般の場合に拡張できることを指摘する.
$\beta$$\beta\ovalbox{\tt\small REJECT} \mathrm{i}\mathrm{o}\mathrm{n}$$2\triangleleft \mathrm{x}\mathrm{p}\mathrm{a}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}$$\beta\simeq 2$$\beta$2 この誤り検出機構は実用化は無理であろう. 注

29 参照のこと

63
本論文の記法. 正整数全体を で表し, $l,m,n,$は正整数を動き, $i,j,$ $k,$は非負整数を動くものとする. $d,d’,$は有限のアルファベット上の要素を表す変数とする. 有限のアルファベット上の有限または無限列を $w,v,$
で表し, 有限のアルファベット上の無限列を特に $f,g,$で表し, $f=f(1)f(\mathit{2})\ldots$とする. $(\sigma f)(n)=f(n+1)$ とする. 有限列に対し, 列 の連接を $wv$ で個を表し, の 回繰り返しで表し, 無限繰り返し $ww\cdots$ をで表す. 無眼列の鋤銀繰り返しは米定義とする. なお, 列 が列 に現われるとき $u\in v$ と記す.
$\mathrm{N}$$\ldots$$\ldots$$\ldots$$\ldots$$\ldots$

$w$

$v$

$t$

$\hat{w\cdots w}$

$i$

$w$

$w^{t}$$w^{\infty}$$u$

定義 Ll $\beta>1$ を基数とする実数の表現法とは,限列全体 $N$ から$[0, \frac{1}{\sim 1} \partial]$$\beta$$v$未満の非負整数たちの無への関数$\rho\beta(f)=\sum_{n\mathrm{r}1}^{\infty}f(n)\beta^{\sim n}$

.

である.

2

非冗長化された実数表現のエントロピ–

定理 2.1 ([司) $N_{\beta}:=$ { $f|f$ は適当な $x\in[0,1)$ の合で,$\beta\beta$$\beta$-ex\mu n 属 on} は$G_{\delta}$

集はその上では単射である.

定義 2.2 $l=1,2,$に属する実数$b$$t=1,2,3,$に対して以下の方程式の根で $[l,l+1]$が一意 存在するが, その逆数をで表す.
$\ldots,$.

$\ldots,$$\infty$$\lambda_{l}^{(t\}}$$\mathrm{F}_{\llcorner}^{\vee}$(2)$1=l(b+b^{2}+\cdots+b^{\mathrm{t}})$は普通の黄金比 $(\sqrt{5}+1)/2=1.6\cdots$ であり,ある.

$\lambda^{(2)}$定義 2.3 $t=0,1,2,$$\ldots$$\lambda_{l}^{(1)}=l,\lambda_{l}^{(\infty\}}=l+1$

でに対して$\varphi_{l}^{(\ell)}(x)=x^{t}-l\sum_{\llcornerarrow 0}^{t-1}x^{\dot{*}}$と定義する. このとき,
事実 2,4は$Pis\sigma t$$t$$\varphi_{l}^{(0\rangle}(x)=1,\varphi_{l}^{(t+1)}(x)=x\varphi_{I}^{()}‘(x)-l$が有限のときは$\lambda_{l}^{(t)}$数である. すなわち,

は$\lambda_{t}^{(t)}$$\varphi_{l}^{(t)}=0$である.

の唯一の正根である. また,の任意の代数的共役数の絶対値は 1 未満である.
$l=\lambda_{l}^{(1)}<\lambda_{l}^{(2\rangle}<\lambda_{l}^{(}<\cdots$

また, 任意の正整数 $e<t$ に対して$\lambda_{l}^{(t)}$<\lambda l(\infty )=l+l=t\rightarrow m 科 .

$\varphi_{l}^{(e)}(\lambda_{l}^{(t)})>0$$\lambda_{\mathit{1}}^{(t)}$

.

64
まず

に対して

$b=(\lambda_{l}^{(t)})^{-1}$1$=$$l(b+b^{2}+\cdots+b^{t-1})+(l-1)b^{t}$$+lb^{t}(b+b^{2}+\cdots+b^{t-1}.)+(l-1)b^{2t}$(3)$+lb^{2t}(b+b^{2}+\cdots+b^{t-1})+\cdots$

を基数とし $\{0, 1, \ldots,l\}$ をアに注意する. 二つの式 $(2,3)$ に見るように,は冗長な (すなわち単射でない) 記数
ルファベットとする実数の記数法への全を非冗長化, すなわち, その値域法である. そこで,$\lambda_{l}^{(t\rangle}$$\rho_{\lambda_{1}}(|)$$\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(\rho_{\lambda}(\mathrm{i}))$$\rho_{\lambda_{1}}(t)$射性を保ったまま定義域を制限して単射にする.
注 2.5 (N\lambda 。) のビットエラー検出機械としてのキュ–) N\lambda 。) に属する無限
列 $f$ には列 $kl^{t}(k<l)$ が現われない. その無限列をノイズのある seial 回線で伝送した場合, 途中で$kl^{t}$を受信したら伝送に誤りがあったと検出できる. そのために必要なのは, 長さ$t$のキューである.

一般に正整数の有限集合 $C=\{0<n_{1}<nz<\cdots<n\iota\}$ に対しては, 唯一の正根$\lambda_{\overline{C}}^{1}$(4)$1/2<\lambda_{\overline{C}}^{1}\leq 1$$1=\psi_{C}(\lambda^{-1}):=\lambda^{-n_{1}}+\lambda^{-n_{2}}+\cdots+\lambda^{-n\iota}$を持つことが中間値の定理からいえるが, そのような$\lambda c$を基数とする実数の 0,1 表現にはビットエラーパターン(each$0d_{1}\ldots d_{n_{1}-1}1d_{n_{1}+1}\ldots\cdot d_{n_{2}-1}1\ldots d_{n_{h}+1}\ldots d_{n_{k}-1}1$$d\iota$

is 0or 1)が現われないと仮定しても一般性を失わないから, 受信列にそれが現われたら伝送に誤りがあったことが検出できる. $C$ に特有な他の有限ビットエラー
パターンが存在するだろうか?
では, 誤り検査を有界なメモリで行なえるだろ
また, どのような基数では, 適当な と適当な $N$ が存在しうか ? すなわち, とのような基数$\lambda c$$t$$\lambda c$て任意の $x\in[0,$$\varpi^{1}-\mathrm{r}1$に対して$1\leq\#\rho_{C}^{arrow 1}(x)\leq t$

であるか ? ここで$\rho c$は

「 $N$ である\mbox{\boldmath $\alpha$}
その一つの解として [3] の定理がある$\rho_{\lambda_{C}}$定理 2.6 $\beta>1$ とする. 次の 3 つは同値である.

の閉包, ) は限集合 $W$ が存在して1. Subshifl($(N\beta)$$\sigma$$p$

次のマルコフである. すなわち適当な有$N\rho=\{f|(f(n),f(n+1),\ldots,f(n+p)\}\in W$

2. 適当な整数$a:$, $:=0,$$\ldots,p,0\leq a:<\epsilon$

が存在してfor any }$n$65$1-\beta^{-\mathrm{p}-1}$$\ovalbox{\tt\small REJECT}$$\sum a_{j}\beta^{-j-1}$$j\ovalbox{\tt\small REJECT}*9$$1-\beta^{-\mathrm{p}-1}$$>$$\sum_{\mathrm{j}\overline{\sim}0}^{p}a_{j+k}\beta^{-j-1}$$(k=1, \ldots,p)$

ここで an+p+l=a。$(n\geq 0)$ とした.

3. 1 の -展開$\beta$$\mathrm{t}t\beta$は周期が $p+1$ である周期列である. すなわち,\sigma 叶1\mbox{\boldmath $\omega$}\beta$=$$\omega\beta$$\sigma^{q}\omega_{\beta}$$<$$\omega_{\beta}$.

$(q=1, \ldots,p)$.

一方, $\beta>2$ ならばどんな $C$ に対しても (4) を満たさないから, 進法は有は全射とは限らない. たとえば,限的な冗長性はない. しかし,は Cantor の 3 進集合のような物になる.
進記法におけると誤り検査可能性の程度を に関して解析す非冗長化るために, 我々は記数法のエントロピーを定義する. 我々が参考にしたのは,
記号力学系である shift space の位相的エントロピーである.
$\beta$$\rho \mathrm{a}(\{0,1\}^{\mathrm{N}})$$\rho\beta$$t$$\lambda_{l}^{(t)}$定義 2.7 記数法のエントロピーを$\lim\underline{1}\log_{2}\#$$n-\nu\infty n${ $w|w$ の長さは$n$であり適当な $f\in N$ の接頭辞}と定義する. ただし, $N$ はその記数法で許されている列の集合である. 文脈により明らかなときは $N$ と記数法を同一視し, エントロピーを $h(N)$ と書く.のエントロピーは $f\in X$
記号の有限集合 に対して shift spaceのエントに現われる一つの記号が持つ情報量 (ビット) と解釈され, 特にであることが知られている.
ロピーは$X\subseteq\Sigma^{\mathrm{Z}}$$\Sigma$$\Sigma^{l}$$\log_{2}\#\Sigma$

また,定理 2.8 ([8, 3]) $h(N\rho)=\log_{2}\beta$が知られている.
注 2.9 次のグラフは, $l=1,2,3,4,5,6$ の場合を, 横軸に $t=2,3,4,$$\ldots$

をとり, 縦軸に h(N\lambda 1。) をとった折線グラフである. 記号の個数 $l+1$ とエラー
ビットパターンの長さ が増大するに従って誤り検査能力が減っているのだ$t$が, 全ての垣こ対して $t\geq 4$ では誤り検査能力がほぼないことがわかる.

66

図 1: \lambda 1(0 \psi ansion のエントロピー

2.1$h(N_{\lambda_{\mathrm{t}}}(t\rangle)$. 横軸は .
$t$

符号付き 2 進表記の冗長度

符号つきの 2 進記法とは$N\pm=${ $f|$ h よ -1, 0, 1 の無限列}に自然に拡張した関数内である. さて, -1, 0, 1 の列 の中の一 1, 1 をそれ
ぞれ -1 に置き換えたものを で表す. &\kappa tion 1 で見たように内は冗長である (単射でない). 基数が 2 であるため,
$w$

$1,$

$\varpi$$\rho_{2}(\cdots 10^{\infty})$$=$$\rho_{2}(\cdots 01^{\infty})$$\rho_{2}(\cdots \mathrm{T}0^{\infty})$$=$$p_{2}(\cdots 0\mathrm{r})$

.

(5)

.

(6)

であるが, 記号として -1 が使えるため,$p_{2}(\cdots 10^{}\mathrm{T}\cdots)$$=$$\rho_{2}(\cdots 01^{t+1}\cdots)$$(: =0,1,2, \ldots)$.

(7)$p_{2}(\cdots\overline{1}0^{}1\cdots)$$=$$\rho_{2}(\cdots 0\mathrm{P}^{+1}\cdots)$$(i=0,1,2, \ldots)$.

(8)である. そこで, 上の 4 式 (5,6,7,8) の右辺の形でない 0,1 無限列全体を人 ’とする. すなわち,$\pm${ $f\in N\pm|$

任意の$01^{\infty}$$i$に対して $f$ は, of,$10^{-}\overline{1},$$\overline{1}0^{\dot{\iota}}1$のい$\backslash \mathrm{f}\text{れ}$も含$\text{ま}$

ない}

67
とする. このの任意の要素 $f$ を先頭文字から $f(\mathfrak{h},f(2),$と走査すると符$\cdots$号が反転しないから, その符号で分類すると$N_{\pm}’=(N_{\lambda_{1}}(\infty)\backslash \{0^{\infty}\})w\{0^{\infty}\}\theta(\pi_{\lambda_{1}}\overline{\mathrm{t}\infty)}\backslash \{0^{\infty}\})$と書ける. ただし$\overline{N_{1}^{(\infty)}}:=\{\overline{f}|f\in N_{1}^{(\infty)}\}$

定瑠 2.10(非冗長化符号付き 2 進記法) $\rho\pm:=$ 内 [$N_{\pm}’$は$N_{\pm}’$から [-1,1]への全単射である.
したがって, $N’$ に属する無限列 $f$ をノイズのある seri 一回線で伝送した場
合, 符号が変わったら伝送に誤りがあったと検査できる. その検査に必要なメ
モリは lbit である.
さて,$\langle N_{\pm}’,$$\rho_{2}\mathrm{r}$$\lim\underline{1}\log_{2}\#$$narrow\infty n$

人\sim 》のエントロピーは定義から{ $w|w$ の長さは$n$であり適当な $f\in N_{\pm}’$ の接頭辞}であるが, 対数の引数の部分を計算すると次のようになる.
$\#${ $w[w$ の長さは{$w|w$ の長さは

$+$

$\#$

$=$

$2^{n}+(2^{n}-1)$

定理 2.11 ($N_{\pm}’,$$n$であり適当な$n$であり適当な$f\in N_{\lambda_{1}}(\infty)$の接頭辞}$f\in\pi_{\lambda_{1}}^{--}\mathrm{t}\infty)\backslash \{0^{\infty}\}$

の接頭辞}

.

$\rho_{2}\mathrm{r}N_{\pm}’\}$のエントロピー $h(N_{\pm}’)$ は 1 である. したがって,

符号つき 2 進表記の冗長度は 1-10’ $2/\log_{2}3$ である.

の区分的線形関数により生或され, 2 進 Gray code がテント関数により生成されるように, $[0, 1]$ の区分的線形関数で傾きの絶対値
が 1 より大きい任意の関数により実数の表現法が得られる. その例として, 付録において, 1+1 進 Gray code $\langle l=1,2,$を導入しそのエントロピーを計算している 3.
$\beta\sim \mathrm{e}\mathrm{x}\mathrm{p}\mathrm{a}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}$が傾き$\beta$$\ldots)$

3Walsh 解析にむけてFine 距離を通じた Fourier-Walsh 解析における計算可能性については, 既に森 [7] らと Brattka[l] とにより考えられているが, そこに現れる Walsh 直交関数系は 2 進法に沿って定義されていた. 我々はそれを拡張し進法に$\lambda_{l}^{(t)}$沿った一 h 直交関数系を与える.
3 有限 1 進数を用 る ジ fl 機械で多項式時間計算可能な言語全体は Linear Space であり, このように基数 1 と 2 の間に大きなギャップがある. エントロピーは 2 進数への変換効率を表すことと理解すれば, こ tllf1 進数のエントロピーが 0 であることに原因があると思われる.
$\mathrm{t}\backslash$$\mathrm{X}$68$l=1,2,$$t=2,3,$$\ldots,$$\ldots,$に対して$\infty$.

$\rho_{\lambda_{l}^{(\ell)}}\uparrow N_{\lambda_{l}^{(2)}}’$$N_{\lambda_{l}^{(t)}}arrow[0,1]$は全単が存在する.
射であったから逆射$[0, 1]$ 上の一般化として, $[0, 1]$ 上の距離である, 基
距離であ Fine
による Fine 距離を定義する. 2 点 $x,y$ がともに内点であれば,
数$d_{t}(x,y)$ は $x,y$ のそれぞれのに関する名前の Cantor 距離のよ$(\rho\lambda_{l}(t)\uparrow N_{\lambda}(t\rangle)^{-1}$$\text{距}k$$\text{る}$$\sigma\supset$$\lambda_{1}^{(t)}$$d_{t}$$\rho_{\lambda_{l}^{(k)}}\mathrm{r}N_{\lambda_{l}^{(t)}}$うなものである.
定義 3.1 (碁数

1. 基数$\lambda_{1}^{(t)}$$\lambda_{1}^{(t)}$による Fine 距離)$t_{\overline{\sim}}2,3,$$\infty$$\backslash \cdot.,$とするによる苫 ne 距離 4: $[0, 1]$ $\mathrm{x}[0,1]arrow[0,2]$ とは次のように定義される.
$d_{t}(x,y)$$=$$\sum_{n=1}^{\infty}|(\rho_{\lambda_{1}^{(2)}}\mathfrak{l}N_{\lambda_{1}^{(t)}})^{-1}(x)(n)-(\rho_{\lambda_{1}^{(l)}}\mathfrak{l}N_{\lambda_{1}^{(t)}})^{-1}(y)(n)|(\lambda_{1}^{(t)})^{-n}$,if $x,y$ がともに 1 未満.
$\phi(x,y)$$=$$d_{t}(x,y)$$=$

普通の Fine 距離は

2. Fine 距離$d_{t}$

if $x,y$ のいずれかが 1.
o.w.(このとき $x,y$ がともに 1).

20$d_{\infty}$となる.

で誘導される [0, 月上の位相を基数$\lambda_{1}^{(l)}$の Fine 位相 $T^{(t)}$と定義する.
普通の Fine 位相は3.

$f\in\psi_{1}^{t)}$が$T^{(\infty)}$$\mathrm{h}.\mathrm{m}_{n}f(n)=0$

書く. 2 進有理数全体はとなる.

である場合,$\mathfrak{G}^{\infty)}$$q=\rho_{\lambda_{1}}(\iota)\mathrm{f}N_{\lambda \mathrm{i}}()(f)\in\Phi^{t)}$

と

となる.

のグラフの直線の傾きの絶対値を 1 とするために 4 の定義とした.
において巾の底を$\phi(x, (\lambda_{l}^{(t)})^{-1})$$(\lambda_{l}^{(t)})^{-1}$定理 $.2 異なる $s,t=2,3,$$\mathit{1}$$\ldots,\infty$に対して. \leq ls)\cap (〆 0\neq \emptyset .

2.

$d.,d\mathrm{t}$は同値でない.

の性質からでる. (2) 正数 を十分小さいとすの最小多項式(1))$x\inq\cdot$
であ
に対して
ならば,
る. 任意のである. 従って, 任意の $x,y$ に対して $d.(x,y)\leq\alpha d.(x,y)$るがとなる正定数 は存在しない. (証明終り)

証明.

$\varphi_{1}^{(t)}$$\lambda_{1}^{(t)}$$\epsilon$$1/\lambda_{l}^{(t)}-x<\epsilon$$d_{t}(x,\lambda_{l}^{(t)})\approx 2/\lambda_{l}^{(t)}$$d.(x,\lambda_{l}^{(t)})\approx 0$$\alpha$定環 $.$ $t=2,3,$$\ldots,\infty$に対しても開集合である. ただし, $q\in\Phi^{t)}$ ,$T^{(t)}$では開区間のみならず半開区間 $[q,r)$

69

図 2: 右の

証明.

のグラフでは$d_{\epsilon}$$x\in\Phi^{\iota)}$

なる点で不連続である

より$q\in \mathfrak{G}^{l)}$$\forall n>n_{\theta}.(\rho_{\lambda_{1}^{(t)}}\mathrm{t}N_{\lambda_{1}^{(t)}}\rangle^{-1}(q)(n)=0 \langle 9)$となるが存在する. このとき

$n_{0}$$q$の開球が半開区間になること$\{y|d_{t}(q,y)<(\lambda_{1}^{(t)})^{-n\mathrm{o}}\}=[q,q+(\lambda_{1}^{(t)})^{-n\mathrm{o}}$を示す. その開球の要素\exists m\leq n か
とすると

従って,

$y$

に対して

$(\rho_{\lambda_{\mathrm{l}}^{(\mathrm{g})}}[N_{\lambda_{1}^{(\cdot)}})^{\sim 1}(q)(m)\neq(\rho_{\lambda}(\mathrm{i})$「 $N_{\lambda_{1}^{(t)}})^{-1}(y)(m)$の定義から以下の任意の $m$ に対して

$d_{t}(x,y)\geq(\lambda_{1}^{(t)})^{-m}.\geq(\lambda_{1}^{(t)})^{-n\mathrm{o}}$$\rho_{\lambda_{1}}(t)\mathrm{r}N_{\lambda_{1}}(t)$$n_{0}$$(\rho_{\lambda_{1}^{(t)}}(N_{\lambda_{1}^{(t\}}})^{-1}(q)(m)=(\rho_{\lambda_{1}^{(t)}}\mathrm{r}N_{\lambda_{1}^{(l)}})^{-1}(y)(m)$$q\neq y$

(10)

)

の場合は,

$n_{0}$

より大きな適当な $m$ に対して$(\rho_{\lambda_{1}^{(t)}}\mathrm{f}N_{\lambda_{1}^{\langle t)}})^{-1}(y)(m)$る. 従って, $y>q$.

$y$となり, (9) よりの上限は無限列...

$(\rho_{\lambda_{1}^{(t)}}$($\rho_{\lambda_{1}^{(t)}}$

. 矛盾.

.

I/VXI。)-I(q)(m)\neq『 $N_{\lambda_{1}^{(t)}})^{-1}(y)(m)=1$ であ$(m)1\cdots 1(01^{t-1})^{\infty}\check{t-1}$の値だが, それをはない. 従って, が*満である.
実際に実現する
故に (10) が言えた.
すると, 半開区間 [ ,\rightar ow も開集合であることが直ちに言える. (証明終り)$f\in N_{\lambda_{1}^{(t)}}$

$q$

$y$

$q+(\lambda_{1}^{(t)})^{-n_{0}}$

70
3.1

Wa 化 h 直交関数系の拡張

まず, いくつかの区間を記号で表す.

.

$U$

$:=$

$[0, 1]$$U_{0}$$:=$$[0, \frac{1}{\beta})$$U_{1}$$:=$$[ \frac{1}{\beta},1]$.

,

それぞれの長さを対応する小文字で表す.
$u_{0}$$:=$$|U_{0}|:= \frac{1}{\beta}$$u_{1}$$:=$$|U_{1}$

I.

$: \approx\frac{\beta-1}{\beta}$.

また$M:=$ 上 2 つの相乗平均とする. 基数が一般の記数法にそった Rademacher 直交関数系$0,1,2,$$\ldots\}$$\{\emptyset:|$$:=$として新たに次のように定義する.

$\phi(x)$

$:=$

1.

$\psi(x)$

$:=$

$\{$

$\phi_{n+1}(x)$$:=$$u_{1}/M$$x\in U_{0;}$$-u_{0}/M$$x\epsilon U_{1}$.

$\phi_{n}(x/u_{0})$$x\in\ovalbox{\tt\small REJECT}$$\phi_{n}((x-u_{\mathrm{O}})/u_{1})$$x\in U_{1}$

$\{$

.

上の関数系は, $\beta=2$ のときは, 2 進数にそった Rademacher 直交関数系に一致する.
上の Rademacher 直交関数系
から基数が一般である
記数法にそった Walsh 直交関数系 { : 目 $=0,1,2,$を従来のとおりにっ$\{\emptyset:|i\overline{\sim}0,1,2, \ldots\}$$\emptyset$$\ldots\rangle$

くる.

非負整数

$n$

に対して, その 2 進表記$(h_{k}\ldots h_{0})$に関して,$\psi_{n}(x):=\prod_{:}\phi_{}^{h_{l}}\langle x)$と定義する. 上の関数系は, $\beta=2$ のときは, 2 進数にそった Walsh 直交関数

系に一致することに注意する.
定理 3.4 $\{\emptyset:|:=0,1,2, \ldots\}$ は実際に直交関数系である. すなゎち,

任意の非負整数 $i,j$ に対して
《 , \psi j)t2。
$\psi_{\{}$$=$$\delta_{1j}.$.

71$\mathfrak{W}\Re$.

$k_{1}>\ldots>k_{l}>1,$ $n_{1},$ $\ldots,n\iota,m\in\{0,1,2\}1_{\llcorner}^{\vee}?\backslash ?\mathrm{b}T$

$I$

$=$

$\int_{U}\phi_{k_{1}}^{n_{1}}(x).,.\phi_{k_{l}}^{n\iota}(x)\phi_{1}^{m}(x)dx$$=$$\int_{U_{\mathrm{O}}}\phi_{k_{1}}^{n_{1}}(x)\ldots\phi_{k_{l}}^{n’}(x)\phi_{1}^{m}(x)$血$+ \int_{U_{1}}\phi_{k_{1}}^{n_{1}}(x)\ldots\phi_{k\iota}^{n_{l}}(x)\phi_{1}^{m}(x)dx$

Rademacher 直交関数系
$I$

$=$

$\{\phi 0,\phi_{1}, \ldots, \}$の定義から$\int_{U_{\mathrm{O}}}\phi_{k_{1}-1}"(x/u_{\mathrm{O}})\ldots\phi_{k_{l}-1}^{n_{l}}(x/u_{0})(M^{-1}u_{1})^{m}dx$$+ \int_{U_{1}}\phi_{k_{1}-1^{n_{1}}}(\frac{x-u_{0}}{u_{1}})\ldots\phi_{k_{t}-1^{n_{l}}}(\frac{x\sim u_{\mathrm{O}}}{u_{1}})(-M^{-1}u_{0})^{m}dx$

第一の積分を $s=x/u_{0}$ とおき置換積分し, 第二の積分を$v= \frac{x\sim \mathrm{u}}{u_{1}}$とおき置換積分すると,$I$$=$$u_{0}(M^{-1}u_{1})^{m} \int_{U}\phi_{k_{1}-1}’*_{1}(s)\ldots\phi_{k_{l}-1^{n_{l}}}(s)ds$$+u_{1}(-M^{-1}u_{0})^{m} \int_{U}\phi_{k_{1}-1^{n_{1}}}(v)\ldots\phi_{k_{l}-1^{n\iota}}(v)dv$$=$$( \int_{U}\phi_{k_{1}-1^{n_{1}}}(x)\ldots\phi_{k_{l}-1^{n\iota}}(x)\ )(u_{\mathrm{O}}u_{1}^{m}+u_{1}(-u_{0})^{m})M^{-m}$である. ここで, $v0+u_{1}=1$ より$(u_{0}u_{1}^{m}+u_{1}(-u_{0})^{m})M^{-m}=\{$となるため, 巾$n_{1},$$\langle\psi_{:},\psi_{j}\rangle_{L(U)}2=\delta_{- j}$$\ldots,n_{l},m$に0if $m=1$ ;1if $m=0,2$ .

1 があれば, $I=0$ となる. したがって,. (証明おわり)-expansion は, 高次元にも拡張され ([5, 4]),の表現法として計算
特に 2 次元ではタイリングとなる. -expansion がの表現法として計算論的に重論的に重要であったように, タイリングが要であるかを調べられればと思う. 論文 [5] は, タイリングの上の Haar-typewavelet(Walsh function と密接な関係がある) を一つの動機としているのだ
が, そのような流れを踏まえ, 高次元空間での計算論と結びつけばと希望して$\mathrm{R}$において定義されていた$\beta$$\mathrm{R}$$\beta$$\mathrm{R}^{2}$いる.

謝辞
新潟大学の秋山茂樹先生, 熊本県立大学の貞広泰造先生, 京都産業大学の森隆一先生には文献を紹介してもらい, 多くを教わった. 九州大学の吉川敦先生には, この論文の初期の内容を発表する機会を与えて下さった. これらの先生方のみならず, 内容にたいしてコメントを下さった識者に感謝する.

72
参考文献
[1] Vasco Brattka. Some notes on fine computabilty. Journal of Universal
Computer Scienoe, $8(3):382-395$ ,2002.
[2] J.

. Some optimal inapproximability results. Journal of $ACM$,$\mathrm{H}^{\mathrm{Q}}\mathrm{a}\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{d}$Vol. 48,$\mathrm{p}\mathrm{p}$. $n8-859$ ,2001.

[31 Shunji Ito and Yoichiro Takahashi, Markov subshifts and realization of, J. Math. Soc. Japan 26 (1974) no. 1, 33-55$\beta- \mathrm{u}\mathrm{p}\mathrm{a}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}$[4] Richaed Kenyon and Anatoly Vershik. Arithmetic construction of sofic
partitions of hyperbolic toral autom.orphisms. Ergodic Theory Dynam.
Systems, Vol. 18, No. 2, . 357-372, 1998.
$\mathrm{p}\mathrm{p}$[S] Jeffiey C. Lagariae and Yang Wang.
-affie tiles inStandard and nonstandard digit sets. J. London Math. Soc. $()$ ,No. 1, pp. 161-179, 1996.
$\mathrm{h}\mathrm{t}\mathrm{e}\Psi \mathrm{a}\mathrm{l}\Re 1\mathrm{f}$$\mathrm{R}^{n}$$\mathrm{V}\mathrm{o}\mathrm{l}$

[6]

.

. I.
$54$

,

Lind and Brian Marcus. An $intmduet:on$ to symbolic dynamics
and coding. Cambrdige University Press, 1995.

$\mathrm{D}\mathrm{o}\mathrm{u}\mathrm{g}\mathrm{l}\mathrm{a}8$[7] Takakazu Mori. On the computabilty of Walsh functions. TheoreticalComputer Science(to appear), 2002.
[8] W. Parry. On the -expansions of real numbers. Acta Mathematica,. Hung., 11:401-416, 1960.
Acad.
$\beta$$S\dot{\alpha}$[9] F. Schipp, W. R. Wade, and P. Simon. Wabh series. Adazn Hilger Ltd.,
Bristol, 1990. An introduction to dyadic harmonic analysis, With thecollaboration of J. P4.
[10] K. Weihrauch. Computable Analysis: An $int|vduction$. Springer, 2000.

付録
A.

$n$

進グレイコードの非冗長化について

実数 の $l+1$ 進 Gray code 展開 $(l=1,2, \ldots)$ は次の区分的線形関数のグラフで生成される :$x$$j=0,1,\ldots$ , 垣こ対し,$\epsilon_{J}^{\langle l)}$は $[0, 1]$ から$[_{l}++,\cdot\vdash_{+1}^{+1}]$への関数で,$x= \xi_{j}^{(l)}(y):=\frac{2[_{2}^{\llcorner^{\underline{1}}}+]}{l+1}.+\frac{(-1)^{j}y}{l+1}$

73

l:( End$l:e\mathrm{v}e\mathrm{n}$図 3: $l+1$ 進 Gray code を生成するグラフ $\{x=\xi_{i}^{(l)}(y)\}_{0\leq:\leq t}$ のグラフ.
である.

全ての
$g:\mathrm{N}arrow\{0,1, \ldots,l\}$に対してその Gray code 展開における値 (意味)$\pi\iota(g)$

に関して

(11)

$\pi\iota(g)=\xi_{g(1)}^{(l)}(\pi\iota(\sigma g))$が成立する. ここで

従って,

$v$

$\sigma$はシフト $\sigma(g)(n)=g(n+1)$ である.

の後に有限列 $w$ の無限繰り返しが続く列$v(w)^{\infty}$に対して$\pi\iota(v(w)^{\infty})$$=$$\xi_{v}^{(l)}(\pi_{l}(w^{\infty}))$(12)$\pi_{l}(w^{\infty})$$=$$\xi_{w}^{(l)}(\pi\iota(w^{\infty}))$$(13\rangle$と書ける. ここで, $v=v(1)v(2)\ldots v(n\rangle$ に対して$\xi_{v}^{(l)}\overline{arrow}\xi_{v(1)}^{(l)}\circ\ldots\circ\xi_{v(n)}^{(l)}$(w 勺が, コンパクト集合 $[0, 1]$ 上の縮小写像
が一次関数だから一意性は明らか). 従っの不動点として一意に決まる (は $[0, 1]$ に属する有理数である. 特に 0 のの値て, 周期列
無限列の値は 0 である.
と定める.
そこで,
と書いた. 式 (13) から,$\xi_{w}^{(l)}$$\pi\iota$$\xi_{w}^{(l)}$$\pi\iota(v(w)^{\infty})$$v\langle w)^{\infty}$$\pi\iota(g)=\lim_{n}\{\pi\iota(g(1)g(2)\ldots g\langle n)\mathrm{O}^{\infty}))$定義垣$\geq 1$に対して,$\pi\iota$: $\{0, 1, \ldots,l\}^{\infty}arrow[0,1]$ を$\pi_{l}(g):=1\dot{\mathrm{m}}\xi_{g(1)}^{(l)}\circ\xi_{g(2)}^{(l)}0\ldots\circ\xi_{g\{n)}^{\{l)}(0)narrow\infty$により定める.

74$\pi_{l}(g)$り,は $[0, 1]$ の要素になることをいう .

$n$に関する縮小閉区間列を作る.

$|_{\llcorner}^{-}\mathrm{R}\mathrm{R}\text{する}$$\pi\iota(g)$は縮小一次関数であは $[0, 1]$ に属するから, それら 2 つを端点とする閉$\xi_{g(n+1)}^{(l)}(0),\xi_{g(n+1)}^{(l)}(1)$区間は$\xi_{g(1)g(2)\ldots g(n)}^{(l)}$$\lim_{n}\xi_{g(1)g(2)\ldots g(n)}^{(l)}(0)$.

が (11) を満たすことは$\xi_{g(1)}^{(l)}(\pi_{l}(\sigma g))$$\xi_{g(1)}^{(l)}$は $[0, 1]$ の要素の連続性による :$=$$\lim_{n}\xi_{g(1)g(2)\ldots g(n+1)}^{(l)}(0)$$=$$\lim_{n}\zeta_{g(1)g(2)\ldots g(n)}^{(l)}(0)$$=$$\pi_{l}(g)$.

特に,$\pi_{l}(g)-arrow 0$$\Rightarrow$$g(1)=0$$\pi\iota(g)=1$$\Rightarrow$$g(1)=l$.

定珊 2 $k\geq 1$ に対して,{ :$G_{2k-1}:=$$f$$\mathrm{N}arrow\{0,1, \ldots,2k-1\}|$

すべての $i\leq k$ に対して $(2i-1)(2k-1)\mathrm{O}^{\infty}\not\in f$

かつすべての $i\leq k-1$ に対して
$G_{2k}:=$

{ :
$f$

$(2i)0^{\infty}\not\in f\}$$\mathrm{N}arrow\{0,1, \ldots,2k\}|$

すべての $:\leq k$ に対して $(2i-1)(2k)^{\infty}\not\in f$

かつすべての $i\leq k$ に対して$(2i)0^{\infty}\not\in f\}$と定める. このとき, $l\geq 1$ に対して$\varpi_{l}:=\pi_{l}$『$G_{l}$

から $[0, 1]$ への全単射である. したがって,
1) である.
は$G\iota$

証明.

かつ $f\neq g$ と仮定し,$G\iota$のエントロピーは $\log_{2}(l+$:=m 石{i\in N $|f(i)\neq g(:)$ } とする. 一般性を失わず $f(i)>g(i)$ としてよいが,’$\varpi(f)=\varpi(g)$$i$$\pi\iota(\sigma^{:-1}f)\in[ffl^{l},$ $[perp] f-\llcorner+1]l+1$$\pi\iota(\sigma^{:-1}g)\in[_{l+1l+1}^{\Delta g-\mathrm{g}\mathrm{L}^{t}\llcorner+1},],$$i+1,$ $g(i)=j,$$\pi\iota(\sigma^{:-1}f)=i+1l\mp 1++_{+}^{\pi\iota\sigma}‘\neq \mathit{1},$$\pi\iota(\sigma^{:}f)\Rightarrow\pi_{l}(\sigma^{\{}g)\simeq 0$である.

$\pi\iota(\sigma^{-+1}f)=\pi\iota(\sigma^{\dot{\iota}+1}g)=0$$f(1)f(2)\ldots f(i-1)(j+1)0^{\infty}$ であるから,であるがら, 特に $f(i)=$としてよい.

$\pi\iota(\sigma^{l-1}f)=\pi_{l}(\sigma^{l-1}g)=.\mathrm{f}\mathrm{l}_{+}^{1}$が奇数のとき.
あるから,$1)=0$ であり,

$j$$\pi\iota(\sigma^{:-1}f)=\pi\iota(\sigma^{:-1}g)$$\pi_{l}(\sigma^{:-1}g)=.\vdash_{+1}^{+1}-\dashv_{+1}^{\pi\iota\lrcorner\sigma^{l}g}$でしたがって, $f(:+1)=g(i+$である. 以下同様にして, $f=$$f\not\in G\iota$

である.

75
$l$

. であるから,

が奇数,

$j$

.

が偶数のとき.

$\Delta_{l+1}^{\sigma}\pi_{l}\dot{A}^{g}$$\pi\iota(\sigma^{:-1}f)=i_{+}^{\mathrm{L}_{1}^{2}}-\dashv_{+}^{\sigma}\pi_{l}\lrcorner_{1}^{l}1,$$\pi\iota(\sigma^{:}f)=\pi\iota(\sigma^{:}g)=1$$g(i+1)=l$ であり,$\pi\iota(\sigma^{:\sim 1}g)=\neq_{+\overline{1}}$である. したがって, $f\langle:+1)=$である. 以下同様にして,$\pi\iota(\sigma^{\dot{\iota}+1}f)=\pi\iota(\sigma^{|+1}.g)=1$$f=f(1)f(2)\ldots f(i-1)(j+1)l^{\infty},$ $g=f(1)f(2)\ldots f(i-1)jl^{\infty}$$(j+1)l^{\infty}\in f$であるからともに偶数のとき.

$l,$ $j$十$f\not\in G\iota$

であるが,

である.

$\pi\iota(\sigma^{:-1}g)=+^{\pi_{l}}+_{+1}^{\sigma^{t}\Delta}\overline{\iota}+\overline{1}$$\pi\iota(\sigma^{t-1}f)=\mathrm{f}_{+1}^{\llcorner 2}.-\dashv_{+1}^{\sigma}\pi_{\iota\lrcorner1\mathrm{j}}‘,$

であるから, $\pi\iota(\sigma^{:}f)=\pi\iota(\sigma g):=1$ である. したがって, $f(i+1)=g(i+$$f(i+1)=$$1)=l$ であり, $\pi_{l}(\sigma^{1+1}.f)=\pi_{l}(\sigma^{-+1}g)=0$ である. よつ$g(i+1)=0$ であり, $\pi_{l}(\sigma^{-+2}f)=\pi_{l}(\sigma^{|+2}.g)=0$ である. 以下同様にして,$f=f(1)f(2)\cdots f(i-1)(j+1)l0^{\infty},$ $g\underline{-}f(1)f(2)\cdots f(i-1)jl0^{\infty}$ であるが,$\text{て},$$(j+1)l0^{\infty}\in f$

B.

$\lambda_{l}^{(t)}$であるから$f\not\in G\iota$

である (証明おわり)-expansion のエントロピーについての一考察

この部分は論文 [3] の定理から特殊系として出る次の定理を, 論文 [3] の定-expansion に関連する推移行
理を知る前に, 証明したときのものである.
列として, 単純な行列が現れ, そのその固有値・固有ベクトルとしてきれいな$\lambda_{l}^{(t)}$ものが現れたので以下に報告しておく.
定理 3 $t=2,3,$$\ldots,\infty$に対して, 記数法

$N_{\lambda_{l}}.(t$}のエントロピ–$\mathrm{F}\mathrm{h}$$\log_{2}\lambda_{l}^{(t)}$である.

N\lambda 。) のビットエラー検出機械は長さ証明の方針をまず説明する.

キューであったが, その状態遷移図を表す接続行列と, $\sum_{k,m}((A^{(l,t)})^{n})_{k,m}$ は異なる$\#$

{ $w|w$ の長さはである. 上式を

$n$

$n$

$n$

$A^{(l,t)}=(A_{k,\acute{m}}^{(\mathrm{t}t)})$

$t$

の

を考える

回遷移の個数である. すなわち,

であり適当な$f\in N_{\lambda_{l}}(t)$の接頭辞}に対して漸近的に評価するために, 以下の命題を用いる.

命題 4([6]) 実正方行列 $A$ の各成分は非負であり, $A$ は零行列でないとす
る. $A$ の適当な固有ベクトルの各或分が正ならば, 対応する固有値 は正で$\lambda$

あり, しかも, 任意の正整数

$n$

に対して

$( \sum_{k}e_{k}/\max_{k}(e_{k}))\lambda^{n}\leq\sum_{k,m}(A^{n})_{\mathrm{k},m}\leq(\sum_{k}e_{k}/\min_{k}(e_{\mathrm{k}}))\lambda^{n}$N\lambda 。) のビットエラー検出機械は長さ$t$.

のキューである. 各状態はキューの内

ら, 桁数 の $(l+1)$ 進数 $i=(a_{1}a_{2}\ldots a_{t})_{l+1}$ で表され, 状態数は $(l+1)^{t}$
が人力 により状態 $j=(b_{1}b_{2}\cdots b_{t})_{l+1}$ こ
である.

容だ

$t$

$\mathrm{B}^{\mathrm{a}}$$\Re \mathrm{a}\mathrm{e}i=(a_{1}a_{2}\cdots a_{t})_{l+1}$$d$遷移するのは$a_{2}=b_{1}$, かつ... かつ, $a_{t}=b_{t-1}$

(14)

76
かつ $b_{t}=d$ かつ$a_{1}b_{1}\ldots b_{t}$は$N_{1}^{(t)}$のビットエラーパターンではない, すな

わち

任意の $d<l$ に対して

$a_{1}b_{1}\ldots b_{t}\neq dl^{t}$

.

(15)

さて, 状態遷移図はラペル付き有限グラフであり, ある状態
記号 によりある状態への遷移がひきおこされる場合は,
$q’$

$s$

$q$

$q$

において入力を表す頂点かのビットである辺が存在する. しかし,エラー検出機械の状態を上のように $(l+1)$ 進数で表せば, 遷移後の状態から
ら $q’$ を表す頂点ヘラベルが$s$$N_{\lambda_{l}}(t)$その遷移をひきおこす入力記号がわかるから, N\lambda l。の状態遷移図は, 0 また
は 1 を成分とする $(l+1)^{t}$ 次正方行列で表される.
$A^{(l,t)}$定義 5 $2\leq t<\infty$ に対し,のビットエラー検出機械の状態遷移図は,または 1 を或分とする $(l+1)^{t}$ 次正方行列で表され, その $ij$ 成分$N_{\lambda_{l}}(t)$$A^{(l,t)}$$\ovalbox{\tt\small REJECT}$.

$A!_{j}^{t,t)}$は次の通りである.

if $((:-1)\mathrm{m}\mathrm{o}\mathrm{d} (l+1)^{t-1})=\lfloor(j-1)/\langle l+1$ )ハ式 (14) が成立する $*/$$\rfloor$thenif[ $(i-1)/(l+1)^{t-1}\rfloor<l$ and $j-1=(l+1)^{t}-1$$/*$ 式 (15) が成立しない $*/$
0e 化 ethen

1flelse 0fl
ここで, $A^{(2,2)}$ を図示すると次のようになる.

$\{\begin{array}{lllllllll}\mathrm{l} \mathrm{l} 1 1 1 \mathrm{l} \mathrm{l} 1 01 \mathrm{l} 1 1 1 1 1 1 01 1 1 1 1 1 \mathrm{l} 1 1\end{array}\}$

ただし空白になっている成分は 0

補題 6 $2\leq t<\infty$ に対し, ベクトル $e=(e_{1}, \ldots,e(l+1)^{t})$ を次のように定義
する.
$e_{k}$$e_{(l+1)^{t}}$

すると,

$e$

$=$

$(\lambda_{l}^{(t)}rightarrow 1)\varphi_{l}^{(\max\{t:(l+1)|k\rangle)}‘(\lambda_{l}^{(t)})$

$=$

$l$

$(1\leq k\leq(l+1)^{t}-1)$.

は $A^{(l,t)}$ の$\lambda_{l}^{(t)}$に属する固有ベクトルである.

77
証明.

$(\lambda I-A^{(l,t)})e=0$, すなわち, 任意の$i$に対して $1\leq i\leq l$ ならば$\sum^{1}e_{(l+1)(jrightarrow 1)+k}\iota+$$\lambda e_{(:-1)(l+1)^{t-1}+j}$

$=$

$k=1$

$(1\leq j\leq(l+1)^{t-1}-1)$

(16)

(17)

$\lambda e:(l+1)^{*-1}$$=$$\sum_{k=1}^{l}e_{l(l+1)^{t-1}+h}$$\sum_{k=1}^{l+1}e_{(l+1)(j-1)+k}$$=$$\lambda e_{l(l+1)^{\ell\sim 1}+j}$$(1\leq j\leq(l+1)^{t-1})$(18)

まず, (16) についてだが, $1\leq j\leq(l+1)^{t-1}-1$ なる任意の整数$p:= \max\{q\backslash . (l+1)^{q}|j\}$ とおく. このとき, (16) の左辺はに対し,を示せばよい.
$j$$\lambda e_{(i-1)(l+1)^{t\sim 1}+j}=\lambda(\lambda-1\}\varphi_{l}^{(\mathrm{p})}$である. (16) の右辺は, $k=l+1$ のとき $(l+1)^{p+1}=(l+1)(j-1)+k=(l+1)j$だから, 定義 22 より,$\sum_{k=1}^{l+1}e_{(l+1)(j-1)+k}$$=$$l(\lambda-1)\varphi_{l}^{(0)}(\lambda)+(\lambda-1)\varphi_{l}^{(p+1)}(\lambda)$$=$$l(\lambda-1)+(\lambda-1)(\lambda\varphi_{l}^{(\mathrm{p})}(\lambda)-l)$$=$$\lambda(\lambda-1)\varphi_{l}^{(\mathrm{p})}(\lambda)$である. したがって (16) は成り立つ.

また, $1\leq i\leq l$ なる任意の整数 H こ対し, (17) の左辺は,$\lambda e_{\dot{\iota}(l+1)^{t-1}}-arrow\lambda(\lambda-1)\varphi_{l}^{(t-1)}(\lambda)$

であり, (17) の右辺は (16) と同様の論法により$\sum_{k=1}^{l}e_{l(\mathit{1}+1)^{l-1}+k}$$=$$l(\lambda-1)\varphi_{l}^{(0)}(\lambda)$$=$$l(\lambda-1)$である. ここで, 定義 22 より,$\lambda(\lambda-1)\varphi_{l}^{(t-1)}(\lambda)-l(\lambda-1)$

である.

$\varphi_{l}^{(t)}(\lambda_{l}^{(t)})=0$$=$$(\lambda-1)(\lambda\varphi_{l}^{(t-1)}(\lambda)-l)$$=$$(\lambda-1)\varphi_{l}^{(t)}(\lambda)$

より, (17) は成り立つ.

最後に, (18) を示す. $j=(l+1)^{t-1}$ のとき, $k=l+1$ ならば $(l+1)(j-$$1)+k=(l+1)((l+1)^{t-1}-1)+(l+1)=(l+1)^{t}$ だから, (18) の左辺は,$\sum_{k=1}^{l+1}e_{\langle l+1)((l+1)^{t-1}\sim 1)+k}$

$=$

$=$

$l(\lambda-1)\varphi_{l}^{(0)}(\lambda)+l$$l\lambda$

78である. また,$\lambda e_{l(l+1)^{t-1}+(l+1)^{*-1}}$$=$$\lambda e_{(l+1)^{2}}$$=$$l\lambda$$=$$\sum_{k=1}^{l+1}e_{(l+1)((l+1)^{*-1}-1)+k}$である. 一方, $1\leq i\leq l$ なる任意の整数

任意の整数

$j$

$i$

と $1\leq j\leq\langle l+1)^{t-1}-1$ なるに対し, $p:= \max\{q : (l+1)^{q}lj\}$ とおけば, $e_{(:-1)(l+1)^{t-1}+j}=$$(\lambda-1)\varphi_{l}^{(p)}(\lambda)=e_{l(l+1)^{t-1}+j}$であるがら, (16) より (18) は成り立っ. (命題6 の証明おわり)
事実 2.4 とあわせることにより次が導かれる.
補題 7A 仏 ) の \lambda l(りに属する固有ベクトルで各成分が正のものがある.
$t$

定理 3 が, 上と命題 4 とから直ちに導がれる.

なお, 参考のために, 以下が成立することを指摘する.
補題 8$l\underline{-}1,2,3,$$\ldots,$$t=2,3,4,$$\ldots$

に対し, 接続行列$A^{(l,t)}$の特性方程式は$\det(xI-A^{(l,t)})=x^{(l+1)^{t}-\iota-1}(x-1)\varphi_{l}^{(t)}(x)=0$である.