有理数が作る無限文字列についての考察
導入
$ 0 \in \mathbb{N} $とする。また、数列や文字列のインデックスは$ 0 $から始まるものとする。
$ r $を正の実数とし、$ r $ごとに定まる$ \mathrm{X}, \mathrm{A}, \mathrm{B} $の3文字からなる無限列$ S_r $を以下で定義する。
実際には$ \mathrm{A}, \mathrm{B} $の2文字からなる列ですが、「$ \mathrm{A} $であり同時に$ \mathrm{B} $である」項が発生することがあるため、そのような項を表す文字として$ \mathrm{X} $が導入されています。
集合$ A_r, B_r, C $を以下で定義する:
- $ A_r = \{ 1 \cdot n \mid n \in \mathbb{N} \} $ (この集合は$ r $に依存しない)
- $ B_r = \{ r \cdot n \mid n \in \mathbb{N} \} $
- $ C = A_r \cup B_r $
数列$ \{a_n\}_{n \in \mathbb{N}} $を$ C $の元を小さい方から並べたものとする。とくに、任意の$ r $に対して$ a_0 = 0 $である。
$ \mathrm{X}, \mathrm{A}, \mathrm{B} $の3文字からなる無限列$ S_r := \{S_{rn}\}_{n \in \mathbb{N}} $を以下で定義する:
任意の$ n \in \mathbb{N} $に対し、
- $ a_n \in A_r $かつ$ a_n \in B_r $であれば、$ S_{rn} = \mathrm{X} $
- $ a_n \in A_r $かつ$ a_n \not\in B_r $であれば、$ S_{rn} = \mathrm{A} $
- $ a_n \not\in A_r $かつ$ a_n \in B_r $であれば、$ S_{rn} = \mathrm{B} $
とする。
$ \{a_n\} $の定義から明らかに任意の$ n \in \mathbb{N} $に対して$ a_n \in C = A_r \cup B_r $なので、$ a_n \not\in A_r $かつ$ a_n \not\in B_r $が成り立つことはない。
これは Sturmian word の一般化である。Sturmian wordは$ r $が無理数であるときのみを対象にするのに対し、この記事では主に$ r $が有理数であるときを扱うので、Sturmian wordに関する直接の車輪の再発明ではない。
例
$ r = \phi = \frac{1+\sqrt{5}}{2} $のとき
$ A_r = \{ 0, 1, 2, 3, \cdots \}, B_r = \{ 0, \phi, 2\phi, 3\phi, \cdots \} $となります。$ C = A_r \cup B_r $を小さい順に並べると、
$ 0 = 0\phi, 1, \phi, 2, 3, 2\phi, 4, 3\phi, 5, \cdots $
と並びます。これらを記号に変換すると、
$ \mathrm{XABAABABA\cdots} $
となります。最初の$ \mathrm{X} $を除くと、 フィボナッチ列 と本質的に同じものになります。
![!FORMULA[45][-1682032487][0]](https://firebasestorage.googleapis.com/v0/b/mathlog-361213.appspot.com/o/uploads%2Fmathdown%2FFzYPEjKgOXFHnOrmmARB.png?alt=media)
$ S_{\phi} $
$ r = \frac{3}{2} $のとき
$ A_r = \{ 0, 1, 2, 3, \cdots \}, B_r = \{ 0 = \frac{0}{2}, \frac{3}{2}, 3 = \frac{6}{2}, \frac{9}{2}, \cdots \} $となります。$ C = A_r \cup B_r $を小さい順に並べると、
$ 0 = \frac{0}{2}, 1, \frac{3}{2}, 2, 3 = \frac{6}{2}, 4, \frac{9}{2}, 5, 6 = \frac{12}{2}, \cdots $
と並びます。これらを記号に変換すると、
$ \mathrm{XABAXABAX\cdots} $
となります。
![!FORMULA[51][-1561520343][0]](https://firebasestorage.googleapis.com/v0/b/mathlog-361213.appspot.com/o/uploads%2Fmathdown%2FNsohh2qmWPd5VcPv89sQ.png?alt=media)
$ S_{\frac{3}{2}} $
定義から明らかに、$ r $が有理数の時は周期性があり、「$ r $を既約分数で表した時の分子」に対応する位置が周期になります。
また、$ r $を既約分数で$ \frac{p}{q} $と書くと、$ S_r $の1周期分には$ \mathrm{X} $が最初に$ 1 $回、$ \mathrm{A} $が$ p - 1 $回、$ \mathrm{B} $が$ q - 1 $回現れます。
以下では、$ 1 \leq r \leq 2 $を満たす有理数$ r $についてのみ考えます。
正の有理数$ r $に対し、$ S_r^n $を$ S_r $のうち$ n + 1 $番目の$ \mathrm{X} $より前の部分とする。
$ S_r^n $は$ S_r $の$ n $周期分に相当する。
性質
$ r $を$ 1 $より大きい非整数の有理数とする。このとき、先頭以外の$ \mathrm{X} $の前の文字は$ \mathrm{A} $である。
$ r > 1 $から即座に従う。
任意の$ 1 \leq r \leq 2 $を満たす有理数$ r $に対し、$ r = 1 + \frac{1}{n} $を満たす$ n \in \mathbb{N} $が存在しないことと、$ S_r $は$ \mathrm{AA} $の並びを含むことは、同値である。
$ \mathrm{AA} $の並びを含む例
$ S_{\frac{5}{3}} = \mathrm{XABAABAXABAABA\cdots} $
$ S_{\frac{7}{5}} = \mathrm{XABABAABABAXABABAABABA\cdots} $
$ \mathrm{AA} $の並びを含まない例
$ S_{\frac{3}{2}} = \mathrm{XABAXABA\cdots} $
$ S_{\frac{5}{4}} = \mathrm{XABABABAXABABABA\cdots} $
$ r = 2 $の場合、$ S_2 = \mathrm{XAXAXA\cdots} $であることから定理は成り立つ。
$ r \neq 2 $で$ r = 1 + \frac{1}{n} $を満たす$ n \in \mathbb{N} $が存在する場合、$ 0 < k < n $を満たす任意の$ k \in \mathbb{N} $に対して$ k < rk < k + 1 $が成り立つことから明らかである。
それ以外の場合、鳩ノ巣原理から即座に従う。
$ r $を既約分数で$ \frac{p + q}{q} $とおき、$ q $を$ p $で割った商を$ a $とする。このとき、$ S_r^1 $の末尾は$ \mathrm{AABAB \cdots ABA} $である。ただし、この部分に$ \mathrm{B} $は$ a $回現れる。
$ S_r^1 $の末尾から考えることで、以下のことを示せばよいことがわかる:
任意の整数$ 1 < k \leq a $に対して、$ k < \frac{p + q}{q} \cdot k < k + 1 $が成り立つ。
これは$ a $の定義から$ \frac{1}{k + 1} < \frac{p}{q} < \frac{1}{k} $が成り立つことから即座にわかる。
$ \mathrm{AABAB \cdots ABA} $は$ S_{\frac{a + 1}{a}}^1 $の先頭に$ \mathrm{A} $を追加して$ \mathrm{X} $を$ \mathrm{AB} $に置き換えたものです。
このように、$ S_r $は後ろの部分を別の有理数から生成される列に「分離」できることがわかりました。
![!FORMULA[120][4340762][0]から!FORMULA[121][1928374364][0]を分離する](https://firebasestorage.googleapis.com/v0/b/mathlog-361213.appspot.com/o/uploads%2Fmathdown%2FBlvBIuNSF7jsmSmWUOrH.png?alt=media)
$ S_{\frac{8}{5}}^1 $から$ S_{\frac{2}{1}}^1 $を分離する
では、「分離」された残りの列はどうなるでしょう。次の定理が成り立ちます:
$ r $を既約分数で$ \frac{p + q}{q} $とおき、$ q $を$ p $で割った商を$ a $、余りを$ s $とする。このとき、もし$ s = 1, 2 $ならば次が成り立つ:
$ S_r^1 = T_{\frac{p + q - (a + 1)}{q - a}}^g T_{\frac{a + 1}{a}}^1 $
ただし
- $ g $は$ p + q - (a + 1) $と$ q - a $の最大公約数
- $ T_{\frac{p + q - (a + 1)}{q - a}}^g $は$ S_{\frac{p + q - (a + 1)}{q - a}}^g $の最初以外のの$ \mathrm{X} $を$ \mathrm{AB} $に変えたもの
- $ T_{\frac{a + 1}{a}}^1 $は$ S_{\frac{a + 1}{a}}^1 $の最初の$ \mathrm{X} $を$ \mathrm{AB} $に変えたもの
次のことを証明すればよい:
$ 0 \leq k \leq q - a $とする。このとき、$ \frac{p + q - (a + 1)}{q - a} \cdot k $の整数部分と$ \frac{p + q}{q} \cdot k $の整数部分は等しい。
以下でこれを証明する。
\begin{align*} & \frac{p + q}{q} - \frac{p + q - (a + 1)}{q - a} \\ =& \frac{(p + q)(q - a) - q(p + q - (a + 1))}{q(q - a)} \\ =& \frac{-ap + q}{q(q - a)} \cdots (\star) \end{align*}
である。ところで、$ q = ap + s $であるから、これを$ (\star) $に代入すると、
$ \frac{p + q}{q} - \frac{p + q - (a + 1)}{q - a} = \frac{s}{ q (q - a) } $
を得る。よって
$ \frac{p + q - (a + 1)}{q - a} + \frac{s}{ q (q - a) } = \frac{p + q}{q} $
であるから、$ k(p + q - (a + 1)) $に$ \frac{ks}{q} $を足した際に、$ q - a $の倍数を「踏むか越えない」ことを示せばよい。
(i) $ s = 1 $のとき
$ 0 < \frac{ks}{q} = \frac{k}{q} < 1 $であるから成り立つ。
(ii) $ s = 2 $のとき
$ p $と$ q $は互いに素なので少なくとも一方は奇数である。ところで、$ q = ap + s = ap + 2 $であるから$ p $が偶数ならば$ q $も偶数であり、$ r = \frac{p + q}{q} $が既約分数であることに矛盾する。したがって$ p $は奇数である。
ところで、
\begin{align*} & \frac{p + q - (a + 1)}{q - a} \\ =& \frac{p + (ap + s) - (a + 1)}{(ap + s) - a} \\ =& \frac{(ap + s - a) + (p - 1)}{ap + s - a} \\ =& \frac{(a(p - 1) + 2) + (p - 1)}{a(p - 1) + 2} (\because s = 2) \end{align*}
である。さて、$ p $が奇数であればこの分数は分母と分子がともに偶数であるため約分できる。したがって、この分数は任意の整数$ m $に対して区間$ \left(m - \frac{1}{(q - a)/2}, m \right) $に入ることはない。
よって、$ \frac{ks}{ q (q - a) } < \frac{2}{q - a} = \frac{1}{(q - a)/2} $より題意が示された。
さらなる一般化
定理4で「$ s = 1, 2 $のとき」を強調していますが、これは$ s = 3 $で反例が見つかったからです。
$ p + q $の値が最小の反例は$ p = 8, q = 5 $のケースで、このとき
\begin{eqnarray*} S_{\frac{13}{8}}^1 =& &\mathrm{XABAABABAABAABABAABA} \\ T_{\frac{11}{7}}^1 =& &\mathrm{XABAABABAABABAABA} \\ T_{\frac{2}{1}}^1 =& &\mathrm{ABA} \end{eqnarray*}
となり、文字列が一致しないことがわかります。また、数値の上でも
\begin{eqnarray*} \frac{13}{8} \cdot 5 =& & 8 + \frac{1}{8} \\ \frac{11}{7} \cdot 5 =& & 7 + \frac{6}{7} \\ \end{eqnarray*}
となり、整数部分は一致しません。
おわりに
最初に立てた予想が一般には成り立たないことが分かって落胆しましたが、それでも一部は成り立つので記事にしました。
ところで、最小の反例は$ p + q = 13 $ですが、某ゲームでは$ p + q = 12 $までしか出てきません。狙ったのでしょうか・・・？