Teorema de Cauchy-Davenport

El teorema de Cauchy-Davenport es el resultado de la combinatoria aditiva, llamada así por Augustin Cauchy y Harold Davenport , que establece que el tamaño del conjunto de sumas de dos conjuntos en un grupo de residuos nunca es sustancialmente menor que la suma de sus tamaños. ${\displaystyle {\mathbb {Z} }_{p))$

El teorema fue propuesto por Hans Heilbronn como un problema sin resolver a Harold Davenport, quien lo resolvió y publicó la prueba en 1935. [una]

Redacción

deja _ Definamos . $A,B\in {\mathbb {Z} }_{p},\ A\not =\emptyset ,\ B\not =\emptyset$ $A+B=\left\lbrace {a+b\mod p:a\in A,b\in B}\right\rbrace$

Después $|A+B|\geq \min \left({|A|+|B|-1,p}\right)$

La esencia de la no trivialidad

Para conjuntos de números enteros (o reales), una declaración similar es obvia, ya que para

A=\left\lbrace {a_{1}<\dots <a_{n}}\right\rbrace

B=\left\lbrace {b_{1}<\dots <b_{m}}\right\rbrace

números y son siempre distintos. ${\displaystyle a_{1}+b_{1},a_{2}+b_{1}\puntos,a_{n}+b_{1))$ ${\displaystyle a_{n}+b_{2},\dots,a_{n}+b_{m))$

Una prueba similar no funciona en el anillo de los residuos, donde los números naturales "bucle". Para un anillo con una declaración compuesta , la declaración simplemente no es verdadera, ya que hay subgrupos (progresiones aritméticas con una diferencia que divide ) para los cuales (esto es generalmente, por definición, siempre cierto para los subgrupos). ${\displaystyle {\mathbb {Z} }_{m))$ $metro$ $GRAMO$ $metro$ ${\ estilo de visualización G + G = G}$

El caso de un módulo simple es interesante porque actúa como un intermediario entre estos dos. Si el teorema resulta ser incorrecto, esto significaría que la construcción del anillo de residuos en sí, incluso sin subgrupos, contiene alguna estructura cercana a una progresión aritmética . Pero el teorema es cierto.

Métodos de prueba

Caso extremo

Si , entonces el enunciado se demuestra elementalmente, ya que para cualquier conjunto e se intersecan simplemente por su tamaño, según el principio de Dirichlet . $\min \left({|A|+|B|-1,p}\right)=p$ ${\displaystyle A+B={\mathbb {Z} }_{p))$ $X$ $A$ $\left\lbrace {xb:b\in B}\right\rbrace$

Por lo tanto, la principal dificultad radica en demostrar cuándo . ${\ estilo de visualización | A + B | \ geq | A | + | B | -1}$ $|A|+|B|\leq p$

Prueba combinatoria

La prueba combinatoria utiliza el hecho obvio de que . Si , entonces esto nos permite aplicar la inducción sobre el tamaño del menor de estos dos conjuntos. De lo contrario, dos situaciones son posibles: $(A\cap B)+(A\cup B)\subset A+B$ $0<|A\cap B|<\min \left\lbrace {|A|,|B|}\right\rbrace$

$A$ y no se cruzan $B$

uno de los conjuntos está completamente contenido en el otro

La primera situación se puede eliminar desplazando los elementos de uno de los conjuntos, ya que . Si todos esos desplazamientos se encuentran completamente en el conjunto (sin pérdida de generalidad, suponemos que ), entonces es fácil demostrar que para cualquier , es decir, es una progresión aritmética infinita en bucle con diferencia . En vista de las peculiaridades del grupo de residuos módulo a primo, esto significa que , y esto lleva al caso más simple . [2] $\forall s:|(A+s)+B|=|(A+B)+s|=|A+B|$ $B$ ${\ estilo de visualización | A | \ leq | B |}$ $b\in B\Rightarrow b+(a_{2}-a_{1})\in B$ $a_{1},a_{2}\en A$ $B$ $a_{2}-a_{1}$ ${\displaystyle B={\mathbb {Z} }_{p))$ ${\ estilo de visualización | A | + | B |> p}$

Demostración algebraica

Una demostración algebraica fue presentada en 2004 por Terence Tao. [3] . Su base es el teorema nulo combinatorio . Si , donde , entonces el polinomio tiene un coeficiente distinto de cero en . De esto, según el teorema del cero combinatorio, se sigue que para algunos el polinomio no se anula, y esto, obviamente, no es así, por definición . [2] $|A+B|=(|A|-1)+(|B'|-1)<|A|+|B|-1$ $B'\subconjunto B$ ${\displaystyle P(x,y)=\prod \limits _{c\in C}{(x+yc)))$ ${\displaystyle x^{|A|-1}y^{|B'|-1))$ ${\ estilo de visualización x \ en A, y \ en B' \ subconjunto B}$ $P(x, y)$ $A+B$

Prueba analítica

La demostración mediante análisis armónico utiliza el principio de incertidumbre y convolución de funciones sobre . Las funciones bajo consideración son tales que ${\displaystyle {\mathbb {Z} }_{p))$ $f, g$

{\begin{matrix}{\rm {soporte}}(f)=A\\{\rm {soporte}}({\widehat {f}})={\tilde {A}}\\{ \rm {suplemento}}(g)=B\\{\rm {suplemento}}({\widehat {g}})={\tilde {B}}\\\end{matriz}}

donde y , y la intersección es tan pequeña como puede ser con tales dimensiones. Usando las propiedades de la convolución, en este caso tenemos: $|{\tilde {A}}|=p+1-|A|$ $|{\tilde {B}}|=p+1-|B|$ ${\tilde {A}}\cap {\tilde {B}}$

{\rm {supp}}({\widehat {f*g}})={\rm {supp}}({\widehat {f}}\cdot {\widehat {g}})={\ rm {supp}}({\widehat {f}})\cap {\rm {supp}}({\widehat {g}})=|{\tilde {A}}|+|{\tilde {B} }|-p

{\rm {soporte}}(f*g)\subset {\rm {soporte}}(f)+{\rm {soporte}}(g)=A+B

Dado que, de acuerdo con el principio de incertidumbre , entonces de esto, con la elección correcta , se sigue directamente el teorema de Cauchy-Davenport. [cuatro] $|{\rm {soporte}}(f*g)|+|{\rm {soporte}}({\widehat {f*g}})|\geq p+1$ ${\ tilde {A}}$ ${\ tilde {B}}$

Variaciones y generalizaciones

Dado que en todas partes a continuación hablaremos de subconjuntos de un campo finito, entonces en cualquier estimación del tamaño del conjunto de sumas, se debe hacer una corrección por el hecho de que si los conjuntos de los que se toman los términos son de tamaño muy grande, entonces la suma ocupa todo el campo. Por lo tanto, por conveniencia de presentación, en todas partes debajo de la notación para cualquier conjunto de sumas (por ejemplo, ) significa que ${\ estilo de visualización | Q | \ geq n}$ $q$ ${\ estilo de visualización Q = A + B}$ $|Q|\geq \min \left\lbrace {p,n}\right\rbrace$

Prohibición de adición de elementos iguales

En 1964, Erdős y Heilbronn conjeturaron que esto es cierto para un conjunto [5] . Esto fue probado en 1994 por Diaz da Silva y Hamidaon utilizando la teoría de la representación de grupos simétricos ( sección especial de la teoría de la representación). Probaron un resultado aún más general [6] , a saber: $A\oplus A=\left\lbrace {a+b:a,b\in A,a\not =b}\right\rbrace$ $|A\oplus A|\geq 2|A|-3$

{\Bigg \lbrace}\sum \limits _{a\in A'}a\ :\A'\subset A,|A'|=m}{\Bigg \rbrace}\geq m|A |-m^{2}+1

Además , esta afirmación coincide exactamente con la conjetura de Erdős y Heilbronn. $metro=2$

Esta estimación resultó no ser la mejor: en 1996, Alon, Natanzon y Rouja lo demostraron . ${\Bigg \lbrace}\sum \limits _{a\in A'}a\ :\A'\subset A,|A'|=m}{\Bigg \rbrace}\geq m|A |-{\binom {m+1}{2}}+1$

La pregunta surgió naturalmente: ¿es posible decir algo similar sobre . Esta pregunta se puede resolver modificando la prueba algebraica del teorema principal de Cauchy-Davenport, si al polinomio en consideración le sumamos un factor, es decir, considera , donde . [2] $A\oplus B=\left\lbrace {a+b:a\in A,b\in B,a\not =b}\right\rbrace$ ${\displaystyle P(x,y)=(xy)\prod \limits_{c\in C}{(x+yc)))$ $A+B\subconjunto C$

Prohibición de elementos con diferencias dadas

En 2009, se publicó una modificación de la prueba analítica, que permite mostrar que para un conjunto finito arbitrario , la desigualdad ${\displaystyle S\subconjunto {\mathbb {Z} }_{p))$

$|A{+}_{S}B|=\#\left\lbrace {a+b:a\in A,b\in B,ab\not \in S}\right\rbrace \leq | A|+|B|-2|S|-1$

Breve descripción de la idea de prueba.

Como se mencionó anteriormente, la prueba analítica utiliza el hecho de que . En consecuencia, para una forma más complicada del problema, es necesario modificar la operación de convolución para que . Sin embargo, la prueba original hizo un uso significativo del hecho de que , por lo que es importante asegurarse de que también obedezca algunas leyes generales. ${\rm {soporte}}(A*B)\subconjunto A+B$ $\circ$ ${\rm {soporte}}(A\circ B)\subconjunto A{+}_{S}B$ ${\sombrero ancho {f*g}}={\sombrero ancho {f}}\cdot {\sombrero ancho {g}}$ ${\widehat {f\circ g))$

Una forma obvia de construir una convolución modificada para la cual se realiza es restringir la convolución normal. Una construcción aproximada da la siguiente fórmula: ${\rm {soporte}}(A\circ B)\subconjunto A{+}_{S}B$

(f\circ g)(x)=\sum \limits _{a+b=x}{f(a)g(b)\prod \limits _{d\in S}{[ab=d ]}}

(los corchetes se utilizan en el sentido de la notación de Iverson ), pero este enfoque no permite ampliar el trabajo y trabajar con él de forma analítica. Por lo tanto, es apropiado introducir una función (arbitraria para empezar) y considerar la siguiente operación: ${\ estilo de visualización d \ en S}$ $\lambda :{\mathbb {Z} _{p}}\to {\mathbb {C} }$

{\displaystyle (f\circ g)(x)=\sum \limits _{a+b=x}{f(a)g(b)\prod \limits _{d\in S}{{\Big ( }{\lambda (ab)-\lambda (d)}{\Grande)))))

Obviamente, si , entonces el producto con respecto a desaparece, de modo que . $ab\in S$ ${\ estilo de visualización d \ en S}$ ${\rm {soporte}}(f\circ g)\subconjunto A{+}_{S}B$

El siguiente paso es seleccionar una característica específica . Por conveniencia de analizar los coeficientes de Fourier, es conveniente asociar funciones con raíces a partir de la unidad (ya que la idea de los coeficientes de Fourier se basa en las propiedades de las raíces a partir de la unidad). Por ejemplo, $\lambda$ $f \circ g$ $\lambda$

{\displaystyle (f\circ g)(x)=\sum \limits _{a+b=x}{f(a)g(b)\prod \limits _{d\in S}{{\Big ( {e_{p}(ab)-e_{p}(d)}{\Big )}}}=\sum \limits _{t}{f(a)g(b)\prod \limits _{d \in S}{{\Grande (}{e_{p}(t-(xt))-e_{p}(d)}{\Grande)))))

donde está la raíz de la unidad. Sin embargo, una consideración explícita del coeficiente de Fourier de tal función no da el resultado deseado. Para obtener una fórmula conveniente para usar, los grados de la raíz de la unidad y deben transformarse mediante la misma transformación lineal, obteniendo, respectivamente , y y considere la operación $e_{p}(k)=e^{2\pi {\frac {k}{p}}i}$ $t-(xt)=2t-x$ $d$ ${\ estilo de visualización xt}$ ${\ estilo de visualización td}$

{\displaystyle (f\circ g)(x)=\sum \limits _{t}{f(a)g(b)\prod \limits _{d\in S}{{\Big (}{e_{ p}(xt)-e_{p}(td)}{\Grande)))))

Entonces, de la permutación de los términos en la expresión explícita , podemos deducir que ${\widehat {f\circ g))$

{\displaystyle {\widehat {f\circ g}}(x)=\sum \limits _{k=0}^{|S|}{c(k){\widehat {f}}(x+k) {\ sombrero ancho {g}}(x+|S|-k)))

donde son coeficientes que dependen sólo de . ${\ estilo de visualización c (k)}$ $S$

A continuación, se eligen los conjuntos , de forma similar a la prueba analítica del teorema principal. Pero ahora se eligen necesariamente para que sus elementos estén en una fila; esto le permite controlar y obtener la estimación deseada, actuando de la misma manera que en la prueba principal. ${\ estilo de visualización {\ tilde {A)], {\ tilde {B))}$ ${\widehat {A\circ B}}(x)$

Esta estimación no es exacta: anteriormente, en 2002, Pan y Sun demostraron, utilizando métodos algebraicos, una de las afirmaciones más sólidas de que . [7] $|A{+}_{S}B|\geq |A|+|B|-|S|-2$

También en su trabajo, Pan y Sun conjeturaron que el sustraendo 2 puede ser reemplazado por 1 si es par. Los autores de un artículo de 2009 (generalizando el método analítico) sugirieron que incluso la condición es suficiente para esto . [ocho] ${\ estilo de visualización | S |}$ ${\ estilo de visualización A \ no = B}$

Restricciones de polinomios en los términos

Una fuerte generalización del problema de Cauchy-Davenport consiste en derivar un método general para estimar en términos de dimensiones y tamaño de un conjunto de la forma $A$ $B$

\oplus _{P}\sum \limits _{k=1}^{n}{A_{k}}=\left\lbrace {a_{1}+\dots +a_{n}:a_{ i}\in A_{i},P(a_{1},\dots ,a_{n})\not =0}\right\rbrace

donde es algún polinomio . Por ejemplo, en el caso, tal problema se reduce a la conjetura de Erdős-Helbronn. El estuche representa su análogo para varios juegos. $PAGS$ ${\ estilo de visualización P (x, y) = xy}$ ${\displaystyle p(x_{1},\dots,x_{n})=\prod \limits _{1\leq i<j\leq n}{(x_{i}-x_{j)))))$

En 2002, Pan y Sun consideraron esta pregunta para polinomios en dos variables y probaron el siguiente resultado [7] : $P(x, y)$

Sea un polinomio homogéneo de grado sobre un campo arbitrario de característica , y exista para el cual sus coeficientes en y no sean iguales a cero. Considere el polinomio y su desarrollo . Denotemos . Sea también dado cualquier polinomio de grado . Después $P(x, y)$ $d$ $pags$ $i\en [0;|A|),\j\en [0;|B|)$ ${\ Displaystyle x^{i}y^{di))$ ${\ estilo de visualización x^{dj}y^{j))$ $P_{*}(x)=P(x,1)$ $P_{*}(x)=(x+1)^{s}(x+\alpha _{1})^{t_{1}}\dots (x+\alpha _{k})^{t_ {k}}$ $N(P_{*})=\max \limits _{k\geq 0}\left\lbrace {p^{k}\cdot \#\left\lbrace {i:t_{i}\geq p ^{k}}\right\rbrace}\right\rbrace$ $R(x, y)$ ${\rm {grados}}R<d$

{\Bigg \vert}\oplus _{P+R}\sum \limits _{k=1}^{n}{A_{k))}{\Bigg \vert}\geq \min \ izquierda\lbrace {ps,\ |A|+|B|-1-dN(P_{*})}\right\rbrace

Reemplazando la sumatoria con un polinomio

En 2008, Sun obtuvo el siguiente resultado [9] :

Sea un polinomio tal que . $f(x_{1},\puntos,x_{n})=a_{1}{x_{1}}^{k}+\puntos +a_{n}{x_{n}}^{k }+g(x_{1},\puntos,x_{n})$ ${\rm {grados}}\ g<k$

Después $\#\left\lbrace {f(x_{1},\dots,x_{n}):x_{1}\en A_{1},\dots,x_{n}\en A_{n} }\right\rbrace \geq \sum \limits _{i=1}^{n}{\left\lfloor {\frac {|A_{i}|-1}{k))\right\rfloor }+1$

Si , entonces se cumple una desigualdad similar incluso si el conjunto de condiciones para . ${\ Displaystyle k\ geq n}$ $(x_{1},\puntos,x_{n})$ ${\displaystyle x_{i}\no =x_{j))$ $yo\no =j$