What is the maximum number of quadrants in $n$ dimensional space that a $k$ dimensional hyperplane can pass through?

Solution 1:

It is worth noting that your problem is equivalent to the following one:

What is the maximal number of cells an arrangement of $n$ hyperplanes can split $\mathbb R^k$ into?

Here, I use "hyperplane" as in "codimension $1$ subspace". More usefully, suppose we represent such an arrangement as a number of non-zero maps $f_1,\ldots,f_n$ with $f_i:\mathbb R^k\rightarrow\mathbb R$ and the hyperplanes in the arrangement being the kernel of each map. A cell is then a subset of $\mathbb R^k$ with a specified sign for each $f_i$ - for instance, the set where each $f_i$ is positive is a cell (if non-empty).

To get from this reduced problem to yours, define a map $f:\mathbb R^k\rightarrow \mathbb R^n$ as $$f(x)=(f_1(x),f_2(x),\ldots,f_n(x)).$$ We find that $f(\mathbb R^k)$ is a subspace of dimension $k$ in $\mathbb R^n$ such that the image of any cell is exactly the intersection of that hyperplane with some quadrant and the preimage of a quadrant is exactly a cell. Thus there are equally many cells in the arrangement as there are quadrants intersected by the associated subspace.

To get from your problem to the reduced one, let $S$ be the subspace of $\mathbb R^n$ in question and $f:S\rightarrow \mathbb R^n$ be the inclusion of $S$ into the space $\mathbb R^n$. Define $f_i(x)$ to be the $i^{th}$ coordinate of $f(x)$ and note that these are linear maps. Moreover, which quadrant some $x\in S$ is in is determined by the signs of the $f_i$ and the intersection of the hyperplane $x_i=0$ in $\mathbb R^n$ with $S$ is precisely the kernel of $f_i$ by definition. Otherwise said, the intersection of a quadrant with $S$ is precisely a cell in the arrangement of hyperplanes given by $f_1,\ldots,f_n$ in $S$.

I think it is easier to get a hold on this modified problem. In particular, suppose we have an arrangement of $n$ hyperplanes $H_1,\ldots,H_n$ in $\mathbb R^k$ and add some hyperplane $H'$ to it and wish to know how many more cells were created by this hyperplane. Well, we get more cells exactly when $H'$ splits an existing cell into two. We can find how many times $H'$ does that by considering the cells induced in $H'$ by the hyperplanes $H_1\cap H',\ldots,H_n\cap H'$. That is, the new cells in $\mathbb R^k$ created by adding the hyperplane $H'$ correspond to the cells in a $k-1$ dimensional arrangement of $n$ hyperplanes.

Letting $F(n,k)$ be the maximal number of cells in such an arrangement, we get the relation $$F(n+1,k)\leq F(n,k) + F(n,k-1).$$ One can find, more strongly, that if you choose a set of $n$ hyperplanes such that the intersection of any $n+1$ of them is a point (i.e. so that they are in general position) that this bound is obtained (this may be proved by induction), thus $$F(n+1,k)=F(n,k) + F(n,k-1).$$ Then, we have initial conditions $$F(1,k)=2$$ $$F(n,1)=2.$$ These uniquely specify the function. One may use this to prove, by induction, the formula: $$F(n,k)=2\sum_{d=0}^{k-1}{n-1 \choose d}.$$