Históricamente, las redes de alta densidad fueron estudiados intensamente, por ejemplo, E_8 celosía o Sanguijuela de Celosía. Sin embargo, hay situaciones en las que las rejillas con baja besos número son necesarios. Específicamente, me preguntaba si hay alguna familia infinita de n-dimensiones de celosías que los besos número está delimitado por poli(n), y todavía relativamente densa?
Respuestas
¿Demasiados anuncios?
Pierre Spring
Puntos
2398
Si la pregunta es sobre el comportamiento asintótico en altas dimensiones, a continuación, yo no creo que sea conocido o incluso conjeturó que los besos número para el empaquetamiento más denso no es polinomio en n. A lo mejor de mi memoria (pero consulte el libro por Conway y Sloane) no se conocen ejemplos de redes donde los besos número es exponencial, y el más conocido obligado sólo son cuasi-polinomio ($n^{\log n}$).
Tan "denso entramado de embalaje" y "besos enormes números" no son iguales en dimensiones muy alto. (No son los mismos en la dimensión de 24!). Si usted está interesado en la interesante nociones de baja densidad envases usted puede pensar acerca de los envases que son localmente más densa a nivel mundial, pero muy undense. Tiene sentido considerar, incluso en bajas dimensiones, ¿cuál es el mínimo de "máximo local" para la densidad de las rejillas.
Actualización: me permito añadir algunos detalles más sobre la conexión entre besos número y, más generalmente, "el extremo inferior de la distribución de la distancia" de un embalaje y la densidad. Es conveniente hablar, más genarally, sobre esférica códigos, y también para llamar la analogía con códigos binarios. La más densa ejemplos de esférica códigos binarios y códigos de corrección de errores se obtienen por aleatorizado construcciones. Para aquellos a los besos se espera que su número se subexponential. Es sabido que si estas aleatorizado límites puede ser mejorado para conseguir una mayor densidad de algunos relajado noción de besos número será exponencial. (Este es un resultado de Nati Linial y a mí para el binario caso y creo que fue extendida a más alfabetos y sperical códigos.) Como he mencionado para la esfera de embalaje (y creo que también para esférica general de los códigos) no hay ningún ejemplo conocido donde los besos número es exponencial. Para la corrección de errores códigos a través de una gran alfabeto el algebraicas de códigos geométricos (que son más densas que el ensayo aleatorizado de la construcción) dar un ejemplo. Este ejemplo puede ser transforned para el binario caso, pero no dar una mayor densidad.
Creo que la noción de densidad mínima entre locales de máxima densidad de envases se ha estudiado y también a la pregunta correspondiente para la cobertura. Al menos en las dimensiones bajas. Esto se parece a la de "corregir" la comprensión de la pregunta. Pero no recuerdo los detalles.
Más actualización: Frank Vallentin me dio un poco de información adicional relevante. De hecho, la noción relevante en la discusión el problema es que de un "perfecto entramado". En un perfecto entramado, la siguiente igualdad es verdadera:
dim span{$v~ v^t: ~v$ menor distinto de cero celosía vector} = $n(n+1)/2$.
(En general, sólo se tiene la desigualdad "$\le$") de Un entramado que es un máximo local para el embalaje de la función de densidad es siempre perfecta.
Tratando de encontrar perfet celosías con baja densidad (que parece ser uno de los propósitos de la pregunta si dejamos de lado los besos número de la revista), es muy interesante. Coxeter conjetura (formas Extremas, 1951) que la rejilla $A_n$, (que es perfecto,) da la densidad más baja entre todos perfecto celosías. Se sabe que es cierto para la dimensión de 8.
Hay otra conjetura por Conway y Sloane (de Baja dimensionalidad celosías III, de formas Perfectas, 1988) diciendo que Coxeter la conjetura es malo si la dimensión es lo suficientemente grande...
John Topley
Puntos
58789
La cuestión es que parece mal planteado, porque siempre se puede hacer una pequeña deformación de un entramado para enviar un beso en número a cero. Incluso si usted ampliar las esferas tanto como sea posible, a los besos número genéricamente ser de 2. Incluso si usted requiere linealmente independientes besos puntos, entonces creo que genéricamente sólo habrá 2n de ellos.
Usted puede mirar unimodular celosías. Por definición, este es un entramado de tal forma que si usted escribe la distancia Euclídea producto escalar en la base de la red, su matriz de enteros de entradas y determinante 1. Si se le cae, ya sea determinante 1 o entero entradas, estás de vuelta a la deformación de la inestabilidad. Hay sólo un número finito de unimodular de celosías en cualquier dimensión fija, y no muchas en dimensiones bajas. No sé el comportamiento de unimodular besos números en altas dimensiones.
Gil respuesta es mejor. Mis comentarios tienen sentido en dimensiones bajas. Pero en altas dimensiones, la gente tiene un montón de problemas para hacer celosías con grandes besos números a todos. Ese giro de los acontecimientos no se me ocurren.
jrcs3
Puntos
2442
Gils respuesta es completa. Pero quiero saber sobre la baja de besos número de códigos. Es cierto que la alta densidad es favorable para los códigos. Pero, cuando tenemos códigos con la misma densidad de cómo encontrar el mejor código? Es el mejor código, en este sentido, cuya tener la menor besos número?
