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

평면 위 점들과 ‘거리 1’의 개수

이 문제는 조합기하학에서 유명한 **에르되시 단위 거리 문제(Erdős unit distance problem)**를 가리키는 경우가 많다. 질문은 단순하다.

유클리드 평면에 서로 다른 n개의 점을 놓았을 때, 정확히 거리 1인 점쌍은 최대 몇 개까지 만들 수 있을까?

겉보기에는 간단하지만, 이 문제는 1946년 헝가리 수학자 **폴 에르되시(Paul Erdős)**가 제기한 이후 지금까지 완전히 해결되지 않은 난제로 남아 있다.

에르되시의 추측

에르되시는 특정한 점 배치(특히 정수 격자 형태)를 관찰해 다음과 같이 추측했다.

• 최대 개수는 거의 선형에 가까운

n^(1+o(1))

정도일 것이라는 것이다. 즉 점의 수가 n이면 단위 거리의 수는 대략 n에 거의 비례하는 수준이라는 의미다 .

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

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

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

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

• O(n^{4/3})

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