Better Bounds for Planar Sets Avoiding Unit Distances

• DOI: 10.1007/s00454-015-9751-5
• Publication Date: 2015-12-09T13:38:02Z
• Authors: Tamás Keleti; Máté Matolcsi; Fernando Mário de...; Imre Z. Ruzsa
• Keywords: QA Mathematics / matematika; Mathematics - Metric Geometry; 42B05, 52C10, 52C17, 90C05; FOS: Mathematics; Metric Geometry (math.MG); 0102 computer and information sciences; QA74 Analysis / analízis; 0101 mathematics; 01 natural sciences

A $1$-avoiding set is a subset of $\mathbb{R}^n$ that does not contain pairs of points at distance $1$. Let $m_1(\mathbb{R}^n)$ denote the maximum fraction of $\mathbb{R}^n$ that can be covered by a measurable $1$-avoiding set. We prove two results. First, we show that any $1$-avoiding set in $\mathbb{R}^n$ ($n\ge 2$) that displays block structure (i.e., is made up of blocks such that the distance between any two points from the same block is less than $1$ and points from distinct blocks lie farther than $1$ unit of distance apart from each other) has density strictly less than $1/2^n$. For the special case of sets with block structure this proves a conjecture of Erdős asserting that $m_1(\mathbb{R}^2) < 1/4$. Second, we use linear programming and harmonic analysis to show that $m_1(\mathbb{R}^2) \leq 0.258795$.<br/>16 pages, 1 figure. Contains a Sage script called dstverify.sage, to verify the application of Theorem 3.3. Download the article source to get the script<br/>