Cómo definir un Voronoi reducido?

Question

Deje $\Lambda$ $n$- dimensiones de la rejilla con base $b_1,\ldots,b_n$. El problema de encontrar una "buena" base para $\Lambda$, o la reducción de un "mal" en una buena, es un área de investigación muy activa. La mayoría de la base de planes de reducción de tratar de optimizar las normas de los vectores de la base y la parte interior de sus productos. El objetivo es tener una base que es como casi ortogonales como sea posible. Una meta más ambiciosa, podría ser la base para la especificación de la región de Voronoi (es decir, su cara vectores) tan simple como sea posible. La expresión "reducción de Voronoi" está tomado de una publicación por Conway y Sloane (Proc. Royal Soc. Londres, 436 (1992), 55-68) donde se aplica a las rejillas en las dimensiones de $n\le 3$.

¿Qué es exactamente lo que debe la definición de Voronoi reducido?

Central para la construcción de la región de Voronoi de $\Lambda$ $2^n$ cosets de $2\Lambda$. En particular, para cualquier $x\in \Lambda$ uno está interesado en el conjunto de mínima norma de elementos en $x+2\Lambda$. Llamar a este conjunto de $S(\Lambda,x)$. Una definición de Voronoi reducción de la base por lo tanto, podría ser la siguiente:

Una base $b_1,\ldots,b_n$ $\Lambda$ es de Voronoi reducido si, por cualquier $x\in \Lambda$ y cualquier $y\in S(\Lambda,x)$ de los enteros $y_1,\ldots,y_n$ en la expansión de la $y=\sum_{i=1}^n y_i b_i$ siempre satisfacer los obligados $|y_i|\le c_n$.

Si esta es una buena definición, entonces, ¿cuál es la mejor constante $c_n$?

Los Conway-Sloane trabajo muestra que la $c_n=1$$n\le 3$. En otras palabras, en dimensión tres y más bajos siempre existe una base tal que la mínima norma de los vectores de la $2\Lambda$ cosets puede ser expresado como sumas con los coeficientes que se limita a $-1, 0, 1$. ¿Con qué rapidez se $c_n$ crecer con $n$? Hace crecer a todos?

Answer 1

Excelente pregunta. No sé la respuesta y tal vez lo que estoy sugiriendo es obvio. Sin embargo, creo que es en la pista de la derecha.

Deje $B$ ser una base para $\Lambda$ y deje $P$ la correspondiente (centrada en el origen fundamental de paralelepípedo. Es decir, $P$ es la región dada por $Bu$ donde $u \in [-0.5,0.5]^n$. Claramente $2P \cap \Lambda$ contiene representantes de $\Lambda/2\Lambda$. Sin embargo, los elementos en $2P \cap \Lambda$ generalmente no son la longitud mínima de los representantes de $\Lambda/2\Lambda$, los que están contenidos en $2\mathcal{V} \cap \Lambda$ donde $\mathcal{V}$ el (cerrado) celda de Voronoi de $\Lambda$.

Deje $d$ ser el más pequeño número real tal que $\mathcal{V} \subseteq dP$. Claramente $2dP \cap \Lambda$ es un superconjunto de a $2\mathcal{V} \cap \Lambda$ y un valor adecuado de $c$ por lo tanto $\lfloor d \rfloor$. Podemos afinar un poco al preguntar por la diagonal de la matriz $D$ tal que $\mathcal{V} \subseteq DP$. Luego tenemos a $n$ diferentes $c$'s, específicamente $c_i = \lfloor d_i \rfloor$ donde $d_i$ son los elementos de la diagonal de a $D$.

El problema ahora es encontrar el valor de $d$ (o matriz $D$). Es decir, ¿cuánto necesitamos a escala de la fundamental forma de paralelepípedo, de modo que es completamente contiene la celda de Voronoi? Tal vez si $R$ es convenientemente reducido, decir LLL reducido o Korkine–Zolotareff reducida, entonces los límites en $d$ se puede encontrar?