Certified exact values for the no-three-in-line problem in the three-dimensional grid
a(n) is the maximum number of points in the n×n×n grid with no three of them collinear in R3. Pór and Wood proved a(n) = Θ(n²); no exact values appear to have been recorded, and the sequence does not appear to be in the OEIS. We determine a(1..6) = 1, 8, 16, 28, 40, 64, give certified lower bounds a(7) ≥ 71 and a(8) ≥ 89, and prove a(p) ≥ p² for every prime p by an elementary construction from an anisotropic binary quadratic form. The method is a certified decision procedure rather than a search. A line carrying at most two lattice points forbids nothing, so admissibility is exactly “at most two chosen points on every line with three or more lattice points” — a propositional formula on n³ variables. Unsatisfiability is answered with a DRAT certificate that an independent checker verifies; lower bounds are witnesses re-verified by exhaustive integer arithmetic over every triple. We are explicit about the four separate links this requires — that the formula expresses the problem, that it is unsatisfiable, that the symmetry pruning discards nothing, and that the case split is complete — because a certificate attests only to the formula it was given, and an error in the others would pass through it unseen. The optima share a layer structure that fails at exactly one computed size. Requiring both outer layers to attain the planar maximum 2n costs nothing at n = 4 and n = 6 (maximum totals 28 and 64, equal to the optima) and exactly one point at n = 5 (39 against 40). We have no explanation. The upload includes a step-by-step verification protocol written for a reader who trusts none of the authors' code, a self-audit checking every number in the note against the file that produced it, and an explicit statement of what is not claimed. 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.
Authors
- Aleksei Kudriashov (ORCID: https://orcid.org/0009-0006-8885-5338)
Institutions
- National Heritage Institute (TN)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-08-20
- DOI
- https://doi.org/10.5281/zenodo.22019280
- Primary Topic
- Computational Geometry and Mesh Generation
- Type
- preprint