En la teoría de números aditivos , un área de las matemáticas , el teorema de Erdős-Tetali es un teorema de existencia relativo a bases económicas aditivas de todo orden. Más específicamente, establece que para cada entero fijo, existe un subconjunto de los números naturales satisfactorio
El teorema lleva el nombre de Paul Erdős y Prasad V. Tetali , quienes lo publicaron en 1990.
Motivación
La motivación original de este resultado se atribuye a un problema planteado por S. Sidon en 1932 sobre bases económicas . Una base aditivase llama económica [2] (o, a veces delgada [3] ) cuando se trata de una base aditivo de orden h y
para cada . En otras palabras, se trata de bases aditivas que utilizan la menor cantidad posible de números para representar una n dada y, sin embargo, representan cada número natural. Los conceptos relacionados incluyen-secuencias [4] y la conjetura de Erdős-Turán sobre bases aditivas .
La pregunta de Sidon era si existe una base económica de orden 2. P. Erdős dio una respuesta positiva en 1956, [5] resolviendo el caso h = 2 del teorema. Aunque se creía que la versión general era cierta, no apareció ninguna prueba completa en la literatura antes del artículo de Erdős y Tetali. [6]
Ideas en la prueba
La demostración es una instancia del método probabilístico y se puede dividir en tres pasos principales. Primero, uno comienza definiendo una secuencia aleatoria por
dónde es una gran constante real, es un número entero fijo yn es lo suficientemente grande para que la fórmula anterior esté bien definida. Se puede encontrar una discusión detallada sobre el espacio de probabilidad asociado con este tipo de construcción en Halberstam y Roth (1983). [7] En segundo lugar, se muestra que el valor esperado de la variable aleatoria tiene el orden de log . Es decir,
Finalmente, se muestra que casi seguramente se concentra en torno a su medio. Más explícitamente:
Este es el paso crítico de la prueba. Originalmente se trató mediante la desigualdad de Janson , un tipo de desigualdad de concentración para polinomios multivariados. Tao y Vu (2006) [8] presentan esta prueba con una desigualdad de concentración bilateral más sofisticada de V. Vu (2000), [9] simplificando relativamente este paso. Alon y Spencer (2016) clasifican esta prueba como una instancia del paradigma de Poisson . [10]
Relación con la conjetura de Erdős-Turán sobre bases aditivas
Dejar ser un número entero. Si es un conjunto infinito tal que para cada n , esto implica que:
- ?
La conjetura original de Erdős-Turán sobre bases aditivas establece, en su forma más general, que sies una base aditiva de orden h entonces
es decir, no puede ser acotado. En su artículo de 1956, P. Erdős [5] preguntó si podría ser el caso que
cuando sea es una base aditiva de orden 2. En otras palabras, esto significa que no solo es ilimitado, sino que ninguna función más pequeña que log puede dominar . La pregunta se extiende naturalmente a, lo que la convierte en una forma más fuerte de la conjetura de Erdős-Turán sobre bases aditivas. En cierto sentido, lo que se está conjeturando es que no hay bases aditivas sustancialmente más económicas que las que garantiza el teorema de Erdős-Tetali.
Nuevos desarrollos
Bases económicas computables
Todas las demostraciones conocidas del teorema de Erdős-Tetali son, por la naturaleza del espacio de probabilidad infinito utilizado, demostraciones no constructivas . Sin embargo, Kolountzakis (1995) [11] mostró la existencia de un conjunto recursivo satisfactorio tal que toma el tiempo polinomial en n para ser calculado. La pregunta para Permanece abierto.
Subbases económicas
Dada una base aditiva arbitraria , uno puede preguntarse si existe tal que es una base económica. V. Vu (2000) [12] mostró que este es el caso de las bases Waring , donde por cada k fijo hay subbase económicas de de orden para cada , para una gran constante computable .
Tasas de crecimiento distintas del registro
Otra posible pregunta es si se aplican resultados similares para funciones distintas de log. Es decir, fijando un número entero, para qué funciones f podemos encontrar un subconjunto de los números naturales satisfactorio ? Se deduce de resultado de C. Táfula (2019) [13] que si f es un localmente integrable , positiva función real satisfaciendo
- , y
- para algunos ,
entonces existe una base aditiva de orden h que satisface. El caso mínimo f ( x ) = log x recupera el teorema de Erdős-Tetali.
Ver también
- Teorema de Erdős-Fuchs : para cualquier valor distinto de cero, no hay set que satisface .
- Conjetura de Erdős-Turán sobre bases aditivas : Si es una base aditiva de orden 2, entonces .
- El problema de Waring , el problema de representar números como sumas de k -poderes, para.
Referencias
- ^ Declaración alternativa ennotación Theta grande :
- ^ Como en Halberstam y Roth (1983), p. 111.
- ^ Como en Tao & Vu (2006), p. 13.
- ^ Véase Definición 3 (pág. 3) de O'Bryant, K. (2004), "Una bibliografía anotada completa de los trabajos relacionados con las secuencias de Sidon" (PDF), Revista Electrónica de Combinatoria , 11 : 39.
- ↑ a b Erdős, P. (1956). "Problemas y resultados en la teoría de números aditivos". Colloque sur la Théorie des Nombres : 127-137.
- ^ Ver p. 264 de Erdős – Tetali (1990).
- ^ Véase el teorema 1 del capítulo III.
- ^ Sección 1.8 de Tao & Vu (2006).
- ^ Vu, Van H. (1 de julio de 2000). "Sobre la concentración de polinomios multivariados con pequeña expectativa". Estructuras y algoritmos aleatorios . 16 (4): 344–363. CiteSeerX 10.1.1.116.1310 . doi : 10.1002 / 1098-2418 (200007) 16: 4 <344 :: aid-rsa4> 3.0.co; 2-5 . ISSN 1098-2418 .[ enlace muerto permanente ]
- ^ Capítulo 8, p. 139 de Alon y Spencer (2016).
- ^ Kolountzakis, Mihail N. (13 de octubre de 1995). "Una base aditiva eficaz para los números enteros". Matemáticas discretas . 145 (1): 307–313. doi : 10.1016 / 0012-365X (94) 00044-J .
- ^ Vu, Van H. (15 de octubre de 2000). "Sobre un refinamiento del problema de Waring". Diario de matemáticas de Duke . 105 (1): 107-134. CiteSeerX 10.1.1.140.3008 . doi : 10.1215 / s0012-7094-00-10516-9 . ISSN 0012-7094 .
- ^ Táfula, Christian (2019). "Una extensión del teorema de Erdős-Tetali". Estructuras y algoritmos aleatorios . 55 (1): 173–214. arXiv : 1807.10200 . doi : 10.1002 / rsa.20812 . ISSN 1098-2418 .
- Erdős, P .; Tetali, P. (1990). "Representaciones de enteros como suma de k términos". Estructuras y algoritmos aleatorios. 1 (3): 245–261. doi : 10.1002 / rsa.3240010302 .
- Halberstam, H .; Roth, KF (1983). Secuencias . Springer Nueva York. ISBN 978-1-4613-8227-0 . OCLC 840282845 .
- Alon, N .; Spencer, J. (2016). El método probabilístico (4ª ed.). Wiley. ISBN 978-1-1190-6195-3 . OCLC 910535517 .
- Tao, T .; Vu, V. (2006). Combinatoria aditiva . Prensa de la Universidad de Cambridge. ISBN 0521853869 . OCLC 71262684 .