MathLabs

未解决问题，组合数学与离散数学, 几何学，1917年提出

无三点共线问题

未解决

对每个整数 n≥2n \ge 2，确定从 n×nn \times n 格点阵 {1,2,…,n}2\{1, 2, \dots, n\}^2 中最多可选出多少个点 f(n)f(n)，使得所选点中没有任何三点位于同一条任意斜率的直线上；特别地，判定是否对所有 nn 都有 f(n)=2nf(n) = 2n，抑或 lim⁡n→∞f(n)/n<2\lim_{n \to \infty} f(n)/n < 2。

研究前沿 截至2026年

截至2026年，渐近比值 lim⁡n→∞f(n)/n\lim_{n \to \infty} f(n)/n 依然未知，仍夹在1975年霍尔–杰克逊–萨德伯里–怀尔德的代数下界 32=1.5\frac{3}{2} = 1.5 与抽屉原理给出的平凡上界 22 之间。计算机搜索（弗拉门坎普、普雷尔贝格、霍伊勒等人）已对所有 n≤74n \le 74 找到了含 2n2n 个格点的无三点共线配置，但随着 nn 增大，对称 2n2n 点解的数量明显减少，从经验上支持了盖伊–凯利启发式猜测 f(n)∼π3n≈1.8138nf(n) \sim \frac{\pi}{\sqrt{3}} n \approx 1.8138n。

已知最佳结果

  • 对所有 n≥2n \ge 2，有 (32−o(1))n≤f(n)≤2n(\frac{3}{2} - o(1))n \le f(n) \le 2n（霍尔、杰克逊、萨德伯里与怀尔德，1975）。
  • 借助计算机显式构造的配置，对所有 2≤n≤742 \le n \le 74 精确等式 f(n)=2nf(n) = 2n 均成立。

使用的方法及其局限

方法取得的结果局限所在
有限域 Fp\mathbb{F}_p 上的代数曲线法（埃尔德什、霍尔–杰克逊–萨德伯里–怀尔德）利用 Fp\mathbb{F}_p 上的贝祖定理——即任意直线与不可约二次曲线（如 y≡x2(modp)y \equiv x^2 \pmod p 或 xy≡k(modp)xy \equiv k \pmod p）在模 pp 意义下至多交于 22 点，进而在 Z2\mathbb{Z}^2 中也至多交于 22 点——构造出 (3/2−o(1))n(3/2 - o(1))n 个点。Fp\mathbb{F}_p 上次数 d≥3d \ge 3 的曲线可能与直线交于 33 个及以上点，而拼接多个平移二次曲线在密度超过 3n/23n/2 时会在不同区块之间产生跨区共线三元组。

尚未解决的问题

  • 是否存在整数 n≥2n \ge 2 使得 f(n)<2nf(n) < 2n？
  • 极限 lim⁡n→∞f(n)/n\lim_{n \to \infty} f(n)/n 是否存在？若存在，它是否严格小于 22（例如等于 π/3≈1.8138\pi/\sqrt{3} \approx 1.8138）？

参考文献

  1. Klaus Friedrich Roth (with an appendix by Paul Erdős) (1951). On a problem of formal logic · DOI:10.1112/jlms/s1-26.3.198
  2. Richard K. Guy, Patrick A. Kelly (1968). The no-three-in-line problem · DOI:10.4153/CMB-1968-062-3
  3. R. R. Hall, T. H. Jackson, A. Sudbery, K. Wild (1975). Some advances in the no-three-in-line problem · DOI:10.1016/0097-3165(75)90043-6