10
$\begingroup$

(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$.

$\endgroup$
15
  • $\begingroup$ 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. $\endgroup$
    – user7530
    Dec 29, 2014 at 3:01
  • $\begingroup$ @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.) $\endgroup$ Dec 29, 2014 at 3:31
  • $\begingroup$ This post will interest you: math.stackexchange.com/questions/1079575/… $\endgroup$
    – Pauly B
    Dec 29, 2014 at 4:53
  • $\begingroup$ 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.) $\endgroup$ Dec 29, 2014 at 19:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – Zander
    Dec 29, 2014 at 23:33

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Dec 29, 2014 at 21:55
  • $\begingroup$ @TitoPiezasIII I don't know. I'd be happy to find a flaw in the argument, but can't think of one right now $\endgroup$
    – gtrrebel
    Dec 29, 2014 at 22:00
  • $\begingroup$ @gtrrebel This seems like a lovely argument, and I don't see a flaw in it either. Nicely done! :) $\endgroup$
    – Erick Wong
    Dec 29, 2014 at 22:10
  • 4
    $\begingroup$ @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 :). $\endgroup$
    – Erick Wong
    Dec 29, 2014 at 22:54
1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Unit
    Dec 29, 2014 at 23:40
  • $\begingroup$ @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. $\endgroup$ Mar 17, 2020 at 3:55
0
$\begingroup$

(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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .