CHỨNG MINH CỦA MỘT AI, ĐƯỢC VẼ LẠI CHO CON NGƯỜI

Hãy vẽ vài chấm và nối một số chấm với nhau bằng các đường. Các nhà toán học gọi đó là một đồ thị; các chấm là đỉnh, các đường là cạnh, và số đường chạm vào một chấm là bậc của nó. Một cây là một đồ thị không có vòng và liền thành một khối, giống như một cành cây phân nhánh; một cây có t chấm luôn có t − 1 đường.

Đầu những năm 1960, Paul Erdős và Vera T. Sós đặt ra một câu hỏi đơn giản: cần bao nhiêu đường để buộc một đồ thị phải chứa mọi cây có kích thước cho trước? Câu trả lời của họ, giả thuyết Erdős–Sós, như sau:

Nếu một đồ thị có bậc trung bình lớn hơn t − 2, nó chứa mọi cây có t đỉnh.

Ngưỡng này là chặt. Hãy lấy các bản sao rời nhau của một đồ thị đầy đủ có t − 1 chấm, trong đó mọi cặp đều được nối: mỗi chấm có đúng t − 2 hàng xóm, nhưng không mảnh nào đủ lớn để chứa một cây có t chấm. Cái khó nằm ở từ trung bình. Nếu từng chấm một đều có ít nhất t − 1 hàng xóm, người ta có thể đặt cây vào từng nhánh một mà không gặp khó khăn gì. Nhưng giá trị trung bình chẳng nói gì về một chấm riêng lẻ nào: có chấm có hàng trăm hàng xóm, có chấm hầu như không có.

Sáu mươi năm của những câu trả lời từng phần

Theo lịch sử được kể lại trong bài báo, bài toán có từ giai đoạn 1962–1964 và trở thành trung tâm của nhánh toán học nghiên cứu cần bao nhiêu cạnh để buộc một mẫu hình cho trước xuất hiện. Các trường hợp đặc biệt lần lượt được giải quyết: hình sao, đường đi, sao kép, cây có ít nhánh. Đầu những năm 1990, bốn nhà toán học — Ajtai, Komlós, Simonovits và Szemerédi — công bố một chứng minh cho các cây rất lớn, nhưng các bài báo gần đây lưu ý rằng chưa từng có bản thảo đầy đủ nào được xuất bản. Thêm các kết quả từng phần ra đời vào năm 2021, 2024 và 2026. Ngày 4 tháng 9 năm 2026, Reed và Stein đăng một chứng minh cho các đồ thị lớn và dày đặc, mà họ cho biết được phát triển mà không dùng AI.

Rồi một báo cáo xuất hiện. Tháng 9 năm 2026, Tom Adamczewski và Thomas Bloom, trong một tài liệu mang tên FrontierMath Erdős, đã quy một chứng minh cho toàn bộ giả thuyết cho một phiên bản chưa phát hành của một mô hình AI, GPT-6 Astra. Lập luận đếm ban đầu được công khai, và một kho lưu trữ đi kèm ghi lại quá trình AI tự động tìm kiếm chứng minh cùng một bản kiểm chứng hình thức bằng ngôn ngữ kiểm tra chứng minh Lean. Các tác giả của báo cáo cũng kêu gọi các chuyên gia con người viết những bản trình bày truyền thống, đầy đủ hơn.

Hé lộ đồ thị từng chấm một

Jay Cummings, thuộc Đại học Bang California, Sacramento, đáp lại lời kêu gọi đó. Bài viết dài 27 trang của ông giữ nguyên lập luận đếm trung tâm của AI nhưng thay đổi cách kể:

1. Hé lộ đồ thị dần dần. Liệt kê các đỉnh theo một thứ tự nào đó và mở ra từng đỉnh một, cùng với các cạnh nối giữa những đỉnh đã được hiển thị.
2. Đòi hỏi nhiều hơn. Thay vì tìm bất kỳ bản sao nào của cây, hãy tìm một bản sao có “gốc” được chọn nằm đúng ở đỉnh đầu tiên. Đòi hỏi nhiều hơn lại khiến chứng minh dễ hơn.
3. Đếm các hàng xóm sớm. Đó là những hàng xóm của đỉnh đầu tiên xuất hiện trước khi một bản sao như vậy xuất hiện. Cộng chúng lại trên mọi thứ tự có thể.
4. Chặn tổng. Bằng cách hoán đổi các đỉnh hoặc cả những khối trong thứ tự — những bước luôn có thể đảo ngược — Cummings chỉ ra rằng, tính trung bình trên mọi thứ tự, có nhiều nhất t − 2 hàng xóm sớm.

Bước cuối cùng rất ngắn. Nếu đồ thị không chứa bản sao nào của cây, mọi hàng xóm của đỉnh đầu tiên đều sẽ là hàng xóm sớm, trong mọi thứ tự. Tính trung bình trên mọi thứ tự, đó chính xác là bậc trung bình — mà theo giả thiết thì lớn hơn t − 2. Mâu thuẫn: cái cây phải có ở đó.

Chứng minh chỉ dùng tổng các bậc, chứ không dùng cách chúng phân bố. Cummings cũng đưa ra một phiên bản xác suất, và làm chi tiết với các cây có bốn và năm đỉnh trên những đồ thị cụ thể.

Một cuốn sách tranh về chứng minh

Bài viết có 32 hình vẽ. Nó kết thúc bằng một hệ quả kinh điển: tô tất cả các đường của một đồ thị đầy đủ bằng q màu, thì một màu sẽ luôn chứa một cây cho trước khi đồ thị có q(t − 2) + 2 đỉnh. Trong một tuyên bố cuối cùng, Cummings giải thích rằng ông đã phát triển văn bản trong một cuộc đối thoại dài với ChatGPT, rằng những ý tưởng trình bày mới — hàng xóm sớm, các phân hoạch tường minh, các hình vẽ — là của ông, và rằng ông đã kiểm tra mọi thứ và chịu hoàn toàn trách nhiệm.

Ông so sánh bản trình bày của mình với những bản gần đây khác của Riordan và Scott, Wood và Frederickson, và lưu ý rằng phương pháp này đã được mở rộng sang các mạng có hướng và các “siêu đồ thị” (hypergraph), một số mở rộng trong đó cũng được cho là của GPT-6 Astra. Đóng góp của ông, ông viết, là “một bản trình bày trực quan, lấy người đọc làm trung tâm, về lập luận, chứ không phải một lời giải mới cho giả thuyết”.