Desigualdad de Plünnecke-Ruzsa

En combinatoria aditiva , la desigualdad de Plünnecke-Ruzsa es una desigualdad que limita el tamaño de varios conjuntos suma de un conjunto. $B$ , dado que hay otro conjunto $A$ de modo que $A+B$ no es mucho más grande que $A$ Una versión ligeramente más débil de esta desigualdad fue demostrada y publicada originalmente por Helmut Plünnecke (1970). ^{[ 1 ]} Imre Ruzsa (1989) ^{[ 2 ]} publicó posteriormente una demostración más sencilla de la versión actual, más general, de la desigualdad. La desigualdad constituye un paso crucial en la demostración del teorema de Freiman .

Declaración

La siguiente notación de conjunto suma es estándar en combinatoria aditiva. Para subconjuntos $A$ y $B$ de un grupo abeliano y un número natural $k$ Se definen los siguientes términos:

$A+B=\{a+b:a\in A,b\in B\}$
$AB=\{ab:a\in A,b\in B\}$
$kA=\underbrace {A+A+\cdots +A} _{k{\text{ veces}}}$

El conjunto $A+B$ se conoce como el conjunto suma de $A$ y $B$ .

Desigualdad de Plünnecke-Ruzsa

La versión más comúnmente citada del enunciado de la desigualdad de Plünnecke-Ruzsa es la siguiente. ^{[ 3 ]}

Teorema (desigualdad de Plünnecke-Ruzsa) — Si $A$ y $B$ son subconjuntos finitos de un grupo abeliano y $K$ es una constante de modo que $|A+B|\leq K|A|$ , entonces para todos los enteros no negativos $m$ y $n$ ,

|mB-nB|\leq K^{m+n}|A|.

Esto se usa a menudo cuando $A=B$ , en cuyo caso la constante $K=|2A|/|A|$ se conoce como la constante de duplicación de $A$ En este caso, la desigualdad de Plünnecke-Ruzsa establece que los conjuntos suma formados a partir de un conjunto con una constante de duplicación pequeña también deben ser pequeños.

La desigualdad de Plünnecke

La versión de esta desigualdad que fue demostrada originalmente por Plünnecke (1970) ^{[ 1 ]} es ligeramente más débil.

Teorema (desigualdad de Plünnecke) — Supongamos que $A$ y $B$ son subconjuntos finitos de un grupo abeliano y $K$ es una constante de modo que $|A+B|\leq K|A|$ Entonces, para todo entero no negativo $m$ , $|mB|\leq K^{m}|A|.$

Prueba

Desigualdad del triángulo de Ruzsa

La desigualdad triangular de Ruzsa es una herramienta importante que se utiliza para generalizar la desigualdad de Plünnecke a la desigualdad de Plünnecke-Ruzsa. Su enunciado es:

Teorema (desigualdad del triángulo de Ruzsa) — Si $A$ , $B$ , y $C$ son subconjuntos finitos de un grupo, entonces

|A||BC|\leq |AB||AC|.

Demostración de la desigualdad de Plünnecke-Ruzsa

La siguiente demostración sencilla de la desigualdad de Plünnecke-Ruzsa se debe a Petridis (2014). ^{[ 4 ]}

Lema: Sea $A$ y $B$ sean subconjuntos finitos de un grupo abeliano $G$ . Si $X\subsetequ A$ es un subconjunto no vacío que minimiza el valor de $K'=|X+B|/|X|$ , entonces para todos los subconjuntos finitos $C\subset G$ ,

|X+B+C|\leq K'|X+C|.

Prueba: Esto se demuestra por inducción sobre el tamaño de $|C|$ . Para el caso base de $|C|=1$ , tenga en cuenta que $S+C$ es simplemente una traducción de $S$ para cualquier $S\subseteg G$ , entonces

|X+B+C|=|X+B|=K'|X|=K'|X+C|.

Para el paso inductivo, supongamos que la desigualdad se cumple para todos $C\subseteg G$ con $|C|\leq n$ para algún entero positivo $n$ . Dejar $C$ ser un subconjunto de $G$ con $|C|=n+1$ y dejar $C=C'\sqcup \{\gamma \}$ para algunos $\gamma \in C$ . (En particular, la desigualdad se cumple para $C'$ .) Finalmente, dejemos $Z=\{x\in X:x+B+\{\gamma \}\subseteq X+B+C'\}$ . La definición de $Z$ implica que $Z+B+\{\gamma \}\subseteq X+B+C'$ . Por lo tanto, según la definición de estos conjuntos,

X+B+C=(X+B+C')\cup ((X+B+\{\gamma \})\backslash (Z+B+\{\gamma \})).

Por lo tanto, considerando los tamaños de los conjuntos,

{\begin{aligned}|X+B+C|&\leq |X+B+C'|+|(X+B+\{\gamma \})\backslash (Z+B+\{\gamma \})|\\&=|X+B+C'|+|X+B+\{\gamma \}|-|Z+B+\{\gamma \}|\\&=|X+B+C'|+|X+B|-|Z+B|.\end{aligned}}

La definición de $Z$ implica que $Z\subseteq X\subseteq A$ , por lo tanto, por definición de $X$ , $|Z+B|\geq K'|Z|$ . Por lo tanto, aplicando la hipótesis inductiva sobre $C'$ y utilizando la definición de $X$ ,

{\begin{aligned}|X+B+C|&\leq |X+B+C'|+|X+B|-|Z+B|\\&\leq K'|X+C'|+|X+B|-|Z+B|\\&\leq K'|X+C'|+K'|X|-|Z+B|\\&\leq K'|X+C'|+K'|X|-K'|Z|\\&=K'(|X+C'|+|X|-|Z|).\end{aligned}}

Para acotar el lado derecho de esta desigualdad, sea $W=\{x\in X:x+\gamma \in X+C'\}$ . Suponer $y\in X+C'$ y $y\in X+\{\gamma \}$ , entonces existe $x\in X$ de tal manera que $x+\gamma =y\in X+C'$ . Por lo tanto, por definición, $x\in W$ , entonces $y\in W+\{\gamma \}$ Por lo tanto, los conjuntos $X+C'$ y $(X+\{\gamma \})\backslash (W+\{\gamma \})$ son disjuntos. Las definiciones de $W$ y $C'$ por lo tanto implican que

X+C=(X+C')\sqcup ((X+\{\gamma \})\backslash (W+\{\gamma \})).

Nuevamente por definición, $W\subseteq Z$ , entonces $|W|\leq |Z|$ . Por eso,

{\begin{aligned}|X+C|&=|X+C'|+|(X+\{\gamma \})\backslash (W+\{\gamma \})|\\&=|X+C'|+|X+\{\gamma \}|-|W+\{\gamma \}|\\&=|X+C'|+|X|-|W|\\&\geq |X+C'|+|X|-|Z|.\end{aligned}}

Al juntar las dos desigualdades anteriores se obtiene

|X+B+C|\leq K'(|X+C'|+|X|-|Z|)\leq K'|X+C|.

Con esto concluye la demostración del lema.

Para demostrar la desigualdad de Plünnecke-Ruzsa, tomemos $X$ y $K'$ como en el enunciado del lema. Primero es necesario demostrar que

|X+nB|\leq K^{n}|X|.

Esto se puede demostrar por inducción. Para el caso base, las definiciones de $K$ y $K'$ implican que $K'\leq K$ . Por lo tanto, la definición de $X$ implica que $|X+B|\leq K|X|$ . Para el paso inductivo, supongamos que esto es cierto para $n=j$ . Aplicando el lema con $C=jB$ y la hipótesis inductiva da

|X+(j+1)B|\leq K'|X+jB|\leq K|X+jB|\leq K^{j+1}|X|.

Esto completa la inducción. Finalmente, la desigualdad triangular de Ruzsa da como resultado

|mB-nB|\leq {\frac {|X+mB||X+nB|}{|X|}}\leq {\frac {K^{m}|X|K^{n}|X|}{|X|}}=K^{m+n}|X|.

Porque $X\subseteq A$ , debe ser el caso que $|X|\leq |A|$ . Por lo tanto,

|mB-nB|\leq K^{m+n}|A|.

Con esto concluye la demostración de la desigualdad de Plünnecke-Ruzsa.

Gráficos de Plünnecke

Tanto la demostración de Plünnecke de la desigualdad de Plünnecke como la demostración original de Ruzsa de la desigualdad de Plünnecke-Ruzsa utilizan el método de los grafos de Plünnecke. Los grafos de Plünnecke son una forma de capturar la estructura aditiva de los conjuntos. $A,A+B,A+2B,\dots$ de una manera teórica de grafos ^{[ 5 ]}^{[ 6 ]}

Para definir un grafo de Plünnecke, primero definimos los grafos conmutativos y los grafos en capas:

Definición . Un grafo dirigido $G$ Se denomina semicommutativo si, siempre que existan distintos $x,y,z_{1},z_{2},\dots ,z_{k}$ de tal manera que $(x,y)$ y $(y,z_{i})$ son bordes en $G$ para cada $i$ , entonces también existen distintos $y_{1},y_{2},\dots ,y_{k}$ de modo que $(x,y_{i})$ y $(y_{i},z_{i})$ son bordes en $G$ para cada $i$ .

$G$ Se dice que un grafo es conmutativo si es semiconmutativo y el grafo formado al invertir todas sus aristas también es semiconmutativo.

Definición . Un grafo en capas es un grafo (dirigido). $G$ cuyo conjunto de vértices puede ser particionado $V_{0}\cup V_{1}\cup \dots \cup V_{m}$ para que todos los bordes en $G$ son de $V_{i}$ a $V_{i+1}$ , para algunos $i$ .

Definición . Un grafo de Plünnecke es un grafo en capas que es conmutativo.

El ejemplo canónico de un grafo de Plünnecke es el siguiente, que muestra cómo la estructura de los conjuntos $A,A+B,A+2B,\dots ,A+mB$ formar un gráfico de Plünnecke.

Ejemplo . Dejemos $A,B$ sean subconjuntos de un grupo abeliano. Entonces, sea $G$ sea el gráfico en capas de modo que cada capa $V_{j}$ es una copia de $A+jB$ , de modo que $V_{0}=A$ , $V_{1}=A+B$ , ..., $V_{m}=A+mB$ . Crea el borde $(x,y)$ (dónde $x\in V_{i}$ y $y\in V_{i+1}$ ) siempre que exista $b\in B$ de tal manera que $y=x+b$ . (En particular, si $x\in V_{i}$ , entonces $x+b\in V_{i+1}$ por definición, por lo que cada vértice tiene un grado de salida igual al tamaño de $B$ .) Entonces $G$ es un gráfico de Plünnecke. Por ejemplo, para comprobar que $G$ es semiconmutativo, si $(x,y)$ y $(y,z_{i})$ son bordes en $G$ para cada $i$ , entonces $y-x,z_{i}-y\in B$ . Entonces, deja $y_{i}=x+z_{i}-y$ , de modo que $y_{i}-x=z_{i}-y\in B$ y $z_{i}-y_{i}=y-x\in B$ . De este modo, $G$ es semiconmutativo. De manera similar, se puede comprobar que el grafo formado al invertir todas las aristas de $G$ también es semiconmutativo, por lo tanto $G$ es un gráfico de Plünnecke.

En un gráfico de Plünnecke, la imagen de un conjunto $X\subseteq V_{0}$ en $V_{j}$ , escrito ${\text{im}}(X,V_{j})$ , se define como el conjunto de vértices en $V_{j}$ que se puede alcanzar mediante un camino que comienza en algún vértice en $X$ . En particular, en el ejemplo mencionado anteriormente, ${\text{im}}(X,V_{j})$ es solo $X+jB$ .

La relación de magnificación entre $V_{0}$ y $V_{j}$ , denotado $\mu _{j}(G)$ , se define entonces como el factor mínimo por el cual la imagen de un conjunto debe exceder el tamaño del conjunto original. Formalmente,

\mu _{j}(G)=\min _{X\subseteq V_{0},X\neq \emptyset }{\frac {|{\text{im}}(X,V_{j})|}{|X|}}.

El teorema de Plünnecke es la siguiente afirmación sobre los gráficos de Plünnecke.

Teorema (Teorema de Plünnecke) — Sea $G$ sea un gráfico de Plünnecke. Entonces, $\mu _{j}(G)^{1/j}$ está disminuyendo en $j$ .

La demostración del teorema de Plünnecke implica una técnica conocida como el "truco del producto tensorial", además de una aplicación del teorema de Menger . ^{[ 5 ]}

La desigualdad de Plünnecke-Ruzsa es una consecuencia bastante directa del teorema de Plünnecke y la desigualdad triangular de Ruzsa. Aplicando el teorema de Plünnecke al gráfico dado en el ejemplo, en $j=m$ y $j=1$ , resulta que si $|A+B|/|A|=K$ , entonces existe $X\subseteq A$ de modo que $|X+mB|/|X|\leq K^{m}$ . Aplicando este resultado una vez más con $X$ en lugar de $A$ , existe $X'\subseteq X$ de modo que $|X'+nB|/|X'|\leq K^{n}$ . Luego, por la desigualdad triangular de Ruzsa (en $-X',mB,nB$ ),

|mB-nB|\leq |X'+mB||X'+nB|/|X'|\leq K^{m}|X|K^{n}=K^{m+n}|X|,

demostrando así la desigualdad de Plünnecke-Ruzsa.

Véase también

Referencias

^ Plünnecke , Helmut (1970). "Eine zahlentheoretische Anwendung der Graphtheorie". Journal für die reine und angewandte Mathematik . 243 : 171– 183. doi : 10.1515/crll.1970.243.171 .
↑ Ruzsa, Imre (1989). "Una aplicación de la teoría de grafos a la teoría aditiva de números". Scientia, Serie A. 3 : 97–109 .
↑ Candela, Pablo; González-Sánchez, Diego; de Roton, Anne (2019). "Una desigualdad de Plünnecke-Ruzsa en grupos abelianos compactos". Revista Matemática Iberoamericana . 35 (7): 2169–2186 . arXiv : 1712.07615 . doi : 10.4171/rmi/1116 .
↑ Petridis, Giorgis (2014). «La desigualdad de Plünnecke-Ruzsa: una visión general». Teoría combinatoria y aditiva de números . Springer Proceedings in Mathematics & Statistics. Vol. 101. pp. 229–241 . doi : 10.1007/978-1-4939-1601-6_16 . ISBN 978-1-4939-1600-9.
1 2 Tao, T.; Vu, V. (2006). Combinatoria aditiva . Cambridge: Cambridge University Press. ISBN 978-0-521-85386-6.
↑ Ruzsa, I., Sumsets y estructura (PDF).

[Plu-1] Plünnecke , Helmut (1970). "Eine zahlentheoretische Anwendung der Graphtheorie". Journal für die reine und angewandte Mathematik . 243 : 171– 183. doi : 10.1515/crll.1970.243.171 .

[2] Ruzsa, Imre (1989). "Una aplicación de la teoría de grafos a la teoría aditiva de números". Scientia, Serie A. 3 : 97–109 .

[3] Candela, Pablo; González-Sánchez, Diego; de Roton, Anne (2019). "Una desigualdad de Plünnecke-Ruzsa en grupos abelianos compactos". Revista Matemática Iberoamericana . 35 (7): 2169–2186 . arXiv : 1712.07615 . doi : 10.4171/rmi/1116 .

[4] Petridis, Giorgis (2014). «La desigualdad de Plünnecke-Ruzsa: una visión general». Teoría combinatoria y aditiva de números . Springer Proceedings in Mathematics & Statistics. Vol. 101. pp. 229–241 . doi : 10.1007/978-1-4939-1601-6_16 . ISBN 978-1-4939-1600-9.

[TaoVu-5] 1 2 Tao, T.; Vu, V. (2006). Combinatoria aditiva . Cambridge: Cambridge University Press. ISBN 978-0-521-85386-6.

[6] Ruzsa, I., Sumsets y estructura (PDF).

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]