Erdős Problem #508

Erdős Problem 508 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/508.tex.

REUSED SOURCE 1

1) FORMAL RESTATEMENT

Consider the graph $G$ with vertex set $\mathbb R^2$ and an edge between two points if their Euclidean distance is exactly $1$. The chromatic number of the plane $\chi$ is \[ \chi := \chi(\mathbb R^2) := \min\big\{k\in\mathbb N:\ \exists\ c:\mathbb R^2\to\{1,\dots,k\}\text{ such that }\lVert x-y\rVert=1\Rightarrow c(x)\ne c(y)\big\}. \] The problem asks to determine $\chi$.

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement records that $\chi\ge 3$ (equilateral triangle), that finite unit-distance graphs such as the Moser spindle imply $\chi\ge 4$, and that the best known bounds currently are $5\le \chi\le 7$ (lower bound due to de Grey, as quoted).

Below I prove the classical bounds $4\le \chi\le 7$ in a fully explicit way (using an explicit unit-distance graph and an explicit 7-coloring).

3) ATTACK PLAN

Lower bound: exhibit an explicit finite unit-distance graph with chromatic number $4$ (the Moser spindle) and prove it is not 3-colorable.

Upper bound: give an explicit 7-coloring of the plane based on a regular hexagon tiling with sufficiently small diameter.

4) WORK

Lemma 508.1 (Explicit Moser spindle; forces 4 colors). There exist seven points in $\mathbb R^2$ with eleven unit-distance edges forming a graph that is not 3-colorable. Hence $\chi\ge 4$.

Proof. Step 1: Coordinates. Let \[ O=(0,0),\quad U=(1,0),\quad V=\left(\tfrac12,\tfrac{\sqrt3}{2}\right),\quad C=U+V=\left(\tfrac32,\tfrac{\sqrt3}{2}\right). \] Then $\lVert O-U\rVert=\lVert O-V\rVert=\lVert U-V\rVert=\lVert U-C\rVert=\lVert V-C\rVert=1$, so $O,U,V,C$ form a rhombus with angles $60^\circ$ and $120^\circ$, plus the short diagonal $UV$.

Let $\alpha:=\arccos(5/6)$ and let $R_{\alpha}$ denote rotation about the origin by angle $\alpha$. Define $D:=R_{\alpha}(C)$; then $\lVert D\rVert=\lVert C\rVert=\sqrt3$ and $\lVert C-D\rVert=1$ (because $\lVert C-D\rVert^2=2\lVert C\rVert^2(1-\cos\alpha)=6(1-5/6)=1$). Let $\phi:=\arg(D)$ and define \[ A:=(\cos(\phi+\pi/6),\ \sin(\phi+\pi/6)),\qquad B:=(\cos(\phi-\pi/6),\ \sin(\phi-\pi/6)). \] Then $\lVert A\rVert=\lVert B\rVert=1$ and the angle between $A$ and $B$ is $\pi/3$, so $\lVert A-B\rVert=1$. Moreover, \[ A+B = 2\cos(\pi/6)\,(\cos\phi,\sin\phi)=\sqrt3\,(\cos\phi,\sin\phi)=D, \] so $D=A+B$ and therefore $\lVert A-D\rVert=\lVert B-D\rVert=1$. Thus $O,A,B,D$ form a second $60/120$ rhombus plus short diagonal $AB$.

Now define a finite graph $H$ on vertex set \[\{O,U,V,C,A,B,D\} \] with edge set consisting of the following eleven pairs: \[ \{O,U\},\{O,V\},\{U,V\},\{U,C\},\{V,C\},\qquad \{O,A\},\{O,B\},\{A,B\},\{A,D\},\{B,D\},\qquad \{C,D\}. \] By the distance checks above, every listed edge is a unit-distance pair. So $H$ is a unit-distance graph in the plane.

Step 2: $H$ is not 3-colorable. Consider the induced subgraph on $\{O,U,V,C\}$. This is the graph $K_4$ with the edge $OC$ missing (all other pairs among these four vertices are edges). In any proper 3-coloring of this subgraph, the adjacent vertices $U$ and $V$ must have different colors. Then $O$ is adjacent to both $U$ and $V$, so $O$ cannot use either of their colors and must use the third color. Similarly, $C$ is adjacent to both $U$ and $V$, so $C$ also must use the third color. Hence in any 3-coloring of $\{O,U,V,C\}$ we must have $\mathrm{col}(O)=\mathrm{col}(C)$.

The same argument applied to the $K_4$-minus-edge subgraph on $\{O,A,B,D\}$ (missing edge $OD$) shows that in any 3-coloring we must have $\mathrm{col}(O)=\mathrm{col}(D)$. Therefore $\mathrm{col}(C)=\mathrm{col}(D)$ in any 3-coloring. But $C$ and $D$ are adjacent in $H$ (edge $CD$), contradiction. So $H$ is not 3-colorable, and thus needs at least 4 colors.

Since $H$ is a unit-distance graph in the plane, any proper coloring of $\mathbb R^2$ with no monochromatic unit-distance pair restricts to a proper coloring of $H$. Therefore $\chi\ge \chi(H)\ge 4$. $\square$

Lemma 508.2 (Explicit 7-coloring by hexagon tiling). There exists a coloring $c:\mathbb R^2\to\{0,1,\dots,6\}$ such that any two points at distance $1$ have different colors. Hence $\chi\le 7$.

Proof. Step 1: Hexagon tiling and parameters. Fix a regular hexagon tiling of the plane by congruent regular hexagons of side length \[s:=\frac{2}{5}. \] For a regular hexagon of side length $s$, the diameter (maximum distance between two points in the hexagon) is $2s=4/5<1$. Therefore any two points within the same hexagon have distance $<1$, and in particular cannot be at distance exactly $1$. So it is safe to give each hexagon a single color.

Let $r:=s$ be the circumradius of each hexagon. The distance between centers of two hexagons that share a side equals twice the inradius, i.e. \[t:=2r\cos(\pi/6)=2s\cdot \frac{\sqrt3}{2}=\sqrt3\,s. \] Thus the set of hexagon centers forms a triangular lattice with nearest-neighbor distance $t$. Choose lattice basis vectors $\mathbf e_1,\mathbf e_2\in\mathbb R^2$ with $\lVert\mathbf e_1\rVert=\lVert\mathbf e_2\rVert=t$ and angle $60^\circ$ between them. Every hexagon center can be written uniquely as $a\mathbf e_1+b\mathbf e_2$ with integers $a,b$.

Step 2: Define the 7-coloring on hexagons. Color the hexagon centered at $a\mathbf e_1+b\mathbf e_2$ by \[c(a,b):= (a+3b)\bmod 7\ \in\{0,1,\dots,6\}. \] Extend this to a coloring of the whole plane by coloring each point with the color of the hexagon containing it. (Points on hexagon boundaries may be assigned arbitrarily among the adjacent hexagons; this does not affect correctness because boundaries have no interior and the distance-1 constraint is closed.)

Step 3: Same-colored hexagon centers are far apart. Suppose two hexagon centers have the same color. Then their difference in lattice coordinates is a nonzero integer pair $(\Delta a,\Delta b)\ne (0,0)$ satisfying \[\Delta a + 3\Delta b \equiv 0\pmod 7. \] Write $\Delta a+3\Delta b=7k$ for some integer $k$. Then \[ \Delta a^2+\Delta b^2+\Delta a\Delta b =(7k-3\Delta b)^2+\Delta b^2+(7k-3\Delta b)\Delta b =49k^2-35k\Delta b+7\Delta b^2 =7(7k^2-5k\Delta b+\Delta b^2). \] In particular, $Q:=\Delta a^2+\Delta b^2+\Delta a\Delta b$ is a positive integer multiple of $7$, hence $Q\ge 7$. The squared Euclidean distance between the two centers is \[\lVert \Delta a\mathbf e_1+\Delta b\mathbf e_2\rVert^2 = t^2\,Q \ge 7t^2, \] so the center-to-center distance is at least $\sqrt7\,t$.

Step 4: No unit-distance monochromatic pair. Take two points $x,y$ of the same color.

- If $x,y$ lie in the same hexagon, then $\lVert x-y\rVert\le 2s=4/5<1$, so they are not at distance $1$.

- If $x,y$ lie in two different hexagons of the same color, let $z_x,z_y$ be the centers of those hexagons. Then $\lVert z_x-z_y\rVert\ge \sqrt7\,t$ by Step 3. Also $\lVert x-z_x\rVert\le s$ and $\lVert y-z_y\rVert\le s$ because $s$ is the circumradius. By the triangle inequality, \[ \lVert x-y\rVert\ge \lVert z_x-z_y\rVert - \lVert x-z_x\rVert - \lVert y-z_y\rVert \ge \sqrt7\,t -2s. \] Using $t=\sqrt3\,s$, this lower bound equals \[\sqrt7\,\sqrt3\,s-2s = (\sqrt{21}-2)s. \] With $s=2/5$, we have $(\sqrt{21}-2)s>1$ (numerically $(\sqrt{21}-2)\cdot 2/5\approx 1.0335$). Therefore any two same-colored points in different hexagons are at distance strictly greater than $1$.

In all cases, two same-colored points cannot be at distance exactly $1$. So this defines a proper 7-coloring for the unit-distance graph of the plane, proving $\chi\le 7$. $\square$

FAST REALITY CHECK (computational sanity for Lemma 508.1). Using the explicit coordinate construction above, I verified numerically (to machine precision) that: - all 11 listed edges have distance exactly $1$; - there are no additional unit-distance pairs among the 7 points; - the resulting graph is not 3-colorable but is 4-colorable.

5) VERIFICATION

Lemma 508.1: The forcing argument uses only local constraints in $K_4$ minus one edge, and the contradiction is the presence of edge $CD$.

Lemma 508.2: The key quantitative step is the lower bound $\lVert x-y\rVert>1$ for points in distinct same-colored hexagons; the calculation is explicit and uses the exact choice $s=2/5$.

6) FINAL UNRESOLVED

(i) Strongest proved partial result here: A fully explicit proof of the classical bounds $4\le \chi\le 7$ (Lemmas 508.1--508.2). (The problem statement reports the stronger current lower bound $\chi\ge 5$.)

(ii) First gap (crisp): Determine whether $\chi$ equals $5$, $6$, or $7$ (the statement in the problem file gives $5\le \chi\le 7$).

(iii) Top 3 next moves: 1. Search for smaller/structured finite unit-distance graphs with chromatic number $6$ or $7$, or prove they cannot exist under certain geometric constraints. 2. Improve the upper bound by constructing a periodic coloring with fewer than $7$ colors and rigorously checking the unit-distance constraint. 3. Investigate whether known $5$-chromatic unit-distance graphs can be extended or combined to force $6$ colors, or alternatively whether there is a measurable coloring with $5$ colors.

(iv) Minimal counterexample structure: If $\chi\ne 5$, then either (a) there exists a finite unit-distance graph requiring $6$ or $7$ colors, or (b) every unit-distance graph is 5-colorable but no 5-coloring extends to the whole plane; understanding which of these can happen (and under what regularity assumptions on the coloring) seems central.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

1) FORMAL RESTATEMENT

Consider the graph $G$ with vertex set $\mathbb R^2$ and an edge between two points if their Euclidean distance is exactly $1$. The chromatic number of the plane $\chi$ is \[ \chi := \chi(\mathbb R^2) := \min\big\{k\in\mathbb N:\ \exists\ c:\mathbb R^2\to\{1,\dots,k\}\text{ such that }\lVert x-y\rVert=1\Rightarrow c(x)\ne c(y)\big\}. \] The problem asks to determine $\chi$.

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement records that $\chi\ge 3$ (equilateral triangle), that finite unit-distance graphs such as the Moser spindle imply $\chi\ge 4$, and that the best known bounds currently are $5\le \chi\le 7$ (lower bound due to de Grey, as quoted).

Below I prove the classical bounds $4\le \chi\le 7$ in a fully explicit way (using an explicit unit-distance graph and an explicit 7-coloring).

3) ATTACK PLAN

Lower bound: exhibit an explicit finite unit-distance graph with chromatic number $4$ (the Moser spindle) and prove it is not 3-colorable.

Upper bound: give an explicit 7-coloring of the plane based on a regular hexagon tiling with sufficiently small diameter.

4) WORK

Lemma 508.1 (Explicit Moser spindle; forces 4 colors). There exist seven points in $\mathbb R^2$ with eleven unit-distance edges forming a graph that is not 3-colorable. Hence $\chi\ge 4$.

Proof. Step 1: Coordinates. Let \[ O=(0,0),\quad U=(1,0),\quad V=\left(\tfrac12,\tfrac{\sqrt3}{2}\right),\quad C=U+V=\left(\tfrac32,\tfrac{\sqrt3}{2}\right). \] Then $\lVert O-U\rVert=\lVert O-V\rVert=\lVert U-V\rVert=\lVert U-C\rVert=\lVert V-C\rVert=1$, so $O,U,V,C$ form a rhombus with angles $60^\circ$ and $120^\circ$, plus the short diagonal $UV$.

Let $\alpha:=\arccos(5/6)$ and let $R_{\alpha}$ denote rotation about the origin by angle $\alpha$. Define $D:=R_{\alpha}(C)$; then $\lVert D\rVert=\lVert C\rVert=\sqrt3$ and $\lVert C-D\rVert=1$ (because $\lVert C-D\rVert^2=2\lVert C\rVert^2(1-\cos\alpha)=6(1-5/6)=1$). Let $\phi:=\arg(D)$ and define \[ A:=(\cos(\phi+\pi/6),\ \sin(\phi+\pi/6)),\qquad B:=(\cos(\phi-\pi/6),\ \sin(\phi-\pi/6)). \] Then $\lVert A\rVert=\lVert B\rVert=1$ and the angle between $A$ and $B$ is $\pi/3$, so $\lVert A-B\rVert=1$. Moreover, \[ A+B = 2\cos(\pi/6)\,(\cos\phi,\sin\phi)=\sqrt3\,(\cos\phi,\sin\phi)=D, \] so $D=A+B$ and therefore $\lVert A-D\rVert=\lVert B-D\rVert=1$. Thus $O,A,B,D$ form a second $60/120$ rhombus plus short diagonal $AB$.

Now define a finite graph $H$ on vertex set \[\{O,U,V,C,A,B,D\} \] with edge set consisting of the following eleven pairs: \[ \{O,U\},\{O,V\},\{U,V\},\{U,C\},\{V,C\},\qquad \{O,A\},\{O,B\},\{A,B\},\{A,D\},\{B,D\},\qquad \{C,D\}. \] By the distance checks above, every listed edge is a unit-distance pair. So $H$ is a unit-distance graph in the plane.

Step 2: $H$ is not 3-colorable. Consider the induced subgraph on $\{O,U,V,C\}$. This is the graph $K_4$ with the edge $OC$ missing (all other pairs among these four vertices are edges). In any proper 3-coloring of this subgraph, the adjacent vertices $U$ and $V$ must have different colors. Then $O$ is adjacent to both $U$ and $V$, so $O$ cannot use either of their colors and must use the third color. Similarly, $C$ is adjacent to both $U$ and $V$, so $C$ also must use the third color. Hence in any 3-coloring of $\{O,U,V,C\}$ we must have $\mathrm{col}(O)=\mathrm{col}(C)$.

The same argument applied to the $K_4$-minus-edge subgraph on $\{O,A,B,D\}$ (missing edge $OD$) shows that in any 3-coloring we must have $\mathrm{col}(O)=\mathrm{col}(D)$. Therefore $\mathrm{col}(C)=\mathrm{col}(D)$ in any 3-coloring. But $C$ and $D$ are adjacent in $H$ (edge $CD$), contradiction. So $H$ is not 3-colorable, and thus needs at least 4 colors.

Since $H$ is a unit-distance graph in the plane, any proper coloring of $\mathbb R^2$ with no monochromatic unit-distance pair restricts to a proper coloring of $H$. Therefore $\chi\ge \chi(H)\ge 4$. $\square$

Lemma 508.2 (Explicit 7-coloring by hexagon tiling). There exists a coloring $c:\mathbb R^2\to\{0,1,\dots,6\}$ such that any two points at distance $1$ have different colors. Hence $\chi\le 7$.

Proof. Step 1: Hexagon tiling and parameters. Fix a regular hexagon tiling of the plane by congruent regular hexagons of side length \[s:=\frac{2}{5}. \] For a regular hexagon of side length $s$, the diameter (maximum distance between two points in the hexagon) is $2s=4/5<1$. Therefore any two points within the same hexagon have distance $<1$, and in particular cannot be at distance exactly $1$. So it is safe to give each hexagon a single color.

Let $r:=s$ be the circumradius of each hexagon. The distance between centers of two hexagons that share a side equals twice the inradius, i.e. \[t:=2r\cos(\pi/6)=2s\cdot \frac{\sqrt3}{2}=\sqrt3\,s. \] Thus the set of hexagon centers forms a triangular lattice with nearest-neighbor distance $t$. Choose lattice basis vectors $\mathbf e_1,\mathbf e_2\in\mathbb R^2$ with $\lVert\mathbf e_1\rVert=\lVert\mathbf e_2\rVert=t$ and angle $60^\circ$ between them. Every hexagon center can be written uniquely as $a\mathbf e_1+b\mathbf e_2$ with integers $a,b$.

Step 2: Define the 7-coloring on hexagons. Color the hexagon centered at $a\mathbf e_1+b\mathbf e_2$ by \[c(a,b):= (a+3b)\bmod 7\ \in\{0,1,\dots,6\}. \] Extend this to a coloring of the whole plane by coloring each point with the color of the hexagon containing it. (Points on hexagon boundaries may be assigned arbitrarily among the adjacent hexagons; this does not affect correctness because boundaries have no interior and the distance-1 constraint is closed.)

Step 3: Same-colored hexagon centers are far apart. Suppose two hexagon centers have the same color. Then their difference in lattice coordinates is a nonzero integer pair $(\Delta a,\Delta b)\ne (0,0)$ satisfying \[\Delta a + 3\Delta b \equiv 0\pmod 7. \] Write $\Delta a+3\Delta b=7k$ for some integer $k$. Then \[ \Delta a^2+\Delta b^2+\Delta a\Delta b =(7k-3\Delta b)^2+\Delta b^2+(7k-3\Delta b)\Delta b =49k^2-35k\Delta b+7\Delta b^2 =7(7k^2-5k\Delta b+\Delta b^2). \] In particular, $Q:=\Delta a^2+\Delta b^2+\Delta a\Delta b$ is a positive integer multiple of $7$, hence $Q\ge 7$. The squared Euclidean distance between the two centers is \[\lVert \Delta a\mathbf e_1+\Delta b\mathbf e_2\rVert^2 = t^2\,Q \ge 7t^2, \] so the center-to-center distance is at least $\sqrt7\,t$.

Step 4: No unit-distance monochromatic pair. Take two points $x,y$ of the same color.

- If $x,y$ lie in the same hexagon, then $\lVert x-y\rVert\le 2s=4/5<1$, so they are not at distance $1$.

- If $x,y$ lie in two different hexagons of the same color, let $z_x,z_y$ be the centers of those hexagons. Then $\lVert z_x-z_y\rVert\ge \sqrt7\,t$ by Step 3. Also $\lVert x-z_x\rVert\le s$ and $\lVert y-z_y\rVert\le s$ because $s$ is the circumradius. By the triangle inequality, \[ \lVert x-y\rVert\ge \lVert z_x-z_y\rVert - \lVert x-z_x\rVert - \lVert y-z_y\rVert \ge \sqrt7\,t -2s. \] Using $t=\sqrt3\,s$, this lower bound equals \[\sqrt7\,\sqrt3\,s-2s = (\sqrt{21}-2)s. \] With $s=2/5$, we have $(\sqrt{21}-2)s>1$ (numerically $(\sqrt{21}-2)\cdot 2/5\approx 1.0335$). Therefore any two same-colored points in different hexagons are at distance strictly greater than $1$.

In all cases, two same-colored points cannot be at distance exactly $1$. So this defines a proper 7-coloring for the unit-distance graph of the plane, proving $\chi\le 7$. $\square$

FAST REALITY CHECK (computational sanity for Lemma 508.1). Using the explicit coordinate construction above, I verified numerically (to machine precision) that: - all 11 listed edges have distance exactly $1$; - there are no additional unit-distance pairs among the 7 points; - the resulting graph is not 3-colorable but is 4-colorable.

5) VERIFICATION

Lemma 508.1: The forcing argument uses only local constraints in $K_4$ minus one edge, and the contradiction is the presence of edge $CD$.

Lemma 508.2: The key quantitative step is the lower bound $\lVert x-y\rVert>1$ for points in distinct same-colored hexagons; the calculation is explicit and uses the exact choice $s=2/5$.

6) FINAL UNRESOLVED

(i) Strongest proved partial result here: A fully explicit proof of the classical bounds $4\le \chi\le 7$ (Lemmas 508.1--508.2). (The problem statement reports the stronger current lower bound $\chi\ge 5$.)

(ii) First gap (crisp): Determine whether $\chi$ equals $5$, $6$, or $7$ (the statement in the problem file gives $5\le \chi\le 7$).

(iii) Top 3 next moves: 1. Search for smaller/structured finite unit-distance graphs with chromatic number $6$ or $7$, or prove they cannot exist under certain geometric constraints. 2. Improve the upper bound by constructing a periodic coloring with fewer than $7$ colors and rigorously checking the unit-distance constraint. 3. Investigate whether known $5$-chromatic unit-distance graphs can be extended or combined to force $6$ colors, or alternatively whether there is a measurable coloring with $5$ colors.

(iv) Minimal counterexample structure: If $\chi\ne 5$, then either (a) there exists a finite unit-distance graph requiring $6$ or $7$ colors, or (b) every unit-distance graph is 5-colorable but no 5-coloring extends to the whole plane; understanding which of these can happen (and under what regularity assumptions on the coloring) seems central.