Variantes del problema de Waring

Question

El problema de Waring (anteriormente preguntado por aquí ) pregunta, para cada número entero $k \ge 2$ ¿Cuál es el menor número entero $g(k)$ tal que cualquier número entero positivo puede escribirse como una suma de $g(k)$ kth poderes. Tenemos $g(2) = 4$ , $g(3) = 9$ etc. Una variante (más difícil) pregunta cuál es el número entero más pequeño $G(k)$ es tal que todos los suficientemente grande Los números enteros pueden escribirse como una suma de $G(k)$ kth poderes.

Tengo dos preguntas relacionadas:

1. Lo que se sabe si relajamos la condición ``cualquier número entero positivo'' y sólo exigimos un subconjunto de densidad positiva ? Más concretamente, buscamos el menor $g'(k)$ para los que hay algún $S \subset \mathbb{Z}_{>0}$ de densidad positiva tal que cualquier $x \in S$ puede escribirse como $g'(k)$ $k$ de los poderes. Entonces tenemos $g'(2) = 3$ , mientras que $G(2) = 4$ y $g'(3) = 4$ mientras que sólo se sabe que $4 \le G(3) \le 7$ . ¿Se sabe algo sobre $g'(k)$ para k = 4,5, o mayor?

2. Para k fijo, ¿existe un algoritmo eficiente que, dado n, escriba n como una suma de $g(k)$ ¿poderes kth? ¿Y si descomponemos n en el mínimo número de potencias kth para ese n? (Aquí "eficiente" significa polinómico en log(n)).

Edición: Wikipedia dice que "En ausencia de restricciones de congruencia, un argumento de densidad sugiere que G(k) debe ser igual a k + 1". Así que tal vez esta es la respuesta a (1)?

Answer 1

En cuanto a la pregunta 1, es fácil demostrar que $g'(k) \ge k$ y la expectativa es que $g'(k)=k$ para todos $k \ge 3$ . Pero la igualdad es una cuestión abierta incluso para $k=3$ . Véase Deshouillers, Jean-Marc; Hennecart, François; Landreau, Bernard; Sumas de potencias: un refinamiento aritmético del modelo probabilístico de Erdös y Rényi. Acta Arith. 85 (1998), nº 1, 13-33, y otros trabajos de estos autores.