Crecimiento asintótico de cierta secuencia entera

Question

Hace algún tiempo, metiendo las narices en la Sloane's Online Encyclopedia of Integer Sequences, me topé con la secuencia A019568 definida del siguiente modo:

$a(n):=$ el menor número entero positivo $k$ tal que el conjunto $\{1^n, 2^n, 3^n,\dots k^n\}$ puede dividirse en dos conjuntos con igual suma.

En otras palabras, $a(n)$ es el más pequeño $k$ de forma que se pueda elegir entre los signos + o - en la expresión $$1^n\pm2^n\pm\dots\pm k^n \qquad\qquad(1) $$ que lo hace desaparecer. Para demostrar que esta $a(n)$ es un número entero bien definido (es decir: que al menos uno de tales $k$ existe), una simple observación da de hecho un límite $$a(n)<2^{n+1}.$$ Razón: $(1-x)^{n+1}$ divide el polinomio $$Q(x):=(1-x)(1-x^2)(1-x^4)\dots(1-x^{2^n})=+1-x-x^2+x^3-\dots +(-1)^n x^{2^{n+1}-1},$$ por lo tanto, si $S$ es el operador de desplazamiento sobre secuencias, el operador $Q(S)$ tiene el $(n+1)$ -ésima diferencia discreta $(I-S)^{n+1}$ como factor, por lo que aniquila cualquier secuencia que sea polinómica de grado no mayor que $n$ . En particular, la suma algebraica (1) con los signos de los coeficientes de $Q(x)$ desaparece (por cierto, la secuencia de signos es la llamada secuencia de Thue-Morse A106400 , $+--+-++--++-+--+\dots$ .

Sin embargo, si se observan los valores comunicados de $a(n)$ para $n$ de $0$ à $12:$

$$2,\ 3,\ 7,\ 12,\ 16,\ 24, \ 31,\ 39,\ 47,\ 44,\ 60,\ 71,\ 79,$$

parece que el crecimiento de $a(n)$ está muy por debajo de $2^{n+1}$ (Tengo debilidad por las secuencias que crecen lentamente, he aquí posiblemente la principal motivación de esta pregunta).

Pregunta : ¿Alguien tiene una referencia para la secuencia anterior? ¿Puede ver cómo demostrar una asintótica, o una realista que $a(n)<2^{n+1}$ ?

Answer 1

Dado que hay alrededor de 2 k sumas posibles, con un orden de magnitud típico en torno a k n parece razonable suponer que el primer caso en que una de estas sumas sea 0 ocurrirá cuando estos 2 números sean aproximadamente iguales, es decir, cuando k sea aproximadamente n log(n)/log(2). Esta estimación, increíblemente aproximada, es algo menor que los datos numéricos, pero quizá sugiera la tasa de crecimiento correcta,

Answer 2

Aunque no tengo ni idea de cómo establecer un límite superior, parece que al menos he encontrado un límite inferior lineal. Empecé por darme cuenta de que se necesita una cantidad suficientemente grande de $k$ para $k^n$ sea menor que la suma de los números más pequeños del conjunto. Si la suma de todo el resto del conjunto no puede ser igual a la de ese elemento, es evidente que no puede haber una partición igual.

Ya que has demostrado que siempre hay una solución, para un determinado $n$ existe un número entero mínimo $k^\star$ tal que:

$\sum_{i=1}^{k^\star-1} i^n \ge k^{\star n}$

Desde $k^\star$ es el número entero más pequeño,

$\sum_{i=1}^{k^\star-2} i^n < (k^\star-1)^n$

y por lo tanto:

$2 (k^\star-1)^{n} > \sum_{i=1}^{k^\star-1} i^n \ge k^{\star n}$

Para n>0, esto da:

$2^{1/n} > \frac{k^*}{k^\star-1}$

$2^{-1/n} < 1-\frac{1}{k^\star}$

$k^\star > \frac{1}{1-2^{-1/n}} = \sum_{i=0}^{\infty}2^{-i/n} > \frac{n}{2} + 1$

(Mis disculpas si el látex no parsea correctamente, la vista previa parece mostrarlo sólo algunas veces).

Answer 3

Esto se basa en el trabajo de la respuesta de Richard Borherds y el comentario que hice allí. Podemos proporcionar una manera de calcular un límite superior que sería mucho mejor que el límite exponencial actual en $n$ pero se basa en la enumeración de soluciones a determinadas ecuaciones diofánticas.

Vamos a intentar enumerar los distinto valores de la expresión $$e_11^n+e_22^n+\cdots+e_kk^n,$$ donde $e_i = \pm 1$ para $i \in [1,n]$ . Sea $S$ sea el conjunto de todos los valores alcanzados por esta expresión. Obviamente tenemos $|S| \le 2^k$ ya que hay $2^k$ formas de elegir los signos, pero sabemos que dos opciones diferentes para el $e_i$ pueden dar el mismo valor numérico. Un ejemplo ilustrativo se da en el caso $(k,n) = (5,2)$ donde tenemos $$+1^2+2^2+3^2+4^2-5^2 = +1^2+2^2-3^2-4^2+5^2 = 5.$$ Si tenemos dos opciones para el $e_i$ - por ahora, llamaremos a las dos listas de coeficientes $a_i$ y $b_i$ que coinciden, podemos formar conjuntos $A = \{i \in [1,n]: a_i = +1, b_i = -1\}$ y $B = \{i \in [1,n]: a_i = -1, b_i = +1 \}$ . Entonces sabemos que $A \cap B = \emptyset$ y lo que es más importante, $\sum_{a\in A}a^n = \sum_{b \in B}b^n$ .

Defina ahora una función $s(k,n,a,b)$ con $a \ge b$ y $a+b \le k$ para contar el número de pares de conjuntos $(A,B)$ que cumpla las siguientes condiciones:

• $A \cup B \subseteq [1,k]$ ;
• $A \cap B = \emptyset$ ;
• $|A| = a$ y $|B| = b$ ;
• si $a = b$ entonces $\max{A} < \max{B}$ ;
• $\sum_{a\in A}a^n = \sum_{b \in B}b^n$ .

Entonces podemos escribir $$|S| \ge 2^k - \sum_{m=3}^k2^{k-m-1}\sum_{1 \le j \le m/2}s(k,n,m-j,j).$$ De hecho, vemos que si algún conjunto de elecciones de $e_i$ dan el mismo valor numérico, todos menos uno serán eliminados por este recuento de inclusión-exclusión. Podemos simplificarlo un poco más escribiendo $$f(k,n) = \sum_{m=3}^k2^{-m-1}\sum_{1 \le j \le m/2}s(k,n,m-j,j)$$ ya que nuestra ecuación se convierte entonces en $|S| \ge 2^k(1-f(k,n))$ . Ahora bien, una vez que hemos establecido límites adecuados para $f(k,n)$ podemos proceder como Richard, observando que simplemente resolvemos para el valor menos válido de $k$ en la desigualdad $$2^k(1-f(k,n)) \ge 2\sum_{i=1}^ki^n.$$

¿Dónde entra el último teorema de Fermat? Bueno, en caso de que $n \ge 3$ sólo tenemos que sumar desde $m = 4$ à $k$ - no hay soluciones para $m = 3$ como solución para $m = 3$ adopta la forma $x^n + y^n = z^n$ ¡! Así que perdemos lo que es (¿posiblemente?) el término que más contribuye a $f(k)$ .

EDIT: Me he equivocado por un factor de dos. Maldición.

Answer 4

He aquí una forma más sencilla de ver este resultado:

• Si f(x)= $\sum a_kx^k$ es un polinomio divisible por $(x-1)^{n+1}$ entonces $\sum a_kg(k)=0$ para cualquier polinomio de grado n (o menor).

Basta con comprobarlo para una base del conjunto de polinomios de estos grados. Como x=1 es una raíz de la derivada j-ésima $f^{(j)}$ la igualdad alegada es válida para $g(k)=k(k-1)(k-2)\cdots(k-j+1)$ .

Así que $(x-1)(x^2-1)(x^4-1)=x^7-x^6-x^5+x^4-x^3+x^2+x-1$ y por lo tanto $\sum_{[0,3,5,6[}k^j=\sum_{[1,2,4,7]}k^j$ para $j=0,1,2$ . Entonces a(3)=7 porque nada más pequeño funciona para el problema restringido $\sum_A k^j=\sum_Bk^j$ sólo para $j=2$ pero con $A,B$ una partición de los enteros positivos hasta algún punto. Tenga en cuenta que la partición es de acuerdo a la paridad de la suma de los bits en el la forma binaria de m. La construcción similar muestra que los números enteros de 1 a b^{n+1}-1 se puede dividir en b conjuntos de tamaño b^{n) con los conjuntos de acuerdo en todas las sumas de potencias jth j=0..n.

$(x-1)(x^2-1)(x^3-1)$ produce $\sum_{[0,4,5]}k^j=\sum_{[1,2,6]}k^j$ para $j=0,1,2$ pero hay un hueco en el 3. El papel El problema Prouhet-Tarry-Escott revisado Enseign. Math. (2) 40 (1994) de Peter Borwein y Colin Ingalls ofrece abundante información sobre este asombroso (otro) problema de sumas iguales de potencias jth powers j=0,1,2,...,n . Suele estar disponible en el sitio web http://www.cecm.sfu.ca/ pero de momento no he podido llegar.

El valor a(3)=12 proviene de la partición {1,2,4,8,9,12},{3,5,6,7,10,11} y existe el polinomio (desplazando hacia abajo) $$1+x-x^2+x^3-x^4-x^5-x^6+x^7+x^8-x^9-x^{10}+x^{11}=$$ $$(x^3-1)(x^8-x^7-x^6+2x^5-2x^3+x^2-x-1)$$

El valor a(4)=16 proviene de la partición {5, 6, 7, 13, 14, 15}, {1, 2, 3, 4, 8, 9, 10, 11, 12, 16} y existe el polinomio (desplazando hacia abajo) $$x^{15}-x^{14}-x^{13}-x^{12}+x^{11}+x^{10}+x^9+x^8+x^7-x^6-x^5-x^4+x^3+x^2+x+1=$$ $$(x^7-x^6-x^5-x^4+x^3+x^2+x+1)(x^8+1)$$ que es intrigante. Sin embargo no encontré nada que factorizara para a(9) (donde los conjuntos están listados en la OEIS) y no hice la búsqueda de los conjuntos que dan las otras a(n).

Es posible que se puedan encontrar construcciones que den soluciones con patrones agradables que no sean mínimos pero que establezcan un límite superior. Sin embargo, yo de momento no puedo. Yo probaría con polinomios desplazando k a $x^{k-1}$ o bien poniendo un 1 para $x^0$ en un conjunto u otro.