Phạm Tuấn Huy và Giả thuyết Kahn-Kalai
Gần đây, báo chí Việt Nam nhắc nhiều đến cái tên Phạm Tuấn Huy – nghiên cứu sinh 26 tuổi, ngành Toán học tại Đại học Stanford được trao tài trợ nghiên cứu Clay (Clay Research Fellowship) của viện toán học cùng tên. Giải thưởng này dành cho những nhà nghiên cứu ở buổi đầu sự nghiệp và có tiềm năng trở thành nhà toán học đầu ngành trong tương lai. Điều đặc biệt ở Clay Research Fellowship là có tính dự đoán cao, trong 45 nhà toán học từng giành được tài trợ này, có chín người đã trở thành chủ nhân giải thưởng Fields sau đó.
Phạm Tuấn Huy từ lâu đã được biết tới như một chàng trai vàng của làng Toán học Việt Nam. Cậu là người Việt Nam thứ sáu đoạt hai huy chương vàng Toán quốc tế (IMO) liên tiếp, tiếp nối thành tích của các bậc tiền bối như Ngô Bảo Châu hay Ngô Đắc Tuấn (nghiên cứu viên cao cấp tại CNRS, Pháp). Sau khi chinh phục vô số giải thưởng và huy chương trong các cuộc thi Toán phổ thông trong và ngoài nước, Huy rời mái trường Phổ thông năng khiếu TP.HCM để theo học chương trình đại học tại Đại học Stanford nổi tiếng của Hoa Kỳ, rồi học tiếp lên thạc sĩ tại Đại học Cambridge danh giá của Anh quốc. Môi trường học tập đỉnh cao thế giới không làm khó được Huy. Cậu liên tiếp đoạt được nhiều giải thưởng xuất sắc như Dean’s Award dành cho top 10 sinh viên đại học xuất sắc nhất, huy chương Firestone và giải thưởng Kennedy cho luận văn tốt nghiệp xuất sắc nhất, giải thưởng Toán lý thuyết cho sinh viên xuất sắc nhất về Toán lý thuyết tại Cambridge. Lên tới chương trình tiến sĩ, Huy quyết định quay lại Stanford để theo học dưới sự hướng dẫn của giáo sư Jabob Fox, một trong những thần đồng Toán học nổi tiếng của Hoa Kỳ. Lĩnh vực nghiên cứu mà Huy lựa chọn là Lý thuyết tổ hợp và xác suất cùng các ứng dụng trong lý thuyết khoa học máy tính và học máy. Huy thường quan tâm tới tính chất của các đối tượng ngẫu nhiên như đồ thị, đa thức hay tập hợp số. Chỉ trong một thời gian ngắn, gia tài khoa học của Huy đã rất đồ sộ với gần 30 bài báo đăng trên các tạp chí khoa học uy tín. Trong số đó, lời giải cho giả thuyết Kahn-Kalai là kết quả gây được tiếng vang lớn nhất và đã giúp Huy giành được giải thưởng danh giá của Viện Clay.
Trong Toán học đôi khi chúng ta bắt gặp những điều kì diệu. Một bài toán rất phức tạp và có độ tổng quát hóa cao lại có thể có một lời giải tường minh hết sức gọn gàng. Chứng minh cho giả thuyết Kahn-Kalai của Phạm Tuấn Huy và người đồng nghiệp người Hàn Quốc Jinyoung Park là một điều kì diệu như vậy.
Giả thuyết Kahn-Kalai được đề xuất năm 2006 bởi hai bậc đại thụ trong làng toán tổ hợp và xác suất là GS. Jeff Kahn (ĐH Rutgers, Mỹ) và GS. Gil Kalai (ĐH Hebrew của Jerusalem, Israel). Giả thuyết được biết tới như là sự tổng quát hóa của rất nhiều bài toán phức tạp xoay quanh sự xuất hiện của một cấu trúc nào đó trong quá trình phát triển của một hệ thống ngẫu nhiên. Để dễ hình dung về nội dung giả thuyết, chúng ta hãy xem xét một ví dụ đơn giản. Hãy tưởng tượng là có 100 thành phố trên thế giới, và chúng ta bắt đầu thiết lập đường bay trực tiếp giữa các thành phố bằng cách tung 1 đồng xu. Giữa hai thành phố bất kì, ta tung đồng xu một lần, nếu đồng xu lật ngửa thì đường bay trực tiếp sẽ được thiết lập, còn nếu đồng xu lật sấp thì sẽ không có đường bay. Giả sử bạn là một khách du lịch muốn thăm tất cả 100 thành phố này, bạn sẽ muốn tìm một lịch trình bay qua 100 thành phố mà không phải quay lại thành phố nào hai lần. Nếu đồng xu được tung không đồng nhất và có khả năng lật ngửa rất thấp, khi đó mạng lưới bay của ta sẽ có rất ít đường bay, và sẽ rất khó để tìm được một lịch trình bay qua tất cả như ý muốn. Giờ hãy tưởng tượng là bằng một cách nào đó, ta thay đổi khả năng lật ngửa của đồng xu theo hướng tăng cao dần lên, khi đó mạng lưới đường bay tương ứng sẽ ngày càng dày đặc thêm, và tới một thời điểm nào đó các lịch trình bay qua cả 100 thành phố sẽ đột ngột xuất hiện. Điểm chuyển tiếp giữa tình trạng “không có một lịch trình nào” và “chắc chắn có lịch trình” đi qua 100 thành phổ sẽ tương ứng với một giá trị cụ thể của khả năng lật ngửa của đồng xu. Và giá trị này gọi là “giá trị ngưỡng”. Mạng lưới đường bay thiết lập như trên là một ví dụ về một hệ thống ngẫu nhiên, còn lịch trình bay qua toàn bộ 100 thành phố là ví dụ về một cấu trúc mong muốn trong hệ thống đó. Hệ ngẫu nhiên và các cấu trúc quan trọng của nó là đối tượng được nghiên cứu rất nhiều trong cơ học thống kê và lý thuyết đồ thị.
Khi nói một hệ thống là ngẫu nhiên có nghĩa là chúng ta không kiểm soát được trạng thái cụ thể của nó. Bởi vậy, việc xác định được giá trị ngưỡng sao cho gần như chắc chắn hệ thống có chứa cấu trúc mong muốn là rất quan trọng. Tuy nhiên thường thì rất khó để tính chính xác được giá trị ngưỡng này. Trong khi đó, có một giá trị khác được gọi là “ngưỡng kì vọng” hay “ngưỡng trung bình” thì lại có thể được tính khá dễ dàng. Nếu có thể xác định được một mối quan hệ rõ ràng giữa giá trị ngưỡng và giá trị ngưỡng kì vọng thì công việc ước lượng giá trị ngưỡng sẽ đơn giản đi rất nhiều.
GS. Kahn và GS. Kalai đã đề xuất một giả thuyết để kết nối hai giá trị này như sau: cho một hệ ngẫu nhiên và một cấu trúc cụ thể, tỉ lệ giữa giá trị ngưỡng kì vọng và giá trị ngưỡng để cấu trúc xuất hiện trong hệ thống luôn nhỏ hơn một hệ số xác định được. Nói một cách khác là hai giá trị này đủ gần với nhau để có thể dùng giá trị ngưỡng kì vọng để ước lượng giá trị ngưỡng một cách khá chính xác. Đây là một giả thuyết đầy tham vọng vì phạm vi áp dụng của nó rất rộng cho nhiều hệ ngẫu nhiên khác nhau. Nếu giả thuyết này là đúng thì nó sẽ cung cấp cho các nhà toán học một con đường tắt để ước lượng giá trị ngưỡng cho nhiều cấu trúc trong nhiều hệ khác nhau. Từ đó, nó có khả năng mở ra một loạt các khám phá mới khác, tương tự như Bổ đề cơ bản mà GS. Ngô Bảo Châu đã chứng minh, dù ở quy mô nhỏ hơn. Chính vì tầm quan trọng đó, rất nhiều nhà toán học (trong đó có bản thân GS. Kahn và GS. Kalai) đã đầu tư thời gian nghiên cứu nhằm giải quyết chứng minh này trong hơn 15 năm qua.
Cơ duyên giữa Phạm Tuấn Huy và giả thuyết Kahn-Kalai bắt đầu từ khi TS. Jinyoung Park gia nhập nhóm nghiên cứu của GS. Jacob Fox tại ĐH Stanford. TS. Park là người phụ nữ kiên cường, từ một giáo viên dạy toán phổ thông vươn lên thành một trong những nhà toán học có triển vọng cao. Mặc dù bắt đầu học t.iến sĩ rất muộn ở tuổi 32, cô đã rất nỗ lực và trở thành một học trò xuất sắc của GS. Kahn tại trường ĐH Rutgers. Luận án tiến sĩ của cô được đánh giá rất cao và được tặng giải thưởng Luận văn xuất sắc của Hội các nhà toán học nữ (AWM). Một trong các kết quả tốt nhất của cô là chứng minh được một phiên bản yếu hơn của giả thuyết Kahn-Kalai, trong đó thiết lập mối quan hệ giữa giá trị ngưỡng với một giá trị “ngưỡng kì vọng một phần”.
“Ngưỡng kì vọng một phần” là khái niệm xuất hiện trong một công trình năm 2010 của GS. Michel Talagrand, trong đó đề xuất một loạt các giả thuyết quan trọng. TS. Park cùng cộng sự đã chứng minh được một trong các giả thuyết đó. Đây được coi là một bước tiến lớn trên con đường chinh phục giả thuyết Kahn-Kalai. Tuy nhiên, phần việc còn lại để chứng minh toàn bộ giả thuyết được GS. Kahn, trong đó phải tìm mối liên hệ giữa “ngưỡng kì vọng” và “ngưỡng kì vọng một phần”, được đánh giá là rất khó khăn. Các kĩ thuật và khái niệm dùng trong chứng minh cũ không sử dụng lại cho “ngưỡng kì vọng”, mà lời giải thực sự lại được tìm ra từ một hướng tiếp cận khác.
Trong Toán học đôi khi chúng ta bắt gặp những điều kì diệu. Một bài toán rất phức tạp và có độ tổng quát hóa cao lại có thể có một lời giải tường minh hết sức gọn gàng. Chứng minh cho giả thuyết Kahn-Kalai của Phạm Tuấn Huy và Jinyoung Park là một điều kì diệu như vậy.
Khi Phạm Tuấn Huy gặp TS. Park tại ĐH Stanford, họ nhanh chóng kết nối với nhau và cùng làm việc để giải quyết một số giả thuyết khác của GS. Talagrand về cực đại của các quá trình ngẫu nhiên. Định hướng nghiên cứu là phát triển một số kĩ thuật thừa hưởng từ các công trình đột phá về “Giả thuyết Hoa hướng dương”. Đây là một giả thuyết rất lâu đời do huyền thoại Paul Erdos và Richard Rado đề xuất, về các điều kiện để một hệ tập hợp có thể được sắp xếp theo mô hình cánh hoa hướng dương. Các kĩ thuật này cho phép xây dựng một hệ thống bằng một chuỗi các bước lặp đi lặp lại, mỗi bước chọn một phần nhỏ của hệ thống. Sau một thời gian dài với rất nhiều nỗ lực để tổng quát hóa và nhiều lần thất bại, Huy và Park đã phát triển được một cụm ý tưởng mới để có thể giải quyết các giả thuyết của Talagrand. “Phân mảnh tối tiểu”, một trong số các ý tưởng đó, tình cờ lại là chìa khóa để có thể chứng mình giả thuyết Kahn – Kalai.
Trong một chuyến đi thăm bạn tại Berkeley, khi đang suy nghĩ về việc dùng khái niệm này cho các ứng dụng khác, Huy tình cờ thấy được sự vai trò của Phân mảnh tối tiểu trong chứng minh của cả giả thuyết Talagrand và giả thuyết Kahn-Kalai. Nó sẽ giúp mã hóa phần đặc trưng nhất của các cấu trúc mong muốn, qua đó giúp cho việc xác định xem các hệ ngẫu nhiên có chứa cấu trúc mong muốn hay không. Thay vì cố gắng xác định xem mật độ của hệ thống bao nhiêu là đủ cho cấu trúc mong muốn xuất hiện (ví dụ như có bao nhiêu đường bay là đủ trong ví dụ của chúng ta), Huy xây dựng một hệ thống con bằng một loạt các phân mảnh tối tiểu (để giữ cho mật độ của hệ thống ở mức thấp) sao cho hệ thống này sẽ chứa cấu trúc mong muốn. Với ý tưởng đột phá này thì chứng minh cho giả thuyết Kahn – Kalai không phải quá phức tạp về mặt kĩ thuật. Ý tưởng cũng giúp nhóm của Huy chứng minh được đầy đủ giả thuyết của Talagrand. Điều đặc biệt ở đây là nếu Huy không theo đuổi nghiên cứu về giả thuyết Talagrand thì sẽ không có ý tưởng để chứng mình giả thuyết Kahn – Kalai. Điều này cũng cho thấy sự đồng nhất của Toán học đỉnh cao khi các ý tưởng đột phá được ứng dụng vào nhiều bài toán và thể hiện một nguyên tắc vận hành chung ẩn giấu dưới các vỏ bọc khác nhau.
Đêm hôm đó Huy đã thức trắng để hoàn thiện chứng minh của giả thuyết Kahn – Kalai. Trong hai ngày tiếp theo, Huy trình bày chứng minh với thầy hướng dẫn và cộng sự. Tất cả mọi người đều ngạc nhiên và gần như không tin vào mắt mình khi thấy một lời giải tường minh và đẹp đẽ như vậy. Cả nhóm lập tức bắt tay vào viết và hoàn thiện bài báo chỉ trong vài ngày. Bài báo chỉ dài vỏn vẹn có sáu trang nhưng ngay lập tức gây tiếng vang lớn trong cộng đồng Toán học thế giới. Các GS. Kahn, Kalai, và Talagrand đều rất vui mừng và chúc mừng thành công của nhóm.
Đối với Huy, thành công này chỉ là bước khởi đầu của một chặng đường phía trước, khi kết quả này sẽ mở ra rất nhiều hướng nghiên cứu mới để tối ưu hóa và rút ngắn khoảng cách giữa giá trị ngưỡng và ngưỡng kì vọng. Huy cũng có kế hoạch tiếp tục theo đuổi nghiên cứu các giả thuyết quan trọng khác trong chuyên ngành và săn tìm các khám phá bất ngờ mới. □
——
*Đại học Fulbright
Nguồn tham khảo:
– Phỏng vấn của quĩ Two Sigma: https://www.twosigma.com/articles/the-fellowship-forum-meet-the-two-sigma-fellows/
– Bài báo của Quanta Magazine: https://www.quantamagazine.org/elegant-six-page-proof-reveals-the-emergence-of-random-structure-20220425/
