Erd\H{o}s's diameter conjecture for separated distances fails in high dimensions

이 논문은 고차원 유클리드 공간에서 모든 쌍거리가 1 이상으로 분리된 점들의 집합에 대한 에르되시 (Erdős) 의 지름 추측이 거짓임을 증명하고, 그 증명을 Lean 4 로 완전히 형식화했다고 요약할 수 있습니다.

핵심

🎈 핵심 주제: "점들 사이의 거리를 일정하게 띄우면, 전체 크기가 얼마나 커져야 할까?"

상상해 보세요. 여러분이 거대한 방 (공간) 안에 $N$ 개의 공 (점) 을 던져 넣었습니다. 이때 중요한 규칙이 하나 있습니다.
"어떤 두 공 사이도 서로 1 미터 이상 떨어져 있어야 한다."

에르되시 선생님은 이렇게 물으셨습니다.

"이렇게 공들을 서로 1 미터 이상 띄워놓으려면, 방의 크기 (가장 먼 두 공 사이의 거리, 즉 '지름') 가 최소한 $N^2$ 에 비례할 정도로 커져야 하지 않을까?"

즉, 공의 개수가 늘어나면 방의 크기가 그 제곱 (제곱수) 만큼 엄청나게 커져야 한다는 것이 에르되시의 추측이었습니다. 이는 1 차원 (선) 에서는 맞지만, 고차원 (입체 공간 등) 에서는 어떻게 될지 궁금했습니다.

🚫 이 논문의 결론: "아니요, 방을 그렇게 크게 만들지 않아도 됩니다!"

이 논문의 저자 (보안 수안 호) 는 "에르되시의 이 추측은 고차원 공간에서는 틀렸습니다" 라고 선언합니다.

그는 다음과 같은 놀라운 사실을 증명했습니다:

1. 공을 아주 많이 (수천, 수만 개) 놓아도 서로 1 미터 이상 띄울 수 있습니다.
2. 하지만 이때 방의 전체 크기 (지름) 는 에르되시가 예상했던 $N^2$ 보다 훨씬 작습니다.
3. 구체적으로, 에르되시가 예상한 크기의 약 89.8% 정도만 되어도 충분하다는 것을 보였습니다. (즉, $0.898 \times N^2$)

🧩 어떻게 그런 게 가능할까요? (비유로 설명)

이 논문은 '싱어 차분 집합 (Singer difference set)' 이라는 수학적 장난감을 사용했습니다. 이를 쉽게 비유해 보겠습니다.

1. 원형 무대 위의 춤 (싱어 집합)

마치 원형 무대 (시계판) 가 있다고 상상해 보세요. 무대에는 $m$ 개의 좌석이 있고, 그중 일부 좌석에만 춤추는 사람들 (점들) 이 서 있습니다.

• 규칙: 이 사람들이 서로의 위치 차이를 계산해 보면, 1 부터 $N$ 까지의 모든 숫자가 딱 한 번씩만 나오도록 배치되어 있습니다. (수학적으로 '차분 집합'이라고 합니다.)
• 이는 마치 "어떤 두 사람 사이의 거리를 재면, 1 미터, 2 미터, 3 미터... 모든 거리가 중복 없이 딱 한 번씩만 나타난다"는 뜻입니다.

2. 거리를 조절하는 마법 (가중치와 진동)

이제 이 사람들을 실제 3 차원 공간이 아닌, 아주 고차원 (수천 차원) 의 공간으로 옮겨 봅니다.

• 저자는 이 공간에서 각 사람 사이의 거리를 결정하는 '마법의 공식'을 만들었습니다.
• 이 공식은 파동 (진동) 을 이용합니다. 서로 다른 거리를 가진 파동들을 섞어서, 거리가 1 미터, 2 미터, 3 미터... 순서대로 아주 조금씩만 차이가 나도록 조정했습니다.
• 핵심 아이디어: 거리가 1 미터인 두 사람과 2 미터인 두 사람 사이의 차이 (1 미터) 가, 100 미터인 두 사람과 101 미터인 두 사람 사이의 차이보다 더 크게 만들 수 있습니다.
  • 마치 계단을 올라갈 때, 아래쪽 계단은 높이가 크고 위쪽 계단은 높이가 아주 얇아지도록 만든 것과 같습니다.

3. 마지막 한 걸음 (스케일링)

이렇게 배치했을 때, 가장 가까운 두 사람 사이의 거리 차이가 아주 작게 (0.1 미터 정도) 남을 수 있습니다.

• 저자는 이 전체 구조를 확대 (스케일링) 합니다.
• 가장 작은 간격이 1 미터가 될 정도로 전체를 키우면, 모든 거리가 1 미터 이상이 됩니다.
• 그런데 흥미로운 점은, 이 확대를 했을 때 전체 공간의 크기가 에르되시가 예상했던 $N^2$ 보다 훨씬 작게 남는다는 것입니다.

💡 왜 이것이 중요한가요?

1. 차원의 마법: 우리가 사는 3 차원 세계에서는 에르되시의 추측이 맞을지도 모릅니다. 하지만 수학적으로 '무한히 많은 차원'을 가진 공간에서는 우리의 직관이 깨집니다. 공간이 너무 넓고 복잡하면, 점들을 서로 띄우면서도 전체를 작게 묶어둘 수 있는 '요술'이 가능해집니다.
2. AI 와 수학의 협력: 이 논문의 마지막에 재미있는 사실이 나옵니다. 이 복잡한 수학적 구조를 인공지능 (GPT-5.4 Pro) 이 발견했고, Lean 4라는 AI 도구를 이용해 수학적 증명을 완벽하게 검증했다고 합니다. 이는 AI 가 이제 수학자의 '창의적 파트너'가 될 수 있음을 보여줍니다.

📝 한 줄 요약

"수천 차원의 거대한 공간에서, 수만 개의 점들을 서로 1 미터 이상 띄워놓아도, 에르되시가 예상했던 것보다 훨씬 작은 공간 안에 모두 담을 수 있다."

이 논문은 수학의 경계를 넓히고, 고차원 기하학의 놀라운 성질을 보여주며, 인공지능이 어떻게 수학의 새로운 지평을 열 수 있는지 보여주는 획기적인 연구입니다.

기술 요약

1. 문제 제기 (Problem Statement)

• 배경: 폴 에르되스 (Pál Erdős) 는 $n$개의 점으로 구성된 유클리드 공간의 점 집합 $C$에 대해, 모든 쌍별 거리 (pairwise distances) 가 서로 최소 1 이상 떨어져 있을 때 (즉, $|x-y| - |x'-y'| \ge 1$), 그 지름 (diameter, $\text{diam}(C)$) 에 대한 하한을 구하는 문제를 제기했습니다.
• 에르되스의 추측: 에르되스는 차원에 관계없이 지름이 $(1+o(1))n^2$ 이상이어야 한다고 추측했습니다. 이는 1 차원에서는 증명되었으나, 고차원에서의 일반성에 대해서는 의문이 제기되어 왔습니다.
• 핵심 질문: 모든 쌍별 거리가 서로 1 이상 간격을 두고 분리되어 있다면, 점 집합의 지름이 반드시 $n^2$에 비례하여 커져야 하는가?

2. 방법론 (Methodology)

저자 Boon Suan Ho 는 이 추측을 반증하기 위해 다음과 같은 명시적 구성 (explicit construction) 을 제시했습니다.

• 싱어 차분 집합 (Singer Difference Sets) 활용:

  • 소수 거듭제곱 $q$를 사용하여 $m = q^2 + q + 1$로 정의합니다.
  • 싱어 정리 (Singer's theorem) 에 따라 $\mathbb{Z}/m\mathbb{Z}$ 위에 크기 $n = q+1$인 차분 집합 $D$를 구성합니다. 이 집합의 특징은 $D$ 내의 임의의 두 원소 $a, b$에 대해 $a-b$가 $m$을 법으로 하여 0 이 아닌 모든 잉여류를 정확히 한 번씩 생성한다는 것입니다.
  • 이를 통해 $D$에서 선택된 $N = \binom{n}{2}$개의 무순서 쌍은 $1, \dots, N$의 순환 분리 (cyclic separation) 값으로 고유하게 인덱싱됩니다.

• 가중치 곱 공간 (Weighted Product Space) 에 점 배치:

  • 점들을 $\mathbb{R}^{2N}$ (즉, $\mathbb{R}^{m-1}$) 공간에 배치합니다.
  • 각 점 $v_t$ ($t \in D$) 는 $N$개의 정규 $m$-각형 (regular $m$-gons) 의 가중치 곱으로 정의됩니다. 각 차원 $r$에서의 가중치 $W_r$은 특정 주파수 성분을 갖도록 설계됩니다.
  • 주파수 섭동 (Frequency Perturbation): 거리의 분포를 조절하기 위해 $W_r$을 다음과 같이 정의합니다.
    $$W_r = \sum_{\substack{j \text{ odd} \\ j \equiv \pm r \pmod m}} \frac{c_j}{j^2}$$
    여기서 $c_1 = 7/8$, $c_j = 1$ ($j \ge 3$) 로 설정하여 거리의 간격 (gap) 을 제어합니다.

• 거리 프로파일 설계:

  • 구성된 점 집합 $Y_m$의 쌍별 거리 $d_s$는 함수 $G(\theta) = \sqrt{H(\theta)}$를 통해 $d_s = G(2\pi s/m)$로 표현됩니다.
  • $H(\theta)$는 $H(\theta) = \frac{\pi\theta}{4} - \varepsilon(1-\cos\theta)$ 형태로, $\varepsilon = 1/8$일 때 $G(\theta)$가 $(0, \pi)$ 구간에서 **엄격하게 증가하고 엄격하게 오목 (strictly concave)**임을 증명합니다.
  • 오목성으로 인해 거리 간격 $d_{s+1} - d_s$는 $s$가 증가함에 따라 감소합니다. 즉, 가장 작은 간격은 마지막 두 거리 ($d_N - d_{N-1}$) 사이에서 발생합니다.

• 스케일링 (Scaling):

  • 모든 쌍별 거리가 최소 1 이상 차이가 나도록, 전체 집합을 $d_N - d_{N-1}$의 역수 ($\lambda_m$) 로 스케일링하여 $X_m = \lambda_m Y_m$을 얻습니다.

3. 주요 결과 (Key Results)

• 정리 1 (Theorem 1):
  • 무한히 많은 $n$에 대해, $\mathbb{R}^{n^2-n}$ 공간에 속하는 $n$개의 점으로 이루어진 집합 $X_n$이 존재합니다.
  • 이 집합은 모든 서로 다른 두 쌍의 거리가 1 이상 차이가 나지만, 그 지름은 다음과 같이 제한됩니다:
    $$\text{diam}(X_n) \le \left(1 - \frac{1}{\pi^2} + o(1)\right) n^2 \approx 0.89867 n^2$$
• 반증: 에르되스가 제안한 $(1+o(1))n^2$ 하한은 고차원 공간에서 성립하지 않습니다. 실제 상수 $c^* = 1 - 1/\pi^2 \approx 0.8987$은 1 보다 작습니다.
• 점근적 분석:
  • $m \to \infty$일 때, 지름과 $m$의 비율은 $\frac{G(\pi)}{2\pi G'(\pi^-)} = 1 - \frac{1}{\pi^2}$로 수렴함이 증명되었습니다.

4. 의의 및 의의 (Significance)

• 추측의 반증: 에르되스의 "차원에 무관한 (dimension-free)" 지름 하한 추측이 거짓임을 보였습니다. 이는 고차원 기하학에서 거리 간격의 제약이 점 집합의 전체적인 크기 (지름) 를 얼마나 강력하게 제한하는지에 대한 이해를 바꿉니다.
• 구체적 구성: 이 결과는 단순한 존재성 증명이 아니라, 싱어 차분 집합과 푸리에 급수 기법을 활용한 명시적인 구성을 제공합니다.
• 형식적 검증: 논문의 모든 증명은 Lean 4를 사용하여 완전히 형식화 (formalized) 되었으며, 이는 수학적 엄밀성을 보장합니다.
• 미래 과제:
  • 이 반증이 특정 차원 $d \ge 2$에 대해 고정된 경우에도 성립하는지는 여전히 미해결 문제입니다 (Remark 9).
  • 저자는 계수 $c_j$를 최적화하면 상수를 약 0.85411 까지 더 낮출 수 있을 것으로 추정합니다 (Remark 10).

5. 결론

이 논문은 고차원 유클리드 공간에서 "모든 쌍별 거리가 1 이상 분리되어 있다"는 조건 하에 지름이 $n^2$에 비례하여 커져야 한다는 에르되스의 직관을 깨뜨렸습니다. 저자는 싱어 차분 집합과 오목한 거리 함수를 결합하여 지름이 약 $0.899 n^2$인 반례를 구성했으며, 이는 형식적 증명 도구를 통해 검증되었습니다. 이 결과는 이산 기하학 (Discrete Geometry) 과 조합론 분야에서 중요한 전환점이 될 것으로 보입니다.