Arrangement of Hyperplanes

1. Problem Statement

You are given $d$ hyperplanes in \(\mathbb{R}^n\). Out of all possible arrangements, find the maximum number of partitions that can be created of the $n$-dimensional space.

As an example, a line partitions \(\mathbb{R}^2\) into 2 parts. A plane partitions \(\mathbb{R}^3\) into 2 parts as well, and so on.

2. Solution

Let \(\phi_n(d)\) be the max number of partitions of \(\mathbb{R}^n\) by $d$-hyperplanes. Clearly the bare minimum condition on hyperplanes have to be - they intersect each other (no 2 are parallel, that would be just suboptimal), call it general position.

Claim 1 (Easy): \(\phi_2(d) = d(d+1)/2 + 1\).

Proof: \(\phi_2(1) = 2\) is clear, \(\phi_2(2) = \phi_2(1) + 2\) and in general \(\phi_2(d) = \phi_2(d-1) + d\). Solving this recursion we get our desired expression. Hopefully the following figure clears the inductive step.

Suggestive figure for n = 2.

Claim 2 (Easy enough): \(\phi_n(d) = \sum_{k = 0}^d \binom{d}{k}\) if \(d \le n\), else \(\phi_n(d) = \sum_{k = 0}^n \binom{d}{k}\).

Proof: First of \(\phi_n(d) = \phi_n(d-1) + \text{ something}\). And that something has to be optimized by placing the \(d\)th hyperplanes at the best possible location. Here is the clever bit - Instead of placing the \(d\)th hyperplane at the optimal spot, think of placing the the existing \(d-1\) hyperplanes onto that \(d\)th hyperplane. Think of this way; let \(n = 3\), and \(d = 3\), you have optimal config for \(d = 2\), and now you want to place the third plane. Wherever you place it, the 2 planes present will intersect the 3rd plane at 2 lines (#\((d-1)\) hyperplanes if viewed on the last hyperplane of \(n-1\) dimension). Think of how many partitions those lines make on that 3rd plane! That is exactly the number of extra partitions that will be added! For \(n = 3\), and \(d = 3\), the 3rd plane is 2-dimensional and 2 lines can partition that plane into 4 pieces max (\(n=2\) result). In general, \(\phi_n(d) = \phi_n(d-1) + \phi_{n-1}(d-1)\).

There are a few ways to solve this recursion - Here is a fun one: Define \(S(\phi_n(d)) = \phi_{n-1}(d)\), this is the shift operator. Our recursion can be written as \(\phi_n(d) = (I + S) \phi_n(d-1)\), where $I$ is the identity map. This is also equal to \(\phi_n(d) = (I + S)^d \phi_n(0)\). This all is just notational simplication to write the obvious expansion! And using binomial theorem on the composition of operators, we get \(\phi_n(d) = \sum_{k=0}^d \binom{d}{k} S^k \phi_n(0) = \sum_{k=0}^d \binom{d}{k} \phi_{n-k}(0)\). We know \(\phi_n(0) = 1 \forall n \ge 1\), and we get our desired result.

There is also the pascal identity - \(\binom{m}{k} = \binom{m-1}{k} + \binom{m-1}{k-1}\) (which is like saying to choose \(k\) out of \(m\) objects, either pick \(k\) from first \(m-1\) objects or pick the last one and pick remaning \(k-1\) from first \(m-1\)’s). You can use this in induction step if you guess the answer. There is also the generating function approach: define \(f_d(x) = \sum_0^\infty \phi_n(d) x^n\), this is equal (upon expanding the \(\phi_n(d)\)), \((1+x)^d \sum_0^\infty x^i\). Read off the coefficent of \(x^n\).