[自由研究]Knuthの代数:フィボナッチ数に関する積について
こんにちは,itouです.
導入
Zeckendorfの定理というものがあります.
任意の正整数$n$は以下のように一意に表示できる.
\begin{align}
n=\sum_{i=0}^{k}F_{c_i}(c_i\geq2)
\end{align}
ただし$F_0=0,F_1=1,F_{n+1}=F_n+F_{n-1}(n\geq 1)$,$c_{i+1}> c_i+1$.
すなわち任意の正整数は連続しないフィボナッチ数の和で表示できます.Knuthは以下のことを示しました.
$F_n$を$F_0=0,F_1=1,F_{n+1}=F_n+F_{n-1}$で生成される数列として,正整数$a,b$を
\begin{align}
a=\sum_{i=0}^{k}F_{c_i}(c_i\geq 2),b=\sum_{j=0}^{l}F_{d_j}(d_j\geq 2)
\end{align}
とゼッケンドルフ表現したとき,二項演算$a\circ b$を次のように定める.
\begin{align}
a\circ b=\sum_{i=0}^{k}\sum_{j=0}^{l}F_{c_i+d_j}
\end{align}
このとき,二項演算$\circ$は結合法則を満たす.
非常に非自明な結果です!Knuthはゼッケンドルフ表示の性質を調べることでこれを示しました([1])が,P.Arnouxは剰余環$\mathbb Z[X^2-X-1]$を用いたより簡略化された証明を与えました.([2])
また,この積は$\phi$を黄金数として
\begin{align}
a\circ b=3ab-a\lfloor \frac{b+1}{\phi^2} \rfloor-b\lfloor \frac{a+1}{\phi^2} \rfloor
\end{align}
という表示があります.
この演算についてはさらなる一般化が調べられています.
一般の線形漸化式への一般化は[3],Knuth積のfloor関数表示の類似については[4]にまとめられています.
私がこの積に興味を持ったのは友人Tが紹介してくれたからです.Ｔは次の示唆をしました.
「Knuth積は結合的だが単位的でない.和の取り方を変えれば単位的な積にできるのではないか」
つまり,以下のように定義します.
$F_n$を$F_0=0,F_1=1$のフィボナッチ数列として,整数$a,b$を
\begin{align}
a=\sum_{i=0}^{k}F_{c_i}(c_i\geq 2),b=\sum_{j=0}^{l}F_{d_j}(d_j\geq 2)
\end{align}
とゼッケンドルフ表現したとき,二項演算$a\circ b$を次のように定める.
\begin{align}
a\circ b=\sum_{i=0}^{k}\sum_{j=0}^{l}F_{c_i+d_j-2}
\end{align}
このとき,二項演算$\circ$は可換である.
インデックスを$-2$しておくことで1が単位元となってくれます.つまり,
すべての正整数$a$について,
$a\circ 1=1 \circ a=a$
たとえば以下のように計算します.
\begin{align} &(6\circ14)\circ19=74\circ19=1210\\ &6\circ(14\circ19)=6\circ231=1210 \end{align}
こうすると単位的かつ結合的な積になる!...と思ったのですが,この積は常に結合的とは限りません.
\begin{align} &(2\circ4)\circ4=7\circ4=25\\ &2\circ(4\circ4)=2\circ15=24 \end{align}
この反例を見つけたときはかなりがっかりしたのですが,多くの場合で結合法則が成立することは事実です.もう少し調べると,Tが以下のような予想を得ました.
後のために,以下のように再定義します.
$F_n$を$F_0=1,F_1=2,F_{n+2}=F_n+F_{n+1}$で生成される数列として,整数$a,b$を
\begin{align}
a=\sum_{i=0}^{k}F_{c_i}(c_i\geq 0),b=\sum_{j=0}^{l}F_{d_j}(d_j\geq 0)
\end{align}
とゼッケンドルフ表現したとき,二項演算$a\circ b$を次のように定める.
\begin{align}
a\circ b=\sum_{i=0}^{k}\sum_{j=0}^{l}F_{c_i+d_j}
\end{align}
このとき,二項演算$\circ$は可換である.
以下,このずらしたフィボナッチ数列を$F_n$とし，ゼッケンドルフ表現もこちらの数列に合わせます.
Tが以下の予想を見つけました.
「ゼッケンドルフ表現に$F_0,F_1$が含まれないような正整数」全体の集合を$\mathbb T$とおくと,任意の$a,b,c\in \mathbb T$について
\begin{align}
(a\circ b)\circ c=a\circ (b\circ c)
\end{align}
さらに,任意の$a,b\in \mathbb T$,任意の正整数$n\in\mathbb Z$について
\begin{align}
(a+b)\circ n=a\circ n+b\circ n
\end{align}
実験を行うと,他にも予想が生えてきます.この記事では,我々が得た予想を紹介します.
conjectures
\begin{align}
f(n)=\lfloor \frac{n+1}{\phi^2}\rfloor
\end{align}
とする.
単位的Knuth積は以下のようにも表示できるようです.
$a\circ b=ab-f(a)f(b)$
これにより,負の整数に対しても単位的Knuth積を拡張できます.
以下のように素数の概念を導入します.
ある正整数$a$がクヌース素数であるとは,$a$以下の正整数$b,c(b\leq c)$であって,
\begin{align}
b\circ c=a
\end{align}
を満たすような組$(b,c)$が$(1,a)$しか存在しないことをいう.
ただし,1はクヌース素数ではないとする.クヌース素数全体の集合を$\mathbb P$とする.
結合法則について調べていると,以下の集合に出会いました.
$1,0,-1,-a$以外のすべての整数$b$について,
\begin{align}
a\circ b \ne(-a)\circ (-b)
\end{align}
を満たすような整数$a$全体の集合をクラス1といい,$\mathbb C_1$で表す.ただし,1はクラス1の数とする.
$\mathbb C_1,\mathbb P$の共通集合を$\mathbb P_1$とする.
$\mathbb C_1$に含まれない正整数全体の集合をクラス2といい,$\mathbb C_2$と表す.
$\mathbb C_2,\mathbb P$の共通集合を$\mathbb P_2$とする.$\mathbb P_2$から単位的Knuth積で生成される集合を$\langle \mathbb P_2 \rangle$とする.
(クラス1,2という名前は私が考えたのですが,ダサいと言われたのでもっとかっこいい名前を募集中.)
クラス1,2については以下のような性質を見つけました.
正整数$a$について,
(1)
\begin{align}
&a\in\mathbb C_1\\
&\Leftrightarrow \text{$a$のゼッケンドルフ表現が$F_0+F_{(偶数)}+\cdots$の形}\\
&\Leftrightarrow f(-a)=-f(a)-1
\end{align}
また,
$S=\{5n-1-2\lfloor \frac{n}{\phi^2} \rfloor:n\in \mathbb N\}$とすると,$\mathbb C_1=S$
(2)\begin{align} &a\in\mathbb C_2\\ &\Leftrightarrow \text{$a$のゼッケンドルフ表現が$F_0+F_{(奇数)}+\cdots$の形,}\\ &\text{または$a$のゼッケンドルフ表現に$F_0$が含まれない}\\ &\Leftrightarrow f(-a)=-f(a) \end{align}
上の$f$を用いた条件は友人Sが見つけました.感謝.
分配法則
分配法則は常には成り立たないのですが,「補正項」を付け加えることで成立します.
$f(n)=\lfloor \frac{n+1}{\phi^2} \rfloor$とする.
任意の$a,b,c\in \mathbb Z$に対し,
(1)$f(a)+f(b)=f(a+b)$なら,
\begin{align}
(a+b)\circ c-(a\circ c+b\circ c)=0
\end{align}
(2)$f(a)+f(b)>f(a+b)$なら,
\begin{align}
(a+b)\circ c-(a\circ c+b\circ c)=f(c)
\end{align}
(3)$f(a)+f(b)< f(a+b)$なら,
\begin{align}
(a+b)\circ c-(a\circ c+b\circ c)=-f(c)
\end{align}
なお,任意の$a,b\in\mathbb C_1$について$f(a)+f(b)< f(a+b)$である.
私が実験的に予想し,Sが証明しました.単位的Knuth積のfloor表示を用いて計算すると証明できます.
これで分配法則については完全に分かったことになります.
しかし,結合法則についてはこれほど単純ではありません.
結合法則
いくつか生えてきた予想を並べてみます.
(1)$a,b\in \mathbb C_2$とすると,
\begin{align}
a\circ b=(-a)\circ(-b)
\end{align}
(2)$a\in \mathbb C_1,b\in \mathbb C_2$とすると,
\begin{align}
a\circ b=(-a)\circ(-b)+\lfloor \frac{b+1}{\phi^2}\rfloor
\end{align}
(3)$a,b\in \mathbb C_1$とすると,
\begin{align}
a\circ b=(-a)\circ(-b)+\lfloor \frac{a+1}{\phi^2}\rfloor+\lfloor \frac{b+1}{\phi^2}\rfloor +1
\end{align}
$a,c\in\mathbb Z,b\in \langle \mathbb P_2\rangle$とすると,
\begin{align}
(a\circ b)\circ c=a\circ(b\circ c)
\end{align}
(真ん中が$\langle \mathbb P_2\rangle$の元なら結合律成立)
任意の$a,c\in\mathbb C_2$,任意の$b\in \mathbb Z$について,
\begin{align}
(a\circ b)\circ c=a\circ(b\circ c)
\end{align}
予想だけが立つばかりで,証明は全然得られていません.代数的な見方ができればよいのかも...
分配法則同様,結合法則の補正項についても考えてみました.
$F(a,b,c)=(a\circ b)\circ c-a\circ(b\circ c)$とする.
任意の$a,b,c\in\mathbb Z(c< a)$について,以下のいずれかの場合が成り立つ.
\begin{equation*} F(a,b,c)=\begin{cases}
0 \\
\pm f(a)\\\pm f(c)\\\pm (f(a)+f(c))\\\pm (f(a)-f(c))
\end{cases} \end{equation*}
(ただし,$\pm (f(a)-f(c))$の場合については0になることもある.)
補正項としてありうるパターンは上の9個だけという予想です.
結合法則は実験してもなかなか法則性がつかめません.クラス1,2という道具だけでは足りないようです.さらに実験をおこなうために,以下の概念を導入しました.
正整数$n$をずらしたフィボナッチ数でゼッケンドルフ表現した際,はじめのフィボナッチ数の添え字を$c_0(n)$とする.
$a,b\in \mathbb N$に対し,先頭誤差を$e(a,b)=c_0(a)+c_0(b)-c_0(a\circ b)$と定める.
$a,b$のうち少なくとも一つがフィボナッチ数なら$e(a,b)=0$です.
実験によると,先頭誤差としてありえる数は$0,\pm1,\pm2,-3,-5$で,$ -3,-5$が現れるのは非常に少なかったです.もっと数が大きければこれら以外の数が現れる可能性は十分あります.
$a,b\in\mathbb N$とし,すべての自然数$b$に対し,
\begin{align}
e(a,b)=0\text{または}-2
\end{align}
を満たすような自然数$a$全体の集合をクラスBといい,$\mathbb C_B$と表す.また,クラスBに含まれず,かつフィボナッチ数でない自然数全体の集合をクラスAといい,$\mathbb C_A$と表す.
なお,$\mathbb C_B\subset\mathbb C_2$です.
$\mathbb T$が「$F_0,F_1$を含まない」という条件で定義されているように,ゼッケンドルフ表現のはじめの方は重要な情報を持っているようです.そのため,このような定義にしました.
(クラスA,Bという名前は私が考えたのですが,ダサいと言われたので（略)
$a\in\mathbb C_A,b\in\mathbb C_B$とすると,$e(a,b)=0$
これ面白くないですか!!?かなり非自明な予想です.
クラスA,Bを用いると,結合法則の必要条件を与えることができます.
組$(a,b,c)\in\mathbb N^3$に対し,$F(a,b,c)=(a\circ b)\circ c-a\circ(b\circ c)$として,
\begin{equation}
\begin{rcases}
e(a,b)=0 \ \land e(b,c)=0 \\
e(a,b)=2 \ \land e(b,c)=2 \\
e(a,b)=-2 \ \land e(b,c)=-2 \\
e(a,b)=\pm2 \ \land e(b,c)=0 \\
e(a,b)=0 \ \land e(b,c)=\pm2 \\
\end{rcases} \text{のとき}F(a,b,c)=0 \end{equation}
組$(a,b,c)\in\mathbb N^3$に対し,$F(a,b,c)=(a\circ b)\circ c-a\circ(b\circ c)$として,
\begin{align}
e(a,b)=2 \ \land e(b,c)=-1 \\
\end{align}
なら$F(a,b,c)=f(a)$
組$(a,b,c)\in\mathbb N^3$に対し,$F(a,b,c)=(a\circ b)\circ c-a\circ(b\circ c)$として,
\begin{align}
e(a,b)=2 \ \land e(b,c)=1 \\
\end{align}
なら$F(a,b,c)=-f(a)$
いずれも十分条件ではないことに注意してください.
感想
以上が私とT,Sが得た結果です.ほとんど予想ですが...証明のめどは立ってないです.なにかアイデアあればぜひ教えてください.Knuthが論文を出して以来,結合法則に関しては類似の演算がたくさん見つかっていますが,単位元の存在するような演算についてはあまり調べられていないのではないでしょうか.また,フィボナッチ数以外の線形漸化式についても同様に単位的な演算を考えることができるので,そちらも気になる所です.
謝辞
誤植指摘等よろしくお願いいたします.ここまで読んで下さりありがとうございました.また,助言を下さった友人のFに感謝いたします.
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
