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 c ...

, 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 In combinatorics, a (v,k,\lambda) difference set is a subset D of size k of a group G of order v such that every nonidentity element of G can be expressed as a product d_1d_2^ of elements of D in exactly \lambda ways. A difference set D is said to ...

, 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 In geometric measure theory, Falconer's conjecture, named after Kenneth Falconer, is an unsolved problem concerning the sets of Euclidean distances between points in compact d-dimensional spaces. Intuitively, it states that a set of points that is ...

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, o ...

larger than

d/2

, the corresponding distance set has nonzero

Lebesgue measure In measure theory, a branch of mathematics, the Lebesgue measure, named after French mathematician Henri Lebesgue, is the standard way of assigning a measure to subsets of ''n''-dimensional Euclidean space. For ''n'' = 1, 2, or 3, it coincides ...

. Although partial results are known, the conjecture remains unproven. *The Erdős–Ulam problem 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 ...

in the

Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions ...

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 ra ...

s. Again, it remains unsolved. * Fermat's theorem on sums of two squares 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 gri ...

: 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 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_3 ...

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 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 and

Nets Katz Nets Hawk Katz is the IBM Professor of Mathematics at the California Institute of Technology. He was a professor of Mathematics at Indiana University Bloomington Indiana University Bloomington (IU Bloomington, Indiana University, IU, or simply ...

, 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 is a finite set of points on a line such that no two pairs of points have the same distance. Sophie Piccard 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 sett ...

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 e ...

. 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 Computer vision is an Interdisciplinarity, interdisciplinary scientific field that deals with how computers can gain high-level understanding from digital images or videos. From the perspective of engineering, it seeks to understand and automate t ...

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. ...

, 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 Tra ...

, 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 The Eindhoven University of Technology ( nl, Technische Universiteit Eindhoven), abbr. TU/e, is a public technical university in the Netherlands, located in the city of Eindhoven. In 2020–21, around 14,000 students were enrolled in its BSc ...

, 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 t ...

, 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 '' Israel Journal of Mathematics'' is a peer-reviewed mathematics journal published by the Hebrew University of Jerusalem (Magnes Press). Founded in 1963, as a continuation of the ''Bulletin of the Research Council of Israel'' (Section F), the j ...

, 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

See also

References