Hyperplane dividing corners of a hypercube into 2 sets Consider the corners of a hypercube in $\mathbb{R}^n$ where each corner of the hypercube is a point of the form $(\pm1, \dotsc, \pm1) \in \{\pm1\}^n$. Index the corners with the notation:
$$\mathbf{c}_i; i \in \{1, \dotsc, 2^n\}$$
Let $\mathbf{a} \in \mathbb{R}^n, b \in \mathbb{R}$ be parameters of a hyperplane $\mathbf{a} \cdot \mathbf{x} = b$. Define a split of the hypercube to be a collection of 2 sets:
$$\bigl\{ \{\mathbf{c_i} \mid \mathbf{a} \cdot \mathbf{c}_i \geq b\}, \{\mathbf{c}_j \mid \mathbf{a} \cdot \mathbf{c}_j < b\}\bigr\}$$


*

*How many unique splits of the hypercube exist?

*Given a hyperplane parameterized by specific $\mathbf{a} \in \mathbb{R}^n, b \in \mathbb{R}$, it produces a split $S$. How many splits are there that are different from $S$ by only 1 corner? For each such split, what are the parameters for a corresponding hyperplane in terms of $\mathbf{a}, b, \mathbf{c}_i \in \{\pm1\}^n$?
If helpful, you may reindex the corners using some specific transformation. For example, you may reindex the corners by their distance from the hyperplane (i.e. $\frac{|\mathbf{a}\cdot\mathbf{x} - b|}{\|\mathbf{a}\|}$) in ascending order.
This didn't jump out to me as any kind of unsolved problem, but an acceptable answer would be to show this reduces to some unsolved problem if that's the case.
 A: Your first question is essentially known. Another way to phrase it is how many distinct functions are there of the form $f(\mathbf{x})=\text{sgn}(\mathbf{a}^T\mathbf{x}-b)$ restricted to the Boolean hypercube. It has been known that each such linear threshold function is uniquely determined by the $n+1$ Chow parameters, $\hat{f}(\emptyset), \hat{f}(\{1\}),\ldots,\hat{f}(\{n\})$, where $\hat{f}(S)$ for $S\subseteq [n]$ are the discrete Fourier coefficients of $f$. It is also well-known that each Fourier coefficient is an integer multiple of $1/2^n$ that lies in $[-1,1]$, and therefore, there are at most $2^{n+1}$ choices of value for each of these $n+1$ coefficients. These two facts immediately imply that there are at most $2^{(n+1)^2}$ such linear threshold functions.
The natural, and more involved, question is whether this asymptotic estimate is right. An easy construction of a family of $3^n$ such subsets comes from considering the faces of the Boolean hypercube. This lower bound is incredibly loose, however. It is actually known that there are at least $2^{n^2-O(n^2/\log n)}$ such functions, so this estimate is essentially tight.
For more information on the upper bound, check out Chapter 5 of O'Donnell's book on harmonic analysis of Boolean functions. The lower bounds are a bit harder to find...there's a reference here, but it seems to be in Russian...
