Toán họcBản tiền ấn phẩmLý thuyết3 phút đọc

MỘT GIẢ THUYẾT NĂM 1969 VỀ CÁC TỔNG TRIỆT TIÊU NHAU HÓA RA SAI

Hãy lấy một chiếc đồng hồ có sáu giờ, và một danh sách các lượt xoay: “xoay kim tiến 1 giờ”, “tiến 4 giờ”, v.v. Với năm lượt xoay mỗi lượt một giờ, không có nhóm nào trong số đó đưa kim trở về đúng vị trí xuất phát. Với sáu lượt xoay, dù chúng là gì, luôn có một nhóm làm được điều đó. Các nhà toán học ký hiệu phép số học đồng hồ này là C₆, và con số sáu ở đây là hằng số Davenport của đồng hồ.

Giờ hãy đặt r chiếc đồng hồ như vậy cạnh nhau, và để mỗi lượt xoay quay mọi kim theo một lượng riêng. Hằng số Davenport của bộ đồng hồ này, ký hiệu D(C₆^r), là số lượt xoay nhỏ nhất đảm bảo có một nhóm mà tổng của nó đưa mọi kim về vị trí xuất phát cùng lúc — theo cách nói của bài báo, đó là một dãy con có tổng bằng không (zero-sum). Hằng số này gắn với các bài toán trong lý thuyết đồ thị, hình học hữu hạn, tổ hợp và lý thuyết phân tích nhân tử (factorization theory).

Một công thức từ năm 1969

Có một cận dưới dễ thấy. Trên mỗi đồng hồ, lấy năm lượt xoay một giờ chỉ tác động lên đồng hồ đó: với r đồng hồ, ta được 5r lượt xoay mà không nhóm nào trong đó triệt tiêu nhau. Vậy cần ít nhất 5r + 1 lượt xoay. Tổng quát, với đồng hồ có n giờ, cần ít nhất r(n − 1) + 1.

Năm 1969, van Emde Boas và Kruyswijk phỏng đoán rằng cận dễ thấy này luôn là đáp án chính xác:

D(C_n^r) = r(n − 1) + 1.

Điều này đã được chứng minh trong thập niên 1960 cho một số trường hợp, chẳng hạn khi số giờ của đồng hồ là lũy thừa của một số nguyên tố, hoặc khi có nhiều nhất hai đồng hồ. Ngoài các trường hợp đó, giá trị chính xác vẫn nằm ngoài tầm với: mãi đến năm 2018, ngay cả trường hợp bốn đồng hồ sáu giờ vẫn chưa được biết. Dù vậy, giả thuyết này đã trở thành “một bài toán nổi bật tồn tại từ lâu” của lĩnh vực, và người ta kỳ vọng nó đúng.

116 lượt xoay không bao giờ triệt tiêu

Weidong Gao (Đại học Thiên Tân), Alfred Geroldinger (Đại học Graz), Guoqing Wang (Đại học Thiên Công) và Xiangneng Zeng (Đại học Trung Sơn) nay chỉ ra rằng nó sai.

Nhóm nghiên cứu ghép các lượt xoay lại như những khối xây dựng:

  • một danh sách gồm 24 lượt xoay trên năm đồng hồ sáu giờ, xây dựng từ một bảng nhỏ: bất kỳ nhóm nào trong số đó có tổng rơi vào một tập nhỏ gồm ba vị trí thì luôn rơi vào cùng một vị trí khác không;
  • hai danh sách như vậy dùng chung ba vị trí đó, cho ra 48 lượt xoay mà không có nhóm nào triệt tiêu nhau;
  • một danh sách riêng gồm 20 lượt xoay trong đó cũng không có nhóm nào triệt tiêu nhau.

Đặt cạnh nhau, chúng cho 2 × 48 + 20 = 116 lượt xoay trên 23 đồng hồ sáu giờ, và không có nhóm nào trong số đó đưa mọi kim về vị trí xuất phát. Giả thuyết cho rằng 23 × 5 = 115 là độ dài lớn nhất có thể của một danh sách như vậy. Vậy với 23 đồng hồ, hằng số Davenport ít nhất là 117, chứ không phải 116.

Các bản sao của khối này có thể được xếp chồng lên nhau: kết quả tổng quát là D(C₆^r) ≥ 5r + ⌊r/23⌋ + 1, trong đó ⌊r/23⌋ đếm số khối 23 trọn vẹn nằm gọn trong r. Do đó giả thuyết sai đối với đồng hồ sáu giờ ngay khi r đạt 23, và với mọi r lớn hơn. Các tác giả lưu ý rằng cùng định lý này cũng bác bỏ một kết quả phỏng đoán về các phép phủ (coverings).

Những gì còn bỏ ngỏ

Chứng minh không cho giá trị thực sự của D(C₆^r), mà chỉ cho một cận mà giả thuyết không cho phép. Nó không nói gì mới khi có ít hơn 23 đồng hồ, lúc cận mới bằng công thức cũ, cũng như với các đồng hồ có số giờ khác sáu. Ghi chú dài năm trang, và vẫn chưa qua bình duyệt.