Esto terminó siendo mucho, mucho más largo de lo que esperaba para llegar al menos en su mayor parte rigurosa, así que disculpas de antemano por una larga respuesta. La respuesta corta es sí: la creación de solapamientos está "acoplada" entre elementos negativos y positivos, de tal forma que el número de elementos negativos es siempre menor que el número de elementos positivos.
(I) Empecemos por hacer $A$ un conjunto ordenado, con $0 < a_1 < a_2 \cdots < a_n$ y conjuntos de etiquetado de tamaño $n$ como $A_n$ en general. Denotaremos $B = A+A-A$ y $C=A-A$ con $B_n, C_n$ según proceda.
Hay tres formas fundamentalmente diferentes de hacer miembro de $B_n$ lo que da tres subconjuntos. Tenemos:
$$ \begin{align} B_{n, 1} & = \{a_j + (a_i - a_j) = a_i \mid a_i, a_j \in A_n\} = A \\ B_{n, 2} &= \{a_i + a_j - a_k \mid a_i, a_j, a_k \in A_n\} \\ B_{n, 3} &= \{2a_i - a_j \mid a_i, a_j \in A_n\} \end{align} $$
Consideremos la cardinalidad máxima posible $B^*_n$ de $\lvert \{B\} \rvert$ . Podemos ver que los hay: $n$ posibles elementos en $B_{n, 1}$ ; $(n-2)\binom{n}{2}$ posibles elementos en $B_{n, 2}$ y $2\binom{n}{2}$ posibles elementos en $B_{n, 3}$ . La suma de estos, $B^*_n = n\binom{n}{2}+n$ resulta ser OEIS A006000 con $B^*_2 = 4, B^*_3 = 12, B^*_4 = 28, B^*_5 = 55, \cdots$ .
(II) Veamos ahora el número máximo de negativo elementos de $B$ , asumiendo también tenemos el número máximo de elementos. Está claro que todos los elementos de $B_{n, 1}=A$ son positivos. Para maximizar los elementos negativos en $B_{n, 2}$ queremos tener $a_m > a_{m-1} + a_{m-2}$ para todos los elementos de $A$ . Entonces cada triple donde $k>j>i$ da un elemento $a_i+a_j-a_k < 0$ y tendremos $\binom{n-1}{2} + \binom{n-2}{2} + \cdots + \binom{2}{2} = \binom{n}{3}$ elementos negativos en $B_{n,2}$ . Si elegimos nuestro conjunto de tal manera que $a_m > 2a_{m-1}$ entonces exactamente la mitad de los elementos de $B_{n,3}$ son negativos. Por lo tanto, hay un máximo de $\binom{n}{3} + \binom{n}{2} = \binom{n+1}{3}$ elementos negativos en $B_n$ para $n\ge 2$ . En $n$ se hace grande, la relación entre éste y el número total de elementos se aproxima a $\frac13$ con un máximo de $\frac{35}{96} < 0.365$ en $n=5$ . (*) Esto será importante más adelante.
(Tenga en cuenta que el conjunto $B$ tiene no elementos negativos si $2a_1 > a_n$ . Prueba dejada como ejercicio, etc.)
(III) Vale, pero ¿qué pasa cuando encogemos $B$ ? Si elegimos $A$ tal que $B$ hace no tienen el máximo número de elementos, ¿permite dicha contracción que los elementos negativos superen a los positivos? La respuesta es "no", pero tenemos que dar algunos pasos más. De momento, supongamos que nuestro punto de partida tiene la cardinalidad máxima de $B$ y el número máximo de elementos negativos en $B$ .
En primer lugar, veamos subconjuntos de $A$ , concretamente triples $(a_x, a_y, a_z)$ . Cada triple da $12$ elementos de $B$ como se ha indicado anteriormente; llámese a este subconjunto en general $B_{xyz}$ . Es evidente que existen $\binom{n}{2}$ triples en $A_n$ Pero también es evidente que hay solapamientos entre las distintas $B_{xyz}$ para $n>3$ como $12 \binom{n}{3} > n\binom{n}{2}+n$ para $n>3$ .
Si cambiamos un elemento de $A$ , digamos $a_i$ tal que algún subconjunto $B_{ijk}$ se reduce debido a nuevos solapamientos, entonces algunos subconjuntos, como $B_{pqr}$ no se modificará. Otros, como $B_{ij \ell}$ , puede o no puede cambio de cardinalidad. Dado que partimos de conjuntos de tamaño máximo, $\lvert B_{ij \ell} \rvert$ al menos, no aumentará.
Hay exactamente dos cambios que podemos hacer que disminuyan $\lvert B_{ijk} \rvert$ :
- (i) Cambio $a_i$ tal que tres de las diferencias en $C$ están en progresión aritmética. Es decir, en el conjunto alterado, $2a_j - 2a_i = a_k - a_j$
- (ii) Cambio $a_i$ tal que tres de los elementos de $A$ están en progresión aritmética. En el conjunto alterado, $a_j - a_i = a_k - a_j$ . Tenga en cuenta que esta elección provoca $\lvert C \rvert$ disminuir (en $2$ ).
Por último, si se produce un cambio en $a_i$ también disminuye $\lvert B_{ij \ell} \rvert$ significa $B_{ij \ell}$ también cambiará de una de las maneras mencionadas. Es decir, cualquier cambio que hagamos para alterar el conjunto original (maximal) $A$ sólo puede cambiar la cardinalidad de $B$ de estas dos maneras.
(IV) Veamos los elementos de $B_{ijk}$ asumiendo $4a_i < 2a_j < a_k$ para obtener el máximo número de elementos negativos:
$$ \begin{align} B_{ijk} = &\{a_i, a_j, a_k\} \\ &\cup \{\color{red}{a_i+a_j-a_k}, a_j+a_k-a_i, a_k+a_i-a_j\} \\ &\cup \{\color{red}{2a_i-a_j, 2a_i-a_k, 2a_j-a_k}, 2a_j-a_i, 2a_k-a_i, 2a_k-a_j\} \end{align} $$
Resaltados en rojo están los cuatro elementos que son negativos según nuestros supuestos.
Si alteramos $a_i$ como en la opción (i) anterior, de modo que $2a_j - 2a_i = a_k - a_j$ nos encontramos con que esto crea dos nuevos duplicados:
\begin{align} \color{red}{2a_i - a_j} &= \color{red}{2a_j - a_k} \\ 2a_j - a_i &= a_i + a_k - a_j \\ \end{align}
Y aquí, finalmente tenemos el "acoplamiento" de solapamientos. Este cambio hace que se solapen dos elementos negativos y dos positivos. Esto significa que seguimos teniendo más elementos positivos que negativos en $B$ .
¿Y la opción (ii)? Modificamos $a_i$ tal que $a_j - a_i = a_k - a_j$ . Eso nos da un gran número de nuevos solapamientos:
\begin{align} \color{red}{2a_i - a_j} &= \color{red}{a_i + a_j - a_k} \\ 2a_k - a_j &= a_j + a_k - a_i \\ 2a_j - a_i &= a_k \\ a_i + a_k - a_j &= a_j \\ \color{red}{2a_j - a_k} &= a_i \end{align}
La primera igualdad disminuye el número de elementos negativos en $1$ . Los tres siguientes disminuyen el número de elementos positivos en $3$ . Y esa última igualdad... bueno, ¿esa última igualdad qué hace? Bueno, sabemos $a_i$ debe seguir siendo positivo, por lo que esta superposición elimina un elemento negativo. Este cambio, entonces, acopla una disminución de tres elementos positivos con una disminución de dos elementos negativos. Eso podría ser un problema...
(V) Excepto, espera... ¿qué es esto? ¿Por qué es el (*) que dije en la Parte II que sería importante más tarde, ¡vendría al rescate! Hola de nuevo, (*) ¡! ¿Cómo dice?
¡Ajá! De nuestro conjunto maximal, sabemos por (*) que como máximo $36.5\%$ de los elementos son negativos, por lo que como mínimo $63.5\%$ son positivos. Dividiendo estos, esto significa que los elementos positivos y negativos están en como mínimo a $1.74:1$ relación.
Utilizando la opción (i), eliminamos los elementos positivos y negativos en a $1:1$ relación. Utilizando la opción (ii), los eliminamos en un $1.5:1$ relación. No importa cuántas alteraciones hagamos como se indica en la Parte III, eliminamos comparativamente más de los elementos negativos sobre la marcha. Si empezamos con un $1.74:1$ relación, y hacer una alteración, la relación siempre se aumentar Hasta que finalmente (1) nos quedamos sin alteraciones que hacer, o (2) nos quedamos sin elementos negativos, dejando sólo elementos positivos.
Por lo tanto, en todo momento, el subconjunto de elementos positivos de $B$ es mayor que el subconjunto de elementos negativos de $B$ según se desee.
¡Lo hemos conseguido! Hora de un trago un descanso cama, ¿en serio? Cómo vuela el tiempo. Buenas noches, y espero que esto resista las pruebas. Por favor, señale los agujeros / errores, por supuesto.
EDIT: Respondiendo a la pregunta de abajo sobre cómo los pasos en III y IV trabajan juntos. He aquí una explicación mejor de la que estoy más convencido. Estoy seguro de que podría ser más riguroso por algo que ha pasado más tiempo en la teoría de conjuntos que yo.
Como usted dice, queremos demostrar la afirmación para el conjunto $A_n$ y empezaremos con otro conjunto $A'_n$ donde $\lvert B' \rvert = B^*_n$ tal y como se ha definido anteriormente. Para completar la prueba, cambiamos elementos de $A'_n$ de uno en uno, a lo largo del tiempo convirtiendo $B'_n$ a $B^{(1)}_{n}, B^{(2)}_{n}, \cdots$ hasta que en algún momento, $B^{(k)}_{n} =B$ . Cuando cambiamos $a'_i$ todos los elementos de $B$ que incluía $a'_i$ en su cálculo también cambian. Estos son todos los subconjuntos $B'_{i[yz]}$ para todos $y,z$ utilizados como índices.
Establecer $B'$ tiene cardinalidad máxima y el número máximo de elementos negativos (supongo que este número podría usar un símbolo, llámalo $B^{*-}_n$ (es probable que lo añada más arriba). Cuando cambiemos $a_i$ para crear $B^{(1)}_{n}$ consideramos cada subconjunto $B_{i[yz]}$ .
Cada subconjunto triple puede cambiar su cardinalidad; la primera vez, cada uno sólo puede disminuir o permanecer igual. Si su cardinalidad hace cambian, entonces (i) se eliminan un elemento positivo y uno negativo, o (ii) se eliminan tres elementos positivos y dos negativos. Esto puede ocurrir para varios subconjuntos triples, pero en cada caso hemos visto que la única forma de cambiar el subconjunto triple (de maximal) es de estas dos maneras.
Después de cambiar un elemento de $A'$ y encontró $B^{(1)}_{n}$ otro cambio puede causar un aumentar en cardinalidad en uno o más de los subconjuntos triples. Ese aumento puede producirse de dos maneras, a la inversa de las disminuciones: el subconjunto gana un elemento positivo y uno negativo, o gana tres elementos positivos y dos negativos.
Hay otra posibilidad no considerada. Es posible tener un cambio en el número de elementos negativos y positivos sin cambiar la cardinalidad total. Pero como partimos de $B^{*-}_n$ elementos negativos, en el primer cambio, éste sólo puede sustituir elementos negativos por positivos. En los cambios posteriores, esto puede invertirse, ganando elementos negativos y perdiendo positivos. Pero el paso atrás sólo puede darse tantas veces como pasos adelante hayamos dado. Nunca podemos pasar de ese número máximo inicial de elementos negativos para cada triple.
En conclusión, cualquiera de estas transiciones puede avanzar o retroceder, pero no pueden retroceder más de lo que han avanzado. No podemos quedarnos sin elementos positivos que eliminar antes de quedarnos sin elementos negativos que eliminar.
De nota, algo que echaba de menos para conjuntos más grandes: Es posible tener una secuencia aritmética como subconjunto de $C$ pero tienen $B$ en cardinalidad máxima. Esto parece ocurrir cuando la secuencia aritmética se forma a partir de tres pares diferentes de $a_i, a_j$ en cuyo caso la secuencia no se ajusta a las ecuaciones dadas, o cuando algún $a_j = 2a_i$ que pierde la cardinalidad máxima de los elementos negativos (como $0$ se considera "positivo" en $B$ ). Esto, sin embargo, no cambia nada en el resto de la prueba - es simplemente algo a notar como un aparte.
Por último, esta secuencia:
$$a_i = 1, 3, 8, 19, 43, 93, 200, 418, 864, 1766, 3575, 7196, 14449, 28956, 57972, 116006$$
Es el más pequeño que he encontrado que se ajuste a los criterios: Tome la primera $n$ de esta lista como elementos de $A_n$ . El conjunto $A_n$ producirá un conjunto $B_n$ con cardinalidad máxima y cardinalidad máxima de elementos negativos.
