Conjetura de Erdős-Turán sobre bases aditivas

Problema no resuelto en teoría de números

La conjetura de Erdős-Turán es un antiguo problema sin resolver en la teoría de números aditivos (que no debe confundirse con la conjetura de Erdős sobre progresiones aritméticas ) planteada por Paul Erdős y Pál Turán en 1941.

Se trata de bases aditivas , subconjuntos de los números naturales con la propiedad de que todo número natural puede representarse como la suma de un número acotado de elementos de la base. A grandes rasgos, establece que el número de representaciones de este tipo tampoco puede ser acotado.

Antecedentes y formulación

La cuestión se refiere a subconjuntos de los números naturales , normalmente denotados por , llamados bases aditivas . Un subconjunto se llama base aditiva (asintótica) de orden finito si hay algún entero positivo tal que cada número natural suficientemente grande puede escribirse como la suma de, como máximo, elementos de . Por ejemplo, los números naturales son en sí mismos una base aditiva de orden 1, ya que cada número natural es trivialmente una suma de, como máximo, un número natural. El teorema de los cuatro cuadrados de Lagrange dice que el conjunto de números cuadrados positivos es una base aditiva de orden 4. Otro resultado altamente no trivial y celebrado en esta línea es el teorema de Vinogradov . ${\displaystyle \mathbb {N} }$ ${\displaystyle B}$ ${\displaystyle h}$ ${\displaystyle n}$ ${\displaystyle h}$ ${\displaystyle B}$

Naturalmente, uno se inclina a preguntar si estos resultados son óptimos. Resulta que el teorema de los cuatro cuadrados de Lagrange no se puede mejorar, ya que hay infinitos números enteros positivos que no son la suma de tres cuadrados. Esto se debe a que ningún número entero positivo que sea la suma de tres cuadrados puede dejar un resto de 7 cuando se divide por 8. Sin embargo, tal vez se debería esperar que un conjunto que sea aproximadamente tan disperso como los cuadrados (lo que significa que en un intervalo dado , aproximadamente de los números enteros en se encuentran en ) que no tenga este déficit obvio debería tener la propiedad de que cada número entero positivo suficientemente grande es la suma de tres elementos de . Esto se desprende del siguiente modelo probabilístico: supongamos que es un número entero positivo y se seleccionan "al azar" de . Entonces, la probabilidad de que se elija un elemento dado de es aproximadamente . Entonces se puede estimar el valor esperado, que en este caso será bastante grande. Por lo tanto, 'esperamos' que haya muchas representaciones de como suma de tres elementos de , a menos que haya alguna obstrucción aritmética (lo que significa que de alguna manera es bastante diferente de un conjunto 'típico' de la misma densidad), como con los cuadrados. Por lo tanto, uno debería esperar que los cuadrados sean bastante ineficientes para representar números enteros positivos como la suma de cuatro elementos, ya que ya debería haber muchas representaciones como sumas de tres elementos para aquellos números enteros positivos que pasaron la obstrucción aritmética. Examinar el teorema de Vinogradov revela rápidamente que los primos también son muy ineficientes para representar números enteros positivos como la suma de cuatro primos, por ejemplo. ${\displaystyle B}$ ${\displaystyle [1,N]}$ ${\displaystyle N^{1/2}}$ ${\displaystyle [1,N]}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle N/2<n\leq N}$ ${\displaystyle x_{1},x_{2},x_{3}}$ ${\displaystyle B\cap [1,N]}$ ${\displaystyle B}$ ${\displaystyle 1/N^{1/2}}$ ${\displaystyle n}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle n}$

Esto genera la pregunta: supongamos que , a diferencia de los cuadrados o los números primos, es muy eficiente para representar números enteros positivos como una suma de elementos de . ¿Qué tan eficiente puede ser? La mejor posibilidad es que podamos encontrar un número entero positivo y un conjunto tal que cada número entero positivo sea la suma de como máximo elementos de exactamente de una manera. En su defecto, tal vez podamos encontrar un tal que cada número entero positivo sea la suma de como máximo elementos de al menos una manera y como máximo maneras, donde es una función de . ${\displaystyle B}$ ${\displaystyle h}$ ${\displaystyle B}$ ${\displaystyle h}$ ${\displaystyle B}$ ${\displaystyle n}$ ${\displaystyle h}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle n}$ ${\displaystyle h}$ ${\displaystyle B}$ ${\displaystyle S(h)}$ ${\displaystyle S}$ ${\displaystyle h}$

Ésta es básicamente la pregunta que Paul Erdős y Pál Turán se hicieron en 1941. De hecho, conjeturaron una respuesta negativa a esta pregunta, a saber, que si es una base aditiva de orden de los números naturales, entonces no puede representar números enteros positivos como una suma de a lo sumo con demasiada eficiencia; el número de representaciones de , como función de , debe tender a infinito. ${\displaystyle B}$ ${\displaystyle h}$ ${\displaystyle h}$ ${\displaystyle n}$ ${\displaystyle n}$

Historia

La conjetura fue formulada conjuntamente por Paul Erdős y Pál Turán en 1941. ^[1] En el artículo original, escriben

"(2) Si para , entonces ", ${\displaystyle f(n)>0}$ ${\displaystyle n>n_{0}}$ ${\displaystyle \varlimsup _{n\rightarrow \infty }f(n)=\infty }$

donde denota el límite superior de . Aquí está el número de formas en que se puede escribir el número natural como la suma de dos elementos (no necesariamente distintos) de . Si siempre es positivo para suficientemente grande , entonces se llama base aditiva (de orden 2). ^[2] Este problema ha atraído mucha atención ^[2] pero sigue sin resolverse. ${\displaystyle \varlimsup _{n\rightarrow \infty }}$ ${\displaystyle f(n)}$ ${\displaystyle n}$ ${\displaystyle B}$ ${\displaystyle f(n)}$ ${\displaystyle n}$ ${\displaystyle B}$

En 1964, Erdős publicó una versión multiplicativa de esta conjetura. ^[3]

Progreso

Aunque la conjetura sigue sin resolverse, se han producido algunos avances en el problema. Primero, expresamos el problema en lenguaje moderno. Para un subconjunto dado , definimos su función de representación . Luego, la conjetura establece que si para todos los suficientemente grandes, entonces . ${\displaystyle B\subset \mathbb {N} }$ ${\displaystyle r_{B}(n)=\#\{(a_{1},a_{2})\in B^{2}\mid a_{1}+a_{2}=n\}}$ ${\displaystyle r_{B}(n)>0}$ ${\displaystyle n}$ ${\displaystyle \limsup _{n\rightarrow \infty }r_{B}(n)=\infty }$

De manera más general, para cualquier subconjunto y , podemos definir la función de representación como . Decimos que es una base aditiva de orden si para todos los suficientemente grandes. Se puede ver a partir de un argumento elemental que si es una base aditiva de orden , entonces ${\displaystyle h\in \mathbb {N} }$ ${\displaystyle B\subset \mathbb {N} }$ ${\displaystyle h}$ ${\displaystyle r_{B,h}(n)=\#\{(a_{1},\cdots ,a_{h})\in B^{h}\mid a_{1}+\cdots +a_{h}=n\}}$ ${\displaystyle B}$ ${\displaystyle h}$ ${\displaystyle r_{B,h}(n)>0}$ ${\displaystyle n}$ ${\displaystyle B}$ ${\displaystyle h}$

${\displaystyle \displaystyle n\leq \sum _{m=1}^{n}r_{B,h}(m)\leq |B\cap [1,n]|^{h}}$

Así obtenemos el límite inferior . ${\displaystyle n^{1/h}\leq |B\cap [1,n]|}$

La conjetura original surgió cuando Erdős y Turán buscaron una respuesta parcial al problema de Sidon (ver: secuencia de Sidon ). Más tarde, Erdős se propuso responder la siguiente pregunta planteada por Sidon: ¿cuán cerca del límite inferior puede llegar una base aditiva de orden ? Esta pregunta fue respondida en el caso por Erdős en 1956. ^[4] Erdős demostró que existe una base aditiva de orden 2 y constantes tales que para todos los suficientemente grandes. En particular, esto implica que existe una base aditiva tal que , que es esencialmente la mejor posible. Esto motivó a Erdős a hacer la siguiente conjetura: ${\displaystyle |B\cap [1,n]|\geq n^{1/h}}$ ${\displaystyle B}$ ${\displaystyle h}$ ${\displaystyle h=2}$ ${\displaystyle B}$ ${\displaystyle c_{1},c_{2}>0}$ ${\displaystyle c_{1}\log n\leq r_{B}(n)\leq c_{2}\log n}$ ${\displaystyle n}$ ${\displaystyle B}$ ${\displaystyle r_{B}(n)=n^{1/2+o(1)}}$

Si es una base aditiva de orden , entonces ${\displaystyle B}$ ${\displaystyle h}$ ${\displaystyle \limsup _{n\rightarrow \infty }r_{B}(n)/\log n>0.}$

En 1986, Eduard Wirsing demostró que una gran clase de bases aditivas, incluidos los números primos, contiene un subconjunto que es una base aditiva pero significativamente más delgada que la original. ^[5] En 1990, Erdős y Prasad V. Tetali extendieron el resultado de Erdős de 1956 a bases de orden arbitrario . ^[6] En 2000, V. Vu demostró que existen subbases delgadas en las bases de Waring utilizando el método del círculo de Hardy-Littlewood y sus resultados de concentración polinómica. ^[7] En 2006, Borwein, Choi y Chu demostraron que para todas las bases aditivas , eventualmente excede 7. ^{[8] [9]} ${\displaystyle B}$ ${\displaystyle f(n)}$

Referencias

1. Erdős, Paul.; Turán, Pál (1941). "Sobre un problema de Sidón en teoría aditiva de números y sobre algunos problemas relacionados". Revista de la Sociedad Matemática de Londres . 16 (4): 212–216. doi :10.1112/jlms/s1-16.4.212.
2. Tao, T. ; Vu, V. (2006). Combinatoria aditiva . Nueva York: Cambridge University Press. p. 13. ISBN 978-0-521-85386-6.
3. Erdős, Paul (1964). "Sobre la representación multiplicativa de números enteros". Revista israelí de matemáticas . 2 (4): 251–261. CiteSeerX 10.1.1.210.8322 . doi : 10.1007/BF02759742 . 
4. Erdős, P. (1956). "Problemas y resultados de la teoría de números aditivos". Colloque sur la Théorie des Nombres : 127-137.
5. Wirsing, Eduard (1986). "Subbases delgadas". Análisis . 6 (2–3): 285–308. doi :10.1524/anly.1986.6.23.285. S2CID  201721463.
6. Erdős, Paul.; Tetali, Prasad (1990). "Representaciones de números enteros como suma de términos". Algoritmos de estructuras aleatorias . 1 (3): 245–261. doi :10.1002/rsa.3240010302. ${\displaystyle k}$
7. Vu, Van (2000). "Sobre un refinamiento del problema de Waring". Duke Mathematical Journal . 105 (1): 107–134. CiteSeerX 10.1.1.140.3008 . doi :10.1215/S0012-7094-00-10516-9. 
8. Borwein, Peter; Choi, Stephen; Chu, Frank (2006). "Una vieja conjetura de Erdős–Turán sobre bases aditivas". Matemáticas de la computación . 75 (253): 475–484. doi : 10.1090/s0025-5718-05-01777-1 .
9. Xiao, Stanley Yao (2011). Sobre la conjetura de Erdős–Turán y resultados relacionados (MSc). hdl : 10012/6150 .