¿El producto tensorial de poliedros es un poliedro?

Question

Convenios: A politopo en una dimensión finita $\mathbb R$ -espacio vectorial $V$ se define como un casco convexo de un número finito de puntos en $V$ . A poliedro en una dimensión finita $\mathbb R$ -espacio vectorial $V$ se define como la intersección de un número finito de semiespacios cerrados en $V$ (es decir, el conjunto de soluciones de un sistema de un número finito de inecuaciones lineales no estrictas sobre un vector en $V$ ). Se sabe que los politopos son exactamente los poliedros acotados.

Tenga en cuenta que, para mí, $\mathbb R$ realmente puede significar cualquier campo ordenado, como $\mathbb Q$ o $\mathbb Q\left[\sqrt{2}\right]$ o muchos otros. Todas las afirmaciones que figuran a continuación son válidas cuando $\mathbb R$ se sustituye por cualquier campo ordenado, y una respuesta que haga uso de propiedades especiales de $\mathbb R$ es bienvenida, pero no se considerará definitiva.

Antecedentes: El teorema de descomposición de los poliedros es una consecuencia sencilla de los siguientes hechos:

1. Si $f:V\to W$ es un $\mathbb R$ -lineal entre dimensiones finitas $\mathbb R$ -y los espacios vectoriales $P$ es un poliedro en $V$ entonces $f\left(P\right)$ es un poliedro. (La misma afirmación es válida sustituyendo "poliedro" por "politopo", pero eso es una trivialidad).

2. Si $f:V\to W$ es un $\mathbb R$ -lineal entre dimensiones finitas $\mathbb R$ -y los espacios vectoriales $P$ es un poliedro en $W$ entonces $f^{-1}\left(P\right)$ es un poliedro. (Esto es obvio, pero sólo se menciona aquí en aras de la "simetría").

3. Si $P$ es un poliedro en una dimensión finita $\mathbb R$ -espacio vectorial $V$ y $Q$ es un poliedro en una dimensión finita $\mathbb R$ -espacio vectorial $W$ entonces $P\times Q$ es un poliedro en $V\times W$ . (Lo mismo vale para los politopos).

4. Si $P$ y $Q$ son dos poliedros en una misma dimensión finita $\mathbb R$ -entonces la suma de Minkowski $P+Q$ y la intersección $P\cap Q$ también son poliedros. (De nuevo, lo mismo vale para los politopos).

5. Si $P$ es un poliedro en una dimensión finita $\mathbb R$ -espacio vectorial $V$ y $Q$ es un poliedro en una dimensión finita $\mathbb R$ -espacio vectorial $W$ entonces $\left\lbrace f\in\mathrm{Hom}_{\mathbb R}\left(V,W\right) \mid f\left(P\right) \subseteq Q\right\rbrace$ es un poliedro en $\mathrm{Hom}_{\mathbb R}\left(V,W\right)$ . (Esto se inspira en la definición 9.16 de Günter M. Ziegler, Conferencias sobre los politopos , 1995 .)

Pregunta:

6. Si $P$ es un poliedro en una dimensión finita $\mathbb R$ -espacio vectorial $V$ y $Q$ es un poliedro en una dimensión finita $\mathbb R$ -espacio vectorial $W$ entonces es cierto que el casco convexo del conjunto $\left\lbrace p \otimes q \mid p\in P,\ q\in Q \right\rbrace $ es un poliedro en $V\otimes W$ ?

Esto es válido para los politopos, y se deduce en ese caso de §2.5 de Lawrence Valby, Una categoría de politopos (advertencia: mi casco convexo no es el suyo $P\otimes Q$ sino la imagen de su $P\otimes Q$ bajo una suryección que mantenga el $p_iq_j$ coordenadas y olvida el $p_i$ , $q_j$ y $1$ coordenadas); pero el argumento no se generaliza a los poliedros. Por otra parte, no encuentro ningún contraejemplo. ¿Alguna idea?

Answer 1

No siempre. Sin embargo, el cierre es un poliedro.

---

No siempre: Toma $P = \{a | 0 \leq a \leq 1\}$ . Toma $Q= \{ b,c | b\geq 0, c=1\}$ . A continuación, bajo el mapa $x=ab$ , $y=ac$ . Desde $P$ es el casco convexo de $(0)$ y $(1)$ y $Q$ es el rayo que comienza en $(0,1)$ y yendo en dirección $(1,0)$ , $P \otimes Q$ es el casco convexo de $(0,0)$ y el rayo que comienza en $(0,1)$ y yendo en dirección $(1,0)$ que es:

$P \otimes Q = \{x,y | 0\leq x, 0 \leq y \leq 1, (y>0 \vee x=0) \}$

No es un poliedro porque no es cerrado.

---

El cierre es: Definir $B$ sea el siguiente cuerpo convexo. Primero demostramos que $B$ es un poliedro. A continuación demostraremos que $cl(P \otimes Q)=B$ .

$B= \operatorname{conv}(P_p \otimes Q_p + ((P_p+P_c) \otimes Q_c) + (P_c \otimes (Q_p+Q_c)) + (P \otimes Q_l) + (P_l \otimes Q)) $

Desde $\operatorname{conv}(A + B) = \operatorname{conv}(A) + \operatorname{conv}(B)$ ,

$B= \operatorname{conv}(P_p \otimes Q_p) + \operatorname{conv}(((P_p+P_c) \otimes Q_c) + (P_c \otimes (Q_p+Q_c)) )+ \operatorname{conv}((P \otimes Q_l) + (P_l \otimes Q))) $

La primera parte es claramente un politopo. La última parte es claramente un subespacio lineal. El cono es complicado, pero se puede ver como el casco convexo de un número finito de rayos. Un tensor de rayos, un politopo, es el casco convexo de un número finito de rayos, es decir, un cono. Un tensor de rayos en un cono es el casco convexo de un número finito de rayos, por tanto, de nuevo un cono. Tomar el casco convexo de diferentes conos podría producir más subespacios lineales, pero no te sacará del mundo de los poliedros. (Dima podría dar un argumento mejor que éste).

A continuación demostramos que $cl(P \otimes Q) \subseteq B$ . Como politopo, es convexo y cerrado, por lo que basta con demostrar que cualquier elemento en $P$ un elemento en $Q$ está en $B$ . Pero esto es obvio: basta con dividir ese elemento en una suma.

Por último, demostramos que $B \subseteq cl(P \otimes Q)$ . Desde $P \otimes Q$ es convexa, $cl(P\otimes Q)$ es convexa, por lo que necesitamos demostrar que la suma de un elemento en $P_p \otimes Q_p$ un elemento de $(P_p+P_c)\otimes Q_c$ etc. está en $B$ . Supongamos, para simplificar, que sólo tenemos que añadir $a \otimes b$ en $P_p \times Q_p$ a $c \otimes d$ en $(P_p+P_c) \otimes Q_c$ . (Para obtener el caes general, basta con repetir el argumento). Sea $e$ sea cualquier elemento de $Q_p$ . Entonces observamos que

$\lim _ {\lambda \to 0} \left((1-\lambda) \left[a \otimes b\right] + \lambda \left[c \otimes \left(\frac{d}{\lambda}+ e \right)\right]\right)= a\otimes b+ c\otimes d $

$a \otimes b$ y $c \otimes \frac{d}{\lambda}+ e$ están en $P \otimes Q$ mientras $\lambda>0$ por lo que una combinación convexa de ellos también lo es, por lo que el límite como $\lambda \to 0$ está en $cl(P \otimes Q)$ . El hecho clave es que $Q_c$ es cerrado bajo multiplicación por números reales positivos. Dado que $P_c$ , $Q_l$ y $P_l$ también lo son, podemos aplicar este truco de nuevo para obtener una suma arbitraria.

Answer 2

Una ruta obvia para una prueba de 6 sería demostrando que conv( $P\otimes Q$ ) se descompone como $$\mathrm{conv}(P_p\otimes Q_p)+\mathrm{conv}((P_p+P_c)\otimes Q_c+P_c\otimes (Q_p+Q_c))+\mathrm{conv}(P\otimes Q_\ell+P_\ell\otimes Q)\qquad (*)$$ donde $P=P_p+P_c+P_\ell$ para $P_p$ un politopo, $P_c$ un cono puntiagudo, y $P_\ell$ un subespacio lineal, y $Q=Q_p+Q_c+Q_\ell$ una descomposición similar para $Q$ . Usted ha mencionado que $\mathrm{conv}(P_p\otimes Q_p)$ es un politopo, y creo que una prueba de esto debería ser fácilmente adaptable para demostrar que el segundo $\mathrm{conv}(...)$ es un cono poliédrico. Y el tercero $\mathrm{conv}(...)$ es un subespacio lineal. Por lo tanto $(*)$ implicaría que $\mathrm{conv}(P\otimes Q)$ es un poliedro.

Lo difícil parece ser mostrar $(*)$ . Cualquier conjunto convexo cerrado $C$ en $\mathbb{R}^m$ tiene una descomposición en la suma de un conjunto convexo $C'$ que no contiene líneas rectas, y un subespacio $C_\ell$ con $C'$ contenida en el complemento ortogonal de $C_\ell$ así que esto se reduce a identificar $C'$ con la suma de los dos primeros conv(...), y $C_\ell$ con el tercer conv(...).