Teorema de Erdös-Tetali

Teorema de existencia para bases aditivas económicas de cualquier orden

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 sobre bases aditivas económicas de cada orden. Más específicamente, establece que para cada entero fijo , existe un subconjunto de los números naturales que satisfacen ${\displaystyle h\geq 2}$ ${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$

$${\displaystyle r_{{\mathcal {B}},h}(n)\asymp \log n,}$$donde denota el número de formas en que un número natural n puede expresarse como la suma de h elementos de B. ^[1] ${\displaystyle r_{{\mathcal {B}},h}(n)}$

El teorema debe su nombre a Paul Erdős y Prasad V. Tetali , quienes lo publicaron en 1990.

Motivación

La motivación original para este resultado se atribuye a un problema planteado por S. Sidon en 1932 sobre bases económicas . Una base aditiva se llama económica ^[2] (o a veces delgada ^[3] ) cuando es una base aditiva de orden h y ${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$

${\displaystyle r_{{\mathcal {B}},h}(n)\ll _{\varepsilon }n^{\varepsilon }}$

para cada . En otras palabras, se trata de bases aditivas que utilizan la menor cantidad de números posible para representar un n dado y, sin embargo, representan todos los números naturales. Los conceptos relacionados incluyen -secuencias ^[4] y la conjetura de Erdős–Turán sobre bases aditivas . ${\displaystyle \varepsilon >0}$ ${\displaystyle B_{h}[g]}$

La pregunta de Sidon era si existía una base económica de orden 2. En 1956, P. Erdős dio una respuesta afirmativa ^[5] , resolviendo el caso h = 2 del teorema. Aunque se creía que la versión general era verdadera, no había aparecido en la literatura ninguna prueba completa antes del artículo de Erdős y Tetali ^{[6] .}

Ideas en la prueba

La prueba es una instancia del método probabilístico y se puede dividir en tres pasos principales. Primero, se comienza definiendo una secuencia aleatoria mediante ${\displaystyle \omega \subseteq \mathbb {N} }$

${\displaystyle \Pr(n\in \omega )=C\cdot n^{{\frac {1}{h}}-1}(\log n)^{\frac {1}{h}},}$

donde es una constante real grande, es un entero fijo y n es lo suficientemente grande como 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 & Roth (1983). ^[7] En segundo lugar, se muestra que el valor esperado de la variable aleatoria tiene el orden de log . Es decir, ${\displaystyle C>0}$ ${\displaystyle h\geq 2}$ ${\displaystyle r_{\omega ,h}(n)}$

${\displaystyle \mathbb {E} (r_{\omega ,h}(n))\asymp \log n.}$

Finalmente, se demuestra que casi con seguridad se concentra alrededor de su media. Más explícitamente: ${\displaystyle r_{\omega ,h}(n)}$

${\displaystyle \Pr {\big (}\exists c_{1},c_{2}>0~|~{\text{for all large }}n\in \mathbb {N} ,~c_{1}\mathbb {E} (r_{\omega ,h}(n))\leq r_{\omega ,h}(n)\leq c_{2}\mathbb {E} (r_{\omega ,h}(n)){\big )}=1}$

Este es el paso crítico de la prueba. Originalmente se trataba 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 así 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

Problema sin resolver en matemáticas :

Sea un entero. Si es un conjunto infinito tal que para cada n , ¿esto implica que: ${\textstyle h\geq 2}$ ${\textstyle {\mathcal {B}}\subseteq \mathbb {N} }$ ${\textstyle r_{{\mathcal {B}},h}(n)>0}$

${\displaystyle \limsup _{n\to \infty }{\frac {r_{{\mathcal {B}},h}(n)}{\log n}}>0}$?

(más problemas sin resolver en matemáticas)

La conjetura original de Erdős-Turán sobre bases aditivas establece, en su forma más general, que si es una base aditiva de orden h entonces ${\textstyle {\mathcal {B}}\subseteq \mathbb {N} }$

${\displaystyle \limsup _{n\to \infty }r_{{\mathcal {B}},h}(n)=\infty ;}$

es decir, no puede ser acotada. En su artículo de 1956, P. Erdős ^[5] preguntó si podría darse el caso de que ${\textstyle r_{{\mathcal {B}},h}(n)}$

${\displaystyle \limsup _{n\to \infty }{\frac {r_{{\mathcal {B}},2}(n)}{\log n}}>0}$

siempre que sea una base aditiva de orden 2. En otras palabras, esto está diciendo que no sólo es ilimitada, sino que ninguna función menor 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 aquellas cuya existencia garantiza el teorema de Erdős–Tetali. ${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$ ${\textstyle r_{{\mathcal {B}},2}(n)}$ ${\textstyle r_{{\mathcal {B}},2}(n)}$ ${\displaystyle h\geq 3}$

Desarrollos futuros

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] demostró la existencia de un conjunto recursivo que satisface tal que tarda un tiempo polinomial en n en calcularse. La cuestión para permanece abierta. ${\displaystyle {\mathcal {R}}\subseteq \mathbb {N} }$ ${\displaystyle r_{{\mathcal {R}},2}(n)\asymp \log n}$ ${\displaystyle {\mathcal {R}}\cap \{0,1,\ldots ,n\}}$ ${\displaystyle h\geq 3}$

Subbases económicas

Dada una base aditiva arbitraria , se puede preguntar si existe tal que sea una base económica. V. Vu (2000) ^[12] demostró que este es el caso para las bases de Waring , donde para cada k fijo existen subbases económicas de de orden para cada , para alguna constante computable grande . ${\displaystyle {\mathcal {A}}\subseteq \mathbb {N} }$ ${\displaystyle {\mathcal {B}}\subseteq {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle \mathbb {N} ^{\wedge }k:=\{0^{k},1^{k},2^{k},\ldots \}}$ ${\displaystyle \mathbb {N} ^{\wedge }k}$ ${\displaystyle s}$ ${\displaystyle s\geq s_{k}}$ ${\displaystyle s_{k}}$

Tasas de crecimiento distintas del logaritmo

Otra pregunta posible es si se aplican resultados similares para funciones distintas de logaritmo. Es decir, fijando un entero , ¿para qué funciones f podemos encontrar un subconjunto de los números naturales que satisfacen ? De un resultado de C. Táfula (2019) ^[13] se deduce que si f es una función real positiva localmente integrable que satisface ${\displaystyle h\geq 2}$ ${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$ ${\displaystyle r_{{\mathcal {B}},h}(n)\asymp f(n)}$

• ${\displaystyle {\frac {1}{x}}\int _{1}^{x}f(t)\,\mathrm {d} t\asymp f(x)}$, y
• ${\displaystyle \log x\ll f(x)\ll x^{\frac {1}{h-1}}(\log x)^{-\varepsilon }}$Para algunos , ${\displaystyle \varepsilon >0}$

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. ${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$ ${\displaystyle r_{{\mathcal {B}},h}(n)\asymp f(n)}$

Véase también

• Teorema de Erdős-Fuchs : Para cualquier , no hay ningún conjunto que satisfaga . ${\displaystyle C\in \mathbb {R} }$ ${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$ ${\displaystyle \textstyle {\sum _{n\leq x}r_{{\mathcal {B}},2}(n)=Cx+o\left(x^{1/4}\log(x)^{-1/2}\right)}}$
• Conjetura de Erdős-Turán sobre bases aditivas : Si es una base aditiva de orden 2, entonces . ${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$ ${\displaystyle r_{{\mathcal {B}},2}(n)\neq O(1)}$
• Problema de Waring , el problema de representar números como sumas de k -potencias, para valores fijos . ${\displaystyle k\geq 2}$

Referencias

1. Enunciado alternativo en notación Theta grande : $${\displaystyle r_{{\mathcal {B}},h}(n)=\Theta (\log(n)),}$$
2. Como en Halberstam y Roth (1983), pág. 111.
3. Como en Tao & Vu (2006), pág. 13.
4. Véase la Definición 3 (p. 3) de O'Bryant, K. (2004), "Una bibliografía completa anotada del trabajo relacionado con las secuencias de Sidón", Electronic Journal of Combinatorics , 11 : 39.
5. Erdős, P. (1956). "Problemas y resultados en la teoría de números aditivos". Colloque sur la Théorie des Nombres : 127–137.
6. Ver pág. 264 de Erdős-Tetali (1990).
7. Véase el Teorema 1 del Capítulo III.
8. Sección 1.8 de Tao & Vu (2006).
9. Vu, Van H. (1 de julio de 2000). "Sobre la concentración de polinomios multivariados con pequeña expectativa". Random Structures & Algorithms . 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. 
10. Capítulo 8, p. 139 de Alon & Spencer (2016).
11. Kolountzakis, Mihail N. (13 de octubre de 1995). "Una base aditiva efectiva para los números enteros". Matemáticas discretas . 145 (1): 307–313. doi : 10.1016/0012-365X(94)00044-J .
12. Vu, Van H. (15 de octubre de 2000). "Sobre un refinamiento del problema de Waring". Revista 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. 
13. Táfula, Christian (2019). "Una extensión del teorema de Erdős-Tetali". Algoritmos y estructuras aleatorias . 55 (1): 173–214. arXiv : 1807.10200 . doi :10.1002/rsa.20812. ISSN  1098-2418. S2CID  119249787.

• Erdős, P. ; Tetali, P. (1990). "Representaciones de números enteros como la 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 . Cambridge University Press. ISBN 0521853869 . OCLC  71262684.