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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Certified exact values for the no-three-in-line problem in the three-dimensional grid

Aleksei Kudriashov
Zenodo (CERN European Organization for Nuclear Research)
Computational Geometry and Mesh Generation
preprint

Certified exact values for the no-three-in-line problem in the three-dimensional grid

Aleksei Kudriashov
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
National Heritage Institute (TN)
Peace, Justice and strong institutions
Computational Geometry and Mesh Generation
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.