# Every natural number is representable as $\sum_{k=1}^{n} \pm k^5$ ... if somebody proves it for 240 integers

(This post is inspired by "Is every $\mathbb{N}$ representable as $\sum\limits_{k=1}^{n} \pm k^3$"? My question is at the end.)

The problem of whether every natural number $N$ is,

$$N=\sum_{k=1}^n \pm k^p$$

in an infinite number of ways may be reduced to finding polynomial identities and checking a finite number of cases. (The background can be found in Dumitrescu and Xu's paper, but the identities here are new.)

For $p=5$, it can be shown this reduces to merely checking all integers $0\leq N<240$.

Details:

$\color{blue}{\text{I.}\;p = 3:}$

$$\sum_{n=1}^{10}s_n\big(x+n)^3-\sum_{n=1}^{10}s_{11-n}\big(x+n+10\big)^3 = 6\tag1$$

for the ten $s_n = 1, -1, -1, 1, -1, 1, -1, 1, 1, 1$.

As the paper points out, what remains is to show that all $0\leq N<6$ is a sum of cubes, which is indeed the case.

Note: This is more symmetrical and uses only $20$ addends, whereas the paper uses $28$ addends.

$\color{blue}{\text{II.}\;p = 4:}$

$$\sum_{n=1}^{20}a_n\big(x+n)^4+\sum_{n=1}^{20}a_{21-n}\big(x+n+20\big)^4 = 192$$

where $a_n =-1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, -1, 1$.

$$\sum_{n=1}^{20}b_n\big(x+n)^4+\sum_{n=1}^{20}b_{21-n}\big(x+n+20\big)^4 = 480$$

where $b_n =-1, 1, 1, -1, 1, -1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, -1, 1$.

Since $\text{GCD}(192,\,480) = 96$, we can combine these two into one with sum $96$.

Let $\alpha=-2,\beta=1$, and $192\alpha+480\beta=96(2\alpha+5\beta)=96$, so we use the first sequence ${2\times,}$ and subtract it with the second sequence $1\times,$ to get,

$$\sum_{n=1}^{120}c_n(x+n)^4 = 96\tag2$$

where $c_n = \text{-Flatten[{a, Reverse[a], a, Reverse[a], -b, -Reverse[b]}]}$, in Mathematica.

Note: This uses only $(40\times2)+(40\times1)=120$ addends, whereas the paper uses $136$. (The authors then show that all $0\leq N<96$ can be decomposed into fourth powers.)

$\color{blue}{\text{III.}\;p = 5:}$

$$\sum_{n=1}^{20}u_n\big(x+n)^5-\sum_{n=1}^{20}u_{21-n}\big(x+n+20\big)^5 = 1668000$$

where $u_n = -1, -1, 1, 1, 1, 1, 1, -1, -1, -1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1$.

$$\sum_{n=1}^{24}v_n\big(x+n)^5-\sum_{n=1}^{24}v_{25-n}\big(x+n+24\big)^5 = 1509120$$

where $v_n = 1, -1, -1,1, -1, -1,1,1,1, -1, 1, 1,1,-1, -1, -1, -1,1, -1,-1,1,1,-1, 1$.

Since $\text{GCD}(1668000,\,1509120) = 480$, we can also combine these.

Let $\alpha=19,\beta=-21$, and $1668000\alpha + 1509120\beta=480 (3475\alpha + 3144\beta) =480$, so we use the first sequence $19\times,$ and subtract it with the second sequence $21\times,$ to get,

$$\sum_{n=1}^{1768}w_n(x+n)^5 = 480\tag3$$

where $(40\times19) + (48\times21)=1768$. (The explicit sequence $w_n$ is too tedious to include.)

Note: The very first version of this post had an identity for $p=5$ with more than $70000$ addends. But it can be reduced to just $168$ given explicitly here.

Question: For the remaining integers, anyone has an efficient computer code to show that,

$$N=\sum\limits_{k=1}^n \pm k^5,\quad\text{where}\; 0\leq N<240$$

is indeed the case? (P.S. Since it involves odd powers, one can reduce the range to $0\leq N<240$ as R. Millikan points out in this related question.)

Note: The paper does not deal with $p=5$.

• Do you have a sense for how large you expect the largest $n$ to be? Writing code to incrementally generate all possible sums for increasing $n$ is a trivial matter, but this strategy will have exponential space and time complexity and is only feasible for $n\leq 30$ or so. Dec 29, 2014 at 3:01
• @user7530: I don't know how they found the correct signage for $\pm1^4\pm2^4\pm3^4\dots\pm64^4=80$, for example, but they were able to go much higher than $n>30$. (See Index at end of their paper.) Dec 29, 2014 at 3:31
• This post will interest you: math.stackexchange.com/questions/1079575/… Dec 29, 2014 at 4:53
• Update: I cobbled up some basic code using Mathematica. For $|N|<240$, I found that $\pm1^5\pm2^5\pm3^5\dots\pm n^5 = N$ up to $n=20$ has solutions for $49$ distinct $N$, while increasing it slightly to $n=24$ already finds $158$ distinct $N$. I'm now quite sure that with high enough $n$, it should find all $|N|<240$. (How the authors of the paper reached a search space up to $n=64$ I don't know.) Dec 29, 2014 at 19:00
• I'd rather not post my code, but I have verified that every $0<N<10000$ can be so written with either $n=42$ or $n=56$. One can calculate all possible values for $[1,14],[15,28],[29,42],[43,56]$ (that is, fourteen terms at a time) which are less than $5\times 10^6$ then take sums and differences. Dec 29, 2014 at 23:33

## 3 Answers

Here's a solution for general $p$:

For general $p$, we only have to check numbers $0 \leq x < C_{p}$. But now actually it also suffices to check all the residue classes modulo $C_{p}$. Now the point is that \begin{eqnarray*} \sum_{n = 1}^{C_{p}^2}n^{p} &=& \sum_{n = 1}^{C_{p}}n^{p} + \sum_{n = C_{p} + 1}^{2C_{p}}n^{p} + \ldots + \sum_{n = (C_{p}-1)C_{p} + 1}^{C_{p}^2}n^{p} \\ &\equiv& \sum_{n = 1}^{C_{p}}n^{p} + \sum_{n = 1}^{C_{p}}n^{p} + \ldots + \sum_{n = 1}^{C_{p}}n^{p} \\ &\equiv & C_{p}\sum_{n = 1}^{C_{p}}n^{p} \\ &\equiv& 0 \mod C_{p} \end{eqnarray*} but now changing the first sign to minus we get $$-1^p+2^p+3^p+\ldots + (C_{p}^2)^p \equiv -2 \mod C_p$$ Now for any even residues just continue like that; for $-2m$ just take $mC_{p}^2$ numbers such that the sign is minus if and only if $n \equiv 1 \mod C_{p}^2$. Finally for odd residues add one final power, which is of the form $(kC_{p}+1)^p \equiv 1 \mod C_{p}$.

This proves that any residue is attainable with at most $\frac{C_{p}^3}{2} + 1$ consecutive signed powers; using this it would take quite a lot of them to get numbers form $0$ to $C_p$, but it works.

• Hm, to quote the abstract of Dumitrescu and Xu's paper, "...Erdos and Suranyi proved that every integer $N$ can be represented in infinitely many ways in the form $k =\pm1^2\pm2^2\pm \dots\pm m^2$ for some positive integer $m$. We extend their result for representations by cubes and fourth powers. To this end, for each of these two powers, we reduce the problem to that of verifying a finite number of cases..." If your answer is correct, why did Erdos limit his result to just $p=2$? Or Dumitrescu and Xu not mentioning a known general result? Dec 29, 2014 at 21:55
• @TitoPiezasIII I don't know. I'd be happy to find a flaw in the argument, but can't think of one right now Dec 29, 2014 at 22:00
• @gtrrebel This seems like a lovely argument, and I don't see a flaw in it either. Nicely done! :) Dec 29, 2014 at 22:10
• @TitoPiezasIII It looks like this is a significant oversight of Dumitrescu and Xu. According to dorinandrica.ro/files/presentation-INTEGERS-2013.pdf this generalization was already obtained in a 1979 paper of Mitek. I'm starting to wonder if the Erdos-Suranyi result is an exercise in their textbook :). Dec 29, 2014 at 22:54

For $n \leq 27$, I know that almost every $N$ with $0 \leq N < 240$ has at least one representation in the form $$N = \sum_{k=1}^n \pm k^5,$$ and I have a list of those representations. (I'm still missing $n=71$ and $131$ and $133$.)

I wrote a Python script which brute forces all $2^n$ possibilities for $\pm$, but it takes quite a while to run. (And as Erick Wong points out in the comments, this probably isn't really necessary.)

The output and code are a bit long to include in an answer here, so here’s a link to the script and the results on GitHub: https://github.com/alexwlchan/drabbles/tree/master/python/powers

I feel pretty confident that the last two values are attainable, but I won't find them myself. (I can't think of any reason why $71$ and $131$ would be the sole exceptions, but after nearly three hours, I’m stopping the script.)

Now that I've stopped, here are a few comments:

• Brute-forcing all $2^n$ values is really slow. This approach probably isn’t practical for larger values of $N$. You’d want to look for a pattern in what $\pm$ combinations work, and limit your search space accordingly – as Erick Wong suggests in the comments.

• Finding new values was fairly bursty. It could go a long time without finding anything new, and then suddenly a dozen or so values would appear at once. Unfortunately I didn’t record the order, but this might be useful for spotting a pattern in what works and what doesn’t.

• 71 and 131 both have representations of length 29. After reading this post, I ran a search just for these two numbers' depth in the $\pm$-tree, dragging along no extra data. Level 28 has 30305511 members ($n$ and $-n$ counted as one). Level 29 was entered at the 136-second mark. 26 seconds later, 131 and 71 were found (0.07 seconds apart). Almost immediately after, I got a MemoryError.
– Unit
Dec 29, 2014 at 23:40
• @alexwlchan So did your program run to completion? This problem was referenced in a recent thread and it only took a few minutes to run up to $N=168$ with my program, so in the unlikely event that you don't have the answer yet (it isn't clear from the discussion) that part of the problem can be considered complete. Mar 17, 2020 at 3:55

(Not an answer, but too long for a comment.) Courtesy of a useful comment by Zander, we can reduce the number of addends for the $p=4,5$ identities.

$\color{blue}{p=4:}$

Given the following sequences of length $12,16$:

$\quad a_n =1, -1, 1, -1, -1, 1, -1, 1, -1, -1, 1, 1.$

$\quad b_n =-1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1.$

Each of which can be used in sums similar to the post. Then define,

$$s_n =\text{Flatten[{a, Reverse[a], b, Reverse[b]}]}$$

in the syntax of Mathematica. Then,

$$\sum_{n=1}^{56}s_n(x+n)^4=96$$

where $2(12+16) =56$.

$\color{blue}{p=5:}$

Given the following sequences of length $16,20,24,24$:

$\quad a_n =-1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1.$

$\quad b_n=-1, -1, 1, 1, 1, 1, 1, -1, -1, -1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1.$

$\quad c_n=-1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, 1, 1, -1, 1, -1, -1, -1, -1, 1, -1, 1, 1.$

$\quad d_n=-1, -1, 1, 1, 1, 1, -1, -1, -1, 1, 1, -1, 1, 1, 1, -1, -1, -1, -1, 1, -1, -1,-1, -1.$

Each of which can separately can be used in sums. Then define,

$$s_n =\text{Flatten[{-a, Reverse[a], -b, Reverse[b], -c, Reverse[c], d, -Reverse[d]}]}$$

Then,

$$\sum_{n=1}^{168}s_n(x+n)^5=480$$

where $2(16+20+24+24) =168$.

P.S. The $5$th power identity went down from about $70000$ to $7000$ to $1768$ to finally $168$ addends in just 24 hours. MSE certainly is helpful.