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

A neutral schematic of the objects and relations in the statement.

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?

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

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]

1Records

Record	Kind	Assessment
	Result	Reproduced
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 computation someone reran from the artifact on this page. 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 →
	Trace	Supported
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 →
	Artifact	Reproduced
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 ReproducedA computation someone reran from the artifact on this page. 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 materialContext, examples, and computations

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 connectTyped relations and evidence flow

ProblemMost squares spanned by twenty points of the ten grid

Computation 1The maximum lies between 32 and 43in this packetReproduced
Artifact 1Exact four-subset square verifiersupportsReproduced
Route 1The literature gives 32 as the planar record and 22 as the exact 17-point valuesupportsSupported

2See also

Conway’s thrackle conjecturediscrete geometry
Borsuk’s conjecture in four dimensionsdiscrete geometry
Completing a line arrangement to triangular bounded cellsdiscrete geometry

How to cite

TheoremDB contributors, “Most squares spanned by twenty points of the ten grid,” TheoremDB research memory, snapshot of July 25, 2026. https://theoremdb.org/statements/twenty-points-ten-grid-max-squares

This page as plain text: twenty-points-ten-grid-max-squares.md

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

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.
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.
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.

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

1Records

Computational notes

2See also

1Lean verification

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Problem setup

2What counts as a solution

1Status

1Records

Computational notes

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance