Desigualdad de Plünnecke-Rouge

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 8 de marzo de 2020; las comprobaciones requieren 4 ediciones .

Las desigualdades de Plünnecke-Rouge son un lema clásico en combinatoria aditiva . Describe restricciones sobre sumas múltiples de conjuntos bajo restricciones conocidas sobre sumas cortas similares. Por ejemplo, restricciones en con restricciones conocidas en . ${\ estilo de visualización | A + ABB |}$ ${\ estilo de visualización | A + B |}$

Las demostraciones de las desigualdades de Plünnecke-Rouge, por regla general, no usan la estructura del conjunto común al que pertenecen y , sino que solo usan los axiomas generales de la operación de grupo , lo que las hace verdaderas para grupos arbitrarios (en particular, para el conjuntos de números naturales y reales , así como los restos de la división de un número dado ) $A$ $B$

Nombrado en honor al matemático alemán H. Plünnecke [1] y al matemático húngaro Imre Rouge . [2]

Formulaciones

Se utiliza la siguiente notación

$A+B=\left\lbrace {a+b:a\in A,b\in B}\right\rbrace$

$nA=\left\lbrace {a_{1}+\dots +a_{n}:a_{1},\dots,a_{n}\in A}\right\rbrace$

$-A=\left\lbrace {-a:a\in A}\right\rbrace$

Para un conjunto

Sea un grupo abeliano , . Entonces se sigue de ${\ estilo de visualización (G, +)}$ $A\subconjunto G,K\in {\mathbb {R} }$ $|A+A|\leq K|A|$ $|nA-mA|<K^{n+m}|A|$

Prueba [3] [4] Lema

Si , entonces . $A,B,S\in G,|A+B|\leq K|B|,\forall Z\subset B(Z\not =B):\ |A+Z|\geq K|Z|$ ${\ estilo de visualización | A + B + S | \ leq K | B + S |}$

El lema se demuestra por inducción de tamaño . Porque la afirmación es obvia. Además, para algunos denotamos . Por la hipótesis de inducción, . $S$ ${\ estilo de visualización | S | = 1}$ $x \ en S$ $S'=S\setminus \left\lbrace {x}\right\rbrace$ $|A+B+S'|\leq K|B+S'|$

Consideremos un conjunto . Si , entonces . De lo contrario $Z_{x}=\left\lbrace {b+x\in B+S':b\in B}\right\rbrace$ ${\ estilo de visualización Z_ {x} = B}$ $|A+B+S|=|A+B+S'|\leq K|B+S'|=K|B+S|$

$A+B+S=(A+B+S')\cup ((A+B+\left\lbrace {x}\right\rbrace)\setminus (A+Z_{x}+\left\lbrace {x}\right\rbrace ))$

$|A+B+S|=|A+B+S'|+|A+B|-|A+Z_{x}|\leq K|B+S'|+K|B|-K |Z_{x}|=K(|B+S'|+|B|-|Z_{x}|)$

Y, por definición , ${\ Displaystyle Z_ {x}}$

$B+S=(B+S')\cup ((B\setminus Z_{x})+\left\lbrace {x}\right\rbrace)$

$|B+S|=|B+S'|+|B|-|Z_{x}|$

${\ estilo de visualización | A + B + S | \ leq K | B + S |}$

Derivación del teorema del lema

Elegimos un subconjunto que satisfaga los requisitos del lema. Entonces, de acuerdo con el lema para , $B=\arg \min \limits _{B\subconjunto A,|B|\geq 1}{\frac {|A+B|}{|B|}}$ ${\ estilo de visualización S = (n-1) A}$

$|nA+B|=|A+B+(n-1)A|\leq K|(n-1)A+B|=|A+B+(n-2)A|\leq K^{ 2}|(n-2)A+B|\leq ...\leq K^{(n-1)}|A+B|\leq K^{n}|A|$

A continuación, usamos la desigualdad del triángulo de Rouge .

$|B||nA-mA|=|-B||nA-mA|\leq |nA+B||mA+B|\leq K^{(n+m)}|A|$

Para dos juegos

Para any existe tal que si es un grupo , , entonces se sigue de $n_{1},n_{2},n_{3},n_{4}\geq 0$ $c=c(n_{1},n_{2},n_{3},n_{4})$ ${\ estilo de visualización (G, +)}$ $A,B\subconjunto G,|A|=|B|>1$ $K\in {\mathbb {R} }$ ${\ estilo de visualización | A + B | \ leq K | A |}$ $|n_{1}A+n_{2}A-n_{3}B-n_{4}B|\leq K^{c}|A|$

Prueba [5] Lema 1

Si , entonces . ${\ estilo de visualización C, D \ en G}$ $|CC|<\left({\frac {|C+D|}{|D|}}\right)|C+D|$

Esta afirmación se deriva directamente de la desigualdad del triángulo de Rouge

Lema 2

Si , entonces se sigue de que existe tal que y . ${\displaystyle A,B\en G,|A|=|B|,K\en {\mathbb {R} ))$ ${\ estilo de visualización | A + B | \ leq K | A |}$ $S\subconjunto A+B$ $|S|>{\frac{|A|}{2))$ $|A+B+S|<K^{3}|A|$

Para probar esto, considere el conjunto de elementos que tienen al menos representaciones en la forma . El número total de pares se puede estimar desde arriba como , entonces . ${\ estilo de visualización S \ en A + B}$ ${\frac{|A|}{2K}}$ ${\ estilo de visualización a + b, a \ en A, b \ en B}$ ${\ estilo de visualización (a, b) \ en A \ veces B}$ $|A|^{2}=|A||B|\leq |S||A|+(|A+B|-|S|){\frac {|A|}{2K}}\ leq |S||A|+{\frac {K|A|^{2}}{2K}}=|S||A|+{\frac {|A^{2}|}{2}}$ $|S|>{\frac{|A|}{2))$

Además, si la función se define como , entonces para cualquier imagen de la forma hay al menos diferentes imágenes inversas de la forma correspondientes a diferentes representaciones de . Es importante considerar tal arreglo de términos en la preimagen, porque todos los pares son obviamente iguales por definición. ${\ estilo de visualización \ lambda: (A + B) \ veces (A + B) \ a G}$ ${\ estilo de visualización \ lambda (x, y) = x + y}$ ${\ estilo de visualización a + b + s \ en A + B + S}$ ${\frac{|A|}{2K}}$ ${\ estilo de visualización (a+b',a'+b)}$ $a'+b'=s(a\en A,b\en B)$ ${\ estilo de visualización (a+b,a'+b')}$

Dado que cada elemento de tiene al menos preimágenes diferentes, entonces ${\ estilo de visualización A + B + S}$ ${\frac{|A|}{2K}}$

$|A+B+S|{\frac {|A|}{2K}}\leq |A+B|^{2}$

$|A+B+S|\leq {\frac {(K|A|)^{2}}{\left({\frac {|A|}{2K}}\right)))=K ^{3}|A|$

Derivación de la desigualdad a partir de lemas

Para datos, considere el conjunto obtenido en el Lema 2 y denote por el Lema 1 . Entonces, por el Lema 1, ${\ estilo de visualización A, B \ en G}$ $S$ ${\ estilo de visualización C = A + B, D = S}$

$|(A+B)-(A+B)|\leq \left({\frac {|A+B+S|}{|S|}}\right)|A+B+S|\ leq {\frac {(K^{3}|A|)^{2}}{\left({\frac {|A|}{2}}\right)}}\leq 2K^{6}|A |\leq K^{8}|A|$ .

La última desigualdad es verdadera, porque para . $K>{\frac{3}{2}}$ ${\ estilo de visualización | A |> 1}$

Entonces, y, repitiendo el mismo procedimiento para en lugar de , podemos obtener , y en general $|(AA)+(BB)|\leq K^{8}|A|$ ${\ estilo de visualización (AA), (BB)}$ $A,B$ $|(A+AAA)+(B+BBB)|\leq (K^{8})^{8}|AA|\leq K^{64}K^{8}|A|=K^ {72}|A|$

$|nA-nA+nB-nB|\leq K^{c}|A|\Rightarrow |2nA-2nA+2nB-2nB|\leq (K^{c})^{8}|nA-nA |\leq K^{(9c)}|A|$ .

Medio,

$|(2^{k})A-(2^{k})A+(2^{k})B-(2^{k})B|\leq K^{(9^{(} k+1))}|A|$

$|n_{1}A-n_{2}A+n_{3}B-n_{4}B|\leq K^{81\max(n_{1},n_{2},n_{3 },n_{4})^{\log _{2}{9}}}|A|\leq K^{(81(n_{1}+n_{2}+n_{3}+n_{4} )^{3.17})}|R|$

Generalización a un número arbitrario de conjuntos

Sea un grupo abeliano , , . Entonces Entonces hay un subconjunto no vacío tal que [2] [6] [7] ${\ estilo de visualización (G, +)}$ ${\ estilo de visualización X, B_ {1}, \ puntos, B_ {k} \ subconjunto G}$ $|B_{i}+X|\leq K_{i}|X|,i=1,\dots,k$ $|B_{1}+\puntos +B_{k}|\leq K_{1}\puntos K_{k}|X|$ $X'\subconjunto X$ $|X'+B_{1}+\puntos +B_{k}|\leq \alpha _{1}\puntos \alpha _{k}|X_{1}|$

Principales consecuencias

si , entonces $|A+A|\leq K|A|$ $|AA|\leq K|A|$

si , entonces $|AA|\leq K|A|$ $|A+A|\leq K^{8}|A|$

Por lo tanto, si se conoce el orden de crecimiento de y para el crecimiento de , entonces $K\in {\mathbb {R} }$ ${\displaystyle |A+A|,A\subconjunto {\mathbb {F} }_{p))$ $pags$

$|A+A|\leq K^{\Theta (1)}|A|\iff |AA|\leq K^{\Theta (1)}|A|$

Aplicaciones

La desigualdad de Plünnecke-Rouge se utiliza para probar el teorema de la suma del producto

Enlaces

M. Z. Garaev, Sumas y productos de conjuntos y estimaciones de sumas trigonométricas racionales en campos de orden primo . Archivado el 11 de diciembre de 2017 en Wayback Machine .

Notas

↑ H. Pl¨unnecke. Eine zahlentheoretische anwendung der graphtheorie. J. Reine Angew. Matemáticas 243:171–183, 1970
↑ 1 2 I. Z. Ruzsa, "Una aplicación de la teoría de grafos a la teoría de números aditivos", Sci. Ser. Una Matemática. ciencia (NS), 3 (1989), 97–109.
↑ Texto resumen de la conferencia de Harald Helfgott en la Universidad Estatal de San Petersburgo (enlace inaccesible)
↑ Conferencia de Harald Helfgott en la Universidad Estatal de San Petersburgo
↑ Boaz Barak, Luca Trevisan, Avi Wigderson, "Mini curso de combinatoria aditiva" (enlace no disponible) . Consultado el 8 de octubre de 2017. Archivado desde el original el 6 de febrero de 2015. (indefinido)
↑ IZ Ruzsa, “Sumas de conjuntos finitos”, Teoría de números (Nueva York, 1991–1995), Springer, Nueva York, 1996, 281–293.
↑ M. Z. Garaev, Sumas y productos de conjuntos y estimaciones de sumas trigonométricas racionales en campos de orden primo, USP, 2010, volumen 65, número 4(394), DOI: http://dx.doi.org/10.4213/rm9367