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

本文详细阐述了加博尔·埃勒曼（Gábor Ellmann）于 2004 年发现的盖伊 - 凯利（Guy-Kelly）启发式论证中的错误，从而修正了“无三点共线”问题的猜想上界，并补充了此前文献中缺失的关于该错误及其修正的具体细节。

要点

这篇文章其实是在讲一个数学界持续了半个多世纪的“误会”是如何被澄清的。为了让你轻松理解，我们可以把这篇论文想象成**“修正一张古老藏宝图上的一个微小笔误”**。

以下是用大白话和比喻为你拆解的内容：

1. 背景：什么是“三点不共线”问题？

想象你有一个巨大的$n \times n$ 的网格棋盘（比如 $100 \times 100$），上面有$n^2$ 个格子点。

• 游戏规则：你要在这些点上放棋子，但是有一个铁律：任何三个棋子都不能排成一条直线（不管是横着、竖着还是斜着）。
• 目标：你最多能放多少个棋子？这个最大数量记作 $f_n$。

目前的已知情况：

• 有一个简单的规则告诉我们，你最多只能放 $2n$个棋子（比如$100 \times 100$ 的棋盘，最多放 200 个）。这就像说“每个横排最多放 2 个，否则肯定会有三个连成线”。
• 对于小棋盘（$n \le 64$），大家已经证明确实可以放满 $2n$ 个。
• 但是，数学家们怀疑：当棋盘变得无限大时，你其实放不到 $2n$ 个那么多，数量会稍微少一点点。

2. 曾经的“藏宝图”：Guy 和 Kelly 的猜想

在 1968 年，两位著名的数学家 Guy 和 Kelly 画了一张“藏宝图”。他们用了一种叫**“启发式”**（也就是基于概率的直觉猜测）的方法，试图算出当棋盘无限大时，到底能放多少个棋子。

• 他们的结论：他们认为最大数量大约是 **$2.72 \times n$**（具体公式是$(2\pi^2/3)^{1/3} n$）。
• 这个结论的问题：这个数值比 $2n$还要大！但这在逻辑上是不可能的，因为前面说了，$2n$ 是绝对上限。所以，他们的计算过程里肯定有个地方“算岔了”。

3. 发现错误：2004 年的“笔误”

时间来到 2004 年，一位叫 Gabor Ellmann 的数学家（他在 2024 年再次向 Guy 确认了此事）发现，Guy 和 Kelly 当年的推导过程中，有一个非常隐蔽的代数错误。

• 比喻：这就像你在做一道复杂的数学题，最后一步把公式里的"$x$"错看成了"$2x$"。虽然只是一个小符号的差别，但导致最后算出来的结果（那个藏宝图）完全跑偏了，甚至得出了一个不可能达到的数值。
• 结果：Guy 在 2004 年承认了这个错误，并修正了公式。修正后的新猜想是：最大数量大约是 **$1.81 \times n$**（具体公式是$\pi/\sqrt{3} n$）。

4. 这篇文章在做什么？

虽然 Guy 在 2004 年就知道了错误，但他生前（2020 年去世前）并没有正式发表详细的修正说明。这就导致：

• 很多后来的研究者虽然知道结果变了，但不知道具体错在哪一步，也不知道那个新数字 $1.81$ 是怎么算出来的。
• 网上只有一些零碎的、非正式的说明。

Paul Voutier（本文作者）做了一件“考古”兼“科普”的工作：

1. 还原现场：他把 Guy 和 Kelly 当年的完整推导过程重新写了一遍。
2. 指认错误：他像侦探一样，精准地指出了错误发生的具体位置（原文第 530 页倒数第 4 行）。
   • 错误原因：他们在估算时，不小心把变量 $k$（代表棋子数量系数）当成了固定的 $2$。就像在计算“如果放$k$ 排棋子”时，他们误以为只能放"2 排”，导致公式里的系数算错了。
3. 展示修正：他展示了如果把那个 $2$改回$k$，经过正确的数学推导，就会自然得出那个修正后的神奇数字 **$1.81$**。

5. 总结：这对我们意味着什么？

• 对于数学界：这是一次重要的“纠错”。它确认了那个修正后的猜想（$f_n \sim 1.81n$）是可信的，并且填补了文献中关于“错误具体在哪”的空白。
• 对于普通人：这告诉我们，即使是顶尖的数学家也会犯小错误，而且这个错误可能藏了几十年。科学进步往往就依赖于有人愿意去重新检查那些看似完美的旧公式，把那个微小的“笔误”找出来。

一句话总结：
这篇文章就像是在修补一张流传了 50 年的数学地图，作者指出：“嘿，这里有个小笔误，把 $2$写成了$k$，修正后，我们终于知道在无限大的棋盘上，最多只能放下约$1.81$ 倍于边长的棋子了。”

技术摘要

基于 Paul M. Voutier 的论文《关于无三点共线问题的 Guy-Kelly 猜想》，以下是该文的详细技术总结：

1. 问题背景 (The Problem)

• 核心问题：无三点共线问题（No-Three-in-Line Problem）。
• 定义：设 $S_n$ 为平面上坐标为整数 $(x, y)$ 且 $1 \le x, y < n$的$n^2$个点集。$f_n$表示$S_n$中不包含三点共线的子集$T$ 的最大大小。
• 已知界限：
  • 简单上界：根据鸽巢原理，$f_n \le 2n$。
  • 已知结果：对于 $n \le 64$，已知 $f_n = 2n$（该范围在 2026 年 2 月由 Prellberg 扩展至 $n=64$）。
  • 猜想：当 $n$ 足够大时，$f_n < 2n$。

2. 方法论与原有论证 (Methodology & Original Argument)

• Guy-Kelly 启发式论证 (1968)：
  • Guy 和 Kelly 在论文 [3] 中提出了一种启发式概率论证，试图推导 $f_n$ 的渐近行为。
  • 步骤 1：利用定理计算 $S_n$ 中三点共线的集合数量 $t_n$，得出 $t_n \sim \frac{3}{\pi^2}n^4 \log n$。
  • 步骤 2：计算随机选取三点共线的概率，进而推导 $k n$ 个点中无三点共线的概率（假设事件独立）。
  • 步骤 3：通过斯特林公式（Stirling's approximation）估算解的数量。
  • 原结论：他们推导出当 $k > \pi/\sqrt{3}$ 时，解的数量趋于 0，从而猜想 $f_n \sim (\frac{2\pi^2}{3})^{1/3} n \approx 1.814 n$（注：原文公式 (1) 中的系数推导存在笔误，导致最终形式看似不同，但核心在于他们得出的常数系数）。

3. 关键贡献：错误发现与修正 (Key Contributions: Error Identification & Correction)

• 错误的发现：
  • 2004 年 3 月，Gabor Ellmann 指出 Guy 和 Kelly 的启发式论证中存在一个代数/几何变换错误。
  • 此前，这一错误的细节及其修正从未在正式文献中发表（尽管 A. Flammenkamp 的网页和 Prellberg 的近期工作 [5] 有所涉及）。
• 错误的具体位置：
  • 位于 Guy-Kelly 原论文 [3] 第 530 页第 -4 行。
  • 错误内容：原推导中使用了 $-2 + 3k^3/\pi^2$。
  • 修正内容：正确的表达式应为 $-k + 3k^3/\pi^2$。
  • 错误原因：在估算阶乘项 $(n^2)! / (n^2 - kn)!$ 和 $(kn)!$ 时，错误地使用了 $2n$代替了变量$kn$（即错误地估算了$(n^2)! / (n^2 - 2n)!$和$(2n)!$）。
• 修正后的推导：
  • 修正指数项后，使得 $k - 3k^3/\pi^2 < 0$ 的条件发生变化。
  • 这导致修正后的临界条件变为 $k > \pi/\sqrt{3}$。

4. 主要结果 (Results)

• 修正后的猜想：
  基于 Ellmann 的修正，Voutier 确认了新的渐近上界猜想：
  $$f_n \sim \left( \frac{\pi}{\sqrt{3}} \right) n \approx 1.813799 n$$
  这与 R.K. Guy 在 2004 年私人通信中确认的常数 $c \approx 1.813799$ 一致（即 $3c^2 = \pi^2$）。
• 文献填补：本文首次正式在学术文献中详细记录了该错误的性质、具体位置以及修正过程，填补了从 2004 年发现错误到 2020 年 Guy 去世期间缺乏正式记录的空白。

5. 意义与讨论 (Significance & Discussion)

• 学术价值：
  • 澄清了离散几何中一个著名问题的长期悬案。
  • 提供了 Guy-Kelly 启发式论证的完整修正版推导，使后续研究者能够准确引用该结果。
• 对启发式方法的反思：
  • 文章指出，尽管修正了代数错误，但 Guy-Kelly 论证中的独立性假设（即假设点是否共线是独立事件）近期受到质疑（如 Nathan Kaplan 的研讨会讨论及 Prellberg 的工作）。
  • 某些实证证据（如具有 90 度旋转对称性的网格）对该假设的有效性提出了挑战。
  • 尽管如此，修正后的上界 $f_n \sim (\pi/\sqrt{3})n$ 目前仍被视为该问题最合理的启发式预测。

总结：本文的核心贡献在于正式公开并详细解释了 Gabor Ellmann 发现的 Guy-Kelly 论证中的代数错误，修正了无三点共线问题的渐近上界猜想，将其从错误的推导结果修正为 $f_n \sim (\pi/\sqrt{3})n$，并强调了虽然代数错误已修正，但该启发式方法背后的概率独立性假设仍需进一步验证。