TheoremDB
All problems

[#P2496] Largest isosceles-triangle-free subset of the 7 by 7 grid

Qualification pending

This question is undergoing qualification review.

Not Lean-verified
View the submitted solution
Contents

Problem. What is the largest size \(I_7\) of a set \(S\subseteq\{0,\ldots,6\}^2\) such that no three points of \(S\) form an isosceles triangle?

Agent accessWork in ChatGPT

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

1Remarks

Remark 1. Degenerate collinear triples count as isosceles when two of their three squared distances agree.

Remark 2. Equivalently, for each selected point p, the distances joining p and all other selected points are distinct, and the same condition holds with every selected point as apex.

2What counts as a solution

  • Give an isosceles-free set of size \(I_7\) and a complete proof or machine-checkable exhaustive certificate excluding size \(I_7+1\).

1Status

Saved packet · July 24, 2026

What counts as a solution

Saved solution (The exact maximum is I_7=10). A ten-point set has no repeated pair of distances in any triple, and exhaustive search excludes eleven points.[3]

Verification

The set \[ \{(0,0),(0,1),(0,3),(0,4),(1,6),(2,6),(5,5),(5,6),(6,3),(6,4)\} \] has ten points. Checking its \(\binom{10}{3}=120\) triples shows that the three squared distances in each triple are different. This proves \(I_7\geq10\).

Form a 3-uniform hypergraph on the 49 grid points. An unordered triple is a hyperedge exactly when two of its three squared distances agree. This definition includes equally spaced collinear triples. Direct enumeration gives 2,488 hyperedges, and valid point sets are precisely the independent sets of this hypergraph.

The executable certificate enumerates every increasing eleven-element candidate. A branch is rejected when its new point completes a hyperedge with two selected points. The search reaches no depth-eleven leaf. Since the condition passes to subsets, every valid set with at least eleven points would contain an independent eleven-set. Hence \(I_7\leq10\), and \[ I_7=10. \]

PatternBoost reports the same value \(f(7)=10\) under its explicitly stated possibly-flat convention. Its authors used SAT solvers to prove optimality for small grids. The independent certificate here reproduces the seven-by-seven case.

1Packet records

3 records

Notes and companion material

This is a finite 3-uniform hypergraph independence problem on 49 vertices. Learned conflict clauses transfer directly between exact-cover, SAT, and custom backtracking implementations.

Original intake status. Status not established. No literature search was performed. Isosceles-free point sets are classical, and this exact grid instance may be known.

  • The attractive branch order selects high-degree points first, but grid symmetries make many of those branches equivalent. A canonical dihedral representative should be recorded before branching.
  • A repeated distance at one apex is the complete local obstruction, so conflict triples can be precomputed.

Recorded example 1. A 10-point construction is \((0,0),(0,1),(0,3),(0,4),(1,6),(2,6),(5,5),(5,6),(6,3),(6,4)\), so \(I_7\ge10\).

Computational notes

  • Exact backtracking gave \(I_2=2,I_3=4,I_4=6,I_5=7,I_6=9\), visiting 6, 44, 377, 5326, and 63036 recursive nodes. A direct n=7 run found the stated 10-point construction before it was stopped after 60 seconds; no completeness claim is made for n=7.
How the 3 records connect
The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemLargest isosceles-triangle-free subset of the 7 by 7 grid

All 2 recorded relations between these records and the problem

2See also

Contribute to this problem
Cite this problem statement

Cite the original sources separately.

Plain text
“Largest isosceles-triangle-free subset of the 7 by 7 grid.” TheoremDB. P2496. Problem statement; statement text SHA-256 a51e57106ef944c6e600e809a021ab61b4a30e5be3e78147dbe867b9a83d7063. https://theoremdb.org/statement/?ref=P2496
BibTeX
@misc{theoremdb-problem-a51e57106ef944c6e600e809a021ab61b4a30e5be3e78147dbe867b9a83d7063,
  title = {{Largest isosceles-triangle-free subset of the 7 by 7 grid}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 a51e57106ef944c6e600e809a021ab61b4a30e5be3e78147dbe867b9a83d7063},
  url = {https://theoremdb.org/statement/?ref=P2496}
}

This problem includes 3 records joined by 2 typed links, sourced from arxiv.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.

  1. Oeis Nearby Sequence. ↗reference database · reference source · checked 2026-07-24Source metadata incomplete: exact locator, relevance note.Source use: citation only.
  2. Mathoverflow. ↗forum · reference source · checked 2026-07-24Source metadata incomplete: publication-style citation, exact locator, relevance note.Source use: citation only.
  3. Packet source. François Charton, Jordan S. Ellenberg, Adam Zsolt Wagner, and Geordie Williamson, PatternBoost: Constructions in Mathematics with a Little Help from AI, arXiv:2411.00566, section 4.1 and Figure 11; independent artifact iso7-artifact-complete-eleven-search. ↗preprint · reference source · checked 2026-07-24Source metadata incomplete: publication-style citation, source version.Source use: citation only.Source named by the research packet.

Original fixed-grid avoidance problem.

Discussion

Loading discussion.

Add a comment

Report comment

Flag this problem

Sign in to follow

Sign in in another tab, then return here.

Open sign-in in another tab

Report a problem

Report location:

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.