Mưa vẫn mưa bay

Mưa ! Mưa to !!

Thế mà thằng khí tượng dự báo là “gần như chắc chắn là nắng đẹp”. Láo ! Cứ khen Mỹ nữa đi !!

Nhân chuyện dự  báo thời tiết, chắc ai cũng đã đọc bản tin kiểu “ngày mai khả năng mưa (hay tuyết)  là 80%”.  Nhưng khả năng 80% là cái quái gì ? Hoặc là mưa hoặc là không mưa chứ nhẩy ? Còn nếu nói kiểu xác suất (cho nó oai), thì phải định nghĩa một cái không gian  xác suất (nôm na là cái 80% đó tính trên cái gì).  Bà con nào thông thạo khí tượng, xin giải thích giùm.

Đài khí tựong Việt Nam có mấy cái thành ngữ  rất nên thơ là “…mưa rải rác” và “..mưa vài nơi”, chẳng hạn “khu vực miền Trung mưa rải rác” hay “miền Đông Nam bộ mưa vài nơi”. Một em phát thanh viên xinh đẹp êm ả đọc lên, giữa mùa hè nghe như có mưa bay trong lòng. Chỉ có điều nó hoàn toàn chẳng có thông tin gì sất. Miền Trung dài mấy trăm cây số, mưa rải rác  là mưa ở đâu ?  Được cái nói xong em cười cái xoè, rất tươi.

Lại chuyện  mưa, một dự báo nữa hay thấy là “lương mưa từ 7 đến 10 cm”. Cái này thì hoàn toàn cụ thể. Ta có thể hình dung là để một cái cốc hay cái chậu giữa sân thì mưa xong trong cốc nước sẽ cao từ 7 đến 10 cm. Ở Hà Nội, có lần tôi đã thử, thấy khá chính xác. Chỉ có điều, vừa bước ra phố, nước ngập ngay đến gần đầu gối !

Khoảng cách giữa cách số nguyên tố

Tin lành đồn xa, Tom Zhang (UNH) vừa  chứng minh sự tồn tại của vô hạn cặp số nguyên tố thoả mãn . Đây là một bước tiến khủng khiếp trong nghiên  cứu về khoảng cách giữa các số nguyên tố.

Kỷ lục trước đó là  thuộc về  Goldston, D. A. Pintz, J.,  Yıldırım, C. Y.  Kỷ lục cũ này cũng đã được coi là một bước tiến rất quan trọng, vì nó vượt qua được ngưỡng  mà bạn có thể cảm nhận qua mật độ của dãy số nguyên tố  ().

Nếu đúng, kết quả của Zhang sẽ mở đường cho một loạt nghiên cứu khác. Hiển nhiên số sẽ được  tối ưu hoá, và có lẽ   Twin Prime cọnjecture  sẽ được giải quyết một ngày khộng xa. Mạnh hơn nữa, ta có thể tấn công các phương trình tổng quát có dạng với là số nguyên cố định và là số nguyên tố.

Kết quả của Zhang hình như đã được một số chuyên gia kiểm chứng, và ông đã  giảng bài tại Harvard. Các trường đại học khác có lẽ sẽ mời ông trong thời gian nhanh nhất.

Một chi tiết rất đáng chú ý. Chân dung của gần như tất cả các nhà toán học khi có công trình tầm cớ như Zhang thường là: trẻ, sao đang lên (các giải thường treo lủng lẳng), làm việc tại các đại học lớn nổi tiếng, tenure rất sớm vv…

Bác Zhang là một ví dụ trái ngược lại tất cả các điều trên. Hình như bác đã 50+, nơi bác làm việc, khoa toán Univ. New Hamshire, là một đơn vị rất khiêm tốn.  Ngay tại khoa này, bác cũng chỉ là lecturer (giảng viên trơn), tức là không co tenure,  dưới cả bậc assistant professor, và là bậc thấp nhất trong các faculty. Nếu chứng minh của bác đúng (tôi cũng hy vọng nó đúng)  thì  ta được thấy tận mắt   Lọ Lem của toán học hiện đại.

Một ngày của Ally

Allison Smith, 23 tuổi,  là vận động viên bơi lội của Mỹ,  sở trường bơi sải. Tại thế vận hội London 2012, cô đoạt năm huy chương, trong đó  3 huy chương vàng, phá  hai kỷ lục thế giới. Số huy chương đó nhiều hơn thành tích của nhiều nước. Nếu nói Ally là một tài năng kiệt xuất, hay báu vật quốc gia, hẳn không có gì quá đáng.

Ally hiện đang học năm cuối tại đại học Georgia (University of Georgia), chuyên ngành Tâm lý. Dưới đây là nhật ký một ngày của cô (lươc dịch từ tạp chí Splash, tháng tư 2013):

5.07. Đồng hồ báo thức kêu inh ỏi. Bắt đầu một ngày mới.

5.13. Tôi và cô bạn cùng phòng, Megan Romano, rời nhà đi tới bể bơi. Khiếp, ra ngoài mới lạnh làm sao.

5.21. Đến bể rồi. Vẫn còn ngái ngủ. Nhưng một khi xuống nước, tớ sẽ tỉnh ngay thôi.

5.30. Buổi tập bắt đầu.

7. Bơi  xong.

7.15. Tập tạ.

8.45. Về nhà ăn sáng.

10.06. Ôn lại bài trước cái test đầu tiên trong ngày. Chắc là không khó lắm đâu. Nhưng mà cũng chẳng biết thế nào nhỉ.

10.22 Đi xe buýt tới lớp. Giá mà có một chỗ đậu xe trong trường nhỉ, lúc đó sẽ được ngủ thêm (hay học thêm) một chút.

10.25.  Xe buýt thật là đông, đóng cứng như cá hộp. Nhưng mà dù sao còn hơn đi bộ mấy cây ngoài trời gió lạnh.

10.52. Chuẩn bị cái test số 1 trong ngày. Đề tài: Nhạc. Lịch sử nhạc pop (5 chương), nhạc dân tộc (nhạc Anh, nhạc Mỹ gốc Phi, nhạc Mỹ gốc Ấn độ, nhạc Latin). Môn bắt buộc cho  ngành về xã hôi.

11.50. Giờ học tiếp sau, ở một tầng khác. Trèo thang gác cho nó lành :=))

12.08. Bạn có thể nhận thấy sinh viên nào là vận động viên vì họ phải đợi ở ngoài để điểm danh. Có một người được khoa thể thao gửi tới để đảm bảo tất cả vận động viên cũng làm test như những sinh viên khác.

12.15. Hôm nay là sinh nhật Uga !! (Uga là maskot của trường Georgia, một chú Bulldog; có điều là bọn Bulldog này là chó thật, trong ảnh là Uga đệ lục).

1.01. Đã đến giờ đến lớp tiếp theo. Lớp ở trên đồi. Vừa leo  vừa học bài, multi-tasking.

1.06. Ôi, may mà không đâm vào ai. Cũng học thêm được một tí cho cái test môn Tâm lý này.  Hy vọng !!

1.15 Cái test  thứ hai trong ngày. Cũng không phải ngày nào cũng lắm test thế này. Nhưng một học kỳ có năm cái test. Mà tớ lại lấy những năm lớp.

2.02. Buổi tập chiều đã đến. Hy vọng là mấy cái test vừa rồi được A (Mỹ cho điểm A, B, C, D, F; A là cao nhất). Không biết hôm nay được xếp bơi ở lane nào nhỉ ?

2.14. Chiều nay sẽ tập hai tiếng. Bơi chừng 7km. Chắc từng đoạn 100-200m mét một với nhịp tim nhất định.

4.52. Đi từ bể bơi về nhà. Đi nhanh còn tránh giờ cao điểm chứ. Bọn tôi đói rồi.

4.55 Buổi tập hôm nay thật vui. Bơi cùng với các bạn Megan, Shannon và Jordan. Cuối giờ, Jared và tôi lột mũ bơi ra trước khi huấn luyện viên cho phép. Thế là bị phạt thêm 50m nữa. Trong giờ nghỉ thì Chase và tôi đấy nhau bằng đầu :=)). Nói chung là rất khoái :=))

5.16. Chương trình tiếp theo là ăn tối. Trong nhà không ai ăn bằng phiếu ăn cả, chúng tôi tự nấu. Tôi và Megan thường nấu với nhau. Cô bé ấy nấu ngon lắm.

6.05. Bữa tối thật tuyêt. Xúc xích, ớt, khoai tây, cơm, trộn hết cả với nhau. Bây giờ đi ra student center ngồi học thôi.

6.55. Tham gia một cuộc họp của hội sinh viên-vận động viên. Chúng tôi nói chuyện rất lâu về làm sao có thể giúp được cộng đồng. Đây là một cơ hội tốt để gặp các vận động viên các môn khác trong trường.

9.03. Về nhà để làm nốt bài tập về nhà.

10.14. Thế là hết một ngày, buồn ngủ quá. Cắt xong mấy cái hoa quả và làm một cái bánh phết mứt cho ngày mai là tôi sẽ chui ngay vào chăn thôi.

Chuyện xảy ra trong buồng tắm hơi

Sáng nay tớ đi đến gym, sau một tuần bỏ bê, với lý do chính đáng là bị viêm họng. Lý do bị viêm họng thật ra không bình thường chút nào, nhưng bao giờ khỏe hẳn mới dám kể, vì đó là chủ đề nhạy cảm, có thể dẫn đến nhiều tranh cãi.

Vấn đề là, vẫn đau họng thì tập ít thôi. Ngồi tắm hơi là chính. Hôm nay thứ bảy, khá là đông. Già có trẻ có, gầy có béo có, dài có ngắn có, quàng khăn tắm có  không quàng cũng có, nói chung là đủ loại. Chuyện trò rôm rả (chắc là ở nhà bị vợ nói hết).

Chủ đề chính hôm nay là vụ bắt giữ kẻ khả nghi thứ hai trong vụ nổ vừa qua tại Boston. Phần lớn những người Mỹ trong phòng muốn  xem thủ phạm bị trừng trị như thế nào (giả thiết là kẻ bị bắt thực sự là kẻ gây án).

Điều mà họ quan tâm nhất là những luật sư biên hộ cho bị cáo có thể làm cách nào để giảm nhẹ mức án (rất có thể là mức cao nhất). Có người thì chắc chắn rằng luật sư sẽ dùng chiến thuật sử dụng những nhận xét của bạn bè, họ hàng người bị bắt (anh này được nhân xét là một người vui vẻ, dễ chịu, nhiều bạn bè quí mến, học chăm  vv) để chứng minh rằng anh ta bị anh trai cưỡng ép hoặc dụ dỗ vào việc phạm tội. Người thì nói luật sư sẽ khuyên anh này nhận tội, và xin lỗi nhân dân, để hy vọng sự thương hại của tòa. Người thì đưa ra chiến thuật là các luật sư cố sao giữ cho vụ án được xử trong phạm vi bang Masschusett, nơi không có án tử hình vv…

Phương án nào thì phương án, một điểm chung thú vị là tất cả những người Mỹ trong phòng đều tin tưởng là những luật sư biện hộ, cũng là người Mỹ và rất có thể còn sinh sống chính tại Boston, sẽ làm tất cả để giảm án cho thân chủ, một kẻ mấy ngày trước đã mưu sát chính họ.

The Universality Phenomenon

In the last 8 years or so,  I spent lots of time looking  at something called “The Universality Phenomenon”  from probability and mathematical physics. Typically, one looks at a lage system consisting of many independent particles (or variables). It has been observed that the outcome of the system, in most cases, do not depend too much on the fine details of the behavior of individual particles.

The most famous “universality” theorem  is the Central Limit Theorem. In its normalized form, it says that if are iid random variables with mean 0 and variance 1, then

the normal distribution. Notice that this statement does not take into account any other distributional information of the (such as third moment, the median, tail decay, etc); thus the  theorem holds for the big class all random variables with mean 0 and variance 1, raging from a very continuous one such as gaussian, to a very discrete one such as Bernoulli ( variable).

Universality has been proved, or conjectured, for a  wide class of functions. Instead of taking the sum, one can consider any other functions of the (such as higher degree polynomials, for instance). The hard cases are when the functions are defined only implicitly, such as in the case of random matrix theory. Here the (or more conveniently )  are the entries of the matrix, and one may care about the, say, th largest eigenvalue, or the number of eigenvalues in a  given small disk or interval. True,  these are still well-defined functions of the entries, but there are no way to write them down in a nice, explicit,  form as in the central limit theorem. Terence Tao blog has many detailed discussions on  problems of this type, so I do not labor further here.

Recent years witness  a tremendous progress in this area, and there is an explosion in term of  connections to other areas to mathematics as well.   This recent article of Natalie Wolchover does a very good job of  giving an comprehensive overview. A very recent, and quite fascinating connection has emerged in the work of Keneth Golden and his student Ben Murphy concerning in the melting of polar ice-caps. (Ken has made about 15 trips to both poles for his studies and the penguins on his website look especially cute :=)).

Still, there are so much to be done and so many mysteries remain. For instance, we still very far from understand why roots of the zeta function follow the law of  eigenvalues of a  random matrix (going back to the famous Montgomery-Dyson tea conversation at the IAS). Of course, to study such a thing, one first needs to assume the Riemann hypothesis (that all roots are on the same line). We are nowhere near it, either. But, well, better be prepared.

A small puzzle: Olydzko famously checked the Montgomery-Dyson conjeture by numerically computed the first roots of the zero function (well, not so sure about the exponent 10, but something of this magnitude). But given that computers only have finite precision, how can he be sure that they are indeed on the line ? (In other words: how can we be sure that it is indeed on the line, and not of distance, say, from it.)

Btw, an even larger prime has been found today…

 

Small ball probability and Inverse Littlewood-Offord theorems

Happy New Year everybody !!

Hoi Nguyen and I just finished a survey on the above topic (to appear in the Erdos centennial proceeding). I try to give a brief overview here. Small probability (or anti-concentration) is a classical topic in probability which has currently been revived thanks to applications for various fields of mathematics. For the whole paper, which can be read without too much knowledge in probability, follow this link or this link. 

Let be a real random variable with mean zero and variance one
and be a multi-set in (here ). The random sum where are iid copies of plays an essential role in probability. The Central Limit Theorem, arguably the most important theorem in the field, asserts that if the ‘s are the same, then the distribution of   tends to the normal distribution

Furthermore, Berry-Esseen theorem shows that if has bounded third moment, then the rate of convergence is .
This, in particular, implies that for any small open interval I, the probability  is of order

The assumption that the coefficients  are the same is, of course, not essential. Typically, it suffices to assume that none of the are dominating.

The probability (and its high dimensional generalization) will be referred to as  small ball  probability. In 1943, Littlewood and Offord, in connection with their studies of random polynomials, raised the problem of estimating the small probability for arbitrary coefficients . This is called the Littlewood-Offord problem. Notice that when we do not assume anything about the coefficients,  even the Central Limit Theorem may fail, so Berry-Esseen type bounds no longer apply.

Quite remarkably, Littlewood and Offord managed to show

Theorem 1. If is Bernoulli (taking values with probability ) and  have absolute value at least 1, then for any open interval of length 2,  

Shortly after, Erdos gave an improvement,  improving the right hand side to (exactly) , where is the largest binomial coefficient.  As far as the order of magnitude is concerned, this (via Sterling formula)  imporved Littlewood-Offord bound by the log factor.

Erdos’proof made an ingenious use of Sperner’s lemma, which asserts that if F  is an anti-chain on a set of $n$ elements, then it has at most elements (an anti-chain is a family of subsets none of which contains the other; it is clear that the collection of subsets of the same size form an anti-chain; thus, Sperner’s bound is sharp). Let be a fixed number. By reversing the sign of if necessary, one can assume that for all i. Now let  F be the collection of all subsets X of the index set such that

One can easily verify that F is an anti-chain. Hence, by Sperner’s lemma,

completing the proof.

To see that the bound is sharp, consider even, then . The problem was also studied in probability by Kolmogorov, Rogozin, Esseen,  Kesten, and many others. In particular, one can define the concentration function and study the behavior of this function.

Erdos’ result is popular in the combinatorics community and has became the starting point for a whole theory. For instance, there are extensions/refinements in several directions. For instance, one can

(1) Consider high dimensional settings.

(2) Consider the original (or the high dimensional) problem with additional assumption on the set (for instance, what happens if the elements of are well separated).

(3) Replace the linear function by a higher degree polynomial.

There has been lots of studies in these directions in the last 40 years or so, including deep and beautiful results of Kleitman, Halasz, Stanley, Sarkozy-Szemeredi, Frankl-Furedi, and many others, using very different methods.  We discussed  these results in the paper, along with few applications, and refer to them as forward theorems. These form the first part of the survey.

The second (middle part) focuses on the inverse phenomenon, which Terry Tao and I proposed about 6 years ago.  We  tried to find the underlying reason as to why the small ball probability is large (say, polynomial in ).

It is easier and more natural to work with the discrete version. Let be a multi-set of integers and be the Bernoulli random variable.

Question. 
Let . Assume that for some constant ,  What can we say about the elements of ? 

Denote by the sum of all elements of and rewrite as . As has subsets, the bound implies that at least among the subset sums are exactly . This overwhelming collision suggests that  A must have some strong additive structure. One can easily see, for instance, that an arithmetic progression satisfies this property.

Tao and I proposed

Inverse Principle. A set with large small ball probability must have strong additive structure.

As a matter of fact, we managed to show that most elements of belong to the Minkowsky sum of few arithmetic progressions (such a sum is refer to as a generalized arithmetic progression in the literature; see this paper and this link for more details). This result was strongly motivated by  the famous Freiman Inverse theorem in Additive Combinatorics. 

Since then, many more inverse theorems concerning small ball probability have been found, thanks to works of Rudelson-Vershynin, Friedland -Sodin, and Hoi and myself. We discussed these results in details, along with some proofs. (In one of the latest proofs, we managed to use Freiman theorem directly as a lemma, so the connection seems even stronger).

The third part of the survey contains an array of applications:

(1) Applying  Inverse theorems to prove Forward theorems. (Several forward theorems followed easily from the inverse ones; some old conjecture, such as one by Frank and Furedi can also be proved using the Inverse approach.)

(2) Strong bounds on the singularity probability of random Bernoulli  matrices by Tao et. al. (unsymmetric case) and Hoi Nguyen and Vershyin (symmetric case).

(3) Tail distribution of the least singular value of random matrix (by Rudelson, Tao et.al. Rudelson-Vershynin, Hoi Nguyen). Partial solution to a conjecture of Spielman and Teng. We do not discuss the connection to the proof of the Circular Law conjecture, but interested reader can check this link  or this link or this link for more information.

(4) Random polynomials (by Kozma-Zeitnouni).

(5) Applications in the theory of Boolean circuits  (Razborov-Viola).

Sự Học

Phiên thảo luận “Người trẻ và sự học” diễn ra cuối tuần trước tại TP.HCM do chương trình Hạt giống lãnh đạo IPL tổ chức đã thu hút được đông đảo bạn trẻ, sinh viên ưu tú của các trường đại học lắng nghe các chuyên gia chia sẻ về việc học hành.

http://vietnamnet.vn/vn/giao-duc/99763/-the-he-chung-toi-da-hut-dau—dao-het-than—-.html

Cuộc thảo luận được VNN đưa tin trọng thể (xem link trên).  Trong đó có nhiều ý kiến bất ngờ và đáng chú ý. Tôi xin trích nguyên văn:

 

“Chuyên gia kinh tế Bùi Văn cho rằng hiện nay, nếu muốn thống trị thế giởi phải là sức mạnh của sự học. Cách đây 700 năm trước đế chế Mông Cổ thống trị cả thế giới bằng vó ngựa. 500 năm về trước người ta thống trị thế giới bằng thuyền buồm và chỉ mới cách đây 250 năm người Anh đã thống trị thế giới bằng sức mạnh của động cơ hơi nước – Ông Bùi Văn phân tích.”

Câu đầu tiên có cách hành văn rất hiện đại (mang đậm tính Anh quốc), nhưng đọc kỹ  ai cũng hiểu đươc. Nhưng ý nghĩa các câu sau thì rất bí hiểm, không kém gì da Vinci code, tôi đọc mãi không hiểu gì cả. Ai làm ơn phân tích giúp !!

 

“Chuyên gia kinh tế Bùi Văn cho rằng, cái chính của sự học là sự nỗ lực. “Chúng ta hay nói việc học ở Việt Nam là thầy giảng, trò ngồi nghe. Lớp học có tới 60-70 người đã cho là đông, khó tiếp thu, nhưng có những lớp học ở Harvard có tới 1.000 SV ngồi nghe, vậy tại sao họ vẫn đưa ra được cách học tốt? Cứ thử làm một phép so sánh đơn giản, để làm được 1 tỷ USD đầu tiên, Bill Gates đã phải mất từ 6 đến 7 năm nhưng ông chủ Facebook làm ra số tiền đó chỉ mất trong vòng 1 năm, đó là sự khác nhau giữa sự học và không học.”

Wow, trường Harvard có cái lớp to dữ, đúng là bọn chơi trội (that is why at Yale we never like those guys :=)). Nhưng so sánh ông G. và ông Z. như trên thì tớ chưa thấy bao giờ. Chắc ông G. phải tiếc ghê lắm, giá mà học thêm năm nữa thêm cái bằng thì, biết đâu… 

 

“Ông Giản Tư Trung – Hiệu trưởng trường PACE và Viện trưởng viện IRED cũng nêu quan điểm rằng, người Việt Nam ai cũng mong muốn tiếng nói của mình được thế giới lắng nghe. Nhưng để có được điều đó phải có năng lực và thành tựu; quan trọng là chúng ta phải học và học kiểu gì để có năng lực và thành tựu.

Tôi rất tâm đắc với các bạn đi học ở nước ngoài về bảo rằng ở Anh- Pháp –Mỹ học chẳng khác gì Việt Nam nhưng vấn đề có chăng chỉ có vài điểm khác nho nhỏ. Khác ở chỗ thầy nói cái gì và nhận thức của người học như thế nào. Ví dụ, tại giảng đường Harvard sinh viên vào trường, câu khẩu hiệu “chúng tôi là những nhà lãnh đạo thế giới” nên suy nghĩ của họ làm thế nào để thay đổi thế giới, làm thế nào để thế giới tốt đẹp hơn. Chính sự khác biệt nho nhỏ đó biến học trò của họ thành người khác và dân tộc họ thành một dân tộc khác – Ông Trung phân tích.”

Híc, điểm “nho nhỏ” là “thầy giảng cái gì”. Thế thì  không biết cái gì là to (và giống) ? 

And again, dân Harvard  lại chơi trội. Bao nhiêu trường khác không có khẩu hiệu chắc là toi hết…:=((

 

“Chuyên gia kinh tế Bùi Văn ví von: “Tôi không dám đại diện cho cả thế hệ chúng tôi. Nhưng cá nhân tôi thấy: Thế hệ chúng tôi đã hút gần hết dầu, đã đào gần hết than, đã dùng lưới cào và  thuốc nổ  khai thác hết cá ở biển, từng đi chặt rừng để bán sang Nhật.

Như vậy, cái chúng tôi để lại cho thế hệ sau là gì? Là hết than, hết dầu, hết cá, hết rừng nhưng tôi rất tự hào về cái đó. Bởi vì chúng tôi để lại cho thế hệ trẻ một con đường duy nhất là phải học là không còn dựa vào tài nguyên thiên nhiên nữa. Đó là điều mà tôi tự hào để lại cho thế hệ sau”.

 

Ngất.