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

Assume that the hyperplane passes through the origin i.e. it is the span of some $k$ linearly independent vectors in $n$-space.

For example, for $n,k = 2,1,$ we have a line in the 2d plane passing through the origin, so the answer is 2. For $n,k=3,2$, it is 6.

In fact, I have proven that $F(n,n-1)=F(n-1,n-2)+2^{n-1}$. This follows by considering the $(n-1)$-subspace for which one of the coordinates is 0. The intersection of this subspace with the hyperplane is an $n-2$ dimensional hyperplane which passes through the origin and $F(n-1,n-2)$ quadrants of the subspace. For each quadrant, the original hyperplane will at maximum pass through two corresponding quadrants of the $n$-space. And for each quadrant it does not pass through, the original can pass through at most one quadrant. The recurrence follows.

But I am unable to extend this proof to general $k$, or even $n-2$. Any help is appreciated.

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}.$$

• As an aside, if you want to know which quadrants can be intersected, one finds that the "signatures" of the quadrants intersected are exactly the maximal vectors of a (realizable) oriented matroid. This is something that has interested me immensely as of late. – Milo Brandt Aug 12 '16 at 5:47
• Why do you claim $F(1,k)=2$? I think $F(n,0)=0$ because a zero-dimensional subspace doesn't intersect (the interior of) any quadrant. Similarly $F(n,n)=2^n$ because $\mathbb R^n$ intersects each of its $2^n$ quadrants. – stewbasic Aug 12 '16 at 6:08
• Ah, on further thought I guess you are restricting to $k\geq1$. In this case I agree. I was using a different boundary because the original problem doesn't make sense for $k>n$. – stewbasic Aug 12 '16 at 6:11
• @McLawrence Oops, yes you are right - I corrected the answer. – Milo Brandt Oct 1 '19 at 15:13
• @McLawrence I edited that paragraph; I think it was confusing and there were some typos. I think it might be clearer now - especially the important point that wasn't restated before: $S$ is a subspace of $\mathbb R^n$. – Milo Brandt Oct 1 '19 at 17:36