[#P2716] Most squares spanned by twenty points of the ten grid

Problem. Choose \(20\) points from \(\{0,1,\ldots,9\}^2\). What is the largest number of nondegenerate Euclidean squares whose four vertices are all chosen?

Agent access

Work on this problem in ChatGPT

Definitions and notation

1Problem setup

Remark 1. Squares of every size and orientation count.

Convention 1. Each unordered four-point set is counted once.

2What counts as a solution

Give a 20-point set attaining the maximum and a complete integer-programming, branch-and-bound, or flag-algebra certificate for the matching upper bound.

1Status

What counts as a solution

Current status (The maximum lies between 32 and 43). A 20-point set in a 5 by 5 window spans 32 squares, while deletion averaging from the exact 17-point planar theorem gives a universal upper bound of 43.^[1]

1Packet records

Show recorded summaries

Record	Kind	Assessment
A 20-point set in a 5 by 5 window spans 32 squares, while deletion averaging from the exact 17-point planar theorem gives a universal upper bound of 43.	Result	Evidence: Reproduced A replay is recorded for this computation. Inspect the replay record for its procedure and scope.
claim · Computation 1 A 20-point set in a 5 by 5 window spans 32 squares, while deletion averaging from the exact 17-point planar theorem gives a universal upper bound of 43.^[1] Relevance to this problem For Most squares spanned by twenty points of the ten grid, record tptgms-claim-certified-interval-32-43 (“The maximum lies between 32 and 43”) records a bound, answer, status fact, or structural consequence. The record states: A 20-point set in a 5 by 5 window spans 32 squares, while deletion averaging from the exact 17-point planar theorem gives a universal upper bound of 43. Evidence ReproducedA replay is recorded for this computation. Inspect the replay record for its procedure and scope. Record state partial Scope all 20-element subsets of the 100 lattice points {0,1,...,9}^2, counting every nondegenerate Euclidean square once Sources Reference 1 Details Write \(M\) for the requested maximum. The following points lie in the ten grid: \[ \begin{aligned} P=\{&(2,2),(2,3),(2,4),\\ &(3,2),(3,3),(3,4),(3,5),\\ &(4,1),(4,2),(4,3),(4,4),(4,5),\\ &(5,1),(5,2),(5,3),(5,4),(5,5),\\ &(6,2),(6,3),(6,4)\}. \end{aligned} \] Exact enumeration finds 32 squares in \(P\). Their squared side lengths have multiplicities \[ 1:11,\quad 2:8,\quad 4:4,\quad 5:7,\quad 8:1,\quad 10:1. \] Hence \(M\geq32\). For the upper bound, let \(U_n\) bound the number of squares in every \(n\)-point set in the plane. If an \(n\)-point set spans \(q\) squares, sum the square counts after deleting each point. Every square survives exactly \(n-4\) deletions, so \[ (n-4)q\leq nU_{n-1}. \] Kurz proved \(U_{17}=22\). Iterating the displayed inequality and taking integer parts gives \[ U_{18}\leq\left\lfloor\frac{18\cdot22}{14}\right\rfloor=28, \quad U_{19}\leq\left\lfloor\frac{19\cdot28}{15}\right\rfloor=35, \quad U_{20}\leq\left\lfloor\frac{20\cdot35}{16}\right\rfloor=43. \] This applies to every planar 20-point set, including subsets of the ten grid. Therefore \[ \boxed{32\leq M\leq43}. \] The exact value remains open in this record. Open full record →
Kurz's primary paper supplies both ingredients used here; a 925-variable binary program would settle the remaining finite-grid gap.	Trace	Evidence: Supported Backed by a cited source or by evidence short of a proof.
attempt · Route 1 Kurz's primary paper supplies both ingredients used here; a 925-variable binary program would settle the remaining finite-grid gap.^[2][1][3] Relevance to this problem For Most squares spanned by twenty points of the ten grid, record tptgms-attempt-literature-audit-and-exact-model (“The literature gives 32 as the planar record and 22 as the exact 17-point value”) documents a concrete method, search boundary, or failed route. The record states: Kurz's primary paper supplies both ingredients used here; a 925-variable binary program would settle the remaining finite-grid gap. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state next experiment Scope published results on squares spanned by small planar point sets, with a proposed exact optimization over the 825 square hyperedges of the ten grid Sources Reference 2, Reference 1, Reference 3 What happened Kurz studies \(S_{\square}(n)\), the largest number of squares spanned by \(n\) arbitrary planar points. Theorem 51 proves \(S_{\square}(17)=22\). Table 6 records the lower bounds 25, 28, and 32 for 18, 19, and 20 points. Appendix C lists point-set representatives. The paper describes the 20-point value as a lower bound, so it does not settle the present finite-grid maximum. The same 32-square pattern fits inside \(\{0,\ldots,9\}^2\), as the executable record verifies. A focused search for the fixed-cardinality ten-grid problem found no paper giving an exact optimum or a grid-specific upper certificate. A direct exact model uses one binary variable \(x_p\) for each of the 100 grid points and one binary variable \(y_s\) for each of the 825 grid squares. Impose \[ \sum_p x_p=20,\qquad y_s\leq x_p\quad(p\in s), \] and maximize \(\sum_s y_s\). Positivity of the objective forces \(y_s=1\) whenever all four vertices of \(s\) are selected. This model has 925 binary variables and 3,301 linear constraints. A solver proof log, checked independently against the 825-square list digest in this record, would close the interval. Related: Computation 1 · Computation 1 Open full record →
Standard-library Python checks all 3,921,225 grid quadruples, finds 825 squares, and confirms that exactly 32 lie in the witness.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 1 Standard-library Python checks all 3,921,225 grid quadruples, finds 825 squares, and confirms that exactly 32 lie in the witness. Relevance to this problem For Most squares spanned by twenty points of the ten grid, record tptgms-artifact-exact-square-verifier (“Exact four-subset square verifier”) supplies evidence or a replay used to check the packet. The record states: Standard-library Python checks all 3,921,225 grid quadruples, finds 825 squares, and confirms that exactly 32 lie in the witness. Evidence Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. Record state available Scope all four-subsets of the 100 points in {0,1,...,9}^2 and all four-subsets of the displayed 20-point witness Entry point `Join source_lines with LF characters and execute the resulting Python program` Runtime CPython 3, standard library only Details A quadruple is accepted precisely when its six squared pair distances consist of four copies of a positive integer \(d\) and two copies of \(2d\). This distance test is invariant under orientation and counts each unordered vertex set once. The program applies the test to every four-subset of the ten grid. It finds 825 squares. It then filters those squares by containment in the displayed witness and independently tests all 4,845 witness quadruples. Both routes return the same ordered list of 32 squares. The canonical list has SHA-256 digest `6c44a24e1b8a7a1cfb59815218f4f1a9af988ad41c3e114f05772ec5094c682c`. The final four integers replay the deletion-averaging arithmetic. The starting value 22 is the external mathematical input supplied by Kurz's Theorem 51. The canonical report has SHA-256 digest `05b18b55243fed5de2d6417dc98e7e385f0249cde1cd2bf472d1769c6b975e22`. Related: Computation 1 Open full record →
No records match these filters.

Notes and companion material

A five by four rectangular block proves a lower bound of 30 squares.

Original intake status. Novelty remains unverified. No primary-source status audit was completed for this cardinality and grid size.

The grid contains 825 square four-sets after canonical deduplication, so the problem is a fixed-cardinality densest-subhypergraph instance.
Counting only axis-parallel squares misses tilted squares, including squares with side vector (1,2).
Pair-based square generation creates every square eight times unless the vertex set is canonicalized.

Recorded example 1. Take all points with 0<=x<=4 and 0<=y<=3.

Computational notes

Exact enumeration found 825 distinct squares in the 10 by 10 point grid. The displayed 20-point block contains 30 of them, including tilted squares; an independent set-containment check verified every counted quadruple.

How the 3 records connect

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

ProblemMost squares spanned by twenty points of the ten grid

All 3 recorded relations between these records and the problem

2See also

Grid points with no three collinear and no four concyclicdiscrete geometry
Largest equilateral-triangle-free subset of the fifteen-row triangular latticediscrete geometry
Most lattice points with all pairwise slopes distinct in a ten by ten griddiscrete geometry

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Most squares spanned by twenty points of the ten grid.” TheoremDB. P2716. Problem statement; statement text SHA-256 1cf7aeaef1ef0024d5d08afed9467f4b4f0fdf97b091e67c76ddae3c7072479a. https://theoremdb.org/statement/?ref=P2716

BibTeX

@misc{theoremdb-problem-1cf7aeaef1ef0024d5d08afed9467f4b4f0fdf97b091e67c76ddae3c7072479a,
  title = {{Most squares spanned by twenty points of the ten grid}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 1cf7aeaef1ef0024d5d08afed9467f4b4f0fdf97b091e67c76ddae3c7072479a},
  url = {https://theoremdb.org/statement/?ref=P2716}
}

Plain text: Built Markdown snapshot

This problem includes 3 records joined by 3 typed links, sourced from arxiv.org^[1], current as of July 25, 2026.

1Lean verification

1References

Packet source. Sascha Kurz, Plane point sets with many squares or isosceles right triangles, arXiv:2112.12716v1 (2021). Sascha Kurz, Plane point sets with many squares or isosceles right triangles, Theorem 51 for S_square(17)=22 and Table 6 for the 20-point lower bound 32; finite-grid witness replay in tptgms-artifact-exact-square-verifier. ↗preprint · reference source · arXiv:2112.12716v1 · checked 2026-07-25Source use: citation only.Proves the exact 17-point value 22 and gives the 20-point construction with 32 squares.Also cited at Theorem 51 and Table 6.Source named by the research packet.For Most squares spanned by twenty points of the ten grid: A 20-point set in a 5 by 5 window spans 32 squares, while deletion averaging from the exact 17-point planar theorem gives a universal upper bound of 43.
Sascha Kurz, Plane point sets with many squares or isosceles right triangles, University of Bayreuth repository manuscript (2021), 31 pp. Theorem 51, Table 6, and Appendix C. ↗preprint · primary source · University of Bayreuth repository manuscript checked 2026-07-27 · checked 2026-08-01Source use: original summary.Supplies the theorem, table, and appendix coordinates used for the 17-point upper bound and 20-point witness.Also cited at Sascha Kurz, Plane point sets with many squares or isosceles right triangles, Theorem 51, Table 6, and Appendix C.For Most squares spanned by twenty points of the ten grid: Kurz's primary paper supplies both ingredients used here; a 925-variable binary program would settle the remaining finite-grid gap.
OEIS Foundation Inc., A051602, maximal number of squares formed by n points in the plane (checked 27 July 2026). Definition, exact values through n=17, comments, and references. ↗reference database · reference source · web version checked 2026-08-01 · checked 2026-07-25Source use: citation only.Records exact maximum-square counts through 17 points and the known lower bound at 20 points.Also cited at comments, references, and linked record table.

Original CC0 finite incidence optimization problem.

[#P2716] Most squares spanned by twenty points of the ten 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

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance