数理解析研究所講究録1020 巻 1997 年 127-142

127

戸田分子の超離散極限とソーティング
東京大学数理科学研究科 永井敦 (Atsushi Nagai)1

1

はじめに近年, 独立変数のみならず従属変数も離散化 (超離散化) したソリトン系 $[1, 2]$ が, 離散型ソリトン方程式に対して「超離散極限」 (ultra-discrete limit) と呼ばれる極限操作をほどこすことによって得られることが指摘された $[3, 4]$ . この極限操作は 2 次元版や [5],不等間隔差分版 [6] などさまざまなソリトン方程式に対して行われてきた.

ソリトン方程式はソリトン解の他, 準周期解, 分子解, 有理解など豊富な種類の解を有することもよく知られた事実である. ここでは離散系に特有の分子解に着目し, その超離散極限および応用について述べる. 分子解は有限非周期の戸田方程式 $(\text{戸田分子方程}$.

式) においてはじめて議論され [7], 工学の分野でさまざまな関連や応用が指摘されている[8, 9, 10, 11].
この論文の構或は以下の通りである.

2 戸田分子方程式とその超離散化

3 超離散型戸田分子方程式の保存量
4 超離散型戸田分子方程式を用いたソーティング
5 結論

A 数値実験結果
1$\mathrm{e}$-mail: slime@poisson.c.u-tokyo.ac.jp

128

戸田分子方程式とその超離散化

2

時間を離散化した戸田分子方程式 [8]$\{$$I_{n}^{t+1}-fl_{n}$$=$$V_{n}^{t}-V_{n}^{t+1}-1$$(1 \leq n\leq \mathit{1}\mathrm{V}))$$I_{n}^{t+1}V_{n}^{t}+1$$=$

蹴+lVnt$(1 \leq n\leq N-1)$ ,(1).

(2)$V_{0}^{t}=V_{N}^{t}=0$,

は従属変数変換$I_{n}^{t}= \frac{\tau^{t}\tau^{t}n-1n+1}{\tau_{nrl^{+}}^{t_{\mathcal{T}^{t}}}-11},$$V_{n}^{t}= \frac{7^{-t+}n+1-\tau_{n}1t1}{\tau_{n}^{t}\tau_{n}t+1}$

によって, 以下の双線形形式と等価になる.
$\tau_{n}^{t+1}\mathcal{T}^{t-1}n=(\tau_{n}^{t})^{2}+T_{n+1}^{t_{-}}\tau 11n-t+1$$(\tau_{-1}^{t}=.

\tau_{\wedge 1}^{t}r_{+}=0)$(3).

方程式 (3) は次の特解を有する [8].

ここで,$c_{i},$$p_{i}(i=1,2, \cdots, N)$はパラメータであり, 特に, 各(4).

$\tau_{n}^{t}=1\leq i_{1}<\cdots in\sum_{<\leq N}\{_{1\leq k<\leq}\prod_{nl}(pi_{k}-p_{i\iota})^{2},.\cdot\prod_{=1}^{n}Ci\gamma p_{\mathrm{i}_{J}}^{t}\}$は固有値に対応し, -般性$p_{i}$を失うことなく不等式$p_{1}>p_{2}>\cdots>p_{N}$を満たす.

次に戸田分子方程式の超離散版を構成する. 従属変数

$Q_{n}^{t,\epsilon}$,,‘,$E_{n}^{t}$$\rho_{n}^{t.\epsilon}$を以下の式で定義する.

$Q_{n}^{t,\epsilon}$$=$$\epsilon\log I_{n}^{t}$$E_{n}^{t,\epsilon}$$=$$\epsilon\log V_{n}^{t}$$\rho_{n}^{t,\epsilon}$$=$$\epsilon\log\tau_{n}^{t}$$(I_{n}^{t}=\exp(Qr\iota t,\epsilon/\epsilon))$$(V_{n}^{t}=\exp(E_{n}t,\epsilon/\epsilon))$$(\tau_{n}^{t}=\exp(\rho_{n}^{t,\epsilon}/\epsilon))$$(1 \leq n\leq N)$$(1 \leq n\leq \mathit{1}\mathrm{V}-1)$$(0\leq n\leq N)$.

(5)

,
,

(6)

(7)

129

関係式
$\max(a, b)\equiv a\oplus b$$=$$\epsilonarrow+01\mathrm{i}\ln\epsilon\log(\mathrm{e}^{a}/\epsilon+\mathrm{e}^{b/\epsilon})$

,

(8)

$\{$

$a+b\equiv a\otimes b$$=$$\epsilonarrow+1\mathrm{i}_{\ln_{0}}\epsilon\log(\mathrm{e}^{a}/\epsilon\cross \mathrm{e}^{b/\epsilon})$,に注意すると, 戸田分子方程式 (1) \iota よ\epsilon \rightarrow +0 の極限 (超離散極限, ultra-discrete limit)
で以下の式に–様収束する.

$(1 \leq n\leq N)$$\max(Q_{n’ n-}^{t+1t+1}E)1=\max(Q_{n}t, E_{n}^{t})$$E_{n}^{t+1}+Q_{n}^{t+1}=E_{n}^{t}+Q_{n+1}^{t}$$E_{0}^{\mathrm{r}}=E_{N}t=-\infty$

,

(9)
(10)

$(1 \leq n\leq N-1)$ ,.

(11)

また双線形形式 (3) の超離散極限から以下の式を得る.

$\rho_{n}^{t+1}+\rho_{n}^{t-1}=.\max(.2.\rho_{n}^{t},’\rho^{t-1}n+!.+\rho_{n-1}^{t+1}.\cdot)$$\rho_{-1}^{t}=\rho_{N+1}^{t}=-\infty$

ただし,$\rho_{n}^{t}$$\epsilonarrow+^{0^{Q1}0arrow}1\mathrm{i}\ln n’ n^{:}t,\epsilon\epsilonarrow \mathrm{i}\ln+E^{t\epsilon},1\mathrm{i}\epsilon$$(.0\leq n\leq..N)$

,

(12)
(13)

,

我\rho 鉦をそれぞれ,$Q_{n}^{t},$$E_{n}^{t},$$\rho_{n}^{t}$

とおいた. 従属変数$(Q_{n}^{t}, E_{n}^{t})$とは以下の関係式で結ばれる.

$Q_{n}^{t}$$E_{n}^{t}$$=$$\rho_{n-1^{+-}}^{tt}\rho_{n}+1-tn+1\rho^{t}n\rho-1$$=$$\rho_{n+1}^{t}+\rho^{t+1}n-1-\rho_{n}^{tt}-\rho_{n}+1$

’

(14)

.

(15)

方程式 (9) $-(11)$ または (12), (13) を超離散型戸田分子方程式 [12] と呼ぶ.

超離散型戸田分子方程式の厳密解も (4) 式に対する同様な極限操作で求めることができる. パラメータ$c_{i},p_{i}$は正であると仮定し, 新しいパラメータ$ci=\mathrm{e}^{C_{i}/\epsilon}$,$p_{i}=\mathrm{e}^{P_{t}/\epsilon}$$C_{i},$$P_{i}$

を(16)

130で定義する. 戸田分子方程式の厳密解 (4) に対する$\epsilonarrow+0$の極限で, 以下の解を得る.

(17)$\rho_{n}^{t}$$= \lim_{\epsilonarrow+0}\epsilon\log_{\mathcal{T}}n^{l}$$= \bigoplus_{i_{1}<\cdots<i_{n}}(_{k=1}\otimes^{n}2(n-k)P_{i}k+C_{i_{k}}+tP_{i_{k}})$$= \dot{\iota}_{1}<\cdots<i_{n}\mathrm{m}\mathrm{a}\mathrm{x}(_{k=1}\sum^{n}2(n-k)P_{i}k+C_{i_{k}}+tP_{i_{k}})$(18)

ここでパラメータ君は不等式,$P_{1}>P_{2}>\cdots>PN$ .

を満たす. 以後演算子\oplus と3$\otimes$(19)

は lnax と +(plus) を表すものとする.

超離散型戸田分子方程式の保存量
はじめに独立変数のみ離散化した戸田分子方程式の保存量 [8] について述べる. 方程式 (1) は次の Lax 形式で書かれる.

$L^{t+1}Rt+1=R^{t_{L^{t}}}$

ただし$L^{t},$$R^{t}$,(20)は以下で定義される $N\cross N$ 行列とする.

.

$L^{t}=$$001^{\cdot}..\cdot.$’$- R^{t}=$ .

(21)

131

このとき行列$X^{t}$

を$X^{t}=L^{t_{R^{t}}}=$,(22)で定義すると保存量は次式で与えられる.

$C_{k}=\mathrm{T}\Gamma[(Xt)^{k}]$(23)$(k=1,2, \cdots \mathit{1}\mathrm{V})2^{\cdot}$

次に上の結果を用いて超離散戸田分子方程式 (9) $-(11)$ の保存量を計算する. (23) 式に対して直接超離散極限をとると, 意味のある保存量は 1 つしか得られない $(C_{k}(k=$2, 3, . . , $N$ ) の超離散極限は$\cdot$$C_{1}$の超離散極限の$k$倍) が, これは${\rm Max}$-Plus 代数の世界で「既約な行列の固有値は 1 つしかない」 という事実に対応していると考えられる. 直接極限をとる代わりに, 保存量$C_{k}=\mathrm{T}\mathrm{r}[(X^{t_{)^{k}]}}$の次の組合せを考える.

,$|C_{N}’C_{m}’CC_{2}’C_{1}3’,=====.\cdot.\cdot.\cdot P_{N}P_{m}\mathrm{T}[(\mathrm{T}\mathrm{r}_{\mathrm{T}}[X^{t}’])2\mathrm{T}_{1}\cdot[.(Xt)^{2},].]./.2[(\dot{\mathrm{T}}1^{\backslash }\mathrm{r}[X^{l}](\mathrm{T}(\mathrm{r}[[X^{t_{])^{3^{-}}}}\mathrm{r}[X^{t}],\mathrm{T}Xt_{],\mathrm{r}}-3\mathrm{T}[(\mathrm{r}[\mathrm{T}_{1[]}(X^{t})^{2}]Xt)X^{t}2],.\cdot\cdot)\mathrm{T}1^{\backslash }[(X)’,’ t_{)^{2}}]+2\mathrm{T}\mathrm{r}[(Xt)^{3}]]/6$

(24)

132

ただし$P_{j}$$(x_{1} , x_{2}, \cdots)$

は Schur 多項式$\exp[-\sum_{j=\iota}^{\infty}\frac{x_{j}s^{j}}{j}]=1+\sum_{1j=}^{\mathrm{c}}(-\backslash 01)jP_{j(}X1,$ $X2,$である. 保存量$C_{i}’$( $i=1,2,$$\cdots$$\cdots)s^{j}$

(25)

.

, 1V) に対して超離散極限を考えることにより, 以下の独立な保存量 $uC_{i}(i=1,2, \cdots, N)$ を得る.
$N$

$uC_{1}$$=$$k_{1}=1^{\cdot}$$uC_{2}$$=$$uC_{3}$

$=$

$N-1$

$\oplus Q_{k_{1}}^{i}\oplus\oplus E_{l_{1}}^{t}$

(26)

,

$l_{1}=1$$(_{k_{1}} \bigoplus_{<k_{2}}^{N}Q_{k_{1}}^{l}\otimes Q_{k_{\vee}}^{t}9)\oplus(l_{1}\bigoplus_{k_{1}\not\in\{.\}}Nl_{1}+1lN-11\bigoplus_{=}^{1}Q_{k_{1}}^{t}\otimes E_{l_{1}}^{t})\oplus(^{N}\bigoplus_{l_{1}<^{\iota}2}^{-1}E_{l1}^{t}\otimes-E_{l_{2}}^{t})$, (27)$(< \bigoplus_{k_{1}k_{2}<k_{\backslash }\mathrm{q}}NQtk_{1}\otimes-Q_{k_{2}}^{t}\overline{\otimes}Q_{k}^{t}\circ.)\oplus(_{\{k_{1},k_{2}\}\cap}k_{1\{}<k9\iota_{1}=Q_{k_{1}}\oplus\bigoplus_{1}^{1}\wedge\iota,l1^{\wedge}1^{+1\}=}’\phi\Lambda\gamma-t\otimes Q_{k_{2}}^{t}\otimes E_{l_{1}}^{t})$$\oplus(_{k_{1}\not\in\{,1\}}\iota_{1}\iota 1+1\oplus,\oplus l\mathrm{A}^{r}l_{2},2+l1N<l-12Q_{k_{1}}^{t}\bigotimes_{-}E_{l_{1}}^{t}\otimes E_{l\underline{\circ}}^{t})\oplus(_{\iota_{1}}<l_{2}<l_{1}\Lambda\gamma-\bigoplus_{l_{3}}^{1}Ei\otimes E_{l_{2}}^{t}\otimes E_{l_{3}}^{t}),(28)$.

$uC_{m}$$=$$uC_{N}$$=$$0_{i\mp^{i}j^{j}}<, \bigoplus_{m}=\leq_{m}$ ,$Q_{1}^{t} \bigotimes_{-}Qt2\otimes\cdots\otimes QtN$(30).

注 3.1 $uC_{m}$ の式 (29) の見方について説明する. 従属変数 Qtl’(29)$Q_{2}^{t},$$\cdots,$$Q_{N}^{t},$$E^{t}1’ 2Et,$ $\cdots,$$EtN-1$

を$Q_{1}^{t},$$E_{1}^{t},$$Q_{2}^{t},$$Q_{\mathit{1}}tE^{t}\cdot.tE_{N-1}\backslash \mathrm{r}-1’ t,$ $Qt$
$EtQ_{3}2$$3’\cdot,$”,(31)のように並べる. そして) 隣り合う 2 つを選ばないように $m$ 個の従属変数を選び和をとる.

その和の, 上記の選び方全体についての最大値か $uC_{m}$ である.

133

最後に,$uC_{1}$が保存量であることを証明する. (9) に対し $n=1,2,$$\cdots,$にわたって lnax

$N$をとると, 以下の式を得る.
.

$Q_{1}^{t+}1\oplus Et+1\oplus 0Q^{t+t}2\oplus E1\oplus\cdots\oplus Q_{N}^{i}1+1+1\oplus E_{N1}l+1=-Q^{l}1\oplus E_{1}^{t}\oplus Q_{2}tE_{2^{\oplus}}i\oplus\oplus\cdots Q_{N^{\oplus}}tEtN$

境界条件 (11) から, 関係式(32)$\oplus Q_{k^{+1}}^{t}\oplus\oplus Et+1\oplus NN-1.N\iota=Qtk\oplus\oplus EN-1\iota^{t}$’を得, したがって$uC_{1}$は時刻$k=1$$l=1$

$k=1$

$t$

$l=1$によらない. 同様にして $uC2,$ $uC3,$ことを証明できるが, このことは (5), (6) で定義される$Q_{n}^{t,\epsilon},$:$E_{n}^{t\epsilon}$$\cdots,$$uCN$ も$t$によらないが\epsilon \rightarrow +O の極限で$Q_{n}^{t},$$E_{n}^{t}$に–様有界収束することからも示される.

4

超離散型戸田分子方程式を用いたソーティング
この節では, 超離散型戸田分子方程式の時間発展について述べ, さらに方程式を用いたソー$\overline{\mathcal{T}}\text{ィ\sqrt[\backslash ]{}ff^{\triangleright}$ァルゴリズムを定式化する.

$Q_{n}^{t+1}$は方程式 (9) から –意に定まらないため,ここでは双線形形式で書かれた超離散戸田分子方程式 (12),(13) を用いる.

はじめに初期値を以下のように選んだときの\rho nt の時間発展 (方程式 (12) は正負両方向に時間発展することに注意) を表 1 に記述する.

$\rho_{n}^{0}=\{-22,16,3, -15,12\},$

さらに, 関係式 (14),(15) を用いて従属変数わかるように, $tarrow\pm\infty$ の極限で

$E_{n}^{t}\#\mathrm{h}\oplus$$\rho_{n}^{1}=\{-2, -8, -24,24, -6\}$$Q_{n}^{t},$$E_{n}^{t}$.

(33)の値も計算することができる. 表 1 からの零元-\infty に収束し,$Q_{n}^{i}$の時間発展はソーティングの性質を有する、 これらの性質は方程式 (12) の解に着目すれば, 明らかである. 式

134(18) #こおいて が十分大きいとき, 不等式 (19) を考慮すると,$t$$\rho_{n}^{t}=\sum 2(n-nk)P_{k}+C_{k}+tP_{k}$(34),$k=1$が成立し, したがって (14), (15) から$Q_{7\iota’ n}^{t}E^{t}$は次式で与えられる.

(.35)

,

$\cdot$$Q_{n}^{t}$$=$$P_{r\iota}$$E_{n}^{t}$$=$$C_{n+1}-C_{n}+i(P_{n+1^{-}}P_{n})$

.

(36)

不等式 (19) から, $Q_{n}^{t}(n=1,2, \cdots, N)$ は $tarrow\infty$ の極限で数の大きい順に並ぶことがわかる.

このことは超離散型戸田分子を用いたソーティングアルゴリズムの存在を示唆している.

以下にそのアルゴリズムを述べる.

$q_{1},$ $q_{2},$$\cdots,$ $q_{N}$を $N$ 個の乱雑な順序に並んだ数として, それらを大きい順にソートする問題を考える. 初期値として$Q_{n}^{0}--q_{n}$と選ぶのは自然であろう. 問題は補助変数$E_{n}^{0}$をどのように選ぶかである. 下手に選ぶと最初の数列と最後にソートされた数列が–致しないこともある. 1 つの解決策として変数$E_{n}^{0}$を次の不等式のうち, 少なくとも 1 つは満たすように選べばよい.

アルゴリズムは次の通り。

$E_{n}^{0}\leq Q_{n}^{0}$

for $1\leq\forall_{n}\leq N-1$ ,(37)$E_{n}^{0}\leq Q_{n+1}^{0}$

for $1\leq\forall_{n}\leq N-1$ .

(38)

135

注 4.1

‘ノ $–$ ティングアルゴリズムを実行する際補助変数$E_{n}^{t}$を(39)$E_{n}^{0}=\mathrm{l}\mathrm{n}\mathrm{i}\mathrm{n}(Q^{00}n’ Q_{n}\dagger 1)$のように選んだ (第 2 段階).

注 4.2 第 3 段階において) 従属変数\rho 00’$\rho_{1’\rho 0}^{01}$は任意に選んでも構わない ($Q_{n}^{t},$$E_{n}^{t}$の時間発展には影響しない).
注 43 第 2 段階における 「不等式

$E_{n}^{0}\leq Q_{n}^{0}$

または$E_{n}^{0}\leq Q_{n+1}^{0}$の少なくともる」 という条件はソーティングが正しく実行される (つまり初期値–方が成立す$\{q_{1}, q_{2}, \cdots , q_{N}\}$と最終的にソート $\text{された数}(\{Q_{n}^{t}\}1\leq n\leq N)_{t}arrow\infty=\{P_{1}, P_{2,N}\ldots, P\}$ が集合として等しくなる) ための十分条件である.

上の注 43 を前節で計算した保存量 (26) $-(30)$ を用いて証明する. 各$uC_{i}$は時間らず–定なので, (26) $-(30)$ の右辺に $t=+\infty$ を $t,=0$ 代入した値は等しい.
$Q_{n}^{t}arrow P_{n},$$E_{n}^{t}arrow-\infty$$t$に依$tarrow\infty$

でとなることおよび不等式 (37) と (38) の少なくとも –方が成立する

136

ことを考慮すると
ガ$uC_{1}$

$=$

(40)

$P_{1}= \oplus Q_{k_{1}}^{0}=_{1\leq k_{1}}\max_{\leq N}qk1$ ’$k_{1}=1$ガ$uC_{2}$$=$$uC_{m}$

$=$

(41)

,

$P_{1}+P_{2}= \bigoplus_{k_{1}<k2}Q_{k_{1}}0\otimes Qk_{2}\max 0-=k1<k2(q_{k_{1^{+}}}q_{k\underline{9}})$$P_{1}+P_{2}+\cdots+P_{m}$ガ$=$$uC_{N}$$=$を得る. 式 (40) から,$k_{1}< \cdots<k\oplus Q_{k_{1^{\otimes}}}0\ldots-\otimes Q^{0}km=mk<\cdots<k_{m}\max_{1}(q_{k_{1^{+}}}\cdots+qk_{m})$$P_{1}+P_{2}+\cdots+P_{\wedge\Gamma}=q1+q_{2}+\cdots+q_{N}$$q_{i}(i=1,2, \cdots, \mathit{1}\mathrm{V})$1, 2, . . , $N$ ) の中で 2 番目に大きい数は$\cdot$と最終結果$P_{2}$の最大値は$P_{1}$(43).に等しく, 式 (41) から, $q_{i}(i=$に等しい. 以下同様にして, 初期数列$(\{Q^{t}n\}_{1\leq n}\leq N\mathrm{I}_{t}arrow\infty=\{P_{1}, P_{2}, \cdots, P_{N}\}$

(42)

,

$\{q_{1}, q_{2}, \cdots, q_{N}\}$は集合として–致する.

超離散戸田分子を用いたソーティングの例 (表 2) からもわかるよう$\square$$\ovalbox{\tt\small REJECT}_{\sim}^{\vee}f’=.39$

でソーティングは完了する. しかしながらこのアルゴリズムは実用面において重大な欠陥を有する. 例えば表 2 において “22” と “42” ( $t=19,$$\cdots,$$30$

における$Q_{2}^{t}$と$Q_{3}^{t},$) が入れ替わるのにかなりの時間ステップを要している. これは (直感的にいうと) 補助変数において非常に小さくなっているために, 式 (9) において, $Q_{2}^{t+1}=$$Q_{2}^{t}$$E_{2}^{t}$が $t=19$となってしまうからである. この欠点を回避するため, アルゴリズムを次のように修正する.

137

主な修止点は第 4,5 戎|階である.

もし時表り $t=S-\perp$ 刀\supset b $t=S$ に$\overline{h}$い$-(_{\sim},$$(d_{n}^{t}(n=$1, 2, . . , $N$ ) が変化しない, つまり$\cdot$$Q_{n}^{s}=QSn-1$

が成立すれば,$Q_{n}^{0}$と$E_{n}^{0}$の値を$Q_{n}^{s}$$(^{-}1\leq n\leq \mathit{1}\mathrm{V}\forall)$,(44)と 1nin $(Q_{n}^{s}, Q^{s}n+1)$ に置き直し, 改めて超離散戸田分子を適用する. 数値実験例 (表 3) からもわかる通り, 超離散戸田分子を直接適用するよりも少ない時間ステップでソートが完了する.

$E_{n}^{0}$をこのようにカサ上げするのは, ソリトンセル

オートマトンで離れた距離にあるためなかなか追い抜けない 2 つのソリトンの間隔を狭めることに対応している.

138

注 44 第 2 段階において$E_{n}^{0}$( $\uparrow=1,2,$$\cdots$, 1V-1) は不等式 (37) $i(.38)$ の少なくとも –方を満たしていれば, どのように選んでもよい.
注 4.5 ソートが完了したかどうかを (戸田分子など可積分系の理論を用いて) チェックする機能は今のところできていない.
注 46 式 (44) が成立するという仮定のもとで, 従属変数$\{Q_{n}^{s}\}_{n=}1,\cdots,N$も最終的な数の集合$\{P_{1}, P_{2}, \cdots , P_{N}\}$$Q_{n}^{0}$$’ E_{n}^{0}$.

をリセットしたが, 集合に等しいという保証はない. この節の残りの部分で, これらの集合が等しいことを示す.

はじめに次の不等式を$n$に関する帰納法によって証明する.

$E_{n}^{s-1}\leq Q_{n}^{s-1}$$(1 \leq n\forall\leq \mathit{1}\mathrm{V}-1)$

(45)

,

式 (9) で $n=1,$ $t=s-1$ を代入して, $n=1$ の場合は証明できる.

$Q_{1}^{s}$$=$$\max(Q_{1^{-1}’ 1}^{S}E^{s}-1)$(fronn eq.(11)),$Q_{1}^{s-1}$$=$$\max(Q_{1}^{S-1}, E")$(from

$E_{1}^{s-1}$$\leq$$Q_{1}^{s-1}$$\mathrm{e}\mathrm{q}.(44)$),

(46)

.

次に仮定
$E_{k}^{s-1}\leq Q_{k}^{S-}1$(47),のもと, $n=k+1$ でも (45) が正しいことを示す. 式 (10) から$E_{k}^{s}$$=$$Q_{k}^{S-1}+1^{-}(Q^{s}k^{-}E_{k^{-1}}s)$$=$$Q_{k+1}^{s-1}-(Q_{k}^{s-1}-E_{k}^{s-1})\leq Q_{k+1}^{s-1}$(from$\mathrm{e}\mathrm{c}_{1}\mathrm{s}.(44),$(47)).

(48)

139

を得, これと (44) を用いると, 式 (9) は次のように書き直される.

1nax $(Q_{k}^{S-1}+1’ E^{s}-1)k+1=Q^{s_{\dagger}}k-11$ ’

したがって不等式 (45) は $n=k+1$ でも成立し,された.

この不等式と注 43 から, 集合

い換えれば集合

5$\{Q_{n}^{0}\}_{n=}1,\cdots.N$(49)$1\leq\forall_{n}\leq N$について成立することが示$\{Q_{n}^{s-}1(=Q_{n}^{s})\}n=1.\cdots,N$

は集合 $\{P_{1;}P_{2}, \cdots, P_{N}\}$ , 言に等しいことが示さ$\hslash_{\vee}$

た.

$\square$結論
戸田分子方程式の超離散化を行い, その特解および保存量を求めた. ソリトン方程式$-$の代数解析において重要な役割を果たす Schur 多項式が, 保存量の構成において現われたことは興味深い. ソリトン方程式の超離散極限において, ソリトン解のみが生き残る [1]ことからもわかるように, 超離散化された系はもとの系の本質的な部分のみを抽出していることが考えられる. 戸田分子方程式の超離散極限については, もとの系からソーティングの性質を遺伝している. この事実を用いてソーティングアルゴリズムを構成したが,ソーティングの際, 補助変数

$E_{\uparrow l}^{t}$が重要な役割を果たしている. アルゴリズムの改良 (このままではバブルソート以下) および計算量の評価は今後の課題としたい. また, 可積分な方程式の有するその他の豊富なクラスの解は超離散極限でどういつだ解に収束するのか調べるのも興味深い問題である.

140

A

数値実験結果超離散戸田分子方程式 (12),(13) の時間発展および$Q_{n}^{t}$と$E_{n}^{t}$の時間発展を表 1 に, 超離散戸田分子によるソーティングアルゴリズムおよび修正版の数値実験結果を表 2,3 に記述する.

表 1: 初期値 (33) から始めた超離散型戸田分子方程式の時間発展

141

表 2: 超離散型戸田分子方程式を用いたソーティングアルゴリズム

142

表 3: 超離散型戸田分子方程式を用いたソーティングアルゴリズム (修正版)