Finding the min of $m$ such that $k = \pm 1^n \pm 2^n \pm 3^n \pm \cdots \pm m^n$ for a given pair $(n,k)$

Erdös-Suranyi theorem states that

For each natural number $k$ there is an $m$ and an appropriate choice of $+$ and $-$ signs (which we write as $±$ in short) such that $k = \pm 1^2 \pm 2^2 \pm 3^2 \pm \cdots \pm m^2$.

By the way, we can generalize this theorem as the following $(\star)$ (I'm going to write the proof at the end of this question):

Letting $n\in\mathbb N$, for each natural number $k$ there is an $m$ and an appropriate choice of $+$ and $-$ signs (which we write as $±$ in short) such that $k = \pm 1^n \pm 2^n \pm 3^n \pm \cdots \pm m^n$.

Here, for a given pair $(n,k)$, let $M(n,k)$ be the min of such $m$.

Then, here are my questions.

Question 1 : What is $M(2,k)$ ? Can we represent it by $k$ ? Or can we estimate it from above?

Question 2 : What is $M(n,k)$ ? Can we represent it by $k$ ? Or can we estimate it from above?

Remark : This question has been asked previously on math.SE without receiving any answers.

Motivation : I've been able to solve the $n=1$ case. Letting $A_m=\{k|k=\pm 1 \pm 2 \pm 3 \pm \cdots \pm m,k\in\mathbb N\}$, we get $$A_1=\{1\}, A_2=\{1,3\},A_3=\{2,4,6\},A_4=\{2,4,6,8,10\},\cdots.$$ These lead that $M(1,k)$ is the min of $m$ such that $$\text{When k is odd}\ \ \ k\le m(m+1)/2\ \ \ m\equiv 1,2\ (\text{mod 4}),$$ $$\text{When k is even}\ \ \ k\le m(m+1)/2\ \ \ m\equiv 3,0\ (\text{mod 4}).$$

For the $n=2$ case, I've been able to find a way to represent $k$ by about $\sqrt k$ terms. Precisely speaking, we can represent $k$ by $m\ (\ge 10)$ terms such that

$$\text{When k is odd}\ \ \ k\le (m+1)^2\ \ \ m\equiv 1,2\ (\text{mod 4}),$$ $$\text{When k is even}\ \ \ k\le (m+1)^2\ \ \ m\equiv 3,0\ (\text{mod 4}),$$ (Note that $m\ge 10$.)

In the following, I'm going to explain this idea briefly.

We know that when $m=10$ we can represent every odd $k$ from $1$ to $121={11}^2$ such as $$1={10}^2-9^2+8^2-7^2-6^2+5^2-4^2-3^2+2^2-1^2,$$ $$121={10}^2-9^2+8^2+7^2+6^2-5^2-4^2-3^2+2^2-1^2.$$ Then, we know that we can represent every even $k$ from $0$ to $144={12}^2$ such as $${11}^2-121=0, {11}^2-119=2,\cdots,{11}^2-1=120, \cdots, {11}^2+23=144={12}^2.$$ Then, we know that we can represent every even $k$ from $0$ to $169={13}^2$ such as $${12}^2-144=0, {12}^2-142=2, \cdots, {12}^2-0=144,\cdots, {12}^2+24=168.$$ Then, we know that we can represent every odd $k$ from $1$ to $196={14}^2$ such as $${13}^2-168=1, {13}^2-166=3, \cdots, {13}^2-0=169, \cdots,{13}^2+26=195$$ and so on.

However, I don't have any good idea for finding $M(n,k)$. Can anyone help?

Proof for $(\star)$ : Considering the $n$-th difference sequence, we can get \begin{align}\pm (m+1)^n\pm (m+2)^n\pm\cdots\pm (m+2^n)^n=n!\times 2^{n(n+1)/2}\qquad(1)\end{align} Signs are determined when we make difference sequences. Letting $l$ be this value, we know that $-l$ can be represented as the left hand side of $(1)$. In the following, let us consider in mod $l$.

Since we know $$-(al+1)^n-(al+2)^n-\cdots -(al+l)^n+(al+l+1)^n+\cdots+(al+l+l)^n\equiv 0,$$ we also get $$(al+1)^n-(al+2)^n-\cdots -(al+l)^n+(al+l+1)^n+\cdots+(al+l+l)^n\equiv 2.$$ Letting $f(a)$ be the left hand side of this equation, we get \begin{align}f(0)+f(2)+\cdots+f(2b)\equiv 2(b+1)\qquad(2)\end{align} Since the left hand side of $(2)$ is $$1^n-2^n-\cdots -l^n+(l+1)^n+\cdots+(2l)^n+(2l+1)^n-\cdots+\{(2b+2)l\}^n,$$ we know that this is in our form. Adding $\{(2b+2)l+1\}^n$ to this equation keeps the form as \begin{align}f(0)+f(1)+\cdots +f(2b)+\{(2b+2)l+1\}^n\equiv 2(b+1)+1\qquad(3)\end{align} $(2)$ shows that every even in system of residues of mod $l$ can be represented in our form. Also, $(3)$ shows that every odd in system of residues of mod $l$ can be represented in our form. Hence, by using $(1)$ many times, we now know that every natural number can be represented in our form.

• For the case $k=0$ there is an exponential bound (that seems far from optimal): mathoverflow.net/questions/36995/… – Pietro Majer Nov 22 '13 at 12:05
• Let S_m be the set of numbers generated using m summands, and let T_m be the union up to m of S_i. For some small m, one should find T_m contains the interval [-f(m), f(m)], and so T_m+1 will contain the interval [-f(m)-(m+1)^n, f(m) + (m+1)^n] when f(m) is larger than (m+1)^n. A reasonable lower bound on f(m) gives you a finite set (depending on m) of indices to search, and a resulting upper bound on M(n,k). Unless the S_m are very nicely described, I doubt an exact formula in k is available, but M(n,k) \in O(k^{1/n}) should be doable. Gerhard "Not Doing Much TeX Today" Paseman, 2013.11.22 – Gerhard Paseman Nov 22 '13 at 17:17

[Upon request from the OP, I have deleted my comment to re-post it as an answer.]

For related work, see the following source and references contained therein: Bleicher, M. N. (1996). On Prielipp's Problem on Signed Sums of kth Powers. Journal of Number Theory, 56(1), 36-51.

The article should be available for free here; an image of the abstract can be found below.

(Don't be misled by the typo in line one!)

Also of interest may be a couple of the papers that have cited the aforelinked: GoogleScholar