Erdős Problem #706

Erdős Problem 706 --- 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/706.tex.

REUSED SOURCE 1

1) FORMAL RESTATEMENT

Fix $r\in\mathbb{N}$. For a finite point set $P\subset\mathbb{R}^2$ and a set of distances $A\subset(0,\infty)$ with $|A|=r$, define a graph $G(P,A)$ with vertex set $P$ and an edge between distinct $x,y\in P$ iff $\|x-y\|_2\in A$. Define $L(r)$ to be the minimal integer such that for all such $(P,A)$, \[ \chi(G(P,A))\le L(r). \] The problem asks for good bounds/estimates for $L(r)$ as $r\to\infty$, in particular whether $L(r)\le r^{O(1)}$.

2) QUICK LITERATURE/CONTEXT CHECK

I will only use facts stated in the problem text. For $r=1$ (unit distance graphs), the text states $5\le L(1)\le 7$.

3) ATTACK PLAN

- Lower bounds: build explicit finite configurations forcing many colors (e.g. cliques). - Upper bounds: produce an explicit coloring of the plane (or of all such graphs) depending only on $r$. A simple product-coloring argument will give an exponential upper bound $7^r$.

4) WORK

Lemma 706.1 (Clique lower bound $L(r)\ge r+1$). For every $r\ge 1$, $L(r)\ge r+1$.

Proof. Let $P=\{0,1,2,\dots,r\}\subset\mathbb{R}$ viewed as a subset of $\mathbb{R}^2$ on the $x$-axis. Let $A=\{1,2,\dots,r\}\subset(0,\infty)$, so $|A|=r$. For any two distinct points $i,j\in P$ we have $\|i-j\|_2=|i-j|\in\{1,2,\dots,r\}=A$, so every pair is an edge. Thus $G(P,A)$ is the complete graph $K_{r+1}$, whose chromatic number is $r+1$. Therefore by definition of $L(r)$, we must have $L(r)\ge r+1$. $\square$

Lemma 706.2 (A $7$-coloring for a single forbidden distance). Assume $L(1)\le 7$ (as stated in the problem text). Then for every $d>0$, the infinite distance graph on $\mathbb{R}^2$ with edges between points at distance exactly $d$ is $7$-colorable.

Proof. Let $d>0$. Consider the scaling map $S:\mathbb{R}^2\to\mathbb{R}^2$ given by $S(x)=x/d$. If two points $x,y$ satisfy $\|x-y\|_2=d$, then $\|S(x)-S(y)\|_2=1$. By the assumption $L(1)\le 7$, there exists a proper $7$-coloring $c:\mathbb{R}^2\to\{1,\dots,7\}$ such that no unit-distance pair has the same color. Then $c\circ S$ is a $7$-coloring of $\mathbb{R}^2$ such that if $\|x-y\|_2=d$, then $c(S(x))\ne c(S(y))$, i.e. $(c\circ S)(x)\ne (c\circ S)(y)$. $\square$

Proposition 706.3 (Exponential upper bound $L(r)\le 7^r$). Assume $L(1)\le 7$. Then for every $r\ge 1$, \[ L(r)\le 7^r. \]

Proof. Let $A=\{d_1,\dots,d_r\}\subset(0,\infty)$ and let $P\subset\mathbb{R}^2$ be finite. For each $j\in\{1,\dots,r\}$, by Lemma 706.2 there exists a $7$-coloring \[ c_j:\mathbb{R}^2\to\{1,\dots,7\} \] that is proper for the distance-$d_j$ graph, i.e. $\|x-y\|_2=d_j\Rightarrow c_j(x)\ne c_j(y)$. Define a combined coloring \[ C:\mathbb{R}^2\to\{1,\dots,7\}^r,\qquad C(x)=(c_1(x),\dots,c_r(x)). \] This uses at most $7^r$ colors. If $x,y\in P$ are adjacent in $G(P,A)$, then $\|x-y\|_2\in A$, so $\|x-y\|_2=d_j$ for some $j$. For that $j$, $c_j(x)\ne c_j(y)$, hence $C(x)\ne C(y)$. Therefore $C$ is a proper coloring of $G(P,A)$ using at most $7^r$ colors. Since $(P,A)$ were arbitrary, $L(r)\le 7^r$. $\square$

FAST REALITY CHECK (small $r$). The bounds above yield: - $r=1$: $2\le L(1)\le 7$ from Lemma 706.1 and the stated fact (the text also states $L(1)\ge 5$). - $r=2$: $3\le L(2)\le 49$. - $r=3$: $4\le L(3)\le 343$.

5) VERIFICATION

- Lemma 706.1: the arithmetic progression construction makes all pairwise distances fall into $A$, so it is indeed a clique. - Lemma 706.2: scaling preserves the adjacency relation up to rescaling of forbidden distance; the pullback of a proper coloring is proper. - Proposition 706.3: if an edge has length $d_j$, the $j$-th coordinate of $C$ differs, guaranteeing a proper coloring.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. Using only the stated bound $L(1)\le 7$, I proved the general bounds \[ r+1\le L(r)\le 7^r. \]

(ii) First gap (crisp). Improve $L(r)\le 7^r$ to a polynomial bound $L(r)\le r^{O(1)}$ (or construct superpolynomial lower bounds).

(iii) Top 3 next moves. 1. Seek better single-distance colorings that compose more efficiently than direct products (e.g. using a common refinement for all $d\in A$). 2. Look for lower bounds beyond $r+1$, e.g. configurations in the plane with $\Omega(r^2)$ points realizing only $r$ distinct distances but forcing high chromatic number. 3. Computational exploration for small $r$ to guess growth of $L(r)$: search for point sets with many-distance edge sets forcing large $\chi$.

(iv) Minimal counterexample structure. A minimal counterexample to $L(r)\le r^{O(1)}$ would be a distance set $A$ of size $r$ such that the plane distance graph $G(\mathbb{R}^2,A)$ contains finite induced subgraphs with chromatic number growing faster than any polynomial in $r$.

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

Fix $r\in\mathbb{N}$. For a finite point set $P\subset\mathbb{R}^2$ and a set of distances $A\subset(0,\infty)$ with $|A|=r$, define a graph $G(P,A)$ with vertex set $P$ and an edge between distinct $x,y\in P$ iff $\|x-y\|_2\in A$. Define $L(r)$ to be the minimal integer such that for all such $(P,A)$, \[ \chi(G(P,A))\le L(r). \] The problem asks for good bounds/estimates for $L(r)$ as $r\to\infty$, in particular whether $L(r)\le r^{O(1)}$.

2) QUICK LITERATURE/CONTEXT CHECK

I will only use facts stated in the problem text. For $r=1$ (unit distance graphs), the text states $5\le L(1)\le 7$.

3) ATTACK PLAN

- Lower bounds: build explicit finite configurations forcing many colors (e.g. cliques). - Upper bounds: produce an explicit coloring of the plane (or of all such graphs) depending only on $r$. A simple product-coloring argument will give an exponential upper bound $7^r$.

4) WORK

Lemma 706.1 (Clique lower bound $L(r)\ge r+1$). For every $r\ge 1$, $L(r)\ge r+1$.

Proof. Let $P=\{0,1,2,\dots,r\}\subset\mathbb{R}$ viewed as a subset of $\mathbb{R}^2$ on the $x$-axis. Let $A=\{1,2,\dots,r\}\subset(0,\infty)$, so $|A|=r$. For any two distinct points $i,j\in P$ we have $\|i-j\|_2=|i-j|\in\{1,2,\dots,r\}=A$, so every pair is an edge. Thus $G(P,A)$ is the complete graph $K_{r+1}$, whose chromatic number is $r+1$. Therefore by definition of $L(r)$, we must have $L(r)\ge r+1$. $\square$

Lemma 706.2 (A $7$-coloring for a single forbidden distance). Assume $L(1)\le 7$ (as stated in the problem text). Then for every $d>0$, the infinite distance graph on $\mathbb{R}^2$ with edges between points at distance exactly $d$ is $7$-colorable.

Proof. Let $d>0$. Consider the scaling map $S:\mathbb{R}^2\to\mathbb{R}^2$ given by $S(x)=x/d$. If two points $x,y$ satisfy $\|x-y\|_2=d$, then $\|S(x)-S(y)\|_2=1$. By the assumption $L(1)\le 7$, there exists a proper $7$-coloring $c:\mathbb{R}^2\to\{1,\dots,7\}$ such that no unit-distance pair has the same color. Then $c\circ S$ is a $7$-coloring of $\mathbb{R}^2$ such that if $\|x-y\|_2=d$, then $c(S(x))\ne c(S(y))$, i.e. $(c\circ S)(x)\ne (c\circ S)(y)$. $\square$

Proposition 706.3 (Exponential upper bound $L(r)\le 7^r$). Assume $L(1)\le 7$. Then for every $r\ge 1$, \[ L(r)\le 7^r. \]

Proof. Let $A=\{d_1,\dots,d_r\}\subset(0,\infty)$ and let $P\subset\mathbb{R}^2$ be finite. For each $j\in\{1,\dots,r\}$, by Lemma 706.2 there exists a $7$-coloring \[ c_j:\mathbb{R}^2\to\{1,\dots,7\} \] that is proper for the distance-$d_j$ graph, i.e. $\|x-y\|_2=d_j\Rightarrow c_j(x)\ne c_j(y)$. Define a combined coloring \[ C:\mathbb{R}^2\to\{1,\dots,7\}^r,\qquad C(x)=(c_1(x),\dots,c_r(x)). \] This uses at most $7^r$ colors. If $x,y\in P$ are adjacent in $G(P,A)$, then $\|x-y\|_2\in A$, so $\|x-y\|_2=d_j$ for some $j$. For that $j$, $c_j(x)\ne c_j(y)$, hence $C(x)\ne C(y)$. Therefore $C$ is a proper coloring of $G(P,A)$ using at most $7^r$ colors. Since $(P,A)$ were arbitrary, $L(r)\le 7^r$. $\square$

FAST REALITY CHECK (small $r$). The bounds above yield: - $r=1$: $2\le L(1)\le 7$ from Lemma 706.1 and the stated fact (the text also states $L(1)\ge 5$). - $r=2$: $3\le L(2)\le 49$. - $r=3$: $4\le L(3)\le 343$.

5) VERIFICATION

- Lemma 706.1: the arithmetic progression construction makes all pairwise distances fall into $A$, so it is indeed a clique. - Lemma 706.2: scaling preserves the adjacency relation up to rescaling of forbidden distance; the pullback of a proper coloring is proper. - Proposition 706.3: if an edge has length $d_j$, the $j$-th coordinate of $C$ differs, guaranteeing a proper coloring.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. Using only the stated bound $L(1)\le 7$, I proved the general bounds \[ r+1\le L(r)\le 7^r. \]

(ii) First gap (crisp). Improve $L(r)\le 7^r$ to a polynomial bound $L(r)\le r^{O(1)}$ (or construct superpolynomial lower bounds).

(iii) Top 3 next moves. 1. Seek better single-distance colorings that compose more efficiently than direct products (e.g. using a common refinement for all $d\in A$). 2. Look for lower bounds beyond $r+1$, e.g. configurations in the plane with $\Omega(r^2)$ points realizing only $r$ distinct distances but forcing high chromatic number. 3. Computational exploration for small $r$ to guess growth of $L(r)$: search for point sets with many-distance edge sets forcing large $\chi$.

(iv) Minimal counterexample structure. A minimal counterexample to $L(r)\le r^{O(1)}$ would be a distance set $A$ of size $r$ such that the plane distance graph $G(\mathbb{R}^2,A)$ contains finite induced subgraphs with chromatic number growing faster than any polynomial in $r$.