En combinatoria aditiva , el teorema de Freiman es un resultado central que indica la estructura aproximada de conjuntos cuyo sumatorio es pequeño. Afirma aproximadamente que si es pequeño, entonces puede estar contenido en una pequeña progresión aritmética generalizada .
Declaración
Si es un subconjunto finito de con , luego está contenido en una progresión aritmética generalizada de dimensión como máximo y tamaño como máximo , dónde y son constantes que dependen solo de .
Ejemplos de
Para un conjunto finito de enteros, siempre es cierto que
con igualdad precisamente cuando es una progresión aritmética.
De manera más general, suponga es un subconjunto de una progresión aritmética generalizada propia finita de dimensión tal que para algunos reales . Luego, así que eso
Historia del teorema de Freiman
Este resultado se debe a Gregory Freiman (1964, 1966). [1] Mucho interés y aplicaciones surgieron de una nueva prueba de Imre Z. Ruzsa (1994). Mei-Chu Chang probó nuevas estimaciones polinómicas para el tamaño de las progresiones aritméticas que surgen en el teorema en 2002. [2] Los mejores límites actuales fueron proporcionados por Tom Sanders . [3]
Herramientas utilizadas en la prueba
La prueba presentada aquí sigue a la prueba en las notas de la conferencia de Yufei Zhao. [4]
Desigualdad Plünnecke-Ruzsa
Ruzsa cubriendo lema
El lema de cobertura de Ruzsa establece lo siguiente:
- Dejar y ser subconjuntos finitos de un grupo abeliano con no vacío, y deja ser un número real positivo. Entonces sí , hay un subconjunto de con como máximo elementos tales que .
Este lema proporciona un límite sobre cuántas copias de uno necesita cubrir , de ahí el nombre. La prueba es esencialmente un algoritmo codicioso :
Prueba: dejar ser un subconjunto máximo de tal que los conjuntos por son todos inconexos. Luego, y también , entonces . Además, para cualquier, hay algunos tal que se cruza , como añadiendo a contradice la maximalidad de . Por lo tanto, entonces .
Homomorfismos de Freiman y el lema de modelado de Ruzsa
Dejar ser un número entero positivo, y y ser grupos abelianos. Dejar y . Un mapaes un Freiman-homomorfismo si
cuando sea para cualquier .
Si además es una biyección y es un Freiman -homomorfismo, entonces es un Freiman -isomorfismo .
Si es un Freiman -homomorfismo, entonces es un Freiman -homomorfismo para cualquier entero positivo tal que .
Luego, el lema de modelado de Ruzsa establece lo siguiente:
- Dejar ser un conjunto finito de enteros, y sea ser un número entero positivo. Dejar ser un entero positivo tal que . Entonces existe un subconjunto de con cardinalidad al menos tal que es Freiman -isomorfo a un subconjunto de .
La última declaración significa que existe algo de Freiman -Homomorfismo entre los dos subconjuntos.
Boceto de prueba: elija un primer suficientemente grande como para que el módulo mapa de reduccion es un Freiman -isomorfismo de a su imagen en . Dejar ser el mapa de elevación que lleva a cada miembro de a su representante único en . Para distinto de cero, dejar ser la multiplicación por mapa, que es un Freiman -isomorfismo. Dejar ser la imagen . Elija un subconjunto adecuado de con cardinalidad al menos tal que la restricción de a es un Freiman -isomorfismo en su imagen, y dejar ser la preimagen de debajo . Entonces la restricción de a es un Freiman -isomorfismo en su imagen . Por último, existe alguna opción de distinto de cero tal que la restricción del módulo reducción a es un Freiman -isomorfismo sobre su imagen. El resultado sigue después de componer este mapa con el anterior Freiman-isomorfismo.
Conjuntos de Bohr y el lema de Bogolyubov
Aunque el teorema de Freiman se aplica a conjuntos de números enteros, el lema de modelado de Ruzsa permite modelar conjuntos de números enteros como subconjuntos de grupos cíclicos finitos . Por lo tanto, es útil trabajar primero en la configuración de un campo finito y luego generalizar los resultados a los números enteros. Bogolyubov demostró el siguiente lema:
- Dejar y deja . Luego contiene un subespacio de de dimensión al menos .
Generalizar este lema a grupos cíclicos arbitrarios requiere una noción análoga a "subespacio": la del conjunto de Bohr. Dejar ser un subconjunto de dónde es un primo. El conjunto de dimensiones de Bohr y ancho es
dónde es la distancia desde al entero más cercano. El siguiente lema generaliza el lema de Bogolyubov:
- Dejar y . Luego contiene un conjunto de dimensiones de Bohr como máximo y ancho .
Aquí la dimensión de un conjunto de Bohr es análoga a la codimensión de un conjunto en. La prueba del lema involucra métodos analíticos de Fourier . La siguiente proposición relaciona los juegos de Bohr con progresiones aritméticas generalizadas, lo que eventualmente conduce a la demostración del teorema de Freiman.
- Dejar ser un Bohr establecido en de dimensión y ancho . Luego contiene una progresión aritmética generalizada adecuada de dimensión como máximo y tamaño al menos .
La demostración de esta proposición utiliza el teorema de Minkowski , un resultado fundamental en la geometría de los números .
Prueba
Por la desigualdad de Plünnecke-Ruzsa, . Según el postulado de Bertrand , existe un primer tal que . Según el lema de modelado de Ruzsa, existe un subconjunto de de cardinalidad al menos tal que es Freiman 8-isomorfo a un subconjunto .
Por la generalización del lema de Bogolyubov, contiene una progresión aritmética generalizada adecuada de dimensión a lo sumo y tamaño al menos . Porque y son Freiman 8-isomorfos, y son Freiman 2-isomorfos. Luego, la imagen bajo el isomorfismo 2 de la progresión aritmética generalizada adecuada en es una progresión aritmética generalizada adecuada en llamada .
Pero , desde . Por lo tanto
así que por el lema de cobertura de Ruzsa para algunos de cardinalidad como máximo . Luego está contenido en una progresión aritmética generalizada de dimensión y tamaño como máximo , completando la prueba.
Generalizaciones
Un resultado debido a Ben Green e Imre Ruzsa generalizó el teorema de Freiman a grupos abelianos arbitrarios. Utilizaron una noción análoga a las progresiones aritméticas generalizadas, a las que llamaron progresiones de clase lateral. Una progresión de la clase lateral de un grupo abeliano es un conjunto para una adecuada progresión aritmética generalizada y un subgrupo de . La dimensión de esta progresión de clases laterales se define como la dimensión de, y su tamaño se define como la cardinalidad de todo el conjunto. Green y Ruzsa mostraron lo siguiente:
- Dejar ser un conjunto finito en un grupo abeliano tal que . Luego está contenido en una progresión de cotas de dimensión como máximo y tamaño como máximo , dónde y son funciones de que son independientes de .
Green y Ruzsa proporcionaron límites superiores de y por alguna constante absoluta . [5]
Terence Tao (2010) también generalizó el teorema de Freiman a grupos solubles de longitud derivada acotada. [6]
La extensión del teorema de Freiman a un grupo arbitrario no beliano aún está abierta. resultados para, cuando un conjunto tiene una duplicación muy pequeña, se denominan teoremas de Kneser . [7]
Ver también
Referencias
- ^ Nathanson (1996) p.252
- ^ Chang, Mei-Chu (2002). "Un polinomio ligado en el teorema de Freiman". Duke Math. J . 113 (3): 399–419. CiteSeerX 10.1.1.207.3090 . doi : 10.1215 / s0012-7094-02-11331-3 . Señor 1909605 .
- ^ Sanders, Tom (2013). "La teoría de la estructura de la adición de conjuntos revisada". Toro. Amer. Matemáticas. Soc . 50 : 93-127. doi : 10.1090 / S0273-0979-2012-01392-7 .
- ^ Zhao, Yufei. "Teoría de grafos y combinatoria aditiva" (PDF) .
- ^ Ruzsa, Imre Z .; Green, Ben (2007). "Teorema de Freiman en un grupo abeliano arbitrario". Revista de la Sociedad Matemática de Londres . 75 (1): 163-175. arXiv : matemáticas / 0505198 . doi : 10.1112 / jlms / jdl021 .
- ^ Tao, Terence (2010). "Teorema de Freiman para grupos solubles". Contrib. Desct. Matemáticas . 5 (2): 137-184. doi : 10.11575 / cdm.v5i2.62020 .
- ^ Tao, Terence . "Un teorema de Freiman elemental no conmutativo" . Blog de Terence Tao .
- Freiman, GA (1964). "Suma de conjuntos finitos". Sov. Math., Dokl . 5 : 1366-1370. Zbl 0163.29501 .
- Freiman, GA (1966). Fundamentos de una teoría estructural de la suma de conjuntos (en ruso). Kazán: Kazan Gos. Ped. Inst. pag. 140. Zbl 0203.35305 .
- Freiman, GA (1999). "Teoría de la estructura de la suma de conjuntos". Astérisque . 258 : 1–33. Zbl 0958.11008 .
- Nathanson, Melvyn B. (1996). Teoría de números aditivos: problemas inversos y geometría de conjuntos . Textos de Posgrado en Matemáticas . 165 . Saltador. ISBN 978-0-387-94655-9. Zbl 0859.11003 .
- Ruzsa, Imre Z. (1994). "Sumas y progresiones aritméticas generalizadas". Acta Mathematica Hungarica . 65 (4): 379–388. doi : 10.1007 / bf01876039 . Zbl 0816.11008 .
- Tao, Terence (2010). "Teorema de Freiman para grupos solubles". Contrib. Desct. Matemáticas . 5 (2): 137-184. doi : 10.11575 / cdm.v5i2.62020 .
Este artículo incorpora material del teorema de Freiman sobre PlanetMath , que está bajo la licencia Creative Commons Attribution / Share-Alike License .