betaFeedback

Reading v1View latest version

WorksMathematics

A problem of Erdős about rich distances

Abstract

An old question posed by Erdős asked whether there exists a set of nn points such that c⋅nc \cdot n distances occur more than nn times. We provide an affirmative answer to this question, showing that there exists a set of nn points such that ⌊n4⌋\lfloor \frac{n}{4}\rfloor distances occur more than nn times. We also present a generalized version, finding a set of nn points where cm⋅nc_m \cdot n distances occurring more than n+mn+m times.

Introduction

In a 1997 paper, Erdős [1] asked the following question:

Problem (Erdős). For a set of nn points in a plane, can c⋅nc \cdot n of the distances occur more than nn times?

We provide an affirmative answer to the question by proving the following theorem:

Theorem 1.1. For all n∈Nn \in\mathbb{N}, there exists a set of nn points such that ⌊n4⌋\left\lfloor\frac{n}{4} \right\rfloor distances occur at least n+1n+1 times.

We also show the following generalization of Theorem 1.1, indicating that cmc_m distances can occur n+mn+m times.

Theorem 1.2. For all n∈Nn \in\mathbb{N}, there exist a set of nn points such that at least ⌊n2(m+1)⌋\left\lfloor\frac{n}{2(m+1)} \right\rfloor distances occur at least n+mn+m times.

Proof of Theorem 1.1

We start with proving the following simple claim:

Claim 2.1. In a regular mm-gon, ⌊m−12⌋\left\lfloor\frac{m-1}{2} \right\rfloor distances appear mm times.

Proof. Observe that in a regular mm-gon v1…vmv_1 \ldots v_m, the distances ∥vi−vi+k∥\lVert v_i-v_{i+k}\rVert and ∥vj−vj+k∥\lVert v_j-v_{j+k}\rVert are equal for all i,j∈[m]i,j \in[m] and some k∈[⌊m−12⌋]k \in\left[\left\lfloor\frac{m-1}{2} \right\rfloor\right]. Thus, we conclude ⌊m−12⌋\left\lfloor\frac{m-1}{2} \right\rfloor of the distances are repeating mm times.

Proof of Theorem 1.1. We will consider two cases: Case 1 for nn odd and Case 2 for nn even.

Case 1 Since nn is odd, let n=2m+1n=2m+1. Consider a (m+1)(m+1)-gon v1…vm+1v_1 \ldots v_{m+1}. From Claim 2.1, ⌊m2⌋\left\lfloor\frac{m}{2} \right\rfloor of the distances are repeated m+1m+1 times. Now, rotate the (m+1)(m+1)-gon around vertex v1v_1 to get a new (m+1)(m+1)-gon v1r2…rm+1v_1r_2 \ldots r_{m+1}. Again, ⌊m2⌋\left\lfloor\frac{m}{2} \right\rfloor of the distances are repeating m+1m+1 times in the new (m+1)(m+1)–gon. Since v1v_1 is the only common vertex between the two (m+1)(m+1)–gons, the total number of vertices in the two (m+1)(m+1)–gons is

A set of 9 points with 2 distances appearing 10 times

Figure 1. A set of 9 points with 2 distances appearing 10 times.

A set of 11 points with 2 distances appearing at least 12 times

Figure 2. A set of 11 points with 2 distances appearing at least 12 times.

2⋅(m+1)−1=2m+1=n2 \cdot(m+1)-1=2m+1=n

Also observe that as nn is odd, ⌊m2⌋=⌊n−14⌋=⌊n4⌋\left\lfloor\frac{m}{2}\right\rfloor=\left\lfloor\frac{n-1}{4}\right\rfloor=\left\lfloor\frac{n}{4}\right\rfloor of the distances occur

2⋅(m+1)=2m+2=n+12 \cdot(m+1)=2m+2=n+1

times. Hence, we get a set of nn points {v1,…,vm+1,r2,…,rm+1}\{v_1,\ldots,v_{m+1},r_2,\ldots,r_{m+1}\} where ⌊n4⌋\left\lfloor\frac{n}{4}\right\rfloor distances occur at least n+1n+1 times. This concludes Case 1.

A set of 10 points with 2 distance appearing at least 11 times

Figure 3. A set of 10 points with 2 distance appearing at least 11 times.

Case 2 The proof is similar to that of Case 1. However, instead of rotating a regular polygon around one of its vertices, we will reflect a regular polygon on one of its edges. Since nn is even, let n=2mn=2m. Consider a (m+1)(m+1)–gon v1…vm+1v_1\ldots v_{m+1}. From Claim 2.1, ⌊m2⌋\left\lfloor\frac{m}{2}\right\rfloor of the distances are repeated m+1m+1 times. Now, reflect the (m+1)(m+1)–gon over the edge v1v2v_1v_2 to get a new (m+1)(m+1)–gon v1v2v3′…vm+1′v_1v_2v'_3\ldots v'_{m+1}. Again, ⌊m2⌋\left\lfloor\frac{m}{2}\right\rfloor of the distances are repeated m+1m+1 times in the new (m+1)(m+1)–gon. Since v1v_1 and v2v_2 are the only common vertices between the two (m+1)(m+1)–gons, the total number of vertices in the two (m+1)(m+1)–gons is

2⋅(m+1)−2=2m=n.2\cdot(m+1)-2=2m=n.

Also, observe that the only distance common between the two (m+1)(m+1)–gons is ∥v1−v2∥\lVert v_1-v_2\rVert, and repeating only for the edge v1v2v_1v_2. Thus, ⌊m2⌋=⌊n4⌋\left\lfloor\frac{m}{2}\right\rfloor=\left\lfloor\frac{n}{4}\right\rfloor of the distances occur at least

2⋅(m+1)−1=2m+1=n+12\cdot(m+1)-1=2m+1=n+1

times. Hence, we get a set of nn points {v1,…,vm+1,v3′,…,vm+1′}\{v_1,\ldots,v_{m+1},v'_3,\ldots,v'_{m+1}\} where ⌊n4⌋\left\lfloor\frac{n}{4}\right\rfloor many of the distances occur at least n+1n+1 times. This concludes Case 2 and proves the theorem.

Proof of Theorem 1.2

Proof of Theorem 1.2. Let n=(m+1)k+rn=(m+1)k+r for some r∈[2,m+2]r\in[2,m+2]. To prove this theorem, we start with a regular (k+2)(k+2)–gon v1…vk+2v_1\ldots v_{k+2}. Fix a vertex, say v1v_1, and take (r−2)(r-2) arbitrarily rotation of the (k+2)(k+2)−gon around v1v_1, resulting in a total of (r−1)(r-1) regular (k+2)(k+2)−gons with a common vertex v1v_1. Now iteratively reflect the (k+2)(k+2)−gon over an edge vi,vi+1v_i,v_{i+1} for some i∈[k]i \in[k], then chose another edge of any the (k+2)(k+2)−gon and reflect again with total of (m+2−r)(m+2-r) times. Hence, the total number of points is

A set of 8 points with 1 distance appearing at least 11 times

Figure 4. A set of 8 points with 1 distance appearing at least 11 times. The diagram consists of two rotations and one reflection of the triangle v1v2v3v_1v_2v_3.

(k+2)+(r−2)(k+1)+(m+2−r)(k)=(m+1)k+r=n.(k+2)+(r-2)(k+1)+(m+2-r)(k)=(m+1)k+r=n.

Observe that from Claim 2.1 ⌊k+12⌋\left\lfloor\frac{k+1}{2} \right\rfloor of the distances repeat k+2k+2 times in each (k+2)(k+2)-gon, with only repetition of one edge for each reflection. Since there are m+2−rm+2-r reflections in total, ⌊k+12⌋\left\lfloor\frac{k+1}{2} \right\rfloor distances appear at least

(k+2)(m+1)−(m+2−r)=[(m+1)k+r]+m=n+m(k+2)(m+1)-(m+2-r)=[(m+1)k+r]+m=n+m

times. Finally, since n=(m+1)k+rn=(m+1)k+r,

⌊k+12⌋≥⌊n2(m+1)⌋,\left\lfloor\frac{k+1}{2} \right\rfloor\geq\left\lfloor\frac{n}{2(m+1)} \right\rfloor,

we conclude that at least ⌊n2(m+1)⌋\left\lfloor\frac{n}{2(m+1)} \right\rfloor of the distances appear more than n+mn+m times. □

Further Research

In [1], this question 1 was mentioned alongside the previously conjectured Erdős’ distinct distance problem [2] from 1946.

Problem (Erdős’ Distinct Distance Problem). Does every set of nn distinct points in R2\mathbb{R}^{2} determine ≫n/log⁡n\gg n/\sqrt{\log n} many distinct distances?

While Erdős’ distinct distance problem was almost settled (with a remaining gap of log⁡n\sqrt{\log n}) by Guth and Katz in 2015 [3]. In the same paper [1] Erdős also mentioned another question of himself and Pach.

Problem (Erdős and Pach). Let A⊂R2A \subset\mathbb{R}^{2} be a set of nn points. Must there be two distances which occur at least once but between at most nn pairs of points?

Pannowitz and Hopf [4] proved that the largest distance between points of AA can occur at most nn times, but it remains unknown whether a second such distance must occur. Erdős and Pach believe that such a distance exists.

Another popular distance problem of Erdős mentioned alongside the distinct distance problem [2] is known as Erdős’ unit distance problem.

Problem (Erdős’ Unit Distance Problem). Does every set of nn distinct points in R2\mathbb{R}^{2} contain at most n1+O(1/log⁡log⁡n)n^{1+O(1/\log\log n)} pairs which are distance 1 apart?

This bound would be best possible as it is achievable for the integer lattice. The best known upper bound is O(n4/3)O(n^{4/3}), due to Spencer, Szemerédi, and Trotter [5].

Acknowledgements

The author was supported by the Austrian Science Fund FWF Project P 34180. I am deeply grateful to Oliver Roche-Newton for his invaluable comments and suggestions. I also thank Alexander Polyanskii and Adam Sheffer for their feedback on an earlier draft of this paper.

References

Johann Radon Institute for Computational and Applied Mathematics, Linz, Austria

Email address: [email protected]

References

  1. [1]Paul Erdős, Some old and new problems in various branches of combinatorics, Discrete Mathematics 165/166 (1997) 227-231.DOI
  2. [2]Paul Erdős, On sets of distances of points, American Mathematical Monthly. 53 (5) (1946): 248–250.
  3. [3]Larry Guth and Nets Hawk Katz, On the Erdős distinct distances problem in the plane, Annals of Mathematics. 181 (1)(2015): 155–190.DOI
  4. [4]H. Hopf and E. Pannwitz, Aufgabe Nr. 167, Jahresbericht d. Deutsch. Math.- Verein. 43 (1934), 114.
  5. [5]Spencer, J. and Szemerédi, E. and Trotter, Jr., W., Unit distances in the Euclidean plane, Graph theory and combinatorics (Cambridge, 1983) (1984), 293-303.

Paper details

vlnc:W_8bs85bpf
Published
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents