Category Archives: Math

Maryam Mirzakhani và bài toán 4 màu tự chọn

Maryam Mirzakhani, cho tới nay, là người phụ nữ duy nhất được huy chương Fields (năm 2014). Chị sinh ra ở Iran, hai lần đoạt huy chương vàng thi toán quốc tế. Mirzakhani học đại học ở Iran, sau đó sang Mỹ, từ năm 2008 là giáo sư đại học Stanford. Chị mới qua đời mấy hôm trước, lúc mới 40 tuổi. “A light was turned off today. It breaks my heart ….. gone far too soon.” – một người bạn của chị viết trên Instagram.

Tôi chắc chắn là mình không thể hiểu được những công trình đã đem lại cho Mirzakhani huy chương Field, nhưng tôi có tìm đọc bài báo đầu tiên của chị. Bài báo có lẽ viết năm 1995 hoặc 1996, được đăng năm 1996. Bài báo liên quan đến định lý bốn màu quen thuộc. Định lý này nói rằng ta có thể dùng bốn màu (ví dụ xanh, đỏ, tím, vàng) để tô bất cứ một bản đồ nào sao cho hai nước có đường biên giới chung bao giờ cũng được tô bằng hai màu khác nhau. Định lý này được Francis Guthrie, một nhà toán học đồng thời cũng là nhà thực vật học, phát biểu năm 1852 và đã được chứng minh vào năm 1976/1977 (với sự giúp đỡ của máy tính).

Bài toán Mirzakhani xem xét cũng liên quan đến việc tô màu bản đồ. Trong bài toán 4 màu kinh điển thì 4 màu có thể coi là do một cơ quan quốc tế chọn trước, tất cả các nước phải tô theo 1 trong 4 màu đó. Ví dụ nếu cơ quan quốc tế quyết định dùng 4 màu xanh-đỏ-tím-vàng thì nước nào trên bản đồ cũng được tô bằng một trong 4 màu đó, không thể bằng màu nào khác, như màu nâu chẳng hạn.

Bây giờ ta tưởng tượng các nước không thống nhất được 4 màu dùng cho bản đồ là những màu gì. Để giải quyết sự tranh chấp, người ta cho mỗi nước được chọn 4 màu của mình. Ví dụ nước A có thể chọn xanh-đỏ-tím-vàng, nước B chọn xanh-đỏ-tím-nâu, nước C đỏ-tím-vàng-nâu v.v. Nhiệm vụ của người làm bản đồ phải tìm cách tô bản đồ sao cho

1. nước nào cũng được tô bằng 1 trong 4 màu mình chọn, và
2. không có 2 nước láng giềng nào bị tô 2 màu giống nhau.

Liệu điều này có thể làm được với tất cả các bản đồ hay không? Tức là cho một bản đồ bất kỳ, cho mỗi nước chọn 4 màu bất kỳ, có phải bao giờ cũng tồn tại một bản đổ thoả mãn hai tính chất nói trên không?

Có thể nghĩ rằng nếu các nước khác nhau chọn những bộ 4 màu khác nhau thì phải dễ tô màu bản đồ hơn là lúc tất cả các nước phải dùng 4 màu giống nhau. Giả sử ta bắt đầu tô bản đồ từ nước A, sau đó chuyển sang nước B láng giềng. Nếu bản đồ chỉ dùng bốn màu xanh-đỏ-tím-vàng, nếu ta tô nước A màu vàng, thì nước B láng giềng chỉ có thể tô bằng một trong ba màu xanh-đỏ-tím. Nhưng trong trường hợp các màu là cho các nước tự chọn, nếu bộ 4 màu của nước B là xanh-đỏ-tím-nâu thì sau khi tô nước A màu vàng ta vẫn còn đủ 4 cách tô màu nước B, thay vì 3.

Tuy nhiên, người ta đã chứng minh được là phải cho mỗi nước được chọn 5 màu thì mới chắc chắn làm được bản đồ mà không ai bị tô màu mình không muốn. Năm 1993 người ta đã tìm ra một tường hợp với 238 nước mà, với một sự chọn lựa màu của từng nước, không tồn tại bản đồ mà nước nào cũng được tô 1 trong 4 màu của mình và khác màu tất cả các nước láng giềng.

Mirzakhani tìm được một bản đồ chỉ có 63 nước và một cách chọn bộ 4 màu của từng nước mà không tồn tại cách tô màu bản đồ với những tính chất viết ở trên. Ngoài việc giảm số lượng nước từ 238 xuống 63, ví dụ của chị còn có một tính chất rất hay là về nguyên tắc, nếu các nước chấp nhận tô màu gì cũng được, thì chỉ cần 3 màu là tô được toàn bộ bản đồ. Trước đây đã có giả thuyết là nếu bản đồ có thể tô được bằng 3 màu thì cho mỗi nước tự chọn 4 màu là đủ để làm bản đồ. Ví dụ của Mirzakhani chứng tỏ giả thuyết này là sai.

Bài báo ngắn và tương đối dễ hiểu, có thể đọc ở đây. Ngoài ra có thể xem thêm bài Tuổi trẻ của một người phụ nữ đạt huy chương Fields đăng ở tạp chí Epsilon số 13, trang 299.

Dưới đây là bản đồ Mirzakhani tìm ra. Bản đồ vẽ dưới dạng graph, mối điểm là một nước, hai điểm nối với nhau bởi một đường là hai nước có chung biên giới. Điểm bên phải nối với tất cả các điểm nằm ở biên của hình bên trái. Các số ở các đỉnh tương ứng với 4 màu nước đó chọn. Muốn hiểu làm thế nào Mirzakhani tìm ra được bản đồ này thì phải đọc bài báo của chị. Không biết 63 đã phải là số nhỏ nhất chưa? Tôi đoán là chưa.

Advertisements

Công thức Hardy-Ramanujan qua mô hình chất rắn Debye

Bạn nào đã xem cuốn phim The Man Who Knew Infinity chắc sẽ nhớ một công thức đóng vai trò rất quan trọng trong phim: công thức về hàm phân hoặch số nguyên, được Hardy và Ramanujan tìm ra năm 1918. Hàm phân hoạch p(n) định nghĩa rất đơn giản. Lấy ví dụ số 4; số này có thể biểu diễn bằng 5 cách khác nhau thành tổng các số nguyên:

4 = 4
4 = 3 + 1
4 = 2 + 2
4 = 2 + 1 + 1
4 = 1 + 1 + 1 + 1

Như vậy p(4) = 5. Tương tự p(5) = 7, p(10) = 42. Nhưng khi n tăng cao thì p(n) tăng lên rất nhanh, ví dụ, p(200) = 3.972.999.029.388. Trong phim MacMahon tính con số này bằng tay, không rõ bằng phương pháp nào. Hardy và Ramanujan tìm ra công thức cho tiệm cận của p(n) với n lớn,

p(n) \approx \displaystyle{\frac1{4n\sqrt3}}\exp\left(\pi\sqrt{\frac{2n}3}\right)

Nếu ta thay n = 200 vào công thức này thì ta sẽ tìm được p(200) = 4,10 × 1012, sai số 3.2% so với kế quả chính xác. n càng lớn thì sai số này càng bé.

Một cảnh trong phim

Có vẻ phương pháp mà Hardy và Ramanujan dùng để tìm được công thức này khá phức tạp. Trong bài này chúng ta sẽ dùng vật lý để tiếp cận công thức Hardy-Ramanujan. Tìm được toàn bộ tiệm cận của p(n) thì hơi khó, ta sẽ chỉ nhắm vào phần quan trọng nhất, phần exp thôi. Nói cách khác, chúng ta sẽ chứng minh:

\ln p(n) \approx \pi\sqrt{\displaystyle{\frac{2n}3}}

Để tìm được công thức này, chúng ta sẽ dùng một cách tiếp cận không chính quy. Ta sẽ dùng mô hình Debye của nhiệt dung của chất rắn. Công trình này của Debye được viết năm 1912, vài năm trước khi Hardy và Ramanujan công bố công thức cho p(n). Có lẽ Hardy và Ramanujan không biết về công trình của Debye.

Trước Debye người ta đã biết định luật Petit-Dulon, theo đó nhiện dung của một khối chất rắn là một hằng số không phụ thuộc vào nhiệt độ. Tuy nhiên thí nghiệm cho thấy định luật Petit-Dulon chỉ đúng ở nhiệt độ đủ cao, định luật này bị vi phạm ở nhiệt độ thấp. Einstein là người đầu tiên chỉ ra mối liên hệ giữa sự vi phạm định luật Petit-Dulon với cơ học lượng tử. Trong mô hình của Einstein, nhiệt dung là hằng số nếu nhiệt độ cao nhưng tiến tới 0 khi nhiệt độ giảm tới 0. Tuy nhiên trong mô hình của Einstein nhiệt dung tiến tới 0 nhanh hơn so với đo được trong thực nghiệm. Năm 1912 Debye đưa ra mô hình giải thích được sự biến thiên của nhiệt dung của chất rắn. Cách tiếp cận của Debye hết sức mới mẻ. Debye không nhìn chất rắn như một tập hợp các nguyên tử, ông nhìn chất rắn là một khí tạo ra bởi các hạt phonon – lượng tử của sóng âm thanh. Trong mô hình Debye, các nguyên tử chỉ là cái nền cho các hạt phonon lan truyển.

Để liên hệ với công thức Hardy-Ramanujan ta chỉ cần xem xét một chất rắn 1 chiều. Để dễ tưởng tượng, ta sẽ xét một chiếc dây đàn, căng giữa hai điểm A và B. Ta chọn trục x của hệ toạ độ chạy theo đường thẳng nối hai điểm A và B. Nếu độ dài dây đàn là L thì tại A ta chọn x = 0, tại B x = L.

Khi ta gẩy đàn sẽ có sóng lan truyền trên dây đàn. Sóng này coi như là âm thanh trong môi trường một chiều. Để cho đơn giản ta giả sử dây đàn chỉ dao động theo chiều y. Trạng thái của dây đàn tại một thời điểm nào đó được mô tả bới hàm y = y(x). Giả sử vận tốc lan truyền của sóng là v. Do hai đầu dây đàn bị đóng cứng, sóng trên dây đàn phải là sóng đứng, và biên độ của sóng biến thiên theo toạ độ và thời gian theo công thức

y = \sum\limits_{k=1}^\infty A_k\cos(k\omega_1 t + \alpha_k) \sin\left( \displaystyle{k \frac{\pi x}L}\right)

Trong công thức trên \omega_1 là tần số cơ bản của dao động của dây đàn,

\omega_1 = \displaystyle{\frac {\pi v}L}

và các hoạ ba (harmonic) cao hơn có tần số \omega_k=k\omega_1 với k=2,3,\ldots.

Bây giờ ta lượng tử hoá cái dây đàn. Mỗi tần số \omega_k nay tương đương với một dao động tử điều hoà, và dây đàn là một tổ hợp các dao động tử điểu hoà với tần số \omega_1, \omega_2, v.v. Các mức năng lượng của dao động tử điều hoà với tần số \omega\hbar\omega(n+\frac12). Như vậy để mô tả trạng thái lượng tử của dây đàn, ta cần một số vô hạn các số lượng tử n_1, n_2,\ldots n_k,\ldots trong đó n_k là số lượng tử của dao động tử với tần số \omega_k=k\omega_1. Như vậy

E = E_0 + \sum\limits_{k=1}^\infty \hbar k \omega_1 n_k

trong đó E_0 là năng lượng của trạng thái cơ bản. Để đơn giản từ nay ta sẽ đo năng lượng của dây đàn từ E_0, tức là cho E_0=0.

Bây giờ có thể nhận ra một điều như sau:

Có p(n) trạng thái lượng tử của dây đàn với năng lượng n\hbar\omega_1

Đây chính là điểm liên hệ giữa vật lý và công thức Hardy-Ramanujan. Nghĩ một lúc các bạn sẽ thấy điều này hầu như là hiển nhiên. Ví dụ ở mức năng lượng 4\hbar\omega_1 có năm trạng thái:

n_4=1; n_k=0, k\neq4
n_3=n_1=1; n_k=0, k\neq 1,3
n_2=2; n_k=0, k\neq 2
n_2=1, n_1=2; n_k=0, k\neq 1,2
n_1=4; n_k=0, k\neq 1.

Khi đã biết số trạng thái có năng lượng n\hbar\omega_1 bằng p(n), ta kết luận \ln p(n) chính là entropy khi năng lượng bằng n\hbar\omega_1, theo định nghĩa của entropy qua tập thống kê vi chính tắc (microcanonical ensenble).

Nhưng trong vật lý thống kê, ta có thể dùng tập thống kê chính tắc (canonical ensemble) để tính entropy của dây đàn, thay vì dùng vi chính tắc. Bình thường tính toán dùng tập thống kê chính tắc bao giờ cũng đơn giản hơn là dụng tập vi chính tắc.

Một điểm làm đơn giản bài toán là khi nhiệt độ lớn hơn tần số dao động cơ bản, ta có thể bỏ qua hiệu ứng bề mặt của hai đầu dây đàn. Bây giờ dây đàn có thể coi là một chất khí phonon một chiều. Bài toán như vậy được đưa về dạng một chiều của bài toán mà Debye đã giải quyết năm 1912 khi ông tính được nhiệt dung của chất rắn ở nhiệt độ thấp.

Bạn có thể làm tiếp những tính toán còn lại nếu bạn nào đã học vật lý thống kê; coi như đây là bài tập cho bạn. Bạn có thể tính entropy trực tiếp, hoặc tính nhiệt dung rồi lấy tích phân để tìm entropy. Kết quả là mô hình Debye của chất rắn cho ta phần exponent của công thức Hardy-Ramanujan.

\ln p(n) \approx \pi\sqrt{\displaystyle{\frac{2n}3}}

Cách tiếp cận vật lý cho công thức Hardy-Ramanujan trên đây có trong cuốn B. Zwiebach, A First Course in String Theory.

Công thức Euler-Maclaurin

Công thức Euler-Maclaurin

f(0) + f(1) + f(2) + \cdots = \displaystyle{\int\limits_0^\infty\!dx\, f(x)} + \frac12 f(0) - \frac{f'(0)}{12} + \frac{f'''(0)}{720} + \cdots

rất hay được sử dụng trong vật lý, ví dụ trong bài toán về nghịch từ Landau, hay hiệu ứng Casimir. Hôm trước tôi có học mót được từ một người bạn cách chứng minh như sau.

Ta bắt đầu từ khai triển Taylor:

f (x+a) = f(x) + a \displaystyle{\frac{d f(x)}{d x}} + \frac{a^2}{2!} \frac{d^2 f(x)}{d x^2} + \frac{a^3}{3!} \frac{d^3 f(x)}{d x^3} + \cdots

Để cho tiện ta ký hiệu \mathrm{d}=d/dx. Ta có thể viết công thức trên như sau:

f (x+a) = \left(1+ a\mathrm{d}+ \displaystyle{\frac{(a\mathrm{d})^2}{2!}} +\cdots \right)f(x) = e^{a \mathrm{d}} f(x)

đo đó

f(0) + f(1) + f(2) + \cdots = (1+ e^{\mathrm{d}} + e^{2\mathrm{d}} + e^{3\mathrm{d}}+\cdots) f(x)|_{x=0}

Lấy tổng cấp số nhân trong ngoặc ta nhận được

f(0) + f(1) + f(2) + \cdots = \displaystyle{\frac1{1- e^{\mathrm{d}}}} f(x)|_{x=0}

Bây giờ ta lại khai triển hàm số (1-e^{\mathrm{d}})^{-1} thành chuỗi Taylor theo \mathrm{d}. Ta nhận được

\left(-\mathrm{d}^{-1}  + \displaystyle{\frac12} - \frac{\mathrm{d}}{12} + \frac{\mathrm{d}^3}{720} + \cdots\right) f(x)|_{x=0}

Bây giờ ta phải xác định \mathrm{d}^{-1} là gì. Nếu \mathrm{d} là đạo hàm thì tất nhiên \mathrm{d}^{-1} phải là tích phân. Giới hạn trên của tích phân thì theo công thức trên phải là 0, giới hạn dưới thì cứ lấy đại +\infty,

\mathrm{d}^{-1} = \displaystyle{\int\limits^0_{+\infty}\!dx}

Và như thế ta nhận được công thức Euler-MacLaurin ở trên.

Bài tập: tìm khai triển của

f\left(\displaystyle{\frac12}\right) + f\left(\displaystyle{\frac32}\right) + f\left(\displaystyle{\frac 52}\right) +\cdots - \displaystyle{\int\limits_0^\infty\!dx\, f(x)}

qua các đạo hàm của hàm số f(x) tại x=0.

Trả tiền nhuận bút

Một tờ tạp chí quy định trả tiền nhuận bút theo số trang. Bài dài n trang được trả

1+\displaystyle{\frac12}+\displaystyle{\frac13}+\cdots+\displaystyle{\frac1n}

đồng.

Bạn Tèo có một bài báo dài 1/2 trang được đăng. Hỏi toà soạn phải trả bạn bao nhiêu tiền?

Không phải cái gì máy tính cũng làm đuợc

Đây là chứng minh:

Chứng minh công thức Euler cho đa diện bằng vật lý

Giải Nobel vật lý năm nay được trao cho ba nhà vật lý, Thouless, Haldane và Kosterlitz, vì những đóng góp liên quan đến các chuyển pha và các trạng thái tôpô. Nhân dịp này chúng ta sẽ dùng vật lý để chứng minh một công thức khá nổi tiếng, liên quan đến tôpô – công thức Euler cho đa diện. Công thức này nói rằng với một đa diện bất kỳ, số đỉnh V, số mặt F và số cạnh E của nó thoả mãn

V + F – E = 2.

Ví dụ với hình lập phương ta có V = 8, F = 6, E = 12, và 8 + 6 – 12 = 2. Bạn có thể kiểm tra với một vài hình đa diện nữa để thấy công thức luôn đúng.

Để chứng minh công thức này, ta sẽ lắp một mạch điện theo hình đa diện, thay mỗi cạnh của đa diện bằng một điện trở. Không quan trọng lắm các giá trị của điện trở là bao nhiêu, miễn là tất cả các điện trở đều khác không. Để cho đơn giản ta cho mỗi điện trở là 1 Ω. Sau đó ta chọn hai đỉnh và nối hai cực của một nguồn điện vào hai đỉnh đó, cũng không quan trọng lắm là đỉnh nào. Chẳng hạn với hình lập phương ta có thể tưởng tượng ra mạch điện như sau:

Khi ta nối một mạch điện như vậy, tất nhiên điện sẽ chạy trong mạch một cách nhất định. Ta có thể đặt nhiều câu hỏi với mạch điện này. Ví dụ ta có thể hỏi điện trở của mạch là bao nhiêu. Câu hỏi tôi sẽ hỏi là như sau: giả sử tổng dòng điện chạy qua mạch là 1 Amper, dòng điện chạy qua từng điện trở là bao nhiêu? (Tất nhiên là nếu trả lời được câu hỏi này thì có thể tìm ra được điện trở của mạch).

Để trả lời câu hỏi trên, ta sẽ lập một hệ phương trình cho phép ta tìm được dòng điện chảy qua từng điện trở. Giả sử AB là một cạnh, ta ký hiệu IAB là dòng điện chạy từ đỉnh A đến đỉnh B. Ta có IAB = –IBA, và có tổng cộng E đại lượng này. Ta sẽ lập một hệ phương trình để tìm giá trị của các dòng điện này.

Có hai loại phương trình, xuất phát từ hai định luật Kirchhoff. Loại đầu tiên là như sau. Giả sử A là một đỉnh, và B, C, D… là các đỉnh kề A. Ta có phương trình:

IAB + IAC + IAD + … = 0 hoặc 1 hoặc –1.

Vế phải là 0 nếu như đỉnh A không phải một trong hai đỉnh nối vào nguồn điện, là 1 nếu A được nối vào cực dương và –1 nếu A nối vào cực âm. Đơn giản phương trình này nói dòng điện chạy vào một đỉnh phải bằng dòng chạy ra từ đó.

Ta có tổng cộng bao nhiêu phương trình như thế này? Đếm thì thấy tổng cộng là V phương trình, nhưng thực ra chúng không độc lập với nhau. Có thể thấy điều này bằng cách lấy tổng tất cả các phương trình trên. Ta sẽ được đồng nhất thức 0 = 0, vì ở vế trái với mỗi IAB bao giờ cũng có IBA. Vế phải thì tất nhiên tổng là 1 + (–1) cộng nhiều số 0, cũng bằng không. Như vậy chỉ có V – 1 phương trình độc lập.

Nhưng những phương trình trên không phải tất cả các phương trình ta phải viết ra. Có một loạt các phương trình khác (phương trình loại hai). Ta giả sử ABCD là một mặt (ta cho nó là tứ giác ở đây nhưng logic tiếp theo đúng với mọi đa giác). Ta sẽ có phương trình

IAB + IBC + ICD + IDA = 0.

Tại sao có phương trình này? Đó là do điện trở trên mỗi cạnh là 1 Ω nên IAB cũng là hiệu điện thế giữa hai đỉnh AB: IAB = UA – UB. Từ đó phương trình ở trên trở thành hiển nhiên. Tổng cộng có F phương trình như vậy. Tuy nhiên các phương trình này cũng không độc lập, nếu cộng tất cả các phương trình này lại ta lại có đồng nhất thức 0 = 0, do đó là chỉ có F – 1 phương trình loại hai.

Tổng cộng ta có như vậy là (V – 1) + (F – 1) = V + F – 2 phương trình.

Ta phải giải các phương trình này để tìm các dòng IAB. Có bao nhiêu ẩn số tất cả? Số ẩn là số cạnh E.

Thiên nhiên cho ta biết khi nối mạch điện thì chỉ có một nghiệm duy nhất, vậy số phương trình phải bằng số ẩn.

Do đó V + F – 2 = E.

Đây chính là công thức Euler phải chứng minh.

Tầm quan trọng của việc học ngoại ngữ

Tôi vẫn nhớ một câu thơ của Mayakovsky mà tôi đọc được từ rất lâu khi đang học tiếng Nga, dịch ra đại khái như sau (xin lỗi là dịch không vần):

Kể cả nếu tôi là người da đen cao tuổi
tôi cũng sẽ không chán nản lười biếng
học tiếng Nga chỉ vì đó là tiếng nói của Lênin

Trên thực thế, tôi không biết người nào (tất cả các màu da và tuổi tác) mà học tiếng Nga chỉ vì đó là tiếng nói của Lênin. Tuy vậy gần đây tôi đọc được một câu chuyện làm tôi nhớ tới câu thơ của Mayakovsky. Câu chuyện được nhà toán học Vladimir Voevodsky kể lại:

Năm 1984, Alexander Grothendieck nộp cho CNRS một đề án có tên là “Esquisse d’un Programme”. Ngay sau đó giới toán học bắt đầu chuyền tay nhau các bản sao của đề án này.

Vài tháng sau đó, thầy hướng dẫn khoa học đầu tiên của tôi, ông George Shabat, đưa đề án này cho tôi đọc. Lúc đó tôi là sinh viên năm thứ nhất trường Đại học Tổng hợp Mátxcơva.

Sau khi học một ít tiếng Pháp với mục tiêu duy nhất là để đọc được tài liệu này, tôi bắt đầu triển khai một số ý tưởng mà Grothendieck phác thảo trong đó…”

18 năm sau khi bắt đầu học tiếng Pháp, Voevodsky được huy chương Fields.