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.
