Bisectors and Pinned Distances
- PDF / 352,198 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 74 Downloads / 217 Views
Bisectors and Pinned Distances Ben Lund1
· Giorgis Petridis2
Received: 1 October 2018 / Revised: 25 June 2019 / Accepted: 5 August 2019 © Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract We prove, under suitable conditions, a lower bound on the number of pinned distances determined by small subsets of two-dimensional vector spaces over fields. For finite subsets of the Euclidean plane we prove an upper bound for their bisector energy. Keywords Distinct distances · Perpendicular bisectors · Finite fields Mathematics Subject Classification 52C10
1 Introduction A well-known conjecture of Erd˝os [3] is that between the pairs of any N points in R2 occur at least (N log−1/2 (N )) different distances. In 2010, Guth and Katz [7] showed that (N log−1 (N )) distinct distances must occur. Erd˝os also made a refinement of this conjecture. This refinement is that among any set A of N points in R2 , there must occur a point a ∈ A such that the remaining points of A are at (N log−1/2 (N )) different distances from a. This is often called the pinned distances conjecture. The best known bound of (N 0.864... ) was proved by Katz and Tardos [11], who improved an earlier proof by Solymosi and Tóth [16].
Dedicated to the memory of Ricky Pollack. Editor in Charge: János Pach Work on this project by the first author was supported by NSF DMS Grant 1344994 and by NSF DMS Grant 1802787. The second author is supported by the NSF DMS Grant 1723016. Ben Lund [email protected] Giorgis Petridis [email protected] 1
Department of Mathematics, Princeton University, Princeton, NJ 08544, USA
2
Department of Mathematics, University of Georgia, Athens, GA 30602, USA
123
Discrete & Computational Geometry
These problems have also been considered over other fields, particularly finite fields. In general, we define the algebraic distance between two points a, b ∈ F2 to be a − b = (a − b) · (a − b) = (a1 − b1 )2 + (a2 − b2 )2 . The distance number and pinned distance number of A are (A) = |{a − b : a, b ∈ A}|
and
pin (A) = max |{a − b : b ∈ A}|. a∈A
We study pin (A). A simple lower bound of pin (A) = (N 1/2 ) comes from the observation that either some single circle contains N 1/2 points (giving at least 1 1/2 distinct distances from any point in the circle), or there are at least N 1/2 − 1 2N distinct distances from each point. This simple bound is tight over fields of positive characteristic, as can be seen by taking our set of points to be the Cartesian product of the prime subfield. In this case (A) is contained in the prime subfield and hence pin (A) ≤ (A) ≤ N 1/2 . There are two ways of proving a non-trivial pinned distance bound over fields of positive characteristic. You can prove a lower bound that depends on the order of the field, or you can assume that the number of points is small relative to the characteristic of the field. In this paper, we are primarily interested in point sets that are relatively small. The first work on the pinned variant of the distinct distance problem over fi
Data Loading...
