Tinh đên hiện tại trong năm nay, Quanta đã ghi lại ba tiến bộ lớn trong lý thuyết Ramsey, nghiên cứu về cách tránh tạo ra các mẫu toán học. Các kết quả đầu tiên đặt giới hạn mới về độ lớn của một tập hợp số nguyên mà không chứa ba số cách đều nhau, chẳng hạn như {2, 4, 6} hoặc {21, 31, 41}. Các 2 và thứ ba tương tự, đặt các giới hạn mới về kích thước của các mạng mà không có cụm điểm nào được kết nối với nhau hoặc tất cả đều bị cô lập với nhau.

Các bằng chứng giải quyết những gì xảy ra khi những con số liên quan tăng lên vô cùng lớn. Nghịch lý thay, điều này đôi khi có thể dễ dàng hơn so với việc xử lý các số lượng phiền phức trong thế giới thực.

Ví dụ, hãy xem xét hai câu hỏi về một phân số có mẫu số rất lớn. Bạn có thể hỏi khai triển thập phân của 1/42503312127361 là bao nhiêu. Hoặc bạn có thể hỏi liệu con số này có tiến gần đến 1 không khi mẫu số tăng lên. Câu hỏi đầu tiên là một câu hỏi cụ thể về một đại lượng trong thế giới thực và nó khó tính toán hơn câu hỏi thứ hai, câu hỏi hỏi đại lượng XNUMX/n sẽ "tiệm cận" thay đổi như n mọc. (Nó càng ngày càng tiến gần đến 0.)

“Đây là một vấn đề cản trở toàn bộ lý thuyết Ramsey,” ông nói William Gasarch, một nhà khoa học máy tính tại Đại học Maryland. “Lý thuyết Ramsey được biết là có kết quả tiệm cận rất tốt.” Nhưng việc phân tích các số nhỏ hơn vô cực đòi hỏi một hộp công cụ toán học hoàn toàn khác.

Gasarch đã nghiên cứu các câu hỏi trong lý thuyết Ramsey liên quan đến các số hữu hạn quá lớn để giải quyết vấn đề bằng vũ lực. Trong một dự án, anh ấy đã đảm nhận phiên bản hữu hạn của bước đột phá đầu tiên của năm nay - một bài báo tháng Hai của Zander Kelley, một sinh viên tốt nghiệp tại Đại học Illinois, Urbana-Champaign, và Raghu Meka của Đại học California, Los Angeles. Kelley và Meka tìm thấy giới hạn trên mới về số lượng số nguyên giữa 1 và N bạn có thể đưa vào một tập hợp trong khi tránh các cấp số ba hoặc các mẫu số cách đều nhau.

Mặc dù kết quả của Kelley và Meka được áp dụng ngay cả khi N tương đối nhỏ, nó không đưa ra một giới hạn đặc biệt hữu ích trong trường hợp đó. Đối với các giá trị rất nhỏ của N, tốt hơn hết là bạn nên sử dụng các phương pháp rất đơn giản. Nếu như N là, giả sử, 5, chỉ cần nhìn vào tất cả các bộ số có thể có giữa 1 và N, và chọn ra một cấp số tự do lớn nhất: {1, 2, 4, 5}.

Nhưng số lượng các câu trả lời khác nhau có thể tăng lên rất nhanh và khiến cho việc sử dụng một chiến lược đơn giản như vậy trở nên quá khó khăn. Có hơn 1 triệu bộ bao gồm các số từ 1 đến 20. Có hơn 10⁶⁰ sử dụng các số từ 1 đến 200. Việc tìm ra tập hợp không lũy ​​tiến tốt nhất cho những trường hợp này cần rất nhiều sức mạnh tính toán, ngay cả với các chiến lược cải thiện hiệu quả. “Bạn cần có khả năng đạt được nhiều hiệu suất từ ​​mọi thứ,” nói James Glenn, một nhà khoa học máy tính tại Đại học Yale. Năm 2008, Gasarch, Glenn và Clyde Kruskal của Đại học Maryland đã viết một chương trình để tìm các bộ không lũy ​​tiến lớn nhất lên đến một N của 187. (Công việc trước đó đã nhận được câu trả lời lên tới 150, cũng như cho 157.) Mặc dù có một danh sách các thủ thuật, nhưng chương trình của họ mất hàng tháng để hoàn thành, Glenn nói.

Để giảm bớt tải tính toán, nhóm đã sử dụng các bài kiểm tra đơn giản để ngăn chương trình của họ theo đuổi các tìm kiếm ngõ cụt và chia tập hợp của họ thành các phần nhỏ hơn để họ phân tích riêng.

Gasarch, Glenn và Kruskal cũng đã thử một số chiến lược khác. Một ý tưởng đầy hứa hẹn dựa trên sự ngẫu nhiên. Một cách đơn giản để tạo ra một tập hợp không có cấp số cộng là thêm 1 vào tập hợp của bạn, sau đó luôn thêm số tiếp theo không tạo cấp số cộng. Làm theo quy trình này cho đến khi bạn chạm vào số 10 và bạn sẽ nhận được bộ {1, 2, 4, 5, 10}. Nhưng hóa ra đây không phải là chiến lược tốt nhất nói chung. “Nếu chúng ta không bắt đầu từ 1 thì sao?” Gasarch nói. “Nếu bạn bắt đầu ở một nơi ngẫu nhiên, bạn thực sự sẽ làm tốt hơn.” Ông nói thêm, các nhà nghiên cứu không biết tại sao tính ngẫu nhiên lại hữu ích như vậy.

Việc tính toán các phiên bản hữu hạn của hai kết quả lý thuyết Ramsey mới khác thậm chí còn khó khăn hơn việc xác định kích thước của các tập hợp không lũy ​​tiến. Những kết quả đó liên quan đến các mạng toán học (được gọi là đồ thị) được tạo thành từ các nút được kết nối bởi các đường được gọi là các cạnh. số Ramsey r(s, t) là số lượng nút nhỏ nhất mà một đồ thị phải có trước khi không thể tránh được việc bao gồm một trong hai nhóm s các nút được kết nối hoặc t những cái bị ngắt kết nối. Số Ramsey thật là đau đầu để tính toán rằng ngay cả r(5, 5) không xác định — nó nằm đâu đó giữa 43 và 48.

Trong 1981, Brendan McKay, hiện là một nhà khoa học máy tính tại Đại học Quốc gia Úc, đã viết một chương trình phần mềm có tên là nauty, nhằm mục đích làm cho việc tính toán các số Ramsey trở nên đơn giản hơn. Nauty đảm bảo rằng các nhà nghiên cứu không lãng phí thời gian để kiểm tra hai biểu đồ chỉ là phiên bản lật hoặc xoay của nhau. “Nếu ai đó ở trong khu vực và không sử dụng hành vi thô tục, trò chơi sẽ kết thúc. Bạn phải sử dụng nó,” nói Stanisław Radziszowski, một nhà toán học tại Viện Công nghệ Rochester. Tuy nhiên, số lượng tính toán liên quan là gần như không thể hiểu được. Năm 2013, Radziszowski và Jan Goedgebeur Chứng minh rằng r(3, 10) nhiều nhất là 42. Goedgebeur, một nhà khoa học máy tính tại Đại học KU Leuven ở Bỉ cho biết: “Tôi nghĩ rằng nó đã mất gần 50 năm cho CPU.

Nếu không thể tính toán số Ramsey chính xác, bạn có thể thử thu hẹp giá trị của nó bằng các ví dụ. Nếu bạn tìm thấy một biểu đồ gồm 45 nút mà không có năm nút nào được kết nối và không có năm nút nào bị ngắt kết nối, điều đó sẽ chứng minh rằng r(5, 5) lớn hơn 45. Các nhà toán học nghiên cứu số Ramsey từng nghĩ rằng việc tìm kiếm những ví dụ đó, được gọi là đồ thị Ramsey, sẽ đơn giản, Radziszowski nói. Nhưng không phải vậy. Ông nói: “Đã có kỳ vọng rằng các công trình toán học đẹp, thú vị sẽ mang lại những công trình tốt nhất có thể và chúng tôi chỉ cần thêm người làm việc với nó. “Cảm giác của tôi ngày càng nhiều rằng nó hỗn loạn.”

Tính ngẫu nhiên vừa là một trở ngại cho sự hiểu biết vừa là một công cụ hữu ích. Geoffrey Exoo, một nhà khoa học máy tính tại Đại học Bang Indiana, đã dành nhiều năm để tinh chỉnh các phương pháp ngẫu nhiên để tạo ra đồ thị Ramsey. TRONG một tờ giấy 2015 công bố hàng chục biểu đồ Ramsey mới, phá kỷ lục, Exoo và Milos Tatarevic đã tạo ra các biểu đồ ngẫu nhiên rồi dần dần điều chỉnh chúng bằng cách xóa hoặc thêm các cạnh làm giảm số cụm không mong muốn cho đến khi họ tìm thấy biểu đồ Ramsey. Tuy nhiên, các kỹ thuật của Exoo cũng là một nghệ thuật, Radziszowski nói. Đôi khi chúng yêu cầu anh ta kết hợp nhiều phương pháp hoặc sử dụng phán đoán về loại biểu đồ nào nên bắt đầu. Radziszowski nói: “Rất, rất nhiều người đã thử và họ không thể làm được.

Goedgebeur, người đã phát biểu làm việc trên tạo ra các loại đồ thị khác, chẳng hạn như đồ thị biểu diễn các hợp chất hóa học. Ông viết trong một email: “Không có khả năng những kỹ thuật này cũng có thể được chuyển giao và điều chỉnh để giúp tạo ra các loại biểu đồ khác hiệu quả hơn (và ngược lại).

Tuy nhiên, đối với Radziszowski, lý do nghiên cứu các số Ramsey nhỏ đơn giản hơn nhiều. “Bởi vì nó mở, bởi vì không ai biết câu trả lời là gì,” anh nói. “Những vụ lặt vặt chúng tôi làm thủ công; lớn hơn một chút, bạn cần một chiếc máy tính, và lớn hơn một chút, ngay cả chiếc máy tính cũng không đủ tốt. Và thế là thách thức xuất hiện.”