Límites de empaquetamiento para conjuntos de sumas, o, bolas muy discretas

Question

Dejemos que $D\subset \mathbb{F}_2^n$ con $D=-D$ y $0\in D$ . Escriba $k D$ para el conjunto de todas las sumas de $k$ (no necesariamente distintos) elementos de $D$ . (Esta es la "bola" del título).

Ahora dejemos que $d(g,h)$ sea la distancia Hamming normalizada, es decir, el número de entradas de $g-h\in \mathbb{F}_2^n$ que son iguales a $0$ dividido por $n$ . (Por ejemplo, para $e_1=(1,0,...,0)$ tenemos $d(e_1,0) = 1/n$ .)

Supongamos que $d(g,0)>1/3$ para cada elemento $g$ de $100 D$ distinto de $0$ . ¿Qué límite superior se puede dar al número de elementos de $D$ ?

(Nota: si asumimos $d(g,0)>\delta$ sólo para cada elemento $g$ de $2D$ ( $=D-D$ ) distinta de $0$ tendríamos un límite superior muy bueno (es decir, minúsculo) del número de elementos de $D$ para $\delta>1/2$ , y un límite superior mucho mayor (exponencial en $n$ ) para $\delta<1/2$ . Estoy buscando pequeños límites).

Answer 1

Creo que para $100D$ sólo se puede esperar un límite exponencial para $\delta=1/3$ (o cualquier $\delta<1/2$ ). Sea $d=(d_1, \dots, d_k)$ , donde el $d_i$ son uniformes e independientes de $\mathbb{F}_2^n$ (puede darse el caso de que algunos $d_i$ son iguales, pero la probabilidad de que esto ocurra es insignificante si $k<2^{n/2}$ e incluso para los más grandes $k$ es probable que sólo haya un pequeño número de repeticiones).

Para cualquier $(i_1, \dots, i_{100})$ la suma $d_{i_1}+\dots+d_{i_{100}}$ también es uniforme en $\mathbb{F}_2^n$ . En particular, la probabilidad de que su distancia de $0$ es como máximo $1/3$ es como máximo $2^{-cn}$ para alguna constante $c>0$ .

Hay menos de $k^{100}$ sumas en $100D$ y cada uno está cerca de $0$ con una probabilidad máxima de $2^{-cn}$ , por lo que la probabilidad $100D$ contiene un elemento cercano a $0$ es como máximo $2^{-cn}k^{100}$ . Si $k$ es una exponencial de crecimiento suficientemente lento en $n$ , entonces esto es menos que $1$ y un conjunto aleatorio de tamaño $k$ probablemente tenga su propiedad.