Vectores casi ortogonales

Question

Esto tiene que ver con la geometría de altas dimensiones, con la que siempre soy un inútil. Supongamos que tenemos algún número entero grande $n$ y algunos pequeños $\epsilon>0$ . Trabajar en la esfera unitaria de $\mathbb R^n$ o $\mathbb C^n$ quiero elegir una gran familia de vectores $(u_i)_{i=1}^k$ que es casi ortogonal en el sentido de que $|(u_i|u_j)| < \epsilon$ cuando $i\not=j$ . Supongo que me interesa saber cómo la mayor elección de $k$ crece con $n$ y $\epsilon$ .

Por ejemplo, podemos dejar que $\{u_1,\cdots,u_n\}$ sea la base habitual y, a continuación, elija $u_{n+1} = (1,1,\cdots,1)/n^{1/2}$ que funciona si $n^{-1/2} < \epsilon$ . A continuación, puede dejar que $u_{n+2} = (1,\cdots,1,-1,\cdots,-1)/n^{1/2}$ y demás, pero no tengo claro hasta dónde se puede llegar.

Answer 1

Esto era demasiado largo para ser un comentario, mis disculpas:

En relación con el comentario de Tim Gowers y la siguiente discusión, el capítulo 6 del precioso libro blanco de Bollobas "Combinatoria - sistemas de conjuntos hipergráficos, familias de vectores y probabilidad combinatoria" estudia exactamente este tipo de cuestiones.

De hecho el comentario de Tim corresponde al Teorema 6 de ese capítulo del libro, creo. El lenguaje de ese teorema utiliza la diferencia simétrica de subconjuntos de $\{1,2,..,n\}$ que se pueden convertir en productos internos normalizados de $n$ vectores dimensionales con entradas $\pm 1/\sqrt{n}$ .

Sea $\epsilon>0$ ser pequeño. El segundo caso del Teorema 6 establece esencialmente que si se permite que el producto interior normalizado esté en $[-1,\epsilon]$ equivalentemente, si las diferencias simétricas por pares de los conjuntos de la familia son todas ligeramente inferiores a $n/2$ en términos relativos, entonces el número de conjuntos de la familia, y por tanto el número de vectores con entradas $\pm 1/\sqrt{n}$ puede ser tan grande como $2^{\epsilon n}.$

La demostración de esta parte del teorema se da como ejercicio con una buena pista en el libro: Centrarse en subconjuntos de tamaño $k=\lceil n/2 \rceil$ y hacer un empaquetamiento esférico en el espacio de Hamming.

La variación con la pregunta OPs es que el rango permitido para el producto interior normalizado es $[-\epsilon, +\epsilon]$ en la pregunta de la OP. De la respuesta de Jelani Nelson se desprende que la penalización por restringir el producto interior a una banda quizá no sea tan grave como cabría esperar. Pasamos de $\epsilon n$ hasta $\epsilon^2 \log(1/\epsilon)n$ en el exponente.