大学数学基礎解説

文献あり

[自由研究]Knuthの代数:フィボナッチ数に関する積について

フィボナッチ数

265

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

こんにちは,itouです.

導入

Zeckendorfの定理というものがあります.

Zeckendorfの定理

任意の正整数 $n$ は以下のように一意に表示できる.
$\begin{array}{r} n = \sum_{i = 0}^{k} F_{c_{i}} (c_{i} \geq 2) \end{array}$

ただし $F_{0} = 0, F_{1} = 1, F_{n + 1} = F_{n} + F_{n - 1} (n \geq 1)$ , $c_{i + 1} > c_{i} + 1$ .

すなわち任意の正整数は連続しないフィボナッチ数の和で表示できます.Knuthは以下のことを示しました.

Knuth積(D.Knuth)

$F_{n}$ を $F_{0} = 0, F_{1} = 1, F_{n + 1} = F_{n} + F_{n - 1}$ で生成される数列として,正整数 $a, b$ を
$\begin{array}{r} 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{array}$
とゼッケンドルフ表現したとき,二項演算 $a \circ b$ を次のように定める.
$\begin{array}{r} a \circ b = \sum_{i = 0}^{k} \sum_{j = 0}^{l} F_{c_{i} + d_{j}} \end{array}$
このとき,二項演算 $\circ$ は結合法則を満たす.

非常に非自明な結果です!Knuthはゼッケンドルフ表示の性質を調べることでこれを示しました([1])が,P.Arnouxは剰余環 $Z [X^{2} - X - 1]$ を用いたより簡略化された証明を与えました.([2])
また,この積は $ϕ$ を黄金数として
$\begin{array}{r} a \circ b = 3 a b - a ⌊ \frac{b + 1}{ϕ^{2}} ⌋ - b ⌊ \frac{a + 1}{ϕ^{2}} ⌋ \end{array}$
という表示があります.

この演算についてはさらなる一般化が調べられています.
一般の線形漸化式への一般化は[3],Knuth積のfloor関数表示の類似については[4]にまとめられています.

私がこの積に興味を持ったのは友人Tが紹介してくれたからです.Ｔは次の示唆をしました.

「Knuth積は結合的だが単位的でない.和の取り方を変えれば単位的な積にできるのではないか」

つまり,以下のように定義します.

単位的Knuth積

$F_{n}$ を $F_{0} = 0, F_{1} = 1$ のフィボナッチ数列として,整数 $a, b$ を
$\begin{array}{r} 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{array}$
とゼッケンドルフ表現したとき,二項演算 $a \circ b$ を次のように定める.
$\begin{array}{r} a \circ b = \sum_{i = 0}^{k} \sum_{j = 0}^{l} F_{c_{i} + d_{j} - 2} \end{array}$
このとき,二項演算 $\circ$ は可換である.

インデックスを $- 2$ しておくことで1が単位元となってくれます.つまり,

すべての正整数 $a$ について,
$a \circ 1 = 1 \circ a = a$

たとえば以下のように計算します.

$\begin{aligned} (6 \circ 14) \circ 19 = 74 \circ 19 = 1210 \\ 6 \circ (14 \circ 19) = 6 \circ 231 = 1210 \end{aligned}$

こうすると単位的かつ結合的な積になる!...と思ったのですが,この積は常に結合的とは限りません.

結合法則の反例

$\begin{aligned} (2 \circ 4) \circ 4 = 7 \circ 4 = 25 \\ 2 \circ (4 \circ 4) = 2 \circ 15 = 24 \end{aligned}$

この反例を見つけたときはかなりがっかりしたのですが,多くの場合で結合法則が成立することは事実です.もう少し調べると,Tが以下のような予想を得ました.

後のために,以下のように再定義します.

単位的Knuth積

$F_{n}$ を $F_{0} = 1, F_{1} = 2, F_{n + 2} = F_{n} + F_{n + 1}$ で生成される数列として,整数 $a, b$ を
$\begin{array}{r} 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{array}$
とゼッケンドルフ表現したとき,二項演算 $a \circ b$ を次のように定める.
$\begin{array}{r} a \circ b = \sum_{i = 0}^{k} \sum_{j = 0}^{l} F_{c_{i} + d_{j}} \end{array}$
このとき,二項演算 $\circ$ は可換である.

以下,このずらしたフィボナッチ数列を $F_{n}$ とし，ゼッケンドルフ表現もこちらの数列に合わせます.

Tが以下の予想を見つけました.

T

は結合的かつ分配的

「ゼッケンドルフ表現に $F_{0}, F_{1}$ が含まれないような正整数」全体の集合を $T$ とおくと,任意の $a, b, c \in T$ について
$\begin{array}{r} (a \circ b) \circ c = a \circ (b \circ c) \end{array}$

さらに,任意の $a, b \in T$ ,任意の正整数 $n \in Z$ について
$\begin{array}{r} (a + b) \circ n = a \circ n + b \circ n \end{array}$

実験を行うと,他にも予想が生えてきます.この記事では,我々が得た予想を紹介します.

conjectures

$\begin{array}{r} f (n) = ⌊ \frac{n + 1}{ϕ^{2}} ⌋ \end{array}$
とする.

単位的Knuth積は以下のようにも表示できるようです.

単位的Knuth積の床関数表示(by T)

$a \circ b = a b - f (a) f (b)$

これにより,負の整数に対しても単位的Knuth積を拡張できます.
以下のように素数の概念を導入します.

クヌース素数

ある正整数 $a$ がクヌース素数であるとは, $a$ 以下の正整数 $b, c (b \leq c)$ であって,
$\begin{array}{r} b \circ c = a \end{array}$
を満たすような組 $(b, c)$ が $(1, a)$ しか存在しないことをいう.
ただし,1はクヌース素数ではないとする.クヌース素数全体の集合を $P$ とする.

結合法則について調べていると,以下の集合に出会いました.

クラス1

C_{1}

,クラス1クヌース素数

P_{1}

$1, 0, - 1, - a$ 以外のすべての整数 $b$ について,
$\begin{array}{r} a \circ b \neq (- a) \circ (- b) \end{array}$
を満たすような整数 $a$ 全体の集合をクラス1といい, $C_{1}$ で表す.ただし,1はクラス1の数とする.

$C_{1}, P$ の共通集合を $P_{1}$ とする.

クラス2

C_{2}

,クラス1クヌース素数

P_{2}, ⟨ P_{2} ⟩

$C_{1}$ に含まれない正整数全体の集合をクラス2といい, $C_{2}$ と表す.
$C_{2}, P$ の共通集合を $P_{2}$ とする. $P_{2}$ から単位的Knuth積で生成される集合を $⟨ P_{2} ⟩$ とする.

(クラス1,2という名前は私が考えたのですが,ダサいと言われたのでもっとかっこいい名前を募集中.)

クラス1,2については以下のような性質を見つけました.

クラス1,2の元であることと同値な性質

正整数 $a$ について,
(1)
$\begin{aligned} a \in C_{1} \\ \Leftrightarrow a のゼッケンドルフ表現が F_{0} + F_{(偶数)} + \dots の形 \\ \Leftrightarrow f (- a) = - f (a) - 1 \end{aligned}$
また,
$S = {5 n - 1 - 2 ⌊ \frac{n}{ϕ^{2}} ⌋ : n \in N}$ とすると, $C_{1} = S$

(2) $\begin{aligned} a \in C_{2} \\ \Leftrightarrow a のゼッケンドルフ表現が F_{0} + F_{(奇数)} + \dots の形, \\ または a のゼッケンドルフ表現に F_{0} が含まれない \\ \Leftrightarrow f (- a) = - f (a) \end{aligned}$

上の $f$ を用いた条件は友人Sが見つけました.感謝.

分配法則

分配法則は常には成り立たないのですが,「補正項」を付け加えることで成立します.

分配法則(by S)

$f (n) = ⌊ \frac{n + 1}{ϕ^{2}} ⌋$ とする.
任意の $a, b, c \in Z$ に対し,
(1) $f (a) + f (b) = f (a + b)$ なら,
$\begin{array}{r} (a + b) \circ c - (a \circ c + b \circ c) = 0 \end{array}$
(2) $f (a) + f (b) > f (a + b)$ なら,
$\begin{array}{r} (a + b) \circ c - (a \circ c + b \circ c) = f (c) \end{array}$
(3) $f (a) + f (b) < f (a + b)$ なら,
$\begin{array}{r} (a + b) \circ c - (a \circ c + b \circ c) = - f (c) \end{array}$

なお,任意の $a, b \in C_{1}$ について $f (a) + f (b) < f (a + b)$ である.

私が実験的に予想し,Sが証明しました.単位的Knuth積のfloor表示を用いて計算すると証明できます.

これで分配法則については完全に分かったことになります.
しかし,結合法則についてはこれほど単純ではありません.

結合法則

いくつか生えてきた予想を並べてみます.

結合法則予想1

(1) $a, b \in C_{2}$ とすると,
$\begin{array}{r} a \circ b = (- a) \circ (- b) \end{array}$
(2) $a \in C_{1}, b \in C_{2}$ とすると,
$\begin{array}{r} a \circ b = (- a) \circ (- b) + ⌊ \frac{b + 1}{ϕ^{2}} ⌋ \end{array}$
(3) $a, b \in C_{1}$ とすると,
$\begin{array}{r} a \circ b = (- a) \circ (- b) + ⌊ \frac{a + 1}{ϕ^{2}} ⌋ + ⌊ \frac{b + 1}{ϕ^{2}} ⌋ + 1 \end{array}$

結合法則予想2

$a, c \in Z, b \in ⟨ P_{2} ⟩$ とすると,
$\begin{array}{r} (a \circ b) \circ c = a \circ (b \circ c) \end{array}$
(真ん中が $⟨ P_{2} ⟩$ の元なら結合律成立)

結合法則予想3

任意の $a, c \in C_{2}$ ,任意の $b \in Z$ について,
$\begin{array}{r} (a \circ b) \circ c = a \circ (b \circ c) \end{array}$

予想だけが立つばかりで,証明は全然得られていません.代数的な見方ができればよいのかも...
分配法則同様,結合法則の補正項についても考えてみました.

結合法則の補正項

$F (a, b, c) = (a \circ b) \circ c - a \circ (b \circ c)$ とする.
任意の $a, b, c \in Z (c < a)$ について,以下のいずれかの場合が成り立つ.
$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}$
(ただし, $\pm (f (a) - f (c))$ の場合については0になることもある.)

補正項としてありうるパターンは上の9個だけという予想です.
結合法則は実験してもなかなか法則性がつかめません.クラス1,2という道具だけでは足りないようです.さらに実験をおこなうために,以下の概念を導入しました.

正整数 $n$ をずらしたフィボナッチ数でゼッケンドルフ表現した際,はじめのフィボナッチ数の添え字を $c_{0} (n)$ とする.

先頭誤差

$a, b \in N$ に対し,先頭誤差を $e (a, b) = c_{0} (a) + c_{0} (b) - c_{0} (a \circ b)$ と定める.

$a, b$ のうち少なくとも一つがフィボナッチ数なら $e (a, b) = 0$ です.
実験によると,先頭誤差としてありえる数は $0, \pm 1, \pm 2, - 3, - 5$ で, $- 3, - 5$ が現れるのは非常に少なかったです.もっと数が大きければこれら以外の数が現れる可能性は十分あります.

クラスA,B

$a, b \in N$ とし,すべての自然数 $b$ に対し,
$\begin{array}{r} e (a, b) = 0 または - 2 \end{array}$
を満たすような自然数 $a$ 全体の集合をクラスBといい, $C_{B}$ と表す.また,クラスBに含まれず,かつフィボナッチ数でない自然数全体の集合をクラスAといい, $C_{A}$ と表す.

なお, $C_{B} \subset C_{2}$ です.
$T$ が「 $F_{0}, F_{1}$ を含まない」という条件で定義されているように,ゼッケンドルフ表現のはじめの方は重要な情報を持っているようです.そのため,このような定義にしました.
(クラスA,Bという名前は私が考えたのですが,ダサいと言われたので（略)

$a \in C_{A}, b \in C_{B}$ とすると, $e (a, b) = 0$

これ面白くないですか!!?かなり非自明な予想です.

クラスA,Bを用いると,結合法則の必要条件を与えることができます.

結合律の必要条件

組 $(a, b, c) \in N^{3}$ に対し, $F (a, b, c) = (a \circ b) \circ c - a \circ (b \circ c)$ として,
$\begin{array}{ll} 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) = \pm 2 \land e (b, c) = 0 \\ e (a, b) = 0 \land e (b, c) = \pm 2 \end{array}} のとき F (a, b, c) = 0$

F (a, b, c) = f (a)

の必要条件

組 $(a, b, c) \in N^{3}$ に対し, $F (a, b, c) = (a \circ b) \circ c - a \circ (b \circ c)$ として,

$\begin{array}{r} e (a, b) = 2 \land e (b, c) = - 1 \end{array}$
なら $F (a, b, c) = f (a)$

F (a, b, c) = - f (a)

の必要条件

組 $(a, b, c) \in N^{3}$ に対し, $F (a, b, c) = (a \circ b) \circ c - a \circ (b \circ c)$ として,

$\begin{array}{r} e (a, b) = 2 \land e (b, c) = 1 \end{array}$
なら $F (a, b, c) = - f (a)$

いずれも十分条件ではないことに注意してください.

感想

以上が私とT,Sが得た結果です.ほとんど予想ですが...証明のめどは立ってないです.なにかアイデアあればぜひ教えてください.Knuthが論文を出して以来,結合法則に関しては類似の演算がたくさん見つかっていますが,単位元の存在するような演算についてはあまり調べられていないのではないでしょうか.また,フィボナッチ数以外の線形漸化式についても同様に単位的な演算を考えることができるので,そちらも気になる所です.

謝辞

誤植指摘等よろしくお願いいたします.ここまで読んで下さりありがとうございました.また,助言を下さった友人のFに感謝いたします.

参考文献

[1]

[2]

[3]

P. J. GRABNER,A. PETHO,R. F. TICHY,G. J. WOEGINGERS, Associativity of Recurrence Multiplication, Appl. Math. L&t. Vol. 7, No. 4, pp. 85-90, 1994 Copyright@1994 Elsevier Science Ltd Printed in Great Britain. All rights reserved

[4]

A.S.Fraekel,H.Porta,K.B.Stolarsky, Some Arithmetical Semigroups, Springer

投稿日：2024年6月6日

更新日：2024年6月14日