Giới thiệu
Vào giữa tháng XNUMX, Justin Gilmer đã bay từ California đến New York để dự đám cưới của một người bạn. Khi ở Bờ biển phía Đông, ông đã đến thăm cố vấn cũ của mình, Michael Saks, một nhà toán học tại Đại học Rutgers, nơi Gilmer đã nhận bằng tiến sĩ bảy năm trước đó.
Saks và Gilmer gặp nhau trong bữa trưa, nhưng họ không nói về toán học. Trên thực tế, Gilmer đã không suy nghĩ nghiêm túc về toán học kể từ khi kết thúc học tại Rutgers vào năm 2015. Đó là lúc anh quyết định không theo đuổi sự nghiệp học thuật mà thay vào đó bắt đầu tự học lập trình. Khi anh ấy và Saks ăn, Gilmer nói với người cố vấn cũ của anh ấy về công việc của anh ấy tại Google, nơi anh ấy làm việc về máy học và trí tuệ nhân tạo.
Trời nắng vào ngày Gilmer đến thăm Rutgers. Khi đi loanh quanh, anh ấy nhớ lại rằng vào năm 2013, anh ấy đã dành phần lớn thời gian của một năm để đi bộ trên những con đường trong khuôn viên đó, suy nghĩ về một vấn đề gọi là phỏng đoán đóng của liên đoàn. Đó là một sự kiên định, mặc dù không có kết quả: Với tất cả nỗ lực của mình, Gilmer chỉ thành công trong việc dạy cho bản thân tại sao bài toán có vẻ đơn giản về các tập hợp số lại khó giải đến vậy.
“Tôi nghĩ nhiều người nghĩ về vấn đề này cho đến khi họ hài lòng rằng họ hiểu tại sao nó khó. Có lẽ tôi đã dành nhiều thời gian cho nó hơn hầu hết mọi người,” Gilmer nói.
Sau chuyến thăm vào tháng 16, một điều bất ngờ đã xảy ra: Anh ấy có một ý tưởng mới. Gilmer bắt đầu nghĩ về cách áp dụng các kỹ thuật từ lý thuyết thông tin để giải quyết phỏng đoán liên-đóng. Anh ấy theo đuổi ý tưởng này trong một tháng, lúc nào cũng nghĩ rằng nó sẽ thất bại. Nhưng thay vào đó, con đường dẫn đến một bằng chứng vẫn tiếp tục mở ra. Cuối cùng, vào ngày XNUMX tháng XNUMX, ông đã đăng một kết quả đầu tiên thuộc loại này điều đó giúp các nhà toán học tiến gần hơn đến việc chứng minh phỏng đoán đầy đủ.
Bài báo đặt ra một loạt các công việc tiếp theo. Các nhà toán học tại Đại học Oxford, Viện Công nghệ Massachusetts và Viện Nghiên cứu Cao cấp, trong số các tổ chức khác, đã nhanh chóng xây dựng dựa trên các phương pháp mới lạ của Gilmer. Nhưng trước khi làm vậy, họ đã tự hỏi một câu hỏi: Anh chàng này là ai?
Một nửa đầy
Phỏng đoán hợp-đóng là về tập hợp các số được gọi là tập hợp, chẳng hạn như {1, 2} và {2, 3, 4}. Bạn có thể thực hiện các thao tác trên các tập hợp, bao gồm lấy hợp của chúng, nghĩa là kết hợp chúng. Ví dụ: hợp của {1, 2} và {2, 3, 4} là {1, 2, 3, 4}.
Một tập hợp hoặc họ các tập hợp được coi là "hợp đóng" nếu hợp của hai tập hợp bất kỳ trong họ bằng bất kỳ tập hợp hiện có nào trong họ. Ví dụ, xét họ bốn tập hợp này:
{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.
Kết hợp bất kỳ cặp nào và bạn sẽ có được một bộ đã có trong gia đình, làm cho liên kết gia đình trở nên khép kín.
Các nhà toán học đã nói chuyện về các phiên bản của phỏng đoán liên đóng từ những năm 1960, nhưng nó đã nhận được tuyên bố chính thức đầu tiên vào năm 1979, trong một bài báo của Peter Frankl, một nhà toán học người Hungary di cư sang Nhật Bản vào những năm 1980 và coi biểu diễn đường phố là một trong những mục tiêu theo đuổi của mình.
Frankl phỏng đoán rằng nếu một họ các tập hợp là tập hợp đóng, nó phải có ít nhất một phần tử (hoặc số) xuất hiện trong ít nhất một nửa tập hợp. Đó là một ngưỡng tự nhiên vì hai lý do.
Đầu tiên, có sẵn các ví dụ về các họ đóng liên hiệp trong đó tất cả các phần tử xuất hiện trong chính xác 50% các tập hợp. Ví dụ, giống như tất cả các bộ khác nhau mà bạn có thể tạo từ các số từ 1 đến 10. Có 1,024 tập hợp như vậy, chúng tạo thành một họ liên-đóng, và mỗi phần tử trong số 10 phần tử xuất hiện trong 512 phần tử trong số đó. Và thứ hai, vào thời điểm Frankl đưa ra phỏng đoán, chưa ai từng đưa ra một ví dụ nào về một gia đình khép kín liên minh mà trong đó phỏng đoán không đúng.
Vì vậy, 50% có vẻ như là dự đoán đúng.
Điều đó không có nghĩa là nó dễ dàng để chứng minh. Trong những năm kể từ bài báo của Frankl, đã có rất ít kết quả. Trước công trình của Gilmer, những bài báo đó chỉ quản lý để thiết lập các ngưỡng thay đổi theo số lượng tập hợp trong họ (trái ngược với ngưỡng 50% giống nhau cho các họ tập hợp ở mọi quy mô).
“Có vẻ như nó sẽ dễ dàng, và nó tương tự như rất nhiều vấn đề dễ dàng, nhưng nó đã chống lại các cuộc tấn công,” nói Sẽ Sawin của Đại học Columbia.
Sự thiếu tiến bộ phản ánh cả bản chất phức tạp của vấn đề và thực tế là nhiều nhà toán học không muốn nghĩ về nó; họ lo lắng rằng họ sẽ mất nhiều năm sự nghiệp để theo đuổi một vấn đề khó hiểu không thể giải quyết được. Gilmer nhớ lại một ngày vào năm 2013 khi anh đến văn phòng của Saks và đưa ra phỏng đoán về sự đóng cửa của công đoàn. Cố vấn của anh ấy - người trong quá khứ đã tự mình vật lộn với vấn đề này - suýt nữa đã ném anh ấy ra khỏi phòng.
“Mike nói, 'Justin, bạn sẽ khiến tôi phải suy nghĩ lại về vấn đề này và tôi không muốn làm điều đó',” Gilmer nói.
Một cái nhìn sâu sắc về sự không chắc chắn
Sau chuyến thăm Rutgers, Gilmer suy nghĩ về vấn đề này trong đầu, cố gắng hiểu tại sao nó lại khó đến vậy. Anh tự nhắc mình bằng một sự thật cơ bản: Nếu bạn có một gia đình gồm 100 nhóm, thì có 4,950 cách khác nhau để chọn hai nhóm và kết hợp chúng. Sau đó, ông tự hỏi: Làm thế nào mà 4,950 tổ hợp khác nhau lại có thể ánh xạ trở lại chỉ 100 tập hợp nếu không có phần tử nào xuất hiện trong các tổ hợp đó với ít nhất một tần suất nào đó?
Ngay cả vào thời điểm đó, anh ấy đang trên đường đi đến một bằng chứng, mặc dù anh ấy chưa biết điều đó. Các kỹ thuật từ lý thuyết thông tin, cung cấp một cách suy nghĩ chặt chẽ về những gì sẽ xảy ra khi bạn kéo ngẫu nhiên một cặp vật thể, sẽ đưa anh ta đến đó.
Lý thuyết thông tin được phát triển vào nửa đầu thế kỷ 20, nổi tiếng nhất với bài báo năm 1948 của Claude Shannon, “Một lý thuyết toán học về truyền thông.” Bài báo đã cung cấp một cách chính xác để tính toán lượng thông tin cần thiết để gửi một thông điệp, dựa trên mức độ không chắc chắn xung quanh nội dung chính xác của thông điệp. Liên kết này - giữa thông tin và sự không chắc chắn - là cái nhìn sâu sắc, cơ bản đáng chú ý của Shannon.
Lấy một ví dụ về đồ chơi, hãy tưởng tượng tôi tung một đồng xu năm lần và gửi chuỗi kết quả cho bạn. Nếu đó là một đồng xu bình thường, nó cần năm bit thông tin để truyền đi. Nhưng nếu đó là một đồng xu được nạp — chẳng hạn, 99% khả năng là mặt ngửa — thì mất ít hơn rất nhiều. Ví dụ: chúng ta có thể đồng ý trước rằng tôi sẽ gửi cho bạn 1 (một chút thông tin) nếu đồng xu được nạp về mặt ngửa cả năm lần, điều này rất có khả năng xảy ra. Kết quả của một lần tung đồng xu công bằng sẽ gây nhiều bất ngờ hơn so với kết quả của một lần tung đồng xu thiên vị, và do đó sẽ có nhiều thông tin hơn.
Suy nghĩ tương tự áp dụng cho thông tin chứa trong các bộ số. Nếu tôi có một họ các tập hợp đóng - giả sử 1,024 tập hợp được tạo từ các số từ 1 đến 10 - thì tôi có thể chọn ngẫu nhiên hai tập hợp. Sau đó, tôi có thể truyền đạt các yếu tố của từng bộ cho bạn. Lượng thông tin cần thiết để gửi tin nhắn đó phản ánh mức độ không chắc chắn xung quanh những phần tử đó là gì: Ví dụ: có 50% khả năng phần tử đầu tiên trong tập hợp đầu tiên là 1 (vì 1 xuất hiện trong một nửa tập hợp trong gia đình), cũng như có 50% khả năng kết quả đầu tiên trong một chuỗi tung đồng xu công bằng là mặt ngửa.
Lý thuyết thông tin thường xuất hiện trong tổ hợp, một lĩnh vực toán học liên quan đến việc đếm các đối tượng, đó là lĩnh vực mà Gilmer đã nghiên cứu khi còn là một sinh viên cao học. Nhưng khi anh bay về California, anh lo lắng rằng cách anh nghĩ để kết nối lý thuyết thông tin với phỏng đoán về công thức đóng là cái nhìn ngây thơ của một người nghiệp dư: Chắc chắn các nhà toán học đang làm việc đã bắt gặp vật thể sáng bóng này trước đây và coi nó là vàng của kẻ ngốc. .
Gilmer nói: “Thành thật mà nói, tôi hơi ngạc nhiên khi không ai nghĩ đến điều này trước đây. “Nhưng có lẽ tôi không nên ngạc nhiên, vì bản thân tôi đã nghĩ về nó trong một năm và tôi biết lý thuyết thông tin.”
Nhiều khả năng hơn không
Gilmer đã giải quyết vấn đề vào ban đêm, sau khi kết thúc công việc của mình tại Google và vào các ngày cuối tuần trong suốt nửa cuối tháng XNUMX và đầu tháng XNUMX. Ông được khuyến khích bởi những ý tưởng mà một nhóm các nhà toán học đã khám phá nhiều năm trước đó trong một cộng tác cởi mở trên blog của một nhà toán học lỗi lạc tên là Tim Gowers. Anh ấy cũng làm việc với một cuốn sách giáo khoa bên cạnh để có thể tra cứu các công thức mà anh ấy đã quên.
“Bạn sẽ nghĩ ai đó đạt được kết quả tuyệt vời thì không cần phải tham khảo Chương 2 của Các yếu tố của lý thuyết thông tin, nhưng tôi đã làm,” Gilmer nói.
Chiến lược của Gilmer là tưởng tượng một họ khép kín liên hợp trong đó không có phần tử nào xuất hiện dù chỉ 1% trong tất cả các tập hợp — một phản ví dụ mà nếu nó thực sự tồn tại, sẽ làm sai lệch phỏng đoán của Frankl.
Giả sử bạn chọn ngẫu nhiên hai tập hợp, A và B, từ họ này và xem xét các phần tử có thể có trong các tập hợp đó, từng phần tử một. Bây giờ hãy hỏi: Tỷ lệ cược mà tập hợp A chứa số 1 là bao nhiêu? Và đặt B? Vì mọi phần tử đều có ít hơn 1% cơ hội xuất hiện trong bất kỳ tập hợp nhất định nào, nên bạn sẽ không mong đợi A hoặc B chứa 1. Điều đó có nghĩa là sẽ có ít bất ngờ — và ít thông tin thu được — nếu bạn biết điều đó trên thực tế cũng không làm.
Tiếp theo, hãy nghĩ về khả năng hợp của A và B chứa 1. Điều đó vẫn khó xảy ra, nhưng có nhiều khả năng hơn là khả năng nó xuất hiện trong một trong các tập hợp riêng lẻ. Đó là tổng khả năng nó xuất hiện ở A và khả năng nó xuất hiện ở B trừ đi khả năng nó xuất hiện ở cả hai. Vì vậy, có thể chỉ dưới 2%.
Điều này vẫn còn thấp, nhưng nó gần với một đề xuất 50-50. Điều đó có nghĩa là cần nhiều thông tin hơn để chia sẻ kết quả. Nói cách khác, nếu có một họ hợp-đóng trong đó không có phần tử nào xuất hiện trong ít nhất 1% của tất cả các tập hợp, thì sẽ có nhiều thông tin hơn trong hợp của hai tập hợp hơn là trong chính một trong hai tập hợp.
“Ý tưởng tiết lộ mọi thứ theo từng yếu tố và xem xét lượng thông tin bạn học được là cực kỳ thông minh. Đó là ý chính của bằng chứng,” nói Ryan Alweiss của Đại học Princeton.
Tại thời điểm này, Gilmer bắt đầu tiếp cận phỏng đoán của Frankl. Đó là bởi vì thật dễ dàng để chứng minh rằng trong một họ hợp đóng, hợp của hai tập hợp nhất thiết phải chứa ít thông tin hơn chính các tập hợp đó — không nhiều hơn.
Để hiểu tại sao, hãy nghĩ về họ hợp-đóng đó chứa 1,024 tập hợp khác nhau mà bạn có thể tạo từ các số từ 1 đến 10. Nếu bạn chọn ngẫu nhiên hai trong số các tập hợp đó, trung bình bạn sẽ có các tập hợp chứa năm phần tử. (Trong số 1,024 tập hợp đó, 252 tập hợp chứa năm phần tử, đây là kích thước tập hợp phổ biến nhất.) Bạn cũng có khả năng kết thúc với một tổ hợp chứa khoảng bảy phần tử. Nhưng chỉ có 120 cách khác nhau để tạo các tập hợp có bảy phần tử.
Vấn đề là, có nhiều điều không chắc chắn về nội dung của hai tập hợp được chọn ngẫu nhiên hơn là về sự kết hợp của chúng. Sự kết hợp nghiêng về các tập hợp lớn hơn với nhiều phần tử hơn, trong đó có ít khả năng hơn. Khi bạn kết hợp hai tập hợp trong một họ kết hợp khép kín, bạn gần như biết mình sẽ nhận được gì — giống như khi bạn tung một đồng xu bị thiên vị — có nghĩa là tập hợp chứa ít thông tin hơn so với các tập hợp mà nó bao gồm.
Với điều đó, Gilmer đã có một bằng chứng. Anh ấy biết nếu không có phần tử nào xuất hiện trong dù chỉ 1% số tập hợp, liên minh buộc phải chứa nhiều thông tin hơn. Nhưng công đoàn phải chứa ít thông tin hơn. Do đó phải có ít nhất một phần tử xuất hiện trong ít nhất 1% số tập hợp.
Đẩy lên 50
Khi Gilmer đăng bằng chứng của mình vào ngày 16 tháng 38, anh ấy đã đính kèm một ghi chú rằng anh ấy nghĩ rằng có thể sử dụng phương pháp của mình để tiến gần hơn đến bằng chứng của phỏng đoán đầy đủ, có khả năng nâng ngưỡng lên XNUMX%.
Năm ngày sau, số ba khác nhau các nhóm của các nhà toán học đã đăng các bài báo cách nhau vài giờ dựa trên công việc của Gilmer để làm điều đó. thêm vào giấy tờ sau, nhưng vụ nổ ban đầu dường như đã đưa các phương pháp của Gilmer đi xa nhất có thể; đạt đến 50% có thể sẽ có thêm những ý tưởng mới.
Tuy nhiên, đối với một số tác giả của các bài báo tiếp theo, việc đạt được 38% là tương đối dễ dàng và họ tự hỏi tại sao Gilmer không tự mình làm điều đó. Lời giải thích đơn giản nhất hóa ra lại đúng: Sau hơn nửa thập kỷ không làm toán, Gilmer không biết cách thực hiện một số công việc phân tích kỹ thuật cần thiết để thành công.
Gilmer nói: “Tôi hơi mệt mỏi và thành thật mà nói, tôi đã bị mắc kẹt. “Nhưng tôi háo hức muốn xem cộng đồng sẽ đưa nó đến đâu.”
Tuy nhiên, Gilmer cho rằng chính những hoàn cảnh khiến ông không thể hành nghề có lẽ đã khiến cho bằng chứng của ông trở nên khả thi ngay từ đầu.
“Đó là cách duy nhất tôi có thể giải thích tại sao tôi đã suy nghĩ về bài toán trong một năm ở trường cao học mà không đạt được tiến bộ nào, tôi đã bỏ toán trong sáu năm, sau đó quay lại bài toán và tạo ra bước đột phá này,” anh nói. “Tôi không biết làm thế nào để giải thích nó ngoài việc học máy đã làm sai lệch suy nghĩ của tôi.”
Điều chỉnh: 3 Tháng một, 2023
Tiêu đề ban đầu gọi Gilmer là “kỹ sư của Google”. Trên thực tế, anh ấy là một nhà nghiên cứu.
