Number of directional orders for $n$ points in $\mathbb{R}^d$?

Imagine there is some set $X$ of $n$ points (different) in $\mathbb{R}^d$. The number of (linear) orders we could define for them is just $n!\approx \sqrt{2\pi n}(n/e)^n$.

Some of these orders can be defined alongside some direction: by projection on some unitary vector $v$: we take scalar products $(v\cdot x^i)_{i=1..n}$ for all these points and use the natural order for these real numbers.

It defines an interesting equivalence relation on the sphere of directions: $v\sim_X u$ iff they define the same order in $X$. Such regions should be connected (and "convex"?). Let's discard their boundaries, which are generic situations: take only directions for which projections of all points are pairwise different.

The question is what is the number of such directional orders e.g. for a $d$-dimensional cube? Upper bound? Probability distribution for points of random positions?

If all points are in one line, there are just 2 different directional orders (the regions are two half-spheres). So the main question is upper bound - denote the maximal number of directional orders as $M_{n,d}$.

Some obvious values are $M_{n,1}=2$, or for $d\geq n-1$ we have simplex: $M_{n,d}=n!$.

Is there a general formula for $M_{n,d}$? Recurrence?

Update: just made some numerics in Mathematica for $M_{n,d}$, (e.g.: "MatrixForm[Table[x = RandomReal[1, {n, d}]; CountDistinct[Table[v = RandomReal[{-1, 1}, d]; Ordering[x.v], {i, 100000}]], {n,10}, {d, 10}]]").

For $d=2$ and $n=1,\ldots,10$, we get looking certain: 1,2,6, 12, 20, 30, 42, 56, 72, 90 ... which can be guessed: $M_{n,2}=n(n-1)$ with exception of $M_{1,2}=1$. This formula suggests that we can choose e.g. first two vertices and the rest follow, but it's more complicated.

For $d=3$ we get: 1,2,6,24, 72, 172?, 352?, 642?, 1072?, 1690? (the last ones may be still increased - tested 10 sets for million directions) - the first four are factorials, but I don't see a formula for the following?

For $d=4$ we get: 1,2,6,24,120, 480, ~1404, ~3488, ~7516, ~14374.

For $d=5$ we get: 1,2,6,24,120,720,3600, ~10500, ~29000, ~62000.

For $d=6$ we get: 1,2,6,24,120,720,5040, 30240?, ~70000, ~260000.

Numerics suggest that the number varies among different sets of points with random positions, leading to further questions e.g. of characterization of sets of points maximizing the number of directional orders?

Update: Searching just below diagonal might be helpful, e.g. "adding one point to simplex": $M_{n,n-2}=(n-1)!\cdot(n-2) $ checked for $n=3,4,5,6,7$ ... (?)

Update: For cubes ($n=2^d$) and dimensions 1,2,3,4, the number of directional orders is correspondingly: 1, 8, 96, 5376.

Update: We can tell a lot about boundaries of the regions. E.g. generic $d$ points in $\mathbb{R}^d$ form unique hyperplane, and its $\pm$normal directions are two vertices of the boundary between $d!$ regions of equivalence of $\sim_X$ relation: with infinitesimal perturbation we can choose any order among these $d$ points. Analogously $d-1$ points define lines at the boundary - between $(d-1)!$ regions.

For such boundary as CW-complex, we would like to apply general Euler formula:

$$1-(-1)^d=\chi=k_0-k_1+k_2-\ldots-(-1)^d k_{d-1}$$

where $k_0$ is the number of vertices, $k_1$ edges and so on, finally allowing to calculate the number of our regions/orders as $k_{d-1}$.

In generic case, every $d$ vertices define hyperplane and so two vertices of the complex: $k_0=2{n \choose d}$.

For $k_1$ we choose $d-1$ vertices in ${n\choose d-1}$ ways - plane going through them defines 1D circle on the sphere. Projecting on two dimensional space orthogonal to such plane, these $d-1$ points become one point there, getting situation with $n-d+2$ points in 2D. Hence, the total number of arcs seems $k_1={n\choose d-1}M_{n-d+2,2}$ (?).

Analogously $k_i={n\choose d-i} M_{n-d+1+i,1+i}$ (?), what also agrees for $k_0$, and allows to get recurrence thanks to Euler formula:

$$M_{n,d}=^?(-1)^d \left((-1)^d-1 +\sum_{i=0}^{d-2} (-1)^i {n\choose d-i} M_{n-d+1+i,1+i} \right) $$

Unverified - I will probably go back to it in a few days.

Here is an explanation of the answer I posted on reddit, which for posterity is

$$ M(n,d) = 2\sum\frac{n!}{m_1!1^{m_1}m_2!2^{m_2}\cdots m_n!n^{m_n}} $$

where the sum is over sequences $(m_1, m_2, \dots, m_n)$ such that $\sum_i im_i = n$, $\sum_i m_i > n-d$, and $\sum_i m_i$ has different parity than $n-d$. This is equivalent to summing over partitions $\lambda\vdash n$ such that $\ell(\lambda) > n-d$ and $\ell(\lambda)$ has different parity than $n-d$. The condition $\ell(\lambda) > n-d$ could be replaced with $\sum(\lambda_i - 1) < d$.

The approach to counting is via hyperplane arrangements. For $n$ points $S = \{v_1, \dots, v_n\}$ in $\mathbb{R}^d$, define a hyperplane arrangement in $(\mathbb{R}^d)^*$ with hyperplanes

$$ H_{ij} = \{ \omega\in(\mathbb{R}^d)^* | \omega(v_i) = \omega(v_j) \}, i \not= j $$

Each region of this arrangement corresponds to a different ordering of $S$ by projection on a particular direction. In order to count the regions, we need to understand the intersection poset of the arrangement and its Moebius function.

We can describe the intersection poset of this arrangement in terms of partitions of $S$. If $\mathcal{B}$ is a partition of $S$, let

$$ H_{\mathcal{B}} = \{ \omega \in (\mathbb{R}^d)^* | \forall B\in\mathcal{B}. \forall u,v\in B. \omega(u) = \omega(v) \} $$

However, these are not all distinct. For example, any partition with a block of size at least $d+1$ will correspond to $\{0\} = H_{\{S\}}$. So we need to determine which partitions determine distinct intersections.

Now I make an assumption. I assume that the maximum $M(n,d)$ is achieved for a set of points in sufficiently general position that this can be done by just dimension counting. Then a block of size $k$ in a partition gives a $k-1$-dimensional condition, so we must have $\sum_{B\in\mathcal{B}}(|B|-1) < d$, but no other requirement to determine a unique intersection. (And, of course, we throw in $H_{\{S\}} = \{0\}$ as the top element in the intersection poset.)

Note that if $\mathcal{B}$ satisfies this condition, then so does any refinement of $\mathcal{B}$, so the intervals $[\hat{0}, \mathcal{B}]$ are the same as the corresponding intervals in the full partition lattice. The Moebius function of the partition lattice is known, so we have

$$ \mu(\hat{0}, \mathcal{B}) = (-1)^{n-|\mathcal{B}|}(2!)^{m_3}(3!)^{m_4}\cdots((n-1)!)^{m_n} $$

where $m_i$ is the number of blocks of size $i$ in $\mathcal{B}$.

We still need to find $\mu(\hat{0}, \hat{1})$. By the definition of the Moebius function, we know that

$$ \mu(\hat{0}, \hat{1}) = -\sum_{\hat{0}\leq\mathcal{B}<\hat{1}}\mu(\hat{0},\mathcal{B}) $$

This sum is taken over all partitions that satisfy our above condition. Since we know the Moebius function for all of these in terms of the multiplicities $m_1, m_2, \dots, m_n$. This is a straightforward multinomial counting exercise. Given multiplicities $m_1, \dots, m_n$ such that $\sum_i im_i = n$, the number of partitions of an $n$-set with $m_i$ blocks of size $i$ is

$$ \frac{n!}{m_1!(1!)^{m_1}m_2!(2!)^{m_2}\cdots m_n!(n!)^{m_n}} $$

So we get

\begin{align*} \mu(\hat{0}, \hat{1}) &= -\sum_{\hat{0}\leq\mathcal{B}<\hat{1}}\mu(\hat{0}, \mathcal{B}) \\ &= - \sum \frac{(-1)^{n-\ell}(2!)^{m_3}(3!)^{m_4}\cdots ((n-1)!)^{m_n}n!}{m_1!(1!)^{m_1}m_2!(2!)^{m_2}\cdots m_n!(n!)^{m_n}} \\ &= - \sum \frac{(-1)^{n-\ell}n!}{m_1!1^{m_1}m_2!2^{m_2}\cdots m_n!n^{m_n}} \end{align*}

where the latter sums are over $m_1,\dots,m_n$ such that $\sum_i im_i = n$ and $\ell := \sum_i m_i > n-d$.

Now we use a fact from the theory of hyperplane arrangements that the number of regions of the arrangement is given by an alternating sum of the Moebius function of the intersection poset.

$$ r(H) = (-1)^d\sum_{\mathcal{B}\in\mathcal{P}}(-1)^{\mathrm{dim}(H_\mathcal{B})}\mu(\hat{0}, \mathcal{B}) $$

where $\mathcal{P}$ is the intersection poset. In the case at hand, this becomes

\begin{align*} M(n,d) =& (-1)^{d}\mu(\hat{0},\hat{1}) + \sum_{\hat{0}\leq\mathcal{B}<\hat{1}}(-1)^{|\mathcal{B}|-n}\mu(\hat{0},\mathcal{B}) \\ =& (-1)^{d+1}\sum \frac{(-1)^{n-\ell}n!}{m_1!1^{m_1}m_2!2^{m_2}\cdots m_n!n^{m_n}} + \sum \frac{n!}{m_1!1^{m_1}m_2!2^{m_2}\cdots m_n!n^{m_n}} \\ =& \sum \frac{((-1)^{n-\ell+d+1}+1)n!}{m_1!1^{m_1}m_2!2^{m_2}\cdots m_n!n^{m_n}} \end{align*}

And finally note that $(-1)^{n-\ell+d+1} + 1$ is $2$ when the parity condition is satisfied and $0$ otherwise.