Muchas sumas

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 11 de mayo de 2018; las comprobaciones requieren 7 ediciones .

El conjunto de sumas es el concepto de combinatoria aditiva , correspondiente a la suma de Minkowski de conjuntos finitos .

Definición

Sea cualquier grupo y sean conjuntos finitos. Entonces su suma es el conjunto ${\mbox{G}}$ $A,B\subconjunto {\mbox{G))$

{\displaystyle A+B:=\{a+b:a\en A,\b\en B\))

Para un conjunto, su conjunto de sumas se llama . Las sumas múltiples se abrevian [1] $A$ ${\ estilo de visualización A + A}$

{\displaystyle kA=A+\dots +A=\{a_{1}+\dots +a_{k}:a_{i}\in A,\ i=1,\dots,k\))

Definiciones relacionadas

De manera similar, el conjunto de diferencias , el conjunto de productos , el conjunto de cocientes y similares se definen para cualquier operación. Por ejemplo, el conjunto de productos se define de la siguiente manera [2] :

{\displaystyle A\times B=\{ab\ :\a\in A,\b\in B\))

El valor se denomina constante de duplicación [3] , y se dice que los conjuntos para los que está acotado tienen una pequeña duplicación [4] . En relación con el teorema de la suma del producto , a menudo se consideran conjuntos con pequeñas duplicaciones multiplicativas , es decir, cuyo valor es limitado [5] . $K(A)={\frac {|A+A|}{|A|}}$ ${\frac{|AA|}{|A|}}$

Propiedades

La potencia del conjunto de sumas está relacionada con la energía aditiva por la desigualdad [6] , por lo que esta última suele utilizarse para estimarla. $A+B$ ${\ estilo de visualización E (A, B)}$ ${\displaystyle |A+B|E(A,B)\leq |A|^{2}|B|^{2))$

Sumas de un conjunto

El teorema de Freiman considera el tamaño como un indicador de la estructuración de un conjunto (si la constante de duplicación es limitada, entonces la estructura es similar a una progresión aritmética generalizada ). [7] [8] ${\ estilo de visualización A + A}$ $A$

El teorema suma-producto relaciona el tamaño del conjunto de sumas y el conjunto de productos. La hipótesis principal dice que para . [9] La combinación de sumatoria y producto en una sola expresión condujo al surgimiento de la combinatoria aritmética . ${\displaystyle \max\{|A+A|,\ |AA|\}\geq |A|^{2-o(1)))$ $A\subconjunto \mathbb {R}$

Estudiamos la influencia de la aplicación elemento por elemento de una función convexa a conjuntos sumables sobre el tamaño del conjunto de sumas. Para sucesiones convexas , los límites inferiores de y son conocidos . [10] Más generalmente, para una función convexa y un conjunto, el problema de estimación y algunos similares a veces se consideran como una generalización del teorema de la suma del producto, ya que y por lo tanto , y la función es convexa. [once] ${\ estilo de visualización | A + A |}$ ${\ estilo de visualización | AA |}$ $F$ $f(A):=\{f(a):a\en A\}$ ${\displaystyle \max\{|A+A|,|f(A)+f(A)|\))$ $AA=\exp \left({\log A+\log A}\right)$ $|AA|=|\log A+\log A|$ ${\ estilo de visualización \ exp}$

Sumas de varios conjuntos

La desigualdad de Plünnecke-Rouge establece que el crecimiento (aumento de tamaño con respecto a los conjuntos sumables) de sumas múltiples no supera, en promedio (en relación con ), mucho más que el crecimiento de . $|kA+lB|,\ k,l\in {\mathbb {N} }$ ${\ estilo de visualización k, l}$ ${\ estilo de visualización | A + B |}$

La desigualdad del triángulo de Rouge relaciona los tamaños de cualquier conjunto y muestra que el tamaño normalizado de la diferencia de conjuntos se puede considerar como una pseudométrica que refleja la cercanía de la estructura de estos conjuntos. [12] $AB,\BC,\CA$ $A B C$ ${\displaystyle {\frac {|AB|}{\sqrt {|A||B|))))$

Estructura

Una de las cuestiones fundamentales de la combinatoria aditiva es: qué estructura pueden o deben tener los conjuntos de sumas. A principios de 2020, no se conoce ningún algoritmo que no sea trivialmente rápido para determinar si un conjunto grande dado se puede representar como o . Sin embargo, se conocen algunos resultados parciales sobre la estructura de los conjuntos de suma. ${\ estilo de visualización A + B, \ (| A |, | B | \ geq 2)}$ $A+A,\ |A|\geq 2$

Por ejemplo, los conjuntos de sumas de números reales no pueden tener pequeñas duplicaciones multiplicativas, es decir, si , entonces para algunos . [13] Y en el grupo de residuos módulo a primo solo hay conjuntos que se pueden representar como . [14] [15] ${\ estilo de visualización A = B + C}$ ${\ estilo de visualización | AA | \ geq | A | ^ {1 + c}}$ $c>0$ $pags$ $2^{\left({{\frac {1}{2}}+o(1)}\right)p}$ $A+B,\ |A|,|B|\hasta \infty$

Se sabe que si son conjuntos densos de números naturales, entonces contiene progresiones aritméticas largas . [16] Sin embargo, se conocen ejemplos de conjuntos densos con un fuerte límite superior en la longitud de tales progresiones. [17] [18] $A,B$ $A+B$ ${\displaystyle {\mathbb {Z} }_{p))$

Véase también

Literatura

Freiman, Grigori Abelevich . Inicios de la Teoría de Conjuntos Estructurales . - Imprenta "Tatpoligraf". — 1966. (Ruso)

T. Tao , Van H. Vu. Combinatorias aditivas . - Prensa de la Universidad de Cambridge. - 2006. - ISBN 0-511-24530-0 .

I. D. Shkredov . Varios resultados nuevos sobre energías superiores // Actas de la Sociedad Matemática de Moscú. - 2013. - T. 74 , núm. 1 . - S. 35-73 . (Ruso)

Paul Erdös , Endre Szemeredi . Sobre sumas y productos de números enteros (inglés) // Estudios de Matemática Pura. - 1983. - P. 213-218 .

Jorge Shakan. Sobre descomposiciones de energía superior y el fenómeno de suma-producto // Procedimientos matemáticos de la Sociedad Filosófica de Cambridge. - 2019. - Vol. 167 , edición. 3 . - pág. 599-617 .

Ilya D. Shkredov, Dmitrii Zhelezov. Sobre bases aditivas de conjuntos con conjunto de productos pequeños . - 2016. - arXiv : matemáticas/1606.02320 .

B. Verde . Progresiones aritméticas en sumas (inglés) // Análisis geométrico y funcional GAFA. - 2002. - vol. 12 _ - pág. 584-597 .

Ernie Croot, Izabella Laba, Olof Sisask. Progresiones aritméticas en sumas y -casi-periodicidad $L^{p}$ // Combinatoria, probabilidad y computación. - 2013. - Vol. 22 , edición. 3 . - P. 351-365 .

N. Alon, A. Granville, A. Ubis. El número de sumas en un campo finito // Boletín de la London Mathematical Society. - 2010. - Vol. 42 , edición. 4 .

Imre Z Ruzsa. Progresiones aritméticas en sumas (inglés) // Acta Arithmetica. - 1991. - vol. 60 , edición. 2 . - pág. 191-202 .

J. Bourgain. Sobre progresiones aritméticas en sumas de conjuntos de números enteros // Tributo a Paul Erdos. - 1990. - P. 105-110 .

Ernie Croot, Imre Z. Ruzsa, Tomasz Schoen. Progresiones aritméticas en sumas dispersas . — 2007.

ID Shkredov, T. Schoen. Sobre sumas de conjuntos convexos // Combinatoria, Probabilidad y Computación. - 2011. - Pág. 793-798 . -arXiv : matemáticas / 1105.3542 .

G. Elekes, MB Nathanson, IZ Ruzsa. Convexity and Sumsets (inglés) // Journal of Number Theory. - 2000. - vol. 83 , edición. 2 . - pág. 194-201 .

Notas

↑ Freiman, 1966 , pág. 7-8
↑ Tao, Wu, 2006 , pág. 54, pág. 92
↑ Tao, Wu, 2006 , pág. 57
↑ Tao, Wu, 2006 , pág. 240
↑ Tao, Wu, 2006 , pág. 188; Shkrédov, 2013 , § 5
↑ Según la desigualdad de Cauchy-Bunyakovsky , , donde es el número de representaciones $(|A||B|)^{2}={\left({\sum \limits _{x\in A+B}{(A*B)(x)))\right)}^ {2}\leq |A+B|\sum \limits _{x\in A+B}{(A*B)(x)^{2}}=|A+B|E(A,B)$ ${\ estilo de visualización (A * B) (x)}$ ${\ estilo de visualización x = a + b, \ a \ en A, \ b \ en B}$
↑ Freiman, 1966 .
↑ Esta pregunta a menudo se llama el problema inverso de la combinatoria aditiva (ver, por ejemplo, Freiman, 1966 , sección 1.8, p. 19)
↑ Erdös, Szemeredi, 1983 ; Shakán, 2019
↑ Shkrédov, Schoen, 2011 .
↑ Elekes, Nathanson, Ruzsa, 2000 .
↑ Tao, Wu, 2006 , pág. 60
↑ Shkredov, Zhelezov, 2016 , consecuencia 2
↑ Alon, Granville, Ubis, 2010 .
↑ Si bien el número total de conjuntos en este grupo es obviamente $2^{p}$
↑ Bourgain demostró esto por primera vez en Bourgain, 1990 . El mejor resultado para 2020 se obtuvo en Green, 2002 , y posteriormente reprobado por un nuevo método más general en Croot, Laba, Sisask, 2013
↑ Ruzsa, 1991 .
↑ Se puede encontrar una descripción general de los resultados sobre este tema en Croot, Ruzsa , Schoen, 2007