에르되시 단위 거리 문제: 평면에서 거리 1인 점쌍은 얼마나 많을까

이 추측의 직관적 근거는 격자 배치다. 예를 들어 √n × √n 크기의 정사각 격자에 점들을 놓으면, 수평·수직 방향으로 거리 1인 점쌍이 많이 생긴다. 이런 구조는 실제로 선형보다 약간 더 많은 단위 거리를 만들어낸다 .

현재까지 알려진 최선의 상한

하지만 모든 가능한 점 배치에 대해 단위 거리의 수가 얼마나 커질 수 있는지에 대한 엄밀한 상한은 아직 크게 줄어들지 않았다.

현재까지 가장 유명한 결과는 다음이다.

• O(n^{4/3})

이 상한은 **스펜서(Spencer), 세메레디(Szemerédi), 트로터(Trotter)**가 1984년에 증명했다 .

즉 어떤 방식으로 점을 배치하더라도 단위 거리의 수는 대략

O(n^(4/3))

을 넘지 않는다는 것이다.

정리: 아직 남아 있는 간극

현재 연구 상황은 다음처럼 요약된다 .

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

하한과 상한 사이에 상당한 차이가 남아 있기 때문에, 에르되시의 원래 추측은 아직 증명되지 않았다.

조합기하학, 그래프 이론, 발생 기하학(incidence geometry) 등의 도구가 계속 발전하고 있지만, 이 간극을 완전히 메우는 결과는 아직 등장하지 않았다. 그래서 이 문제는 지금도 현대 이산기하학에서 가장 유명한 미해결 문제 중 하나로 남아 있다.