Danzer set

Last updated
Unsolved problem in mathematics:
Does a Danzer set with bounded density or bounded separation exist?
Construction of a two-dimensional Danzer set with growth rate
O
(
n
2
log
[?]
n
)
{\displaystyle O(n^{2}\log n)}
from overlaid rectangular grids of aspect ratio 1:1, 1:9, 1:81, etc. Danzer set.svg
Construction of a two-dimensional Danzer set with growth rate from overlaid rectangular grids of aspect ratio 1:1, 1:9, 1:81, etc.

In geometry, a Danzer set is a set of points that touches every convex body of unit volume. Ludwig Danzer asked whether it is possible for such a set to have bounded density. [1] [2] Several variations of this problem remain unsolved. [3]

Contents

Formulation

A Danzer set, in an n-dimensional Euclidean space, is a set of points in the space that has a non-empty intersection with every convex body whose n-dimensional volume is one. The whole space is itself a Danzer set, but it is possible for a Danzer set to be a discrete set with only finitely many points in any bounded area. [4] Danzer's question asked whether, more strongly, the average number of points per unit area could be bounded. [1]

One way to define the problem more formally is to consider the growth rate of a set in -dimensional Euclidean space, defined as the function that maps a real number to the number of points of that are within distance of the origin. Danzer's question is whether it is possible for a Danzer set to have growth rate , expressed in big O notation. If so, this would equal the growth rate of well-spaced point sets like the integer lattice (which is not a Danzer set). [1]

An equivalent formulation involves the density of a set , defined as where denotes the Euclidean ball of radius in -dimensional Euclidean space, centered at the origin, and denotes its volume. Danzer's question asks whether there exists a Danzer set of bounded density or, alternatively, whether every set of bounded density has arbitrarily high-volume convex sets disjoint from it. [3]

Instead of asking for a set of bounded density that intersects arbitrary convex sets of unit volume, it is equivalent to ask for a set of bounded density that intersects all ellipsoids of unit volume, or all hyperrectangles of unit volume. For instance, in the plane, the shapes of these intersecting sets can be restricted to ellipses, or to rectangles. However, these shapes do not necessarily have their sides or axes parallel to the coordinate axes. [3]

Partial results

It is possible to construct a Danzer set of growth rate that is within a polylogarithmic factor of . For instance, overlaying rectangular grids whose cells have constant volume but differing aspect ratios can achieve a growth rate of . [5] A construction for Danzer sets is known with a somewhat slower growth rate, . [3] [4] This construction is based on deep results of Marina Ratner in ergodic theory (Ratner's theorems). [4] Because both the overlaid grids and the improved construction have growth rates faster than , these sets do not have bounded density, and the answer to Danzer's question remains unknown. [3] [4]

Although the existence of a Danzer set of bounded density remains open, it is possible to restrict the classes of point sets that may be Danzer sets in other ways than by their densities, ruling out certain types of solution to Danzer's question. In particular, a Danzer set cannot be the union of finitely many lattices, [5] it cannot be generated by choosing a point in each tile of a substitution tiling (in the same position for each tile of the same type), and it cannot be generated by the cut-and-project method for constructing aperiodic tilings. Therefore, the vertices of the pinwheel tiling and Penrose tiling are not Danzer sets. [4]

Variations

Bounded coverage

A strengthened variation of the problem, posed by Timothy Gowers, asks whether there exists a Danzer set for which there is a finite bound on the number of points of intersection between and any convex body of unit volume. [6] This version has been solved: it is impossible for a Danzer set with this property to exist. [7]

Separation

Another strengthened variation of the problem, still unsolved, is Conway's dead fly problem. John Horton Conway recalled that, as a child, he slept in a room with wallpaper whose flower pattern resembled an array of dead flies, and that he would try to find convex regions that did not have a dead fly in them. [8] In Conway's formulation, the question is whether there exists a Danzer set in which the points of the set (the dead flies) are separated at a bounded distance from each other. Such a set would necessarily also have an upper bound on the distance from each point of the plane to a dead fly (in order to touch all circles of unit area), so it would form a Delone set, a set with both lower and upper bounds on the spacing of the points. It would also necessarily have growth rate , so if it exists then it would also solve the original version of Danzer's problem. Conway offered a $1000 prize for a solution to his problem, [8] [9] as part of a set of problems also including Conway's 99-graph problem, the analysis of sylver coinage, and the thrackle conjecture. [9]

See also

Related Research Articles

<span class="mw-page-title-main">Convex set</span> In geometry, set whose intersection with every line is a single line segment

In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex region is a subset that intersects every line into a single line segment . For example, a solid cube is a convex set, but anything that is hollow or has an indent, for example, a crescent shape, is not convex.

In elementary geometry, a polytope is a geometric object with flat sides (faces). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions n as an n-dimensional polytope or n-polytope. For example, a two-dimensional polygon is a 2-polytope and a three-dimensional polyhedron is a 3-polytope. In this context, "flat sides" means that the sides of a (k + 1)-polytope consist of k-polytopes that may have (k – 1)-polytopes in common.

<span class="mw-page-title-main">Convex hull</span> Smallest convex set containing a given set

In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.

In geometry, the Dehn invariant is a value used to determine whether one polyhedron can be cut into pieces and reassembled ("dissected") into another, and whether a polyhedron or its dissections can tile space. It is named after Max Dehn, who used it to solve Hilbert's third problem by proving that certain polyhedra with equal volume cannot be dissected into each other.

<span class="mw-page-title-main">Arrangement of lines</span> Subdivision of the plane by lines

In geometry, an arrangement of lines is the subdivision of the plane formed by a collection of lines. Problems of counting the features of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.

<span class="mw-page-title-main">Heilbronn triangle problem</span> On point sets with no small-area triangles

In discrete geometry and discrepancy theory, the Heilbronn triangle problem is a problem of placing points in the plane, avoiding triangles of small area. It is named after Hans Heilbronn, who conjectured that, no matter how points are placed in a given area, the smallest triangle area will be at most inversely proportional to the square of the number of points. His conjecture was proven false, but the asymptotic growth rate of the minimum triangle area remains unknown.

<span class="mw-page-title-main">Euclidean minimum spanning tree</span> Shortest network connecting points

A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.

<span class="mw-page-title-main">Convex polytope</span> Convex hull of a finite set of points in a Euclidean space

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.

<span class="mw-page-title-main">Unit distance graph</span> Geometric graph with unit edge lengths

In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.

The Erdős–Anning theorem states that, whenever an infinite number of points in the plane all have integer distances, the points lie on a straight line. The same result holds in higher dimensional Euclidean spaces. The theorem cannot be strengthened to give a finite bound on the number of points: there exist arbitrarily large finite sets of points that are not on a line and have integer distances.

<span class="mw-page-title-main">Hadwiger conjecture (combinatorial geometry)</span>

In combinatorial geometry, the Hadwiger conjecture states that any convex body in n-dimensional Euclidean space can be covered by 2n or fewer smaller bodies homothetic with the original body, and that furthermore, the upper bound of 2n is necessary if and only if the body is a parallelepiped. There also exists an equivalent formulation in terms of the number of floodlights needed to illuminate the body.

In convex geometry, the Mahler volume of a centrally symmetric convex body is a dimensionless quantity that is associated with the body and is invariant under linear transformations. It is named after German-English mathematician Kurt Mahler. It is known that the shapes with the largest possible Mahler volume are the balls and solid ellipsoids; this is now known as the Blaschke–Santaló inequality. The still-unsolved Mahler conjecture states that the minimum possible Mahler volume is attained by a hypercube.

<span class="mw-page-title-main">Equilateral dimension</span> Max number of equidistant points in a metric space

In mathematics, the equilateral dimension of a metric space is the maximum size of any subset of the space whose points are all at equal distances to each other. Equilateral dimension has also been called "metric dimension", but the term "metric dimension" also has many other inequivalent usages. The equilateral dimension of -dimensional Euclidean space is , achieved by the vertices of a regular simplex, and the equilateral dimension of a -dimensional vector space with the Chebyshev distance is , achieved by the vertices of a hypercube. However, the equilateral dimension of a space with the Manhattan distance is not known. Kusner's conjecture, named after Robert B. Kusner, states that it is exactly , achieved by the vertices of a cross polytope.

<span class="mw-page-title-main">Shapley–Folkman lemma</span> Sums of sets of vectors are nearly convex

The Shapley–Folkman lemma is a result in convex geometry that describes the Minkowski addition of sets in a vector space. It is named after mathematicians Lloyd Shapley and Jon Folkman, but was first published by the economist Ross M. Starr.

In geometry, it is an unsolved conjecture of Hugo Hadwiger that every simplex can be dissected into orthoschemes, using a number of orthoschemes bounded by a function of the dimension of the simplex. If true, then more generally every convex polytope could be dissected into orthoschemes.

<span class="mw-page-title-main">Binary tiling</span> Tiling of the hyperbolic plane

In geometry, a binary tiling is a tiling of the hyperbolic plane, resembling a quadtree over the Poincaré half-plane model of the hyperbolic plane. The tiles may be convex pentagons, or they may be shapes with four sides, alternating between line segments and curved arcs.

<span class="mw-page-title-main">Polygonalization</span> Polygon through a set of points

In computational geometry, a polygonalization of a finite set of points in the Euclidean plane is a simple polygon with the given points as its vertices. A polygonalization may also be called a polygonization, simple polygonalization, Hamiltonian polygon, non-crossing Hamiltonian cycle, or crossing-free straight-edge spanning cycle.

<span class="mw-page-title-main">Blichfeldt's theorem</span> High-area shapes can shift to hold many grid points

Blichfeldt's theorem is a mathematical theorem in the geometry of numbers, stating that whenever a bounded set in the Euclidean plane has area , it can be translated so that it includes at least points of the integer lattice. Equivalently, every bounded set of area contains a set of points whose coordinates all differ by integers.

References

  1. 1 2 3 Croft, Hallard T.; Falconer, Kenneth J.; Guy, Richard K. (1991), "E14: Positioning convex sets relative to discrete sets", Unsolved problems in geometry, Problem Books in Mathematics, Springer-Verlag, New York, p.  148, doi:10.1007/978-1-4612-0963-8, ISBN   0-387-97506-3, MR   1107516
  2. Fenchel, Werner (1967), "Problems", Proceedings of the Colloquium on Convexity, Copenhagen, 1965, Copenhagen: Kobenhavns Universitets Matematiske Institut, pp. 308–325, MR   0214420 , Problem 6 (Danzer), as cited by Croft, Falconer & Guy (1991)
  3. 1 2 3 4 5 Adiceam, Faustin (2022), "Around the Danzer problem and the construction of dense forests", L'Enseignement Mathématique, 68 (1–2): 25–60, arXiv: 2010.06756 , doi:10.4171/lem/1020, MR   4420864
  4. 1 2 3 4 5 Solomon, Yaar; Weiss, Barak (2016), "Dense forests and Danzer sets", Annales Scientifiques de l'École Normale Supérieure, 49 (5): 1053–1074, arXiv: 1406.3807 , doi:10.24033/asens.2303, MR   3581810, S2CID   672315
  5. 1 2 Bambah, R. P.; Woods, A. C. (1971), "On a problem of Danzer", Pacific Journal of Mathematics, 37 (2): 295–301, doi: 10.2140/pjm.1971.37.295 , MR   0303419
  6. Gowers, W. T. (2000), "Rough structure and classification", Geometric and Functional Analysis (Special Volume, Part I): 79–117, doi:10.1007/978-3-0346-0422-2_4, ISBN   978-3-0346-0421-5, MR   1826250
  7. Solan, Omri; Solomon, Yaar; Weiss, Barak (2017), "On problems of Danzer and Gowers and dynamics on the space of closed subsets of ", International Mathematics Research Notices (21): 6584–6598, arXiv: 1510.07179 , doi:10.1093/imrn/rnw204, MR   3719473
  8. 1 2 Roberts, Siobhan (2015), Genius at Play: The Curious Mind of John Horton Conway, New York: Bloomsbury Press, p. 382, ISBN   978-1-62040-593-2, MR   3329687
  9. 1 2 Conway, John H., Five $1,000 Problems (Update 2017) (PDF), On-Line Encyclopedia of Integer Sequences , retrieved 2019-02-12. See also OEIS sequenceA248380.