Distance set
   HOME

TheInfoList



OR:

In
geometry Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is ...
, the distance set of a collection of points is the set of
distance Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...
s between distinct pairs of points. Thus, it can be seen as the generalization of a difference set, the set of distances (and their negations) in collections of numbers. Several problems and results in geometry concern distance sets, usually based on the principle that a large collection of points must have a large distance set (for varying definitions of "large"): * Falconer's conjecture is the statement that, for a collection of points in d-dimensional space that has
Hausdorff dimension In mathematics, Hausdorff dimension is a measure of ''roughness'', or more specifically, fractal dimension, that was first introduced in 1918 by mathematician Felix Hausdorff. For instance, the Hausdorff dimension of a single point is zero, of ...
larger than d/2, the corresponding distance set has nonzero Lebesgue measure. Although partial results are known, the conjecture remains unproven. *The
Erdős–Ulam problem In mathematics, the Erdős–Ulam problem asks whether the plane contains a dense set of points whose Euclidean distances are all rational numbers. It is named after Paul Erdős and Stanislaw Ulam. Large point sets with rational distances The Er ...
asks whether it is possible to have a
dense set In topology and related areas of mathematics, a subset ''A'' of a topological space ''X'' is said to be dense in ''X'' if every point of ''X'' either belongs to ''A'' or else is arbitrarily "close" to a member of ''A'' — for instance, the ra ...
in the Euclidean plane whose distance set consists only of
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all rat ...
s. Again, it remains unsolved. *
Fermat's theorem on sums of two squares In additive number theory, Fermat's theorem on sums of two squares states that an odd prime ''p'' can be expressed as: :p = x^2 + y^2, with ''x'' and ''y'' integers, if and only if :p \equiv 1 \pmod. The prime numbers for which this is true ar ...
characterizes the numbers in the distance set of the two-dimensional
integer lattice In mathematics, the -dimensional integer lattice (or cubic lattice), denoted , is the lattice in the Euclidean space whose lattice points are -tuples of integers. The two-dimensional integer lattice is also called the square lattice, or grid ...
: they are the square roots of integers whose prime factorization does not contain an odd number of copies of any prime congruent to 3 mod 4. Analogously,
Legendre's three-square theorem In mathematics, Legendre's three-square theorem states that a natural number can be represented as the sum of three squares of integers :n = x^2 + y^2 + z^2 if and only if is not of the form n = 4^a(8b + 7) for nonnegative integers and . The ...
characterizes the distance set of the three-dimensional integer lattice, and
Lagrange's four-square theorem Lagrange's four-square theorem, also known as Bachet's conjecture, states that every natural number can be represented as the sum of four integer squares. That is, the squares form an additive basis of order four. p = a_0^2 + a_1^2 + a_2^2 + a_ ...
characterizes the distance set of integer lattices in four and higher dimensions as being the square roots of integers without any additional constraints. In lattices of five or more dimensions, every subset of the lattice with nonzero
upper density In number theory, natural density (also referred to as asymptotic density or arithmetic density) is one method to measure how "large" a subset of the set of natural numbers is. It relies chiefly on the probability of encountering members of the de ...
has a distance set containing the squares of an infinite
arithmetic progression An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...
. *According to the Erdős–Anning theorem, every infinite set of points in the Euclidean plane that does not lie on one line has a non-integer in its distance set. *Square grids of points have distance sets of sublinear size, in contrast to points in
general position In algebraic geometry and computational geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the ''general case'' situation, as opposed to some more special or coincidental cases that are ...
whose distance set is quadratic in size. However, according to the 2015 solution of the
Erdős distinct distances problem In discrete geometry, the Erdős distinct distances problem states that every set of points in the plane has a nearly-linear number of distinct distances. It was posed by Paul Erdős in 1946 and almost proven by Larry Guth and Nets Katz in 2015. ...
by
Larry Guth Lawrence David Guth (born 1977) is a professor of mathematics at the Massachusetts Institute of Technology. Education and career Guth graduated from Yale in 2000, with BS in mathematics. In 2005, he got his PhD in mathematics from the Massach ...
and Nets Katz, the distance set of any finite collection of points in the Euclidean plane is only slightly sublinear, nearly as large as the given collection. In particular, only a finite collection of points can have a finite distance set. *A
Golomb ruler In mathematics, a Golomb ruler is a set of marks at integer positions along a ruler such that no two pairs of marks are the same distance apart. The number of marks on the ruler is its ''order'', and the largest distance between two of its m ...
is a finite set of points on a line such that no two pairs of points have the same distance.
Sophie Piccard Sophie Piccard (1904–1990) was a Russian-Swiss mathematician who became the first female full professor (professor ordinarius) in Switzerland. Her research concerned set theory, group theory, linear algebra, and the history of mathematics.. E ...
claimed that no two Golomb rulers have the same distance sets. The claim is incorrect, but there is only one counterexample, a pair of six-point Golomb rulers with a shared distance set. *The equilateral dimension of a
metric space In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general set ...
is the largest size of a collection of points whose distance set has only a single element. Kusner's conjecture states that the equilateral dimension of a d-dimensional space with the
Manhattan distance A taxicab geometry or a Manhattan geometry is a geometry whose usual distance function or metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the absolute differences of their Cartesian co ...
is exactly 2d, but this remains unproven. *A 2-distance set is a set of points for which the set of distinct mutual distances has cardinality exactly 2. An example of a 2-distance set is the set of vertices of the regular
octahedron In geometry, an octahedron (plural: octahedra, octahedrons) is a polyhedron with eight faces. The term is most commonly used to refer to the regular octahedron, a Platonic solid composed of eight equilateral triangles, four of which meet at ea ...
. There are various results about 2-distance sets, including a classification of all 2-distance sets in dimension 4. Every 2-distance set is an isosceles set, a set in which all triangles are isosceles. As a partial converse, every isosceles set that cannot be decomposed into two perpendicular subspaces is a 2-distance set. Distance sets have also been used as a shape descriptor in computer vision.


See also

*
Distance matrix In mathematics, computer science and especially graph theory, a distance matrix is a square matrix (two-dimensional array) containing the distances, taken pairwise, between the elements of a set. Depending upon the application involved, the ''dist ...


References

{{reflist, refs= {{citation , last1 = Arutyunyants , first1 = G. , last2 = Iosevich , first2 = A. , editor-last = Pach , editor-first = János , editor-link = János Pach , contribution = Falconer conjecture, spherical averages and discrete analogs , doi = 10.1090/conm/342/06127 , mr = 2065249 , pages = 15–24 , publisher = Amer. Math. Soc., Providence, RI , series = Contemp. Math. , title = Towards a Theory of Geometric Graphs , volume = 342 , year = 2004, doi-access = free {{citation , first1 = Norman H. , last1 = Anning , first2 = Paul , last2 = Erdős , authorlink2 = Paul Erdős , title = Integral distances , journal =
Bulletin of the American Mathematical Society The ''Bulletin of the American Mathematical Society'' is a quarterly mathematical journal published by the American Mathematical Society. Scope It publishes surveys on contemporary research topics, written at a level accessible to non-experts. I ...
, volume = 51 , pages = 598–600 , year = 1945 , url = https://www.ams.org/bull/1945-51-08/S0002-9904-1945-08407-9/ , doi = 10.1090/S0002-9904-1945-08407-9 , issue = 8, doi-access = free .
{{citation , last1 = Bekir , first1 = Ahmad , last2 = Golomb , first2 = Solomon W. , author2-link = Solomon W. Golomb , doi = 10.1109/TIT.2007.899468 , issue = 8 , journal =
IEEE Transactions on Information Theory ''IEEE Transactions on Information Theory'' is a monthly peer-reviewed scientific journal published by the IEEE Information Theory Society. It covers information theory and the mathematics of communications. It was established in 1953 as ''IRE Tran ...
, mr = 2400501 , pages = 2864–2867 , title = There are no further counterexamples to S. Piccard's theorem , volume = 53 , year = 2007, s2cid = 16689687
{{citation , last = Blokhuis , first = A. , contribution = Chapter 7: Isosceles point sets , doi = 10.6100/IR53747 , pages = 46–49 , publisher = Eindhoven University of Technology , type = Ph.D. thesis , title = Few-Distance Sets , year = 1983 , zbl = 0516.05017 {{citation , last1 = Guth , first1 = Larry , last2 = Katz , first2 = Nets Hawk , arxiv = 1011.4105 , doi = 10.4007/annals.2015.181.1.2 , issue = 1 , journal =
Annals of Mathematics The ''Annals of Mathematics'' is a mathematical journal published every two months by Princeton University and the Institute for Advanced Study. History The journal was established as ''The Analyst'' in 1874 and with Joel E. Hendricks as the ...
, mr = 3272924 , pages = 155–190 , title = On the Erdős distinct distances problem in the plane , volume = 181 , year = 2015
{{citation , last1 = Grigorescu , first1 = C. , last2 = Petkov , first2 = N. , date = October 2003 , doi = 10.1109/tip.2003.816010 , issue = 10 , journal = IEEE Transactions on Image Processing , pages = 1274–1286 , title = Distance sets for shape filters and shape recognition , volume = 12, pmid = 18237892 , url = https://pure.rug.nl/ws/files/2998573/2003IEEETIPGrigorescuC2.pdf , hdl = 11370/dd4f402f-91b0-47ae-94ec-29428a2d8fb9 , hdl-access = free {{citation , last1 = Koolen , first1 = Jack , last2 = Laurent , first2 = Monique , author2-link = Monique Laurent , last3 = Schrijver , first3 = Alexander , author3-link = Alexander Schrijver , doi = 10.1023/A:1008391712305 , issue = 1 , journal = Designs, Codes and Cryptography , mr = 1801196 , pages = 149–164 , title = Equilateral dimension of the rectilinear space , volume = 21 , year = 2000, s2cid = 9391925 {{citation , last1 = Klee , first1 = Victor , author1-link = Victor Klee , last2 = Wagon , first2 = Stan , author2-link = Stan Wagon , contribution = Problem 10 Does the plane contain a dense rational set? , isbn = 978-0-88385-315-3 , pages = 132–135 , publisher= Cambridge University Press , series = Dolciani mathematical expositions , title = Old and New Unsolved Problems in Plane Geometry and Number Theory , url = https://books.google.com/books?id=tRdoIhHh3moC&pg=PA132 , volume= 11 , year = 1991. {{citation , last = Magyar , first = Ákos , doi = 10.1007/s11856-008-0028-z , doi-access=free , journal = Israel Journal of Mathematics , mr = 2391148 , pages = 251–263 , title = On distance sets of large sets of integer points , volume = 164 , year = 2008, s2cid = 17629304 {{citation , last = Szöllösi , first = Ferenc , editor1-last = Akiyama , editor1-first = Jin , editor1-link = Jin Akiyama , editor2-last = Marcelo , editor2-first = Reginaldo M. , editor3-last = Ruiz , editor3-first = Mari-Jo P. , editor3-link = Mari-Jo P. Ruiz , editor4-last = Uno , editor4-first = Yushi , arxiv = 1806.07861 , contribution = The Two-Distance Sets in Dimension Four , doi = 10.1007/978-3-030-90048-9_2 , mr = 4390269 , pages = 18–27 , publisher = Springer , series = Lecture Notes in Computer Science , title = Discrete and Computational Geometry, Graphs, and Games - 21st Japanese Conference, JCDCGGG 2018, Quezon City, Philippines, September 1-3, 2018, Revised Selected Papers , volume = 13034 , year = 2018 Metric geometry