Encontrar la constante c > 0?

Question

Encontrar una constante c > 0 tal que para todo conjunto finito de números enteros B no contiene 0, existe un subconjunto a de B tales que a es la suma y |A| ≥ c|B|, donde |a| se refiere al número de elementos de A.

Answer 1

Este problema se puede encontrar en el Teorema 1.3 de Terence Tao y Van Vu del libro "additve combinatoria". Voy a escribir a continuación ya que tal vez usted no tiene una copia de la misma.

Podemos optar $c=\frac{1}{3}$ mediante el uso de un método de probabilidades. En primer lugar, debemos escoger un número primo $p=3k+2$ donde $k$ es lo suficientemente grande como para que $B\subset [-\frac{p}{3},\frac{p}{3}]\backslash\{0\}$. Podemos ver $B$ como subconjunto de $\mathbb{Z}_p$ y nota que un subconjunto $A$ $B$ es de suma-libre cuando la consideramos como un subconjunto de a $\mathbb{Z}_p$ si, y sólo si se suma gratis en números enteros.

Podemos elegir un número aleatorio $x\in\mathbb{Z}_p\backslash\{0\}$ de manera uniforme, lo que significa que x aparece con igual probabilidad. A continuación, tenemos en cuenta el conjunto $$A=B\cap(x\cdot[k+1,2k+1])=\{a\in A:x^{-1}a\in\{k+1,k+2,\ldots,2k+1\}\}. $$ Since $[k+1,2 k+1]$ is sum-free in $\mathbb{Z}_p$, $$ is also sum-free in $\mathbb{Z}_p$. We have that $$E(|A|)=\sum_{a\in B}P(a\in A)=\sum_{a\in B} P(x^{-1}a\in[k+1,2k+1]).$$ If $un\en B$, then $a$ is a invertible element in $\mathbb{Z}_p$ (since $p$ is a prime), and thus $x^{-1}a$ is uniformly distributed in $\mathbb{Z}_p\backslash\{0\}$. Since $|[k+1,2 k+1]|=k+1>p/3$, so for all $a\en B$ we have $ P(x^{-1}\in[k+1,2 k+1])>1/3$. Thus $E(|A|)>\frac{|B|}{3}$ which implies that $|Un|\geq \frac{|B|}{3}$ with positive probablity and so we can find $x$ to make that $$ is sum-free and $|A|\geq \frac{|B|} {3}$.

De hecho, el número de $1/3$ es óptimo en cierto sentido, como se mostró en un papel de Sean Eberhard, Ben Verde y Freddie Modales denominado "Conjuntos de enteros sin gran suma-libre subconjunto", que dice:

Hay un conjunto de n enteros positivos con ninguna suma-libre subconjunto de tamaño mayor que $\frac{1}{3}n + o(n)$.