How many colours does the plane need?
Colour every point of the plane so no two points exactly one unit apart share a colour. Five is not enough; seven suffice. Is six?
▸Motivation
The Hadwiger–Nelson problem, posed in 1950.
The answer sat between 4 and 7 for 68 years. In 2018 Aubrey de Grey, an amateur in this field, exhibited a unit-distance graph with chromatic number 5, raising the lower bound; the upper bound of 7 comes from a hexagonal tiling. Whether 6 suffices is open.
The de Grey construction is a good argument for this project: it was found by computer search, verified by others by computer, and would have been a natural thing to check mechanically.
Edward Nelson, 1950. Lower bound 5: de Grey 2018.
▸Lean API
import Conjectura.Defs.Mathematics.Combinatorics.GraphTheory.UnitDistanceGraph
import Mathlib.Analysis.InnerProductSpace.EuclideanDist
import Mathlib.Combinatorics.SimpleGraph.Coloring.Vertex
namespace Conjectura.GT001
/-- How many colours are needed so that no two points of the plane at distance one
share a colour? De Grey showed in 2018 that five is not enough; seven suffice. Six
remains undecided, which is what this asks. -/
def goal : Prop :=
(Conjectura.GraphTheory.unitDistanceGraph (EuclideanSpace ℝ (Fin 2))).Colorable 6
end Conjectura.GT001▸Definition6
- unit-distance graphConjectura.GraphTheory.unitDistanceGraph
The unit-distance graph on a metric space joins two points exactly when they are at distance one. Over the Euclidean plane, its chromatic number is the Hadwiger–Nelson problem.
def unitDistanceGraph (X : Type*) [MetricSpace X] : SimpleGraph X where Adj x y := x ≠ y ∧ dist x y = 1 symm := ⟨fun _ _ h => ⟨h.1.symm, by rw [dist_comm]; exact h.2⟩⟩ loopless := ⟨fun _ h => h.1 rfl⟩- MetricSpaceMetricSpace
class
- AdjAdj
structure
- symmh.1.symm
def
- EuclideanSpaceEuclideanSpace
abbrev
- ColorableColorable
def
▸Related work1
- The chromatic number of the plane is at least 5Aubrey D.N.J. de Grey · 2018
Broke a 68-year deadlock with an explicit 1581-vertex graph, found and checked by computer.
▸For your AI
I am proving a theorem in Lean 4 and submitting it to Conjectura.
## Problem GT001 — How many colours does the plane need?
Colour every point of the plane so no two points exactly one unit apart share a colour. Five is not enough; seven suffice. Is six?
## Environment (fixed — do not assume anything newer)
- Lean toolchain: `leanprover/lean4:v4.33.0-rc1`
- Mathlib: `v4.33.0-rc1`
If a lemma you want does not exist in that Mathlib, prove it inline instead of
importing something newer.
## The exact statement I must prove
```lean
theorem solution : (unitDistanceGraph (EuclideanSpace ℝ (Fin 2))).Colorable 6 := by
sorry
```
## The file I submit
```lean
import Conjectura.Problems.GT001.Statement
namespace Submission
theorem solution : Conjectura.GT001.goal := by
sorry
end Submission
```
## The Lean definitions of every term in this problem
These are the actual definitions your proof will be checked against. Do not
substitute your own version of any of them.
### unit-distance graph
The unit-distance graph on a metric space joins two points exactly when they are at distance one. Over the Euclidean plane, its chromatic number is the Hadwiger–Nelson problem.
```lean
Conjectura.GraphTheory.unitDistanceGraph
-- unfolds to:
def unitDistanceGraph (X : Type*) [MetricSpace X] : SimpleGraph X where
Adj x y := x ≠ y ∧ dist x y = 1
symm := ⟨fun _ _ h => ⟨h.1.symm, by rw [dist_comm]; exact h.2⟩⟩
loopless := ⟨fun _ h => h.1 rfl⟩
```
Defined in this corpus.
### MetricSpace
class
```lean
MetricSpace
```
Defined in Mathlib.
### Adj
structure
```lean
Adj
```
Defined in Mathlib.
### symm
def
```lean
h.1.symm
```
Defined in Mathlib.
### EuclideanSpace
abbrev
```lean
EuclideanSpace
```
Defined in Mathlib.
### Colorable
def
```lean
Colorable
```
Defined in Mathlib.
## Rules — submissions violating these are rejected automatically
1. **Do not change the name or type of `solution`.** It must satisfy the
statement above exactly.
2. **Do not redefine or shadow anything from the problem's Statement module.**
Declaring your own `goal`, or redefining a name it depends on, produces a
proof of a *different* statement and is rejected. This is the single most
common rejection.
3. **No `sorry`** anywhere, including in helper lemmas. It surfaces as the
axiom `sorryAx` and is detected transitively through imports.
4. **No `native_decide`** — it surfaces as `Lean.ofReduceBool` and is not
accepted, because it trusts compiled code rather than the kernel.
5. Only these axioms are permitted: `propext`, `Classical.choice`,
`Quot.sound`.
6. Follow Mathlib style: hypotheses left of the colon, explicit types,
`snake_case` theorem names, `UpperCamelCase` types.
## What I want from you
Here is my argument in informal mathematics:
> [PASTE YOUR PROOF SKETCH HERE]
Turn it into Lean 4 that compiles under the environment above and satisfies the
statement exactly. Where you are unsure a lemma exists in this Mathlib version,
say so explicitly rather than guessing a name.Submissions are not open yet
Conjectura is in beta. You can read every statement, every definition and the Lean behind them, and download the exact files the checker uses — but proofs are not being accepted yet.
The reason is a deliberate order of operations. Accepting a proof means running a stranger’s code and standing behind a verdict, and no statement here yet carries a researcher’s name. A machine-checked answer to a question nobody has vouched for is worth very little, so the vouching comes first.
The English write-ups are also switched off during the beta. Nothing on this page is generated by a model.
Discussion
- Nothing yet.
Sign in to take part.