[2016.01.01] Erdős distinct distances problem

평면 위의 n개의 점을 생각하자. n개의 점을 적당히 옮겨감으로써, 임의의 두 점 사이의 거리가 다르게 할 수 있음은 자명하다: 즉 서로 다른 거리의 개수는 최대 \binom{n}{2}개가 가능하다.

이 시점에서, 반대 방향을 생각해 볼 수 있다: 서로 다른 거리의 개수를 최소화하려고 하면, 어느 정도까지 가능할까. 아주 간단한 경우, 즉 n=3일 때를 생각해보자. 이를 정삼각형 형태로 배치할 경우, 점 사이의 거리의 개수는 1개로 충분하다. 하지만 좀더 많은 점이 있다면?

평면상의 문제에서 벗어나서, 쉬운 경우 – 선 위에 있을 경우를 생각해보자. 직관적으로 생각해 봤을 때 n개의 점을 등간격으로 둘 경우 거리의 개수는 n-1개로 정해진다. 따라서 평면에서는 n개보다 확실히 작게 만들 수 있으리라는 생각을 할 수 있다. 어느 정도로 작게 만들 수 있을까? 라는 질문이 Erdős distinct distances problem의 요지이다.

Paul Erdős 본인은 그의 1946년 논문 (PDF 링크)에서 다음을 증명하였다.

정리. 평면 상의 n개의 점 사이의 거리의 개수의 최소값 f(n)은 아래 부등식을 만족한다:

(n-3/4)^{1/2} - 1/2 \le f(n) \ge cn/( \log n)^{1/2} .

이 정리 자체는 쉽게 정리할 수 있다. 논문의 증명 방법을 인용한다.

증명: 우선 n개의 점으로 결정되는 볼록포(convex hull) 상에 있는 점을 잡아, P_1이라 부르고, P_1 P_i (i=2,3, \cdots, n)의 개수를 K라 하자. 이 중, 같은 거리가 최대 N회 나타난다고 할 경우, 당연히 KN \ge n-1.

이제 거리 r이 정확히 N번 나타나는 거리라고 할 때, 이제 P_1을 중심으로 하며 반지름 r인 원 위에는 N개의 점이 있고, 이 점들(Q_1 , Q_2 , \cdots , Q_N )은 한 반원 위에 존재하며 (아니면 P_1 이 convex hull 위에 있음에 모순이므로), 이 때 Q_1 Q_2 < Q_1 Q_3 < \cdots < Q_1 Q_{N-1} 이므로, N-1 개의 서로 다른 거리를 얻게 된다. 따라서, 다음을 얻는다;

f(n) \ge \max (N-1 , (n-1)/N )

이는 N(N-1)=n-1일 때 최소가 되며, 이는 정확히 첫번째 부등식이 된다.

“최대”를 증명하기 위해, 실제 경우의 예시를 들자: 아래와 같은 정사각형 격자를 생각하자.

square1

이 때, 격자점 사이의 거리는 (u^2 + v^2)^{1/2}, (0 \le u,v \le n^{1/2} )의 형태를 가지며,  두 정수의 제곱의 합으로 나타나지는 2n 이하의 자연수는 cn/(\log n )^{1/2} 개 이하임이 알려져 있으며, 이는 부등식의 우변이 된다.

이 방식을 그대로 응용해, 높은 차원의 경우 역시 보일 수 있다.

따름정리. k-차원 공간 위에 있는 n개의 점에 대해 f(n)을 다시 정의할 경우, 다음 부등식이 성립한다:

c_1 n^{1/k} <f(n) < c_2 n^{2/k }

더 나아가, Erdős는 다음을 주장하였다:

가설. 평면 위의 n개의 점 사이의 거리의 개수는 최소 n^{1- o(1) } 이다.

사실 이 가설은 상당히 오랫동안 open이었고, f(n)n^{c}꼴으로 정리하는 작업은 있었지만 위 가설에 접근하지는 못했다. 그렇지만 2010년, 본 가설이 증명되었고, 해당 논문은 2015년 Annals. of Math에 게재되었다.

정리. (Guth and Katz) 상수 c가 존재해, f(n)>cn/( \log n)가 만족한다.

위 정리를 정확히 이해하기는 사실 어렵지만, 중요한 아이디어들은 캐치할 수 있다(이하 내용은 Terrence Tao의 블로그에서 발췌).

Erdős의 하한 증명 과정에서, 한 점을 중심으로 한 원을 그림으로써 원하는 성질을 증명할 수 있었다. 유사하다면 유사하지만, Guth와 Katz는 명제를 증명하기 위해, 본 문제를 3차원 공간상의 에 관한 문제로 변환하였다.

길이가 같다라는 것은 사실은 도형으로써 두 선부이 합동임을 의미하고, 따라서 그에 따른 orient-preserving rigid motion이 유일하게 존재한다. 다시 말해, 두 길이가 같은 선분의 쌍 x_i x_j x_k x_l은 5개 원소의 쌍 (x_i, x_j, x_k, x_l, R)에 유일하게 대응된다. 뿐만 아니라, 이러한 선분의 쌍은, 특정 길이가 N번 언급될 경우 이러한 쌍은 \binom{N}{2}개 존재한다. \binom{n}{2}개의 선분이 f(n)개로 partition되는 케이스이므로, 이는 모두 길이가 같을 때 최소이다. 작은 항을 모두 제외할 경우 이는 n^4 /f(n) 이 되며, 따라서 만약 정리가 성립하지 않는다면 이것이 n^3 \log n보다 커져야만 한다. 이를 반증하자.

거꾸로, 이러한 Rx_ix_k로 보내며, x_jx_l으로 보내는 rigid motion이 되므로, xy로 보내는 모든 rigid motion의 집합 l_{x \rightarrow y}을 정의할 때 Rl_{x_i \rightarrow x_k }l_{x_j \rightarrow x_l }의 공통 원소가 된다. 한편 l_{x \rightarrow y}을 고려할 때, 이러한 rigid motion의 회전 중심은 x,y의 수직이등분선상의 점 중 하나가 되고, 이에 따른 회전각 역시 유일하게 주어진다. 따라서 (p, \cot ( \theta /2) ) 형태의 좌표를 주었을 때, l_{x \rightarrow y}R^3 상에서의 선으로 볼 수 있다. 사실 이렇게 좌표를 줄 경우, 이는 ‘직선’이 됨 역시 쉽게 확인할 수 있을 것이다. (코탄젠트의 값은 (중점에서의 변위)/선분 길이의 반) 으로 주어진다.)

아까도 언급했듯, 길이가 같은 선분의 쌍은  (x_i, x_j, x_k, x_l, R)에 대응되며, 이는 곡 두 선 l_{x_i \rightarrow x_k }l_{x_j \rightarrow x_l }이 교점을 가지게 된다. 즉 문제는 다음과 같아진다. 이러한 선은 대략 n^2개 존재하므로, 상수를 떼고 생각할 경우 아래와 같은 문제가 된다.

n^2개의 선 중, 만나는 선의 쌍은 몇 쌍이나 존재하는가?

위 문제의 답이 n^3 \log n이하라면 가정이 모순이므로 정리가 성립하게 될 것이다. 하지만 일반적으로 위 문제의 답은 당연히 n^4이다(모두 한 점을 지난다고 생각해보자)

Guth & Katz의 방법론을 통해 n개 점에 대한 문제를 ~n^2개의 직선 중 만나는 쌍에 대한 논의로 변환하였다. 우리의 목적은 이러한 쌍이 n^3 \log n 이하로 정해짐을 보이는 것이지만, 일반적으로 그렇게 되지는 않는다.

하지만 우리가 만든 이 ‘직선’은 임의로 결정된 것이 아니므로, 추가적인 제한 조건을 준다면 문제를 해결할 수도 있겠다. 관찰을 해보자.

  • 서 로 다른 점 x_i , x_j , x_k에 대해, l_{x_i \rightarrow x_j}l_{x_i \rightarrow x_k}는 만나지 않는다. 즉 같은 rigid motion은 같은 점을 다른 점으로 대응시킬 수 없다. 즉 만약 두 직선이 만난다면, 서로 다른 점에서 시작하는 직선이여야 한다. 따라서 한 점에서 만날 수 있는 직선의 수는 최대 n개.
  • 임의의 평면 \pi이 있을 때, l_{x_i \rightarrow x_j}\pi 상에 존재할 수 있는 (x_i , x_j )의 쌍은 O(n)개 존재한다.
  • 사실 이것은 평면이 아니라 일반적인 에 서도 성립한다. 증명 과정에서 필요한 것은 임의의 regulus(2차식으로 정해진 면) 역시 기껏해야 O(n)개 직선을 포함할 수 있다는 것이다. (사실 이는 Bezout’s Theorem에 의해 자명하며, 임의의 유한 차수 면에 대해서도 같은 성질이 성립한다.)

그렇게 될 경우, 본 문제는 다시 다음으로 회귀한다.

R^3 안의 ~ n^2 개 직선이

  • 한 점은 최대 n개 직선에서 만나며
  • 임의의 평면이나 regulus가 기껏해야 O(n)개의 직선을 포함할 경우

만나는 직선의 쌍은 최대 O(n^3 \log n)쌍 존재한다.

기초적인 더블 카운팅을 사용해보자. 어떤 점이 k개 직선에서 만날 경우, 그 점은 ~k^2개의 만나는 의 쌍을 만든다고 할 수 있다. 따라서, 여러 개 만나는 직선마다 만나는 횟수에 반비례하게 조금 만난다면, 결론에 조금 더 가까워질수 있을 것이다. 구체적으로는 다음과 같다.

정리. 3차원 실공간에서의 O(n^2)개 직선이, 임의의 평면이나 regulus가 기껏해야 O(n)개의 직선만을 포함한다고 하자. 이 때, 2 \le k \le n에 대해, k개 이상의 직선에서 만나는 점의 집합을 S라 하면, |S| = O(n^3 / k^2 ).

이 때, 정리가 성립할 경우 만나는 선의 개수는 최대

O(n^3 ( 1 + (n-1)^2 (1/(n-1)^2 -1/n^2) + \cdots + 4(1/4-1/9)) = O(n^3(1+1/2+\cdots+1/n))=O(n^3 \log n)

가 되어, 우리가 원하는 결론에 도달함을 알 수 있다.

이하 내용들은 다소 난해하므로, 기회가 된다면 다시 논의해보도록 하겠다.

참조:

[2016.01.01] Erdős distinct distances problem