Polynomials and topology

Recently my friend is working on a problem in topology, and out of his work, it appears that the there is a special pattern in the coefficients of the following polynomial, when m,n are relatively prime:



It appears that if one expands this polynomial out, collects terms and arranges them in decreasing powers of x, then the non-zero coefficients are all either 1 and -1, and they appear to alternate as the power decreases. (e.g. when m=4, n=3, the polynomial is



It is not known whether this pattern really exists. But I thought this is cute and may be of interest to some of you. Does any of you have any idea about how to prove/disprove it?

(The case of interest in topology is when m > 3n, but it looks like this pattern persists as long as m,n are relatively prime.)

Elementary number theory

Someone say that 167588402882520529579353108764873470755823697 is the smallest positive integer k such that all digit of 1989k are the same.

Do you agree?

MD Academic Seminar

數學資料庫將於本月底舉行期待已久的 academic seminar！ 詳情如下：

日期：2009 年 12 月 27 日（星期日）
時間：下午 4 時 30 分至 5 時 30 分
地點：香港大學莊月明文娛中心 302 室
講者：樊偉堂先生（華盛頓大學數學系博士研究生）

=====================================================

Probability from a gambler's viewpoint --- A taste of Martingale Theory

Suppose you keep flipping a fair coin until 10 heads occur consecutively. How many times of flipping do you need on average?

We will solve this and other related problems as an application of the Optional Stopping Theorem. The basic notions and properties of discrete martingales will be introduced in an informal manner, with emphasis on the intuitive ideas.

Prerequisite: Basic probability in secondary school level.

Two Analysis Problems

Recently I heard two problems in analysis, both I think are interesting, and they do not require too deep knowledge in analysis, which is the kind of questions I like most. Share here.

1) Suppose converges. Also, for each positive integer k, it is known that (just to avoid confusion, allow me clarify here that jk means "j times k"). Prove that for all positive integers i.

2) S contains all elements such that for any , there exists a rational number (where p,q are positive integers) satisfying . Prove that S is uncountable.

香港大學「數趣漫話」講座

日期：2010 年 1 月 9 日（星期六）
時間：下午 2 時 30 分至 4 時
地點：香港大學明華綜合大樓 T1 演講廳
講者：李志光教授
講題：數學世界與武俠天地

---

簡介：

數學世界中有抽象的科研題目，有孜孜不倦的學者，有勤奮的學生；武俠天地裏有神奇的絕世武功，有鋤強扶弱的俠客，有堅毅的徒底。數學與武俠，兩者仿似風馬牛不相及，細看又似有不少共通之處。

講者將以其多年從事數學科研教學之經驗，剖析數學世界與武俠天地之異同，聽眾可以輕鬆地瞭解數理學者的工作和生活。

---

有關其他詳情，可瀏覽這裡。

培正數學邀請賽

數學資料庫協辦的「培正數學邀請賽 2010」將於 1 月 23 日（星期六）和 3 月 20 日（星期六）分別舉行初賽和決賽。學校報名的截止日期為 2009 年 12 月 5 日（星期五）。有興趣參賽的同學，可向就讀學校的數學老師查詢有關事宜。其他有關比賽的詳情，可瀏覽比賽網頁。

Log Is Everywhere

今日聽seminar時忽發奇想，不如在這裏玩一個遊戲（要大家參與的）。數學上有很多重要的函數，其中一個就是logarithm（這裏不管是、還是都可以）。這個函數涉及的範疇科目包括數學、物理、化學、計算機科學、各種工程學、天文學、金融等等。我想大家可以在這裏接力每人列三個logarithm出現的地方，看看可以去到幾長。

我先開始吧：

1)

2) 一種不穩定的物質進行radioactive decay。若它在k秒內質量由1變成，則該物質的half-year為秒

3) 絕大部分在現實使用將數字排序（sorting）的算法（algorithm），其運算時間為

------

規則：每人只可以列最多三個，但少一些是可以的（就是說你只想到一個，就列一個吧）。

UCLA Undergraduate Math Scholarship

廣告一則。

曾經參與國際數學奧林匹克（或其他國際性數學比賽）的中六至中七學生，可考慮申請UCLA以下獎學金：

http://terrytao.wordpress.com/2009/11/19/ucla-math-seeks-exceptional-student-for-undergraduate-merit-scholarship/

若有人知道有人適合申請，請代為通傳一下。

另，相信這個獎學金不是搞一年就算，所以符合條件的中四或中五學生亦可考慮下一/二年申請。

電子簽名…(上)

在這個訊息化的世代當中，相信你對 電郵、電子証書等等字眼也不會感到陌生。
往下閱讀前先來一個熱身吧。

(i) 在數碼世界中，到底有冇沒有電子郵票呢？

(ii) 一張証書經掃瞄器傳入電腦後的檔案是電子証書嗎？

那麽你對電子簽名 (數碼簽名) 這個名詞有認識嗎？

小故事一則: (附註：真人真事)
四封簡短的電子郵件

A : "Could you put your electronic signature in the document discussed earlier?"
B : "As I don't have any electronic signature, I signed it on the hard copy which your helper is keeping."
A : "What I meant was if you could scan your signature and merge it into the document."
B : (His mind: Ok....WXF...) "Done, the signed document is attached"

問題:
(1) 你能理解B先生 心裏浮現 WXF 的理由嗎？
(2) 到底B先生的簽署是否一個電子簽名呢？
(3) B先生最後送出的文件的簽名有法律效力嗎？

引伸問題:
假設B先生十天後反悔，口頭上否認那一份文件的簽署，
你能找出證據指証B先生曾經簽署嗎？

那麽電子簽名指的是什麼呢？背後的原理又是怎樣呢？

留待下回揭曉

ami~wkc

p.s.
廣告：
徵求掃瞄一整本書的快速方法
答： 先把書本解體然後放進掃瞄器

Bertrand's Postulate

Bertrand's Postulate says that for any integer n > 1 there is a prime number p such that n < p < 2n. Here's a link to a beautiful and elementary proof of this fact: http://mathforum.org/library/drmath/view/51527.html.

A beautiful solution

Suppose you want to prove that the sum of 1/(m^2 + n^2) diverges as m,n ranges over all positive integers. What do you do?

Here's a very beautiful solution, from one of my students in an undergraduate complex analysis class:

Every prime of the form 4k+1 is expressible as the sum of two squares. Hence the previous sum is bounded below by the sum of 1/p, where p ranges over all primes that are congruent to 1 mod 4. The latter sum diverges. Q.E.D.

Daily Life Application of Number Theory

A message from UC Berkeley (exact situation unknown):

Warning: Due to a known bug, the default Linux document viewer evince prints N*N copies of a PDF file when N copies requested. As a workaround, use Adobe Reader acroread for printing multiple copies of PDF documents, or use the fact that every natural number is a sum of at most four squares.

數學講座

日期：2009 年 11 月 20 日（星期五）
時間：下午 6 時 30 分至 8 時 30 分
地點：香港城市大學教學樓四樓 LT18 演講廳
講者：曾淵滄博士
講題：投資全攻略

簡介：
本講座旨在從科學角度與重點介紹甚麼是管理科學，亦討論管理科學如何在投資及財務應用方面所扮演之角色。本講座亦專為有志參加快張開辦的統計學課程而設。

有關其他詳情及報名方法，可瀏覽這裡。
（如果無法載入，可複製網址 http://hkage.org.hk/b5/new/Students/ma/0910003/poster.pdf）

死後的paper？

前兩天聽了一個關於random graph的seminar，回到辦公室就拿起Janson, Luczak和Rucinski的Random Graphs查一些terms的意思。隨手一揭，見到Erdős, Suen和Winkler在1995年一起出了一份paper。當時我想如果這是Paul Erdős的話，他不是已經離世很久了嗎？但查一查wiki，才知道他是在1996年離世的。

但另外查一查DBLP，竟發現Paul Erdős直到2006年為止仍然有聯名的paper發。究竟是因為其他的作者在十多年前和他討論得出成果，所以將Paul Erdős的名字寫在作者欄上，還是這個世界上有另一個Paul Erdos呢？煩請有識之士指點迷津。

AM-GM 不等式的幾個證明（六）

看見 Kahoo 給了 AM-GM 不等式這麼多個精彩的證明，不禁想再來一個用微分和凸函数 (convex functions) 的。

這裏我們只需留意對任意實數 x 和 a，



這不等式可以用很多不同的方法來證明，其中要想清楚當中的概念的，比較好的方法，是留意 是一凸函數，故其導數是遞增的，用中值定理即可推出上述不等式。（也可以不失一般性假設，從而用一元微積分或 的 Taylor 展開求得此不等式。）

有了這不等式以後，對正數 ，



這裏 a 可以是任何實數。把上列的不等式平均起來，得到

------(1)

取 ，則



從而 AM-GM 不等式得證。事實上不等式 (1) 的右邊是一關於 a 的函數，左邊則跟 a 無關，所以我們會取的 a 使得 (1) 的右邊達至最大值，而這正是我們上面這樣取 a 的原因。

這證明的一個好處，是我們可以用同樣的辦法證明以下這個 AM-GM 不等式的推廣：對任意 ，和任意正數 使得 ，有



從上面的討論可知，其實 AM-GM 不等式是函數 的 convexity 的反映。對任何的凸函數 f，我們都有 Jensen 不等式，詳見 wikipedia。

AM-GM 不等式的幾個證明（五）

作為本系列的完結篇，我們看看 AM-GM 不等式的一個不用數學歸納法的證明。本證明主要用到排序不等式，此不等式指出若 而 ，那麼當我們把這些 a_i 和 b_i「配對相乘再相加」時，有以下不等式：

這裡 f(1)、f(2)、…、f(n) 是 1, 2, ..., n 的一個任意排列，而以上不等式中的三行分別叫「逆序和」、「亂序和」和「順序和」。不等式看起來有點複雜，但其實背後意念很簡單：假設一批學生分 n 組比賽（人數分別是 a₁、a₂、…、a_n），而每組均選擇 n 種隊服中的一種（價錢分別是 b₁、b₂、…、b_n），那麼最省錢的自然是越多人的組別使用越便宜的隊服（即逆序和），最花錢的自然是越多人的組別使用越貴的隊服（即順序和）。利用排序不等式，不難證明對任意正數 y₁、y₂、…、y_n 皆有

（不失一般性設 ，並設 和 ，再使用「亂序和 ≧ 逆序和」即可）。

---

現在我們用以上結果來證明 AM-GM 不等式。不妨設 x₁x₂…x_n = 1（這可通過代換 得到），並設

即可得

從而證明了 AM-GM 不等式。

---

順帶一提，排序不等式的等號成立當且僅當 或 ，大家不妨試試由此導出 AM-GM 不等式的等號成立當且僅當 。

Gil Kalai's Seminar

上週四Hebrew University of Jerusalem和Yale University教授Gil Kalai來了Courant Institute講seminar。大家可能對這個名字有點印象，因為我曾在一篇手記 "Test Your Intuition"中提及他的網誌"Combinatorics and More"。

平時同一時段的"theory seminar"，有多於15人已屬罕見，但今次Prof. Kalai來講seminar卻吸引了38人來。平時有空位剩的房間一下子全院滿座，還有幾個人坐地下聽。

Prof. Kalai講了三個猜想，其中一個比較易懂和有趣，可以在這裏講講。

設。我們可以進行一個"Fourier Transform"，即寫成，當中（這與一般Fourier Series中的的角色相同。）假設，若每一個均獨立地有機會率 t 改變值（即由-1變成1或由1變成-1），若的機會很高，我們就可說 f 是noise stable。

甚麼情況下 f 是noise stable呢？Prof. Kalai舉了一個有趣的例子，就是說美國總統選舉，若Obama得票的數目是單數他就當選，否則McCain當選，這個選舉就很"noisy"，對吧？由此例子見到，noise stable的函數，它的Fourier expansion中，當S是一個較大的集合時，的值就應該很小。