Thursday, December 29, 2005

決戰哥德巴赫~ 一條有限長度的 Recursive Sequence Part2

下面是我將 GoldBach Recursive Search 用數學方式表現出:
首先我們將所有正整數不包括2的奇質數收集起來, 記做 N(p)

Def.

Mp(n) = max {p∈N(p) :p≤n}

Mp(n,m) = max {p∈N(p) :p≤n and p/m}

Def.(GoldBach Recursive Relation)

Let C_i = P_i * K_i and P_i = Mp(n , C_i) = n-d_i , P_i ≠ 2

C_i+1 = P_i+2d_i = 2n-P_i = n+d_i

Def.

If {C_i} , {P_i} , {d_i} satisfy the GoldBach Recursive Relation we denote

(C_i , P_i , d_i) ~ G

上面所定義的是一個遞回型式的序列 , 我利用這個遞回的序列來逼進我們要找的哥德巴赫質數 p , q , 也就是給定我任意一個偶數 2n 並把它標在數線上 , 則n自然成為中間數 , 並將數線劃分為左右兩個區塊 , 左邊區塊為小於n的區域 , 右邊區塊為大於n的區域 , 上面提到 {P_i}的序列根據定義都將分布在左邊區塊 , 且必定是質數 , 並藉由與 n 等距的性質找出分布於右邊區塊的{C_i} , 且根據我的臆測必定會存在一個 C_i 必為質數 , 但這句話其實是相當需要考舊的 , 這句話的背後同時就是GoldBach Conjecture的精神所在 , 我將花很大的工程去說明這件事.......

首先針對GoldBach Recursive Sequence提出兩個簡單的性質 :

Lemma 1

If (C_i , P_i , d_i)~G and C_0=n ⇒ n C_i < 2n

Lemma 2

If (C_i , P_i , d_i)~G 且 P_i < P_j ⇔ C_i+1 < C_j+1

我當時在辦公室再Research 這個GoldBach Recursive Sequence時曾經寫下了一個小Remark , 敘述如下 :

Sequence {C_i} is not a infinitly sequence ?? Why ?? What condition of C_k such that there doesn't exist C_k+1 i.e. C_k is the last term

當初會這樣想 , 主要是擔心我的演算法在搜尋哥德巴赫質數時 , 會行程無窮回圈 , 也就是右邊區域的{C_i} 會重複出現 , 目前我還找不到反例 , 不過要特別說明 , 在邏輯上而言 , 我的GoldBach Recursive Sequence條件其實比原本GoldBach Conjecture還要強 , 也就是說 , 要是我的GoldBach Recursive 的搜尋質數方法對於所有偶數都成立 , 即可說明GoldBach Conjecture為真 , 但如果不幸我的演算法破功 , 也無法說明GoldBach Conjecture是錯誤的 , 然而要避免我的演算法再決戰歌德巴赫功虧一簣 , 我唯一的努力就是避免我的Gold Recursive Search 不會是無窮回圈 , 於是我提出一個猜想 , 這個猜想不是GoldBach Conjecture的等價猜想 , 姑且稱他為 "周氏猜想 " , 這會不會太自戀啦..........!!!

(Chou's Conjecture 2005 )

若 (C_i , P_i , d_i) ~ G ⇒ the length of {C_i} = k , for some nature number k< ∞

不過話說回來 , 提出猜想容易 , 解決猜想可就路途遙遠了 , 雖然這麼說 , 但我仍開始著手猜想的証明 , 不過我先簡單說明為何我的GoldBach Recursive Sequence可以成功證明GoldBach Conjectur

首先 , 我要先提出一個遞回序列的終止條件所產生的性質 , 這個終止條件並不是數學定義 , 而是一個需要證明的Condition

(Terminal Condition)

Assume (C_i , P_i , d_i)~G 若C_k∈N(p) ⇔ C_k+1 doesn't exit

Proof ~ 我們皆採用反證說明

(=>)

C_k∈N(p) but C_k+1 exists => C_k+1 = P_k + 2d_k

=> P_k = Mp(n , C_k)

=> P_k < n 且 P_k / C_k for C_k∈N(p)

=> C_k = P_k < n , contracdiction by Lemma 1

(<=)

若 C_k not belong to N(p) => C_k= P_k * K_k , P_k = M(n , C_k)

=> C_k+1 = P_k +2(n-P_k) = 2n-P_k

=> C_k+1 exists

接下來要說明為何我可以藉由我的猜想來證明GoldBach Conjecture:

Theorem ( Chou to GoldBach)

If (C_i , P_i , d_i)~G

=> for all even number 2n , n ≥ 3 , there must exist p , q ∈N(p) such that 2n=p+q

Proof

∀ n∈N , we set n= C_0

因為 (C_i , P_i , d_i)~G => the length of {C_i} = k , for some nature number k< ∞ (By Chou's Conjecture)

=> ∃k∈N s.t Ck+1 doesn't exit

=> Ck ∈ N(p) (By Terminal Condtion)

=> 2n-P_k-1 = Ck and 2n = C_k + P_k-1 for all n ≥ 3

we get two prime number p = C_k and q = P_k-1

說到這 , 我剩下的責任就是想辦法解決我自己提出的猜想 , 我剛剛說過 , 解決猜想的路是遙遠 , 但我已經開始利用建構式的方法開始著手我的証明 , 證明的過程真的出奇的繁複也相當困難 , 當中也用到著名數學大師Erdos的理論 , 也不確定是不是有其他的數論專家跟我有相同的想法 , 也不確定會不會真的出現讓人意想不到的反例 , 不論我的想法是否正確 , 至少我可以很榮幸的說:

我挑戰了哥德巴赫 !! 等我的好消息吧........^^

決戰哥德巴赫 - 一條有限長度的 Recursive Sequence


今年10月忙完中聯信託的案子 , 呼!! 終於可以鬆一口氣 , 因為我已經受夠每天在狹窄的資訊室 , 修改那些IBM 4758加解密程式 , 回到公司後除了比較輕鬆自在外 , 突然感到小小的無聊 , 想到上星期陳文瑞老兄來我家時 , 我對他提出在數論上存在一個類似線性代數的運算擴張 , 他竟然無動於衷 , 還反問我你這個運算擴張可以做什麼!? 有辦法解決 GoldBach Conjecture 嗎!? 喔喔!! 他刺激到我 , GoldBach 雖然名列希爾伯特第八個問題 , 但我覺得他應該是最可能被解決的問題 , 只是沒想到我當兵的時候 , 第十個 Poincaré Conjecture 竟然先被KO (是第十嗎!? 忘了) , 所以我決定在公司拿哥德巴赫來打發時間並慰勞我的辛勞 , 哥德巴赫猜想解決方式可以說千奇百怪都有 , 每年都有將近十來人聲稱自己經解決哥德巴赫 , 但通通出局 , GoldBach的問題之所以艱深 , 除了質數本身不具規律的性質外 , 重點就是代數結構鮮少處理在跨運算下未呈現封閉(close)特性的結構 , 這個問題目前最成功的是中國著名的解析數論專家陳景潤的 "1+2" , 數學界號稱陳景潤在高德巴赫猜想的成就只差將腳跨過巨峰山頂 , 他的在中國知名度決對不在陳省身之下 , 就連續劇都有他的腳本 , 就可見不是普通的紅 , 先說一下該問題的敘述 :

For all even number 2n , n ≥2 then there must exit two prime number p , q s.t. 2n=p+q

我給他一個等價敘述 :

For all even number 2n , n
≥2 then there must exit a number d s.t. n-d and n+d are both prime numbers

改成這個敘述其實難度是一樣 , 但卻提供給我們另外一個解決這個問題的角度 , 我花了一些時間再解決這問題上提出一個想法 :

任意給我一個偶數 2n , 我都可以透過一個極具規律的演算法 , 找到那個 p 及 q

當然 , 這個想法不是我第一個 , 我之前就在美國的 MathForum 看到有人在想 , 如何去Search 這兩個神祕的Prime Number , 但似乎一直沒有太多的後續結果 , 沒錯!! 我在拿幾個偶數分析後 , 配合我對GoldBach 的等價敘述 , 我想到一個給我任意偶數 , 我都可以透過該演算法輕鬆找到這兩個相加的質數 , 這個演算法背後所呈現是一個 Recursive Sequence , 我姑且稱他為 GoldBach Sequence , 演算法敘述如下 :

GoldBach Recursive Search:

Input : Any even number 2n
Output: two prime number p and q s.t p+q = 2n

1. 先判斷 n 是否為質數 , 如果是 , 找到 p = q = n , 結束
2. 若不是 , 找比n小的最大質數 P0 and we caculate d0 = n-P0
3. Caculate C1= n+d0 , and verify C1 是否為質數 , 如果是 , 找到 p=P0 , q=C1
4. 若不是 , 找整除C1且比n小的最大質數 P1 and we caculate d1 = n-P1
5.
Caculate C2= n+d1 , and verify C2 是否為質數 , 如果是 , 找到 p=P1 , q=C2
6. 若不是 , 再找整除C2且比n小的最大質數 P2 並繼續重複4及5的步驟..........沒錯!! 最終你會找到那兩個神祕的 p 及 q


舉個例子吧:
如何將 56 拆成兩個質數相加

56 -> 28 -> 23 -> 33 -> 11 -> 45 -> 5 -> 51 -> 17 -> 39 -> 13 -> 43

So 56 = 13 + 43

我最大曾經拆解 10000 這麼大的數字都正確無誤 , 但我知道 , 這在數論仍只是區區一個小數字而已.....


這演算法聽起來還挺簡單的 , 小學生都可以下去算 , 不過演算法的難度我可以提早宣告 , 幾乎篤定又是一個Exponetial Time 的複雜度 , 關鍵在於當數字越大時你要做直因數分解難度越高 , 但GoldBach Recursive Search 要拿來解釋GoldBach Conjecture的正確性 , 其實還隱藏許多問題 , 第一個直覺就是 :

憑什麼對於任意偶數 , 都可以透過
GoldBach Recursive Search找到 p 及 q , 也就是會不會有一個偶數會讓該演算法行成無窮回圈 !?

既然要直接面對世紀難題GoldBach 的挑戰 , 看樣子我們又要進入數學 , 接下來我要用數學來表示 , 是否會存在一個 Finite Length GoldBach Recursive Sequence ?


(待續)





Wednesday, December 28, 2005

麻省理工學院開放式網頁~本人大作發佈囉!!

我在MIT Open Course Ware 的第一部課堂中譯大作 Publish
( http://www.twocw.net/mit/Electrical-Engineering-and-Computer-Science/6-441Transmission-of-InformationSpring2003/CourseHome/index.htm) ,
雖然只是First Step 的翻譯 , 但看到我的大名能跟MIT聯在一起 , 還是要給他小小的興奮 , 這次主要翻譯以著名數學家 Shanon 在資訊傳輸領域的課程 , Information Theory 也是我本人再中研院資訊所攻讀的一門 , MIT開這門課的教授也是一個華人 , 不錯不錯 , 還蠻有緣的 , 不過 , 這裡不得不說 , 對朱學恆辛苦經營麻省理工學院開放式網頁 , 本人深感敬佩 , 最近 , 有幾門課程翻譯好久沒著手 , 對朱站長真的不好意思 , 希望各位從事科學研究工作者都能參予 MIT Open Course Ware !!

寶石方塊與圖的著色理論 3 ~ Conjucture and More Extension




回到寶石方塊的問題 , 我在沒有足夠的證據下 , 提出下列疑問

If G is a Grid Graph n x n' and m < max{n , n'} => XS(G , P3) = ??


我目前已知 :

若 G is Grid Graph 8 x 7 則 XS(G, P3) 7 (請參考右圖)
但我有一個關於 m-coloring for Pn 的直觀看法的猜想
X(G,Pn)
X(G,Pm) for n > m



上面這個敘述是不是更可以推廣到如下

If H' is the subgraph of H then X(G,H) X(G,H')

看似合理的推測 , 但要是問我為什麼 , 我大概用一句話回答
"
在越大的子圖產生不會完全同色的情形 , 則自然需要越少的顏色來區分 , 因為我們只需其中一點塗不同色 , 也就是你越可容許更多相同顏色的點佈滿在該越大的子圖其餘點上"
但我相信這需要嚴謹且繁複的証明 , 在這只是漫談的Blog我就不贅述 , 不過或許各位會發現 , 我並沒有對更廣義的 X(G , H ) for H is a subgraph of G 去作定義 , 我在上一篇的那一連串定義只是H=Pn 的情形主要是為了解決寶石方陣在P_3的情形 , 廢話不多說 , 立刻給一個更廣義的著色理論數學定義 :


Def. Π(H) : V(H) -> {0 , 1}

Π(H)d(x,y)=1 δ(x , y) 註:這是連乘

Def. (Coloring Extension to any subgraph H) C(G,H): V(G) -> N={0 , 1 , 2 ...m-1} is a m-coloring for H in G satisfying as follow: for all subgraph H ⊆ G 則 Π(u,v) = 0 and we denote the |C(G,H)| =m

Def. (Chromatic Number For Coloring Extension to any subgraph H) 我們把在Pn子圖上不能同時同色推廣至任意子圖上 ,
X(G , Pn) = min { |C(G,H)| = m | C(G,H) is a m-coloring for H in G}


舉個例子:

G=K4 , H = C3

則 X(K4 , C3) = 2 著色方式如上方小圖 , 圖中任意C3 subgraph 都不會同時塗相同顏色

附帶一提 , 將著色問題推廣至所有子圖 , 並非空穴來風 , 起因我最近思考的MIMO通訊問題中有關發收訊號群如何將他們的出現機率最大的雜訊做最離散的分布!!

嗯....問題敘述到此 , 我可以想像 , 會不會有個數學高手跳出來只著我的鼻子說 : "你真夠愚蠢 !! 難道你看不出來嗎 ? 這個問題有什麼好談的 , 因為它的難度是跟原本一般的Chromatic Number著色問題難度相同 , 懂不懂呀 !! 外行人......"

(複雜度猜想)~~~~~~~~~
OK !! 為了避免淪落成"外行人" , 即使本老爺的部落格也應該沒多少台灣數學好手會觀賞 , 但我還是先來個防禦性猜想吧

Computation Complexity of X(G,H) = Computation Complexity of X(G,P2) !?

沒錯!!要是有演算法分析的高手可以透過問題轉嫁的方式來說明上述這句話為真 , 真的要給她拍拍手 , 但拍拍手之外還不要高興太早 , 不要忘了 X(G,P2)就是原本一般兩點相連不同色的問題 , 在沒有特定的圖之下 , 已經被證實是NP-Complete , 哀哉呀!! 但我仍堅信 , 考慮Swap這個動作~XS(G,Pn) , 也就是我原本對寶石方陣的問題 , 絕對是相當相當困難的 , 我至今對他沒有太多想法...........

寶石方塊與圖的著色理論2~從數學定義開始

Def. Pn(G) = { (u,v) 存在 a length n-1 path connect u and v in G}

Def. Pn(u,v) = { (u=x_1 , x_2 , ... , v=x_n) (u,v) in Pn(G) and d(x_i , x_i+1) = 1 , i=1,2 ... n-1}

Def. C : V(G) -> N is a coloring function on vetex of G , N is natural number

Def.
δ : V x V -> {0,1}
δ(x_i , x_j) = 0 if C(x_i)
≠ C(x_j)
δ(x_i , x_j) = 1 if C(x_i) = C(x_j
)

Def. Π(u,v) :
Pn(u,v) -> {0 , 1}

Π(u,v) =Πi=1 ,2,...n-1 δ(x_i , x_i+1) 註:這是連乘

Def. (Coloring Extension)

C(G,Pn): V(G) -> N={0 , 1 , 2 ...m-1} is a m-coloring for Pn in G satisfying as follow:

for all (u,v) in Pn(G) 則 Π
(u,v) = 0 and we denote the C(G,Pn)= m

Def. (Chromatic Number For Coloring Extension)

X(G , Pn) = min { |C(G,Pn)| = m | C(G,Pn) is a m-coloring for Pn in G}

把上述一連串定義中的 n = 2 就是我們最原始兩點相連不同色的著色問題 , 至於寶石方陣的著色問題是建立在 n=3 且 G = Grid Graph with 8 x 8
Remark:
1. G is a Grid Graph with n x n X(G, P_3) = 2
2. G is a Cyclic Graph Cn X(Cn, P_3) = 2
3. G is a Kn X(Kn, P_3) = n/2 的上高斯 (why!? Because every color can't exceed 2)

在來重點是我要用數學定義 Swap 這個動作 :
Def. C* is a set that collect all coloring function C on V(G) we denote
C*={ C | C : V(G)-> N }
C*(G,Pn) is a set that collect all m-coloring for Pn in G we denote
C*(G,Pn) = { C(G,Pn)| C(G,Pn) : V(G) -> N }
註 : 很明顯 C*(G,Pn) is a subset of C*

Def. ( A Swap transform between two coloring function in G) We define a swap transform S : (C*, V(G) , V(G)) -> C* S(C_1 , a , b )= C_2 such that
C_2(x)=C_1(x) if x≠a and x≠b
C_2(x)=C_1(b) if x=a
C_2(x)=C_1(a) if x=b
現在將Swap的動作加入我們原本考慮的 m-coloring for Pn in G , 我要再定義一個變形的Chromatic Number with Swap Operator

Def. XS(G , Pn ) = min { |C(G,Pn)| | S( C(G,Pn) , a , b ) always lie in C*(G,Pn) for all (a,b) ∈ E(G) }

(待續)





Tuesday, December 27, 2005

寶石方塊與圖的著色理論

從11月的某個星期六下午開始 , 我跟宜伶表妹兩人展開寶石方塊的大車拼 , 哈哈 , 不過終究是自己家裡的電腦 , 六十五萬分的最高分目前仍是本老爺打出來 , 不過表妹的63萬分可以說緊追在後
下面是該遊戲網址:
http://reflexive.net/index.php?PAGE=game_detail&AID=394&CID=21443
在 接觸這個遊戲時 , 我第一個想到的問題就是 , 在每次的消去後 , 隨機掉落的方塊有沒有可能讓我的下一步變成無解 , 也就是我無法再Swap任兩個方塊達成消去效果 , 要贏得寶石方塊的遊戲 , 我必須解決我這個疑惑 , 先說明該遊戲規則是 : 每次只能對調兩方塊 , 當三個直或橫相連且顏色相同的寶石會立即消除 , 我沒有太多的想法可以立即解答我這個問題 , 但我直覺反應就是 , 即時有機率也極低 , 甚至我可以大膽推論就是"沒有" , 不過 , 我表妹跟我說她在玩MSN的寶石方塊時有碰過無法消除的狀況 , 真的嗎!? OK!! Anyway , 是否會存在無法消除的寶石方陣 , 這牽扯到兩個變數 , 一個是該寶石方陣的 Size , 以Reflexive 的 Bejewled 2 遊戲來講 , 是8*8的方陣 , 第二個就是該方塊的顏色種類 , 以該遊戲(Bejewled 2)來看 , 我數過是7種顏色 , 所以 , 現在的問題用通俗的語言來問:

N x N 的方陣中用 N-1 種方塊去填它 , 則永遠都存在可經Swap後消去的解

這 句話還沒用數學去公理化它但已十足的非常咬文爵字 , 所以在看本篇文章的數學同好 , 建議先去Reflexive下載該寶石方塊的遊戲來玩玩 , 不過我可沒有在幫該網站打廣告 , 現在回到上述這個問題 , 我要提出一個 Capacity 或是 Threshold的概念 ,

是否永遠存在可經Swap而消去的N x N的方陣的寶石方塊種類的最大值為 N-1 !?

換個角度說 :

是否對於所有 M>N-1 , 則必定會存在一個無法經Swap而消去的 N x N 方陣 with M種寶石 entry !?

這問題的猜想是否正確 , 可以先從小例子出發 , 首先 , 我們簡稱永遠都會有可經由Swap而消去的方陣為 eliminatable square :

考慮 N=3 的方陣 , 該方陣在填入M種寶石後 , 則仍是eliminatable square的M最大值為何 ??

YA!! M= 2 , Why !? Obviously , Because 動手用兩個數字填 3 x 3 的方陣 , 暴力法也只需要
2^9=512種 , But 如何確定 M=3的時候會破功 , 也就是會存在經由倆倆Swap後仍然無法eliminate的方陣 , 有呀 , 下面這就是一例 :

0 0 1
0 0 1
1 2 2

不過 , 當初再思考這問題時 , 我曾經考慮下面這個例子是否符合我現在該遊戲面臨的問題

0 0 1
0 0 1
0 0 1

該例子很明顯經由倆倆Swap後決對無法產生可消去的方塊 , 但這例子是不成立的 , 因為我們必須對我們討論的方陣加一個條件就是 :

該方陣本身沒有連續三個相同數字相連(不論直或橫來看)

從上面這個敘述開始 , 我發現我面臨的也許是在組合數學領與中相當有名的 "著色問題" 的變形 ,
更精準來說 , 應該是傳統著色理論的極大推廣並再變形處理 , 為什麼說是推廣 ? 因為之前處理圖著色問題都是在"兩個Vertex之間的Relation"給予某特條件 , 簡單來說 , 我現在有 "連續相連的三點需不能同時著相同顏色" , 注意喔 , 這句話是指"不能同時" , 也就是相連三點中至少需存在一點
顏色要不相同例如:

100 , 010 , 001 , 011 , 101 , 110

於是決定廢話不多說 , 我在沒有相關文獻的支援下, 我要給一個著色理論的定義推廣來數學公理化寶石方陣問題 :

(待續)