Bài toán mở, Hình học, Tổ hợp và Toán rời rạc, nêu năm 1946

Bài toán khoảng cách đơn vị của Erdős

Còn mởErdős

Xác định bậc độ lớn tiệm cận của $u(n)$ , số cặp điểm tối đa cách nhau một khoảng cách Euclid bằng $1$ trong một tập hợp bất kỳ gồm $n$ điểm trên mặt phẳng $\mathbb{R}^2$ .

Người nêu, 1946Paul Erdős

Hiện trạng nghiên cứu tính đến năm 2026

Tính đến năm 2026, số mũ tiệm cận chính xác của $u(n)$ trên mặt phẳng Euclid vẫn còn là bài toán mở, dù cục diện đã thay đổi sâu sắc vào tháng 5 năm 2026. Suốt tám mươi năm, chặn dưới tốt nhất vẫn là chặn lưới nguyên $n^{1+c/\log\log n}$ năm 1946 của Erdős, và Erdős từng phỏng đoán rằng $u(n) = n^{1+o(1)}$ . Tháng 5 năm 2026, một cấu trúc trường số đại số do AI phát hiện (được kiểm chứng trong các bản thảo preprint của Alon cùng cộng sự và được Sawin tinh chỉnh) đã bác bỏ giả thuyết của Erdős, chứng minh $u(n) = \Omega(n^{1.014})$ và thu hẹp tốc độ tăng thực sự vào khoảng giữa một lũy thừa lớn hơn $n^1$ và chặn trên Spencer–Szemerédi–Trotter $O(n^{4/3})$ năm 1984.

Kết quả tốt nhất đã biết

Chặn trên tổng quát tốt nhất là $u(n) = O(n^{4/3})$ , được Spencer, Szemerédi và Trotter chứng minh (1984).
Chặn dưới tường minh $u(n) > n^{1.014}$ cho $n$ lớn tùy ý được thiết lập năm 2026 (Sawin, preprint, phát triển từ phản ví dụ của OpenAI được Alon và cộng sự kiểm chứng), bác bỏ giả thuyết $n^{1+o(1)}$ của Erdős.

Công cụ và chỗ dừng

Công cụ	Đạt được	Chỗ dừng
Hình học liên thuộc và bất đẳng thức số giao điểm (Szemerédi–Trotter, Székely)	Chứng minh chặn trên $u(n) = O(n^{4/3})$ bằng cách chặn số quan hệ liên thuộc giữa $n$ điểm và $n$ đường tròn đơn vị	Các chặn giao điểm tô pô và đồ thị hai phía không phân biệt được đường tròn đơn vị Euclid với các giả đường tròn thực sự đạt $\Theta(n^{4/3})$ quan hệ liên thuộc
Trường số đại số và tháp trường lớp Golod–Shafarevich (Alon và cộng sự, Sawin)	Dựng các tập điểm trong $\mathbb{C} \cong \mathbb{R}^2$ từ các trường số bậc lớn có biệt số nhỏ và nhiều ước nguyên tố chẻ có chuẩn bằng $1$ , đạt được $u(n) > n^{1.014}$	Sawin chỉ ra rằng các cấu trúc trường số vô điều kiện đã biết theo khuôn khổ này không thể đẩy số mũ vượt quá khoảng $1.2143$ , vẫn để lại khoảng cách dưới $4/3$

Câu hỏi còn mở

Số mũ tiệm cận thực sự $\limsup_{n \to \infty} \frac{\log u(n)}{\log n}$ trên mặt phẳng Euclid bằng bao nhiêu?
Liệu có thể cải thiện chặn trên $O(n^{4/3})$ thành $O(n^{4/3 - c})$ với $c > 0$ nào đó bằng cách sử dụng tính cứng đại số của các đường tròn đơn vị hay không?

Tài liệu tham khảo

Paul Erdős (1946). On sets of distances of n points · DOI:10.1080/00029890.1946.11991674
Joel Spencer, Endre Szemerédi, William T. Trotter (1984). Unit distances in the Euclidean plane · DOI:10.1007/pl00000428
Noga Alon, Thomas F. Bloom, W. T. Gowers, Daniel Litt, Will Sawin, Arul Shankar, Jacob Tsimerman, Victor Wang, Melanie Matchett Wood (2026). Remarks on the disproof of the unit distance conjecture · arXiv:2605.20695v1 [preprint, chưa bình duyệt]
Will Sawin (2026). An explicit lower bound for the unit distance problem · arXiv:2605.20579v1 [preprint, chưa bình duyệt]