Thue-Morse列

0と1からなるThue-Morse列（TM列） $t=t_0t_1t_2\dots t_n\dots$ は次のように複数の方法で定義できる。

Thue-Morse列(1)

上のThue-Morse列の定義は、$n$を2進表示したときのdigitsの総和を $d_2sum(n)$ としたとき、次のよう書くこともできる。

Thue-Morse列(2) 再帰的定義

Thue-Morse列（TM列）$t=t_0t_1t_2\dots t_n\dots$は、次のようにして再帰的に定義される。

ヒント

関数定義の引数（左辺）では thue[2 n_] というように式を書くことができず、thue[n_] で定義する。 そのため、組み込み関数 Whichを使い、引数 n の条件をチェックするやり方がある。 分かりやすいように、改行などして表記を工夫しよう。

thue[n_Integer] := Which[
  n == 0, 0,
  EvenQ[n], thue[n/2],
  OddQ[n], 1 - thue[(n - 1)/2]
]

Mathematicaの利用で大変強力なのが、patt /; test のように制約条件 test を /; の後に書いて、条件 test がTrueとなった場合に限りpatt にパターンマッチさせることができる点である。

thue[0] := 0;
thue[n_] := thue[n/2] /; EvenQ[n];
thue[n_] := thue[(n - 1)/2] /; OddQ[n]

ほぼ、漸化式の定義に近い形で関数が定義されることに注意。

0番目からn番目のThue-Morse列

$n$を与えて0番目からn番目のThue-Morse列値をリストとして返すMathematica関数 thuemorse[n] は、thue[n] または thue2[n] を使うと Table[thue[i], {i, 0, n}] で定義できる。

$n$番目までの非負整数集合のdisjoint分割

$n$番目までの非負整数集合 $N_n=\{0,1,2,\dots, n\}$ を \[ N_n = A_n \cup B_n,\qquad A_n \cap B_n =\phi \] のように、disjointな集合$A_n$と$B_n$の2つの集合に分割することを考えよう。

Thue-Morse列を使って \begin{gather*} A_n=\{t_n \,|\, t_n=0\},\\ B_n=\{t_n \,|\, t_n=1\}\\ \end{gather*} のようにして、集合$A_n$と$B_n$を選ぶことができる。 これを実際に求めるMathematicaプログラムを考えよう。

次のようなMathematica計算に注意しよう。 0番目から9番目までのThue-Morse列 {0, 1, 1, 0, 1, 0, 0, 1、1} で、0または1がリスとの何番目にためにMathematica関数 Position を使っている。

Position[{0, 1, 1, 0, 1, 0, 0, 1, 1, 0}, 0]
    {{1}, {4}, {6}, {7}, {10}}
Position[{0, 1, 1, 0, 1, 0, 0, 1, 1, 0}, 1]
    {{2}, {3}, {5}, {8}, {9}}

Flatten[Position[{0, 1, 1, 0, 1, 0, 0, 1, 1, 0}, 0]]
    {1, 4, 6, 7, 10}
Flatten[Position[{0, 1, 1, 0, 1, 0, 0, 1, 1, 0}, 1]]
    {2, 3, 5, 8, 9}

Flatten[Position[{0, 1, 1, 0, 1, 0, 0, 1, 1, 0}, 0]] - 1
    {0, 3, 5, 6, 9}
Flatten[Position[{0, 1, 1, 0, 1, 0, 0, 1, 1, 0}, 1]] - 1
    {1, 2, 4, 7, 8}

Multigrades集合の検証

2つの非零整数のdisijoint集合$A$および$B$がMultigradesとは以下の条件を満たす集合$A, B$が存在するときである。

Thue-Morse列を使って、検証0から$n$までの非零整数のdisijoint集合への分割を \begin{gather*} A_n=\{0\leq j<2^{n+1} \,|\, t_n=0\},\\ B_n=\{0\leq j<2^{n+1} \,|\, t_n=1\} \end{gather*} と定義する。

Thue-Morse列(3) morphism

$\Sigma$と$\Delta$をアルファベットとする。 射(morphism)とは、写像 $\psi: \Sigma^*\rightarrow\Delta^*$で \[ \psi(xy)=\psi(x)\psi(y),\qquad \text{word $x,y\in\Sigma^*$} \] を満たすものである。

$\Sigma=\Delta=\{0,1\}$として、 Thue-Morse morphism $\tau$を \begin{gather*} \tau(0) = 0 1,\\ \tau(1)= 10 \end{gather*} で定義する。

\begin{align*} \tau^0(0) &= 0,\\ \tau^1(0) &= 01,\\ \tau^2(0) &= \tau(01)=0110,\\ \tau^3(0) &=\tau(0110) =01101001,\\ \dots \end{align*} というようにして、Thue-Morse列 $t=(t_n)$ は \[ t=\lim_{n\rightarrow\infty}\tau^n(0) \] によって得られる。

ProuhetThueMorse[{0}, 3]
    {0, 1, 1, 0, 1, 0, 0, 1}

tm[0] := {0, 1};  
tm[1] := {1, 0};
SetAttributes[tm, Listable];

ProuhetThueMorse[lst_List, n_Integer] := Flatten[Nest[tm, lst, n]]