grafos

Universidad Aut´onoma de Madrid
Facultad de Ciencias
Departamento de Matem´aticas

El teorema de Freiman-Ruzsa
dirigido por Javier Cilleruelo

CARLOS VINUESA DEL R´IO
2006

Introducci´
on
El teorema de Freiman nos habla de la estructura de conjuntos con “conjunto suma” peque˜
no. ¿Qu´e significa eso?
Si A es un subconjunto (finito y no vac´ıo) de un grupo abeliano G,
definimos suconjunto suma como
A + A = {a + a : a, a ∈ A}
donde a y a no son necesariamente distintos.
¿Cu´antos elementos puede tener A + A? El n´
umero de sumas que se
pueden formar (algunas, por supuesto, podr´ıan dar el mismo resultado) es
|A|(|A|+1)
. As´ı lo muestra la siguiente figura, que es la tabla de sumar en A
2
(digamos que A = {a1 , a2 , . . . , an } y por lo tanto |A| = n)
+ a1 a2 . .. an
a1 • • •
•
a2 ◦ • •
•
... ◦ ◦ •
•
an ◦ ◦ ◦
•
pues 1 + 2 + · · · + n = n(n+1)
. As´ı, |A + A| ≤ |A|(|A|+1)
, y la igualdad puede
2
2
2
3
n−1
darse si, por ejemplo, G = Z y A = {1, 2, 2 , 2 , . . . , 2
} (si alguna suma
se repitiera tendr´ıamos un n´
umero que se escribe de dos formas distintas en
base 2 y eso es imposible).
Por otro lado, es claro que siempre tenemos ladesigualdad |A+A| ≥ |A|,
y la igualdad tambi´en puede darse (por ejemplo si A es un subgrupo de G).
Uno no tarda en darse cuenta de que es f´acil encontrar conjuntos con
conjunto suma grande, pero es mucho m´as dif´ıcil encontrar ejemplos en los
que el conjunto suma sea peque˜
no. De hecho, si tomamos, por ejemplo, un
conjunto A de n enteros “al azar” en el conjunto {1, . . . , x} con x ≥n4+ε
entonces la probabilidad de que no se repita ninguna suma (esto es, de que
|A + A| = |A|(|A|+1)
) tiende a 1 cuando n −→ ∞. Es decir, en general |A + A|
2
es grande y s´olo en casos muy especiales es peque˜
no. ¿Podemos caracterizar
estos pocos casos? ¿El hecho de que |A + A| sea peque˜
no implica que A debe
tener cierta estructura? El resultado de Freiman nos dice exactamente eso.
Apartir de ahora nos centraremos exclusivamente en el caso G = Z.
1

LEMA 1. Sea A ⊆ Z de tama˜
no n. Entonces |A + A| ≥ 2n − 1, con igualdad
si y s´
olo si A es una progresi´
on aritm´etica de longitud n.
Demostraci´
on. Como |A| = n podemos escribir A = {a1 , a2 , . . . , an } con
a1 < a2 < · · · < an . Es f´acil escribir 2n − 1 elementos distintos de A + A
a1 + a1 < a1 + a2 < · · ·
(1)

Tambi´en podemos dar otras listas de 2n − 1 elementos distintos, como las
n − 2 siguientes. Para todo 2 ≤ i ≤ n − 1 tenemos
a1 + a1 < · · · < a1 + ai < · · · < ai + ai < · · · < ai + an < · · · < an + an . (2)
Luego ya hemos demostrado de n − 1 formas que |A + A| ≥ 2n − 1. Ahora
bien, si |A + A| = 2n − 1 entonces todas las listas de 2n − 1elementos tienen
que coincidir. Eso quiere decir que para todo 2 ≤ i ≤ n − 1 se cumple,
comparando (1) con (2), que
a2 + ai = a1 + ai+1
de donde
a2 − a1 = ai+1 − ai

∀ 2 ≤ i ≤ n − 1.

Y decir que a2 − a1 = a3 − a2 = a4 − a3 = · · · = an − an−1 es decir que A es
una progresi´on aritm´etica de longitud n. Por otra parte, es trivial que para
una progresi´on aritm´etica de longitud n se tiene laigualdad.
As´ı que en los enteros, lo m´ınimo que vale |A + A| es 2|A| − 1 y los
conjuntos que alcanzan la cota tienen mucha estructura (son progresiones
aritm´eticas). No es dif´ıcil encontrar conjuntos un poco menos estructurados
para los que |A + A| siga siendo peque˜
no. Por ejemplo, si queremos que
|A + A| ≤ 4|A|, podemos tomar como A cualquier subconjunto de n elementos de unaprogresi´on aritm´etica de longitud 2n. Este tipo de conjuntos
son una parte “significativa” de una progresi´on aritm´etica. Pero si seguimos buscando podemos encontrar ejemplos de conjuntos con conjunto suma
peque˜
no que no son de esta forma.
Si tenemos x0 , x1 , . . . , xd ∈ Z y m1 , . . . , md ∈ Z>0 , podemos definir una
progresi´on aritm´etica generalizada P de dimensi´on d como sigue
P =...

Leer documento completo

Regístrate para leer el documento completo.