On the Guy-Kelly Conjecture for the No-Three-In-Line Problem

Each language version is independently generated for its own context, not a direct translation.

🎮 게임의 규칙: "3 점이 일렬로 나란히 오면 안 돼!"

상상해 보세요. 거대한 격자판 (네모난 칸) 이 있습니다. 이 판 위에 점들을 찍는 게임인데, 어떤 3 개의 점도 일직선 위에 있으면 안 됩니다. (예를 들어, 가로, 세로, 대각선으로 3 점이 줄지어 있으면 탈락입니다.)

이제 질문입니다. 이 판이 얼마나 커지든, 최대 몇 개의 점을 찍을 수 있을까요?

🕵️‍♂️ 과거의 오해: "약 2 배의 점" vs "약 1.81 배의 점"

1968 년, 가이 (Guy) 와 켈리 (Kelly) 라는 두 수학자는 이 문제에 대해 흥미로운 추측을 했습니다.
그들은 "판의 한 변의 길이가 $n$ 이라면, 최대 점의 개수는 대략 $n$ 의 약 2 배 ($2n$) 정도일 것"이라고 생각했습니다.

하지만 그들은 단순히 "2 배"라고 말한 게 아니라, **"점의 개수가 $n$ 이 커질수록 정확히 어떤 수식에 따라 변할까?"**를 계산하려 했습니다. 그들이 계산한 공식은 점의 개수가 약 **$1.814 \times n $** 정도가 된다는 것이었습니다. (수학적으로는$ 2\pi^2/3$의 세제곱근을 쓴 식입니다.)

💣 발견된 실수: "계산기 버튼을 잘못 눌렀다"

2004 년, 가보르 엘만 (Gabor Ellmann) 이라는 수학자가 이 두 사람의 계산을 다시 살펴보다가 치명적인 실수를 발견했습니다.

비유로 설명하면:
가이와 켈리는 "우리가 점 $n$ 개를 찍을 때, 실수가 날 확률을 계산했다"고 가정했습니다. 그런데 그들은 계산 과정에서 실제 점의 개수 ( $n$ ) 대신, '최대 가능한 점의 개수 (2n)'를 대입해서 계산해 버린 것입니다.

마치 "우리가 100 명을 초대할 때 파티를 준비한다"고 생각했는데, 계산할 때는 "최대 200 명을 초대할 수 있는 공간"을 기준으로 계산해 버린 것과 같습니다. 이 작은 숫자 하나가 전체 확률 계산식을 뒤흔들었습니다.

🛠️ 수정된 결과: "정답은 1.814 배"

이 실수를 바로잡고 다시 계산해 보니, 가이와 켈리가 원래 의도했던 결론은 **$1.814 \times n$**이라는 것이었습니다.

오래된 추측 (실수 포함): 점의 개수는 $n$ 의 약 2 배 ($2n$) 를 넘지 않는다.
수정된 추측 (올바른 계산): 점의 개수는 $n$ 의 약 1.814 배 ( $\pi/\sqrt{3} \times n$ ) 를 넘지 않는다.

이 논문 (폴 부티에 저자) 의 핵심은 바로 **"그동안 이 실수가 어디서 어떻게 일어났는지, 그리고 어떻게 고쳐졌는지에 대한 상세한 기록이 세상에 없었는데, 이제 그 과정을 공개한다"**는 것입니다.

📝 요약: 이 논문이 우리에게 알려주는 것

오래된 오류: 유명한 수학자들이 1968 년에 계산할 때, 변수를 잘못 대입하는 실수를 했습니다.
발견: 2004 년에 그 실수가 발견되었지만, 왜 그런 실수가 생겼는지, 어떻게 고쳐야 하는지에 대한 구체적인 설명은 책이나 논문으로 나오지 않았습니다.
해결: 이 논문은 그 실수의 정확한 위치와 수정된 계산 과정을 명확하게 보여줍니다.
최신 동향: 2026 년에 발표된 최신 연구 (프레일버그) 에서도 이 수정된 수치가 다시 확인되었습니다.

🌟 결론

이 논문은 수학의 거인들조차 실수할 수 있음을, 그리고 그 실수를 찾아내고 정정하는 과정이 얼마나 중요한지를 보여주는 **수학계의 '오류 수정 보고서'**입니다.

마치 거대한 퍼즐을 맞추는데, 한 조각을 잘못 끼워 넣어서 전체 그림이 조금 왜곡되었던 것을, 누군가가 그 조각을 찾아내어 원래 자리로 돌려놓은 것과 같습니다. 이제 우리는 "3 점이 일렬로 나란히 오지 않게 점 찍기" 게임의 한계에 대해 더 정확한 답을 알게 되었습니다.

Each language version is independently generated for its own context, not a direct translation.

논문 요약: 노 - 쓰리 - 인 - 라인 문제의 가이 - 켈리 추측에 관하여

1. 문제 정의 (The Problem)

노 - 쓰리 - 인 - 라인 (No-Three-in-Line) 문제: $n \times n$ 격자 (정수 좌표 $(x, y)$ , $1 \le x, y \le n $) 에서 세 점이 일직선 위에 오지 않도록 선택할 수 있는 점들의 최대 개수$ f_n$을 구하는 이산 기하학의 고전적인 문제입니다.
현재의 지식:
- 비둘기집 원리 (Pigeon-hole principle) 를 적용하면 $f_n \le 2n$ 임이 쉽게 증명됩니다.
- $n \le 64$ 인 경우 $f_n = 2n$ 임이 알려져 있습니다 (2026 년 2 월 Prellberg 에 의해 $n=64$ 까지 확장됨).
- 그러나 $n$ 이 충분히 크다면 $f_n < 2n$ 일 것이라는 추측이 존재합니다.

2. 기존 연구 및 가이 - 켈리 추측 (Guy-Kelly Conjecture)

1968 년 Guy 와 Kelly 의 연구: 그들은 확률론적 접근법 (Heuristic argument) 을 사용하여 $f_n$ 의 점근적 상한을 추측했습니다.
기존 추측 (식 1):
$f_n \sim \left(\frac{2\pi^2}{3}\right)^{1/3} n \approx 1.814 \dots n$
- 이 추측은 $n$ 개의 점 중 무작위로 3 점을 선택했을 때 일직선이 될 확률과 사건들의 독립성을 가정하여 유도되었습니다.

3. 발견된 오류 및 수정 (The Error and Correction)

오류의 발견: 2004 년 3 월, Gabor Ellmann 이 Guy 와 Kelly 의 유도 과정에서 계산 오류를 발견했습니다.
오류의 위치: 1968 년 논문 [3] 의 530 페이지 4 번째 줄 (Line -4) 에 있습니다.
- 원인: 점의 개수를 $2n $으로 고정하여 계산하는 과정에서, 일반적인$ kn $(여기서$ k $는 상수) 으로 두었을 때의 식을 유도하는 과정에서 실수가 발생했습니다. 구체적으로,$ -2 + 3k^3/\pi^2 $대신$ -k + 3k^3/\pi^2 $가 되어야 하는 부분에서$ 2n $을$ kn $으로 일반화하지 않고$ 2n$을 대입하여 계산한 것이 오류의 근원입니다.
수정된 추측 (식 2):
오류를 수정한 결과, 새로운 상수 $c$ $c$ 는 다음과 같이 도출됩니다.
$3c^2 = \pi^2 \implies c = \frac{\pi}{\sqrt{3}} \approx 1.813799$
따라서 수정된 추측은 다음과 같습니다:
$f_n \sim \frac{\pi}{\sqrt{3}} n$
- 수치적으로는 기존 추측과 매우 유사하지만 ($1.814 $대$ 1.8138$), 수학적 유도가 정확해졌습니다.

4. 방법론 (Methodology)

본 논문은 다음과 같은 논리적 흐름으로 오류를 분석하고 수정했습니다.

기존 유도 재검토: Guy 와 Kelly 가 제시한 $n^2$ 개의 점 중 3 점이 일직선이 되는 집합의 개수 $t_n$ 에 대한 점근식 ( $t_n \sim \frac{3}{\pi^2}n^4 \log n$ ) 을 재확인합니다.
확률 계산: 무작위로 선택된 3 점이 일직선이 아닐 확률을 계산하고, $kn$ 개의 점으로 구성된 집합에서 모든 3 점 조합이 일직선이 아닐 확률을 독립성 가정 하에 추정합니다.
계승 (Factorial) 근사: Stirling 근사 공식을 사용하여 조합 수 $\binom{n^2}{kn}$ $(k n n ^{2})$ 와 확률 항을 결합합니다.
- 기존 논문에서는 $k=2$ 인 경우 ($2n$) 에 대한 계산을 일반화하지 않고 직접 대입하는 과정에서 지수 부분의 계수 오류가 발생했습니다.
오류 식별 및 수정: $k$ 를 변수로 두고 식을 전개할 때, 지수 항이 $-k + 3k^3/\pi^2$ 가 되어야 함을 보이며, 이 값이 음수가 되는 조건 ( $k > \pi/\sqrt{3}$ ) 을 도출하여 수정된 추측을 증명합니다.

5. 주요 기여 (Key Contributions)

오류의 정확한 규명: Gabor Ellmann 이 발견한 오류의 구체적인 위치 (논문 [3] 의 특정 줄) 와 그 수학적 원인을 문헌에 처음 공개했습니다.
수정된 추측의 공식화: $f_n \sim (\pi/\sqrt{3})n$ 이라는 수정된 점근적 상한을 명확히 제시했습니다.
완전한 유도 과정 제시: 오류가 매우 국소적 (localized) 이지만, 완전성을 위해 Guy-Kelly 의 전체 유도 과정을 포함하고 오류가 발생한 지점을 명확히 지적하여 재현했습니다.
최근 연구와의 연결: Thomas Prellberg 가 2026 년에 발표한 논문 [5] 에서도 동일한 수정된 추측을 유도한 사실을 언급하며, 이 주제가 활발히 연구되고 있음을 확인시켰습니다.

6. 의의 및 한계 (Significance and Limitations)

의의: 50 년 이상 지속되어 온 이산 기하학의 중요한 추측에 대한 수학적 엄밀성을 높였습니다. 비록 수치적 차이는 미미하지만, 추측의 이론적 기반을 올바르게 정립했다는 점에서 의미가 큽니다.
한계 및 주의점:
- 본 논문의 핵심은 확률론적 유도 과정의 오류 수정에 있습니다.
- 최근 연구들 (Nathan Kaplan 의 세미나 등) 은 Guy-Kelly 가 사용한 '사건의 독립성 가정' (Independence assumption) 자체에 대한 의문을 제기하고 있습니다. 90 도 회전 대칭 격자 등의 경험적 증거는 이 가정이 타당하지 않을 수 있음을 시사합니다.
- 따라서 수정된 상한 ( $\pi/\sqrt{3}n$ ) 은 '독립성 가정이 성립한다'는 전제 하에 유효한 점근적 상한이며, 실제 $f_n$ 의 정확한 점근적 거리는 아직 완전히 증명되지 않았습니다.

결론

본 논문은 Guy 와 Kelly 의 1968 년 논문에서 발견된 계산 오류를 상세히 분석하고 수정함으로써, 노 - 쓰리 - 인 - 라인 문제의 점근적 상한에 대한 추측을 $\pi/\sqrt{3} \approx 1.8138$ 로 정정했습니다. 이는 해당 분야의 이론적 정확성을 높이는 중요한 기여이며, Prellberg 의 최근 연구와도 일치하는 결과를 제공합니다.