GIẢ THUYẾT HOA HƯỚNG DƯƠNG ĐÃ ĐỔ

Hãy lấy các số từ 1 đến n và xét mọi cách chọn ra một vài số trong đó: có 2ⁿ tập con như vậy. Bây giờ, chọn vài tập con có chung đúng cùng một phần chung, và không chung gì khác. Các nhà toán học gọi đó là một hoa hướng dương (sunflower): phần chung là lõi, và phần còn lại của mỗi tập là một cánh hoa không chạm vào cánh nào khác.

Hoa hướng dương là một công cụ cơ bản của tổ hợp. Bài báo liệt kê các mối liên hệ với giới hạn của một số mạch logic, với bài toán “cap set”, với phép nhân ma trận nhanh và với lý thuyết thông tin.

Một câu hỏi từ năm 1970

Theo các tác giả, câu hỏi tự nhiên nhất về chúng bắt nguồn từ một bài báo năm 1970 của Paul Erdős. Một họ các tập con của {1, …, n} có thể lớn đến mức nào nếu không có k tập nào trong đó tạo thành một hoa hướng dương?

Vào những năm 1970, Erdős và Endre Szemerédi phỏng đoán rằng một họ như vậy phải nhỏ hơn theo cấp số mũ so với 2ⁿ tập con có thể có: nhiều nhất là cⁿ, với một số c nào đó nhỏ hơn hẳn 2.

Trong nhiều thập kỷ, các cận tốt nhất chỉ bớt được một chút, chưa bao giờ đủ để đưa cơ số xuống dưới 2. Chỉ trường hợp ba cánh (k = 3) được giải quyết, vào năm 2016, nhờ bước đột phá về bài toán cap set và một phép quy dẫn của Alon, Shpilka và Umans.

Cận trên

Matija Bucić và Fankang He (Đại học Vienna) cùng Hyunwoo Lee (KAIST và Viện Khoa học Cơ bản, Hàn Quốc) chứng minh giả thuyết với mọi k ≥ 3. Định lý chính của họ: một họ không chứa hoa hướng dương k cánh có nhiều nhất

3 · (2 − 1/(16k³))ⁿ

phần tử. Cơ số nằm ngay dưới 2, nhưng đó là một số cố định nhỏ hơn 2, và đó chính xác là điều Erdős và Szemerédi đòi hỏi. Một cách xây dựng từ năm 1997 cho thấy rằng, với k lớn, giá trị thực không thể thấp hơn nhiều.

Từ tập hợp đến vectơ

Chứng minh đi qua một phiên bản của bài toán với các vectơ. Chia các số thành n khối gồm D phần tử và chọn một phần tử trong mỗi khối: mỗi lựa chọn là một vectơ. Một số vectơ tạo thành hoa hướng dương khi, ở mọi vị trí, các thành phần của chúng hoặc đều bằng nhau hoặc đều khác nhau.

Sau đó, các tác giả xây dựng một “bộ kiểm tra hoa hướng dương”: một hàm mà, trên một họ không chứa hoa hướng dương, chỉ khác không khi mọi đầu vào của nó đều là cùng một vectơ. Thành phần mới là viết hàm này, từng bước một, bằng các đa thức nội suy bậc thấp. Đếm các đa thức đó cho ta một cận cho kích thước của họ (Định lý 2 của họ). Một lập luận xác suất, với các khối ngẫu nhiên được lấy trung bình trên mọi kích thước tập hợp, đưa cận này trở lại các tập hợp thông thường.

Được một cỗ máy tìm ra, được một cỗ máy khác kiểm tra

Tuyên bố của bài báo về AI thẳng thắn một cách bất thường. Chứng minh của Định lý 2 do ChatGPT 6 Astra Pro tìm ra, sau một cuộc trao đổi ngắn bắt đầu bằng việc yêu cầu nó tổng quát hóa lập luận đã biết cho trường hợp ba cánh. Các tác giả cần bước đó cho một mục tiêu khác: một phiên bản cảm sinh (induced) của một bài toán đồ thị do Szemerédi đặt ra, mà họ thông báo sẽ trình bày trong một ghi chú sau.

Mô hình đã viết chứng minh bằng ngôn ngữ “slice rank”. Các tác giả viết lại nó bằng ngôn ngữ của phương pháp đa thức, mà họ thấy dễ hiểu hơn đối với người đọc. Họ khẳng định đã kiểm tra mọi kết quả và chịu hoàn toàn trách nhiệm, và rằng chứng minh đã được xác minh bằng Lean 4.35, một phần mềm kiểm tra chứng minh, với bản xác minh sẽ được đăng trên kho Palomar.

Những gì chưa được giải quyết

Các tác giả không tìm cách tối ưu hóa cơ số. Với ba cánh, nó không vượt qua được cận năm 2017 của Naslund và Sawin, khoảng 1,89. Và bài toán chị em mạnh hơn, giả thuyết hoa hướng dương Erdős–Rado, vẫn còn bỏ ngỏ: các cận của họ vẫn phụ thuộc nhiều vào kích thước khối D, đúng là điều mà bài toán đó không cho phép.