Danzer set

Last updated October 23, 2022

Unsolved problem in mathematics:

Does a Danzer set with bounded density or bounded separation exist?

Density

One way to define the problem more formally is to consider the growth rate of a set $S$ in $d$ -dimensional Euclidean space, defined as the function that maps a real number $r$ to the number of points of $S$ that are within distance $r$ of the origin. Danzer's question is whether it is possible for a Danzer set to have growth rate $O(r^{d})$ , 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]

It is possible to construct a Danzer set of growth rate that is within a polylogarithmic factor of $O(r^{d})$ . For instance, overlaying rectangular grids whose cells have constant volume but differing aspect ratios can achieve a growth rate of $O(n^{d}\log ^{d-1}n)$ .^[3] Constructions for Danzer sets are known with a somewhat slower growth rate, $O(r^{d}\log r)$ , but the answer to Danzer's question remains unknown.^[4]

Bounded coverage

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

Separation

A third 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.^[7] 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 $O(r^{d})$ , 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,^[7]^[8] as part of a set of problems also including Conway's 99-graph problem, the analysis of sylver coinage, and the thrackle conjecture.^[8]

Additional properties

It is also possible to restrict the classes of point sets that may be Danzer sets in other ways than by their densities. In particular, they cannot be the union of finitely many lattices,^[3] they 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 they 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]

Related Research Articles

In elementary geometry, a polytope is a geometric object with flat sides (faces). It is a generalization in any number of dimensions of the three-dimensional polyhedron. Polytopes may exist in any general number of dimensions $n$ as an $n$ -dimensional polytope or $n$ -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. For example, a two-dimensional polygon is a 2-polytope and a three-dimensional polyhedron is a 3-polytope.

<span class="mw-page-title-main">Minkowski's theorem</span> Every symmetric convex set in R^n with volume > 2^n contains a non-zero integer point

In mathematics, Minkowski's theorem is the statement that every convex set in $which is symmetric with respect to the origin and which has volume greater than contains a non-zero integer point. The theorem was proved by Hermann Minkowski in 1889 and became the foundation of the branch of number theory called the geometry of numbers. It can be extended from the integers to any lattice and to any symmetric convex set with volume greater than, where denotes the covolume of the lattice.$

Geometry of numbers is the part of number theory which uses geometry for the study of algebraic numbers. Typically, a ring of algebraic integers is viewed as a lattice in $and the study of these lattices provides fundamental information on algebraic numbers. The geometry of numbers was initiated by Hermann Minkowski (1910).$

<span class="mw-page-title-main">Pick's theorem</span> Formula for area of a grid polygon

In geometry, Pick's theorem provides a formula for the area of a simple polygon with integer vertex coordinates, in terms of the number of integer points within it and on its boundary. The result was first described by Georg Alexander Pick in 1899. It was popularized in English by Hugo Steinhaus in the 1950 edition of his book Mathematical Snapshots. It has multiple proofs, and can be generalized to formulas for certain kinds of non-simple polygons.

In geometry and group theory, a lattice in the real coordinate space $is an infinite set of points in this space with the properties that coordinatewise addition or subtraction of two points in the lattice produces another lattice point, that the lattice points are all separated by some minimum distance, and that every point in the space is within some maximum distance of a lattice point. Closure under addition and subtraction means that a lattice must be a subgroup of the additive group of the points in the space, and the requirements of minimum and maximum distance can be summarized by saying that a lattice is a Delone set. More abstractly, a lattice can be described as a free abelian group of dimension which spans the vector space . For any basis of, the subgroup of all linear combinations with integer coefficients of the basis vectors forms a lattice, and every lattice can be formed from a basis in this way. A lattice may be viewed as a regular tiling of a space by a primitive cell.$

In arithmetic combinatorics, Szemerédi's theorem is a result concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured that every set of integers A with positive natural density contains a k-term arithmetic progression for every k. Endre Szemerédi proved the conjecture in 1975.

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.

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

A double exponential function is a constant raised to the power of an exponential function. The general formula is $(where a >1 and b >1), which grows much more quickly than an exponential function. For example, if a = b = 10:$

A thrackle is an embedding of a graph in the plane, such that each edge is a Jordan arc and every pair of edges meet exactly once. Edges may either meet at a common endpoint, or, if they have no endpoints in common, at a point in their interiors. In the latter case, the crossing must be transverse.

In mathematics, the Gauss circle problem is the problem of determining how many integer lattice points there are in a circle centered at the origin and with radius $. This number is approximated by the area of the circle, so the real problem is to accurately bound the error term describing how the number of points differs from the area. The first progress on a solution was made by Carl Friedrich Gauss, hence its name.$

In geometry and polyhedral combinatorics, an integral polytope is a convex polytope whose vertices all have integer Cartesian coordinates. That is, it is a polytope that equals the convex hull of its integer points. Integral polytopes are also called lattice polytopes or Z-polytopes. The special cases of two- and three-dimensional integral polytopes may be called polygons or polyhedra instead of polytopes, respectively.

<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 a $-dimensional Euclidean space is, achieved by a regular simplex, and the equilateral dimension of a -dimensional vector space with the Chebyshev distance is, achieved by 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 a cross polytope.$

In geometry, Keller's conjecture is the conjecture that in any tiling of $n$ -dimensional Euclidean space by identical hypercubes, there are two hypercubes that share an entire $(n - 1)$ -dimensional face with each other. For instance, in any tiling of the plane by identical squares, some two squares must share an entire edge, as they do in the illustration.

In mathematics, a square-difference-free set is a set of natural numbers, no two of which differ by a square number. Hillel Furstenberg and András Sárközy proved in the late 1970s the Furstenberg–Sárközy theorem of additive number theory showing that, in a certain sense, these sets cannot be very large. In the game of subtract a square, the positions where the next player loses form a square-difference-free set. Another square-difference-free set is obtained by doubling the Moser–de Bruijn sequence.

In combinatorics, tripod packing is a problem of finding many disjoint tripods in a three-dimensional grid, where a tripod is an infinite polycube, the union of the grid cubes along three positive axis-aligned rays with a shared apex.

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.

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 2 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
↑ 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)
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
1 2 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
↑ 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
↑ Solan, Omri; Solomon, Yaar; Weiss, Barak (2017), "On problems of Danzer and Gowers and dynamics on the space of closed subsets of $\mathbb {R} ^{d}$ ", International Mathematics Research Notices (21): 6584–6598, arXiv: 1510.07179 , doi:10.1093/imrn/rnw204, MR 3719473
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
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.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[cfg-1] 1 2 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

[dan-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)

[bw-3] 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

[sw-4] 1 2 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

[g-5] 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

[ssw-6] Solan, Omri; Solomon, Yaar; Weiss, Barak (2017), "On problems of Danzer and Gowers and dynamics on the space of closed subsets of $\mathbb {R} ^{d}$ ", International Mathematics Research Notices (21): 6584–6598, arXiv: 1510.07179 , doi:10.1093/imrn/rnw204, MR 3719473

[r-7] 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

[c-8] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]