メモ(数論13): Lucas–Lehmer Land

チラ裏 > 数論 i > メモ13

「チラ裏」は、きちんとまとまった記事ではなく、断片的なメモです。誤字脱字・間違いがあるかもしれません。

***

2023-01-13 いかすぜ!バイナッチ 依存症者の末路…w

#数論 #フィボナッチ #Lucas-Lehmer

フィボナッチ数列というのは 1, 1, 2, 3, 5, 8, 13, 21, … のように、各項が直前の2項の和になっている数列の一種。「第0項」の 0 から始めると:
  0, 1, 1, 2, 3, 5, 8, 13, 21, …

それと似ているが、ひとひねり加え、各項を直前の2項の和の2倍としてみよう:
  0, 1, 2, 6, 16, 44, 120, 328, …
例えば第3項(左端の 0 を第0項とする)の 6 は、直前の2項の和 1+2 の2倍。第4項の 16 は、直前の2項の和 2+6 の2倍。以下同様。フィボナッチ数列の「直前の2項の和」という部分に「~の2倍」という処理を追加した数列なんで、これをバイナッチ数列と呼ぶことにする(正式名称ではない)。「一般化 Lucas 数列」の一例だが、あまり取り上げられることのない存在だろう。どんな景色が待ち受けているのだろうか…

*

【1】 とりあえず Binet の公式的な「一般項の式」を作りたい。Fibonacci の場合を思い出すと、フィボナッチ的性質を持つ単純な等比数列――
  x, x2, x3, …  ただし x + x2 = x3
――を考えることが出発点となった。それを模倣して、
  x, x2, x3, …  ただし 2(x + x2) = x3
を考え、「ただし」の式の両辺を x で割ると:
  2(1 + x) = x2 つまり x2 − 2x − 2 = 0
この2次方程式を解くと x = 1 ± √3。この2解を f = 1 + √3, g = 1 − √3 とすると、数列 fn も数列 gn も、それぞれ「直前の2項の和が次の項」という性質を持つのだから(n = 0, 1, 2, …)、それらを足した fn + gn も同じ性質を持ち、より一般的に cfn + dgn も同じ性質を持つ(c, d は定数。Fibonacci 数列やその一般化を考えたときの cun + dvn と同様)。この定数 c, d を決定したい。

n = 0 のとき fn = gn = 1 なので cfn + dgn = c + d = 0 (なぜならバイナッチ数列の第0項は 0)、つまり d = −c。

n = 1 のとき fn = 1 + √3, gn = 1 − √3 なので cfn + dgn = c(1 + √3) + d(1 − √3) = 1 (なぜならバイナッチ数列の第1項は 1)、上記 d = −c を代入すると:
  c(1 + √3) − c(1 − √3) = 1 つまり 2c√3 = 1 だから c = 1/(2√3)

結局、バイナッチ数列の第n項――大文字の Un で表すことにする――は(d = −c に注意すると):
  Un = cfn + dgn = cfn − cgn = c(fn − gn) ところが c = 1/(2√3) なので
  Un = (fn − gn) / (2√3) ここで f = 1 + √3, g = 1 − √3
これが Binet の公式 Fn = (un − vn) / √5 の*1、バイナッチ・バージョン。

*1 ここで u = (1 + √5)/2, v = (1 − √5)/2。従って u − v = √5 = 公式の分母。バイナッチ・バージョンでも f − g = 2√3 = 公式の分母。この小文字の u, v は、バイナッチ数列を表すのに使う大文字の U, V とは無関係。

Binet の公式とそのバイナッチ版
  フィボナッチ数列の一般項 Fn = (un − vn)/(u − v)
    ただし u = (1 + √5)/2, v = (1 − √5)/2
  バイナッチ数列の一般項 Un = (fn − gn)/(f − g)
    ただし f = 1 + √3, g = 1 − √3
フィボナッチの u & v が f & g に置き換わっただけで、内容的には同じパターン。

〔例〕 n = 3 の場合を考えてみる。二項定理の「3乗」の場合の式…
  (x + y)3 = x3 + 3x2y + 3xy2 + y3
…を使って展開すると:
  f3 = (1 + √3)3 = 1 + 3⋅1⋅√3 + 3⋅1⋅3 + 3√3 = 10 + 6√3
同様に g3 = (1 − √3)3 = 1 − 3√3 + 9 − 3√3 = 10 − 6√3 なので:
  f3 − g3 = (10 + 6√3) − (10 − 6√3) = 12√3
だから U3 = (f3 − g3) / (2√3) = (12√3) / (2√3) = 6 バイナッチ数列の第3項と一致!

【2】 フィボナッチ数列 Fn には、Lucas 数と呼ばれる相棒の数列 Ln = 2, 1, 3, 4, 7, 11, … があって、両者は緊密な関係にあり、この二つを組み合わせることで、しばしば見通しが良くなるのだった。バイナッチ数列 Un にも同様の相棒―― Vn で表すことにする――が考えられる。フィボナッチ数列の相棒は、Binet 形式では
  Ln = un + vn  ← 小文字の u, v。バイナッチ数列の U, V とは無関係
だったので、同様に考えると、バイナッチ数列の相棒は:
  Vn = fn + gn

この相棒 Vn = fn + gn は、やはり cfn + dgn の形なので(c = d = 1)、「ある項は直前の2項の和の2倍」というバイナッチ的性質を持つ。具体的に…
  V0 = f0 + g0 = 1 + 1 = 2
  V1 = f1 + g1 = (1 + √3) + (1 − √3) = 2
…なので、Vn は 2, 2, 8, 20, 56, … となるはず(8 は直前の2項の和 2 + 2 の2倍、その次の 20 も直前の2項の和 2 + 8 の2倍、等々)。

〔例〕 n = 3 に対して f3 + g3 = (1 + √3)3 + (1 − √3)3 = (1 + 3√3 + 3⋅3 + 3√3) + (1 − 3√3 + 3⋅3 − 3√3) = 1 + 9 + 1 + 9 = 20

バイナッチ数列とその相棒
n0123456
Un01261644120
Vn2282056152416

バイナッチ数列の一般項
  Un = (fn − gn)/(f − g), Vn = fn + gn
  ここで f = 1 + √3, g = 1 − √3 (従って f − g = 2√3)

相棒が活躍する一例として、フィボナッチ数列には F2n = (u2n − v2n)/(u − v) = (un + vn)(un − vn)/(u − v) = LnFn = FnLn というシンプルな関係*2がある(小文字の u, v はバイナッチの U, V とは無関係)。バイナッチとその相棒に関しても、単に文字が u, v から f, g に置き換わるだけで式の形は全く同じなので、同様に U2n = UnVn というシンプルな関係が成り立つ。

〔例〕 U4 = 16 は U2V2 = 2 × 8 に等しい。U6 = 120 は U3V3 = 6 × 20 に等しい。

*2 詳細については「不思議っち☆フィボナッチ(第5話)」【15】参照。

文字が違うだけの同じ式なんだから「そうなって当然」とはいえ、なかなかエレガントで美しい!

*

でも、こんなこと、一体何の役に立つのだろうか。

A Primer for the Fibonacci Numbers [1] の中で Brousseau という人は、冗談半分に The inveterate Fibonacci addict tends to(長年のフィボナッチ依存症の人は往々にして…)と書いている。いわく 13 という数字を聞くと反射的に F7 を連想し、55 という数字を聞くと F10 だと思うのだそうだ。依存症なので、やめたくなくても、やめられない(らしいw)。

[1] https://www.fq.math.ca/primer.html

一般化 Lucas 数列の理論には、ある種の応用もあるかもしれないけれど、その開祖(?)の Lucas 自身 Récréations mathématiques という本も書いている。数学パズルという言葉もあるように、それはレクリエーション(遊び)であり、悪く言えば「現実逃避」。分散コンピューティングによる因数分解や素数探しにしたって、誰かが「何の役に立つのか?」と尋ねれば「数学の発展に寄与する可能性もあるし、ハードウェアのテストにもなる」といった答えが返ってくるだろうが、参加者の本音は「あわよくば世界最大の素数を見つけて自慢したい」とか「面白ければ、役に立つかどうかなんてどうでもいい」といったところだろう。

高性能マシンを使い「誰が最初に素因数を見つけるか」と競争しているありさま、0.1%の高速化でしのぎを削っているありさま、オーバークロックしたCPUを徹夜でフル回転させているありさまなど、本質的には「走り屋」と変わらないのでは…w

普通の人は「数学」と聞くと「学校の勉強」を連想し、「数論の面白さ」といわれれば「頭がいいんだ・うらやましい」などと短絡的に判断するかもしれないが、数論には「面白いだけで、とりあえず何の役にも立たない事柄」が非常に多い。歴史を振り返ると、そうした「すぐには役立たない研究」が後から重大な意味を持つことも確かにあるんだけど、リアルタイムで見ると、当事者は「面白いからやってる」だけ。何の役にも立たないことに夢中になれるのは、果たして善いことなのか。幸せなのか、ばかなのか…。たぶん、その両方なのだろう。

(続く)

⁂

2023-01-16 「マイナス番目」のフィボナッチ数? 因数の出現位置

#数論 #フィボナッチ #Lucas-Lehmer

フィボナッチ数列 1, 1, 2, 3, 5, 8, 13, …。その第1項 F1 = 1 の直前の理論上の「第0項」は F0 = 0 だが、そのさらに直前の「第マイナス1項」は何だろうか? このような「マイナス番目の項」を考えることで、通常の範囲のフィボナッチ数列について、素敵な性質が証明される。

*

【3】 フィボナッチ数列の第 −1 項を x として、それ以降の項を並べると:
  x, 0, 1, 1, 2, 3, 5, …
フィボナッチ数列の性質上 x + 0 = 1 になるはずだから x = 1。

第 −2 項を y とすると y, 1, 0, 1, 1, 2, 3, 5, … となって y + 1 = 0 だから y = −1。

第 −3 項を z とすると z, −1, 1, 0, 1, 1, 2, 3, 5, … となって z + (−1) = 1 だから z = 2。

以下同様に考えると:
  …, 13, −8, 5, −3, 2, −1, 1, 0, 1, 1, 2, 3, 5, 8, 13, …

〔補足〕 フィボナッチ数列を一つずつ左(マイナス番目の方向)に延ばすには、現在の左端の項をその手前(右隣)の項から引けばいい。例えば −8−13 = −21。なぜなら左端を B として
  ?, B, C
の形になっているとき、フィボナッチの性質上 ? + B = C だから ? = C − B となる。

次のことが予想される。「マイナス番目」のフィボナッチ数は、「プラス番目」の対応するフィボナッチ数と、絶対値は同じ。符号については、「マイナス奇数番目」の項はプラスで、「マイナス偶数番目」の項はマイナス。

普段 Binet の公式
  Fn = (un − vn)/√5
  ただし u = (1 + √5)/2, v = (1 − √5)/2
…を使うとき、何となく n は 1 以上(あるいは 0 以上)の整数のような感じがするが、別に n が負じゃ駄目という理由もなさそうだ(成分の v も、もともと負の数だし)。とりあえず n を 1 以上の正の整数と仮定しておいて、Binet の公式の n を負の整数 −n に置き換えてみると:
  F−n = (u−n − v−n)/√5

例えば u−n というのは u の逆数 u−1 の n 乗のことだが*3、u の逆数は −v で v の逆数は −u なので*4、結局こうなる:
  F−n = (u−n − v−n)/√5 = [(u−1)n − (v−1)n]/√5 = [(−v)n − (−u)n]/√5
  この右端の分子 = (−1)n(v)n − (−1)n(u)n = (−1)n(vn − un)  ← (−1)n でくくった
  = (−1)n × (−1)(−vn + un)  ← 無理やり (−1) でくくって右端の丸かっこ内の符号を逆に
  = (−1)n+1(un − vn)
これは通常の Fn の分子の (−1)n+1 倍に当たる(分母は同じ)。すなわち通常の Fn と比べ、n が奇数なら全く同じ(プラス1倍)、n が偶数なら符号だけ逆(マイナス1倍)。前記の予想通り!

負の番号のフィボナッチ数は整数で、対応する正の番号のフィボナッチ数と等しいか、またはその −1 倍である: F−n = (−1)n+1Fn

(−1)n+1 の指数 n+1 に深い意味はなく、n が偶数か奇数かに応じて (−1)? が −1 or +1 になってくれれば、? は何でもいい(例えば n−1 や n+3 でもOK)。

*3 なぜなら u−n = (u−1)n なんで。

*4 x = u と x = v は x2 − x − 1 = 0 の2解なんで、解と係数の関係から uv = −1、つまり u(−v) = (−u)v = 1 となる(「カッシーニの隙間をたたけ!」【1】参照)。あるいは u = (1 + √5)/2 について、直接計算で u−1 = 2/(1 + √5)。分母を有理化して:
  u−1 = [2(1 − √5)]/[(1 + √5)(1 − √5)] = [2(1 − √5)]/[12 − (√5)2]
  = 2(1 − √5)/(−4) = (1 − √5)/(−2) = −v
v = (1 − √5)/2 についても同様。

【4】 「負の番号のフィボナッチ数」の概念を使うと、加法定理
  Fa+b = Fa+1Fb + FaFb−1  《ア》
…の引き算バージョンが得られる。単に b を −b に置き換えればいい:
  Fa−b = Fa+1F−b + FaF−b−1  《イ》

今 a 番目のフィボナッチ数 Fa と、b 番目のフィボナッチ数 Fb が、どちらも整数 q の倍数だと仮定しよう。このとき、q の倍数 Fa のそのまた倍数は、何であれ q の倍数。 q の倍数 Fb のそのまた倍数も、何であれ q の倍数。だから《ア》右辺は q の倍数と q の倍数の和で、従って、その和に等しい左辺 Fa+b もまた q の倍数。同じ仮定の下で、《イ》についても同様のことがいえる。F−b−1 は何らかの整数だから、《イ》右辺第2項は Fa の倍数、従って q の倍数。一方 F−b は、q の倍数 Fb の ±1 倍なので、やはり q の倍数*5。従って《イ》右辺第1項も q の倍数。結局、q の倍数の和に等しい左辺 Fa−b も q の倍数。

*5 例えば b = 9 のとき Fb = F9 = 34 は q = 17 の倍数; それに等しい F−b = F−9 = 34 も、もちろん q = 17 の倍数。別の例として b = 10 のとき Fb = F10 = 55 は q = 5 の倍数(11倍); 符号が違うだけの F−b = F−10 = −55 も、もちろん q = 5 の倍数(−11倍)。

観察 Fa と Fb がどちらも q の倍数なら、Fa+b も q の倍数、Fa−b も q の倍数。

〔例〕 F9 = 34 と F6 = 8 は、どちらも 2 の倍数なので、F9+6 = F15 も2の倍数、F9−6 = F3 も2の倍数(具体的な値は、それぞれ 610 と 2)。

この単純な観察が、以下の議論の鍵に!

【5】 フィボナッチ数列には、「数列の番号 n の倍数関係が、その番号に対応する値 Fn の倍数関係に、反映される」という美しい性質がある(「星のらせん階段」)。例えば、番号 7, 14, 21, … は 7 の倍数なので、それらの番号に対応する値 F7, F14, F21, … は、どれも F7 の倍数に。

値 Fn を構成する因数のレベルで見ても――。もし素数 q が、項の番号 n = w のとき Fw の因数として初登場(新出)したのなら、同じ素数 q は F2w, F3w, F4w, … の因数として、周期的に再登場する(下の表参照)。しかも、それ以外の位置で q が Fn の因数になることはない(つまり n が「q の新出位置の番号」w の倍数でないなら、Fn は q の倍数ではない)。

フィボナッチ数の因数: 丸かっこ内は新出素数
nFn素因数分解nFn素因数分解
1113233(233)
211437713 × (29)
32(2)156102 × 5 × (61)
43(3)169873 × 7 × (47)
55(5)171597(1597)
682318258423 × 17 × (19)
713(13)194181(37) × (113)
8213 × (7)2067653 × 5 × 11 × (41)
9342 × (17)21109462 × 13 × (421)
10555 × (11)221771189 × (199)
1189(89)2328657(28657)
1214424 × 32244636825 × 32 × 7 × (23)

〔例〕 素因数 q = 7 の新出位置は w = 8。すなわち F8 は素因数 7 を含むが、F1~F7 の各数は、この素因数を持たない。素因数 q = 7 は、「w = 8 の任意の倍数」の番号の項(F16, F24, etc.)において出現する; それ以外の番号の項では出現しない。F8 は新出素数 q = 7 の他に、既出の素因数 3 を持つ(それは第4項で新出した――項の番号 w = 8 は、因数 3 が初登場した項の番号 4 の倍数)。

素因数の出現位置の法則 第 w 項 Fw において新出した素因数 q は、第 2w 項、第 3w 項、第 4w 項、…で周期的に再出現するが、それ以外の項で出現することはない: 任意の整数 n について、n が w の倍数なら Fn は q の倍数; n が w の倍数でないなら Fn は q の倍数でない。

〔補足〕 素数 q がフィボナッチ数の因数のとき、「q が Fn の因数になる最初の項」の番号 n を「q が初登場する項の番号」(the rank of apparition of q)――略して q の新出位置――と呼ぶ。Fn の素因数は、
  (I) その位置で初登場する原始的な素因数(primitive prime factor)――略して新出素数――と、
  (II) その位置より前の(n の約数番目のどれかの)項で初登場し、周期的に再登場する既出素数
に分けられる。Édouard Lucas は前者を diviseur propre、後者を diviseur impropre と呼んだ。

証明 F2w, F3w, F4w などは Fw 自体の倍数なので(「星のらせんの定理」)、q に限らず Fw の全素因数を含む。よって命題の前半は当たり前。問題は「それ以外の項は因数 q を含まない」という部分。例えば F8 において初登場する素因数 q = 7 が F16, F24, F32, … で再登場するのはいいとして、番号が8の倍数以外の項(例えば F30)が因数 q = 7 を含んじゃ駄目!という理由があるのだろうか?

ここで最初の「マイナス番目のフィボナッチ数」の研究が役立つ。【4】の観察によれば、もしも F30 と F24 がどちらも q = 7 の倍数なら F30−24 = F6 も q = 7 の倍数になってしまう! これは理不尽: 因数 q = 7 が初登場する項の番号は w = 8 だから、それより前の第6項がこの因数を持つわけない。よって F30 が因数 q を持つという可能性は、否定される。この発想を一般の場合に適用しよう…。

一般に因数 q の新出位置を w とする。「w の倍数以外の変な番号 h の項 Fh が因数 q を持つ場合がある」と仮定して、矛盾を導く。変な番号 h は w の倍数じゃないので、w で割り切れない; h を w で割ったとき、商が k で余りが j とでもしよう:
  h = kw + j  ここで j は w で割った余りなので 1 以上 w 未満
  つまり h − kw = j
仮定によれば Fh は因数 q を持つ(つまり q の倍数)。Fkw は Fw の倍数なので、もちろん因数 q を持つ。従って【4】の観察から…
  Fh−kw = Fj
…も q の倍数(つまり因数 q を持つ)。これは、ばかげているッ! q が初登場する項の番号は w なので、Fj(番号 j は 1 以上 w 未満である)が因数 q を持つわけない。この不合理が生じた原因は「変な番号の項 Fh が因数 q を持つ」という仮定。だからその仮定は撤回され「w の倍数以外の番号の項が、因数 q を持つことはない」と結論される。□

*

第 w 項で新出した素因数 q は、w の倍数番目の全部の項で周期的にフィボナッチ数の因数となり、それ以外の項では因数とならない。シンプルで素敵な構造だ!

出現位置の法則は、因数 q を(素数に限らず)任意の正の整数として、その初登場・再登場を考えても、そのまま成り立つ。その結果、次のことが示されるだろう: 番号 a, b の最大公約数が d なら、Fa と Fb の最大公約数は Fd に等しい。つまり(倍数関係だけでなく)最大公約数の関係についても、フィボナッチ数の項の番号の間の関係が、項の値の間の関係にそのまま反映される(後述)。

出現位置の法則や最大公約数との関係について証明する場合、文献的には Bézout の定理を経由することが多いようだ。このメモでは「負の番号のフィボナッチ数」という奇手を使い Bézout の定理をバイパスして、分かりやすい証明を目指した。アイデアは、本質的には Lehmer [2] に基づく。Lehmer は Lucas–Lehmer test の証明の補題において、バイナッチ数列に関して同種の論法を使った。

(続く)

[2] D. H. Lehmer (1935): On Lucas’s Test for the Primality of Mersenne’s Numbers
https://primes.utm.edu/mersenne/LukeMirror/lit/lit_007s.htm

⁂

2023-01-17 バイナッチ数列の加法定理

#数論 #フィボナッチ #Lucas-Lehmer

フィボナッチ数列の場合、Binet の公式や加法定理が、いろいろな研究の土台となった。フィボナッチ数列のいとこ「バイナッチ数列」についても、加法定理を考えてみたい。導出法はフィボナッチ版とほとんど同じで、その復習ともいえる。加法定理の一つでは、フィボナッチ版にはなかった係数が付く(この係数は「逆数」の形の違いに由来し、さかのぼると、背後にある2次方程式の定数項の、符号を変えたものに当たる)。

*

【6】 Fibonacci 数列には、2種類の加法定理がある:
  ① Fa+b = Fa+1Fb + FaFb−1
  ② Fa+b = (FaLb + FbLa)/2
Fibonacci 数同士の関係として話が完結する①は、概念的にはシンプルだが、式の形がやや複雑で覚えにくい(覚え方)。②は相棒の Lucas 数とペアで考える必要があるが、その代わり式の形はシンプル。これらの公式については、帰納法で証明することもできるし()、Binet 形式を使い直接証明することもできるのだった。

①②の Bi-nacci バージョンを考えよう。②については、フィボナッチの②と同様の計算が成り立つ。バイナッチ数列とその相棒の一般項の公式から:
  UaVb = (fa − ga)/(f − g) × (fb + gb)
  UbVa = (fb − gb)/(f − g) × (fa + ga)
この2式について、左辺同士と、展開した右辺同士*6をそれぞれ足し合わせると:
  UaVb + UbVa = (2fafb − 2gagb)/(f − g)
  = 2(fa+b − ga+b)/(f − g) = 2Ua+b
これは②の両辺を 2 倍して、文字 F, G をそれぞれ U, V に置き換えたものと同一。つまり②に関しては、バイナッチでも、フィボナッチと全く同じ形の加法定理が成り立つ!

*6 分子に生じる計8項のうち、第1式から出る fagb, −gafb と第2式から出る fbga, −gbfa は、打ち消し合う。

〔例1〕 バイナッチ数列 Un の第3項と第5項から第8項を求める。
  2U8 = 2U3+5 = U3V5 + U5V3 = 6 × 152 + 44 × 20
  両辺を2で割って U8 = 3 × 152 + 22 × 20 = 456 + 440 = 896

バイナッチ数列とその相棒
n012345678
Un01261644120328896
Vn228205615241611363104

次に①のバイナッチ版。Lucas–Lehmer の文脈では①は必須アイテムではないのだが、せっかくなので、ついでにこっちも検討しておこう。証明法は、フィボナッチ①の直接証明とほぼ同じ。以下で見るように「Ub−1 を含む項が2倍される」という小さな違いが生じる。

スペース節約のため f − g を H と略すと、一般項の公式から:
  Ua+1Ub = (fa+1 − ga+1)/H × (fb − gb)/H = (faf − gag)(fb − gb)/H2  《ウ》
  UaUb−1 = (fa − ga)/H × (fb−1 − gb−1)/H = (fa − ga)(fbf−1 − gbg−1)/H2
f−1 = −g/2, g−1 = −f/2 という逆数関係*7を利用すると:
  UaUb−1 = (fa − ga)[fb(−g/2) − gb(−f/2)]/H2 = (fa − ga)[½(gbf − fbg)]/H2
逆数の分母が 2 なので ½ という因子が発生した。これを解消するため両辺を2倍する:
  2UaUb−1 = (fa − ga)(gbf − fbg)/H2  《エ》
《ウ》《エ》について、左辺同士と、展開した右辺同士*8をそれぞれ足し合わせると:
  Ua+1Ub + 2UaUb−1 = (fa+bH − ga+bH)/H2 = (fa+b − ga+b)/H = Ua+b

〔例2〕 a = 3, b = 5 とすると U8 = U3+5 = U4U5 + 2U3U4 = 16 × 44 + 2(6 × 16) = 896

バイナッチ数列の加法定理
  ① Ua+b = Ua+1Ub + 2UaUb−1  第2項の係数 2 がフィボナッチの①と違う
  ② Ua+b = (UaVb + UbVa)/2   フィボナッチの②と全く同じ形

*7 直接計算すると fg = (1 + √3)(1 − √3) = 1 − 3 = −2。あるいは x = f と x = g は x2 − 2x − 2 = 0 の2解だから、解と係数の関係から、同じ等式 fg = −2 を得る。その両辺の −½ 倍を考えると f⋅(−g/2) = (−f/2)⋅g = 1。

*8 《ウ》《エ》から生じる分子の計8項のうち、4項は打ち消し合い、次の4項が残る:
  fa+bf + ga+bg − fa+bg − ga+bf = fa+b(f − g) + ga+b(g − f) = fa+bH − ga+bH

*

これで出発の準備は整った! まずは前回同様、マイナス番目の項を考え、加法定理と組み合わせることで、バイナッチ数列の倍数構造(「星のらせん」)を解明したい。(続く)

⁂

2023-01-20 その数列は強いか? 「星のらせん階段」

#数論 #フィボナッチ #Lucas-Lehmer

ちょうど10段ごとに一周するらせん階段では、10段目・20段目・30段目…が、階段の基点(0段目)の真上になる。そのように、フィボナッチ数列では、第10項・第20項・第30項…が同じ倍数列の上で、きれいにハモっている
  F20 = 6765, F30 = 832040, F40 = …
が、全部 F10 = 55 でキッカリ割り切れる*9のだ!

この性質は、10に限らず任意の周期で成り立つ: F6, F12, F18, … も倍数列、F7, F14, F21, … も倍数列。その結果、例えば F20 は「F4 から始まる倍数列」、「F10 から始まる倍数列」など、複数の周期の「波」に乗っていて、自分自身も F20, F40, F60, … という新たな「波」の出発点となる。

画像: チューリッヒ中央駅のフィボナッチ数列フィボナッチ数で遊んでて、この性質に気付いたときは、ちょ~美しい!と感じ「星のらせん階段」と名付けた。フィボナッチ数の黄金比は、正五角形・星型と縁が深いので「星」。フィボナッチ数には、巻き貝のような「らせん」のイメージもある――この渦巻きは「ジョジョの奇妙な冒険」第7部でも、重要な小道具となってるようだ*10。スイスのチューリッヒ中央駅にも、らせんとフィボナッチ数を題材にした巨大オブジェがある(画像)。

「星のらせん」構造を持つ数列は、正式には divisibility sequence と呼ばれるらしい。フィボナッチのいとこ「バイナッチ」も同じ構造を持つが、フィボナッチは「強い」、バイナッチは「弱い」という違いがある。後学のため「強い・弱い」の意味を具体例で観察しておきたい。

*9 これらの数は 5 の倍数なので、11 の倍数であることさえ確かめれば、55 の倍数と分かる。11 の倍数を素早く見分けるには、奇数番目の桁の和から偶数番目の桁の和を引く方法がある:
  6765 → 奇数桁の和(7+5=12) − 偶数桁の和(6+6=12) = 0 → 0 は 11 の倍数なので 6765 も 11 の倍数
  832040 → 奇数桁の和(3+0+0=3) − 偶数桁の和(8+2+4=14) = −11 → −11 は 11 の倍数なので 832040 も 11 の倍数
「11で割り切れるかどうか」の判定だけなら、逆に偶数桁の和から奇数桁の和を引いてもよく、大きい方から小さい方を引けばいいのだが、奇数桁ひく偶数桁の順で引き算すると、11で割り切れない場合に「11で割った余り」の情報が得られる:
  (例) 1234 を 11 で割ると (2+4)−(1+3) = 2 余る
「余り」については mod 11 と考えてもいいし、必要なら 11 or 22 or 33 などを加減して0~10の範囲に調整してもいい:
  (例) 2143 を 11 で割ると (1+3)−(2+4) = −2 余る → プラス11補正して 9 余る

*10 斜め読みしただけなんでよく分かんないけど、自然界に存在する黄金比を使って、らせん状に攻撃のボール(?)を投げるみたいな設定。

*

【7】 フィボナッチ数列(各項は直前の2項の和)も、バイナッチ数列(各項は直前の2項の和の2倍)も、同じ「星のらせん」の構造を持っている。つまり、項の番号 n の倍数関係が、項の値 Fn ないし Un の倍数関係にそのまま反映される――例えば 4, 8, 12, 16, … は 4 の倍数なので、第4項・第8項・第12項・第16項…は第4項の倍数。同様に、10 と 15 はどちらも 5 の倍数なので、第10項と第15項は、どちらも第5項の倍数。

フィボナッチ数・バイナッチ数の因数: 丸かっこ内は新出素数
nFnUn
111
212= (2)
32= (2)6= 2⋅(3)
43= (3)16= 24
55= (5)44= 22⋅(11)
68= 23120= 23⋅3⋅(5)
713= (13)328= 23⋅(41)
821= 3⋅(7)896= 27⋅(7)
934= 2⋅(17)2448= 24⋅32⋅(17)
1055= 5⋅(11)6688= 25⋅11⋅(19)
1189= (89)18272= 25⋅(571)
12144= 24⋅3249920= 28⋅3⋅5⋅(13)
13233= (233)136384= 26⋅(2131)
14377= 13⋅(29)372608= 27⋅41⋅(71)
15610= 2⋅5⋅(61)1017984= 27⋅3⋅11⋅(241)
16987= 3⋅7⋅(47)2781184= 212⋅7⋅(97)
171597= (1597)7598336= 28⋅(67)⋅(443)
182584= 23⋅17⋅(19)20759040= 29⋅32⋅5⋅17⋅(53)

別の例として、第12項と第18項は、第6項の倍数。逆に言えば、第6項は第12項の約数であり、第18項の約数でもある――つまり、第6項は、第12項と第18項の公約数。ここまではフィボナッチもバイナッチも同じだが、この 6 という項の番号は、12 と 18 の最大公約数だ。フィボナッチの場合 F6 = 8 自身も F12 = 144 と F18 = 2584 の最大公約数になっている。この「番号の間の最大公約数の関係が、そのまま項の間の最大公約数の関係になる」という性質が strong divisibility というもの。一方、バイナッチ数列の場合、U12 と U18 の最大公約数を計算すると 3840 になる――従って U6 = 120 は、「最大公約数ではないただの公約数」の一つにすぎず、バイナッチ数列は strong divisibility を持たないということになる。

イメージ的な説明として、フィボナッチ数 F12 = 24⋅32 と F18 = 23⋅17⋅19 の因子の共通部分 23(要するに両者の最大公約数)は、純粋に、共通の先祖 F6 の「遺伝子」(因子)を受け継いだもの。U12 と U18 も、ご先祖 U6 の因子を100%受け継ぐ。ところが U12 = 28⋅3⋅5⋅13 と U18 = 29⋅32⋅5⋅17⋅53 の共通部分 28⋅3⋅5 = 3840 には、「純粋」に U6 = 23⋅3⋅5 の遺伝子が100%あるだけでなく「過剰」な部分がある: U6 と比べ 2 が 5 乗も増えている!

「先祖の遺伝子」ではないものが、どこからともなく入り込んでいるのだ。その理由も明らかだろう。バイナッチ数列では、新しい項を作るとき、直前の2項の和を「2倍する」という操作が行われる。「2倍する」というのは 2 を掛け算することなので、それによって因子「2」が強制追加され、直前の2項のどちらと比べても、「2」の指数が少なくとも 1 増えてしまう。いわば「遺伝子操作」。

〔補足〕 一つ一つの各項は、祖先から受け継いだものではない因子を含む(新出素数、または既出素数の指数が増える場合)。それはその項自体の「個性」であり、その項の子孫(倍数番目の項)たちに継承される。一方、直接の先祖・子孫関係にない二つの項 Fa, Fb について(直近の)共通の先祖 Fd を考えた場合、Fa, Fb の2項が「共通して持つ因子」は、全て Fd から受け継がれている。「共通して持つ因子」を考えることで、Fa, Fb それぞれの「個性の因子」は考察対象外となり、純粋に「遺伝関係」の問題となる。バイナッチの場合も「共通の祖先の因子は100%受け継がれる」点に変わりはないが、Ua, Ub は一般に「それ以外の“過剰”な共通因子」も持っている(具体的に、共通祖先は遺伝子「2」を少ししか持っていないのに、Ua, Ub はどちらも、先祖が持っていた以上の数の遺伝子「2」を持つ)。

先祖から子孫へ「倍数関係」を保存するという観点では、フィボナッチもバイナッチも問題ない。水増しの「2倍」があっても、やたらと大きな倍数になるだけで、倍数関係自体(例えば 7 の倍数が 7 の倍数であるという性質)は破壊されないからだ。一方、逆に子孫から先祖へさかのぼろうとすると、バイナッチ数列には「遺伝子操作」があるので、フィボナッチ数列ほど単純明快な構造にはならない。

【8】 先祖から子孫への「倍数関係」の継承。それは、加法定理が「倍数関係」を保存することの結果。すなわち、第 a 項と第 b 項がどちらも q の倍数なら、第 a+b 項も q の倍数。このことは、フィボナッチ数列に関しては【4】で考察した。バイナッチ数列に関しても同様で、
  Ua+b = Ua+1Ub + 2UaUb−1
なのだから(【7】)、もし Ua が q の倍数なら右辺第2項は q の倍数になり、もし Ub が q の倍数なら右辺第1項は q の倍数になる――その二つの条件が満たされるとき、Ua+b は q の倍数と q の倍数の和に等しく、再び q の倍数。

フィボナッチ数列またはバイナッチ数列の第 n 項が q の倍数だとして、加法定理で a = n, b = n とすれば、第 a 項も第 b 項も q の倍数; 第 a+b 項、つまり第 2n 項も q の倍数。今、あらためて a = 2n, b = n とすれば、再び第 a 項も第 b 項も q の倍数; 第 a+b 項、つまり第 3n 項も q の倍数。今、あらためて a = 3n, b = n とすれば…。と、この議論を必要なだけ繰り返すことで、第 n 項が q の倍数なら、第 kn 項も q の倍数(k: 任意の正の整数)。特に、第 n 項の値自身を q とすれば(そのとき第 n 項は q の 1 倍である)、「第 2n 項・第 3n 項・第 4n 項…がいずれも第 n 項の倍数」という「星のらせん」の性質が生じる。

「ある数が q の倍数」ということは「その数は q で割り切れる」ということなので、倍数関係とは、裏を返せば約数関係ともいえる。

数列における倍数・約数の関係が、最大公約数の関係にまで拡張できるかどうか――つまり strong divisibility が成立するかどうか――は、前記のイメージ的説明からも想像がつくように「子孫から先祖へ、ある種の“逆算”ができるか?」という問題と関連している。具体的には: 加法定理の足し算 a+b を引き算 a−b に置き換えた「減法定理」が、倍数関係を保存するか?

a と b の最大公約数を d としよう。もし第 a 項と第 b 項が q の倍数のときに第 a−b 項も q の倍数になる保証があるのなら、実はその性質を繰り返し使うことで第 d 項も q の倍数になる――このような引き算によって番号 a と b の項から番号 d の項に至ることは、ユークリッドの互除法で a と b の最大公約数 d を求めることに当たる。ここでは「互除法」の部分の説明を省き、「減法定理が倍数関係を保存するか?」を考えてみたい。フィボナッチ数列の減法定理について、答えが yes であることは、【4】で考察した。

フィボナッチ数列の「マイナス番目」の項は、対応する「プラス番目」の項と(符号は一致することも逆になることもあるが)絶対値が同じなので、第 b 項を考えても、第 −b 項を考えても、倍数・約数関係には一切影響しないのだった。

【9】 バイナッチ数列の場合、話はそう簡単にはいかない――マイナス番目の項は、知らないとびっくりするような振る舞いを見せる。

いつものように f = 1 + √3, g = 1 − √3, f−1 = −g/2, g−1 = −f/2 を使って、Binet 形式で第 −n 項を求めると:
  U−n = (f−n − g−n) / (f − g)  《カ》
《カ》の分子は:
  (f−1)n − (g−1)n = (−g/2)n − (−f/2)n = gn(−½)n − fn(−½)n
  = (−½)n × (gn − fn) = −(−½)n × (fn − gn)
従って《カ》は:
  U−n = −(−½)n × (fn − gn) / (f − g) = −(−½)n Un  《キ》

U−1, U−2, U−3, … は U1, U2, U3, … と比べて、絶対値がそれぞれ 1/2, 1/4, 1/8, … となる(符号は、奇数番目の項がプラス、偶数番目の項がマイナス)。バイナッチ数列のプラス番目の項は 1, 2, 6, 16, 44, … なので、対応するマイナス番目の項は 1/2 = 0.5, −2/4 = −0.5, 6/8 = 0.75, −16/16 = −1, 44/32 = 11/8 = 1.375, …。最初の(素朴な)驚きは、値が整数にならないことだろう。フィボナッチ数は、マイナス番目の項も含めて整数値なので…。けれどすぐ「バイナッチはプラス方向に行くとどんどん2倍されていくのだから、マイナス方向に行けば 1/2, 1/4, 1/8, … となるのは当然かも」と思い付く。ところが、よく検討すると、マイナス方向に行くとどんどん半分になるわけではなく、むしろ絶対値は増える。というのも、バイナッチ数列の増大は、大ざっぱに言えば fn によって支配される: f = 1 + √3 = 2.732… の n 乗は 2n より大きいので、因子 (½)n = 2−n による急激な減少より fn 本体の増加の方がでかく、トータルでは増加。

さて、加法定理① Ua+b = Ua+1Ub + 2UaUb−1 の b を −b に置き換える:
  Ua−b = Ua+1U−b + 2UaU−(b+1)  ← U−b−1 = U−(b+1)
《キ》を使って:
  Ua−b = Ua+1[−(−½)b Ub] + 2Ua[−(−½)b+1 Ub+1]
右辺第2項は 2Ua[−(−½)(−½)b Ub+1] = Ua[(−½)b Ub+1] なので:
  Ua−b = Ua+1[−(−½)b Ub] + Ua[(−½)b Ub+1] = (−½)b[UaUb+1 − Ua+1Ub]  《ク》

〔例〕 a = 7, b = 4, Ua = 328, Ua+1 = 896, Ub = 16, Ub+1 = 44:
  U3 = (−½)4[328 × 44 − 896 × 16] = (1/16) × 96 = 6
Ua = 328 も Ub = 16 も最大公約数 8 の倍数だが、「8 の倍数」という性質は Ua−b = 6 では保たれない。

バイナッチの Ua−b は、一般には倍数関係を保存しないが、Ua と Ub がどちらも「2 と互いに素な q」の倍数という条件下では Ua−b も q の倍数(ただし a > b)。実際、《ク》の角かっこ内は(Ua の倍数と Ub の倍数の差なので、仮定により q の倍数同士の差であり、従って)q の倍数。係数 (−½)b は因子 2 の数を減らすが、2 と互いに素な q の倍数性には影響を与えない(a−b は正の整数なので Ua−b は整数)。

【10】 整理すると…

項の番号の和は倍数・約数関係を保存 Fibonacci 数列でも Bi-nacci 数列でも、第a項・第b項が両方 q の倍数なら、第a+b項も q の倍数。言い換えれば: q が第a項・第b項の約数なら q は第a+b項の約数。

項の番号の差と倍数・約数関係 第a−b項について: Fibonacci 数列では第a+b項と同様、無条件で倍数性(約数性)が保存される。Bi-nacci 数列では、項の番号の差に関しては、一般には倍数性(約数性)が保存されない。

どちらの数列も倍数性(約数性)を保存する(divisibility sequence):
「a が d の倍数なら Fa は Fd の倍数」(a, d は正の整数)
 → 「d が a の約数なら Fd は Fa の約数」
 Fibonacci 数列は倍数性(約数性)を強く保存する(strong divisibility sequence):
 → 「d が a, b の最大公約数なら Fd は Fa, Fb の最大公約数」

(続く)

⁂

2023-01-23 LLT: Lehmer’s Lemma 1 ギネスに載る素数…?

#数論 #フィボナッチ #Lucas-Lehmer

新しいメルセンヌ素数が発見されると、場合によっては「世界最大の既知の素数」として、一般メディアでも話題になる。2023年1月現在の最大 [3] は、2018年に発見された 282589933 − 1 で、2500万桁に近い。

計算以前に「数字自体を書く」だけでも大変な巨大さで、1ページに1万桁ずつ書くとしても約2500ページ。毎秒1桁ずつ飲まず食わずで数字を書き続けたとして、書き終わるのは10カ月後だ!

そんなでかい数が素数か素数でないか、どうやって判定されるのか? 一般には困難な問題だが、メルセンヌ数に限っては「LLT」という方法がある。やり方自体はシンプルで、普通の人でも容易に理解可能。比較的小さいメルセンヌ数なら、ブラウザ上の JavaScript でも判定は可能。「なぜその方法で判定できるの?」という理論についても、基本アルゴリズムを完成させた D. H. Lehmer 自身による初等的な証明 [2] があり、フィボナッチ数列のいとこ「バイナッチ数列」と関係している。一連のメモでは、この証明を最終目的地として各ステップをのんびり検討し、興味を引くような話題があれば寄り道もして、いろんな景色を楽しみたい。

[3] List of Known Mersenne Prime Numbers — https://www.mersenne.org/primes/

*

【11】 D. H. Lehmer の証明は 3つの Lemmas(補題=補助命題)と本体から成り、古典的な整数論の範囲に余裕で収まる。難所があるとすれば、二項定理の「一年生の夢」だが、それは取り組む価値のある話題だし、寄り道で見える景色も楽しい(フィボナッチの「夢のもつれ」のバイナッチ版。これは次回に)。まずは最初の Lemma を…

LEMMA 1 3 以上の任意の素数 p を選んで固定する。バイナッチ数列 Un の第1項以降について、どれかの項が p の倍数になるとして*11、p の倍数になる最初の項の番号を w としよう。このとき、w の倍数番目の項はどれも p の倍数。それ以外の項は p の倍数ではない。言い換えると、ある項 Ux が p で割り切れるなら、その項の番号 x は w の倍数。

〔例1〕 p = 5 の倍数になる最初の項は、第6項 U6 = 120(下の表参照)。つまり w = 6。このとき、第6項・第12項・第18項…は、どれも p = 5 の倍数; それ以外の項は 5 の倍数にならない。言い換えると、第○項が 5 の倍数になるとすれば、その項の番号○は w = 6 の倍数。

〔例2〕 p = 11 の倍数になる最初の項は、第5項 U5 = 44。つまり w = 5。このとき、第5項・第10項・第15項…は、どれも p = 11 の倍数; それ以外の項は 11 の倍数にならない。言い換えると、第○項が 11 の倍数になるとすれば、その項の番号○は w = 5 の倍数。

*11 実はどんな素数 p を選んでも、バイナッチ数列の第1項以降のどれかの項は p の倍数になる(後述)。第0項 U0 = 0 も p の倍数だが、ここでは話を第1項以降に限る。

バイナッチ数列(第1項~第18項)
各項は直前の2項の和の2倍
n123456
Un1261644120
n789101112
Un328896244866881827249920
n131415161718
Un13638437260810179842781184759833620759040

証明はフィボナッチ版の【5】と同様――「星のらせん」構造に着目すると、Uw が p の倍数のとき、そのまた倍数 U2w, U3w, … も p の倍数ってことは明らかだが、「星のらせん」と無関係に、基礎から考えてみる。

加法定理により:
  U2w = Uw+w = Uw+1(Uw) + 2(Uw)Uw−1 = (Uw)(Uw+1 + 2Uw−1)
仮定により Uw は p の倍数だから Uw = p × A と書ける(A: 整数)。つまり:
  U2w = (p × A)(Uw+1 + 2Uw−1) = p × (A)(Uw+1 + 2Uw−1)
これは確かに p の倍数だ! U2w が p の倍数と確定したので U2w = p × B と書ける(B: 整数)*12。再び加法定理により:
  U3w = U2w+w = U2w+1(Uw) + 2(U2w)Uw−1 = U2w+1(p × A) + 2(p × B)Uw−1
  つまり U3w = p × [U2w+1(A) + 2(B)Uw−1]
これで U3w も p の倍数と確定したので U3w = p × C と書ける(C: 整数)。再び加法定理により:
  U4w = U3w+w = U3w+1(Uw) + 2(U3w)Uw−1 = U3w+1(p × A) + 2(p × C)Uw−1
  つまり U4w = p × [U3w+1(A) + 2(C)Uw−1]
これで U4w も p の倍数と確定したので…

以下同様、延々と続けられるので、U2w, U3w, … は、どれも p の倍数。

*12 上の式と見比べると B = A(Uw+1 + 2Uw−1)。 p = 11, w = 5 のケースで検算すると: Uw = 44 = p × 4 なので A = 4, B = 4(U6 + 2U4) = 4(120 + 2⋅16) = 608, p × B = 11 × 608 = 6688。これは確かに U2w = U10 と一致!

問題は「Uw, U2w, U3w, … 以外の項は p の倍数にならない」ことの証明。前回の《ク》の式(減法定理)がその鍵となる:
  Ua−b = (−½)b[UaUb+1 − Ua+1Ub]
a, b が正の整数で a の方が大きいとすると、a−b は正の整数。つまり、上記の左辺はバイナッチ数列のプラス番目の項なので、整数値を持つ。それと等しい右辺も、もちろん同じ整数。右辺の (−½)b の部分は、符号を無視すると ½ を b 回掛けること(つまり 2 で b 回割ること)だが、その結果が整数ってことは…?

角かっこ内の整数(それを K としよう)が、因子 2 を b 個以上、含んでる――ってことだ! つまり、
  K = 2 × 奇数
…の形を持ち、指数 ○ が b 以上なので、2 で b 回割っても大丈夫ってこと。

〔例〕 a = 8, b = 5 の場合、次のように ○ = 6 となる:
  K = UaUb+1 − Ua+1Ub = U8U6 − U9U5 = 896⋅120 − 2448⋅44 = −192 = 26 × (−3)
だから (−½)b = (−½)5 倍しても(つまり −2 で5回割っても)結果は整数:
  Ua−b = U8−5 = (−½)5[26 × (−3)] = −(21) × (−3) = 6  ← U3 に一致

今 Ua, Ub がどちらも p の倍数だと仮定すると(p は 3 以上の素数)、Ua = p × A, Ub = p × B と書ける(A, B は整数。前記の A, B とは無関係)。このとき…
  K = UaUb+1 − Ua+1Ub = (p × A)Ub+1 − Ua+1(p × B) = p × (AUb+1 − Ua+1B)
…も p の倍数なので、K は次の形を持つ:
  K = 2 × p × 整数*13
この値を (−½)b 倍すると、2 の指数 ○ は減少するが、それ以外の部分には影響せず、
  Ua−b = (−½)bK = ±2○−b × p × 整数
…の形になって*14、結果は依然として p の倍数。

*13 この整数は、「K = 2 × 奇数」の「奇数」を p で割った商。K は p の倍数なので、この奇数は必ず p で割り切れる(商は 1 以上の奇数)。

*14 先頭の ± は b の偶・奇による。 Ua−b は正の整数なので、この符号がマイナスの場合、K は負の整数。

要するに Ua, Ub が両方 p の倍数で a > b なら Ua−b も p の倍数。このことから、「w の倍数ではない変な番号の項 Uh が、p の倍数になる可能性」を否定できちゃうよ。だってさー、その変な番号 h を w で割って、商が k 余りが j とするとさー、こーなるじゃん?
  h = kw + j  ← h は w の倍数でないので w で割り切れず、1 以上 w 未満の余り j が発生
仮定の話として、もしも Uh = Ukw+j が p の倍数になるとしたら、何が起きるか…? Ukw が p の倍数であることは確定しているので、a = kw+j, b = kw と置けば Ua, Ub は両方 p の倍数になり(a > b)、従って Ua−b = Uj も p の倍数になってしまう!

証明の弁護人「異議あり、矛盾ですッ! p の倍数になる最初の項の番号が w なんだから、w より小さい番号 j に対して Uj が p の倍数ってことは、あり得ません!」

裁判長「異議を認めます。検察は不合理な仮定の話を撤回しなさい」

…ってなわけで「w の倍数ではない変な番号の項 Uh が p の倍数になる可能性」は、否定されちゃう。証明終わりッ。□

この議論はフィボナッチ数列の場合とほとんど同じだが、フィボナッチの場合、上記の p の代わりに、任意の整数 q を使うことができた。バイナッチの場合、p = 2 とすることは、できない。減法定理では因子 2 の数が変動し、Ua, Ub が両方「2 の倍数」だとしても Ua−b も 2 の倍数になる保証がないから…。

Lemma 1 の p(それは 3 以上の素数である)を一般の整数 q に拡張するとしたら、q は因子 2 を持つことができないので、「任意の奇数」に限る必要がある(フィボナッチ数では、倍数・約数関係について強い保存法則が成り立つが、バイナッチ数列ではそれが弱く、条件付きになる)。

(続く)

⁂

2023-01-29 美しいアラベスク ちょっと寄り道

#数論 #フィボナッチ #Lucas-Lehmer #二項定理

このメモで紹介する景色は、それ自体も素敵だが、フィボナッチ数の同様のパターンと見比べると「深い何か」が感じられる。整数と無理数が織り成す、繊細なアラベスク。

現象は小学生でも理解できるような単純なことなのだが、どうしてそうなるのか?という理由が、なかなか味わい深い。

フィボナッチ数列に比べると、バイナッチ数列は無名に近い存在で、そこに隠されているこのパターンは、ほとんど紹介されることもないだろう。半分寄り道になるけど、この秘密の花園を散策してみたい。

*

【12】 バイナッチ数列は 1, 2 から始めて(あるいは 0, 1 から始めて)、直前の2項の和の2倍を次の項としたもの:
  1, 2, 6, 16, 44, 120, 328, 896, …
最初の 1 を第1項、2番目の 2 を第2項、3番目の 6 を第3項…と呼び、それぞれ U1, U2, U3, … で表す(もし 0, 1 から始めた場合には 0 を第0項 U0 とする)。例えば U7 = 328 は直前の2項 44, 120 の和の2倍。

2 以上の整数のうち、1 と自分自身でしか割り切れない数を素数という。素数番目のバイナッチ数や、その前後のバイナッチ数には、次のような秘密が隠されている。

n が 5 以上の素数(5, 7, 11, 13, …)のとき、Un の直前か直後のバイナッチ数が n の倍数になる!

フィボナッチと比べバイナッチは、すぐに数がでかくなり、暗算では倍数関係を見通しにくい。でも、大きな数の割り算のことなんて、気にする必要ない。桁が多い数を見てもびびらず、純粋に「倍数関係のパターン」の存在それ自体に注目すると、何ともきれい…

バイナッチ数の秘密
nUn観察Un の値は…
11
22
36
4165の倍数+1
5445 は 12k±5型素数5の倍数−1
6120120 = 24 × 55の倍数7の倍数+1
73287 は 12k±5型素数7の倍数−1
8896896 = 128 × 77の倍数
92448
1066886688 = 608 × 1111の倍数
111827211 は 12k±1型素数11の倍数+1
124992049920 = 3840 × 1311の倍数+213の倍数
1313638413 は 12k±1型素数13の倍数+1
1437260813の倍数+2
151017984
16278118417の倍数+1
17759833617 は 12k±5型素数17の倍数−1
1820759040= 1221120 × 1717の倍数19の倍数+1
195671475219 は 12k±5型素数19の倍数−1
20154947584= 8155136 × 1919の倍数

詳しく言うと、5 以上の素数 n が12の倍数と1違いのとき(つまり12k±1型のとき)、Un直前のバイナッチ数 Un−1 がその n で割り切れる; 素数 n がそれ以外のとき(つまり12k±5型のとき)、直後のバイナッチ数 Un+1 がその n で割り切れる。本質的には「夢のもつれ」と同じ現象だが、「もつれ」をほどいて、もう一度整理し直してみたい。

〔イメージ音楽 ドビュッシー「アラベスク」第1番 arabesque_debussy.mkv
  https://invidious.esmailelbob.xyz/watch?v=Yh36PaE-Pf0&local=true より〕

【13】 バイナッチ数列の一般項は、Binet 形式で…
  Un = [(1 + √3)n − (1 − √3)n] / (2√3)  《サ》
…となる(ここで n は正の整数)。フィボナッチやバイナッチのような整数の数列の一般項が、無理数が絡んだこんな変てこな形になるということ自体、初めは意味不明に思えるかもしれない。これを一応きちんと理解することが、最初の一歩だろう。

《サ》の分子のようなパターンは、「和の n 乗」の展開と「差の n 乗」の展開の結果、プラスとマイナスが打ち消し合って、半分の項は消滅。打ち消し合わない残りの項は、符号が同じものが2個ずつあるので、それぞれ2倍になる。例えば…
  (x + y)3 = x3 + 3x2y + 3xy2 + y3
  (x − y)3 = x3 − 3x2y + 3xy2 − y3
…の上と下を足し合わせれば、右辺の奇数番目の項だけが残って
  (x + y)3 + (x − y)3 = 2(x3 + 3xy2)
になるし、上から下を引き算すれば、偶数番目の項だけが残って、こうなる:
  (x + y)3 − (x − y)3 = 2(3x2y + y3)

この具体例は、落ち着いて考えれば当たり前の単純計算だけど、そもそも (x + y)3 とか (x + y)4 とか (x + y)5 のような累乗の展開、一般に (x + y)n の展開は、どういう形になるのだろうか…。これについては「一年生の夢」にあるように、次のことを考える必要がある:
  ① 一つ一つの係数は「組み合わせの数」として、分数で表される
  ② その分数は必ず割り切れて、整数になる
「組み合わせの数」なので整数になるのは当たり前だけど、形式的・心理的な話として「なぜ分数が整数になる保証があるのか?」という素朴な疑問をクリアーにしておくと、気分がすっきり。

ここで「一年生の夢」が絡む: n を奇数の素数とすると、《サ》の分子から発生する二項係数は、ほとんど全て n の倍数。上記 (x + y)3 の右辺でいえば(n = 3)、両端の2項以外、係数は 3 の倍数になっている(この場合 3 の 1 倍、つまり 3 自身)。別の例として n = 5 の (x + y)5 の場合、両端以外の係数は 5, 10, 10, 5 で 5 の倍数だし、n = 7 の (x + y)7 の場合、それらは 7, 21, 35, 35, 21, 7 で 7 の倍数。結果として、
  (x + y)n − (x − y)n
の場合でいえば、n の倍数を無視すると、二項展開の最後の項だけが残って ≡ 2yn (mod n) となる。

上記のように、この引き算の形では偶数番目の項だけが残るので、両端の項のうち、左端の第1項はもともと消えている。n は奇数の素数なので、項の数 n+1 は偶数: 右端の最後の項は、偶数番目だから、残っている。両端以外は「一年生の夢」によって n の倍数なので、無視していい。三本線の合同記号 ≡ と丸かっこ内の mod n の意味は「n の倍数の差を無視すると、等しい」あるいは同じことだが「n で割った余りが等しい」(説明)。例えば 23 ≡ 8 (mod 5)。

《サ》の分子は x = 1, y = √3 のケースなので、もし n が奇数の素数なら、《サ》の分数は mod n でこうなる:
  Un ≡ 2(√3)n / (2√3) = (√3)n / (√3) = (√3)n−1

分子・分母の 2 を約分した。(√3) を n 個(例えば 5 個)掛け合わせたものを (√3) で割れば、商は (√3) を n−1 個(例えば 4 個)掛け合わせた積になる:
  (√3)(√3)(√3)(√3)(√3) / (√3) = (√3)(√3)(√3)(√3)

複雑そうな《サ》が、やけにシンプルになった! しかも、この n は奇数なので n−1 は偶数であり、2 で割り切れる。ということは…
  Un ≡ (√3)n−1 = (√3)2×(n−1)/2 = [(√3)2](n−1)/2 = 3(n−1)/2  《シ》

n = 5 の例では (√3)4 = [(√3)2]2 = 32 となる。ベタに書けば:
  (√3)(√3)(√3)(√3)(√3) / (√3) = (√3)(√3)(√3)(√3) = (√3)4 = 32

《シ》の Un ≡ 3(n−1)/2 (mod n) の右辺は、オイラーの判定基準の形だ: n を 5 以上の素数とすると、3 が n の平方剰余か非剰余かに応じて ≡ ±1 (mod n)。要するに Un は n の倍数±1。第三補充法則*15によれば、素数 n が12k±1型なら 3 は平方剰余、12k±5型なら非剰余なので、前者では Un は n の倍数より 1 大きく、後者では n の倍数より 1 小さい。前者の例として、U1111 の倍数より 1 大きい。後者の例として、U55 の倍数より 1 小さい; U77 の倍数より 1 小さい。【12】で観察した「バイナッチ数の秘密」のうち、(第5項以降の)素数番目のバイナッチ数の性質が、これで明らかになった!

*15 教科書的には、3 の平方性は、平方剰余の相互法則から、記号操作で導出される(「遊ばせて」§6末尾の☆☆参照)。一方、われわれはガウス直伝の方法で、相互法則を介さず、直接これを得た――論理的には冗長だが、±2 や ±3 の平方性がパッと分かるのは便利だし、直接証明には(形式的な記号操作と比べると)一種の充実感がある。

【14】 引き続き 5 以上の素数(それを p とする)について、今度は第 p 項の次の項――つまり Up+1――の値を考えてみよう。「夢のもつれ」にあるような「一年生の夢」のバリエーションが発生し、p+1 乗の二項展開では、左端の2項と右端の2項以外は p の倍数となる。

〔例〕 p = 5 のとき 6 乗の二項係数 1, 6, 15, 20, 15, 6, 1 のうち、左端の 1, 6 と右端の 6, 1 以外(つまり 15, 20, 15)は p = 5 の倍数。
同様に p = 7 のとき 8 乗の二項係数 1, 8, 28, 56, 70, 56, 28, 8, 1 について、両端から2番目までを除く各項は p = 7 の倍数。

要するに (x + y)p+1 を展開した場合、mod p では、両端から2番目までの計4項だけを考えればいい(それ以外の項は p の倍数なので、無視可能)。

(x + y)n の展開の二項係数について、両端の係数は 1 であること、端から2番目の係数は n であることに注意する。

ところで n = p+1 なので、もちろん n−1 = p

(飾りの画像: ドビュッシーの「アラベスク第1番」の楽譜より)

さて (x + y)n の展開では、xn を含む項から x0 を含む項まで、計 n+1 個の項が生じる。
  (x + y)n − (x − y)n
という引き算の形では、前半の二項展開と後半の二項展開の相互作用の結果、それぞれの奇数番目の項は打ち消し合い、偶数番目の項の2倍だけが残るのだった。n = p+1 は偶数なので、p+1 乗の二項展開では n+1 = p+2 個(つまり奇数個)の項が発生するけど、奇数番目の項は消えてしまうのだから、最初の項と最後の項は消える。「両端から2番目までの計4項だけ考えればいい」ことと「最初の項と最後の項は奇数番目で消滅」というから、二項展開に関しては、左から2番目と右から2番目の計2項だけを考えればいい。それらの項の二項係数は n つまり p+1 であり(なぜなら端から2番目)、係数が掛かっている xy は、左から2番目の項では xn−1y1 つまり xpy(なぜなら n−1 = p)、右から2番目の項では x1yn−1 つまり xyp。以上を総合すると:
  (x + y)p+1 − (x − y)p+1 ≡ 2[(p+1)xpy + (p+1)xyp] (mod p)
  共通因数をくくり出すと ≡ 2(p+1)xy[xp−1 + yp−1] (mod p)
最後の p+1 の部分は ≡ 1 (mod p) なので(なぜなら p+1 を p で割れば 1 余る)、係数としては 1 と同じで省略可能:
  (x + y)p+1 − (x − y)p+1 ≡ 2xy(xp−1 + yp−1) (mod p)  《ス》

〔例〕 x = 3, y = 1, p = 5 のとき《ス》は:
  左辺 (x + y)p+1 − (x − y)p+1 = 46 − 26 = 4096 − 64 = 4032
  右辺 2xy(xp−1 + yp−1) = 2⋅3⋅1(34 + 14) = 6(81 + 1) = 6 × 82 = 492
どちらも 5 で割ると 2 余るので、確かに 4032 ≡ 492 (mod 5)

今、一般項の公式《サ》の n に p+1 を入れると:
  Up+1 = [(1 + √3)p+1 − (1 − √3)p+1] / (2√3)
この分子は、《ス》で x = 1, y = √3 としたものだから:
  Up+1 ≡ {2⋅1⋅√3[1p−1 + (√3)p−1]} / (2√3) = 1p−1 + (√3)p−1 = 1 + 3(p−1)/2 (mod p)
ここで (√3)p−1 の計算は、【13】の (√3)n−1 の計算と全く同様で、結果は再びオイラーの基準の形に。従って:
  p が12k±1型素数なら Up+1 ≡ 1 + 1 ≡ 2 (mod p)
  p が12k±5型素数なら Up+1 ≡ 1 + (−1) ≡ 0 (mod p)
前者では Up+1 は p の倍数より 2 大きく、後者では p の倍数に等しい。前者の例として、U1211 の倍数より 2 大きい。後者の例として、U65 の倍数; U87 の倍数。【12】で観察した「バイナッチ数の秘密」のうち、(第5項以降の)「素数+1」番目のバイナッチ数の性質が、明らかになった!

【15】 p が12k±1型の素数なら、【13】から Up ≡ 1 (mod p)、【14】から Up+1 ≡ 2 (mod p)。この Up+1 は、バイナッチ数列の性質上、直前の2項の和の2倍だから、次の関係が成り立つ:
  2(Up−1 + Up) ≡ Up+1 (mod p)
  つまり 2(Up−1 + 1) ≡ 2 (mod p)
両辺を 2 で割ると(2 と p は互いに素なので割ってもいい):
  Up−1 + 1 ≡ 1 (mod p)
  つまり Up−1 ≡ 0 (mod p)
これは Up の一つ手前の項 Up−1 が p で割り切れること(言い換えれば p の倍数であること)を意味する。

同様に p が12k±5型の素数なら、【13】から Up ≡ −1 (mod p)、【14】から Up+1 ≡ 0 (mod p) なので:
  2(Up−1 − 1) ≡ 0 (mod p)
  これを解くと Up−1 ≡ 1 (mod p)
これは Up の一つ手前の項 Up−1 が p の倍数より 1 大きいことを意味する。

前者の例として、U1011 の倍数。後者の例として、U45 の倍数より 1 大きい; U67 の倍数より 1 大きい。

これで【12】で観察した「バイナッチ数の秘密」は、全て明らかになった!

*

「LLT」の証明に必要なのは、【13】の結論の Up (mod p) の値と、それに対応する相棒 Vp (mod p) の値だけで、今回のメモの内容は大部分、無関係な寄り道に当たる。けれど、ここを通りがかって、この素敵な景色を楽しまないのは、もったいない。

フィボナッチ数列は、もともと文字通り Arabesque(アラビア風)だった。学術が停滞していた中世ヨーロッパにおいて、進んでいたイスラム圏の数学が研究され、フィボナッチ数列もその結果の一部だったらしい。三角関数もイスラム文化から移入されたものだし、現在の普通の「数字」のコンセプトもアラビア経由でヨーロッパに伝わったようだ(発祥はインドかもしれない)。当時、イスラム文化が花開く一方、ヨーロッパがいわゆる暗黒時代であった背景については、いろいろな研究があるのだろうが、気候が関係していたという説もある。中世ヨーロッパは平均気温が低く、その影響で食糧事情も不安定で、そこから争いや暴政・迷信、ひいては魔女裁判のような宗教的暴走が生じ、科学はあまり進歩しなかった――という解釈も成り立つ。アラビアは暑いイメージがあるが、寒過ぎる当時のヨーロッパと比べると、温暖で快適だったのかもしれない。

(続く)

⁂


<メールアドレス>