betaFeedback

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−v(i+k)∥\lVert v_i-v_{(i+k)}\rVert and ∥vj−v(j+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. □\square

Proof of Theorem 1.1. For n<4n<4 the statement is vacuously true. Hence, we will assume n≥4n \geq4. 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 an (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

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

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

2⋅(m+1)−1=2m+1=n.(1)2 \cdot(m+1) - 1 = 2m+1 = n. \tag*{(1)}

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.

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 an (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 union of 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

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.

Proof of Theorem 1.2. For n<m+3n < m + 3 the statement is vacuously true hence, we will assume n≥m+3n \ge m + 3. 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) arbitrary rotations 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 a total of (m+2−r)(m+2-r) reflections. Hence, the total number of points is

(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 we have,

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

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

Further Research

In [1], the main problem of this paper was mentioned in the context of 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?

Erdős’ distinct distance problem was almost settled (with a remaining gap of log⁡n\sqrt{\log n}) by Guth and Katz [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?

Pannwitz 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
Version
v2 · latest
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