# 數學之美

## 質數
- 質數定理：在{2,3,...,n)中的質數，大約有$\frac{n}{log_en}$ 個
- 歌德巴赫猜想：任何大於二的偶數，可以寫成兩質數和。
- 孿生質數猜想：孿生質數有無窮多個。
- 目前被證明相差不超過246的質數對，有無窮多個
- RSA
- TLS/SSL使用RSA加密，防止機密資料在傳輸過程被竊取
- 步驟：
- 1.挑出大質數p,q，算出
- **n=pq**
- **m=(p-1)(q-1)**
- 2.挑出和m互質的質數**e**
- 3.找出e的乘法反元素**d**(mod m)
- 4.(e,n)是公鑰，(d,n)是私鑰
- 加密：$密文=明文^e~mod~n$
- 解密：$明文=密文^d~mod~n$

- 定理一：質數的個數有無窮多個
- 1.Euclid反證法：假設有限多個 -->矛盾
- 2.歌德巴赫：兩兩互質的數字有無窮多個 -->質(因)數無窮多
- 費馬數$F_n=2^{2^n}+1$
- Lemma2：$F_j=2+\prod\limits_{i=0}^{j-1}F_{i}$
- $2+\prod\limits_{i=0}^{j-1}F_{i}=2+\prod\limits_{i=0}^{j-2}F_{i}F_{j-1}=2+(F_{j-1}-2)F_{j-1}=F_j$
- Lemma1：費馬數兩兩互質
- $gcd(F_i,F_j)|F_j-2$
- $gcd(F_i,F_j)|F_j$
- 3.拉格朗日(有限乘法群)
- 4.Euler
- 5.Furstenberg
- 6.Erdos
- 疊書問題
- $d_i=\frac{1}{i}$
- $\sum\limits_{i\gt0}\frac{1}{i}=\infty$ 調和級數
- 定理二：$\sum\limits_{p~is~prime}\frac{1}{P}=\infty$
- 1.平方數觀察：1~2n的平方數，最多$\sqrt{2n}個$
- 2.次不過一觀察：$p_1^{b_1}...p_k^{b_k}形式的數，最多2^k種$
- 3.前質因數觀察：1~2n的數中，$c^2p_1^{b_1}...p_k^{b_k}形式的數，最多\sqrt{2n}2^k種$
- 4.後質因數觀察：1~2n的數中，p的倍數最多$\frac{2n}{p}個$
- 5.關鍵觀察：如果$r_1,r_2,...$是實數，且$\sum\limits_{i=1}^{\infty}r_i<\infty$，則存在k使得$\sum\limits_{i=k}^{\infty}r_i<\frac{1}{2}$
- 證明：令$p_1,p_2,...$是所有的質數
- 假設$\sum\limits_{i=1}^{\infty}\frac{1}{p_i}<\infty$，則存在k滿足$\sum\limits_{i=k}^{\infty}\frac{1}{p_i}<\frac{1}{2}$
- $n=2^{2k+1}$，後質因數$=\{p_k,p_{k+1},...\}$
- $N_前=\{1\sim 2n中沒有後質因數的數\}$
- $N_後=\{1\sim 2n中有後質因數的數\}$
- $|N_後|\le\frac{2n}{p_k}+\frac{2n}{p_{k+1}}+...<n$
- $|N_前|\le 2^{k-1}\cdot\sqrt{2n}=2^{k-1}\cdot\sqrt{2^{2k+2}}=2^{2k}<n$
## 無窮與無理1
- 刀砍海怪
- 任意砍掉一個頭（紅點）
- 如果砍的頭直接長在身體（黑點）上
- 砍掉就砍掉，直接進入下一回合
- 如果砍的頭是長在脖子（藍點）上
- 砍掉之後，在進入下一回合之前，必須先把分支都複製兩份
- 定理一：從任何長相的海怪開始，以任何順序砍頭，最後海怪必定會被消滅。
- 定理二：只根據Peano的自然數公設是絕對證不出定理一。
- 1.0 是自然數。
- 2.如果 a 是自然數，則 a 的後繼元素也是自然數。
- 3.0 不是任何自然數的後繼元素。
- 4.如果兩個自然數的後繼元素相等，則這兩個自然數相等。
- 5.如果有一個自然數的子集 S 包含 0 ，同時，也包含 S 之中每一個元素的後繼元素，則每一個自然數都落在 S 這個集合之中。
- 哥德不完備
- 希爾伯德認為：自然數的性質只要成立就一定可以證得出來
- 哥德卻證出：任何數學系統只要包含Peano Axioms，就必定有個該系統可以描述的正確敘述，是在該系統中絕對證明不出來的
- 海怪對應自然數
- 每個海怪對應到二進位中某個整數
- f(x,i)=y，是一個給定的function，滿足海怪性質
- 海怪定理：每個自然數x，對每個無窮序列$i_1,i_2,...$，都存在某個自然數k，使得$f(f(...f(x,i_1),...)i_k)=0$
- 3n+1猜想
- 又稱**奇偶歸一猜想**、**3n＋1猜想**、**冰雹猜想**、**角谷猜想**、**哈塞猜想**、**烏拉姆猜想**、**敘拉古猜想**
- ，只要從正整數開始，一定會收斂到 1
- 停機問題
- Turing用對角線證法，證明這個問題不存在任何電腦硬體軟體能正確解答

- 黃金比例 $\phi$
- 畢氏音階：不同音高的音階，頻率比為$3^n:2^m$
- 五芒星： 
-  
- 定理三：對任意兩整數a,b，
- 尤拉數 $e$
- 
- 尤拉數來自金融：
## 無窮與無理2
- 尤拉 Leonhard Euler (1707－1783）
- 平均每年發表八百頁的學術論文，是史上發表論文數第二多的數學家，紀錄到20世紀才被Paul Erdős打破
- 人生最後7年，雙目全盲，仍以驚人速度產出生平一半著作
- 七橋問題、$i=\sqrt{-1},sin,cos,\pi$
- 定理：對任意正整數a,b，$\sum\limits_{n=0}^{\infty}\frac{1}{n!}\ne\frac{a}{b}$
- $m=b!(\frac{a}{b}-\sum\limits_{n=0}^{b}\frac{1}{n!})=b!\sum\limits_{n=b+1}^{\infty}\frac{1}{n!}=\frac{1}{b+1}+\frac{1}{(b+1)(b+2)}+...$
- $<\sum\limits_{n=1}^{\infty}\frac{1}{(b+1)^n}=\frac{\frac{1}{b+1}}{1-\frac{1}{b+1}}=\frac{1}{b}\le1$
- 等比級數
- $1+r+r^2+...=\frac{1}{1-r}$
- 公式
- $\frac{\pi}{4}=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+...$
- $\frac{\pi^2}{6}=1+\frac{1}{2^2}+\frac{1}{3^2}+\frac{1}{4^2}+...=\zeta(2)$
- $\frac{\pi^4}{90}=1+\frac{1}{2^4}+\frac{1}{3^4}+\frac{1}{4^4}+...=\zeta(4)$
- Buffon’s needle
- 長度l針與相距1的直線香交的機率為何?
- $P(m\le0.5~l~cos\theta)=\frac{2l}{\pi}$
- $\pi$是無理數
- $tanx=\frac{x}{1-\frac{x^2}{3-\frac{x^2}{5-\frac{x^2}{...}}}}$
- x是有理數，則tanx是無理數。
- tanx是有理數，則x是無理數。
- $\pi^2$是無理數，因此$\pi$是無理數
- $e^\pi$是無理數
- $e+\pi，~~~e\cdot\pi，~~~\frac{e}{\pi}，~~~\pi^e$不知道是否為有理數
- $e^{i\pi}+1=0$
- 集合比大小
- $|R|\le|S|如果存在從R到S的一對一函數$
- $|R|=|S|~if~|R|\le|S|~and~|S|\le|R|$
- $|R|<|S|~if~|R|\le|S|~and~|R|\ne|S|$
- $B=C/\{P\}$
- $|B|=|C|因為|B|\le|C|且|C|\le|B|$
- 可數無限
- 跟自然數的大小一樣
- 質數，偶數，有理數
- 電腦有解的問題個數
- 不可數無限
- 跟自然數的大小不同
- 無理數, 實數, 複數
- 電腦注定無解的問題個數
- **實數是不可數集合**：對角線證法
- 相差5
- $0.999...=1$
- 最小的無窮基數$\aleph_0=|N|=\beth_0$
- 第二小的無窮基數$\aleph_1$
- 第三小的無窮基數$\aleph_2$
- 幂集$2^S=\{R\subseteq S\}$
- 如果S有限，則$|2^S|=2^{|S|}$
- $|S|<|2^S|$
- 如果S有限，則$|S|<2^{|S|}=2^{|S|}$
- $對s\in S，\{s\}是2^S的成員$
- $\beth_0=|N|$
- $\beth_1=|2^N|$
- $\beth_2=|2^{2^N}|$
- 連續統假設 Continuum Hypothesis(CH)
- $|R|=\aleph_1$
- ZFC集合論公設
- 外延、正規、分類
- 配對、聯集、替代
- 無窮、幂集、良序、選擇
- 羅素悖論
- $R=\{S:S\notin S\}$
- $S\notin S$ 的例子
- $S=\phi$
- $S=\{1,2\}$
- $S=\{1,\{S\}\}$
- $S\in S$ 的例子
- $S=\{S,1,2\}$
- $S=\{S,\{S\}\}$
- $S=\{R~is~a~set\}$
- $|2^S|\le|S|$ 違反 $|S|<|2^S|$
- 並不是把任意一些『東西』收集起來就是集合，可能not well defined。
- ZFC集合論公設，是目前最普遍被接受的公設組合
- 希爾伯特旅館悖論
- 可數無限多個房間的旅館
- 有限個新客人
- $1\rightarrow 2，2\rightarrow 3，3\rightarrow 4，...$
- 無限個新客人
- $1\rightarrow 2，2\rightarrow 4，3\rightarrow 6，...$
- 無限客車每輛有無限客人
- 第i輛車，安排在 $p^n$房間，其中p是第i+1質數
- 網球悖論
- 在1/2分鐘，依序丟入兩球，拿走一球
- 在1/4分鐘，依序丟入兩球，拿走一球
- 在1/8分鐘，依序丟入兩球，拿走一球
- ...
- 如果每次拿走的球，是最晚丟入的，則袋子裡有無窮多球
- 如果每次拿走的球，是最早丟入的，則袋子沒有球
- 如果每次拿走的球，是隨機的，**則袋子沒有球**
- 一號球在袋子機率為0
- 二號球在袋子機率為0...
- 死神悖論
- 0.999999… = 1，差距不存在所以相等
- 致死致命物不存在所以安全
- 在(0,1)之中放可數無窮多的致命物，依序放於$1/2^n$
- 從0的右邊出現然後左移，必定會碰到某個致命物
- 從0的左邊出現然後右移，**不會碰到致死致命物**
- 假設最先碰到的致命物為$1/2^k$
- 但應該會更先碰到$1/2^{k+1}$，矛盾
## 無理之理一
- 有理數和無理數有稠密性
- 代數數(algebraic)：有理係數多項式的根。
- 超越數(transcendental)：其他。
- 
- 代數數(algebraic)
- 包含了三大類
- 所有的有理數
- 部分的無理實數
- 部分的複數
- 問題：代數數可不可數?
- 整係數多項式可數，所以代數數可數
- 超越數(transcendental)
- 1.劉維爾Joseph Liouville
- 第一個證明超越數存在
- 1844證明了$\sum\frac{1}{10^{n!}}是超越數$
- 小數點後第$1!,2!,3!$...是1，其他是0
- 2.埃爾米特Charles Hermite
- 1874證明出e是超越數
- 伴隨運算子
- 3.馮林德曼Ferdinand von Lindemann
- 1882證明π是超越數
- 化圓為方是不可能的
- 三大幾何難題
- 三等分角：給出任意一個角θ，求作一角等於θ/3。
- 倍立方體：求作一立方體，使其體積等於已知立方體體積的二倍。
- 化圓為方：求作一正方形，使其面積等於一已知圓的面積。
- Pierre Wantzel
- 1837年證明三等分角與倍立方體無法以尺規作圖完成
- 帕普斯
- 著有【數學彙編】
- 質疑歐幾里得的作圖法沒有根據:
- 「怎知相交的圓一定有交點?」
- 規矩數
- 可以用圓規直尺畫出來的長度
- 規矩數一定是代數數
- 化圓為方不可能
- 坑洞
- 有理數Q有洞，如$\sqrt{2}$
- 有理數與無理數聯集起來無洞，稱為實數
- 實數R又稱為：continuum連續統。
- 戴德金Richard Dedekind
- 高斯的關門弟子，黎曼的好朋友
- 史上第一個用有理數來定義實數的方法
- **戴德金切割** ： 有理數子集 $L$滿足(每個切割對應實數)
- 1.不空不滿
- 2.向左封閉
- 3.無最大值
- $R=Q$\ $L$ 有最小元素的切割，對應到有理數
- $L:\{q\in Q|q<0.1\}，R:\{q\in Q|q\ge 0.1\}$
- $R=Q$\ $L$ 最小元素不存在的切割，對應到無理數
- $L:\{q\in Q|q^2<2\}，R:\{q\in Q|q^2\ge 2\}$
- 切割一些定義
- $L_0=Q^-=\{q\in Q|q<0\}$
- $L_1=\{q\in Q|q<1\}$
- $-L=\{q\in Q|q<-r\}$
- $L_1<L_2\leftrightarrow L_1\subsetneq L_2$
- 此外有以下性質
- $L+L_0=L$
- $L\cdot L_1=L$
- $L_1+L_2=\{q_1+q_2|q_1\in L_1,q_2\in L_2\}$
- $L_1-L_2=L_1+(-L_2)$
- 實數集合大小：$|R|=\beth_1$
- $|R|\le|2^Q|=\beth_1$
- 因為每個實數可以用一個有理數的子集合來表示。
- $\beth_1=|2^N|\le2|R|=|R|$
- 因為任何$2^N$裡的元素，可以用$[0,1)$中的二進位數來表達。
- 一些集合大小比較
- 整數 $\beth_0$
- 整數切割 $\beth_0$
- 有理數 $\beth_0$
- 有理數切割 $\beth_1$
## 無理之理 怪怪實數
- [0,1]中的有理數
- $\frac{\beth_0}{\beth_1}=0$
- [0,1]中實數長度為1
- [0,1]中有理數長度為0
- 目標：找一個[0,1]子集合\$ ， 使得 |\$|=$\beth_1$ 且 \$ 的長度為0
- 
- 1.長度為0，因為每次長度變成原本的2/3
- 2.|\$|=$\beth_1$，因為剩下的數恰好為，三進位表示法只有0和2的小數
## 無理之理 怪怪等比級數
- $\frac{1}{1-r}=1+r+r^2+r^3+...$
- 等比級數證明
- 
- 奇怪的性質
- 
- 懷疑人生三等式
- 
- 等式一：切薩羅收斂
- 兩個收斂的無窮級數相乘之後雖然未必收斂但必定是切薩羅收斂。
- $(1-\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}-\frac{1}{\sqrt{4}}+...)(1-\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}-\frac{1}{\sqrt{4}}+...)$發散但切薩羅收斂。
- 等式二：
- $1-2+3-4+5-6+...=(1-1+1-1+1-...)^2=\frac{1}{4}$
- 等式三：
- 
- 因此 $1+2+3+4+5+...=-\frac{1}{12}$
- 計程車數
- 
- Srinivasa Ramanujan 拉馬努金1887－1920
- Godfrey Harold Hardy 哈代1877－1947

## 黎曼zeta函數
- $\{x\in R:0<|x|<1\}：f(x)=\frac{1}{1-x}$
- $\{z\in C:z\ne1\}：g(z)=\frac{1}{1-z}$
- $\{r\in R:r>1\}：h(r)=\sum\frac{1}{n^r}$
- $\{r\in C:r\ne1\}：\zeta(r)=\sum\frac{1}{n^r}$
- $\zeta(-1)=-\frac{1}{12}$
- $\zeta(2)=\frac{\pi^2}{6}$
- $\zeta(4)=\frac{\pi^4}{90}$
- $\zeta(3)\sim1.202056$，阿培里常數，是無理數，不知是否超越
- $\zeta(1^+)=\infty$
- $\zeta(1^-)=-\infty$
- $\zeta(2n)=\frac{b}{a}\pi^{2n}$，必定是無理數
- $\zeta(2n+1)$，不知是否為無理數
- 黎曼函數定義：
- 
- $\{r\in C:r\ne1\}：\zeta(r)=\sum\frac{1}{n^r}$
- $\zeta(5),\zeta(7),\zeta(9),\zeta(11)$，有一個無理數
- $\zeta(5),\zeta(7),~...~,\zeta(69)$，有兩個無理數
- **黎曼猜想**：$\zeta(z)=0\leftrightarrow$
- 1.$z=-2n$
- 2.$z=\frac{1}{2}+yi$
- 等價於：
- 3個隨機正整數互值的機率=$\prod(1-\frac{1}{p^3})$
- 4個隨機正整數互值的機率=$\prod(1-\frac{1}{p^4})$
- Gelfond Schneider Theorem
- ${非0、1代數數}^{非有理代數數}：是超越數$
- $e^\pi=(-1)^{-i}：是超越數$
- 解析拓延 analytic continuation
- 拓延(extension)：擴大定義域，不改變原本取值
- 解析(analytic)：可以用定義域中每個點，及其鄰居開區間，和某些係數，來描述此函數
- 尤拉猜想：
- $a_1^n+...+a_{n-1}^n\ne b^n~~~n\ge2$
- 是錯的，存在n=4, 5, 7的反例
- 
- 費馬最後定理：
- $x^n+y^n\ne z^n~~~n\ge3$
## 多邊形、多面體
- 針線販謎題：把正三角形切成四個多邊形，然後重新組合成正四邊形?
- 等分解(equidecomposition)
- 把兩個多面體(polytope)，切割成有限個兩兩全等(congruent)的多面體
- 等補貼(equicomplementation)
- 兩個多面體分別黏上有限個兩兩全等的多面體，使得黏好之後的兩個多面體擁有「等分解」.
- 二維多邊形
- 等分解 $\leftrightarrow$ 等補貼 $\leftrightarrow$ 等面積
- 三維多面體
- 
- 引理零 (月逆引理)
- $\begin{array}ABx\ge b\\~~~x\ge1\end{array}$
- 整係數有實數解 $\rightarrow$ 有有理數解
- 引理一 (錐體引理)
- $\begin{array}AAx=0\\~~~x>0\end{array}$
- 整係數有實數解 $\rightarrow$ 有整數解
- 引理二 (珍珠引理)
- 多面體PQ等分解：可以assign正整數到每一個segment使得一一對應
- 引理三 (夾角引理)
- 多面體PQ等分解：雙面角滿足
- 引理四 (只欠東風)
- $\frac{1}{\pi}arccos\frac{1}{\sqrt{3}}$ 是無理數
- 雙面角(dihederal angle)
- ：$\frac{\pi}{2}$
- ：$arccos\frac{1}{3}$
- ：$\frac{\pi}{2}*3~~~、~~~\frac{\pi}{4}*2~~~、~~~\frac{\pi}{3}*1$
- ：$arccos\frac{1}{\sqrt{3}}、~~~\frac{\pi}{2}$
## 塗色問題
- 
- chromatic number$\chi(G)$：至少要幾個顏色才夠
- $\chi(G)\le|V|$
- 雙色
- P問題
- 三色
- NP問題
- NP hard
- 四色
- 1976：平面圖必有$\chi(G)\le4$：電腦結果
- 六色
- n-m+r=2
- 1.數學歸納法
- 2.T的邊數n-1，T'的邊數r-1，總和為m
- 平面圖必有$\chi(G)\le6$
- n點的平面圖，必存在一點擁有$\le5$鄰居
- $m\le3n-6$
- $2m\le6n-12$
- By induction
- 五色
- 五色引理
- 
- 
- 五色定理
-