妖精現実

[ 新着記事 | 数学・プログラミング | 天文・暦
| シリア語・Unicode・詩 | ジョーク | 漫画・アニメ
| 字幕 | 哲学・ファンタジー | 全記事 ]

チラ裏コーナー（過去のチラ裏 | 野蛮な解法）

2020-07-07　野蛮な解法（その29の続き）

【5】 ケイリーの公式は、計算上は一般的に成立するが、実用上、ペル方程式の解法に役立つのは一定の場合に限られる。

〔悪い例〕　d = 11 とする。T² − 11U² = 4 の最小解は:
20² − 11 × 6² = 4　（ガ）
これに (V) を適用すると:
3970² − 11 × 1197² = 1　（ク）
（ク）は d = 11 の場合のペル方程式の解の一つだが、最小解
10² − 11 × 3² = 1　（カ）
とは異なる。右辺4の場合の最小解からスタートしたのに、右辺1の場合の最小解（カ）ではなく、ややこしい（ク）が出てきてしまった。何が悪かったのか。そもそも（ガ）の各項は 4 = 2² の倍数なのだから、単に（ガ）の両辺を4で割れば（カ）になっていた。公式からも【4】の証明からも明らかなように、(V) ではもともとの解が大ざっぱに3乗される。下手に使うと、最小解ではなく第3解が出てきてしまう。T = 20, U = 6 のように両方偶数の場合、この公式を使うのではなく、単にそれらの偶数を2で割ればいい（平方された結果としては、4で割ることに相当）。t, u が両方偶数の場合についても、(IV) から明白なように T, U が両方偶数になるので、同じこと。本筋と関係ないが、参考までに（カ）と（ク）の間にある第2解は:
199² − 11 × 60² = 1　（キ）

〔別の種類の悪い例〕　d = 12 とする。T² − 12U² = 4 の最小解は:
4² − 12 × 1² = 4
これに (V) を適用すると:
26² − 12 × (15/2)² = 1
…計算は合っているが、整数解を求めたいのだから、これでは役立たない。T, U がそれぞれ偶数・奇数の場合、(V) を適用すると y 側に2分の1の端数が生じてしまう。t, u がそれぞれ偶数・奇数の場合も (IV) を適用すると (V) において同じ状態に。では T, U ないし t, u がそれぞれ奇数・偶数 の場合はどうか。その場合、
T² − dU²
のような式は「奇数マイナス偶数」で値が奇数。偶数である ±4 になり得ない。

結局、両方偶数も駄目だし、片方だけ偶数も駄目。ケイリーの公式が奏功するとすれば、T, U などが両方とも奇数の場合である。例えば
261² − 109 × 25² = −4
のような形が得られたなら、見込みがある。

【6】 上記のことから、公式の適用条件をもっと具体的に限定できる。mod 8 で考えると、(V) が有用なのは
T² − dU² ≡ 4 (mod 8)　（＊）
において T, U がどちらも 1, 3, 5, 7 (mod 8) のどれかになる場合だが、これら16通りの組み合わせに対して、d ≡ 0, 1, 2, …, 7 (mod 8) の8パターンを考えると、（＊）が成り立つ可能性があるのは d ≡ 5 (mod 8) のみ。(IV) についても同様。

〔証〕　仮定より T, U はどちらも ≡ ±1, ±3 (mod 8)、ゆえに T², U² はどちらも ≡ 1。従って（＊）は 1 − d ≡ 4 (mod 8) を含意する。つまり d ≡ 5。□

すなわち、ケイリーの公式が役立ち得るのは d ≡ 5 (mod 8) の場合のみであり、しかも、T, U などを奇数に限定できる（もし仮に限定なしの検索を行い、右辺が ±4 の偶数解が得られた場合、ケイリーの公式を使わず直ちに各項を4で割れば、正または負のペル方程式の解が得られる）。

〔例〕　d = 37 ≡ 5 (mod 8) のとき、外形的には公式が役立ち得るが、実際には (IV), (V) は奇数解を持たない（ブルートフォースの立場からは、このことは「やってみないと分からない」）。もし仮に検索を奇数に限定しない場合、
12² − 37 × 2² = −4
が見つかるが、この偶数解に (IV), (V) を適用すると、最初の「悪い例」と同様の結果になる。このような最小解が得られた場合、両辺を4で割り
6² − 37 × 1² = −1
としてから「負のペル」に対する通常の扱いを行えば、ペル方程式の最小解が得られる。この場合、最初から「負のペル」の検索を行っていれば、半分の検索範囲（半分の時間）で同じ結論が得られていた。

「奇数解が存在せず、偶数解なら存在するケースがあるのだから、両方探した方がいいのではないか。そのような場合、奇数解だけを探すと、いつまでたっても検索が終わらない。偶数解も探していれば、効率はともかく、少なくとも検索は完了する」という疑問が生じるかもしれない。マルチスレッドが許されるなら、±4 の奇数解と ±1 の整数解を平行して検索するのが最も効率的だろう。シングルスレッドの場合は微妙だが、奇数だけを探せば（奇数・偶数両方の検索に比べ）半分の時間で済む。2倍の高速化ができるポイントなので、できればそれを生かしたい。

普通のアルゴリズム（平方根の連分数展開を利用）では、上記の疑問は自然に消滅する（ケイリーのノットもそういう記述になっている）。ブルートフォースは「連分数というレーダー」を見ないで行うブラインド・アタックなので、この部分の見通しが利かず、何が最善なのか即断できない。

「8k+5型の d 専用」なので若干使い道が限られるが、うまくいくかどうかは別として、全素数の約25%に適用でき、同じ型の合成数にも適用できる。d < 1000 の範囲で実際に試すと、適用可能なケースの半数以上でうまくいくようだ。特に d = 61, 109, 188 のような「ペル方程式が記録的に大きい解」を持つ場合（言い換えれば、単純なブルートフォースでは非常に時間がかかる場合）、桁違いの高速化を期待できる。d = 109 のケースは、最初にやったとき、10分くらいかかった。それが一瞬。「負のペル」経由と比べても、実測で50倍くらい速く、ミリ秒（1000分の1秒）未満で検索完了する。

2020-07-03　野蛮な解法（その29）　ケイリーのノット

【1】　ペル方程式 x² − dy² = 1 を直接解かなくても、その右辺を −1 または ±2 にした式の解が見つかれば、間接的にペル方程式の解が得られる:

(I)　A² − dB² = −1 ならば x² − dy² = 1 である。ここで x = A² + B²d, y = 2AB。（「その24」参照）

(II)　A² − dB² = −2 ならば x² − dy² = 1 である。ここで x = A² + 1, y = AB。（その28）

(III)　A² − dB² = 2 ならば x² − dy² = 1 である。ここで x = A² − 1, y = AB。（その28の追記）

この手法により、d = 500 以上まで「ブルートフォースで」ペル方程式を解けるようになった…ただ一つの例外 d = 421 を除いて。x² − 421y² = 1 の最小解は40桁くらいあって、とてもブルートフォースでは解けない。対応する (I) の解も17桁で、ブルートフォースでは時間がかかり過ぎる。このケースでは (II), (III) の手法も使えない。

「ブルートフォースで」という縛りは「できるかな？」という遊びであり、普通の解法を使えば d = 421 が難しいわけではない。でも、たった一つの d のため「d = 500 までコンプ」できないというのも悔しい。このケースに使えるうまい手は無いか？

【2】　(I)～(III) を眺めていると、A² − dB² = ±4 からのショートカットも可能なのでは、という考えが浮かぶ。d = 421 については
444939² − 421 × 21685² = −4
という事実もある。これを利用できないか？

19世紀の英国の数学者 Cayley（ケイリー）は、この種の状況について、こう指摘した [1]。

(IV)　t² − du² = −4 ならば T² − dU² = 4 である。ここで T = t² + 2, U = tu。

(V)　T² − dU² = 4 ならば x² − dy² = 1 である。ここで x = (T³ − 3T)/2, y = (T² − 1)U/2。

【3】　ケイリーのような大数学者は、この問題をどういう角度から眺めていたのだろうか？　それを紹介する前に、比較のため、素朴な方法で同じ結論を導いてみよう。(IV) は易しい。−4 を +4 にしたいのだから2で割って2乗するか、（同じことだが）2乗して4で割ればいい。
(t² − du²)² = 16 の左辺は
t⁴ − 2t²du² + d²u⁴ = (t² + du²)² − 4(tu)²d
仮定により du² = t² + 4 なので上記右辺は
(t² + t² + 4)² − 4(tu)²d = [2(t² + 2)]² − 4(tu)²d = 4(t² + 2)² − 4(tu)²d
これが 16 に等しいというのだから 4 で割ると
(t² + 2)² − (tu)²d = 4

〔例1〕　d = 13, t = 3, u = 1, 3² − 13 × 1² = −4 のとき
T = 3² + 2 = 11, U = 3 × 1 = 3, 11² − 13 × 3² = 4

(V) については、仮定より dU² = T² − 4。その両辺に (T² − 1)² を掛けて
dU²(T² − 1)² = (T² − 4)(T² − 1)² = (T² − 4)(T⁴ − 2T² + 1)
= T⁶ − 6T⁴ + 9T² − 4 = (T³ − 3T)² − 4
これを整理した (T³ − 3T)² − d[(T² − 1)U]² = 4 の両辺を 4 で割れば、書かれている通りの結果を得る。□

〔例2〕　d = 13, T = 11, U = 3, 11² − 13 × 3² = 4 のとき
x = (11³ − 3 × 11)/2 = 649, y = [(11² − 1) × 3]/2 = 180, 649² − 13 × 180² = 1

【4】　上記 (V) の証明は透明でない。なぜ dU² = (T² − 4) からスタートし、なぜ両辺に (T² − 1)² を掛けるのか。必然性が感じられない。(IV) の証明にしても、
(a − b)² = (a + b)² − 4ab
のパターンは「よく使われるトリック」ではあるが、なぜそれをここで使うのか。

ケイリー自身の考え方は、かみ砕いて言うと、次の通り。
t² − du² = (t + u√d)(t − u√d) という分解を念頭に置いて、(IV) の前提条件を
(t + u√d)(t − u√d) = −4
と書く。その両辺を平方する。左辺の平方は次のようになり、これが右辺の平方 16 に等しい:
(t + u√d)²(t − u√d)² = (t² + du² + 2tu√d)(t² + du² − 2tu√d)
= (2t² + 4 + 2tu√d)(2t² + 4 − 2tu√d) = (2t² + 4)² − (2tu)²d
2個目の等号では、du² = t² + 4 を使った。…最初の証明と同じようなものだが、トリッキーな面がなくなった。

(V) については、同様の手法が（証明の上で）絶大な効果を発揮する。(T + U√d)(T − U√d) = 4 の両辺を立方すると:
(T + U√d)³(T − U√d)³ = 64　（ア）
左辺の前半について、機械的に計算すると:
(T + U√d)³ = 4(T³ − 3T) + 4(T² − 1)U√d
途中経過は略したが、3乗の部分を展開して整数部分とそれ以外（√d を含む部分）をそれぞれまとめ、dU² = T² − 4 を使って整理しただけ。見やすくするため
A = 4(T³ − 3T), B = 4(T² − 1)U　（イ）
と書くと (T + U√d)³ = A + B√d となる。同様にして（ア）の左辺後半は
(T − U√d)³ = A − B√d となる。従って（ア）は、こうなる:
(A + B√d)(A − B√d) = A² − B²d = 64
この真ん中の式について（イ）の省略記法を元に戻すと:
16(T³ − 3T)² − 16[(T² − 1)U]²d = 64
両辺を 64 = 16⋅2² で割ると:
[(T³ − 3T)/2]² − d[(T² − 1)U/2]² = 1
すなわち x = (T³ − 3T)/2, y = (T² − 1)U/2 と置けば x² − dy² = 1 である。

…淡々と計算するだけで、自然に結論が得られた！　最初の証明（論理は分かるが、意味が分からない）とは大違い。

半面「整数解の話なのに、なぜ無理数が出てくるのか」「立方するという発想はどこから出てきたのか」といった別の疑問が生じるかもしれない。それをきっちり理解するには、少し準備が必要だが、遊びのような具体例を通じて「普通の整数の背後にある少し深い世界」を垣間見るのも悪くないかと…。ケイリーは同じノットの中で、右辺 −4 のペル型方程式から、右辺 −1 のペル型方程式の解を導く方法にも言及している。

Cayley は英国人だが、英語だけでなく時々フランス語で論文を書いた。1857年のこの Note もフランス語（だから「ノート」でなく「ノット」）。19世紀にはまだ「共通語＝ラテン語」時代の余韻が強く、国際的な学術の世界でも、今より言語的多様性が大きかった。Note で言及されている「Degen の表」はラテン語の文献で、ペル方程式の解を d = 1000 まで収録。Cayley 自身、後にこれを拡張して d = 1001 から 1500 までの表を作った。

[1] A. Cayley, Note sur l’équation x² − Dy² = ±4, D ≡ 5 (mod. 8)
http://www.digizeitschriften.de/dms/resolveppn/?PID=GDZPPN002149834 　［367～371ページ］
https://archive.org/details/collmathpapers04caylrich 　［論文集・第4巻40～42ページ］

2020-07-01　地球の自転が一時的に速くなっている　1日の長さ24時間を切る

精密に測ると地球の自転は日々変動しているが、長期的にはだんだん遅くなっている。「自転による1日は、定義上の24時間＝86400秒より1ミリ秒（1000分の1秒）くらい長い」というのが、これまでの大ざっぱな感覚だった。だから1000日くらい（数年）のオーダーで地球は時計より1秒遅れ、時計合わせのため「うるう秒」が挿入される…と。

ところが実測で、2020年6月5日ごろから、86400秒かからないで自転が終わる状態が続いている。「自転と時計の差」（UT1−UTC）が普通ならだんだん減るはずなのに（自転より時計の方が進みが速いので、マイナスが大きくなる）、逆に少しずつ増えている。この傾向は9月頃まで続き、その後も時々自転が速めになると予想されている（[1]）。このこと自体は、決して異常ではない。2004年ごろにも同様のことが起こり、その影響で7年間くらい一度もうるう秒がないことがあった（[2]）。24時間を切ったと言っても違いは、せいぜい1ミリ秒。地球の自転と無関係に1日は通常86400秒に固定されているので、生活に影響が出るわけではない。大昔の地球はもっと速く回っていて、1日が23時間だったときもあるというのだから、1ミリ秒ずれたくらいで、大騒ぎすることもないだろう。

しかし年オーダーの短期的な話として、「うるう秒が入らない最長期間」の新記録になる可能性がある。「うるう秒」制度が始まって以降、これまでの最高記録は「7年間うるう秒なし」。協定世界時（UTC）1998年12月31日の末尾（日本時間1999年1月1日8時59分59秒の後ろ）にうるう秒が挿入されてから、UTC2005年の末尾に再びうるう秒が入るまで7年あいた。前回のうるう秒はUTC2016年末。2020年末のうるう秒の有無が公式発表されるのは数日後だが、UT1−UTCマイナス0.2秒台で「うるう秒」という先例は、21世紀に入ってから1度もない。マイナス0.5秒になりそうな辺りで挿入してプラス0.5秒側に振るのが、常識的に無難な線だし、最近の運用は実際そんな感じ。

前回の「7年間なし」記録のときは、うるう秒を入れてから4年で、またマイナス0.3秒くらいまで地球が遅れた。一方、2020年末にうるう秒がない場合、結果は「ずれマイナス0.2秒くらい」＝前回の同じ条件より、ずれのペースが小さめ。この調子だと「8年間うるう秒なし」、場合によっては「10年間なし」といった新記録もあり得る。

地球の自転は、大ざっぱに10～20年の周期で速くなったり遅くなったりしているらしい。グラフ [3] を見ての漠然とした印象だが、現在入りつつある「谷」（1日の長さが短くなる）は前回よりちょっと深いかも…。地球の自転は気象の影響も受けているので、気象の乱れも関係しているのかもしれない。地球の自転が速めになるのは、UTCがずれにくいという点では良いこと。これまでの遅れの「貯金」がたっぷりあるので、「負のうるう秒」などという事態にはならない。長期的には、どっちにしても誤差の範囲内の揺らぎだろう。

[1] https://datacenter.iers.org/data/latestVersion/6_BULLETIN_A_V2013_016.txt

[2] https://en.wikipedia.org/wiki/File:Deviation_of_day_length_from_SI_day.svg

[3] https://en.wikipedia.org/wiki/File:Leapsecond.ut1-utc.svg