Complexity of non-abelian cut-and-project sets of polytopal type I: special homogeneous Lie groups

Abstract

The aim of this paper is to determine the asymptotic growth rate of the complexity function of cut-and-project sets in the non-abelian case. In the case of model sets of polytopal type in homogeneous two-step nilpotent Lie groups, we can establish that the complexity function asymptotically behaves like $r^{{\mathrm {homdim}}(G) \dim (H)}$. Further, we generalize the concept of acceptance domains to locally compact second countable groups.

1. Introduction

This article is concerned with the complexity of discrete subsets of locally compact groups, which obey some form of aperiodic order. An extensive discussion of this can be found in the thesis by the author [27]. In this paper, our focus is on the Lie group case and in a following paper, we will extend the argumentation to hyperbolic spaces.

For discrete subsets of locally compact abelian groups, notably for discrete subsets of ${\mathbb {R}}^n$ , there is an established notion of complexity based on the study of the so-called patch counting function [1, 5, 21, 26, 30, 32, 37, 38, 50]. More recently, there has been an approach to extend results about discrete subsets of locally abelian groups to general locally compact groups [7–10].

In the present article, we contribute to this program by extending the notion of complexity to discrete subsets of non-abelian locally compact groups. More specifically, we are going to generalize an approach of Julien [26], and Haynes, Koivusalo and Walton [21]. While the theory works in full generality, we will obtain our strongest results in the case of two-step-nilpotent Lie groups.

1.1. Aperiodic order in the Euclidean case

Consider the abelian group $({\mathbb {R}}^n, +)$ as a metric group with respect to the standard Euclidean metric. A set $\Lambda \subset {\mathbb {R}}^n$ is called locally finite if for all bounded sets $B \subset {\mathbb {R}}^n$ , the intersection $\Lambda \cap B$ is finite. For these sets, one can define the patch counting function $p(r)$ (see Definition 1.2) as a measure of their complexity. Examples of locally finite sets are lattices. Their complexity functions are constant 1, meaning that lattices are highly structured. In the case of aperiodic ordered sets, the patch counting function is growing at least linearly [30, 32, 37, 38, 50]. A locally finite set with $p(r)< \infty $ for all $r>0$ is called a set with finite local complexity or an FLC set.

There are two important methods to construct FLC sets, either by substitution or by cut-and-project. We are interested in the cut-and-project approach, which is due to Yves Meyer, who is a pioneer in the field of aperiodic order and laid the foundation for much of our common knowledge in the 1960s [34–36]. The idea in the cut-and-project approach is to consider a lattice $\Gamma $ in the product ${\mathbb {R}}^n \times {\mathbb {R}}^d$ . Then one chooses a subset $W \subset {\mathbb {R}}^d$ , which is called the window. The projection of $({\mathbb {R}}^n \times W) \cap \Gamma $ to ${\mathbb {R}}^n$ results in a point set, which is called a cut-and-project set. Under some extra conditions, this cut-and-project set is an FLC set, and in this case, it is called the model set defined by the data $\Lambda ({\mathbb {R}}^n, {\mathbb {R}}^d, \Gamma , W)$ . Such sets have been studied from different perspectives, see for example [3, 21, 24, 29, 39].

The approach has also been generalized to abelian locally compact second countable groups, see for example [42, 43].

In the 1980s, the popularity of this field was pushed by the discovery of quasi-crystals [45]. After this discovery, physicists, crystallographers and mathematicians worked on models to describe these newly discovered aperiodic structures. Physicists are primarily interested in quasi-crystals in ${\mathbb {R}}^n$ for $n \leq 3$ , but mathematically, the restriction on the dimension is unnatural and therefore was rapidly dropped. A history of the developments in this time can be found in the book by Senechal [44]. The characterizing property of a quasi-crystal is pure-point diffraction, which is a global property and was studied in [4, 13, 22, 23, 31]. Another line of research is to characterize the structure of an aperiodic ordered set by some local data, namely its repetitivity or its complexity [30, 32, 37, 38, 50]. For a comprehensive overview of the field, see [2].

This paper will focus on understanding the complexity of model sets. We want to determine how the complexity function $p(r)$ behaves asymptotically.

Definition 1.1. (Patch)

Let X be a metric space, $\Lambda \subset X$ a locally finite subset, $\unicode{x3bb} \in \Lambda $ and $r\in {\mathbb {R}}^+$ . Then the r-patch $P_r(\unicode{x3bb} )$ is the constellation of points from $\Lambda $ around $\unicode{x3bb} $ , which have distance at most r to $\unicode{x3bb} $ , that is, $ P_r(\unicode{x3bb} ):= B_r(\unicode{x3bb} ) \cap \Lambda $ .

If G is a locally compact second countable (lcsc) group, the set of patches of radius r impose an equivalence relation on the elements of $\Lambda \subset G$ by

(1.1) $$ \begin{align} \unicode{x3bb} \sim_r \mu :\Leftrightarrow P_r(\unicode{x3bb})\unicode{x3bb}^{-1}=P_r(\mu)\mu^{-1}. \end{align} $$

We will denote the r-equivalence class of $\unicode{x3bb} $ by

$$ \begin{align*} A_r^G(\unicode{x3bb}):= \{\mu \in \Lambda \mid \unicode{x3bb} \sim_r \mu\} \subset G \end{align*} $$

and the set of all equivalence classes by

$$ \begin{align*} A_r^G:=\{A_r^G(\unicode{x3bb}) \mid \unicode{x3bb} \in \Lambda\}. \end{align*} $$

Definition 1.2. (Complexity function)

Let G be an lcsc group and $\Lambda \subset G$ a locally finite subset. Then the complexity function $p(r)$ is given by

$$ \begin{align*} p(r) := \vert\{B_r(e) \cap \Lambda \unicode{x3bb}^{-1} \,|\, \unicode{x3bb} \in \Lambda\} \vert = \vert\{P_r(\unicode{x3bb}) \unicode{x3bb}^{-1} \,|\, \unicode{x3bb} \in \Lambda \}\vert = \vert A_r^G \vert. \end{align*} $$

The function p is also called the patch-counting function and first appeared in the work by Lagarias and Pleasants [32], where it is denoted by $N_X$ . Note that model sets carry more information than the underlying point set itself, and this can be used to determine the complexity function. Some early work in this context is done in [1, 5] for some special cases and low dimensions. A general approach first appeared in the paper by Julien [26], where the main idea is that each class of patches corresponds to a certain region inside the window, the so called acceptance domain. Optimal results can be obtained in the case of polytopal windows, that is, when W is a convex polytope. The ideas of Julien were picked up by Koivusalo and Walton [28], who proved the following theorem. We will assume the stabilizers of the hyperplanes which bound the window are trivial; in the original theorem, the role of these stabilizers is addressed.

Theorem 1.3. (Koivusalo and Walton [28, Theorem 7.1])

Consider a model set $\Lambda ({\mathbb {R}}^n, {\mathbb {R}}^d, \Gamma , W)$ with a polytopal window W. Assume that the stabilizers of the hyperplanes which bound the window are trivial. Then the complexity grows asymptotically as $p(r) \asymp r^{n \cdot d}$ .

1.2. Aperiodic order beyond the Euclidean case

A natural generalization of FLC sets in ${\mathbb {R}}^n$ is to consider FLC sets in arbitrary locally compact groups equipped with some metric. We will be interested in studying their complexity functions. We emphasize that in doing so, the choice of metric is important. By the restriction to lcsc groups, a theorem of Struble [47] guarantees the existence of a ‘nice’ metric. ‘Nice’ means in this context that the metric is right-invariant, proper and compatible. So we will study metric groups, in which the metric fulfils these properties. This is the setup in which the Euclidean ideas are generalized [7–10, 33].

The cut-and-project approach also applies in this more general setup [10]. The question we want to answer is how the approach of Julien, and Koivusalo and Walton can be translated to this more general setup? This question was asked during the 2017 Oberwolfach workshop ‘Spectral Structures and Topological Methods in Mathematical Quasicrystals’ for the Heisenberg group by Tobias Hartnick and Henna Koivusalo.

1.3. Results on two-step homogeneous Lie groups

Ideally, one would like to describe the complexity of FLC sets for all lcsc groups. However, this turns out to be quite challenging so we will have to introduce some more restrictions. In particular, since we want to follow the approach of Julien [26], and Koivusalo and Walton [28], we need a notion of hyperplanes. So a first question is in which groups can we define hyperplanes?

We will consider homogeneous Lie groups. These groups are nilpotent, real, finite-dimensional, connected, simply connected and admit a family of dilations which replace the scalar multiplication. For a detailed discussion of such groups, we refer to the book by Fischer and Ruzhansky [14]. For this class of groups, it is possible to identify the underlying set of the Lie group G with the corresponding Lie algebra ${\mathfrak {g}}$ . Since ${\mathfrak {g}}$ is a vector space, we can define hyperplanes in the usual sense. An example of such a group is the Heisenberg group.

Moreover, these groups admit a canonical quasi-isometry class of homogeneous norms, which provide the same complexity resolving the aforementioned issue of dependence on the choice of metric. It turns out that balls with respect to such norms have exact polynomial growth, that is, the volume of a ball $B_r(e)$ grows as $r^{\alpha }$ . The exponent of this growth is called the homogeneous dimension of the homogeneous Lie group.

A second restriction has to be made since we also need that the group acts on the space of hyperplanes in the vector space underlying ${\mathfrak {g}}$ . We can show that this is the case exactly if the Lie group has nilpotency degree one or two, that is, if it is abelian or two-step nilpotent. For higher nilpotency degree, the action of the group bends the hyperplanes into algebraic hypersurfaces.

Naively, one would expect that the complexity function of a model set $\Lambda (G,H, \Gamma , W)$ would depend on the dimension of the Lie groups G and H, that is, $p(r)\asymp r^{\dim (G)\dim (H)}$ , or if not, their homogeneous dimensions, that is, $p(r) \asymp r^{{\mathrm {homdim}}(G){\mathrm {homdim}}(H)}$ , but surprisingly, both turn out to be false. In fact, the two factors behave differently. On the G-side, the homogeneous dimension replaces the dimension, while on the H-side, it does not. More precisely, we prove the following theorem, which is the main theorem of this paper.

Theorem 1.4. (Informal version of the main theorem, Theorem 5.1)

Consider a model set $\Lambda (G, H, \Gamma , W)$ with a convex polytopal window W, and G and H two-step nilpotent homogeneous Lie groups. Assume that the stabilizer of the hyperplanes which bound the window is trivial. Then the complexity grows asymptotically as $p(r) \asymp r^{{\mathrm {homdim}}(G) \cdot \dim (H)}$ .

1.4. Method of proof

The proof of the main theorem consists of four steps. The first three are similar to the Euclidean case, while the fourth one uses different techniques.

First, we will establish the connection between the equivalence classes of patches and the acceptance domains in §2. This is a translation from the Euclidean case considered in [28]. The only difference is that we have to be a bit more careful since our groups are, in general, non-abelian. The established result is the same as in the Euclidean case.

Definition 1.5. Let $\Lambda (G,H, \Gamma , W)$ be a model set, with $G, H$ lcsc groups, $\Gamma \subset G \times H$ a uniform lattice and $W\subset H$ a non-empty, pre-compact, $\Gamma $ -regular window. Further, let $\unicode{x3bb} \in \Lambda $ and $r>0$ , then

$$ \begin{align*} \bigg(\bigcap_{\mu \in {\mathcal{S}}_r(\unicode{x3bb})}\mu \mathring{W}\bigg)\cap \bigg(\bigcap_{\mu \in {\mathcal{S}}_r(\unicode{x3bb})^{\mathrm{C}}} \mu W^{\mathrm{C}} \bigg)=:W_r(\unicode{x3bb}) \end{align*} $$

is called the r-acceptance domain of $\unicode{x3bb} $ , where $S_r$ is the set of points in $\Gamma $ which project into $W W^{-1}$ and are within radius r of the origin, see Definition 2.7 for a formal definition.

Theorem 2.2. (Acceptance domains versus equivalence classes)

Let $\Lambda (G,H, \Gamma , W)$ be a model set, with $G, H$ lcsc groups, $\Gamma \subset G \times H$ a uniform lattice and $W\subset H$ a non-empty, pre-compact, $\Gamma $ -regular window, then

$$ \begin{align*} A_r^H(\unicode{x3bb}) \subset W_r(\unicode{x3bb}). \end{align*} $$

Further, for $\unicode{x3bb} \not \sim _r \unicode{x3bb} '$ , we have

$$ \begin{align*} W_r(\unicode{x3bb}) \cap W_r(\unicode{x3bb}') = \emptyset. \end{align*} $$

Finally, we have

$$ \begin{align*} \overline{W} = \bigcup_{\unicode{x3bb} \in A_r^G}\overline{W_r(\unicode{x3bb})}. \end{align*} $$

We will give the precise definition of ${\mathcal {S}}_r(\unicode{x3bb} )$ in §2 and of $A_r^H(\unicode{x3bb} )$ in Definition 1.12. For now, think of $A_r^H(\unicode{x3bb} )$ as the projection of all the points in the equivalence class of $\unicode{x3bb} $ to H. Further, ${\mathcal {S}}_r(\unicode{x3bb} )$ and ${\mathcal {S}}_r^{\mathrm {C}}(\unicode{x3bb} )$ are roughly speaking a decomposition of the possible neighbours of $\unicode{x3bb} $ projected to H.

As a second step, we establish a lattice point counting argument in §3.

Proposition 3.1. (Growth lemma)

Let G and H be lcsc groups. For a model set $\Lambda (G,H, \Gamma , W)$ with a uniform lattice $\Gamma \subset G \times H$ and a bounded open set ${\emptyset \neq A \subset H}$ , the asymptotic growth of the number of lattice points inside $B^G_r(e) \times A$ is bounded by

$$ \begin{align*} \mu_G (B^G_{r-k_1}(e)) \ll \vert(B^G_r(e)\times A)\cap \Gamma \vert \ll \mu_G(B^G_{r+k_2}(e)) \end{align*} $$

for some constants $k_1,k_2>0$ as $r \to \infty $ .

Remark 1.6. For the asymptotic behaviour, we use the common notation $g(t) \ll f(t)$ which means $\limsup \limits _{t \to \infty }\vert {g(t)}/{f(t)} \vert < \infty $ . If both $g(t) \ll f(t)$ and $g(t) \gg f(t)$ hold, we write $g(t) \asymp f(t)$ .

This result connects the number of lattice points in sets of a certain form to the measure of these sets. The standard proof is via ergodic theory, but we will give a more elementary proof.

In the third step, we show in §5 that we can estimate the number of acceptance domains by extending the boundary of the window. This is also done in [28]; the new regions inside the window are called cut regions in this paper. Again, the result we obtain is the same as in the Euclidean case. However, we have to overcome a major difference in its proof since in the Euclidean case, the group acts on a hyperplane by translations, which preserves the directions of the hyperplane. Or formulated differently, a translation does not rotate a hyperplane. In our general setup, the group action can rotate hyperplanes, leading to a new phenomenon.

The following theorem is a combination of Lemmas 5.2, 5.3 and Proposition 5.23.

Theorem 1.7. (Cut regions versus acceptance domains)

For a polytopal model set $\Lambda (G,H,\Gamma ,W)$ , where the window is bounded by $P_1,\ldots ,P_N$ , and G and H at most two-step nilpotent homogeneous Lie groups, we have

$$ \begin{align*} \vert A_r^H\vert \leq \# \pi_0 \bigg( H \setminus \bigcup_{\mu\in{\mathcal{S}}_r} \bigcup_{i=1}^N \mu P_i\bigg). \end{align*} $$

For a certain ball $B_h(c_W)\subset W$ , we also have

$$ \begin{align*} \# \pi_0 \bigg( B_h(c_W) \setminus \bigcup_{i=1}^N \bigcup_{\mu \in U_i(r)} \mu P_i \bigg) \leq \vert A_r^H \vert. \end{align*} $$

The last step is devoted to solving the problem with the rotating hyperplanes, see §6. To do so, we use the theory of hyperplane arrangements; this tool was not needed in the abelian case. The research of such arrangements has a long history and goes back as far as [41], whereas more modern approaches are due to Grünbaum [18–20] and Zaslavsky [51]. Two sources for a survey of the field are the book by Dimca [12] and the lecture notes by Stanley [46]. An important tool for our combinatorial argument is by Beck [6]. We need a special version of Beck’s theorem. To prove this version of Beck’s theorem, we need some combinatorial inputs from [48]. This lets us extend the standard counting formulae to our specific context and we can prove the following theorem, which will then finish the proof of the main theorem.

Theorem 6.1. (Higher dimensional local dual of Beck’s theorem)

Let ${\mathcal {H}}$ be a hyperplane arrangement in ${\mathbb {R}}^d$ and let $B \subset {\mathbb {R}}^d$ be convex. Further, let ${\mathcal {H}}$ consist of d families $F_1,\ldots ,F_d$ with $\vert F_i \vert = {n}/{d}$ and such that for all $(f_1,\ldots ,f_d) \in F_1 \times \cdots \times F_d$ , we have $B \cap \bigcap _{i=1}^d f_i = \{p\}$ for some point $p \in B$ . Moreover, assume that there is a constant $c < {1}/{100}$ such that at most $c \cdot \vert F_i \vert $ hyperplanes from $F_i$ can intersect in one point. Then there exists a constant $c_d$ , depending on the dimension d, such that the number of intersection points in B exceeds $c_d \cdot n^d$ , that is, $\vert F_{0,B} \vert \geq c_d \cdot n^d$ .

1.5. General results for lcsc groups

As discussed above, our restriction to homogeneous Lie groups is necessary for the proof of the main theorem, but the individual steps work in greater generality. Acceptance domains and cut regions can be defined for all connected lcsc groups, and the polytopal condition on the window is not needed for this approach.

1.6. Notation

Throughout this text, G and H will always be locally compact second countable groups, $\Gamma \subset G \times H$ a uniform lattice and $W \subset H$ a precompact $\Gamma $ -regular, that is, $\partial W \cap \pi _H(\Gamma ) = \emptyset $ , subset with non-empty interior, which is called the window. Why these restrictions on W are required will be explained in Proposition A.2. Further, we denote the projection on G by $\pi _G$ and on H by $\pi _H$ .

Definition 1.8. A triple $(G,H, \Gamma )$ is called a cut-and-project scheme (CPS) if $\pi _G\vert _\Gamma $ is injective and $\pi _H(\Gamma )$ is dense in H. The set

$$ \begin{align*} \Lambda = \Lambda(G, H, \Gamma, W) := \pi_G((G \times W) \cap \Gamma) = \tau^{-1}(\Gamma_H \cap W) \end{align*} $$

is called a model set if $(G,H, \Gamma )$ is a cut-and-project scheme. Here we use the notation $\Gamma _H := \pi _H(\Gamma )$ and $\tau := \pi _H \circ (\pi _G \vert _\Gamma )^{-1}$ .

Remark 1.9. Observe that we do not consider non-uniform model sets, so in our terminology of a model set, the lattice is always uniform.

We will always put a G (respectively H) in the index if we consider the projection of an object to the factor G (respectively H). Figure 1 visualizes the relation between the different groups in this setup.

Figure 1 Visualization of a CPS.

To study complexity, we need a metric that will always be associated to a norm by $d(x,y):= \vert x y^{-1}\vert $ . In the case of homogeneous Lie groups, we have an homogeneous norm on G and H, which we will denote by $\vert \cdot \vert _G$ , $\vert \cdot \vert _H$ ; if it is clear which norm we consider, we drop the index.

Definition 1.10. (Delone)

Let X be a metric space, a subset $\Lambda \subset X$ is called $(R,r)$ -Delone if:

1. (a) it is R-relatively dense, that is,

   $$ \begin{align*} \text{there exists } R>0\quad \text{for all } x \in X : B_R(x) \cap \Lambda \neq \emptyset; \end{align*} $$

2. (b) it is r-uniformly discrete, that is,

   $$ \begin{align*} \text{there exists } r>0\quad \text{for all } \unicode{x3bb}, \mu \in \Lambda: d(\unicode{x3bb},\mu) \geq r. \end{align*} $$

If one is not interested in the parameters R and r, one simply speaks of a Delone set.

Remark 1.11. By Proposition A.2, model sets are Delone sets.

Definition 1.12. (Pre-acceptance domains)

Let $\Lambda (G,H, \Gamma , W)$ be a model set. The image of $A_r^G(\unicode{x3bb} )$ under the map $\tau $ is called the r-pre-acceptance domain of $\unicode{x3bb} $ :

$$ \begin{align*} A_r^H(\unicode{x3bb}):=\tau (A_r^G(\unicode{x3bb})) \subset H. \end{align*} $$

We denote the set of all pre-acceptance domains by $A_r^H$ .

2. How to measure complexity?

In this section, we will explain how one can determine the complexity function of a given FLC set, e.g. a model set $\Lambda (G, H, \Gamma , W)$ , where $G=(G,d_G)$ and $H=(H,d_H)$ are metric locally compact second countable groups. The statements in this section are translations from the Euclidean case, we refer to the paper of Koivusalo and Walton [28] for this setup. We will take a closer look at how the complexity function p is connected to local constellations, which are called patches, in the FLC set. We will then establish a connection between these patches and certain regions in the window W.

Definition 2.1. (Finite local complexity)

Let $\Lambda \subset G$ be an FLC subset. If the complexity function of $\Lambda $ is finite for all r, we say that $\Lambda $ has finite local complexity. There are several ways of viewing this condition, compare Lemma A.1.

Theorem 2.2. (Acceptance domains)

Let $\Lambda (G,H, \Gamma , W)$ be a model set, with $G, H$ lcsc groups, $\Gamma \subset G \times H$ a uniform lattice and $W\subset H$ a non-empty, pre-compact, $\Gamma $ -regular window, then

(2.1) $$ \begin{align} A_r^H(\unicode{x3bb}) \subset \bigg(\bigcap_{\mu \in {\mathcal{S}}_r(\unicode{x3bb})}\mu \mathring{W}\bigg)\cap \bigg(\bigcap_{\mu \in {\mathcal{S}}_r(\unicode{x3bb})^{\mathrm{C}}} \mu W^{\mathrm{C}} \bigg)=:W_r(\unicode{x3bb}), \end{align} $$

where ${\mathcal {S}}_r(\unicode{x3bb} )$ will be defined in Definition 2.7. The $W_r(\unicode{x3bb} )$ are called r-acceptance domains of $\unicode{x3bb} $ . Further, for $\unicode{x3bb} \not \sim _r \unicode{x3bb} '$ , we have

(2.2) $$ \begin{align} W_r(\unicode{x3bb}) \cap W_r(\unicode{x3bb}') = \emptyset. \end{align} $$

Finally, we have

(2.3) $$ \begin{align} \overline{W} = \bigcup_{\unicode{x3bb} \in A_r^G}\overline{W_r(\unicode{x3bb})}. \end{align} $$

Remark 2.3. The terminology is due to Koivusalo and Walton [28]. In their paper, they treat the case of model sets $\Lambda ({\mathbb {R}}^d,{\mathbb {R}}^n,\Gamma , W)$ and extend on Julien’s paper [26], which first introduced the idea of considering a decomposition of the window.

Corollary 2.4. $p(r)=\vert \{W_r(\unicode{x3bb} ) \mid \unicode{x3bb} \in \Lambda \}\vert =\vert A_r^H\vert $ .

The rest of the section is devoted to the proof of the theorem and we begin by working towards the definition of $S_r(\unicode{x3bb} )$ .

Definition 2.5. (Displacements)

Let $\Lambda $ be a CPS. We define the displacements of $\unicode{x3bb} \in \Lambda $  as

$$ \begin{align*} \mathrm{Disp}(\unicode{x3bb}):=\{\mu \in \Gamma_G \mid \mu \unicode{x3bb} \in \Lambda\}. \end{align*} $$

Lemma 2.6. [28, Lemma 2.1]

Let $\unicode{x3bb} \in \Lambda $ and $\mu \in G$ . If $\mu \unicode{x3bb} \in \Lambda $ , then $\mu \in \Gamma _G$ . However, if $\mu \in \Gamma _G$ ,

$$ \begin{align*} \mu \unicode{x3bb} \in \Lambda \Leftrightarrow \tau(\unicode{x3bb}) \in \tau(\mu)^{-1}\mathring{W} \Leftrightarrow \tau(\mu) \in \mathring{W}\tau(\unicode{x3bb})^{-1}. \end{align*} $$

In particular, $\tau (\mathrm {Disp}(\unicode{x3bb} )) \subset \mathring {W}\mathring {W}^{-1}$ .

Proof. Since $\unicode{x3bb} , \mu \unicode{x3bb} \kern1.3pt{\in}\kern1.3pt \Lambda $ , we find elements $\gamma , \delta \kern1.3pt{\in}\kern1.3pt \Gamma $ such that $\pi _G(\gamma )\kern1.3pt{=}\kern1.3pt\unicode{x3bb} $ , ${\pi _G(\delta )\kern1.3pt{=}\kern1.3pt(\mu \unicode{x3bb} )^{-1}}$ . Then $\gamma \delta \in \Gamma $ and $\pi _G(\gamma \delta )= \unicode{x3bb} (\mu \unicode{x3bb} )^{-1} = \mu ^{-1} \in \Gamma _G$ , and therefore $\mu \in \Gamma _G$ .

Now let $\mu \in \Gamma _G$ . By definition, $\mu \unicode{x3bb} \in \Lambda $ if and only if $\tau (\mu \unicode{x3bb} ) \in \mathring {W}$ and since $\tau $ is a homomorphism, this is equivalent to $\tau (\mu ) \in \mathring {W} \tau (\unicode{x3bb} )^{-1}$ and $\tau (\unicode{x3bb} ) \in \tau (\mu )^{-1}\mathring {W}$ .

To understand patches on the H-side of the model set, we transport the information of the displacements to this side. Since we always consider patches in dependence of r, we only need displacements of magnitude at most r (see Figure 2).

Figure 2 Preimage of the slab for a fixed r in the setting of an ${\mathbb {R}} \times {\mathbb {R}}$ model set.

Definition 2.7. (r-slab)

Let $\Lambda (G,H,\Gamma ,W)$ be a model set. We define the r-slab as

$$ \begin{align*} {\mathcal{S}}_r := \pi_H(\{(\gamma,\mu) \in \Gamma \,\vert\, \vert \gamma \vert <r \text{ and } \mu \in WW^{-1} \}). \end{align*} $$

Further, in the case where we are only interested in the displacements of a certain equivalence class, we define the r-slab of $\unicode{x3bb} $ as

$$ \begin{align*} {\mathcal{S}}_r(\unicode{x3bb}) := \pi_H(\{(\gamma,\mu) \in \Gamma \,\vert\, \vert \gamma \vert <r \text{ and } \mu \in WW^{-1} \text{ and } \gamma^{-1} \in \mathrm{Disp}(\unicode{x3bb}) \}) \end{align*} $$

and

$$ \begin{align*} {\mathcal{S}}_r^{\mathrm{C}}(\unicode{x3bb}) := \pi_H(\{(\gamma,\mu) \in \Gamma \,|\, \vert \gamma \vert <r \text{ and } \mu \in WW^{-1} \text{ and } \gamma^{-1} \notin \mathrm{Disp}(\unicode{x3bb}) \}). \end{align*} $$

Remark 2.8. In the paper of Koivusalo and Walton, the sets $S_r(\unicode{x3bb} )$ and $S_r^{\mathrm {C}}(\unicode{x3bb} )$ are called $P_{in}$ and $P_{out}$ , but we think that our notation highlights the connection to the slab in a better way, whereas their notation highlights the connection to the patch P.

Lemma 2.9. For $\unicode{x3bb} , \mu \in \Lambda $ , we have that $\unicode{x3bb} \sim _r \mu \Leftrightarrow {\mathcal {S}}_r(\unicode{x3bb} )={\mathcal {S}}_r(\mu )$ .

Proof. Assume $\unicode{x3bb} \sim _r \mu $ , then $(B_r(\unicode{x3bb} ) \cap \Lambda )\unicode{x3bb} ^{-1}=(B_r(\mu ) \cap \Lambda )\mu ^{-1}$ . Let $x \in S_r(\unicode{x3bb} )$ , then there exists a $(\gamma , x)\in \Gamma $ such that

$$ \begin{align*} \gamma^{-1}\unicode{x3bb} &\in B_r(\unicode{x3bb}) \cap \Lambda\\ &\Leftrightarrow \gamma^{-1} \in (B_r(\unicode{x3bb}) \cap \Lambda)\unicode{x3bb}^{-1} = (B_r(\mu) \cap \Lambda)\mu^{-1}\\ &\Leftrightarrow \gamma^{-1}\mu \in B_r(\mu) \cap \Lambda. \end{align*} $$

Therefore, $x \in S_r(\mu )$ .

Now assume ${\mathcal {S}}_r(\unicode{x3bb} )\kern1.4pt{=}\kern1.4pt{\mathcal {S}}_r(\mu )$ and let $x \kern1.4pt{\in}\kern1.4pt (B_r(\unicode{x3bb} )\kern1.4pt{\cap}\kern1.4pt \Lambda )\unicode{x3bb} ^{-1}$ , then ${\tau (x^{-1}) \kern1.4pt{\in}\kern1.4pt {\mathcal {S}}_r(\unicode{x3bb} )\kern1.4pt{=}\kern1.4pt{\mathcal {S}}_r(\mu )}$ and this implies $x \in (B_r(\mu )\cap \Lambda )\mu ^{-1}$ .

Proof of Theorem 2.2

Lemma 2.9 tells us that for all $\unicode{x3bb} \in A_r^G(\unicode{x3bb} )$ , the set

$$ \begin{align*} W_r(\unicode{x3bb}):=\bigg(\bigcap_{\mu \in {\mathcal{S}}_r(\unicode{x3bb})}\mu \mathring{W}\bigg)\cap \bigg(\bigcap_{\mu \in {\mathcal{S}}_r(\unicode{x3bb})^{\mathrm{C}}} \mu W^{\mathrm{C}} \bigg) \end{align*} $$

is the same. So to prove equation (2.1), it is enough to show $\tau (\unicode{x3bb} )\in W_r(\unicode{x3bb} )$ . By the definition of the r-slab of $\unicode{x3bb} $ , we have for all $\mu \in {\mathcal {S}}_r(\unicode{x3bb} )$ that there is a $\mu _G \in \Gamma _G$ with $\tau (\mu _G)=\mu $ and $\mu _G^{-1}\unicode{x3bb} \in \Lambda $ . Further, Lemma 2.6 tells us that $\tau (\unicode{x3bb} ) \in \mu \mathring {W}$ . For $\mu \in {\mathcal {S}}_r^{\mathrm {C}}(\unicode{x3bb} )$ , Lemma 2.6 tells us that $\tau (\unicode{x3bb} ) \not \in \mu W$ , but this means that $\tau (\unicode{x3bb} ) \in \mu W^{\mathrm {C}}$ . So it follows that $\tau (\unicode{x3bb} )\in W_r(\unicode{x3bb} )$ .

Now let $\unicode{x3bb} \not \sim _r \unicode{x3bb} '$ , so by Lemma 2.9, $S_r(\unicode{x3bb} ) \neq S_r(\mu )$ and the disjointness of $W_r(\unicode{x3bb} )$ and $W_r(\unicode{x3bb} ')$ follows by the same argument.

Finally, we show that the $W_r(\lambda)$ cover the closure of the window W. The inclusion ${\overline {W_r(\unicode{x3bb} )} \subseteq \overline {W}}$ is clear since $e_H \in {\mathcal {S}}_r(\unicode{x3bb} )$ for all $\unicode{x3bb} \in \Lambda $ and all $r>0$ . Since $\Gamma _H$ is dense in W and $W_r(\unicode{x3bb} )$ is open, we know that $\Gamma _H$ is dense in $W_r(\unicode{x3bb} )$ . Since ${A_r^H(\unicode{x3bb} )=\Gamma _H \cap W_r(\unicode{x3bb} )}$ , we know that $A_r^H(\unicode{x3bb} )$ is dense in $W_r(\unicode{x3bb} )$ . Therefore, the completion by sequences $\overline {A_r^H(\unicode{x3bb} )}^{\mathrm{seq}}$ is the topological closure $\overline {W_r(\unicode{x3bb} )}^{\mathrm{top}}$ . Further, since every ${\gamma \in \Gamma _H \cap W}$ has to belong to some $W_r(\unicode{x3bb} )$ , we get that

$$ \begin{align*} W \cap \Gamma_H= \bigcup_{\unicode{x3bb} \in A_r^G} A_r^H(\unicode{x3bb}). \end{align*} $$

Completion by sequences on both sides delivers

$$ \begin{align*} \overline{W} = \bigcup_{\unicode{x3bb} \in A_r^G} \overline{A_r^H(\unicode{x3bb})}^{\mathrm{seq}} = \bigcup_{\unicode{x3bb} \in A_r^G} \overline{W_r(\unicode{x3bb})}^{\mathrm{top}}.\\[-50pt] \end{align*} $$

Remark 2.10. Taking the closure of the window in the theorem does not make a big difference, since by $\Gamma $ -regularity, there are no projected lattice points on the boundary. This also holds for the shifted window, since if $\gamma _1, \gamma _2 \in \Gamma _H$ with $\gamma _1 \in \gamma _2 W$ , then $\gamma _2^{-1}\gamma _1 \in W$ in contradiction to the $\Gamma $ -regularity of W. So for all acceptance domains, $\partial W_{r}(\unicode{x3bb} ) \cap \Gamma _H = \emptyset $ .

3. Lattice point counting

Before we begin with the actual proof of our main theorem, we will establish the growth lemma, Proposition 3.1. The growth lemma tells us how to count points in sets of the form $(B_r(e) \times A) \cap \Gamma $ . Notice that, in particular, the slab ${\mathcal {S}}_r=\pi _H((B_r(e)\times WW^{-1})\cap \Gamma )$ is of this form.

Proposition 3.1. (Growth lemma)

Let G and H be lcsc groups. For a model set with a uniform lattice $\Gamma \subset G \times H$ and a bounded open set ${\emptyset \neq A \subset H}$ , the asymptotic growth of the number of lattice points inside $B^G_r(e) \times A$ is bounded by

$$ \begin{align*} \mu_G(B^G_{r-k_1}(e)) \ll \vert(B^G_r(e)\times A)\cap \Gamma \vert \ll \mu_G(B^G_{r+k_2}(e)) \end{align*} $$

for some constants $k_1,k_2>0$ as $r \to \infty $ .

The proof consists of the following well-known proposition, see for example [2, Lemma 7.4], and the two subsequent lemmas.

Proposition 3.2. Let G and H be lcsc groups and $\Gamma \subset G \times H$ a uniform lattice such that $\pi _H(\Gamma )$ is dense in H. Further, let $U \subset H$ be an open non-empty set. Then there exists a compact set $K \subset G$ such that

$$ \begin{align*} G \times H = (K \times U)\Gamma. \end{align*} $$

Proof. Since $\Gamma $ is a uniform lattice in $G \times H$ , there exists a compact set C such that $G \times H= C\Gamma $ . We can cover C by the bigger compact set $\pi _G(C) \times \pi _H(C)$ , which implies $ G \times H = (C_G \times C_H)\Gamma $ . By density of $\pi _H(\Gamma )$ in H, we get a covering

$$ \begin{align*} \bigcup_{ \gamma \in \Gamma} U\pi_H(\gamma) = H \supset C_H. \end{align*} $$

Since $C_H$ is compact, we can choose a finite subcovering with finite $F\subset \Gamma $ such that

$$ \begin{align*} \bigcup_{ \gamma \in F} U\pi_H(\gamma) \supset C_H. \end{align*} $$

Now let $z\in G \times H$ be arbitrary. By the choice of C, we find a $\gamma \in \Gamma $ such that ${z \gamma ^{-1} \in C \subset C_G \times C_H}$ . By our covering argument, we find a $f \in F$ such that $\pi _H(z \gamma ^{-1}) \in \ U \pi _H(f)$ and therefore $\pi _H(z \gamma ^{-1} f^{-1}) \in U$ . If we project the same element to G, we get

$$ \begin{align*} \pi_G(z \gamma^{-1} f^{-1}) \in C_G \pi_G(F^{-1}) =:K. \end{align*} $$

Now K is compact since $C_G$ is compact and $\pi _G(F^{-1})$ is finite. Putting things together, we realise

$$ \begin{align*} z = (z \gamma^{-1} f^{-1}) (f \gamma) \in (K \times U) \Gamma.\\[-40pt] \end{align*} $$

Lemma 3.3. Let G and H be lcsc groups. For a model set with a uniform lattice $\Gamma \subset G \times ~H$ and a bounded open set ${\emptyset \neq A \subset H}$ , the growth of the lattice points inside $B^G_r(e) \times A$ is asymptotically bounded from above by

$$ \begin{align*} \vert(B^G_r(e)\times A)\cap \Gamma \vert \ll \mu_G(B^G_{r+k_2}(e)), \end{align*} $$

where $k_2$ is some constant as $r \to \infty $ .

Proof. Since $\Gamma $ is a lattice, it is uniformly discrete; therefore, we find a constant $c_1$ such that $d(\gamma _1,\gamma _2)> c_1$ for all $\gamma _1 \neq \gamma _2 \in \Gamma $ . If we halve the constant, we get disjoint balls around the lattice points, that is, $B^{G\times H}_{{c_1}/{2}}(\gamma _1) \cap B^{G\times H}_{{c_1}/{2}}(\gamma _2)=\emptyset $ .

Since A is bounded, we find a second constant $c_2$ such that $A \subset B_{c_2}^H(e)$ and that $B_{c_1}^{G\times H}(x)\subset G \times B^H_{c_2}(e)$ for every $x \in G\times A$ . The norm in the product is given by the maximum of the norms of the components.

The idea is that we build a set that contains not only the points of $(B^G_r(e)\times A)\cap \Gamma $ , but also the balls around them. Then we can obtain an upper bound for the number of points in $(B^G_r(e)\times A) \cap \Gamma $ by estimating how often the thickened set of points could fit in this set via a volume estimate. Since by our choice of ${c_1}/{2}$ the balls do not overlap, we obtain that

$$ \begin{align*} \sum_{\gamma \in (B^G_r(e)\times A) \cap \Gamma} \mu_{G \times H}(B^{G \times H}_{{c_1}/{2}}(\gamma)) \leq \mu_{G\times H} (B^G_{r+c_1}(e) \times B^H_{c_2}(e)). \end{align*} $$

We need the ‘ $+c_1$ ’ in the index so the set can also contain all the balls whose centres lie close to the border of $B^G_r(e)$ . The volume of a ball is independent of its centre point since the metric and the Haar-measure are right-invariant. Therefore, we can write the inequality as

$$ \begin{align*} \vert(B^G_r(e)\times A) \cap \Gamma\vert \cdot \mu_{G \times H}(B^{G \times H}_{{c_1}/{2}}(e)) \leq \mu_{G \times H}(B^G_{r+c_1}(e)\times B^H_{c_2}(e)). \end{align*} $$

We will now divide this equation by $\mu _{G \times H}(B^{G\times H}_{{c_1}/{2}}(e))$ , which is just a constant dependent on $c_1$ which we will denote by $c_1'$ and the constant $\mu _{H}(B^H_{c_2}(e))$ will be denoted by $c_2'$ .

$$ \begin{align*} \vert(B^G_r(e)\times A) \cap \Gamma\vert &\leq \frac{\mu_{G \times H}(B^G_{r+c_1}(e) \times B^H_{c_2}(e))}{c_1'}\\ &=\frac{\mu_{G}(B^G_{r+c_1}(e)) \cdot \mu_{H}(B^H_{c_2}(e))}{c_1'} = \frac{c_2'}{c_1'} \mu_G(B^G_{r+c_1}(e)).\\[-45pt] \end{align*} $$

Lemma 3.4. Let G and H be lcsc groups. For a model set with a uniform lattice ${\Gamma \subset G \times H}$ and a bounded open set ${\emptyset \neq A \subset H}$ , the growth of the number of lattice points inside $B^G_r(e) \times A$ is asymptotically bounded from below by

$$ \begin{align*} \vert(B^G_r(e)\times A)\cap \Gamma \vert \gg \mu_G(B^G_{r-k_1}(e)), \end{align*} $$

where $k_1$ is some constant as $r \to \infty $ .

Proof. Let $\varepsilon>0$ be fixed. We choose an open ball $B^H_\varepsilon (\gamma _H) \subset A$ with $\gamma _H \in \Gamma _H$ , this can be done since $\Gamma _H$ is dense in H and A is open, and therefore $\Gamma _H \cap A \subset A$ is dense.

First, we assume that $\gamma _H = e$ . By Proposition 3.2, we find a compact set ${K \subset G}$ such that $ G \times H = (K \times B^H_\varepsilon (e))\Gamma $ . Since K is compact, it is bounded, and we can consider $\overline {B^G_{c_1}}(e)$ , with $c_1$ large enough, instead. Then for all $z \in G \times H$ , we see $(B^G_{c_1}(e) \times B^H_\varepsilon (e)) z \cap \Gamma \neq \emptyset $ . This holds true since we can write $z=(k_z,u_z)(\gamma _{zG},\gamma _{zH})$ with $(\gamma _{zG},\gamma _{zH}) \in \Gamma $ , $k_z \in B^G_{c_1}(e)$ and $u_z \in B^H_\varepsilon (e)$ . However, then

$$ \begin{align*} (\gamma_{zG},\gamma_{zH}) = (k_z^{-1},u_z^{-1}) z \in (B^G_{c_1}(e) \times B^H_\varepsilon (e)) z \cap \Gamma, \end{align*} $$

since $k_z^{-1} \in B^G_{c_1}(e)$ and $u_z^{-1} \in B^H_\varepsilon (e)$ .

We can find a lower bound of the growth if we can fit enough of the sets of type ${(B^G_{c_1}(e)\times B^H_\varepsilon (e)) z}$ into $B^G_r(e) \times A$ in a disjoint way. One should think of this as stacking these sets onto another with base $B^H_\varepsilon (e)$ . This comes down to

$$ \begin{align*} &\vert(B^G_r(e)\times A)\cap \Gamma \vert> \vert(B^G_r(e) \times B^H_\varepsilon (e))\cap \Gamma \vert\\ &\quad\geq \max \{ \vert X \vert \,|\, X \subset G,\text{ such that } \text{ for all } x \in X: B^G_{c_1}(x) \subset B^G_r(e) \\ &\quad\quad \quad \quad \text{ and } B^G_{c_1}(x)\cap B^G_{c_1}(y) = \emptyset \text{ for all } x \neq y \in X \}\\ &\quad\geq \max \{ \vert X \vert \,|\, X \subset B^G_{r-c_1}(e) \text{ and } X \text{ is } 2c_1\text{-uniformly discrete}\}. \end{align*} $$

We can extend every $c_1$ -uniformly discrete set to a $(c_2,c_1)$ -Delone set for some constant $c_2$ [11, Proposition 3.C.3]. Thus,

$$ \begin{align*} &\vert(B^G_r(e)\times A)\cap \Gamma \vert\\ &\quad> \max \{ \vert X \vert \,|\vert\, X \subset B^G_{r-c_1}(e) \text{ and } X \text{ is a } (c_2,2c_1)\text{-Delone subset of } B_r^G(e)\}. \end{align*} $$

For every such Delone set, we can cover $B^G_{r-c_1}(e)$ with balls $B^G_{c_2}(x)$ for $x\in X$ , so that

$$ \begin{align*} \bigcup_{x \in X} B^G_{c_2}(x) \supset B^G_{r-c_1}(e) \Rightarrow \sum_{x\in X} \mu_{G}(B^G_{c_2}(x)) \geq \mu_G(B^G_{r-c_1}(e)). \end{align*} $$

Since the metric and the Haar-measure are right-invariant, all of these balls have the same measure and we get

$$ \begin{align*} \vert X \vert \cdot \mu_G(B^G_{c_2}(e)) \geq \mu_G(B^G_{r-c_1}(e)) \Leftrightarrow \vert X \vert \geq \frac{\mu_G(B^G_{r-c_1}(e))}{\mu_G(B^G_{c_2}(e))}. \end{align*} $$

Summing up, we have

$$ \begin{align*} \vert(B^G_r(e)\times A)\cap \Gamma \vert> \frac{\mu_G(B^G_{r-c_1}(e))}{\mu_G(B^G_{c_2}(e))}.\\[-42pt] \end{align*} $$

Definition 3.5. Let G be a locally compact group and let d be a right-invariant metric on G compatible with the topology on G. Then G is a group with exact polynomial growth of degree $\kappa $ with respect to d if there exists a constant $c>0$ such that

$$ \begin{align*} \lim\limits_{r \to \infty} \frac{\mu_{G}(B_r(e))}{c r^\kappa} =1. \end{align*} $$

Corollary 3.6. If G is a group with exact polynomial growth of degree $\kappa $ with respect to d, then

$$ \begin{align*} \vert(B^G_r(e)\times A)\cap \Gamma \vert \asymp r^\kappa. \end{align*} $$

4. Homogeneous Lie groups

In this section, we will review the basic concepts of homogeneous Lie groups, following the book by Fisher and Ruzhansky [14]. In this context, we also recall an ergodic theorem, due to Gorodnik and Nevo [16, 17, 40], which will be recalled later.

Definition 4.1. [14, Definition 3.1.7]

1. (a) A family of dilations of a Lie algebra ${\mathfrak {g}}$ is a family of linear mappings $\{D_r, r>0\}$ from ${\mathfrak {g}}$ to itself which satisfies:

   1. (i) the mappings are of the form

      $$ \begin{align*} D_r=e^{(\ln(r) A)} = \sum_{l=0}^\infty \frac{1}{l !}(\ln(r)A)^l, \end{align*} $$
      where A is a diagonalizable linear operator on ${\mathfrak {g}}$ with positive eigenvalues and $\ln (r)$ the natural logarithm of $r>0$ ;

   2. (ii) each $D_r$ is a morphism of the Lie algebra ${\mathfrak {g}}$ , that is, a linear mapping from ${\mathfrak {g}}$ to itself which respects the Lie bracket, that is,

      $$ \begin{align*} \text{for all } X,Y \in {\mathfrak{g}}, r>0: [D_r X, D_r Y] = D_r[X,Y]. \end{align*} $$

2. (b) An homogeneous Lie group is a connected simply connected Lie group whose Lie algebra is equipped with a fixed family of dilations.

3. (c) We call the eigenvalues of A the dilations’ weights, and the sum of these weights is the homogeneous dimension of ${\mathfrak {g}}$ , denoted by ${\mathrm {homdim}}({\mathfrak {g}})$ .

Convention 4.2. From now on, we will always assume G and H to be homogeneous Lie groups.

Remark 4.3. Since every Lie algebra, which is equipped with dilations, is nilpotent, an homogeneous Lie group is nilpotent [14, Proposition 3.1.10]. This together with the connectedness and the simply connectedness implies that the exponential map is a global diffeomorphism, see [14, Proposition 1.6.6], which we use to identify the underlying sets of G and ${\mathfrak {g}}$ . On ${\mathfrak {g}}$ , the group multiplication takes the form

$$ \begin{align*} X \ast Y := \log(\exp(X)\exp(Y)). \end{align*} $$

The operation $\ast $ is called the Baker–Campbell–Hausdorff (BCH) multiplication, since to determine it, we can use the BCH formula. The explicit formula for multiplication then is

$$ \begin{align*} X \ast Y = X + \sum_{\substack{k,m \geq 0 \\ p_i+q_i \geq 0\\ i \in \{0,\ldots ,k\}}} (-1)^k \frac{{{\mathrm{ad}}_X}^{p_1} \circ {{\mathrm{ad}}_Y}^{q_1} \circ \cdots \circ {{\mathrm{ad}}_X}^{p_k} \circ {{\mathrm{ad}}_Y}^{q_k} \circ {{\mathrm{ad}}_X}^m }{(k+1)(q_1+\cdots+q_k+1) \cdot p_1!\cdot q_1! \cdot \cdots \cdot p_k! \cdot q_k! \cdot m!}(Y). \end{align*} $$

In the case of an n-step nilpotent Lie group, this sum is finite since all terms there $m+\sum _i p_i + q_i \geq n$ are zero. The first few terms of the sum then look like

$$ \begin{align*} X \ast Y = X + Y +\tfrac{1}{2}[X,Y] + \tfrac{1}{12} ([X,[X,Y]]-[Y,[X,Y]])- \tfrac{1}{24} [Y,[X,[X,Y]]] + \cdots \end{align*} $$

Observe that the inverse of X in terms of the action $\ast $ is given by the additive inverse of X in the Lie algebra, that is, $X^{-1}= -X$ .

In particular, the group law is a polynomial, see [14, Proposition 1.6.6], which means that for $x=(x_1,\ldots ,x_n)$ and $y=(y_1,\ldots ,y_n)$ , we have

$$ \begin{align*} x \ast y = (P_1(x,y),\ldots , P_n(x,y)), \end{align*} $$

with $P_1,\ldots , P_n$ polynomials in $2n$ variables. We will observe some restrictions for this polynomials in Appendix B.1.

Observe that we can transport the dilations of the Lie algebra to the Lie group via the exponential map so that we also have a dilation structure on the Lie group itself. This results in a family of dilations of the form $D_r=\exp (A \ln (r))$ with a diagonalizable linear operator A. The eigenvalues of A are the weights we mentioned above. In accordance with [14], we denote these weights by $\nu _1,\ldots ,\nu _n$ . The trace of A gives us the homogeneous dimension of G. The properties listed below explain this terminology.

Definition 4.4. [14, Definition 3.1.33]

An homogeneous quasi-norm is a continuous non-negative function $G \to [0,\infty ), x \mapsto \vert x \vert $ satisfying:

1. (i) $\vert x^{-1}\vert = \vert x \vert $ ;

2. (ii) $\vert D_r( x )\vert = r \cdot \vert x \vert \text { for all } r>0$ ;

3. (iii) $\vert x \vert =0$ if and only if $x=e$ .

It is called an homogeneous norm if additionally:

1. (iv) for all $x,y \in G$ , it is $\vert xy\vert \leq \vert x \vert + \vert y\vert $ .

Lemma 4.5. [14, Theorem 3.1.39]

If G is an homogeneous Lie group, then there exists an homogeneous norm $\vert \cdot \vert $ on G.

Lemma 4.6. [14, Proposition 3.1.35]

Any two homogeneous quasi-norms $\vert \cdot \vert $ and $\vert \cdot \vert '$ on G are mutually equivalent, in the sense that there exists $a,b>0$ such that for all $g \in G$ , it is $a \vert x \vert ' \leq \vert x\vert \leq b \vert x\vert '$ .

Remark 4.7. To such an homogeneous norm, we can associate the right invariant metric d given by $d(x,y):= \vert x y^{-1}\vert $ .

Lemma 4.8. [14, Proposition 3.1.37]

If $\vert \cdot \vert $ is a homogeneous quasi-norm on a homogeneous Lie group G of dimension n, then the topology induced by the quasi-norm coincides with the Euclidean topology on the underlying set ${\mathbb {R}}^n$ .

Proposition 4.9. [14, §§3.1.3 and 3.1.6]

Let G be an homogeneous Lie group and $\vert \cdot \vert $ an homogeneous norm on G with associated right invariant metric d, then for $x,y \in G$ and $r,s>0$ :

1. (i) $B_r(x) = \{y \in G \mid \vert y x^{-1}\vert < r\} = B_r(e) \cdot x$ ;

2. (ii) $D_r(x y) = D_r(x) D_r(y)$ ;

3. (iii) $D_r(B_s(e)) = B_{r\cdot s}(e)$ ;

4. (iv) $D_r(B_s(x))=B_{r \cdot s}(D_r(x))$ ;

5. (v) $\mu _{G}(B_r(x))= r^{{\mathrm {homdim}}(G)}\cdot \mu _{G}(B_1(e))$ .

Remark 4.10. The fifth point of Proposition 4.9 tells us that an homogeneous Lie group has exact polynomial growth of degree ${\mathrm {homdim}}(G)$ . Since all homogeneous quasi-norms on G are mutually equivalent, the behaviour is independent from the choice of a metric.

Definition 4.11. A hyperplane in an homogeneous Lie group G is the image of a hyperplane in the Lie algebra ${\mathfrak {g}}$ under the exponential map. The set of all hyperplanes in G is denoted by ${\mathcal {H}}(G)$ .

A half-space in an homogeneous Lie group G is the image of a half-space in the Lie algebra ${\mathfrak {g}}$ under the exponential map.

Definition 4.12. A group G is non-crooked if ${\mathcal {H}}(G) \subset {\mathcal {P}}(G)$ is G invariant.

Definition 4.13. A Lie group G is called locally k-step nilpotent if for all $X,Y \in {\mathfrak {g}}$ , we have ${\mathrm {ad}}_X^k(Y) = 0$ .

Theorem 4.14. Let G be an homogeneous Lie group, then the following are equivalent:

1. (a) G is non-crooked;

2. (b) G is $2$ -step nilpotent or abelian;

3. (c) G is locally $2$ -step nilpotent.

For a proof of the theorem, see Appendix B.

Remark 4.15. The notion of locally k-step nilpotent and k-step nilpotent are only equivalent for $k=1$ and $k=2$ . For greater k, the notions are different.

Definition 4.16. We call a window polytopal or of polytopal type if it is the intersection of finitely many half-spaces.

Convention 4.17. If W is polytopal, we can express W as $\bigcap _{i=1}^N P_i^+$ , where each $P_i^+$ is a half-space with opposite half-space $P_i^-$ and bounding hyperplane $P_i$ . This $P_i$ can be chosen such that $P_i \cap W$ has the same dimension as $P_i$ .

Further, we denote the faces of W by $\partial _i W=W \cap P_i$ . In the rest of the paper, we will always use this notation for the half-spaces and hyperplanes associated to a window of polytopal type.

We give a small example that the reader can keep in mind. We will now fix the basics of this example so the reader can follow the steps in the paper.

Example 4.18. We set $G=H={\mathbb {H}}$ , where ${\mathbb {H}}$ denotes the Heisenberg group. We view the underlying set of ${\mathbb {H}}$ as ${\mathbb {R}}^3$ . Further, we set

$$ \begin{align*} \Gamma= \{(a,b,c, a^\ast,b^\ast,c^\ast) \in G \times H \,|\, a,b,c \in {\mathbb{Z}}[\sqrt{2}]\} \end{align*} $$

and $W=[-\tfrac 12,\tfrac 12]\times [-\tfrac 12,\tfrac 12]\times [-\tfrac 12,\tfrac 12]$ , so it is clear that W is non-empty, pre-compact and $\Gamma $ -regular. Also, W is a polytope, in fact, it is a cube.

A dilation structure on ${\mathbb {H}}$ is given by $D_r((x,y,z)) = (r \cdot x, r \cdot y , r^2 \cdot z)$ . Further, an homogeneous norm is given by the Korányi–Cygan norm $\vert (x,y,z)\vert _{{\mathbb {H}}} = ( (x^2+y^2)^2 + z^2 )^{1/4}$ .

4.1. Ergodic theorems for homogeneous Lie groups

In this section, we will learn about the growth of the number of lattice points in the slab under some extra conditions.

Definition 4.19. [17, Definition 1.1]

Let $O_\varepsilon $ , $\varepsilon>0$ be a family of symmetric neighbourhoods of the identity in an lcsc group G, which are decreasing in $\varepsilon $ . Then a family of bounded Borel subsets of finite Haar-measure $(B_t)_{t>0}$ is well rounded with respect to $O_\varepsilon $ if for every $\delta>0$ , there exists $\varepsilon , t_1>0$ such that for all $t \geq t_1$ ,

$$ \begin{align*} \mu_G(O_\varepsilon B_t O_\varepsilon ) \leq (1+\delta) \mu_G\bigg(\bigcap_{u,v \in O_\varepsilon }u B_t v\bigg). \end{align*} $$

In our setup, we will always fix $O_\varepsilon $ as $B_\varepsilon (e)$ , which does not make a difference by [25, Remark 2.3].

Definition 4.20. [17, Definitions 1.4 and 1.5]

Let G be an lcsc group and $B_t$ a family of bounded Borel subsets of finite Haar-measure in X, where X is a space on which G acts. Additionally, let $\beta _{X,B_t}$ be the operator

$$ \begin{align*} \beta_{X,B_t}f(x) := \frac{1}{\mu_{X}(B_t)} \int_{B_t} f(g^{-1}x)\,d\mu_X(g) \end{align*} $$

for $f \in L^2(X)$ . We say that the mean ergodic theorem in $L^2(X)$ holds if

$$ \begin{align*} \bigg\| \beta_{X,B_t}f - \int_X f\,d\mu \bigg\|_{L^2(X)} \to 0 \quad\text{as } t \to \infty \end{align*} $$

for all $f \in L^2(X)$ . We say that the stable mean ergodic theorem in $L^2(X)$ holds if the mean ergodic theorem in $L^2(X)$ holds for the sets

$$ \begin{align*} B_t^+(\varepsilon ) = O_\varepsilon B_t O_\varepsilon \quad\text{and}\quad B_t^-(\varepsilon )=\bigcap_{u,v \in O_\varepsilon }u B_t v \end{align*} $$

for all $\varepsilon \in (0, \varepsilon _1)$ with $\varepsilon _1>0.$

Remark 4.21. From now on, we fix a Haar-measure $\mu _{G \times H}$ , which we assume to be normalized by $\mu _{G \times H /\Gamma }(G \times H / \Gamma ) = 1$ .

Theorem 4.22. [17, Theorem 1.7]

Let G be an lcsc group, $\Gamma \subset G$ a discrete lattice subgroup and $(B_t)_{t>0}$ a well-rounded family of subsets of G. Assume that the averages $\beta _{G/\Gamma , B_t}$ satisfy the stable mean ergodic theorem in $L^2(G/\Gamma )$ . Then

$$ \begin{align*} \lim\limits_{t \to \infty} \frac{\vert \Gamma \cap B_t\vert}{\mu_{G}(B_t)} = 1. \end{align*} $$

To apply this theorem, we have to show that the sets we consider are well rounded and that they satisfy the stable means ergodic theorem. We will give criteria which ensure this.

Lemma 4.23. Let G be an homogeneous Lie group and $(B_t(x))_{t>0}$ be the family of balls of radius t and centre x in G. Then this family is well rounded.

Proof. We have to show that for every $\delta>0$ , there exists some $\varepsilon , t_1>0$ such that for all $t \geq t_1$ ,

$$ \begin{align*} \mu_G(B_\varepsilon (e) B_t(x) B_\varepsilon (e)) \leq (1+\delta) \mu_G\bigg(\bigcap_{u,v \in B_\varepsilon (e)}u B_t(x) v\bigg) \end{align*} $$

holds. We first show that we can choose $\varepsilon $ such that for a constant $k \in (0,t)$ , we have $B_{t-k}(x) \subset \bigcap _{u,v \in B_\varepsilon (e)}u B_t(x) v$ . So let $g \in B_{t-k}(x)$ . Then we can write g as $u u^{-1} g v^{-1} v$ with $u,v \in B_\varepsilon (e)$ and we have to show that $u^{-1} g v^{-1} \in B_t(x)$ .

$$ \begin{align*} d(x, u^{-1}g v^{-1}) &= \vert x v g^{-1} u\vert_G = \vert x v x^{-1} x g^{-1} u\vert_G\\ &\leq \vert x v x^{-1}\vert_G + \vert xg^{-1} \vert_G + \vert u\vert_G \leq c_x(\varepsilon ) + t-k + \varepsilon. \end{align*} $$

Here the last inequality holds by Lemma 5.11. Additionally, we have to choose $\varepsilon $ so small that $k> \varepsilon + c_x(\varepsilon )$ , which is possible since $c(\varepsilon ) \to 0$ as $\varepsilon \to 0$ .

However, $B_\varepsilon (e)B_t(x)B_\varepsilon (e) \subset B_{\varepsilon + t}(x)B_\varepsilon (e)$ . Let $y \in B_{t+\varepsilon }(x)$ and $u \in B_\varepsilon (e)$ , then

$$ \begin{align*} d(x, yu) &= \vert x u^{-1} y^{-1}\vert_G = \vert x u^{-1} x^{-1} x y^{-1} \vert_G\\ &\leq \vert x u ^{-1} x^{-1}\vert_G + \vert x y^{-1} \vert_G \leq c_x(\varepsilon ) + \varepsilon + t. \end{align*} $$

Therefore, $B_\varepsilon (e)B_t(x)B_\varepsilon (e) \subset B_{\varepsilon + t + c_x(\varepsilon )}(x)$ . Hence, we can choose $\varepsilon> 0$ and $k \in (0, t)$ such that

$$ \begin{align*} B_\varepsilon (e) B_t(x) B_\varepsilon (e) \subset B_{\varepsilon + t + c_x(\varepsilon )}(x) \quad\text{and}\quad B_{t-k}(x) \subset \bigcap_{u,v \in B_\varepsilon (e)}u B_t(x) v \end{align*} $$

hold simultaneously. Now we can use that we can calculate the measure of balls in homogeneous Lie groups by Proposition 4.9:

$$ \begin{align*} \mu_G(B_\varepsilon (e) B_t(x) B_\varepsilon (e)) \leq \mu_G(B_{\varepsilon + t + c_x(\varepsilon )}(x)) = (t+\varepsilon +c_x(\varepsilon ))^{{\mathrm{homdim}}(G)} \mu_G(B_1(e)) \end{align*} $$

and

$$ \begin{align*} (t-k)^{{\mathrm{homdim}}(G)} \mu_G(B_1(e)) \leq \mu_G(B_{t-k}(x)) \leq \mu_G\bigg(\bigcap_{u,v \in B_\varepsilon (e)}u B_t(x) v\bigg). \end{align*} $$

Combining the arguments, we see that we have to choose $\varepsilon $ , k and $t_1$ such that for all $t> t_1$ ,

$$ \begin{align*} \bigg(\frac{(t+\varepsilon +c_x(\varepsilon ))}{(t-k)}\bigg)^{{\mathrm{homdim}}(G)} \leq (1+\delta).\\[-42pt] \end{align*} $$

Lemma 4.24. Let G be an homogeneous Lie group and $(B_r(x))_{t>0}$ a constant family of balls in G. Then this family is well rounded.

Proof. We have already seen in the proof of Lemma 4.23 that $\bigcap _{u,v \in B_\varepsilon (e)} u B_r(x) v$ contains a ball of the form $B_{r-k}(x)$ for any $k\in (0,t)$ if we choose $\varepsilon $ accordingly. However, $B_\varepsilon (e)B_r(x)B_\varepsilon (e)$ is contained in a ball $B_{r+\varepsilon +c_x(\varepsilon )}(x)$ and therefore has finite measure. Choosing $\varepsilon $ accordingly, we are done.

Now what is left to show is that the stable mean ergodic theorem holds for our families of sets. To do so, we use [15, Theorem 3.33] which tells us that we have to check that our families are Følner sequences. Alternatively, see the work by Nevo [40], especially, Step I in the proof of Theorem 5.1 is exactly what we need.

Definition 4.25. (Følner sequences)

Let G be an lcsc group acting on a measure space $(X,\mu )$ . A sequence $F_1, F_2, \ldots $ of subsets of finite, non-zero measure in X is called a (right) Følner sequence if for all $g \in G$ ,

$$ \begin{align*} \lim\limits_{i \to \infty}\frac{\mu(F_i g \triangle F_i)}{\mu(F_i)} = 0. \end{align*} $$

Lemma 4.26. Let $G \times H$ be a product of homogeneous Lie groups, $\Gamma \subset G \times H$ a lattice, $(B_t^G(e))_{t>0}$ a family of balls in G and $(B_r^H(x))_{t>0}$ a constant family of balls in H. The family $(B_t^G(e) \times B_r^H(x))_{t>0}/\Gamma $ is a Følner sequence for $G \times H$ acting on $(G\times H)/ \Gamma $ .

Proof. We use Proposition 3.2, which tells us that for every $r>0$ and every ${x \in H}$ , we find a compact $K \subset G$ such that $(K \times B_r^H(x))\Gamma = G \times H$ . Additionally, since every compact set K is contained in some $B_t^G(e)$ , for t large enough, we get that $(B_t^G(e) \times B_r^H(x)) \Gamma = G \times H$ . This also holds if we consider balls $B_t^G(g)$ instead of $B_t^G(e)$ . Therefore, we have for every $(g,h) \in G \times H$ that there exists a $t_{g,h}>0$ such that $(B_t^G(g) \times B_r^H(xh)) \Gamma = G \times H$ and so

$$ \begin{align*} \lim\limits_{t \to \infty} \mu_{(G \times H)/\Gamma}((B_t^G(g) \times B_r^H(xh))_{(G\times H)/\Gamma} \triangle (B_t^G(e) \times B_r^H(x))_{(G\times H)/ \Gamma}) = 0 \end{align*} $$

for all $(g,h) \in G \times H$ .

5. Growth of the complexity function

In this section, we prove our main theorem, modulo Theorem 6.1 which we will prove in §6.

Theorem 5.1. Let $\Lambda (G,H, \Gamma , W)$ be a model set, where G is an homogeneous Lie group and H is a non-crooked homogeneous Lie group. Further, let $W \subset H$ be a non-empty, precompact window of polytopal type with bounding hyperplanes $P_1,\ldots , P_N$ such that $P_i$ has trivial stabilizer and that $P_i \cap \Gamma _H = \emptyset $ for all $i \in \{1,\ldots , N\}$ . Then for the complexity function p of $\Lambda $ , we have

$$ \begin{align*} p(r) \asymp r^{{\mathrm{homdim}}(G)\dim(H)}. \end{align*} $$

Notice that the condition of $\Gamma $ -regularity is hidden in the stronger condition that all the hyperplanes $P_i$ do not intersect $\Gamma _H$ . The condition that the $P_i$ have trivial stabilizer simplifies the problem since otherwise, we had to address the effects of the stabilizer. The effect of a non-trivial stabilizer is similar to the Euclidean case, for which we refer to [28].

The proof of Theorem 5.1 will be divided into establishing an upper bound and a lower bound. For the lower bound, we have to put in much more effort.

5.1. Upper bound of the growth

For an upper bound, we consider the decomposition of the window $W \setminus \bigcup _{x\in {\mathcal {S}}(r)} x\partial W$ . We will show that counting the connected components is an upper bound for the number of acceptance domains. Then we will use the theory of real hyperplane arrangements, which gives us an upper bound for our counting.

Lemma 5.2. For a model set $\Lambda (G,H,\Gamma ,W)$ , we have

$$ \begin{align*} \vert A_r^H\vert \leq \#\pi_0 \bigg( W \setminus \bigcup_{\mu\in{\mathcal{S}}_r} \mu\partial W\bigg). \end{align*} $$

Proof. By Theorem 2.2, we know that the acceptance domains $W_r(\unicode{x3bb} )$ tile the window W and that they are disjoint. Further, for every $A_r(\unicode{x3bb} )$ , we know that

$$ \begin{align*} A_r(\unicode{x3bb}) \subset W_r(\unicode{x3bb}). \end{align*} $$

So

$$ \begin{align*} \partial W_r(\unicode{x3bb}) &= \partial \bigg( \bigg(\bigcap_{\mu \in {\mathcal{S}}_r(\unicode{x3bb})}\mu \mathring{W}\bigg)\cap \bigg(\bigcap_{\mu \in {\mathcal{S}}_r(\unicode{x3bb})^{\mathrm{C}}} \mu W^{\mathrm{C}} \bigg) \bigg)\\ &\subset \bigg(\bigcup_{\mu \in {\mathcal{S}}_r(\unicode{x3bb})}\mu \partial \mathring{W}\bigg) \cup \bigg(\bigcup_{\mu \in {\mathcal{S}}_r(\unicode{x3bb})^{\mathrm{C}}} \mu \partial W^{\mathrm{C}} \bigg) = \bigcup_{\mu \in S_r} \mu \partial W. \end{align*} $$

Therefore, every connected component of $ W \setminus \bigcup _{\mu \in {\mathcal {S}}_r} \mu \partial W$ is contained in some $W_r(\unicode{x3bb} )$ , so

$$ \begin{align*} \vert A^H_r\vert = \vert W_r \vert \leq \#\pi_0 ( W \setminus \bigcup_{\mu\in{\mathcal{S}}_r} \mu\partial W).\\[-46pt] \end{align*} $$

Lemma 5.3. For a model set $\Lambda (G,H,\Gamma , W)$ with polytopal window $W \subset H$ , we have

$$ \begin{align*} \#\pi_0 \bigg( W \setminus \bigcup_{\mu\in{\mathcal{S}}_r} \mu\partial W\bigg) \leq \# \pi_0 \bigg( H \setminus \bigcup_{\mu\in{\mathcal{S}}_r} \bigcup_{i=1}^N \mu P_i\bigg). \end{align*} $$

Proof. Since $\bigcup _{\mu \in {\mathcal {S}}_r} \mu \partial W \subset \bigcup _{\mu \in {\mathcal {S}}_r} \bigcup _{i=1}^N \mu P_i$ , we have

$$ \begin{align*} \#\pi_0 \bigg( W \setminus \bigcup_{\mu\in{\mathcal{S}}_r} \mu\partial W\bigg) \leq \# \pi_0 \bigg( W \setminus \bigcup_{\mu\in{\mathcal{S}}_r} \bigcup_{i=1}^N \mu P_i\bigg). \end{align*} $$

Since $e \in {\mathcal {S}}_r$ for all r, we have $\partial W \subset \bigcup _{\mu \in S_r}\bigcup _{i=1}^N \mu P_i$ such that all regions inside W stay the same if we increase W to H. If we add the regions outside of W, we therefore get

$$ \begin{align*} \#\pi_0 \bigg( W \setminus \bigcup_{\mu\in{\mathcal{S}}_r} \bigcup_{i=1}^N \mu P_i\bigg) \leq \# \pi_0 \bigg( H \setminus \bigcup_{\mu\in{\mathcal{S}}_r} \bigcup_{i=1}^N \mu P_i\bigg).\\[-46pt] \end{align*} $$

By Lemma 4.8, the topology on H is the same as on ${\mathbb {R}}^{\dim (H)}$ and we additionally assumed H to be non-crooked. So the problem of counting the connected components is a well-known problem from the theory of real hyperplane arrangements. A general upper bound for the number of connected components has been known for a long time and first appeared in [41] by Schläfli, see also [12, Theorem 1.2]. For an arrangement ${\mathcal {H}} \subset {\mathbb {R}}^n$ consisting of k different hyperplanes, we get the general upper bound

$$ \begin{align*} \sum_{i=0}^n \begin{pmatrix} k \\ i\end{pmatrix} \asymp k^n. \end{align*} $$

In our case, $n= \dim (H)$ and $k= \vert {\mathcal {S}}(r)\vert $ . We know from Proposition 3.1 that ${\vert {\mathcal {S}}(r)\vert \asymp r^{{\mathrm {homdim}}(G)}}$ . Combining these results yields

$$ \begin{align*} p(r) = \vert A_r^H\vert \leq \#\pi_0 \bigg( H \setminus \bigcup_{\mu\in{\mathcal{S}}(r)} \bigcup_{i=1}^N \mu P_i\bigg) \ll \vert {\mathcal{S}}(r)\vert^{\dim(H)} \asymp r^{{\mathrm{homdim}}(G) \cdot \dim (H)}. \end{align*} $$

5.2. Lower bound of the growth

We fix some parameters of the window which will help us in proving Theorem 5.1.

Definition 5.4. For a given polytopal window W, we fix the following parameters:

1. (i) a centre of the window $c_W \in W$ such that $\inf \{r \in {\mathbb {R}} \mid B_r(c_W) \subset W \}$ is maximal;

2. (ii) the inner radius of the window $I_W:=\sup \{r \in {\mathbb {R}} \mid B_r(c_W) \subset W\}$ ;

3. (iii) the outer radius of the window $O_W:=\inf \{r \in {\mathbb {R}}\mid W \subset B_r(c_W)\}$ ;

4. (iv) the size of $\partial _i W$ , respectively the inner radius of face i,

   $$ \begin{align*} F_i:=\sup\{r \in {\mathbb{R}} \mid \text{there exists } p \in P_i: B_r(p)\cap \partial_i W = B_r(p) \cap P_i\} \end{align*} $$
   and the minimum of all the sizes of the faces
   $$ \begin{align*} F_W:=\min\{F_i \mid i \in \{1,\ldots ,N\}\}; \end{align*} $$

5. (v) for each face $\partial _i W$ , a face centre $p_i \in \partial _i W$ such that $B_{F_W}(p_i)\cap \partial _i W= B_{F_W}(p_i)\cap P_i$ .

We will use these parameters in our proof later. The centres may not be unique, but we fix a choice for the rest of the argument. Further, we need to widen the definition of parallel a little since we are only interested in intersections inside a bounded region.

Definition 5.5. Let $B \subset H$ be a bounded region and $P_1, P_2$ two hyperplanes in H. We call $P_1$ and $P_2$ almost parallel with respect to B if $P_1\cap P_2 \cap B = \emptyset $ .

The aim is now to find a region inside W for which it makes no difference if it is divided by a face $\partial _i W$ or by the whole hyperplane $P_i$ . Further, we wish to get a one-to-one correspondence between the connected components and the acceptance domains in this small region.

Definition 5.6. Let $B \subset H$ be a bounded region. For $s \in H$ , we say $s \partial _i W$ cuts B fully if

$$ \begin{align*} (s \partial_i W) \cap B = (s P_i) \cap B \neq \emptyset. \end{align*} $$

If additionally

$$ \begin{align*} (s P_i^+) \cap B = (s W) \cap B \neq \emptyset, \end{align*} $$

we say $s \partial _i W$ cuts B all-round.

Remark 5.7. An all-round cut is always a full cut, but the converse is false, see Figure 3.

Figure 3 On the left, $\partial _i W$ cuts B fully and all-round, and on the right, $\partial _i W$ cuts B fully but not all-round.

Additionally to decreasing the area of interest, we will decrease the set from which we operate on the window. Instead of considering all elements from ${\mathcal {S}}_r$ , we define for each face a subset $U_i(r) \subset {\mathcal {S}}_r$ . The $U_i(r)$ will be defined such that we only obtain all-round cuts and get a one-to-one correspondence between the connected components and the acceptance domains.

Definition 5.8. Let $(k,h) \in {\mathbb {R}}^2$ . The region we will consider is $B_h(c_W)$ and the set from which we operate is ${U_i:= B_k(c_W p_i^{-1})}$ for all $i\in \{1,\ldots ,N\}$ . If the following conditions are fulfilled, we call $(k,h)$ a good pair:

1. (i) $0 < k <h$ ;

2. (ii) $h < I_W$ , therefore, $B_h(c_W) \subset W$ ;

3. (iii) $\text {for all } a\in B_{O_W}(e)$ , $x \in B_{2h}(e)$ : $\vert a x a^{-1}\vert _H \leq F_W$ ;

4. (iv) $\text {for all } i \in \{1,\ldots ,N\}$ , $\text {for all } s \in U_i$ , $(s P_i^+) \cap B_h(c_W) = (s W) \cap B_h(c_W)$ .

Remark 5.9. Observe that if $(k,h)$ is a good pair, then $(k',h)$ is a good pair for all ${0 < k' < k}$ .

Proposition 5.10. A good pair exists.

For the proof, we need some preparation. It will begin after Corollary 5.19.

Lemma 5.11. Let G be an homogeneous Lie group and $x \in G$ fixed. Then for all $\varepsilon>0$ , there exists $\delta (x)>0$ such that for $u \in B_{\delta (x)}(e)$ ,

$$ \begin{align*} x u x^{-1} \in B_{\varepsilon }(e). \end{align*} $$

Further, if $\vert x \vert \leq k$ , then there exists a $\delta '(k)>0$ such that for $u \in B_{\delta '(k)}(e)$ ,

$$ \begin{align*} x u x^{-1} \in B_{\varepsilon }(e). \end{align*} $$

Proof. Using the Baker–Campbell–Hausdorff formula, we get

$$ \begin{align*} x u x^{-1} &= (x + u + \tfrac{1}{2}[x,u]+\tfrac{1}{12}([x,[x,u]]-[u,[x,u]])-\cdots) x^{-1}\\ &= (x + u + \tfrac{1}{2}[x,u]+\tfrac{1}{12}([x,[x,u]]-[u,[x,u]])-\cdots)\\ &\quad - x + \tfrac{1}{2}[(x + u + \tfrac{1}{2}[x,u]+\tfrac{1}{12}([x,[x,u]]-[u[x,u]])-\cdots) ,x^{-1}]+\cdots\\ &= u +B(x,u), \end{align*} $$

where $B(x,u)$ only contains terms which include $[u,x]$ . The continuity of the Lie bracket implies the claim. Be aware that we work in exponential coordinates here, as explained in §4, so formally, we should write $\exp (x)$ and $\exp (u)$ instead of x and u.

Lemma 5.12. Let $(k,h)$ fulfil conditions (i) and (iii) of Definition 5.8, then for any ${i\in \{1,\ldots ,N\}}$ and for every $s \in U_i$ , it holds that $s P_i $ cuts $B_h(c_W)$ fully.

Proof. First, we show that for all $s \in U_i$ , we get $s P_i \cap B_h(c_W) \neq \emptyset $ . We can write ${s=a \cdot c_W \cdot p_i^{-1}}$ with $a \in B_k(e)$ . Then

$$ \begin{align*} d(s \cdot p_i, c_W)= \vert a \cdot c_W \cdot p_i^{-1} \cdot p_i \cdot c_W^{-1}\vert = \vert a \vert < k < h. \end{align*} $$

Now we need to show that $s \partial _i W \cap B_h(c_W) = s P_i \cap B_h(c_W)$ . This is equivalent to

$$ \begin{align*} \partial_i W \cap s^{-1} B_h(c_W) = P_i\cap s^{-1} B_h(c_W). \end{align*} $$

The inclusion $\subseteq $ is obvious since $\partial _i W \subset P_i$ . We show that $s^{-1} B_h(c_W) \subseteq B_{F_W}(p_i)$ , then the claim follows from the definition of $p_i$ and $F_W$ . Let $x \cdot c_W \in B_h(c_W)$ be an arbitrary element and $s=a \cdot c_W \cdot p_i^{-1}$ as above.

$$ \begin{align*} d(s^{-1} x c_W, p_i)= \big\vert \hspace{-0.45cm}\underbrace{p_i c_W^{-1}}_{=: y \in B_{O_W}(e) } \cdot \underbrace{a^{-1} x_{}}_{\in B_{h + k}(e)} \cdot \underbrace{c_W p_i^{-1}}_{=y^{-1}}\big\vert \leq F_W. \end{align*} $$

The inequality follows by condition (iii) of Definition 5.8.

From the proof, we can extract the following corollary.

Corollary 5.13. Let $i\in \{1,\ldots ,N\}$ . For every $s \in U_i$ , we have that $s P_i $ intersects $B_k(c_W)$ non-trivially.

Corollary 5.14. Let $(k,h)$ fulfil conditions (i), (iii) and (iv) of Definition 5.8, then for any $i\in \{1,\ldots ,N\}$ and for every $s \in U_i$ , $s P_i $ cuts $B_h(c_W)$ all-round holds.

We will also need the definition of an intersection angle between two hyperplanes since we will show that by acting with a small element, we can only rotate a plane a little.

Definition 5.15. The angle between two hyperplanes P and Q in ${\mathbb {R}}^d$ with normals $n_P$ and $n_Q$ , both normalized, is given by

$$ \begin{align*} \sphericalangle(P,Q) := \cos^{-1} (\vert \langle n_P \cdot n_Q \rangle \vert). \end{align*} $$

For $i,j \in \{1,\ldots ,N\}$ with $i \neq j$ , we denote by $\alpha _{ij}$ the angle between $c_Wp_i^{-1} P_i$ and $c_W p_j^{-1} P_j$ , that is,

$$ \begin{align*} \alpha_{ij}:=\sphericalangle(c_W p_i^{-1} P_i, c_W p_j^{-1} P_j). \end{align*} $$

Remark 5.16. In the definition, we use $c_W p_i^{-1} P_i$ instead of $P_i$ . Since this plane is sort of the prototype for the family $U_i P_i$ , all the other planes from this family then result from an action with a small element. Here, $u \in U_i$ is of the form $a c_Wp_i^{-1}$ with $a\in B_k(e)$ .

Convention 5.17. We choose $i_1,\ldots , i_{\dim (H)}$ such that

$$ \begin{align*} \bigcap_{l=1}^{\dim(H)} c_W p_{i_l}^{-1} P_{i_l}= \{c_W\}. \end{align*} $$

So this is a set of hyperplanes in which each intersection of k hyperplanes has dimension $\dim (H)-k$ . From now on, we fix such a family and denote it by ${\mathcal {F}}$ . Without loss of generality, ${\mathcal {F}} = \{P_1,\ldots ,P_{\dim (H)}\}$ .

Lemma 5.18. For all $r>0$ , there exists $\beta (r)$ , with $\beta (r) \to 0$ for $r \to 0$ , such that for all $x \in B_r(e) \subset H$ and any hyperplane P, we have $\sphericalangle (x P, P) \leq \beta (r)$ .

Proof. Since H is a non-crooked homogeneous Lie group, we know that $xP$ is again a hyperplane. So let

$$ \begin{align*} P= \bigg\{a + \sum_{i=1}^n t_i v_i \mid t_i \in {\mathbb{R}}\bigg\}, \end{align*} $$

where $a, v_i \in {\mathbb {R}}^n$ . By the form of the group action, which we discuss in Appendix B.1, we know that $xP$ is of the form

$$ \begin{align*} xP = (f_1(x,P),\ldots ,f_n(x,P))^{\mathrm{T}} \end{align*} $$

with $f_i$ polynomials of a special form, namely

$$ \begin{align*} f_i(x,P) = x_i + P_i +\sum_{k=1}^n\sum_{\substack{\alpha_1,\ldots ,\alpha_n \in {\mathbb{N}} \\ \sum \alpha_i \neq 0}} c_{k,\alpha_1,\ldots ,\alpha_n} P_k x_1^{\alpha_1}\cdots x_n^{\alpha_n}. \end{align*} $$

The direction vectors are those from P plus some deviation which depends on x. If x gets smaller, the two planes are getting closer to being parallel.

Corollary 5.19. For all $r>0$ , there exists $\beta (r)$ , with $\beta (r) \to 0$ for $r \to 0$ , such that for all $x, y \in B_r(e) \subset H$ and any hyperplane P, we have $\sphericalangle (x P, y P) \leq 2\beta (r)$ .

Proof of Proposition 5.10

By Lemma 5.11, there exists an upper bound $b_1$ on h such that for all $a\in B_{O_W}(e)$ , $x \in B_{2h}(e)$ : $\vert a x a^{-1}\vert _H \leq F_W$ . Set $h':=\min \{b_1, {I_W}/{2}\}$ and set $k':= {h'}/{2}$ , then conditions (i), (ii) and (iii) from Definition 5.8 are fulfilled.

By Lemma 5.12, for any $i \in \{1,\ldots ,N\}$ and all $s \in B_{k'}(c_Wp_i^{-1})$ , we have $sP_i$ cuts $B_{h'}(c_W)$ fully, this also holds for all $h \leq h'$ .

Now assume that there is a cut that is full but not all-round; therefore,

$$ \begin{align*} s P_i^+ \cap B_{h'}(c_W) \neq sW \cap B_{h'}(c_W). \end{align*} $$

To be more precise, we have $sW \cap B_{h'}(c_W) \subsetneq s P_i^+ \cap B_{h'}(c_W)$ since $sW \subset sP_i^+$ . Let

$$ \begin{align*} b_{s}^i:= \inf\{r \in {\mathbb{R}} \mid \text{there exists } x \in B_r(c_W) : x \in s P_i^+, x \notin sW\}. \end{align*} $$

We see that $b_s^i \neq 0$ since $sW$ is a polytope with non-empty interior. Now set

$$ \begin{align*} h:=\min\big\{h', \inf_{s\in B_{k'}(c_Wp_i^{-1})}\{b_s^i\}\big\} \end{align*} $$

and $k={h}/{2}$ . The last thing to observe now is that the infimum over the $b_s^i$ is not zero. If it were zero, this would mean that the polytope $sW$ could become arbitrarily thin such that only an even smaller ball would fit in. However, this cannot be the case since we have seen that we can only rotate the bounding hyperplanes only by a small amount.

Convention 5.20. From now on, let $(k,h)$ be a good pair.

Observe that $U_i \subset WW^{-1}$ for all $i\in \{1,\ldots ,N\}$ . Further, notice that we operate differently on the different hyperplanes that bound W. Te $U_i$ may overlap but they are not equal. Additionally, we have chosen $B_h(c_W)$ so that for each of the hyperplanes, it does not make a difference if we operate on the face $\partial _i W$ or on the hyperplane $P_i$ .

Now we will reconsider the dependence of the growing parameter r and the lattice $\Gamma $ .

Definition 5.21. Set $U_i(r):= \pi _H((B_r^G(e) \times U_i)\cap \Gamma )$ which is a finite subset of $U_i$ .

Remark 5.22. Observe that $U_i(r)$ is a subset of the r-slab ${\mathcal {S}}_r$ since $U_i \subset WW^{-1}$ .

Proposition 5.23. The number of connected components of $ B_h(c_W) \setminus \bigcup _{i=1}^N \bigcup _{s \in U_i(r)} s \partial _i W$ is a lower bound of the number of acceptance domains $\vert A_r^H \vert $ , that is,

$$ \begin{align*} \# \pi_0 \bigg( B_h(c_W) \setminus \bigcup_{i=1}^N \bigcup_{s \in U_i(r)} s \partial_i W \bigg) \leq \vert A_r^H \vert. \end{align*} $$

Proof. Recall that a pre-acceptance domain $A_r^H(\unicode{x3bb} )$ is contained in an acceptance domain $W_r(\unicode{x3bb} )$ . Let C be a connected component of $B_h(c_W) \setminus \bigcup _{i=1}^N \bigcup _{s \in U_i(r)} s \partial _i W$ . By Lemma 5.12, we can replace the faces by the hyperplanes without changing the connected components in $B_h(c_W)$ , so we consider ${B_h(c_W) \setminus \bigcup _{i=1}^N \bigcup _{s \in U_i(r)} s P_i}$ .

We show that if an acceptance domain intersects a connected component of $B_h(c_W) \setminus \bigcup _{i=1}^N \bigcup _{s \in U_i(r)} s P_i$ , it is fully contained in it. Let $C'$ be another connected component of $B_h(c_W) \setminus \bigcup _{i=1}^N \bigcup _{s \in U_i(r)} s P_i$ and assume that $C \cap W_r(\unicode{x3bb} ) \neq \emptyset \neq C' \cap W_r(\unicode{x3bb} )$ . Between C and $C'$ is a hyperplane $s P_i$ for some $i\in \{1,\ldots ,N\}$ and $s \in U_i(r)$ . Therefore, $C \subset s \mathring {P^+}$ and $C'\subset s \mathring {P^-}$ , or the other way around. Additionally, since the cut $s\partial _i W$ is all-round, we get that $C \subset s \mathring {W}$ and $C' \subset s W^{\mathrm {C}}$ , or the other way around. However, either $W_r(\unicode{x3bb} ) \subset s\mathring {W}$ or $W_r(\unicode{x3bb} ) \subset sW^{\mathrm {C}}$ , which is a contradiction.

It remains to find a combinatorial argument for counting the connected components of

$$ \begin{align*} B_h(c_W) \setminus \bigcup_{i=1}^N \bigcup_{s \in U_i} s \partial_i W=B_h(c_W) \setminus \bigcup_{i=1}^N \bigcup_{s \in U_i} s P_i, \end{align*} $$

which yields a lower bound by Proposition 5.23. This will be done in the next section.

In the rest of the section, we will prove the following proposition, which gives us the tools for the combinatorics in the next section.

Proposition 5.24. There exists a good pair $(k,h)$ such that:

1. (a) for all $I \subset \{1,\ldots ,N\}$ with $\vert I \vert = \dim (H)$ and all $u_{1} \in U_{i_1},\ldots ,u_{{\dim (H)}} \in U_{i_{\dim (H)}}$ , we get

   $$ \begin{align*} u_{1} P_{i_1} \cap \cdots \cap u_{{\dim(H)}} P_{i_{\dim(H)}} = \{s\}\quad\text{where } s \in B_h(c_W); \end{align*} $$

2. (b) for every constant $c>0$ and all $s \in H$ , there is a $r_0$ such that for all $r> r_0$ , we get that

   $$ \begin{align*} \vert \{u \in U_i(r) \mid s \in u P_i\}\vert \leq c \vert U_i(r) \vert. \end{align*} $$

Lemma 5.25. For $i,j \in \{1,\ldots ,\dim (H)\}$ , $i \neq j$ , there exists a good pair $(k,h)$ such that for all $u \in U_i=B_k(c_Wp_i^{-1}), v \in U_j$ , we have $u P_i$ and $vP_j$ are not almost parallel with respect to $B_h(c_W)$ .

Proof. Fix some $i,j \in \{1,\ldots ,N\}$ with $i \neq j$ . By Corollary 5.13, all the $u P_i$ , $v P_j$ with $u \in U_i$ , $v \in U_j$ intersect $B_k(c_W)$ .

Further, we can control the angle between the two hyperplanes by Lemma 5.18 so that for all $ u \in U_i, v \in U_j $ ,

$$ \begin{align*} \sphericalangle(u P_i, v P_j) \geq \sphericalangle(P_i, P_j) - \sphericalangle(u P_i, P_j) - \sphericalangle(P_i, v P_j)\geq \alpha_{ij} - 2 \beta(k), \end{align*} $$

where $\beta (k)$ is from Lemma 5.18. We can choose k so small such that $0 < \alpha _{ij} - 2 \beta (k) < {\pi }/{2}$ , which means that the hyperplanes cannot be parallel so they intersect somewhere. For two hyperplanes that intersect the same ball of radius k and which intersect in at least a given angle, there is a bound for the intersection to the centre point of the ball:

$$ \begin{align*} c(k):= k \bigg( 1+\frac{1}{\tan(({\alpha_{ij}-2 \beta(k)})/{2})}\bigg). \end{align*} $$

The idea of how to establish this bound is to consider the space which is orthogonal to the intersection of $u P_i$ and $v P_j$ , and contains $c_W$ . Then one can argue in a two-dimensional plane.

The bound $c(k)$ goes to zero if k goes to zero, so we can choose k so small that $c(k) < h$ . Therefore, the two planes intersect inside $B_h(c_W)$ .

Corollary 5.26. There exists a good pair $(k,h)$ such that for all $u_i \in U_{i}$ and ${i \in \{1,\ldots ,\dim (H)\}}$ , we can find some $x \in B_h(c_W)$ such that

$$ \begin{align*} \bigcap_{i=1}^{\dim(H)} u_i P_i = \{x\}. \end{align*} $$

Proof. By the choice of the family ${\mathcal {F}}$ , we know that $\bigcap _{i=1}^{\dim (H)} c_W p_{i}^{-1} P_{i}= \{c_W\}$ . We will first show that there is a $k_0$ such that for all $0< k \leq k_0$ , we also get a zero-dimensional intersection inside $B_h(c_W)$ if we replace $c_W p_i^{-1}$ by $u_i \in U_i=B_k(c_Wp_i^{-1})$ .

This intersection behaviour means that if we choose some vector $v \parallel c_Wp_i^{-1}P_i$ , then $v \parallel c_Wp_j^{-1}P_j$ can maximally hold for all but one j since otherwise, the intersection of all hyperplanes would end up in a line instead of a point. We have to choose $k_0$ such that for all $i\in \{1,\ldots ,\dim (H)\}$ and all $v \parallel u_i P_i$ , $u_i \in U_i$ , there exists a $j\in \{1,\ldots ,\dim (H)\}\setminus \{i\}$ and a $u_j \in U_j$ such that $v \nparallel u_jP_j$ . Since operating with an element from $U_i$ only rotates the hyperplane a little, it is possible to find such a $k_0$ and then the property also holds for all k smaller than $k_0$ .

Now we have to check that the intersection point also lies inside of $B_h(c_W)$ . We do this stepwise. It is clear that $\bigcap _{i=1}^{\dim (H)} c_W p_{i}^{-1} P_{i}= \{c_W\}$ and $c_W \in B_h(c_W)$ . Now we change $c_W p_1^{-1}$ to some $u_1 \in U_1$ and consider $u_1 P_1 \cap \bigcap _{i=2}^{\dim (H)} c_W p_{i}^{-1} P_{i} =\{x_1\}$ . We already know that $\bigcap _{i=2}^{\dim (H)} c_W p_{i}^{-1} P_{i}$ is a subspace of dimension $1$ and that $u_1 P_1$ intersects this subspace. Since $u_1= a_1 c_W p_1^{-1}$ with $a_1\in B_k(e)$ , the plane $u_1 P_1$ is just a small shift, which follows from the form of the group action that we explained in §4, and a small rotation away from $c_W p_1^{-1} P_1$ , which follows from Lemma 5.18. Therefore, $d(x_1, c_W) < \varepsilon _1(k)$ , where $\varepsilon _1$ depends on k and goes to zero if k goes to zero. We can iterate this process and get a new solution on each step until we end at $x_d$ , $d=\dim (H)$ , where we have

$$ \begin{align*} d(x_d,c_W)&< d(x_d, x_{d-1})+ d(x_{d-1},x_{d-2})+\cdots + d(x_2,x_1)+d(x_1,c_W)\\ & < \sum_{i=1}^d \varepsilon _i(k) =:\varepsilon (k). \end{align*} $$

So by choosing k such that $\varepsilon (k)<h$ , we get the claim. This is possible since $\varepsilon (k) \to 0$ for $k \to 0$ .

The corollary tells us that all intersections result in a single point in $B_h(c_W)$ , but it is not clear that different choices of $u_j$ result in different intersection points. This is a major difference to the Euclidean case since here, the action is just translation, so by acting on a hyperplane, we get a parallel hyperplane, which then either is still the same hyperplane or does not intersect the original hyperplane at all.

To prove part (b) of Proposition 5.24, we need Theorem 4.22. We can use it by the discussion in §4.1.

Lemma 5.27. Consider a family $U_i(r) \cdot P_i$ . For any constant $c>0$ and all $s \in H$ , there is an $r_0$ such that for all $r \geq r_0$ , we get that

$$ \begin{align*} \vert\{u \in U_i(r) \mid s \in u P_i \}\vert \leq c \cdot \vert U_i(r) \vert. \end{align*} $$

Proof. Let $u \in U_i(r)$ such that $s\in u P_i$ . This implies that $u^{-1} \in P_i s^{-1}$ , so $u \in U_i(r) \cap (P_i s^{-1})^{-1}$ . So the question is how many elements are in $U_i(r) \cap (P_i s^{-1})^{-1}$ compared with the number of elements in $U_i(r)$ . To get an estimate via the Haar measure, we have to thicken $(P_i s^{-1})^{-1}$ since it is a subset of lower dimension. We consider an $\varepsilon $ -strip around the set, so we choose a finite set $A(\varepsilon ) \subset (P_is^{-1})^{-1}\cap U_i$ such that

$$ \begin{align*} U_i \cap (P_i s^{-1})^{-1} \subset \bigcup_{p \in A(\varepsilon )}B_\varepsilon (p) \end{align*} $$

and further let $S_\varepsilon := U_i(r) \cap \bigcup _{p \in A(\varepsilon )} B_\varepsilon (p)$ . We have seen that we can use Theorem 4.22, so for every $\delta>0$ and r large enough,

$$ \begin{align*} \delta &\geq \vert \vert U_i(r)\vert - \mu_{G \times H}(B_r(e) \times U_i) \vert = \vert \vert U_i(r)\vert - \mu_{G}(B_r(e)) \mu_{H}(U_i) \vert\\ &= \vert \vert U_i(r)\vert - r^{{\mathrm{homdim}}(G)}\mu_{G}(B_1(e)) \mu_{H}(U_i)\vert. \end{align*} $$

Since $S_\varepsilon $ is a finite union of balls, we can use the same argument for all the balls simultaneously and get for $\delta>0$ that

$$ \begin{align*} \lim\limits_{r \to \infty} \frac{\vert U_i(r) \cap (P_i s^{-1})^{-1}\vert }{\vert U_i(r)\vert} &< \lim\limits_{r \to \infty}\frac{\vert S_\varepsilon \vert}{\vert U_i(r)\vert} = \frac{\sum_{p \in A(\varepsilon )} r^{{\mathrm{homdim}}(G)}\mu_{G}(B_1(e))\mu_{H}(B_\varepsilon (p))}{r^{{\mathrm{homdim}}(G)}\mu_{G}(B_1(e))\mu_{H}(U_i)}\\ &= \frac{\vert A(\varepsilon ) \vert \cdot \mu_{H}(B_\varepsilon (e))}{\mu_{H}(U_i)} \xrightarrow{\varepsilon \to 0} 0.\\[-42pt] \end{align*} $$

6. Combinatorics

The aim of this section is to give a lower bound for the number of connected components of

$$ \begin{align*} B_h(c_W) \setminus \bigcup_{i=1}^N \bigcup_{s \in U_i(r)} s P_i, \end{align*} $$

under some conditions on the family $s P_i$ . This will fill the gap we left in the last section. To do so, we will give a short introduction to the theory of hyperplane arrangements and fix the common notation for this setup. To do so, we will follow the lines of Dimca [12] and Stanley [46]. Furthermore, we will consider Beck’s theorem which was first proved in [6], but also follows from the Szémeredi–Trotter theorem [49]. An easier proof for the Szémeredi–Trotter theorem can be found in the paper by Szekely [48]. We leave it to the reader to see that the two versions are equivalent.

Theorem 6.1. (Higher dimensional local dual of Beck’s theorem)

Let ${\mathcal {H}}$ be a hyperplane arrangement in ${\mathbb {R}}^d$ and let $B \subset {\mathbb {R}}^d$ be convex. Further, let ${\mathcal {H}}$ consist of d families $F_1,\ldots ,F_d$ with $\vert F_i \vert = {n}/{d}$ and such that for all $(f_1,\ldots ,f_d) \in F_1 \times \cdots \times F_d$ , we have $B \cap \bigcap _{i=1}^d f_i = \{p\}$ for some point $p \in B$ . Moreover, assume that there is a constant $c< {1}/{100}$ such that at most $c \cdot \vert F_i \vert $ hyperplanes from $F_i$ can intersect in one point. Then there exists a constant $c_d$ , depending on the dimension d, such that the number of intersection points in B exceeds $c_d \cdot n^d$ , that is, $\vert F_{0,B} \vert \geq c_d \cdot n^d$ .

Corollary 6.2. In the situation of Theorem 5.1 and Proposition 5.24,

$$ \begin{align*} \# \pi_0 \bigg( B_h(c_W) \setminus \bigcup_{i=1}^N \bigcup_{s \in U_i(r)} s P_i \bigg) \gg r^{{\mathrm{homdim}}(G) \cdot \dim(H)}. \end{align*} $$

Proof. Notice that $B_h(c_W)$ is convex and the family we constructed in §5.2 fulfils the requirements in Theorem 6.1 by Proposition 5.24. Then by Corollary 6.11, the claim follows.

This finishes the proof of the main theorem, Theorem 5.1. The rest of the section is devoted to prove Theorem 6.1.

Definition 6.3. A finite set of affine hyperplanes ${\mathcal {H}}=\{P_1,\ldots ,P_n\}$ in ${\mathbb {R}}^d$ is called a hyperplane arrangement.

Definition 6.4. Let ${\mathcal {H}}$ be a hyperplane arrangement in ${\mathbb {R}}^d$ .

1. (i) A non-empty intersection of hyperplanes from ${\mathcal {H}}$ is called a flat of ${\mathcal {H}}$ . The set of all flats is denoted by $F({\mathcal {H}})$ . If we are only interested in flats of a certain dimension k, we denote this set by $F_k({\mathcal {H}})$ . Notice that the whole space is also a flat, as a result of the intersection over the empty set.

2. (ii) The connected components of

   $$ \begin{align*} {\mathbb{R}}^d \setminus \bigcup_{H \in {\mathcal{H}}} H \end{align*} $$
   are called regions of the arrangement. The set of all regions is denoted by $f_d({\mathcal {H}})$ and the number of these regions is denoted by $r({\mathcal {H}})$ .

3. (iii) Let $B\subset {\mathbb {R}}^d$ , then the connected components of

   $$ \begin{align*} B \setminus \bigcup_{H \in {\mathcal{H}}} H \end{align*} $$
   are called regions of the arrangement with respect to B and the number of these regions is denoted by $r_B({\mathcal {H}})$ .

4. (iv) Let $B\subset {\mathbb {R}}^d$ , then define the arrangement with respect to B as

   $$ \begin{align*} {\mathcal{H}}_B := \{H \in {\mathcal{H}} \mid H \cap B \neq \emptyset\}. \end{align*} $$

5. (v) Let $B\subset {\mathbb {R}}^d$ , then a flat with respect to B is a flat of ${\mathcal {H}}$ which intersects B. The set of these flats is denoted by $F_B({\mathcal {H}})$ and, again, if we only consider the flats of dimension k, we write $F_{k,B}({\mathcal {H}})$ .

Remark 6.5. Obviously $r_B({\mathcal {H}})$ only depends on the hyperplanes which intersect B, so $r_B({\mathcal {H}})=r_B({\mathcal {H}}_B)$ . Further, notice that in general, $r_B({\mathcal {H}}) \neq \vert \{ R \in f_d({\mathcal {H}}) \mid R \cap B \neq \emptyset \}\vert $ , but the following proposition will show that equality holds for convex B.

Proposition 6.6. Let ${\mathcal {H}}$ be a hyperplane arrangement in ${\mathbb {R}}^d$ and $B \subset {\mathbb {R}}^d$ convex, then

$$ \begin{align*} r_B({\mathcal{H}}) = \vert\{R \in f_d({\mathcal{H}}) \mid R \cap B \neq \emptyset\}\vert. \end{align*} $$

Proof. The regions of a hyperplane arrangement are convex. Since B is also convex, we have for all $R \in f_d({\mathcal {H}})$ that $R \cap B$ is convex and especially connected. So each region of the arrangement either intersects B and therefore contributes exactly one to $r_B({\mathcal {H}})$ , or it does not intersect at all.

Definition 6.7. An arrangement ${\mathcal {H}}$ in ${\mathbb {R}}^d$ is called:

1. (i) central if $\bigcap _{H \in {\mathcal {H}}} H \neq \emptyset $ (observe that the empty arrangement is central since the empty intersection is the whole space);

2. (ii) central with respect to B, for some $B \subset {\mathbb {R}}^d$ , if $B \cap \bigcap _{H \in {\mathcal {H}}} H \neq \emptyset $ .

We will now define the characteristic polynomial for the arrangement ${\mathcal {H}}$ which depends on $B\subset {\mathbb {R}}^d$ . This idea is similar to the standard idea of considering the characteristic polynomial of the arrangement.

Definition 6.8. Let ${\mathcal {H}}$ be a hyperplane arrangement in ${\mathbb {R}}^d$ . The characteristic polynomial with respect to B is defined by

$$ \begin{align*} \chi_{{\mathcal{H}},B}(t):= \hspace{-0.5cm }\sum_{\substack{{\mathcal{A}} \subset {\mathcal{H}}\\ {\mathcal{A}} \text{ central with respect to } B}} \hspace{-0.5cm } (-1)^{\vert {\mathcal{A}} \vert} t^{\dim(\bigcap_{H \in {\mathcal{A}}} H)}. \end{align*} $$

Following the argumentation in [12] for the characteristic polynomial with respect to B instead of the characteristic polynomial, we can establish the following theorem. Since the argument is exactly the same, we will not prove the statement here.

Theorem 6.9. [12, Theorem 2.8]

Let ${\mathcal {H}}$ be a hyperplane arrangement in ${\mathbb {R}}^d$ and $B \subset {\mathbb {R}}^d$ convex, then

$$ \begin{align*} r_{B}({\mathcal{H}}) = (-1)^d \chi_{{\mathcal{H}},B}(-1). \end{align*} $$

We can use this formula with the help of the following lemma, which we import from Stanley.

Lemma 6.10. [46, Theorem 3.10]

Let $\chi (t)$ be a characteristic polynomial of a hyperplane arrangement ${\mathcal {H}}$ in ${\mathbb {R}}^d$ , then

$$ \begin{align*} \chi(t) = \sum_{f \in F_B({\mathcal{H}})} a_f t^{\dim(f)} \end{align*} $$

with $(-1)^{d-\dim (f)} a_f>0$ for $f \in F_B({\mathcal {H}})$ .

Corollary 6.11. Let ${\mathcal {H}}$ be a hyperplane arrangement in ${\mathbb {R}}^d$ and $B \subset {\mathbb {R}}^d$ convex, then

$$ \begin{align*} r_B({\mathcal{H}}) \geq \vert F_B({\mathcal{H}}) \vert \geq \vert F_{0,B}({\mathcal{H}}) \vert. \end{align*} $$

Proof. By Theorem 6.9 and Lemma 6.10, it is

$$ \begin{align*} r_{B}({\mathcal{H}}) = (-1)^d \chi_{{\mathcal{H}},B}(-1) = \sum_{f \in F_B({\mathcal{H}})} (-1)^d a_f (-1)^{\dim(f)}> \sum_{f \in F_B({\mathcal{H}})} 1 = \vert F_B({\mathcal{H}}) \vert.\quad\quad \\[-2.2pc] \end{align*} $$

This proposition means that to establish a lower bound of the regions, it is enough to count the number of intersection points. We will do this by following the idea of the proof of Beck’s theorem [6]. However, instead of considering the set of lines/hyperplanes spanned by a point set, we turn all the arguments around and consider the intersection points of a given arrangement. We will first handle the case of dimension two and then use induction to generalize the statement.

We first state the Szemerédi–Trotter theorem in two equivalent ways.

Theorem 6.12. (Szemerédi–Trotter theorem, [48, 49])

Let $n,m \in {\mathbb {N}}$ . We set

$$ \begin{align*} I(n,m)= \max_{\vert P \vert =n, \vert L \vert =n} \vert\{(p,l) \in P \times L \mid p \in l\} \vert, \end{align*} $$

where P denotes a set of points and L a set of lines in ${\mathbb {R}}^2$ .

1. (i) There exists a constant $c>0$ such that $I(n,m) < c \cdot (n^{2/3}m^{2/3} + n + m)$ .

2. (ii) Let $\sqrt {n} \leq m \leq \begin {pmatrix} n \\ 2 \end {pmatrix}$ , then there exists a constant $c>0$ such that $I(n,m) < c \cdot (n^{2/3}m^{2/3})$ .

Remark 6.13. The constant for the growth in the Szemerédi–Trotter theorem is known to be less than $2.5$ but more than $0.4$ .

Definition 6.14. Let ${\mathcal {H}}$ be a hyperplane arrangement. Then for a flat $f \in F({\mathcal {H}})$ , we define $S(f):=\{H \in {\mathcal {H}} \mid f \subset H \}$ and further $a(f):=\vert S(f) \vert $ .

Definition 6.15. For a hyperplane arrangement ${\mathcal {H}}$ , let

$$ \begin{align*} t({\mathcal{H}},k) &:= \vert \{p \in F_0({\mathcal{H}}) \mid a(p) \geq k\}\vert, \\ t^\ast({\mathcal{H}},k) &:= \vert \{p \in F_0({\mathcal{H}}) \mid k \leq a(p) < 2k\}\vert. \end{align*} $$

Further, we consider the maximal value of the two terms:

$$ \begin{align*} t(n,k) &:= \max_{\vert {\mathcal{H}} \vert = n } t({\mathcal{H}},k), \\ t^\ast(n,k) &:= \max_{\vert {\mathcal{H}} \vert = n } t^\ast({\mathcal{H}},k). \end{align*} $$

For our proof, we need some bounds on these terms. The first two are from the paper of Beck [6] and are easy to prove. The third is a corollary of the Szemerédi–Trotter theorem. Beck proves a similar inequality [6, Lemma 2.2], which is the main part of his argument. For us, it would also be possible in our setup to translate the proof of Beck, but this would require much effort. If the reader is interested, we challenge them to follow the proof, it certainly is illuminating to translate all the arguments.

Lemma 6.16. [6, Lemma 2.1]

For a hyperplane arrangement ${\mathcal {H}}$ in ${\mathbb {R}}^2$ , with $\vert {\mathcal {H}} \vert = n$ , we have

$$ \begin{align*} t(n,k) \leq \frac{n(n-1)}{k(k-1)}\quad &\text{for all } 2 \leq k \leq n,\\ t(n,k) < \frac{2n}{k}\quad &\text{for all } \sqrt{2n} < k \leq n. \end{align*} $$

Proof. For the first formula, we consider the number of pairs of lines. On the one hand, we consider all possible pairs and on the other hand, the pairs through points in which at least k lines intersect:

$$ \begin{align*} t(n,k) \cdot \begin{pmatrix} k \\ 2 \end{pmatrix} \leq \begin{pmatrix} n \\ 2 \end{pmatrix}\hspace{-1.5pt}. \end{align*} $$

For the second inequality, the points in which at least k lines intersect are denoted by $p_1,\ldots ,p_t$ . We assume that $t= (({2n +l})/{k}) \in {\mathbb {N}}$ , where $l \in \{0,\ldots ,k-1\}$ . Then ${t < \sqrt {2n} + {l}/{k}}$ , since $\sqrt {2n} < k$ . Notice that $\vert S(p_i) \vert \geq k$ and $\vert S(p_i) \cap S(p_j) \vert \leq 1$ for $i \neq j$ , since two points are connected by exactly one line. Then

$$ \begin{align*} n &= \vert {\mathcal{H}} \vert \geq \bigg\vert \bigcup_{i=1}^t S(p_i) \bigg\vert \geq \sum_{i=1}^t \vert S(p_i)\vert - \sum_{1 \leq i < j \leq t} \vert S(p_i) \cap S(p_j)\vert\\ &\geq \sum_{i=1}^t k - \sum_{1 \leq i < j \leq t} 1 = tk - \frac{1}{2}t (t-1)> 2n+l - \frac{1}{2} \bigg(\sqrt{2n}+\frac{l}{k}\bigg) \bigg(\sqrt{2n}+\underbrace{\frac{l}{k}-1}_{<0}\bigg)\\ &> 2n+l - n - \sqrt{\frac{n}{2}} \frac{l}{k} = n+ l \bigg( 1 - \frac{\sqrt{n}}{\sqrt{2}k}\bigg) > n+l\bigg(1- \frac{1}{2}\bigg) \geq n. \end{align*} $$

This is a contradiction, so $t=\lceil {2n}/{k}\rceil $ cannot hold and also $t> {2n}/{k}$ is not possible since we can simply ignore some points to get the same contradiction.

Corollary 6.17. (Corollary of Theorem 6.12, [49, Theorem 2])

For a hyperplane arrangement ${\mathcal {H}}$ in ${\mathbb {R}}^2$ , there is some constant $\beta>0$ such that

$$ \begin{align*} t(n,k) < \beta \frac{n^2}{k^3}\quad \text{for all } 3 \leq k \leq \sqrt{n}. \end{align*} $$

Proof. Assume there are $t= ({c^3n^2+l})/{k^3} \in {\mathbb {N}}$ , where $l\in \{0,\ldots , k^3-1\}$ and ${c=2.5}$ , points with $a(p)\geq k$ .

Then

$$ \begin{align*} \sqrt{t} = n \sqrt{\frac{c^3}{k^3} + \frac{l}{n^2 k^3}} \leq n \sqrt{\frac{c^3}{k^3} + \frac{k^3-1}{n^2k^3}} < n \sqrt{\frac{2.5^3}{3^3}+\frac{1}{n^2}} < n, \end{align*} $$

since $n> 3$ . Further,

$$ \begin{align*} \begin{pmatrix} t \\ 2 \end{pmatrix} &= \frac{1}{2} \frac{c^3 n^2+l}{k^3}\bigg(\frac{c^3 n^2+l}{k^3}-1 \bigg) \geq \frac{1}{2} \bigg(c^3 \sqrt{n}+ \frac{l}{n^{{3}/{2}}}\bigg) \bigg(c^3 \sqrt{n}+ \frac{l}{n^{{3}/{2}}}-1 \bigg)\\ &\geq \frac{1}{2} c^3 \sqrt{n}(c^3 \sqrt{n}-1)>n, \end{align*} $$

since $c=2.5$ and $n>3$ . Therefore, we can use version (ii) of the Szemerédi–Trotter theorem: there is a constant c such that $I(n,m) < c n^{2/3}m^{2/3}$ and we know that $c=2.5$ works. The t point induces $t \cdot k$ incidences, but

$$ \begin{align*} t \cdot k = c^3 \frac{n^2 + l}{k^2} \not< c n^{2/3}t^{2/3}, \end{align*} $$

which is a contradiction to the theorem. Therefore, $t=\lceil {c^3n^2}/{k^3} \rceil $ is not possible and also $t> {c^3n^2}/{k^3}$ is not possible by the same argument if we ignore some points. We see that $\beta =2.5^3$ is a possible choice.

Theorem 6.18. (Local dual of Becks theorem)

Let ${\mathcal {H}}$ be a hyperplane arrangement in ${\mathbb {R}}^2$ and $B \subset {\mathbb {R}}^2$ convex, where ${\mathcal {H}}$ consist of two disjoint families $F_1$ and $F_2$ of hyperplanes with $\vert F_1 \vert = \vert F_2 \vert = {n}/{2}$ and such that for all $(f,g)\in F_1 \times F_2$ , we have $B \cap f \cap g =\{p\}$ for some point $p \in B$ depending on f and g. Then there exists a constant $c_2$ such that one of the following two cases holds.

1. (a) There is a point $p \in B$ such that $a(p) \geq {n}/{100}$ .

2. (b) The number of intersection points in B exceeds $c_2 \cdot n^2$ , that is, $\vert F_{0,B}({\mathcal {H}}) \vert \geq c\cdot n^2$ .

Proof. We count the number of pairs of lines, we get

$$ \begin{align*} \begin{pmatrix} n \\ 2 \end{pmatrix} \geq \sum_{p \in F_{0,B}({\mathcal{H}})} \begin{pmatrix} a(p) \\ 2 \end{pmatrix} \geq \vert F_1 \vert \cdot \vert F_2 \vert = \frac{1}{4}n^2. \end{align*} $$

On the left side, we counted all the possible options, in the middle, we counted the pairs that intersect inside B and on the right, we counted the pairs of lines from the two families since we know that they intersect in B. We will split the sum into three parts:

$$ \begin{align*} S_1 &:= \sum_{\substack{p \in F_{0,B}({\mathcal{H}})\\ 2^k \leq a(p) < \sqrt{n}}} \begin{pmatrix} a(p) \\ 2\end{pmatrix}\hspace{-1.5pt},\\ S_2 &:= \sum_{\substack{p \in F_{0,B}({\mathcal{H}})\\ \sqrt{n} \leq a(p) < \frac{n}{100}}} \begin{pmatrix} a(p) \\ 2\end{pmatrix}\hspace{-1.5pt},\\ S_3 &:= \sum_{\substack{p \in F_{0,B}({\mathcal{H}})\\ 2 \leq a(p) < 2^k}} \begin{pmatrix} a(p) \\ 2\end{pmatrix} + \sum_{\substack{p \in F_{0,B}({\mathcal{H}})\\ \frac{n}{100} \leq a(p) \leq n}} \begin{pmatrix} a(p) \\ 2\end{pmatrix}\hspace{-1.5pt}, \end{align*} $$

where $k=10$ is constant. Now we will bound $S_1$ and $S_2$ . We start with $S_1$ using Corollary 6.17:

$$ \begin{align*} S_1 &= \sum_{l \geq k} \sum_{\substack{p \in F_{0,B}({\mathcal{H}}) \\ 2^l \leq a(p) < 2^{l+1} \\ a(p) < \sqrt{n}}} \begin{pmatrix} a(p) \\ 2 \end{pmatrix} \leq \sum_{\substack{l \geq k \\ 2^{l+1}<\sqrt{n}}} t^{\ast}(n,2^l) \begin{pmatrix} 2^{l+1} \\ 2 \end{pmatrix} \\ &= \sum_{\substack{l \geq k \\ 2^{l+1} < \sqrt{n}}} t^{\ast}(n,2^l) 2^l (2^{l+1}-1) \leq \sum_{\substack{l \geq k \\ 2^{l+1} < \sqrt{n}}} \beta \frac{n^2}{2^{3l}} 2^l (2^{l+1}-1)\\ &\leq 2 \beta n^2 \sum_{l \geq k} \frac{1}{2^l} = \frac{4 \beta}{2^k} n^2 \leq \frac{1}{8} \begin{pmatrix} n \\ 2\end{pmatrix}\hspace{-1.5pt}, \end{align*} $$

since $\beta = 2.5^3$ , $k=10$ and $n\geq 2$ . For the next sum, we use Lemma 6.16 and Corollary 6.17:

$$ \begin{align*} S_2 &= \sum_{l \geq0} \sum_{\substack{p \in F_{0,B}({\mathcal{H}}) \\ 2^l \sqrt{n} \leq a(p) < 2^{l+1} \sqrt{n} \\ a(p) < \frac{n}{100}}} \begin{pmatrix} a(p) \\ 2 \end{pmatrix} \leq \sum_{\substack{l \geq 0\\ 2^{l} \sqrt{n} < \frac{n}{100}}} t(n, 2^l \sqrt{n}) \begin{pmatrix} 2^{l+1} \sqrt{n} \\ 2 \end{pmatrix}\\ &= t(n, \sqrt{n}) \begin{pmatrix} 2 \sqrt{n} \\ 2 \end{pmatrix} +\sum_{\substack{l \geq 1\\ 2^{l} \sqrt{n} < \frac{n}{100}}} t(n,\underbrace{2^l \sqrt{n}}_{> \sqrt{2n}}) \begin{pmatrix} 2^{l+1} \sqrt{n} \\ 2 \end{pmatrix}\\&< \beta \frac{n^2}{n^{3/2}} \sqrt{n} (2 \sqrt{n}-1) + \sum_{\substack{l \geq 1\\ 2^{l} \sqrt{n} < \frac{n}{100}}} \frac{2n}{2^l \sqrt{n}} 2^l \sqrt{n} (2^{l+1} \sqrt{n}-1)\\ &< 2 \beta n^{3/2} + 4 n^{3/2} \sum_{\substack{l \geq 1 \\ 2^{l} < \frac{\sqrt{n}}{100}}} 2^l = 2 \beta n^{3/2} + 4 n^{3/2} \bigg( \frac{\sqrt{n}}{50}-2\bigg)\\ &= \frac{2}{25} n^2 + (2 \beta -8 )n^{3/2} \leq \frac{1}{4} \begin{pmatrix} n \\ 2\end{pmatrix}. \end{align*} $$

Combining the two results, we get a lower bound for $S_3$ :

$$ \begin{align*} S_3 \geq \vert F_1 \vert \cdot \vert F_2 \vert - \frac{1}{4}\begin{pmatrix} n \\ 2 \end{pmatrix} - \frac{1}{8}\begin{pmatrix} n \\ 2 \end{pmatrix} \geq \frac{1}{16}n^2. \end{align*} $$

So now assume that condition (a) of the theorem does not hold, then

$$ \begin{align*} \vert F_{0,B}({\mathcal{H}}) \vert \geq \sum_{\substack{p \in F_{0,B}\\ 2 \leq a(p) < 2^k}} 1 \geq \begin{pmatrix} 2^k \\ 2 \end{pmatrix}^{-1} \sum_{\substack{p \in F_{0,B}\\ 2 \leq a(p) < 2^k}} \begin{pmatrix} a(p) \\ 2 \end{pmatrix} \geq \begin{pmatrix} 2^k \\ 2 \end{pmatrix}^{-1} \frac{1}{16} n^2. \end{align*} $$

Since we have seen that $k=10$ is a possible choice, the constant would be $c={1}/{8 380416}$ .

Remark 6.19. In condition (a), the constant ${1}/{100}$ is by no means optimal, but since for us the constant plays an insignificant role, we stick to the original constant used by Beck.

Further notice that we have even proved a stronger theorem, namely that

$$ \begin{align*} \vert \{p \in F_{0,B}({\mathcal{H}}) \mid 2 \leq a(p) \leq 2^k\}\vert \geq c \cdot n^2 \end{align*} $$

if condition (a) does not hold.

Proof of Theorem 6.1

The idea of the proof is that for a family $F_i$ of hyperplanes, the other families induce a hyperplane arrangement in all $H \in F_i$ , thus we can conclude by induction. The case $d=2$ is already completed by Theorem 6.18, where we even proved the stronger statement that

$$ \begin{align*} \vert \{p \in F_{0,B}({\mathcal{H}}) \mid 2 \leq a(p) < 2^k\}\vert \geq c_2 \cdot n^2 \end{align*} $$

if for all $p \in B$ , we have $a(p) < {n}/{100}$ . That $a(p) < {1}/{100} n$ is guaranteed by the assumption that at most $c \cdot \vert F_i \vert $ hyperplanes from $F_i$ can intersect in one point and $c < {1}/{100}$ . So the initial case of the induction holds.

Now consider the family $F_1$ . We are interested in the $(d-1)$ -dimensional arrangement which is induced on the hyperplanes $H\in F_1$ . Notice that for $H_i \in F_i, H_j \in F_j$ and $H_k\in F_k$ , $i \neq j \neq k$ , we have $H_i \cap H_j \neq H_i \cap H_k$ since otherwise, we get a contradiction to the assumption that $B \cap \bigcap _{i=1}^d f_i = \{p\}$ for all $(f_1,\ldots ,f_d) \in F_1 \times \cdots \times F_d$ . So the different families induce different $(d-2)$ -hyperplanes on the hyperplanes of $F_1$ . Set

$$ \begin{align*} {\mathcal{H}}^{H \ast} := \{H \cap f \mid f \in F_2 \cup \cdots \cup F_d\}, \end{align*} $$

here $H \cap f \neq \emptyset $ holds for all f by the assumption on the intersection behaviour. Now we prove the following claim, which gives us the induction hypothesis.

Claim. $\vert {\mathcal {H}}^{H \ast } \vert> \delta \cdot n$ for some constant $\delta $ , and at least $\varepsilon \cdot ({n}/{d})$ hyperplanes $H \in F_1$ for some constant $\varepsilon>0$ .

We prove the claim. We do this by considering two families and show that the one induces enough planes on the second one. To do so, let P be a generic two-dimensional plane in ${\mathbb {R}}^d$ , that is, $P \cap H$ is one-dimensional for all $H \in F_1 \cup F_2$ and they are all distinct for different H. Additionally, $P\cap f$ is a point for all $f=H \cap K$ with $H \in F_1$ , $K \in F_2$ which are also distinct if the $K \cap H$ are distinct. So each hyperplane corresponds to a line and each $(d-2)$ -dimensional flat corresponds to a point. The intersection behaviour for the lines clearly fulfils the assumptions in Theorem 6.18. So we can apply the theorem and get $c \cdot ({n}/{d})^2$ intersection points and therefore $c \cdot ({n}/{d})^2$ induced flats. Since each hyperplane can carry at most ${n}/{d}$ induced flats, we see that the flats have to spread out such that the claim holds.

Denote the set of hyperplanes from $F_1$ for which the claim holds by $\tilde {F_1}$ . It is clear that the intersection behaviour of the different families also holds in the $(d-1)$ -dimensional arrangement induced on the hyperplanes in $\tilde {F_1}$ . Also, assume that the stronger statement

$$ \begin{align*} \vert \{p \in F_{0,B}({\mathcal{H}}) \mid l \leq a(p) < l^k\}\vert \geq c_l \cdot n^l \end{align*} $$

is proved for all dimensions l up to $d-1$ , where k is a constant.

Now we can do the induction step. We get the following inequality:

$$ \begin{align*} \vert F_{0,B}({\mathcal{H}}) \vert \cdot \begin{pmatrix} d^k \\ d \end{pmatrix}> \sum_{\substack{p \in F_{0,B}({\mathcal{H}})\\ d \leq a(p) < d^{k}}} \begin{pmatrix} a(p) \\ d \end{pmatrix} \geq \sum_{H \in F_1} \sum_{\substack{p \in F_{0,B}({\mathcal{H}}^{H\ast})\\ d-1 \leq a_{{\mathcal{H}}^{H\ast}}(p) < (d-1)^k}} \begin{pmatrix} a_{{\mathcal{H}}^{H\ast}}(p) \\ d-1 \end{pmatrix}\hspace{-1.5pt}. \end{align*} $$

For the last inequality, notice that $a_{{\mathcal {H}}^{H\ast }}(p)$ now only counts the hyperplanes in ${\mathcal {H}}^{H \ast }$ and we only have to take $d-1$ out of them since we fixed the choice $H \in F_1$ . Now further by the induction assumption,

$$ \begin{align*} &\sum_{H \in F_1} \sum_{\substack{p \in F_{0,B}({\mathcal{H}}^{H\ast})\\ d-1 \leq a(p) < (d-1)^k}} \begin{pmatrix} a(p) \\ d-1 \end{pmatrix} \geq \sum_{H \in \tilde{F_1}} \sum_{\substack{p \in F_{0,B}({\mathcal{H}}^{H\ast})\\ d-1 \leq a(p) < (d-1)^k}} \begin{pmatrix} a(p) \\ d-1 \end{pmatrix}\\ &\quad\geq \sum_{H \in \tilde{F_1}} \vert \{ p \in F_{0,B}({\mathcal{H}}^{H\ast}) \mid d-1 \leq a(p) < (d-1)^k\}\vert\\ &\quad\geq \sum_{H \in \tilde{F_1}} c_{d-1} \cdot \delta^{d-1} n^{d-1} \geq \varepsilon \frac{n}{d} c_{d-1} \delta^{d-1} n^{d-1} = \frac{\varepsilon c_{d-1}}{d} \cdot \delta^{d-1} n^d.\\ \end{align*} $$

This finally yields

$$ \begin{align*} \vert \{ F_{0,B}({\mathcal{H}}) \mid d \leq a(p) < d^k \} \vert \geq \begin{pmatrix} d^k \\ d \end{pmatrix}^{-1} \frac{\varepsilon c_{d-1}}{d} \cdot \delta^{d-1} n^d =: c_d n^d.\\[-42pt] \end{align*} $$