# P2428: Grid points with no three collinear and no four concyclic

- ID: `P2428`
- Reference: `no-three-collinear-no-four-concyclic-grid`
- Page: https://theoremdb.org/statements/P2428
- Record maturity: Reviewed problem with recorded work

## Problem

Let \(f(n)\) be the largest number of points that can be chosen from the \(n \times n\) grid \(\{0, \dots, n-1\}^2\) so that no three are collinear and no four lie on a common circle. Is \(f(n) = 2n - 2\) for every \(n \ge 4\)?

### Problem setup

- **Definition.** Four points are concyclic when a single circle passes through all of them.
- **Remark.** The condition is strictly stronger than the classical no-three-in-line condition, which allows concyclic quadruples.

### What counts as a solution

- Prove that f(n) = 2n-2 for all n at least 4, or compute a value of f(n) that differs from 2n-2.

## Status

Current results give \(n/3-o(n)\leq f(n)\leq2n\). [1](#reference-1)

## Work

### Evidence for the current status

**Proposition 1 (The published bounds leave a wide gap).** Current results give \(n/3-o(n)\leq f(n)\leq2n\).

Dong and Xu write this function as \(\operatorname{ex}([n]^2;3,4)\): a set contains no three collinear points and no four concyclic points. Their Theorem 3, specialized to dimension two, gives \(f(n)\geq n/3-o(n)\). The elementary upper bound \(f(n)\leq2n\) follows by looking at the \(n\) horizontal rows. The proposed formula \(2n-2\) remains well above the best published general construction located in this audit.

### Background and intake notes

The no-three-in-line problem asks for the maximum with only the collinearity condition, where 2n is an upper bound. Requiring in addition that no four points be concyclic reduced the maximum by exactly 2 at every computed n from 4 upward.

- Original intake status: Status not established. The classical no-three-in-line problem is famously open, so this stronger variant is unlikely to be easy, but it may also have been studied; no search was performed. The computed range is small, so the pattern 2n-2 is a fragile conjecture.
- No literature search was carried out.
- The verified range only reaches n = 7. Given that the seed pattern in a related determinant question broke between n = 60 and n = 130, a pattern established on six data points should be treated with suspicion until pushed further.

- Recorded example: f(2) = 3, f(3) = 5, f(4) = 6, f(5) = 8, f(6) = 10, f(7) = 12.

### Other known results

- **Proposition 2** (supported): Thiele's no-four-on-circle construction also enforces the no-three-in-line condition and yields more than \(n/4\) points. [2](#reference-2)

### Open directions

- **Route 1** (conjectured): The next exact target is to decide whether a 16-point configuration exists. [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): Exact backtracking gives \(f(2),\ldots,f(7)=3,5,6,8,10,12\).
- **Artifact 2** (reported): An independent model proves 15 points infeasible and supplies a valid 14-point set.

### Computational notes

- Exhaustive backtracking search over all subsets of the grid, with exact integer arithmetic for the collinearity and concyclicity tests, for n from 2 to 7.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `no-three-collinear-no-four-concyclic-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>Zichao Dong and Zijian Xu, “Large grid subsets without many cospherical points”. arXiv:2506.18113 (2025). Zichao Dong and Zijian Xu, Large grid subsets without many cospherical points, pages 2-3, Theorem 3; Exact-search direction following the known bounds for ex([n]^2;3,4) https://arxiv.org/abs/2506.18113
   - Also cited at Zichao Dong and Zijian Xu, Large grid subsets without many cospherical points, pages 2-3, Theorem 3
   - Also cited at Exact-search direction following the known bounds for ex([n]^2;3,4)
   - preprint; primary source; arXiv:2506.18113, version checked 2026-07-24; checked 2026-08-01
   - Source use: original_summary
   - For Grid points with no three collinear and no four concyclic: The published bounds leave a wide gap. Current results give \(n/3-o(n)\leq f(n)\leq2n\). Resolve the 9 by 9 case. The next exact target is to decide whether a 16-point configuration exists.
   - Source named by the research packet.
2. <a id="reference-2"></a>Torsten Thiele, “The no-four-on-circle problem”. Journal of Combinatorial Theory, Series A 71(2) (1995), 332-334. DOI 10.1016/0097-3165(95)90007-1. Torsten Thiele, The no-four-on-circle problem, Journal of Combinatorial Theory Series A 71 (1995), pages 332-334 https://doi.org/10.1016/0097-3165(95)90007-1
   - journal_article; primary source; version of record; checked 2026-08-01
   - Source use: original_summary
   - For Grid points with no three collinear and no four concyclic: Thiele's no-four-on-circle construction also enforces the no-three-in-line condition and yields more than \(n/4\) points.