# On convex holes in $d$-dimensional point sets

Boris Bukh Department of Mathematical Sciences, Carnegie Mellon University,
Pittsburgh, PA 15213, USA. Supported in part by U.S. taxpayers through NSF
CAREER grant DMS-1555149. Email<EMAIL_ADDRESS><EMAIL_ADDRESS>Ting-Wei Chao††footnotemark:  Ron Holzman Department of Mathematics, Technion-
Israel Institute of Technology, 3200003 Haifa, Israel. Work done during a
visit at the Department of Mathematics, Princeton University, supported by the
H2020-MSCA-RISE project CoSP–GA No. 823748. Email<EMAIL_ADDRESS>
###### Abstract

Given a finite set $A\subseteq\mathbb{R}^{d}$, points
$a_{1},a_{2},\dotsc,a_{\ell}\in A$ form an $\ell$-hole in $A$ if they are the
vertices of a convex polytope which contains no points of $A$ in its interior.
We construct arbitrarily large point sets in general position in
$\mathbb{R}^{d}$ having no holes of size $O(4^{d}d\log d)$ or more. This
improves the previously known upper bound of order $d^{d+o(d)}$ due to Valtr.
The basic version of our construction uses a certain type of equidistributed
point sets, originating from numerical analysis, known as $(t,m,s)$-nets or
$(t,s)$-sequences, yielding a bound of $2^{7d}$. The better bound is obtained
using a variant of $(t,m,s)$-nets, obeying a relaxed equidistribution
condition.

##  1 Introduction

A finite set $A\subseteq\mathbb{R}^{d}$ is in _general position_ if any
$k$-dimensional affine subspace of $\mathbb{R}^{d}$, with $k<d$, contains at
most $k+1$ points of $A$. Points $a_{1},a_{2},\dotsc,a_{\ell}\in A$ are in
_convex position_ if they are the vertices of a convex polytope. If that
polytope is empty, i.e., contains no points of $A$ in its interior, the points
$a_{1},a_{2},\dotsc,a_{\ell}$ are said to form an $\ell$-_hole_ in $A$.

A classic result of Erdős and Szekeres [ES35] asserts that for any positive
integer $\ell$, every sufficiently large finite set $A$ in general position in
$\mathbb{R}^{2}$ contains $\ell$ points in convex position. Erdős [Erd75] went
on to ask if one can also guarantee an $\ell$-hole in a large enough
$A\subseteq\mathbb{R}^{2}$ in general position. Harborth [Har78] proved that
one can always find a $5$-hole, while Horton [Hor83] constructed arbitrarily
large sets without any $7$-hole. The remaining case $\ell=6$ turned out to be
more challenging, but was settled in the affirmative by Nicolás [Nic07] and,
independently, Gerken [Ger08].

Another question studied is the asymptotic behavior, as $n\to\infty$, of the
number of $\ell$-holes guaranteed to exist in a set $A$ of $n$ points in
general position in $\mathbb{R}^{2}$. For $\ell=3,4$ this number was shown to
be $\Theta(n^{2})$ by Katchalski and Meir [KM88] and Bárány and Füredi [BF87].
The order of magnitude for $\ell=5,6$ is not known, but very recently
Aichholzer, Balko, Hackl, Kynčl, Parada, Scheucher, Valtr and Vogtenhuber
[ABH+20] proved it is superlinear for $\ell=5$.

Turning to higher dimensions, much less is known. Valtr [Val92] gave a simple
projection argument to extend the Erdős–Szekeres result to any dimension
$d\geq 2$: for every $\ell$, any sufficiently large finite set $A$ in general
position in $\mathbb{R}^{d}$ contains $\ell$ points in convex position.
Regarding holes, he defined:

$h(d)\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}\max\\{\ell:\textrm{any
large enough }A\subseteq\mathbb{R}^{d}\textrm{ in general position contains an
}\ell\textrm{-hole}\\}.$

Using this notation, the $2$-dimensional results recalled above say that
$h(2)=6$. Valtr proved the following bounds for $d\geq 3$:

$2d+1\leq h(d)\leq 2^{d-1}(P(d-1)+1),$

where $P(d-1)$ is the product of the smallest $d-1$ prime numbers (and thus is
asymptotically $d^{d+o(d)}$). For $d=3$ he gave the better upper bound
$h(3)\leq 22$. These remained the best known bounds on $h(d)$ for almost 30
years. In this note, we improve the upper bound to become exponential in $d$.

######  Theorem 1.

For all $d\geq 3$ we have $h(d)<2^{7d}$.

In fact, the upper bound that we get, as explained below, is slightly better,
with the exponent reduced from $7d$ to less than $7d-8\sqrt{\frac{d-2}{3}}$.
For low values of $d$, we get even better bounds, e.g.,

$h(3)\leq 32,\,h(4)\leq 240,\,h(5)\leq 988,\,h(6)\leq 8000,$

which (except for $d=3$) improve upon those of Valtr.

In order to explain the source of our improvement, we recall that,
generalizing Horton’s original $2$-dimensional construction, Valtr constructed
for any $d\geq 2$ arbitrarily large point sets in $\mathbb{R}^{d}$, which he
called $d$-Horton sets, containing no hole of size greater than
$2^{d-1}(P(d-1)+1)$. The key property that he used, and the one responsible
for the superexponential term $P(d-1)$ in the bound, is the following: For two
relatively prime moduli $q_{1}$ and $q_{2}$ and any two residue classes
$r_{1}(\operatorname{mod}q_{1})$ and $r_{2}(\operatorname{mod}q_{2})$, their
intersection is equidistributed in the sense that it contains one of any
$q_{1}q_{2}$ consecutive integers (by the Chinese remainder theorem). We
generalize Horton’s construction in a different way, using another kind of
equidistribution which is “cheaper” to achieve. Instead of recruiting larger
and larger prime factors as the dimension grows, we use the fixed prime $2$.
The relevant notion of equidistribution is captured by the following
definition, due to Sobol’ [Sob67].

######  Definition 2.

Let $t\leq m$ be nonnegative integers, and let $s$ be a positive integer.

A subset $X\subseteq[0,1)^{s}$ is a _$(t,m,s)$ -net_ in base $2$ if $\lvert
X\rvert=2^{m}$ and every dyadic sub-box $B$ of $[0,1)^{s}$ of the form

$B=\prod_{i=1}^{s}\Bigl{[}\frac{b_{i}}{2^{k_{i}}},\frac{b_{i}+1}{2^{k_{i}}}\Bigr{)},$

where $b_{i},k_{i}$ are nonnegative integers, $b_{i}<2^{k_{i}}$, and
$\sum_{i=1}^{s}k_{i}=m-t$, contains exactly $2^{t}$ points of $X$.

For a real number $y\in[0,1]$ let $y=\sum_{j=1}^{\infty}\frac{y_{j}}{2^{j}}$
with $y_{j}\in\\{0,1\\}$ be a binary expansion of $y$, and
$[y]_{m}=\sum_{j=1}^{m}\frac{y_{j}}{2^{j}}$ its length $m$ truncation (which
may depend on the choice of expansion). For $x\in[0,1]^{s}$ we write $[x]_{m}$
for the point in $[0,1]^{s}$ obtained by applying this truncation
coordinatewise.

An infinite sequence $x_{0},x_{1},\ldots$ of points in $[0,1)^{s}$ with
prescribed binary expansions of their coordinates is a _$(t,s)$ -sequence_ in
base $2$ if for every nonnegative integer $a$ and every integer $m>t$, the set
$X_{a,m}\subseteq[0,1]^{s}$ given by

$X_{a,m}=\\{[x_{n}]_{m}:\,a2^{m}\leq n<(a+1)2^{m}\\}$

is a $(t,m,s)$-net in base $2$.

These notions (and their analogs in bases other than $2$) have been studied
intensively in discrepancy theory, with applications to numerical analysis.
The goal is, for a given dimension $s$, to construct $(t,s)$-sequences and
hence $(t,m,s)$-nets with $t$ as small as possible ($t$ is called the quality
parameter, with lower values corresponding to stronger uniformity of the
net/sequence). It has been observed (see e.g. [NX96, Lemma 1]) that the
existence of a $(t,s)$-sequence implies the existence of $(t,m,s+1)$-nets for
all $m>t$. Various constructions have been proposed, the best among them using
global function fields. We will use the following upper bound on the lowest
possible value of $t$.

######  Theorem 3 (Xing and Niederreiter [XN95]).

For every positive integer $s$ there exists a $(t,s)$-sequence in base $2$
with $t\leq 5s-8\sqrt{\frac{s-1}{3}}-3$. Moreover, for infinitely many values
of $s$, there exists a $(t,s)$-sequence in base $2$ with $t<3s$.

These upper bounds are not sharp in general. In particular, for low values of
$s$, better estimates are known (see [NX96, Table III]): e.g.,
$(t,s)$-sequences in base $2$ with $(t,s)=(0,2),(1,3),(1,4),(2,5),\ldots$ have
been constructed (and can be used, as explained below, to get the upper bounds
on $h(d)$ in dimensions $d=3,4,5,6$ stated above). However, as $s$ grows, $t$
must grow linearly in $s$. The strongest known lower bound, due to Schürer
[Sch08], is $t>s-(1+o(1))\log_{2}s$.

Our generalization of Horton’s construction to higher dimensions uses
$(t,m,s)$-nets and is summarized in the following proposition, proved in the
next section.

######  Proposition 4.

Let $d\geq 2$ and let $t\leq m$ be nonnegative integers so that a
$(t,m,d)$-net in base $2$ exists. Then there exists a set $A$ of $2^{m}$
points in general position in $\mathbb{R}^{d}$, having no holes of size
greater than $2^{d}(2^{t+d-1}-2^{t}+1)$.

Together with Theorem 3, and the fact that a $(t,s)$-sequence entails
$(t,m,s+1)$-nets for all $m>t$, this implies the upper bound on $h(d)$ stated
in Theorem 1 (with something to spare). The second part of Theorem 3 shows
that for infinitely many values of $d$, we get an upper bound on $h(d)$ which
is exponentially better than stated in Theorem 1. The specific upper bounds on
$h(d)$ for low values of $d$ stated above follow by plugging in the parameters
of the corresponding known constructions of $(t,s)$-sequences.

### Improvement.

After the original version of the paper was written, we noticed that we may
replace $(t,m,d)$-nets by sets satisfying a weaker condition. For
$0\leq\varepsilon<1$, a non-empty set $X\subseteq[0,1)^{d}$ is a
_$(T,\varepsilon)$ -almost net_ in base $2$ if $\lvert X\rvert=2^{n}T$ for
some natural number $n$ and

$(1-\varepsilon)T\leq\lvert X\cap B\rvert\leq(1+\varepsilon)T$

for every dyadic box $B$ of volume $2^{-n}$. The following is a generalization
of Proposition 4.

######  Proposition 5.

Let $d\geq 2$ and suppose there exists a $(T,\varepsilon)$-almost net in base
$2$ in $[0,1)^{d}$ of size $2^{n}T$. Then there exists a set $A$ of $2^{n}T$
points in general position in $\mathbb{R}^{d}$, having no holes of size
greater than $2^{d}(2^{d-1}(1+\varepsilon)T-(1-\varepsilon)T+1)$.

In [BC21], we construct for every natural number $n$ a $(T,1/3)$-almost net in
base $2$ in $[0,1)^{d}$ of size $2^{n}T$, where $T\leq 900d\log(2d)$. This
implies the following improvement:

######  Theorem 6.

For all sufficiently large $d$ we have $h(d)=O(4^{d}d\log d)$.

##  2 Horton-like constructions

### Geometric idea.

Our construction uses the same basic idea that is used in Horton’s
construction, and in Valtr’s construction. Namely, if $U\subset\mathbb{R}^{d}$
is finite, $v\in\mathbb{R}^{d}$ is arbitrary, and $e\in\mathbb{R}^{d}$ is a
non-zero vector, then from the point of view of $U$, for large values of
$t\in\mathbb{R}_{+}$ the convex hull $\operatorname{conv}(U\cup\\{v+te\\})$ is
almost equal to $\operatorname{conv}(U)+e\mathbb{R}_{+}$, the Minkowski sum of
the set $\operatorname{conv}(U)$ and the ray $e\mathbb{R}_{+}$. The set
$\operatorname{conv}(U)+e\mathbb{R}_{+}$ has two advantages: it is independent
of $v$ and it is geometrically simpler than
$\operatorname{conv}(U\cup\\{v+te\\})$. We extract the desirable properties
into a lemma.

For $U\subset\mathbb{R}^{d}$, we denote by $\operatorname{conv}U$ its convex
hull, by $U^{o}$ its interior, and by $\operatorname{conv}^{o}U$ the interior
of its convex hull. For $e\in\mathbb{R}^{d}$, we write $U+e$ for the translate
of the set $U$ by the vector $e$, and $U-e$ is defined similarly. Given a non-
zero vector $e\in\mathbb{R}^{d}$, we denote by $\overline{p}_{e}$ the
projection of the point $p\in\mathbb{R}^{d}$ on the subspace orthogonal to
$e$. We drop the subscript $e$ when it is clear from the context, and use the
similar notation $\overline{U}$ for the projection of the set $U$.

######  Lemma 7.

Suppose $U,V\subset\mathbb{R}^{d}$ are finite, and $e\in\mathbb{R}^{d}$ is a
non-zero vector. Then there exists a large $t^{*}=t^{*}(U,V)$ with the
following property. For all $U^{\prime}\subseteq U$, $V^{\prime}\subseteq V$,
with $V^{\prime}\neq\emptyset$, for any point $u\in U$, and every $t\geq
t^{*}$ we have:

  1. (a)

if $u\in(\operatorname{conv}(U^{\prime})+e\mathbb{R}_{+})^{o}$ then
$u\in\operatorname{conv}^{o}\bigl{(}U^{\prime}\cup(V^{\prime}+te)\bigr{)}$,
and

  2. (b)

if $\overline{u}\in\operatorname{conv}^{o}\overline{U^{\prime}\cup
V^{\prime}}$ then
$u\in\bigl{(}\operatorname{conv}\bigl{(}U^{\prime}\cup(V^{\prime}+te)\bigr{)}-e\mathbb{R}_{+}\bigr{)}^{o}$.

Part (a) of the lemma is illustrated in the figure below. As the lemma is
intuitively plausible, we defer its proof to the end of this section.

$\scriptstyle u$$e$Figure 1: The set $U$ is on the left, the set $V+te$ is on
the right.The black points are the elements of $U^{\prime}$ and
$V^{\prime}+te$ respectively.The convex hull of
$U^{\prime}\cup(V^{\prime}+te)$ is in gray.

We will use the following consequence of Lemma 7.

######  Lemma 8.

Suppose $U,V,W\subset\mathbb{R}^{d}$ are finite, and $e\in\mathbb{R}^{d}$ is a
non-zero vector. Let $t\geq t^{*}(U,V)$, and $t^{\prime}\geq
t^{*}\bigl{(}U\cup(V+te),W\bigr{)}$ with $t^{*}$ as in Lemma 7. Assume that
$S\subseteq U\cup(V+te)$ and $u\in U$ satisfy

  * •

the intersection $S\cap(V+te)$ is non-empty, and

  * •

$\overline{u}\in\operatorname{conv}^{o}\overline{S}$.

Then $u\in\operatorname{conv}^{o}(S\cup\\{w\\})$ for every $w\in
W-t^{\prime}e$.

Like the proof of Lemma 7, we defer the proof of the preceding lemma to the
end of the section.

We apply the construction in Lemma 7 repeatedly. We start with the one-element
set containing the origin. At each step, we choose a direction $e$ and replace
the previously constructed set $U$ by $U\cup(U+te)$ for suitably large $t$.
The directions are chosen among the standard basis vectors as follows: for the
first $m$ steps we choose $e_{1}$ and apply the lemma relative to
$\mathbb{R}^{1}$, for the next $m$ steps we choose $e_{2}$ and apply the lemma
relative to $\mathbb{R}^{2}$, and so forth, ending with $m$ steps when we
choose $e_{d}$ and work in $\mathbb{R}^{d}$. Each point of the resulting set
is of the form

$P(\mathbf{a})\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\sum_{\begin{subarray}{c}i\in[d]\\\
j\in[m]\end{subarray}}a^{i}_{j}t_{i,j}e_{i},$

where $\mathbf{a}=(a^{1},a^{2},\dotsc,a^{d})\in(\\{0,1\\}^{m})^{d}$, and

$0\ll t_{1,m}\ll t_{1,m-1}\ll\dotsb\ll t_{1,1}\ll t_{2,m}\ll
t_{2,m-1}\ll\dotsb\ll t_{2,1}\ll\dotsb\dotsb\ll t_{d,m}\ll
t_{d,m-1}\ll\dotsb\ll t_{d,1}$

with the meaning of $\ll$ being supplied iteratively by Lemma 7. Note that we
chose to parameterize the points so that the last entry of $a^{i}$ corresponds
to the first step of the construction in direction $e_{i}$, etc. We may also
assume that each next $t_{i,j}$ is at least double the preceding one. This way
the order between the $i$’th coordinate values of two points $P(\mathbf{a})$
and $P(\mathbf{b})$ is determined by the lexicographic order between $a^{i}$
and $b^{i}$. Our Horton-like construction will consist of appropriately chosen
points of the form $P(\cdot)$.

### Good sets.

We next describe a sufficient condition on a set
$Y\subseteq(\\{0,1\\}^{m})^{d}$ that ensures the absence of large holes in
$P(Y)$.

We call $a\in\\{0,1\\}^{k}$ _a binary sequence of length $k$_ and write
$k=\operatorname{len}a$. We denote the concatenation of sequences $a$ and $b$
by $ab$. We write $a\preceq b$ if $a$ is a prefix of $b$. For
$a\in\\{0,1\\}^{k}$, we denote by $\hat{a}$ the sequence of length $k-1$
obtained from $a$ by removing the last element.

######  Definition 9.

We say that a set $Y\subseteq(\\{0,1\\}^{m})^{d}$ is _$q$ -good_ if every pair
of distinct points $\mathbf{x},\mathbf{y}\in Y$ satisfies $x^{i}\neq y^{i}$
for all $i\in[d]$, and the following holds true. For every $d-1$ binary
sequences $a^{2},\dotsc,a^{d}$ (possibly of different lengths) and every
$(q+1)$-element set $Z\subseteq Y$ obeying the condition

  1. (C)

for each $i\in\\{2,3,\dotsc,d\\}$, all $\mathbf{z}\in Z$ satisfy
$\hat{a}^{i}\preceq z^{i}$,

there is $\mathbf{y}\in Y$ such that $a^{i}\preceq y^{i}$ for all
$i\in\\{2,3,\dotsc,d\\}$ and $\min\\{z^{1}:\mathbf{z}\in
Z\\}<y^{1}<\max\\{z^{1}:\mathbf{z}\in Z\\}$ in the lexicographic order.

We shall see below that any $(T,\varepsilon)$-almost net in base $2$ can be
turned into a $(2^{d}(1+\varepsilon)T-2(1-\varepsilon)T+2)$-good set. In
particular, since a $(t,m,d)$-net in base $2$ is also a $(2^{t},0)$-almost net
in base $2$, any $(t,m,d)$-net in base $2$ can be turned into a
$(2^{t+d}-2^{t+1}+2)$-good set.

######  Definition 10.

Given a finite set of points $V\subseteq\mathbb{R}^{d}$, we say that $V$ is
_$\ell$ -hole-free_ if for any $\ell$ points $v_{1},v_{2},...,v_{\ell}\in V$,
there is a point $v\in V$ in the interior of
$\operatorname{conv}\\{v_{1},v_{2},...,v_{\ell}\\}$.

If the set $V$ is in general position, the definition agrees with the usual
definition of a set without $\ell$-holes. The advantage of this definition is
its robustness: every sufficiently small perturbation of an $\ell$-hole-free
set, which is not necessarily in general position, is again $\ell$-hole-free.

######  Theorem 11.

Let $d\geq 2$, $m$ and $q$ be positive integers, and suppose that
$Y\subseteq(\\{0,1\\}^{m})^{d}$ is $q$-good. Then the set $P(Y)$ is
$(2^{d-1}q+1)$-hole-free.

By the remark following Definition 10, we do not need to worry about general
position. So, Theorem 11 gives us a purely combinatorial way to construct
$\ell$-hole-free sets.

###### Proof of Theorem 11.

Let $U\subseteq Y$ be an arbitrary set of size $|U|>2^{d-1}q$. We must show
that there is a $\mathbf{y}\in Y$ such that
$P(\mathbf{y})\in\operatorname{conv}^{o}P(U)$.

We shall define sets $U_{d}\supseteq U_{d-1}\supseteq
U_{d-2}\supseteq\dotsb\supseteq U_{1}$ and binary sequences
$a^{d},a^{d-1},\ldots,a^{2}$ inductively. We begin by setting
$U_{d}\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}U$. Suppose $i>1$ and
$U_{i}$ has been defined. Denote by $U_{i}^{i}$ the set
$\\{x^{i}:\mathbf{x}\in U_{i}\\}$. Let $b^{i}$ be the longest binary sequence
that is a prefix of all elements of $U_{i}^{i}$, and let $\alpha_{i}$ be an
element of $\\{0,1\\}$ which maximizes the size of

$U_{i-1}\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}\\{\mathbf{x}\in
U_{i}:b^{i}\,\alpha_{i}\preceq x^{i}\\};$

in case of a tie, we pick $\alpha_{i}$ arbitrarily. Note that $\lvert
U_{i-1}\rvert\geq\lvert U_{i}\rvert/2$. Let
$\beta_{i}\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}1-\alpha_{i}$. We then
set $c^{i}$ to be the longest sequence such that $b^{i}\,\alpha_{i}\,c^{i}$ is
a prefix of all elements of $U_{i-1}^{i}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\\{x^{i}:\mathbf{x}\in U_{i-1}\\}$ and define

$a^{i}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}b^{i}\,\alpha_{i}\,c^{i}\,\beta_{i}.$

It is clear that $a^{i}$ satisfies (C) for $Z=U_{i-1}$.

This way we obtain a nested sequence $U_{1}\subseteq
U_{2}\subseteq\dotsb\subseteq U_{d}$ with $\lvert U_{1}\rvert>q$. Since $Y$ is
$q$-good, and $a^{2},\dotsc,a^{d}$ and $U_{1}$ satisfy condition (C) in
Definition 9, there exist $\mathbf{y}\in Y$,
$\mathbf{x}_{\text{small}},\mathbf{x}_{\text{big}}\in U_{1}$ satisfying
$a^{i}\preceq y^{i}$ for all $i\in\\{2,3,\dotsc,d\\}$ as well as
$x_{\text{small}}^{1}<y^{1}<x_{\text{big}}^{1}$ (in the lexicographic
ordering). We claim that $P(\mathbf{y})\in\operatorname{conv}^{o}P(U)$.

To prove this claim, we will show by induction on $i=1,2,\dotsc,d$ that

$\pi_{i}(P(\mathbf{y}))\in\operatorname{conv}^{o}\pi_{i}(P(U_{i})),$

where $\pi_{i}\colon\mathbb{R}^{d}\to\mathbb{R}^{i}$ is the projection map
onto the first $i$ coordinates. The base case $i=1$ holds because of
$x_{\text{small}}^{1}<y^{1}<x_{\text{big}}^{1}$. Suppose that $i>1$. There are
two (similar) cases depending on the value of $\alpha_{i}$. Suppose first that
$\alpha_{i}=1$. We apply Lemma 8 in $\mathbb{R}^{i}$ using the vector $e_{i}$,
with

$\displaystyle\\{\pi_{i}(P(\mathbf{x})):b^{i}\,1\,c^{i}\,1\preceq x^{i},\
\mathbf{x}\in(\\{0,1\\}^{m})^{d}\\}$ $\displaystyle\text{ in place of }V+te,$
$\displaystyle\\{\pi_{i}(P(\mathbf{x})):b^{i}\,1\,c^{i}\,0\preceq x^{i},\
\mathbf{x}\in(\\{0,1\\}^{m})^{d}\\}$ $\displaystyle\text{ in place of }U,$
$\displaystyle\\{\pi_{i}(P(\mathbf{x})):b^{i}\,0\,\phantom{c^{i}\,1}\preceq
x^{i},\ \mathbf{x}\in(\\{0,1\\}^{m})^{d}\\}$ $\displaystyle\text{ in place of
}W-t^{\prime}e,$

and with $S=\pi_{i}(P(U_{i-1}))$, $u=\pi_{i}(P(\mathbf{y}))$, and
$w=\pi_{i}(P(\mathbf{x}))$ for some $\mathbf{x}\in U_{i}$ such that
$b^{i}\,0\preceq x^{i}$ (such $\mathbf{x}$ exists by the maximality of
$b^{i}$). Note that $S\cap(V+te)$ is non-empty by the maximality of $c^{i}$,
and $\overline{u}\in\operatorname{conv}^{o}\overline{S}$ holds by the
induction hypothesis. Therefore we deduce from Lemma 8 that
$u\in\operatorname{conv}^{o}(S\cup\\{w\\})\subseteq\operatorname{conv}^{o}\pi_{i}(P(U_{i}))$,
as required. The case when $\alpha_{i}=0$ is treated similarly by exchanging
the roles of $0$’s and $1$’s, and replacing the vector $e_{i}$ by $-e_{i}$. ∎

### Good sets from $(T,\varepsilon)$-almost nets.

Here we show how to transform a $(T,\varepsilon)$-almost net
$X\subseteq[0,1)^{d}$ of size $2^{n}T$ into a good set
$Y\subseteq(\\{0,1\\}^{m})^{d}$ for $m=n+\lceil\log_{2}T\rceil+1$. Fix
$i\in[d]$. For $x=(x_{1},\dotsc,x_{d})\in X$, let $y_{i}$ be the unique
nonnegative integer such that $y_{i}\leq x_{i}2^{m}<y_{i}+1$. Let
$\widetilde{y}_{i}\in\\{0,1\\}^{m}$ be the $m$-digit binary representation of
$y_{i}$. Applying the definition of a $(T,\varepsilon)$-almost net to the sub-
boxes of the form
$B=[0,1)^{i-1}\times[\frac{b}{2^{n}},\frac{b+1}{2^{n}})\times[0,1)^{d-i}$, we
know that there are between $(1-\varepsilon)T$ and $(1+\varepsilon)T$ points
$x$ in $X$ for which the corresponding $\widetilde{y}_{i}$ has any given
prefix of length $n$. By suitably changing, if necessary, the last
$\lceil\log_{2}T\rceil+1$ entries of $\widetilde{y}_{i}$ we obtain
$y^{i}\in\\{0,1\\}^{m}$ so that the mapping $x\mapsto y^{i}$ is injective.
Doing this for each $i\in[d]$, we transform every $x$ in $X$ into a
$\mathbf{y}=(y^{1},y^{2},\dotsc,y^{d})$ in $(\\{0,1\\}^{m})^{d}$, so that the
resulting set $Y\subseteq(\\{0,1\\}^{m})^{d}$ satisfies the requirement in
Definition 9 that its elements should differ for all $i\in[d]$. Moreover, the
definition of a $(T,\varepsilon)$-almost net implies that for any $d$ binary
sequences $a^{1},a^{2},\dotsc,a^{d}$ with
$\sum_{i=1}^{d}\operatorname{len}a^{i}=k\leq n$, the set

$I(a^{1},a^{2},\dotsc,a^{d})\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\\{\mathbf{y}\in Y:a^{i}\preceq y^{i}\text{ for all }i\in[d]\\}$

has size between $2^{n-k}(1-\varepsilon)T$ and $2^{n-k}(1+\varepsilon)T$. We
call such a set $Y$ a _binary $(T,\varepsilon)$-almost net_ of size $2^{n}T$.

The next result, together with Theorem 11, implies Proposition 5, which was
announced in the introduction, and hence Theorem 6. The case $\varepsilon=0$
yields Proposition 4, and hence Theorem 1.

######  Proposition 12.

If $Y\subseteq(\\{0,1\\}^{m})^{d}$ is a binary $(T,\varepsilon)$-almost net
then $Y$ is $\lfloor 2^{d}(1+\varepsilon)T-2(1-\varepsilon)T+2\rfloor$-good.

###### Proof.

Suppose that the binary sequences $a^{2},\dotsc,a^{d}$ and the set $Z\subseteq
Y$ with size $|Z|>2^{d}(1+\varepsilon)T-2(1-\varepsilon)T+2$ satisfy condition
(C) in Definition 9. By condition (C) we have, using the notation introduced
above, $Z\subseteq I(\emptyset,\hat{a}^{2},\dotsc,\hat{a}^{d})$. As
$|Z|>2^{d-1}(1+\varepsilon)T$ and
$|I(\emptyset,\hat{a}^{2},\dotsc,\hat{a}^{d})|\leq(1+\varepsilon)T\max(1,2^{n-\sum_{i=2}^{d}\operatorname{len}\hat{a}^{i}})$,
we conclude that $d-1<n-\sum_{i=2}^{d}\operatorname{len}\hat{a}^{i}$ and hence
$\sum_{i=2}^{d}\operatorname{len}a^{i}=\sum_{i=2}^{d}\operatorname{len}\hat{a}^{i}+d-1<n$.
Thus the quantity $r\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}\nobreak
n-\sum_{i=2}^{d}\operatorname{len}a^{i}$ is positive. Given a sequence
$a\in\\{0,1\\}^{r}$, consider the sets $B(a)\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}I(a,a^{2},\dotsc,a^{d})$ and
$\hat{B}(a)\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}I(a,\hat{a}^{2},\dotsc,\hat{a}^{d})$. From the discussion above we
know that $\lvert B(a)\rvert\geq(1-\varepsilon)T$ and
$\lvert\hat{B}(a)\rvert\leq 2^{d-1}(1+\varepsilon)T$ for every
$a\in\\{0,1\\}^{r}$. From condition (C) we know also that
$Z\subseteq\bigcup_{a\in\\{0,1\\}^{r}}\hat{B}(a)$.

Our aim is to find $\mathbf{y}\in Y$ that is contained in some $B(a)$ and
whose first coordinate is sandwiched between the first coordinates of two
elements in $Z$.

Suppose first that $Z\cap\hat{B}(a)$ is non-empty for three (or more) distinct
sequences $a\in\\{0,1\\}^{r}$, say for $a^{(1)},a^{(2)},a^{(3)}$. We may
assume that, of the three, $a^{(1)}$ is the lexicographically smallest and
$a^{(3)}$ is the lexicographically largest. Then we may pick $\mathbf{y}$ to
be any element of $B(a^{(2)})$, for its first coordinate is between those of
elements in $Z\cap\hat{B}(a^{(1)})$ and in $Z\cap\hat{B}(a^{(3)})$.

So, we may assume that $Z$ is entirely contained in
$\hat{B}(a)\cup\hat{B}(a^{\prime})$ for some pair
$a,a^{\prime}\in\\{0,1\\}^{r}$. Then either $\hat{B}(a)$ or
$\hat{B}(a^{\prime})$ contains more than
$2^{d-1}(1+\varepsilon)T-(1-\varepsilon)T+1$ elements of $Z$. By size
considerations, at least $2$ of them must be in the respective $B(\cdot)$-set,
and at most one of the $2$ is extremal in $Z$, so choosing the other one as
our $\mathbf{y}$ works. ∎

### Proofs of the geometrical lemmas.

It remains to prove Lemmas 7 and 8.

###### Proof of Lemma 7.

Because there are only finitely many subset pairs $(U^{\prime},V^{\prime})$
and points $u\in U$, it suffices to prove the assertion for any one such
choice. We may then pick the largest $t^{*}$ over all choices of
$(U^{\prime},V^{\prime})$ and $u$.

Proof of part (a). Pick $v\in V^{\prime}$ arbitrarily. Let
$u\in(\operatorname{conv}(U^{\prime})+e\mathbb{R}_{+})^{o}$ be arbitrary. Let
$B(u,\varepsilon)$, with $\varepsilon>0$, be a closed ball around $u$ that is
contained in $\operatorname{conv}(U^{\prime})+e\mathbb{R}_{+}$.

Assume, for contradiction’s sake, that
$u\notin\operatorname{conv}^{o}(U^{\prime}\cup\\{v+te\\})$. Then there is a
hyperplane through $u$ such that the convex set
$\operatorname{conv}(U^{\prime}\cup\\{v+te\\})$ lies entirely on one of its
sides. Pick a unit normal vector $w$ to this hyperplane, such that the
halfspace $H\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}\\{x:\langle
w,x-u\rangle>0\\}$ does not meet
$\operatorname{conv}(U^{\prime}\cup\\{v+te\\})$. Consider the point
$\widetilde{u}\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}u+\varepsilon w$,
and note that $\widetilde{u}\in H$.

Since $\operatorname{dist}(u,\widetilde{u})=\varepsilon$, it follows that
$\widetilde{u}\in\operatorname{conv}(U^{\prime})+e\mathbb{R}_{+}$, and so we
may write $\widetilde{u}=u_{0}+et_{0}$ with
$u_{0}\in\operatorname{conv}U^{\prime}$ and $t_{0}\in\mathbb{R}_{+}$. Define
points $p\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\frac{t_{0}}{t_{0}-t}v+\frac{t}{t-t_{0}}u_{0}$ and
$u^{\prime}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}(t_{0}/t)(v+te)+(1-t_{0}/t)u_{0}$. We may pick $t^{*}$ large enough
so that $\operatorname{dist}(p,u_{0})<\varepsilon$ for $t\geq t^{*}$. Since
$\widetilde{u}=(t_{0}/t)(v+te)+(1-t_{0}/t)p$, it then follows that
$\operatorname{dist}(\widetilde{u},u^{\prime})<\varepsilon$, and hence
$u^{\prime}\in H$. Since
$u^{\prime}\in\operatorname{conv}(U^{\prime}\cup\\{v+te\\})$, this contradicts
the definition of $H$.

Proof of part (b). We first note that it suffices to show that
$u\in\operatorname{conv}\bigl{(}U^{\prime}\cup(V^{\prime}+te)\bigr{)}-e\mathbb{R}_{+}$,
for we may then apply this to all points in a sufficiently small neighborhood
of $u$ to conclude that in fact
$u\in\bigl{(}\operatorname{conv}\bigl{(}U^{\prime}\cup(V^{\prime}+te)\bigr{)}-e\mathbb{R}_{+}\bigr{)}^{o}$.

As $\overline{u}$ is in the interior of
$\operatorname{conv}\overline{U^{\prime}\cup V^{\prime}}$, we may write it as
a convex combination, in which the coefficients of every point in
$\overline{U^{\prime}}$ and of every point in $\overline{V^{\prime}}$ are non-
zero. Indeed, for sufficiently small $\varepsilon>0$, the point
$\overline{u}_{\varepsilon}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}(1+\varepsilon)\overline{u}-\frac{\varepsilon}{\lvert
U^{\prime}\rvert+\lvert V^{\prime}\rvert}\sum_{u^{\prime}\in
U^{\prime}}\overline{u\raisebox{-2.0pt}{${}^{\prime}$}}-\frac{\varepsilon}{\lvert
U^{\prime}\rvert+\lvert V^{\prime}\rvert}\sum_{v^{\prime}\in
U^{\prime}}\overline{v\raisebox{-2.0pt}{${}^{\prime}$}}$ is in
$\operatorname{conv}\overline{U^{\prime}\cup V^{\prime}}$. Writing
$\overline{u}_{\varepsilon}$ as a convex combination of the points in
$\overline{U^{\prime}\cup V^{\prime}}$, and rearranging, we obtain an
expression for $\overline{u}$ as a convex combination with strictly positive
coefficients.

Fix such a convex combination, say $\overline{u}=\sum_{u^{\prime}\in
U^{\prime}}\alpha_{u^{\prime}}\overline{u\raisebox{-2.0pt}{${}^{\prime}$}}+\sum_{v^{\prime}\in
V^{\prime}}\beta_{v^{\prime}}\overline{v\raisebox{-2.0pt}{${}^{\prime}$}}$.
Since the $\beta$’s are positive, we may choose $t^{*}$ large enough so that
for $t\geq t^{*}$, the convex combination $\sum_{u^{\prime}\in
U^{\prime}}\alpha_{u^{\prime}}u^{\prime}+\sum_{v^{\prime}\in
V^{\prime}}\beta_{v^{\prime}}(v^{\prime}+te)$ is above $u$ in the direction
$e$, and so
$u\in\operatorname{conv}\bigl{(}U^{\prime}\cup(V^{\prime}+te)\bigr{)}-e\mathbb{R}_{+}$.
∎

###### Proof of Lemma 8.

From Lemma 7(b) applied to the sets $U^{\prime}=S\cap U$ and
$V^{\prime}=(S-te)\cap V$, using
$\overline{u}\in\operatorname{conv}^{o}\overline{S}$ we deduce that
$u\in(\operatorname{conv}S-e\mathbb{R}_{+})^{o}$ (note that
$V^{\prime}\neq\emptyset$ because $S\cap(V+te)$ is non-empty). Then, from
Lemma 7(a) applied to the sets $U\cup(V+te)$ and $W$ in place of $U$ and $V$,
the direction $-e$ in place of $e$, with $U^{\prime}=S$ and
$V^{\prime}=\\{w+t^{\prime}e\\}$, we obtain the desired conclusion. ∎

##  3 Problems and remarks

  * •

We suspect that every large enough set in general position in $\mathbb{R}^{d}$
contains an exponentially large hole. However, we were unable to improve
Valtr’s bound $h(d)\geq 2d+1$. We do have an argument (details omitted)
showing that constructions along the lines of Horton’s, Valtr’s and ours
cannot avoid exponentially large holes: if a set in $\mathbb{R}^{d}$ consists
of points of the form $P(\mathbf{a})$ and is large enough, then it contains a
hole of size $2^{d}$.

  * •

Let $f_{d,\ell}(n)$ be the least number of $\ell$-holes in an $n$-point set in
general position in $\mathbb{R}^{d}$. It is possible to give lower bounds on
$f_{d,\ell}(n)$. First, for $\ell\leq h(d)$, we may cut the $n$-point set into
linearly-many equally large pieces by parallel hyperplanes. If each piece is
large enough, then it contains an $\ell$-hole, and so
$f_{d,\ell}(n)=\Omega(n)$ in this case.

Second, $f_{d+1,\ell+1}(n+1)\geq\frac{n+1}{\ell+1}\cdot f_{d,\ell}(\lceil
n/2\rceil)$ holds. Indeed, suppose $P\subset\mathbb{R}^{d+1}$ is in general
position and $p\in P$ is arbitrary. Pick any hyperplane that passes only
through $p$, and push it slightly towards the side containing more points of
$P$. Consider the central projection towards $p$ to the hyperplane of points
on this larger side; we may think of it as a set in $\mathbb{R}^{d}$. Every
$\ell$-hole in this set entails an $(\ell+1)$-hole in $P$. As an
$(\ell+1)$-hole arises in this manner at most $\ell+1$ times, the bound
follows.

Taken together with the known lower bounds on $f_{2,\ell}(n)$ and with the
aforementioned bound of Valtr, these two observations yield
$f_{d,\ell}(n)=\Omega(n^{d})$ for $\ell=d+1,d+2$,
$f_{d,d+3}(n)=\Omega(n^{d-1}\log^{4/5}n)$, $f_{d,d+4}(n)=\Omega(n^{d-1})$, and
$f_{d,d+k}(n)=\Omega(n^{d-k+2})$ for $k=5,\dotsc,d+1$.

  * •

It would be interesting to characterize large sets that contain no holes of
some fixed size. In this connection we conjecture that, for each
$n,\ell\in\mathbb{N}$, every sufficiently large $\ell$-hole-free set in
general position in $\mathbb{R}^{2}$ contains an $n$-point subset whose order
type is the same as that of an $n$-point Horton set.

## References

  * [ABH+20] Oswin Aichholzer, Martin Balko, Thomas Hackl, Jan Kynčl, Irene Parada, Manfred Scheucher, Pavel Valtr, and Birgit Vogtenhuber.  A superlinear lower bound on the number of $5$-holes.  J. Combin. Theory Ser. A, 173:105236, 31, 2020.  arXiv:1703.05253.
  * [BC21] Boris Bukh and Ting-Wei Chao.  Digital almost nets.  arXiv:2102.12872, 2021.
  * [BF87] Imre Bárány and Zoltán Füredi.  Empty simplices in Euclidean space.  Canad. Math. Bull., 30(4):436–445, 1987.  https://faculty.math.illinois.edu/~z-furedi/PUBS/furedi_barany_empty-simplices.pdf.
  * [Erd75] Paul Erdős.  On some problems of elementary and combinatorial geometry.  Ann. Mat. Pura Appl. (4), 103:99–108, 1975.  https://users.renyi.hu/~p_erdos/1975-25.pdf.
  * [ES35] P. Erdős and G. Szekeres.  A combinatorial problem in geometry.  Compositio Math., 2:463–470, 1935.
  * [Ger08] Tobias Gerken.  Empty convex hexagons in planar point sets.  Discrete Comput. Geom., 39(1-3):239–272, 2008.
  * [Har78] Heiko Harborth.  Konvexe Fünfecke in ebenen Punktmengen.  Elem. Math., 33(5):116–118, 1978.  doi:10.5169/seals-32945.
  * [Hor83] J. D. Horton.  Sets with no empty convex $7$-gons.  Canad. Math. Bull., 26(4):482–484, 1983.
  * [KM88] M. Katchalski and A. Meir.  On empty triangles determined by points in the plane.  Acta Math. Hungar., 51(3–4):323–328, 1988.
  * [Nic07] Carlos M. Nicolás.  The empty hexagon theorem.  Discrete Comput. Geom., 38(2):389–397, 2007.
  * [NX96] Harald Niederreiter and Chaoping Xing.  Low-discrepancy sequences and global function fields with many rational places.  Finite Fields Appl., 2(3):241–273, 1996.
  * [Sch08] Rudolf Schürer.  A new lower bound on the $t$-parameter of $(t,s)$-sequences.  In Monte Carlo and quasi-Monte Carlo methods 2006, pages 623–632. Springer, Berlin, 2008.
  * [Sob67] I. M. Sobol’.  Distribution of points in a cube and approximate evaluation of integrals.  Ž. Vyčisl. Mat i Mat. Fiz., 7:784–802, 1967.  http://mi.mathnet.ru/zvmmf7334.
  * [Val92] Pavel Valtr.  Sets in ${\bf R}^{d}$ with no large empty convex subsets.  Discrete Math., 108(1–3):115–124, 1992.  Topological, algebraical and combinatorial structures. Frolík’s memorial volume.
  * [XN95] Chao Ping Xing and Harald Niederreiter.  A construction of low-discrepancy sequences using global function fields.  Acta Arith., 73(1):87–102, 1995.