Número de órdenes direccionales para $n$ puntos en $\mathbb{R}^d$ ?

Question

Imagina que hay un conjunto $X$ de $n$ puntos (diferentes) en $\mathbb{R}^d$ . El número de órdenes (lineales) que podríamos definir para ellos es simplemente $n!\approx \sqrt{2\pi n}(n/e)^n$ .

Algunos de estos órdenes pueden definirse junto a alguna dirección: por proyección sobre algún vector unitario $v$ : tomamos productos escalares $(v\cdot x^i)_{i=1..n}$ para todos estos puntos y utilizar el orden natural para estos números reales.

Define una interesante relación de equivalencia en la esfera de las direcciones: $v\sim_X u$ si definen el mismo orden en $X$ . Tales regiones deben estar conectadas (¿y "convexas"?). Descartemos sus límites, que son situaciones genéricas: tomemos sólo las direcciones para las que las proyecciones de todos los puntos son diferentes por pares.

La pregunta es cuál es el número de estas órdenes direccionales, por ejemplo, para un $d$ -¿un cubo de dimensiones? ¿Límite superior? ¿Distribución de probabilidad para puntos de posiciones aleatorias?

Si todos los puntos están en una línea, sólo hay 2 órdenes direccionales diferentes (las regiones son dos medias esferas). Así que la cuestión principal es el límite superior: denote el número máximo de órdenes direccionales como $M_{n,d}$ .

Algunos valores evidentes son $M_{n,1}=2$ o para $d\geq n-1$ tenemos simplex: $M_{n,d}=n!$ .

¿Existe una fórmula general para $M_{n,d}$ ? ¿Recurrencia?

---

Actualización: Acabo de hacer algunos números en Mathematica para $M_{n,d}$ (por ejemplo "MatrixForm[Tabla[x = RandomReal[1, {n, d}]; CountDistinct[Tabla[v = RandomReal[{-1, 1}, d]; Ordering[x.v], {i, 100000}]], {n,10}, {d, 10}]".

Para $d=2$ y $n=1,\ldots,10$ nos vemos con certeza: 1,2,6 , 12, 20, 30, 42, 56, 72, 90 ... que se pueden adivinar: $M_{n,2}=n(n-1)$ a excepción de $M_{1,2}=1$ . Esta fórmula sugiere que podemos elegir, por ejemplo, los dos primeros vértices y el resto sigue, pero es más complicado.

Para $d=3$ nos encontramos con que: 1,2,6,24 72, 172?, 352?, 642?, 1072?, 1690? (los últimos pueden estar todavía aumentados - probado 10 conjuntos para millones de direcciones) - los primeros cuatro son factoriales, pero no veo una fórmula para los siguientes?

Para $d=4$ nos encontramos con que: 1,2,6,24,120 , 480, ~1404, ~3488, ~7516, ~14374.

Para $d=5$ nos encontramos con que: 1,2,6,24,120,720 ,3600, ~10500, ~29000, ~62000.

Para $d=6$ nos encontramos con que: 1,2,6,24,120,720,5040 , 30240?, ~70000, ~260000.

Los datos numéricos sugieren que el número varía entre distintos conjuntos de puntos con posiciones aleatorias, lo que lleva a plantear otras cuestiones, como la caracterización de los conjuntos de puntos que maximizan el número de órdenes direccionales.

Actualización: Buscar justo debajo de la diagonal podría ser útil, por ejemplo, "añadir un punto al simplex": $M_{n,n-2}=(n-1)!\cdot(n-2) $ comprobado para $n=3,4,5,6,7$ ... (?)

Actualización: Para los cubos ( $n=2^d$ ) y las dimensiones 1,2,3,4, el número de órdenes direccionales es el correspondiente: 1, 8, 96, 5376.

---

Actualización: Podemos decir mucho sobre los límites de las regiones. Por ejemplo, el genérico $d$ puntos en $\mathbb{R}^d$ forman un único hiperplano, y su $\pm$ direcciones normales son dos vértices de la frontera entre $d!$ regiones de equivalencia de $\sim_X$ relación: con una perturbación infinitesimal podemos elegir cualquier orden entre estos $d$ puntos. Análogamente $d-1$ los puntos definen líneas en el límite - entre $(d-1)!$ regiones.

Para un límite tal como CW-complejo nos gustaría aplicar fórmula general de Euler :

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

donde $k_0$ es el número de vértices, $k_1$ aristas y así sucesivamente, permitiendo finalmente calcular el número de nuestras regiones/órdenes como $k_{d-1}$ .

En el caso genérico, cada $d$ vértices definen el hiperplano y por lo tanto dos vértices del complejo: $k_0=2{n \choose d}$ .

Para $k_1$ elegimos $d-1$ vértices en ${n\choose d-1}$ caminos - el plano que los atraviesa define un círculo 1D en la esfera. Proyectando en el espacio bidimensional ortogonal a dicho plano, estos $d-1$ puntos se convierten en un punto allí, obteniendo situación con $n-d+2$ puntos en 2D. Por lo tanto, el número total de arcos parece $k_1={n\choose d-1}M_{n-d+2,2}$ (?).

Análogamente $k_i={n\choose d-i} M_{n-d+1+i,1+i}$ ( ), lo que también concuerda para $k_0$ y permite obtener la recurrencia gracias a la fórmula de Euler:

$$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) $$

No verificado - Probablemente volveré a él en unos días.

Answer 1

Aquí está la explicación de la respuesta que publiqué en reddit, que para la posteridad es

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

donde la suma es sobre las secuencias $(m_1, m_2, \dots, m_n)$ tal que $\sum_i im_i = n$ , $\sum_i m_i > n-d$ y $\sum_i m_i$ tiene una paridad diferente a la de $n-d$ . Esto equivale a sumar sobre las particiones $\lambda\vdash n$ tal que $\ell(\lambda) > n-d$ y $\ell(\lambda)$ tiene una paridad diferente a la de $n-d$ . La condición $\ell(\lambda) > n-d$ podría sustituirse por $\sum(\lambda_i - 1) < d$ .

La aproximación al recuento es a través de arreglos de hiperplanos. Para $n$ puntos $S = \{v_1, \dots, v_n\}$ en $\mathbb{R}^d$ , definen una disposición de hiperplanos en $(\mathbb{R}^d)^*$ con hiperplanos

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

Cada región de esta disposición corresponde a una ordenación diferente de $S$ por proyección en una dirección determinada. Para contar las regiones, necesitamos entender el poset de intersección del arreglo y su función de Moebius.

Podemos describir el poset de intersección de este arreglo en términos de particiones de $S$ . Si $\mathcal{B}$ es una partición de $S$ , dejemos que

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

Sin embargo, no todos son distintos. Por ejemplo, cualquier partición con un bloque de tamaño al menos $d+1$ corresponderá a $\{0\} = H_{\{S\}}$ . Así que tenemos que determinar qué particiones determinan intersecciones distintas.

Ahora hago una suposición. Asumo que el máximo $M(n,d)$ se consigue para un conjunto de puntos en una posición lo suficientemente general como para que se pueda hacer con un simple recuento de dimensiones. Entonces, un bloque de tamaño $k$ en una partición da un $k-1$ -condición dimensional, por lo que debemos tener $\sum_{B\in\mathcal{B}}(|B|-1) < d$ pero ningún otro requisito para determinar una intersección única. (Y, por supuesto, añadimos $H_{\{S\}} = \{0\}$ como el elemento superior del conjunto de intersección).

Tenga en cuenta que si $\mathcal{B}$ satisface esta condición, entonces también lo hace cualquier refinamiento de $\mathcal{B}$ por lo que los intervalos $[\hat{0}, \mathcal{B}]$ son los mismos que los intervalos correspondientes en la red de partición completa. La función de Moebius de la red de partición es conocida, por lo que tenemos

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

donde $m_i$ es el número de bloques de tamaño $i$ en $\mathcal{B}$ .

Todavía tenemos que encontrar $\mu(\hat{0}, \hat{1})$ . Por la definición de la función de Moebius, sabemos que

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

Esta suma se toma sobre todas las particiones que satisfacen nuestra condición anterior. Como conocemos la función de Moebius para todas ellas en términos de las multiplicidades $m_1, m_2, \dots, m_n$ . Se trata de un ejercicio sencillo de recuento multinomial. Dadas las multiplicidades $m_1, \dots, m_n$ tal que $\sum_i im_i = n$ el número de particiones de un $n$ -configurar con $m_i$ bloques de tamaño $i$ es

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

Así que obtenemos

\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} \dots ((n-1)!)^{m_n}n!}{m_1!(1!)^{m_1}m_2!(2!)^{m_2} \dots m_n!(n!)^{m_n}} \\ &= - \sum \frac {(-1)^{n- \ell }n!}{m_1!1^{m_1}m_2!2^{m_2} \dots m_n!n^{m_n}} \end {align*}

donde las últimas sumas son sobre $m_1,\dots,m_n$ tal que $\sum_i im_i = n$ y $\ell := \sum_i m_i > n-d$ .

Ahora utilizamos un hecho de la teoría de los arreglos de hiperplanos que el número de regiones del arreglo está dado por una suma alternada de la función de Moebius del conjunto de intersección.

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

donde $\mathcal{P}$ es el conjunto de intersección. En el caso que nos ocupa, esto se convierte en

\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} \dots m_n!n^{m_n}} + \sum \frac {n!}{m_1!1^{m_1}m_2!2^{m_2} \dots m_n!n^{m_n}} \\ =& \sum \frac {((-1)^{n- \ell +d+1}+1)n!}{m_1!1^{m_1}m_2!2^{m_2} \dots m_n!n^{m_n}} \end {align*}

Y, por último, tenga en cuenta que $(-1)^{n-\ell+d+1} + 1$ es 2 cuando se cumple la condición de paridad y 0 en caso contrario.