Teorema de Freiman

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|}$${\estilo de visualización A}$

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 . ${\estilo de visualización A}$${\displaystyle \mathbb {Z}}$${\displaystyle |A+A|\leq K|A|}$${\estilo de visualización A}$${\estilo de visualización d(K)}$${\displaystyle f(K)|A|}$${\estilo de visualización d(K)}$${\estilo de visualización f(K)}$${\estilo de visualización K}$

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

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

con igualdad precisamente cuando es una progresión aritmética. ${\estilo de visualización 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 ${\estilo de visualización A}$${\estilo de visualización P}$${\estilo de visualización 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|.}$

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]

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

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 .${\estilo de visualización A}$${\estilo de visualización S}$${\estilo de visualización S}$${\estilo de visualización K}$${\displaystyle |A+S|\leq K|S|}$${\estilo de visualización T}$${\estilo de visualización A}$${\estilo de visualización K}$${\displaystyle A\subseteq T+SS}$

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 : ${\estilo de visualización SS}$${\estilo de visualización 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 . ${\estilo de visualización T}$${\estilo de visualización A}$${\estilo de visualización t+S}$${\estilo de visualización A}$${\displaystyle |T+S|=|T|\cdot |S|}$${\displaystyle |T+S|\leq |A+S|\leq K|S|}$${\displaystyle |T|\leq K}$${\displaystyle a\en A}$${\displaystyle t\en T}$${\estilo de visualización t+S}$${\estilo de visualización a+S}$${\estilo de visualización a}$${\estilo de visualización T}$${\estilo de visualización T}$${\displaystyle a\en T+SS}$${\displaystyle A\subseteq T+SS}$

Sea un entero positivo, y y grupos abelianos. Sean y . Una función es un homomorfismo de Freiman si${\displaystyle s\geq 2}$${\estilo de visualización \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}$

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\in \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\in \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 .

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|}$

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}}$

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

• Freiman, GA (1999). "Teoría estructural de la adición 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 .