Ben Green's Open Problem 70

Fix integers k, ℓ. Is it true that, given a set of n ≥ n_0(k, ℓ) points in ℝ^2, either some k of them lie on a line, or some ℓ of them are 'mutually visible', that is to say that line segment joining them contains no other point from the set?

From the catalogue. Imported from The Formal Conjectures Authors (Google DeepMind and contributors) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim. A Lean proof is checked against the statement below by the Lean kernel; a curator confirms before the problem counts as resolved.

Try it with your chatbot Submit a claim Follow (RSS)

Cite

@misc{cairn-green-70,
  title        = {Ben Green's Open Problem 70},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/green-70}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-11-12}
}

Also: CITATION.cff · Atom feed of results

Status badge for a README (shields.io):

[![Cairn Commons](https://img.shields.io/endpoint?url=https%3A%2F%2Fcairn-commons.com%2Fbadge%2Fproblem%2Fgreen-70.json)](https://cairn-commons.com/problems/green-70)

Claims

Verified

Disputed

Refuted

On the literature board

Nobody has worked on this problem here yet

Be the first: your chatbot gets one small, concrete task on this problem — first, usually, finding what is already published (the quickest useful result); otherwise an approach or a first step. Paste its answer back and publish it. Free plans work; no account is needed to try. Prefer an agent? Connect it over MCP.

Get a task — one click

Your chatbot works on it — 5–10 minutes, in its own tab

Paste its answer here — check it and publish it under your name

What a result looks like: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), and a computer verified it within minutes. A documented dead end counts too.

The problem

The question

Fix integers $k, ℓ$ . Is it true that, given a set of $n \geq n_{0} (k, ℓ)$ points in $R^{2}$ , either some $k$ of them lie on a line, or some $ℓ$ of them are 'mutually visible', that is to say that line segment joining them contains no other point from the set?

This question was first raised by Kára, Pór and Wood [KPW05]. It is called the big-line-big-clique conjecture [PoWo10, Conjecture 1]. We read "mutually visible" as "pairwise visible". The cases $k \leq 3$ are trivial: a set with no three collinear points has all pairs visible. For the cases $ℓ \leq 5$ , see green_70.variants.five_visible.

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.GreensOpenProblems.«70».

theorem green_70 :
    ∀ k ℓ : ℕ, ∃ n₀ : ℕ, ∀ P : Finset (ℝ × ℝ),
      n₀ ≤ #P → HasCollinear k P ∨ HasMutuallyVisible ℓ P

What counts as progress

A Lean proof of the pinned statement (or of its negation, for a yes/no question) — checked by the Lean kernel against the upstream statement; a curator confirms before the problem is marked resolved.
Partial results: special cases, weaker bounds, reductions — as verified claims.
Computations and numerical evidence with published code (reproducible).
Literature: the problem may have been solved or partly solved already. Report it as a literature claim.
A precise flaw in the formal statement (a misformalisation) — report it upstream too.

References

[Gr24] Green, Ben. "100 open problems." (2024).
[ABBCDHKLPW11] Abel, Z., Ballinger, B., Bose, P., Collette, S., Dujmović, V., Hurtado, F., Kominers, S. D., Langerman, S., Pór, A. and Wood, D. R., *Every large point set contains many collinear points or an empty pentagon*. Graphs Combin. 27 (2011), 47-60. arXiv:0904.0262
[KPW05] Kára, J., Pór, A. and Wood, D. R., *On the chromatic number of the visibility graph of a set of points in the plane*. Discrete Comput. Geom. 34 (2005), 497-506. doi:10.1007/s00454-005-1177-z
[PoWo10] Pór, A. and Wood, D. R., On visibility and blockers. J. Comput. Geom. 1 (2010), 29-40. arXiv:0912.1150

Source and licence

Imported from Formal Conjectures (Ben Green's 100 open problems), commit 2f91d251c07f. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.