537 SỐ, SÁU MÀU, KHÔNG MỘT TỔNG NÀO

Đây là một câu đố mà trẻ con cũng hiểu được. Lấy các số 1, 2, 3, cứ thế tiếp tục. Gán cho mỗi số một màu. Luật duy nhất: trong cùng một màu, không bao giờ được có hai số cùng với tổng của chúng. Hai số đó thậm chí có thể giống nhau, nên nếu 2 màu đỏ thì 4 không được màu đỏ, vì 2 + 2 = 4.

Một tập hợp không chứa bộ ba như vậy được gọi là tập không chứa tổng (sum-free). Bạn có thể đi xa đến đâu trước khi luật chơi buộc bạn dừng lại? Giới hạn đó, với k màu, chính là số Schur S(k). Bài toán bắt nguồn từ một bài báo năm 1916 của I. Schur, mục đầu tiên trong danh sách tài liệu tham khảo.

Một dãy số nổi tiếng cứng đầu

Với một màu, bạn bị kẹt ngay lập tức: 1 + 1 = 2, nên màu đó chỉ chứa được số 1. Các giá trị đã biết là:

S(1) = 1
S(2) = 4
S(3) = 13
S(4) = 44
S(5) = 160, do M. J. H. Heule xác định (trong một bài báo công bố năm 2018).

Với sáu màu, chưa ai biết đáp án. Từ năm 2000, cách dựng tốt nhất từng biết, do H. Fredricksen và M. M. Sweet tìm ra bằng cách tìm kiếm trong các cách tô màu đối xứng, đạt tới 536. Con số đó từ bấy đến nay vẫn được trích dẫn như cận dưới tốt nhất — một mức sàn: S(6) ít nhất lớn chừng ấy, còn giá trị thật của nó, đến nay vẫn chưa biết, có thể cao hơn.

Thêm một số nữa

Zhiyang Chen và Fan Long, thuộc Đại học Toronto, cùng Ligeng Zhu, thuộc NVIDIA Research, nay đẩy nó lên 537. Chứng minh của họ thuộc loại mà các nhà toán học yêu thích vì sự thẳng thừng: họ in luôn đáp án. Sáu danh sách số — lần lượt gồm 76, 76, 88, 70, 76 và 151 số — cùng nhau chứa mọi số nguyên từ 1 đến 537 đúng một lần, và không màu nào chứa cùng lúc x, y và x + y. Kiểm tra nó nghĩa là thử mọi tổng trong từng danh sách, một việc máy tính làm trong chớp mắt.

Lời giải có một hình dạng nổi bật. Nó đối xứng: mỗi số x có cùng màu với 538 − x. Bốn màu đầu tiên bắt đầu ở 1, 2, 3 và 4; màu thứ năm chỉ xuất hiện từ 38 trở đi, màu thứ sáu chỉ từ 151 trở đi, và màu thứ sáu lấp kín toàn bộ đoạn giữa từ 237 đến 301. Ngay cả màu đầu tiên cũng có thể dựng lại từ một hạt giống chỉ gồm 14 số nhỏ bằng một phép đối xứng gương, một phép tịnh tiến và một số thêm vào.

Lan tỏa lên cao hơn

Các số Schur nuôi dưỡng lẫn nhau. Những công thức đã biết biến một cách tô màu tốt với k màu thành một cách tô với k + 2 hoặc k + 5 màu: S(k + 2) ít nhất bằng 10 S(k) + 2, và S(k + 5) ít nhất bằng 380 S(k) + 148. Vì vậy con số 537 mới nâng các kỷ lục khác lên:

tám màu: từ 5.362 lên 5.372 — và nhóm cũng đã dựng tường minh cách tô màu đó;
mười một màu: từ 203.828 lên 204.208;
mười ba màu: từ 2.038.282 lên 2.042.082.

Nó cũng cải thiện một số Ramsey, R₆(3): số điểm nhỏ nhất, tất cả được nối với nhau từng đôi một, sao cho mọi cách tô sáu màu cho các đường nối đều buộc phải chứa một tam giác cùng màu. Đánh số 538 điểm từ 0 đến 537 và tô đường nối giữa i và j bằng màu của hiệu |i − j| của chúng: cách tô màu không chứa tổng không để lại tam giác cùng màu nào. Vậy R₆(3) ít nhất là 539, so với 538 trước đây.

131 cách để làm điều đó

Cuộc tìm kiếm không chỉ tìm ra một lời giải mà tới 131 lời giải thực sự khác nhau, được các tác giả xếp thành năm họ và công bố đầy đủ. Phần lớn rất gần với lời giải đầu tiên: các lời giải thuộc họ F1 đến F4 trùng với nó ở ít nhất 462 trên 537 vị trí. Một họ phá vỡ tính đối xứng gương; một họ khác được dựng bằng cách trộn ba bản sao bị xáo trộn của lời giải gốc.

Bài báo không giải thích bản thân cuộc tìm kiếm được tiến hành ra sao. Các tác giả nhấn mạnh rằng 131 cách tô màu của họ không phải là một danh mục đầy đủ các lời giải sáu màu, mà chỉ là những điểm xuất phát mới cho bất kỳ ai muốn thử sức với 538.