CẦN BAO NHIÊU MÀU ĐỂ TÔ KHÔNG GIAN? VỚI MỘT CÂY THƯỚC ĐIỂN HÌNH, KHÔNG QUÁ 2d

Lấy mọi điểm của một mặt phẳng và gán cho mỗi điểm một màu. Chỉ một quy tắc: hai điểm cách nhau đúng một đơn vị không bao giờ được cùng màu. Số màu nhỏ nhất đáp ứng được là bao nhiêu?

Đây là bài toán Hadwiger–Nelson, có từ năm 1950 và, theo lời các tác giả, là một trong những bài toán mở nổi tiếng nhất của hình học rời rạc. Trong thời gian dài, người ta chỉ biết đáp án nằm giữa 4 và 7. Một đột phá gần đây đã nâng cận dưới lên 5. Đáp án chính xác vẫn chưa được biết.

Đổi cây thước

Khoảng cách không nhất thiết phải đo bằng một cây thước bình thường. Các nhà toán học định nghĩa nhiều chuẩn khác — những cách đo độ dài — mỗi chuẩn được mô tả bằng “quả cầu đơn vị” của nó, tức tập hợp các điểm cách tâm không quá 1. Với khoảng cách thông thường, đó là một quả cầu tròn; với các chuẩn khác, nó có thể là bất kỳ hình lồi nào đối xứng qua tâm.

Với mọi chuẩn trên mặt phẳng, đáp án của bài toán tô màu nằm giữa 4 và 7. Trong d chiều, với mọi chuẩn nó tối đa là hàm mũ theo d, và với nhiều chuẩn tự nhiên — kể cả chuẩn Euclid thông thường — nó cũng tối thiểu là hàm mũ: số màu bùng nổ khi số chiều tăng.

Liệu sự bùng nổ ấy có phải là quy luật? Noga Alon (Đại học Princeton và Đại học Tel Aviv), Matija Bucić (Đại học Vienna) và James Davies (Đại học Leipzig) xem xét một chuẩn điển hình. Không có cách tự nhiên nào để chọn một chuẩn “ngẫu nhiên”, nên họ dùng một khái niệm tô pô: một tính chất đúng với chuẩn điển hình nếu các ngoại lệ tạo thành một tập không đáng kể (tập “gầy”, meagre). Công trình trước đó của Alon, Bucić và Lisa Sauermann đã chỉ ra rằng một chuẩn điển hình cần nhiều nhất 2ᵈ màu, và đặt câu hỏi con số đó gần sự thật đến đâu.

Tuyến tính, không phải hàm mũ

Câu trả lời: còn xa lắm. Bài báo mới chứng minh rằng

• với một chuẩn điển hình trên không gian d chiều, 2d màu luôn là đủ;
• và đây là tốt nhất có thể: một tập mở các chuẩn cần ít nhất 2d màu. Vậy một số chuẩn cần đúng 2d.

Trong mười chiều, một chuẩn điển hình cần nhiều nhất hai mươi màu, trong khi khoảng cách thông thường cần một số màu tăng theo hàm mũ. Theo các tác giả, đây cũng là lần đầu tiên số màu được xác định chính xác cho một chuẩn “lồi chặt” trong một số chiều d bất kỳ.

Cận dưới dùng một cái bẫy khéo léo. Tìm 2d điểm mà từng đôi một cách nhau đúng một đơn vị, trừ hai điểm a và b, cách nhau nửa đơn vị. Thêm ảnh đối xứng của toàn bộ cấu hình qua a. Với ít hơn 2d màu, cả b lẫn ảnh đối xứng của nó đều buộc phải mang màu của a — nhưng chúng lại cách nhau đúng một đơn vị. Mâu thuẫn. Một bổ đề ổn định cho thấy cấu hình này vẫn tồn tại dù chuẩn bị thay đổi chút ít.

Một người chạy cô đơn trong không gian nhiều chiều

Cận trên tô màu mỗi điểm theo vị trí mà một phép chiếu được chọn khéo của nó rơi vào, trên các lát có bề rộng 1/(2d). Để làm được điều đó cần một thành phần then chốt mà các tác giả mô tả là phiên bản ma trận, nhiều chiều của giả thuyết người chạy cô đơn (lonely runner conjecture) nổi tiếng:

sup over x of minᵢ ‖aᵢ · x − bᵢ‖ ≥ k / (2n)

trong đó ‖t‖ là khoảng cách từ t đến số nguyên gần nhất, với n vectơ aᵢ bất kỳ trong k chiều mà k vectơ bất kỳ trong số đó đều độc lập. Mệnh đề này cũng giải quyết một giả thuyết năm 1978 của I. J. Schoenberg về “che khuất tầm nhìn” (view obstruction) — câu hỏi về độ dày cần thiết của các phiến tuần hoàn để chặn mọi tầm nhìn ra vô cực — mà các tác giả gọi là một trong những bài toán mở kinh điển nhất của lĩnh vực, cũng như một giả thuyết liên quan của Henze và Malikiosis.

Cỗ máy trong lời cảm ơn

Các tác giả nói rõ: “ChatGPT 6 Pro đã cung cấp cho chúng tôi chứng minh của thành phần cuối cùng chúng tôi cần trong chứng minh Định lý 1, cụ thể là Bổ đề 7, sau một cuộc thảo luận kéo dài”, trong đó họ đã chia sẻ những quan sát của chính mình — gồm cả ý tưởng quy nạp và chiến lược chung. “Lập luận cận dưới cũng được tìm ra với sự hỗ trợ của ChatGPT 6 Pro.”

Vẫn còn những câu hỏi. Giá trị chính xác 2d được chứng minh trên một tập mở các chuẩn, chứ không phải cho mọi chuẩn điển hình. Và với khoảng cách Euclid thông thường, các tác giả dự đoán cần nhiều hơn hẳn 2d màu trong mọi số chiều — điều đã được biết trong các chiều 2, 4, 7, 8 và từ 9 trở lên, nhưng vẫn còn bỏ ngỏ ở các chiều 3, 5 và 6.