geometry Geometry (; ) is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures. Geometry is, along with arithmetic, one of the oldest branches of mathematics. A mathematician w ...

, a Danzer set is a set of points that touches every

convex body In mathematics, a convex body in n-dimensional Euclidean space \R^n is a compact convex set with non- empty interior. Some authors do not require a non-empty interior, merely that the set is non-empty. A convex body K is called symmetric if it ...

of unit volume. Ludwig Danzer asked whether it is possible for such a set to have bounded density. Several variations of this problem remain unsolved.

Formulation

A ''Danzer set'', in an -dimensional

Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...

, is a set of points in the space that has a non-empty intersection with every

whose -dimensional

volume Volume is a measure of regions in three-dimensional space. It is often quantified numerically using SI derived units (such as the cubic metre and litre) or by various imperial or US customary units (such as the gallon, quart, cubic inch) ...

is one. The whole space is itself a Danzer set, but it is possible for a Danzer set to be a

discrete set In mathematics, a point (topology), point is called an isolated point of a subset (in a topological space ) if is an element of and there exists a Neighborhood (mathematics), neighborhood of that does not contain any other points of . This i ...

with only finitely many points in any bounded area. Danzer's question asked whether, more strongly, the average number of points per unit area could be bounded. One way to define the problem more formally is to consider the growth rate of a set

S

in 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 Origin(s) or The Origin may refer to: Arts, entertainment, and media Comics and manga * ''Origin'' (comics), a Wolverine comic book mini-series published by Marvel Comics in 2002 * ''The Origin'' (Buffy comic), a 1999 ''Buffy the Vampire Sl ...

. Danzer's question is whether it is possible for a Danzer set to have growth expressed in

big O notation Big ''O'' notation is a mathematical notation that describes the asymptotic analysis, limiting behavior of a function (mathematics), function when the Argument of a function, argument tends towards a particular value or infinity. Big O is a memb ...

. If so, this would equal the growth rate of well-spaced point sets like the

integer lattice In mathematics, the -dimensional integer lattice (or cubic lattice), denoted , is the lattice (group), lattice in the Euclidean space whose lattice points are tuple, -tuples of integers. The two-dimensional integer lattice is also called the s ...

(which is not a Danzer set). An equivalent formulation involves the density of a set

S

, defined as

\limsup_ \frac,

where

B_d(r)

denotes the

Euclidean ball A ball is a round object (usually spherical, but sometimes ovoid) with several uses. It is used in ball games, where the play of the game follows the state of the ball as it is hit, kicked or thrown by players. Balls can also be used for simp ...

of radius

r

in Euclidean space, centered at the origin, and

V_d(r)

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

hyperrectangle In geometry, a hyperrectangle (also called a box, hyperbox, k-cell or orthotopeCoxeter, 1973), is the generalization of a rectangle (a plane figure) and the rectangular cuboid (a solid figure) to higher dimensions. A necessary and sufficient cond ...

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

Partial results

It is possible to construct a Danzer set of growth rate that is within a polylogarithmic factor For instance, overlaying rectangular grids whose cells have constant volume but differing

aspect ratio The aspect ratio of a geometry, geometric shape is the ratio of its sizes in different dimensions. For example, the aspect ratio of a rectangle is the ratio of its longer side to its shorter side—the ratio of width to height, when the rectangl ...

s can achieve a growth rate A construction for Danzer sets is known with a somewhat slower growth rate, This construction is based on deep results of

Marina Ratner Marina Evseevna Ratner (; October 30, 1938 – July 7, 2017) was a professor of mathematics at the University of California, Berkeley who worked in ergodic theory. Around 1990, she proved a group of major theorems concerning unipotent flows on h ...

ergodic theory Ergodic theory is a branch of mathematics that studies statistical properties of deterministic dynamical systems; it is the study of ergodicity. In this context, "statistical properties" refers to properties which are expressed through the behav ...

(

Ratner's theorems In mathematics, Ratner's theorems are a group of major theorems in ergodic theory concerning unipotent flows on homogeneous spaces proved by Marina Ratner around 1990. The theorems grew out of Ratner's earlier work on horocycle flows. The study of ...

). Because both the overlaid grids and the improved construction have growth rates faster than

O(r^d)

, these sets do not have bounded density, and the answer to Danzer's question remains unknown. 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, it cannot be generated by choosing a point in each tile of a

substitution tiling In geometry, a tile substitution is a method for constructing highly ordered Tessellation, tilings. Most importantly, some tile substitutions generate aperiodic tilings, which are tilings whose prototiles do not admit any tiling with translational ...

(in the same position for each tile of the same type), and it cannot be generated by the

cut-and-project method An aperiodic tiling is a non-periodic tiling with the additional property that it does not contain arbitrarily large periodic regions or patches. A set of tile-types (or prototiles) is aperiodic if copies of these tiles can form only non- period ...

for constructing

aperiodic tiling An aperiodic tiling is a non-periodic Tessellation, tiling with the additional property that it does not contain arbitrarily large periodic regions or patches. A set of tile-types (or prototiles) is aperiodic set of prototiles, aperiodic if copie ...

s. Therefore, the vertices of the

pinwheel tiling In geometry Geometry (; ) is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures. Geometry is, along with arithmetic, one of the oldest branches of mathematics. A m ...

and

Penrose tiling A Penrose tiling is an example of an aperiodic tiling. Here, a ''tiling'' is a covering of two-dimensional space, the plane by non-overlapping polygons or other shapes, and a tiling is ''aperiodic'' if it does not contain arbitrarily large Perio ...

are not Danzer sets.

Variations

Bounded coverage

A strengthened variation of the problem, posed by

Timothy Gowers Sir William Timothy Gowers, (; born 20 November 1963) is a British mathematician. He is the holder of the Combinatorics chair at the Collège de France, a director of research at the University of Cambridge and a Fellow of Trinity College, Camb ...

, 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. This version has been solved: it is impossible for a Danzer set with this property to exist.

Separation

Another strengthened variation of the problem, still unsolved, is Conway's dead fly problem.

John Horton Conway John Horton Conway (26 December 1937 – 11 April 2020) was an English mathematician. He was active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He also made contributions to many b ...

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. 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 In the mathematical theory of metric spaces, -nets, -packings, -coverings, uniformly discrete sets, relatively dense sets, and Delone sets (named after Boris Delone) are several closely related definitions of well-spaced sets of points, and ...

, a set with both lower and upper bounds on the spacing of the points. It would also necessarily have growth 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, as part of a set of problems also including Conway's 99-graph problem, the analysis of

sylver coinage Sylver coinage is a mathematical game for two players, invented by John H. Conway. The two players take turns naming positive integers that are not the sum of nonnegative multiples of previously named integers. The player who names 1 loses. For i ...

, and the thrackle conjecture.

References

{{reflist, refs= {{citation , last = Adiceam , first = Faustin , arxiv = 2010.06756 , doi = 10.4171/lem/1020 , issue = 1-2 , journal = L'Enseignement Mathématique , mr = 4420864 , pages = 25–60 , title = Around the Danzer problem and the construction of dense forests , volume = 68 , year = 2022 {{citation , last1 = Bambah , first1 = R. P. , last2 = Woods , first2 = A. C. , journal = Pacific Journal of Mathematics , mr = 0303419 , pages = 295–301 , title = On a problem of Danzer , url = https://projecteuclid.org/euclid.pjm/1102970604 , volume = 37 , year = 1971, issue = 2 , doi = 10.2140/pjm.1971.37.295 , doi-access = free {{citation , last = Conway , first = John H. , author-link = John Horton Conway , accessdate = 2019-02-12 , publisher =

On-Line Encyclopedia of Integer Sequences The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to th ...

, title = Five $1,000 Problems (Update 2017) , url = https://oeis.org/A248380/a248380.pdf. See also {{OEIS el, A248380. {{citation , last1 = Croft , first1 = Hallard T. , last2 = Falconer , first2 = Kenneth J. , author2-link = Kenneth Falconer (mathematician) , last3 = Guy , first3 = Richard K. , author3-link = Richard K. Guy , contribution = E14: Positioning convex sets relative to discrete sets , doi = 10.1007/978-1-4612-0963-8 , isbn = 0-387-97506-3 , mr = 1107516 , page
148
, publisher = Springer-Verlag, New York , series = Problem Books in Mathematics , title = Unsolved problems in geometry , year = 1991 , url = https://archive.org/details/unsolvedproblems0000crof/page/148 {{citation , last = Fenchel , first = Werner , author-link = Werner Fenchel , contribution = Problems , mr = 0214420 , pages = 308–325 , publisher = Kobenhavns Universitets Matematiske Institut , location = Copenhagen , title = Proceedings of the Colloquium on Convexity, Copenhagen, 1965 , year = 1967, Problem 6 (Danzer), as cited by {{harvtxt, Croft, Falconer, Guy, 1991 {{citation , last = Gowers , first = W. T. , authorlink = Timothy Gowers , doi = 10.1007/978-3-0346-0422-2_4 , issue = Special Volume, Part I , journal = Geometric and Functional Analysis , mr = 1826250 , pages = 79–117 , title = Rough structure and classification , year = 2000, isbn = 978-3-0346-0421-5 {{citation , last = Roberts , first = Siobhan , authorlink = Siobhan Roberts , isbn = 978-1-62040-593-2 , location = New York , mr = 3329687 , page = 382 , publisher = Bloomsbury Press , title = Genius at Play: The Curious Mind of John Horton Conway , url = https://books.google.com/books?id=gJssCQAAQBAJ&pg=PA382 , year = 2015 {{citation , last1 = Solan , first1 = Omri , last2 = Solomon , first2 = Yaar , last3 = Weiss , first3 = Barak , doi = 10.1093/imrn/rnw204 , issue = 21 , journal = International Mathematics Research Notices , mr = 3719473 , pages = 6584–6598 , title = On problems of Danzer and Gowers and dynamics on the space of closed subsets of

\mathbb{R}^d

, year = 2017, arxiv = 1510.07179 {{citation , last1 = Solomon , first1 = Yaar , last2 = Weiss , first2 = Barak , arxiv = 1406.3807 , doi = 10.24033/asens.2303 , issue = 5 , journal = Annales Scientifiques de l'École Normale Supérieure , mr = 3581810 , pages = 1053–1074 , title = Dense forests and Danzer sets , volume = 49 , year = 2016, s2cid = 672315 Convex analysis Metric geometry