Vào Chủ nhật, ngày 5 tháng XNUMX, Olof Sisask và Thomas Bloom nhận được một email chứa đựng bước đột phá tuyệt vời về vấn đề lớn nhất chưa được giải quyết trong lĩnh vực của họ. Zander Kelley, một sinh viên tốt nghiệp tại Đại học Illinois, Urbana-Champaign, đã gửi Sisask và Bloom một bài báo anh ấy đã viết với Raghu Meka của Đại học California, Los Angeles. Cả Kelley và Meka đều là những nhà khoa học máy tính, một thế giới trí tuệ khác với tổ hợp phụ gia mà Sisask và Bloom nghiên cứu.

“Đầu óc tôi choáng váng. Giống như, đợi đã, họ có thực sự làm điều này không? Sisask, một giảng viên tại Đại học Stockholm cho biết. Kelley và Meka, những người bên ngoài lĩnh vực tổ hợp, cho biết họ đã tìm thấy một giới hạn mới — và thấp hơn đáng kể — về kích thước của một tập hợp các số nguyên trong đó không có ba số nào cách đều nhau (loại trừ các tổ hợp như 3, 8 và 13 hoặc 101, 201 và 301).

Yêu cầu của Kelley và Meka đã phá vỡ kỷ lục trước đó, đạt năm 2020 của Sisask và Bloom, một nhà nghiên cứu tại Đại học Oxford. Ben Green, một đồng nghiệp của Bloom's tại Oxford, cho biết: “Công trình của Bloom và Sisask - công việc rất mạnh mẽ - nó thực sự gây ấn tượng là cực kỳ khó cải thiện. "Nó trông rất bị mắc kẹt ở nơi nó đã được."

Mặc dù cả Bloom và Sisask đều có những vấn đề cấp bách khác cần giải quyết vào thời điểm họ nhận được email - Bloom vừa nhận nuôi một chú chó con, trong khi Sisask đang chuyển nhà - họ nhanh chóng bắt tay vào công việc xác minh bài báo mới.

Trong vài ngày, Bloom và Sisask tin rằng bằng chứng mới là chính xác. Sisask gọi đó là “kết quả lớn nhất trong khu vực trong 20 năm.” Mong muốn người khác đánh giá cao ý tưởng của Kelley và Meka, họ đã soạn thảo báo cáo giải thích bằng chứng theo thuật ngữ quen thuộc hơn với các nhà toán học.

Meka cho biết phản hồi từ cộng đồng “tích cực hơn tôi nghĩ. Thật tuyệt vời khi thấy tất cả các phản hồi.”

Tiến độ kéo dài

Dãy các số cách đều nhau mà Kelley và Meka tìm cách tránh được gọi là cấp số cộng. Chúng có thể tồn tại mãi mãi hoặc chỉ chứa một vài thuật ngữ. Kelley và Meka tập trung vào các cấp số chỉ gồm ba số, theo một hướng nghiên cứu thường bắt nguồn từ một giấy 1936 của Paul Erdős và Paul Turan.

Erdős và Turan muốn biết có bao nhiêu số nhỏ hơn trần nhà N có thể được đưa vào một tập hợp mà không cần lập bất kỳ một cấp số cộng ba số hạng nào. N có thể là 1,000, 1 triệu hoặc một số khổng lồ không thể tưởng tượng được. Họ phỏng đoán rằng như N ngày càng lớn hơn, một tập hợp không có lũy tiến ba kỳ hạn sẽ trở nên vô cùng thưa thớt. Tạo một bộ như vậy sẽ giống như thu thập giày trong khi nhấn mạnh rằng không có hai đôi nào có cùng màu. Có lẽ bạn có thể tiếp tục mãi mãi, nhưng khi bộ sưu tập của bạn lớn hơn, bạn sẽ thấy mình thêm vào nó với tốc độ ngày càng chậm hơn.

“Có một số cấu trúc sẽ xuất hiện trong bối cảnh, bất kể bạn chọn bối cảnh như thế nào,” Meka giải thích. “Bạn thực sự cần một bộ lớn đến mức nào để đảm bảo rằng bạn có cấu trúc này trong đó?”

Năm 1946, Felix Behrend đã tìm ra cách xây dựng các tập hợp của các số từ 1 đến N mà không tạo ra bất kỳ lũy tiến ba kỳ nào. Phương pháp của anh ấy dẫn đến các tập hợp trở nên lớn hơn khi N đã làm, nhưng đau đớn từ từ. Khi N là 100,000, tập hợp của Behrend chỉ chứa 171 phần tử. Khi N là 1 triệu, tập hợp của anh ấy có 586 số — ít hơn 0.06% so với các số từ 1 đến 1 triệu.

Các tập hợp của Behrend đã mang lại cho các nhà toán học một nền tảng để làm việc: Tập hợp lớn nhất không có cấp số ba kỳ hạn ít nhất phải lớn bằng tập hợp của Behrend. Năm 1953, Klaus Roth cung cấp một trần, tìm một ngưỡng vượt qua mà một tập hợp chắc chắn phải chứa một cấp số ba.

Roth đã chứng minh phỏng đoán của Erdős và Turan bằng cách chỉ ra rằng N lớn hơn, một tập hợp không có lũy tiến ba kỳ hạn sẽ bao gồm một phần nhỏ hơn bao giờ hết của các số từ 1 đến N. Nhưng mức trần của Roth cách xa mức sàn của Behrend. Behrend đã chỉ ra rằng 0.06% phần tử từ 1 đến 1 triệu có thể nằm gọn trong một tập hợp không lũy ​​tiến. Mặc dù công thức của Roth khó tính toán chính xác, nhưng nó không ở mức thấp như vậy - một ước tính sơ bộ cho rằng nó giới hạn tỷ lệ phần trăm ở mức khoảng 40%.

Nhưng nổi bật hơn khoảng cách cụ thể đó là hành vi tổng thể của hai công thức. Vẽ phân số của các phần tử giữa 1 và N mà mỗi công thức đại diện, và bạn sẽ thấy số Behrend nhanh chóng thu nhỏ về XNUMX khi N mọc. Mặt khác, phân số của Roth trượt về XNUMX, nhưng chậm và nhẹ nhàng. Hai đường cong có hình dạng rất khác nhau và tỷ lệ thực sự của các phần tử nằm trong một tập hợp không có cấp số cộng, theo như các nhà toán học đã biết, có thể nằm ở bất kỳ đâu giữa chúng.

Bắt đầu từ những năm 1980, “có một chuỗi dài, theo nhận thức muộn màng, những cải tiến khá gia tăng bởi một số lượng lớn các nhà toán học thực sự nổi tiếng,” Green nói. Thỉnh thoảng, ai đó sẽ đẩy giới hạn trên của Roth xuống một hoặc hai sợi tóc, và cuối cùng nó giảm xuống đáng kể. Ngược lại, giới hạn dưới của Behrend không nhúc nhích trong nhiều thập kỷ. Bloom cho biết các nhà toán học bắt đầu nghĩ rằng Behrend có thể không còn xa câu trả lời thực sự.

Cho đến khi bài báo của Kelley và Meka xuất hiện vào đầu năm 2023, kích thước tối đa của một tập hợp không lũy ​​tiến được viết từ bên dưới theo công thức của Behrend và từ bên trên theo công thức của Bloom và Sisask. Bài báo của Bloom và Sisask từ tháng 2020 năm XNUMX đã vượt qua ngưỡng “logarit” quan trọng bằng cách chỉ ra rằng một tập hợp không lũy ​​tiến phải có ít hơn đáng kể N/(nhật ký N) phần tử. Nhưng kết quả của họ vẫn cao hơn Behrend. Giới hạn trên mới của Kelley và Meka gần hơn rất nhiều so với giới hạn do Behrend đặt ra.

Terence Tao, một nhà toán học nổi tiếng tại UCLA, cho biết: “Meka và Kelley gần như đã đi tắt đón đầu tất cả những tiến bộ gia tăng này.

Công thức của họ gần giống như của Behrend, chỉ có một số thông số được điều chỉnh. BẰNG N tiến đến vô cùng, đồ thị của công thức Kelley và Meka cuối cùng sẽ ổn định thành một đường cong giống như đường cong Behrend. Bloom nói: “Trước đây, bất kỳ giới hạn nào của hình dạng đó dường như là một giấc mơ không thể thực hiện được.

Green nói: “Tôi thực sự khá sửng sốt khi họ đã có một sự cải tiến như vậy.

Một chiến thuật khác

 Mặc dù Kelley và Meka chưa bao giờ hoàn toàn mạo hiểm nghiên cứu toán học thuần túy trước đây, nhưng cấp số cộng đã quen thuộc với họ khi họ bắt đầu. Nói chung, các nhà khoa học máy tính “đang khao khát tìm kiếm các kỹ thuật có thể giải quyết các vấn đề của chúng ta,” Kelley nói. Các công cụ trước đây được sử dụng để nghiên cứu kích thước của một tập hợp không lũy ​​tiến đã được sử dụng rộng rãi trong lĩnh vực khoa học máy tính của lý thuyết phức tạp. Vấn đề thu hẹp kích thước của một tập hợp như vậy được các nhà lý thuyết về độ phức tạp biết đến như một ví dụ điển hình của việc áp dụng các kỹ thuật thăm dò cấu trúc bên trong của các tập hợp.

Vào cuối năm 2021, Kelley và Meka đang phân tích khả năng giành chiến thắng của một nhóm người chơi trong một trò chơi hợp tác nhất định, một loại bài toán khoa học máy tính tiêu chuẩn. Họ nhận ra rằng các kỹ thuật từ nghiên cứu về kích thước của các tập hợp lũy tiến có thể hữu ích. Nhưng họ thấy việc nghiên cứu trực tiếp những kỹ thuật đó dễ dàng hơn là áp dụng chúng vào trò chơi hợp tác. Kelley nói: “Ý tưởng tốt nhất của tôi về cách đạt được tiến bộ trong vấn đề này [là] thực sự cải thiện chính công cụ đó chứ không phải sử dụng nó theo cách thông minh hơn.

“Tại một thời điểm nào đó, chúng tôi quyết định trực tiếp giải quyết vấn đề này,” Meka nhớ lại. Sáu tháng sau, hai nhà nghiên cứu đã tìm ra chiến lược của họ và chỉ cần tìm ra cách áp dụng phương pháp của họ cho vấn đề hiện tại.

Để xem làm thế nào họ đạt đến giới hạn trên mới của mình, hãy lấy bất kỳ bộ số nào trong khoảng từ 1 đến N. Gọi nó đi A. Mật độ của A là tỷ lệ phần trăm của các số từ 1 đến N mà nó bao gồm. Vì có rất nhiều cấp số cộng có thể giữa 1 và N, nếu bạn không chọn các phần tử của A cẩn thận, bất kỳ A với mật độ cao sẽ có khả năng chứa rất nhiều cấp số cộng.

Trong bằng chứng của họ, Kelley và Meka tưởng tượng rằng A có ít hoặc không có cấp số cộng, và họ đã cố gắng tìm ra các hệ quả. Nếu như A đủ dày đặc, họ đã chỉ ra rằng sự vắng mặt của sự tiến triển đòi hỏi một mức độ cấu trúc bên trong A điều đó chắc chắn sẽ dẫn đến một mâu thuẫn, có nghĩa là A sau tất cả, phải chứa ít nhất một tiến trình.

Để hiểu cấu trúc đó, họ đã xem xét bộ A + A, bao gồm tất cả các số được tạo bằng cách cộng hai phần tử của A. Họ nhận thấy rằng nếu A chứa tương đối ít cấp số cộng, điều này ngụ ý sự dư thừa giữa các phần tử của A + A: Các cặp số khác nhau từ A thường cộng lại thành một số.

Mật độ có thể được xác định không chỉ so với tất cả các số nguyên từ 1 đến N nhưng so với một số tập hợp con - chỉ nói các số nguyên chẵn trong khoảng đó hoặc chỉ các bội số của 3. Kelley và Meka đã sử dụng các phần dư thừa trong A + A để tìm một tập hợp con của các số nguyên trong đó các phần tử của A đặc biệt phổ biến.

Ví dụ: nếu A chứa nhiều bội số của 3 một cách không cân xứng, thì Kelley và Meka sẽ tập trung vào phần chứa bội số của 3. Họ lặp đi lặp lại chiến lược này nhiều lần. Mỗi lần họ tìm thấy các tập hợp con nhỏ hơn và nhỏ hơn của các số nguyên, trong đó Amật độ của nó sẽ tiếp tục phát triển và phát triển. Ví dụ, A có thể chứa 10% số nguyên từ 1 đến N, 15% bội số của 3 trong khoảng đó và 25% bội số chẵn của 3.

Một cái gì đó thú vị xảy ra khi A là lớn. Nếu quy trình được lặp lại, mật độ của A trên một số tập hợp con vượt quá 100%. Điều đó, tất nhiên, là không thể. A có thể chứa, chẳng hạn, tất cả bội số của 24, nhưng nó không thể chứa nhiều hơn tất cả chúng. Nghịch lý này chỉ phát sinh nếu A đủ lớn để bắt đầu, nhưng khi nó xảy ra, điều đó có nghĩa là giả định rằng A không chứa bất kỳ cấp số cộng nào chắc chắn đã sai.

Đó là một “cuộc tranh luận đôi bên cùng có lợi,” khi A lớn, Meka nói. Hoặc A bao gồm rất nhiều cấp số cộng, hoặc có rất nhiều dư thừa trong A + A — trong trường hợp đó họ có thể sử dụng quy trình tìm tập hợp con (được gọi là “chiến lược gia tăng mật độ”) để chỉ ra rằng một cấp số phải xuất hiện trong A. Mặc dù chiến lược gia tăng mật độ là một kế hoạch chi tiết đã lỗi thời trong lĩnh vực này, Kelley và Meka đã cố gắng làm cho nó hoạt động với quy mô nhỏ hơn. Ahơn bao giờ hết. Cùng với đó, họ đã phát hiện ra một mức trần mới cho kích thước của một tập hợp không lũy ​​tiến.

Kelley và Meka đã xây dựng một sự kết hợp ý tưởng độc đáo từ bản thiết kế gia tăng mật độ. Thay vì nghĩ ra một khuôn khổ hoàn toàn mới, họ đã suy nghĩ lại cách họ tìm thấy tập hợp con dày đặc của mình. Đối với điều này, họ đã sử dụng một kỹ thuật mà họ gọi là “sàng lọc”, bao gồm dịch chuyển tập hợp của họ theo một lượng không đổi, cắt tập hợp đó với chính nó và lặp lại quá trình này nhiều lần. Những gì còn lại, sau nhiều vòng giao nhau, là một tập hợp có cấu trúc cao với các thuộc tính có thể dự đoán được. Mặc dù phương pháp chọn lọc đã được sử dụng trong các bài báo khác, nhưng nó chưa bao giờ được thử đối với bài toán lũy tiến ba kỳ.

Nhìn lại

Kelley và Meka đã giảm giới hạn kích thước của một bộ không có lũy tiến xuống một mức đáng kinh ngạc bằng cách đưa các công cụ bị bỏ quên như sàng lọc vào các phương pháp truyền thống. “Kelley và Meka đã cho chúng tôi thấy rằng bằng cách nào đó những kỹ thuật này, vốn đang được công khai, mạnh mẽ hơn nhiều so với những gì chúng tôi nghi ngờ,” Bloom nói. Anh ấy nói thêm về tính hiệu quả mới phát hiện của những công cụ này, “chúng ta phải quay lại và xem xét lại mọi thứ.”

Chiến lược gia tăng mật độ lần đầu tiên xuất hiện trong bài báo của Roth cách đây 70 năm và đã được sử dụng trong hầu hết các bài báo về cấp số cộng kể từ đó. Green rất ngạc nhiên khi khuôn khổ này có thể được sử dụng để chứng minh một giới hạn thấp như của Kelley và Meka. “Tôi nghĩ rằng sẽ cần một cái gì đó hoàn toàn, hoàn toàn khác biệt,” anh nói.

Kelley rất hào hứng tiếp tục lấn sân sang lĩnh vực toán học. “Tôi không thiếu những hy vọng và ước mơ về nhiều vấn đề khác nhau mà tôi cho là ít nhất có liên quan về mặt tinh thần với vấn đề này,” anh nói.

Việc Kelley và Meka cố gắng phát hiện ra sức mạnh của những ý tưởng từng bị bỏ qua cho thấy bản chất thường phù hợp của tiến bộ toán học - một phẩm chất mà đối với Tao là một điều may mắn hơn là một lời nguyền. “Không phải lúc nào toán cũng ngày càng khó hơn,” anh nói. “Tạ ơn Chúa.”