KỶ LỤC MỚI CHO PHÉP NHÂN CÁC LƯỚI SỐ

Nhân hai ma trận — những lưới số — là một trong những phép toán cơ bản nhất của tính toán. Làm theo cách trong sách giáo khoa, chi phí nhân hai lưới n nhân n tăng như n³. Thuật toán năm 1969 của Volker Strassen là thuật toán đầu tiên làm tốt hơn — “dưới bậc ba” (subcubic), theo cách nói của bài báo — và từ đó các nhà toán học đo tiến bộ bằng một con số duy nhất: số mũ ω (omega), lũy thừa nhỏ nhất của n là đủ khi các lưới lớn dần.

Strassen đã đưa nó xuống dưới 2,81. Hàng thập kỷ nghiên cứu, được liệt kê trong bài báo, đã đẩy nó xuống khoảng 2,37, với những bước ngày càng nhỏ. Năm 2026, Emilien Dupont và các đồng nghiệp đạt 2,371177. Giờ đây Reza Zadeh, thuộc công ty Matroid, Inc., chứng minh ω < 2,37115924.

Một số cải tiến tiêu biểu của cận trên của ω, từ Strassen năm 1969 đến bài báo này. — Bảng 1, Zadeh (2026), arXiv:2610.10593, CC BY 4.0.

Một công thức với 212.820 tham số

Những kỷ lục này không đến từ một mẹo khéo hơn cho các lưới nhỏ. Chúng đến từ một đối tượng đại số gọi là tensor Coppersmith–Winograd, có thể được cắt ra và ghép lại, một cách đệ quy, thành nhiều phép nhân ma trận độc lập. Cách cắt được quyết định bởi một tập hợp lựa chọn khổng lồ: các phân phối xác suất, các mức phạt entropy và kích thước ma trận được xác định qua từng tầng. Bất kỳ tập lựa chọn hợp lệ nào cũng cho một cận hợp lệ; nghệ thuật là tìm ra một tập tốt.

Dựa trên khung lý thuyết của Josh Alman và các đồng nghiệp cùng cách phát biểu của Dupont và các đồng nghiệp, Zadeh tinh chỉnh 212.820 con số cùng lúc, với ba cải tiến:

• Điều chỉnh thang đo theo mức quan trọng. Một số thành phần của cấu trúc chỉ xuất hiện hiếm hoi, nên ảnh hưởng của chúng lên kết quả rất nhỏ và bộ tối ưu hầu như không dịch chuyển chúng. Mỗi con số được điều chỉnh thang đo theo trọng số mà thành phần của nó mang.
• Sáu núm điều chỉnh cho các điểm nghẽn. Số mũ cuối cùng được quyết định bởi đại lượng yếu nhất trong ba đại lượng cạnh tranh ở ba giai đoạn. Một bước hiệu chỉnh riêng chỉ dùng sáu tham số điều khiển để giữ chúng cân bằng.
• Xuất dữ liệu chính xác. Công thức cuối cùng được chuyển thành các phân số chính xác có mẫu số 2⁹⁶.

Chứng minh bằng kiểm tra

Cận này là một chứng minh có máy tính hỗ trợ. Một chương trình ngắn, chỉ dùng thư viện chuẩn của Python — không mạng, không mô hình, không gói bổ sung — dựng lại mọi phân phối từ các phân số chính xác và đánh giá kết quả với phép làm tròn được bảo đảm. Nó xác định rằng đại lượng then chốt là dương, khoảng 8,5 phần tỷ, qua đó chứng minh cận. Tác giả nhấn mạnh những gì điều này không bao quát: chương trình là mã có thể kiểm toán, không phải sự hình thức hóa toàn bộ lý thuyết trong một trợ lý chứng minh, và việc tìm kiếm mang tính cục bộ, không có khẳng định nào rằng công thức là tốt nhất có thể.

Tác giả cũng viết rằng các công cụ AI tạo sinh, không được nêu tên, đã hỗ trợ việc khám phá số, phần mềm và bản thảo, và rằng mã ban đầu dựa trên các ghi chú tính toán do Eric Naslund chia sẻ công khai. Một chứng chỉ máy tính công khai riêng biệt, phát hành ngày 5 tháng 10 năm 2026, đã đạt 2,371169353; giá trị mới còn thấp hơn nữa.

Nhanh hơn, trên lý thuyết

Mức cải thiện so với Dupont và các đồng nghiệp là 0,00001776 ở số mũ. Như mọi cận thu được theo cách này, sự bảo đảm mang tính tiệm cận: riêng số mũ không cho biết từ kích thước ma trận nào thuật toán mới mới thực sự vượt qua các thuật toán hiện có. Điều nó thay đổi là câu trả lời tốt nhất đã biết cho một câu hỏi tồn tại từ năm 1969 — về nguyên tắc, các lưới số có thể được nhân nhanh đến mức nào?