[#P2492] Distinct-distance general-position sets in the 9 by 9 grid

Contents

Problem. Let \(G_9\) be the largest size of a set \(S\subseteq\{0,\ldots,8\}^2\) such that no three points of \(S\) are collinear and all squared distances \(\|p-q\|^2\), over unordered pairs \(\{p,q\}\subset S\), are distinct. Determine \(G_9\).

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

1Problem setup

Remark 1. Squared Euclidean distances are used, so every comparison is an exact integer comparison.

Definition 1. General position here means that no three selected grid points are collinear.

2What counts as a solution

Give a set of \(G_9\) points satisfying both conditions and a complete certificate that no larger set exists.

1Status

Saved packet · July 24, 2026

What counts as a solution

Saved solution (The exact value is G_9=8). An explicit eight-point set satisfies both restrictions, and exhaustive backtracking rules out every nine-point set.^[3]

Verification

The exact extremal value is \[ \boxed{G_9=8}. \] The set in `ddg9-claim-eight-point-witness` proves the lower bound. It has 28 distinct squared distances and no collinear triple.

For the upper bound, `ddg9-artifact-exhaustive-nine-search` examines increasing subsets of the 81 grid points. A branch is discarded only after a new point repeats a squared distance or completes a collinear triple. Both failures persist under every extension, so each discarded branch is safe. The search reaches no depth-nine node. Therefore no valid nine-point subset exists. Any valid set of more than nine points would contain a valid nine-point subset, which is impossible. The two bounds give the claimed equality.

1Packet records

Show recorded summaries

Record	Kind	Assessment
An explicit eight-point set satisfies both restrictions, and exhaustive backtracking rules out every nine-point set.	Result	Evidence: Computational evidence The record reports a computation within its stated scope. Reproduction requires a separate replay.
claim · Computation 1 An explicit eight-point set satisfies both restrictions, and exhaustive backtracking rules out every nine-point set.^[3] Relevance to this problem This records a result, observation, or conjecture used to assess the target problem. Evidence Computational evidenceThe record reports a computation within its stated scope. Reproduction requires a separate replay. Record state established Scope subsets of the 81 lattice points {0,...,8}^2 with distinct squared distances and no collinear triple Sources Reference 3 Details The exact extremal value is \[ \boxed{G_9=8}. \] The set in `ddg9-claim-eight-point-witness` proves the lower bound. It has 28 distinct squared distances and no collinear triple. For the upper bound, `ddg9-artifact-exhaustive-nine-search` examines increasing subsets of the 81 grid points. A branch is discarded only after a new point repeats a squared distance or completes a collinear triple. Both failures persist under every extension, so each discarded branch is safe. The search reaches no depth-nine node. Therefore no valid nine-point subset exists. Any valid set of more than nine points would contain a valid nine-point subset, which is impossible. The two bounds give the claimed equality. Open full record →
The candidate witness has 28 distinct squared distances and all 56 of its triples have nonzero signed area.	Result	Evidence: Computational evidence The record reports a computation within its stated scope. Reproduction requires a separate replay.
claim · Computation 2 The candidate witness has 28 distinct squared distances and all 56 of its triples have nonzero signed area.^[3] Relevance to this problem This records a result, observation, or conjecture used to assess the target problem. Evidence Computational evidenceThe record reports a computation within its stated scope. Reproduction requires a separate replay. Record state established Scope the stated eight-point subset of {0,...,8}^2 Sources Reference 3 Details Take \[ S=\{(6,0),(8,8),(1,1),(1,3),(8,7),(5,7),(5,1),(6,5)\}. \] Its sorted squared-distance list is \[ [1,2,4,5,8,9,10,13,16,17,20,25,26,29,32,34,36,41,45,50,52,53,58,65,68,74,85,98]. \] The list has \(\binom82=28\) entries and no repetition. For each of the \(\binom83=56\) triples, the verifier evaluates the integer cross product \[ (x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1). \] Every value is nonzero. Hence \(S\) has distinct mutual distances and no three collinear points. Related: Computation 1 Open full record →
The grid distinct-distance problem is classical, and a compiled exact table independently gives the required upper bound.	Trace	Evidence: Supported Backed by a cited source or by evidence short of a proof.
attempt · Route 1 The grid distinct-distance problem is classical, and a compiled exact table independently gives the required upper bound.^[3][1][2] Relevance to this problem This records a line of attack on the target problem, including what it establishes and where it stops. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state completed Scope published and compiled results concerning distinct-distance subsets and general-position subsets of a 9 by 9 lattice grid Sources Reference 3, Reference 1, Reference 2 What happened Lefmann and Thiele define \(f_2(n)\) as the maximum size of a subset of the \(n\times n\) grid with all mutual Euclidean distances distinct. Their 1995 paper develops asymptotic lower bounds and also studies distinct-distance selection when the ambient point set is in general position. It does not report the combined fixed-grid value \(G_9\). OEIS A193838 records the inverse distance-only parameter: the smallest square grid supporting eight points is \(9\times9\), while nine points first occur in a \(10\times10\) grid. This compiled table independently rules out nine distance-distinct points in the present grid, even without imposing general position. Its displayed eight-point example contains a collinear triple, so a separate witness is still needed for the lower bound in this entry. The targeted search covered distinct-distance grid subsets, Golomb squares, no-three-in-line sets, and general-position distance selection. It located no primary source tabulating the exact combined value. The exhaustive artifact provides a self-contained upper-bound certificate, and the verified witness supplies the lower bound. Related: Computation 1 Open full record →
A deterministic C backtracker visits 7,805,045 admissible prefixes and finds no valid set of size nine.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 1 A deterministic C backtracker visits 7,805,045 admissible prefixes and finds no valid set of size nine.^[3] Relevance to this problem This supplies a computation, dataset, or executable check used to assess the target problem. Evidence Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. Record state available Scope every nine-element subset of the 81 lattice points {0,...,8}^2 Sources Reference 3 Entry point `join source_lines with newline as check.c, then run cc -O3 -std=c11 check.c -o check && ./check` Runtime ISO C11; approximately one second with Apple clang 21.0.0 at -O3 Details Grid points are ordered first by \(x\), then by \(y\). The recursion adds points with strictly increasing indices, so every nine-element subset has one possible search path. Three 64-bit masks record used squared distances 0 through 128. Before recursing, the program checks that the new distances are mutually different and absent from the masks. It then checks the new point against every pair of selected points with an exact cross product. Node counts by selected-set size are \[ [1,73,2701,59535,701441,3234340,3441289,365239,426,0]. \] Their sum is 7,805,045. The program considers 76,241,190 candidate extensions. Repeated distances reject 67,073,486, while collinearity rejects 1,362,660 after the distance check. The remaining 7,805,044 extensions are exactly the nonroot nodes in the search tree. No node reaches depth nine. The source asserts every counter before printing its canonical trace. The SHA-256 digest of the complete stdout line, including its final newline, is `761705fa45b932b9871e8e5206d9b2bd774fe6abb4def4c28e6910904626482d`. The same executable verifies the eight-point witness before starting the nonexistence search. Related: Computation 1 Open full record →
No records match these filters.

Notes and companion material

This combines a Golomb-ruler condition on the complete geometric graph with the no-three-in-line condition. Search records can preserve exact excluded branches and symmetry representatives.

Original intake status. Status not established. No literature search was performed. Distinct-distance sets and general-position grid sets are studied topics, so this fixed instance may already have been computed.

A branch-and-bound search can use the number of unused grid points as a cardinality bound. Dihedral symmetry breaking and precomputed incompatibility tables should cut the 9 by 9 instance substantially.
The distance condition alone does not imply general position. A collinear triple can have three different pairwise distances.

Recorded example 1. Eight valid points are \((6,0),(8,8),(1,1),(1,3),(8,7),(5,7),(5,1),(6,5)\), so \(G_9\ge 8\).

Computational notes

Exact depth-first branch-and-bound with integer cross products and squared distances gave \(G_n=2,3,4,5,6,6,7\) for \(2\le n\le8\). The searches visited 6, 54, 444, 3210, 22371, 173346, and 1221336 recursive nodes, respectively. A seeded greedy search of 20000 random point orders found the stated 8-point set for n=9; that greedy run supplies a lower bound only.

How the 4 records connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemDistinct-distance general-position sets in the 9 by 9 grid

All 3 recorded relations between these records and the problem

Eight points satisfy both restrictions supports The exact value is G_9=8
Exhaustive nonexistence certificate for nine points is evidence for The exact value is G_9=8
Prior work covers the distance-only problem corroborates The exact value is G_9=8

2See also

Grid points with no three collinear and no four concyclicdiscrete geometry
Distinct nonzero triangle areas in the 9 by 9 griddiscrete geometry
Largest isosceles-triangle-free subset of the 7 by 7 griddiscrete geometry

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Distinct-distance general-position sets in the 9 by 9 grid.” TheoremDB. P2492. Problem statement; statement text SHA-256 efcaa0d14bd85da05d1dcf9e800e336a898a67a8cf5a1f6f22bc998d6482459d. https://theoremdb.org/statement/?ref=P2492

BibTeX

@misc{theoremdb-problem-efcaa0d14bd85da05d1dcf9e800e336a898a67a8cf5a1f6f22bc998d6482459d,
  title = {{Distinct-distance general-position sets in the 9 by 9 grid}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 efcaa0d14bd85da05d1dcf9e800e336a898a67a8cf5a1f6f22bc998d6482459d},
  url = {https://theoremdb.org/statement/?ref=P2492}
}

Plain text: Built Markdown snapshot

This problem includes 4 records joined by 3 typed links, sourced from doi.org^[3], current as of July 24, 2026.

1Lean verification

Lean formalization needed

A solution has been submitted and awaits independent review.

Open TheoremDB Researcher

Upload a Lean project archive

Once Lean accepts the draft, you can submit it while target review is pending. Your submission request is saved and continues after approval. Private checks stay private until you choose to submit.

1References

3 entries have incomplete source metadata. Each affected row names the fields that still need editorial review.

Open Preprint. ↗website · reference source · checked 2026-07-24Source metadata incomplete: publication-style citation, exact locator, relevance note.Source use: citation only.
Compiled Exact Table. ↗reference database · reference source · checked 2026-07-24Source metadata incomplete: exact locator, relevance note.Source use: citation only.
Packet source. Independent witness and exhaustive certificate in ddg9-claim-eight-point-witness and ddg9-artifact-exhaustive-nine-search. ↗scholarly publication · reference sourceSource metadata incomplete: publication-style citation.Source use: citation only.Source named by the research packet.Also cited at Direct integer verification in ddg9-artifact-exhaustive-nine-search.Also cited at Inline ISO C11 source executed with Apple clang 21.0.0 on 2026-07-24.

Original finite grid extremal problem.

Discussion

Loading discussion.

[#P2492] Distinct-distance general-position sets in the 9 by 9 grid

1Problem setup

2What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Problem setup

2What counts as a solution

1StatusSolution submittedNot Lean-verified

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance

1Status