Chromatic number of the unit-distance graph of $\mathbb{R}^n$: does $\lim \chi(G_n)^{1/n}$ exist? (Erdős #704)
Statement
Let $G_n$ be the unit distance graph on $\mathbb{R}^n$: vertices are all points of $\mathbb{R}^n$, with two points joined by an edge if and only if the Euclidean distance between them is exactly $1$. Estimate the chromatic number $\chi(G_n)$ (the least number of colour classes partitioning $\mathbb{R}^n$ so that no class contains two points at distance $1$). Does $\chi(G_n)$ grow exponentially in $n$? Does $$\lim_{n\to\infty}\chi(G_n)^{1/n}$$ exist?
Acceptance. FULLY RESOLVES: a proof (machine-checkable Lean/Coq preferred, else a full written proof with all steps) that $\lim_{n\to\infty}\chi(G_n)^{1/n}$ exists together with its value — or a proof that the limit does not exist. No finite computation can close this (classified OPEN on the source site). ADVANCES: a proven lower bound $(c+o(1))^n$ with $c$ strictly larger than the best base stated in the background (Raigorodsky's $1.239\ldots$), or a proven upper bound $(C+o(1))^n$ with $C$ strictly below the best stated base ($3$) — computer-assisted constructions admissible only with reproducible code and machine-verifiable certificates of the construction's validity; a proof that the limit exists without determining its value; or a proof of Larman–Rogers' conjectured $2^{3/2}$ base in either direction. Improved bounds on $\chi(G_n)$ for individual small $n$ count only insofar as they yield a new asymptotic base. Deliver the proof file, plus (for computer-assisted bounds) the construction, code, and verification certificates.
Background
Posed by Erdős [Er81]; listed as open on erdosproblems.com/704 (fetched 2026-07-13, status 'open', tagged 'graph theory | geometry | chromatic number'). This is the high-dimensional generalisation of the Hadwiger–Nelson problem (the $n=2$ case, where $5\le\chi\le 7$ after de Grey's 2018 lower bound). Known frontier: Frankl and Wilson [FrWi81] proved exponential growth, $\chi(G_n)\geq(1+o(1))\,1.2^n$, via their forbidden-intersection theorem; Raigorodsky [Ra00] improved the base to $\chi(G_n)\geq(1.239\ldots+o(1))^n$, still the record. Upper bounds: the trivial colouring by tiling with small cubes gives $(2+\sqrt{n})^n$; Larman and Rogers [LaRo72] improved this to $\chi(G_n)\leq(3+o(1))^n$ and conjectured the truth may be $(2^{3/2}+o(1))^n\approx(2.828)^n$; Prosanov [Pr20] gave an alternative proof of the $3^n$-type bound. So exponential growth is settled between bases $1.239$ and $3$; what remains is the correct base and whether the limit $\chi(G_n)^{1/n}$ exists at all. Related problems: Erdős #508, #705, #706 (erdosproblems.com/508, /705, /706). Closely related to the venue problem on the chromatic number of 3-space ($\chi(\mathbb{R}^3)$), which targets the fixed low-dimensional case; this problem is the asymptotic-in-$n$ question. The attacker's tools: lower-bound progress has historically come from explicit algebraic set-systems (Frankl–Wilson-type) with parameters optimizable by computer search; upper bounds from explicit lattice tilings/coverings — both are concrete computational targets; the existence-of-the-limit question is proof-shaped (no general super-/sub-multiplicativity argument is known).
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #704 (T. F. Bloom) | website |
| REF-02 | Hadwiger–Nelson problem (the n=2 case) | website |
| REF-03 | Erdős Problem #705 (related unit-distance chromatic problem) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.