Los caminos más cortos en el Hipercubo

Question

Pediremos longitudes de caminos más cortos en el hipercubo que obedezcan a restricciones dimensionales.

Dado $n \in\mathbb N$ el hipercubo o n-cube es el $n$ -producto del intervalo de unidades (por lo que es no el cubo Hilbert!). Es por lo tanto el conjunto $$F_{n,n}\:=\: \left\ { \sum\nolimits ^n_{i=1} \beta_ie_i\ : \Big\vert\ : \beta_i\in \big [0\,,1 \big ] \right\ }$$ donde $\,(e_i)_{1 \le i \le n}\,$ denota el estándar ONB de $ \mathbb R^n$ equipado con la distancia euclidiana. Para $1 \leqslant d \leqslant n\,$ la unión de $\,d$ -caras dimensionales de la $n$ -cubo se define como $$F_{n,d}:= \left\ { \sum\nolimits ^n_{i=1} \beta_ie_i\ : \Big\vert \text { where $ d $ coefficients } \beta_i\in \big [0\,,1 \big ], \text { the remaining ones live in }\{0,1\} \right\ }, \\ [2.5ex] \text {then } F_{n,1}\: \subsetneq\ :F_{n,2}\: \subsetneq\ : \ldots\ : \subsetneq\ : \,F_{n,n}\,.$$

¿Cuál es la longitud $\,s(n,d)\,$ de un camino más corto entre la esquina en el origen y la esquina opuesta en $\,(1,1, \ldots ,1)\,$ cuando el camino se ve obligado a estar en $F_{n,d}\,$ ?

Para $\,F_{n,1}$ por lo tanto, sólo los bordes, y $\,F_{n,n}$ permitiendo la línea recta, la pregunta es respondida rápidamente por $\,s(n,1)=n\,$ y $\,s(n,n)= \sqrt n\,$ : \begin {matrix}{ \begin {matrix}&d \\n & \end 1, 2, 3, 4 \ldots\\ 1&1 \\ 2&2& \sqrt 2 \\ 3&3& \sqrt 5& \sqrt 3 \\ 4&4&?&??&2 \\ \vdots &&&&& \ddots\end {matrix}

La entrada menos obvia $\,s(3,2)= \sqrt 5\,$ es proporcionado por esta llamativa respuesta al post "¿Cuál es la geodésica entre dos esquinas opuestas de un cubo en su superficie? [cerrado]". ¿Pero qué pasa con todo el resto?

¿Cómo puede la secuencia decreciente (¡ciertamente!) $$\,s(n,1),\;s(n,2),\; \ldots ,\;s(n,n-1),\;s(n,n)$$ se determine? No encontré referencias, ni en la @SE ni en el internet residual. Además, no estoy seguro de la etiqueta apropiada del puesto, pero omitiendo Teoría de los gráficos fue intencionado.

Answer 1

Lo que sigue es una generalización de la "prueba visual" a la que se refiere la pregunta.

Si $p_i \geq0 $ $(1 \leq i \leq d)$ y $ \sum_ {i=1}^d p_i=n$ entonces $$ \ell ({ \bf p}):= \sqrt { \sum_ {i=1}^d p_i^2}$$ es mínima cuando todos $p_i$ son iguales. Cuando el $p_i$ están obligados a ser enteros, entonces debemos hacerlos tan iguales como sea posible. Con este fin, asumamos $$n= q d+r, \qquad q \geq1 , \quad 0 \leq r<d$$ y poner $$p_i:= \left\ { \eqalign {&q+1 \qquad (1 \leq i \leq r) \cr &q \quad\qquad (r+1 \leq i \leq d)\ . \cr } \right. $$ Afirmo que $$s_{n,d}= \ell ({ \bf p})= \sqrt {dq^2+r(2q+1)}\ .$$ Sólo probaré que $s_{n,d} \leq\ell ({ \bf p})$ . Sin embargo, no veo cómo se podría hacer mejor.

En el ${ \bf y}$ -espacio ${ \mathbb R}^d$ consideramos una caja virtual $$V:=[0,p_1] \times [0,p_2] \times\cdots\times [0,p_d] \subset { \mathbb R}^d\ .$$ Esta caja está construida a partir de $d$ -cubos de unidades dimensionales, llamados Cámaras . La diagonal principal $ \sigma $ de esta caja conecta ${ \bf 0}$ con ${ \bf p}=(p_1, \ldots ,p_d)$ y tiene una longitud $ \ell ({ \bf p})$ . Esta diagonal pasa por un cierto número de cámaras a su vez. Ahora interpretamos estas cámaras como $d$ -caras dimensionales del cubo original $C:=[0,1]^n \subset { \mathbb R}^n$ para que $ \sigma $ puede ser visto como un desarrollo de un camino admisible desde ${ \bf 0}$ a ${ \bf 1}$ en $C$ .

El pretendido "repliegue" de $ \sigma $ se realiza de la siguiente manera: Asignar cada intervalo $[k-1,k]$ $(1 \leq k \leq p_1)$ en el $y_1$ -el eje del número $k$ y luego asignar cada uno de esos intervalos en el $y_2$ -eje uno de los siguientes $p_2$ números, y así sucesivamente a lo largo de la otra $y_i$ -ejes, hasta que todos los números de $1$ a $n$ se han distribuido así. Ahora identificamos cada intervalo $0 \leq x_k \leq 1$ en uno de los ejes de ${ \mathbb R}^n$ con el correspondiente $y_i$ -intervalo en el eje apropiado de ${ \mathbb R}^d$ .

Por proyección en el $y_i$ -eje cada pieza $ \Delta \sigma\subset \sigma $ yaciendo en alguna cámara se le asigna $d$ diferentes números de $[n]$ y estos números indican qué coordenadas $x_k$ será "activo" a lo largo de $ \Delta \sigma $ en otras palabras: en el cual $d$ -la cara dimensional de $C$ la pieza "doblada" $ \Delta \sigma $ mentirá. De ello se deduce que $ \sigma $ "retrocede" isométricamente a una trayectoria de longitud admisible $ \ell ({ \bf p})$ en $[0,1]^n$ .

Answer 2

¡Buen problema!

Aquí hay algunos resultados parciales

Por ahora, los declararé sin pruebas.

Para una mejor legibilidad, usaré $f(n,d)$ en lugar de $s_{n,d}$ .

Para simplificar las fórmulas, será conveniente ampliar el dominio de $f$ como sigue

Para los números enteros positivos $n,d$ que $e = \min (d,n)$ y definir $f(n,d)$ que es la longitud del camino más corto a lo largo de la adyacente $e$ -carácteres dimensionales de la unidad estándar $n$ -cubo desde el origen $(0,...,0)$ al vértice diagonalmente opuesto $(1,...,1)$ .

Así, para todos los números enteros positivos $n,d$ Tenemos $f(n,d) = f(n, \min (d,n))$

Deje que $a,b,n,d$ ser enteros positivos.

Primero, una desigualdad general: \begin {alineado*} y (1)\N- f(a+b,d) \le f(a,d) + f(b,d) \qquad\qquad\qquad\ ;\;\;\, \\ [4pt] \end {alineado*} A continuación, algunas fórmulas: \begin {alineado*} f(1,d) = 1 \\ [4pt] f(n,1) = n \\ [4pt] f(n,n-1) = \sqrt {n+2} \qquad\qquad\qquad\qquad\qquad\ ;\, \\ [4pt] f(n,n) = \sqrt {n} \\ [4pt] \end {alineado*} A continuación, una desigualdad particular: \begin {alineado*} y (6)\N- f(n,d) \le \sqrt {\a6},}; \text {\i1}Si.{\i} \le n \le 2d \qquad\qquad\ ;\;\; \\ [4pt] \end {alineado*} Para la propiedad $(4)$ la afirmación es que para los caminos restringidos a $(n-1)$ -caras dimensionales, el camino \begin {alineado*} &(0,...,0) \to (1,{ \small { \frac {1}{2}}},...,{ \small { \frac {1}{2}}},0) \to (1,...,1) \qquad\qquad\\ [4pt] \end {alineado*} es una geodésica.

Usando estas propiedades, obtenemos: \begin {alineado*} f(1,1)&=1&& \text {[por $(2)$ o por $(3)$ o por $(5)$ ]} \\ [14pt] f(2,1)&=2&& \text {[por $(3)$ o por $(4)$ ]} \\ [4pt] f(2,2)&= \sqrt {2}&& \text {[por $(5)$ ]} \\ [14pt] f(3,1)&=3&& \text {[por $(3)$ ]} \\ [4pt] f(3,2)&= \sqrt {5}&& \text {[por $(4)$ ]} \\ [4pt] f(3,3)&= \sqrt {3},&& \text {[por $(5)$ ]} \\ [14pt] f(4,1)&=4&& \text {[por $(3)$ ]} \\ [4pt] f(4,2)& \le 2 \sqrt {2}&& \text {[por $(1)$ o por $(6)$ ]} \\ [4pt] f(4,3)&= \sqrt {6}&& \text {[por $(4)$ ]} \\ [4pt] f(4,4)&=2&& \text {[por $(5)$ ]} \\ [14pt] f(5,1)&=5&& \text {[por $(3)$ ]} \\ [4pt] f(5,2)& \le \sqrt {5}+ \sqrt {2}&& \text {[por $\;(1)\;$ ]} \\ [4pt] f(5,3)& \le 3&& \text {[por $(1)$ o por $(6)$ ]} \\ [4pt] f(5,4)&= \sqrt {7}&& \text {[por $(4)$ ]} \\ [4pt] f(5,5)&= \sqrt {5},&& \text {[por $(5)$ ]} \\ [14pt] \end {alineado*} En el futuro, tengo algunas ideas (y conjeturas) sobre cómo tratar el caso en general, pero esperaré hasta que investigue más a fondo.

Algunos pensamientos adicionales. . .

Mediante la aplicación repetida de $(1)$ tenemos $$(7)\;\;f(ab,d) \le af(b,d) \qquad\qquad\qquad\ ;$$ Sin embargo, por razonamiento heurístico, conjeturo $$(*)\;\; \text {If}\;d \le b,\; \text {then}\;f(ab,d) = af(b,d)$$