The error of the Guy-Kelly heuristic, measured against exact counts

Abstract

The Guy-Kelly conjecture predicts that the maximum number of points in general position in an n×n grid is asymptotically c·n. We measure how far the heuristic behind it stands from the truth, using the exact counts of A000755 rather than the threshold it predicts, since a threshold inherits the whole error of an estimate without exhibiting its size. The constant in closed form. Measuring the number of collinear triples gives T(n)/n⁴ = (3/π²)ln n − 0.2545, with the coefficient constant to six figures over five doublings. Balancing the terms of order n·ln n then yields α = (3/π²)α³, that is α² = π²/3 and α = π/√3. Guy's original (2π²/3)1/3 is the root of α³ = 2π²/3 — a cubic balance where a quadratic one belongs. Numerically, two implementations sharing no code agree to 10⁻⁵ from n = 16000 and bracket the limit at 1.8138 ± 0.002, containing π/√3 = 1.813799 and excluding the retracted value by thirty times the uncertainty. The error is a function of shape, not of the heuristic. At one and the same n = 20 the discrepancy is a factor of eight million at the hard ceiling m = 2n, eighty-three near the threshold, and reverses sign at m = 1.6n where the heuristic is accurate. Both implementations obtain the low-ratio point to within 0.18 standard deviations. The catastrophic figure usually quoted against the heuristic belongs to the ceiling — which is where the published exact counts happen to live, not where the question is. What cannot be decided, and why not by computing further. Whether the residual error is Θ(n) or Θ(n ln n) determines whether the constant survives. Four three-parameter forms all fit the tail acceptably and three of them imply the opposite conclusion to the fourth, so a coefficient at eighty standard deviations from zero inside one model settles nothing between models. The two candidate bases stay collinear to 0.9993 out to n = 10⁴, so the obstruction is not a shortage of data. This version retracts a claim of its own earlier draft — that at fixed ratio the multiplier is bounded, at thirteen standard deviations. The two points carrying it had five and one hundred sixty successful descents per two hundred thousand attempts; the quoted uncertainty was unattainable from them. The retraction, the hit rates that expose it, and every raw run are included. Disclosure: the computations, the programs and the text were produced by AI agents (Anthropic Claude) under the direction of the author of record, who posed the question, chose what to compute, decided what to claim and is responsible for the content. Two agents worked independently and their disagreements are recorded rather than reconciled silently. Version 1.9, after an external review. The v1.8 abstract still asserted the withdrawn bounded-multiplier claim of the earlier Section 6 — the abstract of a retracted version attached to the corrected text. It is rewritten to match the content. The sign of the correlation in the two-error mechanism of Section 4 was stated backwards (the measured overestimate forces negative correlation — budget rigidity at the ceiling — not positive); the three-dimensional section drew a conclusion from two increments, against this paper's own standard, and is softened to an indication; N. Kaplan is now credited correctly; section cross-references and the r=0.5 table are repaired.