Skip to main content

Section 47.3 Density of planar sets avoiding unit distance

The density of a planar set avoiding unit distances is a concept that has been studied for many decades and was first proposed by Leo Moser. The question that still trills mathematicians is: “What is \(m_{1}(\mathbb{R}^2)\text{,}\) the maximum density of a measurable set in the plane that does not contain a unit-distance pair?”

The problem was popularized by Erdős who stated that it “seems likely” that \(m_{1}(\mathbb{R}^2)\) has an upper bound of \(1/4\text{.}\)

To give an intuitive example of how we can find the density of \(\mathbb{R}^2\text{,}\) consider packing the Euclidean plane with unit circles (circles with radius 1) in figure. In each unit circle, we put another circle of radius \(1/2\) and note that the points in the blue circles of figure are all non-unit distance.

Figure 47.3.1. An “easy” lower bound for \(m_{1}(\mathbb{R}^2)\)

To find the density, i.e the portion of the part of the plane covered by unit circles we consider the triangulation of the plane by equilateral triangles of side 2 and with the verices at the centres of unit circles.

Figure 47.3.2. A triangle of side 2 and its intersections with three unit circles.

Recall that the vertices of the triangle are the centres of unit circles and observe that the area of the intersection of the triangle and the circles is given by \(3\cdot\frac{1^2\cdot \frac{\pi}{3}}{2}=\frac{\pi}{2}\text{.}\)

Since the area of the equilateral triangle of side 2 equals to \(\sqrt{3}\) it follows that the proportion of the triangle covered by its intersections with the unit circles is

\begin{equation*} \frac{\mbox{Area of the intersection}}{\mbox{Area of the triangle}}=\frac{\frac{\pi}{2}}{\sqrt{3}}=\frac{\pi}{2\sqrt{3}}\approx 0.9069. \end{equation*}
Since this is true for any triangle in the this particular triangulation of the plane we conclude that the density of a unit circle packing in the Euclidean plane is about \(0.9069\text{.}\)
Figure 47.3.3. A closer look: Blue circles with no boundary and radius \(0.5\text{.}\)

Observe that the area of each blue circle takes \(\frac{0.5^2\pi}{\pi}=\frac{1}{4}\) of the area of the yellow circle. Hence the density of the set covered by blue circles in the Euclidean plane is equal to one quarter of the density of the set covered by yellow circles

.

In other words,

\begin{equation*} m_1(\mathbb{R}^2)\gt \frac{1}{4}\cdot 0.9069\approx 0.2267. \end{equation*}

The history of finding the upper and lower bounds of the density of planar sets is quite interesting as many different techniques are used.

In 2010 Oliveira Filho and Vallentin used a combination of linear programming and Fourier analysis to prove \(m_{1}(\mathbb{R}^2) \leq 0.268\text{.}\)

In 2020 Bellitto, Pêcher, and Sédillot studied the fractional number of the plane together with the density of the sets that avoid unit distances to show that \(m_{1}(\mathbb{R}^2) \leq 0.25646\text{.}\) The best current known upper bound is \(0.25442\) found by Gergely Ambrus and Mátê Matolcsi in their 2020 paper “Density Estimates of 1-Avoiding Sets Via Higher Order Correlations”.

We are getting closer and closer to Erdős conjecture that \(m_{1}(\mathbb{R}^2)\lt 0.25\) many decades ago!

Above we have shown how to obtain the lower bound of \(m_{1}(\mathbb{R}^2) \geq 0.2267\text{.}\)

The best current known lower bound is \(0.229\) which was achieved by Croft in 1967.

\(\textbf{References:}\)

Ambrus, G. and Matolcsi, M. (2020). Density estimates of 1-avoiding sets via higher order correlations. https://arxiv.org/abs/1809.05453

Bellitto, T., Pêcher, A., and Sédillot, A. (2020). On the density of sets of the Euclidean plane avoiding distance 1. https://arxiv.org/abs/1810.00960

Croft, H.T. (1967). Incidence incidents. Eureka 30, 22-26.

de Oliveira Filho, F.M. and Vallentin, F. (2010). Fourier analysis, linear programming, and densities of distance-avoiding sets in \(\mathbb{R}^n\text{,}\) Journal of the European Mathematical Society 12, 1417-1428.

R. Hochberg and P. O'Donnell. (1993). A large independent set in the unit distance graph. Geombinatorics, 2(4):83-84.