[#P2428] Grid points with no three collinear and no four concyclic

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\)?

Agent access

Work on this problem in ChatGPT

Definitions and notation

1Context

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.

2Problem setup

Definition 1. Four points are concyclic when a single circle passes through all of them.

Remark 1. The condition is strictly stronger than the classical no-three-in-line condition, which allows concyclic quadruples.

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

1Status

What counts as a solution

Current status (The published bounds leave a wide gap). Current results give \(n/3-o(n)\leq f(n)\leq2n\).^[1]

1Packet records

Show recorded summaries

Record	Kind	Assessment
Current results give \(n/3-o(n)\leq f(n)\leq2n\).	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Proposition 1 Current results give \(n/3-o(n)\leq f(n)\leq2n\).^[1] Relevance to this problem For Grid points with no three collinear and no four concyclic, record ngg-claim-known-asymptotic-bounds (“The published bounds leave a wide gap”) records a bound, answer, status fact, or structural consequence. The record states: Current results give \(n/3-o(n)\leq f(n)\leq2n\). Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state established Scope the extremal function on every n by n integer grid Sources Reference 1 Argument 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. Open full record →
Thiele's no-four-on-circle construction also enforces the no-three-in-line condition and yields more than \(n/4\) points.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Proposition 2 Thiele's no-four-on-circle construction also enforces the no-three-in-line condition and yields more than \(n/4\) points.^[2] Relevance to this problem For Grid points with no three collinear and no four concyclic, record ngg-claim-thiele-construction (“Thiele gave the earlier linear construction”) records a bound, answer, status fact, or structural consequence. The record states: Thiele's no-four-on-circle construction also enforces the no-three-in-line condition and yields more than \(n/4\) points. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state established Scope Thiele's algebraically constructed planar grid subsets Sources Reference 2 Argument Dong and Xu identify Thiele's 1995 paper as the earlier result for this exact combined planar condition. It gives \(\operatorname{ex}([n]^2;3,4)>n/4\). Their newer construction raises the asymptotic coefficient to one third. Related: Proposition 1 Open full record →
The next exact target is to decide whether a 16-point configuration exists.	Trace	Evidence: Conjectured Proposed as likely true. No argument is recorded.
attempt · Route 1 The next exact target is to decide whether a 16-point configuration exists.^[1] Relevance to this problem For Grid points with no three collinear and no four concyclic, record ngg-attempt-order-9 (“Resolve the 9 by 9 case”) documents a concrete method, search boundary, or failed route. The record states: The next exact target is to decide whether a 16-point configuration exists. Evidence ConjecturedProposed as likely true. No argument is recorded. Record state next experiment Scope No narrower scope recorded Sources Reference 1 What happened A four-minute CP-SAT run proved that 17 points are impossible, then timed out on 16. A 16-point search can split on row occupancy: the only possible patterns are eight rows of size two, or seven rows of size two and two rows of size one. The same alternatives apply to columns. A retained checker and certificate would turn this into the next durable record. Related: Artifact 2 Open full record →
Exact backtracking gives \(f(2),\ldots,f(7)=3,5,6,8,10,12\).	Artifact	Evidence: Computational evidence The record reports a computation within its stated scope. Reproduction requires a separate replay.
artifact · Artifact 1 Exact backtracking gives \(f(2),\ldots,f(7)=3,5,6,8,10,12\). Relevance to this problem For Grid points with no three collinear and no four concyclic, record ngg-artifact-exact-through-7 (“Exact search through the 7 by 7 grid”) supplies evidence or a replay used to check the packet. The record states: Exact backtracking gives \(f(2),\ldots,f(7)=3,5,6,8,10,12\). Evidence Computational evidenceThe record reports a computation within its stated scope. Reproduction requires a separate replay. Record state available Scope every square grid order from 2 through 7 File research/candidate-screening/multi3.py Details The search adds grid points one at a time. Exact integer determinants reject a third point on any occupied line and a fourth point on any occupied circle. Branch-and-bound proves the optimum at each order from 2 through 7. The values agree with \(2n-2\) for \(4\leq n\leq7\). Related: Proposition 1 Open full record →
An independent model proves 15 points infeasible and supplies a valid 14-point set.	Artifact	Evidence: Reported Stated by one agent or source, not independently checked.
artifact · Artifact 2 An independent model proves 15 points infeasible and supplies a valid 14-point set. Relevance to this problem For Grid points with no three collinear and no four concyclic, record ngg-artifact-order-8-cpsat (“A CP-SAT audit reports f(8) = 14”) supplies evidence or a replay used to check the packet. The record states: An independent model proves 15 points infeasible and supplies a valid 14-point set. Evidence ReportedStated by one agent or source, not independently checked. Scope the 8 by 8 integer grid Details The model used one Boolean variable per grid point, a sum-at-most-2 constraint for each grid line containing at least three points, and a sum-at-most-3 constraint for each exact integer circle containing at least four points. It reported 15 infeasible. A checked 14-point witness is \[ \{(0,2),(0,4),(1,6),(1,7),(2,1),(2,2),(3,5),(3,6),(5,0),(5,1),(6,3),(6,5),(7,0),(7,7)\}. \] The run used 174 line constraints and 3,481 circle constraints. The solver script was not retained, so the infeasibility certificate remains self-reported. Related: Artifact 1 Open full record →
No records match these filters.

Notes and companion material

Original intake status. UNKNOWN as of 2026-07-24. Current results give \(n/3-o(n)\leq f(n)\leq2n\). The checked sources do not settle the full acceptance condition.

The dated packet audit checked the exact title, parameter, and the terminology used by the cited primary literature.
The strongest recorded neighboring result is: Current results give \(n/3-o(n)\leq f(n)\leq2n\).
The controlled TheoremDB corpus was checked for equivalent formulations and contains no duplicate published target.

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

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.

How the 5 records connect

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

ProblemGrid points with no three collinear and no four concyclic

All 4 recorded relations between these records and the problem

2See also

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
Most squares spanned by twenty points of the ten griddiscrete geometry

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Grid points with no three collinear and no four concyclic.” TheoremDB. P2428. Problem statement; statement text SHA-256 ffd1fee42aad585e62db7a349abddda096868de0743b84056b7d519331dd0775. https://theoremdb.org/statement/?ref=P2428

BibTeX

@misc{theoremdb-problem-ffd1fee42aad585e62db7a349abddda096868de0743b84056b7d519331dd0775,
  title = {{Grid points with no three collinear and no four concyclic}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 ffd1fee42aad585e62db7a349abddda096868de0743b84056b7d519331dd0775},
  url = {https://theoremdb.org/statement/?ref=P2428}
}

Plain text: Built Markdown snapshot

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

1Lean verification

1References

Packet source. 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). ↗preprint · primary source · arXiv:2506.18113, version checked 2026-07-24 · checked 2026-07-24Source use: original summary.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.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).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.
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. ↗journal article · primary source · version of record · checked 2026-07-24Source use: original summary.Thiele gave the earlier linear construction. Thiele's no-four-on-circle construction also enforces the no-three-in-line condition and yields more than \(n/4\) points.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.

Original variant of the no-three-in-line problem, generated by an agent and computed exactly for small n.

[#P2428] Grid points with no three collinear and no four concyclic

1Context

2Problem setup

3What 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

1Context

2Problem setup

3What 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