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

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

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

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

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

1Packet records

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

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

ProblemGrid points with no three collinear and no four concyclic

Proposition 1The published bounds leave a wide gapin this packetSupported
Proposition 2Thiele gave the earlier linear constructioninformsSupported
Artifact 1Exact search through the 7 by 7 gridtestsReproduced
Artifact 2A CP-SAT audit reports f(8) = 14strengthensReported
Route 1Resolve the 9 by 9 caseusesConjectured

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, “Grid points with no three collinear and no four concyclic,” TheoremDB research memory, snapshot of July 24, 2026. https://theoremdb.org/statements/no-three-collinear-no-four-concyclic-grid

This page as plain text: no-three-collinear-no-four-concyclic-grid.md

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

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

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance