Para un conjunto finito A de reales positivos, demuestre que el conjunto A + A - A contiene al menos tantos elementos positivos como negativos

Question

Actualmente estoy trabajando en una prueba que necesitaría utilizar el siguiente teorema que no puedo demostrar:

"Let $A$ sea un conjunto finito de números reales positivos. Entonces, el conjunto $A + A - A$ contiene al menos tantos elementos positivos como negativos. ( $0$ se cuenta como elemento positivo)"

Aclaración: el conjunto $A + A - A$ se define como $\{a_1 + a_2 - a_3\mid a_1, a_2, a_3 \in A \}$ .

Por ejemplo: Si $A = \{2,5\}$ . Entonces $A+A-A = \{-1, 2, 5, 8\}$ .

La naturaleza de este problema radica en los duplicados que pueden producirse. Intuitivamente creo que el teorema debería ser cierto ya que añadimos un elemento de $A$ dos veces, pero resta un elemento sólo una vez. Sin embargo, me parece que es muy difícil de demostrar.

Esta es la idea en la que he estado trabajando hasta ahora (que podría ser la forma equivocada de hacer esto):

Sea $A = \{a_1, a_2,\dotsc,a_n\}$ . Primero examinamos el conjunto $A-A$ . Este conjunto es simétrico en torno a cero. Para cada elemento $x$ en $A-A$ , $-x$ también se produce en $A-A$ . Esto significa que para cada elemento negativo, también existe un único elemento positivo.

A continuación examinamos el conjunto $a_1 + A - A$ . Esto sólo cambia $A-A$ a la derecha. Algunos elementos negativos podrían transformarse en positivos, pero eso no nos importa. Lo importante es que todos los elementos positivos sigan siendo positivos. Por lo tanto, de nuevo, este conjunto contiene más o igual número de elementos positivos que negativos.

Mi siguiente idea es mirar el conjunto $a_2 + A - A$ y tomar la unión con el conjunto $a_1 + A - A$ . Quiero hacer esto con cada $a_i$ . Eso significa que al final tomo la siguiente unión: $\bigcup\limits_{i=1}^{n}a_i + A - A$ que es exactamente $ A+A-A$ .

Quiero demostrar en cada paso que todavía hay más o igual número de elementos positivos que negativos en la unión actual de conjuntos. Mi idea para hacer esto es pensar en lo siguiente: Puesto que $A-A$ es simétrica en torno a $0$ puedo dividir $A-A$ en elementos que son $>0$ y elementos que son $<0$ (no nos importa el $0$ ). Estos dos subconjuntos tienen el mismo tamaño. Si añadimos un $a_i$ a un elemento positivo, tenemos dos casos:

1. Caso: Obtenemos un nuevo elemento que no aparece ya en nuestra unión de conjuntos. En este caso no tenemos que hacer nada.

2. Caso: Tenemos un duplicado. En este caso tenemos que demostrar que también obtenemos un duplicado único si añadimos $a_i$ a un determinado elemento negativo.

Mi método para el segundo caso fue: Si $a_i + x_1 = y$ y $y$ es un duplicado, entonces existe un $a_j$ tal que $a_j + x_2 = y$ . Desde $x_1$ y $x_2$ están contenidos en el conjunto $A - A$ sabemos que $-x_1$ y $-x_2$ también están contenidos en el conjunto $A - A$ . Ahora vemos que $a_i + (-x_2)$ también produce un duplicado que se origina a partir del número negativo $-x_2$ ya que $a_i + (-x_2) = a_j + (-x_1)$ .

En realidad, este método siempre encuentra un duplicado negativo, pero no es el único en casos muy concretos. Es posible que dos duplicados positivos diferentes se refieran al mismo duplicado negativo.

Ejemplo (un ejemplo real sería demasiado grande, así que supongamos que $A$ contiene $3$ , $4$ y $6$ y asumir que $A - A$ contiene $4$ , $5$ y $7$ y por lo tanto también $-4$ , $-5$ y $-7$ ):

• $4 + A - A$ contiene $4 + 4 = 8$ (y $4 + (-5) = -1$ )

• $6 + A - A$ contiene $6 + 4 = 10$ (y $6 + (-7) = -1$ )

• $3 + A - A$ contiene $3 + 5 = 8$ y $3 + 7 = 10$ . Ambos duplicados se refieren al mismo duplicado negativo $3 + (-4) = -1$ .

Aunque este caso es muy específico, desgraciadamente destruye toda mi prueba.

Si alguien tiene una idea para este problema, tal vez incluso con un método completamente diferente, estaría muy agradecido de escuchar y también muy emocionado de discutirlo.

Nota al margen: Para mi proyecto, bastaría con demostrar que

$$ \left(\begin{array}{@{}c@{}} \text{Number of positive}\\ \text{elements in $A + A - A$}\\ \end{array}\right) \geq c\cdot \left(\begin{array}{@{}c@{}} \text{Number of elements}\\ \text{in $A + A - A$}\\ \end{array}\right) $$ donde $c>0$ no depende de $A$ . Creo que es cierto para $c = \frac{1}{2}$ .

Answer 1

He aquí un contraejemplo. Primero necesitamos un " más sumas que diferencias " construcción:

Lema . Para cualquier $\varepsilon>0$ existe un grupo cíclico ${\bf Z}/N{\bf Z}$ y un subconjunto no vacío $A \subset {\bf Z}/N{\bf Z}$ tal que $A+A = {\bf Z}/N{\bf Z}$ pero $|A-A| \leq \varepsilon N$ .

Prueba . Hay muchas construcciones; he aquí sólo una. Primero observamos si $p$ es un primo grande, entonces podemos conseguir esta afirmación con $N=p$ y $\varepsilon = 1-2/p$ mediante una construcción probabilística, es decir, seleccionando $A$ consistirá en un elemento al azar para cada uno de los $\lfloor \frac{p}{3}\rfloor$ pares $\{ 3j, 3j+1\}$ para $0 \leq j < \frac{p-2}{3}$ . $A-A$ seguramente evitará $\pm 1$ mientras que $A+A$ será igual a todo ${\bf Z}/p{\bf Z}$ con una probabilidad exponencialmente alta por un argumento estándar de límite de unión.

Tomando los productos cartesianos de estos ejemplos y utilizando el teorema chino del resto, se puede llegar a la afirmación para $\varepsilon = \prod_{k=1}^K (1-\frac{2}{p_k})$ para cualquier secuencia $p_1,\dots,p_K$ de primos distintos suficientemente grandes. En Teorema de Mertens (o Teorema de Euler ) este producto puede ser arbitrariamente pequeño, y la afirmación se cumple. $\Box$

Corolario . Para cualquier $\varepsilon>0$ existe $N > 1$ y $A' \subset \{1,\dots,2N\}$ tal que $|A'+A'| \geq N$ y $|A'-A'| = O(\varepsilon N)$ .

Prueba Toma $A' := \{ 1 \leq n \leq 2N: n \hbox{ mod } N \in A \}$ donde $A$ es como en el lema anterior; nótese que $A'+A'$ entonces contiene $\{N+1,\dots,2N\}$ . $\Box$

Ahora dejemos que $\varepsilon>0$ sea una cantidad suficientemente pequeña (por ejemplo, se puede tomar $\varepsilon = \frac{1}{100}$ ), y $A' \subset \{1,\dots,2N\}$ sea como en el corolario anterior, entonces $|A'| \leq |A'-A'| \ll \varepsilon N$ Por lo tanto $\varepsilon N \gg 1$ . Si tomamos

$$ A'' := A' \cup \{ 10N, 20N, 30N, 40N, 50N \}$$ entonces $|A''| = O(\varepsilon N)$ y $A''+A''-A''$ contiene el conjunto $$ A'+A' - \{10N, 20N, 30N, 40N, 50N \}$$ que tiene cardinalidad al menos $5N$ y consiste enteramente en números negativos. Por otra parte, los elementos positivos de $A''+A''-A''$ están contenidos en la unión de $\{1,\dots,4N\}$ el conjunto $$ \{10N, 20N, 30N, 40N, 50N \} + A'-A',$$ el conjunto $$ \{10N, 20N, 30N, 40N, 50N \} + \{10N, 20N, 30N, 40N, 50N \} - A''$$ y el conjunto $$ \{10N, 20N, 30N, 40N, 50N \} + A'' - \{10N, 20N, 30N, 40N, 50N \},$$ y por tanto el número de elementos positivos es como máximo $4N + O(\varepsilon N)$ . Para $\varepsilon$ suficientemente pequeño obtenemos un contraejemplo.

EDIT: Por otra parte, si se cuentan los elementos del conjunto $A+A-A$ con multiplicidad (es decir, se estudia la convolución $1_A * 1_A * 1_{-A}$ en lugar de la suma $A+A-A$ ), entonces es seguro que al menos la mitad de los elementos (contando la multiplicidad) son positivos. Esto se debe a que para cualquier $a_1,a_2,a_3 \in A$ al menos uno de $a_1+a_2-a_3$ y $a_1+a_3-a_2$ es positivo. Promediando este hecho sobre todas las opciones de $a_1,a_2,a_3$ da la reclamación.

SEGUNDA EDICIÓN: como menciona Oliver en los comentarios, (una ligera modificación de) esta construcción responde a la primera pregunta de la sección 4.3 de esta tesis de Peter Bradshaw en negativo.

Answer 2

La siguiente idea puede funcionar, aunque el último paso parece heurístico.

Sea $A=\{a_1, \ldots, a_n \}$ y que $$C:= \{0 , \pm \alpha_1, \ldots \pm \alpha_k \}$$ con $\alpha_1, \ldots, \alpha_k >0$ .

Sea $D:= \{ \alpha_1, \ldots, \alpha_k \}$ .

Entonces $$ (A+A-A)_+=\{x \in A+A-A : x >0 \} \supseteq A+D \\ (A+A-A)_-=\{x \in A+A-A : x <0 \} \subseteq A-D \\ $$ Por lo tanto, si podemos demostrar que $|A-D| \leq |A+D|$ ya está.

Ahora, defina $$ F: A \times D \to A+D , F(x,y)= x+y \\ G: A \times D \to A-D, G(x,y)=x-y \,. $$ Estas funciones cumplen $F(a,b)=F(c,d) \Leftrightarrow G(a,d)=G(c,d)$ . Si esto se puede utilizar para demostrar que $F,G$ tienen rangos de cardinalidad iguales, ya está; si no, debería borrar esto.