gpt pro 5.2 attempt on Math-910

Erdős Problem #704

FORMAL RESTATEMENT

Let $G_n$ be the (infinite) graph with vertex set $\mathbb{R}^n$ and an edge between two distinct vertices $x,y\in\mathbb{R}^n$ if and only if $\|x-y\|_2=1$. Let $\chi(G_n)$ denote its (ordinary) chromatic number. Tasks:

1. Give upper and lower bounds on $\chi(G_n)$ as a function of $n$.
2. Decide whether $\chi(G_n)$ grows exponentially in $n$.
3. Decide whether $\lim_{n\to\infty} \chi(G_n)^{1/n}$ exists.

QUICK LITERATURE/CONTEXT CHECK

The problem statement records an exponential lower bound due to Frankl--Wilson and an exponential upper bound due to Larman--Rogers (with an alternative proof by Prosanov). The corresponding discussion pages and papers exist, but I do not reproduce those deep arguments here; I give elementary bounds and sanity checks only.

ATTACK PLAN

• Lower bounds: build explicit finite unit-distance subgraphs with large chromatic number. The easiest is a clique (regular simplex) giving $\chi(G_n)\ge n+1$.
• Upper bounds: partition $\mathbb{R}^n$ into small-diameter cells (cubes) and color the cells periodically so that same-colored cells are separated by distance $>1$.

WORK

Lemma 704.1 (clique lower bound via a regular simplex). For every $n\ge 1$, the unit distance graph $G_n$ contains a clique of size $n+1$. Consequently \[\chi(G_n)\ge n+1. \]

Proof. In $\mathbb{R}^n$ there exists a regular simplex with $n+1$ vertices, i.e. points $v_0,\dots,v_n$ with all pairwise distances equal to some constant $r>0$. (One explicit construction is to take the $n+1$ vectors in $\mathbb{R}^{n+1}$ given by $e_i-\tfrac{1}{n+1}\sum_{j=0}^n e_j$ and view them in the $n$-dimensional subspace of vectors summing to $0$.) Scaling the simplex by factor $1/r$ yields $n+1$ points in $\mathbb{R}^n$ with all pairwise distances exactly $1$. These vertices form a clique $K_{n+1}$ in $G_n$, and any proper coloring needs at least $n+1$ colors. $\square$

Lemma 704.2 (elementary cube-tiling upper bound). For every $n\ge 1$, \[\chi(G_n)\le \left(\lceil\sqrt{n}\rceil+3\right)^n. \] In particular, $\chi(G_n)\le (\sqrt{n}+3)^n$.

Proof. Let $s:=1/(\lceil\sqrt{n}\rceil+1)$. Tile $\mathbb{R}^n$ by axis-parallel cubes of side length $s$ whose vertices lie in the lattice $s\mathbb{Z}^n$. Any two points within the same cube have Euclidean distance at most the cube diameter $s\sqrt{n}$. Since $\lceil\sqrt{n}\rceil\ge \sqrt{n}$, we have \[s\sqrt{n}=\frac{\sqrt{n}}{\lceil\sqrt{n}\rceil+1}\le \frac{\sqrt{n}}{\sqrt{n}+1}<1. \] Thus no two points at distance exactly $1$ can lie in the same cube.

Now color the cubes periodically by their lattice indices modulo $t:=\lceil 1/s\rceil+1$ in each coordinate. Since $1/s=\lceil\sqrt{n}\rceil+1$, we have $t=\lceil\sqrt{n}\rceil+2$. This gives at most $t^n=(\lceil\sqrt{n}\rceil+2)^n$ colors. Finally, to ensure cubes of the same color are separated by distance $>1$, observe that if two cubes have the same color then their indices differ by a multiple of $t$ in every coordinate, so in at least one coordinate the index differs by at least $t$ unless they coincide. In that coordinate, the distance between the corresponding cube intervals is at least $(t-1)s$. But \[(t-1)s=(\lceil\sqrt{n}\rceil+1)\cdot \frac{1}{\lceil\sqrt{n}\rceil+1}=1. \] To avoid the boundary case "$=1$", we can instead take $t:=\lceil\sqrt{n}\rceil+3$, which yields $(t-1)s>1$ and still uses only $(\lceil\sqrt{n}\rceil+3)^n$ colors. Then any two points in cubes of the same color are at distance $>1$, so they are non-adjacent, and the induced vertex-coloring of $\mathbb{R}^n$ is proper. Hence $\chi(G_n)\le (\lceil\sqrt{n}\rceil+3)^n$. $\square$

FAST REALITY CHECK.

• $n=1$: Lemma 704.1 gives $\chi(G_1)\ge 2$. A 2-coloring is obtained by coloring $x\in\mathbb{R}$ by the parity of $\lfloor x\rfloor$; any two reals at distance $1$ have floors differing by $1$, hence different colors. So $\chi(G_1)=2$.
• $n=2$: Lemma 704.1 gives $\chi(G_2)\ge 3$ and Lemma 704.2 gives $\chi(G_2)\le (\lceil\sqrt{2}\rceil+3)^2=25$ (very weak).

VERIFICATION

• Lemma 704.1: verified that scaling preserves unit distances and that a clique forces at least that many colors.
• Lemma 704.2: the only delicate point is ensuring same-colored cubes are at distance strictly greater than $1$; I addressed this by padding the period from $t=\lceil\sqrt{n}\rceil+2$ to $t=\lceil\sqrt{n}\rceil+3$.

FINAL

UNRESOLVED.

1. (i) Strongest proved partial results here:
   • Elementary bounds: $n+1\le \chi(G_n)\le (\lceil\sqrt{n}\rceil+3)^n$ (Lemmas 704.1--704.2).
   • The problem text records much stronger exponential bounds (Frankl--Wilson lower bound and Larman--Rogers/Prosanov upper bound), but I did not reproduce those proofs.
2. (ii) First gap: establish sharp exponential growth rates (or the existence of $\lim_{n\to\infty}\chi(G_n)^{1/n}$) with proofs that do not rely on deep external theorems not included in the statement.
3. (iii) Top 3 next moves:
   1. Work out an explicit finite unit-distance graph in $\mathbb{R}^n$ with chromatic number $(c+o(1))^n$ (re-deriving a Frankl--Wilson-type lower bound from first principles).
   2. Improve the cube-tiling argument by using better sphere/ball packings or Voronoi cells to reduce the base of the exponential upper bound.
   3. Numerically compute/approximate $\chi(G_n)$ for small $n$ in restricted models (e.g. measurable colorings or periodic colorings) to guess limiting behavior.
4. (iv) Minimal counterexample structure (to existence of the limit): one would need oscillation between lower-bound constructions and upper-bound constructions so that $\chi(G_n)^{1/n}$ fails to converge; this would likely involve different extremal configurations dominating in different dimensions.