Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Source: original paper, printed p. 535, the counterexample following Theorem 3. The distance estimates below supply the omitted geometric verification.

Statement

There is a red-blue coloring of R2\mathbb R^2 with no red unit-distance pair and no blue congruent copy of a particular 101210^{12}-point set.

Full proof

Set M=106M=10^6, h=3/Mh=3/M, and

K={(ih,jh):0≤i,j<M}.K=\{(ih,jh):0\le i,j<M\}.

Color red the closed squares

[2m,2m+1/2]×[2n,2n+1/2],m,n∈Z,[2m,2m+1/2]\times[2n,2n+1/2],\qquad m,n\in\mathbb Z,

and color every other point blue. Points in one red square have mutual distance at most 2/2<1\sqrt2/2<1. Points in different red squares differ by at least 3/23/2 in at least one coordinate, so their distance exceeds one. Thus there is no red unit pair, including on square boundaries.

Consider any congruent copy of KK, with arbitrary orientation and location. Its convex hull is a square of side

L=(M−1)h=3−3/M.L=(M-1)h=3-3/M.

The red square centers form (1/4,1/4)+2Z2(1/4,1/4)+2\mathbb Z^2. A center cc lies at distance at most 2\sqrt2 from the center of the grid square, by rounding the two coordinates to that lattice. Since L/2>2L/2>\sqrt2, the point cc lies inside the grid square regardless of its orientation.

Round the two coordinates of cc in the grid's orthonormal coordinate system to the nearest grid positions. Because cc is inside the grid square, the resulting point zz belongs to the finite grid and satisfies

∣z−c∣≤h/2<1/4.|z-c|\le h/\sqrt2<1/4.

The disk of radius 1/41/4 centered at cc lies in its red square, so zz is red. Every congruent copy of KK therefore meets the red set. None is wholly blue.

This is an array of small red squares, not a coloring by strips. The size 101210^{12} is a historical sufficient example, not an optimal threshold. The argument does not refute the blue-unit-square conclusion of Problem 214.