コラッツ予想と parity sequence
先日OMCにて、コラッツ予想に関する自作の問題が出題されました(
OMCE022(E)
)。
このことを記念して、コラッツ予想の研究に役立つ(かもしれない) parity sequence というものを紹介します。これは実際に論文等でも使われている概念です(
参考文献
)。英語で書くとなんだか難しそうですが、日本語で言うなら「偶奇列」でしょうか。これなら簡単そうですね。実際、概念自体はいたってシンプルなものです。
コラッツ予想について
この記事を見ている方であればコラッツ予想についてはご存じのことと思いますが、一応書いておきます。以下、自然数は正の整数のこととし、自然数全体の集合を$\mathbb N$とします。
写像 $T : \mathbb N \to \mathbb N$ を
$$ T(n) = \begin{cases}
\frac{3n+1}{2} & (\text{$n$ が奇数})\\
\frac{n}{2} & (\text{$n$ が偶数})\\
\end{cases}$$
で定める。与えられた自然数に$T$を施すことを コラッツ操作 という。
奇数に対しては $T(n) = 3n+1$ とすることもありますが、$3n+1$ は必ず偶数となるので、もう一度操作すると $\displaystyle \frac{3n+1}{2}$ となります。これを最初からまとめて1つの操作としたのが上の定義です。
例えば自然数$17$に対してコラッツ操作を繰り返し行うと
$$ 17 \to 26 \to 13 \to 20 \to 10 \to 5 \to 8 \to 4 \to 2 \to 1 \to 2 \to 1 \to \cdots$$
となります。
上の例では最終的に1,2の繰り返しになりましたが、どんな自然数から始めてもそうなるというのがコラッツ予想です。
任意の自然数に対し、コラッツ操作を有限回行うと$1$になる。
2026年2月6日現在、この予想は証明も反証もされていません。
parity sequence
おさらいが済んだところで、早速 parity sequence について見ていきましょう。先ほどコラッツ操作の例
$$ 17 \to 26 \to 13 \to 20 \to 10 \to 5 \to 8 \to 4 \to 2 \to 1 \to 2 \to 1 \to \cdots$$
を見ましたが、ここで現れたそれぞれの数について奇数を$1$,偶数を$0$に対応させると
$$ 1,0,1,0,0,1,0,0,0,1,0,1,\cdots$$
という数列ができます。最後は$0,1$の繰り返しになりますね。このようにして得られる数列が parity sequence です。
一般に定義しましょう。
自然数$n$に対し、コラッツ操作を$k$回施して得られる数を$a_k$とする($k=0,1,2,...$)。さらに数列$\{b_k\}_{k=0,1,...}$を、$a_k$が奇数なら$b_k=1$, $a_k$が偶数なら$b_k=0$として定める。このときの数列$\{b_k\}_{k=0,1,...}$を、$n$の parity sequence という。
いくつか例を書いておきます。
| $n$ | parity sequence |
|---|---|
| $1$ | $1,0,1,0,\ldots$ |
| $2$ | $0,1,0,1,0,\ldots$ |
| $3$ | $1,1,0,0,0,1,0,1,0,\ldots$ |
| $4$ | $0,0,1,0,1,0,\ldots$ |
| $5$ | $1,0,0,0,1,0,1,0,\ldots$ |
| $6$ | $0,1,1,0,0,0,1,0,1,0,\ldots$ |
| $7$ | $1,1,1,0,1,0,0,1,0,0,0,1,0,1,0,\ldots$ |
| $8$ | $0,0,0,1,0,1,0,\ldots$ |
| $9$ | $1,0,1,1,1,0,1,0,0,1,0,0,0,1,0,1,0,\ldots$ |
| $10$ | $0,1,0,0,0,1,0,1,0,\ldots$ |
ちなみに$27$の parity sequence は
$$ 1,1,0,1,1,1,1,1,0,1,0,1,1,0,1,1,1,0,1,1,1,1,0,1,0,0,1,1,1,0,1,1,0,1,1,1,1,1,1,0,0,1,1,1,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,1,1,1,0,0,0,0,1,0,0,0,1,0,1,0,\ldots$$
です。
もしコラッツ予想が正しければ、どんな自然数に対しても parity sequence は有限項を除いて $0,1$ の繰り返しになります。
コラッツ操作を1回行うと、parity sequence の初項が消えます。例えば$6$にコラッツ操作を3回行うと $6 \to 3 \to 5 \to 8$ となりますが、それぞれの parity sequence を見ると、項が順々に消えていることが見て取れます。
初期値の一意性
parity sequence の最も重要な性質は、以下のものではないかと思います。
2つの自然数$m,n$の parity sequence が一致するならば、$m=n$ である。
すなわち、parity sequence から元の自然数が(もし存在すれば)一意に定まります。
証明の準備として以下を示しましょう。
2つの自然数$m,n$の parity sequence の最初の$k$項が等しいならば、$m \equiv n \ (\mathrm{mod} \ 2^k)$ が成り立つ。
上で添え字を$0$から始めてしまったため紛らわしいですが、数列$\{ b_k \}_{k=0,1,\ldots}$の「最初の$k$項」とは $b_0, b_1, \ldots, b_{k-1}$ のことを指します。
帰納法により示す。$k=1$のときは、もし初項が共に$0$なら$m,n$は共に偶数、初項が共に$1$なら$m,n$は共に奇数なので、いずれの場合も $m \equiv n \ (\mathrm{mod} \ 2)$ が成り立つ。
ある$k$で正しいとして、$k+1$でも成り立つことを示す。$m,n$の parity sequence の最初の$k+1$項が等しいとすると、特に初項が等しいので$m,n$の偶奇は一致する。
- $m,n$が共に偶数のとき
$m,n$にコラッツ操作を1回行うと、それぞれ$\disp \frac m2, \frac n2$となる。$\disp \frac m2, \frac n2$の parity sequence はそれぞれ$m,n$の parity sequence の初項を除いたものであるから、最初の$k$項が一致する。よって帰納法の仮定より
$$ \frac m2 \equiv \frac n2 \ (\mathrm{mod} \ 2^k)$$
であり、両辺を2倍して
$$ m \equiv n \ (\mathrm{mod} \ 2^{k+1})$$
を得る。
- $m,n$が共に奇数のとき
同様の議論により、
$$ \frac {3m+1}2 \equiv \frac {3n+1}2 \ (\mathrm{mod} \ 2^k)$$
が得られる。これを変形して
$$ 3m+1 \equiv 3n+1 \ (\mathrm{mod} \ 2^{k+1})$$
$$ 3m \equiv 3n \ (\mathrm{mod} \ 2^{k+1})$$
$$ m \equiv n \ (\mathrm{mod} \ 2^{k+1})$$
を得る。
ちなみに、この記事では証明しませんが、補題2は逆も成り立ちます。
補題2から命題1はすぐに従います。
2つの自然数$m,n$の parity sequence が一致するとする。このとき補題より、任意の自然数$k$に対して
$$ m \equiv n \ (\mathrm{mod} \ 2^k)$$
が成り立つ。すなわち $m-n$ は$2$で何回でも割り切れるので、$m-n=0$ となるしかない。
これで初期値の一意性が示せました。例えば、parity sequence が $1,0,1,0,1,0,\ldots$ となるような自然数は$1$しかない、ということになりますね。
応用例を1つ紹介します。
parity sequence が $1,0,0,1,0,0,\ldots$(周期$3$で循環) であるような自然数は存在しないことを示せ。
存在すると仮定して、それを$n$とおく。$n$にコラッツ操作を3回施すと、parity sequence は最初の3項が消え、再び $1,0,0,1,0,0,\ldots$ という数列になる。よって、初期値の一意性により、$n$にコラッツ操作を3回施すと再び$n$になる。実際に操作を行うと
$$ n \to \frac{3n+1}{2} \to \frac{3n+1}{4} \to \frac{3n+1}{8}$$
となるので、
$$ \frac{3n+1}{8} = n$$
が成り立つ。これを解くと $\disp n = \frac 15$ となり、$n$が自然数であることに矛盾。
ここで、$\disp \frac 15$を形式的に奇数だと思えば、コラッツ操作により $\disp \frac 15 \to \frac 45$ となります。さらに$\disp \frac 45$を偶数だと思えば$\disp \frac 45 \to \frac 25$, $\disp \frac 25$を偶数だと思えば$\disp \frac 25 \to \frac 15$となって、「$\disp \frac 15$の parity sequence は $1,0,0,1,0,0,\ldots$」という主張がなんとなく正当化されそうな感じがします。これに関しては後で触れます。
さてここで、ある自然数$n$の parity sequence が
$$ *,*,\ldots,*,1,0,1,0,\ldots$$
のように、有限項を除いて$1,0$の繰り返しになったとしましょう。このとき、$n$にコラッツ操作を何回か施すことで parity sequence が $1,0,1,0,\ldots$ となります。これはすなわち、$n$にコラッツ操作を何回か施すと$1$になる、ということを意味します。
というわけで、先ほど述べた
$$ \text{コラッツ予想が真 $\Longrightarrow$ どんな自然数に対しても parity sequence は有限項を除いて 0,1 の繰り返しになる}$$
という話は、逆も成り立ちます。
以下は同値。
- コラッツ予想が真。
- どんな自然数に対しても parity sequence は有限項を除いて $0,1$ の繰り返しになる。
個人的に気になること
もしコラッツ予想が正しければ、自然数は2つのグループに分けられます。すなわち、parity sequence の $0,1$ の繰り返しの部分において、$0$が奇数番目、$1$が偶数番目の項にあるか、$0$が偶数番目、$1$が奇数番目の項にあるかです。これは、$1$に到達するまでにコラッツ操作を行う回数が奇数か偶数かで分類するのと同じことです。
操作回数が偶数: $1,4,5,6,11,14,15,16,\ldots$
操作回数が奇数: $2,3,7,8,9,10,12,13,\ldots$
これは何か法則性があるのでしょうか……？
有理数への拡張
ここからは、話を有理数に拡張して考えます。コラッツ予想から離れてしまうように見えるかもしれませんが、広い視点から見ることで初めて気づけることというのも数学ではしばしばあるので、何か役に立つかもしれません。また、拡張することによって、サイクルに関して気持ちの良い結果が得られます。
さて、有理数に拡張すると言っても、まず有理数に対して偶奇が定義されません。そこで、範囲を制限して以下のような集合の中で考えます。
分母が奇数であるような分数で表せる有理数全体の集合を $\mathbb Q_{\text{奇}}$ とする。すなわち
$$ \mathbb Q_{\text{奇}} = \left\{ \frac mn \ \middle| \ \text{$m,n \in \mathbb Z$, $n$ は奇数} \right\}$$
と定める。$r \in \mathbb Q_{\text{奇}}$ が$\disp \frac{\text{奇数}}{\text{奇数}}$の形の分数で表せるなら$r$は奇数、$\disp \frac{\text{偶数}}{\text{奇数}}$の形の分数で表せるなら$r$は偶数であるという。
このようにして、$\mathbb Q_{\text{奇}}$ の範囲では偶奇の概念が定まります。ここで、偶奇は well-defined です。すなわち、ある有理数が $\disp \frac{\text{奇数}}{\text{奇数}}$ の形でも $\disp \frac{\text{偶数}}{\text{奇数}}$ の形でも表せるということはありません。
$r \in \mathbb Q_{\text{奇}}$ とし、
$$ r = \frac ab = \frac cd \qquad (\text{$a,b,d$ は奇数、$c$ は偶数})$$
と表せるとする。このとき
$$ ad=bc$$
となるが、左辺は奇数、右辺は偶数なので矛盾。
自然数 $n$ は $\disp \frac n1$ と表せるので、$\mathbb N \subset \mathbb Q_{\text{奇}}$ です。$\mathbb N$ における奇数は $\mathbb Q_{\text{奇}}$ においても奇数、$\mathbb N$ における偶数は $\mathbb Q_{\text{奇}}$ においても偶数となるので、両者の偶奇の概念は矛盾しません。
$\mathbb Q_{\text{奇}}$ の範囲内で足し算、引き算、掛け算をすることができます。さらに、通常の計算と同じように以下の法則が成り立ちます。
$$ \begin{matrix}
\text{(奇数)$+$(奇数)$=$(偶数)} & \ & \text{(奇数)$\times$(奇数)$=$(奇数)} \\
\text{(偶数)$+$(偶数)$=$(偶数)} & \ & \text{(偶数)$\times$(偶数)$=$(偶数)} \\
\text{(奇数)$+$(偶数)$=$(奇数)} & \ & \text{(奇数)$\times$(偶数)$=$(偶数)} \\
\end{matrix}$$
これらは一つ一つは難しくありませんが、書くのが面倒なので証明は省略します。
上で定義した $\mathbb Q_{\text{奇}}$ は、環$\mathbb Z$の素イデアル$(2)$による局所化$\mathbb Z_{(2)}$に他なりません。また、ある環の偶奇を定義するというのは$\mathbb Z/2\mathbb Z$への全射環準同型を指定することと同じです。$\pi : \mathbb Z \to \mathbb Z/2\mathbb Z$ を自然な全射とします。このとき素イデアル$(2)$の補集合の元(すなわち$\mathbb Z$の奇数)は可逆元に移るので、局所化$\mathbb Z_{(2)}$から$\mathbb Z/2\mathbb Z$への全射環準同型が誘導されます。これにより定まる偶奇が上記のものです。
また、$\mathbb Q_{\text{奇}}$ の範囲で「偶数を2で割る」という操作が可能です。
コラッツ操作と parity sequence
$\mathbb Q_{\text{奇}}$ において偶奇が定義され、自然数と同じように扱えることが分かったので、コラッツ操作を定義することができます。
写像 $T : \mathbb Q_{\text{奇}} \to \mathbb Q_{\text{奇}}$ を
$$ T(r) = \begin{cases}
\frac{3r+1}{2} & (\text{$r$ が奇数})\\
\frac{r}{2} & (\text{$r$ が偶数})\\
\end{cases}$$
で定める。与えられた$\mathbb Q_{\text{奇}}$の元に$T$を施すことを コラッツ操作 という。
例えば、$\disp \frac 15$にコラッツ操作を繰り返し行うと
$$ \frac 15 \to \frac 45 \to \frac 25 \to \frac 15 \to \frac 45 \to \cdots$$
となります。他には例えば
$$ -\frac{13}{27} \to -\frac 29 \to -\frac 19 \to \frac 13 \to 1 \to \cdots$$
のように負の数から始めて1に到達したり、
$$ -\frac{73}{17} \to -\frac{101}{17} \to -\frac{143}{17} \to -\frac{206}{17} \to -\frac{103}{17} \to -\frac{146}{17} \to -\frac{73}{17}$$
のように負の数のみで循環したりもします。
parity sequence もまったく同様に定義することができます。例えば$\disp \frac 15$の parity sequence は
$$ 1,0,0,1,0,0,\ldots$$
となります。
初期値の一意性も同じ証明によって示すことができます。
2つの有理数$r,s \in \mathbb Q_{\text{奇}}$の parity sequence が一致するならば、$r=s$ である。
$\mathbb Q_{\text{奇}}$ で $\mathrm{mod}$ を使って良いのか？と思うかもしれませんが、この場合は大丈夫です。詳細は省略します。
$\mathbb Q_{\text{奇}}$におけるサイクル
以下、コラッツ操作$T$を$n$回施す写像を$T^n$で表します。ここでは$\mathbb Q_{\text{奇}}$におけるサイクルに着目します。
有理数$r \in \mathbb Q_{\text{奇}}$と自然数$n$が$T^n(r)=r$を満たすとき、$(r,T(r),T^2(r),\ldots,T^{n-1}(r))$を長さ$n$のサイクルと呼ぶ。
「ループ」と呼ぶこともありますが、論文などではサイクルと呼ぶのが一般的なようです。
これまでに見たように、例えば$(1,2)$や$\disp \left( \frac 15, \frac 45, \frac 25 \right)$はサイクルです(それぞれ長さ2,3)。また、初期値の一意性から、例えば(奇数、偶数、偶数)の形のサイクルは$\disp \left( \frac 15, \frac 45, \frac 25 \right)$しかありません。
なお、定義に従えば$\disp \left( \frac 15, \frac 45, \frac 25, \frac 15, \frac 45, \frac 25 \right)$もサイクルになります。このようなサイクルを認めるかどうかは文献によると思いますが、ここでは認めることにします。
さて、$r \in \mathbb Q_{\text{奇}}$がサイクルに含まれるならば、$r$の parity sequence は初項から循環します。では逆に、初項から循環する parity sequence が与えられたら、対応する有理数を見つけられるでしょうか？
以降の議論を正確に述べるため、1つ言葉を準備します。
非負整数で添え字づけられた数列で各項が$0$または$1$であるものを、単に無限01列と呼ぶ。
実は、以下が成り立ちます。
$\{b_k\}_{k=0,1,\ldots}$を初項から循環する無限01列とすると、parity sequence が$\{b_k\}_{k=0,1,\ldots}$であるような$r \in \mathbb Q_{\text{奇}}$が一意に存在する。
証明はだいぶややこしいので、無理に読まなくてもいいと思います。
$r$を見つけるには、先ほど$1,0,0,1,0,0,\ldots$から$\disp \frac 15$を得たように方程式を立てて解けばよいのですが、面倒なのでここでは天下り的に与えてしまいます。
初期値の一意性から、一意であることはOK。存在を示せばよい。もしすべての$k$で$b_k=0$なら、$r=0$とすればよい。以下、$b_k=1$となる$k$が存在するとする。
$\{b_k\}$は初項から循環するので、ある自然数$l$が存在して、任意の非負整数$k$に対して$b_{k+l}=b_k$が成り立つ。$b_k=1$であるような$k$を小さい順に$k_1,k_2,\ldots$とする。このうち$l-1$以下のものを$k_1, \ldots, k_m$とすれば、周期性より、任意の自然数$i$に対して
$$ k_{i+m}=k_i+l$$
が成り立つ。ここで
$$ r = \frac{\sum_{i=1}^{m}\cdot 2^{k_i} \cdot 3^{m-i}}{2^l-3^m}$$
とおく。分母は奇数なので$r \in \mathbb Q_{\text{奇}}$である。$r$の parity sequence を$\{ c_k \}_{k=0,1,\ldots}$とおく。
$r$の分子は2でちょうど$k_1$回割り切れるので、$r$にコラッツ操作を施すと、まず$2$で割るという操作が$k_1$回行われ、奇数になる。したがって$c_0=\cdots = c_{k_1-1} = 0, \ c_{k_1}=1$であり、これは$b_0,\ldots, b_{k_1}$に一致する。
$r$を$2$で$k_1$回割ると
$$ T^{k_1}(r) = \frac{\sum_{i=1}^{m} 2^{k_i-k_1} \cdot 3^{m-i}}{2^l-3^m}$$
となる。以下、任意の自然数$N$に対して
$$ T^{k_N}(r) = \frac{\sum_{i=N}^{m+N-1} 2^{k_i-k_N} \cdot 3^{m+N-1-i}}{2^l-3^m}$$
が成り立つことを帰納法によって示す。また同時に、$c_0,\ldots ,c_{k_N}$が$b_0, \ldots, b_{k_N}$に一致することを示す。$N=1$のときはすでに示した。
ある$N$で成り立つとする。このとき
$$ T^{k_N}(r) = \frac{\sum_{i=N}^{m+N-1}\cdot 2^{k_i-k_N} \cdot 3^{m+N-1-i}}{2^l-3^m} = \frac{3^{m-1} + \sum_{i=N+1}^{m+N-1} 2^{k_i-k_N} \cdot 3^{m+N-1-i}}{2^l-3^m}$$
は奇数なので、コラッツ操作を行うと
$$ \begin{aligned} T^{k_N+1}(r) &= \left( \frac{3^{m} + \sum_{i=N+1}^{m+N-1} 2^{k_i-k_N} \cdot 3^{m+N-i}}{2^l-3^m} +1 \right) \cdot \frac 12\\
&= \left( \frac{2^l + \sum_{i=N+1}^{m+N-1} 2^{k_i-k_N} \cdot 3^{m+N-i}}{2^l-3^m} \right) \cdot \frac 12\\
&= \frac{2^{l-1} + \sum_{i=N+1}^{m+N-1} 2^{k_i-k_N-1} \cdot 3^{m+N-i}}{2^l-3^m}
\end{aligned}$$
となる。ここで $l= k_{N+m}-k_N$ を用いれば、
$$ T^{k_N+1}(r) = \frac{\sum_{i=N+1}^{m+N} 2^{k_i-k_N-1} \cdot 3^{m+N-i}}{2^l-3^m}$$
と表せる。分子は$2$でちょうど$k_{N+1}-k_N-1$回割り切れるので、$T^{k_N+1}(r)$にコラッツ操作を施すと、$2$で割るという操作が$k_{N+1}-k_N-1$回行われ、奇数になる。したがって$c_{k_N+1}=\cdots = c_{k_{N+1}-1} = 0, \ c_{k_{N+1}}=1$であり、これは$b_{k_N+1},\ldots, b_{k_{N+1}}$に一致する。
$T^{k_N+1}(r)$を$2$で$k_{N+1}-k_N-1$回割ると
$$ T^{k_{N+1}}(r) = \frac{\sum_{i=N+1}^{m+N} 2^{k_i-k_{N+1}} \cdot 3^{m+N-i}}{2^l-3^m}$$
となり、$N+1$でも成り立つことが言えた。
以上から、帰納法により、$r$の parity sequence は$\{b_k\}$となる。
(もっと良い証明方法があるかもしれません……)
したがって、考え得るすべての偶奇パターンに対し、それに当てはまるサイクルが一意に存在します。
ここで一旦話を元のコラッツ予想に戻します。自然数の範囲ではサイクルは$(1,2)$とその繰り返ししか見つかっておらず、他のサイクルが存在するかどうかは分かっていません。ここで、上の証明から、$\mathbb Q_{\text{奇}}$のサイクルに含まれる元は
$$ \frac{\sum_{i=1}^{m}\cdot 2^{k_i} \cdot 3^{m-i}}{2^l-3^m}$$
の形をしています($k_1,\ldots,k_m$は単調増加な非負整数列)。よって、自然数におけるサイクルを探す問題は、上の形の分数のうち約分されて自然数になるものを探す問題と同じになります。まあ、結局難しい問題であることに変わりはないのですが……。
さて、有理数の話に戻ります。命題5はさらに、有限項を除いて循環する無限01列の場合に拡張できます。以下の簡単な補題を用います。
$r \in \mathbb Q_{\text{奇}}$の parity sequence を$\{ b_k \}_{k=0,1,\ldots}$とおく。このとき
$2r \in \mathbb Q_{\text{奇}}$ であり、$2r$の parity sequence は
$$ 0,b_0,b_1,b_2, \ldots$$
となる。$\disp \frac{2r-1}{3} \in \mathbb Q_{\text{奇}}$であり、$\disp \frac{2r-1}{3}$の parity sequence は
$$ 1,b_0,b_1,b_2 \ldots$$
となる。
実際に計算すればわかる。
これにより、parity sequence の先頭に自由に項を付け足すことができます。
$\{b_k\}_{k=0,1,\ldots}$を有限項を除いて循環する無限01列とすると、parity sequence が$\{b_k\}_{k=0,1,\ldots}$であるような$r \in \mathbb Q_{\text{奇}}$が一意に存在する。
$\{b_k\}$から最初の有限項を除いて初項から循環するようにすれば、命題5によって対応する有理数が存在する。その有理数に補題6の変換を何回か施して、元の$\{b_k\}$を復元すればよい。
さて、ここまでサイクルについて考えてきましたが、実はこれまでに調べられている範囲では、コラッツ操作によってサイクルに到達しない$\mathbb Q_{\text{奇}}$の元は見つかっていません。これも未解決問題です。
任意の$r \in \mathbb Q_{\text{奇}}$に対し、数列$\{T^n(r)\}_{n=0,1,\ldots}$は高々有限項を除いて循環する。
この予想とコラッツ予想は微妙な関係で、一方が証明または否定されたからといって、もう一方が証明または否定されるとは限りません。
別のアプローチ
上では与えられた無限01列に対してそれを parity sequence に持つ数を探す問題を考えましたが、この問題に対する別のアプローチを紹介します。
突然ですが、
$$ r = -\frac{2^3}{3} - \frac{2^4}{3^2} - \frac{2^6}{3^3}$$
という数を考えます。$r$にコラッツ操作を繰り返し施すと
$$ \begin{aligned}
r&=-\frac{2^3}{3} - \frac{2^4}{3^2} - \frac{2^6}{3^3}\ (\text{偶})\\
&\to -\frac{2^2}{3} - \frac{2^3}{3^2} - \frac{2^5}{3^3}\ (\text{偶})\\
&\to -\frac{2}{3} - \frac{2^2}{3^2} - \frac{2^4}{3^3}\ (\text{偶})\\
&\to -\frac{1}{3} - \frac{2}{3^2} - \frac{2^3}{3^3}\ (\text{奇})\\
&\to - \frac{1}{3} - \frac{2^2}{3^2}\ (\text{奇})\\
&\to - \frac{2}{3}\ (\text{偶})\\
&\to - \frac{1}{3}\ (\text{奇})\\
&\to 0 \to 0 \to \cdots\\
\end{aligned}$$
となるので、$r$の parity sequence は
$$ 0,0,0,1,1,0,1,0,0,\ldots$$
となります。この数列と元の$r$の関係が分かるでしょうか。parity sequence を $\{b_k\}_{k=0,1,\ldots}$ とおくと、$b_3 = b_4 = b_6 = 1$ で、他の$b_k$は$0$となっています。この$3,4,6$という数は、$r$の定義に現れる分数の分子の指数に一致しています。
このようにして、$1$が有限回しか現れない無限01列に対しては、対応する有理数を簡単に作ることができます。
$k_1< k_2<\cdots< k_n$を単調増加な非負整数列とする。このとき
$$ r = -\sum_{i=1}^n \frac{2^{k_i}}{3^i}$$
の parity sequence を $\{b_k\}_{k=0,1,\ldots}$とすると、$b_{k_1} = \cdots = b_{k_n} = 1$であり、他の$b_k$はすべて$0$となる。
これを$1$が有限個でない場合に拡張できないでしょうか？例えば$1$の parity sequence は $1,0,1,0,\ldots$なので、もし同様の結果が成り立つとすれば
$$ 1 = -\frac{1}{3} - \frac {2^2}{3^2} - \frac{2^4}{3^3} - \frac{2^6}{3^4} - \cdots$$
となるはずですが、右辺は公比$\disp \frac 43$の無限等比級数の和なので発散してしまいます。これはうまくいきませんね。
しかし、必ずしもうまくいかないわけではありません。例えば parity sequence が $1,1,0,1,1,0,\ldots$(周期3で繰り返し) となる有理数を考えると
$$ - \frac 13 - \frac {2}{3^2} - \frac {2^3}{3^3} - \frac{2^4}{3^4} - \frac{2^6}{3^5} - \frac{2^7}{3^6} - \cdots$$
となりますが、2項ごとにまとめれば
$$ -\left( \frac 13 + \frac 2{3^2} \right) - \left( \frac{2^3}{3^3} + \frac {2^4}{3^4} \right) - \left( \frac{2^6}{3^5} + \frac {2^7}{3^6} \right) - \cdots$$
となり、これは公比$\disp \frac 89$の無限等比級数となっています。これは収束し、その和は
$$ -\left( \frac 13 + \frac 2{3^2} \right) \cdot \frac{1}{1-\frac 89} = - \frac 59 \cdot 9= -5$$
となります。実際、$(-5,-7,-10)$はサイクルをなすので、狙い通りの parity sequence を持つ有理数が得られました。
整数論に詳しい方であれば、どうすればこのアイデアがよりうまくいくのか、見当がついているのではないでしょうか。というわけで、さらに拡張していきます。
2進整数環への拡張
最後に2進整数環$\mathbb Z_2$への拡張について少し触れておきます。2進整数環について説明すると長くなってしまうので、知っている方向けに書きます。
自然な全射 $\mathbb Z_2 \to \mathbb Z / 2 \mathbb Z$ があるので、$\mathbb Z_2$には自然に偶奇の概念が定まります。これにより、$\mathbb Z_2$におけるコラッツ操作が定義され、同時に parity sequence も定義されます。さらに$\mathbb Z_2$には$\mathrm{mod} \ 2^k$ ($k=1,2,\ldots$) の概念が自然に定まり、初期値の一意性も同様に示すことができます。
なお、$\mathbb N \subset \mathbb Q_{\text{奇}} \subset \mathbb Z_2$ なので、これは確かにこれまでの話の拡張になっています。
$\mathbb Z_2$に拡張することにより、先ほどのアイデアがいつでも上手くいくようになります。
$k_1< k_2< k_3< \cdots$ を単調増加な非負整数列(有限で終わっても良い)とする。このとき$\mathbb Z_2$の元$\alpha$を
$$ \alpha = -\sum_{i \geq 1}\frac{2^{k_i}}{3^i}$$
で定めると、$\alpha$の parity sequence $\{ b_k \}_{k=0,1,\ldots}$ は $b_{k_i} = 1$ ($\forall i$) かつそれ以外の$k$については $b_k=0$ を満たす。
任意の$\mathbb Z_2$の元に対して parity sequence が定まり、また任意の無限01列に対してそれを parity sequence とする$\mathbb Z_2$の元が存在します。したがって、$\mathbb Z_2$の元と無限01列が1対1に対応することになります。
$\mathbb Z_2$の元に対してその parity sequence を対応させる写像は、$\mathbb Z_2$ から無限01列全体の集合への全単射を与える。
というわけで、初期値の一意性を保ったままコラッツ操作を拡張するのはこれが限界と言えるでしょう。
サイクルについては、上で見たように、$\mathbb Q_{\text{奇}}$で尽くされています。ちゃんと書くと以下の通り。
$\alpha \in \mathbb Z_2$ に対してコラッツ操作を繰り返してサイクルに到達するならば、$\alpha \in \mathbb Q_{\text{奇}}$である。
$\alpha$ に対してコラッツ操作を繰り返してサイクルに到達するとすると、$\alpha$ の parity sequence は高々有限項を除いて循環する。命題7より、その parity sequence を持つような有理数$r \in \mathbb Q_{\text{奇}}$が存在するが、初期値の一意性より $\alpha = r$ である。
逆に言えば、
$\mathbb Z_2 \setminus \mathbb Q_{\text{奇}}$ の元にコラッツ操作を繰り返し施してもサイクルには到達しない。
とも言えます。
$\mathbb Z_2$に拡張したからといって何が分かるということも(今のところ)ありませんが、無限01列と1対1に対応するいうのがやはり気持ちいいですね。
終わりに
というわけで、parity sequence の紹介記事でした。parity sequence の意義を一言で言うなら、「見方を変えることができる」ということでしょうか。例えば自然数$3$の parity sequence は
$$ 1,1,0,0,0,1,0,1,0,\ldots$$
でした。初期値の一意性より、この数列から$3$を復元することができます。したがって、この数列は$3$という自然数と同等の情報を持っていると言えます。$3$という数をいくら眺めていても、コラッツ操作でどのように変化していくのかはわかりませんが、parity sequence を見ればある程度は分かります。逆に parity sequence を見ても、対応する自然数が$3$の倍数かどうか、などはすぐには分かりません。このように、同じものでも見方によって見えやすい部分と見えにくい部分とがあります。なので、見方を変えるということは、問題解決のための有効な手段となり得るのです。
とはいえ、単に見方を変えるだけでは意味がありません。見方を変えることによって新しいことに気づいたり、これまでにないアプローチを思いついたりして初めて意味があるというものです。皆さんは何か気づいたことはありますか？
ではまた
