7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ For the case $k=0$ there is an exponential bound (that seems far from optimal): mathoverflow.net/questions/36995/… $\endgroup$ – Pietro Majer Nov 22 '13 at 12:05
  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Nov 22 '13 at 17:17
7
$\begingroup$

[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!)

enter image description here

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.