イヤンホホに意味のある量を

ㅤ

$n$-一般化イヤンホホ化操作

こちらの記事： 文字列のイヤンホホ化 (不見) による呼び方にはないイヤンホホ化操作をこの記事では考えます。先にこちらの記事を見ることをお勧めします。

この記事では$2$-GIRのみを考えることにするため、以降GIRという場合は$2$-GIRを指すものとします。
これは任意の2文字以上の文字列$S$に対して無限に操作を繰り返せるので、停止しないです。
というかこれについては 数学デー において少し研究されていて、
任意の文字列$S$と$T$に対して、$S$にGIRを繰り返し行うことで$T$に変換できるかどうかの必要十分条件が判明しています。
1文字からなる文字列にはGIRは適用できないです。
かつ2文字以上の文字列にGIRを適用しても1文字にはできないので、$S$または$T$が1文字ならば$S=T$でない限り変換できないです。
$S,T$の両方が2文字以上ならば、$S$に含まれる文字全体の集合と$T$に含まれる文字全体の集合が等しい場合、かつその場合に限りGIRを繰り返すことで$S$から$T$へ変換できるっぽいです。

ㅤ

意味のある値

ここで、GIRという操作に対してあまり変化しない、意味のある値を考えていきたいです。
不変量、つまり常に一定の値をとるものはここではあまり意味がないです。なぜなら上記のように任意の文字列$S$と$T$について、$S$にGIRを繰り返すことで$T$に変換できるかどうかの必要十分条件がすでに分かっているからです。この条件から考えるに、$S$に含まれる文字全体の集合$\text{Set}(S)$がいい不変量になることが分かります。
しかしこの記事では主に"0"と"1"からなる文字列でかつ、"0"のみまたは"1"のみの文字列を除いたものを対象としているので、常に$\text{Set}(S)=\{\text{"0"},\text{"1"}\}$となります。よってこの不変量についてはあまり深追いしません。

これ以外の不変量はおそらくありません。なぜならば、$\text{Set}(S)$さえ変わらなければ任意の文字列に移れるからです。
よって、ここからは不変量のような常に変化しないものではなく、変化はするもののそこまで大きく動かない値を探していきます。

この先の議論では文字列と言えば"0"と"1"のみからなる文字列とします。

ㅤ

案1

"0","1"の2種類の文字のみからなる文字列$S$に対し、$S[i]$で$i$文字目の文字を表すものとします。

これは値が変わりやすすぎる
\begin{eqnarray} ・&&& f(00000010) &&= -5 \\ ・&&& f(000000011) &&= -14 \end{eqnarray}

ㅤ

案2

$S$を同じ文字の連続ごとに圧縮して以下のように表現します。(ランレングス圧縮というらしい)
\begin{eqnarray} S = X_1^{n_1}X_2^{n_2}X_3^{n_3}X_4^{n_4}\cdots X_k^{n_k} \end{eqnarray}
ただし$X_i$は"0"または"1"で、$k$は正の整数
$0^a$は"0"を$a$個続けるという意味。$1^4$は$1111$と同じ

例えば、
\begin{eqnarray} 0110000110001111 = 0^11^20^41^20^31^4 \end{eqnarray}
です
文字が何個連続しているか書いている感じです。

例えば、
\begin{eqnarray} 0110000110001111 = 0^11^20^41^20^31^4 \end{eqnarray}
なので、
\begin{eqnarray} \Phi_\text{diff}(0110000110001111) &=& \Phi_\text{diff}(0^11^20^41^20^31^4) \\&=& 1\cdot1+2\cdot(-1)+4\cdot1+2\cdot(-1)+3\cdot(1)+4\cdot(-1) \\&=& 1-2+4-2+3-4 \\&=&0 \end{eqnarray}

ここで気づいたのは、これは次と等価です。

こちらを定義とした方がよさそう

ㅤ

考えたかったこと

実は、元々上の$\Phi_\text{diff}$という関数は以下のように定義しようとしていたのです。

これを少し変形したのが上記の定義2でした。
(和を取る範囲を$k$から$k-1$へ変えると元々の定義しようとしていた値に一致する)

また、もう一つ意味のある値として文字列の長さが存在します。$|S|$と書くことにします。
しかし、$S$に現れる"0"の個数を$|S|_0$とし、"1"の個数を$|S|_1$とすると、$|S|=|S|_0+|S|_1$ですから、結局は$|S|_0$と$|S|_1$の和と差を持っているだけになります。

じゃぁ和と差を持つのではなく$|S|_0,|S|_1$をそれぞれ持っていれば良いのではと考えてしまいますが、実は和と差にしておく方がいいかもしれません。
なぜなら、$|S|_0,|S|_1$を個別に持っておくと、GIRをした時に片方の値は変わりません。しかし、和や差は毎回のGIRによって$+1$または$-1$されます。
まぁ後付けの理由ですが。
どちらがいいのかというのは使ってみて実感すればいいのです。

ㅤ

案3

他にはないでしょうか？さっきのランレングス圧縮というのは面白そうです。

この時、次のことが言えます。

ㅤ

最小ステップ数の評価

下界

この定理によって、$\Phi_0$や$\Phi_1$自体を見る意味はほぼなくなりました。(泣く)

ㅤ
ㅤ

この定理は次のように証明できます(離散空間のリプシッツ条件？というらしいがよく知らない)

ㅤ

ㅤ

あぁそれと、$\Phi$関連の言葉をまとめておきましょう

こうすると、さっきの定理5を拡張できます。

これはさっきの定理5の証明とほぼ同じようにできます。

この定理6より、次のことがすぐに言えます。

他にも下界に関していろいろとポテンシャルを考えてみましたが、なかなかいいものはありませんでした。

• $\Phi_\text{LCS}$:最長共通部分列 (LCS: Longest Common Subsequence
• $\Phi_\text{sqLCS}$:文字列を一度すべて圧縮（"00" $\to$ "0" などのスクイーズ）した状態でのLCSを計算
• $\Phi_\text{RLE\_add}$:$\Phi_\text{sqLCS}$ + ("0"を何文字圧縮したか) + ("1"を何文字圧縮したか)
• $\Phi_\text{RLE\_sub}$:$\Phi_\text{sqLCS}$ - ("0"を何文字圧縮したか) - ("1"を何文字圧縮したか)

$\Phi_\text{RLE\_sub}$の面白い特徴として、一度のGIRに対して必ず$+1$か$-1$されるという点があります。(理由は知らない)
ただほとんどが使い物にならない(それほど値が変わらない or リプシッツ定数が$3$など大きい)です。
それと、上記の使い物にならない物にかかわらず、どのポテンシャルも"01"$\to$"10"がだいたい$1$か$0$になってしまいました。まぁ仕方がないですね。

上界

下界は自明な下界として$1$があるのでさほど距離が遠くない文字列同士ならそれでも十分ですが、自明な上界は存在しないです。("01"$\to$"10"が自明でないから)
ということで上界を考えるほうが実は有意義だったりするかもしれません。考えてみましょう。

"01"$\to$"10"が可能であるという事実を使ってもいいですが、もうちょっと賢く行きたいですね。

よくある手法としては、今回は可逆な操作が可能なので基準形という形を設定し、文字列$S,T$から基準形までの距離を上から抑える方法があげられます。

問題は、基準形を何に取るかです。いい基準形を探さないといけません。
最初に考え付いたのは"00...011...1"もしくは"11...100...0"です。これは文字列にある"1"か"0"を全部左側に持っていけばいいので、必ず到達することが分かります。
じゃぁ基準形は"00...011...1"に

$1100100100110$なら、このようにできます。

GIRは、その変換方法から文字を左側に寄せるほうが簡単です。(赤を左に寄せようとする上図)
この図は イヤンホホパズル 可視化 という私のサイトで可視化することができます。

右側に寄せようとすると、思ったより手数がかかります。(青を右に寄せようとする上図)

では、計算してみましょうか、
書き換え規則は
\begin{eqnarray} 00 \to 000 \\ 11 \to 111 \\ 01 \to 100 \\ 10 \to 011 \\ 000 \to 00 \\ 111 \to 11 \\ 100 \to 01 \\ 011 \to 10 \end{eqnarray}
で全てですから、これをどこに適用するかだけ考えればいいです。
\begin{eqnarray} 000 \to 00 \\ 111 \to 11 \end{eqnarray}
これに関しては単純な収縮ですね。同じ文字が連続した文字列を最小で2文字まで小さくすることができます。
逆に、
\begin{eqnarray} 00 \to 000 \\ 11 \to 111 \end{eqnarray}
はぱっと見使い道が分かりません。しかし、こういう時に使えます。
\begin{eqnarray} &&1100 \\ &&11000 \\ &&110000 \\ &&10100 \\ &&1001 \\ &&011 \\ \end{eqnarray}
なるほど、"0"の個数を意図的に増やすことで$100\to01$をたくさん生み出しているんですね。
しかしまぁ、単純に"0"を左に動かそうと言う思いだけならどうなるでしょうか？
\begin{eqnarray} &&1100 \\ &&101 \\ &&0111 \\ \end{eqnarray}
となり、結果的にはあまり意味がないことが分かります。使わないでいいでしょう。
残りは
\begin{eqnarray} 01\to100\\ 10\to011\\ 100\to01\\ 011\to10 \end{eqnarray}
ですが、まぁ"0"と"1"のどちらを左側に寄せたいかで使うべき手が変わってきますよね。

• "0"を左に寄せたい場合: $10\to011$ or $100\to01$
• "1"を左に寄せたい場合: $01\to100$ or $011\to10$
  ということは、左に寄せたい文字が"0"だとしたら、一番右にある"0"について、
  $\,\,\,\cdots1\textbf{0}$となっていれば、$10\to011$を、
  $\cdots10\textbf{0}$となっていれば、$100\to01$を使えばいいということですね。
  この規則に従ってみたいところですが、如何せん複雑です。

とりあえずまぁ、これによって左側に"0"を、右側に"1"を寄せることができます。
一番右にある"0"について、かならずステップ(2)で左に1つずれることができるため、文字列$S$に対してこのアルゴリズムで基本形になるまでにかかる最長ステップ数は$|S|$です。

あとは、基本形同士の移り変わりにおけるステップ数の評価ですね。
そのために正規化されたときの
正規化アルゴリズムの(2)の i. では、文字列が伸びています。
しかし、"1"は三文字以上連続している時には二文字にまで縮まるので、
(1)や(3)を毎回適用していることから、(2)をする直前では"1"は最大でも二文字しか連続しません。
よって、最初から考えると i. は二回までしか連続して行えず、その後は必ず ii. または iii. が必ず行われます。

iii. を繰り返したのちには必ず ii. に到達します。
これが重要で、ii. の時の文字列は
(あ) $S0100S'$
または
(い) $S1100S'$の二通りに分けられます。($S'$は"1"が連続した文字列)
それと、(い) $S1100S'$は
(い)-a $S11100S'$
(い)-b $S01100S'$
の二通りが考えられますが、"1"は連続して3つ出てこないので、(い)-b $S01100S'$の場合しかありえません。

(あ) $S0100S'$の場合、
ii. によってこれは$S001S'$となり、
これは ii. または iii. に戻されます。

(い)-b $S01100S'$の場合
ii. によってこれは$S0101S'$となり、これは i. に移ります。
i. によって$S00111S'$となり、これは ii. または iii. に移ります。

ここで大事なのは
最初だけ i. は二度連続することがある。
その後、iii. が何度か行われ必ず ii. に移る。
ii. の後、ii. か iii. に移る　もしくは i. を一度だけ経由してから ii. に移る
ということです。
分かりにくいですよね？図にしてみました
\begin{xy} \xymatrix{ \text{i.} \ar[d] \\ \text{i.} \ar[r] & \text{iii.} \ar@(ur,ul)[] \ar[r] & \text{ii.} \ar[d] \ar[dl] \ar[dr] \\ & \text{iii.} & \text{ii.} & \text{i.} \ar[d] \ar[dl] \\ & & \text{ii.} & \text{iii.} }\end{xy}

図にはなりましたが、これでは同じ状態がいろんなところに登場しています。
もうちょっとまとめてみるとこうなります。
\begin{xy}\xymatrix{ & & \text{ii.} \ar@(ur,ul)[] \ar@/_/[dl] \ar@/_/[dr] \\ \text{i.} \ar[r] & \text{i.} \ar@/_/[ur] \ar@/_/[rr] & & \text{iii.} \ar@(dr,ur)[] \ar@/_/[ul] }\end{xy}

きれい。
...それが大事なのではなく、大事なのは i. に自己ループ(自分に帰ってきているループ)が無いということです。
ということは、i. によって文字列全体の長さが増えた後は、必ず ii. か iii. で全体の長さが縮みます。
i. は最大でも連続して2回しか起きないので、文字列全体の長さは最終的に3文字以上は増えないと分かります

この定理から考えると、文字列$S,T$を各々正規化した後には、$|S|+|T|-4$ステップがかかり、
$S$は$2\sim|S|+2$文字、$T$は$2\sim|T|+2$文字になっています。
また、$01\leftrightarrow 011$や$01\leftrightarrow001$や$01\leftrightarrow0011$や$001\leftrightarrow011$は以下のようにして可能です。
\begin{eqnarray} &[0]&01 \\ &[1]&100 \\ &[2]&1000 \\ &[3]&10000 \\ &[4]&0100 \\ &[5]&001 \\ \\ &[0]&01 \\ &[1]&100 \\ &[2]&0110 \\ &[3]&10010 \\ &[4]&100011 \\ &[5]&10011 \\ &[6]&0111 \\ &[7]&011 \\ \\ &[0]&01 \\ &[1]&100 \\ &[2]&1000 \\ &[3]&010 \\ &[4]&0011 \\ \\ &[0]&001 \\ &[1]&0100 \\ &[2]&10000 \\ &[3]&011000 \\ &[4]&01100 \\ &[5]&100100 \\ &[6]&10001 \\ &[7]&1001 \\ &[8]&011 \\ \end{eqnarray}

よって、正規化後の$S$と正規化後の$T$を双方$01,001,011,0011$のいずれかに移すのに最大$|S|+|T|+4$文字、そして最大でも8手でいずれからいずれへも変換可能ですから、
合計で$|S|+|T|-4+|S|+|T|+4+7 = 2(|S|+|T|)+8$手で移れるということになります。

上界の改善

基本形の変更

ちょい多いと思います。まぁ$001\leftrightarrow110$が12手かかります。

これが最小手数なので、$2(|S|+|T|)+8 = 2(3+3)+8=20$ですから、ましな評価なのかもしれません。
本当にそうでしょうか。
$d(000000000000001,111111111111110)=36$です。
しかし$2(15+15)+8 = 68$です。おおい...
さすがに$|S|+|T|+(\text{定数})$ぐらいに抑えたいところです。

基本形を変えてみませんか？
新たな正規化アルゴリズムを考えてみました
今度は単純です

単純ですね。遷移も$\begin{xy}\xymatrix{\text{(1)}\ar@(ur,ul)[]}\end{xy} $ですから単純です。
しかし結果はどうなるのでしょうか？

まず、3文字以上同じ文字が連続することがありません。($000\to00,\;\;111\to11$による)
そして、同じ文字が2文字連続する、"00","11"があるのは一番左にある時だけです。
なぜなら、一番左に"00","11"がないなら、この左に逆の文字があるはずです。($\cdots100,\;\;\cdots011$のどちらか)
しかしこの状況はどちらも(1)が適用できてしまいます。($\cdots100\to\cdots01,\;\;\;\cdots011\to\cdots10$)
よって(1)が適用できない状態になれば、一番左以外には2文字連続することはありません。
ということは、実質的に以下のようなパターンに限られます。
\begin{eqnarray} &&001010\cdots01 \\ &&001010\cdots10 \\ &&110101\cdots10 \\ &&110101\cdots01 \\ &&0101\cdots01 \\ &&0101\cdots10 \\ &&1010\cdots10 \\ &&1010\cdots01 \\ \end{eqnarray}
まぁちょい複雑かもしれませんが...とりあえずいいでしょう。

今度はステップ数と正規化が終了したときの文字列の長さがどうなるか考えてみましょう。
といっても、今回すごく単純で、(1)は常に1文字短くするので、ステップ数と文字列の合計が常に一定の値になります。$S$を正規化するとして、ステップ0で文字列の長さが$|S|$なので、合計が$|S|$で一定であることが分かります。

あとは基本形同士の移り変わりです。
けど、いろいろ実験してみるといけそうな気がします。

この図を見るとなんか行けそうな気がしますね。

ㅤ

$\underbrace{0101\cdots0101}_{n\text{ times 01}}100$を$A(n)$型

$\underbrace{0101\cdots0101}_{n\text{ times 01}}1000$を$B(n)$型とします。

まぁ$L=01$とすれば

$L^n100$がA型
$L^n1000$がB型となります。($n$は非負整数)

この、$L=01$は今後たくさん出てくるので覚えておいてください。

$A(n),B(n),L^n$の行き来について考えてみましょう。
$A(n)$型の一番後ろの"00"の部分にGIRを適用して"000"にすると、$B(n)$型になります。
\begin{eqnarray} A(n) &=& L^n100 \\&\overset{\text{GIR}}{\longleftrightarrow}& L^n1000 \\&=& B(n) \end{eqnarray}
つまり、$\displaystyle{A(n)\overset{\text{GIR}}{\longleftarrow\!\longrightarrow} B(n)}$です。

次は、画像から$B(n)\to A(n+1)$の遷移を考えてみましょう
$B(n)$型の一番後ろにある"10"の部分を"011"にすると$A(n+1)$型になりそうです。
\begin{eqnarray} B(n) &=& L^n1000 \\&\overset{\text{GIR}}{\longleftrightarrow}& L^n01100 \\&=& L^nL100 \\&=& L^{n+1}100 \\&=& A(n+1) \end{eqnarray}
ということで、$\begin{xy}\xymatrix@C=40pt{A(n) \ar@{<->}[r]^{\text{GIR}} & B(n) \ar@{<->}[r]^-{\text{GIR}} & A(n+1)}\end{xy}$となります。

また、$L^{n+1}$と$A(n)$型が移り変われます。
\begin{eqnarray} L^{n+1} &=& L^nL \\&=& L^n01 \\&\overset{\text{GIR}}{\longleftrightarrow}& L^n100 \\&=& A(n) \end{eqnarray}
しかも、$L^{n+1}0$と$B(n)$型が移り変われます。
\begin{eqnarray} L^{n+1}0 &=& L^nL0 \\&=& L^n010 \\&\overset{\text{GIR}}{\longleftrightarrow}& L^n1000 \\&=& B(n) \end{eqnarray}

そうですね。図にしてみましょう。
\begin{xy}\xymatrix@C=40pt{ A(n) \ar@{<->}[r]^{\text{GIR}} & B(n) \ar@{<->}[r]^-{\text{GIR}} & A(n+1) \ar@{}[r]|{\Huge\cdots} & \\ L^{n+1} \ar@{<->}[u] & L^{n+1}0 \ar@{<->}[u] & L^{n+2} \ar@{<->}[u] }\end{xy}
これによって$A(n),B(n),L^{n+1},L^{n+1}0$同士の移り変わりに最低何ステップで行けるかが判明しました。

ㅤ

基本形間の距離

さて、
基本形同士の移り変わりを実際に計算していくステップに移りたいのですが、そもそも基本形はどんな形があったでしょうか？

番号を付けておきます。
\begin{eqnarray} &&001010\cdots01 &=& 0L^{n+1} &\qquad\qquad\cdots(\text{R1})& \\ &&001010\cdots10 &=& 0L^{n+1}0 &\qquad\qquad\cdots(\text{R2})& \\ &&110101\cdots10 &=& 11L^n0 &\qquad\qquad\cdots(\text{R3})& \\ &&110101\cdots01 &=& 11L^{n+1} &\qquad\qquad\cdots(\text{R4})& \\ &&0101\cdots01 &=& L^{n+1} &\qquad\qquad\cdots(\text{R5})& \\ &&0101\cdots10 &=& L^{n+1}0 &\qquad\qquad\cdots(\text{R6})& \\ &&1010\cdots10 &=& 1L^n0 &\qquad\qquad\cdots(\text{R7})& \\ &&1010\cdots01 &=& 1L^{n+1} &\qquad\qquad\cdots(\text{R8})& \\ \end{eqnarray}

それと、最初から短かったという可能性がありますから、

\begin{eqnarray} 10 \\ 01 \end{eqnarray}

という可能性もありますが、上記の$n$が非負整数であることから
\begin{eqnarray} 10 &=& 1L^00\\ 01 &=& L\\ \end{eqnarray}
という形で尽くされています。

では、上記の8種の基本形同士の距離はどうなるでしょうか？

・$L^{n+1}$と$L^{m+1}0$ $\qquad(\text{R5}),(\text{R6})$

この場合、定理10から
\begin{eqnarray} d(L^{n+1},A(n)) &=& 1 \\ d(A(n),A(m)) &=& 2|m-n| \\ d(A(m),B(m)) &=& 1 \\ d(B(m),L^{m+1}0) &=& 1 \end{eqnarray}

ですから、$d(L^{n+1},L^{m+1}0) \leqq 1+2|m-n|+1+1 = 2|m-n|+3$と分かります。

・$0L^{n+1}$と$0L^{m+1}0$ $\qquad(\text{R1}),(\text{R2})$

こちらは先ほどの$L^{n+1}$と$L^{m+1}0$の先頭に"0"を付ければいいので、
$d(0L^{n+1},L^{m+1}0) \leqq 2|m-n|+3$と分かります。

・$1L^{n}0$と$1L^{m+1}$ $\qquad(\text{R7}),(\text{R8})$

$1L^n0$の$0$と$1$を反転させると、
\begin{eqnarray} 1L^n0 &=& 1\underbrace{0101\cdots01}_{n \text{ times 01}}0 \\&\underset{\text{反転}}{\longleftrightarrow}& 0\underbrace{1010\cdots10}_{n \text{ times 10}}1 \\&=& \underbrace{01010\cdots1}_{n \text{ times 01}}01 \\&=& L^n01 \\&=& L^{n+1} \end{eqnarray}
です。
また同じように$1L^{m+1}$も考えると、
\begin{eqnarray} 1L^{m+1} &=& 1\underbrace{0101\cdots01}_{m+1 \text{ times 01}} \\&\underset{\text{反転}}{\longleftrightarrow}& 0\underbrace{1010\cdots10}_{m+1 \text{ times 10}} \\&=& \underbrace{01010\cdots1}_{m+1 \text{ times 01}}0 \\&=& L^{m+1}0 \end{eqnarray}

この"反転"をちゃんと定義しておきましょう

ㅤ

この$\text{not}$に関して、以下の定理が成り立ちます。

この定理をさっきの$1L^n0 = \text{not}(L^{n+1})$と$1L^{m+1} = \text{not}(L^{m+1}0)$に使えば、
\begin{eqnarray} d(1L^n0,1L^{m+1}) &=& d(\text{not}(L^{n+1}),\text{not}(L^{m+1}0)) \\&=& d(L^{n+1},L^{m+1}0) \\&\leqq&2|m-n|+3 \end{eqnarray}
と証明できます。

・$11L^n0$と$11L^{m+1}$ $\qquad(\text{R3}),(\text{R4})$

こちらは先ほどの$1L^{n}0$と$1L^{m+1}$の先頭に"1"を付ければいいので、
$d(11L^n0,11L^{m+1}) \leqq 2|m-n|+3$と分かります。

ㅤ

今はこんな感じです。
\begin{xy}\xymatrix{ (\text{R1}) \ar@{<->}[rr]^{\large 2|m-n|+3} && (\text{R2}) \\ (\text{R3}) \ar@{<->}[rr]^{\large 2|m-n|+3} && (\text{R4}) \\ (\text{R5}) \ar@{<->}[rr]^{\large 2|m-n|+3} && (\text{R6}) \\ (\text{R7}) \ar@{<->}[rr]^{\large 2|m-n|+3} && (\text{R8}) }\end{xy}
うーん。縦のつながりが欲しいですね。

ㅤ

・$0L^{n+1}$と$L^{m+1}$ $\qquad(\text{R1}),(\text{R5})$

$n\geqq1$の時は次の遷移を使います。
\begin{eqnarray} 0L^{n+1} &=& 00101L^{n-1} \\&\overset{\text{GIR}}{\longleftrightarrow}& 000111L^{n-1} \\&\overset{\text{GIR}}{\longleftrightarrow}& 00111L^{n-1} \\&\overset{\text{GIR}}{\longleftrightarrow}& 0101L^{n-1} \\&=& L^{n+1} \end{eqnarray}
これにより、$d(0L^{n+1},L^{n+1})\leqq3$であることが分かるので、
$d(L^{n+1},L^{m+1}) \leqq 2|m-n|+2$を使って
$$d(0L^{n+1},L^{m+1}) \leqq 2|m-n|+5$$
と分かります。(本当は$2|m-n|+3$まで証明できるっぽいがそこまで証明しない)

$n=0,m\geqq1$の時は、
\begin{eqnarray} &[0]& 001 \\ &[1]& 0100 \\ &[2]& 10000 \\ &[3]& 011000 \\ &[4]& 01100 \\ &[5]& 0101 \end{eqnarray}
より、$d(0L^{0+1},L^{1+1}) \leqq 5$と分かるので、
$d(L^{1+1},L^{m+1}) \leqq 2|m-1|+2 = 2m$を使って、
$$d(0L^{0+1},L^{m+1}) \leqq 2m+5 = 2|m-n|+5$$
と分かります($n=0$だからです。)

$n=0,m=0$の時は、
\begin{eqnarray} &[0]&001 \\ &[1]&0100 \\ &[2]&10000 \\ &[3]&1000 \\ &[4]&100 \\ &[5]&01 \end{eqnarray}
これは、$d(0L^{0+1},L^{0+1}) \leqq 5$であることを表しています。$n=0,m=0$なので、
$d(0L^{0+1},L^{0+1}) \leqq 2|n-m|+5$とも書けます。

結局、任意の非負整数$n,m$に対して$d(0L^{n+1},L^{m+1}) \leqq 2|n-m|+5$と示せました。

この$(\text{R1})$と$(\text{R5})$の遷移、結構使えます。

・$0L^{n+1}0$と$L^{m+1}0$ $\qquad(\text{R2}),(\text{R6})$

これは先ほどの$0L^{n+1}$と$L^{m+1}$の先頭に"0"を付ければいいので、
$d(0L^{n+1}0,L^{m+1}0) \leqq 2|m-n|+5$と分かります。

・$11L^n0$と$1L^m0$ $\qquad(\text{R3}),(\text{R7})$

これは$\text{not}$をしてみましょう。
\begin{eqnarray} 11L^n0 &=& 11\underbrace{0101\cdots01}_{n \text{ times 01}}0 \\&\underset{\text{反転}}{\longleftrightarrow}& 00\underbrace{1010\cdots10}_{n \text{ times 10}}1 \\&=& 0\underbrace{01010\cdots1}_{n \text{ times 01}}01 \\&=& 0L^n01 \\&=& 0L^{n+1} \end{eqnarray}
\begin{eqnarray} 1L^m0 &=& 1\underbrace{0101\cdots01}_{m \text{ times 01}}0 \\&\underset{\text{反転}}{\longleftrightarrow}& 0\underbrace{1010\cdots10}_{m \text{ times 10}}1 \\&=& \underbrace{01010\cdots1}_{m \text{ times 01}}01 \\&=& L^m01 \\&=& L^{m+1} \end{eqnarray}
ということで、$11L^n0 = \text{not}(0L^{n+1}),\;1L^m0=\text{not}(L^{m+1})$です。
これは先ほどの$0L^{n+1}$と$L^{m+1}$と全く同じなので、
\begin{eqnarray} d(11L^{n+1},1L^{m+1}) &=& d(\text{not}(0L^{n+1}),\text{not}(L^{m+1})) \\&=& d(0L^{n+1},L^{m+1}) \\&\leqq& 2|m-n|+5 \end{eqnarray}
と分かりました。

・$11L^{n+1}$と$1L^{m+1}$ $\qquad(\text{R4}),(\text{R8})$

これは先ほどの$11L^n0$と$1L^{m+1}$の先頭に"0"を付ければいいので、
$d(0L^{n+1}0,L^{m+1}0) \leqq 2|m-n|+5$と分かります。

ㅤ

今のところこんな感じです
\begin{xy}\xymatrix{ (\text{R1}) \ar@{<->}[d]_{\large 2|m-n|+5} \ar@{<->}[rr]^{\large 2|m-n|+3} && (\text{R2}) \ar@{<->}[d]_{\large 2|m-n|+5} && (\text{R3}) \ar@{<->}[d]_{\large 2|m-n|+5} \ar@{<->}[rr]^{\large 2|m-n|+3} && (\text{R4}) \ar@{<->}[d]_{\large 2|m-n|+5} \\ (\text{R5}) \ar@{<->}[rr]_{\large 2|m-n|+3} && (\text{R6}) && (\text{R7}) \ar@{<->}[rr]_{\large 2|m-n|+3} && (\text{R8}) }\end{xy}

うーん。完璧に二つに分かれていますね。ここをうまくつなげられる道、どこに作りましょうか

ㅤ

・$0L^{n+1}$と$1L^{m+1}$ $\qquad(\text{R1}),(\text{R8})$

$n\geqq1$の時は、このような遷移があります。
\begin{eqnarray} 0L^{n+1} &=& 00101L^{n-1} \\&\overset{\text{GIR}}{\longleftrightarrow}& 010001L^{n-1} \\&\overset{\text{GIR}}{\longleftrightarrow}& 1000001L^{n-1} \\&\overset{\text{GIR}}{\longleftrightarrow}& 100001L^{n-1} \\&\overset{\text{GIR}}{\longleftrightarrow}& 10001L^{n-1} \\&\overset{\text{GIR}}{\longleftrightarrow}& 1001L^{n-1} \\&\overset{\text{GIR}}{\longleftrightarrow}& 01101L^{n-1} \\&\overset{\text{GIR}}{\longleftrightarrow}& 011101L^{n-1} \\&\overset{\text{GIR}}{\longleftrightarrow}& 10101L^{n-1} \\&=& 1L^{n+1} \end{eqnarray}
つまり、$d(0L^{n+1},1L^{n+1}) \leqq 8$です。
それと、$d(L^{n+1},L^{m+1}) \leqq 2|m-n|+2$を使って、
\begin{eqnarray} d(0L^{n+1},1L^{m+1}) \leqq 2|m-n|+10 \end{eqnarray}
と分かります。

そして、$n=0,m\geqq1$の時は
\begin{eqnarray} &[0]&001 \\ &[1]&0100 \\ &[2]&10000 \\ &[3]&011000 \\ &[4]&01100 \\ &[5]&011100 \\ &[6]&01101 \\ &[7]&011101 \\ &[8]&10101 \end{eqnarray}
より、$d(0L^1,1L^2) \leqq 8$です。
それと、$d(L^{1+1},L^{m+1}) \leqq 2|m-1|+2 = 2m$を使って、
\begin{eqnarray} d(0L^{n+1},1L^{m+1}) \leqq 2m+8 \leqq 2|m-n|+10 \end{eqnarray}
と分かります。
と分かります($n=0$だからです。)

そして、$n=0,m=0$の時は、
\begin{eqnarray} [0]&&001 \\ [1]&&0100 \\ [2]&&10000 \\ [3]&&011000 \\ [4]&&0111000 \\ [5]&&101000 \\ [6]&&1100000 \\ [7]&&110000 \\ [8]&&11000 \\ [9]&&1100 \\ [10]&&101 \end{eqnarray}
より、$n=0,m=0$なので、$d(0L^{n+1},1L^{m+1}) \leqq 2|m-n|+10$
と分かります。

・$0L^{n+1}0$と$1L^{m}0$ $\qquad(\text{R2}),(\text{R7})$

さっきの末尾に"0"を付け足しただけ...とはいかないんですよね。
なぜなら、$(\text{R7})$が$1L^m0$だからです。$1L^{m+1} \;\;(\text{R8})$の末尾に"0"を付け足しても$1L^m0 \;\;(\text{R7})$になりません。
(罠)
なので、普通に別で考えます。

$m\geqq1$の時から考えます。
といっても、さっきの結果である$d(0L^{n+1},1L^{n+1})\leqq8$を使います。
これの末尾に"0"を付け足すと$d(0L^{n+1}0,1L^{n+1}0)\leqq8$と分かります。
そして $d(L^{n+1},L^m) \leqq 2|n-(m-1)|+2 \leqq 2|n-m|+4$ ですから、
\begin{eqnarray} d(0L^{n+1}0,1L^m0) \leqq 2|n-m|+12 \end{eqnarray}
と分かりました。

$m=0$の時
\begin{eqnarray} &[0]&0010 \\ &[1]&00011 \\ &[2]&0011 \\ &[3]&01001 \\ &[4]&100001 \\ &[5]&10001 \\ &[6]&1001 \\ &[7]&011 \\ &[8]&10 \end{eqnarray}
という遷移を使います。これから、 $d(0L^10,10) \leqq 8$と分かります。
$d(L^{n+1},L^1) \leqq 2|n-0|+2 = 2n+2$ですから、$L^{n+1},L^1$の先頭と末尾に"0"を付ければ、
$d(0L^{n+1}0,0L^10) \leqq 2n+2$と分かります。
よって、合わせると
\begin{eqnarray} d(0L^{n+1}0,10) \leqq 2n+10 \leqq 2|n-m|+12 \end{eqnarray}
と分かりました。

・$11L^n0$と$L^{m+1}0$ $\qquad(\text{R3}),(\text{R6})$

これは$\text{not}$を使ってみましょう
\begin{eqnarray} 11L^n0 &=& 11\underbrace{0101\cdots01}_{n \text{ times 01}}0 \\&\underset{\text{反転}}{\longleftrightarrow}& 00\underbrace{1010\cdots10}_{n \text{ times 10}}1 \\&=& 0\underbrace{01010\cdots1}_{n \text{ times 01}}01 \\&=& 0L^n01 \\&=& 0L^{n+1} \end{eqnarray}
\begin{eqnarray} L^{m+1}0 &=& \underbrace{0101\cdots01}_{m+1 \text{ times 01}}0 \\&\underset{\text{反転}}{\longleftrightarrow}& \underbrace{1010\cdots10}_{m+1 \text{ times 10}}1 \\ &=& 1\underbrace{010\cdots101}_{m+1 \text{ times 01}} \\ &=& 1L^{m+1} \end{eqnarray}
ですから、
\begin{eqnarray} d(11L^n0,L^{m+1}0) &=& d(\text{not}(0L^{n+1}),\text{not}(1L^{m+1})) \\&=& d(0L^{n+1},1L^{m+1}) \\&\leqq& 2|n-m|+10 \end{eqnarray}
と分かります。

・$11L^{n+1}$と$L^{m+1}$ $\qquad(\text{R4}),(\text{R5})$

これも反転させてみましょう。
\begin{eqnarray} 11L^{n+1} &=& 11\underbrace{0101\cdots01}_{n+1 \text{ times 01}} \\&\underset{\text{反転}}{\longleftrightarrow}& 00\underbrace{1010\cdots10}_{n+1 \text{ times 10}} \\ &=& 0\underbrace{01010\cdots1}_{n+1 \text{ times 01}}0 \\ &=& 0L^{n+1}0 \end{eqnarray}
\begin{eqnarray} L^{m+1} &=& \underbrace{0101\cdots0101}_{m+1 \text{ times 01}} \\&\underset{\text{反転}}{\longleftrightarrow}& \underbrace{1010\cdots1010}_{m+1 \text{ times 10}} \\ &=& \underbrace{1010\cdots10}_{m \text{ times 10}}10 \\ &=& 1\underbrace{010\cdots101}_{m \text{ times 01}}0 \\ &=& 1L^m0 \end{eqnarray}
ですから、
\begin{eqnarray} d(11L^{n+1},L^{m+1}) &=& d(\text{not}(0L^{n+1}0),\text{not}(1L^m0)) \\&=& d(0L^{n+1}0,1L^m0) \\&\leqq& 2|n-m|+12 \end{eqnarray}
と分かります。

ㅤ

ここまでをまとめるとこうなります。
\begin{xy}\xymatrix{ (\text{R1}) \ar@{-}[rrr]|{2|m-n|+3} \ar@{-}[dddd]|{2|m-n|+5} \ar@{-}[rd]|{2|m-n|+10} & & & (\text{R2}) \ar@{.}[dddd]|{2|m-n|+5} \ar@{-}[rd]|{2|m-n|+12} \\ & (\text{R8}) \ar@{-}[rrr]|{2|m-n|+3 } \ar@{-}[dddd]|{2|m-n|+5} & \;\quad & & (\text{R7}) \ar@{-}[dddd]|{2|m-n|+5} \\ \\\\ (\text{R5}) \ar@{.}[rrr]|{2|m-n|+3} \ar@{-}[rd]|{2|m-n|+12} & & & (\text{R6}) \ar@{.}[rd]|{2|m-n|+10} \\ & (\text{R4}) \ar@{-}[rrr]|{2|m-n|+3} & & & (\text{R3}) }\end{xy}

これで一応行けない道はなくなりましたね。

ㅤ

最終的な評価

次の不等式が成り立ちます。

これを使って、次を証明しましょう！

まぁ一つ一つゆっくりやっていきます。

再掲しておきます。
\begin{eqnarray} &&001010\cdots01 &=& 0L^{n+1} &\qquad\qquad\cdots(\text{R1})& \quad\text{文字列の長さ: }2n+3 \\ &&001010\cdots10 &=& 0L^{n+1}0 &\qquad\qquad\cdots(\text{R2})& \quad\text{文字列の長さ: }2n+4 \\ &&110101\cdots10 &=& 11L^n0 &\qquad\qquad\cdots(\text{R3})& \quad\text{文字列の長さ: }2n+3 \\ &&110101\cdots01 &=& 11L^{n+1} &\qquad\qquad\cdots(\text{R4})& \quad\text{文字列の長さ: }2n+4 \\ &&0101\cdots01 &=& L^{n+1} &\qquad\qquad\cdots(\text{R5})& \quad\text{文字列の長さ: }2n+2 \\ &&0101\cdots10 &=& L^{n+1}0 &\qquad\qquad\cdots(\text{R6})& \quad\text{文字列の長さ: }2n+3 \\ &&1010\cdots10 &=& 1L^n0 &\qquad\qquad\cdots(\text{R7})& \quad\text{文字列の長さ: }2n+2 \\ &&1010\cdots01 &=& 1L^{n+1} &\qquad\qquad\cdots(\text{R8})& \quad\text{文字列の長さ: }2n+3 \\ \end{eqnarray}

・$(\text{R1})\leftrightarrow(\text{R2})\quad(\text{R3})\leftrightarrow(\text{R4})\quad(\text{R5})\leftrightarrow(\text{R6})\quad(\text{R7})\leftrightarrow(\text{R8})$

まずはそれぞれのペアについて、文字列の長さ $|S'|, |T'|$ と、その和 $+6$ を整理してみます。

どのペアであっても、 $|S'|+|T'|+6$ は $2(m+n)+11$ 以上になります。
一方、先ほどの議論により、これらのペアの距離は共通して $d(S',T') \leqq 2|m-n|+3$ です。
したがって、すべてのペアにおいて次の不等式が成り立ちます。
\begin{eqnarray} d(S',T') &\leqq& 2|m-n|+3 \\ &\leqq& 2(m+n)+3 \\ &<& 2(m+n)+11 \leqq |S'|+|T'|+6 \end{eqnarray}
よって、4 パターンすべてにおいて $d(S',T') \leqq |S'|+|T'|+6$ が成り立ちます。

・$(\text{R1})\leftrightarrow(\text{R5})\quad(\text{R2})\leftrightarrow(\text{R6})\quad(\text{R3})\leftrightarrow(\text{R7})\quad(\text{R4})\leftrightarrow(\text{R8})$

同じようにそれぞれのペアについて、文字列の長さ $|S'|, |T'|$ と、その和 $+6$ を整理してみます。

どのペアであっても、さっきと同じように $|S'|+|T'|+6$ は $2(m+n)+11$ 以上になります。
一方、先ほどの議論により、これらのペアの距離は共通して $d(S',T') \leqq 2|m-n|+5$ です。
したがって、すべてのペアにおいて次の不等式が成り立ちます。
\begin{eqnarray} d(S',T') &\leqq& 2|m-n|+5 \\ &\leqq& 2(m+n)+5 \\ &<& 2(m+n)+11 \leqq |S'|+|T'|+6 \end{eqnarray}
よって、4 パターンすべてにおいて $d(S',T') \leqq |S'|+|T'|+6$ が成り立ちます。

・$(\text{R1})\leftrightarrow(\text{R8})\quad(\text{R2})\leftrightarrow(\text{R7})\quad(\text{R3})\leftrightarrow(\text{R6})\quad(\text{R4})\leftrightarrow(\text{R5})$

同じようにそれぞれのペアについて、文字列の長さ $|S'|, |T'|$ と、その和 $+6$ を整理してみます。

どのペアであっても、 $|S'|+|T'|+6$ は $2(m+n)+12$ 以上になります。
一方、先ほどの議論により、これらのペアの距離は $2|m-n|+10$ または $2|m-n|+12$ です。
どちらであっても $2|m-n|+12$ 以下になります。
したがって、すべてのペアにおいて次の不等式が成り立ちます。
\begin{eqnarray} d(S',T') &\leqq& 2|m-n|+12 \\ &\leqq& 2(m+n)+12 \leqq |S'|+|T'|+6 \end{eqnarray}
よって、4 パターンすべてにおいて $d(S',T') \leqq |S'|+|T'|+6$ が成り立ちます。

・$(\text{R1})\leftrightarrow(\text{R6})\quad(\text{R2})\leftrightarrow(\text{R5})\quad(\text{R3})\leftrightarrow(\text{R8})\quad(\text{R4})\leftrightarrow(\text{R7})$

同じようにそれぞれのペアについて、文字列の長さ $|S'|, |T'|$ と、その和 $+6$ を整理してみます。

どのペアであっても、さっきと同じように $|S'|+|T'|+6$ は $2(m+n)+12$ 以上になります。
一方、これらのペアは先ほどの図で言う所の対角線にあって、こんな感じです。

\begin{gather}\xymatrix{ (\text{R1}) \ar@{<->}[d]_{\large 2|m-n|+5} \ar@{<->}[rr]^{\large 2|m-n|+3} && (\text{R2}) \ar@{<->}[d]_{\large 2|m-n|+5} && (\text{R3}) \ar@{<->}[d]_{\large 2|m-n|+5} \ar@{<->}[rr]^{\large 2|m-n|+3} && (\text{R4}) \ar@{<->}[d]_{\large 2|m-n|+5} \\ (\text{R5}) \ar@{<->}[rr]_{\large 2|m-n|+3} && (\text{R6}) && (\text{R7}) \ar@{<->}[rr]_{\large 2|m-n|+3} && (\text{R8}) }\end{gather}

この図から分かるように、対角線上にあるペアの距離は、
\begin{eqnarray} d(S',T') &\leqq& 2|m-n|+3 + 2|m-m|+5 \\&=& 2|m-n|+8 \end{eqnarray}
というように、$d(S',T')$は$2|m-n|+8$で上から抑えられます。
したがって、すべてのペアにおいて次の不等式が成り立ちます。
\begin{eqnarray} d(S',T') &\leqq& 2|m-n|+8 \\ &\leqq& 2(m-n)+8 \\ &\leqq& 2(m+n)+12 \leqq |S'|+|T'|+6 \end{eqnarray}
よって、4 パターンすべてにおいて $d(S',T') \leqq |S'|+|T'|+6$ が成り立ちます。

さぁ、残りのペアに対してはこのような単純な不等式が成り立ちません。

・$(\text{R1})\leftrightarrow(\text{R7})\quad(\text{R2})\leftrightarrow(\text{R8})\quad(\text{R3})\leftrightarrow(\text{R5})\quad(\text{R4})\leftrightarrow(\text{R6})$

同じようにそれぞれのペアについて、文字列の長さ $|S'|, |T'|$ と、その和 $+6$ を整理してみます。

どのペアであっても、 $|S'|+|T'|+6$ は $2(m+n)+11$ 以上になります。
一方、これらのペアは先ほどの図で言う所の対角線にあって、こんな感じです。

\begin{gather}\xymatrix{ (\text{R1}) \ar@{<->}[d]_{\large 2|m-n|+10} \ar@{<->}[rr]^{\large 2|m-n|+3} && (\text{R2}) \ar@{<->}[d]_{\large 2|m-n|+12} && (\text{R5}) \ar@{<->}[d]_{\large 2|m-n|+12} \ar@{<->}[rr]^{\large 2|m-n|+3} && (\text{R6}) \ar@{<->}[d]_{\large 2|m-n|+10} \\ (\text{R8}) \ar@{<->}[rr]_{\large 2|m-n|+3} && (\text{R7}) && (\text{R4}) \ar@{<->}[rr]_{\large 2|m-n|+3} && (\text{R3}) }\end{gather}

この図から分かるように、対角線上にあるペアの距離は、
\begin{eqnarray} d(S',T') &\leqq& 2|m-n|+3 + 2|m-m|+10 \\&=& 2|m-n|+13 \end{eqnarray}
というように、$d(S',T')$は$2|m-n|+13$で上から抑えられます。
しかし、これではだめで、$2(m+n)+11\leqq|S'|+|T'|+6$で$13$では抑えられてないです。
どうしましょうか。

$n\geqq1$かつ$m\geqq1$のとき、$m-1\geqq0,n-1\geqq0$ つまり$m-1,n-1$は非負整数ですから、
\begin{eqnarray} |(m-1)-(n-1)| &\leqq& m-1+n-1 = m+n-2 \\ |m-n| &\leqq& m+n-2 \end{eqnarray}
です。これを使うと、
\begin{eqnarray} d(S',T') &\leqq& 2|m-n| +3 + 2|m-m|+10 \\&=& 2|m-n| + 13 \\&\leqq& 2(m+n-2) + 13 \\&=& 2(m+n) + 9 \\&\leqq& 2(m+n) + 11 \leqq |S'|+|T'|+6 \end{eqnarray}
で、$d(S',T') \leqq |S'|+|T'|+6$が成り立っています。


$0L^{n+1}\;\;(\text{R1}),\;1L^n0\;\;(\text{R7})$の時を考えていきましょう... めんどい
$n=0$かつ$m\geqq1$の時は、$0L^{n+1} = 001$です。ここで以下のような遷移を考えます。
\begin{eqnarray} &[0]&001 \\ &[1]&0100 \\ &[2]&10000 \\ &[3]&1000 \\ &[4]&100 \\ &[5]&0110 \\ &[6]&01110 \\ &[7]&1010 \end{eqnarray}
つまり、$d(0L^{0+1},1L^10) \leqq 7$です。
$m\geqq1$ですから、 $d(L^{0+1},L^{m-1+1}) \leqq 2|m-1-0|+2 = 2m-2+2 = 2m$
の先頭に"1",末尾に"0"を付けると $d(1L^{0+1}0,1L^{m}0) \leqq 2m$ と分かります。
よって、$d(0L^{0+1},1L^m0) \leqq 2m+7$というのと、
\begin{eqnarray} |0L^{0+1}|+|1L^m0|+6 &=& 3+2m+2+6 \\&=& 2m+11 \end{eqnarray}
ですから
$d(0L^{0+1},1L^m0) \leqq |0L^{0+1}|+|1L^m0|+6$が成立しています。

$n=m=0$の時は、
\begin{eqnarray} &[0]&001 \\ &[1]&0100 \\ &[2]&10000 \\ &[3]&1000 \\ &[4]&01100 \\ &[5]&0101 \\ &[6]&10001 \\ &[7]&1001 \\ &[8]&011 \\ &[9]&10 \end{eqnarray}
という遷移から、$d(0L^{0+1},1L^00) \leqq 9$です。
それと$|0L^{0+1}|+|1L^00|+6 = 3+2+6 = 11$ですから、
$d(0L^{0+1},1L^00) \leqq |0L^{0+1}|+|1L^00| + 6$が成立しています。

$m=0,n\geqq1$の時は、
$d(L^{n+1},L^{1+1}) \leqq 2|n-1|+2 = 2n$で、先頭に"0"を付けると
$d(0L^{n+1},0L^{1+1}) \leqq 2n$と分かります。
次のような遷移があります。
\begin{eqnarray} &[0]&00101 \\ &[1]&010001 \\ &[2]&1000001 \\ &[3]&100001 \\ &[4]&10001 \\ &[5]&1001 \\ &[6]&011 \\ &[7]&10 \end{eqnarray}
つまり、$d(0L^{1+1},1L^{0}0) \leqq 2n+7$ と分かります。
それと$|0L^{n+1}|+|1L^00|+6 = $
\begin{eqnarray} |0L^{n+1}|+|1L^00|+6 &=& 2n+3 + 2 + 6 \\&=& 2n+11 \end{eqnarray}
ですから、
$$d(0L^{n+1},1L^00) \leqq |0L^{n+1}|+|1L^00|+6$$
と分かります。

$0L^{n+1}0\;\;(\text{R2}),\;1L^{n+1}\;\;(\text{R8})$の時を考えます。
これ実はそのままいけて、
$(\text{R2})$の長さは$2n+4$
$(\text{R8})$の長さは$2m+3$ですから、
\begin{eqnarray} |S'|+|T'|+6 &=& 2n+4+2m+3+6 \\&=& 2(m+n)+13 \end{eqnarray}
で、
\begin{eqnarray} d(S',T') &\leqq& 2|m-n|+10+2|n-n|+3 \\&=& 2|m-n|+13 \\&\leqq& 2(m+n)+13 = |S'|+|T'|+6 \end{eqnarray}
が成り立っています。よかったね。


さて、つぎは$11L^n0 \;\;(\text{R3}),\;L^{m+1}\;\;(\text{R5})$です。
ここで反転させてみましょう
\begin{eqnarray} 11L^n0 &=& 11\underbrace{0101\cdots01}_{n \text{ times 01}}0 \\&\underset{\text{反転}}{\longleftrightarrow}& 00\underbrace{1010\cdots10}_{n \text{ times 10}}1 \\&=& 0\underbrace{01010\cdots1}_{n \text{ times 01}}01 \\&=& 0L^n01 \\&=& 0L^{n+1} \quad(\text{R1}) \end{eqnarray}
\begin{eqnarray} L^{m+1} &=& \underbrace{0101\cdots0101}_{m+1 \text{ times 01}} \\&\underset{\text{反転}}{\longleftrightarrow}& \underbrace{1010\cdots1010}_{m+1 \text{ times 10}} \\ &=& \underbrace{1010\cdots10}_{m \text{ times 10}}10 \\ &=& 1\underbrace{010\cdots101}_{m \text{ times 01}}0 \\ &=& 1L^m0 \quad(\text{R7}) \end{eqnarray}
よって、
\begin{eqnarray} d(11L^n0,L^{m+1}) &=& d(\text{not}(0L^{n+1}),\text{not}(1L^m0)) \\&=& d(0L^{n+1},1L^m0) \\&\leqq& |0L^{n+1}|+|1L^m0| + 6 \\&=& 2n+3+2m+2+6 \\&=& |11L^n0|+|L^{m+1}|+6 \end{eqnarray}
と証明できます。

つぎは$11L^{n+1} \;\;(\text{R4}),\;L^{m+1}0\;\;(\text{R6})$です。
これもまた反転させてみましょう
\begin{eqnarray} 11L^{n+1} &=& 11\underbrace{0101\cdots01}_{n+1 \text{ times 01}} \\&\underset{\text{反転}}{\longleftrightarrow}& 00\underbrace{1010\cdots10}_{n+1 \text{ times 10}} \\&=& 0\underbrace{01010\cdots1}_{n+1 \text{ times 01}}0 \\&=& 0L^{n+1}0 \quad{(\text{R2})} \end{eqnarray}
\begin{eqnarray} L^{m+1}0 &=& \underbrace{0101\cdots0101}_{m+1 \text{ times 01}}0 \\&\underset{\text{反転}}{\longleftrightarrow}& \underbrace{1010\cdots1010}_{m+1 \text{ times 10}}1 \\ &=& 1\underbrace{010\cdots10101}_{m+1 \text{ times 01}} \\ &=& 1L^{m+1} \quad(\text{R8}) \end{eqnarray}
よって、
\begin{eqnarray} d(11L^{n+1},L^{m+1}0) &=& d(\text{not}(0L^{n+1}0),\text{not}(1L^{m+1})) \\&=& d(0L^{n+1}0,1L^{m+1}) \\&\leqq& |0L^{n+1}0|+|1L^{m+1}| + 6 \\&=& 2n+4+2m+3+6 \\&=& |11L^{n+1}|+|L^{m+1}0|+6 \end{eqnarray}
と証明できます。

あと表が出てくるのは2回です。頑張りましょう。

・$(\text{R1})\leftrightarrow(\text{R4})\quad(\text{R2})\leftrightarrow(\text{R3})\quad(\text{R5})\leftrightarrow(\text{R8})\quad(\text{R6})\leftrightarrow(\text{R7})$

同じようにそれぞれのペアについて、文字列の長さ $|S'|, |T'|$ と、その和 $+6$ を整理してみます。

しかし、前の議論で出した距離は以下の通りです。

\begin{gather}\xymatrix{ (\text{R1}) \ar@{<->}[d]_{\large 2|m-n|+5} \ar@{<->}[rr]^{\large 2|m-n|+10} && (\text{R8}) \ar@{<->}[d]_{\large 2|m-n|+5} && (\text{R2}) \ar@{<->}[d]_{\large 2|m-n|+5} \ar@{<->}[rr]^{\large 2|m-n|+12} && (\text{R7}) \ar@{<->}[d]_{\large 2|m-n|+5} \\ (\text{R5}) \ar@{<->}[rr]_{\large 2|m-n|+12} && (\text{R4}) && (\text{R6}) \ar@{<->}[rr]_{\large 2|m-n|+10} && (\text{R3}) }\end{gather}

ここから言うと、対角線上にあるペアの距離は
\begin{eqnarray} d(S',T') &\leqq& 2|m-n|+5+2|m-m|+10 \\&=& 2|m-n|+15 \end{eqnarray}
という風に上から抑えられます。でもこれはやっぱり $2(m+n)+11\leqq|S'|+|T'|+6$ より、
$|S'|+|T'|+6$ では抑えられないです。
さっきと同じことしましょうか。

$n\geqq1$かつ$m\geqq1$のとき、$m-1\geqq0,n-1\geqq0$ つまり$m-1,n-1$は非負整数ですから、
\begin{eqnarray} |(m-1)-(n-1)| &\leqq& m-1+n-1 = m+n-2 \\ |m-n| &\leqq& m+n-2 \end{eqnarray}
です。これを使うと、
\begin{eqnarray} d(S',T') &\leqq& 2|m-n|+15 \\&\leqq& 2(m+n-2)+15 \\&=& 2(m+n)+11 &\leqq& |S'|+|T'|+6 \end{eqnarray}
で、 $d(S',T')\leqq|S'|+|T'|+6$ が成り立っています。


あとは個別にやるしかないですね...
$0L^{n+1}\;\;(\text{R1}),\;11L^{m+1}\;\;(\text{R4})$を考えます。
$n=0$の時を考えます。このとき$(\text{R1})$は$001$です。
このような遷移があります。
\begin{eqnarray} [0]&&001 \\ [1]&&0100 \\ [2]&&10000 \\ [3]&&011000 \\ [4]&&0111000 \\ [5]&&01111000 \\ [6]&&1011000 \\ [7]&&110000 \\ [8]&&11000 \\ [9]&&111000 \\ [10]&&11100 \\ [11]&&1101 \end{eqnarray}
ここから、$d(0L^{0+1},11L^{0+1}) \leqq 11$と分かります。
そして、$d(L^{0+1},L^{m+1}) \leqq 2|m-0|+2 = 2m+2$ なので、
\begin{eqnarray} d(0L^{0+1},11L^{m+1}) &\leqq& 11+2m+2 \\&=& 3+2m+4+6 \\&=& |0L^{0+1}|+|11L^{m+1}|+6 \end{eqnarray}
より、成り立っています。

今度は$m=0$の時を考えます。
まぁさっきの遷移を考えると、$d(0L^{0+1},11L^{0+1})\leqq11$
と、$d(L^{0+1},L^{n+1}) \leqq 2|n-0|+2 = 2n+2$ から、
\begin{eqnarray} d(0L^{n+1},11L^{0+1}) &\leqq& 2n+2+11 \\&=& 2n+3+4+6 \\&=&|0L^{n+1}|+|11L^{0+1}|+6 \end{eqnarray}
より、成り立っています。


$L^{n+1}\;\;(\text{R5}),\;1L^{m+1}\;\;(\text{R8})$を考えます。
このような遷移があります。
\begin{eqnarray} &[0]&01 \quad= L^{0+1}\\ &[1]&100 \\ &[2]&0110 \\ &[3]&10010 \\ &[4]&100011 \\ &[5]&10011 \\ &[6]&0111 \\ &[7]&101 \quad= 1L^{0+1} \end{eqnarray}
つまり、$d(L^{0+1},1L^{0+1}) \leqq 7$ です。
これの末尾に$L^m$をくっつけると、
$d(L^{m+1},1L^{m+1}) \leqq 7$と分かります。
また、$d(L^{n+1},L^{m+1}) \leqq 2|m-n|+2$ です。
よって、
\begin{eqnarray} d(L^{n+1},1L^{m+1}) &\leqq& d(L^{n+1},L^{m+1}) + d(L^{m+1},1L^{m+1}) \\&=& 2|m-n|+2 + 7 \\&\leqq& 2(m+n)+9 \\&\leqq& 2n+2m+11 \\&=& 2n+2+2m+3+6 \\&=& |L^{n+1}|+|1L^{m+1}|+6 \end{eqnarray}
となり、示せました。


$0L^{n+1}0\;\;(\text{R2}),\;11L^m0\;\;(\text{R3})$を考えます。
これは反転してみましょう。
\begin{eqnarray} 0L^{n+1}0 &=& 0\underbrace{01010\cdots1}_{n+1 \text{ times 01}}0 \\&\underset{\text{反転}}{\longleftrightarrow}& 1\underbrace{10101\cdots0}_{n+1 \text{ times 10}}1 \\&=& 11\underbrace{0101\cdots01}_{n+1 \text{ times 01}} \\&=& 11L^{n+1} \quad(\text{R4}) \end{eqnarray}
\begin{eqnarray} 11L^m0 &=& 11\underbrace{0101\cdots01}_{m \text{ times 01}}0 \\&\underset{\text{反転}}{\longleftrightarrow}& 00\underbrace{1010\cdots10}_{m \text{ times 10}}1 \\&=& 0\underbrace{01010\cdots1}_{m \text{ times 01}}01 \\&=& 0L^m01 \\&=& 0L^{m+1} \quad(\text{R1}) \end{eqnarray}
よって、
\begin{eqnarray} d(0L^{n+1}0,11L^m0) &=& d(\text{not}(11L^{n+1}),\text{not}(0L^{m+1})) \\&=& d(11L^{n+1},0L^{m+1}) \\&\leqq& |11L^{n+1}|+|0L^{m+1}|+6 \\&=& 2n+4+2m+3+6 \\&=& |0L^{n+1}0|+|11L^m0|+6 \end{eqnarray}
と証明できます。


$L^{n+1}0\;\;(\text{R6}),\;1L^m0\;\;(\text{R7})$を考えます。
これも反転してみましょう。
\begin{eqnarray} L^{n+1}0 &=& \underbrace{01010\cdots1}_{n+1 \text{ times 01}}0 \\&\underset{\text{反転}}{\longleftrightarrow}& \underbrace{10101\cdots0}_{n+1 \text{ times 10}}1 \\&=& 1\underbrace{0101\cdots01}_{n+1 \text{ times 01}} \\&=& 1L^{n+1} \quad(\text{R8}) \end{eqnarray}
\begin{eqnarray} 1L^m0 &=& 1\underbrace{0101\cdots01}_{m \text{ times 01}}0 \\&\underset{\text{反転}}{\longleftrightarrow}& 0\underbrace{1010\cdots10}_{m \text{ times 10}}1 \\&=& \underbrace{01010\cdots1}_{m \text{ times 01}}01 \\&=& L^m01 \\&=& L^{m+1} \quad(\text{R5}) \end{eqnarray}
よって、
\begin{eqnarray} d(L^{n+1}0,1L^m0) &=& d(\text{not}(1L^{n+1}),\text{not}(L^{m+1})) \\&=& d(1L^{n+1},L^{m+1}) \\&\leqq& |1L^{n+1}|+|L^{m+1}|+6 \\&=& 2n+3+2m+2+6 \\&=& |L^{n+1}0|+|1L^m0|+6 \end{eqnarray}
と証明できます。

最後です...

・$(\text{R1})\leftrightarrow(\text{R3})\quad(\text{R2})\leftrightarrow(\text{R4})\quad(\text{R5})\leftrightarrow(\text{R7})\quad(\text{R6})\leftrightarrow(\text{R8})$

これ、かなり厄介で、なぜかと言うとペアになっているのが反転した者どうしなのです。
つまり、反転しても別のペアの証明に使うことができません。
しかも前に示したやつから距離を考えると、
\begin{eqnarray} d(S',T') &\leqq& 2|m-n|+10+2|n-n|+3+2|n-n|5 \\&=& 2|m-n|+18 \end{eqnarray}
となり、予想から計算すると出る$2(m+n)+10$を全然抑えられないです。
だから一つ一つ証明していきます。

$0L^{n+1}\;\;(\text{R1}),\;11L^m0\;\;(\text{R3})$を考えます。

$m\geqq1$の時の場合と、$n\geqq1$の時の場合を並行して書きます。
このような遷移があります。
\begin{eqnarray} [0] && 001 &\quad [0] && 00101 \\ [1] && 0100 &\quad [1] && 000111 \\ [2] && 10000 &\quad [2] && 00111 \\ [3] && 011000 &\quad [3] && 001111 \\ [4] && 01100 &\quad [4] && 01011 \\ [5] && 011100 &\quad [5] && 100011 \\ [6] && 01101 &\quad [6] && 10011 \\ [7] && 011101 &\quad [7] && 1010 \\ [8] && 10101 &\quad [8] && 11000 \\ [9] && 110001 &\quad [9] && 111000 \\ [10] && 1110001 &\quad [10] && 11100 \\ [11] && 110101 &\quad [11] && 1101 \end{eqnarray}
つまり、
$d(0L^{0+1},11L^{1+1}) \leqq 11 \qquad(m\geqq1)$
$d(0L^{1+1},11L^{0+1}) \leqq 11 \qquad(n\geqq1)$
です。上の式には$L^n$を末尾に付け、下の式には$L^{n-1}$を末尾に付けます。
\begin{eqnarray} d(0L^{n+1},11L^{n+2}) &\leqq& 11 \qquad(m\geqq1) \\ d(0L^{n+1},11L^{n}) &\leqq& 11 \qquad(n\geqq1) \end{eqnarray}
です。

そして、
\begin{eqnarray} d(11L^{n+2},11L^{m+1}) = d(L^{(n+1)+1},L^{m+1}) &\leqq& 2|n+1-m| &\qquad& (m\geqq1) \\ d(11L^{n},11L^{m+1}) = d(L^{(n-1)+1},L^{m+1}) &\leqq& 2|n-1-m| &\qquad& (n\geqq1) \end{eqnarray}
です。

ここで、次のような遷移ができます。
\begin{eqnarray} 11L^{m+1} &=& 11\underbrace{01\cdots0101}_{m+1 \text{ times } 01} \\&=& 1\underbrace{101\cdots010}_{m+1 \text{ times } 10}1 \\&=& 1\underbrace{101\cdots0}_{m \text{ times } 10}101 \\&\overset{\text{GIR}}{\longleftrightarrow}& 1\underbrace{101\cdots0}_{m \text{ times } 10}0111 \\&\overset{\text{GIR}}{\longleftrightarrow}& 1\underbrace{101\cdots0}_{m \text{ times } 10}011 \\&\overset{\text{GIR}}{\longleftrightarrow}& 1\underbrace{101\cdots0}_{m \text{ times } 10}10 \\&=& 11\underbrace{01\cdots01}_{m \text{ times } 01}0 \\&=& 11L^m0 \end{eqnarray}
よって、$d(11L^{m+1},11L^m0) \leqq 3$です。 (これは$m=0$でも成り立つ)


$m\geqq1$の時を考えます。
この時、$m-1$が非負整数で、今$n$も非負整数ですから、
\begin{eqnarray} |n+1-m| &=& |n-(m-1)| \\&\leqq& n+(m-1) \end{eqnarray}
です。これを使います。
\begin{eqnarray} d(0L^{n+1},11L^m0) &\leqq& d(0L^{n+1},11L^{n+2}) + d(11L^{n+2},11L^{m+1}) + d(11L^{m+1},11L^m0) \\&\leqq& 11+2|n+1-m|+3 \\&\leqq& 2(n+m-1)+14 \\&=& 2n+2m+12 \\&=& 2n+3+2m+3+6 \\&\leqq& |0L^{n+1}|+|11L^m0|+6 \end{eqnarray}

$n\geqq1$の時を考えます。
この時、$n-1$が非負整数で、$m$も非負整数ですから、
\begin{eqnarray} |n-1-m| &=& |(n-1)-m| \\&\leqq& (n-1)+m \end{eqnarray}
です。これを使います。
\begin{eqnarray} d(0L^{n+1},11L^m0) &\leqq& d(0L^{n+1},11L^n) + d(11L^n,11L^{m+1}) + d(11L^{m+1},11L^m0) \\&\leqq& 11+2|n-1+m|+3 \\&\leqq& 2(n-1+m)+14 \\&=& 2n+2m+12 \\&=& 2n+3+2m+3+6 \\&\leqq& |0L^{n+1}|+|11L^m0|+6 \end{eqnarray}

最後に、$n=0$かつ$m=0$の時ですが、
\begin{eqnarray} [0] && 001 \\ [1] && 0100 \\ [2] && 10000\\ [3] && 1000 \\ [4] && 100 \\ [5] && 0110 \\ [6] && 01110\\ [7] && 1010 \\ [8] && 10011\\ [9] && 0111 \\ [10] && 01111\\ [11] && 1011 \\ [12] && 110 \end{eqnarray}
なので、
\begin{eqnarray} d(0L^{0+1},11L^00) &=& d(001,110) \\&\leqq& 12 \\&=& |001|+|110|+6 \\&=& |0L^{0+1}|+|11L^00|+6 \end{eqnarray}
よって証明できました。

あと三つある....



$0L^{n+1}0\;\;(\text{R2}),\;11L^{m+1}\;\;(\text{R4})$を考えます。

$m\geqq1$の時の場合と、$n\geqq1$の時の場合を並行して書きます。

さっきの$(\text{R1})$と$(\text{R3})$の時に出した結果を使いましょう。

\begin{eqnarray} d(0L^{n+1},11L^{n+2}) &\leqq& 11 \qquad(m\geqq1) \\ d(0L^{n+1},11L^{n}) &\leqq& 11 \qquad(n\geqq1) \end{eqnarray}

この先頭に"0"を付けると、
\begin{eqnarray} d(0L^{n+1}0,11L^{n+2}0) &\leqq& 11 \qquad(m\geqq1) \\ d(0L^{n+1}0,11L^{n}0) &\leqq& 11 \qquad(n\geqq1) \end{eqnarray}
と分かります。

そして、これもさっきの結果ですが、

\begin{eqnarray} d(11L^{n+2},11L^{m+1}) = d(L^{(n+1)+1},L^{m+1}) &\leqq& 2|n+1-m| &\qquad& (m\geqq1) \\ d(11L^{n},11L^{m+1}) = d(L^{(n-1)+1},L^{m+1}) &\leqq& 2|n-1-m| &\qquad& (n\geqq1) \end{eqnarray}

ですから、先頭に"0"を付けると
\begin{eqnarray} d(11L^{n+2}0,11L^{m+1}0) &\leqq& 2|n+1-m| &\qquad& (m\geqq1) \\ d(11L^{n}0,11L^{m+1}0) &\leqq& 2|n-1-m| &\qquad& (n\geqq1) \end{eqnarray}

ここで、次のような遷移ができます。
\begin{eqnarray} 11L^{m+1}0 &=& 11\underbrace{0101\cdots01}_{m+1 \text{ times } 01}0 \\&=& 11\underbrace{01\cdots01}_{m \text{ times } 01}010 \\&\overset{\text{GIR}}{\longleftrightarrow}& 11\underbrace{01\cdots01}_{m \text{ times } 01}1000 \\&\overset{\text{GIR}}{\longleftrightarrow}& 11\underbrace{01\cdots01}_{m \text{ times } 01}100 \\&\overset{\text{GIR}}{\longleftrightarrow}& 11\underbrace{01\cdots01}_{m \text{ times } 01}01 \\&=& 11\underbrace{01\cdots0101}_{m+1 \text{ times } 01} \\&=& 11L^{m+1} \end{eqnarray}
よって、$d(11L^{m+1}0,11L^{m+1}) \leqq 3$です。 (これは$m=0$でも成り立つ)


$m\geqq1$の時を考えます。
この時、$m-1$が非負整数で、今$n$も非負整数ですから、
\begin{eqnarray} |n+1-m| &=& |n-(m-1)| \\&\leqq& n+(m-1) \end{eqnarray}
です。これを使います。
\begin{eqnarray} d(0L^{n+1}0,11L^{m+1}) &\leqq& d(0L^{n+1}0,11L^{n+2}0) + d(11L^{n+2}0,11L^{m+1}0) + d(11L^{m+1}0,11L^{m+1}) \\&\leqq& 11+2|n+1-m|+3 \\&\leqq& 2(n+m-1)+14 \\&=& 2n+2m+14 \\&=& 2n+4+2m+4+6 \\&\leqq& |0L^{n+1}0|+|11L^{m+1}|+6 \end{eqnarray}

$n\geqq1$の時を考えます。
この時、$n-1$が非負整数で、$m$も非負整数ですから、
\begin{eqnarray} |n-1-m| &=& |(n-1)-m| \\&\leqq& (n-1)+m \end{eqnarray}
です。これを使います。
\begin{eqnarray} d(0L^{n+1}0,11L^{m+1}) &\leqq& d(0L^{n+1}0,11L^n0) + d(11L^n0,11L^{m+1}0) + d(11L^{m+1}0,11L^{m+1}) \\&\leqq& 11+2|n-1+m|+3 \\&\leqq& 2(n-1+m)+14 \\&=& 2n+2m+14 \\&=& 2n+4+2m+4+6 \\&\leqq& |0L^{n+1}0|+|11L^{m+1}|+6 \end{eqnarray}

$n=0$かつ$m=0$の時は、以下のような遷移があり、
\begin{eqnarray} [0] && 0010 \\ [1] && 00011 \\ [2] && 0011 \\ [3] && 00111 \\ [4] && 0101 \\ [5] && 10001 \\ [6] && 1001 \\ [7] && 011 \\ [8] && 0111 \\ [9] && 101 \\ [10] && 1100 \\ [11] && 11100 \\ [12] && 1101 \end{eqnarray}
ここから

\begin{eqnarray} d(0L^{0+1}0,11L^{0+1}) &=& d(0010,1101) \\&\leqq& 12 \\&\leqq& |0010|+|1101|+6 \\&=& |0L^{0+1}0|+|11L^{0+1}| + 6 \end{eqnarray}
と分かります。

よって証明できました。




$L^{n+1}\;\;(\text{R4}),\;1L^m0\;\;(\text{R6})$を考えます。

以下のような遷移があります。
\begin{eqnarray} [0] && 01 \\ [1] && 100 \\ [2] && 0110 \\ [3] && 01110 \\ [4] && 1010 \\ [5] && 11000 \\ [6] && 1100 \\ [7] && 101 \\ \end{eqnarray}
よって、$d(L^{0+1},1L^{0+1}) \leqq 7$ です。
この先頭に$L^n$を付けると、$d(L^{n+1},1L^{n+1}) \leqq 7$ と分かります。

また、$d(L^{n+1},L^{m+1}) \leqq 2|m-n|$ の先頭に"1"を付ければ、
$d(1L^{n+1},1L^{m+1}) \leqq 2|m-n|$ と分かります。

そして、
\begin{eqnarray} 1L^{m+1} &=& 1\underbrace{01\cdots0101}_{m+1 \text{ times } 01} \\&=& \underbrace{101\cdots010}_{m+1 \text{ times } 10}1 \\&=& \underbrace{101\cdots0}_{m \text{ times } 10}101 \\&\overset{\text{GIR}}{\longleftrightarrow}& \underbrace{101\cdots0}_{m \text{ times } 10}0111 \\&\overset{\text{GIR}}{\longleftrightarrow}& \underbrace{101\cdots0}_{m \text{ times } 10}011 \\&\overset{\text{GIR}}{\longleftrightarrow}& \underbrace{101\cdots0}_{m \text{ times } 10}10 \\&=& 1\underbrace{01\cdots01}_{m \text{ times } 01}0 \\&=& 1L^m0 \end{eqnarray}
ですから、$d(1L^{m+1},1L^m0) \leqq 3$です。

以上をまとめると、
\begin{eqnarray} d(L^{n+1},1L^m0) &\leqq& d(L^{n+1},1L^{n+1}) + d(1L^{n+1},1L^{m+1}) + d(1L^{m+1},1L^m0) \\&\leqq& 7+2|m-n|+3 \\&\leqq& 2(m+n) + 10 \\&=& 2n+2 + 2m+2 + 6 \\&=& |L^{n+1}| + |1L^m0| + 6 \end{eqnarray}

よって証明できました。

あと一つ...




$L^{n+1}0\;\;(\text{R6}),\;1L^{m+1}\;\;(\text{R8})$を考えます。

さっきの$(\text{R5})$と$(\text{R7})$の時に出した結果を使います。
$d(L^{n+1},1L^{n+1}) \leqq 7$ です。
この末尾に"0"を付けると、$d(L^{n+1}0,1L^{n+1}0) \leqq 7$ と分かります。

また、$d(L^{n+1},L^{m+1}) \leqq 2|m-n|$ の先頭に"1",末尾に"0"を付ければ、
$d(1L^{n+1}0,1L^{m+1}0) \leqq 2|m-n|$ と分かります。

そして、
\begin{eqnarray} 1L^{m+1}0 &=& 1\underbrace{01\cdots0101}_{m+1 \text{ times } 01}0 \\&=& 1\underbrace{01\cdots01}_{m \text{ times } 01}010 \\&\overset{\text{GIR}}{\longleftrightarrow}& 1\underbrace{01\cdots01}_{m \text{ times } 01}1000 \\&\overset{\text{GIR}}{\longleftrightarrow}& 1\underbrace{01\cdots01}_{m \text{ times } 01}100 \\&\overset{\text{GIR}}{\longleftrightarrow}& 1\underbrace{01\cdots01}_{m \text{ times } 01}01 \\&=& 1\underbrace{01\cdots0101}_{m+1 \text{ times } 01} \\&=& 1L^{m+1} \end{eqnarray}
ですから、$d(1L^{m+1}0,1L^{m+1}) \leqq 3$です。

以上をまとめると、
\begin{eqnarray} d(L^{n+1}0,1L^{m+1}) &\leqq& d(L^{n+1}0,1L^{n+1}0) + d(1L^{n+1}0,1L^{m+1}0) + d(1L^{m+1}0,1L^{m+1}) \\&\leqq& 7+2|m-n|+3 \\&\leqq& 2(m+n) + 10 \\&=& 2n+3 + 2m+3 + 4 \\&\leqq& 2n+3 + 2m+3 + 6 \\&=& |L^{n+1}0| + |1L^{m+1}| + 6 \end{eqnarray}

よって証明できました。

ふぅぅぅ。

頑張った証↓

\begin{xy}\xymatrix{ (\text{R1}) \ar@{-}[rrr] \ar@{-}[ddddd] \ar@{-}[rrd] \ar@{-}[rrrrrd] \ar@{-}[rrdddddd] \ar@{.}[rrrddddd] \ar@{--}[rrrrrdddddd] & \;\quad\;\; & & (\text{R2}) \ar@{.}[ddddd] \ar@{-}[rrd] \ar@{-}[ld] \ar@{.}[rrdddddd] \ar@{.}[lllddddd] \ar@{--}[ldddddd] \\ & & (\text{R8}) \ar@{-}[rrr] \ar@{-}[ddddd] \ar@{-}[lldddd] \ar@{-}[rrrddddd] \ar@{--}[rdddd] & \;\qquad\qquad\quad\;\;\;\; & & (\text{R7}) \ar@{-}[ddddd] \ar@{.}[lldddd] \ar@{-}[lllddddd] \ar@{--}[llllldddd] \\ \\\\\\ (\text{R5}) \ar@{.}[rrr] \ar@{-}[rrd] \ar@{.}[rrrrrd] & & & (\text{R6}) \ar@{.}[rrd] \ar@{.}[ld] \\ & & (\text{R4}) \ar@{-}[rrr] & & & (\text{R3}) }\end{xy}

上界の最終的な結果

結局は、

が示せたこととなりました。これは非常にうれしくて、というのも定理9の主張である：

から、 $d(S,S') = |S|-|S'|$ と分かるので、ここから任意の文字列間の距離を上から抑えることができます。

今回のまとめ&予想と私の記事のお話

まとめって書くの苦手なんですよね。

今回、2種類の文字からなる文字列に対して2-GIRでの文字列間の距離の上界と下界を考えました。

つまり、「最低これ以上は手数がかかるよね」という値と、
「最大でもこれ以下の手数でいいよね」という値を計算しました。

しかし、2種類の文字のみからなるものしかやっていないですから、これを$n$種類にまで拡張する...などの一般化はいろいろと考えられます。ただ見てきたように、証明はおそらく泥沼で、コンピュータにも頼るのがいいでしょう。

また、$n$-GIRでの距離はまだ何も考えてないですし、私はこれで心が折れかけているので考えたくありません。

それと、2種類の文字からなる文字列で、かつ2-GIRの世界であっても、まだ予想となっているものがあります。今回証明した$|S|+|T|+6$という上界ですが、これは上限だろうという予想です。つまり、

という意味です。
ちなみに$2$文字の文字列ではこの予想は成立しません。例えば$n=m=2$の時$S=01$と$T=10$との距離が最長ですが、$d(S,T) = 8$です。$10$ではないです。しかし$n,m$が$3$以上ならどうやら成り立ちそうで、$S=0^{n-1}1$と$T=1^{m-1}0$とすると達成されそうな雰囲気が醸し出されています。
実際$d(001,110) = 12$でぴったりです。

今回の最初の方の議論から、
\begin{eqnarray} \Phi_{\text{diff}}(S) &=& |S|_0 - |S|_1 \\&=& n-1 - 1 \\&=& n-2 \\ \Phi_{\text{diff}}(T) &=& |T|_0 - |T|_1 \\&=& 1 - (m-1) \\&=& 2-m \end{eqnarray}
ですから、
\begin{eqnarray} d(S,T) &\geqq& |\Phi_{\text{diff}}(S) - \Phi_{\text{diff}}(T)| \\&=& | n-2 - (m-2) | \\&=& | n + m - 4| \\&=& n + m - 4 \end{eqnarray}
までは分かりますが、なんせあと$10$を証明するのはまぁ...

なんか累積帰納法で証明できそうな気がしてきたぞ。
なんせ最初の$S$や$T$にGIRを適用させる場所が実質的に2箇所しかないし、片方は正解の道であって文字数が減るので累積帰納法の仮定を使えそうです。
そのほかのGIRの適用の仕方が文字数が伸びる方向に行ってしまうので、その方向に進んでしまうとどうやっても$|S|+|T|+5$手ではもう片方に移れないことを証明できればよさそうです。
まぁ、ちゃんとした証明は考えないことにします。(めんどい)
証明出来たら記事にすれば、みんなからいいねをもらえますよ。少なくとも僕はいいねします。

私の記事について少し話します。
私は以前からいくつか記事を書いてきましたが、ほとんどの記事に共通する点として、「高校数学が分かって入れば記事の内容を理解できる」というコンセプトがあります。
例えば今回の記事でも、一切$\le$や$\ge$という記号は使いませんでした。まぁ気づきませんよね.. しかもそんなところに気を配るもんでもないですし。
けど、一度友人に数学の問題を解説しているときに私が書いた$\ge$ってどういう意味？と言われたことがあったので、それを思い出してこうしました。
これは私が記事を書き始めたのが高校生の頃であるからで、その頃は他の優秀なmathlogで記事を書いていたりTwitterで活動している高校生の方々とは違い、私自身は大学数学を一切勉強したことはありませんでした。
もちろん、高校数学の範囲内で主張が理解できる難しい定理であったりなどはいくらか知っていましたが、大学数学の範囲、もっと言えばもともと高校数学であった行列のかけ算の定義などの内容も一切知りませんでした。
しかし、mathlogの記事の半分ぐらいは専門的な内容であり、私なんかは知識が無く読めないものです。いま私は大学生になったので、行列なんかは少し知識がつきましたが、まだまだ位相すら理解していません。
なので皆様からすれば、これまでの私の記事でも「この数学の概念を使えば非常に簡明に書けるのに..」と思ったり、「これならここの構造を調べたほうが対象の性質の色々なことが分かるのに..」などと思ったことがあるかもしれません。
かもしれませんが、私の記事のモットーは専門知識なしにできるだけ高校数学までの知識で記事を書くことです。(さらに言えば高校数学もあまり入れないようにできるならする)私の記事にした内容の一般化やさらなる研究はぜひしていただきたい。私の許可も何もいらないです。
それだけ言いたかった(自己満足)だけです。これからも私は高度な知識なしに読める記事を書きます。記事が長くなるかもしれないですが、よろしくお願いします。