Bài toán khoảng cách đơn vị của Erdős và giới hạn của các điểm trên mặt phẳng

[
U(n) = n^{1+o(1)}
]

Giả thuyết này dựa trên các cấu hình dạng lưới điểm nguyên. Khi các điểm được đặt trên một lưới vuông kích thước khoảng (\sqrt{n} \times \sqrt{n}), ta có thể tạo ra nhiều cặp điểm cách nhau đúng 1 đơn vị theo các hướng ngang và dọc, cho số lượng khoảng cách đơn vị lớn hơn tuyến tính một chút.

Các kết quả tốt nhất hiện nay

Cho đến nay, các nhà toán học mới chỉ xác định được các giới hạn trên và dưới cho bài toán.

• Giới hạn dưới:

 n^(1 + Ω(1 / log log n))

• Giới hạn trên tốt nhất đã biết:

 O(n^(4/3))

Giới hạn trên này được chứng minh vào năm 1984 bởi Spencer, Szemerédi và Trotter, sử dụng các kỹ thuật trong lý thuyết giao điểm hình học (incidence geometry).

Tình trạng hiện tại của bài toán

Tóm lại, hiện nay chúng ta có:

lower bound:  n^(1 + O(1 / log log n))
upper bound:  O(n^(4/3))
conjecture:   n^(1 + o(1))

Khoảng cách giữa hai giới hạn vẫn còn khá lớn. Vì vậy, giả thuyết ban đầu của Erdős vẫn chưa được chứng minh hoặc bác bỏ.

Vì sao bài toán này quan trọng?

Bài toán khoảng cách đơn vị liên quan chặt chẽ đến nhiều lĩnh vực của toán học hiện đại, đặc biệt là:

• hình học rời rạc
• lý thuyết đồ thị hình học
• lý thuyết giao điểm (incidence theory)

Nhiều phương pháp mạnh mẽ trong toán học tổ hợp và hình học đã được phát triển một phần để giải quyết những câu hỏi kiểu này.

Sau gần 80 năm kể từ khi Erdős nêu ra (năm 1946), bài toán vẫn là một trong những câu hỏi nổi tiếng chưa có lời giải trong hình học rời rạc.