Knuth代数2

186

定義,予想をまとめる.
以下,命題はすべて予想.

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$ は可換である.
(本家クヌース積と区別したいときは単位的クヌース積という)

Knuth積の床関数表示

$a \circ b = a b - ⌊ \frac{a + 1}{ϕ^{2}} ⌋ ⌊ \frac{b + 1}{ϕ^{2}} ⌋$

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}$

クヌース素数

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

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

クラス2

C_{2}

,クラス1クヌース素数

P_{2}, ⟨ P_{2} ⟩

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

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

正整数 $a$ について,
(1)
$\begin{aligned} a \in C_{1} \\ \Leftrightarrow a \circ 4 \neq (- a) \circ (- 4) \\ \Leftrightarrow a のゼッケンドルフ表現が F_{0} + F_{(偶数)} + \dots の形 \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 \circ 4 = (- a) \circ (- 4) \\ \Leftrightarrow a のゼッケンドルフ表現が F_{0} + F_{(奇数)} + \dots の形, \\ または a のゼッケンドルフ表現に F_{0} が含まれない \end{aligned}$

クラス1クヌース素数の負の整数への分解

任意の $C_{2}$ クヌース素数 $a$ に対しある $b \in C_{1}$ が存在して,
$\begin{array}{r} a = (- 2) \circ (- b) . \end{array}$

結合律予想1

(1) $a, b \in C_{2}$ とすると,
$\begin{array}{r} a \circ b = (- a) \circ (- b) \end{array}$
(クラス2内は結合的)
(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} ⟩$ の元なら結合律成立)

分配律予想

$a, b \in C_{1}, c \in Z$ のとき,
$\begin{array}{r} (a + b) \circ c + ⌊ \frac{c + 1}{ϕ^{2}} ⌋ = a \circ c + b \circ c \end{array}$

クラス2の部分集合がなす群

$S_{0} = {⌊ n ϕ^{2} ⌋ : n \in N}$
$S_{1} = {⌊ ⌊ n ϕ^{2} ⌋ ϕ ⌋ : n \in N}$ とすると,

(1) $a, b \in S_{0} \Rightarrow a \circ b \in S_{1}$
(2) $a, b \in S_{1} \Rightarrow a \circ b \in S_{1}$
(3) $a \in S_{0}, b \in S_{1} \Rightarrow a \circ b \in S_{0}$