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

- ID: `P2716`
- Reference: `twenty-points-ten-grid-max-squares`
- Page: https://theoremdb.org/statements/P2716
- Record maturity: Reviewed problem with recorded work

## 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?

### Problem setup

- **Remark.** Squares of every size and orientation count.
- **Convention.** Each unordered four-point set is counted once.

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

## Status

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](#reference-1)

## Work

### Evidence for the current status

**Computation 1 (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.

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.

### Background and intake notes

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: Take all points with 0<=x<=4 and 0<=y<=3.

### Open directions

- **Route 1** (supported): Kurz's primary paper supplies both ingredients used here; a 925-variable binary program would settle the remaining finite-grid gap. [2](#reference-2) [1](#reference-1) [3](#reference-3)

### Runnable artifacts

- **Artifact 1** (reproduced): Standard-library Python checks all 3,921,225 grid quadruples, finds 825 squares, and confirms that exactly 32 lie in the witness.

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

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `twenty-points-ten-grid-max-squares`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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 https://arxiv.org/abs/2112.12716
   - Also cited at Theorem 51 and Table 6
   - preprint; reference source; arXiv:2112.12716v1; checked 2026-07-25
   - Source use: citation_only
   - Proves the exact 17-point value 22 and gives the 20-point construction with 32 squares.
   - Source named by the research packet.
2. <a id="reference-2"></a>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 https://epub.uni-bayreuth.de/5936/1/squares_in_plane_point_sets.pdf
   - preprint; primary source; University of Bayreuth repository manuscript checked 2026-07-27; checked 2026-08-01
   - Source use: original_summary
   - Supplies the theorem, table, and appendix coordinates used for the 17-point upper bound and 20-point witness.
3. <a id="reference-3"></a>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 https://oeis.org/A051602
   - reference_database; reference source; web version checked 2026-08-01; checked 2026-07-25
   - Source use: citation_only
   - Records exact maximum-square counts through 17 points and the known lower bound at 20 points.