10
$\begingroup$

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.

$\endgroup$
7
+50
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Milo Brandt Aug 12 '16 at 5:47
  • 1
    $\begingroup$ 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. $\endgroup$ – stewbasic Aug 12 '16 at 6:08
  • 1
    $\begingroup$ 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$. $\endgroup$ – stewbasic Aug 12 '16 at 6:11
  • 1
    $\begingroup$ @McLawrence Oops, yes you are right - I corrected the answer. $\endgroup$ – Milo Brandt Oct 1 '19 at 15:13
  • 1
    $\begingroup$ @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$. $\endgroup$ – Milo Brandt Oct 1 '19 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.