發刊日期 |
2021年6月
|
||
---|---|---|---|
標題 | 格子圖形中的格子直線數 |
||
作者 | |||
關鍵字 | |||
檔案下載 | |||
全文 |
在 $k$ 維空間中, 由 $k$ 個整數為坐標的點 $(x_1,x_2,\ldots,x_k)$ 稱為格子點。 以格子點為頂點的圖形稱為格子圖形。 皮克 (Pick, 1859$\sim$1942) 在 1899 年提出一個計算格子單純多邊形 (simple polygon) 的面積公式, 這公式僅需要知道多邊形中邊上及內部格子點的個數就可算出面積, 這是一個簡單又實用的計數方式。 本文選定某些特定格子圖形作探討, 計算通過特定格子圖形內所有點所需的格子直線之個數, 此個數簡稱格子直線數。 注意本文所談的格子直線必過原點 $O$ 且過非原點的格子點所成的連線。 首先選定特定格子圖形是平面上的格子三角形, 計算格子直線數中, 進而探究出歐拉函數 (totient function) 的恆等式 (異於 \eqref{1} 式的式子)。 為了推廣, 將歐拉函數記作 $\varphi_1(n)$, 其中 $\varphi_1(n)$ 表示為不大於 $n$ 且與 $n$ 互質的正整數個數且 $\varphi_1(1)=1$, 而歐拉函數 $\varphi_1(n)$ 的推廣為喬丹函數 (Jordan's totient function), 記作 $\varphi_k(n)$, 即 \begin{align} \varphi_k(n)=n^k\Big(1-\frac 1{p_1^k}\Big)\Big(1-\frac 1{p_2^k}\Big)\cdots \Big(1-\frac 1{p_m^k}\Big),\ \hbox{其中 }\ \varphi_k(1)=1,\label{1} \end{align} $p_1,\ldots, p_k$ 為質因數。 注意 \eqref{1} 式中 $k=1$ 時, 指常見的歐拉函數 $\varphi_1(n)$。 本文遵循歐拉函數出發與類推, 再配合平面至空間類推概念, 首先選定平面上的格子正方形及空間中的格子立方體來同步探究, 逐步發現其一般的規律, 因而擴充得到格子 $k$--超立方體 ($k$-hypercube) 的喬丹函數之恆等式, 驚喜地推導出兩個恆等式。 從選定某些特定圖形中, 配合特例, 進而發現規律到一般化的論證過程, 都富有創造性的思考啟發性, 值得追根究柢。 1. 歐拉函數的恆等式甲、問題探原歐氏幾何告訴我們 「相異兩點決定一直線」, 由於同一條格子直線上有無限多個非原點的格子點型如: $(x_1,x_2,\ldots,x_k),(2x_1,2x_2,\ldots,2x_k),\ldots,(dx_1,dx_2,\ldots,dx_k)$, 其中 $d$ 為正整數。 事實上, 此格子直線可由原點 $O$ 與非原點的格子點 $(x_1,x_2,\ldots,x_k)$ 所決定。 換言之, 所決定非原點的格子點為滿足 $\gcd(x_1,x_2,\ldots,x_k)=1$ 的格子點。 因此, 非原點的格子點滿足 $\gcd(x_1,x_2,\ldots,x_k)=1$ 的個數等於格子直線數。 例 1: 計算圖 1 中底與高皆為 3 的格子三角形中格子直線數為 $1+\displaystyle\sum_{i=1}^3 \varphi_1(i)$。 解答: 用描點法可知格子直線是由原點 $O$ 分別與格子點 $(1,0),(1,1),(2,1),(3,1),(3,2)$ 五點連線所決定, 所以格子直線數為 5。
我們不妨考慮將圖1中格子三角形之格子直線數以歐拉函數 $\varphi_1(n)$ 來表示, 這絕對可辦到的。 因為非原點的格子點滿足 $\gcd(x_1,x_2,\ldots,x_k)=1$ 的個數等於格子直線數, 而 $\gcd(x_1,x_2)$ $=1$ 這概念正符合歐拉函數, 建構方式是將非原點的格子點用直線 $x=i$ 上來區分 $(i=1,2,3)$, 分成三類:
因此, 由 (i)$\sim$(iii) 知底與高皆為 3 的格子三角形中的格子直線數為 $$\varphi_0(1)+\varphi_1(1)+\varphi_1 \eqref{2} +\varphi_1(3)=1+\sum_{i=1}^3\varphi_1(i)\hbox{。}\Box$$ 由例 1 給我們二個啟發:
當然將格子點 $(n,t)$ 改為 $(t,n)$ 也成立。 同理, 推廣至 當然將格子點 $(n,n,n,\ldots,t)$ 改為 $(n,n,\ldots,t,n)$、 $\cdots$、 $(t,n,n,\ldots,n)$ 均成立。 乙、計數格子直線數給定圖 1 中的格子三角形一般定義: 定義 1: 在平面上, 滿足 $0\le x_2\le x_1\le n$ 的所有格子點所成的集合, 稱為底與高皆為 $n$ 的格子三角形, 記作 $S([0,n]^2)$, 參見圖 1 中格子三角形 $S([0,3]^2)$。 令 $a_2(n)$ 表示過原點且過在 $S([0,n]^2)$ 中非原點的格子點之格子直線數。
例 1 中想用歐拉函數來協助計算格子直線數, 於是定義在 $S([0,n]^2)$ 而不在 $S([0,n-1]^2)$ 滿足 $\gcd(x_1,x_2)=1$ 的格子點稱為新增格子點, 連接原點 $O$ 與新增格子點的直線稱為新增格子直線, 即新增格子直線數為 $a_2(n)-a_2(n-1)$。 又從例 1 中得知 $a_2(n)-a_2(n-1)=\varphi_1(n)$, 參見圖 2, 即 \begin{align} a_2(n)=a_2(n-1)+\varphi_1(n),\ \hbox{其中}\ \varphi_1(1)=1\hbox{。}\label{2} \end{align} 如此一來, 歐拉函數 $\varphi_1(n)$ 可視為 $S([0,n]^2)$ 而不在 $S([0,n-1]^2)$ 的新增格子點之個數。 同樣地, 當後面計算在格子 $k$-超立方體中的格子直線數也是類推如 \eqref{2} 式的遞迴關係來協助計數。 定理 1: (計算在格子三角形中的格子直線數) 設 $a_2(n)$ 為在格子三角形 $S([0,n]^2)$ 中的格子直線數, 則 $a_2(n)=1+\sum\limits_{i=1}^n\varphi_1(i)$。 證明: 由 \eqref{2} 式知 $a_2(n)=a_2(n-1)+\varphi_1(n)$。 由遞迴關係可求得 $$a_2(n)=a_2(1)+\varphi_1(2)+\varphi_1(3)+\cdots+\varphi_1(n)\hbox{。}$$ 又 $a_2(1)=2$, $\varphi_1(1)=1$ 所以 $$a_2(n)=1+(\varphi_1(1)+\varphi_1(2)+\cdots +\varphi_1(n))=1+\sum_{i=1}^n\varphi_1(i)\hbox{。}\Box$$ 2. 喬丹函數的恆等式甲、推導恆等式 (I)前面推導歐拉函數 $\varphi_1(n)$ 的恆等式是針對滿足 $\gcd(n,t)=1$ 的格子點個數, 其中 $t=1,2,3,\ldots,n$。 根據平面至空間類推概念, 可猜測喬丹函數 $\varphi_k(n)$ 的恆等式也可針對滿足 $\gcd(x_1,x_2,\ldots,x_k,n)=1$ 的格子點 $(x_1,x_2,\ldots,x_k)$ 個數, 不妨採用格子正方形及格子立方體來思考是否可推導出 $\varphi_2(n)$ 與 $\varphi_3(n)$, 然而其推廣圖形即格子 $k$-超立方體, 定義為 定義 2: 在 $k$ 維空間中, 若滿足 $m\le x_i\le n$ $(i=1,2,\ldots,k)$ 的所有格子點形成的集合, 記為 $[m,n]^k$, 其中 $m,n$ 為整數。 當 $m=0$, $n\gt 0$ 時, 則 $[0,n]^k$ 是一個邊長為 $n$ 的格子 $k$-超立方體 ($k$-hypercube), 含有 $(n+1)^k$ 個格子點, 參見圖 3 與圖 4。 當 $n=0$ 時, 則 $[0,n]^k$ 恰含一個唯一的格子點, 就是原點 $O(0,0,\ldots,0)$。
我們可以考慮 $[1,n]^k$ 或 $[0,n-1]^k$, 底下就先從 $[1,n]^k$ 著手, 先觀察兩個特例。 例 2: 計算在 $[1,4]^2$ 中滿足 $\gcd(x_1,x_2,4)=1$ 的格子點 $(x_1,x_2)$ 個數為 $\varphi_2(4)$。 解答: 由定義 2 知 $[1,4]^2$ 中含有 16 個格子點, 但若要滿足 $\gcd(x_1,x_2,4)=1$ 的格子點, 必須刪掉四個格子點 (2,2), (2,4), (4,2), (4,4), 所以得到 12 個格子點, 參見圖 3。 又 $\varphi_2(4)=4^2\Big(1-\dfrac{1}{2^2}\Big)=12$, 故這樣的格子點個數剛好等於 $\varphi_2(4)$。$\Box$ 例 3: 計算在 $[1,2]^3$ 中滿足 $\gcd(x_1,x_2,x_3,2)=1$ 的格子點 $(x_1,x_2,x_3)$ 個數為 $\varphi_3(2)$。 解答: 由定義 2 知 $[1,2]^3$ 中含有 8 個格子點, 但若要滿足 $\gcd(x_1,x_2,x_3,2)=1$ 的格子點, 必須刪掉格子點 (2,2,2), 所以得到 7 個格子點, 參見圖 5。 又 $\varphi_3(2)=2^3\Big(1-\dfrac{1}{2^2}\Big)=7$, 故這樣的格子點個數剛好等於 $\varphi_3(2)$。 $\Box$
由例 2 與例 3 中可推測知喬丹函數 $\varphi_k(n)$ 表示在格子 $k$-超立方體 $[1,n]^k$ 中滿足 $\gcd(x_1,x_2,\ldots,x_k,n)=1$的格子點 $(x_1,x_2,\ldots,x_k)$ 的個數。 特別是 $[1,1]^k$ 含 1 個格子點, 不難看出 $\varphi_k(1)=1$, 當 $n\gt 1$, 則有定理 2。 定理 2: (喬丹函數的恆等式 (I)) 設 $n$ 的標準分解式為 $n\!=\!p_1^{a_1}\cdot p_2^{a_2}\cdots p_m^{a_m}$, 其中 $p_1,p_2,\ldots,p_m$ 為相異質數且 $\alpha_1,\alpha_2,\ldots,\alpha_m\in N$, 若 $\varphi_k(n)$ 為 $k$-超立方體 $[1,n]^k$ 中滿足 $\gcd(x_1,x_2,\ldots,x_k,n)=1$ 的格子點 $(x_1,x_2,\ldots,x_k)$ 的個數, 則 $$\varphi_k(n)=n^k\Big(1-\frac{1}{p_1^k}\Big)\Big(1-\frac{1}{p_2^k}\Big)\cdots\Big(1-\frac{1}{p_m^k}\Big),\ \hbox{ 其中} \ \varphi_k=1\hbox{。}$$
證明:
底下就來證明 $n\gt 1$ 的情形。
若 $d$ 為 $n$ 的正因數, 令 $M_d$ 是在 $[1,n]^k$ 中滿足坐標 $x_1,x_2,\ldots,x_k$ 都是 $d$ 的倍數的格子點
$(x_1,x_2,\ldots,x_k)$ 所成的集合。 乙、推導恆等式 (II)現在從 $[0,n-1]^k$ 中推導喬丹函數的第二個恆等式, 先觀察一個特例: 例 4: 計算在 $[0,3]^2$ 中滿足 $\gcd(x_1,x_2,4)=1$ 的格子點 $(x_1,x_2)$ 個數為 $\varphi_2(4)$。
解答: 考慮 $[1,4]^2$ 與 $[0,3]^2$ 中不重疊的格子點 $(x_1,x_2)$, 參見圖 6, 在 $[1,4]^2$ 中為 $\overline{AB}$ 與 $\overline{BC}$ 上的格子點, 而在 $[0,3]^2$ 中為 $\overline{OQ}$ 與 $\overline{OP}$ 上的格子點。 由於 $OP\equiv n(\hbox{mod}\, n)$, 所以 $[1,4]^2$ 中 $\overline{AB}$ 與 $\overline{BC}$ 上滿足 $\gcd(x_1,x_2,4)=1$ 的格子點 $(x_1,x_2)$ 分別對應 $\overline{OQ}$ 與 $\overline{OP}$ 上滿足 $\gcd(x_1,x_2,4)=1$ 的格子點 $(x_1,x_2)$, 所以在 $[1,4]^2$ 中滿足 $\gcd(x_1,x_2,4)=1$ 的格子點 $(x_1,x_2)$ 個數等於在 $[0,3]^2$ 中滿足 $\gcd(x_1,x_2,4)=1$ 的格子點 $(x_1,x_2)$ 個數, 因此, 由定理 2 知在 $[0,3]^2$ 中滿足 $\gcd(x_1,x_2,4)=1$ 的格子 點 $(x_1,x_2)$ 個數為 $\varphi_2(4)$。 由例 4 可推論出$k$-超立方體 $[0,n-1]^k$ 中 $\gcd(x_1,x_2,\ldots,x_k,n)=1$ 的格子點個數為 $\varphi_k(n)$, 為了區別證明, 將 $[0,n-1]^k$ 中 $\gcd(x_1,x_2,\ldots,x_k,n)=1$ 的格子點個數記作 $\varphi_k^*(n)$, 於是 $\varphi_k^*(n)=\varphi_k(n)$。 定理 3:(喬丹函數的恆等式 (II)) 設 $\varphi_k^*(n)$ 為 $k$-超立方體 $[0,n-1]^k$ 中 $\gcd(x_1,x_2,\ldots,x_k,n)$ $=1$ 的格子點 $(x_1,x_2,\ldots,x_k)$ 的個數, 則 $\varphi_k^*(n)=\varphi_k(n)$, 其中 $\varphi_k(1)=1$ 及 $\varphi_0^*(n)=\left\{\begin{array}{ccc} 1,&~&\hbox{當}\ n=1\\ 0,&~&\hbox{當}\ n\not=1\end{array}\right.$。 證明: 當 $n=1$ 時, $[0,n-1]^k$ 恰含唯一的格子點, 即原點 $O=(0,0,\ldots,0)$。 又 $\gcd(0,\ldots,0$, $1)=1$, 所以 $\varphi_0^*(1)=1$。 當 $n\not=1$ 時, $\gcd(0,\ldots,0,1)\not=1$, 所以 $\varphi_0^*(n)=0$。 其餘的情形仿照定理 2來證明。 將定理 2 中 $\Big\{1d,2d,\ldots,\Big(\dfrac nd\Big)d\Big\}$ 以 $\Big\{0,1d,2d,\ldots,\Big(\dfrac nd-1\Big)d\Big\}$ 取代, 並討論之, 同時也可以得到 $\varphi_k(n)$ 也是在 $[0,n-1]^k$ 中滿足條件 $\gcd(0,\ldots,0,1)=1$ 的格子點個數。$\Box$ 3. 計數格子直線數現在要採用喬丹函數來計算在 $[0,n]^k$ 中的格子直線數, 於是令 $b_k(n)$ 表示過原點且過在 $[0,n]^k$ 中非原點的格子點之格子直線數。 定義在 $[0,n]^k$ 而不在 $[0,n-1]^k$ 滿足 $\gcd(x_1,x_2)=1$ 的格子點稱為新增格子點, 連接原點 $O$ 與新增格子點的直線稱為 新增格子直線, 即新增格子直線數為 $b_k(n)-b_k(n-1)$。 \eqref{2} 式談到新增格子直線數 $a_2(n)-a_2(n-1)=\varphi_1(n)$, 但此時 新增格子直線數 $b_k(n)-b_k(n-1)\not=\varphi_k^*(n)$。 這乃是類推至高階的妙趣所在, 就從一個特例一看究竟。 例 5: 計算在 $[0,n]^2$ 中的格子直線數為 $b_2(n)=3+C_1^2\displaystyle\sum_{i=2}^n\varphi_1^*(i)$。 解答: 顯然在 $[0,1]^2$ 中但不在 $[0,0]^2$ 的新增格子直線數為 $2^2-1$, 即 $b_2(1)=3$。
由圖 7 知新增格子點落在線段 $\overline{AB}$ 與 $\overline{BC}$ 上的格子點, 這些格子點型如: $(t,n)$ 及 $(n,t)$ 等二種情形, 其中 $0\le t\le n$。 又每種滿足 $\gcd(t,n)=1$ 的格子點個數等於 $\varphi_1^*(n)$, 所以 $$b_2(n)-b_2(n-1)=2\varphi_1^*(n) ,\ \hbox{即}\ b_2(n)=b_2(n-1)+2\varphi_1^*(n)\hbox{。}$$ 由遞迴關係可求得 $$b_2(n)=b_2(1)+2(\varphi_1^*(2)+\varphi_1^*(3)+\cdots+\varphi_1^*(n))\hbox{。}$$ 又 $b_2(1)=3$, 因此, $$b_2(n)=3+2\sum_{i=2}^n\varphi_1^*(i),\ \hbox{方便推廣寫成}\ b_2(n)=3+C_1^2\sum_{i=2}^n\varphi_1^*(i)\hbox{。}\Box$$ 底下要計數在 $[0,n]^3$ 中的格子直線數, 仿照例 5 的推導方式。 定理 4: (計算在 $[0,n]^3$ 中的格子直線數) 設 $b_3(n)$ 為在 $[0,n]^3$ 中的格子直線數, 則 $$b_3(n)=7+\displaystyle\sum_{j=1}^2\sum_{i=2}^n C_j^3\varphi_j^*(i)\hbox{。}$$ 證明: 顯然在 $[0,1]^3$ 中但不在 $[0,0]^3$ 的新增格子直線數為 $2^3-1$, 即 $b_3(1)=7$。 底下 $n\ge 2$ 的情形, 欲求新增格子直線數 $b_3(n)-b_3(n-1)$, 即求新增格子點數。 由圖 8 知新增格子點落在平面 $DEFG$、 $ABFE$ 與 $BCGF$ 上的格子點 $(x_1,x_2,x_3)$, 將 $x_1,x_2,x_3$ 排序 $x_{(3)}\le x_{(2)}\le x_{(1)}=n$ 分成互斥 2 類:
由 (i) 與 (ii) 知故 $b_3(n)-b_3(n-1)=C_1^3\varphi_1^*(n)+C_2^3\varphi_2^*(n)$, 即 $$b_3(n)=b_3(n-1)+\sum_{j=1}^2C_j^3\varphi_j^*(n)\hbox{。}$$ 由遞迴關係可求得 $$b_3(n)=b_3(1)+\sum_{j=1}^2C_j^3\varphi_j^*(2)+\sum_{j=1}^2C_j^3\varphi_j^*(3)+\cdots+\sum_{j=1}^2C_j^3\varphi_j^*(n)\hbox{。}$$ 又 $b_3(1)=2^3-1=7$, 因此, $b_3(n)=7+\sum\limits_{j=1}^2\sum\limits_{i=2}^nC_j^3\varphi_j^*(i)$。 $\Box$ 仿照定理 4 推廣至 $k$ 維, 同樣地可用 $\varphi_1^*(n),\varphi_2^*(n),\ldots,\varphi_{k-1}^*(n)$ 來計數格子直線數 $b_k(n)$, 參見定理 5。 定理 5: (計算在 $[0,n]^k$ 中的格子直線數) 設 $b_k(n)$ 為在 $[0,n]^k$ 中的格子直線數, 則 $$b_k(n)=(2^k-1)+\sum_{j=1}^{k-1}\sum_{i=2}^nC_j^k\varphi_j^*(i)\hbox{。}$$ 特別的, 考慮 0 維的情形, 可將式子再改寫成 $b_k(n)=\sum\limits_{j=0}^{k-1}\sum\limits_{i=1}^nC_j^k\varphi_j^*(i)$。 4. 結語本文探討某特定格子圖形中過原點的格子點的直線數, 若計數不採新增格子點方式來看, 相當困難的, 於是為了克服計算部分, 不停地在數量上做些改變, 驚喜地得到了喬丹函數的二個恆等式, 因而在計數上化繁為簡。 這裡探究過程中正符合是古希臘哲學家蘇格拉底所採用的 「產婆法」--知識是一種「發現」, 強調「引出」、 「誘發」, 從解決「計算格子直線數」這單純問題, 建構一套合理的論述, 再由數學概念理解發展至理論化, 驚喜開拓了喬丹函數的數學世界, 也享受開啟數學知識的喜悅。 此外, 若配合由平面上格子三角形類推空間中格子三角錐來聯想, 理論上還可以擴充至格子 $k$-單體 (simplex), 這圖形內格子點較特殊, 將成另一篇文章展 現, 敬請期待, 有興趣讀者, 不妨試一試。 數學家拉普拉斯 (Laplace, 1749$\sim$1827) 說: 讀 Euler, 讀 Euler, 他是我們全能的大師。 Read Euler, read Euler, he is the master of us all. 有人將歐拉比擬為數學界的莎士比亞 (the Shakespeare of Mathematics): 普世性, 鉅細靡遺, 取之不盡, 用之不竭。 Universal, richly detailed, and inexhaustible. 可見歐拉活在的每個數學角落裡, 他提出的數學創作值得我們永恆地拜讀, 甚至使之美麗。 本文是指導范同學參賽 2017 年台灣區國際科展作品 : 「格子直線數與歐拉函數之探討與推廣」, 提及在特定格子圖形中利用喬丹函數來計算格子直線數, 這是一個美妙的發想。 有感指導參賽作品內容複雜且難以閱讀, 於是改寫參賽作品中最精髓部分將它描述清楚, 使成為更清晰可見的文章。 再者, 分享計數上一個不錯的結果, 也作為喬丹函數的應用範疇。 最後深深感謝審稿教授對此文章的指正與建議, 使本文有更好論述的標題及內容。 參考文獻---本文作者范谷瑜投稿時為清華大學數學系大四學生, 林鳳美任教於臺北市立成淵高級中學--- |