遊びの数論

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


遊びの数論(メモ)の目次

コンラッドの不等式とか

2020-07-26 谷山予想(フェルマーの最終定理を含む)を証明したコンラッド

…というと雲の上の人のようだが、数学の世界に貴賎(きせん)はない。拡張ペル方程式に関連して、Brian Conrad のテキストの主定理の改善に成功した!

まず旧バージョン(2017年)の上界。
PNGファイル

こちらが新バージョン(2020年)の上界。数時間前に思い付いて、速攻メール。教授も同意、たまたま日曜だったせいか、ものすごい勢いでテキストが更新された。
PNGファイル
この強い上界を使うと、検索が有意に高速化するばかりか、冗長な「同値解」が出にくくなる。ブルートフォースから生まれた「野蛮流」も、とうとう世界的数学者のお墨付き?(笑)な~んてネ…単なるワンアイデアだが、うまいショートカットが見つかると普通にうれしい。

http://virtualmath1.stanford.edu/~conrad/154Page/ ここにある Generalized Pell equation のファイル。証明の道筋が非常に面白いけれど、バリバリの代数的整数論の言葉で書かれていて、このファイル自体は一般向けではない。しかし「ごく普通の高校生にも十分理解できる」ような普通の言葉で説明可能なので(数学が好きなら中学生でも分かる)、できれば近々一般向けの記事にしたい(→ 妖精の森 ♌︎ ペル方程式の夏)。

↓思い付いたときのメモ。使用済みルーズリーフの、字が書いてない隙間に走り書き。
JPGファイル

2020-07-27 コンラッドの不等式について

誰にでも意味が分かるような、シンプルな問題。例えば…
x2 − 79y2 = 5 は整数解を持たないことを証明せよ」
左辺の xy にどんな整数を入れても、右辺は5にならないんだよ~と。ちょっと試せば確かに解は見つからないが、もしかして、この式を満たすような100桁くらいの巨大な解があるかもしれない。「そんなものは絶対存在しない!」と数学的に証明するのは、決して簡単ではない。

必要な予備知識は対数関数の基本だけ。でもこの証明は「普通」の数学の発想とは、あさっての方角に懸け離れている。数論が好きな人でも初めて見ると「不思議な証明だなぁ」と感じるかもしれない。本質的に代数的整数論の世界だが、ちょっと感覚が違う点がある(だって普通、二次体の整数論の入門的部分に、対数関数なんて出てこないでしょう)。

一定の場合には、剰余演算さえ導入すれば、この手の問題は易しい。上記の例は、その手法が使えないケース。平方根の連分数展開を使う方法もあるが、右辺の整数の絶対値が大きい場合、実用上、話がややこしくなる。「解があれば、必ずこの範囲にある」という明示的な範囲指定をして、その範囲を探す…というのが、面白いアプローチ。種を明かせばレギュレーターというか、単数定理の埋め込み写像的な発想なんだろうけど、拡張ペルの解をある方法で平面に配置すると等間隔で並ぶ。その間隔を1とすると、必ず一定の場所からずれが1/2以下になる解を選べる。従って、解が存在する場合、最小解の x が取り得る範囲は有限なのである。

この説明だけでは、何のことやら…? とにかく不等式で x の範囲を指定できる、という方向で…

コンラッドは c2(α) の絶対値が 1/2 以下という状況を作って、
【+】 log | x + yd | = (1/2) log | n | + c2(α) log u ≤ (1/2) log | n | + (1/2) log u
【-】 log | x − yd | = (1/2) log | n | − c2(α) log u ≤ (1/2) log | n | + (1/2) log u
と評価していた。確かに ±c2(α)−1/2 以上 1/2 以下なので、どちらにしても ±c2(α) ≤ 1/2 であり、上記のようになる。どちらの右辺も log (| n |u)1/2 に等しいことに注意しつつ、これらを全部 e の肩に乗せ、辺々足し合わせると
2x ≤ 2(| n |u)1/2
となり、その両辺を2で割ると2017年版のシンプルな上界を得る。

しかしもし c2(α)0 以上だったら(仮定1)どうだろう。そのときは c2(α) log u ≤ 0 なので【-】の式の不等号の右側、一番右端の項 + (1/2) log u を落とす(なくす)ことができる(log u > 0 であることは分かっている)。あるいはもし c2(α)0 未満だったら(仮定2)どうだろう。同様の理由から、今度は【+】の右端から + (1/2) log u を落とすことができる。仮定1と仮定2のどちらか一方は必ず成り立つのだから、いずれにしても、どちらか一方の式から + (1/2) log u を落とすことができる。双子の不等式のうち、一方については確かに log (| n |u)1/2 以下としかいえないが、他方についてはもっと本気を出して Gyu! と押さえると log (| n |)1/2 まで縮む。こうして改善された評価について、最初と同じように、e の肩に乗せ、辺々足し合わせて2で割ると、2020年版の強い上界を得る。どっちの式から + (1/2) log u を落とせるのか確定できないが、どうせ足し合わせて2で割るのだから、どっちがどっちでも構わない。

これで分かるように、「コンラッドの主定理を改善」といっても、その中身は単純で小さなアイデアにすぎない。このアイデアがどこから来たかというと…。まず仮定1を考えた。【-】左辺の c2(α) log u は事実として 0 以下なのに、それをわざわざ + (1/2) log u 以下だと評価するのは「もったいない」と感じた。けれど c2(α) は負かもしれず、仮定1が成り立つ保証はないので、一般論としては、最悪のケースでも大丈夫なように、そう評価するしかないのか…。ん、待てよ。仮定1が偽なら、自動的に仮定2が成り立つんだから…。という流れ。

単に技術的に上界を改善できるだけでなく、多くの場合、これによって検索結果から冗長性を排除できる。この副産物が数学的には一番大きいかもしれない。

2020-07-31 双子の数学者

谷山予想の Brian Conrad と、コネチカットの Keith Conrad は、どちらも数論研究者で、きょうだい。確認はできなかったが、ウィキペディアによると双子らしい。

Keith Conrad のサイトは宝箱のよう。面白いものがいっぱいある。専門的なものも多いが、初心者向け・中級者向けのものも…。
https://kconrad.math.uconn.edu/blurbs/
拡張ペル方程式の話題もあって、こちらは(Brian Conrad版と違い)一般向けとして、お薦めできる。
https://kconrad.math.uconn.edu/blurbs/ugradnumthy/pelleqn1.pdf
https://kconrad.math.uconn.edu/blurbs/ugradnumthy/pelleqn2.pdf

Brian Conrad の不等式を改善してメールを送ったとき、最後に一言「話がうま過ぎるような気もするので、間違っていたらご教示ください」とコメントした。そりゃそうでしょう、常識で考えれば、素人考えでコンラッドの上界を1/2に改善できるわけなく、何かの初歩的な勘違いが疑われる。けれど教授からは「私もそれに同意します」という返事が来て、あれよあれよという間にテキストが更新された…。これまでも、他の数学者・物理学者・シリア語学者などに、ちょくちょくちょっとしたミスを報告してはいたのだが(あら探しというよりお礼の意味で)、こんなふうに、実質的な寄与をできたのは初めてかもしれない。Brian Conrad は、双子の Keith Conrad にもこの結果を連絡したらしく Keith Conrad から「兄(弟?)から聞きました」とメールが来た。そんなわけで、チラ裏お遊びの副産物により、スタンフォードとコネチカットの2カ所でテキストが改訂された。ひょうたんから駒というか…純粋に遊びでやっていたことが、思わぬ展開。

調子に乗ってもうちょっと考えたところ、n が正の場合に限ると、改善された評価をさらにもう少し改善できそうな感じ。Keith Conrad の方にその話をしてみたところ「自分としては、正の場合と負の場合の両方に当てはまる不等式の方がいいと思うので、1回目の改善版のままでいく」とのお返事をいただいた。

きょうだいで数学者といえば、Lenstra もそうで、こちらは確か4人きょうだいくらい。それぞれいろいろ活躍しているようだが、一番有名なのは、何と言っても楕円曲線法の Hendrik Lenstra でしょう。その発想のインパクトは、狭義の数学にとどまらず、インターネットの認証の Ed25519 にも結び付いていて、すなわち目に見えないところで日常的に使われている。そして、この楕円曲線法の初期には、日本のスヤマという人が、小さいけれど重要な貢献をしている(多分アマチュアだと思われる)。だから「アマチュアの遊び」だからといって、侮れないんじゃないかな…。

だけどね…

インドでは子どもでも知ってる有名な言葉(ギーター)…

「カルマンニェーヴァーディカーラス、テー。マー、パレーシュ…」(作業の中にこそ、そなたの権利はあれ。結果の中にではなく…)

すなわち「正しいと思われることをしていい。それがあなたの唯一の権利である。その結果(甘い果実か苦い果実か、名誉か不名誉か、成功か失敗か)については、あなたには何の権利もない」。

カルマンニェーヴァーディカーラス、テー。マー・パレーシュ。カダーチャナ…
マー・カルマパラ・ヘートゥル、ブール。マー、テー・サンゴー、ストヴァカルマニ
 そなたはただわざをなせ。成り行きは天意なり、
 そなたのものにあらざる。それでもなさねばならぬぞ。

「自分は今何をするといいのだろう。それを思い、やってみる。あなたにはその権利がある。けれど、その結果がどうなるかについては、あなたには何の権利もない。神の気まぐれは、あなたの管轄事項ではないのだから。余計なことを考えず、成り行きに任せておけばいい。だが達成しようとすることをやめてはいけない。どうせあなたは明日くらいに死ぬ人間。来年の果実を受け取れるかどうか気にしても仕方ない。心を静め、今日できるちょうどいい分量を今日やっておきなさい」

もちろん物事がうまくいけばうれしいだろう。でも結果がどうなるかは自分の問題ではなく、だから「成功して何かを残したい」といったことを動機にしてはいけない。とはいえ、別次元の問題として、スタンフォードの教科書を書き換えた(?)とか大げさに言えば、権威に弱い日本人はびびるかもしれない。そこに付け込んで「アスペだサバンだと自閉症圏の者をばかにするのは、やめてもらおう」と主張するのは許されるだろう。実際、呼吸するようにコードを書くわたしたちがいて、現代のネット社会が回っているのだから。クヌースだってそうなのだから(笑)。ばかとはさみは使いよう。というより、この種族がいなくなると、自称健常者諸君だけでは、もはや世界は回らない…

2020-09-28 中学生でも分かる?コンラッドの不等式(メモ)

ここで「コンラッドの不等式」というのは、Conrad が発見したのかどうかは知らないが、Brian Conrad が書いた数学のテキストで証明されている不等式。

(説明)・・・

「nを0ではない整数、Dを平方数ではない正の整数とする。x^2−Dy^2 = n (☆)の整数解 x, y が存在するか。存在するなら一般解を求め、存在しなければ存在しないことを証明せよ」というタイプの問題を「拡張ペル方程式」という。

ここで n と D は、問題ごとに固定されている。例えば「x2 − 109y2 = 12 に整数解があるか。あるなら求めなさい」というタイプの方程式を考えている。

今 s と t を s^2−Dt^2 = 1 を満たす正の整数として(これは必ず存在する)、u = s+t√D, m = |n| と置く。(☆)に解があるなら、その一つは必ず |x| ≤ √(mu) の範囲にあり、本質的に異なる2種類以上の解があるとしても、必ずそれらは全部この範囲に現れる。これが「コンラッドの不等式」(2017年版)の概要であり、つまり「0以上、√(mu) 以下の整数を順に(☆)のxに入れて、yが整数になるかどうかを調べる」という単純処理によって、拡張ペル方程式は、原理的には有限時間で100%解ける。「解ける」というのは、もちろん「解なし」が答えになる場合も含む。

・・・(説明終わり)

これは素晴らしい。そのような不等式がないと、どれだけ(☆)の解を探しても…例えば「0以上1兆以下のどの整数をx, yに入れても(☆)は成り立たない」としても…「もしかすると1兆より大きい解があるのかもしれない」という可能性を否定できず、問題が有限時間で解決しないのだから。しかしコンラッドの不等式(2017年版)には短所もあった。それは「この範囲を探すと、本質的に同じ2組の解が重複して別々に検出されてしまうことが多い」ということ。「本質的に同じ」かどうかは、別途チェックすればいいことなので、大きな妨げにはならないのだが…。実は、この不等式の上界は改善できる。√(mu) まで探さなくても、およそ半分の範囲、(1+√u)√(m)/2 まで探せば十分(一定条件下では、この上界をさらに改善できる可能性がある)。半分の範囲で十分なのに、その2倍の範囲まで探していたのだから、2017年版で重複検出が起きやすかったのは当然と言えるだろう。この改善は比較的最近…今年(2020年)の7月26日(日本時間では27日朝)に発見された。

「ごく普通の高校生にも十分理解できる」ような普通の言葉で説明可能なので(数学が好きなら中学生でも分かる)、できれば近々一般向けの記事にしたい…とそのときチラ裏にメモしたが、それっきりになっていた。しかし今日、9月28日になって、コンラッドの証明を簡単化して、中学生でも分かるように説明できるかもしれない道筋を思い付いた。オリジナルのコンラッドの証明は、代数的整数論を応用するもので、それなりに難しいのだが、一応、ベクトルの線型独立の概念があれば、あとは対数関数の初歩だけで足りる(二次体や基本単数やノルムの概念を使わずに証明可能)。高校生なら、ベクトルの足し算は普通に知っているのだから、一応理解に支障ないはず。…とはいえ「平面上で、線型独立な2個のベクトルの線型結合で任意の点は表現可能」というのは(知っている人にとっては当たり前のことだが)予備知識を仮定しない一般向けの説明としては、ちょっとむずい…。ベクトルの概念から順に説明するのは可能だが、かなり長くなるし、線型独立を1回使いたいだけのためにそれをやるのは大げさでもある。代わりに、次のようにしたら、分かりやすいかな…と。

任意の2個の実数AとBが与えられたとき、A=q+r, B=q−r を満たす実数 q, r が存在する」…これなら中学生でも理解できそうだよね。普通に連立方程式を解けば q=(A+B)/2, r=(A−B)/2 となり、確かに条件を満たしている。

で(☆)の解 x, y があったとして A = log |x+y√D|, B = log |x−y√D| について同様のことを考えると、
q = (log |x+y√D| + log |x−y√D|)/2 = (log |x^2−Dy^2|)/2 = (log m)/2
は固定され、r についてもある値になるが、もし(☆)が解を持つなら「rの絶対値が1/2以下であるような解が必ずある」。これだけでは全然説明になってないが、とりあえずメモ。(☆)に解が1個でもあれば、それと本質的に同じ解が無限個あって、それらについて log |x+y√D| の値を考えると、数直線上で間隔1できれいに並ぶ点・点・点になる。間隔1で並ぶので、どう配置しても、どれか1個が幅1の区間 (−1/2, 1/2] に入る。これが証明の核心かも。ここで log の底は何でもいいのだが、u を底とするのが、上記の簡単化の「みそ」。

中学生にも分かるようにするためには log を説明する必要があるが、それは比較的簡単にできるだろう。

(追記: 上記のアイデアの中身については、2020年10月30日のメモ参照。)

2020-09-30 x^2−10y^2=89 について

u = 19+6√10。弱い上界(2018年版)は58、この範囲を検索すると (x,y) = (27,8), (33,10) の2種類の解が得られる。2020年7月26日の強い上界は33なので、実際には33まで探せば十分で、この場合、同じ結論が得られる。この2種類の解は、本質的に異なるのだろうか、それとも本質は同じで、単に実二次体の単数倍による「粗製乱造」だろうか。第1解から、任意の整数 k に対して
xk + yk√10 = (27+8√10)(19+6√10)k
は、第1解と本質的に同じ。k = −3, −2, −1, 0, 1, 2, 3 についてこれを計算すると
x−3 + y−3√10 = (27+8√10)(19+6√10)−3 = 46593 − 14734√10
x−2 + y−2√10 = (27+8√10)(19+6√10)−2 = 1227 − 388√10
x−1 + y−1√10 = (27+8√10)(19+6√10)−1 = 33 − 10√10
x0 + y0√10 = (27+8√10)(19+6√10)0 = 27 + 8√10
x1 + y1√10 = (27+8√10)(19+6√10)1 = 993 + 314√10
x2 + y2√10 = (27+8√10)(19+6√10)2 = 37707 + 11924√10
x3 + y3√10 = (27+8√10)(19+6√10)3 = 1431873 + 452798√10
となるので x = 27, 33, 993, 1227, 37707, 46593, 1431873 などは「符号を無視すれば、本質的には同じ」。符号を無視しなければ、33 + 10√10 は (27−8√10)(19+6√10) に等しく、つまり (33,10) は (27,8) と同値ではないが (27,−8) と同値。

「2種類」の解といっても自動的に (27,±8), (33,±10) の「4種類」が得られている。その4種類を同値類で分類すれば2種類しかないので、これは冗長(重複検出)だろう。ここで「2組の解が同値」というのは「それらに対応する2個の代数的整数が、単数倍の違いしかない」という意味。

2020-10-30 コンラッドの不等式(メモ2)

2020年9月28日のメモにあるアイデアは、具体的には以下の通り。次のように進めれば「ベクトル」や「線型独立」の概念を使わずに、この不等式を導ける。

s, t をペル方程式 s^2 − Dt^2 = 1 の正の整数解として、u = s + t√D と置く。u > 1 である。

【1】 log の底を u とする。ゼロでない任意の2個の実数 z, z′ について
log |zz′| = log (|z||z′|) = log |z| + log |z′|。
今 g(z) = log |z|
と書くと
g(zz′) = g(z) + g(z′)。
ところで log の定義から、任意の整数 N について g(u^N) = N。

【2】 任意の2個の実数 a, b が与えられたとき、q = (a+b)/2, r = (a−b)/2 と置くと、a = q+r, b = q−r が成り立つ。

【3】 x, y を拡張ペル方程式 x^2 − Dy^2 = n の解だと仮定する。
a = log |x + y√D| と b = log |x − y√D| について、【2】によって、実数 q, r が存在して a = q+r, b = q−r と書ける。ここで:
q = (log |x + y√D| + log |x − y√D|)/2
= (log |x^2 − Dy^2|)/2 = (log |n|)/2。

【4】 上記の実数 q は、与えられた拡張ペル方程式の右辺 n に対応して固定されている。ところで、
a = g(x + y√D) = log |x + y√D| = q+r
という対数は、拡張ペル方程式のある1組の解 x, y と対応しているが、この対数に任意の整数 N を足した数もまた、同じ拡張ペル方程式の別の解と対応している。なぜなら
x + y√D
が解が表すなら、
(x + y√D)(u^N)
はそれと本質的に同じ解を表していて、【1】から次が成り立つ:
g((x + y√D)(u^N)) = g(x + y√D) + g(u^N) = g(x + y√D) + N

【5】 すなわち解が実際にあったとして、上記 q+r をその解に対応する対数だとすると、それに …, −3, −2, −1, 0, 1, 2, 3, … を足したものは、どれも解に対応する対数である(それぞれ別の解に対応している)。ただし q は固定されているので、この観察は「r を1刻みで勝手に変動させても、その結果は依然として、拡張ペル方程式の解のどれかと対応している」という意味になる。すると、自分勝手に解を1個選んでいい…という局面では、初めから r は (−1/2, 1/2] の範囲に入っていると仮定しても差し支えない。実際にはその範囲外だとしても、任意に整数を加減できるのだから、その結果が範囲内になるように加減してから、その結果をあらためて r と置けばいいわけである。すなわち、そもそも解があるとすれば、r の絶対値が1/2以下であるような a = q+r と b = q−r を選ぶことが常に可能であり、それに対応する解 x, y が存在する。このとき
a = log |x + y√D| = q + r = (log |n|)/2 + r ≤ (log |n|)/2 + 1/2 【ア】
b = log |x − y√D| = q − r = (log |n|)/2 − r ≤ (log |n|)/2 + 1/2 【イ】
とするのが、2017年のコンラッドの不等式の出発点。【ア】の不等号は、r が1/2以下なのだから、直観的には「そのまんま」。【イ】の不等号は、せっかく r を引き算しているのに「プラスの」1/2で上から押さえるのは「もったいない」というか「余裕を見過ぎている」気もするが、実際問題 r は負かもしれず、分かっているのは(大ざっぱに言えば)絶対値が1/2以下というだけ(詳しく言えば「以下」を「未満」にできるが、実用上、どちらでも同じ)。この考え方では、結局 +r でも −r でも、不等号の上限は同じ値になる。log の底が u だったことを思い出すと:
log |x + y√D| ≤ (log |n|)/2 + 1/2 * log u = (log |n| + log u)/2
|x + y√D| ≤ (|n|u)^(1/2) = √(|n|u)
同様に:
|x − y√D| ≤ √(|n|u)
辺々足し合わせて2で割ると:
|x| ≤ √(|n|u)

これが2017年版の結果だった。

【6】 2020年7月の改良版コンラッドの不等式は、次のようにして導かれる。もし r が負でなければ【イ】の評価は確かにもったいない。その条件なら
log |x − y√D| = (log |n|)/2 − r ≤ (log |n|)/2 【イイ】
とできる。実際には r が負でないという保証はないけれど、r が負なら負で、そのときはその性質を活用して【ア】の方を
log |x + y√D| = (log |n|)/2 + r ≤ (log |n|)/2 【アア】
とできる。いずれにしても、組み合わせる2個の不等式は【ア】&【イイ】か、または【アア】&【イ】のどちらか。つまり、どっちにしても【ア】【イ】のどちらか一方(どちらかは確定できないが、とにかくどちらか一方)から +1/2 の項を消せる。この一見微妙な「節約」によって、最終的には2017年版の約半分まで上限を減らせる。検索速度的にはざっと2倍の高速化なので、この工夫は有意義である。

【7】 しかし数値的に検証すると、こうして得られる改良版も、もともとの2017年版より良いのは確かだが、まだ最善の評価とは言い難い。成功するかどうかはともかく、さらなる研究の余地がある。

拡張ペル方程式を解くことに関しては、このようなブルートフォースより良いアルゴリズムが存在する。だからこそ「ブルートフォースの上界なんてどうでもいい。ブルートフォースそのものが必要ない」ということになって、この上界が真剣に検討されていないのだろう(もし仮にこれが数学的に重要と見なされ、専門家が総力を挙げれば、それほど難しい問題ではないはず)。けれど「拡張ペル方程式の解の分布を幾何学的に解釈したときに、解があるなら、必ずこのタイルの中に1個はある」とか「本質的に異なる全部の解を含む最小のタイルはこれ」みたいな、幾何学的な数論の文脈においては、こういう一見「古くさい」問題も、新しい意味を持つかもしれない。

2020-12-08 コンラッドの不等式(メモ12) 対数を使わない証明

もともと数学専攻・学部2~3年以上を対象としたような内容。普通の中学生に説明するには、二次体の整数論は平易に言い換えるとして「ベクトル・線型独立・対数関数」をどうするか。「ベクトル・線型独立」を使わないようにするアイデアはあったが、対数関数は導入するしかないと思っていた。しかし、試行錯誤の末、どうやら対数関数を使わない証明の道筋が見つかった。λ = log(x + y√D) と μ = log(x − y√D) の算術平均を γ として半径 δ の円を描く…という部分を「α = x + y√D と β = x − y√D の幾何平均を γ として…」とやればいい。分かってみれば単純明快。

対数を使えば、淡々とできるのだが、中学生向けの記事にしたい!というこだわりから、かなりの縛りプレイになった。一般に、代数的整数論を古典数論の言葉で述べると、見通しが悪くなる。ところが、この場合に関しては、あえてそうすることで、むしろイメージが明確になる面もある。対数関数を導入して、それを使う道もあるが、導入したての対数関数を使うのは、読者にとって実感が湧きにくい。対数関数を使わない方が、一般向けの説明としてはいい。

なぜ中学生向けにこだわったのか…よく分からないが「この証明は中学数学の範囲でスッキリ再構成できる」という漠然とした勘、妙な使命感(?)があった。全体から見れば、拡張ペルの話題のマイナーな命題にすぎないけれど、理論的に重要な意味を持っているように思えるし、発見者が何をどう考えたのか忘れないうちに整理しておくことは、自分自身にとっての覚え書きでもあり、第三者にとっても何かの参考になるかもしれない。アマチュアだって「ちょっとした発見」ができる! プロにとっては、たわいないことでも、そこにはワクワクがある! 教科書をなぞって暗記するのが数学ではなく、実験や遊びがあってもいい。実際、「2020年7月の改良版不等式自体、まだ最善の上界ではない」というのは非常に確からしい。

2020-11-07 コーヒーブレイク 「フェルマーの最終定理」のロマン~失敗は発展のもと

「アマチュアだから」「大して知識がないから」などと余計な遠慮をせず、興味があることは何でも試したらいい。人は何も持たずに裸で生まれ、やがて何も持たずに去っていく。人生なんてゼロから始まりゼロで終わるもの。だったら「最終成果」なんて気にしても仕方なく、生きてる間に「本当の意味で楽しむ」こと…「自分には、それ自体が面白い」…それが必要、それで十分。

フェルマーの最終定理については、多くの方が耳にしたことがあるでしょう。その内容は…

x3 + y3 = z3 を満たす正の整数 x, y, z は存在しない。「3乗」を「4乗」「5乗」「6乗」…に変えても、結論は同じ。

…というもの。一見シンプルな主張。

アマチュアを含めて多くの数学者がこの問題に取り組み(フェルマー自身、職業的な数学者ではなく「アマチュア」だったらしい)、多くの人が何度も何度も失敗しましたが、その過程でいろいろな新しい知見が得られ、数論そのものが大きく発展しました。

最終定理自体は、比較的最近になって、ようやく証明されたようですが、数論の世界には「問題の意味はシンプルなのに、まだよく分かっていないこと」が今でもいっぱい。「プロ棋士ではないから、囲碁・将棋を楽しんではいけない」ということはなく、登山だって、料理だって、ピアノだって…それを好きな人が、趣味として楽しむのは個人の自由。むしろ「アマチュアの立場だからこそ、職業上の責務やプレッシャーと関係なく純粋に楽しめる」という面も。数論も同じこと。

ペル方程式の一般化は、最終定理同様、古くて新しい問題。その最初歩ともいえる「負のペル方程式」…

x2dy2 = −1 に整数解はあるか?

…は、具体的な d が与えられたとき、アルゴリズム的には解決できるのですが、この場合には解がある、という d についての必要十分条件は、今でも完全には分かっていないようです。それを少し拡張した…

x2dy2 = z に整数解はあるか?

…という問題も、具体的な個々の問題を解決するアルゴリズムは昔から知られているものの、全体を見通す理論は未完成。さて「谷山予想」というのは、フェルマーの最終定理の証明とも関係しているものですが、Brian Conrad によって証明されました。そのコンラッドは、2017年、上記の「拡張ペル方程式」に解がある場合、必ず次の範囲に一つは解がある…ということを書きました(これは深い問題ではなく、初等的なものです。ここでは u の意味の説明は省きますが、それは d に応じて定まる数で、一般には大きい値)。

0 ≤ x ≤ √|z| × (√u + √u)/2 = √(|z|u)

2020年7月、非常に簡単な議論によって、上記の
u + √u
の部分を
u + 1
に減らせること(つまり、範囲をざっと半分に絞れること)を筆者は指摘しました。これが「改良版」コンラッドの不等式。2020年10月、これをさらに
u + 1/√u
に減らせる…と主張しました。これが「再改良版」コンラッドの不等式であり、10月の時点では証明に初歩的なミスがあったものの、主張そのものは正しいと筆者は考えています。現在2020年11月の時点では「今度は正しいはず」という証明を得ています。それが勘違いでまた間違っている可能性も、もちろんあるのですが…

核心は「不等式の範囲をもうちょっと絞る」という数値的な「節約」ではなく(数値的にはどちらにしても巨大)、「この範囲を捜索することが必要かつ十分、というシャープな線を引く」という理論的なもの。実用上、ペル方程式の解法では、もっと良いアルゴリズムが知られていますが、この種の不等式は理論的に興味深いものであり、だからこそコンラッドもこれを記述したわけです。実用上も、考えている数が小さいときは、全数検索は手軽で便利。

のみならず、もともとのコンラッドの証明は、学部上級~大学院初級を対象とし、代数的整数論と線型代数を使うものですが、メモ2にあるように高校数学の範囲(中学数学+対数関数だけ)でも証明できる(素人だからこそ意味を持つ工夫かもね)。それは改良版にも有効。再改良版の証明には、今のところ、それプラス微分が必要ですが…。上記は x の範囲に関するものですが、y の範囲についても同様の不等式が成り立ちます。そして y については「再改良版」の
u + 1/√u
を一定条件下で
u − 1/√u
に減らせる…というのが「再々改良版」。これについては、まだよく見通せていませんが、もしかすると、これも理論面で面白い意味を持つのかもしれません。

2020-11-09 数論ごっこ

8で割って5余るような任意の自然数 d について、
【ケ】 X^2 − d*Y^2 = +4 または −4
は「奇数の解」を持つこともあれば、持たないこともある。奇数の自然数解を持つ場合、そのうち最小のものを「基本解」と呼ぶことにしよう。例えば d=45 について
7^2 − 45*1^2 = +4
であり、それより小さい自然数解はないので (X,Y) = (7,1) は基本解。一方 d=37 について【ケ】を満たす整数は
12^2 − 37*2^2 = −4
のように偶数に限られるので、上記の意味での「基本解」は存在しない。1857年のケイリーのノットに、1000以下の d について、基本解の一覧表が載っている。

8で割って5余る d について、具体的な数値例を考えると、どうやら次のことが成り立つようだ。
「X^2 − d*Y^2 = ±4 が奇数解を持つことは、Q(√d) の基本単数 ε = x + yω の y が奇数であることと同値。解があるなら、この y が基本解のY成分。その際、±4 の符号は、ε のノルムの符号に一致する。」

これが事実とすると、基本解のX成分は、X^2 = d*Y^2 ± 4 から自動的に定まる。

基本単数とは何か、どうやってそれが決定されるのか…といった伏線は、そのうち回収したいが、とりあえず http://www.numbertheory.org/php/unit.html で計算してもらえる(Gフリーな良いページ)。PARI では例えば
quadunit(37)
とタイプすると 5 + 2*w が表示される。少なくとも d ≤ 109 の全例について、上記の観察は正しい。以下、基本単数については上記のウェブページから直接コピペ、ケイリーのノットと組み合わせて関係性を色で表す:

the fundamental unit of Q(√5) is ε=x+yω : norm=-1
x=0, y=1 : 1^2-5*1^2=-4
ω=(1+√5)/2

the fundamental unit of Q(√13) is ε=x+yω : norm=-1
x=1, y=1 : 3^2-13*1^2=-4
ω=(1+√13)/2

the fundamental unit of Q(√21) is ε=x+yω : norm=+1
x=2, y=1 : 5^2-21*1^2=+4
ω=(1+√21)/2

the fundamental unit of Q(√29) is ε=x+yω : norm=-1
x=2, y=1 : 5^2-29*1^2=-4
ω=(1+√29)/2

the fundamental unit of Q(√37) is ε=x+yω : norm=-1
x=5, y=2 : 偶数だから X^2-37*Y^2=±4 は基本解なし!
ω=(1+√37)/2

d=45 is divisible by 3^2
あらまあ…平方因子があるとエラーになってしまうので、これはPARIで…
 quadunit(45) is ε=x+yω : norm=+1
 x=3, y=1 : 7^2-45*1^2=+4
 ω=(1+√45)/2

the fundamental unit of Q(√53) is ε=x+yω : norm=-1
x=3, y=1 : 7^2-53*1^2=-4
ω=(1+√53)/2

the fundamental unit of Q(√61) is ε=x+yω : norm=-1
x=17, y=5 : 39^2-61*5^2=-4
ω=(1+√61)/2

the fundamental unit of Q(√69) is ε=x+yω : norm=+1
x=11, y=3 : 25^2-69*3^2=+4
ω=(1+√69)/2

the fundamental unit of Q(√77) is ε=x+yω : norm=+1
x=4, y=1 : 9^2-77*1^2=+4
ω=(1+√77)/2

the fundamental unit of Q(√85) is ε=x+yω : norm=-1
x=4, y=1 : 9^2-85*1^2=-4
ω=(1+√85)/2

the fundamental unit of Q(√93) is ε=x+yω : norm=+1
x=13, y=3 : 29^2-93*3^2=+4
ω=(1+√93)/2

the fundamental unit of Q(√101) is ε=x+yω : norm=-1
x=9, y=2 : 偶数だから X^2-101*Y^2=±4 は基本解なし!
ω=(1+√101)/2

the fundamental unit of Q(√109) is ε=x+yω : norm=-1
x=118, y=25 : 261^2-109*25^2=-4
ω=(1+√109)/2

右辺が 4 の拡張ペル方程式と、二次体の整数論の関係は基本的なことで、別に神秘的なことではないはずだが、こうして結果だけ眺めると、やっぱり数の不思議さ・奥深さのようなものを感じる。

注: 上記の数値例だけ見ると、偶数の y は常に y=2 のようにも思えるが、それは正しくない。例えば d=269 の場合:

the fundamental unit of Q(√269) is x+yω
x=77, y=10
ω=(1+√269)/2
norm=-1

2020-11-18 x2 − 61y2 = 900 のんびり数論

【1】 x2 − 61y2 = 900 【ア】
には、本質的に異なる整数解が14種類もある。

まず 900 = 302 は平方数。y = 0 としてしまえば、与式は x2 = 900 となり (x, y) = (30, 0) は【ア】を満たす。これは自明解、つまらない解。

(x, y) = (31, 1) も【ア】を満たす。実際、312 = 961 なので
312 − 61⋅12 = 961 − 61 = 900

同様に (x, y) = (91, 11) も【ア】の解。

【2】 次に小さい自然数解は、(x, y) = (213, 27) で、確かに
2132 − 61⋅272 = 45369 − 61⋅729 = 900 (★)
となるが、この計算は3の倍数だらけ。「213」も、各桁の数字を足すと 2+1+3 = 6 なので3の倍数。213 = 3⋅71。「暗視カメラ」のような「因数ビジョン」で、(★)の内容を分析してみましょう。
(3⋅71)2 − 61⋅(3⋅9)2 = (32⋅712) − 61⋅(32⋅92) = 32⋅100
どの項も 32 で割り切れるのは一目瞭然。この現象の根源は、(x, y) = (213, 27) が公約数3を持つこと。最初から全体を 32 で割った
x2 − 61y2 = 100 【イ】
を考え、その解 (x, y) を3倍すれば【ア】の解になる。(★)の計算は間違いではないが“約分されていない”というか、ある意味、無駄に大きな数を考えている。具体的に、(★)は
712 − 61⋅92 = 100
の各項を9倍したものに他ならない。

今考えたのは (x, y) の最大公約数が3のケースだった。最大公約数が2のケースや、5のケースも、解があるとすれば同様のことになるだろう。ここで 2, 3, 5 のような数を考えるのは【ア】の右辺が
900 = 22⋅32⋅52
だから。逆に言うと、例えば (x, y) がどちらも7の倍数だとすると、【ア】の左辺は(7の倍数ひく7の倍数なので)7の倍数になり、【ア】の右辺と等しくなる可能性はない。すなわち公約数が7のケースは、あり得ない。

【3】 それでは【ア】を【イ】のように“約分”というか“通分”できるのは(=もっと簡単な式にすぐ変換できるのは)、解の最大公約数が 2, 3, 5 の3パターンだけだろうか? 次のパターンはどうか。
12502 − 61⋅1602 = 900 【ウ】
この解 (x, y) = (1250, 160) が10で割り切れること、つまり【ウ】の各項が 102 = 100 で“通分”できることは明らか。【ウ】の代わりに
1252 − 61⋅162 = 9 【エ】
を見つけて、解を10倍する方が(理屈の上では)話が早い。【ア】を“通分”できるケースは、解の公約数が 2, 3, 5 に限らず、解の公約数の平方が右辺900の約数になっていれば十分であり、また、それが必要でもある(前記7の例から分かるように、それ以外の因子が含まれていると、右辺が900になる可能性はないので)。【ウ】は、解の公約数が 2⋅5 = 10 になるケース。同様に、解の公約数が 2⋅3 = 63⋅5 = 15 になるケースも、存在するとすれば、同様に考えることができる。さらに、一番最初に考えた自明解 (30, 0) は、解の公約数が 2⋅3⋅5 = 30 のケースに他ならない。【ア】の右辺900の素因数分解は 22⋅32⋅52 なので、“通分”できるパターンは、以上で全て。【ア】には、このような解が10種類も存在する。通分のパターンが7もあるので(これは 2⋅3⋅5 が持つ1以外の約数の個数)、解の種類がそのくらいあっても、おかしくはないだろう。

通分した「小さい」方程式について、試行錯誤で解を見つけることはやればできるが、そうして見つかる解が「本質的に同じ」かどうかという判断は、理論武装がないと難しい(そもそも「本質的に同じ」の意味をまだちゃんと定義していない…)。

【4】 細かいことを気にせず、雰囲気的に話を進める。結局【ア】の解のうち“通分”できないケース…つまり (x, y) が1以外の公約数を持たないケース…が理論上、基本的。【1】にある (x, y) = (31, 1)(x, y) = (91, 11) が、その例。x と y が互いに素なケース、と言い換えることもできる。原始解とか、既約解とか、適当に名前を付けておこう。【ア】には、
(x, y) = (17659, 2261)
(x, y) = (134719, 17249)
という解もある。【ア】について、これら計4種類の原始解が「本質的に異なる」こと、そして「本質的に異なる」原始解はこの4種類だけであること…。このことは、いろいろな角度から考えることができる。まず【ア】では x, y の符号はプラスでもマイナスでもどちらでもいい(2乗してしまうので)。ここでは符号を無視、正の解だけを考えることにする。その上で、まず一番小さい
(x, y) = (31, 1)
を考えると、x = 31y = 1 の31倍だが、この31という数は、次のように mod 900 における61の平方根になっている(61は【ア】における y2 の係数)。
312 = 961 ≡ 61 (mod 900)
これと同様のことが他の原始解についても成立する。
91 ≡ 581⋅11, 5812 ≡ 61 (mod 900) ここで 581 ≡ −319 (mod 900)
17659 ≡ 419⋅2261, 4192 ≡ 61 (mod 900)
134719 ≡ 131⋅17249, 1312 ≡ 61 (mod 900)

すなわち、【ア】の原始解は mod 900 における61の平方根と結び付いている(【ア】の式の形からも、そうなりそうな感じがする)。mod 900 における61の平方根は、±31, ±131, ±319, ±419 の4種類だけなので、本質的に異なる解は最大でも4種類だと予想される。

【5】 この観察は、実は、昔から教科書に記されているような古典的なことなのだが、現代でもよく分かっていない部分が残っている。まず【ア】のような形の不定方程式が解を持つ場合、今見たように平方剰余が絡むことが必要で、そこが平方非剰余だったら解があり得ないことは容易に示される。だが、その条件では十分ではない。「非剰余なら解なし」「解があれば平方剰余」とまでは簡単に断言できるのに、逆に「平方剰余なら解がある」とは限らず、何かもっと深い問題が絡んでいる…。

それとは別の話として「この範囲を探せば、本質的に異なる全ての解が見つかる」という範囲指定ができるのだが、その範囲は現状、必要十分ちょうどぴったりではなく「十分過ぎる」。結果として、本質的に同じ別の解が重複検出されるケースがある。筆者はこの範囲指定を「必要十分ぴったりにできる」と考えていて、結果についてかなりの確信を持っているのだが、しょせんは素人考え、客観的には「よく分からない」。しかし対数を使ったある種の表現において、δ とか r とか呼ばれる数が (−1/2, 1/2] の範囲に収まること。そこに問題が帰着される。さらに別の話として、この種の方程式の実用的な解法は、平方根の連分数展開(こちらは古典的話題)。その観点からの謎は、実際に計算しないで、循環の周期を直接的に求められるのか…。さらにさらに別の話として【ア】のような式は、結局2次曲線が整数格子点と交わる場所を探す問題である。

これらいろいろな見方は、必ず深いレベルでは絡み合っているはずで、同じ本質から生じるいろいろな表面的現象を観察している…と予想される。その全体像については、数学のプロにもまだ完全には分かってないらしい。専門家にも分からないことを素人が考えても仕方ないかもしれないが、そこはそれ、具体例を考え、のんびり遊んでみるのも悪くないでしょう。

2020-11-19 x2 − dy2 = n の解の、とある条件 のんびり数論・2

【1】 前回【4】では、具体例について、何となく次のようになってることを観察した。

(観察) x2 − dy2 = n 【サ】
が自然数解 (x, y) = (a, b) を持ち、a, b が互いに素だとすると
a ≡ kb (mod m) 【シ】
を満たす k が 0, 1, 2, …, m−1 の中に一つだけ存在する。ここで m = |n|。このとき
k2 ≡ d (mod m) 【ス】
が成り立つ。

…これをきちんと証明したい。

【2】 まず a, b が互いに素という仮定について。もしそうでないとすると(つまり a, b に2以上の公約数があるとすると)、その公約数で【サ】を「通分」して、もっとシンプルな方程式にできるのだった。もっと簡単にできることをわざわざ複雑に考えることもあるまい。とりあえず、簡単化できない「互いに素」な場合だけを考えよう、というのである。(a, b) は【サ】の解だから
a2 − db2 = n 【セ】
a2 = n + db2 【ソ】
となるが、このとき b, n も互いに素。実際、そうでないとすると、b, n に2以上の公約数 c があって次のように書けることになる…。
b = b′c, n = n′c
…しかし、だとすると【ソ】の右辺は c の倍数になり、それと等しい【ソ】の左辺も c の倍数でなければならない。すると a, b がどちらも c で割り切れる…という事態になり「a, b は互いに素」という前提に反する。従ってそのようなことは起こり得ず、b, n は互いに素であり、b, m も互いに素(m は n の符号をなくしたものなので、倍数・約数の関係に関する限り n と全く同じこと)。

【3】 b, m が互いに素であるというこの制約によって、【シ】が成り立つ。というのも、k が m 種類の値
{0, 1, 2, …, m−1}
を取るとき、kb の値の変化を記録すると、全体として、やはり m 種類の値
{0, 1, 2, …, m−1}
と合同になる。そのことを確かめるために、上記の範囲の k の中に k1 と k2 があって
k1b ≡ k2b (mod m) 【謎】
になってしまった!と仮定してみよう。つまり、m 種類の入力「k」から m 種類の出力「kb」が得られず、ある入力 k1 と別の入力 k2 が同じ出力にマップされてしまった!と仮定してみる。その場合【謎】から
k1b − k2b ≡ 0 (mod m)
(k1 − k2)b ≡ 0 (mod m)
となるが、これは (k1 − k2)b が m の倍数という意味。ところが b, m は互いに素、すなわち b には m の素因数が全く含まれてないのだから、
(k1 − k2)b
が m の倍数だとしたら (k1 − k2) の部分が m の倍数になる必要がある。でも k が取り得る値は上記の通りなので、どのように2個の値を選んでも (k1 − k2) の絶対値が m 以上になるわけない。つまり (k1 − k2) が m の倍数になるとしたら、唯一の可能性は
(k1 − k2) = 0, k1 = k2

0 も確かに m の倍数には違いないが、これは「別々の入力のつもりだった k1 と k2 が、強制的に等しい値になってしまう」という意味である。つまり「別々の入力が同じ出力にマップされてしまう」という【謎】の事態は起こり得ず、m を法として出力が同じ ⇔ 入力が同じ、入力が違う ⇔ 出力も違う。結局、不合同の m 種類の入力は、不合同の m 種類の出力と1対1対応する。このことから【シ】が成立。

【4】 こうして確かめられた【シ】を今度は【セ】の左辺に代入すると、
a2 − db2 ≡ (kb)2 − db2 = b2(k2 − d) (mod m) 【左】
となるが、【セ】の右辺 n は m または −m に等しいのだから
n ≡ 0 (mod m) 【右】
となる。【セ】の左辺・右辺は等しく、等しいものはもちろん合同なので
b2(k2 − d) ≡ 0 (mod m)

ここで【3】と同様に考えると、これは (k2 − d) が m の倍数であること、言い換えれば
k2 − d ≡ 0 (mod m)
を意味する。このことから【ス】が成立。それが、証明したいことだった。 □

【5】 証明を考えると、あまり「のんびり数論」ではないが…まあ、のんびり検討してみるのも良いかと…。数論のスローライフ。

<例> x2 − 13y2 = −17 は、解 (x, y) = (10, 3) を持つ(d = 13, n = −17)。

このとき 10 ≡ 9⋅3 (mod 17)。つまり【シ】において
a = 10, b = 3, k = 9, m = 17
であり、確かに【ス】が成り立つ:
92 ≡ 13 (mod 17)

2020-11-21 x2 − 43y2 = 24 のんびり数論・3

a2 − db2 = n 【タ】
が成り立つなら、当然 a2 − db2 は n の倍数(詳しく言えば、n の1倍)。つまり:
a2 − db2 ≡ 0 (mod n)
db2 ≡ a2 (mod n) 【チ】
(ここでは n の符号を無視する。例えば n = −17 の場合、mod −17 は mod 17 と同じ意味だと約束する。要するに m = |n| について mod m を考える。)

b の逆数 1/b が存在するという保証があれば、【チ】を次のように変形できる。
d ≡ a2/b2 ≡ (a/b)2 (mod n) 【ツ】

前回・前々回の内容は、大ざっぱに言うと【タ】から【ツ】への変形。この変形を正当化するには 1/b の存在が不可欠であり、そのため「b, n が互いに素であること」に、こだわった。この「互いに素」は、重箱の隅をようじでつつくような、こうるさい限定にも思えるが、そこが肝心。それを逆手に取って 1/b の計算をわざと失敗させることは、楕円曲線法の要(かなめ)でもある。

さて【ツ】の意味は「mod n において、a/b という比(前回それを k と呼んだ)を平方すると d になる」。

【タ】ならば【チ】なので、【チ】が不成立なら【タ】は不成立。特に「互いに素である解」については、【ツ】から、d が平方剰余でなければならない。d が平方非剰余なら、【タ】に「互いに素である解」はない。その場合でも「互いに素でない解」が存在しているかもしれない。

<例> x2 − 43y2 = 24 は、解を持つだろうか。「互いに素である解」が存在するためには、43 ≡ 19 (mod 24) が平方剰余であること(つまり k2 ≡ 19 (mod 24) を満たす k が存在すること)が必要。この必要条件が満たされないので「互いに素である解」はない。けれど「互いに素」という限定を外すと、
(x, y) = (14, 2)
のような解が見つかる。実際、
72 − 43⋅12 = 6
…の全部の項を4倍すると:
142 − 43⋅22 = 24

a = 14, b = 2, d = 43 は【タ】【チ】を満たすが、1/b ≡ 1/2 (mod 24) が存在しないので【ツ】の方向には変形できない。さてはて、どうしましょう…

❋

2020-11-25 何で 14/2 が7じゃねーんだよ!! なんとかしろよ、お前ら ☡

前回、末尾の例で「a = 14, b = 2, d = 43 は【タ】【チ】を満たすが、1/b ≡ 1/2 (mod 24) が存在しないので【ツ】の方向には変形できない」みたいなことを書いたが、「逆算すれば 7⋅2 ≡ 14 (mod 24) なんだから数学的に見ても a/b は7だろ。あ゙ぁ?」という苦情が来るかもしれない。もっともな疑問であり、すっきりさせる価値がある話題だろう。

2020-04-11 「マイナスかけるマイナスはプラス」にならない例

どちらの例も内容は当たり前だが、「マイナスかけるマイナスはプラスに決まってる」と簡単には言い切れないことが分かる。

「マイナスかけるマイナスはプラスということは、分配法則から言えること」という「知識」を持っている人もいるかもしれない。それも突っ込みどころがあって、例えば、整数において「マイナスかけるマイナスはプラス」「プラスかけるプラスはマイナス」としても分配法則は成り立つ。

「マイナスかけるマイナスはプラス」を少しきちんと言い直すと「任意の2元 a, b の積は、a の加法逆元と b の加法逆元の積に等しい」。この明確化によって、上記の紛れは解消する。とはいえ、明確化された命題が成り立つかどうかは、依然として「考えている代数系の性質」であり、「積という演算そのものの性質」ではない。

「マイナスかけるマイナスはプラス」ということについては、次のような「一見エレガントな証明」が成り立つ。下記二つの主張に基づく。

第一の主張 m というものは、m と足し合わせるとゼロになるような数のことである…と定義しよう。例えば −3 というものは、3 と足し合わせるとゼロになるような数である。これは定義なのでケチのつけようがない。

第二の主張 m(−1) × m に等しい。例えば −3(−1) × 3 に等しい。これも明らかだろう。

ここで m をマイナスの数、例えば −4 だとしよう。第一の主張から、−(−4) は「−4 と足し合わせるとゼロになるような数」なので、+4 に他ならない。すなわち
−(−4) = +4
である。一方、第二の主張から
−(−4) = (−1) × (−4)
であり、これらを組み合わせると
(−1) × (−4) = +4
となる。マイナスかけるマイナスがプラスになることが「証明」された…。

この「証明」の問題点は、第二の主張が成立する根拠が示されていないこと。普通の数(例えば実数の集合)の計算では、事実として、第二の主張は成り立つ。しかし、第二の主張が成り立つ理由は、負数の乗法が「このように」定義されていること。定義の結果である第二の主張を使って定義を正当化するのは、循環論法である。

子どもに説明するような場合には、時間軸のプラス(未来)とマイナス(過去)について、「速度がマイナスの(バックしている)車の位置」をイメージするのが手っ取り早い。位置が速度かける経過時間であること、バックしている車の過去の位置がプラスであることは、直観的に明らかだろう。

2020-06-27 現金でちょうど50円払う方法は37通り

1円、5円、10円、50円という通貨があるとする。ちょうど50円を払う方法は何通りあるか。1円を50個、1円を45個・5円を1個…といった全ての可能性を考える。

50円を1個という単純な方法(1通り)の他に、下記のように
11 + 9 + 7 + 5 + 3 + 1 = (11+1) + (9+3) + (7+5) = 12*3 = 36
通りの方法がある。一見たわいもない算数だが、通貨の種類と支払う額を一般化した場合(例: 63円、84円、94円、100円の切手を組み合わせてちょうど1万円払う方法は何通りあるか)、解けることは解けるものの、計算量的に困難。計算法(アルゴリズムの実装)もいろいろで、興味深い。この問題の有名なバージョンは「1セント、5セント、10セント、25セント、50セント、1ドルを使って1ドル払う方法」。50円バージョンは37通り、1ドルバージョンは293通りと、どちらも答えが素数になるところが、誘惑的。

  1 : [ 10*0 + 5*0 + 50 = 50 ] 10円0枚なら残り50円: 5円は0~10枚=11通り
  2 : [ 10*0 + 5*1 + 45 = 50 ] (不足分は1円で払う。
  3 : [ 10*0 + 5*2 + 40 = 50 ] 1円の枚数は自動的に決まる)
  4 : [ 10*0 + 5*3 + 35 = 50 ]
  5 : [ 10*0 + 5*4 + 30 = 50 ]
  6 : [ 10*0 + 5*5 + 25 = 50 ]
  7 : [ 10*0 + 5*6 + 20 = 50 ]
  8 : [ 10*0 + 5*7 + 15 = 50 ]
  9 : [ 10*0 + 5*8 + 10 = 50 ]
 10 : [ 10*0 + 5*9 + 5 = 50 ]
 11 : [ 10*0 + 5*10 + 0 = 50 ]
 12 : [ 10*1 + 5*0 + 40 = 50 ] 10円1枚なら残り40円: 5円は0~8枚=9通り
 13 : [ 10*1 + 5*1 + 35 = 50 ]
 14 : [ 10*1 + 5*2 + 30 = 50 ]
 15 : [ 10*1 + 5*3 + 25 = 50 ]
 16 : [ 10*1 + 5*4 + 20 = 50 ]
 17 : [ 10*1 + 5*5 + 15 = 50 ]
 18 : [ 10*1 + 5*6 + 10 = 50 ]
 19 : [ 10*1 + 5*7 + 5 = 50 ]
 20 : [ 10*1 + 5*8 + 0 = 50 ]
 21 : [ 10*2 + 5*0 + 30 = 50 ] 10円2枚なら残り30円: 5円は0~6枚=7通り
 22 : [ 10*2 + 5*1 + 25 = 50 ]
 23 : [ 10*2 + 5*2 + 20 = 50 ]
 24 : [ 10*2 + 5*3 + 15 = 50 ]
 25 : [ 10*2 + 5*4 + 10 = 50 ]
 26 : [ 10*2 + 5*5 + 5 = 50 ]
 27 : [ 10*2 + 5*6 + 0 = 50 ]
 28 : [ 10*3 + 5*0 + 20 = 50 ] 10円3枚なら残り20円: 5円は0~4枚=5通り
 29 : [ 10*3 + 5*1 + 15 = 50 ]
 30 : [ 10*3 + 5*2 + 10 = 50 ]
 31 : [ 10*3 + 5*3 + 5 = 50 ]
 32 : [ 10*3 + 5*4 + 0 = 50 ]
 33 : [ 10*4 + 5*0 + 10 = 50 ] 10円4枚なら残り10円: 5円は0~2枚=3通り
 34 : [ 10*4 + 5*1 + 5 = 50 ]
 35 : [ 10*4 + 5*2 + 0 = 50 ]
 36 : [ 10*5 + 5*0 + 0 = 50 ] 10円5枚なら残り0円: 5円は0枚=1通り

このタイプの問題は「危険」。入り口はスイートでエレガントで簡単そうだが、スッキリ解決させようとすると予想外に深く、最初に考えていたことは氷山の一角で、一般の問題が面白くてハマってしまう…
Lectures on Integer Partitions
http://www.math.upenn.edu/%7Ewilf/PIMS/PIMSLectures.pdf

2020-07-15 きれいなパターン

32 + 42 = 52 = 25

102 + 112 + 122 = 132 + 142 = 365

212 + 222 + 232 + 242 = 252 + 262 + 272 = 2030

おいおい、どうなってるんだ、これは???

362 + 372 + 382 + 392 + 402 = 412 + 422 + 432 + 442 = 7230

むむむ…。

552 + 562 + 572 + 582 + 592 + 602 = 612 + 622 + 632 + 642 + 652 = 19855

見えた! 一番左の数、3は1~2の和、10は1~4の和、21は1~6の和、36は1~8の和、55は1~10の和。このパターンで行くと、次は1~12の和、すなわち78がスタートポイントになるはず…

782 + 792 + 802 + 812 + 822 + 832 + 842 = 852 + 862 + 872 + 882 + 892 + 902 = 45955

ごちゃごちゃ計算すれば、三角数がなんちゃら、2乗の和の公式がなんちゃらかんちゃらで、こういう仕組みになるんでしょう。

「5項ピタゴラス」の導出↓

a2 + (a+1)2 + (a+2)2 = b2 + (b+1)2
(2b + 1)2 − 6(a + 1)2 = 3 を含意するので、
題意を満たす x2 − 6y2 = 3 の解を求めればいい。ここで x = 2b + 1, y = a + 1

(3 + 1√6)(5 + 2√6) = 27 + 11√6, b = (27 − 1)/2 = 13, a = 11 − 1 = 10

第2解: (3 + 1√6)(5 + 2√6)2 = 267 + 109√6, b = (267 − 1)/2 = 133, a = 109 − 1 = 108 より
1082 + 1092 + 1102 = 1332 + 1342 = 35645

第3解: (3 + 1√6)(5 + 2√6)3 = 2643 + 1079√6, b = (2643 − 1)/2 = 1321, a = 1079 − 1 = 1078 より
10782 + 10792 + 10802 = 13212 + 13222 = 3492725

〔補足〕 拡張ペル方程式 x2 − 6y2 = 3 の最小解は x = 3, y = 1、それに対応する実数は 3 + 1√6。 対応する狭義ペル方程式 x2 − 6y2 = 1 の最小(非自明)解は x = 5, y = 2、それに対応する実数は 5 + 2√6。よって、この拡張ペル方程式の (x, y) = (3, 1) と同系列の一般解(3 + 1√6)(5 + 2√6)n の形を持つ; n = 0 は、拡張ペル方程式の最小解 (x, y) = (3, 1) に当たり、「5項ピタゴラス」としては、自明解 02 + 12 + 22 = 12 + 22 となる(a = 0, b = 1)。

「7項ピタゴラス」の導出↓

a2 + (a+1)2 + (a+2)2 + (a+3)2 = b2 + (b+1)2 + (b+2)2
(2a + 3)2 − 3(b + 1)2 = −3 を含意するので、
題意を満たす x2 − 3y2 = −3 の解を求めればいい。ここで x = 2a + 3, y = b + 1

(0 + 1√3)(2 + 1√3)3 = 45 + 26√3, a = (45 − 3)/2 = 21, b = 26 − 1 = 25

第2解: (0 + 1√3)(2 + 1√3)5 = 627 + 362√6, b = (627 − 1)/2 = 313, a = 362 − 1 = 361 より
3122 + 3132 + 3142 + 3152 = 3612 + 3622 + 3632 = 393134


Prime Curios!

→ Prime Curios!


暦・天文

→ 暦・天文


メールアドレス(画像)