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

This paper details a previously unrecorded error in Guy and Kelly's 2004 heuristic argument for the no-three-in-line problem, identified by Gabor Ellmann, and presents the resulting correction to their conjectured upper bound.

The Gist

Imagine you have a giant grid of dots, like a piece of graph paper, where the side length is $n$. So, if $n=10$, you have a $10 \times 10$ grid with 100 dots total.

The "No-Three-in-Line" problem is a simple game with a tricky rule: You want to pick as many dots as possible from this grid, but you are forbidden from picking three dots that form a straight line. It's like playing a game of "Don't draw a straight line" with your finger on the dots.

The Old Rule of Thumb

For a long time, mathematicians knew a simple limit: You can't pick more than $2n$dots. Why? Because if you have$n$rows, and you pick 3 dots in any single row, you've broken the rule. So, the safest bet is to pick at most 2 dots per row, giving you$2n$ dots total.

For small grids (up to size 64), we know you can actually reach this limit of $2n$. But mathematicians suspected that as the grid gets huge (infinite size), you can't quite reach$2n$. You have to leave some dots behind to avoid accidental lines.

The "Guy and Kelly" Guess

In 1968, two mathematicians named Guy and Kelly tried to guess exactly how many dots you could pick as the grid gets infinitely big. They used a method called heuristic reasoning.

Think of their method like this:

1. The Coin Flip: Imagine you are randomly picking dots. What are the odds that any three random dots happen to line up perfectly?
2. The Calculation: They calculated that the chance of three dots lining up is very small, but not zero.
3. The Multiplication: They assumed that if you pick a certain number of dots, the "bad luck" of finding a line happens independently for every group of three.
4. The Result: Based on their math, they concluded that the maximum number of dots you can pick grows like **$1.81 \times n$** (specifically,$\frac{2\pi^2}{3}^{1/3} n$).

The Mistake: A Typo with Big Consequences

In 2004, a mathematician named Gabor Ellmann found a tiny, almost invisible error in Guy and Kelly's math.

The Analogy:
Imagine Guy and Kelly were trying to calculate how much space a crowd of people would take up in a room.

• They correctly calculated the space for a crowd of $k$ people.
• But, somewhere in their notes, they accidentally wrote down the number $2$** instead of **$k$.
• Because of this, they calculated the space for a crowd of 2 people, but then used that result to predict the space for a crowd of $k$ people.

In the paper, the author points out that Guy and Kelly used the number $2n$** (the old, known limit) in their formula where they should have used a variable **$kn$ (the unknown number they were trying to find).

Because of this mix-up, their final formula was slightly off.

The Correction

When Gabor Ellmann fixed this tiny error, the math changed. The new, corrected guess for the maximum number of dots is:

$$\text{Max Dots} \approx \frac{\pi}{\sqrt{3}} \times n \approx 1.8138 \times n$$

While the old guess was roughly $1.817 \times n$, the new one is slightly smaller. It's a very small difference, but in the world of pure math, getting the exact constant right is like finding the perfect key for a lock.

Why This Paper Matters

This short paper by Paul Voutier is essentially a "correction notice."

• The Mystery: For 20 years, everyone knew Guy and Kelly's guess was wrong, but the exact where and how of the mistake wasn't written down in any official math journal. It was just a rumor in private emails.
• The Mission: Voutier wrote this paper to officially document the error, show exactly where the typo was (a specific line on page 530 of the old paper), and prove the new, correct formula.
• The Context: He also mentions that a very recent researcher, Prellberg, has independently found the same answer, which gives everyone extra confidence that the new number is correct.

The Bottom Line

The "No-Three-in-Line" problem is a puzzle about arranging dots without making straight lines.

1. Old Guess: You can pick about $1.817 \times n$ dots.
2. The Error: The original math accidentally swapped a variable for a fixed number.
3. New Truth: You can actually pick about $1.814 \times n$ dots.

It's a reminder that even brilliant mathematicians can make a small typo that changes the answer, and that sometimes, the most important work is simply cleaning up the notes to make sure the rest of the world gets the right answer.

Technical Summary

Based on the paper "On the Guy-Kelly Conjecture for the No-Three-in-Line Problem" by Paul M. Voutier, here is a detailed technical summary:

1. Problem Statement

The paper addresses the No-Three-in-Line Problem, a classic problem in discrete geometry.

• Definition: Let $S_n$ be the set of $n^2$ points in $\mathbb{R}^2$ with integer coordinates $(x, y)$ where $1 \le x, y \le n$. Let$f_n$be the maximum size of a subset$T \subseteq S_n$such that no three points in$T$ are collinear.
• Current Knowledge: The trivial upper bound is $f_n \le 2n$ (derived from the pigeonhole principle). It is known that $f_n = 2n$ for $n \le 64$ (with the extension to $n=64$ recently achieved by Prellberg in 2026).
• The Conjecture: It is conjectured that for sufficiently large $n$, $f_n < 2n$. In 1968, Guy and Kelly proposed a heuristic argument suggesting the asymptotic behavior:
  $$f_n \sim \left(\frac{2\pi^2}{3}\right)^{1/3} n \approx 1.8138 n$$
  However, a private communication in 2004 revealed an error in their derivation, leading to a corrected conjecture:
  $$f_n \sim \frac{\pi}{\sqrt{3}} n \approx 1.8138 n$$
  (Note: While the numerical values appear similar in the text, the algebraic forms differ, and the correction is the primary focus of this paper.)

2. Methodology

Voutier's paper does not introduce new probabilistic models but rather provides a critical reconstruction and correction of the original heuristic argument presented by Guy and Kelly.

• Review of Original Heuristic: The paper re-examines the probabilistic argument used by Guy and Kelly.
  1. They calculated the number of collinear triplets ($t_n$) in $S_n$ as $t_n \sim \frac{3}{\pi^2} n^4 \log(n)$.
  2. They derived the probability that three random points are collinear.
  3. Assuming independence, they calculated the probability that a set of $k n$ points contains no three collinear points.
  4. They estimated the total number of such subsets using combinatorial approximations involving factorials and Stirling's approximation.
• Identification of the Error: Voutier traces the specific algebraic mistake in the original 1968 paper.
  • The Mistake: In the original derivation (specifically on page 530, line -4 of their paper), Guy and Kelly incorrectly substituted $2n$for the variable$kn$ during the estimation of factorial terms.
  • The Correction: The term $-2 + \frac{3k^3}{\pi^2}$ in their original equation was incorrect. It should have been $-k + \frac{3k^3}{\pi^2}$. This error arose because they estimated $(n^2)! / (n^2 - 2n)!$ and $(2n)!$ instead of the general $(n^2)! / (n^2 - kn)!$ and $(kn)!$ required for the asymptotic analysis of a subset of size $kn$.

3. Key Contributions

• First Published Correction: While the error was identified by Gabor Ellmann in 2004 and mentioned in private communications and online forums (e.g., A. Flammenkamp's website), Voutier provides the first formal, detailed publication of the nature of the error and its mathematical correction in the academic literature.
• Derivation of the Corrected Conjecture: The paper explicitly demonstrates how correcting the algebraic error leads to the revised asymptotic bound.
  • The condition for the number of solutions to approach zero as $n \to \infty$ changes from the original incorrect derivation to the condition where the exponent in the probability estimate becomes negative.
  • This yields the corrected conjecture: $f_n \sim \frac{\pi}{\sqrt{3}} n$.
• Contextualization: The paper acknowledges recent independent work by Prellberg (2026) who also derived the corrected bound, but emphasizes that Voutier's contribution is the explicit documentation of the specific error in the original Guy-Kelly logic.

4. Results

• Corrected Asymptotic Bound: The paper confirms that the heuristic argument, when corrected, supports the conjecture that:
  $$f_n \sim \frac{\pi}{\sqrt{3}} n$$
• Validation of the Error Location: The paper pinpoints the exact location of the error in the original 1968 text (Page 530, line -4), clarifying that the substitution of $2n$for$kn$ was the root cause of the discrepancy in the exponent of the probability estimate.

5. Significance

• Resolution of a Long-Standing Ambiguity: For nearly two decades, the precise nature of the error in the Guy-Kelly conjecture was known only through private correspondence and informal online notes. This paper formalizes the correction, ensuring the mathematical record is accurate.
• Clarification of Heuristic Limits: The paper highlights the fragility of heuristic arguments in combinatorial geometry. It notes that while the independence assumption in the Guy-Kelly argument has been questioned (e.g., by Kaplan and Prellberg regarding rotational symmetry and empirical data), the algebraic correction of the original derivation is necessary regardless of the validity of the independence assumption.
• Foundation for Future Research: By providing the correct derivation, the paper establishes a solid baseline for future researchers attempting to prove or disprove the asymptotic behavior of $f_n$, distinguishing between errors in calculation versus errors in probabilistic modeling.

In summary, Voutier's paper serves as a necessary erratum and technical clarification, ensuring that the corrected upper bound for the No-Three-in-Line problem is properly attributed and mathematically justified within the formal literature.