Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-06T13:32:50.684Z Has data issue: false hasContentIssue false
  • English
  • Français

A COUNTEREXAMPLE TO A CONJECTURE OF LARMAN AND ROGERS ON SETS AVOIDING DISTANCE 1

Part of: Discrete geometry Distance geometry

Published online by Cambridge University Press:  14 May 2019

Fernando Mário de Oliveira Filho  and
Frank Vallentin
Fernando Mário de Oliveira Filho
Affiliation:
Delft Institute of Applied Mathematics, Delft University of Technology, Van Mourik Broekmanweg 6, 2628 XE Delft, The Netherlands email fmario@gmail.com
Frank Vallentin
Affiliation:
Mathematisches Institut, Universität zu Köln, Weyertal 86–90, 50931 Köln, Germany email frank.vallentin@uni-koeln.de

Abstract

For each $n\geqslant 2$ we construct a measurable subset of the unit ball in $\mathbb{R}^{n}$ that does not contain pairs of points at distance 1 and whose volume is greater than $(1/2)^{n}$ times the volume of the unit ball. This disproves a conjecture of Larman and Rogers from 1972.

MSC classification

Primary: 52C10: Erdős problems and related topics of discrete geometry 51K99: None of the above, but in this section

Information

Type
Research Article
Information
Mathematika , Volume 65 , Issue 3 , 2019 , pp. 785 - 787
Copyright
Copyright © University College London 2019 

Larman and Rogers [Reference Larman and Rogers6, Conjecture 1] conjectured: “Suppose that the distance  $1$ is not realized in a closed subset $S$ of a spherical ball $B$ of radius  $1$ . Then the Lebesgue measure of $S$ is less than $(1/2)^{n}$ times the Lebesgue measure of $B$ .” Since an open ball of radius  $1/2$ does not have pairs of points at distance 1, this bound would be tight. Croft, Falconer, and Guy [Reference Croft, Falconer and Guy3, p. 178] comment on the planar case of this conjecture, saying about the optimal set  $S$ (they disregard the requirement that it has to be closed): “Surely it must be a disk of radius  $1/2$ , but this seems hard to prove”.

The following simple construction shows that the conjecture is wrong in all dimensions  $n\geqslant 2$ . Let  $e_{1}=(1,0,\ldots ,0)\in \mathbb{R}^{n}$ and write  $a=(1/6)(1+\sqrt{10})$ . Let

$$\begin{eqnarray}T_{n}=\{x\in \mathbb{R}^{n}:x_{1}>1/2,\Vert x-ae_{1}\Vert <1/2,\Vert x\Vert <1\}\end{eqnarray}$$

and set  $S_{n}=T_{n}\cup -T_{n}$ . The set  $T_{n}$ is the intersection of the open ball of radius  $1/2$ centered at  $ae_{1}$ with the open ball of radius 1 centered at the origin and the open halfspace  $x_{1}>1/2$ . It is easy to see that  $T_{n}$ does not contain pairs of points at distance 1, and hence neither does  $S_{n}$ . This is the counterexample to the conjectureFootnote 1 , as is shown below; see also Figure 1.

Figure 1

The set  $S_{2}$ . The parameter  $a$ is chosen so that  $ae_{1}$ is equidistant to the hyperplane  $x_{1}=1/2$ and the hyperplane that contains the intersection between the spheres  $\Vert x\Vert =1$ and $\Vert x-ae_{1}\Vert =1/2$ ; this choice for  $a$ maximizes the volume of  $T_{n}$ .

The volume of the unit ball  $B_{n}$ is  $v_{n}=\unicode[STIX]{x1D70B}^{n/2}/\unicode[STIX]{x1D6E4}(1+n/2)$ . So

$$\begin{eqnarray}\operatorname{vol}T_{n}=\int _{1/2-a}^{a-1/2}v_{n-1}(1/4-x^{2})^{(n-1)/2}\,dx+\int _{2a-1/2}^{1}v_{n-1}(1-x^{2})^{(n-1)/2}\,dx.\end{eqnarray}$$

This gives  $\operatorname{vol}S_{2}/\text{vol}\,B_{2}=0.2848\ldots$ and  $\operatorname{vol}S_{3}/\text{vol}\,B_{3}=0.1563\ldots .$

Actually, for  $n\geqslant 3$ it suffices to use the lower bound

$$\begin{eqnarray}\operatorname{vol}T_{n}\geqslant \int _{1/2-a}^{a-1/2}v_{n-1}(1/4-x^{2})^{(n-1)/2}\,dx\end{eqnarray}$$

to disprove the conjecture. It is known that the volume of the unit ball is concentrated around the equatorFootnote 2 : if  $n\geqslant 3$ and  $c\geqslant 1$ , then

$$\begin{eqnarray}\frac{\operatorname{vol}\{x\in B_{n}:|x_{1}|\leqslant c/\sqrt{n-1}\}}{\operatorname{vol}B_{n}}\geqslant 1-(2/c)\text{e}^{-c^{2}/2}.\end{eqnarray}$$

From this inequality one gets immediately the asymptotic relation

(1) $$\begin{eqnarray}\frac{\operatorname{vol}S_{n}}{\operatorname{vol}B_{n}}=(2-o(1))(1/2)^{n}>(1/2)^{n}.\end{eqnarray}$$

In other words, in high dimension it is almost possible to fit two balls of radius  $1/2$ inside the unit ball instead of only one as conjectured by Larman and Rogers. Choosing an appropriate constant  $c$ , one shows that  $\operatorname{vol}S_{n}/\text{vol}\,B_{n}>(1/2)^{n}$ for all  $n\geqslant 15$ ; the remaining cases can be checked directly.

One of the original motivations of Larman and Rogers in proposing their conjecture is that it is related to another, still open conjecture of Moser, also popularized by Erdős, on the global behavior of sets avoiding distance 1. This conjecture states that the upper densityFootnote 3 of any measurable subset of  $\mathbb{R}^{2}$ containing no pair of points at distance 1 is less than  $1/4$ ; Larman and Rogers’ conjecture would imply that any such subset of  $\mathbb{R}^{2}$ has upper density at most  $1/4$ . Note that Larman and Rogers’ conjecture, if it were true, still would not imply Moser’s conjecture. Indeed, Larman and Rogers’ conjecture says that a closed subset of the unit disk that avoids distance 1 has area less than  $1/4$ times the area of the unit disk; this in turn implies that the area of a measurable subset of the unit disk that avoids distance 1 is at most  $1/4$ times the area of the unit disk.

The construction of  $S_{n}$ shows that the local behavior resembles the double cap conjecture [Reference Kalai5, Conjecture 2.8], which states that the union of two antipodal spherical caps of radius  $\unicode[STIX]{x1D70B}/4$ each is a maximum-area subset of the unit sphere having no pairs of orthogonal vectors; see DeCorte, Oliveira, and Vallentin [Reference DeCorte, de Oliveira Filho and Vallentin4] for more information on these conjectures.

Footnotes

The second author was partially supported by the SFB/TRR 191 “Symplectic Structures in Geometry, Algebra and Dynamics”, funded by the DFG, and the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie agreement number 764759.

1 Since Larman and Rogers ask for a closed set, take closed inner approximations of  $S_{n}$ .

2 See, for example, Theorem 2.7 in Blum, Hopcroft, and Kannan [Reference Blum, Hopcroft and Kannan2]; Ball [Reference Ball1] and Matoušek [Reference Matoušek7] present analogous results for the sphere instead of the ball.

3 The upper density of a Lebesgue-measurable set  $X\subseteq \mathbb{R}^{n}$ is

$$\begin{eqnarray}\sup _{p\in \mathbb{R}^{n}}\limsup _{T\rightarrow \infty }\frac{\operatorname{vol}(X\cap (p+[-T,T]^{n}))}{\operatorname{vol}[-T,T]^{n}}.\end{eqnarray}$$

Intuitively, it is the fraction of space covered by  $X$ .

References

Ball, K., An elementary introduction to modern convex geometry. In Flavors of Geometry (Mathematical Sciences Research Institute Publications 31 ), Cambridge University Press (Cambridge, 1997), 1–58.Google Scholar
Blum, A., Hopcroft, J. and Kannan, R., Foundations of Data Science, 2018, http://www.cs.cornell.edu/jeh.Google Scholar
Croft, H. T., Falconer, K. J. and Guy, R., Unsolved Problems in Geometry, Springer (New York, 1991).Google Scholar
DeCorte, E., de Oliveira Filho, F. M. and Vallentin, F., Complete positivity and distance-avoiding sets. Preprint, 2018, arXiv:1804:09099.Google Scholar
Kalai, G., Some old and new problems in combinatorial geometry I: around Borsuk’s problem. In Surveys in Combinatorics 2015 (London Mathematical Society Lecture Note Series 424 ), Cambridge University Press (Cambridge, 2015), 147–174.Google Scholar
Larman, D. G. and Rogers, C. A., The realization of distances within sets in Euclidean space. Mathematika 19 1972, 1–24.Google Scholar
Matoušek, J., Lectures on Discrete Geometry (Graduate Texts in Mathematics 212 ), Springer (New York, 2002).Google Scholar
Figure 0

Figure 1 The set $S_{2}$. The parameter $a$ is chosen so that $ae_{1}$ is equidistant to the hyperplane $x_{1}=1/2$ and the hyperplane that contains the intersection between the spheres $\Vert x\Vert =1$ and $\Vert x-ae_{1}\Vert =1/2$; this choice for $a$ maximizes the volume of $T_{n}$.