에르되시 서로 다른 거리 — 평면 $n$점은 거리 몇 가지를 만드는가

평면 위의 *$n$개 점이 서로 결정하는 거리의 가짓수의 최솟값* $g(n)$은?

Erdős 1946: $g(n) = \Omega(n / \sqrt{\log n})$ 추측. 2010년 Guth–Katz에서 *$g(n) = \Omega(n / \log n)$ 증명으로 추측에 로그factor만 차이*로 거의 해결.

*직선 위 $n$점*: 최소 거리 가짓수 $= n - 1$. *정사각 격자 $\sqrt{n} \times \sqrt{n}$*: $\sim n / \sqrt{\log n}$ — 정수 표현 가능 거리수 (Landau-Ramanujan 상수). 격자가 최적에 가깝다는 게 Erdős의 직관. 증명은 대수기하·incidence 이론·다항법이 동원되는 깊은 결과 — 조합기하의 새 기법이 이 문제로부터 탄생.

Guth–Katz는 2010년 원고(2015년 Annals 출판)에서 다항식 분할과 ruled-surface 분석으로 *$g(n)\ge c n/\log n$*을 증명해 올바른 $n$의 지수를 얻었다. 그러나 격자 상계 $O(n/\sqrt{\log n})$와는 아직 *$\sqrt{\log n}$* 차이가 있어 정확한 로그 차수는 미해결이다. 따라서 “거의 해결”은 진척의 크기를 뜻할 뿐 해결 상태가 아니다.