30：Lucas数列と原始的約数

$(\alpha, \beta)$ *1がLucasペアであるとは、 $\alpha, \beta$ が代数的整数で、 $a:=\alpha +\beta$ および $b:=\alpha \beta$ がともに零でない互いに素な整数であり、更に $\alpha /\beta$ が $1$ の冪根でないときにいいます。

Lucasペア $(\alpha, \beta)$ に対して、二種類のLucas数列 $\{u_n\}_{n=0}^{\infty}, \{v_n\}_{n=0}^{\infty}$ を

$\begin{align}&u_n = u_n(\alpha, \beta ) = \frac{\alpha^n-\beta^n}{\alpha -\beta} \\ &v_n = v_n(\alpha, \beta) = \alpha^n+\beta^n\end{align}$

によって定義します。漸化式で書くと、

$\begin{align}u_n &= au_{n-1}-bu_{n-2}, (u_0=0, u_1=1) \\ v_n &= av_{n-1}-bv_{n-2}, (v_0=2, v_1=a)\end{align}$

となります。

$a=1, b=-1$ のとき（ $\alpha =\phi, \beta = -\phi^{-1}$ , $\phi$ は黄金比） $u_n, v_n$ はそれぞれFibonacci数、Lucas数を表します。

89：フィボナッチ数 - INTEGERS
199：リュカ数 - INTEGERS

つまり、Lucas数列はFibonacci数やLucas数を含む数列をもっと一般に取り扱おうというものです。例えば、

144：フィボナッチ平方数 - INTEGERS

で扱った補題１は一般のLucas数列でも成立します(証明は定義から計算するだけ)：

相互法則 $D:=a^2-4b$ とする。任意の非負整数 $m, n$ に対して次が成立。

$\begin{align}2u_{m+n} &= u_mv_n+u_mv_n \\ 2v_{m+n} &= v_mv_n+Du_mu_m.\end{align}$

次の性質もFibonacci数に限らずに成立します：

命題 $n$ が $m$ の倍数であれば、 $u_n$ は $u_m$ の倍数である。

証明. 上記相互法則を使おうとすると、係数にある $2$ が邪魔である。代わりに $u_{m+n}=u_mv_n-b^nu_{m-n}$ を使えば、 $u_{km}=u_{(k-1)m}v_m-q^mu_{(k-2)m}$ となって $k$ に関する帰納法が使える形になる。 $u_{2m}=u_mv_m$ より、 $k=2$ のときもOK。 Q.E.D.

さて、この記事では $u_n$ に関する原始的約数の話を紹介しようと思います。

定義 $n \geq 1$ に対して、 $u_n$ の素因子 $p$ が原始的約数であるとは*2、 $D=a^2-4b$ および $m < n$ に対する $u_m$ のいずれも割り切らないときにいう。

例えば、Fibonacci数の場合( $D=5$ )は

$F_1=1,$ 原始的約数なし
$F_2=1,$ 原始的約数なし
$F_3=2,$ $2$ が原始的約数
$F_4=3,$ $3$ が原始的約数
$F_5=5,$ 原始的約数なし
$F_6=8=2^3,$ 原始的約数なし
$F_7=13,$ $13$ が原始的約数
$F_8=21=3\times 7,$ $7$ が原始的約数
$F_9=34=2\times 17,$ $17$ が原始的約数
$F_{10}=55=5\times 11,$ $11$ が原始的約数
$F_{11}=89,$ $89$ が原始的約数
$F_{12}=144=2^4\times 3^2,$ 原始的約数なし
$F_{13}=233,$ $233$ が原始的約数
$F_{14}=377=13\times 29,$ $29$ が原始的約数

のようになっています。実は、 $F_1, F_2, F_5, F_6, F_{12}$ 以外のFibonacci数は全て原始的約数を持ちます！ 或る意味で $F_{12}$ より後のFibonacci数は常に新しい情報を有していると表現できるでしょう。 $F_{12}$ はただでさえ冪乗数となる最大のFibonacci数という素敵な性質を持っていたのですが、かような性質(原始的約数をもたない最大のFibonacci数という特徴)も持っていたのです！

Lucas数列に関する非常にチャレンジングな問題として、原始的約数を持たないようなLucas数列の項の全把握という問題がありました。この問題はBilu-Hanrot-Voutierによって2001年に完全解決されています(彼らはLehmer数列も同時に扱っていますがこの記事では省略します)：

Y. Bilu, G. Hanrot, P. M. Voutier, Existence of primitive divisors of Lucas and Lehmer numbers, J. Reine Angew. Math. 539 (2001), 75--122.

まず、彼らの論文の主結果である次の定理は極めて強い結果です：

定理 (Bilu-Hanrot-Voutier) 任意のLucasペア $(\alpha, \beta)$ に対して、 $u_n$ は $n > 30$ ならば原始的約数を持つ！

非常に強力かつ美しいです。Fibonacci数列の場合だけを考えても、少数の例外を除いてずっと原始的約数を持ち続けるというのは非自明なことでしたが、どんなLucas数列を考えても例外が $30$ 個そこら(実際には最大で $10$ 個)を超えることはないと言っているのです。これはLucas数列が単なる一般化ではなく非常に深い数列のクラスであることを表していると言えるでしょう。あんなに単純なる数列と一般性からかような定理が成り立つとは想像もできません！しかも、これはベストポッシブルな結果のため、 $30$ に今まで以上に特別な感情を抱いてしまいます。個人的には $30$ 定理という名称を与えたいです。

残念ながら証明は(難解なため)現段階では当ブログで紹介することはできません。実はZsigmondyの定理という1800年代後半に得られた有名な定理があるのですが、Zsigmondyの定理を(今から述べるものも含めた)Bilu-Hanrot-Voutierの結果はそのプロトタイプとして含んでいます。Zsigmondyの定理の方は近いうちに証明を紹介するつもりです*3。今回は証明抜きに結果を味わうことにしましょう。

彼らは問題を完全解明したと言いましたが、そのためには $n \leq 30$ の場合に原始的約数を持たないようなLucasペアと $n$ の組を全て列挙すればよいです。まず、次は明らかです：

任意のLucasペアに対して、 $u_1=1$ は原始的約数をもたない。

$2 \leq n \leq 30$ の場合の分類表において、簡単のため、Lucasペアに同値関係を定義します：

定義二つのLucasペア $(\alpha_1, \beta_1), (\alpha_2, \beta_2)$ が同値であるとは、 $\alpha_1/\alpha_2 =\beta_1/\beta_2=\pm 1$ のときにいう。

次の定理によって、原始的約数をもたない例が全て列挙されています：

定理 $2 \leq n \leq 30$ に対して、原始的約数をもたないようなLucasペアは必ず $\displaystyle \left( \frac{a-\sqrt{b}}{2}, \frac{a+\sqrt{b}}{2} \right)$ なる形をしたペアと同値である*4。更に、実際に原始的約数をもたないものは各 $n$ 毎に次のような $(a, b)$ の場合である。

$\color{red}{n=2}$ $(1, 1-4q), (q\neq 1);$ $(2^k, 4^k-4q), (q \equiv 1 \pmod{2}, (k, q) \neq (1, 1))$
$\color{red}{n=3}$ $(m, 4-3m^2), (m > 1);$ $(m, 4\cdot 3^k-3m^2), (m\not \equiv 0\pmod{3}, (k, m) \neq (1, 2))$
$\color{red}{n=4}$ $(m, 2-m^2), (m > 1, m \equiv 1\pmod{2});$ $(m, 4-m^2), (m > 2, m \equiv 0\pmod{2})$
$\color{red}{n=5}$ $(1, -7); (2, -40); (1, -11); (1, -15); (12, -76); (12, -1364)$
$\color{red}{n=6}$ $(m, (4-m^2)/3), (m \geq 4, m \not \equiv 0 \pmod{3});$ $(m, (4^{k+1}-m^2)/3), (m \equiv \pm 1\pmod{6});$ $(m, 4-m^2/3), (m \equiv 0 \pmod{3});$ $(m, 2^{k+2}-m^2/3), (m \equiv 3 \pmod{6})$
$\color{red}{n=7}$ $(1, -7); (1, -19)$
$\color{red}{n=8}$ $(2, -24); (1, -7)$
$\color{red}{n=10}$ $(2, -8); (5, -3); (5, -47)$
$\color{red}{n=12}$ $(1, 5); (1, -7); (1, -11); (2, -56); (1, -15); (1, -19)$
$\color{red}{n=13}$ $(1, -7)$
$\color{red}{n=18}$ $(1, -7)$
$\color{red}{n=30}$ $(1, -7)$

ここで、 $q$ は非負整数であり、 $k, m$ は自然数。

$(a, b)=(1, -7)$ というペアがかなり原始的約数なしのケースが多いようなので実際に確認してみましょう。これは $((1-\sqrt{-7})/2, (1+\sqrt{-7})/2/)$ なるLucasぺアに対するLucas数列で、漸化式は

$u_n=u_{n-1}-2u_{n-2}$

で与えられます( $D=-7$ )。

$u_0=0,$
$u_{1}=1,$ 原始的約数なし
$u_{2}=1,$ 原始的約数なし
$u_{3}=-1,$ 原始的約数なし
$u_{4}=-3,$ $3$ が原始的約数
$u_{5}=-1,$ 原始的約数なし
$u_{6}=5,$ $5$ が原始的約数
$u_{7}=7,$ 原始的約数なし
$u_{8}=-3,$ 原始的約数なし
$u_{9}=-17,$ $17$ が原始的約数
$u_{10}=-11,$ $11$ が原始的約数
$u_{11}=23,$ $23$ が原始的約数
$u_{12}=45=3^2\times 5,$ 原始的約数なし
$u_{13}=-1,$ 原始的約数なし
$u_{14}=-91=-7\times 13,$ $13$ が原始的約数
$u_{15}=-89,$ $89$ が原始的約数
$u_{16}=93=3\times 31,$ $31$ が原始的約数
$u_{17}=271,$ $271$ が原始的約数
$u_{18}=85=5\times 17,$ 原始的約数なし
$u_{19}=-457,$ $457$ が原始的約数
$u_{20}=-627=-3\times 11 \times 19,$ $19$ が原始的約数
$u_{21}=287=7\times 41,$ $41$ が原始的約数
$u_{22}=1541=23 \times 67,$ $67$ が原始的約数
$u_{23}=967,$ $967$ が原始的約数
$u_{24}=-2115=-3^2\times 5\times 47,$ $47$ が原始的約数
$u_{25}=-4049,$ $4049$ が原始的約数
$u_{26}=181,$ $181$ が原始的約数
$u_{27}=8279=17\times 487,$ $487$ が原始的約数
$u_{28}=7917=3\times 7\times 13 \times 29,$ $29$ が原始的約数
$u_{29}=-8641,$ $8641$ が原始的約数
$u_{30}=-24475 = -5^2\times 11\times 89$ 原始的約数なし
$u_{31}=-7193,$ $7193$ が原始的約数
$u_{32}=41757=3\times 31 \times 449,$ $449$ が原始的約数
$u_{33}=56143=23 \times 2441,$ $2441$ が原始的約数