# P2682: Most lattice points with all pairwise slopes distinct in a ten by ten grid

- ID: `P2682`
- Reference: `distinct-slopes-ten-grid`
- Page: https://theoremdb.org/statements/P2682
- Record maturity: Reviewed problem with recorded work

## Problem

Determine the largest subset \(A\subseteq\{0,\ldots,9\}^2\) such that no two distinct unordered pairs of points in \(A\) determine parallel segments.

### Remarks

- **Remark.** Two segments have the same slope when their primitive integer direction vectors agree up to sign.
- **Remark.** The condition forbids three collinear points as well as parallel disjoint segments.

### What counts as a solution

- Give a maximum set and a complete branch-and-bound, SAT, or clique certificate excluding one more point.

## Status

A new 10-point witness improves the lower bound, while the complete direction count gives 15. [4](#reference-4)

## Work

### Evidence for the current status

**Computation 1 (The maximum lies between 10 and 15).** A new 10-point witness improves the lower bound, while the complete direction count gives 15.

Let \(M_{10}\) denote the maximum. The point set
\[
A=\{(0,7),(1,2),(2,0),(4,6),(5,3),(6,9),(7,1),(8,1),(9,5),(9,8)\}
\]
has ten points. Reducing every difference vector by the greatest common divisor of its coordinates, with a fixed sign convention, produces 45 distinct primitive directions. Thus \(M_{10}\geq10\).

For the upper bound, every segment direction has a unique representative \((a,b)\) with \(0\leq a\leq9\), \(-9\leq b\leq9\), \(\gcd(a,|b|)=1\), and \(a>0\), apart from the vertical representative \((0,1)\). Exact enumeration gives 112 supported undirected directions. A \(k\)-point set in the problem uses a different direction for each of its \(\binom{k}{2}\) pairs, so
\[
\binom{k}{2}\leq112.
\]
Since \(\binom{15}{2}=105\) and \(\binom{16}{2}=120\), this proves \(M_{10}\leq15\). The certified interval is therefore
\[
\boxed{10\leq M_{10}\leq15}.
\]
The exact value remains unresolved in this entry.

### Background and intake notes

The certified interval is 9 through 15. The upper bound follows from C(k,2)<=112, and the lower bound is an explicit construction.

- Original intake status: Novelty remains unverified. No primary-source status audit was completed for this exact grid instance.
- Store each used slope as a normalized primitive pair (a,b) with a>0, or a=0 and b>0. Adding one point must create pairwise new slopes disjoint from the stored set.
- The pair-count bound uses all 112 slopes available anywhere in the box and gives size at most 15. Most slope sets cannot be realized simultaneously, so a geometric branch bound should be much sharper.
- Translations, reflections, and coordinate exchange can normalize the first points.

- Recorded example: A 9-point incumbent is (3,8),(1,1),(0,8),(6,9),(5,5),(1,2),(7,0),(9,4),(8,7).

### Prior approaches

- **Route 1** (inconclusive): The literature confirms the established problem family, while the capped size-11 run returned no certificate. [3](#reference-3) [1](#reference-1) [2](#reference-2) [4](#reference-4)

### Runnable artifacts

- **Artifact 1** (reproduced): Standard-library Python checks all slopes, proves the counting bound, and hashes a complete 0-1 pseudo-Boolean instance for the next case. [4](#reference-4)

### Computational notes

- All primitive undirected directions supported by the grid were enumerated exactly; there are 112. Thirty thousand seeded random greedy runs found the displayed 9-point set, and an exact pair check verified that its 36 slopes are distinct.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `distinct-slopes-ten-grid`, 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>Paul Erdős, Ron Graham, Imre Z. Ruzsa, and Herbert Taylor, “Bounds for arrays of dots with distinct slopes or lengths”. Combinatorica 12(1) (1992), 39-44. DOI 10.1007/BF01191203. Main asymptotic lower and upper bounds on pp. 39-44 https://doi.org/10.1007/BF01191203
   - journal_article; primary source; version of record; checked 2026-07-28
   - Source use: original_summary
   - For Most lattice points with all pairwise slopes distinct in a ten by ten grid: Introduces the grid distinct-slope function and proves its first asymptotic bounds.
   - Introduces the grid distinct-slope function and proves its first asymptotic bounds.
2. <a id="reference-2"></a>Zhen Zhang, “A note on arrays of dots with distinct slopes”. Combinatorica 13(1) (1993), 127-128. DOI 10.1007/BF01202795. The improved asymptotic lower bound on pp. 127-128 https://doi.org/10.1007/BF01202795
   - journal_article; primary source; version of record; checked 2026-07-28
   - Source use: original_summary
   - For Most lattice points with all pairwise slopes distinct in a ten by ten grid: Improves the lower bound for the distinct-slope grid function.
   - Improves the lower bound for the distinct-slope grid function.
3. <a id="reference-3"></a>R.E Peile and H Taylor, “Sets of points with pairwise distinct slopes”. Computers & Mathematics with Applications 39(11) (2000), 109-115. DOI 10.1016/S0898-1221(00)00115-2. R. E. Peile and H. Taylor, Sets of points with pairwise distinct slopes, Computers & Mathematics with Applications 39 (2000), 109-115; Felix Christian Clemen, Applications of Sparse Hypergraph Colorings, Discrete Mathematics 349 (2026), 114822; solver run on 2026-07-25 https://doi.org/10.1016/S0898-1221(00)00115-2
   - scholarly_publication; reference source; checked 2026-08-01
   - Source use: citation_only
   - For Most lattice points with all pairwise slopes distinct in a ten by ten grid: The literature confirms the established problem family, while the capped size-11 run returned no certificate.
4. <a id="reference-4"></a>Felix Christian Clemen, “Applications of sparse hypergraph colorings”. Discrete Mathematics 349(2) (2026), 114822. DOI 10.1016/j.disc.2025.114822. Full journal article relevant to Most lattice points with all pairwise slopes distinct in a ten by ten grid. https://doi.org/10.1016/j.disc.2025.114822
   - Also cited at Exact construction and direction-count replay in dstg-artifact-witness-direction-check
   - Also cited at Inline Python 3 computation executed on 2026-07-25
   - scholarly_publication; reference source; arXiv:2406.01499, checked 2026-08-01; checked 2026-08-01
   - Open copy: https://arxiv.org/abs/2406.01499
   - Source use: citation_only
   - For Most lattice points with all pairwise slopes distinct in a ten by ten grid, the reviewed source scope is Full journal article relevant to Most lattice points with all pairwise slopes distinct in a ten by ten grid.. The packet makes no inference beyond that cited scope.
   - Source named by the research packet.