Dos conjeturas de aproximadamente cero productos internos y conjuntos disociados

Question

Los siguientes problemas vienen de algo que me funcionó (con mis coautores) relativa a la prueba de un nuevo tiempo límite inferior para el streaming de problemas. Después de haber trabajado en estos problemas durante algún tiempo con poco progreso, yo estaría muy agradecido a escuchar si alguien ve una forma de acercarse a ellos.

Considere la posibilidad de una $2n$-dimensiones del vector de $v$ con $v_i \in \{0,1\}$. Ahora considere un $n$-dimensiones del vector de $w$ con $w_i \in \{-1,0,1\}$. Los elementos $w_i$ se muestra de forma independiente, por lo que el $P(w_i = -1) = P(w_i = 1) = 1/4$ e $P(w_i=0) = 1/2$.

La indexación de $1$, podemos ahora definir $A_i = \sum_{j=1}^n w_j v_{i+j-1}$ a de la $i$th producto interior entre el $w$ y un subvector de $v$. Sabemos que $P(A_i = 0) \sim 1/\sqrt{\pi n}$ si todos los elementos de $v$ igual $1$.

Conjetura 1

Para todos lo suficientemente grande $n$, existe un vector $v \in \{0,1\}^{2n}$ tal que $$P{\left(\forall i \leq \frac{n}{\log_2{n}}, A_i = 0\right)} \leq 2^{-\frac{n}{4}}.$$

Computacionalmente costosos experimentos numéricos sugieren que la conjetura 1 es plausible verdadero. Todavía es muy interesante, y abierto por lo que yo sé, para mostrar el mismo resultado con $n/4$ reemplazar por $n/C$ cualquier $C \geq 4$. De hecho, incluso un límite superior como $2^{-n/\sqrt{\log_2{n}}}$ sería interesante.

Sin embargo computacional experimentos sugieren que el siguiente aún más fuerte conjetura sostiene que ahora he de salir.

Un conjunto, cuyos subconjunto sumas son pares distintos, se llama disociadas. Un clásico de la pregunta ¿cuál es el tamaño más grande posible de un disociadas subconjunto del conjunto $\{0,1\}^n\subset{\mathbb R}^n$. Es conocido que el mayor tamaño de sus disociadas subconjunto es $$ \frac12(1+o(1))\,n\log_2 n; $$ véase, por ejemplo, este papel por Bshouty para obtener más detalles y un relato histórico.

En nuestro problema, se requiere que el disociadas subconjunto también tienen la propiedad de que hay alguna forma de organización de los vectores dentro de ella como columnas de una matriz de Toeplitz.

Conjetura 2

El mayor tamaño de disociadas subconjunto del conjunto $\{0,1\}^n\subset{\mathbb R}^n$ con la restricción adicional de que hay alguna forma de organización de los vectores dentro de ella como las columnas de un Matriz de Toeplitz es $$ \frac12(1+o(1))\,n\log_2 n. $$

Hasta donde yo sé, el no-trivial asintótica resultados son conocidos en todo para este problema en particular de la formulación. En una manera similar a la Conjetura 1, apenas alrededor de cualquier signos diacríticos límite inferior sería un importante primer paso.

Equipo experimentos muestran que los mayores tamaños para $n=2,3,4,5,6,7,8,9,10$ parecen ser $2,4,5,7,9,12,14,16,19$. Estos son los mismos como el más grande de los tamaños de un disociadas subconjunto sin la Toeplitz de restricción (ver los enlaces de MO pregunta anterior para ejemplos de estos). Si alguien puede encontrar una manera de encontrar soluciones para grandes $n$ (o incluso verificar los resultados) que podrían ser de utilidad.

Podemos considerar las filas de una matriz de Toeplitz consecutivos $n$-longitud subvectors de los vectores $v$ en la Conjetura 1.

Aquí está la solución para $n=3$.

\begin{pmatrix} 1&1&0&1\\ 0&1&1&0\\ 0&0&1&1 \end{pmatrix}

Aquí está la solución para $n=7$ .

\begin{pmatrix} 1&0&1&0&0&1&1&0&1&1&1&1\\ 1&1&0&1&0&0&1&1&0&1&1&1\\ 1&1&1&0&1&0&0&1&1&0&1&1\\ 0&1&1&1&0&1&0&0&1&1&0&1\\ 0&0&1&1&1&0&1&0&0&1&1&0\\ 1&0&0&1&1&1&0&1&0&0&1&1\\ 0&1&0&0&1&1&1&0&1&0&0&1 \end{pmatrix}

Un método estándar para demostrar que los grandes disociadas conjuntos existen es a través del método de probabilidades. Que es elegir uno uniformemente al azar y mostrar que hay una probabilidad no nula de que es disociado. No veo cómo utilizar este enfoque para mi problema, sin embargo.

Answer 1

Gracias Rafael por esta muy interesante y todo un reto! El siguiente es un aproximado argumento, el apoyo tanto de la Conjetura 1 y Conjetura 2. Tal vez se puede dar una pista de cómo construir una más rigurosa prueba.

Permítanme empezar por la reformulación de la Conjetura 1 algo. Como ya se ha indicado en la pregunta, se puede partir de la $2n$-dimensiones del vector de $v$ construir un $m \times n$ matriz de Toeplitz $M$ con elementos $M_{m+1-i,j} = v_{i+j-1}$ para $j=1,...n$ e $i=1,...,m$ (donde $m=\lfloor \frac n{\log_2n} \rfloor < n$). Definir, además, $a_i = A_{m+1-i}$ (es decir, simplemente invirtiendo el orden de los elementos), entonces tenemos en notación matricial $a=Mw$, y la Conjetura 1 puede ser expresado de la siguiente forma:

Conjetura 1*

Por lo suficientemente grande $n$, existe una matriz de Toeplitz $M \in \{0,1\}^{m \times n}$, con $m=\lfloor \frac n{\log_2n} \rfloor$, de tal manera que $P(Mw=0)\leq2^{-\frac n4}$.

Ahora voy a construir un argumento a favor de la Conjetura 1* (o, en realidad, como vamos a ver, un poco más fuerte conjetura).

Vamos a definir la función característica (= "transformada de Fourier") de la distribución del vector $a=Mw$ como $$ \tilde P(\xi) = \left\langle {\rm e}^{2\pi{\rm i}\,\xi^{\rm T}Mw} \right\rangle_w \ , \hspace{2cm} (1) $$ donde $\left\langle \cdots \right\rangle_w$ denota la media de los $w \in \{-1,0,1\}^n$ con las probabilidades especificado en la pregunta. Puesto que el vector aleatorio $a=Mw$ ha entero componentes, la cantidad que nos interesa puede ser expresada por la siguiente $m$-dimensión integral: $$ P(Mw=0) = \int_{[-\frac12,\frac12]^m} {\rm d}^m\xi \ \tilde P(\xi) \ . \hspace{2cm} (2) $$ Por otro lado, el $w$ promedio en $(1)$ puede ser fácilmente llevado a cabo de manera explícita, con el resultado de $$ \tilde P(\xi) = \prod_{j=1}^n \cos^2 \left( \pi \sum_{i=1}^m \xi_i M_{ij} \right) \ . \hspace{2cm} (3) $$ Por lo tanto, tienen un $n$veces producto de periódico $\cos^2$ términos, siendo una función de $m$ real de las variables de $\xi_i$, cada uno de los cuales está integrado en el intervalo de $[-\frac12,\frac12]$. Desde esta integral múltiple parece muy difícil de hacer, yo uso la siguiente aproximación: $$ \cos^2 (\pi t) \approx \sum_{k=-\infty}^\infty {\rm e}^{-4\pi(t-k)^2} \ , \hspace{2cm} (4) $$ el que ha sido elegido de tal manera que su valor máximo es de cerca de $1$ (el máximo de $\cos^2$) y que también conserva el valor integral $\int_{-1/2}^{1/2} {\rm d}t\ \cos^2 (\pi t) = \frac12$ más de un período. Ahora podemos volver a escribir $(2)$ como \begin{align} P &\approx \int_{[-\frac12,\frac12]^m} {\rm d}^m\xi \ \prod_{j=1}^n \left[ \sum_{k_j=-\infty}^\infty {\rm e}^{-4\pi \big( \sum_{i=1}^m \xi_i M_{ij} - k_j \big)^2} \right] \nonumber\\ &= \sum_{k\, \in\, \mathbb Z^n} \left[ \int_{[-\frac12,\frac12]^m} {\rm d}^m\xi \ \ {\rm e}^{-4\pi (M^{\rm T}\xi-k)^{\rm T}(M^{\rm T}\xi-k)} \right] \ . \nonumber \hspace{2cm} (5) \end{align} El integrando es ahora un multidimensionales de gauss, que sería fácil de manejar si el $k$ total fueron una parte integral en lugar de una suma, y/o si los límites de la $\xi$ a la integración en el infinito, en lugar de $\pm1$. Ahora voy a describir las formas de evitar estos problemas.

Primero voy a tratar de cambiar el $\xi$ integración con finito de integración límites en un puro de gauss integral con límites en el infinito. La idea es llevar a cabo un singular valor de la descomposición de $M$, re-interpretar $\xi \in [-\frac12,\frac12]^m$ como un vector aleatorio con me.yo.d. componentes (cada una con media de $0$ y la varianza $\langle \xi_i^2 \rangle = \frac\gamma{8\pi}$) y, a continuación, aplicar el teorema del límite central. La varianza del parámetro $\gamma$ tiene un valor definido $$ \gamma\, = 8\pi \int_{-\frac12}^{\frac12}{\rm d}\xi\, \xi^2 = \frac{2\pi}3 \ , \hspace{2cm} (6) $$ pero por el momento voy a mantener como un parámetro. Expresar el $m$-dimensional $\xi$ integración como un estocástico promedio, $\langle \cdots \rangle_\xi = \int_{[-\frac12,\frac12]^m} {\rm d}^m\xi(\cdots)$, Eq. $(5)$ lee $$ P \approx \sum_{k\, \en\, \mathbb Z^n} \left\langle {\rm e}^{-4\pi \big(M^{\rm T}\xi-k\big)^{\rm T}\big(M^{\rm T}\xi-k\big)} \right\rangle_\xi \ . \hspace{2cm} (7) $$ Ahora vamos a utilizar la descomposición en valores singulares $M=V \Sigma U^{\rm T}$ con orthoganal matrices $V$, $U$ y una rectangular matriz diagonal $\Sigma$, que contiene en su diagonal (no negativo) valores singulares de $\sigma_i$ de % de$M$. Denota la ortonormales vectores columna de $U$ por $U_j$ ($j=1,...,n$) y los de $V$ por $V_i$ ($i=1,...,m$) podemos escribir esta descomposición de la siguiente manera: $$ M = \sum_{i=1}^m \sigma_i V_i U_i^{\rm T} \ . \hspace{2cm} (8) $$ Los autovalores de $MM^{\rm T}$ son $\lambda_i = \sigma_i^2$ ($i=1,...,m$) . La inserción de $(8)$ a $(7)$, entonces los rendimientos $$ P \approx \sum_{k\, \en\, \mathbb Z^n} \left\langle {\rm e}^{-4\pi \big( \sum_{i=1}^m \lambda_i \eta_i^2 - 2 \sum_{i=1}^m \eta_i \sigma_i U_i^{\rm T}k + k^{\rm T} k \big)} \right\rangle_\eta \ , \hspace{2cm} (9) $$ con $\eta_i = V_i^{\rm T}\xi$ (es decir, $\eta = V^{\rm T}\xi$). Si suponemos que todos los componentes de la matriz $V$ tiene "tamaño similar" ($\approx m^{-\frac12}$) en algunos adecuado sentido (por ejemplo, podrían ser normal distribuido con la varianza $m^{-1}$), se sigue del teorema central del límite que un gran $m$ la $\eta_i$ están correlacionadas gaussiano variables aleatorias con cero la media y la matriz de covarianza $\langle \eta_i \eta_j \rangle = \frac\gamma{8\pi} V_i^{\rm T}V_j = \frac\gamma{8\pi} \delta_{ij}$. Esto a su vez sugiere que, asintóticamente, $(9)$ puede ser re-escrita como \begin{align} P &\sim \sum_{k\, \in\, \mathbb Z^n} \left[ (\gamma/4)^{-\frac m2} \int_{\mathbb R^m} {\rm d}^m\eta \ \ {\rm e}^{-4\pi \big( \sum_{i=1}^m\eta_i^2/\gamma + \sum_{i=1}^m \lambda_i \eta_i^2 - 2 \sum_{i=1}^m \eta_i \sigma_i U_i^{\rm T}k + k^{\rm T} k \big)} \right] \nonumber\\ &\sim \left[ \prod_{i=1}^m \big( 1 + \gamma\, \lambda_i \big)^{-\frac12} \right] \sum_{k\, \in\, \mathbb Z^n} \exp {-4\pi \left[ \sum_{i=1}^m \frac{(U_i^{\rm T}k)^2}{1 + \gamma\, \lambda_i} + \sum_{j=m+1}^n (U_j^{\rm T}k)^2 \right]} \ . \nonumber \hspace{.5cm} (10) \end{align} Tenga en cuenta que de acuerdo a $(10)$, parece que la cantidad de $P$ asintóticamente sólo depende de los espectros de valor propio de la (simétrica) de matrices de $\Lambda = MM^{\rm T}$, es decir en la $\lambda_i$. (Además, puede depender, en cierta manera sutil, en el ortonormales de vectores $U_j$ definido por la descomposición de valor singular de $M$, pero permítanme hacer caso omiso a esta posibilidad por el momento.)
Los elementos de la matriz de $\Lambda = MM^{\rm T}$ puede ser expresado en la forma $$ \Lambda_{ij} = \frac n4 (\delta_{ij} + 1) + \mu_{ij} \ , \hspace{2cm} (11) $$ donde $\mu_{ij}$ son de gauss variables aleatorias con media de $0$ y la varianza $\langle \mu_{ij}^2 \rangle \approx \frac n4$ (pero no necesariamente correlacionados unos con otros). Utilizando la matriz de la teoría uno puede mostrado que la distribución de los autovalores $\lambda_i$ de ese $m \times m$ matriz $\Lambda$ para $m \ll n$ es muy alcanzó su punto máximo alrededor de $\lambda = \frac n4$ (el ancho de la distribución en $\lambda_{\rm max} - \lambda_{\rm min} \approx \sqrt{mn}$), aparte de un único autovalor, que es de la orden de $\lambda \approx \frac{mn}4$. Estrictamente hablando, al azar de la teoría de la matriz de garantías sólo si el $\mu_{ij}$ o el original de los elementos de la matriz de $M_{ij}$ son independientes de las variables aleatorias, pero experimentos numéricos sugieren que también tiene por azar Toeplitz (o circulantes) de matrices de $M$ (he hecho pruebas para la matriz de tamaños de hasta $m=4\times10^3$, $n=2\times10^5$). A partir de esto puedo concluir que se puede reemplazar todas las $\lambda_i$ en $(10)$ por $\frac n4$, a excepción de uno que es $\sim \frac{mn}4$.

Ahora podemos tratar de evaluar $(10)$. Si se nos permitió reemplazar el $k$ suma por una $n$-dimensión integral, nos gustaría obtener \begin{align} \sum_{k\, \in\, \mathbb Z^n} \exp-4\pi(\cdots) &\sim \int_{k\, \in\, \mathbb R^n} {\rm d}^n k \ \exp-4\pi(\cdots) \nonumber\\ &= 2^{-n} \left[ \prod_{i=1}^m \big( 1 + \gamma\, \lambda_i \big)^{\frac12} \right] \nonumber\\ &\sim 2^{-n}\, m^\frac12 \left( \frac{\gamma\, n}4 \right)^{\frac m2} \ , \nonumber \hspace{2cm} (12) \end{align} que junto con $(10)$ inmediatamente implica que $P$ tiene el valor más bajo posible $P \sim 2^{-n}$ para cualquier $m$. Sin embargo, sabemos que, al menos para los pequeños $m$ la última expresión en $(12)$ debe ser malo, puesto que el $k=0$ término de la suma es siempre igual a$1$, por lo que la suma total nunca puede ser menor que $1$. Además, $(12)$ puede, por supuesto, sólo sea una aproximación razonable si muchos términos en la suma de hacer alguna contribución sustancial, es decir, si la suma es mucho mayor que $1$.
Sobre la base de los argumentos anteriores, por lo tanto, creo que el siguiente tiene, asymtotically para un gran $n$: $$ \sum_{k\, \en\, \mathbb Z^n} \exp-4\pi\cdots) \sim \max\left\{ 1,\ 2^{n}\, m^\frac12 \left( \frac{\gamma\, n}4 \right)^{\frac m2} \right\} \ . \hspace{2cm} (13) $$ Ahora podemos combinar $(13)$ con $(10)$. Asintóticamente, el factor de $m^\frac12$ en $(13)$ es irrelevante e $2^{-n}\, m^\frac12 \left( \frac{\gamma\, n}4 \right)^{\frac m2} \geq 1$ es equivalente a $m \geq \frac{2n}{\log_2 ( \gamma n/4)}$, y así obtenemos: $$ P \sim \begin{cases} \quad 2^{-n} \ , \quad m > \frac{2n}{\log_2 ( \gamma n/4)} \\ \left( \frac{\gamma\, n}4 \right)^{-\frac m2} \ , \quad m \leq \frac{2n}{\log_2 ( \gamma n/4)} \end{casos} \ . \hspace{2cm} (14) $$ En particular, si elegimos $m$ a $$ m = \beta \frac{2n}{\log_2 ( \gamma\, n/4)} \ , \hspace{2cm} (15) $$ con algunas constantes $\beta \in ]0,1]$ de nuestra elección, entonces obtendremos $$ P \sim \left( \frac{\gamma\, n}4 \right)^{-\beta \frac{n}{\log_2 ( \gamma n/4)}} = 2^{-\beta n} \ . \hspace{2cm} (16) $$ Además, $(15)$ implica que el $m \sim \beta \frac{2n}{\log_2 n}$ asintóticamente, por lo que la hipótesis en la Conjetura 1* (o en el original de la Conjetura 1) corresponden a $\beta=\frac12$. En ese caso, $(16)$ parece conducir a la predicción de $P(Mw=0) \sim 2^{-\frac n2}$, para cualquier "típico" de la matriz de $M \in \{0,1\}^{m \times n}$, ya sea de Toeplitz forma o no. Esta es una declaración más fuerte (exponente mayor por un factor de 2) que la Conjetura 1.

Finalmente, como ya se indicó al principio de esta respuesta, creo que el argumento también tiene una influencia en la Conjetura 2. Es decir, desde la primera línea de $(14)$ (o mediante el establecimiento $\beta = 1$ en $(15)$ e $(16)$) vemos que predice que, si $m \geq \frac{2n}{\log_2 n}$ entonces $P(Mw=0) \sim 2^{-n}$ asintóticamente. Como tengo entendido, esto a su vez significaría que el conjunto de columnas de una elegidos al azar de la matriz $M \in \{0,1\}^{m \times n}$, ya sea de Toeplitz forma o no, es "débil disociadas" en el sentido de que la fracción de todos los sub-conjuntos cuya suma es no diferenciado de todos los demás tiende a cero en el límite de $n \to \infty$.