Erdős Problem #174

Erdős Problem 174: finite Ramsey witnesses and a quadratic obstruction

1. Statement and scope

A finite Euclidean set $A$ is Ramsey if, for every finite number of colours, some sufficiently high-dimensional Euclidean space has a monochromatic congruent copy of $A$ in every colouring. Characterising all such sets remains unresolved. We prove that every rectangular box, and every subset of its vertices, is Ramsey. We also give an explicit obstruction for every nonspherical set with rational coordinates. These statements are reconstructions of known mechanisms, not a proposed new classification.

2. Pairs have finite witnesses

For $k$ colours and a prescribed length $a>0$, take $k+1$ points at pairwise distance $a$, the vertices of a regular simplex in $\mathbb R^k$. For example, the vectors $(a/\sqrt2)e_i$ in $\mathbb R^{k+1}$ lie in a $k$-dimensional affine subspace and have these distances. Two vertices share a colour. Thus this finite set forces a monochromatic pair of length $a$.

This finite-witness property is preserved by Cartesian products. Suppose $F\subset\mathbb R^u$ forces a monochromatic copy of $A$ in every $k$-colouring, and put $M=|F|$. Suppose $G\subset\mathbb R^v$ forces a monochromatic copy of $B$ in every $k^M$-colouring. In any $k$-colouring of $F\times G$, assign to $g\in G$ the entire ordered colour pattern on the fibre $F\times\{g\}$. There are at most $k^M$ patterns. Choose a copy $B'\subset G$ with a common pattern, then a monochromatic copy $A'\subset F$ in that pattern. The set $A'\times B'$ is monochromatic. Orthogonality of the two coordinate spaces gives \[ |(x,y)-(x',y')|^2=|x-x'|^2+|y-y'|^2, \] so it is congruent to $A\times B$.

Starting with the pair witnesses and iterating proves the assertion for every box $\{0,a_1\}\times\cdots\times\{0,a_r\}$, with $a_i>0$. Taking subsets preserves the Ramsey property, because a monochromatic copy of a larger set contains a copy of each subset. This proves the claimed positive family without an infinite compactness input.

3. An explicit obstruction from an integer affine relation

Suppose $A=\{a_1,\ldots,a_s\}$ has integers $m_i$, not all zero, satisfying \[ \sum_i m_i=0,\qquad \sum_i m_i a_i=0,\qquad C:=\sum_i m_i|a_i|^2\ne0.\tag{1} \] Reverse all signs if necessary to make $C>0$, and set \[ K=\sum_{m_i>0}m_i=-\sum_{m_i<0}m_i\ge1, \qquad \varepsilon=C/K. \] In every dimension colour $x$ by \[ \left\lfloor |x|^2/\varepsilon\right\rfloor\pmod {2K}.\tag{2} \] This uses the same finite number $2K$ of colours in all dimensions. First translate $A$ so that $a_1=0$; all three conditions in $1$, including $C$, are unchanged. Any congruent copy then has points $x_i=t+Ua_i$, where $U$ preserves inner products on the linear span of $A$. Expanding the squares and using $1$ gives $\sum_i m_i|x_i|^2=C$.

If the copy were monochromatic, write $|x_i|^2/\varepsilon=q_i+\theta_i$, with $q_i$ integers of one residue modulo $2K$ and $0\le\theta_i<1$. Then \[ K=\sum_i m_iq_i+\sum_i m_i\theta_i\in 2K\mathbb Z+(-K,K). \] The strict error interval follows because the positive and negative coefficients each have total absolute weight $K$. The displayed membership is impossible: $K$ is exactly midway between consecutive multiples of $2K$. Thus $2$ avoids every monochromatic copy of $A$, proving it is not Ramsey.

For instance, three equally spaced collinear points have coefficients $(1,-2,1)$, $K=2$ and $C=2a^2$, where $a$ is their spacing. Four colours, given by $\lfloor |x|^2/a^2\rfloor$ modulo four, avoid them in every dimension.

4. Why the obstruction covers rational nonspherical sets

A finite set is spherical precisely when there are $b\in\mathbb R^n$ and $\beta\in\mathbb R$ with \[ |a_i|^2=2b\cdot a_i+\beta\qquad(1\le i\le s).\tag{3} \] Indeed, this is equivalent to $|a_i-b|^2=|b|^2+\beta$ being constant; for a set with at least two points this constant is positive. Singletons cause no difficulty and are Ramsey.

If all coordinates are rational and $3$ is inconsistent, rational row reduction supplies a rational vector annihilating the columns of the constant and coordinate matrix but not the squared-norm column. Clearing denominators gives exactly $1$. Hence every rational-coordinate Ramsey set must be spherical.

The full necessary spherical condition, without rationality, is known from Erdős and collaborators, as recorded on the problem page. Our explicit argument above proves only the rational-relation case: irrational coefficients cannot simply be reduced modulo an integer in $2$. Conversely, the positive box family does not prove that every spherical set is Ramsey. These are the two limits of this attempt.

Source: https://www.erdosproblems.com/174. No external classification theorem is used in the proved partial results.

Completion rate estimate: 35%.

PROBLEM

A finite set $A\subset \mathbb{R}^n$ is called Ramsey if, for any $k\geq 1$, there exists some $d=d(A,k)$ such that in any $k$-colouring of $\mathbb{R}^d$ there exists a monochromatic copy of $A$. Characterise the Ramsey sets in $\mathbb{R}^n$.

OUTPUT

1) FORMAL RESTATEMENT

Fix $n\ge 1$. A finite set $A\subseteq\mathbb R^n$ is called Ramsey if for every integer $k\ge 1$ there exists an integer $d=d(A,k)\ge 1$ such that for every coloring \[ c:\mathbb R^d\to\{1,2,\dots,k\} \] there exists an isometric embedding (distance-preserving map) \[ \varphi:\mathbb R^n\to\mathbb R^d \] and a color $\gamma$ such that $c$ is constant equal to $\gamma$ on $\varphi(A)$.

The problem asks for a characterization of such finite sets $A$.

---

2) QUICK LITERATURE/CONTEXT CHECK

I will not use or claim any external results beyond what is explicitly written in the problem text.

The problem text reports:

* Every Ramsey set is spherical (lies on a sphere). * Two conjectures: spherical $\Rightarrow$ Ramsey (Graham), and Ramsey $\Leftrightarrow$ subtransitive (Leader–Russell–Walters). * Several families known to be Ramsey (rectangles, simplices, trapezoids, regular polygons/polyhedra).

I do not re-prove these deep results.

---

3) ATTACK PLAN

A full characterization is beyond my current reach. I instead prove basic closure properties that any proposed characterization must respect.

---

4) WORK

Lemma 4.1 (congruence invariance)

If $A\subseteq\mathbb R^n$ is Ramsey and $A'$ is congruent to $A$ (i.e. $A'=\psi(A)$ for some isometry $\psi$ of $\mathbb R^n$), then $A'$ is Ramsey.

Proof. Fix $k\ge 1$. Since $A$ is Ramsey, there exists $d=d(A,k)$ such that every $k$-coloring of $\mathbb R^d$ contains a monochromatic copy of $A$.

Let $c:\mathbb R^d\to\{1,\dots,k\}$ be any $k$-coloring. By the Ramsey property of $A$, there exists an isometric embedding $\varphi:\mathbb R^n\to\mathbb R^d$ such that $c$ is constant on $\varphi(A)$.

Now consider $A'=\psi(A)$. The composition $\varphi\circ \psi^{-1}$ is also an isometric embedding of $\mathbb R^n$ into $\mathbb R^d$, and \[ (\varphi\circ\psi^{-1})(A')=(\varphi\circ\psi^{-1})(\psi(A))=\varphi(A). \] Therefore $c$ is constant on $(\varphi\circ\psi^{-1})(A')$, giving a monochromatic copy of $A'$. Since $c$ was arbitrary, the same $d$ works for $A'$. $\square$

---

Lemma 4.2 (heredity under taking subsets)

If $A\subseteq\mathbb R^n$ is Ramsey and $B\subseteq A$ is a (finite) subset, then $B$ is Ramsey.

Proof. Fix $k\ge 1$ and let $d=d(A,k)$ witness that $A$ is Ramsey for $k$ colors. Given any $k$-coloring $c$ of $\mathbb R^d$, there exists an isometric embedding $\varphi$ such that $c$ is constant on $\varphi(A)$. Then in particular $c$ is constant on $\varphi(B)\subseteq \varphi(A)$, so $\varphi(B)$ is a monochromatic copy of $B$. Thus the same $d$ works for $B$. $\square$

---

5) VERIFICATION

* Lemma 4.1: the only step is that composition with an isometry preserves distances, so it maps congruent copies to congruent copies. * Lemma 4.2: immediate from the definition; any monochromatic copy of $A$ contains a monochromatic copy of any subset.

These lemmas are correct but do not approach the deep classification problem.

---

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result obtained here.

I proved two structural necessities for the class of Ramsey sets:

* invariance under congruence (Lemma 4.1); * heredity under taking subsets (Lemma 4.2).

(ii) Exact first gap.

Give a nontrivial necessary-and-sufficient geometric characterization of Ramsey sets beyond these basic closure properties.

(iii) Top 3 next moves (concrete targets).

1. Prove “spherical $\Rightarrow$ Ramsey” or find a spherical counterexample. 2. Understand the “subtransitive” condition and either prove it implies Ramsey or find a Ramsey set that is not subtransitive. 3. Develop obstructions: show that certain non-spherical configurations cannot be Ramsey by constructing explicit colorings avoiding them.

(iv) What a minimal counterexample would likely look like.

A minimal counterexample to “spherical $\Rightarrow$ Ramsey” would be a spherical finite set $A$ with a family of colorings in increasing dimension avoiding monochromatic copies. Such a counterexample would likely be highly symmetric (to evade standard Ramsey embeddings) yet fail the subtransitivity property.