Mathematics in Lean4の数論の章の3つ目のセクションではいよいよ「自然数には素数が無限個ある」ことを形式化して証明します。 証明方法として3つのやり方が説明されています。それぞれの形式化も異なるので下記に記載してみました。 ある自然数nに対して必ずnよりも大きな素数が存在する（作れる）ことを示す。theorem primes_infinite : ∀ n, ∃ p > n, Nat.Prime p := by... 素数が有限個しかないとして、それらの積に1を足した数を考えるとその素因数が元の素数の集合に含まれることから矛盾を導く（ユークリッド）。theorem primes…
有限の場合の総和記号について勉強したことで任意桁数の場合の3の倍数の確認方法について形式化して証明することが出来そうです。ということでやってみました。 まず与えられた自然数が3の倍数かどうかの確認方法と普通の証明をざっと述べてみます。 3の倍数の確認方法：$N, i, a_i$を自然数として$a_i$は各桁の数を表します。従って$\sum_{i=0}^{N-1} a_i\cdot 10^i$が与えられた自然数です。確認方法は、$$3 \sum_{i=0}^{N-1} a_i\cdot 10^i \iff 3 \sum_{i=0}^{N-1} a_i$$が成り立つので、右辺の和（各桁の数…
Mathmatics In Lean4の第5章 初等数論の2つ目の話題は帰納法と再帰です。自然数では定義が帰納的であること（自然数型は帰納型であること）を知ります。 inductive Nat zero : Nat succ (n : Nat) : Nat この意味は、0はNat型、Nat型の要素を1つとってnとするとsucc nもNat型です。そしてsucc n=0となるようなnはありません。ちなみにsucc nはn+1とも書かれます。 次にこの型の上で階乗関数を再帰的に定義します。 def fac : ℕ → ℕ 0 => 1 n + 1 => (n + 1) * fac …
まだ小学生の頃に習ったことで印象に残っているのは3の倍数の確認方法でした。各桁を足した数が3の倍数ならば元の数も3の倍数、というアレです。 倍数とか約数とかがLean4で扱えるようになり、この3の倍数の確認方法の証明を書き下してみようと思いました。自分で定理を形式化して証明を与えることを一通りやるには良いのではないかと思ったのです。 任意桁数の3の倍数で証明しようとすると、その数の10進数展開がk桁あるとして各桁を$a_n$とすると$\sum_{n=0}^{k-1} a_n\,10^n$と表すことができるところから始める必要があります。まだ$\sum$記号を勉強していないこともあり、えいやで3…
Mathematics in Lean 4で進めてきているLean4の勉強も第4章となり、初等整数論が扱えるところまで来ました。 最初の節では$\sqrt{2}$が無理数であることを示します。とはいってもこの段階で示すことは$\sqrt{2}$が有理数であるとして矛盾を導くことまでです。$\sqrt{2}$が実数の中に存在することまで示すわけではありません。 証明は古代ギリシャから知られているものです。$\sqrt{2}=\frac{m}{n}$となる互いに素な自然数$m,n$が存在するとします。すると $$m^2=2\,n^2$$ です。ここから$m$が偶数であることがわかります。$m=2\…
第4章「集合と関数」の最後のセクションはシュレーダー＝ベルンシュタインの定理のLean4による証明です。 初めてこの定理をきちんとした形で知りました。集合論の濃度に関する基本的な定理です。 定理：$\alpha, \beta$を集合、$f:\alpha \rightarrow\beta, g:\beta\rightarrow\alpha$が両方とも単射である時、$\alpha$から$\beta$への全単射がある。 集合の濃度に関して$ \alpha \ge \beta , \beta \ge \alpha $のとき$ \alpha = \beta $が成り立つということで確かに基本的です…
Mathematics in Leanの第4章「集合と関数」の中の2つ目のセクションである「関数」を読みながら練習問題を解いています。その問題の中で集合族の積集合の写像と集合族の写像の積集合に関する問題がありました。全称量化子と存在量化子が絡み、なかなか手強かったので、紹介したいと思います。 練習問題とその証明は下記のとおりです。 example (i : I) (injf : Injective f) : (⋂ i, f '' A i) ⊆ f '' ⋂ i, A i := by01 intro y h102 simp at h103 simp04 have : (∃ x, (∀ (j : …
しばらく前のmacOSではbluetoothイヤフォンで音楽を楽しむ際、コーデック選択の問題で音質が悪い状況がありました。私もiMacとソニーのWF-1000MX4 の組み合わせでこの辺について色々と試してきています。 最近知ったのですが、この状況は少なくともmacOS Sonomaでは大きく改善された面もあり改善されていない面もあります。 以前のmacOSではbluetoothイヤフォンの(正確にはA2DPプロファイルで使う)デフォルトのコーデックがSBCでした。このためたとえイヤフォンがAACをサポートしていてもSBCで繋がってしまい、音が悪い、ということが発生していました。よく知られた改…
Mathematics in LeanもC04 Sets and Functionsの最初の章である集合まで辿り着きました。ここでは集合に関する性質の証明方法のLean4での実現の仕方を知ります。 集合が等しいこと(A=B)を示す場合、ゴールをA=Bとして方法として、AがBの部分集合であり、かつBがAの部分集合であることを示すこと AがBの部分集合であることを示すにはAの任意の要素がBの要素であることを示すこと 空集合と全体集合の性質 和集合と積集合をメンバーシップの論理和と論理積 集合族の積集合と和集合 のようなことがここでは解説されています。ここでは上記の初めの2つについて簡単な命題を示し…
Lean4を証明支援系として使っていても、型と証明の対応や関数型言語が突然現れることがあります。このことを知っていないと証明が読めないことがありました。 具体的には例えばある定理がこんな形だったとします。 def P (x:ℕ) : Prop := sorrytheorem theoA : ∀ x > 3, P x := sorry P xを命題としてxが3より大きい場合はP xが成り立つ、というのがtheoAという定理です。 当然P 4は4>3なので成り立つはずです。証明は普通はこんなふうにやると思うのです。 example : P 4 := by apply theoA -- ⊢ 4 > …
Lean4での論理記号の取り扱いの勉強も後半です。今回は論理積と論理和の扱いを見ていきます。この辺はあまり難しい話は出てきません。 ゴールが論理積A ∧ Bの形の場合にはconstructorタクティクを使うとAとBが両方ともゴールとなり両方証明するとA ∧ Bの証明が終わります。 仮定にh:A ∧ Bがある場合には仮定としてAとBが成り立つのですからバラしてそれぞれを仮定としたいですよね。仮定にh1:Aとh2:Bを入れるにはrcases h with <h1,h2>とかhave <h1,h2>:=hなどとすれば良いです。 ゴールが論理和A∨ Bの形の場合にはAかBのどちらかを証明できれば良い…
否定が論理式に含まれているとき使えるタクティクを勉強しました。 introタクティク：ゴールがある命題の否定¬ Aである場合、intro hとすると仮定h: Aが導入されて、ゴールがFalse (矛盾)に変わります。仮定の集まりの中で適当な命題Bについてhb:Bとhbn:¬ Bを両方含むようにできれば最後にapply hb hbnで矛盾を導いて証明が終わります。 by_contraタクティク：ゴールが特に否定の形ではない場合でも、by_contra hとすることでゴールの否定を仮定hとして導入するとともに、ゴールをFlase(矛盾)にすることができます。仮定の中で矛盾を導くことで証明を終了させ…
現役で最高の数学者のお一人で情報発信にも熱心なテレンスタオ教授のブログがあります。 terrytao.wordpress.com 残念ながら難しすぎて普段はほとんど見ない数学ブログですが、Lean4の勉強をしていたら検索で記事が1つヒットしました！ A slightly longer Lean 4 proof tour What's new 実数の2つの無限数列に関するある補題の証明をLean4を使って形式化して確認する、というものです。証明自体は望遠鏡和(telescoping sum)という手法を使ったものです。有限和をうまく作ると、実は隣り合った項が打ち消しあって最初と最後の項だけが…
ゴールに存在量化子が入っている場合、存在量化子がついた変数に値を入ることでゴールの論理式を証明することができます。useタクティクを使うと、「この値を使え」ということができます。例えばこんな感じです。 example : ∃ x : ℝ, 2 < x ∧ x < 3 := by use 5 / 2 -- ⊢ 2 < 5 / 2 ∧ 5 / 2 < 3 norm_num -- No goals ゴールの論理式の意味は「2より大きくて3より小さい実数xが存在する」です。まあ当たり前ですがどうやって証明するかです。この場合xが$\frac{5}{2}$であればこの不等式は確かに成立するので、xが存在…
今勉強しているMILの第3章「論理」では仮定の論理式やゴールの論理式に登場する論理記号をタクティクでどのように取り扱えば良いのかを説明しています。 この章の最初の方で説明されるのは全称量化子 ∀ です。ゴールの論理式にこの論理記号がついている場合、その変数や中身の式を証明することができません。そこで多くの場合には全称量化子 ∀を外してその中身にアクセスできるようにすることが証明の第一歩となります。 全称量化子 ∀がゴールの論理式に登場している場合、introタクティクを使うとその変数がラベル付きで導入されて、以降の証明で使えるようになります。 例えば前回見たcalcモードの説明の記事では偶関数…
前の記事でcalcモードがわかっていないと書きました。calcは便利そうなのでとりあえず簡単なユースケースを勉強しました。理解できたと思うのでメモを残しておきます。 Quantifiers and Equality - Theorem Proving in Lean 4にある説明を中心にして理解しました。最も典型的なユースケースは等式A=Bを証明する場合です。式Aから始めてタクティクを使って変形し、式Bを導ければ等式証明が成功します。等式変形なので使うタクティクはrwで、仮定や既知の定理を使って式変形します。 現在勉強中の第3章「論理」の中ので分かり易い例があったので紹介します。偶関数と奇関数…
数学の記事では普通は環境について書かないのですが、Lean4はプログラミング環境でもあるし、一応概要を記しておきます。 パソコン：M1 iMac (主記憶16GB), macOS 14.2.1 Lean (version 4.5.0-rc1) VS Code バージョン1.85.1 VS Code機能拡張Lean4 v0.0.124 起動中のVSCodeの様子はこんな感じです。縦分割の左から、フォルダ階層、Mathematics In Lean、練習ファイル、証明ゴール が表示されています。 MILの「2章 基本」の最後の練習問題である「距離関数は常にゼロ以上」の証明が終わったところが練習ファ…
"Mathematics In Lean"に沿ってLean4の証明支援系の勉強を進めています。まだ基本編で、今やっているのはmin, maxの性質の証明です。具体的には全順序集合上の関数min a b （a, bの小さい方を返す）について次の性質の証明です。 min a (min b c) = min (min a b) c 直感的には結局両辺ともa,b,cのうち最小の値を返しますから等しくなるのは納得です。一方この学習では以下の4つの性質だけから上記の性質を示すことが課題です。 le_antisymm : a $\le$ b $\land$ b $\le$ a $\iff$ a=b min_…
これからしばらくの間はLean4の証明支援系の勉強の話をシリーズ的に記事にします。相変わらず自分の勉強メモのような感じです。つまづいたところや感動したところを中心に書いていきます。 使用するテキストはMathematics In Lean(通称MIL)にしました。 Mathematics in Lean — Mathematics in Lean 0.1 documentation もう1つ、"Theorem Proving In Lean4"(通称TPIL)というテキストもありそちらは有志の皆様による日本語版もあります。両者の最大の違いは、MILはmathlib4という証明ライブラリも利用し…
年末は帰省していたのですが、有休含めて1/8までお休みにしたこともあり時間ができました。そこでLean 4を勉強してみることにしました。 Lean 4は以前このブログで紹介したLean 3と呼ばれる定理証明支援システムの後継システムです。 Lean 4からは関数型プログラミング言語としても使える、という触れ込みのようです。そこで今回はまず関数型プログラミング言語としてのLean 4を勉強してみました。勉強に使ったテキストは Functional Programming in Lean - Functional Programming in Lean です。このテキストを1章から4章まで読んでみ…
この記事では平方剰余の相互法則の証明に必要な補助定理である命題4.19を証明します。そためにまず命題4.18を補題として示します。 命題4.18$p,q$を相異なる奇素数、有限体$F_p$上で$1$の原始$q$乗根の1つを$\zeta$とします。法$q$に関する平方剰余記号の値を係数とする$\zeta$のガウス和を$ G_q=\sum_{a=1}^{q-1}\left( \frac{a}{q} \right)\zeta^a $と定義します。この時任意の整数$k$について次が成り立ちます。$$\sum_{a=1}^{q-1}{\left( \frac{a}{q}\right)\,\zeta^{k…
この記事では補助定理の1つである命題4.16 $G_q^2=q^{\ast}$ を証明します。そのためにまず、補題4.17 を示します。 補題4.17$a$を整数、$\mu \neq 1$を$1$の$n$乗根とするとき、$$\sum_{k=1}^{n-1}{\mu^{a\,k}}= \begin{cases}n-1 & (a \equiv 0\,(mod\,n))\\-1 & (a \not\equiv 0\,(mod\,n))\end{cases}$$ 証明 1) $a \equiv 0\,(mod\,n)$の場合、すなわち$a$が$n$の倍数の場合には$\mu^{a\,k}=(\mu^a)…
いよいよ山本先生の本数論入門 (現代数学への入門)による相互法則の証明を見ていきます。有限体$F_p$におけるフロべニウス写像とガウス和を用いた証明です。今回はいくつかの補助定理を紹介し、それらを使った相互法則の証明を紹介します。それぞれの補助定理の証明は次回以降にしましょう。 まずは平方剰余の相互法則を再掲します。 命題4.9 相互法則 $p,q$を奇素数とします。$$\left(\frac{q}{p}\right)\,\left(\frac{p}{q}\right)=(-1)^{\frac{p-1}{2}\,\frac{q-1}{2}}=\begin{cases}1 & p\equiv 1…
今回はいきなり第2補充則の証明から行きます。前回の記事 では第2補充則において$\sqrt{2}^p$の指数の$p$が変化するとそれに伴って平方剰余記号の値$\left(\frac{2}{p}\right)$が周期$8$で変化することを観察しました。 今回は山本先生の数論入門 (現代数学への入門)で紹介されている証明を見ていきます。ここでは$\sqrt{2}$を有限体$F_{p^2}$の中の$1$の原始$8$乗根の適当な和で表しています。これを$p$乗すると和の$p$乗は$p$乗の和を使い、$\sqrt{2}^p$を$1$の$8$乗根の$p$乗の適当な和で表すことができます。 これが周期$8$…
以下の式は$F_p$のフロべニウス写像によって$a$がいつ平方剰余になるのかを特徴づけているとも見えます。 $$\sqrt{a}^p=\left(\frac{a}{p}\right)\,\sqrt{a}\tag{A}$$ それが前回の記事の最後のステートメントでした。それらを再掲します。 「このことから第1補充則、第2補充則、相互法則をフロべニウス写像の言葉で言うと次のようになります。 $\sqrt{-1}^p=\sqrt{-1}$となる$p$の条件を求めること。 $\sqrt{2}^p=\sqrt{2}$となる$p$の条件を求めること。 $\sqrt{q^{\ast}}^p=\sqrt{q^…
ちょっとだけおさらいから入りましょう。 $p$を素数、$F_p$を 位数$p$の有限体とします。$F_p$の$0$以外の元の集合$F_p^{\times}$は位数$p-1$の巡回群になります。そうするとフェルマーの定理から任意の$x\in F_p$について$x^{p-1}=1$が分かります。両辺に$x$を掛ければ$x^p=x$となります。この式は$x=0$も含めて$F_p$の全ての元で成り立ちます。また$x^p=x$を$F_p$あるいはその拡大体での方程式と見た時、その解の個数は多項式の理論から高々$p$個です。一方、実際に$p$個の要素を持つ有限体$F_p$の元は全てこの方程式の解となってい…
いよいよこのシリーズも核心に入っていきます。今回は平方剰余の定義を与え、平方剰余記号を定義します。また平方剰余の基本的な性質を示した後、平方剰余の相互法則と関連する補充則などを紹介し、簡単なものには証明をつけます。最後に平方剰余の相互法則をより対称な形で表した命題を提示し、それが成り立つことをMaximaで再確認してみます。 定義 \(p\)を奇素数として\(a\)を\(p\)と互いに素な整数とします。\(a\)がある整数\(n\)の平方と法\(p\)で合同である時、\(a\)を\(p\)の平方剰余であるといいます。式で書けば、方程式\(X^2\equiv a\,(mod\,p)\)が解を持つ…
window.addEventListener('message', function(e) { var iframe = document.getElementById("tako"); var eventName = e.data[0]; var data = e.data[1]; switch(eventName) { case 'setHeight': console.log(data); iframe.style.height = data + "px"; break; } }, false); 前の記事で有限体\(F_p\)やその拡大体\(F_{p^f}\)で成り立つ幾つかの命題と…
駆け足で有限体を復習しましょう。 定義 有限体\(F_p\) 整数をある素数\(p\)で割った余りの集合\(\{0,1,\cdots,p-1\}\)には整数の加算や乗算の結果を\(p\)で割った余りとして自然に加算、乗算が定義でき、それらの単位元は\(0,1\)です。また全ての元に対して加算の逆元があり、\(0\)を除く全ての元に対して乗算の逆元があります。従って\(\{0,1,\cdots,p-1\}\)は体になります。この集合は要素数\(p\)の有限体であり記号\(F_p\)で表します。 具体的に\(p=3\)の有限体を例として考えてみましょう。\(F_3=\{0,1,2\}\)です。加算…
小島寛之先生のブログ記事 で山本芳彦先生の著書「数論入門」 数論入門 (現代数学への入門) 作者:山本 芳彦 岩波書店 Amazon が絶賛されていました。その中で印象に残ったのが、有限体を使った平方剰余の相互法則の証明が秀逸、という点でした。 山本先生のこの本にはこのブログの以前の記事でも色々とお世話になっていますが、平方剰余は個人的に苦手意識もありちゃんと読んでいませんでした。改めて第3章剰余環から読んでみました。1週間くらいかけて有限体の復習、平方剰余と\(F_p\)とフロべニウス写像\(x^p\)、有限体のガウス和、そして平方剰余の相互法則の証明を理解することができました。 その過程で…
昨年の11月にVMwareからVMware Fusion Player 13がリリースされました。VMware Fusion PlayerはmacOS上で仮想マシンを実行できるソフトウェアで、UTMやVirtualboxなどと同様のカテゴリの製品です。 store-jp.vmware.com セキュリティ関係でKali Linuxを使いたくてUTMにインストールしたのですが、Apple virtualizationではキーボードのマッピングが変で や_が入力できずshell操作がろくに出来ません。QEMUではキーボードはいいのですがスピードが遅くて困りました。 VMware Fusion Pl…
今年最後の記事は最近よく聴く楽曲の話です。 www.youtube.com Da-iCEのAnswersという楽曲です。最近お気に入りでよく聞いていたのですが、歌詞の中に「円周率」という言葉が聞こえることに気がつきました。おっ！と思って歌詞を調べてみると数学の用語が散りばめられていることがわかりました。 以下は数学に関係する単語とフレーズを抜き出してみたものです。 確率を知る為の公式、方程式、割り切れない円周率、導き出した答え、 理解して解くまでなどでもやり直そう 0をかけて台無しにしない 自然数、定義、数学 そもそも曲のタイトルがAnswersですね。数学をとても意識して作詞されたのでしょう…
この記事では最も簡単なシンギュラーモジュリ\(x_2\)を求めてみます。この値は前回の記事で求めた式 $$\frac{2}{\pi}=\sum_{k=0}^{\infty}(-1)^k\,A_k\,(4\,k+1), ただしA_k=\frac{\left( \frac12\right)_k^3}{k!^3}$$ でも使いました。 シンギュラーモジュリ\(x_2\)を求めるにあたりもう一度その定義を復習しておきましょう。アイゼンシュタイン級数の議論では一貫して次のような記号を定義して使ってきました。 $$q=e^{-y}, f(-q)=\prod_{n=1}^{\infty}(1-q^n), z…
