Teoria Combinatoria

Cap´ ıtulo 1 Teor´ Aditiva y Combinatoria de ıa N´ meros u
En este cap´ ıtulo trataremos algunos problemas aditivos en la teor´ de n´meros ıa u con cierto sabor combinatorio. ¿Qu´ podemos deciracerca del tama˜o de un conjunto A ⊂ [1, N ] de enteros e n con la propiedad de que sus elementos no satisfacen una ecuaci´n determinada? o La respuesta a esta pregunta en cada una de las siguientesecuaciones representa un problema central en la teor´ combinatoria de n´meros. ıa u 1. x + y = z + w (Conjuntos de Sidon) 2. x + y = 2z (Conjuntos sin progresiones aritm´ticas) e 3. x + y = z (Conjuntoslibres de sumas )

Se define el conjunto suma de dos conjuntos A y B como A + B = {a + b : a ∈ A, b ∈ B}. De manera m´s general se define a A1 + · · · + Ak = {a1 + · · · + ak : ai ∈ Ai }. Los conjuntosproductos se definen de manera an´loga. a Muchos problemas de la teor´ de n´meros se pueden plantear en t´rminos de ıa u e los conjuntos suma. 1

2

´ CAP´ ITULO 1. TEOR´ ADITIVA Y COMBINATORIA DENUMEROS IA

Por ejemplo la conjetura de Goldbach afirma que P + P = {6, 8, 10, ..., 2n, ...} donde P es el conjunto de los primos impares. El teorema de Lagrange que vimos en una secci´n anteriorafirma que S + S + S + S = {0, 1, 2, 3, ..n, ..} donde S = o 2 {k : k ≥ 0}. El estudio de todos estos problemas nos permiten ilustrar los diferentes m´toe dos, combinatorios, anal´ ıticos y probabil´ısticos que aparecen con frecuencia en la teor´ aditiva combinatoria de n´meros. ıa u Empezaremos con los m´todos de criba que han permitido resolver muchos e problemas.

1.1.

M´todos de criba eSupongamos que queremos construir una tabla formada por todos los n´meros u primos menores que un cierto entero positive x. Empezaremos escribiendo todos los enteros menores que x. Como un enterocompuesto debe ser divisible por por un primo menor o igual que su ra´ cuadrada, ız el procedimiento a seguir consistir´ en ir tachando todos aquellos que sean divisibles a √ por alg´n primo menor que...