Intuición detrás de un contraejemplo a$|A+A|\leq |A-A|$, donde$A$ es un conjunto finito

Question

Definir

$$A+A=\{a+b:a,b \in A\}, A-A = \{a-b:a,b \in A\}$$

A continuación, demostrar o refutar las siguientes

$$|A+A|\leq |A-A|$$

Intuitivamente, esto debe ser cierto, como

$$a+b=b+a$$

$$a-b \neq b-a$$

Sin embargo, me descubrió accidentalmente el siguiente contraejemplo por Conway propuesto en 1969

$$A=\{1,2,3,5,8,9,13,15,16\}$$

donde

$$A+A=\{2,3,...,32\}-\{27\}, |A+A|=30$$ $$A-A=\{-15,-14,...,15\}-\{\pm 9\}, |A-A|=29$$

Increíble! Cómo había llegado a esto? (Por supuesto, puede hacerlo utilizando un programa de ordenador...)

Answer 1

Permítanme mencionar un resultado general: Teorema 4 en "Muchos de los juegos de Más las Sumas De las Diferencias" por Greg Martin y Kevin O''Bryant:

Para cada entero $x$, hay un conjunto $A\subseteq\{0, 1,\dots , 17|x|\}$ con $|A+A|−|A−A|=x$.

Su prueba da una idea de cómo estos conjuntos puede ser obtenida.

Tenga en cuenta que para $x=1$, tenemos $A=\{0, 2, 3, 4, 7, 11, 12, 14\}$. Entonces $$A+A=\{0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 26, 28\}$$ y $$A-A= \{-14, -12, -11, -10, -9, -8, -7, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 14\}.$$ Por lo tanto $|A+A|=26>25=|A-A|$.

Para una generalización para abelian grupos de "Conjuntos con más sumas de las diferencias por Melvyn B. Nathanson.