A Note on the No-$(d+2)$-On-a-Sphere Problem

We proceed by induction on $d$. The base case $d=1$ is trivial since a 0-sphere consists of 2 points. For the inductive step, assume the statement holds for . For sake of contradiction, suppose that a set $Q$ of $d+2$ points in ${[n]}^d$ is shattered by ${𝒮}_{n,d}$.

Suppose $Q$ is in general position, that is, no $d+1$ members in $Q$ lie on a hyperplane. By linear algebra, any $d+1$ points in $Q$ determines a unique sphere in ${ℝ}^d$. However, since $Q$ is shattered by ${𝒮}_{n,d}$, there is a sphere that contains $Q$. Hence, there is no sphere that contains exactly $d+1$ points from $Q$. Contradiction.

Suppose $Q$ contains a $(d+1)$-tuple $Q^{\prime }$ that lies on a hyperplane $h$ in ${ℝ}^d$. Since the intersection of a sphere with $h$ is a $(d-2)$-sphere in $h$, by induction on $d$, $Q^{\prime }$ cannot be shattered by ${𝒮}_{n,d}$. Hence, $Q$ cannot be shattered by ${𝒮}_{n,d}$, which is a contradiction. $◀$

By the lemma above, the number of $(d+1)$-tuples in ${[n]}^d$ that lie on a hyperplane which passes through the origin is at most

By symmetry, for any fixed point $p\in {[n]}^d$, the number of $(d+1)$-tuples in ${[n]}^d$ that lies on a hyperplane which passes through $p$ is at most $O(n^{d^2-1}).$ After summing over all points in ${[n]}^d$, the statement follows. Note that Lemma 7 applies to hyperplanes whose intersection with ${[n]}^d$ spans a $(d-1)$-dimensional subspace. We can assume that any $(d+2)$-tuple in ${[n]}^d$ lying on a common hyperplane meets this requirement by adding other points from ${[n]}^d$ if needed.$◀$

Finally, we will use the following result due to Sheffer that bounds the number of points from ${[n]}^d$ that lies on a $k$-sphere in ${ℝ}^d$, for $k\le d-1$. See also [10, Sec. 11.2, Equation 11.9], [17, Theorem 2].

Before we prove Theorem 1, let us give a brief outline of the argument. First, we use the probabilistic method and Lemmas 7 and 8 to obtain a large subset $A\subset {[n]}^d$ such that very few members of $A$ lie on a $(d-2)$-sphere or a hyperplane in ${ℝ}^d$. We then apply Theorem 3 and ideas from incidence geometry to estimate the number of $r$-tuples in $A$ that lie on a common sphere. Finally, we apply the deletion method to find a large subset $A^{\prime \prime }\subset A$ such that no $d+2$ members of $A^{\prime \prime }$ lie on a sphere or a hyperplane. We now flesh out all of the details of the proof.

Without loss of generality, we can assume that $n$ is a power of 2. Indeed, otherwise we can find an integer that is a power of 2 such that $n^{\prime }>n/2$, and apply the arguments below to the subcube ${[n^{\prime }]}^d$. This would only change the hidden constant in the $o(1)$ term in the exponent. Moreover, we will assume that $n$ is sufficiently large.

Fix a positive integer that will be determined later, such that $D$ divides $n$. We partition the $d$-dimensional cube ${[n]}^d$ into $D^d$ smaller cubes $Q_1,\mathrm{\dots },Q_{D^d}$, where each $Q_i$ is of the form

where $i_1,\mathrm{\dots },i_d\in \{0,\mathrm{\dots },D-1\}$. Hence, $|Q_i|={(n/D)}^d$.

Consider a random subset $A\subset {[n]}^d$ obtained by selecting each point in ${[n]}^d$ independently with probability $n^{3-d}$. Set $P_i=Q_i\cap A$, for $i=1,\mathrm{\dots },D^d$. Let $𝒲$ be the event that the subset $A\subset {[n]}^d$ satisfies the following properties.

1. 1.

   $n^3/2\le |A|\le 2n^3$.

2. 2.

   $n^3{D}^{-d}/2\le |P_j|\le 2n^3{D}^{-d}$ for all $1\le j\le D^d$.

3. 3.

   Every $(d-2)$-sphere contains less than $n^{c_1/\log \log n}$ points of $A$, where $c_1=c_1(d)$.

4. 4.

   The number $(d+2)$-tuples in $A$ that lie on a common hyperplane is at most $c_2{n}^{2d+5}$, where $c_2=c_2(d)$.

By Lemma 5 and Markov’s inequality, event $𝒲$ holds with probability at least 1/2. Indeed, by Lemma 5, the probability that $|A|>2n^3$ or is at most $e^{-\frac{n^3}{3}}+e^{-\frac{n^3}{12}}.$ Thus, the first property holds with high probability, that is, with probability tending to 1 as $n$ approaches infinity. A similar argument follows for the second property. For the third property, let us fix a $(d-2)$-sphere $S$ in ${ℝ}^d$. By Lemma 8, there is a constant $c=c(d)$ such that $S$ contains at most $n^{d-3+c/\log \log n}$ points from ${[n]}^d$. By Lemma 5,

Since there are at most $n^{d^2}$ $(d-2)$-spheres in ${ℝ}^d$ with at least $d$ points from ${[n]}^d$, the union bound implies that the third property holds with high probability. For the fourth property, let $X$ denote the number $(d+2)$-tuples in $A$ that lie on a common hyperplane. By Lemma 7, we have $𝔼[X]\le c^{\prime }{n}^{2d+5}$, where $c^{\prime }=c^{\prime }(d)$. By Markov’s inequality (see [1]), we have

Putting everything together, and setting $c_1,c_2$ sufficiently large, event $𝒲$ holds with probability at least $1/2$.

Thus, let us fix $A\subset {[n]}^d$ with the four properties described above, and set $t=2n^{c_3/\log \log n}$, where $c_3=\max \{c_1,c_2\}$. Let $𝒮$ be the collection of spheres in ${ℝ}^d$, such that each sphere in $𝒮$ contains at least $d+1$ points from $A$ in general position. Hence, $|𝒮|=O({|A|}^{d+1})$. Let ${𝒮}_j\subset 𝒮$ be the set of spheres in $𝒮$ that contains at least one point of $P_j=Q_j\cap A$. Let $G_j=(P_j,{𝒮}_j,E_j)$ be the bipartite incidence graph between $P_j$ and ${𝒮}_j$. Since the intersection of two distinct spheres in ${ℝ}^d$ is a $(d-2)$-sphere, and every $(d-2)$-sphere contains less than $t$ points from $A$, each graph $G_j$ is $K_{t,2}$-free.

Let ${ℱ}_j$ be the set system whose ground set is $P_j$, and whose sets are $S\cap P_j$, where $S\in {𝒮}_j$ and $|S\cap P_j|\ge t$. That is,

By Lemma 4, the VC-dimension of ${ℱ}_j$ is at most $d+1$. By inequality (1), we have

Hence, we apply Theorem 3 with $t=n^{c_3/\log \log n}$ to conclude that

where $c_4=c_4(d)$.

Given the partition ${[n]}^d=Q_1\cup \mathrm{\cdots }\cup Q_{D^d}$ described above, we say that a sphere $S$ crosses the subcube $Q_i$ if $S\cap Q_i\ne \mathrm{\varnothing }$.

Let $c_5=c_5(d)$ be a large constant that depends only on $d$. We will determine $c_5$ later. For sake of contradiction, suppose there is a sphere $S$ in ${ℝ}^d$ the crosses more than $c_5{D}^{d-1}$ subcubes $Q_i$. Note that we will not make any serious attempts to optimize the constant $c_5$.¹¹1A careful calculation shows that one can take $c_5=2^{O(d)}$. Another proof follows from a simple inductive argument with $c_5=d^{O(d)}$.

Let $T\subset {[n]}^d\cap S$ be a subset of points ${[n]}^d\cap S$ obtained by selecting 1 point from each subcube $Q_i$ that $S$ crosses. Hence, $|T|\ge c_5{D}^{d-1}.$ Let $𝒢=(T,E)$ be an auxiliary graph on $T$, where two points in $T$ are adjacent if their distance is less than $n/D$. Since two points in $T$ have distance less than $n/D$ only if they lie in adjacent subcubes $Q_i$ and $Q_j$, this implies that $𝒢$ has maximum degree $3^d-1$. By Turan’s theorem, we can find a subset $T^{\prime }\subset T$, such that the minimum distance between any two points in $T^{\prime }$ is at least $n/D$. Moreover, $|T^{\prime }|\ge (c_5/3^d)D^{d-1}$.

For each point $p\in T^{\prime }$, consider the spherical cap $C_p$ obtained by intersecting $S$ with the ball $B_p$ centered at $p$ with radius $n/(2D)$. Since the minimum distance among the points in $T^{\prime }$ is at least $n/D$, the collection of spherical caps corresponding to the points in $T^{\prime }$ will have pairwise disjoint interiors. Moreover, since each spherical cap arises from a ball whose center is on $S$ with radius $n/(2D)$, each spherical cap will have area at least $c_6{(n/D)}^{d-1}$ where $c_6=c_6(d)$. Hence, the total area of all of the spherical caps corresponding to the points in $T^{\prime }$ is at least

On the other hand, all of the spherical caps on $S$ will lie inside of a “large” ball $B$ with radius $dn$. Hence, the area of all of the spherical caps is at most the surface area of the ball $B$ with radius $dn$. Since the surface area of $B$ is at most $c_7{n}^{d-1}$, where $c_7=c_7(d)$, we have

By setting $c_5$ sufficiently large, we have a contradiction.$◀$

By the observation above, ${\sum }_{j=1}^{D^d}|{𝒮}_j|=O(D^{d-1}|𝒮|)$. Putting all of these bounds together and applying Jensen’s inequality, the number of incidences between $A$ and $𝒮$ is at most

Set $D$ to be a power of 2 such that

Note that $|𝒮|\le {|A|}^{d+1}$. From above, the number of incidences between $𝒮$ and $A$ is at most

where $c_8=c_8(d)$. Let ${𝒮}_r\subset 𝒮$ denote the set of $r$-rich spheres in $𝒮$, that is, the set of spheres in $𝒮$ with at least $r$ points from $A$. Then we have

which implies

Let ${𝒯}_i\subset 𝒮$ be the set of spheres in $𝒮$ with at least $2^i$ points from $A$, and at most $2^{i+1}$ from $A$. Hence

Therefore, the number of $(d+2)$-tuples of $A$ that lie on a common sphere $S\in 𝒮$ is at most

We now consider a random subset $A^{\prime }\subset A$ obtained by selecting each point in $A$ independently with probability $p$, where $p$ will be determined later. Let $X$ be the number of $(d+2)$-tuples of $A^{\prime }$ that lie on a common sphere or a hyperplane. Then, by linearity of expectation, we have

and

where $c_9=c_9(d)$. Hence, there is a $c_{10}=c_{10}(d)$ such that for $p=n^{-3d/(d+1)-c_{10}/\log \log n}$, we have . By Lemma 5, there is a subset $A^{\prime }\subset A$ of size at least $p|A|/2$, such that $A^{\prime }$ contains at most $p|A|/4$ $(d+2)$-tuples on a sphere or a hyperplane. By deleting one point from each $(d+2)$-tuple on a sphere or a hyperplane, we obtain a subset $A^{\prime \prime }\subset A^{\prime }$ of size at least

such that no $d+2$ members in $A^{\prime \prime }$ lie on a sphere or a hyperplane.$◀$

Let $n$ be prime, and let $A\subset {[n]}^d$ be points from the $d$-dimensional cube on the moment curve $(x,x^2,\mathrm{\dots },x^d)modn$, for $1\le x\le \lfloor n/(4d)\rfloor$. Hence, $|A|=\lfloor n/(4d)\rfloor$. For sake of contradiction, suppose there is a sphere $S$ in ${ℝ}^d$, such that $S$ contains $2d$ points from $A$. Note that this means $S$ contains $2d$ of ${[n]}^d$ when viewed as a sphere in ${𝔽}_n^d$. Let the center of $S\subset {𝔽}_n^d$ be $(c_1,\mathrm{\dots },c_d)$ and radius $r$, such that $S$ contains $2d$ points from $A$. Then we have $2d$ solutions $s_1,s_2,\mathrm{\dots },s_{2d}$ to the equation

On the other hand, by the division algorithm, we have

which implies that $s_1+\mathrm{\cdots }+s_{2d}=0modn$ as the coefficient of $x^{2d-1}$ is $0modn$. However, $s_i\le n/(4d)$, which implies $s_1+\mathrm{\cdots }+s_{2d}\ne 0modn$, contradiction. Hence, no $2d$ points in $A$ lie on a sphere and no $d+1$ points lie on a hyperplane. If $n$ is not prime, we apply Bertrand’s postulate to obtain a prime such that $n^{\prime }>n/2$, and apply the argument above to ${[n^{\prime }]}^d$.$◀$

Another natural question is to determine the maximum number of points that can be selected from ${[n]}^d$ with no $d+2$ points on a sphere, but allowing many points on a hyperplane. Since each point from ${[n]}^d$ lies on a sphere centered at the origin with radius $\sqrt{t}$, where $t=1,2,\mathrm{\dots },d{n}^2$, we have an upper bound of $d(d+1)n^2$ for this problem. Using Lemma 8 and the probabilistic method, one can show the existence of $n^{2-4/(d+1)-o(1)}$ points from ${[n]}^2\subset {[n]}^d$ with no $d+2$ on a sphere.