On the Number of Monochromatic Lines in $\pmb {\mathbb {R}}^d$

Abstract

Let X be a nonempty finite subset of ${\mathbb {R}}^d$ and $X=\bigcup _{i=1}^m X_i$ a coloring with $m<d$. In this paper we study the number of monochromatic lines generated by X. More specifically we give three results which establish that, under nontrivial assumptions, the number of monochromatic lines generated by X is $\varTheta (|X|^2)$.

1 Introduction

In this paper ${\mathbb {N}}$, ${\mathbb {Z}}$ and ${\mathbb {R}}$ denote the set of natural numbers, integers and real numbers, respectively; we consider $0\not \in {\mathbb {N}}$. From now on, $d\in {\mathbb {N}}$ and ${\mathbb {R}}^d$ is equipped with its usual euclidean structure. Let X be a nonempty subset of ${\mathbb {R}}^d$ and $m\in {\mathbb {N}}$. A coloring of X is a family of pairwise disjoint subsets $\{X_1,X_2,\ldots , X_m\}$ of X such that $X=\bigcup _{i=1}^m X_i$ and we will denote the coloring by $X=\bigcup _{i=1}^mX_i$. For each $i\in \{1,2,\ldots ,m\}$, $X_i$ will be called a chromatic class. A translation F of a vector subspace V of ${\mathbb {R}}^d$ will be called a flat. We write $\dim F:=\dim V$, and also if V is a $d'$-dimensional subspace, we say that F is a $d'$-flat; in particular 1-flats will be called lines and $(d{-}1)$-flats will be called hyperplanes. For technical reasons, we will also consider the empty set a flat with $\dim \emptyset :=-1$ and we will say that $\emptyset$ is a $(-1)$-flat. We denote by ${\mathrm {Fl}}(X)$ the smallest flat (with respect to $\subseteq$) which contains X and we write $\dim X:=\dim {\mathrm {Fl}}(X)$. Given a coloring $X=\bigcup _{i=1}^mX_i$, we say that a line L of ${\mathbb {R}}^d$ is monochromatic if $X\cap L$ is contained in a chromatic class and $|X\cap L|\ge 2$; the family of monochromatic lines with respect to the coloring $X=\bigcup _{i=1}^mX_i$ will be denoted by ${\mathcal {M}}\bigl (\bigcup _{i=1}^mX_i\bigr )$. We write $\bigl | {\mathcal {M}}\bigl (\bigcup _{i=1}^mX_i\bigr )\bigr |=\varTheta (|X|^2)$ if there are $c,c'>0$ such that $|X|^2/c\le \bigl | {\mathcal {M}}\bigl (\bigcup _{i=1}^mX_i\bigr )\bigr |\le c|X|^2$ whenever $|X|\ge c'$; if c and $c'$ depend on the parameters $c_1,c_2,\ldots$, we write $\bigl |{\mathcal {M}}\bigl (\bigcup _{i=1}^mX_i\bigr )\bigr |=\varTheta _{c_1,c_2,\ldots }(|X|^2)$.

One of the most famous and fruitful theorems in discrete geometry is the Sylvester–Gallai Theorem, see [3]. The colorful version of Sylvester–Gallai Theorem was proven independently by Motzkin and Rabin.

Theorem 1.1

Let X be a nonempty finite subset of ${\mathbb {R}}^2$ and a coloring $X=X_1\cup X_2$. If $\dim X=2$, then ${\mathcal {M}}(X_1\cup X_2)\ne \emptyset$.

Proof

See [3, 7].$\square$

For higher dimensions, Theorem 1.1 was generalized by Shannon.

Theorem 1.2

Let X be a nonempty finite subset of ${\mathbb {R}}^d$ with $\dim X=d$ and a coloring $X=\bigcup _{i=1}^m X_i$. If $m\le d$, then ${\mathcal {M}}\bigl (\bigcup _{i=1}^m X_i\bigr )\ne \emptyset$.

Proof

See [2, 8].$\square$

There are more results related to the existence of monochromatic lines, see for instance [2, 3, 7, 8]. However, in this paper we will be interested in quantitative results. One important quantitative result in this area was obtained by Dvir and Tessier-Lavigne in [5]. Here we will be more interested in the number of monochromatic lines that can be generated rather than the dimension of the Motzkin–Rabin configurations. The main motivation of this paper is the following. Let X be a nonempty finite subset of ${\mathbb {R}}^d$ such that $\dim X=d$ and a coloring $X=\bigcup _{i=1}^mX_i$. It is not difficult to see that if most of the points of X are in a line, it is possible to have $\bigl |{\mathcal {M}}\bigl (\bigcup _{i=1}^mX_i\bigr )\bigr |\ll |X|^2$. Moreover, if almost all the points of X are in a hyperplane H of ${\mathbb {R}}^d$, then $X\cap H$ (and therefore X) may not have a lot of monochromatic lines (for instance, if $X=X_1\cup X_2$ is a finite subset of ${\mathbb {R}}^2$ with $X_1$ a singleton and $X_2$ contained in a line, there is only one monochromatic line). Thus we want to study under which conditions, if there are no hyperplanes in ${\mathbb {R}}^d$ with a lot of points of X, we have that $\bigl |{\mathcal {M}}\bigl (\bigcup _{i=1}^mX_i\bigr )\bigr |=\varTheta (|X|^2)$. The first result of this paper is the following.

Theorem 1.3

Let X be a nonempty finite subset of ${\mathbb {R}}^d$ with $\dim X=d$, a coloring $X=\bigcup _{i=1}^m X_i$ with $m<d$, $0< c'\le 1$ and $0<c<1$. If there is a chromatic class $X_i$ such that $|X_i|\ge c'|X|$ and $|X_i\cap H|\le c|X_i|$ for any hyperplane H of ${\mathbb {R}}^d$, then

$$\begin{aligned} \Biggl |{\mathcal {M}}\Biggl (\bigcup _{i=1}^mX_i\Biggr )\Biggr |=\varTheta _{c,c',m,d}(|X|^2). \end{aligned}$$

The assumption $m<d$ is necessary. Theorem 1.3 can be extended readily to ${\mathbb {R}}\mathbb {P}^d$, and here we give an example which shows that $m<d$ is fundamental. Take $m=d=2$, $n>3$ and the Böröczky example $X=X_{2n}$ with the coloring $X=X_1\cup X_2$ where the chromatic classes are

$$\begin{aligned} X_1&:=\biggl \{\biggl [\cos \frac{2\pi j}{n}:\sin \frac{2\pi j}{n}:1\biggr ]\,:\,j\in \{0,1,\ldots ,n-1\}\biggr \},\\ X_2&:=\biggl \{\biggl [-\sin \frac{2\pi j}{n}:\cos \frac{2\pi j}{n}:0\biggr ]\,:\,j\in \{0,1,\ldots ,n-1\}\biggr \}. \end{aligned}$$

X and the chromatic class $X_1$ satisfy all the conditions of Theorem 1.3 for $c=c'={1}/{2}$ except for $m<d$. Nevertheless, the unique monochromatic line is $L_{\infty }=\{[x:y:0]:x,y\in {\mathbb {R}}\}$.

Theorem 1.3 needs the existence of a chromatic class which satisfies certain properties. However, even if we do not have information about a specific chromatic class, we are able to obtain an interesting result.

Theorem 1.4

Let X be a nonempty finite subset of ${\mathbb {R}}^d$ with $\dim X=d$, a coloring $X=\bigcup _{i=1}^m X_i$ with $2m\le d$ and $0<c<1$. If $|X\cap H|\le c|X|$ for any hyperplane H of ${\mathbb {R}}^d$, then

$$\begin{aligned} \Biggl |{\mathcal {M}}\Biggl (\bigcup _{i=1}^mX_i\Biggr )\Biggr |=\varTheta _{c,m,d}(|X|^2). \end{aligned}$$

The condition $2m\le d$ in Theorem 1.4 is necessary. Indeed, take $2m-1=d$, $L_1,L_2,\ldots , L_m$ lines in ${\mathbb {R}}^d$ such that $\dim {\bigcup _{j=1}^iL_j}=2i-1$ for all $i\in \{1,2,\ldots ,m\}$, X a subset of $\bigcup _{i=1}^{m}L_i$ such that $|X\cap L_1|=|X\cap L_2|=\cdots =|X\cap L_m|>2m$ and $c=({2m{-}1})/({2m})$. Define the coloring $X=\bigcup _{i=1}^m X_i$ with $X_i:=X\cap L_i$ for all $i\in \{1,2,\ldots , m\}$. Since $|X_i|>2m$ for all $i\in \{1,2,\ldots , m\}$, we have that $|H\cap X|\le (m{-}1)|X|/m+1\le c|X|$ for any hyperplane H of ${\mathbb {R}}^d$. However, the monochromatic lines are just $L_1,L_2,\ldots , L_m$.

Another fundamental result in discrete geometry is Beck’s Theorem, see Theorem 2.2. Here we state a weak colorful version of it.

Theorem 1.5

Let X be a nonempty finite subset of ${\mathbb {R}}^d$ with $\dim X=d$ and a coloring $X=\bigcup _{i=1}^m X_i$ with $m<d$. If $|X\cap H|\le |X|/({2d})$ for any hyperplane H of ${\mathbb {R}}^d$, then

$$\begin{aligned} \Biggl |{\mathcal {M}}\Biggl (\bigcup _{i=1}^mX_i\Biggr )\Biggr |=\varTheta _{m,d}(|X|^2). \end{aligned}$$

(1)

As it was kindly remarked by the reviewers, a number of questions arise in connection with the above results. We have chosen three of them.

• In Theorem 1.3, if we assume that all the chromatic classes $X_i$ satisfy that $|X_i|\ge c'|X|$ and $|X_i\cap H|\le c|X_i|$ for any hyperplane H of ${\mathbb {R}}^d$, can we weaken the assumption $m<d$?

• In Theorem 1.3, can we weaken the assumption $m<d$ for $d\gg 0$? The example given immediately after Theorem 1.3 shows that the assumption cannot be weakened for $d=2$.

• Let X be a nonempty finite subset of ${\mathbb {R}}^d$ with $\dim X=d$ and a coloring $X=\bigcup _{i=1}^m X_i$ such that $m<d$ and $|X\cap L|\le |X|/(2d)$ for any line L of ${\mathbb {R}}^d$. Is it true that (1) holds?

We want to make two remarks. The first one is that the constants of the main results can be found explicitly although we think that they are far of being optimal. The second point is that if X is a finite subset of ${\mathbb {R}}^d$, then it generates at most $\left( {\begin{array}{c}|X|\\ 2\end{array}}\right)$ lines. Thus, in the proofs of the theorems, it suffices to show that there are $c'',c'''>0$ such that if $|X|\ge c''$, then ${\mathcal {M}}\bigl (\bigcup _{i=1}^mX_i\bigr )\ge c'''|X|^2$.

We describe briefly the organization of this paper. In Sect. 2 we state some results that will be needed in the forthcoming sections. The key ingredient in the proof of the main results is Proposition 3.2 and it is proven in Sect. 3. The proofs of the main theorems are completed in Sect. 4. The proof of Theorem 1.3 depends on the number of hyperplanes generated by $X_i$. If $X_i$ generates a lot of hyperplanes, the statement is a consequence of Proposition 3.2. If $X_i$ does not generate a lot of hyperplanes, Corollary 2.6 implies that $X_i$ (and therefore X) has a special structure; with this information about the structure of $X_i$, we can find a number of monochromatic lines as well. The proof of Theorem 1.4 is done by induction on the number of chromatic classes. In the induction step we follow similar ideas to the ones of the proof of Theorem 1.3, however we have to be very careful with the parameters to be able to use the induction hypothesis. The proof of Theorem 1.5 is the easiest one due to Corollary 2.4 and Proposition 3.2.

2 Preliminaries

In this section we state some auxiliary results that will be needed later. For a subset X of ${\mathbb {R}}^d$ and ${\mathcal {F}},{\mathcal {G}}$ families of subsets of ${\mathbb {R}}^d$, set

$$\begin{aligned} I(X,{\mathcal {F}})&:=\{({\mathbf {x}},F)\in X\times {\mathcal {F}}:{\mathbf {x}}\in F\},\\ I({\mathcal {G}},{\mathcal {F}})&:=\{(G,F)\in {\mathcal {G}}\times {\mathcal {F}}:G\subseteq F\}. \end{aligned}$$

The first result that we will need is the Szemerédi–Trotter Theorem.

Theorem 2.1

Let X be a finite subset of ${\mathbb {R}}^d$ and ${\mathcal {L}}$ a finite family of lines in ${\mathbb {R}}^d$. Then

$$\begin{aligned} |I(X,{\mathcal {L}})|\le 4|X|^{{2}/{3}}|{\mathcal {L}}|^{{2}/{3}}+4|X|+|{\mathcal {L}}|. \end{aligned}$$

Proof

See [9, Thm. 8.3].$\square$

Let F be a flat of ${\mathbb {R}}^d$. For a subset X of ${\mathbb {R}}^d$, we say that X generates F if there is a subset $X'$ of X such that ${\mathrm {Fl}}(X')=F$. More generally, for a family ${\mathcal {F}}$ of subsets of ${\mathbb {R}}^d$, we say that ${\mathcal {F}}$ generates F if there is a subfamily ${\mathcal {F}}'$ of ${\mathcal {F}}$ such that ${\text {Fl}}{\bigl (\bigcup _{F'\in {\mathcal {F}}'}F'\bigr )}=F$. We state now Beck’s Theorem which is a consequence of the Szemerédi–Trotter Theorem.

Theorem 2.2

There are two absolute constants $c,c'>0$ such that for any finite subset X of ${\mathbb {R}}^d$ one of the following statements holds:

• (i) There is a line L in ${\mathbb {R}}^d$ such that $|X\cap L|\ge c|X|$.

• (ii) X generates at least $c'|X|^2$ lines.

Proof

See [1, Thm. 3.1].$\square$

Using Beck-type results and other tools, Do and Lund obtained independently the following result.

Theorem 2.3

For any $0<c<1$, there is $0<c'<1$ such that for any finite subset X of ${\mathbb {R}}^d$ one of the following statements holds:

• (i) There is a finite family of nonzero dimensional flats $\{F_1,F_2,\ldots , F_k\}$ of ${\mathbb {R}}^d$ such that $\sum _{i=1}^k\dim F_i<d$ and $\bigl |X\cap \bigcup _{i=1}^k F_i\bigr |\ge c|X|$.

• (ii) X generates at least $c'|X|^d$ hyperplanes.

Proof

See [4, Thm. 1.6], [6, Thm. 2].$\square$

We shall consider two corollaries of Theorem 2.3.

Corollary 2.4

For any $d\ge 2$ and $0<c<{1}/({d{-}1})$, there is $0<c'<1$ such that for any finite subset X of ${\mathbb {R}}^d$ one of the following statements holds.

• (i) There is a hyperplane H of ${\mathbb {R}}^d$ such that $|X\cap H|\ge c|X|$.

• (ii) X generates at least $c'|X|^d$ hyperplanes.

Proof

See [4, Corr. 1.9].$\square$

We say that two flats $F_1$ and $F_2$ of ${\mathbb {R}}^d$ are skew if $\dim {(F_1\cup F_2)}=\dim F_1+\dim F_2+1$; in particular skew flats do not intersect. We will need two trivial facts.

Remark 2.5

Let $F_1$ and $F_2$ be flats of ${\mathbb {R}}^d$.

• (i) The dimension of $F_1\cup F_2$ is bounded above as follows:

  $$\begin{aligned} \dim {(F_1\cup F_2)}\le \min {\{\dim F_1+\dim F_2+1,d\}}. \end{aligned}$$

  Moreover, if $F_1$ and $F_2$ are not skew, then

  $$\begin{aligned} \dim {(F_1\cup F_2)}\le \min {\{\dim F_1+\dim F_2,d\}}. \end{aligned}$$

• (ii) Let $F'_1$ and $F'_2$ be flats such that $F'_1\subseteq F_1$ and $F'_2\subseteq F_2$. If $F_1$ and $F_2$ are skew, then $F'_1$ and $F'_2$ are skew.

Under the assumptions and notation of Corollary 2.4, we have that there is a hyperplane H of ${\mathbb {R}}^d$ such that $|X\cap H|\ge c|X|$ or X generates at least $c'|X|^d$ hyperplanes. However, $c'$ may be very small for our purposes (i.e., the assumption of Proposition 3.2). Thus, when X generates a lot of hyperplanes but not enough, we need to know a little bit about the structure of X. The next corollary provides this information.

Corollary 2.6

For any $0<c<1$, there is $0<c'<1$ such that for any finite subset X of ${\mathbb {R}}^d$ with

$$\begin{aligned} |X|\ge \frac{2d}{(1-c^{{1}/({d+1})})c^{({d+2})/({d+1})}}, \end{aligned}$$

(2)

one of the following statements holds:

• (i) There is a hyperplane H of ${\mathbb {R}}^d$ such that $|X\cap H|\ge c|X|$.

• (ii) There is a finite family of nonzero dimensional pairwise skew flats $\{F_1,F_2,\ldots , F_k\}$ of ${\mathbb {R}}^d$ with $d_i:=\dim F_i$ for all $i\in \{1,2,\ldots , k\}$ such that

  • $\sum _{i=1}^k d_i<d$,

  • $\bigl |X\cap \bigcup _{i=1}^k F_i\bigr |\ge c|X|$,

  • for all $i\in \{1,2,\ldots , k\}$, $|X\cap F|\le c^{{1}/({d+1})}|X\cap F_i|$ for each $(d_i{-}1)$-flat F contained in $F_i$.

• (iii) X generates at least $c'|X|^d$ hyperplanes.

Proof

Theorem 2.3 implies that for $c^{{1}/({d+1})}$ there is $0<c'<1$ such that one of the following occurs:

• (I) There is a finite family of nonzero dimensional flats $\{F_{1,1},F_{1,2},\ldots ,F_{1,n}\}$ of ${\mathbb {R}}^d$ such that $\sum _{i=1}^n\dim F_{1,i}<d$ and $\bigl |X\cap \bigcup _{i=1}^n F_{1,i}\bigr |\ge c^{{1}/({d+1})}|X|$.

• (II) X generates at least $c'|X|^d$ hyperplanes.

If (II) holds, then we are in (iii). From now on we assume that (I) occurs. Since $\sum _{i=1}^n\dim F_{1,i}<d$ and the flats are nonzero dimensional,

$$\begin{aligned} n<d. \end{aligned}$$

(3)

Starting with the family of flats $\{F_{1,1},F_{1,2}\ldots ,F_{1,n}\}$, we construct recursively families of nonzero dimensional flats $\{F_{m,1},F_{m,2},\ldots ,F_{m,n-m+1}\}$ of ${\mathbb {R}}^d$ such that $\sum _{i=1}^{n-m+1}\dim F_{m,i}<d$ and $\bigl |X\cap \bigcup _{i=1}^{n-m+1} F_{m,i}\bigr |\ge c^{{1}/({d+1})}|X|$ as follows. Given a family of nonzero dimensional pairwise nonskew flats $\{F_{m,1},F_{m,2},\ldots , F_{m,n-m+1}\}$ of ${\mathbb {R}}^d$ such that $\sum _{i=1}^{n-m+1}\dim F_{m,i}<d$ and $\bigl |X\cap \bigcup _{i=1}^{n-m+1} F_{m,i}\bigr |\ge c^{{1}/({d+1})}|X|$, we construct $\{F_{m+1,1},F_{m+1,2},\ldots , F_{m+1,n-m}\}$ in the following way. Assume without loss of generality that $F_{m,n-m}$ and $F_{m,n-m+1}$ are not skew. For each $i\in \{1,2,\ldots ,n{-}m\}$ set

$$\begin{aligned} F_{m+1,i}:= {\left\{ \begin{array}{ll} F_{m,i} &{} \hbox {if }i\ne n-m,\\ {\text {Fl}}{(F_{m,n-m}\cup F_{m,n-m+1})} &{} \hbox {if }i=n-m. \end{array}\right. } \end{aligned}$$

From Remark 2.5(i), we have that $\sum _{i=1}^{n-m}\dim F_{m+1,i}<d$ and $\bigl |X\cap \bigcup _{i=1}^{n-m} F_{m+1,i}\bigr |\ge c^{{1}/({d+1})}|X|$. The construction of these families of flats proceeds until one of the following two cases occurs.

Case 1. Assume that we can construct the families until $m=n$. Then we get a flat $F_{n,1}$ such that $\dim F_{n,1}<d$ and $|X\cap F_{n,1}|\ge c^{{1}/({d+1})}|X|\ge c|X|$. Thus we are in (i) and are done.

Case 2. Assume that there is $m<n$ and a family of nonzero dimensional pairwise skew flats $\{F_{m,1},F_{m,2},\ldots , F_{m,n-m+1}\}$ of ${\mathbb {R}}^d$ such that $\sum _{i=1}^{n-m+1}\dim F_{m,i}<d$ and $\bigr |X\cap \bigcup _{i=1}^{n-m+1} F_{m,i}\bigl |\ge c^{{1}/({d+1})}|X|$. Assume without loss of generality that

$$\begin{aligned} |X\cap F_{m,1}|\ge |X\cap F_{m,2}|\ge \cdots \ge |X\cap F_{m,n-m+1}|, \end{aligned}$$

and let $k\in \{1,2,\ldots ,n{-}m{+}1\}$ be such that

$$\begin{aligned} |X\cap F_{m,1}|\ge \cdots \ge |X\cap F_{m,k}|\ge \frac{2}{c}> |X\cap F_{m,k+1}| \ge \cdots \ge |X\cap F_{m,n-m+1}|. \end{aligned}$$

(4)

Set $F'_{1,i}:=F_{m,i}$ with $d'_i:=\dim F'_{l,i}$ for each $i\in \{1,2,\ldots , k\}$. For $i\in \{1,2,\ldots , k\}$, we construct recursively a family of flats $F'_{1,i}\supsetneq F'_{2,i}\supsetneq \cdots \supsetneq F'_{l,i}$ as follows. Given a $(d'_i{-}l{+}1)$-flat $F'_{l,i}$, if there exists a $(d'_i{-}l)$-flat $F\subseteq F'_{l,i}$ such that $|X\cap F|>c^{{1}/({d+1})}|X\cap F'_{l,i}|$, then we choose one of those flats F and we call it $F'_{l+1,i}$. Let $n_i$ be the greatest number $l\in \{1,2,\ldots , d'_i{+}1\}$ such that $F'_{l,i}$ can be constructed and write $F_i:=F'_{n_i,i}$ and $d_i:=\dim F_i=d'_i-n_i+1$. We shall show that $F_1,F_2,\ldots , F_k$ satisfy (ii). First, since $F_i\subseteq F'_{1,i}=F_{m,i}$ for each $i\in \{1,2,\ldots , k\}$, we have that $F_1,F_2,\ldots , F_k$ are pairwise skew by Remark 2.5(ii); in particular $F_1,F_2,\ldots , F_k$ are pairwise disjoint and $F_{m,1},F_{m,2},\ldots , F_{m,n-m+1}$ are pairwise disjoint, so

$$\begin{aligned} \begin{aligned} \Biggl |X\cap \bigcup _{i=1}^k F_i\Biggr |&=\sum _{i=1}^{k}|X\cap F_i|,\\ \Biggl |X\cap \bigcup _{i=1}^{n-m+1} \!\!F_{m,i}\Biggr |&=\sum _{i=1}^{n-m+1}\!\! |X\cap F_{m,i}|. \end{aligned} \end{aligned}$$

(5)

Second, from (4), $|X\cap F'_{1,i}|\ge {2}/{c}$ for all $i\le k$. Then we have that for all $i\in \{1,2,\ldots , k\}$,

$$\begin{aligned} |X\cap F_i|\ge c^{({n_i-1})/({d+1})}|X\cap F'_{1,i}|\ge 2c^{({n_i-d-2})/({d+1})}\ge 2. \end{aligned}$$

Thus $F_1,F_2,\ldots , F_k$ are nonzero dimensional. Third,

$$\begin{aligned} \sum _{i=1}^kd_i\le \sum _{i=1}^{k}d'_i\le \sum _{i=1}^{n-m+1}\!\!\dim F_{m,i}<d. \end{aligned}$$

Moreover, for all $i\in \{1,2,\ldots , k\}$, we already know that $F_i$ is nonzero dimensional so $n_i\le d'_i$; this leads to

$$\begin{aligned} n_i\le d'_i \le \sum _{i=1}^{k}d'_i\le \sum _{i=1}^{n-m+1}\!\!\dim F_{m,i}<d, \end{aligned}$$

and hence

$$\begin{aligned} |X\cap F_i|\ge c^{({n_i-1})/({d+1})}|X\cap F'_{1,i}|\ge c^{({d-1})/({d+1})}|X\cap F'_{1,i}|. \end{aligned}$$

(6)

Fourth,

$$\begin{aligned} \sum _{i=1}^{k} |X\cap F_{m,i}|&\ge \sum _{i=1}^{n-m+1} \!\!|X\cap F_{m,i}|-(n-m+1-k)\frac{2}{c}&\quad (\text {by } (4))\\&= \Biggl |X\cap \bigcup _{i=1}^{n-m+1} \!F_{m,i}\Biggr |-(n-m+1-k)\frac{2}{c}&\quad (\text {by } (5))\\&\ge c^{{1}/({d+1})}|X|-(n-m+1-k)\frac{2}{c}\\&\ge c^{{1}/({d+1})}|X|-\frac{2d}{c},&\quad (\text {by }(3)) \end{aligned}$$

and then, from (2), we get that

$$\begin{aligned} c^{({d-1})/({d+1})}\sum _{i=1}^{k} |X\cap F_{m,i}|\ge c|X|. \end{aligned}$$

(7)

Hence

$$\begin{aligned} \Biggl |X\cap \bigcup _{i=1}^k F_i\Biggr |&=\sum _{i=1}^{k}|X\cap F_i|&\quad (\text {by }(6))\\&\ge c^{({d-1})/({d+1})}\sum _{i=1}^{k} |X\cap F'_{1,i}|&\quad (\text {by }(7))\\&= c^{({d-1})/({d+1})}\sum _{i=1}^{k} |X\cap F_{m,i}|\ge c|X|.&\quad (\text {by }(8)) \end{aligned}$$

Finally, for each $i\in \{1,2,\ldots , k\}$, the maximality of $n_i$ implies that $|X\cap F|\le c^{{1}/({d+1})}|X\cap F_i|$ for any $(d_i{-}1)$-flat F contained in $F_i$. Then all the conditions of (ii) are satisfied. $\square$

The reason why we are interested in skew flats is the following.

Lemma 2.7

Let X and Y be disjoint finite subsets of ${\mathbb {R}}^d$. For any skew flats $F_1$ and $F_2$, the number of lines generated by $X\cap (F_1\cup F_2)$ that do not intersect Y is at least $|X\cap F_1|\cdot |X\cap F_2|-|Y|$.

Proof

Set $d_i:=\dim F_i$ for $i\in \{1,2\}$ and the family of lines

$$\begin{aligned} {\mathcal {L}}:=\{{\text {Fl}}{(\{{\mathbf {x}}_1,{\mathbf {x}}_2\})}:{\mathbf {x}}_1\in X\cap F_1,\,{\mathbf {x}}_2\in X\cap F_2\}. \end{aligned}$$

Translating if necessary, assume that the origin is contained in $F_1$. Let $\{{\mathbf {y}}_1,{\mathbf {y}}_2,\ldots , {\mathbf {y}}_{d_1}\}$ be a basis of $F_1$. Fix ${\mathbf {y}}_{d_1+1}\in F_2$ and let $\{{\mathbf {y}}_{d_1+2},{\mathbf {y}}_{d_1+3},\ldots , {\mathbf {y}}_{d_1+d_2+1}\}$ be a basis of $F_2-\{{\mathbf {y}}_{d_1+1}\}$. Take ${\mathbf {x}}_1,{\mathbf {x}}'_1\in X\cap F_1$ and ${\mathbf {x}}_2,{\mathbf {x}}'_2\in X\cap F_2$. Then

$$\begin{aligned} {\mathbf {x}}_1&=\sum _{j=1}^{d_1}\lambda _{j}{\mathbf {y}}_j,&{\mathbf {x}}_2&={\mathbf {y}}_{d_1+1}+\sum _{j=d_1+2}^{d_1+d_2+1}\lambda _{j}{\mathbf {y}}_j,\\ {\mathbf {x}}'_1&=\sum _{j=1}^{d_1}\lambda '_{j}{\mathbf {y}}_j,&{\mathbf {x}}'_2&={\mathbf {y}}_{d_1+1}+\sum _{j=d_1+2}^{d_1+d_2+1}\lambda '_{j}{\mathbf {y}}_j, \end{aligned}$$

and hence

$$\begin{aligned} {\text {Fl}}{(\{{\mathbf {x}}_1,{\mathbf {x}}_2\})}&=\Biggl \{\sum _{j=1}^{d_1}\mu \lambda _j{\mathbf {y}}_j+(1-\mu ){\mathbf {y}}_{d_1+1}+\sum _{j=d_1+2}^{d_1+d_2+1}(1-\mu )\lambda _{j}{\mathbf {y}}_j\,:\,\mu \in {\mathbb {R}}\Biggr \},\nonumber \\ {\text {Fl}}{(\{{\mathbf {x}}'_1,{\mathbf {x}}'_2\})}&=\Biggl \{\sum _{j=1}^{d_1}\mu \lambda '_j{\mathbf {y}}_j+(1-\mu ){\mathbf {y}}_{d_1+1}+\sum _{j=d_1+2}^{d_1+d_2+1}(1-\mu )\lambda '_{j}{\mathbf {y}}_j\,:\,\mu \in {\mathbb {R}}\Biggr \}. \end{aligned}$$

(8)

Since $F_1$ and $F_2$ are skew, $\{{\mathbf {y}}_1,{\mathbf {y}}_2,\ldots , {\mathbf {y}}_{d_1+d_2+1}\}$ is a basis of ${\text {Fl}}{(F_1\cup F_2)}$. Thereby if ${\mathbf {x}}_1\ne {\mathbf {x}}'_1$ and ${\mathbf {x}}_2\ne {\mathbf {x}}'_2$, we get from the explicit formulas of the lines in (8) that ${\text {Fl}}{(\{{\mathbf {x}}_1,{\mathbf {x}}_2\})}$ and ${\text {Fl}}{(\{{\mathbf {x}}'_1,{\mathbf {x}}'_2\})}$ are distinct, so $|{\mathcal {L}}|\ge |X\cap F_1|\cdot |X\cap F_2|$. Moreover, since X and Y are disjoint, the previous claim implies that each point of Y can be in at most one line of ${\mathcal {L}}$; therefore the number of lines in ${\mathcal {L}}$ that do not intersect Y is at least $|X\cap F_1|\cdot |X\cap F_2|-|Y|$, and this implies statement of the lemma.$\square$

Let F be a $d'$-flat of ${\mathbb {R}}^d$. For any $(d{-}d'{-}1)$-flat G of ${\mathbb {R}}^d$ disjoint from F, define the projection

$$\begin{aligned} \pi _{F,G}:{\mathbb {R}}^d\setminus F\rightarrow G,\qquad \{\pi _{F,G}({\mathbf {x}})\}=G\cap {\text {Fl}}{(F\cup \{{\mathbf {x}}\})}. \end{aligned}$$

The projection gives a bijective correspondence between the $(d'{+}1)$-flats that contain F and the points of $F'\simeq {\mathbb {R}}^{d-d'-1}$.

Lemma 2.8

Let F, G, and H be flats of ${\mathbb {R}}^d$ such that $F\subseteq G\subseteq H$ and set $d':=\dim H-\dim G$. Take ${\mathcal {F}}$ a family of $(\dim F{+}1)$-flats in ${\mathbb {R}}^d$ such that G and H are generated by ${\mathcal {F}}$, and K contains F for all $K\in {\mathcal {F}}$. Then there are $F_1,F_2,\ldots ,F_{d'}\in {\mathcal {F}}$ such that $H={\text {Fl}}{\bigl (G\cup \bigcup _{i=1}^{d'}F_i\bigr )}$.

Proof

First assume that $F=\emptyset$. In this case the proof is by induction on $d'$. If $d'=0$, $G=H$. Assume that the claim holds for all $0\le d''<d'$. Since $d'>0$ and G, H are generated by ${\mathcal {F}}$, there is ${\mathbf {x}}\in {\mathbb {R}}^d$ such that $\{{\mathbf {x}}\}\in {\mathcal {F}}$ and ${\mathbf {x}}\in H\setminus G$. Set $F_0:=\{{\mathbf {x}}\}$ and $K:={\text {Fl}}{(G\cup F_0)}$. Note that $\dim K=\dim G+1$. Clearly $F\subseteq K\subseteq H$ and K is generated by ${\mathcal {F}}$. Thus we can apply the induction, and therefore there exist $F_1,F_2,\ldots ,F_{d'-1}\in {\mathcal {F}}$ such that $H={\text {Fl}}{\bigl (K\cup \bigcup _{i=1}^{d'-1}F_i\bigr )}$. This completes the induction since

$$\begin{aligned} H={\text {Fl}}{\Biggl (\!K\cup \bigcup _{i=1}^{d'-1}F_i\Biggr )}={\text {Fl}}{\Biggl (\!G\cup \bigcup _{i=0}^{d'-1}F_i\Biggr )}. \end{aligned}$$

Now we show the general case. If $\dim F\ge d-1$, the statement is trivial. Thus, from now on, we assume that $\dim F<d-1$. Let ${\widehat{F}}$ be a $(d{-}\dim F{-}1)$-flat disjoint from F and the projection $\pi :=\pi _{F,{\widehat{F}}}$. We have that $\emptyset \subseteq \pi (G)\subseteq \pi (H)$. Set $\pi ({\mathcal {F}}):=\{\pi (K):K\in {\mathcal {F}}\}$ and note that it is a family of 0-flats in ${\widehat{F}}\simeq {\mathbb {R}}^{d-\dim F-1}$ such that $\pi (G)$ and $\pi (H)$ are generated by $\pi ({\mathcal {F}})$. Applying the case we solved in the previous paragraph, there are $F_1,F_2,\ldots ,F_{d'}\in {\mathcal {F}}$ such that

$$\begin{aligned} \pi (H)={\text {Fl}}{\Biggl (\!\pi (G)\cup \bigcup _{i=1}^{d'}\pi (F_i)\Biggr )}. \end{aligned}$$

(9)

Since $F_1,F_2,\ldots , F_{d'},G,H$ contain F, we get from (9) that

$$\begin{aligned} H={\text {Fl}}{\Biggl (\!G\cup \bigcup _{i=1}^{d'}F_i\Biggr )}, \end{aligned}$$

and this concludes the proof.$\square$

Lemma 2.9

Let X be a nonempty subset, $0<c<1$ and $k\in \{0,1,\ldots , d{-}1\}$. If X generates at least $c|X|^d$ hyperplanes, then it generates at least $c|X|^{k+1}$ k-flats.

Proof

The proof is done by a double induction first on d and then on $d-k$. If $d=1$, then $k=d-1=0$ and there is nothing to prove. We assume that the claim is true for all $1\le d'<d$ from now on. If $k=d-1$, we are done. We assume that the claim holds for all $k<k'\le d-1$. Let ${\mathcal {F}}$ be the family of k-flats generated by X and ${\mathcal {F}}'$ be the family of $(k{+}1)$-flats generated by X. For any $F'\in {\mathcal {F}}'$, there are ${\mathbf {x}}_1,{\mathbf {x}}_2,\ldots , {\mathbf {x}}_m\in X$ such that $F'={\text {Fl}}{(\{{\mathbf {x}}_1,{\mathbf {x}}_2,\ldots , {\mathbf {x}}_m\})}$. Let $n\in \{1,2,\ldots ,m\}$ be the minimum number satisfying $F'={\text {Fl}}{(\{{\mathbf {x}}_1,{\mathbf {x}}_2,\ldots , {\mathbf {x}}_{n+1}\})}$. On the one hand, the minimality of n leads to ${\text {Fl}}{(\{{\mathbf {x}}_1,{\mathbf {x}}_2,\ldots , {\mathbf {x}}_{n}\})}\subsetneq F'$. On the other hand, if we drop one point ${\mathbf {x}}_i$ from $F'={\text {Fl}}{(\{{\mathbf {x}}_1,{\mathbf {x}}_2,\ldots , {\mathbf {x}}_{n+1}\})}$, we lose at most one dimension; thereby $\dim {\text {Fl}}{(\{{\mathbf {x}}_1,{\mathbf {x}}_2,\ldots , {\mathbf {x}}_{n}\})}=k-1$. We have proven that for any $F'\in {\mathcal {F}}'$, there is $F\in {\mathcal {F}}$ such that $F\subseteq F'$. Therefore $|I({\mathcal {F}},{\mathcal {F}}')|\ge |{\mathcal {F}}'|$, and the induction hypothesis applied to ${\mathcal {F}}'$ leads to

$$\begin{aligned} |I({\mathcal {F}},{\mathcal {F}}')|\ge |{\mathcal {F}}'|\ge c|X|^{k+2}. \end{aligned}$$

(10)

Let $F\in {\mathcal {F}}$ and take $F'\in {\mathcal {F}}'$ such that $F\subseteq F'$. Lemma 2.8 (applied to the flats $\emptyset \subseteq F\subseteq F'$ and the family ${\mathcal {F}}:=\{\{{\mathbf {x}}\}:{\mathbf {x}}\in X\}$) implies the existence of ${\mathbf {x}}\in X$ such that $F'={\text {Fl}}{(F\cup \{{\mathbf {x}}\})}$. Then

$$\begin{aligned} |I(\{F\},{\mathcal {F}}')|\le |X|. \end{aligned}$$

(11)

This yields that

$$\begin{aligned} c|X|^{k+2}&\le |I({\mathcal {F}},{\mathcal {F}}')|&\quad (\text {by }(9))\\&=\sum _{F\in {\mathcal {F}}}|I(\{F\},{\mathcal {F}}')|\le |{\mathcal {F}}|\cdot |X|,&\quad (\text {by }(10)) \end{aligned}$$

and hence $|{\mathcal {F}}|\ge c|X|^{k+1}$ completing the induction. $\square$

3 A Key Ingredient

The purpose of this section is to prove Proposition 3.2. In order to do it, we need a technical lemma.

Lemma 3.1

Let $0<c\le {1}/{4}$, $k\in \{-1,0,\ldots , d{-}3\}$ and $n\in {\mathbb {N}}$ with $n\ge {5^3}/{c^5}$. Take

• a k-flat X of ${\mathbb {R}}^d$;

• a family ${\mathcal {F}}$ of $(k{+}1)$-flats of ${\mathbb {R}}^d$ such that $|{\mathcal {F}}|\le n$ and all its elements contain X;

• a family ${\mathcal {H}}$ of hyperplanes of ${\mathbb {R}}^d$ such that $|{\mathcal {H}}|\ge cn^{d-k-1}$ and all its elements are generated by ${\mathcal {F}}$;

• a family ${\mathcal {M}}$ of $(k{+}2)$-flats of ${\mathbb {R}}^d$ such that each element of ${\mathcal {M}}$ is generated by ${\mathcal {F}}$ and contained in some element of ${\mathcal {H}}$.

If $|{\mathcal {M}}|\le {c^5}n^2/{5^3}$, then there exists $X'\in {\mathcal {F}}$ with the following two properties.

• (i) If ${\mathcal {F}}'$ is the family of $(k{+}2)$-flats F of ${\mathbb {R}}^d$ such that F contains $X'$, F is generated by ${\mathcal {F}}$ and $F\not \in {\mathcal {M}}$, then $|{\mathcal {F}}'|\le n$.

• (ii) If ${\mathcal {M}}':=\{M\in {\mathcal {M}}: M\supseteq X'\}$ and ${\mathcal {H}}'$ is the family of elements $H\in {\mathcal {H}}$ which contain $X'$ and such that $M\nsubseteq H$ for all $M\in {\mathcal {M}}'$, then $|{\mathcal {H}}'|\ge {c}n^{d-k-2}/4$.

Proof

Set ${\mathcal {F}}_1:=\{F\in {\mathcal {F}}:I(\{F\},{\mathcal {H}})\ge {c}n^{d-k-2}/2\}$. For any $H\in {\mathcal {H}}$, H is generated by ${\mathcal {F}}$ so it contains at least one element of ${\mathcal {F}}$. Hence

$$\begin{aligned} |I({\mathcal {F}},{\mathcal {H}})|\ge |{\mathcal {H}}|. \end{aligned}$$

(12)

Let $F\in {\mathcal {F}}$ and $H\in {\mathcal {H}}$ be such that $F\subseteq H$. Since the elements of ${\mathcal {F}}$ and ${\mathcal {H}}$ are generated by ${\mathcal {F}}$ and the elements of ${\mathcal {F}}$ contain X, we can apply Lemma 2.8 to $X\subseteq F\subseteq H$ and ${\mathcal {F}}$. Hence there are $F_1,F_2,\ldots , F_{d-k-2}\in {\mathcal {F}}$ such that $H={\text {Fl}}{\bigl (F\cup \bigcup _{i=1}^{d-k-2}F_i\bigr )}$. Therefore

$$\begin{aligned} |I(\{F\},{\mathcal {H}})|\le \left( {\begin{array}{c}|{\mathcal {F}}|\\ d-k-2\end{array}}\right) \le n^{d-k-2}. \end{aligned}$$

(13)

Then we have that

$$\begin{aligned} cn^{d-k-1}&\le |{\mathcal {H}}|\le |I({\mathcal {F}},{\mathcal {H}})|&\quad (\text {by }(12))\\&=\sum _{F\in {\mathcal {F}}_1}\!|I(\{F\},{\mathcal {H}})|+\sum _{F\in {\mathcal {F}}\setminus {\mathcal {F}}_1}\!|I(\{F\},{\mathcal {H}})|\\&\le |{\mathcal {F}}_1|n^{d-k-2}+\sum _{F\in {\mathcal {F}}\setminus {\mathcal {F}}_1}|I(\{F\},{\mathcal {H}})|&\quad (\text {by }(12))\\&\le |{\mathcal {F}}_1|n^{d-k-2}+|{\mathcal {F}}\setminus {\mathcal {F}}_1|\frac{cn^{d-k-2}}{2}\\&\le \Bigl (|{\mathcal {F}}_1|+\frac{c}{2}(n-|{\mathcal {F}}_1|)\Bigr )n^{d-k-2},&\quad (\text {since } |{\mathcal {F}}|\le n) \end{aligned}$$

and thereby

$$\begin{aligned} |{\mathcal {F}}_1|\ge \frac{cn}{2}. \end{aligned}$$

(14)

Let $F_0$ be a $(d{-}k{-}1)$-flat disjoint from X and write $\pi :=\pi _{X,F_0}$ (recall that $\pi _{X,F_0}({\mathbf {x}})$ is the intersection of $F_0$ and ${\text {Fl}}{(X\cup \{{\mathbf {x}}\})}$ for any ${\mathbf {x}}\in {\mathbb {R}}^d\setminus X$). Set ${\mathcal {Y}}:=\{\pi (F):F\in {\mathcal {F}}\}$, ${\mathcal {Y}}_1:=\{\pi (F):F\in {\mathcal {F}}_1\}$ and the family of lines

$$\begin{aligned} {\mathcal {L}}:=\{L\text { line in }F_0:\pi ^{-1}(L)\in {\mathcal {M}}\}. \end{aligned}$$

The projection $\pi$ has the property that

$$\begin{aligned} |{\mathcal {F}}|=|{\mathcal {Y}}|,\qquad |{\mathcal {F}}_1|=|{\mathcal {Y}}_1|,\qquad |{\mathcal {M}}|=|{\mathcal {L}}|. \end{aligned}$$

(15)

Theorem 2.1 implies that

$$\begin{aligned} |I({\mathcal {Y}}_1,{\mathcal {L}})|\le 4\bigl (|{\mathcal {L}}|^{{2}/{3}}|{\mathcal {Y}}_1|^{{2}/{3}}+|{\mathcal {L}}|+|{\mathcal {Y}}_1|\bigr ). \end{aligned}$$

(16)

Since $n\ge {5^3}/{c^5}$, $|{\mathcal {F}}_1|\le |{\mathcal {F}}|\le n$, and $|{\mathcal {M}}|\le {c^5}n^2/{5^3}$, we get that

$$\begin{aligned} \frac{c^3n^2}{2}\ge 4\bigl (|{\mathcal {M}}|^{{2}/{3}}|{\mathcal {F}}_1|^{{2}/{3}}+|{\mathcal {M}}|+|{\mathcal {F}}_1|\bigr ). \end{aligned}$$

(17)

Thus

$$\begin{aligned} \frac{c^3n^2}{2}&\ge 4\bigl (|{\mathcal {M}}|^{{2}/{3}}|{\mathcal {F}}_1|^{{2}/{3}}+|{\mathcal {M}}|+|{\mathcal {F}}_1|\bigr )&\quad (\text {by }(17))\\&=4\bigl (|{\mathcal {L}}|^{{2}/{3}}|{\mathcal {Y}}_1|^{{2}/{3}}+|{\mathcal {L}}|+|{\mathcal {Y}}_1|\bigr )&\quad (\text {by }(15))\\&\ge |I({\mathcal {Y}}_1,{\mathcal {L}})|&\quad (\text {by }(16))\\&=\sum _{{\mathbf {y}}\in {\mathcal {Y}}_1}|I(\{{\mathbf {y}}\},{\mathcal {L}})|\ge |{\mathcal {Y}}_1|\min _{{\mathbf {y}}\in {\mathcal {Y}}_1}|I(\{{\mathbf {y}}\},{\mathcal {L}})|\\&= |{\mathcal {F}}_1|\min _{{\mathbf {y}}\in {\mathcal {Y}}_1}|I(\{{\mathbf {y}}\},{\mathcal {L}})|&\quad (\text {by }(15))\\&\ge \frac{cn}{2}\min _{{\mathbf {y}}\in {\mathcal {Y}}_1}|I(\{{\mathbf {y}}\},{\mathcal {L}})| ,&\quad (\text {by }(14)) \end{aligned}$$

and therefore there is ${\mathbf {x}}\in {\mathcal {Y}}_1$ such that $|I(\{{\mathbf {x}}\},{\mathcal {L}})|\le c^2n$; fix such ${\mathbf {x}}\in {\mathcal {Y}}_1$. Set $X':=\pi ^{-1}(\{{\mathbf {x}}\})$. Since $|I(\{{\mathbf {x}}\},{\mathcal {L}})|\le c^2n$, we get that

$$\begin{aligned} |I(X',{\mathcal {M}})|\le c^2n. \end{aligned}$$

(18)

$X'$ is a $(k{+}1)$-flat and $X'\in {\mathcal {F}}$ since ${\mathbf {x}}\in {\mathcal {Y}}$. For any $F'\in {\mathcal {F}}'$, $F'$ is generated by ${\mathcal {F}}$. Thus, applying Lemma 2.8 to $X\subseteq X'\subseteq F'$ and ${\mathcal {F}}$, there is $F\in {\mathcal {F}}$ such that $F'={\text {Fl}}{(F\cup X')}$. This implies that $|{\mathcal {F}}'|\le |{\mathcal {F}}|\le n$, and hence (i) holds.

The definition of ${\mathcal {H}}'$ yields that ${\mathcal {H}}'\subseteq {\mathcal {H}}$ and $M\nsubseteq H$ for all $H\in {\mathcal {H}}'$ and $M\in {\mathcal {M}}'$. For all $H\in {\mathcal {H}}$, there are $F_1,F_2,\ldots ,F_k\in {\mathcal {F}}$ such that $H={\text {Fl}}{\bigl (\bigcup _{i=1}^k F_i\bigr )}$ since ${\mathcal {H}}'\subseteq {\mathcal {H}}$ and the elements of ${\mathcal {H}}$ are generated by ${\mathcal {F}}$. Set $F'_i:={\text {Fl}}{(X'\cup F_i)}$ for all $i\in \{1,2,\ldots , k\}$. Since H contains $X'$, we get that $H={\text {Fl}}{\bigl (\bigcup _{i=1}^k F'_i\bigr )}$. Moreover, since $M\nsubseteq H$ for all $M\in {\mathcal {M}}'$ and $F'_i\subseteq H$ for all $i\in \{1,2,\ldots ,k\}$, $F'_i\notin {\mathcal {M}}$; thereby $F_i\in {\mathcal {F}}'$ for all $i\in \{1,2,\ldots ,k\}$ and thus H is generated by ${\mathcal {F}}'$. Finally, let $M\in {\mathcal {M}}'$ and $H\in {\mathcal {H}}$ be such that $X'\subseteq M\subseteq H$. Since the elements of ${\mathcal {M}}$ and ${\mathcal {H}}$ are generated by ${\mathcal {F}}$ and they contain $X'$, we can apply Lemma 2.8 to conclude there are $F_1,F_2,\ldots ,F_{d-k-3}\in {\mathcal {F}}$ such that $H={\text {Fl}}{\bigl (M\cup \bigcup _{i=1}^{d-k-3}F_i\bigr )}$. Therefore

$$\begin{aligned} |I(\{M\},{\mathcal {H}})|\le \left( {\begin{array}{c}|{\mathcal {F}}|\\ d-k-3\end{array}}\right) \le n^{d-k-3}. \end{aligned}$$

(19)

On the one hand, (19) implies each element of ${\mathcal {M}}'$ is contained in at most $n^{d-k-3}$ elements of ${\mathcal {H}}$. On the other hand, (18) yields that $|{\mathcal {M}}'|\le c^2n$. Therefore there are at most $c^2n^{d-k-2}$ elements of ${\mathcal {H}}$ that contain an element of ${\mathcal {M}}'$. Because ${\mathbf {x}}\in Y_1$, we have that $X'\in {\mathcal {F}}_1$ and thereby it is contained in at least ${c}n^{d-k-2}/{2}$ elements of ${\mathcal {H}}$. These claims lead to

$$\begin{aligned} |{\mathcal {H}}'|\ge \frac{cn^{d-k-2}}{2}-c^2n^{d-k-2}, \end{aligned}$$

and then $|{\mathcal {H}}'|\ge {c}n^{d-k-2}/{4}$ as $c\le {1}/{4}$; we have shown that (ii) is satisfied. $\square$

Proposition 3.2

Let X be a nonempty finite subset of ${\mathbb {R}}^d$ with $\dim X=d$, a coloring $X=\bigcup _{i=1}^m X_i$ with $m<d$ and $0<c\le {1}/{4}$. If X generates at least $c|X|^d$ hyperplanes and $|X|\ge {5^3\cdot 4^{5(m-1)}}/{c^5}$, then

$$\begin{aligned} \Biggl |{\mathcal {M}}\Biggl (\bigcup _{i=1}^mX_i\Biggr )\Biggr |\ge \frac{c^5}{5^3\cdot 4^{5(m-1)}}|X|^2. \end{aligned}$$

Proof

First we deal with the case $m=d{-}1$. In the first part of the proof, for $k\in \{-1,0,\ldots ,d{-}3\}$, we construct recursively a k-flat $X_k$, a family ${\mathcal {F}}_k$ of $(k{+}1)$-flats, a family ${\mathcal {H}}_k$ of hyperplanes, and a family ${\mathcal {M}}_k$ of $(k{+}2)$-flats, using Lemma 3.1. We start setting $n:=|X|$, $X_{-1}=\emptyset$, ${\mathcal {F}}_{-1}:=\{\{{\mathbf {x}}\}:{\mathbf {x}}\in X\}$, ${\mathcal {H}}_{-1}$ the family of hyperplanes generated by X and ${\mathcal {M}}_{-1}:={\mathcal {M}}\bigl (\bigcup _{i=1}^mX_i\bigr )$. If $|{\mathcal {M}}_{-1}|\le {c^5}n^2/{5^3}$, then Lemma 3.1 implies the existence of $X_0$, ${\mathcal {F}}_0$, and ${\mathcal {H}}_0$ satisfying (i) and (ii) of Lemma 3.1, respectively. For $k\in \{0,1,\ldots ,d{-}3\}$, assume that we have

• (i) a k-flat $X_k$ of ${\mathbb {R}}^d$ such that $X_{k}\in {\mathcal {F}}_{k-1}$;

• (ii) the family ${\mathcal {F}}_k$ of $(k{+}1)$-flats F of ${\mathbb {R}}^d$ such that F contains $X_k$, F is generated by ${\mathcal {F}}_{k-1}$ and $F\not \in {\mathcal {M}}_{k-1}$; in particular $|{\mathcal {F}}_k|\le n$;

• (iii) a family ${\mathcal {H}}_k$ of hyperplanes of ${\mathbb {R}}^d$ such that ${\mathcal {H}}_k\subseteq {\mathcal {H}}_{k-1}$, $|{\mathcal {H}}_k|\ge {c}n^{d-k-1}/{4^{k+1}}$, all its elements are generated by ${\mathcal {F}}_k$, and also $M\nsubseteq H$ for all $H\in {\mathcal {H}}_k$ and $M\in {\mathcal {M}}_{k-1}$ satisfying $M\supseteq X_k$;

• (iv) the family ${\mathcal {M}}_k$ of $(k{+}2)$-flats M of ${\mathbb {R}}^d$ generated by ${\mathcal {F}}_k$ such that M is contained in an element of ${\mathcal {H}}_k$ and M contains an element of ${\mathcal {M}}\bigl (\bigcup _{i=1}^mX_i\bigr )$.

If $|{\mathcal {M}}_k|\le {c^5}n^2/({5^3\cdot 4^{5(k+1)}})$, then Lemma 3.1 implies the existence of $X_{k+1}$, ${\mathcal {F}}_{k+1}$, $H_{k+1}$, and ${\mathcal {M}}_{k+1}$ satisfying (i), (ii), (iii), and (iv), respectively (with $k+1$ instead of k in each case). The next step in the proof is to show that this recursion has to stop before $k=m-1$; in other words, we shall show that

$$\begin{aligned} |{\mathcal {M}}_k|>\frac{c^5n^2}{5^3\cdot 4^{5(k+1)}} \qquad \text {for some}\ \;k\le m-2. \end{aligned}$$

(20)

If there is $k< m-2$ such that $|{\mathcal {M}}_k|>{c^5}n^2({5^3\cdot 4^{5(k+1)}})$, we are done. Hence we assume that $|{\mathcal {M}}_k|\le {c^5}n^2/({5^3\cdot 4^{5(k+1)}})$ for all $k<m-2$. Therefore there exist $X_{m-2}$, ${\mathcal {F}}_{m-2}$, ${\mathcal {H}}_{m-2}$, and ${\mathcal {M}}_{m-2}$ satisfying (i), (ii), (iii), and (iv), respectively. We shall show that

$$\begin{aligned} {\mathcal {M}}_{m-2}={\mathcal {H}}_{m-2}. \end{aligned}$$

(21)

For all $M\in {\mathcal {M}}_{m-2}$, M is contained in H for some $H\in {\mathcal {H}}_{m-2}$. However,

$$\begin{aligned} \dim H=d-1=m=\dim M \end{aligned}$$

so $M=H$; thereby ${\mathcal {M}}_{m-2}\subseteq {\mathcal {H}}_{m-2}$. For all $H\in {\mathcal {H}}_{m-2}$, H is generated by ${\mathcal {F}}_{m-2}$. Recall that for all $i\in \{0,\ldots ,m{-}2\}$ and $F\in {\mathcal {F}}_i$, F is generated by ${\mathcal {F}}_{i-1}$; iterating this fact, we conclude that H is generated by ${\mathcal {F}}_{-1}$, and thus H is generated by X; in particular,

$$\begin{aligned} \dim {(X\cap H)}=d-1=m. \end{aligned}$$

(22)

Notice that $\bigcup _{i=1}^{m}(X_i\cap H)$ is a coloring of $X\cap H$. Then, from (22), we can apply Theorem 1.2 to the coloring $X\cap H=\bigcup _{i=1}^{m}(X_i\cap H)$ in $H\simeq {\mathbb {R}}^{d-1}$ to conclude that there is $L\in {\mathcal {M}}\bigl (\bigcup _{i=1}^{m}(X_i\cap H)\bigr )$. Since $X\cap H\subseteq X$ and $X_i\cap H\subseteq X_i$ for all $i\in \{1,2,\ldots , m\}$, L contains at least two points of X and it is contained in a chromatic class $X_i$; in other words, $L\in {\mathcal {M}}\bigl (\bigcup _{i=1}^{m}X_i\bigr )$. Since $L\subseteq H$, we conclude that $H\in {\mathcal {M}}_{m-2}$. This proves ${\mathcal {H}}_{m-2}\subseteq {\mathcal {M}}_{m-2}$ and it completes the proof of (21). Because $|{\mathcal {H}}_{m-2}|\ge {c}n^{2}/{4^{m-1}}$, (21) implies (20).

Let $k\in \{-1,0,\ldots ,m{-}2\}$ be the minimum value satisfying (20). If $k=-1$, we are done by the definition of ${\mathcal {M}}_{-1}$; hence we assume that $k>-1$ from now on. The next step in the proof is to show that for all $l\in \{-1,0,\ldots ,k\}$, $M\in {\mathcal {M}}_k$ and F an $(l{+}1)$-flat generated by X such that $X_{l}\subseteq F\subseteq M$, we have $F\in {\mathcal {F}}_l$. We prove this claim by induction on l. For $l=-1$, the claim is trivial since ${\mathcal {F}}_{-1}=\{\{{\mathbf {x}}\}:{\mathbf {x}}\in X\}$. Assume that the claim holds for all $-1\le l'<l$. Since F is generated by X, $X_l\subseteq F$ and $\dim F-\dim X_l=1$, we get the existence of ${\mathbf {x}}\in X$ such that $F={\text {Fl}}{(X_l\cup \{{\mathbf {x}}\})}$. On the one hand, ${\text {Fl}}{(X_{l-1}\cup \{{\mathbf {x}}\})}$ is an l-flat generated by X such that $X_{l-1}\subseteq {\text {Fl}}{(X_{l-1}\cup \{{\mathbf {x}}\})}\subseteq M$ so, by induction, ${\text {Fl}}{(X_{l-1}\cup \{{\mathbf {x}}\})}\in {\mathcal {F}}_{l-1}$. On the other hand, $X_l\in {\mathcal {F}}_{l-1}$. Then F is generated by ${\mathcal {F}}_{l-1}$ since

$$\begin{aligned} F={\text {Fl}}{(X_l\cup \{{\mathbf {x}}\})}={\text {Fl}}{(X_l\cup (X_{l-1}\cup \{{\mathbf {x}}\}))}. \end{aligned}$$

Since $M\in {\mathcal {M}}_k$, there is $H\in {\mathcal {H}}_k$ containing M. Now $H\in {\mathcal {H}}_k\subseteq {\mathcal {H}}_l$ and $F\subseteq M\subseteq H$ so F cannot be in ${\mathcal {M}}_{l-1}$ by the definition of ${\mathcal {H}}_l$. Therefore $F\in {\mathcal {F}}_l$ and the induction is complete.

For each $M\in {\mathcal {M}}_k$, fix $L_M\in {\mathcal {M}}\bigl (\bigcup _{i=1}^mX_i\bigr )$ contained in M and $H_M\in {\mathcal {H}}_k$ that contains M. To complete the proof of the proposition when $m=d-1$, the last step is to show the injectivity of the correspondence

$$\begin{aligned} {\mathcal {M}}_k\rightarrow {\mathcal {M}}\Biggl (\bigcup _{i=1}^{m}X_i\Biggr ),\qquad M\mapsto L_M. \end{aligned}$$

Suppose that there are $M,M'\in {\mathcal {M}}_k$ such that $L_{M}=L_{M'}$. Set $M'':={\text {Fl}}{(X_k\cup L_M)}$. We claim that

$$\begin{aligned} \dim M''=k+2. \end{aligned}$$

(23)

If $\dim M''\le k+1$, we get a contradiction as follows. Set $l:=\dim M''-1$. Recall that the elements of ${\mathcal {F}}_{k-1}$ are generated by ${\mathcal {F}}_{k-2}$, the elements of ${\mathcal {F}}_{k-2}$ are generated by ${\mathcal {F}}_{k-3}$, etc.; hence $X_k\in {\mathcal {F}}_{k-1}$ is generated by X. On the one hand, $M''$ is generated by X since $X_k$ and $L_M$ are generated by X. Also note that $X_l\subseteq X_k\subseteq M''\subseteq M$. Thus the previous paragraph implies that $M''\in {\mathcal {F}}_{l}$. On the other hand, the following three claims prove that $M''\in {\mathcal {M}}_{l-1}$:

• $\star$ $M''$ is generated by elements of ${\mathcal {F}}_{l-1}$ (since $M''\in {\mathcal {F}}_{l}$).

• $\star$ $M''\subseteq M\subseteq H_M$ with $H_M\in {\mathcal {H}}_k\subseteq {\mathcal {H}}_{l-1}$.

• $\star$ $L_M\subseteq M''$.

However, this is impossible since ${\mathcal {F}}_l$ and ${\mathcal {M}}_{l-1}$ are disjoint; thereby (23) is true. Since $M\cap M'$ contains $X_k$ and $L_M$, $M\cap M'$ contains $M''$. However, (23) implies that $\dim M''=k+2=\dim M=\dim M'$ so $M=M'$. Thus the correspondence $M\mapsto L_M$ is injective and, as a consequence,

$$\begin{aligned} \Biggl |{\mathcal {M}}\Biggl (\bigcup _{i=1}^{m}X_i\Biggr )\Biggr |\ge |{\mathcal {M}}_k|\ge \frac{c^5n^2}{5^3\cdot 4^{5(k+1)}}\ge \frac{c^5n^2}{5^3\cdot 4^{5(m-1)}}. \end{aligned}$$

Finally we show the general case using the case $m=d-1$. Because X is finite, we can find an $(m{+}1)$-flat $F_0$ and $\pi :{\mathbb {R}}^d\rightarrow F_0$ its orthogonal projection such that $\dim \pi (F)=\dim F$ for any flat F generated by X such that $\dim F\le m$; in particular $|\pi (X)|=|X|$. Set $X':=\pi (X)$ and $X'_i:=\pi (X_i)$ for all $i\in \{1,2,\ldots ,m\}$. Because $\pi$ is the orthogonal projection and $\dim X=d$, notice that $\dim X'=m+1$. Since X generates at least $c|X|^d$ hyperplanes, X generates at least $c|X|^{m+1}$ m-flats by Lemma 2.9. Therefore $X'$ generates at least $c|X'|^{m+1}$ hyperplanes in $F_0$. Then $X'$ with its coloring $X'=\bigcup _{i=1}^m X'_i$ satisfies all the assumptions of the case $m=d-1$, so

$$\begin{aligned} \Biggl |{\mathcal {M}}\Biggl (\bigcup _{i=1}^{m}X'_i\Biggr )\Biggr |\ge \frac{c^5}{5^3\cdot 4^{5(m-1)}}|X'|^2=\frac{c^5}{5^3\cdot 4^{5(m-1)}}|X|^2. \end{aligned}$$

(24)

For any $L'\in {\mathcal {M}}\bigl (\bigcup _{i=1}^{m}X'_i\bigr )$, fix ${\mathbf {x}}'_1,{\mathbf {x}}'_2\in L'\cap X'$ with ${\mathbf {x}}'_1\ne {\mathbf {x}}'_2$ and ${\mathbf {x}}_1,{\mathbf {x}}_2\in X$ such that $\pi ({\mathbf {x}}_j)={\mathbf {x}}'_j$ for $j\in \{1,2\}$. Set $L:={\text {Fl}}{(\{{\mathbf {x}}_1,{\mathbf {x}}_2\})}$. Since $L'\in {\mathcal {M}}\bigl (\bigcup _{i=1}^{m}X'_i\bigr )$, notice that $L\in {\mathcal {M}}\bigl (\bigcup _{i=1}^{m}X_i\bigr )$. Also note that $\pi (L)=L'$. Clearly the correspondence

$$\begin{aligned} {\mathcal {M}}\Biggl (\bigcup _{i=1}^{m}X'_i\Biggr )\rightarrow {\mathcal {M}}\Biggl (\bigcup _{i=1}^{m}X_i\Biggr ),\qquad L'\mapsto L, \end{aligned}$$

is injective, so

$$\begin{aligned} \Biggl |{\mathcal {M}}\Biggl (\bigcup _{i=1}^{m}X_i\Biggr )\Biggr |\ge \Biggl |{\mathcal {M}}\Biggl (\bigcup _{i=1}^{m}X'_i\Biggr )\Biggr |, \end{aligned}$$

and the result follows from (24).$\square$

4 Proofs of the Main Results

In this section we complete the proofs of the main results.

Proof of Theorem 1.3

Assume that

$$\begin{aligned} |X|\ge \frac{2d}{c'(1-c^{{1}/{(d+1)^2}})c^{({d+2})/{(d+1)^2}}}, \end{aligned}$$

so the conditions of Corollary 2.6 are satisfied by $X_i$ for the value $c^{{1}/({d+1})}$. Let $c''>0$ be the number corresponding to $c^{{1}/({d+1})}$ as in Corollary 2.6; assume without loss of generality that $c''\le 1/{4}$. The proof will depend on which case of Corollary 2.6 is satisfied by $X_i$. Since no hyperplane H of ${\mathbb {R}}^d$ contains more than $c|X_i|$ points of $X_i$, Corollary 2.6(i) is impossible. If Corollary 2.6(iii) holds, then $X_i$ generates at least $c''|X_i|^d$ hyperplanes in ${\mathbb {R}}^d$. Because $X_i$ is contained in X and $c'|X|\le |X_i|$, we have that X generates at least $c''c'^d|X|^d$ hyperplanes. Then the assumptions of Proposition 3.2 are satisfied by X, so

$$\begin{aligned} \Biggl |{\mathcal {M}}\Biggl (\bigcup _{j=1}^mX_j\Biggr )\Biggr |=\varTheta _{c''c'^d,m}(|X|^2)=\varTheta _{c,c',m,d}(|X|^2). \end{aligned}$$

It remains to prove the claim when $X_i$ is as in Corollary 2.6(ii). Let $F_1,F_2 ,\ldots , F_k$ be nonzero dimensional pairwise skew flats of ${\mathbb {R}}^d$ such that

$$\begin{aligned} \sum _{j=1}^k\dim F_j<d \end{aligned}$$

(25)

and $\bigl |X_i\cap \bigcup _{j=1}^kF_j\bigr |\ge c^{{1}/({d+1})}|X_i|$. For all $j\in \{1,2,\ldots ,k\}$, we have

$$\begin{aligned} \dim F_j\le \sum _{l=1}^k\dim F_l<d. \end{aligned}$$

For any hyperplane H of ${\mathbb {R}}^d$, we have that $|X_i\cap H|\le c|X_i|$; in particular this is true for any hyperplane containing $F_j$ so

$$\begin{aligned} |X_i\cap F_j|\le c|X_i|. \end{aligned}$$

(26)

Rearranging if necessary, assume that

$$\begin{aligned} |X_i\cap F_1|\le |X_i\cap F_2|\le \ldots \le |X_i\cap F_k|. \end{aligned}$$

From (26) applied to $j=k$, we conclude that

$$\begin{aligned} \Biggl |X_i\cap \bigcup _{l=1}^{k-1} F_l\Biggr |\ge \Biggl |X_i\cap \bigcup _{l=1}^{k} F_l\Biggr |-|X_i\cap F_k|\ge (c^{{1}/({d+1})}-c)|X_i|, \end{aligned}$$

and thereby

$$\begin{aligned} |X_i\cap F_{k-1}|\ge \frac{1}{k-1}\Biggl |X_i\cap \bigcup _{l=1}^{k-1} F_l\Biggr |\ge \frac{c^{{1}/({d+1})}-c}{k-1}|X_i|. \end{aligned}$$

Thus

$$\begin{aligned} |X_i\cap F_{k}| \ge |X_i\cap F_{k-1}|\ge \frac{c^{{1}/({d+1})}-c}{k-1}|X_i|. \end{aligned}$$

(27)

Let ${\mathcal {L}}$ be the family of lines generated by $X_i\cap (F_{k-1}\cup F_k)$ without elements in $X\setminus X_i$. Applying Lemma 2.7 to the sets $X_i$ and $X\setminus X_i$ and the skew flats $F_{k-1}$ and $F_k$, we get that

$$\begin{aligned} |{\mathcal {L}}|\ge |X_i\cap F_{k-1}|\cdot |X_{i}\cap F_k|-|X\setminus X_i|. \end{aligned}$$

(28)

Hence

$$\begin{aligned} \Biggl |{\mathcal {M}}\Biggl (\bigcup _{j=1}^mX_j\Biggr )\Biggr |&\ge |{\mathcal {L}}|\ge |X_i\cap F_{k-1}|\cdot |X_{i}\cap F_k|-|X\setminus X_i|&(\text {by })\\&\ge \biggl (\frac{c^{{1}/({d+1})}-c}{k-1}\biggr )^{\!2}|X_i|^2-|X\setminus X_i|&(\text {by }(27))\\&\ge \biggl (\frac{c^{{1}/({d+1})}-c}{d}\biggr )^{\!2}|X_i|^2-|X\setminus X_i|&(\text {by }(25))\\&\ge \biggl (\frac{c'(c^{{1}/({d+1})}-c)}{d}\biggr )^{\!2}|X|^2-|X|,&\end{aligned}$$

and then also in this case

$$\begin{aligned} \Biggl |{\mathcal {M}}\Biggl (\bigcup _{j=1}^mX_j\Biggr )\Biggr |=\varTheta _{c,c',m,d}(|X|^2). \end{aligned}$$

$\square$

Remark 4.1

With the notation as in Theorem 1.3, it can be obtained explicitly from the proof that if |X| is at least

$$\begin{aligned}&\max {\biggl \{\frac{2d}{c'(1-c^{{1}/{(d+1)^2}})c^{({d+2})/{(d+1)^2}}},\frac{5^3\cdot 4^{5(m-1)}}{(c''{c'}{}^d){}^5},\frac{4d^2}{c'^2(c^{{1}/({d+1})}-c)^2}\biggr \}}\\&\quad \ge \frac{2d}{c'(1-c^{{1}/{(d+1)^2}})c^{({d+2})/{(d+1)^2}}}\cdot \frac{5^3\cdot 4^{5(m-1)}}{(c''{c'}{}^d){}^5}\cdot \frac{4d^2}{c'^2(c^{{1}/({d+1})}-c)^2}, \end{aligned}$$

then

$$\begin{aligned} \Biggl |{\mathcal {M}}\Biggl (\bigcup _{j=1}^mX_j\Biggr )\Biggr |&\ge \min {\biggl \{\frac{(c''{c'}{}^d){}^5}{5^3\cdot 4^{5(m-1)}},\,\frac{c'^2(c^{{1}/({d+1})}-c)^2}{2d^2}\biggr \}}\cdot |X|^2\\&\ge \frac{(c''{c'}{}^d){}^5}{5^3\cdot 4^{5(m-1)}}\cdot \frac{c'^2(c^{{1}/({d+1})}-c)^2}{2d^2}\cdot |X|^2. \end{aligned}$$

We prove Theorem 1.4.

Proof of Theorem 1.4

First we establish some notation and parameters that will be used in the proof. Corollary 2.6 states that for any $0<b<1$ and Y nonempty finite subset of ${\mathbb {R}}^e$ with

$$\begin{aligned} |Y|\ge \frac{2e}{(1-b^{{1}/({e+1})})b^{({e+2})/({e+1})}}, \end{aligned}$$

there is $0<b'<1$ such that at least one of the three statements there holds. For any b and e as above, we will fix one of those $0<b'<1$ and we will denote it by $\phi (b,e)$. For each $0<b<1$ and $n,e\in {\mathbb {N}}\cup \{0\}$, set $\tau _{n,e}(b):=b^{{1}/{(e+1)^{n}}}$; more generally, for ${\mathbf {n}}=(n_1,n_2,\ldots ,n_k),{\mathbf {e}}=(e_1,e_2,\ldots ,e_k)\in ({\mathbb {N}}\cup \{0\})^k$, write

$$\begin{aligned} \tau _{{\mathbf {n}},{\mathbf {e}}}(b):=\tau _{n_k,e_k}(\ldots (\tau _{n_2,e_2}(\tau _{n_1,e_1}(b))). \end{aligned}$$

Set $I_n:=\bigl \{{\mathbf {n}}=(n_1,n_2,\ldots , n_k)\in ({\mathbb {N}}\cup \{0\})^k:k\in {\mathbb {N}},\,\sum _{i=1}^{k}n_k\le n\bigr \}$. Define the parameters

$$\begin{aligned} \phi _{n,e}(b):=&\min {\{\phi (\tau _{{\mathbf {n}},{\mathbf {e}}}(b),e'):{\mathbf {n}}\in I_n,\,{\mathbf {e}}\in I_e,\,e'\le e\}},\\ \rho _{n,e}(b):=&\min {\biggl \{\min {\biggl \{\frac{\tau _{4,e}(\tau _{{\mathbf {n}},{\mathbf {e}}}(b))}{\tau _{3,e}(\tau _{{\mathbf {n}},{\mathbf {e}}}(b))}-1,\,1\biggl \}^{\!2}}:{\mathbf {n}}\in I_n,\,{\mathbf {e}}\in I_e \biggr \}},\\ \theta _{n,e}(b):=&\min {\biggl \{\biggl (\frac{\tau _{2,e}(\tau _{{\mathbf {n}},{\mathbf {e}}}(b))-\tau _{{\mathbf {n}},{\mathbf {e}}}(b)}{2e}\biggr )^{\!2}:{\mathbf {n}}\in I_n,\,{\mathbf {e}}\in I_e\biggr \}},\\ \varrho _{n,e}(b):=&\min {\bigl \{(1-\tau _{1,e'}(\tau _{{\mathbf {n}},{\mathbf {e}}}(b)))\tau _{1,e'}\bigl (\tau _{{\mathbf {n}},{\mathbf {e}}}(b)^{({e'+2})/({e'+1})}\bigr )}:\\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \,\,\,{:{\mathbf {n}}\in I_n,\,{\mathbf {e}}\in I_e,\,e'\le e\bigr \}},\\ \varphi _{n,e}(b):=&\biggl (\frac{1}{2}\biggr )^{\!({16^n-1})/({16-1})}\biggl (\frac{\phi _{4n,e}(b)\cdot \rho _{4n,e}(b)\cdot \theta _{4n,e}(b)}{n^4\cdot 5^3\cdot 4^{5(4n-1)}}\biggr )^{\!16^n},\\ \psi _{n,e}(b):=&\frac{2e}{\varphi _{n,e}(b)\cdot \varrho _{4n,e}(b)}. \end{aligned}$$

Notice that for all $n'>n$, $e'> e$, and $0<b<1$, we have that $b<\tau _{n,e}(b)<\tau _{n',e}(b)<1$ and $b<\tau _{n,e}(b)<\tau _{n,e'}(b)<1$. Then $0< \varphi _{n,e}(b)< 1$ and $\psi _{n,e}(b)>0$. Also

$$\begin{aligned} \begin{aligned} \varphi _{n,e}(b)&\ge \varphi _{n',e}(b)\qquad \text { if }n\le n',\\ \varphi _{n,e}(b)&\ge \varphi _{n,e'}(b)\qquad \text { if }e\le e',\\ \psi _{n,e}(b)&\le \psi _{n',e}(b)\qquad \text { if }n\le n',\\ \psi _{n,e}(b)&\le \psi _{n,e'}(b)\qquad \text { if }e\le e'. \end{aligned} \end{aligned}$$

(29)

Since

$$\begin{aligned} \phi _{4n-4,e}(\tau _{4,e}(b))&\ge \phi _{4n,e}(b),&\rho _{4n-4,e}(\tau _{4,e}(b))&\ge \rho _{4n,e}(b),\\ \theta _{4n-4,e}(\tau _{4,e}(b))&\ge \theta _{4n,e}(b),&\varrho _{4n-4,e}(\tau _{4,e}(b))&\ge \varrho _{4n,e}(b), \end{aligned}$$

we have that

$$\begin{aligned} \begin{aligned} \varphi _{n-1,e}(\tau _{4,e}(b))&\ge 2\varphi _{n,e}(b)^{{1}/{16}},\\ \psi _{n-1,e}(\tau _{4,e}(b))&\le \varphi _{n,e}(b)^{{1}/{16}}\cdot \psi _{n,e}(b). \end{aligned} \end{aligned}$$

(30)

We will show by induction on m that if

$$\begin{aligned} |X|\ge \psi _{m,d}(c), \end{aligned}$$

(31)

then

$$\begin{aligned} \Biggl |{\mathcal {M}}\Biggl (\bigcup _{j=1}^mX_j\Biggr )\Biggr |\ge \varphi _{m,d}(c)|X|^2, \end{aligned}$$

(32)

and this will imply the proof of the theorem. First assume that $m=1$. Then X has one chromatic class which is precisely X. Since $m<2m\le d$, we can apply Theorem 1.3 to X. Notice that

$$\begin{aligned} \varphi _{1,d}(c)&\le \frac{1}{2}\cdot \frac{\phi _{1,d}(c)^5}{5^3}\cdot \biggl (\frac{\tau _{1,d}(c)-c}{2d}\biggr )^{\!2},\\ \psi _{1,d}(c)&\ge \frac{2d}{(1-\tau _{1,d}(c))\tau _{1,d}(c^{({d+2})/({d+1})})}\cdot \frac{5^3}{\phi _{1,d}(c)^5}\cdot \biggl (\frac{2d}{\tau _{1,d}(c)-c}\biggr )^{\!2}. \end{aligned}$$

Then Remark 4.1 yields that (31) implies (32) in this case.

From now on assume that (31) implies (32) for all $1\le m'<m$. Assume that X satisfies (31); then we can apply Corollary 2.6 to X with the value $\tau _{2,d}(c)$. The completion of the induction will depend on which case of Corollary 2.6 applies to X. First, since no hyperplane of ${\mathbb {R}}^d$ contains more than c|X| points of X, X is not in Corollary 2.6(i). If X is in Corollary 2.6(iii), then Proposition 3.2 implies (32). Thus it remains to complete the induction when X is in Corollary 2.6(ii). Let $F_1,F_2,\ldots , F_k$ be nonzero dimensional pairwise skew flats of ${\mathbb {R}}^d$. Set $d_i:=\dim F_i$ for all $i\in \{1,2,\ldots , k\}$. Then:

• (I) $\sum _{i=1}^k d_i<d$.

• (II) $\bigl |X\cap \bigcup _{i=1}^k F_i\bigr |\ge \tau _{2,d}(c)|X|$.

• (III) For all $i\in \{1,2,\ldots , k\}$, $|X\cap F|\le \tau _{3,d}(c)|X\cap F_i|$ for each $(d_i{-}1)$-flat F contained in $F_i$.

To abbreviate the notation, we write

$$\begin{aligned} c':=\frac{\varphi _{m,d}(c)^{{1}/{16}}}{\min {\{{\tau _{4,d}(c)}/{\tau _{3,d}(c)}-1,1\}}}+\varphi _{m,d}(c)^{{1}/{4}},\qquad c'':=\frac{\varphi _{m,d}(c)^{{1}/{4}}}{m}. \end{aligned}$$

Assume without loss of generality that

$$\begin{aligned} |X\cap F_1|\ge |X\cap F_2|\ge \cdots \ge |X\cap F_k|. \end{aligned}$$

Hence

$$\begin{aligned} |X\cap F_1|&\ge \frac{1}{k}\sum _{i=1}^{k}|X\cap F_i|\ge \frac{1}{k}\Biggl |X\cap \bigcup _{i=1}^k F_i\Biggr |\ge \frac{\tau _{2,d}(c)}{k}|X|&(\text {by (II}))\\&\ge \frac{\tau _{2,d}(c)}{d}|X|.&(\text {by (I})) \end{aligned}$$

Because

$$\begin{aligned} \varphi _{m,d}(c)\le \biggl (\frac{1}{2}\cdot \frac{\tau _{2,d}(c)}{d}\cdot \min {\biggl \{\frac{\tau _{4,d}(c)}{\tau _{3,d}(c)}-1,1\biggr \}}\biggr )^{\!16}, \end{aligned}$$

we have ${\tau _{2,d}(c)}/{d}\ge c'$. Then there is $k'\in \{1,2,\ldots ,k\}$ such that

$$\begin{aligned} |X\cap F_1|\ge \cdots \ge |X\cap F_{k'}|\ge c'|X|>|X\cap F_{k'+1}|\ge \cdots \ge |X\cap F_k|. \end{aligned}$$

(33)

For each $i\in \{1,2,\ldots , m\}$, set

$$\begin{aligned} {\mathcal {F}}_i:=\{F_j\in \{F_1,\ldots , F_{k'}\}:|X_i\cap F_j|\ge c''|X|\}; \end{aligned}$$

since $\sum _{j=1}^m|X_j\cap F_1|\ge |X\cap F_1|$, (33) yields that there is at least one $i\in \{1,2,\ldots , m\}$ such that ${\mathcal {F}}_i\ne \emptyset$. The conclusion of the induction is divided into two cases.

Case 1. Assume that $|{\mathcal {F}}_i|\le 1$ for all $i\in \{1,2,\ldots , m\}$. We already know that there is an ${\mathcal {F}}_i$ that is nonempty. Therefore, rearranging if necessary, we assume that there is $m'\in \{1,2,\ldots , m\}$ such that $|{\mathcal {F}}_1|=|{\mathcal {F}}_2|=\cdots =|{\mathcal {F}}_{m'}|=1$ and $|{\mathcal {F}}_{m'+1}|=|{\mathcal {F}}_{m'+2}|=\cdots =|{\mathcal {F}}_{m}|=0$. For each $i\in \{1,2,\ldots , m'\}$, let $\sigma (i)$ be the element of $\{1,2,\ldots , k'\}$ such that ${\mathcal {F}}_i=\{F_{\sigma (i)}\}$; also set

$$\begin{aligned} I:=\{\sigma (j):j\in \{1,2,\ldots , m'\}\}. \end{aligned}$$

Notice that

$$\begin{aligned} |X_i\cap F_j|< c''|X|\qquad \text {for all } i\in \{1,2,\ldots , m\} \text { such that } F_j\not \in {\mathcal {F}}_i. \end{aligned}$$

(34)

Thus

$$\begin{aligned} \Biggl |X\,\cap \!\!\bigcup _{j\in \{1,\ldots ,k'\}\setminus I}\!\!F_j\Biggr |\le \sum _{i=1}^m\,\Biggl |X_i\,\cap \!\!\bigcup _{j\in \{1,\ldots ,k'\}\setminus I}\!\!F_j\Biggr |<mk'c''|X|. \end{aligned}$$

(35)

From (II), (33), and (35), we are able to bound $\bigl |X\setminus \bigcup _{i\in I} F_i\bigr |$ from above as follows:

$$\begin{aligned} \begin{aligned} \Biggl |X\setminus \bigcup _{i\in I}F_i\Biggr |&\le \Biggl |X\setminus \bigcup _{i=1}^kF_i\Biggr |+\Biggl |X\,\cap \!\bigcup _{i=k'+1}^k\!F_i\Biggr |+\Biggl |X\,\cap \!\bigcup _{j\in \{1,\ldots ,k'\}\setminus I}\!F_j\Biggr |\\&< (1-\tau _{2,d}(c))|X|+(k-k')c'|X|+mk'c''|X|\\&=\bigl (1-\tau _{2,d}(c)+ (k-k')c'+mk'c''\bigr )|X|. \end{aligned} \end{aligned}$$

(36)

Note that

$$\begin{aligned} c', mc''\le 2\varphi _{m,d}(c)^{{1}/{4}}\le \frac{\tau _{2,d}(c)-c}{4d}. \end{aligned}$$

(37)

Therefore

$$\begin{aligned} \Biggl |X\cap \bigcup _{i\in I} F_i\Biggr |&=|X|-\Biggl |X\setminus \bigcup _{i\in I} F_i\Biggr |&\\&>\bigl (\tau _{2,d}(c)- (k-k')c'-mk'c''\bigr )|X|&\quad (\text {by }(36))\\&\ge (\tau _{2,d}(c)- dc'-mdc'')|X|&\quad (\text {by (I)})\\&\ge c|X|.&\quad (\text {by }(37)) \end{aligned}$$

This means that $\bigcup _{i\in I} F_i$ cannot be contained in a hyperplane, and we conclude that

$$\begin{aligned} \dim \bigcup _{i\in I} F_i=d. \end{aligned}$$

(38)

For all $i\in I$, set $J_i:=\{j\in \{1,2,\ldots , k'\}:\sigma (j)=i\}$ and $m_i:=|J_i|$; then $\sum _{i\in I}m_i=m'$ and $m_i\ge 1$ for all $i\in I$. From (I), we have that for all $i\in I$

$$\begin{aligned} d_i\le \sum _{j=1}^k d_j<d \end{aligned}$$

so (38) implies that $|I|>1$; this fact yields

$$\begin{aligned} m_i=m'\,-\!\sum _{j\in I\setminus \{i\}}m_j\le m\,-\!\sum _{j\in I\setminus \{i\}}m_j<m\qquad \text {for all}\ i\in I. \end{aligned}$$

(39)

We claim that there is $i\in I$ such that $2m_i\le d_i$ and we prove it by contradiction. Assume that

$$\begin{aligned} 2m_i>d_i\qquad \text {for all}\ i\in I. \end{aligned}$$

(40)

From Remark 2.5(i) and (38),

$$\begin{aligned} \dim \bigcup _{i\in I} F_i\le \sum _{i\in I}d_i+|I|-1. \end{aligned}$$

(41)

Then

$$\begin{aligned} d\ge 2m\ge 2m'&=\sum _{i\in I}2m_i\ge \sum _{i\in I}d_i+|I|&\quad (\text {by }(40))\\&\ge \dim \bigcup _{i\in I} F_i+1&\quad (\text {by }(41))\\&= d+1,&\quad (\text {by }(38)) \end{aligned}$$

and this is the contradiction we were looking for. Fix $i\in I$ such that

$$\begin{aligned} 2m_i\le d_i. \end{aligned}$$

(42)

Set $X'_j:=X_j\cap F_i$ for all $j\in J_i$ and $X':=\bigcup _{j\in J_i} X'_j=\bigl (\bigcup _{j\in J_i}X_j\bigr )\cap F_i$. From (34),

$$\begin{aligned} |(X\cap F_i)\setminus X'|\,\le \!\!\sum _{j\in \{1,2,\ldots , m\}\setminus J_i}\!\!|X_j\cap F_i|<(m-m_i)c''|X|\le mc''|X|. \end{aligned}$$

(43)

Thus (33) and (43) lead to

$$\begin{aligned} |X'|=|X\cap F_i|-|(X\cap F_i)\setminus X'|\ge (c'-mc'')|X|. \end{aligned}$$

(44)

Then

$$\begin{aligned} |X\cap F_i|&=|X'|+ |(X\cap F_i)\setminus X'|\nonumber \\&=|X'|+mc''|X|&\quad (\text {by }(43))\nonumber \\&\le \biggl (1+\frac{mc''}{c'-mc''}\biggr )|X'|.&\quad (\text {by } (44)) \end{aligned}$$

(45)

Since $\varphi _{m,d}(c)<1$, we have $\varphi _{m,d}(c)^{{1}/{16}}\ge \varphi _{m,d}(c)^{{1}/{4}}$ and thus

$$\begin{aligned} 1+\frac{mc''}{c'-mc''}\le \frac{\tau _{4,d}(c)}{\tau _{3,d}(c)}. \end{aligned}$$

(46)

For any $(d_i{-}1)$-flat F contained in $F_i$, we get that

$$\begin{aligned} |X'\cap F|&\le |X\cap F|\le \tau _{3,d}(c)|X\cap F_i|&\quad (\text {by (III)})\nonumber \\&\le \tau _{3,d}(c)\biggl (1+\frac{mc''}{c'-mc''}\biggr )|X'|&\quad (\text {by } (45))\\&\le \tau _{4,d}(c)|X'|.&\quad (\text {by }(46))\nonumber \end{aligned}$$

(47)

From (30),

$$\begin{aligned} (c'-mc'')\psi _{m,d}(c)=\frac{\varphi _{m,d}(c)^{{1}/{16}}\psi _{m,d}(c)}{\min {\{{\tau _{4,d}(c)}/{\tau _{3,d}(c)}-1,1\}}}\ge \psi _{m-1,d}(\tau _{4,d}(c)). \end{aligned}$$

(48)

Thus

$$\begin{aligned} \begin{array}{ll} |X'|\ge (c'-mc'')|X|&{}\quad \quad \quad \quad (\text {by }(44))\\ \qquad \,\, \ge (c'-mc'')\psi _{m,d}(c)&{}\quad \quad \quad \quad (\text {by }(31))\\ \qquad \,\,\ge \psi _{m-1,d}(\tau _{4,d}(c))&{}\quad \quad \quad \quad (\text {by }(48))\\ \qquad \,\, \ge \psi _{m_i,d_i}(\tau _{4,d}(c)). &{}\quad \quad \quad \quad (\text {by } (29),(39)) \end{array} \end{aligned}$$

(49)

From (39), (42), (47), and (49), we have that $X'$ with the coloring $X'=\bigcup _{j\in J_i}X'_j$ and the value $\tau _{4,d}(c)$ satisfy the conditions and we can apply the induction hypothesis. Therefore

$$\begin{aligned} \Biggl |{\mathcal {M}}\Biggl (\bigcup _{j\in J_i}X'_j\Biggr )\Biggr |&\ge \varphi _{m_i,d_i}(\tau _{4,d}(c))|X'|^2&\quad (\text {by }(32))\nonumber \\&\ge (c'-mc'')^2\varphi _{m_i,d_i}(\tau _{4,d}(c))|X|^2.&\quad (\text {by } (44)) \end{aligned}$$

(50)

Let ${\mathcal {L}}$ be the family of lines L such that L is contained in $F_i$, generated by X and it intersects $(X\cap F_i)\setminus X'$. Then $|{\mathcal {L}}|\le |(X\cap F_i)\setminus X'|\cdot |X\cap F_i|$, and hence (43) implies that

$$\begin{aligned} |{\mathcal {L}}|\le mc''|X|^2. \end{aligned}$$

(51)

Note that ${\mathcal {M}}\bigl (\bigcup _{j\in J_i}X'_j\bigr )\setminus {\mathcal {L}}\subseteq {\mathcal {M}}\bigl (\bigcup _{j=1}^mX_j\bigr )$. Thus (50) and (51) yield

$$\begin{aligned} \Biggl |{\mathcal {M}}\Biggl (\bigcup _{j=1}^mX_j\Biggr )\Biggr |\ge \bigl ((c'-mc'')^2\varphi _{m_i,d_i}(\tau _{4,d}(c))-mc''\bigr )|X|^2. \end{aligned}$$

(52)

Notice that

$$\begin{aligned} \varphi _{m_i,d_i}(\tau _{4,d}(c))&\ge \varphi _{m-1,d}(\tau _{4,d}(c))&(\text {by }(29),(39))\nonumber \\&\ge 2\varphi _{m,d}(c)^{{1}/{16}}&(\text {by }(30))\\&\ge 2\min {\biggl \{\biggl (\frac{\tau _{4,d}(c)}{\tau _{3,d}(c)}-1\biggr )^{\!2}\!,\,1\biggr \}}\cdot \varphi _{m,d}(c)^{{1}/{16}}.\nonumber \end{aligned}$$

(53)

Then

$$\begin{aligned}&\Biggl |{\mathcal {M}}\Biggl (\bigcup _{j=1}^mX_j\Biggr )\Biggr |\ge \bigl ((c'-mc'')^2\varphi _{m_i,d_i}(\tau _{4,d}(c))-mc''\bigr )|X|^2&\quad (\text {by }(52))\\&\quad =\biggl (\biggl (\frac{\varphi _{m,d}(c)^{{1}/{16}}}{\min {\{{\tau _{4,d}(c)}/{\tau _{3,d}(c)}-1,1\}}}\biggr )^{\!2}\varphi _{m_i,d_i}(\tau _{4,d}(c))-\varphi _{m,d}(c)^{{1}/{4}}\biggr )|X|^2\\&\quad =\bigl (2\varphi _{m,d}(c)^{{3}/{16}}-\varphi _{m,d}(c)^{{1}/{4}}\bigr )|X|^2&\quad (\text {by }(53))\\&\quad \ge \varphi _{m,d}(c)^{{3}/{16}}|X|^2\ge \varphi _{m,d}(c)|X|^2,&\end{aligned}$$

and it completes the induction in this case.

Case 2. Assume that there exists $j\in \{1,2,\ldots , m\}$ such that $|{\mathcal {F}}_j|>1$. Assume without loss of generality that $|{\mathcal {F}}_1|>1$, and take $F_{i_1}$ and $F_{i_2}$, elements of ${\mathcal {F}}_1$, such that $F_{i_1}\ne F_{i_2}$. Let ${\mathcal {M}}$ be the family of lines L generated by $X_i\cap (F_{i_1}\cap F_{i_2})$ such that $L\cap (X\setminus X_1)=\emptyset$. Then

$$\begin{aligned} {\mathcal {M}}\subseteq {\mathcal {M}}\Biggl (\bigcup _{j=1}^mX_j\Biggr ). \end{aligned}$$

(54)

Since $F_{i_1}$ and $F_{i_2}$ are skew, Lemma 2.7 yields that

$$\begin{aligned} |{\mathcal {M}}|\ge |X_1\cap F_{i_1}|\cdot |X_1\cap F_{i_2}|-|X\setminus X_1|. \end{aligned}$$

(55)

Hence

$$\begin{aligned} \Biggl |{\mathcal {M}}\Biggl (\bigcup _{j=1}^mX_j\Biggr )\Biggr |&\ge |{\mathcal {M}}|&\ (\text {by }(54))\nonumber \\&\ge |X_1\cap F_{i_1}|\cdot |X_1\cap F_{i_2}|-|X\setminus X_1|&\ (\text {by }(55))\\&\ge (c'')^2|X|^2-|X\setminus X_1|\ge (c'')^2|X|^2-|X|.\nonumber \end{aligned}$$

(56)

On the one hand, $|X|\ge \psi _{m,d}(c)\ge {2}/{c''}$. On the other hand, $\varphi _{m,d}(c)\le {1}/({2m^4})$. Hence (56) leads to

$$\begin{aligned} \Biggl |{\mathcal {M}}\Biggl (\bigcup _{j=1}^mX_j\Biggr )\Biggr |\ge \frac{(c'')^2}{2}|X|^2\ge \varphi _{m,d}(c)|X|^2, \end{aligned}$$

and it completes the induction in this case.$\square$

We conclude this paper proving Theorem 1.5.

Proof of Theorem 1.5

Assume that $|X|>6d$. Let $0<c<1$ be a value that satisfies Corollary 2.4(ii) for $0<{2}/({3d})<{1}/({d{-}1})$; assume without loss of generality that $c\le {1}/{4}$. Notice that X is not in Corollary 2.4(i) since all the hyperplanes of ${\mathbb {R}}^d$ contain at most |X|/(2d) elements, but $|X|/({2d})<{2|X|}/({3d})$. Therefore X generates at least $c|X|^d$ hyperplanes by Corollary 2.4(ii). Thus, from Proposition 3.2 applied to X and c, if $|X|\ge {5^3\cdot 4^{5(m-1)}}/{c^5}$, then

$$\begin{aligned} \Biggl |{\mathcal {M}}\Biggl (\bigcup _{i=1}^mX_i\Biggr )\Biggr |\ge \frac{c^5}{5^3\cdot 4^{5(m-1)}}|X|^2. \end{aligned}$$

This proves the theorem because c depends only on d.$\square$