Erdős Problem #1127

Erdős Problem 1127: distinct distances and the continuum hypothesis

Statement and answer.

For each fixed positive integer $n$, the assertion that $\mathbb R^n$ is a countable union of sets with all unordered pairwise distances distinct is equivalent, over ZFC, to the continuum hypothesis (CH). We prove the obstruction and the one-dimensional construction below, and explicitly use Kunen's theorem for the higher-dimensional positive direction. This reconstructs the known independence result; see https://www.erdosproblems.com/1127.

CH gives a partition of the line.

Assume CH and index a Hamel basis of $\mathbb R$ over $\mathbb Q$ as $\{b_\alpha:\alpha<\omega_1\}$. For each countable ordinal $\alpha$, fix an injection $e_\alpha:\alpha\to\mathbb N$. If $x\ne0$, express it uniquely as a finite rational linear combination of basis elements, and let $\alpha$ be the largest index appearing. Colour $x$ by its nonzero leading coefficient together with the finite list of pairs \[ \{(e_\alpha(\beta),q_\beta):\beta<\alpha,\ q_\beta\ne0\}. \] There are countably many possible colours. In a fixed colour, at most one real has any given largest index $\alpha$. Every finite set of distinct elements of that colour is therefore linearly independent: in a purported nontrivial rational relation, the uniquely largest basis index among the participating reals cannot cancel. Give $0$ a separate colour.

Rational linear independence implies distinct distances. An equality $|x-y|=|z-w|$ between two distinct unordered pairs, each consisting of distinct elements of one colour, yields $x-y=\pm(z-w)$, a nontrivial rational linear relation after collecting repeated elements.

Failure of CH forbids such a partition, already on a line.

If $2^{\aleph_0}>\aleph_1$, a Hamel basis has cardinality $2^{\aleph_0}$. Indeed the rational span of an infinite set has the same cardinality as that set. Choose disjoint subfamilies $\{u_i:i\in I\}$, $\{v_j:j\in J\}$ with $|I|=\aleph_1$, $|J|=\aleph_2$. Given any countable colouring of the reals, for each $j$ choose distinct $i_j,i'_j$ such that $u_{i_j}+v_j$ and $u_{i'_j}+v_j$ have a common colour $c_j$. Such a pair exists because $I$ is uncountable.

There are only $\aleph_1$ possible triples $(\{i_j,i'_j\},c_j)$. Two distinct $j,j'$ therefore give the same triple. The four reals \[ u_i+v_j,\quad u_{i'}+v_j,\quad u_i+v_{j'},\quad u_{i'}+v_{j'} \] are distinct by basis independence, are monochromatic, and have two distinct pairs at distance $|u_i-u_{i'}|$. This contradicts the required property. A partition in any higher dimension would restrict to such a partition of a line, so the same obstruction applies.

Explicit higher-dimensional input.

K. Kunen, Partitioning Euclidean space, Mathematical Proceedings of the Cambridge Philosophical Society 102 $1987$, 379--383, proves in Section 2: under CH, for every finite $n$ there is a countable colouring of $\mathbb R^n$ whose colour classes have distinct distances. The primary paper is https://doi.org/10.1017/S0305004100067426. That geometric transfinite-construction theorem is an external input here; the Hamel-basis argument above alone does not prove its higher-dimensional version. Together with the obstruction it proves the claimed equivalence for every positive $n$. The usual relative consistency and independence of CH are the additional foundational input for calling the question independent of ZFC.

Completion estimate.

The equivalence is established, with Kunen's higher-dimensional theorem and the standard independence of CH explicitly imported. COMPLETION: 100%

FORMAL RESTATEMENT

Fix an integer dimension $n\ge 1$ and consider Euclidean space $\mathbb{R}^n$ with its usual metric $d(x,y)=\|x-y\|_2$. Question: does there exist a partition \[ \mathbb{R}^n = \bigcup_{j=1}^{\infty} S_j,\qquad S_i\cap S_j=\varnothing\ (i\neq j), \] such that for every $j$ the set of pairwise distances inside $S_j$ is distinct, i.e. \[ \forall\{x,y\}\neq\{u,v\}\subset S_j\ (x\neq y,\ u\neq v)\implies \|x-y\|_2\neq \|u-v\|_2? \]

QUICK LITERATURE/CONTEXT CHECK

I only record context explicitly stated in the problem file. The file states:

• Assuming the continuum hypothesis (CH), this is true for $n=1$ (Erdős--Kakutani), for $n=2$ (Davies), and for all $n$ (Kunen).
• Some dependence on CH is necessary in the sense that if CH is false then (as stated) any finite decomposition of $\mathbb{R}$ has four points determining only four distances.

ATTACK PLAN

Proof track ideas.

• Under CH, attempt to build each color class as a large $\mathbb{Q}$-linearly independent set (in $n=1$), since that property forces distinct distances (Lemma 1127.1).
• In higher $n$, search for algebraic independence conditions that force distinct Euclidean distances (hard because distances involve squares and sums).

Disproof track ideas.

• Try to show that in ZFC (without CH) a countable partition must create repeated distances in some cell via a Ramsey-type argument.
• Construct adversarial colorings and search for forced repeated distances in one color.

WORK

Lemma 1127.1 ($\mathbb{Q}$-linear independence implies distinct distances in $\mathbb{R}$). Let $S\subset\mathbb{R}$ be linearly independent over $\mathbb{Q}$. Then for any two unordered pairs of distinct points $\{x,y\}\ne\{u,v\}\subset S$ we have \[ |x-y|\ne |u-v|. \]

Proof. Assume for contradiction that $|x-y|=|u-v|$ for two unordered pairs of distinct points from $S$. Then either

1. $x-y=u-v$, in which case $x-y-u+v=0$, or
2. $x-y=v-u$, in which case $x-y+u-v=0$.

In both cases we obtain a rational linear relation among the elements of $\{x,y,u,v\}\subset S$ with coefficients in $\{\pm 1\}$, not all zero. Since $S$ is $\mathbb{Q}$-linearly independent, the only such relation is the trivial one, so all coefficients must be $0$. That is impossible unless the multiset of variables collapses, forcing $\{x,y\}=\{u,v\}$. This contradicts $\{x,y\}\ne\{u,v\}$. Therefore $|x-y|\ne |u-v|$. $\square$

Lemma 1127.2 (explicit infinite set with distinct distances). The set $S:=\{2^k: k\in\mathbb{N}\}\subset\mathbb{R}$ has all pairwise distances distinct. Consequently, for every $n\ge 1$ the embedded set $S e_1=\{2^k e_1\}\subset\mathbb{R}^n$ has all pairwise Euclidean distances distinct.

Proof. Consider two pairs with indices $i<j$ and $k<\ell$ and suppose \[ 2^j-2^i = 2^{\ell}-2^k. \] Factor both sides: \[ 2^i(2^{j-i}-1)=2^k(2^{\ell-k}-1). \] The integers $2^{j-i}-1$ and $2^{\ell-k}-1$ are odd. Taking the $2$-adic valuation (the exponent of $2$ dividing an integer) of both sides shows $i=k$. Substituting $i=k$ gives $2^{j-i}-1=2^{\ell-i}-1$, hence $j=\ell$. Therefore the unordered pairs coincide, so all distances are distinct. In $\mathbb{R}^n$, points on the $e_1$-axis satisfy $\|2^j e_1-2^i e_1\|_2=|2^j-2^i|$, so the same distinctness holds. $\square$

Lemma 1127.3 (no isosceles triangles in one cell). If $S\subset\mathbb{R}^n$ has all pairwise distances distinct, then $S$ contains no (nondegenerate) isosceles triangle.

Proof. If $x,y,z\in S$ are distinct and form an isosceles triangle, then two of the three distances among them are equal, e.g. $\|x-y\|_2=\|x-z\|_2$. But this gives two distinct unordered pairs $\{x,y\}$ and $\{x,z\}$ with the same distance, contradicting the defining property of $S$. $\square$

FAST REALITY CHECK (finite sample). For $S=\{1,2,4,8,16\}$ the distances are \[ 1,2,3,4,6,7,8,12,14,15 \] (all distinct). This matches Lemma 1127.2.

VERIFICATION

• Lemma 1127.1: the only subtlety is the use of absolute values; both sign cases give a nontrivial rational relation, so independence rules them out.
• Lemma 1127.2: the $2$-adic valuation argument is rigorous because each side is a product of a power of $2$ and an odd integer, so the exponent of $2$ is unique.
• Lemma 1127.3 is immediate from the definition of distinct pairwise distances.

FINAL

UNRESOLVED

(i) Strongest proved partial result. In $\mathbb{R}$, any $\mathbb{Q}$-linearly independent set has distinct pairwise distances (Lemma 1127.1). Independently of set-theoretic issues, explicit infinite examples exist in every $\mathbb{R}^n$ (Lemma 1127.2).

(ii) First gap (crisp). Decide in ZFC (without additional axioms such as CH) whether there exists a countable partition of $\mathbb{R}^n$ into sets with all pairwise distances distinct.

(iii) Top 3 next moves.

• Identify a purely geometric/algebraic condition on $S\subset\mathbb{R}^n$ that forces distinct distances and is compatible with building a countable partition.
• Attempt a ZFC lower-bound obstruction: prove that any countable coloring of $\mathbb{R}^n$ yields repeated distances in some color via a combinatorial/measure/category argument.
• For $n=1$, analyze whether "$\mathbb{R}$ is a countable union of $\mathbb{Q}$-linearly independent sets" can be decided in ZFC.

(iv) Minimal counterexample structure. A negative answer in ZFC would manifest as a proof that in every countable partition of $\mathbb{R}^n$ there exists at least one cell $S_j$ containing two distinct pairs at the same distance; in particular that cell would contain an isosceles triangle (Lemma 1127.3).