Teorema de Freiman

Sobre la estructura aproximada de conjuntos cuya suma es pequeña

En la combinatoria aditiva , una disciplina dentro de las matemáticas, el teorema de Freiman es un resultado central que indica la estructura aproximada de los conjuntos cuyo conjunto sumatorio es pequeño. A grandes rasgos, establece que si es pequeño, entonces puede estar contenido en una progresión aritmética generalizada pequeña . ${\displaystyle |A+A|/|A|}$ ${\displaystyle A}$

Declaración

Si es un subconjunto finito de con , entonces está contenido en una progresión aritmética generalizada de dimensión como máximo y tamaño como máximo , donde y son constantes que dependen únicamente de . ${\displaystyle A}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle |A+A|\leq K|A|}$ ${\displaystyle A}$ ${\displaystyle d(K)}$ ${\displaystyle f(K)|A|}$ ${\displaystyle d(K)}$ ${\displaystyle f(K)}$ ${\displaystyle K}$

Ejemplos

Para un conjunto finito de números enteros, siempre es cierto que ${\displaystyle A}$

${\displaystyle |A+A|\geq 2|A|-1,}$

con igualdad precisamente cuando es una progresión aritmética. ${\displaystyle A}$

De manera más general, supongamos que es un subconjunto de una progresión aritmética generalizada propia finita de dimensión tal que para algún real . Entonces , de modo que ${\displaystyle A}$ ${\displaystyle P}$ ${\displaystyle d}$ ${\displaystyle |P|\leq C|A|}$ ${\displaystyle C\geq 1}$ ${\displaystyle |P+P|\leq 2^{d}|P|}$

${\displaystyle |A+A|\leq |P+P|\leq 2^{d}|P|\leq C2^{d}|A|.}$

Historia del teorema de Freiman

Este resultado se debe a Gregory Freiman (1964, 1966). ^{[1] [2] [3]} Mucho interés en él, y sus aplicaciones, surgieron a partir de una nueva prueba de Imre Z. Ruzsa (1992,1994). ^{[4] [5]} Mei-Chu Chang demostró nuevas estimaciones polinómicas para el tamaño de las progresiones aritméticas que surgen en el teorema en 2002. ^[6] Los mejores límites actuales fueron proporcionados por Tom Sanders . ^[7]

Herramientas utilizadas en la prueba

La prueba presentada aquí sigue la prueba en las notas de la conferencia de Yufei Zhao. ^[8]

Desigualdad de Plünnecke-Ruzsa

Lema de cobertura de Ruzsa

El lema de cobertura de Ruzsa establece lo siguiente:

Sean y subconjuntos finitos de un grupo abeliano con no vacío, y sea un número real positivo. Entonces, si , existe un subconjunto de con como máximo elementos tales que . ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle K}$ ${\displaystyle |A+S|\leq K|S|}$ ${\displaystyle T}$ ${\displaystyle A}$ ${\displaystyle K}$ ${\displaystyle A\subseteq T+S-S}$

Este lema proporciona un límite sobre la cantidad de copias de uno que se deben cubrir , de ahí el nombre. La prueba es esencialmente un algoritmo voraz : ${\displaystyle S-S}$ ${\displaystyle A}$

Demostración: Sea un subconjunto máximo de tal que los conjuntos para son todos disjuntos. Entonces , y también , por lo que . Además, para cualquier , existe algún conjunto tal que interseca a , ya que de lo contrario, sumar a contradice la maximalidad de . Por lo tanto , por lo que . ${\displaystyle T}$ ${\displaystyle A}$ ${\displaystyle t+S}$ ${\displaystyle A}$ ${\displaystyle |T+S|=|T|\cdot |S|}$ ${\displaystyle |T+S|\leq |A+S|\leq K|S|}$ ${\displaystyle |T|\leq K}$ ${\displaystyle a\in A}$ ${\displaystyle t\in T}$ ${\displaystyle t+S}$ ${\displaystyle a+S}$ ${\displaystyle a}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle a\in T+S-S}$ ${\displaystyle A\subseteq T+S-S}$

Homomorfismos de Freiman y el lema de modelado de Ruzsa

Sea un entero positivo, y y grupos abelianos. Sean y . Una función es un homomorfismo de Freiman si ${\displaystyle s\geq 2}$ ${\displaystyle \Gamma }$ ${\displaystyle \Gamma '}$ ${\displaystyle A\subseteq \Gamma }$ ${\displaystyle B\subseteq \Gamma '}$ ${\displaystyle \varphi \colon A\to B}$ ${\displaystyle s}$

${\displaystyle \varphi (a_{1})+\cdots +\varphi (a_{s})=\varphi (a_{1}')+\cdots +\varphi (a_{s}')}$

cuando sea para cualquier . ${\displaystyle a_{1}+\cdots +a_{s}=a_{1}'+\cdots +a_{s}'}$ ${\displaystyle a_{1},\ldots ,a_{s},a_{1}',\ldots ,a_{s}'\in A}$

Si además es una biyección y es un homomorfismo de Freiman, entonces es un isomorfismo de Freiman . ${\displaystyle \varphi }$ ${\displaystyle \varphi ^{-1}\colon B\to A}$ ${\displaystyle s}$ ${\displaystyle \varphi }$ ${\displaystyle s}$

Si es un homomorfismo de Freiman, entonces es un homomorfismo de Freiman para cualquier entero positivo tal que . ${\displaystyle \varphi }$ ${\displaystyle s}$ ${\displaystyle \varphi }$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle 2\leq t\leq s}$

Luego el lema de modelado de Ruzsa establece lo siguiente:

Sea un conjunto finito de números enteros, y sea un número entero positivo. Sea un número entero positivo tal que . Entonces existe un subconjunto de con cardinalidad al menos tal que es isomorfo en el sentido de Freiman a un subconjunto de . ${\displaystyle A}$ ${\displaystyle s\geq 2}$ ${\displaystyle N}$ ${\displaystyle N\geq |sA-sA|}$ ${\displaystyle A'}$ ${\displaystyle A}$ ${\displaystyle |A|/s}$ ${\displaystyle A'}$ ${\displaystyle s}$ ${\displaystyle \mathbb {Z} /N\mathbb {Z} }$

La última afirmación significa que existe cierto homomorfismo de Freiman entre los dos subconjuntos. ${\displaystyle s}$

Bosquejo de la demostración: Elija un primo suficientemente grande de modo que la función de reducción módulo sea un isomorfismo de Freiman de a su imagen en . Sea la función de elevación que lleva cada miembro de a su único representante en . Para distinto de cero , sea la función de multiplicación por , que es un isomorfismo de Freiman. Sea la imagen . Elija un subconjunto adecuado de con cardinalidad al menos tal que la restricción de a sea un isomorfismo de Freiman sobre su imagen, y sea la preimagen de bajo . Entonces la restricción de a sea un isomorfismo de Freiman sobre su imagen . Por último, existe alguna elección de distinto de cero tal que la restricción de la reducción módulo a sea un isomorfismo de Freiman sobre su imagen. El resultado se obtiene después de componer esta función con el isomorfismo de Freiman anterior . ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle \pi _{q}\colon \mathbb {Z} \to \mathbb {Z} /q\mathbb {Z} }$ ${\displaystyle s}$ ${\displaystyle A}$ ${\displaystyle \mathbb {Z} /q\mathbb {Z} }$ ${\displaystyle \psi _{q}\colon \mathbb {Z} /q\mathbb {Z} \to \mathbb {Z} }$ ${\displaystyle \mathbb {Z} /q\mathbb {Z} }$ ${\displaystyle \{1,\ldots ,q\}\subseteq \mathbb {Z} }$ ${\displaystyle \lambda \in \mathbb {Z} /q\mathbb {Z} }$ ${\displaystyle \cdot \lambda \colon \mathbb {Z} /q\mathbb {Z} \to \mathbb {Z} /q\mathbb {Z} }$ ${\displaystyle \lambda }$ ${\displaystyle s}$ ${\displaystyle B}$ ${\displaystyle (\cdot \lambda \circ \pi _{q})(A)}$ ${\displaystyle B'}$ ${\displaystyle B}$ ${\displaystyle |B|/s}$ ${\displaystyle \psi _{q}}$ ${\displaystyle B'}$ ${\displaystyle s}$ ${\displaystyle A'\subseteq A}$ ${\displaystyle B'}$ ${\displaystyle \cdot \lambda \circ \pi _{q}}$ ${\displaystyle \psi _{q}\circ \cdot \lambda \circ \pi _{q}}$ ${\displaystyle A'}$ ${\displaystyle s}$ ${\displaystyle \psi _{q}(B')}$ ${\displaystyle \lambda }$ ${\displaystyle N}$ ${\displaystyle \mathbb {Z} \to \mathbb {Z} /N\mathbb {Z} }$ ${\displaystyle \psi _{q}(B')}$ ${\displaystyle s}$ ${\displaystyle s}$

Conjuntos de Bohr y 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 el contexto de un cuerpo finito y luego generalizar los resultados a los números enteros. El siguiente lema fue demostrado por Bogolyubov:

Sea y sea . Entonces contiene un subespacio de de dimensión al menos . ${\displaystyle A\subseteq \mathbb {F} _{2}^{n}}$ ${\displaystyle \alpha =|A|/2^{n}}$ ${\displaystyle 4A}$ ${\displaystyle \mathbb {F} _{2}^{n}}$ ${\displaystyle n-\alpha ^{-2}}$

Generalizar este lema a grupos cíclicos arbitrarios requiere una noción análoga a la de “subespacio”: la del conjunto de Bohr. Sea un subconjunto de donde es un primo. El conjunto de Bohr de dimensión y anchura es ${\displaystyle R}$ ${\displaystyle \mathbb {Z} /N\mathbb {Z} }$ ${\displaystyle N}$ ${\displaystyle |R|}$ ${\displaystyle \varepsilon }$

${\displaystyle \operatorname {Bohr} (R,\varepsilon )=\{x\in \mathbb {Z} /N\mathbb {Z} :\forall r\in R,|rx/N|\leq \varepsilon \},}$

donde es la distancia desde hasta el entero más cercano. El siguiente lema generaliza el lema de Bogolyubov: ${\displaystyle |rx/N|}$ ${\displaystyle rx/N}$

Sea y . Entonces contiene un conjunto de Bohr de dimensión como máximo y ancho . ${\displaystyle A\subseteq \mathbb {Z} /N\mathbb {Z} }$ ${\displaystyle \alpha =|A|/N}$ ${\displaystyle 2A-2A}$ ${\displaystyle \alpha ^{-2}}$ ${\displaystyle 1/4}$

Aquí la dimensión de un conjunto de Bohr es análoga a la codimensión de un conjunto en . La prueba del lema implica métodos analíticos de Fourier . La siguiente proposición relaciona los conjuntos de Bohr con progresiones aritméticas generalizadas, lo que finalmente conduce a la prueba del teorema de Freiman. ${\displaystyle \mathbb {F} _{2}^{n}}$

Sea un conjunto de Bohr de dimensión y ancho . Entonces contiene una progresión aritmética generalizada propia de dimensión como máximo y tamaño como mínimo . ${\displaystyle X}$ ${\displaystyle \mathbb {Z} /N\mathbb {Z} }$ ${\displaystyle d}$ ${\displaystyle \varepsilon }$ ${\displaystyle X}$ ${\displaystyle d}$ ${\displaystyle (\varepsilon /d)^{d}N}$

La prueba 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, . Por el postulado de Bertrand , existe un primo tal que . Por el lema de modelado de Ruzsa, existe un subconjunto de de cardinalidad al menos tal que es 8-isomorfo de Freiman a un subconjunto . ${\displaystyle |8A-8A|\leq K^{16}|A|}$ ${\displaystyle N}$ ${\displaystyle |8A-8A|\leq N\leq 2K^{16}|A|}$ ${\displaystyle A'}$ ${\displaystyle A}$ ${\displaystyle |A|/8}$ ${\displaystyle A'}$ ${\displaystyle B\subseteq \mathbb {Z} /N\mathbb {Z} }$

Por la generalización del lema de Bogolyubov, contiene una progresión aritmética generalizada propia de dimensión como máximo y tamaño como mínimo . Porque y son isomorfos 8 de Freiman, y son isomorfos 2 de Freiman. Entonces la imagen bajo el isomorfismo 2 de la progresión aritmética generalizada propia en es una progresión aritmética generalizada propia en llamada . ${\displaystyle 2B-2B}$ ${\displaystyle d}$ ${\displaystyle (1/(8\cdot 2K^{16}))^{-2}=256K^{32}}$ ${\displaystyle (1/(4d))^{d}N}$ ${\displaystyle A'}$ ${\displaystyle B}$ ${\displaystyle 2A'-2A'}$ ${\displaystyle 2B-2B}$ ${\displaystyle 2B-2B}$ ${\displaystyle 2A'-2A'\subseteq 2A-2A}$ ${\displaystyle P}$

Pero , ya que . Por lo tanto ${\displaystyle P+A\subseteq 3A-2A}$ ${\displaystyle P\subseteq 2A-2A}$

${\displaystyle |P+A|\leq |3A-2A|\leq |8A-8A|\leq N\leq (4d)^{d}|P|}$

Así, 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. ${\displaystyle A\subseteq X+P-P}$ ${\displaystyle X\subseteq A}$ ${\displaystyle (4d)^{d}}$ ${\displaystyle X+P-P}$ ${\displaystyle |X|+d}$ ${\displaystyle 2^{|X|}2^{d}|P|\leq 2^{|X|+d}|2A-2A|\leq 2^{|X|+d}K^{4}|A|}$

Generalizaciones

Un resultado de 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 cosets. Una progresión de cosets de un grupo abeliano es un conjunto para una progresión aritmética generalizada propia y un subgrupo de . La dimensión de esta progresión de cosets se define como la dimensión de , y su tamaño se define como la cardinalidad de todo el conjunto. Green y Ruzsa demostraron lo siguiente: ${\displaystyle G}$ ${\displaystyle P+H}$ ${\displaystyle P}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle P}$

Sea un conjunto finito en un grupo abeliano tal que . Entonces está contenido en una progresión de clase lateral de dimensión como máximo y tamaño como máximo , donde y son funciones de que son independientes de . ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle |A+A|\leq K|A|}$ ${\displaystyle A}$ ${\displaystyle d(K)}$ ${\displaystyle f(K)|A|}$ ${\displaystyle f(K)}$ ${\displaystyle d(K)}$ ${\displaystyle K}$ ${\displaystyle G}$

Green y Ruzsa proporcionaron límites superiores de y para alguna constante absoluta . ^[9] ${\displaystyle d(K)=CK^{4}\log(K+2)}$ ${\displaystyle f(K)=e^{CK^{4}\log ^{2}(K+2)}}$ ${\displaystyle C}$

Terence Tao (2010) también generalizó el teorema de Freiman a grupos resolubles de longitud derivada acotada. ^[10]

La extensión del teorema de Freiman a un grupo no abeliano arbitrario aún está abierta. Los resultados para , cuando un conjunto tiene una duplicación muy pequeña, se conocen como teoremas de Kneser . ^[11] ${\displaystyle K<2}$

La conjetura polinómica de Freiman–Ruzsa, ^[12] es una generalización publicada en un artículo ^[13] de Imre Ruzsa pero atribuida por él a Katalin Marton . Establece que si un subconjunto de un grupo (una potencia de un grupo cíclico ) tiene una constante de duplicación tal que entonces está cubierto por un número acotado de clases laterales de algún subgrupo con . En 2012, Tom Sanders dio un límite casi polinómico de la conjetura para grupos abelianos. ^{[14] [15] En 2023,} Tim Gowers , Ben Green , Freddie Manners y Terry Tao publicaron una solución sobre un cuerpo de característica 2 como preimpresión . ^{[16] [17] [18]} Esta prueba se formalizó completamente en el lenguaje de prueba formal Lean 4 , un proyecto colaborativo que marcó un hito importante en términos de los matemáticos que formalizaron con éxito las matemáticas contemporáneas. ^[19] ${\displaystyle A\subset G}$ ${\displaystyle |A+A|\leq K|A|}$ ${\displaystyle K^{C}}$ ${\displaystyle H\subset G}$ ${\displaystyle |H|\leq |A|}$ ${\displaystyle G=\mathbb {F} _{2}^{n}}$

Véase también

• Espectro de Markov
• Desigualdad de Plünnecke-Ruzsa
• Teorema de Kneser (combinatoria)

Referencias

1. Freiman, GA (1964). "Suma de conjuntos finitos". Matemáticas soviéticas. Doklady . 5 : 1366–1370. Zbl  0163.29501.
2. Freiman, GA (1966). Fundamentos de una teoría estructural de la adición de conjuntos (en ruso). Kazán: Kazán Gos. Ped. Inst. p. 140. Zbl  0203.35305.
3. Nathanson, Melvyn B. (1996). Teoría de números aditivos: problemas inversos y geometría de conjuntos sumatorios . Textos de posgrado en matemáticas . Vol. 165. Springer. ISBN. 978-0-387-94655-9.Zbl 0859.11003  .pág. 252.
4. Ruzsa, IZ (agosto de 1992). "Progresiones aritméticas y el número de sumas". Periodica Mathematica Hungarica . 25 (1): 105–111. doi :10.1007/BF02454387. ISSN  0031-5303.
5. Ruzsa, Imre Z. (1994). "Progresiones aritméticas generalizadas y conjuntos de sumas". Acta Mathematica Hungarica . 65 (4): 379–388. doi : 10.1007/bf01876039 . Zbl  0816.11008.
6. Chang, Mei-Chu (2002). "Un polinomio ligado en el teorema de Freiman". Revista de Matemáticas de Duke . 113 (3): 399–419. CiteSeerX 10.1.1.207.3090 . doi :10.1215/s0012-7094-02-11331-3. SEÑOR  1909605. 
7. Sanders, Tom (2013). "Revisión de la teoría de la estructura de la adición de conjuntos". Boletín de la Sociedad Matemática Americana . 50 : 93–127. arXiv : 1212.0458 . doi :10.1090/S0273-0979-2012-01392-7. S2CID  42609470.
8. Zhao, Yufei. "Teoría de grafos y combinatoria aditiva" (PDF) . Archivado desde el original (PDF) el 23 de noviembre de 2019. Consultado el 2 de diciembre de 2019 .
9. 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 : math/0505198 . doi :10.1112/jlms/jdl021. S2CID  15115236.
10. Tao, Terence (2010). "Teorema de Freiman para grupos resolubles". Contribuciones a las matemáticas discretas . 5 (2): 137–184. doi : 10.11575/cdm.v5i2.62020 .
11. Tao, Terence (10 de noviembre de 2009). "Un teorema elemental de Freiman no conmutativo". Blog de Terence Tao .
12. "(Ben Green) La conjetura polinómica de Freiman–Ruzsa". Novedades . 2007-03-11 . Consultado el 2023-11-14 .
13. Ruzsa, I. (1999). "Un análogo del teorema de Freiman en grupos" (PDF) . Astérisque . 258 : 323–326.
14. Lijadoras, Tom (15 de octubre de 2012). "Sobre el lema de Bogolyubov-Ruzsa". Análisis y PDE . 5 (3): 627–655. arXiv : 1011.0107 . doi : 10.2140/apde.2012.5.627 . ISSN  1948-206X.
15. Brubaker, Ben (4 de diciembre de 2023). "Un problema que parece fácil produce números demasiado grandes para nuestro universo". Revista Quanta . Consultado el 11 de diciembre de 2023 .
16. Gowers, WT; Green, Ben; Manners, Freddie; Tao, Terence (2023). "Sobre una conjetura de Marton". arXiv : 2311.05762 [math.NT].
17. "Sobre una conjetura de Marton". Novedades . 2023-11-13 . Consultado el 2023-11-14 .
18. Sloman, Leila (6 de diciembre de 2023). «El 'Equipo A' de Matemáticas demuestra un vínculo crítico entre la suma y los conjuntos». Revista Quanta . Consultado el 16 de diciembre de 2023 .
19. "La conjetura polinómica de Freiman-Ruzsa". Página de inicio del proyecto PFR .

Lectura adicional

• Freiman, GA (1999). "Teoría de la estructura de la suma de conjuntos". Astérisque . 258 : 1–33. Zbl  0958.11008.

Este artículo incorpora material del teorema de Freiman en PlanetMath , que se encuentra bajo la licencia Creative Commons Attribution/Share-Alike License .