Giả thuyết Courtade-Kumar: một bài toán mở và câu chuyện bất ngờ
Giả thuyết Courtade-Kumar là một bài toán mở trong lý thuyết thông tin và hàm Boolean, đặt ra năm 2013, hỏi cấu trúc tối ưu của một hàm nén dữ liệu bit qua kênh nhiễu sao cho thông tin giữ lại là lớn nhất ở mọi chiều, mọi mức nhiễu và trong toàn bộ lớp hàm Boolean liên quan. Đây không phải câu hỏi vui dành cho những người thích đố mẹo, mà là điểm giao nhau của truyền tin, xử lý dữ liệu và toán học hiện đại. Bài toán nghe qua có vẻ “dễ”: hãy chọn một hàm để nén cả nguồn dữ liệu thành một bit, rồi truyền qua kênh nhiễu, làm sao để vẫn thu được nhiều thông tin nhất về bit đó. Nhưng “dễ hiểu” khác xa “dễ chứng minh”. Suốt hơn một thập kỷ, giả thuyết Courtade-Kumar được mô tả là một trong những bài toán mở quan trọng nhất của lý thuyết thông tin, thu hút sự theo đuổi của nhiều nhóm nghiên cứu trên thế giới.
Hai lời giải độc lập: từ FPT, USTC đến Google Research và CUHK
Điểm nút của câu chuyện nằm ở việc có tới hai lời giải độc lập xuất hiện gần như cùng lúc. Một phía là công trình "Dictators are most informative" của TS Vũ Khắc Kỷ, giảng viên Bộ môn Toán, Trường Đại học FPT, cùng GS Trần Mạnh Tuấn, Đại học Khoa học và Công nghệ Trung Quốc. Phía còn lại là nhóm bảy nhà khoa học đến từ Google Research, Chinese University of Hong Kong (CUHK) và một số trường đại học khác. Cả hai nhóm đều đi theo những con đường kỹ thuật khác nhau nhưng cùng gặp nhau ở một kết luận: trong bức tranh tổng quát, không có cấu trúc tinh vi nào đánh bại được điều tưởng như quá đơn giản – chọn một bit duy nhất làm hàm nén tối ưu. Đây là thắng lợi của trực giác toán học được chứng minh đến tận cùng, và là thắng lợi của sự kiên trì: TS Kỷ đã theo đuổi bài toán từ khoảng 10 năm trước, thời còn nghiên cứu sau tiến sĩ tại ITCSC thuộc CUHK.
Tại sao bài toán tưởng đơn giản lại khó đến vậy?
Điều khiến giả thuyết Courtade-Kumar thành bài toán mở kéo dài hơn một thập kỷ không nằm ở phát biểu dài hay ngắn, mà ở độ phức tạp của đối tượng phải kiểm soát. Một hàm Boolean trên n bit được xác định bởi giá trị của nó tại 2^n đầu vào nên tổng số hàm có thể có là 2^{2^n}, trong khi n có thể lớn tùy ý và tham số nhiễu biến thiên liên tục. Không ai có thể “thử từng hàm một”; lời giải buộc phải tìm ra một nguyên lý chung cho mọi số chiều, mọi mức nhiễu và toàn bộ lớp hàm. Đồng thời, đại lượng cần tối ưu là thông tin tương hỗ – một đối tượng phi tuyến, phụ thuộc vào toàn bộ phân phối của hàm sau khi đi qua kênh nhiễu. Nhiều công cụ quen thuộc trong lý thuyết thông tin, xác suất hay giải tích Fourier chỉ kiểm soát được vài mômen, một phần phổ, hoặc những lớp hàm đặc biệt, khiến khoảng cách giữa trực giác “dictator là tối ưu” và một chứng minh đầy đủ trở nên rất lớn. Đây là bài học rõ ràng: trong toán học hiện đại, phát biểu ngắn không có nghĩa là con đường chứng minh ngắn.
Khung entropy–phổ và cuộc hẹn 15h: tinh thần công bằng trong khoa học
Điểm đáng chú ý không chỉ nằm ở kết quả, mà ở cách hai nhóm ứng xử khi phát hiện ra nhau. Chứng minh của nhóm TS Kỷ và GS Trần Mạnh Tuấn phát triển một khung entropy–phổ mới, khai thác sự tương tác giữa entropy, toán tử nhiễu và cấu trúc phổ Fourier của hàm Boolean; bản thảo dài khoảng 36 trang, phần lõi là các lập luận giải tích cùng một lượng nhỏ tính toán có thể tái lập để kiểm tra các bất đẳng thức. Nhóm quốc tế dùng một hướng khác: phương trình vi phân, bài toán Bellman hữu hạn chiều và các phép tính được chứng nhận bằng máy tính, sau đó hình thức hóa và kiểm tra bằng Lean. Hai nhóm không hề biết về công trình của nhau cho đến khi gần hoàn tất; khi nhận ra kết quả trùng khớp, họ trao đổi để xác nhận tính độc lập của chứng minh rồi thống nhất đưa bản thảo lên cộng đồng khoa học cùng ngày, vào đúng 15h giờ Hong Kong. Như TS Kỷ nói, đây là "câu chuyện đẹp của nghiên cứu khoa học", nơi cạnh tranh không cần đi kèm với việc làm lu mờ người khác.
Ý nghĩa với toán học Việt Nam và những bài toán mở phía trước
Nếu chỉ nhìn vào sự kiện như một mốc kỹ thuật của lý thuyết thông tin, ta sẽ bỏ lỡ tầng ý nghĩa quan trọng với toán học Việt Nam. Việc hai nhà toán học Việt Nam xây dựng được một chứng minh độc lập cho một trong những bài toán mở quan trọng nhất của lĩnh vực cho thấy các nhóm nghiên cứu nhỏ trong nước vẫn có thể tham gia trực tiếp vào những vấn đề nền tảng mà các nhóm mạnh trên thế giới cùng quan tâm. Công bố bản thảo mới chỉ là bước đầu: cả hai lời giải đều cần được cộng đồng đọc, kiểm tra và phản biện kỹ lưỡng; không lời giải nào thay thế lời giải còn lại, mà mỗi phương pháp có thể mở ra những hệ quả riêng. Điều tích cực là quan hệ giữa hai nhóm đã trở nên gần gũi hơn và họ thường xuyên trao đổi về các dự án liên quan, đặc biệt là một bài toán mở khác đang có tiến triển khả quan. Từ góc nhìn rộng hơn, đây là lời nhắc rằng khoa học không chỉ là bảng điểm các công bố mà còn là cách ta cùng định nghĩa công bằng, ghi nhận và hợp tác trên những bài toán chưa có lời giải.
